Quadtree-based eigendecomposition for pose estimation in the presence of occlusion and background clutter | Pattern Analysis and Applications Skip to main content
Springer Nature Link
Log in

Quadtree-based eigendecomposition for pose estimation in the presence of occlusion and background clutter

  • Theoretical Advances
  • Published:
Pattern Analysis and Applications Aims and scope Submit manuscript

Abstract

Eigendecomposition-based techniques are popular for a number of computer vision problems, e.g., object and pose estimation, because they are purely appearance based and they require few on-line computations. Unfortunately, they also typically require an unobstructed view of the object whose pose is being detected. The presence of occlusion and background clutter precludes the use of the normalizations that are typically applied and significantly alters the appearance of the object under detection. This work presents an algorithm that is based on applying eigendecomposition to a quadtree representation of the image dataset used to describe the appearance of an object. This allows decisions concerning the pose of an object to be based on only those portions of the image in which the algorithm has determined that the object is not occluded. The accuracy and computational efficiency of the proposed approach is evaluated on 16 different objects with up to 50% of the object being occluded and on images of ships in a dockyard.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Notes

  1. For purely appearance-based techniques, no modeling is required and thus no feature extraction/selection needs to be performed. Hence these techniques can be applied to any class of objects and can be effectively used in a wide variety of applications [23].

  2. Note that when the actual object location is not of rank one, the rank one candidate is frequently far from the correct location (due to occlusion) so that local optimization techniques such as gradient descent [32] are not effective.

  3. Specifically, the image data matrices corresponding to the training sub-images, whose rank is below 12, are automatically discarded.

  4. Empirical results showed that using a constant subspace dimension at every sub-image performs consistently better than using a constant energy recovery ratio. The main reason behind this is that a constant subspace dimension tends to make the energy recovery ratio increase as the algorithm searches further down the quadtree.

  5. The generation of the occluded test images in this manner can induce artifacts, like large step edges along the boundaries, however, our results indicate that these artifacts do not affect the performance of the algorithm.

  6. We elected not to use one of the “standard” object data sets, like COIL-100 [49], COIL-10 [50], SOIL-47 [51], and ALOI [52], because they only contain 72 orientations per object.

  7. A video sequence of ship images with resolution of 720 × 1,280 pixels each was provided by the National Imagery and Mapping Agency.

  8. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the US Government.

