Research and Reviews - International Journals

International Journal of Innovative Research in Science, Engineering and Technology

Menu

ISSN ONLINE(2319-8753)PRINT(2347-6710)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Review on Image Segmentation, Clustering and Boundary Encoding

Shah Nilima1, PatelDhanesh2, JivaniAnjali3
  1. Assistant Professor, Department of Applied Mathematics, Faculty of Technology and Engineering, The M.S.University of Baroda, Vadodara, Gujarat, India.
  2. Professor, Department of Applied Mathematics, Faculty of Technology and Engineering, The M.S. University of Baroda, Vadodara, Gujarat, India
  3. Associate Professor, Department of Computer Science, Faculty of Technology and Engineering, TheM.S.University of Baroda, Vadodara, Gujarat, India.
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Science, Engineering and Technology

International Journal of Innovative Research in Science, Engineering and Technology

Abstract

Identification of an object in an image is the main objective of image segmentation which can be further applied to object recognition. Image segmentation can be described as a process of segregating an image into different parts which give a meaningful representation to the image. Clustering algorithms are very popular in image segmentation,but the number of regions of the image and initial cluster centroids has to be known a priori. To represent objects, boundary encoding of the objects or segments is also one of the important tasks. Presently,to find the best polygon that achieves a small distortion for a given number of vertices for boundary encoding of segments or objects is a challenging task. Several methods for encoding of object boundaries are known that use the concept of chain codes, B-spline, convex hull or Delaunay triangulation approach etc. A review of various segmentation approaches, clustering algorithms applied to image segmentation as well as boundary encoding algorithms is done in this paper

Keywords
Image segmentation, Clustering, Boundary encoding, Object recognition

I. INTRODUCTION
Images are considered as one of the convenient medium of conveying information, in the field of pattern recognition, object identification and computer vision. Some of the innumerable fields where image analysis is required are: extracting malign tissues from MRI images, navigation of robots, identification of various objects like land and water bodies, forests etc. from remote sensedimages,medical applications, finger print recognition, iris recognition, face recognition etc.
Image segmentation is one of the most critical and essential steps, with the help of which, we can understand images and extract information or objects.It isthe process of segregating an image into one or multiple segments that change the representation of an image into objects of interest, which then becomes more meaningful and can be easily analyzed. For the above mentioned image analysis applications, image segmentation processleads to detection of cancerous cells, detecting paths and objects for robot navigation, detection of land, forest and water regions, face extraction or detection, iris (eye) detection respectively from images. Hence, image segmentation is the basic step in the process of analysis of images.
Once the objects of interest are identified in an image, the shape of the object is stored using object boundary information. As digital images are stored and processed in a grid format where spacing is equal between pixels along x and y directions, the boundary pixels are coded by following the boundary of the connected object in say clockwise direction, assigning a direction to segments joining two consecutive pixels. The most popular coding technique is Chain codes given by Freeman. But this is inefficient in terms of time and memory requirements i.e. the chain code will be very long. To reduce the length of the chain code, the grid can be resampled using larger grid spacing. Then as the boundary is traversed, a boundary point is assigned to each node of the larger grid depending on the nearest original boundary pixel. This boundary can then be encoded resulting in reduced boundary length. Boundary points can also be obtained by tracing polygons obtained using various other techniques like B-spline, convex hull or Delaunay triangulation approach which can further be encoded.
The goal of various boundary tracing and encoding algorithms hence is to minimize the boundary length as well as minimize the time taken for the process. Literature survey shows that several algorithms and techniques have been developed for image segmentation and boundary encoding. The choice of one segmentation technique over another and the level of segmentation are decided by the particular type of image and characteristics of the concerned problem.The research on boundary coding is proposed in [35,36,37,25].
This paper compiles the different general segmentation techniques, clustering methods and various boundary coding methods.
The paper is organized as follows: Section 2 describes segmentation techniques, section3 discusses boundary encoding techniques and section 4 concludes the paper.

