TWI430204B - 編碼簿產生方法 - Google Patents

Description

編碼簿產生方法

本發明係關於一種編碼簿產生方法，特別是一種用於影像壓縮技術之編碼簿產生方法。

一般而言，影像壓縮技術中，通常係透過一編碼簿產生方法產生一編碼簿(codebook)，後續在保存圖片及傳輸圖片時，都以此容量較小的編碼簿代替原始輸入影像，進而達到壓縮之目的；相反地，在進行解壓縮時，將編碼簿透過解碼演算法還原成數個還原區塊，最後再將這些還原區塊組合成一還原影像(reconstructed image)，即完成解壓縮之步驟。

習用編碼簿產生方法通常係先對一原始輸入影像進行”切塊”，將該原始輸入影像切成較小且數量較多的原始區塊，透過一向量量化(VQ,Vector Quantization)技術將該些原始區塊轉換為原始向量。再以一編碼演算法對該些原始向量進行處理，以取得數量較少但可代表該原始輸入影像的代表區塊(codeword)，以透過該些代表區塊共同組成該編碼簿。

習用編碼演算法，如LBG演算法，其係由Linde、Buzo及Gray於1980年提出。其概念類似於資料分群方法中之K-means法。其係先進行第一步驟預設一失真度參數ε及欲分群之群數k；接著進行一第二步驟隨機由該些原始向量中選出k個原始向量作為形心點；接著進行一第三步驟將各原始向量與分別與所有之形心點進行歐幾里得距離運算，以將各個原始向量分群至所對應之形心點；接著進行一第四步驟求出各群內原始向量的質心，以作為新的形心點；接著進行一第五步驟計算新的形心點與舊的形心點的差異，亦即失真度，若失真度不小於該失真度參數ε，則重複該第三步驟，若差異大於該失真度參數ε，則完成訓練，所獲得之形心點便可作為該代表區塊共同組成該編碼簿。

一般而言，上述LBG演算法係以隨機初始之方式進行，且原始向量之數目較多且較為複雜，因此以該LBG法進行編碼演算所獲得之結果不甚穩定，使其具有品質較差之缺點。

另一習用編碼演算法，例如自組織映射圖(Self-Organizing Map,SOM)法，如第1圖所示，其係先進行一第一步驟將一影像中之數個像素(pixel)轉換為數個輸入樣本8；接著進行一第二步驟預設N個之神經元9，並隨機選出N個輸入樣本作為該N個神經元9之初始位置；接著進行一第三步驟隨機選出一輸入樣本8，並將該輸入樣本8分別與所有神經元9進行歐幾里得距離運算；接著進行一第四步驟選擇距離最短之神經元9作為一優勝神經元91，並調整該優勝神經元91以及距離該優勝神經元91一鄰近半徑R內之鄰近神經元92，使該優勝神經元91及鄰近神經元92向該一個輸入樣本8產生位移；接著進行一第五步驟判斷是否所有輸入樣本8皆完成該歐幾里得距離運算，若否，則進行該第三步驟，若是，則完成本次訓練，並依一定比例縮小該鄰近半徑R，再進行下一次之訓練，直至迭代次數達一預定之迭代次數後，便可獲得由該數個神經元9所組成之神經網絡圖。如此，所獲得之該些神經元9便可作為編碼簿應用於影像壓縮技術中。

上述習用編碼演算法由於需要經過大量的運算，方可得到令人滿意之神經網絡圖，且當該神經元9之數目越多，或者該輸入樣本8越多時，其需要越長之運算時間，因此，需要耗費大量時間進行運算，造成其具有效率低落之缺點。

另一習用編碼演算法，例如Fast SOMs法，其係針對上述以自組織映射圖法進行改良，其係先以K-means演算法將該數個輸入樣本分為N群，且N係與該神經元之數目相同；再以該N群之群心點分別做為該N個神經元之初始位置，如此，便可獲得初步之神經網絡圖；接著再以該習用自組織映射圖法進行運算，便可縮短自組織映射圖法之運算時間。

