httpiscsnthuedutwcourse20xxspringisa530100slidesl(已修改)
2025-08-02 23:33 本頁面
【正文】 An Algorithmic Study on Lossless Compression of VQ Index 孫宏民 博士 Outline ? What is VQ ? Related work – GLA algorithm – Cellsplit algorithm – Standard VQ encoding – Image pression with VQ – Search Order Coding algorithm – HuChang algorithm ? motivation ? The improved HuChang algorithm ? Index Searching Algorithm with Index Associated List (ISAIAL) ? Simple Tree Structure for Index Grouping Algorithm (STSIGA) ? conclusion What is Vector Quantization? Vector Codewords y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y12 y11 y13 y14 y15 y16 Aim of vector quantization ? To reduce the size of a database What is VQ? ? Step1:Divide the original image into blocks（ vectors） . ? Step2: Use index to denote each block. index vector codebook How does VQ work in pression? Encoder Decoder Reconstruction Find closest codevector Table lookup Source output Unblock Group into vectors Vector Quantization encoding ? First, construct codebook which is posed of codevector. ? For one vector being encoding, find the nearest vector in codebook. (determined by Euclidean distance) ? Replace the vector by the index in codebook. ? When decoding, find the vector corresponding by the index in codebook. Two important issues ? Codevectors in codebook need representative. It affects the quality of depressed image a lot. So, how to build a good codebook is an important issue. ? Euclidean distance is timeconsuming. How to fasten to search for the nearest vector is also an important issue. GLA (Generalized Lloyd Algorithm) 1. Divide image into blocks. Then we can view one block as kdimension vector. Ex: block: 4x4 , consider 512x512 image, which can be divided into blocks. Each block can be viewed 16 dimension vector. 2. Arbitrarily choose initial codebook. 3. Set these initial codebook as centroids. Other vectors are grouped. Vectors are in the same group when they have the same nearest centroid. 4. Again, to find new centroids for every group. Get a new codebooks. Repeat 2,3 steps until the centroids of every group converge. GLA (Generalized Lloyd Algorithm) 28 27 28 27 27 29 28 29 28 27 27 28 29 29 28 28 28 29 27 28 27 28 27 29 27 28 28 29 28 29 28 27 Euclidean Distance ? ? 211Nnji i jiyx?? ???Index table pp Block (MxN pixels) Vector Training Set GLA ? The GLA ： Group Codebook initial Codebook renew Compute distortion rate Training set test GLA loop stop convergence Standard VQ encoding ? For one vector to be encoding, pute the Euclidean distance with every codevectors in codebook, and find the codevector with smallest Euclidean distance. To encode Codebook i codewords Cell split method For Y, after grouping, find new centorid For Z, after grouping, find new centorid algorithm 1. Divide image into blocks. Choose a block (kdimension) X=(x1, x1,…, x1) as initial vector. 2. Spit X vector into two vector Y=(y1, y1,…, y1) and Z=(z1, z1,…, z1) yi=xi? ,zi=xi+? 3. Y and Z are centroids. For all blocks, find the nearest centroid. Repute the centroid of blocks and get new centroid Y’ and Z’. 4. Recursively, do Y’ and Z’. Repeat 2 ,3 step. Until find enough number of codevector. Image pression with VQ ? Coding and decoding of the codebook： Divide to a Vector set Original image X v Min Euclidean Distance Codebook Channel i ? ?CVV ji
公司管理相關(guān)推薦
鄂ICP備17016276號-1