Abstract

.We derive a pseudo-metric for weighted point sets.There are numerous situations,for example in the shape description domain,where the individual points in a feature point set have an associated attributc,a wcight.A distancc function that incorporatcs this cxtra information apart from thc points'position can bc vcry uscful for inatching and retrieval purposes.There are two mnain approaches to do this.One approach is to interpret the point sets as fuzzy sets.However,a distance measure for fiizzy sets that is a metric,invariant under rigid motion and rcspccts scaling of thc undcrlying ground distancc,docs not exist.Iu additiou,a Hausdorff-like pseudo-mnetric fails to differeutiate between fuzzy sets with arbitrarily different maximum membership values.The other approach is the Earth Mover's Distance.However,for scts of uncqual total wcights,it gives zcro distancc for arbitrarily diffcrcnt scts,and docs not obcy thc trianglc incquality.In this papcr we derive a distance mncasure,based on weighit trausportation,that is invariant under rigid motion,respects scaling,and obeys the triangle inequality,so that it can be used in efficient database searching.Morcovcr,our pscudo-inctric idcntifics only wcight-scalcd vcrsions of the samne set.We dernonstrate its potential use by testing it on two dif-ferent collections,one of company logos and another one of fish contours