然而，上述Fast SOMs法由於該神經元之初始位置係利用二維空間的概念，因此並不適合應用於高維度資料之處理。

另一習用編碼演算法，例如階層式自組織映射圖(HSOM)法，其主要概念係將自組織映射圖法之演算過程分為兩層，例如，若原先自組織映射圖法中之神經元預設為16×16=256個，則其時間複雜度將較高，而此法則是先以16個第一層神經元，利用自組織映射圖法完成第一層訓練後，再將該數個輸入樣本分群至該16個第一層神經元，以分成16群輸入樣本；再分別對每一群之輸入樣本以16個第二層神經元，並利用自組織映射圖法完成第二層訓練後，每一群之輸入樣本中便可獲得16個第二層神經元，如此便可獲得16×16=256個第二層神經元。如此，便可降低自組織映射圖法之時間複雜度。

然而，由於該階層式自組織映射圖法中，第一層及第二層神經元之數目皆以SOM演算法進行訓練，其訓練時間較長；再且，各群內之輸入樣本數量不一，各群卻以相同之神經元數量進行第二層神經元之訓練，相同無法確實描述輸入樣本的真實分佈狀況，使得其具有訓練精確度較差之缺點；再且，於SOM法訓練過程中，可能有些神經元初始位置不佳，造成訓練過程中該些神經元從未成為優勝神經元，而使得該些神經元亦無法確實描述輸入樣本的真實分佈狀況。

基於上述原因，其有必要進一步改良上述習用編碼簿產生方法。

本發明乃改良上述缺點，以提供一種編碼簿產生方法，係以降低產生編碼簿之時間成本為目的。

本發明次一目的係提供一種編碼簿產生方法，係可以提升影像資料之壓縮品質。

本發明再一目的係提供一種編碼簿產生方法，係可以提升神經元之分佈精確度。

根據本發明的編碼簿產生方法，係包含：一切割轉換步驟，將一原始輸入影像分割成數個原始區塊，再將各該原始區塊轉換為原始向量，並設定一編碼簿之大小；一初步分群步驟，以分割式分群演算法對該數個原始向量進行分群，以獲得數個第一形心點，並將該些原始向量分別分群至最接近之第一形心點，以獲得數個群集；一神經元分配步驟，係依失真度比例分配各群集中神經元之數量，再根據分配結果於各群集中選擇數個原始向量作為該神經元，其中該些神經元之總數係與該編碼簿之大小相同；一神經元訓練步驟，係以各群集內之原始向量做為樣本，並以自組織映射圖(SOM)演算法分別對各群集內之神經元進行訓練，以獲得數個最終神經元；一閒置神經元判斷步驟，選取其中一群集，並將該群集中從未成為優勝者之最終神經元定義為閒置神經元；一取代步驟，對該群集內之原始向量以分割式分群演算法進行分群，以獲得對應該閒置神經元數量之第二形心點，並以該第二形心點取代該閒置神經元作為最終神經元；一終止判斷步驟，係判斷是否所有群集之閒置神經元皆已被取代，若判斷為「否」，則重新進行該閒置神經元判斷步驟，若判斷為「是」，則將該些最終神經元所分別對應之向量共同儲存於該編碼簿內。

為讓本發明之上述及其他目的、特徵及優點能更明顯易懂，下文特舉本發明之較佳實施例，並配合所附圖式，作詳細說明如下：請參照第2圖所示，本發明較佳實施例之編碼簿產生方法係包含一切割轉換步驟S1、一初步分群步驟S2、一神經元分配步驟S3、一神經元訓練步驟S4、一閒置神經元判斷步驟S5、一取代步驟S6及一終止判斷步驟S7。

請參照第2圖所示，本發明之編碼簿產生方法係藉由一電腦系統連接至少一資料庫作為執行架構，該資料庫中係存有至少一原始輸入影像，且該原始輸入影像係由數個像素所組成。