References

  1. Fukunaga K (1990) Introduction to Statistical Pattern Recognition, 2nd edn. Academic, London

    MATH  Google Scholar 

  2. Martinez AM, Kak AC (2001) PCA versus LDA. IEEE Trans PAMI 23(2):228–233

    Google Scholar 

  3. Sirovich L, Kirby M (1987) Low-dimensional procedure for the characterization of human faces. J Opt Soc Am 4(3):519–524

    Article  Google Scholar 

  4. Kirby M, Sirovich L (1990) Application of the Karhunen–Loeve procedure for the characterization of human faces. IEEE Trans PAMI 12(1):103–108

    Google Scholar 

  5. Turk M, Pentland A (1991) Eigenfaces for recognition. J Cogn Neurosci 3(1):71–86

    Article  Google Scholar 

  6. Belhumeur PN, Hespanha JP, Kriegman DJ (1997) Eigenfaces vs. fisherfaces: Recognition using class specific linear projection. IEEE Trans PAMI 19(7):711–720

    Google Scholar 

  7. Brunelli R, Poggio T (1993) Face recognition: Features versus templates. IEEE Trans PAMI 15(10):1042–1052

    Google Scholar 

  8. Pentland A, Moghaddam B, Starner T (1994) View-based and modular eigenspaces for face recognition. In: Proceedings of IEEE conference computer vision and pattern recognition. Seattle, WA, pp 84–91

  9. Yang MH, Kriegman DJ, Ahuja N (2002) Detecting faces in images: A survey. IEEE Trans PAMI 24(1):34–58

    Google Scholar 

  10. Murase H, Sakai R (1996) Moving object recognition in eigenspace representation: Gait analysis and lip reading. Pattern Recogn Lett 17(2):155–162

    Article  Google Scholar 

  11. Chiou G, Hwang J-N (1997) Lipreading from color video. IEEE Trans Image Process 6(8):1192–1195

    Article  Google Scholar 

  12. Murase H, Nayar SK (1994) Illumination planning for object recognition using parametric eigenspaces. IEEE Trans PAMI 16(12):1219–1227

    Google Scholar 

  13. Huang CY, Camps OI, Kanungo T (1997) Object recognition using appearance-based parts and relations. In: Proceedings of IEEE conference on computer vision and pattern recognition. San Juan, PR, USA, pp 877–883

  14. Campbell RJ, Flynn PJ (1999) Eigenshapes for 3D object recognition in range data. In: Proceedings of IEEE conference on computer vision and pattern recognition. Fort Collins, CO, USA, pp 505–510

  15. Jogan M, Leonardis A (2000) Robust localization using eigenspace of spinning-images. In: Proceedings of IEEE workshop omnidirectional vision. Hilton Head Island, South Carolina, USA, pp 37–44

  16. Borgefors G (1988) Hierarchical chamfer matching: A parametric edge matching algorithm. IEEE Trans PAMI 10(6):849–865

    Google Scholar 

  17. Yoshimura S, Kanade T (1994) Fast template matching based on the normalized correlation by using multiresolution eigenimages. In: 1994 IEEE workshop motion of non-rigid and articulated objects, Austin, Texas, pp 83–88

  18. Winkeler J, Manjunath BS, Chandrasekaran S (1999) Subset selection for active object recognition. In: Proceedings of IEEE conference computer vision and pattern recognition. Fort Collins, Colorado, USA, pp 511–516

  19. Martinez AM, Vitria J (2001) Clustering in image space for place recognition and visual annotations for human–robot interaction. IEEE Trans Syst Man Cybern 31(5):669–682

    Article  Google Scholar 

  20. Crowley JL, Pourraz F (2001) Continuity properties of the appearance manifold for mobile robot position estimation. Image Vis Comput 19(11):741–752

    Article  Google Scholar 

  21. Nayar SK, Murase H, Nene SA (1994) Learning, positioning, and tracking visual appearance. In: Proceedings of IEEE international conference on robotics and automation, San Diego, CA, USA, pp 3237–3246

  22. Black MJ, Jepson AD (1998) Eigentracking: robust matching and tracking of articulated objects using a view-based representation. Int J Comput Vis 26(1):63–84

    Article  Google Scholar 

  23. Murase H, Nayar SK (1995) Visual learning and recognition of 3-D objects from appearance. Int J Comput Vis 14(1):5–24

    Article  Google Scholar 

  24. Murase H, Nayar SK (1997) Detection of 3D objects in cluttered scenes using hierarchical eigenspace. Pattern Recogn Lett 18(4):375–384

    Article  Google Scholar 

  25. Nayar SK, Nene SA, Murase H (1996) Subspace method for robot vision. IEEE Trans Rob Autom 12(5):750–758

    Article  Google Scholar 

  26. Moghaddam B, Pentland A (1997) Probabilistic visual learning for object representation. IEEE Trans PAMI 19(7):696–710

    Google Scholar 

  27. Chang C-Y, Maciejewski AA, Balakrishnan V (2000) Fast eigenspace decomposition of correlated images. IEEE Trans Image Process 9(11):1937–1949

    Article  MathSciNet  MATH  Google Scholar 

  28. Martinez AM (2002) Recongnizing imprecisely localized, partially occluded, and expression varient faces from a single sample per class. IEEE Trans PAMI 24(6):748–763

    Google Scholar 

  29. Nayar SK, Murase H (1995) Image spotting of 3D objects using parametric eigenspace representation. In: Proceedings of 9th Scandinavian conference on image analysis, pp 325–332

  30. Edward J, Murase H (1997) Appearance matching of occluded objects using coarse-to-fine adaptive masks. In: Proceedings of IEEE conference on computer vision and pattern recognition, Los Alamitos, CA, USA, pp 533–539

  31. Rao RPN (1997) Dynamic appearance-based recognition. In: Proceedings of IEEE conference on computer vision and pattern recognition, San Juan, PR, USA, pp 540–546

  32. Krumm J (1996) Eigenfeatures for planar pose measurement of partially occluded objects. In: Proceedings of IEEE conference on computer vision and pattern recognition, Los Alamitos, CA, USA, pp 55–60

  33. Ohba K, Ikeuchi K (1997) Detectability, uniqueness, and reliability of eigen windows for stable verification of partially occluded objects. IEEE Trans PAMI 19(9):1043–1048

    Google Scholar 

  34. Leonardis A, Bischof H (2000) Robust recognition using eigenimages. Comput Vis Image Understand 78(1):99–118

    Article  Google Scholar 

  35. Huttenlocher DP, Lilien RH, Olson CF (1999) View-based recognition using an eigenspace approximation to the Hausdorff measure. IEEE Trans PAMI 21(9):951–955

    Google Scholar 

  36. Wang Z, Ben-arie J (2001) Detection and segmentation of generic shapes based on affine modeling of energy in eigenspace. IEEE Trans Image Process 10(11):1621–1629

    Article  MATH  Google Scholar 

  37. Bischof H, Leonardis A (1998) Robust recognition of scaled eigenimages through a hierarchical approach. In: Proceedings of IEEE conference on computer vision and pattern recognition, Santa Barbara, CA, USA, pp 664–670

  38. Schneiderman H, Kanade T (2000) A histogram-based method for detection of faces and cars. In: Proceedings of IEEE international conference on image processing, Vancouver, BC, pp 504–507

  39. Mohan A, Papageorgiou C, Poggio T (2001) Example-based object detection in images by components. IEEE Trans PAMI 23(4):349–361

    Google Scholar 

  40. Stauffer C, Grimson E (2001) Similarity templates for detection and recognition. In: Proceedings of IEEE conference on computer vision and pattern recognition, Kauai, HI, pp I221–I228

  41. Lee DD, Seung HS (1999) Learning the parts of objects by non-negative matrix factorization. Lett Nat 401(6755):788–791

    Article  Google Scholar 

  42. Guillamet D, Vitria J (2003) Evaluation of distance metrics for recognition based on non-negative matrix factorization. Pattern Recogn Lett 24(9–10):1599–1605

    Article  MATH  Google Scholar 

  43. Li SZ, Hou XW, Zhang HJ, Cheng QS (2001) Learning spatially localized, parts-based representation. In: Proceedings of IEEE conference computer vision and pattern recognition, Kauai, HI, pp I207–I212

  44. Jugessur D, Dubek G (2000) Local appearance for robust object recognition. In: Proceedings of IEEE conference on computer vision and pattern recognition, Hilton Head Island, SC, USA, pp 834–839

  45. Nene SA, Nayar SK (1997) A simple algorithm for nearest neighbor search in high dimensions. IEEE Trans PAMI 19(9):989–1003

    Google Scholar 

  46. Kakarala R, Ogunbona PO (2001) Signal analysis using a multiresolution form of the singular value decomposition. IEEE Trans Image Process 10(5):724–735

    Article  MathSciNet  MATH  Google Scholar 

  47. Uenohara M, Kanade T (1997) Use of Fourier and Karhunen–Loeve decomposition for fast pattern matching with a large set of templates. IEEE Trans PAMI 19(8):891–898

    Google Scholar 

  48. Ohba K, Ikeuchi K (1996) Recognition of the multi specularity objects for bin-picking task. In: Proceedings of IEEE international conference on intelligent robots and systems, Osaka, Japan, pp 1440–1447

  49. Nene SA, Nayar SK, Murase H (1996) Columbia object image library (COIL-100), http://www.cs.columbia.edu/cave/research/softlib/coil-100.html. In: Technical report CUCS-006-96, Columbia University, 1996

  50. Nene SA, Nayar SK, Murase H (1996) Columbia object image library (COIL-20), http://www.cs.columbia.edu/cave/research/softlib/coil-20.html. In: Technical report CUCS-005-96, Columbia University, 1996

  51. Koubaroulis D, Matas J, Kittler J (2002) Evaluating colour-based object recognition algorithms using the SOIL-47 database. In: Proceedings of Asian conference on computer vision, Melbourne, Australia, pp 840–845

  52. Geusebroek JM, Burghouts GJ, Smeulders AWM (2004) The Amsterdam library of object images. Int J Comput Vis 61(1):103–112

    Article  Google Scholar 

  53. Chang C-Y (1999) Eigenspace methods for correlated images. PhD Dissertation, Purdue University, USA

