Color Image Segmentation Using Kekre-s Algorithm for Vector Quantization

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.

Authors:

• H. B. Kekre
• Tanuja K. Sarode
• Bhakti Raul

Keywords:

• Image Segmentation
• Codebook
• Codevector
• data compression
• Encoding

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