A FAST GENERALIZED 2-DIMENSIONAL HEAP FOR HAUSDORFF AND EARTH MOVER'S DISTANCE

摘要

A method of measupng distance between two distributions of data points in a space is described The distances between data points are ordered in a plurality of heaps stored within 2-D heaps which is constructed by giving heap structure to a list of one-dimensional heaps The maximum of the 2-D heaps are compared to determine the Hausdorff distance which is the greater of the maximums The corresponding heaps are removed from their respective 2-D heaps The Hausdorff distance is utilized in a set of calculations to generate an EMD path Determining the Hausdorff distance and generating the EMD is repeated until no more earths and no more holes remain at which time the similanty of the plurality of images is determined.