請參照第2及3圖所示，本發明之切割轉換步驟S1將一原始輸入影像分割成數個原始區塊，再將各該原始區塊轉換為原始向量11，並設定一編碼簿之大小。舉例而言，若該影像資料為512×512之圖片檔，可將該原始輸入影像切割成16384個原始4×4區塊，則各個原始區塊內將包含有16個像素，接著再透過向量量化(VQ,Vector Quantization)技術將該16384個原始區塊內之像素轉換為原始向量11，並儲存於該資料庫中。該編碼簿之大小係指該編碼簿中所儲存之向量數量，例如，若使用者最終欲以1024個代表區塊表示該原始輸入影像，則該編碼簿之大小便為1024，以容納1024個用以轉換成該些代表區塊之向量。舉例而言，本實施例之編碼簿大小係設定為1024。

請參照第2及4圖所示，本發明之初步分群步驟S2以分割式分群演算法對該數個原始向量11進行分群，以獲得數個第一形心點12，並將該些原始向量11分別分群至最接近之第一形心點12，以獲得數個群集2。更詳言之，於本實施例中，該分割式演算法係選擇為LBG分群演算法，其中，該LBG法詳述如下：該LBG法之第一步驟係先設定欲分群之群數k，該群數k之平方較佳係等於該編碼簿之大小。延續上述例子，該編碼簿之大小為1024=k² ，則該群數k便為；接著進行該LBG法之第二步驟，由該些原始向量11隨機選出32個作為初始形心點之初始位置；接著進行該LBG法之第三步驟，將各原始向量11與該初始形心點進行歐幾里得距離運算，以將各個原始向量11分群至所對應之初始形心點；接著進行該LBG法之第四步驟，求出各個群組內原始向量11的質心，以作為新的形心點；接著進行該LBG法之第五步驟，以計算失真度，該失真度係指新的初始形心點與舊的初始形心點的差異，若失真度不小於該失真度參數，則重複該LBG法之第三步驟，若差異大於該失真度參數，則完成訓練，並獲得32個第一形心點12。再將各個原始向量11分別與所有第一形心點12進行歐幾里得距離運算，並將原始向量11分群至距離最近之第一形心點12。延續上述例子，該第一形心點12之數量係為32個，因此便可將該些原始向量11分為32個群集2。其中，該失真度係以平均平方誤差(Mean Square Error,MSE)進行估算，如式(a)所示：

於式(a)中，W 係指影像之寬；H 係指影像之高；係指原始影像中第(x ,y )個像素與壓縮影像中第(x ,y )像素之位元深度的差值，求得連續兩次之MSE ，即MSE (t )與MSE (t +1)，進而在求得平均失真的變異量△，求得之△MSE 若大於預先設定之收斂閥值則進入下一個迭代，反之則停止，本實施例該LBG法之收斂閥值係設定為0.0001。如此，便可透過分割式演算法對該些大量之原始向量11進行初步分群，以降低後續訓練之複雜度，進而可大幅的降低運算時間。

請參照第2及5圖所示，本發明較佳實施例之神經元分配步驟S3係依失真度比例分配各群集2中神經元13之數量，再根據分配結果於各群集2中選擇數個原始向量11作為該神經元13，其中該些神經元13之總數係與該編碼簿之大小相同。更詳言之，延續上述例子，本發明之編碼簿大小若設定為1024，而該第一形心點12之數量為32，則各群集2中神經元16之數量應配置為32，方可達到該編碼簿之大小32×32=1024。然而，各個群集2中之原始向量11並不相同，原始向量11較多之群集2應該配置較多的神經元13並進行訓練，方可較為準確的表達該區域原始向量11之分佈。因此，本實施例中該神經元13之分佈係依據各群集2之失真度比例進行配置，其主要係先透過式(d)將各群集2中各個樣本(原始向量11)與其所對應第一形心點12的距離總和，式(b)如下所示：

