TWI462057B

TWI462057B - 基於哈達瑪轉換之影像壓縮電路及方法

Info

Publication number: TWI462057B
Application number: TW098140923A
Authority: TW
Inventors: Ren Kuan Liang; Jen Shi Wu
Original assignee: Mstar Semiconductor Inc
Priority date: 2009-12-01
Filing date: 2009-12-01
Publication date: 2014-11-21
Also published as: TW201120818A; US8768085B2; US20110129163A1

Description

基於哈達瑪轉換之影像壓縮電路及方法

本發明係有關於影像壓縮，尤指一種基於哈達瑪轉換之影像壓縮電路及方法。

在進行影像壓縮時，哈達瑪轉換(Hadamard transform)是種常用的技術。在先前技術中，對影像(通常為靜態畫面)執行哈達瑪正轉換(forward Hadamard transform，為行文方便，下文亦以哈達瑪轉換稱之)時，係以同屬一條掃描線之8個像素為單位影像區塊，並將8階(即8×8)哈達瑪矩陣(Hadamard matrix)乘上8個像素值所組成之8×1矩陣，以轉換至頻域，而相乘所得之8×1矩陣之8個矩陣元素即為轉換值，如下所示：

式(1)中，H₈ 為8階哈達瑪矩陣，P[8]為8個像素P0~P7所組成之8×1矩陣；H₈ ＊P[8]則為8×1矩陣，其包含8個轉換值，即1個直流(DC)值及7個交流(AC)值AC0~AC6，其中DC值代表8個像素P0~P7的平均值，AC0~AC6則依序代表從低頻至高頻的部份。在執行完哈達瑪轉換後，再對轉換值進行量化(quantization)，亦即將轉換值之數個最低位元(LSB)捨棄，以減少位元數，達到影像壓縮的目的。

哈達瑪轉換的優點之一，在於執行哈達瑪反轉換(inverse Hadamard transform)時，所使用之哈達瑪反矩陣就是原本進行正轉換時所用之哈達瑪矩陣，以式(1)而言，若以H₈ ^-1 代表H₈ 的反矩陣，則H₈ ^-1 =H₈ ；另一優點則是，轉換過程只需執行簡單的加減法，這點從式(1)可看出。

由於哈達瑪轉換具有如上所述的優點，因此，如能基於哈達瑪轉換，設計出更具彈性及效率的影像壓縮電路，則可達到更好的影像壓縮效果。

有鑑於此，本發明之一目的，在於提供一種基於哈達瑪轉換之影像壓縮電路及方法，以提供更具彈性及效率的影像壓縮功能。

本發明揭露一種基於哈達瑪轉換之影像壓縮方法，包含下列步驟：依據2^k ×2^k 之哈達瑪矩陣，對2^k 個像素值執行哈達瑪轉換，以產生2^k 個轉換值，其中k為正整數，每一轉換值包含一大小部分；對至少一轉換值進行量化；以及將所有量化與未量化之轉換值儲存至一記憶體；其中，若2^k 個轉換值中，至少有一第一轉換值之大小部份之前n個最高位元皆為零，n為正整數，則在將第一轉換值儲存至記憶體時，省略該前n個最高位元，並產生一對應之省略記錄，儲存至記憶體。

本發明另揭露一種基於哈達瑪轉換之影像壓縮方法，包含下列步驟：依據2^k ×2^k 之哈達瑪矩陣與2^k ×2^k 之調整矩陣的乘積，對2^k 個像素值執行哈達瑪轉換，以產生2^k 個轉換值，k為正整數，其中至少有一轉換值為零；以及儲存所有非零轉換值至一記憶體；其中，調整矩陣滿足以下條件：若將2^k 個像素值分成G個像素組，每一像素組包含2^k /G個相鄰像素值，且將調整矩陣乘以2^k 個像素值所組成之2^k ×1之第一矩陣，以轉換第一矩陣為2^k ×1之第二矩陣，則在第二矩陣中，第一矩陣之各像素值係轉換為該像素值所屬之像素組之平均像素值。

本發明另揭露一種基於哈達瑪轉換之影像壓縮方法，包含下列步驟：選取第一模式或第二模式之哈達瑪轉換；若選取第一模式，則依據2^k ×2^k 之哈達瑪矩陣，k為正整數，對2^k 個像素值執行哈達瑪轉換，以產生2^k 個第一轉換值，並對至少一第一轉換值進行量化；以及若選取第二模式，則依據該哈達瑪矩陣與2^k ×2^k 之調整矩陣的乘積，對2^k 個像素值執行哈達瑪轉換，以產生2^k 個第二轉換值，其中至少有一第二轉換值為零；其中，調整矩陣滿足以下條件：若將2^k 個像素值分成G個像素組，每一像素組包含2^k /G個相鄰像素值，且將調整矩陣乘以2^k 個像素值所組成之2^k ×1之第一矩陣，以轉換第一矩陣為2^k ×1之第二矩陣，則在第二矩陣中，第一矩陣之各像素值係轉換為該像素值所屬之像素組之平均像素值；且，該選取步驟係依據在第二模式下，2^k 個像素值之各像素值與其所屬像素組之平均像素值之差值，來決定選取第一模式或第二模式之哈達瑪轉換。

