Renato O. Stehling, Mario A. Nascimento and Alexandre
X. Falcão,
MiCRoM: A Metric Distance to Compare Segmented Images,
In Shi-Kuo Chang, Zen Chen and Suh-Yin Lee eds., Proceedings of the 5th International Conference on Recent
Advances in Visual Information Systems (VISUAL 2002),
Hsin Chu, Taiwan, No. 2314 in Lecture Notes in Computer Science, pp. 12-23, Springer-Verlag, March 11-13 2002.Recently, several content-based image retrieval (CBIR) systems that make use of segmented images have been proposed. In these systems, images are segmented and represented as a set of regions, and the distance between images is computed according to the visual features of their regions. A major problem of existing distance functions used to compare segmented images is that they are not metrics. Hence, it is not possible to exploit filtering techniques and/or access methods to speedup query processing, as both techniques make extensive use of the triangular inequality property - one of the metric axioms. In this work, we propose MiCRoM (Minimum-Cost Region Matching), an effective metric distance which models the comparison of segmented images as a minimum-cost network flow problem. To our knowledge, this is the first time a true metric distance function is proposed to evaluate the distance between segmented images. Our experiments show that MiCRoM is at least as effective as existing non-metric distances. Moreover, we have been able to use the recently proposed Omni-sequential filtering technique, and have achieved nearly 2/3 savings in retrieval/query processing time.