Matching Spikes: A Novel Approach to Feature Matching in Point Sets

Ponente(s): Luis Guillermo Ruiz Velázquez, Edgar Chavez, Miguel Raggi

This paper introduces a novel approach to feature matching and tracking in two-dimensional point sets, with applications in various domains such as computer vision, biometric data, astronomical data, and geographical information systems. Our method associates a sequence of real numbers, termed a "spike," to each point based on its surrounding context. We define a distance metric between spikes, the collapse distance, which allows for efficient comparison and matching. For spikes containing only positive numbers, we provide an algorithm to compute the collapse distance in linear time. Furthermore, we generalize the notion of spike with arbitrary real numbers, the collapse distance becomes a metric akin to the Earth Mover's Distance (EMD), which can be computed by finding the maximum non-crossing matching in a bipartite graph. This generalization of the collapse distance to real-valued spikes offers a new perspective on measuring the dissimilarity between sequences of real numbers with fixed sum, of independent interest in various fields.