Part-based models

<h2 id="non-constellation-models">Non-constellation models</h2>
	Many overlapping ideas are included under the title part-based models even after having excluded those models of the constellation variety. The uniting thread is the use of small parts to build up to an algorithm that can detect/recognize an item (face, car, etc.)
	Early efforts, such as those by Yuille, Hallinan and Cohen<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> sought to detect facial features and fit deformable templates to them. These templates were mathematically defined outlines which sought to capture the position and shape of the feature. Yuille, Hallinan and Cohen's algorithm does have trouble finding the <a href="/facts/Maxima_and_minima/ADlgnyzV">global minimum</a> fit for a given model and so templates did occasionally become mismatched.
Later efforts such as those by Poggio and Brunelli<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> focus on building specific detectors for each feature. They use successive detectors to estimate scale, position, etc. and narrow the search field to be used by the next detector. As such it is a part-based model, however, they seek more to recognize specific faces rather than to detect the presence of a face. They do so by using each detector to build a 35 element vector of characteristics of a given face. These characteristic can then be compared to recognize specific faces, however cut-offs can also be used to detect whether a face is present at all.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
Cootes, Lanitis and Taylor<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> build on this work in constructing a 100 element representation of the primary features of a face. The model is more detailed and robust however, given the additional complexity (100 elements compared to 35) this might be expected. The model essentially computes deviations from a mean face in terms of shape, orientation and gray level. The model is matched by the minimization of an <a href="/facts/Error_function/Ca2H7pGr">error function</a>. These three classes of algorithms naturally fall within the scope of <a href="/facts/Template_matching/sE13sU8W">template matching</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
Of the non-constellation perhaps the most successful is that of Leibe and Schiele.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> Their algorithm finds templates associated with positive examples and records both the template (an average of the feature in all positive examples where it is present) and the position of the center of the item (a face for instance) relative to the template. The algorithm then takes a test image and runs an interest point locater (hopefully one of the <a href="/facts/Scale_invariance/S96sxg2R">scale invariant</a> variety). These interest points are then compared to each template and the probability of a match is computed. All templates then cast votes for the center of the detected object proportional to the probability of the match, and the probability the template predicts the center. These votes are all summed and if there are enough of them, well enough clustered, the presence of the object in question (i.e. a face or car) is predicted.
The algorithm is effective because it imposes much less constellational rigidity the way the constellation model does. Admittedly the constellation model can be modified to allow for occlusions and other large abnormalities but this model is naturally suited to it. Also it must be said that sometimes the more rigid structure of the constellation is desired.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Computer_vision/Tl2Yyk66">Computer vision</a></li>
<li><a href="/facts/Template_matching/sE13sU8W">Template matching</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Fischler, M.A.; Elschlager, R.A. (1973). "The Representation and Matching of Pictorial Structures". IEEE Transactions on Computers. C-22: 67–92. doi:10.1109/T-C.1973.223602. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Fergus, R.; Perona, P.; Zisserman, A. (2003). Object class recognition by unsupervised scale-invariant learning. IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Vol. 2. pp. II–264. doi:10.1109/CVPR.2003.1211479. ISBN 0-7695-1900-8. <a href="0-7695-1900-8" target="_blank">0-7695-1900-8</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Yuille, Alan L.; Hallinan, Peter W.; Cohen, David S. (1992). "Feature extraction from faces using deformable templates". International Journal of Computer Vision. 8 (2): 99. doi:10.1007/BF00127169. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Brunelli, R.; Poggio, T. (1993). "Face recognition: Features versus templates". IEEE Transactions on Pattern Analysis and Machine Intelligence. 15 (10): 1042. doi:10.1109/34.254061. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Simonite, Tom. "Photo Algorithms ID White Men Fine—Black Women, Not So Much". Wired. ISSN 1059-1028. Retrieved 2023-04-17. <a href="https://www.wired.com/story/photo-algorithms-id-white-men-fineblack-women-not-so-much/" target="_blank">https://www.wired.com/story/photo-algorithms-id-white-men-fineblack-women-not-so-much/</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Lanitis, A.; Taylor, C.J.; Cootes, T.F. (1995). A unified approach to coding and interpreting face images. IEEE International Conference on Computer Vision. p. 368. doi:10.1109/ICCV.1995.466919. ISBN 0-8186-7042-8. <a href="0-8186-7042-8" target="_blank">0-8186-7042-8</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Brunelli, R. (2009). Template Matching Techniques in Computer Vision: Theory and Practice. Wiley. ISBN 978-0-470-51706-2. <a href="978-0-470-51706-2" target="_blank">978-0-470-51706-2</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Leibe, Bastian; Leonardis, Aleš; Schiele, Bernt (2007). "Robust Object Detection with Interleaved Categorization and Segmentation". International Journal of Computer Vision. 77 (1–3): 259–289. CiteSeerX 10.1.1.111.464. doi:10.1007/s11263-007-0095-3. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Leibe, Bastian; Leonardis, Ales; Schiele, Bernt (2006). "An Implicit Shape Model for Combined Object Categorization and Segmentation". Toward Category-Level Object Recognition. Lecture Notes in Computer Science. Vol. 4170. p. 508. CiteSeerX 10.1.1.5.6272. doi:10.1007/11957959_26. ISBN 978-3-540-68794-8. <a href="978-3-540-68794-8" target="_blank">978-3-540-68794-8</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
</ol>

Part-based models open-in-new

Part-based models