Görüntü Sıkıştırmada Kod Vektör Listesi Üretimi İçin Yeni Bir Bölme Tabanlı LBG Algoritması

Abstract

Linde-Buzo-Gray (LBG) algoritması, görüntü sıkıştırmada Vektör Nicemleme (VN) tekniği için kullanılan,

performansı büyük oranda başlangıç kod vektör listesine bağlı, kararlı, yerel optimum sonuç veren bir tekniktir.

Bölme tabanlı LBG algoritmasında görüntüyü oluşturan vektörlerin ortalaması başlangıç olarak seçilir. Merkezler

2n kez ikiye bölünüp güncellenerek yerel optimum kod listesi oluşturulur. Önerilen yeni teknikte (YLBG), LBG

algoritması geliştirilmiş ve algoritma içerisindeki bölme işlemi tüm bölgelere uygulanmayıp sadece hatası en fazla

olan bölge tespit edilip o bölgenin merkezi ikiye bölünerek merkez artırması sağlanmıştır. Böylece mevcut standart

LBG’den farklı olarak merkezler teker teker artırılıp kod vektör listesinin performansı global olarak artırılmıştır.

Bu çalışmada önerilen yeni teknik standart görüntülere uygulanmış, K-Ortalamalar (KO), LBG ve Bulanık

C-Ortalamalar (BCO) ile karşılaştırılmış, ortalama karesel hata(OKH) ölçütüne göre üstün olduğu görülmüştür.

Keywords

• Bulanık C–ortalamalar,K-ortalamalar,LBG,vektör nicemleme

A New Spliting LBG Algorithm for Codebook Generation in Image Compression

Abstract

Linde-Buzo-Gray (LBG) algorithm is used in image processing for Vector Quantization (VQ). LBG

technique is robust, performs locally best but depends on the initial codebook. In the splitting based VQ, the first

center is defined as average of all vectors. The rest of 2n centres are calculated by splitting and updated procedure.

In the proposed new technique (NLBG) the LBG is improved and insted of splitting all centres into two new

areas, the worst area that has highest mean square error splitted and updated into to new areas. Therefore, the

number of codevectors is increased one by one apart from the classical LBG. Consequently, the performance of

the codebook is increased globally. In this paper, the new technique is applied to the standard images, compared

to the FCM(Fuzzy C-Means), K-Means (K – Ortalamalar) and LBG. As a result, it is seen that the proposed new

technique performs better according to the criteria of MSE.

Keywords

• Fuzzy C-means,K-means,LBG,vector quantization

References

1. Gray RM, 1984. Vector Quantization. IEEE ASSP Magazine, 1(2): 4-29.
2. Linde Y, Buzo A, Gray RM, 1980. An Algorithm for Vector Quantizer Design. IEEE Transactions on Communications, 28: 84-95.
3. Lin YC, Tai SC, 1998. A Fast Linde-Buzo-Gray Algorithm in Image Vector Quantization. IEEE Transactions on Circiuts and Systems-II : Analog and Digital Signal Processing, 45: 432-435.
4. Patane G, Russo M, 2001. The enhanced LBG algorithm. Neural Networks, 14: 1219 – 1237.
5. Tsai CW, Lee CY, Chiang MC, Yang CS, 2009. A fast VQ codebook generation algorithm via pattern reduction. Pattern Recognition Letters, 30: 653–660.
6. Pan ZB, Yu GH, Li Y, 2011. Improved fast LBG training algorithm in Hadamard domain. Electronics Letters, 47(8): 488-489.
7. Ku NY, Chang SC, Hwang SH, 2014. Binary search vector quantization. AASRI Procedia, 8: 112 – 117.
8. Khan MAU, Mousa WA, Khan TM, 2015. Entropy-constrained reflected residual vector quantization: A realization of large block vector quantization. Optik, 126: 888–897.

9. Dunn JC, 1973. A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters. Journal of Cybernetics, 3: 32-57.
10. Bezdek JC, Ehrlich R, Full W, 1984. FCM: The Fuzzy C-Means clustering algorithm. Computers & Geosciences, 10(2-3): 191-203.
11. Ya-zhong L, Gan H, Jin-ku GU, 2011. Improved FCM algorithm using difference of neighborhood information. Journal of Computer Applications, 31(2): 375-378.
12. Kang J, Min L, Luan Q, Li X, Liu J, 2009. Novel modified fuzzy c-means algorithm with applications. Digital Signal Processing, 19(2): 309-319.
13. Lloyd Stuart P, 1982. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28 (2): 129–137.
14. Bagirov AM, Ugon J, Webb D, 2011. Fast modified global k-means algorithm for incremental cluster construction. Pattern Recognition 44(4): 866-876.
15. Bai L, Liang J, Sui C, Dang C, 2013. Fast global k-means clustering based on local geometrical information. Information Sciences, 245: 168–180.
16. Tzortzis G, Likas A, 2014. The MinMax k-Means clustering algorithm. Pattern Recognition, 47: 2505–2516.
17. Khah SS, Chouakria AD, Gaussier E, 2016. Generalize d k -means-base d clustering for temporal data under weighted and kernel time warp. Pattern Recognition Letters, 75: 63–69.