在敘述本發明之實施例前，先說明2^k 階(即2^k ×2^k )之哈達瑪矩陣的產生方式，其中k為正整數。若H是d階的哈達瑪矩陣，則藉由可產生2d階的哈達瑪矩陣，而反覆執行此過程，即可依序產生1階、2階、4階...之哈達瑪矩陣如下：

因此，藉由以上方式，可產生任何2^k 階之哈達瑪矩陣。

以下所述之各實施例皆是基於哈達瑪轉換來進行影像壓縮，以提供更具彈性及效率的影像壓縮功能。此處的影像可為靜態畫面或影片，而實施例中所提及之像素值可為像素之亮度值或色度值。第1圖係本發明之影像壓縮電路之第一實施例的方塊圖，其中，影像壓縮電路10包含哈達瑪轉換單元11及記憶體12。哈達瑪轉換單元11係依據2^k 階哈達瑪矩陣，對2^k 個像素值執行哈達瑪轉換，以產生2^k 個轉換值。因此，在此第一實施例中，係以2^k 個像素為單位影像區塊來執行哈達瑪轉換。此2^k 個像素可屬於同一條掃描線(即1×2^k 之影像區塊)，或是分屬於2^m 條掃描線(即2^m ×2^k-m 之影像區塊)，m為正整數。哈達瑪轉換單元11在執行哈達瑪轉換時，係將2^k ×2^k 之哈達瑪矩陣乘上2^k 個像素值所組成之2^k ×1矩陣，而相乘所產生之2^k ×1矩陣之2^k 個矩陣元素即為轉換值，其包含1個DC值及2^k -1個AC值。AC值之值域涵蓋正負範圍，因此AC值包含一符號位元(sign bit，即第1個最高位元(MSB))，其餘位元則屬大小部份(magnitude part)；DC值之值域為不小於零，所以其所有位元皆屬大小部份，而不包含符號位元。

接著，為了達到影像壓縮的目的，哈達瑪轉換單元11須對至少一轉換值進行量化(quantization)，以減少2^k 個轉換值之總位元數。哈達瑪轉換單元11可預先設定哪個(或哪些)轉換值需進行量化以及每個需量化之轉換值的量化位元數(quantization bit number)。由於人眼對於低頻的影像訊號較為敏感，因此對於低頻之轉換值可保留較多量化位元，而高頻之轉換值則保留較少量化位元。接著，哈達瑪轉換單元11依據所設定之量化位元數(以b表示)，保留轉換值的前b個最高位元，其餘位元則捨棄，以完成量化。另一種作法則是，若轉換值之第b+1個最高位元為1，則進位至第b個最高位元，並保留進位後的前b個最高位元，捨棄其他位元；若第b+1個最高位元值為0，則不進位而保留原來的前b個最高位元，其餘位元直接捨棄。在執行完量化後，哈達瑪轉換單元11將所有量化與未量化之轉換值儲存至記憶體12。

須注意的是，當2^k 個轉換值中，至少有一轉換值(在第一實施例中稱為第一轉換值)之大小部份的前n個最高位元皆為零，n為正整數時，若第一轉換值不需執行量化，則哈達瑪轉換單元11在將第一轉換值儲存至記憶體12時，可省略其大小部分之前n個最高位元不予儲存，並產生一對應之省略記錄；若第一轉換值需執行量化，則哈達瑪轉換單元11在對第一轉換值進行量化時，亦可先省略其大小部分之前n個最高位元，並產生對應之省略記錄，接著再就剩下之位元進行量化，量化後再儲存至記憶體12。前述省略記錄亦需儲存至記憶體12，惟其格式並無限制，只要能記錄是哪個轉換值省略了多少個最高位元即可。省略記錄的用處，在於進行影像解壓縮時，可依據省略記錄將儲存於記憶體12中之轉換值還原，以便正確執行哈達瑪反轉換。前述省略前n個為零之最高位元的作法有兩個好處，一是當n值較大或是有較多第一轉換值時，需要儲存的位元數(即省略後的轉換值+省略記錄的總位元數)可減少，以節省記憶體空間；另一是若第一轉換值需量化，則經過省略後之第一轉換值，在量化後可比未省略的情形保留更多資訊，提昇影像壓縮的品質。為了確保達到影像壓縮的目的，在經過前述量化與省略處理後，所有儲存至記憶體12之轉換值的總位元數與省略記錄之位元數兩者之和，應小於原本2^k 個像素值之總位元數。

較佳地，哈達瑪轉換單元11係於2^k 個轉換值中所有2^k -1個AC值之大小部分的前n個最高位元皆為零時，才進行前述之省略處理，亦即，在儲存任一AC值至記憶體12時，不論該AC值有無經過量化，其大小部分的前n個為零的最高位元皆省略而不儲存。而由於事先已知道是哪些轉換值(即所有AC值)會執行此省略動作，因此省略記錄只需記錄n值，使省略記錄本身的位元數可以降低。舉例而言，若k=3且每個像素值為8個位元(亦即，像素值之值域為0~255)，則依前述式(1)可知，所有AC值AC0~AC6的值域為±(255＊4)之區間，所以每個AC值為11個位元，其包含1個符號位元及10位元之大小部份。藉由以下方式，可判斷n值的大小，即可知每個AC值可省略多少位元：

