The combinatorics of object recognition in cluttered environments using constrained search.

*(English)*Zbl 0717.68084Summary: 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. We establish formal bounds on the combinatorics of this approach. Under some simple assumptions, we show that the expected complexity of recognizing isolated objects is quadratic in the number of model and sensory fragments, but that the expected complexity of recognizing objects in cluttered environments is exponential in the size of the correct interpretation. We also provide formal bounds on the efficacy of using the Hough transform to preselect likely subspaces, showing that the problem remains exponential, but that in practical terms the size of the problem is significantly decreased.

##### MSC:

68T10 | Pattern recognition, speech recognition |

PDF
BibTeX
XML
Cite

\textit{W. E. L. Grimson}, Artif. Intell. 44, No. 1--2, 121--165 (1990; Zbl 0717.68084)

Full Text:
DOI

##### References:

[1] | Ayache, N.J.; Faugeras, O.D., HYPER: A new approach for the recognition and positioning of two-dimensional objects, IEEE trans. pattern anal. Mach. intell., 8, 44-54, (1986) |

[2] | Ballard, D.H., Generalizing the Hough transform to detect arbitrary patterns, Pattern recogn., 13, 2, 111-122, (1981) · Zbl 0454.68112 |

[3] | Bolles, R.C.; Cain, R.A., Recognizing and locating partially visible objects: the local-feature focus method, Int. J. rob. res., 1, 3, 57-82, (1982) |

[4] | Bolles, R.C.; Horaud, P.; Hannah, M.J., 3DPO: A three-dimensional part orientation system, (), 413-424 |

[5] | Freuder, E.C., Synthesizing constraint expressions, Commun. ACM, 21, 958-966, (1978) · Zbl 0386.68065 |

[6] | Freuder, E.C., A sufficient condition for backtrack-free search, J. ACM, 29, 24-32, (1982) · Zbl 0477.68063 |

[7] | Gaschnig, J., Performance measurement and analysis of certain search algorithms, () |

[8] | Grimson, W.E.L., The combinatorics of local constraints in model-based recognition and localization from sparse data, J. ACM, 33, 658-686, (1986) |

[9] | Grimson, W.E.L., Sensing strategies for disambiguating among multiple objects in known poses, IEEE J. rob. autom., 2, 196-213, (1986) |

[10] | Grimson, W.E.L., On the recognition of curved objects, MIT AI lab memo 983, (1987), Cambridge, MA · Zbl 1046.68809 |

[11] | Grimson, W.E.L., Recognition of object families using parameterized models, (), 93-101 |

[12] | Grimson, W.E.L.; Lozano-Pérez, T., Model-based recognition and localization from sparse range or tactile data, Int. J. rob. res., 3, 3, 3-35, (1984) |

[13] | Grimson, W.E.L.; Lozano-Pérez, T., Localizing overlapping parts by searching the interpretation tree, IEEE trans. pattern anal. Mach. intell., 9, 469-482, (1987) |

[14] | Haralick, R.M.; Elliott, G.L., Increasing tree search efficiency for constraint satisfaction problems, Artificial intelligence, 14, 263-313, (1980) |

[15] | Haralick, R.M.; Shapiro, L.G., The consistent labeling problem, IEEE trans. pattern anal. machine intell., 1, 173-184, (1979) · Zbl 0418.68080 |

[16] | Hough, P.V.C., Methods and means for recognizing complex patterns, (1962), US Patent 3069654 · Zbl 0032.23901 |

[17] | Jacobs, D., The use of grouping in visual object recognition, () |

[18] | Mackworth, A.K., Consistency in networks of constraints, Artificial intelligence, 8, 99-118, (1977) · Zbl 0341.68061 |

[19] | Mackworth, A.K.; Freuder, E.C., The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artificial intelligence, 25, 65-74, (1985) |

[20] | Merlin, P.M.; Farber, D.J., A parallel mechanism for detecting curves in pictures, IEEE trans. comput., 13, 96-98, (1975) · Zbl 0293.68076 |

[21] | Montanari, U., Networks for constraints: fundamental properties and applications to picture processing, Inf. sci., 7, 95-132, (1974) · Zbl 0284.68074 |

[22] | Murray, D.W., Model-based recognition using 3d shape alone, Comput. vision graph. image process., 40, 250-266, (1987) |

[23] | Nudel, B., Consistent-labeling problems and their algorithms: expected-complexities and theory-based heuristics, Artificial intelligence, 21, 135-178, (1983) |

[24] | Porrill, J.; Pollard, S.B.; Pridmore, T.P.; Bowen, J.B.; Mayhew, J.E.W.; Frisby, J.P., TINA: the Sheffield AIVRU vision system, (1987), University of Sheffield AIVRU Memo Sheffield, England |

[25] | Sklansky, J., On the Hough technique for curve detection, IEEE trans. comput., 27, 923-926, (1978) · Zbl 0398.68040 |

[26] | van Hove, P., Model-based silhouette recognition, (), 88-93 |

[27] | Waltz, D., Understanding line drawings of scenes with shadows, (), 19-91 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.