An evolutionary optimization approach for 3D human head model classification

ABSTRACT

Classification of 3-D head models based on their shape attributes for subsequent indexing and retrieval are important in many applications, as in the selection and generation of human characters in virtual scenes, and the composition of morphing sequences requiring a qualitatively similar target head model. Simple feature representations are more efficient but may not be adequate for distinguishing the subtly different head model classes. In view of these, we propose an optimization approach based on genetic algorithm (GA) where the original model representation is transformed in such a way that the classification rate is significantly enhanced while retaining the efficiency and simplicity of the original representation. Specifically, based on the Extended Gaussian Image (EGI) representation for 3-D models which summarizes the surface normal orientation statistics, we consider these orientations as a random variable, and proceed to search for an optimal transformation for this variable based on genetic optimization. The resulting transformed distribution for the random variable is then used as the modified classifier inputs. Experiments have shown that the optimized transformation results in a significant improvement in classification results for a large variety of class structures. More importantly, the transformation can be indirectly realized by bin removal and bin count merging in the original histogram, thus retaining the advantage of the original EGI representation.

REFERENCES

• 1: Mihael Ankerst , Gabi Kastenmüller , Hans-Peter Kriegel , Thomas Seidl, Nearest Neighbor Classification in 3D Protein Databases, Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology, p.34-43, August 06-10, 1999
• 2: Mihael Ankerst , Gabi Kastenmüller , Hans-Peter Kriegel , Thomas Seidl, 3D Shape Histograms for Similarity Search and Classification in Spatial Databases, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.207-226, July 20-23, 1999
• 3: Ronen Basri , Daphna Weinshall, Distance Metric Between 3D Models and 2D Images for Recognition and Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.4, p.465-470, April 1996 [doi>10.1109/34.491630]
• 4: R. P. W. Duin, "The Combining Classifier: to Train or Not to Train?", Proc. 16th Intl. Conf. on Pattern Recognition, Quebec City, Canada, vol. 2, 765--770 (2002).
• 5: Thomas Funkhouser , Patrick Min , Michael Kazhdan , Joyce Chen , Alex Halderman , David Dobkin , David Jacobs, A search engine for 3D models, ACM Transactions on Graphics (TOG), v.22 n.1, p.83-105, January 2003 [doi>10.1145/588272.588279]
• 6: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 7: Tin Kam Ho , Jonathan J. Hull , Sargur N. Srihari, Decision Combination in Multiple Classifier Systems, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.1, p.66-75, January 1994 [doi>10.1109/34.273716]
• 8: Masaki Hilaga , Yoshihisa Shinagawa , Taku Kohmura , Tosiyasu L. Kunii, Topology matching for fully automatic similarity estimation of 3D shapes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.203-212, August 2001 [doi>10.1145/383259.383282]
• 9: B. K. P. Horn, "Extended Gaussian Images", Proceedings of the IEEE, Vol. 72, No. 12, pp. 1671--1686, 1984.
• 10: H. H. S. Ip and W. Y. F. Wong, "3D Head Models Retrieval Based on Hierarchical Facial Region Similarity", 15th Vision Interface, Calgary, Canada, pp. 314--319, May, 2002.
• 11: Daniel A. Keim, Efficient geometry-based similarity search of 3D spatial databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.419-430, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 12: J. Kittler , F. M. Alkoot, Sum Versus Vote Fusion in Multiple Classifier Systems, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.1, p.110-115, January 2003 [doi>10.1109/TPAMI.2003.1159950]
• 13: Josef Kittler , Mohamad Hatef , Robert P. W. Duin , Jiri Matas, On Combining Classifiers, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.3, p.226-239, March 1998 [doi>10.1109/34.667881]
• 14: L. I. Kuncheva and L. C. Jain, "Designing Classifier Fusion Systems by Genetic Algorithms", IEEE Trans. on Evolutionary Computation, 4(4), 327--336 (2000).
• 15: Ludmila I. Kuncheva, A Theoretical Study on Six Classifier Fusion Strategies, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.2, p.281-286, February 2002 [doi>10.1109/34.982906]
• 16: Rynson W. H. Lau , Ben Wong, Web-Based 3D Geometry Model Retrieval, World Wide Web, v.5 n.3, p.193-206, 2002 [doi>10.1023/A:1020984612969]
• 17: M. Newall, D. Meny and S. Hoon, "3D Performance Matching for Terminator 3", Sketches and Applications, SIGGRAPH 2003, San Diego, CA, USA, 27--31 July 2003.
• 18: Marcin Novotni , Reinhard Klein, A Geometric Approach to 3D Object Comparison, Proceedings of the International Conference on Shape Modeling & Applications, p.167, May 07-11, 2001
• 19: Robert Osada , Thomas Funkhouser , Bernard Chazelle , David Dobkin, Matching 3D Models with Shape Distributions, Proceedings of the International Conference on Shape Modeling & Applications, p.154, May 07-11, 2001
• 20: Robert Osada , Thomas Funkhouser , Bernard Chazelle , David Dobkin, Shape distributions, ACM Transactions on Graphics (TOG), v.21 n.4, p.807-832, October 2002 [doi>10.1145/571647.571648]
• 21: Eric Paquet , Marc Rioux, Content-Based Access of VRML Libraries, Proceedings of the IAPR International Workshop on Multimedia Information Analysis and Retrieval, p.20-32, August 13-14, 1998
• 22: E. Paquet, M. Rioux, A. Murching, T. Naveen and A. Tabatabai, "Description of Shape Information for 2-D and 3-D Objects", Signal Processing: Image Communication, vol. 16, 103--122 (2000).
• 23: Dietmar Saupe , Dejan V. Vranic, 3D Model Retrieval with Spherical Harmonics and Moments, Proceedings of the 23rd DAGM-Symposium on Pattern Recognition, p.392-397, September 12-14, 2001
• 24: Michael J. Swain , Dana H. Ballard, Color indexing, International Journal of Computer Vision, v.7 n.1, p.11-32, Nov. 1991 [doi>10.1007/BF00130487]
• 25: L. Villalobos, and F. L. Merat, "3D modeling and indexing for CAD-based object recognition", 1994 IEEE Intl. Conf. on Rogbotics and Automation, Vol. 3, pp. 1965--1972, 1994.
• 26: D. V. Vranic, D. Saupe, and J. Richter, "Tools for 3D-object Retrieval: Karhunen-Loeve Transform and Spherical Harmonics", Proc. IEEE 2001 Workshop Multimedia Signal Processing, Cannes, France, pp. 293--298, Oct. 2001.
• 27: D. Zhang and T. Chen, "Efficient Feature Extraction for 2D/3D Objects in Mesh Representation", Proc. Intl. Conf. Image Processing, Thessaloniki, Greece, pp. 935--938, Oct. 2001.
• 28: Yong Zhou , Arthur W. Toga, Efficient Skeletonization of Volumetric Objects, IEEE Transactions on Visualization and Computer Graphics, v.5 n.3, p.196-209, July 1999 [doi>10.1109/2945.795212]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.8 Applications
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

Keywords:
3D head model, evolutionary computation, genetic algorithm, multiple classifier system, pattern classification