Download references

Acknowledgments

This work was supported in part by the Office of Naval Research under contract no. N00014-97-1-0640, the National Imagery and Mapping Agency under contract no. NMA201-00-1-1003, through collaborative participation in the Robotics Consortium sponsored by the US Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-01-2-0012, and the Missile Defense Agency under the contract no. HQ0006-05-C-0035. The US Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation thereon. A preliminary version of this work was presented at the IEEE/RSJ International Conference on Intelligent Robots and Systems held at Maui, Hawaii, October 29–November 3, 2001.

Author information

Authors and Affiliations

  1. Energid Technologies, 124 Mount Auburn Street, Suite 200, North Cambridge, MA, 02138, USA

    Chu-Yin Chang

  2. Department of Electrical and Computer Engineering, Colorado State University, Fort Collins, CO, 80523-1373, USA

    Anthony A. Maciejewski & Kishor Saitwal

  3. Department of Electrical and Computer Engineering, Purdue University, West Lafayette, IN, 47907-1285, USA

    Venkataramanan Balakrishnan

  4. Department of Electrical and Computer Engineering, Florida A&M—Florida State University, Tallahassee, FL, 32310-6046, USA

    Rodney G. Roberts

Authors
  1. Chu-Yin Chang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Anthony A. Maciejewski
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Venkataramanan Balakrishnan
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Rodney G. Roberts
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Kishor Saitwal
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chang, CY., Maciejewski, A.A., Balakrishnan, V. et al. Quadtree-based eigendecomposition for pose estimation in the presence of occlusion and background clutter. Pattern Anal Applic 10, 15–31 (2007). https://doi.org/10.1007/s10044-006-0046-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10044-006-0046-6

Keywords

Search

Navigation