Assessing distances between pairs of histograms based on relaxed flow constraints

摘要

The example embodiments of the invention notably are directed to a computer-implemented method for assessing distances between pairs of histograms. Each of the histograms is a representation of a digital object; said representation comprises bins associating weights to respective vectors. Such vectors represent respective features of said digital object. This method basically revolves around computing distances between pairs of histograms. That is, for each pair {p, q} of histograms p and q of said pairs of histograms, the method computes a distance between p and q of said each pair {p, q}. In more detail, said distance is computed according to a cost of moving p into q, so as to obtain a flow matrix F, whose matrix elements F_i,j indicate, for each pair {i,j} of bins of p and q, how much weight of a bin i of p has to flow to a bin j of q to move p into q. This is achieved by minimizing a quantity Σ_i,jF_i,j·C_i,j, where C_i,j is a matrix element of a cost matrix C representing said cost. Said quantity Σ_i,jF_i,j·C_i,j is minimized under two flow constraints, which, interestingly, include a relaxed flow constraint F_i,j≤r_i,j, in addition to a complementary flow constraint. The relaxed flow constraint F_i,j≤r_i,j is applied for at least some of the pairs {i,j}, with r_i,j equal to p_i or q_j, where p_i and q_j are weights associated to bins i and j of p and q, respectively, and the complementary flow constraint is either an out-flow constraint Σ_iF_i,j=p_i if r_i,j=q_j or an in-flow constraint Σ_iF_i,j=q_j if r_i,j=p_i. The invention is further directed to related computer program products.