若2⁸ <=max(|ACx|)<2⁹ ，x=0~6，則n=1；2⁷ <=max(|ACx|)<2⁸ ，則n=2...依此類推，其中max()代表取最大值。

第2圖係本發明之影像壓縮電路之第二實施例的方塊圖，其中，影像壓縮電路20包含哈達瑪轉換單元21及記憶體22。哈達瑪轉換單元21係依據2^k ×2^k 之哈達瑪矩陣與一2^k ×2^k 之調整矩陣的乘積，對2^k 個像素值執行哈達瑪轉換，以產生2^k 個轉換值，其中至少有一轉換值為零。若所有非零轉換值之總位元數不小於2^k 個像素值之總位元數，則哈達瑪轉換單元21再對至少一非零轉換值進行量化，以使所有量化與未量化之非零轉換值的總位元數小於2^k 個像素值之總位元數，而達到影像壓縮的效果。接著，哈達瑪轉換單元21將所有量化與未量化之非零轉換值儲存至記憶體22，以供後續要進行影像解壓縮時使用。另一種作法則是，哈達瑪轉換單元21預先設定好影像壓縮率，並依據此影像壓縮率決定哪個(或哪些)非零轉換值需進行量化以及各個需量化之非零轉換值的量化位元數，以使所有量化與未量化之非零轉換值的總位元數等於2^k 個像素值之總位元數乘上影像壓縮率，以實現該影像壓縮率。例如，若k=3且每個像素值為8位元，則2^k 個像素值之總位元數為64位元，此時若設定影像壓縮率為75%，則所有量化與未量化之非零轉換值的總位元數須等於64＊75%=48。

第二實施例的特徵之一，在於將哈達瑪矩陣乘上調整矩陣後，可產生一簡化的哈達瑪矩陣，利用此簡化的哈達瑪矩陣進行哈達瑪轉換，可使所產生之2^k 個轉換值中，至少有一個為零，以達到更高的影像壓縮率，或者在進行轉換值的量化時可保留更多的量化位元。此調整矩陣滿足以下條件：若將2^k 個像素值分成G個像素組，每一像素組包含2^k /G個相鄰像素值，且將調整矩陣乘以2^k 個像素值所組成之2^k ×1之第一矩陣，以轉換第一矩陣為2^k ×1之第二矩陣，則在第二矩陣中，第一矩陣之各像素值係轉換為該像素值所屬像素組之平均像素值。以下以數個實例來說明調整矩陣如何產生：

<例1>G等於2^k-1 ，而每一像素組包含兩個垂直相鄰像素值。以k=3為例，則以2^k =8個像素值為單位影像區塊來執行哈達瑪轉換，且此8個像素分成G=4個像素組。假設8個像素值(表示為P0~P7)係來自兩條掃描線，亦即此8個像素值為2×4之影像區塊，則P0、P2、P4、P6各與其垂直相鄰像素P1、P3、P5、P7形成一像素組，如第3A圖所示。此時，調整矩陣(在例1中以Av表示)應滿足下式：

從式(2)可看出第一矩陣M1中之各像素值在第二矩陣M2中皆轉換為該像素值所屬像素組之平均像素值。從式(2)可推得：

將8階之哈達瑪矩陣H₈ 乘上調整矩陣Av，可得到大幅簡化之8階哈達瑪矩陣，如下所示：

利用此大幅簡化之8階哈達瑪矩陣來對像素值P0~P7進行哈達瑪轉換，可得：

亦即，所產生之8個轉換值包含1個DC值及3個AC值(AC0~AC2)，其餘4個皆為零。

<例2>G等於2^k-1 ，而每一像素組包含兩個水平相鄰像素值。同樣以k=3為例，則以8個像素值為單位影像區塊，並分成4個像素組。同樣假設8個像素值P0~P7來自兩條掃描線，則P0、P1、P4、P5各與其水平相鄰像素P2、P3、P6、P7形成一像素組，如第3B圖所示。此時，調整矩陣(在例2中以Ah表示)應滿足下式：

從式(3)可看出第一矩陣M1中之各像素值在第二矩陣M2中皆轉換為該像素值所屬像素組之平均像素值。從式(3)可推得：

將8階之哈達瑪矩陣H₈ 乘上調整矩陣Ah，可得到大幅簡化之8階哈達瑪矩陣，如下所示：

亦即，所產生之8個轉換值包含1個DC值及3個AC值(AC0、AC5及AC6)，其餘4個皆為零。

<例3>G等於2^k-2 ，而每一像素組包含排列方式為2×2的四個像素值，亦即每一像素組為2×2之影像區塊。同樣以k=3為例，則以8個像素值為單位影像區塊，並分成2個像素組。同樣假設8個像素值P0~P7來自兩條掃描線，則P0與相鄰像素P1、P2、P3形成一像素組，P4與相鄰像素P5、P6、P7形成另一像素組，如第3C圖所示。此時，調整矩陣(在例3中以Aq表示)應滿足下式：