式(b)中，d係為距離總和；x_ir 係為第i個樣本第r個維度；c_r 係為該樣本所對應之第一形心點12之位置。再透過式(c)求出每一群集2內應配置的神經元13的數量，若求得知N_g 值為0，則將其設定為1。式(c)如下所示：

式(c)中的N_g 係指第g群內應配置的神經元13數量，且符號[]係為四捨五入。如此，便可於具有較大距離總和值的群集2內配置較多之神經元13，以符合樣本之真實分佈。

請參照第2及5至8圖所示，本發明之神經元訓練步驟S4係以各群集2內之原始向量11做為樣本，並以自組織映射圖(SOM)演算法分別對各群集2內之神經元13進行訓練，以獲得數個最終神經元14。更詳言之，延續上述例子，如第5圖所示，由該群集2中隨機選取數個原始向量11作為神經元13之初始位置，再透過自組織映射圖演算法以該群集2內之原始向量11作為樣本訓練該數個神經元13。本實施例之自組織映射圖演算法詳述如下：首先，如第6至8圖所示，該SOM法之第一步驟係以式(d)將群集2內其中一原始向量11’分別與對應分配數量之神經元13進行歐幾里得距離計算，選擇距離最接近該原始向量11’之神經元13作為優勝神經元15。式(d)如下所示：

式(d)中，w^* _n 係為優勝神經元15；y_m 係為第m個原始向量11之位置，m=1,2…k，w_n (t)係為第n個神經元13於第t次時的位置。

接著，如第7圖所示，該SOM法之第二步驟係以式(e)調整優勝神經元15及該優勝神經元15鄰近區域S內之鄰近神經元16的位置，式(e)如下所示：

式(e)中，η(t)係為第t次之學習率；r係為神經元13之相對位置，以r ：∥n-n ^* ∥表示；R係為鄰近區域半徑；本實施例中，η(0)=1，鄰近區域半徑。

接著重複進行該SOM法之第一步驟及第二步驟，直至所有原始向量11皆完成距離計算。

接著進行該SOM法之第三步驟，係更新鄰近區域半徑R(t)及學習率η(t)，其中，R(t+1)=R(t)×0.95，若R(t+1)<0.1，則R(t+1)=0.1；η(t+1)=η(t)×0.975，若η(t+1)<0.01，則η(t+1)=0.01。

最後再進行該SOM法之第四步驟，係判斷平均失真率是否大於一門檻值，若判斷為是，則重複進行該SOM法之第一步驟至第三步驟；若判斷為否，則終止該SOM法。該平均失真率之計算詳述如下：先以式(f)計算所有樣本(原始向量11)與其對應的神經元之距離的總和：

式(f)中，x_ir 係為第i個樣本第r個維度；c_r 係為該樣本所對應之神經元之位置。再如式(g)將該距離總和除以樣本數(式(g)中之分母)求得平均失真度，如式(g)所示。

再以式(h)計算平均失真率，便可判斷該平均失真率是否大於該門檻值，本實施例之門檻值係設定為0.0001。

如上述，本發明所採用之SOM法與習用SOM法之差異在於，習知SOM法係以預設之迭代次數作為終止條件，因此即使訓練過程中已相當接近正確分佈，仍須達到預設之迭代次數後方可終止，無法針對分佈差異較大之樣本進行適當調整，將耗費過多時間進行多餘運算；而本發明係進行改良，以平均失真率作為終止條件之判斷依據，因此可針對各種不同樣本分佈進行差異化調整，可避免耗費不必要之時間成本。至此，便完成該神經元訓練步驟S4，並獲得數個最終神經元14，如第8圖所示。