II. CURRENT SEGMENTATION TECHNIQUES
Research in the area of image segmentation has gained a lot of attention since many years. Several different segmentation techniques are available in the literature. But a universal method which can be applied to any type of image is hardly available. Hence, all methods are not equally good for a particular type of image [41]. Hence algorithms developed for a particular category of images, e.g. tissue or cell images may not be suitable for extracting faces from human images or extracting land and water bodies from satellite images. Till today, developing a generalized algorithm has been a challenging issue.Image segmentation approaches are currently categorized based on two properties, detecting discontinuities and detecting dissimilarities, in the image.
A. Detecting Discontinuities
Detecting discontinuities partitions an image based on abrupt changes in intensity[11]. These methods attempt to obtain image segmentation by detecting the edges or pixels between different regions that have rapid transition in intensity, [11, 31] and are connected. Gray histogram and gradient based method are the two main methods based on this theory [18].
Simple and noise-free images can be segmented using edge detection algorithms but when applied on complex and noisy images they may produce missing edges or extra edges [45].
B. Detecting Similarities
Detecting similarities means to partition an image into regions that are similar according to a set of predefined criterion [11]. The algorithms included in this category are thresholding, region growing, region splitting and merging. Image segmentation by thresholding is a simple but powerful approach for segmenting images having light objects on dark background [11]. Threshold can be user input or obtained by an algorithm but the number of partitions is limited to two. Also it does not take into account the spatial characteristics of an image and is sensitive to noise[18]. Region based methods, partition an image into regions that are similar according to a set of predefined criteria [16, 11]. Region based algorithms are further categorized as Region Growing and Region Splitting and Merging methods. Region growing is a procedure [2, 12] that groups pixels of the entire image into sub regions or larger regions based on predefined criterion [3] starting from putting each pixel in a group. An image can be divided into a set of arbitrary unconnected regions and then the regions can be merged instead of selecting initial seed points [2, 18] in an attempt to satisfy the conditions of reasonable image segmentation.
Region splitting and merging is a technique that is usually implemented by quad tree data theory.
C. Segmentation Methods Based on PDE (Partial Differential Equation)
Partial differential equations and its numerical scheme can be used to segment the image. Kass et al. in 1987 first introduced this method[15] to find familiar objects in presence of noise. Active contours or snakes are computer generated curves obtained using PDE [15, 49] which are placed by user interaction [19] around the object which than move within the image to find object boundaries under the influence of internal and external forces.
The level set method which was highly useful was developed by Osher and Sethian[15]used PDEs based on moving curves and surfaces with curvature based velocities. The technique developed here handles topological change very well and provides more accurate numerical implementations also.
D. Neural Network based segmentation
Neural Network based segmentationdiffers totally from traditional segmentation algorithms. Here an image is mapped onto a neural network and every neuron represents a pixel from the image [18], thus converting image segmentation problem into energy minimization problem.
E. Clustering
Clustering is defined as an unsupervised learning task, where one needs to identify a finite set of categories known as clusters to classify pixels [5]. The grouping of pixels into clusters is based on the principle of the intra class similarity minimization and the inter class similaritymaximization. According to characteristics of an algorithm, we may divide the clustering algorithms into broadly hard clustering and soft clustering.
Hard clustering methods are applicable to data sets that have a large difference between groups i.e. it has sharp boundaries between clusters [22] and a pixel belongs to one and only one cluster. The most popular algorithm of hard clustering algorithm is K-means clustering algorithm [5]. It is simple to implement and computational cost is also low, which makes it the first preference with large data sets. But in this method, K the number of clusters must be determined [24].It may lead to different results for each execution which depends on initial cluster centroids.
Fuzzy clustering techniques are usedwhen there are no crisp boundaries between objects in an image. These techniques classify pixel values with great extent of accuracy and are suitable for decision applications like tissue classification and tumour detection etc.
Some of the fuzzy clustering algorithms are Fuzzy C means, Gustafson-Kessel, Gaussian mixture decomposition, Fuzzy C varieties etc. Fuzzy C means is the most popular method as preserves more information than other approaches [29] but in case of noisy images does not consider spatial information which has led to the development of several other algorithms as modified FCM, GSFCM, mean shift based FCMetc.