從式(4)可看出第一矩陣M1中之各像素值在第二矩陣M2中皆轉換為該像素值所屬像素組之平均像素值。從式(4)可推得：

將8階之哈達瑪矩陣H₈ 乘上調整矩陣Aq，可得到更大幅簡化之8階哈達瑪矩陣，如下所示：

利用此更大幅簡化之8階哈達瑪矩陣來對像素值P0~P7進行哈達瑪轉換，可得：

亦即，所產生之8個轉換值包含1個DC值及1個AC值(AC0)，其餘6個皆為零。

<例4>G等於2^k-2 ，而每一像素組包含排列方式為1×4的四個像素值，亦即此四個像素值屬於同一條掃描線。同樣以k=3為例，則以8個像素值為單位影像區塊，並分成2個像素組。同樣假設8個像素值P0~P7來自兩條掃描線，則P0與P2、P4、P6形成一像素組，P1與P3、P5、P7形成另一像素組，如第3D圖所示。藉由與<例3>類似的方式，可推導出對應的調整矩陣Ar以及大幅簡化後之哈達瑪矩陣如下：

而利用此大幅簡化之哈達瑪矩陣對像素值P0~P7進行哈達瑪轉換時，所產生之8個轉換值包含1個DC值及1個AC值(AC0)，其餘6個皆為零。

在第二實施例中，除了可利用簡化的哈達瑪矩陣進行哈達瑪轉換外，還可使用原本未簡化的哈達瑪矩陣來執行哈達瑪反轉換，只是此時反轉換的結果並非原本的像素值，而是原像素值所屬像素組的平均像素值，如下式所示：

H^-1 ＊(H＊A＊M)=(H^-1 ＊H)＊(A＊M)=A＊M　式(5)

式(5)中，H與H^-1 分別為哈達瑪矩陣與哈達瑪反矩陣(H^-1 =H)，A為調整矩陣，M為單位影像區塊內之所有像素值所組成的矩陣，H＊A＊M則為利用簡化的哈達瑪矩陣(即H＊A)所進行之哈達瑪轉換。式(5)中，將H^-1 乘上(H＊A＊M)以執行反轉換，可得結果為A＊M，亦即將調整矩陣A乘上M，如此可將M中各像素值轉換為該像素值所屬像素組之平均像素值，而此即是原本調整矩陣所須滿足之條件，如前文所述。因此，原本2^k 個像素值在分成G個像素組，並經過簡化過後之哈達瑪矩陣的正轉換及原本哈達瑪矩陣的反轉換後，會產生G個影像區塊，每一影像區塊內之各像素值皆相同。換言之，當G值越大，影像解析度越大，反之亦然。應注意的是，實際在執行哈達瑪反轉換時，由於原本正轉換(即H＊A＊M)所產生之轉換值至少有一部分已執行過量化，因此反轉換的結果會與式(5)有所誤差，不過此誤差為量化所造成，與哈達瑪正轉換或反轉換本身無關。

從上述幾個例子可看出，G值越小，影像壓縮率越高，但代價是某些頻率的AC值會消失，造成影像解析度變小及影像細節的流失。實作上，可依實際需要來選擇適當的G值，例如，若希望提高影像解析度及保留較多的影像細節，可選擇較大的G值；若希望提高影像壓縮率以節省記憶體空間，則可選擇較小的G值。

在此第二實施例中，作為哈達瑪轉換之單位影像區塊的2^k 個像素值，可屬於同一條掃描線，或是分屬於2^m 條掃描線。在像素組數相同(即G值相同)的情況下，若2^k 個像素值分屬於2^m 條掃描線，像素組可具有較多種的像素排列方式；但若屬於同一條掃描線，則像素組僅具有一種像素排列方式。舉例來說，在前述例3與例4中，當2^k =8個像素值分屬兩條掃描線時，像素組可有1×4與2×2兩種像素排列方式，但若8個像素值同屬一條掃描線，則像素組僅有1×4的像素排列方式。

進一步言，調整矩陣的形態，還依據以下因素而決定：

(1)第一矩陣中2^k 個像素值的排列順序。例如，在式(2)與式(3)之第一矩陣M1中，若像素值P0~P7的排列順序改變，則所推得之調整矩陣Av與Ah也會隨之改變，且仍可用以簡化8階之哈達瑪矩陣。

(2)G值的大小。從前述例子可知，調整矩陣的形態會隨著G值的大小而改變：當k=3時，若G=4，則可推得如例1與例2中之調整矩陣Av與Ah；若G=2，則可推得如例3與例4中之調整矩陣Aq與Ar。

(3)每一像素組中2^k /G個相鄰像素值的排列方式。例如，在例1中，每一像素組包含兩個垂直相鄰像素值，所推得之調整矩陣為Av；在例2中，每一像素組包含兩個水平相鄰像素值，而所推得之調整矩陣則為Ah。

綜言之，調整矩陣除了滿足前述「在第二矩陣中，第一矩陣之各像素值係轉換為該像素值所屬像素組之平均像素值」的條件外，其形態還依據前述(1)~(3)之因素而決定。

