VQ: Vector Quantization

Vector Quantization

Vector Quantization

This page contains information related to vector quantization (VQ). Currently this page includes information about VQ with regards to compression. In the future, we will make this page a more comprehensive VQ page. 


In what applications is VQ used?

Vector quantization is used in many applications such as image and voice compression, voice recognition (in general statistical pattern recognition), and surprisingly enough in volume rendering (I have no idea how VQ is used in volume rendering!). 


What is VQ?

A vector quantizer maps k-dimensional vectors in the vector space Rk into a finite set of vectors Y = {yii = 1, 2, ..., N}.  Each vector yi is called a code vector or a codeword. and the set of all the codewords is called a codebook.  Associated with each codeword, yi, is a nearest neighbor region called Voronoi region, and it is defined by:

The set of Voronoi regions partition the entire space Rk such that:

 
     for all ij
As an example we take vectors in the two dimensional case without loss of generality.  Figure 1 shows some vectors in space.  Associated with each cluster of vectors is a representative codeword.  Each codeword resides in its own Voronoi region.  These regions are separated with imaginary lines in figure 1 for illustration.  Given an input vector, the codeword that is chosen to represent it is the one in the same Voronoi region. 
  
 
Figure 1: Codewords in 2-dimensional space.  Input vectors are marked with an x, codewords are marked with red circles, and the Voronoi regions are separated with boundary lines.

The representative codeword is determined to be the closest in Euclidean distance from the input vector.  The Euclidean distance is defined by:

where xj is the jth component of the input vector, and yij is the jth is component of the codeword yi. 


How does VQ work in compression?

A vector quantizer is composed of two operations.  The first is the encoder, and the second is the decoder.  The encoder takes an input vector and outputs the index of the codeword that offers the lowest distortion.  In this case the lowest distortion is found by evaluating the Euclidean distance between the input vector and each codeword in the codebook.  Once the closest codeword is found, the index of that codeword is sent through a channel (the channel could be a computer storage, communications channel, and so on).  When the encoder receives the index of the codeword, it replaces the index with the associated codeword.  Figure 2 shows a block diagram of the operation of the encoder and decoder. 
  
 
Figure 2: The Encoder and decoder in a vector quantizer.  Given an input vector, the closest codeword is found and the index of the codeword is sent through the channel.  The decoder receives the index of the codeword, and outputs the codeword.

How is the codebook designed?

So far we have talked about the way VQ works, but we haven't talked about how to generate the codebook.  What code words best represent a given set of input vectors?  How many should be chosen?

Unfortunately, designing a codebook that best represents the set of input vectors is NP-hard.  That means that it requires an exhaustive search for the best possible codewords in space, and the search increases exponentially as the number of codewords increases (if you can find an optimal solution in polynomial time your name will go down in history forever).  We therefore resort to suboptimal codebook design schemes, and the first one that comes to mind is the simplest.  It is named LBG for Linde-Buzo-Gray, the authors of this idea.  This algorithm is similar to the k-means algorithm. 
 

The algorithm

  1. Determine the number of codewords, N,  or the size of the codebook.
  2. Select codewords at random, and let that be the initial codebook.  The initial codewords can be randomly chosen from the set of input vectors.
  3. Using the Euclidean distance measure clusterize the vectors around each codeword.  This is done by taking each input vector and finding the Euclidean distance between it and each codeword.  The input vector belongs to the cluster of the codeword that yields the minimum distance.
  4. Compute the new set of codewords.  This is done by obtaining the average of each cluster.  Add the component of each vector and divide by the number of vectors in the cluster.
    where i is the component of each vector (x, y, z, ... directions), m is the number of vectors in the cluster.
  1. Repeat steps 2 and 3 until the either the codewords don't change or the change in the codewords is small.

This algorithm is by far the most popular, and that is due to its simplicity.  Although it is locally optimal, yet it is very slow.  The reason it is slow is because for each iteration, determining each cluster requires that each input vector be compared with all the codewords in the codebook (We have programmed this algorithm in C, and for an 512x512 image, a codebook of 256, and vectors in 4 dimensions, the generation of the codebook took about 20 minutes on an HP machine).

