TWI385592B - 編碼簿產生方法 - 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之初始位置；接著進行一第三步驟隨機選出一輸入樣本81，並將該輸入樣本81分別與所有神經元9進行歐幾里得距離運算；接著進行一第四步驟選擇距離最短之神經元9作為一優勝神經元91，並調整該優勝神經元91以及距離該優勝神經元91一鄰近半徑R內之鄰近神經元92，使該優勝神經元91及鄰近神經元92向該一個輸入樣本81產生位移；接著進行一第五步驟判斷是否所有輸入樣本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)演算法訓練該數個第一層神經元；一分群步驟，將該些原始向量分群至最接近之第一層神經元，以獲得數個群集；一第二層神經元分配步驟，係根據各群集之原始向量的數量，依失真度比例分配各群集中第二層神經元之數量，並根據分配結果於各群集中選擇數個原始向量作為該第二層神經元；及一第二層神經元訓練步驟，係以各群集之原始向量做為樣本，並以自組織映射圖演算法分別對各群集內之第二層神經元進行訓練，以獲得數個最終神經元，並將該些最終神經元所分別對應之向量共同儲存於一編碼簿內。

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

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

請參照第2及3圖所示，本發明之切割轉換步驟S1係將該原始輸入影像分割成數個原始區塊，再將各該原始區塊轉換為原始向量11。舉例而言，若該影像資料為512×512之圖片檔，可將該原始輸入影像切割成16384個原始4×4區塊，則各個原始區塊內將包含有16個像素，接著再透過向量量化(VQ,Vector Quantization)技術將該16384個原始區塊內之像素轉換為原始向量11，並儲存於該資料庫中。

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

於式(a)中，W 係指影像之寬；H 係指影像之高；i (x ,y )-(x ,y )係指原始影像中第(x ,y )個像素與壓縮影像中第(x ,y )像素之位元深度的差值，求得連續兩次之MSE ，即MSE (t )與MSE (t +1)，進而再求得平均失真的變異量△，求得之△MSE 若大於預先設定之收斂閥值則進入下一個迭代，反之則停止，本實施例該LBG法之收斂閥值係設定為0.01。如此，便可將該些大量之原始向量11降低至該些形心點12之數量(256個)，再以該些形心點12作為虛擬輸入樣本進行後續之訓練，便可大幅的降低運算時間。

本發明後續之步驟係針對習用HSOM法進行改良。舉例而言，本實施例最後欲獲得之編碼薄大小係為1024個，如先前技術所述，若以習用HSOM法進行訓練，而將1024分解為32x32，因此第一層神經元設定為32個，而各個群組之第二層神經元亦設定為32個，以對稱式之方式進行第一層及第二層神經元之設定，因此容易落入區域最佳解，而無法正確表示樣本之真實分佈。而本發明之第一層神經元之設置數量較各個群組之第二層神經元之設置數量多，例如，將1024分解為128x8，因此第一層神經元之數量為128，第二層神經元之數量約為8，以不對稱之方式進行第 一層及第二層神經元之設定，可避免落入區域最佳解。接著，進行後續步驟之介紹。

請參照第2、5及6圖所示，本發明之第一層神經元訓練步驟S3係由該數個形心點12中選擇數個作為第一層神經元13，並以所有的形心點12作為樣本，透過自組織映射圖(SOM)演算法訓練該數個第一層神經元13。延續上述例子，由該256個形心點12中隨機選取128個作為第一層神經元13之初始位置，再透過自組織映射圖演算法以該256個形心點12作為樣本訓練該數個第一層神經元13。本實施例之自組織映射圖演算法詳述如下：首先，如第7圖所示，該SOM法之第一步驟係以式(b)將其中一形心點12’分別與該N個(128個)第一層神經元13進行歐幾里得距離計算，選擇距離最接近該形心點12’之第一層神經元為優勝神經元14。式(b)如下所示：

