{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:41:33Z","timestamp":1777714893683,"version":"3.51.4"},"reference-count":39,"publisher":"SAGE Publications","issue":"6","license":[{"start":{"date-parts":[[1989,12,1]],"date-time":"1989-12-01T00:00:00Z","timestamp":628473600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[1989,12]]},"abstract":"<jats:p>An important task in computer vision is the recognition of partially visible two-dimensional objects in a gray scale image. Recent works addressing this problem have attempted to match spatially local features from the image to features generated by models of the objects. However, many algo rithms are considerably less efficient than they might be, typ ically being O(IN) or worse, where I is the number offeatures in the image and N is the number of features in the model set. This is invariably due to the feature-matching portion of the algorithm. In this paper we discuss an algorithm that significantly improves the efficiency offeature matching. In addition, we show experimentally that our recognition algo rithm is accurate and robust. Our algorithm uses the local shape of contour segments near critical points, represented in slope angle-arclength space (\u03b8-s space), as fundamental fea ture vectors. These feature vectors are further processed by projecting them onto a subspace in \u03b8-s space that is obtained by applying the Karhunen-Lo\u00e8ve expansion to all such fea tures in the set of models, yielding the final feature vectors. This allows the data needed to store the features to be re duced, while retaining nearly all information important for recognition. The heart of the algorithm is a technique for performing matching between the observed image features and the precomputed model features, which reduces the runtime complexity from O(IN) to O(I log I + I log N), where I and N are as above. The matching is performed using a tree data structure, called a kD tree, which enables multidi mensional searches to be performed in O(log) time.<\/jats:p>","DOI":"10.1177\/027836498900800608","type":"journal-article","created":{"date-parts":[[2007,3,4]],"date-time":"2007-03-04T20:24:06Z","timestamp":1173039846000},"page":"110-131","source":"Crossref","is-referenced-by-count":12,"title":["Efficient Recognition of Partially Visible Objects Using a Logarithmic Complexity Matching Technique"],"prefix":"10.1177","volume":"8","author":[{"given":"Paul G.","family":"Gottschalk","sequence":"first","affiliation":[{"name":"Robotics Research Laboratory University of Michigan Ann Arbor, Michigan 48109"}]},{"given":"Jerry L.","family":"Turney","sequence":"additional","affiliation":[{"name":"Robotics Research Laboratory University of Michigan Ann Arbor, Michigan 48109"}]},{"given":"Trevor N.","family":"Mudge","sequence":"additional","affiliation":[{"name":"Robotics Research Laboratory University of Michigan Ann Arbor, Michigan 48109"}]}],"member":"179","published-online":{"date-parts":[[1989,12,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1037\/h0054663"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1986.4767751"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(81)90009-1"},{"key":"atypb4","first-page":"67","author":"Ballard, D.H.","year":"1985","journal-title":"Proc. IEEE Conf. Pattern Recog. Image Process"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/356789.356797"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1984.4767499"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/0734-189X(85)90002-7"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(78)90025-0"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1177\/027836498200100304"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1147\/sj.41.0025"},{"key":"atypb11","volume-title":"Finding edges and lines in images","author":"Canny, J.F.","year":"1983"},{"key":"atypb12","first-page":"481","author":"Chien, C.H.","year":"1987","journal-title":"Proc. IEEE First Int. Conf. Comp. Vision"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/6462.6464"},{"key":"atypb14","first-page":"176","author":"Cowan, C.K.","year":"1984","journal-title":"First Conf. AI Appl"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1986.4767752"},{"key":"atypb16","first-page":"168","author":"Freeman, H.","year":"1977","journal-title":"Proc. IEEE Conf. Pattern Recog. Image Process"},{"key":"atypb17","volume-title":"Syntactic Methods in Pattern Recognition","author":"Fu, K.S.","year":"1974"},{"key":"atypb18","first-page":"94","author":"Goad, C.","year":"1983","journal-title":"Proc. Image Understanding Workshop"},{"key":"atypb19","first-page":"46","author":"Gottschalk, P.G.","year":"1988","journal-title":"Proc. SPIE: Intell. Robots Comp. Vision"},{"key":"atypb20","first-page":"1582","author":"Gottschalk, P.G.","year":"1987","journal-title":"Proc. IEEE Conf. Robot. Automat"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1987.4767935"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1109\/JRA.1986.1087031"},{"key":"atypb23","first-page":"55","author":"Koch, M.W.","year":"1985","journal-title":"Proc. IEEE Conf. Pattern Recog. Image Process"},{"key":"atypb24","first-page":"1407","author":"Lamdan, Y.","year":"1988","journal-title":"Proc. IEEE Conf. Robot. Automat"},{"issue":"1","key":"atypb25","first-page":"58","volume":"1","author":"Lowe, D.G.","year":"1987","journal-title":"Int. J. Comp. Vision"},{"issue":"7","key":"atypb26","first-page":"18","volume":"78","author":"Mattill, J.","year":"1976","journal-title":"Technol. Rev"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1977.1674917"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1017\/S0263574700015083"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-88304-0"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1978.1675046"},{"key":"atypb31","unstructured":"Rosenfeld, A., and Kak, A.C. 1976 Digital Picture Processing New York : Academic Press, pp. 109-123."},{"key":"atypb32","first-page":"676","author":"Segen, J.","year":"1983","journal-title":"Proc. Soc. Photo-optical In-strum. Eng. Cambridge Symp. Robot Vision and Sensory Controls"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1177\/027836498600500403"},{"key":"atypb34","first-page":"241","author":"Tropf, H.","year":"1980","journal-title":"Fifth IEEE Int. Conf. Pattern Recog"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1049\/ip-e.1987.0002"},{"key":"atypb36","volume-title":"Recognition of partially occluded parts","author":"Turney, J.L.","year":"1986"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1985.4767680"},{"key":"atypb38","first-page":"4-21","author":"Turney, J.L.","year":"1986","journal-title":"Vision 86 Conf. Proc"},{"key":"atypb39","volume-title":"Analysis of scenes containing several occluding curvilinear objects","author":"Yam, K.R.","year":"1980"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836498900800608","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836498900800608","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:13:14Z","timestamp":1777457594000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/027836498900800608"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,12]]},"references-count":39,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1989,12]]}},"alternative-id":["10.1177\/027836498900800608"],"URL":"https:\/\/doi.org\/10.1177\/027836498900800608","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,12]]}}}