請參照第2、6及9圖所示，本發明較佳實施例之閒置神經元判斷步驟S5係選取其中一群集2’，並將該群集2’中從未成為優勝者(winner)之最終神經元14定義為閒置神經元17。更詳言之，上述之神經元訓練步驟S4中，可能有部分神經元13於SOM訓練過程中從未成為優勝神經元15，而於SOM訓練完成後直接成為該最終神經元14，而造成該神經元13之浪費，所以於此閒置神經元判斷步驟S5中，係將群集2’中從未成為優勝神經元15之最終神經元14定義為閒置神經元17，再進行該取代步驟S6。

請參照第2、9及10圖所示，本發明較佳實施例之取代步驟S6係對該群集2’內的原始向量11以分割式分群演算法進行分群，以獲得對應該閒置神經元17數量之第二形心點18，並以該第二形心點18取代該閒置神經元17作為最終神經元。更詳言之，如第9圖所示，若該群集2’中有3個閒置神經元17，則以分割式演算法對該群集2’內之原始向量11進行分群，本實施例係選擇以LBG分群演算法進行分群，以獲得對應該閒置神經元17數量的3個第二形心點18，並以該3個第二形心點18取代該3個閒置神經元17，如第10圖所示，以避免該閒置神經元17無法真實表達該原始向量11之分佈。

請參照第2、10及11圖所示，本發明較佳實施例之終止判斷步驟S7係判斷是否所有群集2之閒置神經元17皆已被取代，若判斷為「否」，則重新進行該閒置神經元判斷步驟S5，若判斷為「是」，則將該些最終神經元14所分別對應之向量共同儲存於該編碼簿內。更詳言之，接著係判斷是否所有群集2之閒置神經元17是否皆已被該第二形心點18取代，若有群集2內的閒置神經元17尚未被取代，則重新進行該閒置神經元判斷步驟S5；若所有群集2內的閒置神經元17皆已被取代，則將獲得之最終神經元14所對應之向量儲存於該編碼簿內，便可完成本發明之編碼簿產生方法。

透過本發明上述步驟所獲得之編碼簿內的向量可轉換為數個代表區塊，且各個代表區塊皆有一對應之編碼。如此，該原始輸入影像中之原始區塊便可分別與該些代表區塊進行比較，以最接近的代表區塊之編碼代表該原始區塊做為索引，便可以該容量較小的編碼簿代表該原始輸入影像，而達到壓縮之目的。

相反地，在進行解壓縮時，透過解碼演算法將該編碼簿並透過索引還原出數個還原區塊，最後再將這些還原區塊組合成一還原影像(reconstructed image)，即完成解壓縮之步驟。

請參照表一所示，為驗證本發明之壓縮品質及壓縮時間，另對6組影像圖片進行測試，該6組影像圖片分別為Lena、Airplane、Peppers及Boat，並執行？次的獨立運算來取得平均測試結果。該6組影像圖片以4×4的區塊大小來進行前置切塊。其中，由於習用HSOM法無法處理不可開平方得整數之編碼簿大小，因此有些測試表格中的欄位並無測試資料(N/A,Not Available)。而PSNR(Peak Signal-to-Noise Ratio)為一常用來評比壓縮品質之公式，PSNR越高代表壓縮品質越好，如式(i)所示：

式(i)中之MSE如式(a)所示。

其中，表一中之INTSOM係指以本發明所產生之編碼簿進行壓縮之方法。由表一之結果可得知，本發明(INTSOM)之編碼簿產生方法不論於壓縮品質(PSNR)及運算時間上皆較習用LBG、SOM及HSOM法佳。

本發明係提供一種編碼簿產生方法，其係透過該初步分群步驟S2對該些原始向量11進行初步分群，以降低訓練複雜度。

本發明係提供一種編碼簿產生方法，其係根據失真度比例決定各群集2所配置之神經元13數目，以使該些神經元13可更真實的表現該些原始向量11之分佈。

本發明係提供一種編碼簿產生方法，其係以平均失真率作為自組織映射圖(SOM)演算法之終止條件判斷依據，可依據不同樣本分佈之群組而差異化地進行訓練，可避免花費不必要的時間成本進行訓練。