There are many other methods to designing the codebook, methods such as Pairwise Nearest Neighbor (PNN), Simulated AnnealingMaximum Descent (MD), and Frequency-Sensitive Competitive Learning (FSCL), etc. 


How does the search engine work?

Although VQ offers more compression for the same distortion rate as scalar quantization and PCM, yet is not as widely implemented.  This due to two things.  The first is the time it takes to generate the codebook, and second is the speed of the search.  Many algorithms have be proposed to increase the speed of the search.  Some of them reduce the math used to determine the codeword that offers the minimum distortion, other algorithms preprocess the codewords and exploit underlying structure.

The simplest search method, which is also the slowest, is full search.  In full search an input vector is compared with every codeword in the codebook.  If there were M input vectors, N codewords, and each vector is in k dimensions, then the number of multiplies becomes kMN, the number of additions and subtractions become MN((k - 1) + k) = MN(2k-1), and the number of comparisons becomes MN(k - 1).  This makes full search an expensive method. 


What is the measure of performance VQ?

How does one rate the performance of a compressed image or sound using VQ?  There is no good way to measure the performance of VQ.  This is because the distortion that VQ incurs will be evaluated by us humans and that is a subjective measure.  Don't despair!  We can always resort to good old Mean Squared Error (MSE) and Peak Signal to Noise Ratio (PSNR).  MSE is defined as follows:

where M is the number of elements in the signal, or image.  For example, if we wanted to find the MSE between the reconstructed and the original image, then we would take the difference between the two images pixel by pixel, square the results, and average the results.

The PSNR is defined as follows:

where n is the number of bits per symbol.  As an example, if we want to find the PSNR between two 256 gray level images, then we set n to 8 bits. 

http://www.mqasem.net/vectorquantization/vq.html

Vector Quantization - چندی سازی برداری

تکنیک های متفاوتی برای فشرده سازی تصاویر وجود دارد و از این میان چندی سازی برداری نخستین بار در سال 1984 اریه شد. یک راهبرد برای فشرده سازی تصاویر است. که کوانتیزرها میزان اتلاف را تعیین می کنند. چندی سازی برداری یک روش پراتلاف می باشد.

اگر بلوک هایی از ورودی با هم کوانتیزه شوند به آن چندی سازی برداری می گویند. در چندی سازی برداری تصاویر، ساده ترین راهبرد برای پردازش بخشهای تصویر، تقسیم تصویر ورودی در رمزگذار به بلوکها یا بردارهای مستطیلی، غیر همپوشانی، چسبیده و کوچک از پیکسلها است که هر کدام جداگانه کوانتیزه شود.

ابعاد بردار مساوی تعداد پیکسل های هر بلوک است. بعد از تقسیم عکس به بلوک هایی، در هر بلوک بهترین نماینده انتخاب می شود و بعنوان نماینده در کتاب کد ذخیره می شود. این کتاب کد برای گیرنده ارسال می شود. و بعد از رمز گشایی عکس مورد نظر به نایش در می آید

 

نمونه های بدست آمده از خروجی منبع درون بردار k بعدی دسته بندی می شوند، این بردار در حقیقت ورودی فرآیند چندی سازی برداری را تشکیل می دهد. مولفه اصلی VQ یک کتاب کد بوده که شامل بردارهای نماینده با عنوان بردارهای کد است

به منظور یافتن مشابه ترین و نزدیک ترین بردار کد به بردار ورودی، کتاب کد بر اساس معیار خطای انحراف جستجو می شود. شاخص بردار کد برای گیرنده ارسال می شود. گیرنده به یک جدول جستجو ساده نیازمند است، شاخص دریافت شده جهت تولید مجدد یا تکثیر بردارکد تقریبا شبیه بردار ورودی دربر گیرنده Kنمونه مورد استفاده قرار می گیرد.

الگوریتم های مختلفی برای بدست آوردن کتاب کد بهینه استفاده شده است. تهیه کتاب کد مناسب بر کیفیت عکس فشرده شده تاثیر مستقیمی دارد. در این میان الگوریتم های خوشه بندی بیشترین استفاده را داشته اند. یکی از الگوریتم های خوشه بندی معروف K-means  می باشد.

 

 

 

 

 

...

