Color Image Segmentation Using Kekre-s Algorithm for Vector Quantization

Authors: H. B. Kekre, Tanuja K. Sarode, Bhakti Raul

Abstract:

In this paper we propose segmentation approach based on Vector Quantization technique. Here we have used Kekre-s fast codebook generation algorithm for segmenting low-altitude aerial image. This is used as a preprocessing step to form segmented homogeneous regions. Further to merge adjacent regions color similarity and volume difference criteria is used. Experiments performed with real aerial images of varied nature demonstrate that this approach does not result in over segmentation or under segmentation. The vector quantization seems to give far better results as compared to conventional on-the-fly watershed algorithm.

Keywords: Image Segmentation, , Codebook, Codevector, data compression, Encoding

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1072870

References:

[1] Ariano B. Huguet1, Marcos C. de Andrade2, Rodrigo L. Carceroni1, Arnaldo de A. Ara ujo1, Color-Based Watershed Segmentation of Low- Altitude Aerial Images", Proceedings of the XVII Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI-04), pp. 138- 145, 17-20 Oct 2004.
[2] L. Vincent and P. Soille, "Watersheds in digital spaces: an efficient algorithm based on immersion simulations," IEEE Trans. Pattern Anal.Mach. Intell., vol. 13, no. 6, pp. 583-598, Jun. 1991.
[3] M. Andrade, G. Bertrand, and A. Araujo, "Segmentation of microscopic images by flooding simulation: A catchment basins merging algorithm." In Proc. SPIE Nonlinear Image Processing VIII, vol. 3026, pp. 164-175, Feb 1997.
[4] R. Adams and L. Bischof, " Seeded region growing", IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 15 , no. 6, pp. 641-647, June 1994.
[5] A. Mehnert and P. Jackway, "An improved seeded region growing algorithm", Pattern Recognition Letters, vol. 18, no. 10, pp. 1065-1071, Oct. 1997.
[6] M. Kass, A.Witkin, and D. Terzopoulos, "Snakes - active contour models", Int. J. Computer Vision, vol. 1, no. 4, pp. 321-331, Jan. 1998.
[7] L. Cohen and I. Cohen , "Finite element methods for active contour models and balloons for 2d and 3d images", IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 15, no.11, pp. 1131-1147, Nov. 1993.
[8] C. Xu and J. L. Prince, "Snakes, shapes, and gradient vector flow", IEEE Trans Image Processing, vol. 7, no. 3, pp. 359-369, Mar. 1988.
[9] J. A. Sethian, "Tracking interfaces with level sets", American Scientist, pp. 254-263, May 1997.
[10] J. A. Sethian, "Level Set Methods and Fast Marching Methods", Cambridge U. Press, second edition, 1999.
[11] F. Caselles, "Image selective smoothing and edge detection by nonlinear diffusion", SIAM J. Numerical Analysis, vol. 29, no. 1, pp. 182-193, Feb 1992.
[12] R. Malladi, J. A. Sethian, and B. C. Vemuri, "Shape modeling with front propagation: A level set approach", IEEE Trans. On Pattern Analysis and Machine Intelligence, vol. 17, no. 2, pp. 158-175, Feb 1995.
[13] R. Malladi, J. A. Sethian, and B. C. Vemuri, "A fast level set based algorithm for topology-independent shape modeling", .J. Math. Imaging and Vision, vol. 6, no.2-3, pp. 269-290, Jun. 1996.
[14] Dr. H. B. Kekre, Ms. Tanuja K. Sarode, "New Fast Improved Clustering Algorithm for Codebook Generation for Vector Quantization", International Conference on Engineering Technologies and Applications in Engineering, Technology and Sciences, Computer Science Department, Saurashtra University, Rajkot, Gujarat. (India), Amoghsiddhi Education Society, Sangli, Maharashtra (India), 13th - 14th January 2008
[15] M. Borsotti , P. Campadelli , R. Schettini, "Quantitative evaluation of color image segmentation results", Pattern Recognition Letters, vol. 19, no. 8, pp. 741-747, Jun. 1998..
[16] R. M. Gray.: ÔÇÿVector quantization-, IEEE ASSP Mag, Apr. 1984, pp. 4- 29.
[17] Y. Linde, A. Buzo, and R. M. Gray.: ÔÇÿAn algorithm for vector quantizer design," IEEE Trans. Commun.-, vol. COM-28, No. 1, 1980, pp. 84-95.
[18] A. Gersho, R.M. Gray.: ÔÇÿVector Quantization and Signal Compressio-, Kluwer Academic Publishers, Boston, MA, 1991.
[19] C. D. Bei and R. M. Gray.: ÔÇÿAn improvement of the minimum distortion encoding algorithm for vector quantization-, IEEE Trans. Commun.,vol. 33, No. 10, pp. 1132-1133, Oct. 1985.
[20] Momotaz Begum, Nurun Nahar, Kaneez Fatimah, M. K. Hasan, and M. A. Rahaman: ÔÇÿAn Efficient Algorithm for Codebook Design in Transform Vector Quantization-, WSCG-2003, February 3-7, 2003.
[21] Robert Li and Jung Kim: ÔÇÿImage Compression Using Fast Transformed Vector Quantization-, IEEE Applied Imagery Pattern Recognition Workshop, 2000 Proceedings 29th Volume , 2000, pp.141 - 145.
[22] Zhibin Pan; Kotani, K.; Ohmi, T., ÔÇÿEnhanced fast encoding method for vector quantization by finding an optimally-ordered Walsh transform kernel-, ICIP 2005, IEEE International Conference, Volume 1, pp I - 573-6, Sept. 2005.
[23] Guan, L., and Kamel, M. : ÔÇÿEqual-average hyperplane partitioning method for vector quantization of image data-, Patt. Recognit. Lett., 1992, pp. 693-699.
[24] Lee, H., and Chen, L. H. : ÔÇÿFast closest codevector search algorithms for vector quantization-, Signal Process., vol. 43, 1995, pp. 323-331.
[25] Z. Li, and Z.- M. Lu. : ÔÇÿFast codevector search scheme for 3D mesh model vector quantization-, Electron. Lett., vol. 44, 2008, pp. 104-105.
[26] Chin-Chen Chang, Wen-Chuan Wu, " Fast Planar-Oriented Ripple Search Algorithm for Hyperspace VQ Codebook", IEEE Transaction on image processing, vol 16, No. 6, June 2007.
[27] C. C. Chang and T. S. Chen, "New tree-structured vector quantization with closest-coupled multipath searching method," Opt. Eng., vol. 36, No. 6, pp. 1713-1720, Jun. 1997.
[28] C. C. Chang and I. C. Lin, "Fast search algorithm for vector quantization without extra look-up table using declustered subcodebooks," IEE Proc. Vis., Image, Signal Process., vol. 152, No. 5, pp. 513-519, Oct.2005.
[29] C. C. Chang, D. C. Lin, and T. S. Chen, "An improved VQ codebook search algorithm using principal component analysis," J. Vis. Commun. Image Represent., vol. 8, No. 1, pp. 27-37, Mar. 1997.
[30] C. C. Chang, F. J. Shiue, and T. S. Chen, "Tree structured vector quantization with dynamic path search," in Proc. Int. Workshop on Multimedia Network Systems, Aizu, Japan, pp. 536 -541, Sep. 1999.
[31] R. M. Gray and Y. Linde, "Vector quantization and predictive quantizers for gauss-markov sources," IEEE Trans. Commun., vol. 30, No. 2, pp. 381-389, Feb. 1982.
[32] C. M. Huang, Q. Bi, G. S. Stiles, and R. W. Harris, "Fast full-search equivalent encoding algorithms for image compression using vector quantization," IEEE Trans. Image Process., vol. 1, No. 3, pp. 413-416, Jul. 1992.
[33] Y. C. Hu and C. C. Chang, "An effective codebook search algorithm for vector quantization", Imag. Sci. J., vol. 51, No. 4, pp. 221-234, Dec. 2003.
[34] C. H. Lee and L. H. Chen, "High-speed closest codeword search algorithm for vector quantization," Signal Process., vol. 43, No. 3, pp.323-331, May 1995.
[35] L. Torres and J. Huguet, "An improvement on codebook search for vector quantisation", IEEE Trans. Commun., vol. 42, No. 2, pp. 208- 210, Feb. 1994.
[36] S. J. Wang and C. H. Yang, "Hierarchy-oriented searching algorithms using alternative duplicate codewords for vector quantization mechanism," Appl. Math. Comput., vol. 162, No. 234, pp. 559-576, Mar. 2005.
[37] S. C. Tai, C. C. Lai, and Y. C. Lin, "Two fast nearest neighbor searching algorithms for image vector quantization," IEEE Trans. Commun., vol. 44, No. 12, pp. 1623-1628, Dec. 1996.
[38] C. Bei, R.M. Gray, ÔÇÿÔÇÿAn improvement of the minimum distortion encoding algorithm for vector quantization--, IEEE Trans. Commun.33, 1985, pp. 1132-1133.
[39] S.H. Huang, S.H. Chen, ÔÇÿÔÇÿFast encoding algorithm for VQ-based image coding--, Electron. Lett. Vol. 26, No. 19, 1990, pp. 1618-1619.
[40] W. Li, E. Salari, ÔÇÿÔÇÿA fast vector quantization encoding method for image compression--, IEEE Trans. Circ. Syst. Vid. Vol 5, 1995, pp. 119-123.
[41] C.H. Hsieh, Y.J. Liu, ÔÇÿÔÇÿFast search algorithms for vector quantization of images using multiple triangle inequalities and wavelet transform--, IEEE Trans. Image Process. Vol. 9, No. 3, 2000, pp. 321-328.
[42] S.W. Ra, J.K. Kim, ÔÇÿÔÇÿA fast mean-distance-ordered partial codebook search algorithm for image vector quantization--, IEEE Trans. Circuits- II, vol. 40, No. 9, 1993, pp. 576-579.
[43] K.S. Wu, J.C. Lin, ÔÇÿÔÇÿFast VQ encoding by an efficient kick-out condition--, IEEE Trans. Circ. Syst. Vid., vol.10, No. 1, 2000, pp. 59- 62.
[44] J.S. Pan, Z.M. Lu, S.H. Sun, ÔÇÿÔÇÿAn efficient encoding algorithm for vector quantization based on subvector technique--, IEEE Trans. Image Process. Vol 12, No.3, 2003, pp. 265-270.
[45] B.C. Song, J.B. Ra, ÔÇÿÔÇÿA fast algorithm for vector quantization using L2- norm pyramid of codewords--, IEEE Trans. Image Process. Vol. 4, No.12, 2002, pp. 325-327.
[46] Z. Pan, K. Kotani, T. Ohmi, ÔÇÿÔÇÿFast encoding method for vector quantization using modified L2-norm pyramid--, IEEE Signal Process. Lett. Vol. 12, issue 9, 2005, pp. 609-612.
[47] Y. Chen, B. Hwang, C. Chiang, "Fast VQ codebook search algorithm for grayscale image coding", Image and Vision Compu., vol. 26, 2008, pp. 657-666.
[48] H. B. Kekre, Tanuja K. Sarode, "New Fast Improved Codebook Generation Algorithm for Color Images using Vector Quantization," International Journal of Engineering and Technology, vol.1, No.1, pp. 67-77, September 2008
[49] H. B. Kekre, Tanuja K. Sarode, "Fast Codebook Generation Algorithm for Color Images using Vector Quantization," International Journal of Computer Science and Information Technology, Vol. 1, No. 1, pp: 7-12, Jan 2009.
[50] H. B. Kekre, Tanuja K. Sarode, "An Efficient Fast Algorithm to Generate Codebook for Vector Quantization," First International Conference on Emerging Trends in Engineering and Technology, ICETET-2008, held at Raisoni College of Engineering, Nagpur, India, 16-18 July 2008, Avaliable at online IEEE Xplore.
[51] H. B. Kekre, Tanuja K. Sarode, "Speech Data Compression using Vector Quantization", WASET International Journal of Computer and Information Science and Engineering 2;4 ┬® www.waset.org Fall 2008 (IJECSE), Volume 2, Number 4, 251-254, 2008. available: http://www.waset.org/ijcise
[52] H. B. Kekre, Tanuja K. Sarode, ""Centroid Based Fast Search Algorithm for Vector Quantization", International Journal of Imaging (IJI), Volume 1, Number A08, pp. 73-83, Autumn 2008, available: http://www.ceser.res.in/iji.html
[53] H. B. Kekre, Tanuja K. Sarode, ""Fast Codevector Search Algorithm for 3-D Vector Quantized Codebook", WASET International Journal of Electrical Computer and Systems Engineering (IJCISE), Volume 2, Number 4, pp. 235-239, Fall 2008. available: http://www.waset.org/ijcise