III. BOUNDARY ENCODING SCHEME
Planar curves encoding is a more fascinating problem in today’s scenario, such as object recognition, and CAD. Several researchers have done work in this area but the algorithms which they have developed in the above mentioned area can be used for different applications. The efficient encoding of boundaries can be seen in the research work ofMusmann et al. [26,27].
The approximation of the boundary can be done by a polygon and is similar in the sense of spline approximation. In this case the encoding of successive vertices can be achieved with a chain code scheme.
It is well known that there are two approaches for encoding the segmentation information – a lossy approach [14] approach which is based on spline approximation and chain codes[8] respectively.
Jain A.K.[14] used B-spline curves for the approximation of a boundary. He formulated an optimization procedure for finding the optimal locations of the control points by the mean squared error (MSE) between the approximation and the boundary. He observed that this is the best method to smoothen the boundary by selecting the mean squared error as a distortion measure.
M. Höter et al. [27] approximated a boundary by a combination of splines and polygons. In this case the distortion measure is taken as maximum distance between original boundary and approximation. His method leads to a good approximation but the resulting rate is little bit less. Hence it is observed that the result does not facilitate the rate constraint for encoding boundary.
[8, 34, 23, 28, 17, 32] show research work done in the area of chain coding for boundary encoding. The most widely used chain code is the eight-connect chain code. Further studying the work of Guido M. Schuster and Aggelos K. Katsaggelos[35,37]show the use of polygon for boundary approximation and 8 connect chain codes for boundary encoding. It is fast but lossy approach. The algorithm of [35] is based on the shortest path algorithm for the weighted directed a cyclic graph and [37] based on Lagrangian approach.[36]is an extension of the previous two methods . FabianMeirer, Guido M Schuster and Aggelos K. Katsaggelos[25]have used same approach but using B-spline curve. It is obvious that using curves is more reasonable approach than using polygons as it gives a better approximation of the boundary.
Gerry Melnikov, Guido M Schuster, and Aggelos K. Katsaggelos[51]have used the concept of object contours and have approximated the contours by the connected second order spline segments.

IV. CONCLUSION
In this paper we have outlined the main image segmentation techniques. This paper also presents a survey of methods for boundary encoding.Research till date shows that there is no unique segmentation algorithm and boundary encoding algorithm that can be applied to all types of images. Thus image segmentation as well as encoding of boundary such that it leads to a minimum encoding length still remains a challenging problem.

ACKNOWLEDGMENT
The author1 expresses special thanks to the School of Computing, University of Joenssu, Finland for providing necessary help.