در این وبلاگ قصد معرفی و پیاده سازی موارد زیر را برای دستیابی به یک روش بهینه با سرعت اجرای بالا در CPU , GPU درایم. تا انجا که بتوانم مشکلات در اجرا و راه حل های اتخاذ شده را به اشتراک می گذارم.


1- باز کردن یک تصویر Bitmap ارسال پیکسل های تصویر به یک آرایه

2- کد نویسی و اجرای Kmeans بر روی پیکسل های تصویر

3-گد نویسی و اجرای ++kmaens بر روی پیکسل ها

4- کد نویسی و اجرای Kmeans , ++kmeans  با CUDA در GPU


Software

- Visual studio

cuda_6.5.14_windows_general_64


Hardware

- NVIDIA GeForce GT 610  OK


مفاهیم و تعاریف پایه

الگوریتم های کلاسترینگ

 

خوشه بندی و یا آنالیز خوشه ای ، گروهی از اشیا داده ای که تنها براساس اطلاعات به دست آمده از داده ها کار می کند که به توصیف اشیاارتباط بین آنها می پردازد.هدف این است که اشیا درون یک گروه شبیه باشند و اشیا درون گروه های مختلف متفاوت باشند.

کیفیت خوشه ها بر اساس تمایز بین گروه ها و همسان بودن درونی گروه ها تعیین می شود. در دامنه ای از تصاویر این توصیف کلی  به فاصله پیکسل ها در فضای رنگی تفسیر می شود پیکسل هایی که در کنار یکدیگر در یک کلاستر می باشند.


Kmeans

یک الگوریتم تکرار شونده است که تعداد کلاستر ها را قبل از اجرا تعیین می کند. در ابتدا مرکز حجم K به وسیله قوانینی تعیین می شود.(در ابتدا به صورت تصادفی با استفاده از نقاط داده ) و آنها وزن مرکز کلاستر را تعیین می کنند   

برای هر نقطه داده یک مرکز حجم محاسبه می شود. در نتیجه کلاستری هایی از نقاط تشکیل می شود و در مرحله بعد تمام نقاط به کلاستر ها می پیوندند این روند ادامه پیدا می کند تا شرط پایان برسد.



                                

Algorithm 1 Basic K-means algorithm 

 

1- انتخاب  K نقطه به عنوان مرکز حجم های اولیه

   تکرار

2- اضافه کردن نقاط به نزدیک ترین مرکز حجم از کلاستر های K 

3- محاسبه مجدد حجم هر کلاستر

 پایان    زمانی که شرط پایان برسد

 برای محاسبه فاصله مرکز حجم  تا نقطه x از رابطه زیر استفاده می کنیم

ِ

 -شرایط پایان الگوریتم

دستیابی به حداکثر تعداد تکرار ها


مرکز حجم ها کمینه شود(Local or Global)- تغییر زیادی در محل حجم ها به وجود نیاید.

 

c' مرکز حجم به روز شده   و  مقدار جابه جایی که کمتر یا مساوی از حداکثر جابه جایی است

در کلاستر بندی تصاویر شرط خاتمه دوم  استفاده می شود

پیچیدگی K means  از نوع  NP-Hard می باشد

 


 INTRODUCTION
Clustering is an important technique with applications in many fields such as computer vision and genome analysis. The goal of clustering is to group a number of input data points into several sets, so that data points within one set share similar characteristics. The k-means algorithm , also
known as Lloyd’s algorithm, is a well known clustering method and widely used in various applications. The k-means algorithm assigns each data point to a closest cluster. For a data point, its distance to a cluster is defined as its distance to the centroid of the cluster, where the centroid of a cluster is defined as the mean position of all the data points contained in the cluster. kmeans algorithm uses an iterative approach. Initially, the positions of k clusters’ centroids are randomly chosen. In a standard k-means iteration, each data point is labeled to the nearest cluster. After all the data points labeled, the centroid of each cluster is then be updated according to its data points. The labeling step and updating step are iterated until the labels do not change any more. Improving the performance of the k-means algorithm has attracted a lot of research attentions. Among the large number of proposed methods, an important approaches is to use triangle inequalities to eliminate unnecessary distance calculations when searching for the nearest centroid. Algorithms based on this idea have been studied by various researchers. Considerable speedups were reported over the standard k-means algorithm.