Assessing distances between pairs of histograms based on relaxed flow constraints

Abstract

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 Findicate, 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 ΣF·C, where Cis a matrix element of a cost matrix C representing said cost. Said quantity ΣF·Cis minimized under two flow constraints, which, interestingly, include a relaxed flow constraint F≤r, in addition to a complementary flow constraint. The relaxed flow constraint F≤ris applied for at least some of the pairs {i,j}, with requal to por q, where pand qare weights associated to bins i and j of p and q, respectively, and the complementary flow constraint is either an out-flow constraint ΣF=pif r=qor an in-flow constraint ΣF=qif r=p. The invention is further directed to related computer program products.