IIAE CONFERENCE SYSTEM, The 1st IEEE/IIAE International Conference on Intelligent Systems and Image Processing 2013 (ICISIP2013)

Font Size: 
Fast sphere detection based on polytope method using one-dimensional histogram
Shota Nakashima, Hiroyuki Nakamoto, Shenglin Mu, Yuhki Kitazono, Huimin Lu, Kanya Tanaka

Last modified: 2013-10-01


We propose a method for fast extraction of sphere. Basically, main algorithms of the extraction in 3D figure are the same as 2D method we reported in previous research. The proposed method utilizes the one-dimensional histogram as search space, and the polytope method which is one of the minimization algorithms for search parameters in target figure. The histogram has two characteristics: (a) The distribution of the histogram changes if the parameters of representing the sphere changes. (b) The value of highest frequency of histogram becomes maximum if the best parameters are obtained. Therefore, the maximum value of highest frequency of histogram is searched to obtain the best parameters of the sphere by using the polytope method. By using the polytope method, the proposed method can extract the sphere from 3D vertex data without a large memory space or long processing time.


3D pattern matching, polytope method, figure detection


(1)     Manabu Hashimoto and Kazuhiko Sumi : “3-D Object Recognition Based on Integration of Range Image and Gray-scale Image”, Proceedings of The British Machine Vision Conference 2001, pp. 253-262, 2001

(2)     Jamie Shotton, Andrew Fitzgibbon, Mat Cook, Toby sharp, Mark finocchio, Richard Moore, Alex Kipman, and Andrew Blake : “Real-Time Human Pose Recognition in Parts from Single Depth Images”, Proceedings of Computer Vision and Pattern Recognition 2011, 2011

(3)     Hiroshi Kimura, Tomoyuki Horiuchi, and Katsushi Ikeuchi : “Human Robot Cooperation for Mechanical Assembly using Cooperative Vision System”, 2nd Int. Workshop on Cooperative Distributed Vision, pp.213-228, 1998

(4)     Yue Liu, Yuhki Kitazono, Shota Nakashima, Lifeng Zhang, and Seiichi Serikawa : “Proposal of Driver Symbol Mark Detection using One-Dimensional Histogram Figure Extraction Method”, Applied Mechanics and Materials, Vol.36, pp.376-380, 2010

(5)     Shota Nakashima, Makoto Miyauchi, and Seiichi Serikawa : “Proposal of a method to extract of arbitrary figures using one-dimensional histogram”, Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol.13, No.4, pp.380-385, 2009

(6)     Shota Nakashima and Seiichi Serikawa : “Proposal of a method to extract straight line and circle using one-dimensional histogram”, Journal of Artificial Life and Robotics, Vol.13, No.1, pp.306-310, 2008

(7)     Yoshihiro Okada : “3D Model Matching Based On Silhouette Image Matching”, Proceedings of Circuits/Systems, Computers and Communications 2002, WSEAS Press, pp. 380-385, 2002

(8)     Louis-Philippe Morency, Ali Rahimi, and Trevor Darrell : “Fast 3D Model Acquisition from Stereo Images”, Proceedings of 3D Processing • Visualization • Transmission, pp. 172-176, 2002

(9)     Lijing Bu and Zhengpeng Zhang : “Application Of Point Clouds from Terrestrial 3D Laser Scanner for Deformation Measurements”, Proceedings of International Society for Photogrammetry and Remote Sensing, Vol. XXXVII, Part B5, pp.545-548, 2008

(10) Andrew Schworer and Peter Hovey : “Newton-Raphson Versus Fisher Scoring Algorithms in Calculating Maximum Likelihood Estimates”, Proceedings of Undergraduate Mathematics Day, 2004

(11) Shota Nakashima, Hiroyuki Nakamoto, Yuhki Kitazono, Lifeng Zhang and Seiichi Serikawa : “A Method for sphere Detection Using One-Dimensional Histogram and Polytope Method”, Applied Mechanics and Materials, Vol.103, pp.628-632, 2011

(12) Haruhiko Okumura : “An algorithm encyclopedia using C”, Gijutsu-Hyohron Co.,p.262, 2006

(13) W. H. Press, B. P. Flannery, S. A. Teulolsky, and W. T. Vetterling : “Numerical Recipes-The Art of Scientific Computing”, Cambridge University Press, pp. 289-293, 1987

Full Text: PDF