在一較佳實施例中，哈達瑪轉換單元21可提供至少兩種形態之調整矩陣，於執行哈達瑪轉換時擇一使用。哈達瑪轉換單元21可依據所需之影像解析度及壓縮率(例如，由使用者所設定的)，選擇適當形態之調整矩陣來使用。另一種作法是，哈達瑪轉換單元21估計2^k 個像素值在分別使用各種形態之調整矩陣執行哈達瑪轉換時，所分別對應之轉換誤差，並依據此轉換誤差，選取其中一種形態之調整矩陣來執行哈達瑪轉換。此轉換誤差代表著2^k 個像素值在執行哈達瑪正轉換與反轉換之前與之後的差異度。由於各像素值在執行哈達瑪正轉換及反轉換後，會轉變為其所屬像素組之平均像素值(雖然可能有量化誤差，但為求簡化計算，此處可忽略不計)，因此哈達瑪轉換單元21可依據各像素值與其所屬像素組之平均像素值的差值，來估計每一種形態之調整矩陣所對應之轉換誤差。例如，哈達瑪轉換單元21可依據各像素值與其所屬像素組之平均像素值之差值的總和，來估計轉換誤差；或者，亦可依據各像素值與其所屬像素組之平均像素值之差值中的最大者，來估計轉換誤差。

當每一像素組僅包含兩個相鄰像素時，不論是水平相鄰或垂直相鄰，估計轉換誤差的方式可進一步簡化。假設任一像素組包含兩像素P1與P2，則P1、P2與此像素組之平均像素值(即)的差值分別為、，將此兩差值相加即得|P1-P2|，亦即此像素組之兩像素值的差值。因此，前述估計轉換誤差時所依據之「各像素值與其所屬像素組之平均像素值之差值的總和或最大者」即可簡化為「各像素組之兩像素值之差值的總和或最大者」。

在此較佳實施例中，哈達瑪轉換單元21還產生一對應之形態記錄(其格式並無限制)，儲存至記憶體22，用以記錄選用何種形態之調整矩陣來執行哈達瑪轉換。此時，為達影像壓縮目的，所有量化與未量化之非零轉換值的總位元數與該形態記錄之位元數兩者之和，需小於2^k 個像素值之總位元數。由於不同形態之調整矩陣會產生對應之不同頻率的非零轉換值，如前述例1中，調整矩陣Av產生DC及AC0~AC2的非零轉換值，例2中，調整矩陣Ah則產生DC、AC0、AC5及AC6的非零轉換值，因此後續在進行影像解壓縮時，藉由參照記憶體22所儲存之形態紀錄，即可知道記憶體22所儲存的是哪些頻率的非零轉換值，以便正確地執行哈達瑪反轉換。

此較佳實施例還有一優點：不管選用何種形態之調整矩陣來執行哈達瑪轉換，後續執行哈達瑪反轉換時所使用之哈達瑪反矩陣皆相同(即原本未經簡化之哈達瑪矩陣)，因此，後續在進行影像解壓縮時，可共用同一套哈達瑪反轉換電路(圖未顯示)，以節省硬體。

前述第一實施例中，將轉換值之大小部分之前n個為零的最高位元予以省略的作法，亦可應用於第二實施例。由於作法相同，此處不再贅述。

第4圖係本發明之影像壓縮電路之第三實施例的方塊圖，其中，影像壓縮電路40包含哈達瑪轉換單元41及記憶體42。哈達瑪轉換單元40可依據第一模式或第二模式執行哈達瑪轉換，而第一模式與第二模式分別為前述第一實施例與第二實施例的作法。換言之，第三實施例為第一實施例與第二實施例的結合。具體而言，在第一模式下，哈達瑪轉換單元41依據2^k ×2^k 之哈達瑪矩陣，對2^k 個像素值執行哈達瑪轉換，以產生2^k 個第一轉換值，並對至少一第一轉換值進行量化；在第二模式下，哈達瑪轉換單元41依據2^k ×2^k 之哈達瑪矩陣與2^k ×2^k 之調整矩陣的乘積，對2^k 個像素值執行哈達瑪轉換，以產生2^k 個第二轉換值，其中至少有一第二轉換值為零。記憶體42耦接至哈達瑪轉換單元41，用以儲存在第一模式下之所有量化與未量化之第一轉換值以及在第二模式下之所有非零之第二轉換值。

進一步言，在第一模式下，每一第一轉換值包含一大小部分，若2^k 個第一轉換值中，至少有一第三轉換值之大小部分之前n個最高位元皆為零，則當哈達瑪轉換單元41在將第三轉換值儲存至記憶體42時，省略該前n個最高位元，並產生一對應之省略記錄，儲存至記憶體42。此外，若哈達瑪轉換單元41對此第三轉換值進行量化，則量化後之第三轉換值不包含該前n個最高位元。另一方面，在第二模式下，若所有非零之第二轉換值之總位元數不小於2^k 個像素值之總位元數，哈達瑪轉換單元41對至少一非零之第二轉換值進行量化，以使所有量化與未量化之非零之第二轉換值的總位元數小於2^k 個像素值之總位元數，其中，該至少一非零之第二轉換值係於量化後才儲存至記憶體42。至於第二模式所使用之調整矩陣所須滿足的條件，已如第二實施例中所述，此處不再贅述。