式(b)中，w^* _n 係為優勝神經元14；y_m 係為第m個形心點12之位置，m=1,2…k；w_n (t)係為該第一層神經元13於第t次時的位置。

接著，該SOM法之第二步驟係以式(c)調整優勝神經元14及該優勝神經元14鄰近區域內之鄰近神經元15的位置，式(c)如下所示：w _n (t +1)=w _n (t )+η (t )×exp(-(r /R ))×[y _m -w _n (t )]………式(c)

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

接著重複進行該SOM法之第一步驟及第二步驟，直至所有形心點12皆完成距離計算。

接著進行該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法。該平均失真率之計算詳述如下：先以式(d)計算所有樣本與其對應的神經元之距離的總和：

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

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

如上述，本發明所採用之SOM法與習用SOM法之差異在於，習知SOM法係以預設之迭代次數作為終止條件，因此即使訓練過程中已相當接近正確分佈，仍須達到預設之迭代次數後方可終止，無法針對分佈差異較大之樣本進行適當調整，將耗費過多時間進行多餘運算；而本發明係進行改良，以平均失真率作為終止條件之判斷依據，因此可針對各種不同樣本分佈進行差異化調整，可避免耗費不必要之時間成本。其中，為避免因門檻值設定過低而造成運算次數過高方可收斂，因此較佳另以運算次數達一預定次數作為終止條件之判斷依據之一，例如，將該預定次數設定為500次，即使該平均失真率尚未達門檻值，而訓練次數達500次，則終止該SOM法之訓練。至此，便完成該第一層神經元訓練步驟S3。

請參照第2及8圖所示，本發明較佳實施例之分群步驟S4係將該些原始向量11分群至最接近之第一層神經元13，以獲得數個群集2。更詳言之，將各個原始向量11分別與所有第一層神經元13進行歐幾里得距離運算，並將原始向量11分群至距離最近之第一層神經元13。舉例而言，延續上述例子，該第一層神經元13之數量係為128個，因此便可將該些原始向量11分為128個群集2。

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

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

請再參照第2及9圖所示，本發明較佳實施例之第二層神經元訓練步驟S6係以各群集2之原始向量11做為樣本，並分別對各群集2內之第二層神經元16以自組織映射圖(SOM)演算法進行訓練，以獲得數個最終神經元，並將該些最終神經元所分別對應之向量共同儲存於一編碼簿內。更詳言之，此步驟所使用之自組織映射圖(SOM)演算法係與該第一層神經元訓練步驟S3相同，同樣係以平均失真率作為終止條件之依據，因此於該些不等數量之第二層神經元16之訓練上更為適用，以避免數量較少之第二層神經元16花費過多之時間成本進行訓練。至此，該第二層神經元16完成訓練便為該最終神經元，延續上述例子，共有1024個最終神經元，再將該1024個最終神經元所對應之向量儲存於一編碼簿內，便可完成本發明之編碼簿產生方法。

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

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

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

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

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

本發明係提供一種編碼簿產生方法，其係透過該初步分割步驟S2獲得該數個形心點12，以該些數量較少之形心點12對該第一層神經元13進行訓練，可降低訓練時間。

本發明係提供一種編碼簿產生方法，其係透過不對稱之方式進行第一層神經元13及第二層神經元16數量之設定，且該第一層神經元13之數量係大於各群集2中第二層神經元16之數量，以避免落入區域解。

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

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

[本發明]

11．．．原始向量

12．．．形心點

12’．．．形心點

13．．．第一層神經元

14．．．優勝神經元

15．．．鄰近神經元

16．．．第二層神經元

2．．．群集

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

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

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

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

第5圖：本發明完成初步分割步驟的局部放大示意圖。

第6圖：本發明之編碼簿產生方法的第一層神經元訓練步驟之示意圖。

第7圖：本發明之編碼簿產生方法的第一層神經元訓練步驟進行SOM法之示意圖。

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

第9圖：本發明之編碼簿產生方法的第二層神經元訓練步驟之示意圖。

Claims (5)

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