Image Segmentation using Euler Graphs
Keywords:
Image Segmentation, Graph theory, Euler Graphs, CyclesAbstract
This paper presents a new algorithm for image segmentation problem using the concepts of Euler graphs in graph theory. By treating image as an undirected weighted non-planar finite graph (G), image segmentation is handled as graph partitioning problem. The proposed method locates region boundaries or clusters and runs in polynomial time. Subjective comparison and objective evaluation shows the efficacy of the proposed approach in different image domains.References
J.A. Bondy and U.S.R. Murty. Graph Theory with Applications, Fifth printing. Elsevier Science Publishing Co., Inc., 52, Vanderbilt Avenue, New York, 1982.
H.Greenspan C.Carson, S.Belongie and J.Malik. Blobworld: Image segmentation using expectationmaximization and its application to image querying. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(8):1026-1038, 2002. http://dx.doi.org/10.1109/TPAMI.2002.1023800
C.R.Brice and C.Fennema. Scene analysis using regions. Artificial Intelligence, 1(3-4):205-226, 1970. http://dx.doi.org/10.1016/0004-3702(70)90008-1
C.T.Zahn. Graph theoretical methods for detecting and describing gestalt clusters. IEEE Transactions on Computation, 20:68-86, 1971. http://dx.doi.org/10.1109/T-C.1971.223083
E.L.Schwartz. Spatial mapping in the primate sensory projection: Analytic structure and relevance to perception. Biological Cybernetics, 25(4):181-194, 1977. http://dx.doi.org/10.1007/BF01885636
Euler. Solutio problematis ad geometriam situs pertinentis comment. Academiae Sci. I. Petropolitanae, 8:128-140, 1736.
Pedro F. Felzenszwalb and Daniel P. Huttenlocher. Efficient graph-based image segmentation. International Journal of Computer Vision, 59(2):167-181, 2004. http://dx.doi.org/10.1023/B:VISI.0000022288.19776.77
K.S. Fu and J.K. Mui. A survey of image segmentation. Pattern Recognition, 13:3-16, 1981. http://dx.doi.org/10.1016/0031-3203(81)90028-5
R.M. Haralick and L.G. Shapiro. Survey, image segmentation techniques. Computer Vision, Graphics and Image Processing, 29:100-132, 1985. http://dx.doi.org/10.1016/S0734-189X(85)90153-7
I.Jermyn and H.Ishikawa. Globally optimal regions and boundaries as minimum ratio weight cycles. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(4):1075-1088, 2001. http://dx.doi.org/10.1109/34.954599
L.Vincent and P.Soille. Watersheds in digital spaces: an efficient algorithm based on immersion simulations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(6):583-598, 1991. http://dx.doi.org/10.1109/34.87344
R.Velthuizen L.Hall D.Goldgof L.Clarke M.Clark and M.Silbiger. Mri segmentation using fuzzy clustering techniques. IEEE Engineering in Medicine and Biology Magazine, 13(5):730-742, 1994. http://dx.doi.org/10.1109/51.334636
O.Monga. An optimal region growing algorithm for image segmentation. PRAI, 1(4):351-375, 1987. http://dx.doi.org/10.1142/s0218001487000242
N. Otsu. A threshold selection method from grey level histograms. IEEE Transactions on System, Man and Cybernetics, 9:62-66, 1979. http://dx.doi.org/10.1109/TSMC.1979.4310076
N.R. Pal and S.K. Pal. A review on image segmentation techniques. Pattern Recognition, 26:1277- 1294, 1993. http://dx.doi.org/10.1016/0031-3203(93)90135-J
P.Parent and S.W.Zucker. Trace inference, curvature consistency, and curve detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(8):823-839, 1989. http://dx.doi.org/10.1109/34.31445
R.Adams and L.Bischof. Seeded region growing. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(6):641-647, 1994. http://dx.doi.org/10.1109/34.295913
R.Urquhart. Graph theoretical clustering based on limited neighborhood sets. Pattern Recognition, 15(3):173-187, 1982. http://dx.doi.org/10.1016/0031-3203(82)90069-3
P.W.Ong. R.Wallace and E.Schwartz. Space variant image processing. International Journal of Computer Vision, 13(1):71-90, 1994. http://dx.doi.org/10.1007/BF01420796
S.C.Zhu and A.L.Yuille. Region competition: Unifying snakes, region growing, and bayes/mdl for multiband image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(9):884-900, 1996. http://dx.doi.org/10.1109/34.537343
M.Pelillo S.Dickinson and Ramin Zabih. Introduction to the special section on graph algorithms in computer vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(10):1049- 1052, 2001. http://dx.doi.org/10.1109/TPAMI.2001.954597
J. Shi. and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888-905, 2000. http://dx.doi.org/10.1109/34.868688
S.L.Horowitz and T.Pavlidis. A graph-theoretic approach to picture processing. JACM, 7(2):282- 291, 1976.
S.L.Horowitz and T.Pavlidis. Picture segmentation by a tree traversal algorithm. JACM, 23(2):368- 388, 1976. http://dx.doi.org/10.1145/321941.321956
S.Ullman and A.Shaashua. Structural saliency: The detection of globally salients structures using a locally connected network. Technical report, Cambridge, MA, USA, 1988.
U.Montanari. On the optimal detection of curves in noisy pictures. Communications. ACM, 14(5):335-345, 1971. http://dx.doi.org/10.1145/362588.362594
A.R. Weeks and G.E. Hague. Color segmentation in the hsi color space using the k-means algorithm. In SPIE, p. 143-154, Nonlinear Image Processing VIII, Edward R. Dougherty; Jaakko T. Astola; Eds, Volume 3026, pages 143-154, 1997.
Y.Haxhimusa andW.Kropatsch. Hierarchy of partitions with dual graph contraction. Lecture Notes in Computer Science, 2781:338-345, 2003. http://dx.doi.org/10.1007/978-3-540-45243-0_44
Y.Haxhimusa and W.Kropatsch. Segmentation graph hierarchies. In Proceedings of Structural, Syntactic, and Statistical Pattern Recognition, Volume 3138, pages 343-351. LNCS, 2004. http://dx.doi.org/10.1007/978-3-540-27868-9_36
Y.Weiss. Segmentation using eigenvectors: A unifying view. In Proceedings of the International Conference on Computer Vision, Volume 2, pages 975-982, 1989.
Z.Wu and R.Leahy. An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(11):1101-1113, 1993. http://dx.doi.org/10.1109/34.244673
Dickinson, S., Pelillo, M. and Zabih, R. Introduction to the special section on graph algorithms in computer vision IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(10):1049- 1052, 2001. http://dx.doi.org/10.1109/TPAMI.2001.954597
D. Martin and C. Fowlkes and D. Tal and J. Malik A Database of Human Segmented Natural Images and its Application to Evaluating Segmentation Algorithms and Measuring Ecological Statistics Proc. 8th Int'l Conf. Computer Vision, Volume 2, pages 416-423, 2001.
http://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/
Piotr Dollar, Zhuowen Tu, and Serge Belongie Supervised Learning of Edges and Object Boundaries Proc. IEEE Computer Vision and Pattern Recognition, CVPR, June, 2006.
Michael Maire, Pablo Arbelaez, Charless Fowlkes and Jitendra Malik Using Contours to Detect and Localize Junctions in Natural Images Proc. IEEE Computer Vision and Pattern Recognition, CVPR, 2008.
Xiaofeng Ren Multi-Scale Improves Boundary Detection in Natural Images Proc. ECCV Conference, 2008.
Marius George Linguraru, Miguel ´A ngel Gonz ´ a lez Ballester, Nicholas Ayache Deformable Atlases for the Segmentation of Internal Brain Nuclei in Magnetic Resonance Imaging International Journal of Computers, Communications & Control, Volume 2, No. 1, pages 26-36, 2007.
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