第三實施例除了結合第一實施例與第二實施例，還提供如何選取適當模式以執行哈達瑪轉換的方法。哈達瑪轉換單元41可依據在第二模式下，2^k 個像素值之各像素值與其所屬像素組之平均像素值之差值，來決定選取第一模式或是第二模式。舉例來說，哈達瑪轉換單元41可將各像素值與其所屬像素組之平均像素值之差值的總和與一臨界值做比較，再依據比較結果來決定選取第一模式或第二模式，例如，當該總和小於該臨界值時，表示以第二模式執行哈達瑪轉換之轉換誤差是可接受的，因此選取第二模式，而當該總和不小於該臨界值時，表示第二模式之轉換誤差過大，因此改選第一模式較為妥當；或者，哈達瑪轉換單元41亦可將各像素值與其所屬像素組之平均像素值之差值中的最大者與另一臨界值做比較，並依據比較結果來決定選取第一模式或第二模式。

另一種選取適當模式的方法則是，哈達瑪轉換單元41除了計算在第二模式下，2^k 個像素值之各像素值與其所屬像素組之平均像素值之差值，還計算在第一模式下，各第一轉換值在經過哈達瑪反轉換後與原本2^k 個像素值中之對應像素值之差值，再將前述此兩種差值做比較，以決定選取第一模式或第二模式。舉例來說，哈達瑪轉換單元41可將第一模式與第二模式下計算所得之差值分別加總，以比較此兩種差值的總和來選取適當模式；哈達瑪轉換單元41亦可直接將第一模式下所得之差值中的最大者，直接與第二模式下所得之差值中的最大者做比較，以決定選取哪個模式。

第5圖係本發明之影像壓縮方法之第一實施例的流程圖，其係對應於前述影像壓縮裝置之第一實施例。在步驟51中，依據2^k ×2^k 之哈達瑪矩陣，對2^k 個像素值執行哈達瑪轉換，以產生2^k 個轉換值，其中每一轉換值包含一大小部分。在步驟52中，對至少一轉換值進行量化。在步驟53中，將所有量化與未量化之轉換值儲存至一記憶體。其中，若該2^k 個轉換值中，至少有一第一轉換值之該大小部份之前n個最高位元皆為零，n為正整數，則在將該第一轉換值儲存至該記憶體時，省略該前n個最高位元，並產生一對應之省略記錄，儲存至該記憶體。

第6圖係本發明之影像壓縮方法之第二實施例的流程圖，其係對應於前述影像壓縮裝置之第二實施例。在步驟61中，依據2^k ×2^k 之哈達瑪矩陣與一2^k ×2^k 之調整矩陣的乘積，對2^k 個像素值執行哈達瑪轉換，以產生2^k 個轉換值，其中至少有一轉換值為零。在步驟62中，若所有非零轉換值之總位元數不小於2^k 個像素值之總位元數，則對至少一非零轉換值進行量化，以使所有量化與未量化之非零轉換值的總位元數小於2^k 個像素值之總位元數。在步驟63中，儲存所有量化與未量化之非零轉換值至一記憶體。至於調整矩陣所須滿足的條件，已如影像壓縮裝置之第二實施例中所述，此處不再贅述。

在一較佳實施例中，調整矩陣具有至少兩種形態，而步驟61還包含產生一形態記錄，用以記錄使用何種形態之調整矩陣來執行哈達瑪轉換，其中所有非零轉換值之總位元數與該形態記錄之位元數兩者之和，小於2^k 個像素值之總位元數。並且，在步驟61中，還估計2^k 個像素值在分別使用各種形態之調整矩陣執行哈達瑪轉換時，所分別對應之轉換誤差，藉以依據該轉換誤差，選取其中一種形態之調整矩陣來執行哈達瑪轉換。至於如何估計轉換誤差，已如影像壓縮裝置之第二實施例中所述，此處不再贅述。

第7圖係本發明之影像壓縮方法之第三實施例的流程圖，其係對應於前述影像壓縮裝置之第三實施例。在步驟71中，選取第一模式或第二模式之哈達瑪轉換。若選取第一模式，則繼續步驟72；若選取第二模式，則跳至步驟75。在步驟72中，依據2^k ×2^k 之哈達瑪矩陣，對2^k 個像素值執行哈達瑪轉換，以產生2^k 個第一轉換值；在步驟73中，對至少一第一轉換值進行量化；在步驟74中，將所有量化與未量化之第一轉換值儲存至一記憶體。另一方面，在步驟75中，依據2^k ×2^k 之哈達瑪矩陣與一2^k ×2^k 之調整矩陣的乘積，對2^k 個像素值執行哈達瑪轉換，以產生2^k 個第二轉換值，其中至少有一第二轉換值為零；在步驟76中，將所有非零之第二轉換值儲存至該記憶體。前述之調整矩陣所須滿足之條件，已如影像壓縮裝置之第二實施例中所述，此處不再贅述。

