Vector Quantization的疑問

hotball · 文章由 **hotball** » 2003-05-22 10:37

這…當然是要選一個適當的 code book 和 vector 的大小啊…
像我之前舉的例子，用 2x2 pixel block 為單位，使用 12 bits code book，則 code book 的大小是 4,096×12 bytes = 48KB。圖的壓縮比是 1:8。因此，只要原圖的大小超過 53.33KB，就會有壓縮的效果。

Yann · 文章由 **Yann** » 2003-06-15 01:52

小弟提一下自己的想法..請各位指教一下..我只懂一些概念..
1.細胞圖名稱應該是Voronoi diagram吧..它的性質很長..我稍微描述一下..
每個細胞內的重心..與另一個細胞的重心..兩重心間的邊界為兩點間的中垂線..
因此任兩重心間的距離為最短(與其它重心距離相較)..
所以Voronoi diagram圖所建立出來的應該是相當均勻的取樣..

2.VQ中的code book一般不會很大..因為要達到壓縮的話..
絕對不會取一對一的code book..不然就不必做VQ..
以同樣的VQ方法而言..code book的大小與品質成正比..
其中的平衡就看演算法的威力了..好的演算法可以取較小的code book..
或者在相同code book卻有更好的品質(通常計算Mean Square Error)..

hotball · 文章由 **hotball** » 2003-06-16 20:49

Yann 寫:小弟提一下自己的想法..請各位指教一下..我只懂一些概念..
1.細胞圖名稱應該是Voronoi diagram吧..它的性質很長..我稍微描述一下..
每個細胞內的重心..與另一個細胞的重心..兩重心間的邊界為兩點間的中垂線..
因此任兩重心間的距離為最短(與其它重心距離相較)..
所以Voronoi diagram圖所建立出來的應該是相當均勻的取樣..

其實 Voronoi diagram 的性質很簡單，就是考慮集合中每個「重心」都屬於不同的群組，則對於集合裡的任何一個成員，它所屬的「群組」就是和它距離最近的「重心」的群組。至於中垂線等等是引申而得的性質。要注意 Voronoi diagram 並不限於平面空間，任何有良好定義的「距離」的空間，都可以有 Voronoi diagram。

不過，平面空間的 Voronoi diagram 有快速演算法，而 3D 以上目前還沒有這樣的演算法。

2.VQ中的code book一般不會很大..因為要達到壓縮的話..
絕對不會取一對一的code book..不然就不必做VQ..
以同樣的VQ方法而言..code book的大小與品質成正比..
其中的平衡就看演算法的威力了..好的演算法可以取較小的code book..
或者在相同code book卻有更好的品質(通常計算Mean Square Error)..

這其實是 VQ 最大的缺點，就是壓縮的速度慢。要找出好的 code book 非常不容易，太簡單的演算法效果又差。而 minimise mean square error 也不是最好的方法。一般來說，VQ 主要還是用在需要能快速進行解壓縮的場合（例如顯示晶片要用的貼圖就是很好的例子），不然的話，通常會使用別的方法。

Yann · 文章由 **Yann** » 2003-06-17 16:20

hotball大說得我清楚多了..
因此可以引出一個重點..就是重心要如何決定..如何才算一個群組..
對應到VQ..就是要決定code book..
這也是一般分群(clustering)的最大問題..
對於一組資料..要分成幾群才適當..不同的參數設定會產不同數目的群組..
當決定重心後..才能畫細胞圖(決定細胞邊界)..