 Accelerating Families of Fuzzy K-Means Algorithms for Vector Quantization Codebook Design_2016_Edson Mata

sensorsArticleAccelerating Families of Fuzzy K-Means Algorithmsfor Vector Quantization Codebook DesignEdson Mata1 , Silvio Bandeira 1 , Paulo de Mattos Neto 2 , Waslon Lopes 3, * and Francisco Madeiro 11Center of Science and Technology, Catholic University of Pernambuco (UNICAP), Recife 50050-900, Brazil;edsonmata@hotmail.com (E.M.); silvio@c3.unicap.br (S.B.); madeiro@c3.unicap.br (F.M.)2Centro de Informática, Universidade Federal de Pernambuco (UFPE), Recife 50740-560, Brazil;psgmn@cin.ufpe.br3Department of Electrical Engineering, Center of Alternative and Renewable Energy,Federal University of Paraíba (UFPB), João Pessoa 58038-130, Brazil* Correspondence: waslon@cear.ufpb.br; Tel.: +55-83-3216-7268Academic Editor: Vittorio M. N. PassaroReceived: 24 August 2016; Accepted: 15 November 2016; Published: 23 November 2016Abstract: The performance of signal processing systems based on vector quantization dependson codebook design. In the image compression scenario, the quality of the reconstructed imagesdepends on the codebooks used. In this paper, alternatives are proposed for accelerating families offuzzy K-means algorithms for codebook design. The acceleration is obtained by reducing the numberof iterations of the algorithms and applying eff i cient nearest neighbor search techniques. Simulationresults concerning image vector quantization have shown that the acceleration obtained so far doesnot decrease the quality of the reconstructed images. Codebook design time savings up to about 40%are obtained by the accelerated versions with respect to the original versions of the algorithms.Keywords: fuzzy K-means; vector quantization; computational complexity1. IntroductionSignal compression techniques aim at decreasing the number of bits needed to represent the signal(such as speech, image, audio and video), enhancing the eff i ciency both of transmission and storage.Compression techniques are widely used in applications with storage and bandwidth constraints,such as: storage of medical images, satellite transmissions, voice communication in mobile telephonyand videoconference. One of the many techniques used to achieve signal compression is vectorquantization (VQ), in which a codebook is used for signal reconstruction.Vector quantization [ 1 , 2 ] is a lossy compression technique, which uses a mapping Q of a vector X,in a K-dimensional Euclidean space, into another vector belonging to a f i nite subset W of R K :Q : R K → W . (1)The f i nite subset W is called a codebook. Each codebook element w j , 1 ≤ j ≤ N , is called a codevector.The number of components in the codevectors is the dimension (K). The size of the codebook is thenumber of codevectors, denoted by N. In several speech coding [ 3 – 5 ] and image coding [ 6 – 9 ] systems,VQ has been used successfully, leading to high compression rates. VQ has also been used in otherapplications, such as speaker identif i cation [ 10 , 11 ], information security such as steganography anddigital watermarking [12–18], and classif i cation of pathological voice signals [19].Vector quantization is an extension of scalar quantization in a multidimensional space.The performance of VQ depends on the designed codebooks. The prevailing algorithm for codebookdesign is Linde-Buzo-Gray (LBG) [ 20 ], also known as Generalized Lloyd Algorithm (GLA) or K-means.Sensors 2016, 16, 1963; doi:10.3390/s16111963 www.mdpi.com/journal/sensors