在步驟71中，係依據在第二模式下，2^k 個像素值之各像素值與其所屬像素組之平均像素值的差值，來決定選取第一模式或第二模式之哈達瑪轉換。或者，還計算在第一模式下，各第一轉換值在經過哈達瑪反轉換後與2^k 個像素值中之對應像素值的差值，以與各像素值與其所屬像素組之平均像素值的差值來做比較，藉以決定選取第一模式或第二模式。至於進一步之實例，已如影像壓縮裝置之第三實施例中所述，此處不再贅述。

以上所述係利用較佳實施例詳細說明本發明，而非限制本發明之範圍。凡熟知此類技藝人士皆能明瞭，可根據以上實施例之揭示而做出諸多可能變化，仍不脫離本發明之精神和範圍。

10、20、40．．．影像壓縮電路

11、21、41．．．哈達瑪轉換單元

12、22、42．．．記憶體

51~53．．．影像壓縮方法之第一實施例的流程

61~63．．．影像壓縮方法之第二實施例的流程

71~76．．．影像壓縮方法之第三實施例的流程

第1圖係本發明之影像壓縮電路之第一實施例的方塊圖。

第2圖係本發明之影像壓縮電路之第二實施例的方塊圖。

第3A圖係顯示2×4之8個像素值如何分成四個像素組之一實例。

第3B圖係顯示2×4之8個像素值如何分成四個像素組之另一實例。

第3C圖係顯示2×4之8個像素值如何分成二個像素組之一實例。

第3D圖係顯示2×4之8個像素值如何分成二個像素組之另一實例。

第4圖係本發明之影像壓縮電路之第三實施例的方塊圖。

第5圖係本發明之影像壓縮方法之第一實施例的流程圖。

第6圖係本發明之影像壓縮方法之第二實施例的流程圖。

第7圖係本發明之影像壓縮方法之第三實施例的流程圖。

20．．．影像壓縮電路

21．．．哈達瑪轉換單元

22．．．記憶體

Claims

