The Combinatorics of Object Recognition in Cluttered Environments Using Constrained Search

Abstract
The problem of recognizing rigid objects from noisy sensory data has been successfully attacked in previous work by using a constrained search approach. Empirical investigations have shown the method to be very effective when recognizing and localizing isolated objects, but less effective when dealing with occluded objects where much of the sensory data arises from objects other than the one of interest. When clustering techniques such as the Hough transform are used to isolate likely subspaces of the search space, empirical performance in cluttered scenes improves considerably. This note establishes formal bounds on the combinatorics of this approach. Under some simple assumptions, the expected complexity of recognizing isolated objects is quadratic in the number of model and sensory fragments, but the expected complexity of recognizing objects in cluttered environments is exponential in the size of the correct interpretation. Formal bounds are provided on the efficacy of using the Hough transform to preselect likely subspaces, showing that problem remains exponential, but that in practical terms, the size of the problem is significantly decreased. Keywords: Object recognition, Hough transform, Combinatoric complexity, Image processing.

This publication has 0 references indexed in Scilit: