Object instance recognition using triplets of feature symbols

Larry Zitnick, Jie Sun, Rick Szeliski, Simon Winder

MSR-TR-2007-53 |

Known object recognition is the task of recognizing specific objects, such as cereal boxes or soda cans. Millions of such objects exist, and finding a computationally feasible method for recognition can be difficult. Ideally, the computational costs should scale with the complexity of the testing image, and not the size of the object database. To accomplish this goal we propose a method for detection and recognition based on triplets of feature descriptors. Each feature is given a label based on a modified K-means clustering algorithm. Object matching is then done by inverse lookup within a table of possible triplets. The ambiguity of the matches is further reduced by having each triplet vote on its proposed object center. For planar objects, the proposed object centers should cluster at a single point. In general, assuming orthographic projection, the proposed centers will lie along a line. If enough triplets are in agreement on a specific object’s center, the object is labeled as detected. Our algorithm has been evaluated on a new database with 118 training objects and various testing scenarios.