一種基於哈達瑪轉換之影像壓縮方法，包含：依據一2^k ×2^k 之哈達瑪矩陣與一2^k ×2^k 之調整矩陣的乘積，對2^k 個像素值執行哈達瑪轉換，以產生2^k 個轉換值，k為正整數，其中，該2^k 個轉換值中至少有一轉換值為零；以及儲存該2^k 個轉換值中之所有非零轉換值至一記憶體；其中，該調整矩陣滿足以下條件：若將該2^k 個像素值分成G個像素組，每一像素組包含2^k /G個相鄰像素值，且將該調整矩陣乘以該2^k 個像素值所組成之一2^k ×1之第一矩陣，以轉換該第一矩陣為一2^k ×1之第二矩陣，則在該第二矩陣中，該第一矩陣之各像素值係轉換為該像素值所屬之像素組之一平均像素值。
如申請專利範圍第1項所述之影像壓縮方法，更包含：若所有非零轉換值之總位元數不小於該2^k 個像素值之總位元數，則對至少一非零轉換值進行量化，以使所有量化與未量化之非零轉換值的總位元數小於該2^k 個像素值之總位元數，其中，該至少一非零轉換值係於量化後才儲存至該記憶體。
如申請專利範圍第1項所述之影像壓縮方法，其中該2^k 個像素值係屬於同一條掃描線。
如申請專利範圍第1項所述之影像壓縮方法，其中該2^k 個像素值係分屬於2^m 條掃描線，m為正整數。
如申請專利範圍第1項所述之影像壓縮方法，其中G等於2^k-1 ，而每一像素組包含兩個垂直相鄰像素值。
如申請專利範圍第1項所述之影像壓縮方法，其中G等於2^k-1 ，而每一像素組包含兩個水平相鄰像素值。
如申請專利範圍第1項所述之影像壓縮方法，其中G等於2^k-2 ，而每一像素組包含排列方式為1×4的四個像素值。
如申請專利範圍第1項所述之影像壓縮方法，其中G等於2^k-2 ，而每一像素組包含排列方式為2×2的四個像素值。
如申請專利範圍第1項所述之影像壓縮方法，其中該調整矩陣係依據該第一矩陣中該2^k 個像素值的排列順序而決定。
如申請專利範圍第1項所述之影像壓縮方法，其中該調整矩陣係依據G的大小而決定。
如申請專利範圍第10項所述之影像壓縮方法，其中該調整矩陣還依據每一像素組中2^k /G個相鄰像素值的排列方式而決定。
如申請專利範圍第1項所述之影像壓縮方法，其中當該調整矩陣具有至少兩種形態時，在該執行哈達瑪轉換之步驟中，還包含產生一形態記錄，用以記錄使用何種形態之調整矩陣來執行哈達瑪轉換。
如申請專利範圍第12項所述之影像壓縮方法，其中所有非零轉換值之總位元數與該形態記錄之位元數兩者之和，小於該2^k 個像素值之總位元數。
如申請專利範圍第12項所述之影像壓縮方法，其中在該執行哈達瑪轉換之步驟中，還估計該2^k 個像素值在分別使用各種形態之該調整矩陣執行哈達瑪轉換時，所分別對應之一轉換誤差，並依據該轉換誤差，選取其中一種形態之該調整矩陣來執行哈達瑪轉換。
如申請專利範圍第14項所述之影像壓縮方法，其中，係依據該2^k 個像素值之各像素值與其所屬像素組之該平均像素值之差值，來估計該轉換誤差。
如申請專利範圍第15項所述之影像壓縮方法，其中，係依據該2^k 個像素值之各像素值與其所屬像素組之該平均像素值之差值的總和，來估計該轉換誤差。
如申請專利範圍第15項所述之影像壓縮方法，其中，係依據該2^k 個像素值之各像素值與其所屬像素組之該平均像素值之差值中的最大者，來估計該轉換誤差。
一種基於哈達瑪轉換之影像壓縮方法，包含：選取一第一模式或一第二模式之哈達瑪轉換；若選取該第一模式，則依據一2^k ×2^k 之哈達瑪矩陣，k為正整數，對2^k 個像素值執行哈達瑪轉換，以產生2^k 個第一轉換值，並對該2^k 個第一轉換值中至少一第一轉換值進行量化；以及若選取該第二模式，則依據該哈達瑪矩陣與一2^k ×2^k 之調整矩陣的乘積，對該2^k 個像素值執行哈達瑪轉換，以產生2^k 個第二轉換值，其中該2^k 個第二轉換值中至少有一第二轉換值為零；其中，該調整矩陣滿足以下條件：若將該2^k 個像素值分成G個像素組，每一像素組包含2^k /G個相鄰像素值，且將該調整矩陣乘以該2^k 個像素值所組成之一2^k ×1之第一矩陣，以轉換該第一矩陣為一2^k ×1之第二矩陣，則在該第二矩陣中，該第一矩陣之各像素值係轉換為該像素值所屬之像素組之一平均像素值；且，該選取步驟係依據在該第二模式下，該2^k 個像素值之各像素值與其所屬像素組之該平均像素值之差值，來決定選取該第一模式或該第二模式之哈達瑪轉換。
如申請專利範圍第18項所述之影像壓縮方法，其中若該第一模式被選取，則將所有量化與未量化之第一轉換值儲存至一記憶體；若該第二模式被選取，則將所有非零之第二轉換值儲存至該記憶體。
如申請專利範圍第19項所述之影像壓縮方法，其中在該第一模式下，每一第一轉換值包含一大小部分；若該2^k 個第一轉換值中，至少有一第三轉換值之該大小部分之前n個最高位元皆為零，n為正整數，則在將該第三轉換值儲存至該記憶體時，省略該前n個最高位元，並產生一對應之省略記錄，儲存至該記憶體。
如申請專利範圍第20項所述之影像壓縮方法，其中若對該第三轉換值進行量化，則量化後之該第三轉換值不包含該前n個最高位元。
如申請專利範圍第19項所述之影像壓縮方法，其中在該第二模式下，若所有非零之第二轉換值之總位元數不小於該2^k 個像素值之總位元數，則對至少一非零之第二轉換值進行量化，以使所有量化與未量化之非零之第二轉換值的總位元數小於該2^k 個像素值之總位元數，其中，該至少一非零之第二轉換值係於量化後才儲存至該記憶體。
如申請專利範圍第18項所述之影像壓縮方法，其中該選取步驟係依據在該第二模式下，該2^k 個像素值之各像素值與其所屬像素組之該平均像素值之差值的總和，來決定選取該第一模式或該第二模式之哈達瑪轉換。
如申請專利範圍第23項所述之影像壓縮方法，其中該選取步驟係將該2^k 個像素值之各像素值與其所屬像素組之該平均像素值之差值的總和與一臨界值做比較，以決定選取該第一模式或該第二模式之哈達瑪轉換。
如申請專利範圍第18項所述之影像壓縮方法，其中該選取步驟係依據在該第二模式下，該2^k 個像素值之各像素值與其所屬像素組之該平均像素值之差值中的最大者，來決定選取該第一模式或該第二模式之哈達瑪轉換。
如申請專利範圍第25項所述之影像壓縮方法，其中該選取步驟係將該2^k 個像素值之各像素值與其所屬像素組之該平均像素值之差值中的最大者與一臨界值做比較，以決定選取該第一模式或該第二模式之哈達瑪轉換。
如申請專利範圍第18項所述之影像壓縮方法，其中該選取步驟還計算在第一模式下，各第一轉換值在經過哈達瑪反轉換後與該2^k 個像素值中之對應像素值之差值的總和，來與在該第二模式下該2^k 個像素值之各像素值與其所屬像素組之該平均像素值之差值的總和作比較，以決定選取該第一模式或該第二模式之哈達瑪轉換。
如申請專利範圍第18項所述之影像壓縮方法，其中該選取步驟還計算在第一模式下，各第一轉換值在經過哈達瑪反轉換後與該2^k 個像素值中之對應像素值之差值中的最大者，來與在該第二模式下該2^k 個像素值之各像素值與其所屬像素組之該平均像素值之差值中的最大者作比較，以決定選取該第一模式或該第二模式之哈達瑪轉換。