References
  1. Aurdal L.(2006),“Image Segmentation beyond thresholding”, NorskRegnes central.
  2. AksoyS.,“Image Segmentation”, Department of Computer Engineering, Bilkent Univ.
  3. Chang Y(1994), X. Li,“Adaptive Image Region Growing”, IEEE Trans. On Image Processing, Vol. 3, No. 6, 1994.
  4. Cormen T., Leiserson C., and Rivest R. (1991), Introduction to Algorithms. New York: McGraw-Hill.
  5. Dehariya V. K., Shrivastava S. K., Jain R. C.(2010),“Clustering of Image Data Set Using K-Means and Fuzzy K-Means Algorithms”, International conference on CICN, pp. 386-391.
  6. Everett H. (1963), “Generalized Lagrange multiplier method for solving problems of optimum allocation of resources,” Oper. Res., vol. 11, pp.399–417.
  7. Fisher M. L. (1981), “The Lagrangian relaxation method for solving integer programming problems,” Manage. Sci., vol. 27, pp. 1–18, Jan. 1981.
  8. Freeman H. (1961): On the encoding of arbitrary geometric configurations; IRE Trans. Electron. Comput. , Vol.EC-10, pp.260-268.
  9. Gerald C. F. and Wheatley P. O. (1990) Applied Numerical Analysis, 4th ed. Reading, MA: Addison.
  10. Gevers T., Kajcovski V. K.,“Image Segmentation by direct region subdivision”, Proceedings of the 12th IAPR International Conference on Pattern Recognition, Vol. 1.
  11. Gonzalez R. C., Richard E. Woods (2007), “Digital Image Processing”, 2nd ed., Beijing: Publishing House of Electronics Industry.
  12. Gunturk K. G., “EE 7730- Image Analysis I”, Louisiana state university.
  13. Hötter M. (1990), “Object-oriented analysis-synthesis coding based on movingtwo-dimensional objects,” Signal Process.: Image Commun., vol. 2, pp.409–428, Dec. 1990.
  14. Jain A. K.(1989), Fundamentals of digital image processing, Prentice_Hall.
  15. Jiang X., Zhang R., Nie S. (2009),“Image Segmentation Based on PDEs Model: a Survey”, IEEE conference, pp. 1-4.
  16. Kaganami H. G., Beij Z.(2009),“Region Based Detection versus Edge Detection”, IEEE Transactions on Intelligent information hiding and multimedia signal processing, pp. 1217-1221.
  17. Kaneko T. andOkudaira M.(1985), “Encoding of arbitary curves based on the chain code representation,” IEEE Trans. Commun., vol. COMM-33, pp. 697–707, July 1985.
  18. Kang W. X., Yang Q. Q., Liang R. R. (2009),“The Comparative Research on Image Segmentation Algorithms”, IEEE Conference on ETCS, pp. 703-707.
  19. Karch P., Zolotova I. (2010),“An Experimental Comparison of Modern Methods of Segmentation”, IEEE 8th International Symposium on SAMI, pp. 247-252.
  20. Katsaggelos et al.(1997), “MPEG-4 and rate-distortion based shape coding techniques,” Pronication, Erlangen, Germany, April 25, 1997, pp. 75–84.
  21. Katsaggelos et al. A. K., “MPEG-4 and rate-distortion based shape coding techniques,” Proc. IEEE Special Issue Multimedia Signal Processing, to be published.
  22. Kettaf F .Z., D. BI, J. P.(1996),“A Comparison Study of Image Segmentation by Clus 282,
  23. Koplowitz J. (1981), “On the performance of chain codes for quantization of line drawings,” IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-3,pp. 180–185, Mar. 1981.
  24. Lukac P, Hudec R., Benco M., Kamencay P., Dubcova Z., ZachariasovaM.,“Simple Comparison of Image Segmentation Algorithms Based on Evaluation Criterion
  25. Meier F. W., Schuster G. M., and Katsaggelos A. K.(1997), An efficientboundary encoding scheme using B-spline curves which is optimal in therate-distortion sense,” in Proc. 2nd Erlangen Symp., Advances in DigitalImage Communication, Erlangen, Germany, April 25, 1997, pp. 75–84.
  26. Musmann H. and Hotter M. and Ostermann J.(1989) :Object oriented analysis_synthesis coding of moving images Signal Processing_ Image Communication, vol 2 pp. 117-138.
  27. Musmann H., Hotter M., and Ostermann J. (1989), “Object-oriented analysis- ¨ synthesis coding of moving images,” Signal Process.: Image Commun.,vol. 1, pp. 117–138.
  28. Neuhoff D. and Castor K.(1985), “A rate and distortion analysis of chain codes for line drawings,” IEEE Trans. Inform. Theory, vol. IT-31, pp. 53–68.
  29. Naz S, Majeed H., Irshad H.(2010),“Image Segmentation using Fuzzy Clustering: A Survey”, International Conference on ICET, pp.181-186.
  30. Oz T. (1984)¸ ¨celik, “A very low bit rate video codec,” Ph.D. dissertation, Dept.Electr. Eng. Comput. Sci., Northwestern Univ., Evanston, IL, Dec. 1994.
  31. Pal N. R., Pal S. K. (1993),“A Review on Image Segmentation Techniques”, Pattern Recognition, Vol. 26, No. 9, pp. 1277-1294.
  32. Prasad R., Vieveen J. W., Bons J. H., and Arnbak J. C.(1989), “Relative vector probabilities in differential chain coded line-drawings,” in Proc. IEEE Pacific Rim Conf. Communication, Computers, and Signal Processing, Victoria, B.C., Canada, June 1989, pp. 138–142.
  33. Ramchandran K., Ortega A., and Vetterli M.(1994), “Bit allocation for dependent quantization with applications to multiresolution and MPEG videom coders,” IEEE Trans. Image Processing, vol. 3, pp. 533–545, Sept. 1994.
  34. Saghri J. and Freeman H.(1981), “Analysis of the precision of generalized chain codes for the representation of planar curves,” IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-3, pp. 533–539.
  35. Schuster G. M. and Katsaggelos A. K.(1996), “An optimal lossy segmentation encoding scheme,” in SPIE Proc. Conf. Visual Communications and Image Processing, Mar. 1996, pp. 1050–1 ding scheme,” in SPIE Proc. Conf. Visual Communications and Image Processing, Mar. 1996, pp. 1050–1061.
  36. Schuster G. M. and Katsaggelos A. K.(1996) “An efficient boundary encoding scheme which is optimal inthe rate distortion sense,” in Proc. 1996 Int. Conf. Image Processing,Lausanne, Switzerland, Sept. 1996, pp II-77–80.
  37. Schuster G. M. andKatsaggelos A. K.(1997), Rate-Distortion Based VideoCompression, Optimal Video Frame Compression, and Object BoundaryEncoding. Boston, MA: Kluwer, 1997.
  38. Schuster G. M. andKatsaggelos A.K.(1996) “An optimal segmentation encoding scheme in the rate-distortion sense,” in Proc. Int. Symp. Circuits and Systems, Atlanta, GA, May 1996, vol. 2, pp. 640–643.
  39. Schuster G. M. andKatsaggelos A.K.(1996) “Fast and efficient mode and quantizer selection in the rate distortion sense for H.263,” in SPIE Proc. Conf. Visual Communications and Image Processing, Mar. 1006, pp. 784–795.
  40. Shoham Y. and Gersho A. (1988), “Efficient bit allocation for an arbitrary setofquantizers,” IEEE Trans. Acoust., Speech, Signal Processing, vol. 36,pp. 1445–1453, Sept. 1988
  41. Singh S. A, Singh A. (2010),“A Study of Image Segmentation Algorithms for Different Types of Images”, International Journal of Computer Science Issues, Vol. 7, Issue 5.
  42. Tatiraju S., Mehta A.,“Image Segmentation using k-means clustering, EM and Normalized Cuts”, Department of EECS, pp. 1-7.
  43. Trushkin A. V.(1980), “Bit number distribution upon quantization of a multivariate random variable,” Problems Inform. Transmission, vol. 16, p variate random variable,” Problems Inform. Transmission, vol. 16, pp. 76–79, 1980, trans. from Russian] ,
  44. Trushkin A. V.(1981)“Optimal bit allocation algorithm for quantizing a randomvector,” Problems Inform. Transmission, vol. 17, pp. 156– 161(trans. from Russian).
  45. Varshney S. S., Rajpal N. , Purwar R.(2009),“Comparative Study of Image Segmentation Techniques and Object Matching using Segmentation”, Proceeding of International Conference on Methods and Models in Computer Science, pp. 1-6,.
  46. Wei B. C., Mandava R.(2010),“Multi–objective Nature-inspired Clustering Techniques for Image Segmentation”, IEEE Conference on CIS, pp.150-155.
  47. Wei B. C., Mandava R.(2010),“Multiobjective optimization Approaches in Image Segmentation- the Direction and Challenges”, ICSRS Publication.
  48. Zhang Y., Qu H., Wang Y.(1994),“Adaptive Image Segmentation Based on Fast Thresholding and Image Merging”, Artificial reality and Telexistence-Workshops, pp. 308-311.
  49. Zhu C., Ni J., Li Y., Gu G.(2009),“General Tendencies in Segmentation of Medical Ultrasound Images”, International Conference on ICICSE, pp. 113-117.
  50. Zhang H., Fritts J. E., Goldman S. A.(2008),“Image Segmentation Evaluation: A Survey of unsupervised methods”, computer vision and image understanding, pp. 260-280.
  51. Gerry Melnikov and Guido M. Schuster and Aggelos K. Katsaggelos(1998),” Simultaneous Optimal Boundary Encoding And Variable- Length Code Selection”, Proc. ICIP98,256-260.