本發明係提供一種編碼簿產生方法，其係以該些第二形心點18取代該些閒置神經元17，以避免神經元17之浪費。

雖然本發明已利用上述較佳實施例揭示，然其並非用以限定本發明，任何熟習此技藝者在不脫離本發明之精神和範圍之內，相對上述實施例進行各種更動與修改仍屬本發明所保護之技術範疇，因此本發明之保護範圍當視後附之申請專利範圍所界定者為準。

[本發明]

11．．．原始向量

11’．．．原始向量

12．．．第一形心點

13．．．神經元

14．．．最終神經元

15．．．優勝神經元

16．．．鄰近神經元

17．．．閒置神經元

18．．．第二形心點

2．．．群集

2’．．．群集

R．．．鄰近區域半徑

[習用]

8．．．輸入樣本

9．．．神經元

91．．．優勝神經元

92．．．鄰近神經元

第1圖：習用編碼演算法之示意圖。

第2圖：本發明之編碼簿產生方法的流程圖。

第3圖：本發明之編碼簿產生方法的原始向量分佈示意圖。

第4圖：本發明之編碼簿產生方法的初步分群步驟之示意圖。

第5圖：本發明之神經元訓練步驟中進行SOM之神經元初始示意圖。

第6圖：本發明之神經元訓練步驟中進行SOM之優勝神經元的示意圖。

第7圖：本發明之神經元訓練步驟中進行SOM之調整神經元位置之示意圖。

第8圖：本發明完成神經元訓練步驟之局部示意圖。

第9圖：本發明完成神經元訓練步驟之示意圖。

第10圖：本發明之閒置神經元判斷步驟的示意圖。

第11圖：本發明之取代步驟的示意圖。

Claims (5)

1. 一種編碼簿產生方法，包含：一切割轉換步驟，將一原始輸入影像分割成數個原始區塊，再將各該原始區塊轉換為原始向量，並設定一編碼簿之大小；一初步分群步驟，以分割式分群演算法對該數個原始向量進行分群，以獲得數個第一形心點，並將該些原始向量分別分群至最接近之第一形心點，以獲得數個群集；一神經元分配步驟，係依失真度比例分配各群集中神經元之數量，再根據分配結果於各群集中選擇數個原始向量作為該神經元，其中該些神經元之總數係與該編碼簿之大小相同；一神經元訓練步驟，係以各群集內之原始向量做為樣本，並以自組織映射圖(SOM)演算法分別對各群集內之神經元進行訓練，以獲得數個最終神經元；一閒置神經元判斷步驟，選取其中一群集，並將該群集中從未成為優勝者(winner)之最終神經元定義為閒置神經元；一取代步驟，對該群集內之原始向量以分割式分群演算法進行分群，以獲得對應該閒置神經元數量之第二形心點，並以該第二形心點取代該閒置神經元作為最終神經元；一終止判斷步驟，係判斷是否所有群集之閒置神經元皆已被取代，若判斷為「否」，則重新進行該閒置神經元判斷步驟，若判斷為「是」，則將該些最終神經元所分別對應之向量共同儲存於該編碼簿內。
2. 依申請專利範圍第1項所述之編碼簿產生方法，其中該神經元分配步驟中，係以式(c)根據失真度比例決定各群集所配置之神經元數目； 其中，d_g 係指第g個群集中各個原始向量與群集中心的距離總和。
3. 依申請專利範圍第1項所述之編碼簿產生方法，其中該神經元訓練步驟中之自組織映射圖演算法係以平均失真率是否低於一門檻值，或者訓練次數是否等於一預定次數作為終止條件之判斷依據。
4. 依申請專利範圍第3項所述之編碼簿產生方法，其中該門檻值係為0.0001。
5. 依申請專利範圍第1項所述之編碼簿產生方法，其中該分割式分群演算法係為LBG演算法。