TW201120818A - Hadamard transform-based image compression circuit and method - Google Patents

Description

201120818 六、發明說明： 【發明所屬之技術領域】 本發明係有關於影像壓縮，尤指一種基於哈達瑪轉換 之影像壓縮電路及方法。 【先前技術】 在進行影像壓縮時，哈達瑪轉換(Hadamard transform；) 疋種常用的技術。在先前技術中，對影像(通常為靜態晝 面)執行哈達瑪正轉換(forward Hadamard transform，為行 文方便，下文亦以哈達瑪轉換稱之)時，係以同屬一條掃 描線之8個像素為單位影像區塊’並將8階(即8x8)哈達 瑪矩陣(Hadamard matrix)乘上8個像素值所組成之8><1矩 陣’以轉換至頻域，而相乘所得之8χι矩陣之8個矩陣元 素即為轉換值，如下所示： H8*P[8] =

i-i *11 1-11-1

1 ·ι i-i 1 1 1 -1 -1 -1 -1 -1 1 1 1 -1 1 -1 -1 -1 1 1 -1 1 -1 1 -1 1 P0 DC P1 ACO P2 AC1 P3 AC2 P4 &a AC3 P5 AC4 P6 AC5 P7 l . AC6 » . 式⑴ 式⑴中’ Hs為8階哈達瑪矩陣’ 1»[8]為8個像素洲〜打所組 成之8x1矩陣；H8*P[8]則為8X1矩陣，其包含8個轉換值，即 1個直流(DC)值及7個交流(AC)值AC0〜AC6，其中DC值代表8 個像素财7的平均值，AC0〜AC6則依序代表從低頻至高頻的 部份。在執行完哈違瑪轉換後，再對轉換值進行量化 201120818 (quantization)，亦即將轉換值之數個最低位元(LSB)捨棄，以減少 位元數，達到影像壓縮的目的。 哈達瑪轉換的優點之一’在於執行哈達瑪反轉換(inverse Hadamard transform)時，所使用之哈達瑪反矩陣就是原本進行正 轉換時所用之哈達瑪矩陣，以式(1)而言’若以Η/代表h8的反 矩陣，則Hs-1= Hg ;另一優點則是，轉換過程只需執行簡單的加 減法，這點從式(1)可看出。 由於哈達瑪轉換具有如上所述的優點，因此，如能基於哈達 瑪轉換，設計出更具彈性及效率的影像壓縮電路，則可達到更好 的影像壓縮效果。 【發明内容】 有鑑於此，本發明之一目的，在於提供一種基於哈達 瑪轉換之影像壓縮電路及方法，以提供更具彈性及效率的 影像壓縮功能。 本發明揭露-種基於哈達瑪轉換之影像壓縮方法，包 含下列步驟：絲2kx2k之哈達瑪轉，對》個像素值執 ，哈達瑪轉換，以產生/個轉換值，其中k為正整數， 每-轉換值包含-大小部分；對至少—轉換值進行量化； 以及將所有量化與未量化之轉換值儲存至—記憶體，·其 令，若f個轉換值中，至少有一第一轉換值之大小部份 之前η個最高餘料零，n為正整數，則在將第一轉換 值儲存至罐體時，省略該前n赌高位元，並產生一對 應之省略記錄，儲存至記憶體。 本發明另揭露-種基於哈達瑪轉換之影像壓縮方 201120818 法，包含下列步驟：依據2kX2k2哈達瑪矩陣與2kx2k之 調整^矩陣絲積，對#轉素錄行哈賴轉換，以產 生2個轉換值，k為正整數，其中至少有一轉換值為零； 以及儲存所有轉娜值至_記紐；其中，調整矩陣滿 足以下條件：若將2k個像素值分成⑽像素組，每一像 素組包含加谢_像素值，膽職矩陣絲#個像 素值所喊之2 xl之第—矩陣，以轉換第_矩陣為况 之第-矩陣’則在第二矩陣中，第一矩陣之各像素值係轉 換為該像素值所屬之像素組之平均像素值。 、本發明另揭露一種基於哈達瑪轉換之影像壓縮方 法’包含下列步驟：選取第一模式或第二模式之哈達瑪轉 換；若選取第一模式，則依據九》之哈達瑪矩陣，k為 正整數，對β個像素值執行哈達瑪轉換，以產生$個第 轉換值並對至少一第一轉換值進行量化；以及若選取 第二模式，則依據該哈達瑪矩陣與之調整矩陣的乘 積對2個像素值執行哈達瑪轉換，以產& y個第二轉 換值’其中至少有-第二轉換值為零；其中，調整矩陣滿 足以下條件：若將/個像素值分成G個像素組，每—像 素組包含2VG_轉素值，且將調整辦乘以/個像 素值所組成之九1之第-矩陣，哺換第-矩陣為#χ1 之第二矩陣’則在第二矩陣中，第一矩陣之各像素值係轉 換為該像素值所屬之像素組之平均像素值；且，該選取步 驟係依據在第二赋下’ 2k轉素值之各像素值與其所屬 像素組之平均像素值之差值，來紋選取第-模式或第二 模式之哈達瑪轉換。 一 201120818 【實施方式】 在敘述本發明之實施例前，先說明2k階(即2kx2k)之 哈達瑪矩P車的產生方式，其中k為正整數。若H是d階

Ή HI 的哈達瑪矩陣，則藉由1h -h|可產生2d階的哈達瑪矩 陣’而反覆執行此過程，即可依序產生1階、2階、4階… 之哈達瑪矩陣如下：

丑1 = W %=「ί Λ· 因此，藉由以上方式，可產生任何2k階之哈達瑪矩 陣。 以下所述之各實施例皆是基於哈達瑪轉換來進行影 像壓縮，以提供更具彈性及效率的影像壓縮功能。此處的 景夕像可為靜態晝面或影片，而實施例中所提及之像素值可 為像素之亮度值或色度值。第i圖係本發明之影像壓縮電 路之第一實施例的方塊圖，其中，影像壓縮電路1〇包含 哈達瑪轉換單元11及記憶體12。哈達瑪轉換單元u係 依據2k階哈達瑪矩陣，對2k個像素值執行哈達瑪轉換， 以產生2個轉換值。因此，在此第一實施例中，係以# 201120818 個像素為單位影像區塊來執行哈達瑪轉換。此/個像素 1屬於同-條掃描線(即1χ/之影像區塊），或是分屬於 2條掃描線(即2〜产之影像區塊），m為正整數。哈達 瑪轉換單it 11在執行哈達瑪轉換時，係將2kx2k之哈達 瑪矩陣^乘上β個像素騎組成之#χ1轉，而相乘所產 生之2kxl輯之2k個矩陣元素即為轉換值，其包含卫個 DC值及2k4個AC值。AC值之值域涵蓋正負範圍，因 此AC值包含一符號位元(sign bit ,即第1個最高位元 (MSB)) ’其餘位元則屬大小部份㈣触流p抓）；值 之值域為不小於零，所以其所有位元皆屬大小部份，而不 包含符號位元。 接著，為了達到影像壓縮的目的，哈達瑪轉換單元 11須對至少一轉換值進行量化(quantization)，以減少2k 個轉換值之總位元數。哈達瑪轉換單元11可預先設定哪 個(或哪些)轉換值需進行量化以及每個需量化之轉換值 的量化位元數(quantization bit number)。由於人眼對於低 頻的影像訊號較為敏感，因此對於低頻之轉換值可保留較 多量化位元，而高頻之轉換值則保留較少量匕位元。接 著’哈達瑪轉換單元11依據所設定之量化位元數(以b表 示）’保留轉換值的前b個最高位元，其餘位元則捨棄， 以完成量化。另一種作法則是，若轉換值之第b+Ι個最高 位元為1，則進位至第b個最高位元，並保留進位後的前 b個最高位元，捨棄其他位元；若第b+Ι個最高位元值為 〇 ’則不進位而保留原來的前b個最高位元，其餘位元直 接捨棄。在執行完量化後，哈達瑪轉換單元11將所有量 201120818 化與未量化之轉換值儲存至記憶體12。 須注意的是，當2k個轉換值中，至少有一轉換值(在 第一實施例中稱為第一轉換值)之大小部份的前η個最高 位元皆為零，η為正整數時，若第一轉換值不需執行量 化’則哈達瑪轉換單元11在將第一轉換值儲存至記憶體 12時，可省略其大小部分之前η個最高位元不予儲存， 並產生一對應之省略記錄；若第一轉換值需執行量化，則 哈達瑪轉換單元11在對第一轉換值進行量化時，亦可先 省略其大小部分之前η個最高位元，並產生對應之省略記 錄，接著再就剩下之位元進行量化，量化後再儲存至記憶 體12 ^前述省略記錄亦需儲存至記憶體12，惟其格式並 無限制，只要能記錄是哪個轉換值省略了多少個最高位元 即可。省略記錄的用處，在於進行影像解壓縮時，可依據 省略記錄將儲存於記憶體12中之轉換值還原，以便正確 執行哈達瑪反轉換。前述省略前η個為零之最高位元的作 法有兩個好處，一是當η值較大或是有較多第一轉換值 時，需要儲存的位元數(即省略後的轉換值+省略記錄的總 位元數)可減少，以節省記憶體空間；另一是若第一轉換 值需量化，則經過省略後之第一轉換值’在量化後可比未 省略的情形保留更多資訊，提昇影像壓縮的品質。為了確 保達到影像壓縮的目的，在經過前述量化與省略處理後， 所有儲存至記憶體12之轉換值的總位元數與省略記錄之 位元數兩者之和，應小於原本2k個像素值之總位元數。 較佳地，哈達瑪轉換單元Π係於2^個轉換值中所有 2k-l個AC值之大小部分的前n個最高位元皆為零時才 201120818 進行前述之省祕理，亦即，麵雜—AC值至記憶體 12時，不論該AC值有無經過量化，其大小部分的前n 個為零的最高位元皆省略而不儲存。而由於事先已知道是 哪些轉換值(即所有AC值)會執行此省略動作，因此省略 記錄只需記錄η值’使省略記錄本身的位元數可以降低。 舉例而言，若k=3且每個像素值為8個位元(亦即，像素 值之值域為0〜255)，則依前述式(1)可知，所有AC值 aco〜AC6的值域為±(255*4)之區間，所以每個ac值為 11侧立元，其包含1個符號位元及1G位^之大小部份。 藉由以下方式，可判斷η值的大小，即可知每個AC值可 省略多少位元： 产 8<=max(|ACX|)<29 ’ χ=〇〜6,則 n=1; 27<=m蜂Cx|) <2，則n=2…依此類推’其中max〇代表取最大值。 第2圖係本發明之影像壓縮電路之第二實施例的方 塊圖，其中，影像壓縮電路2〇包含哈達瑪轉換單元21 及記憶體22。哈達婦換私21係依據2分之哈達瑪 矩陣與一 2S<2k之調整矩陣的乘積，對/個像素值執行哈 達瑪轉換，以產生2k轉換值，其中至少有—轉換值為 零。若所有非零轉換值之總位元數不小於2k個像素值之 總位元數，則哈達瑪轉換單元21再對至少一非零轉換值 進行量化’以使所有量化與未量化之非零轉換值的總位元 數小於2k個像素值之總位元數，而達到影像壓縮的效果。 接著，哈達瑪轉換單元21將所有量化與未量化之非零轉 換值儲存至記憶體22，以供後續要進行影像解壓縮時使 用。另一種作法則是，哈達瑪轉換單元21預先設定好影 201120818 雜縮率，並鎌崎縣_決定(麵些)非零轉 換值需進行量化以及各倾量化之非零轉換值的量化位 元數&以使所有量化與未量化之非零轉換值的總位元數等 於2個錢值之触元數紅影龍鮮，以實現該影 像壓縮率。例如，若k=3且每個像素值為8位元則^ 個像素值之驗元料64位元，此時若奴影像壓縮率 為75%，贿有量倾未量化之非轉換值賴位元數須 等於 64 氺 75%=48。 、 第一實施例的特徵之一，在於將哈達瑪矩陣乘上調整 矩陣後’可產生-簡化的哈達瑪矩陣，利用此簡化的哈達 瑪矩陣進行哈達瑪賴’可使所產生之2k轉換值中， 至少有-鹏零’以制更高_像壓醉，或者在進行 轉換值的量化時可保留更多的量化位元。此調整矩陣滿足 以下條件：若將2k個像素值分成G個像素組，每一像素 組包含2k/G個相轉素值，且將調整矩陣乘以#個像素 值所組成之2kxl之第一矩陣，以轉換第一矩陣為^之 第一矩陣’則在第—矩陣巾，第_矩陣之各像素值係轉換 為該像素值所屬像素組之平均像素值。以下以數個實例來 說明調整矩陣如何產生： <例1>G等於21^ ’而每一像素組包含兩個垂直相鄰 像素值。以k=3為例，則以2k=8個像素值為單位影像區 塊來執行哈達瑪轉換，且此8個像素分成G=4個像素組。 假設8個像素值(表示為PO〜P7)係來自兩條掃描線，亦即 此8個像素值為2x4之影像區塊，則p〇、p2、p4、％各 與其垂直相鄰像素PI、P3、p5、P7形成—像素組，如第 [S] 11 201120818 3A圖所示。此時，調整矩陣(在例1中以Av表示)應滿足 下式： PO + P1 ~~2~ P0 + P1 ~~2~~ P2 + P3 Αν * ΜΙ = Αν* 「ΡΟΙ PI P2 P3 P4 P5 P6 P7 :M2： 2 P2 + P3 P4 + P5 P4 + P5 ~~2~~ P6 + P7 2 P6 + P7 2 式(2) 從式(2)可看出第一矩陣M1巾之各像素值在第二矩 陣M2中皆轉換為該像素值所屬像素組之平均像素 式(2)可推得： μ ^ 0 〇 ο ο 〇 〇 〇〇〇〇〇〇 「11 11 Αν= 2 0 0 1 1 0 0 0 〇 0〇11〇〇〇〇 〇〇0〇11 〇〇 〇〇0〇11 〇〇 0 0 〇 〇 0 〇 11 〇〇〇0〇〇 1 1 H8*Av: 〇 〇 0 〇 0 〇 〇 〇 〇 〇 Ο 〇 0 〇 Ο 〇 0 0 0 0 0 0 0 0 ο ο 0 0 〇0 0 0 12 201120818 利甩此大幅簡化之8階哈達瑪矩陣來對像素值p〇〜P7 進行哈達瑪轉換，可得： 1 1 1 1 1 1 1 Γ •P0 DC 1 1 11 -1 -1 -1 -1 P1 AC0 1 1 _1 -1 -1 -1 1 1 P2 AC1 1 1 -1 -1 1 1-1-1 P3 AC2 0 〇 0 0 00 00 P4 0 0 0 0 0 00 〇〇 P5 0 〇 0 0 0 00 〇〇 P6 0 0 〇 0 0 0 0 〇〇 * P7 0 •

亦即，所產生之8個轉換值包含1個DC值及3個 AC值(AC0〜AC2) ’其餘4個皆為零。 <例2>G等於2kl，而每一像素組包含兩個水平相鄰 像素值。同樣以k=3為例，則以8個像素值為單位影像區 塊，並分成4個像素組。同樣假設8個像素值p〇~p7來 自兩條掃描線，則P0、PI、P4、P5各與其水平相鄰像素 P2、P3、P6、P7形成一像素組，如第3B圖所示β此時， 調整矩陣(在例2中以Ah表示)應滿足下式： Ρ0 + Ρ2Ί 2 P0 + P2 ~~2^ P1+P3

Ah 本 Ml=Ah 木 ·ρ〇· P1 P2 P3 P4 P5 P6 P7

2 P1 + P3 ~~2~~ P4 + P6 2 P4 + P6

P5 + P7 2 式(3) 從式(3)可看出第-矩陣M1中之各像素值在第二矩 13 201120818 陣M2中皆轉換為該像素值所屬像素組之平均像素值。從 式(3)可推得： ' •1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 00000101 1〇〇001〇1〇 Ah=2l° 0 0 0 0 1 0 1 將8階之哈達瑪矩陣Hs乘上調整矩陣Ah，可得到大 幅簡化之8階哈達瑪矩陣，如下所示： 1111111Π -o o o o 1 1 o o o o 1 - •'o o o o 1 1 o o o o 1 垂- 1 ο ο ο o-1 1 o o o o 1 1 o o o o-1 1 o o o o 1

Hs*Ah= L1 Ί 1 -ι 1 -11 -l 利用此大幅簡化之8階哈達瑪矩陣來對像素值p〇〜p7 進行哈達瑪轉換，可得： fp01lplllp2llp3llp4llp5llp6lip7J 氺 l^ooool·1 11^*00001^1 lvooool·1 11^-0000^1 1 lo oo o·1-1 llooooll 1 looo o 1 •1 1 o o o oil.

DC^coooo^c5lc6 •ΙΑ A A 亦即，所產生之8個轉換值包含1個DC值及3個 AC值(AC0、AC5及AC6)，其餘4個皆為零。 <例3> G等於2k·2，而每一像素組包含排列方式為2x2 的四個像素值，亦即每一像素組為2x2之影像區塊。同樣 201120818 以k=3為例，則以8個像素值為單位影像區塊，並分成2 個像素組。同樣假設8個像素值p〇〜P7來自兩條掃描線， 則P0與相鄰像素P1、P2、P3形成一像素組，p4與相鄰 像素P5、P6、P7形成另一像素組，如第3C圖所示。此 時，調整矩陣(在例3中以Aq表示)應滿足下式： P〇 + Pl + P2 + P3 PO + Pl + P2 + P3 4 P0 + P1 + P2 + P3

Aq*Ml=Aq* ΓΡ0 P1 P2 P3 P4 P5 P6 P7 P0 + P1 + P2 + P3 4 P4 + P5 + p6 + p7 4 P4 + P5 + p6 + p7 4 P4 + P5 + P6 + P7 4 P4 + P5 + P6 + P7 M2： 4 式(4) 從式(4)可看出第-矩陣M1中之各像素值在第二矩

陣M2中皆轉換為該像素值所屬像素組之平均像素值。從 式(4)可推得：

將8階之哈達瑪矩陣H8乘上調整矩陣Aq，可得到更 大幅簡化之8階哈達瑪矩陣，如下所示： 15 201120818 1 1 1 11 1 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0000 00 00 H8氺Aq=L〇 0 0 0 0 0 0 0 利用此更大幅簡化之8階哈達瑪矩陣來對像素值 P0〜P7進行哈達瑪轉換，可得： lloooooo lloooooo ο ο ο ο ο ο ccooooooo D A_____- II g~~^lp21£lp4llp51lp6l^] 氺 11^*000000 亦即，所產生之8個轉換值包含i個Dc值及i d AC值(ACO)，其餘6個皆為零β <例4>G等於2k2，而每一像素組包含排列方式為心 的四個像素值’亦即此四個像素值屬於同—條掃描線。 樣以k=3為例’則以8個像素值為單位影像區塊，並分 2個像素組。_微8個像素值射7來自 線，則P0與P2、P4、P6f a ^水目兩條私 ㈣成另，，如素=與P3、P5 的方式，可由與 <例3洲 哈達瑪矩·下：的調整矩陣々以及大幅簡化後: 16 201120818 10 10 10 10 10 10 10 10 10 10 10 10 10101010 0 10 10 10 1 ο ο ο

Ar=4 10 10 10 1 10 10 10 1 10 10 10 1 11111111 1-11-11-11-1 00000000 00000000 00000000

118氺八1：= ο ο ο 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 而利用此大幅簡化之哈達瑪矩陣對像素值Ρ0〜Ρ7進 行哈達瑪轉換時’所產生之8個轉換值包含1個DC值及 1個AC值(AC0)，其餘6個皆為零。

在第二實施例中，除了可利用簡化的哈達瑪矩陣進行 哈達瑪轉換外’還可使用原本未簡化的哈達瑪矩陣來執行 哈達瑪反轉換，只是此時反轉換的結果並非原本的像素 值’而是原像素值所屬像素組的平均像素值，如下式所示: ii1 * 氺 A氺 Μ):#1 氺 氺(A氺 M)=A* Μ 式(5) 式(5)中，Η與Η1分別為哈達瑪矩陣與哈達瑪反矩陣 (ffl=H) ’ Α為調整矩陣，Μ為單位影像區塊内之所有像 素值所組朗轉，Η*Α*Μ則為_簡化的哈達瑪矩 陣(即Η*Α)所進行之哈達瑪轉換。式(5)中，將乘上阳 *a*m)以執行反轉換，可得結果為a*m，亦即將調整 M ’灿舊M中各料值·為該像素值 …组之平均像素值，而此即是原本調整矩陣所須滿 17 201120818 足之條件，如前文所述。因此，原本2^固像素值在分成g 個像素組，並經過簡化過後之哈達瑪矩陣的正轉換及原本 哈達瑪矩陣的反轉換後’會產生G個影像區塊，每一影 像區塊内之各像素值皆相同。換言之，當G值越大，影 像解析度越大，反之亦然。應注意的是，實際在執行哈達 瑪反轉換時，由於原本正轉換(即H*A*M)所產生之轉 換值至少有一部分已執行過量化，因此反轉換的結果會與 式(5)有所誤差，不過此誤差為量化所造成，與哈達瑪正 轉換或反轉換本身無關。 ^促上迷戍個例子可看出^彳…扮Ί豕滥雕平越 阿，但代價是某些頻率的AC值會消失，造成影像解析度 變小及影像細節的流失。實作上，可依實際需要來選擇適 當的G值，例如，若希望提高影像解析度及保留較多的 影，細節，可選擇較大的G值；若希望提高影像壓縮率 以節省記憶體空間，則可選擇較小的G值。 k在此第二實施例中，作為哈達瑪轉換之單位影像區塊 的2個像素值，可屬於同一條掃描線，或是分屬於^條 掃描線。在像素组數相同(即G值相同)的情況下，若公 =像素值分屬於21掃描線，像素組可具有較多種的像 絲排列方式；但若祕同—條掃描線，娜素組僅具有一 ，素排列方式。舉例來說，在前述例3與例4中，告 Γ像素值分屬兩條掃描線時，像素組可有1x4與2x2

列方式铺8個像素細—條掃描線，則 像素組爾1x4的係素排列方式。 J 進步。，調整矩陣的形態，還依據以下因素而決定: 18 201120818 (1) 第一矩陣中2k個像素值的排列順序。例如，在式 (2)與式(3)之第-矩陣M1中，若像素值p〇〜ργ的排列順 序改變，則所推得之調整矩陣Αν與Μ也會隨之改變， 且仍可用以簡化8階之哈達瑪矩陣。 (2) G值的大小。從前述例子可知，調整矩陣的形態 會隨著G值的大小而改變：當k=3時，若G=4，則可推 得如例1與例2令之調整矩陣Av與^ ;若G=2，則可 推得如例3與例4中之調整矩陣Aq與&。 (3) 每一像素組中2k/G個相鄰像素值的排列方式。例 如’在例1中’每-像素組包含兩健直相鄰像素值，所 推得之調整矩陣為Av ;在例2中，每—像素組包含兩個 水平相鄰像素值，而所推得之調整矩陣則為灿。 综言之，調整矩陣除了滿足前述「在第二矩陣中，第 -矩陣之各像素值係賴域像素值所屬像素組之平均 像素值」_件外，其形態還依據前述⑴〜⑶之因素而決 定。 在一較佳實施例中，哈達瑪轉換單元21可提供至少 兩獅態之罐贿，於執行哈達瑪賴時擇_使用。哈 達瑪轉換單元21可錄所需之f彡像崎度及壓縮率(例 如，由使肖麵設定的），選擇射形態之碰矩陣來使 用。另一種作法是，哈達瑪轉換單元21估計#個像素值 在分別使用各獅敵_矩陣執行哈達瑪觀時，所分 別對應之轉換誤差，並依據此轉換誤差，選取其中一種形 態之調整㈣來猜哈達瑪轉換。此轉換代表著2k 個像素值在執行哈達觀轉換與反轉換之前與之後的差 19 201120818 異度γ由於各像素值在執行哈達瑪正轉換及反轉換後，會 轉變為其所屬像素組之平均像素值(雖然可能有量化誤 差，但為求簡化計算，此處可忽略不計），因此哈達瑪轉 換單元21可依據各像素值與其所屬像素組之平均像素值 的差值，來估計每一種形態之調整矩陣所對應之轉換誤 差。例如，哈達瑪轉換單元21可依據各像素值與其所屬 像素組之平均像素值之差值的總和，來估計轉換誤差；或 者’亦可依據各像素值與其所屬像素組之平均像素值之差 值中的最大者，來估計轉換誤差。 _ 當每一像素組僅包含兩個相鄰像素時，不論是水平相 鄰或垂直相鄰，估計轉換誤差的方式可進一步簡化^鼠設 任一像素組包含兩像素P1與P2，則P1、p2與此像素組 像素值（即2 )的差值分別為Ρ1μ I 2 —Ρ2|，將此兩差值相加即得|Ρ1—ρ2卜亦即此像素 組之兩像素值的差值。因此，前述估計轉換誤差時所依據 之「各像素值與其所屬像素組之平均像素值之差值的總和 鲁 或最大者」即可簡化為「各像素組之兩像素值之差值的總 和或最大者」。 在此較佳實施例中，哈達瑪轉換單元21還產生一對 應之形態記錄(其格式並無限制），儲存至記憶體22，用以 記錄選用何種形態之調整矩陣來執行哈達瑪轉換。此時， 為達影像壓縮目的，所有量化與未量化之非零轉換值的總 位元數與該形態記錄之位元數兩者之和，需小於2k個像 素值之總位元數。由於不同形態之調整矩陣會產生對應之 20 201120818 Γ同頻率的非零轉換值，如前述例1中，調整矩陣Αν產 DC及AC0〜AC2的非零轉換值，例2中調整矩陣 4 ^產生DC、AC〇、AC5及AC6的非零轉換值，因此 續在進行影像解壓科，藉由參照記賴22所儲存之 L、’.己錄g卩可知道體22所儲存的是哪些頻率的非 零轉換值，以便正確地執行哈達瑪反轉換。 此較佳實施例還有-優點：不管選用何種形態之調整 • 矩陣來執行哈達瑪轉換’後續執行哈達瑪反轉換時所使用 之哈達瑪反矩陣皆相同（g卩原本未_化之哈達瑪矩 陣）’因此’後續在進行影像解壓縮時，可共用同一套哈 達瑪反轉換電路(圖未顯示），以節省硬體。 前述第-實施例中，將轉換值之大小部分之前n㈣ 零的最高位元予以省略的作法，亦可應用於第二實施例。 由於作法相同，此處不再贅述β 第4圓係本發明之影像壓縮電路之第三實施例的方 • 塊圖，其中，影像壓縮電路40包含哈達瑪轉換單元41 及記憶體42。哈達瑪轉換單元4〇可依據第一模式或第二 模式執行哈達瑪轉換，而第-模式與第二模式分別為前述 第一實施例與第二實施例的作法。換言之，第三實施例為 第一實施例與第二實施例的結合。具體而言，在第一模式 下，哈達瑪轉換單元41依據2kx2k之哈達瑪矩陣，對2k 個像素值執行哈達瑪轉換，以產生2k個第一轉換值，並 對至少一第一轉換值進行量化；在第二模式下，哈達瑪轉 換單元41依據2S<2k之哈達瑪矩陣與2kX2k之調整矩陣的 乘積，對2k個像素值執行哈達瑪轉換，以產生2k個第二 21 201120818 轉換值’其中至少有一第二轉換值為零。記憶體42輕接 至哈達瑪轉換單元41，用以儲存在第一模式下之所有量 化與未量化之第一轉換值以及在第二模式下之所有非= 之第二轉換值。 進一步言，在第一模式下，每一第一轉換值包含一大 小部分，若妙個第一轉換值中，至少有一第三轉換值之 大小部分之前η個最高位元皆為零，則當哈達瑪轉換單元 41在將第三轉換值儲存至記憶體42時，省略該前η個最 高位元，並產生一對應之省略記錄，儲存至記憶體· 此外’若哈達瑪轉換單元41對此第三轉換值進行量化， 則量化後之第三轉換值不包含該前η個最高位元。另一方 面’在第二模式下，若所有非零之第二轉換值之總位元數 不小於2k個像素值之總位元數，哈達瑪轉換單元41對至 少一非零之第二轉換值進行量化，以使所有量 >(匕與未量化 之非零之第二轉換值的總位元數小於2k個像素值之總位 元數，其中’該至少一非零之第二轉換值係於量化後才儲 存至記憶體42。至於第二模式所使用之調整矩陣所須滿 籲 足的條件，已如第二實施例中所述，此處不再贅述。 第三實施例除了結合第一實施例與第二實施例，還提 供如何選取適當模式以執行哈達瑪轉換的方法。哈達瑪轉 換單元41可依據在第二模式下，2k個像素值之各像素值 與其所屬像素組之平均像素值之差值，來決定選取第一模 式或是第二模式。舉例來說，哈達瑪轉換單元41可將各 像素值與其所屬像素組之平均像素值之差值的總和與一 臨界值做比較，再依據比較結果來決定選取第一模式或第 22 201120818 二模式’例如’當該總和小於該臨界值時，表示以第二模 式執行哈達_換之雛誤差是可接受的目此選取第二 模式，而當該總和不小於該臨界值時，表示第二模式之^ 換誤，過大，因此改選第—模式較為妥當；或者ς達瑪 轉換單元41村將各騎值與其關像雜之平均像素 值之差值㈣最大者與另—臨界值做比較，並絲比較結 果來決定選取第一模式或第二模式。

另一種選取適當模式的方法則是，哈達瑪轉換單元 41除了計算在第二模式下，^像素值之各像素值與其 所屬像素組之平均像素值之差值，還計算在第_模式下， 各第-轉換值在經過哈達瑪反轉換後與原本/個像素值 中之對應像素值之差值，再將前述此兩種差值做比較，以 決定選取第-模式或第Κ舉例來說，哈達瑪轉換單 元41可將第一模式與第二模式下計算所得之差值分別加 總，以比較此兩種差值的總和來選取適當模式；哈達瑪轉 換單疋41亦可直接將第一模式下所得之差值中的最大 者，直接與第二模式下所得之差值中的最大者做比較，以 決定選取哪個模式。 第5圖係本發明之影像壓縮方法之第一實施例的流 程圖’其係對應於前述影像壓縮裝置之第一實施例。在步 驟51中，依據2kx2k之哈達瑪矩陣，對2k個像素值執行 哈達瑪轉換，以產生2k個轉換值’其中每一轉換值包含 一大小部分。在步驟52中，對至少一轉換值進行量化。 在步驟53中，將所有量化與未量化之轉換值儲存至一記 憶體。其中，若該2k個轉換值中，至少有一第一轉換值 23 201120818 之該大小部份之前η個最高位元皆為零，n為正整數，則 在將該第-繼_存㈣記舰時，省略該前n個最高 位元，並產生一對應之省略記錄，儲存至該記憶體。 第6圖係本發明之影像壓縮方法之第二實施例的流 程圖，其係對應於前述影像壓縮裝置之第二實施例。在步 驟61中’依據2kx2k之哈達瑪矩陣與一 2fcx2k之調整矩陣 的乘積，對2k個像素值執行哈達瑪轉換，以產生妙個轉 換值，其中至少有一轉換值為零。在步驟62中，若所有 非零轉換值之總位元數不小於妙個像素值之總位元數， 則對至少一非零轉換值進行量化，以使所有量化與未量化 之非零轉換值的總位元數小於2k個像素值之總位元數。 在步驟63中’儲存所有量化與未量化之非零轉換值至一 記憶體。至於調整矩陣所須滿足的條件，已如影像壓縮裝 置之第二實施例中所述，此處不再贅述。 在一較佳實施例中，調整矩陣具有至少兩種形態，而 步驟61還包含產生一形態記錄，用以記錄使用何種形態 之調整矩陣來執行哈達瑪轉換，其中所有非零轉換值之總 位元數與該形態記錄之位元數兩者之和，小於2k個像素 值之總位元數。並且，在步驟61中’還估計/個像素值 在分別使用各種形態之調整矩陣執行哈達瑪轉換時，所分 別對應之轉換誤差，藉以依據該轉換誤差，選取其中一種 形態之調整矩陣來執行哈達瑪轉換。至於如何估計轉換誤 差，已如影像壓縮裝置之第二實施例中所述，此處不再贅 述0 第7圖係本發明之影像壓縮方法之第三實施例的流 24 201120818 程圖’其鱗應於前述影像壓難置之第三實施例 竭瑪轉換。若選 取第一欺，職續步驟72 ;若選取第二模式，則跳至 步驟75。在步驟72中，傾纪之哈賴輯，對# 個像素值執行哈辆讎，以產生2k㈣—轉換值 步驟73 +，對至少ϋ換值進行量化；在步驟74 中’將所有4化與未量化之第—轉換值儲存至—記憶體。

1了面，*步驟75中，依據2分之哈達瑪矩陣^ 2x2k之調整矩陣的乘積，對/個像素值執行哈 換，以產生^第二轉換值，其中至少有—第二轉= 為零；在步驟76中，將所有非零之第二轉換 記憶體。前述之調整矩陣所須滿足之條件，已如影像壓^ 裝置之第二實施例+所述，此處不再贅述。 在步驟71中，係依據在第二模式下，妙個像素值之 各像素值與其所屬像素組之平均像素值的差值，來決定選 取第一模式或第二模式之哈達瑪轉換。或者，還計算在第 一模式下，各第一轉換值在經過哈達瑪反轉換後與/個 像素值中之對應像素值的差值，以與各像素值與其所屬像 素組之平均像素值的差值來做比較，藉以決定選取第一模 式或第二模式。至於進一步之實例，已如影像壓縮裝置之 第三實施例中所述，此處不再贅述。 以上所述係利用較佳實施例詳細說明本發明，而非限 制本發明之範圍。凡熟知此類技藝人士皆能明瞭，可根據 以上實施例之揭示而做出諸多可能變化，仍不脫離本發明 之精神和範圍。 25 201120818 【圖式簡單說明】 第1圖係本發明之影像壓縮電路之第—實 塊圖。 第2圖係本發明之影像壓縮電路之第二實施例 塊圖。 第3A圖係顯示2x4之8個像素值如何分成四個像素 組之一實例。 、 第沌圖係顯示2X4之8個像素值如何分成四個像素 組之另一實例。 第3C圖係顯示2x4之8個像素值如何分成二個像素 組之一實例。 ’、 第沁圖係顯示％之8個像素值如何分成二個像素 組之另一實例。 第4圖係本發明之影像壓縮電路之第三實施例的方 塊圖。 第5圖係本綱之影像壓縮方法之第—實施例的流 程圖。 第6圖係本發明之影像壓縮方法之第二實施例的流 程圖。 第7圖係本發明之影像壓缩方法之第三實施例的流 程圖。 26 201120818 【主要元件符號說明】 10、 20、40:影像壓縮電路 11、 21、41 :哈達瑪轉換單元 12、 22、42 :記憶體 51〜53 :影像壓縮方法之第一實施例的流程 61〜63 :影像壓縮方法之第二實施例的流程 71〜76 :影像壓縮方法之第三實施例的流程

27

Claims (1)

1. 201120818 七、申請專利範圍： 1· 種基於哈達瑪轉換之影像塵縮方法，包含： 依據一 2kx2k之哈達瑪矩陣，對2k個像素值執行哈達 瑪轉換，以產生妙個轉換值，其中k為正整數’ 每一轉換值包含一大小部分(magnitudepart); 對該些轉換值中至少一轉換值進行量化； 將所有量化與未量化之轉換值儲存至一記憶體；以及 其中，若該2k個轉換值中，至少有一第一轉換值之 該大小部份之前η個最高位元皆為零，n為正整 數，則在將該第一轉換值儲存至該記憶體時，省略 該前η個最高位元，並產生一對應之省略記錄，儲 存至該記憶體。 2.如申清專利範圍第1項所述之影像壓縮方法，其中所 有量化與未量化之轉換值的總位元數與該省略記錄 之位元數兩者之和，小於該妙個像素值之總位元數。 3·如申請專利範圍第1項所述之影像壓縮方法，其中若 對該第一轉換值進行量化，則量化後之該第一轉換值 不包含該前η個最高位元。 4.如申請專利範圍第1項所述之影像壓縮方法，其中該 2k個像素值係屬於同一條掃描線。 5·如申請專利範圍第1項所述之影像壓縮方法，其中該 2個像素值係分屬於2m條掃描線，m為正整數。 6.=申請專利範圍第1項所述之影像壓縮方法，其中該 2k個轉換值包含一直流(DC)值，其餘為交流收)值: 其中該第一轉換值為交流值。 28 2〇1l2〇8l8 一種基於哈達瑪轉換之影像壓縮方法，包含： 依據- 之哈達瑪矩陣與一 2kx2k之調3整矩陣的 乘積，對2fc個像素值執行哈達瑪轉換，以產生妙 個轉換值’ k為正整數，其中，該妙個轉換值中至 少有一轉換值為零；以及 儲存該#個轉換值中之所有非零轉換值至一記憶體； 其中，該調整矩陣滿;i以下條件：若將該2k個;素 • 值分成G個像素組，每一像素組包含2k/G個相鄰 像素值，且將該調整矩陣乘以該2k個像素值所組 成之一 2kxl之第一矩陣，以轉換該第一矩陣為一 2kxl之第二矩陣，則在該第二矩陣中，該第一矩陣 之各像素值係轉換為該像素值所屬之像素組之一 平均像素值。 ~ 8·如申請專利範圍® 7項所述之影像屋縮方法，更包 含： • 若所有非零轉換值之總位元數不小於該2k個像素值 之總位元數，則對至少一非零轉換值進行量化，以 使所有量化與未量化之非零轉換值的總位元數小 於該2k個像素值之總位元數，其令，該至少一非 零轉換值係於量化後才儲存至該記憶體。 9. 如申諳專利範圍第7項所述之影像壓縮方法，其中該 2k個像素值係屬於同一條掃描線。 、μ 10. 如申請專利範圍第7項所述之影像卿方法，其中該 2個像素值係分屬於2ω條掃描線，m為正整數。 11·如申請專利範圍第7項所述之影像壓縮方法，其中〇 29 201120818 12. 13. 2=·，而每-像素組包含兩個垂直 如申凊專利範圍第7項所述之影像壓縮方法，其中g 等於2“ ’而每—像素組包含兩個水平相鄰像素值。 如申請^利範圍第7項所述之影健縮方法，其中g 等於2k·2，而每-像素組包含排列方式為μ的 像素值。 14. 如申請專利範圍第7項所述之影賴縮方法，其中g 等於β，而每一像素組包含排列方式為^的四個 像素值。 15.如申請專利範圍第7項所述之影像壓縮方法，其中該 調整矩陣係依據該第一矩陣中該#個像素值的排列 順序而決定。 16·如申請專利範圍第7項所述之影像壓縮方法，其中該 調整矩陣係依據G的大小而決定。 Π.如申請專利範圍第16項所述之影像壓縮方法，其中 該調整矩_依縣—録、財细_鄰像素值 的排列方式而決定。 18.如申請專利範圍第7項所述之影像壓縮方法，其中當 該調整矩陣具有至少兩種形態時，在該執行哈達瑪轉 換之步驟中，還包含產生—形態記錄，用以記錄使用 何種形態之調整矩陣來執行哈達瑪轉換。 19·如申請專利範圍第18項所述之影像壓縮方法，其中 所有非零轉換值之總位元數與該形態記錄之位元數 兩者之和’小於該公個像素值之總位元數。 20.如申請專利範圍第18項所述之影像壓縮方法，其中 201120818 =執行哈達雜狀步财，祕計該2k個像素 =分別使用各種形態之該調整矩陣執行哈達瑪轉 、,'，所分別對應之—轉換誤差，並依據該轉換誤 、取其巾—鄉態之賴整鱗純行哈達瑪轉 換。

   •如申請專利_第2G項所述之影像壓縮方法，其 中，係依驗個像素值之各像素值與其所屬像素 組之該平均像素值之差值，來估計該轉換誤差。 22. 如申請專利範圍第21項所述之影像壓縮方法，其 中，係依據該2k個像素值之各像素值與其所屬像素 組之該平均像素值之差值的總和，來估計該轉換誤 差。 23. 如申明專利範圍第21項所述之影像壓縮方法，其 中，係依據該》個像素值之各像素值與其所屬像^ 組之該平均像素值之差值中的最大者，絲計該轉換 誤莫。

   24. —種基於哈達瑪轉換之影像壓縮方法包含·· 選取一第一模式或一第二模式之哈達瑪轉換； 若選取該第-模式，則依據- 之哈達瑪矩陣，k 為正整數，對2k個像素值執行哈達瑪轉換，以產 生2k個第一轉換值，並對該妙個第一轉換值中至 少一第一轉換值進行量化；以及 若選取該第二模式，則依據該哈達瑪矩陣與一 之調整鱗的乘積，對該/個像素值執行哈達瑪 轉換，以產生2k個第二轉換值，其中該/個第二 31 201120818 轉換值中至少有-第二轉換值為零； 其中’該調整矩陣滿足以下條件：若將該2k個像素 值分成G個像飯，每—像雜包含2k/G個相鄰 像素值，且將該調整矩陣乘以該2k個像素值所組 成之一 2kxl之第一矩陣，以轉換該第一矩陣為一 2kxl之第二矩陣’則在該第二矩陣中，該第一矩陣 之各像素值係轉換為該像素值所屬之像素組之一 平均像素值；且，該選取步驟係依據在該第二模式 下，該2k個像素值之各像素值與其所屬像素組之 該平均像素值之差值，來決定選取該第一模式或該 第二模式之哈達瑪轉換。 25. 如申請專利範圍第24項所述之影像壓縮方法，其中 若該第一模式被選取’則將所有量化與未量化之第一 轉換值儲存至一記憶體；若該第二模式被選取，則將 所有非零之第二轉換值儲存至該記憶體。 26. 如申請專利範圍第25項所述之影像壓縮方法，其中 在該第一模式下，每一第一轉換值包含一大小部分； 若該2*^個第一轉換值中，至少有一第三轉換值之該 大小部分之前η個最高位元皆為零，n為正整數，則 在將該第三轉換值儲存至該記憶體時，省略該前η個 最鬲位元’並產生一對應之省略記錄，儲存至該記憶 ΜΑ 體。 27. 如申請專利範圍第26項所述之影像壓縮方法，其中 若對該第三轉換值進行量化’則量化後之該第三轉換 值不包含該前η個最高位元。 32 201120818 28·如申請專利範圍第25項所述之影像壓縮方法，其中 在該第二模式下’若所有非零之第二轉換值之總位元 數不小於該2k個像素值之總位元數，則對至少一非 零之第二轉換值進行量化，以使所有量化與未量化之 非零之第二轉換值的總位元數小於該2k個像素值之 總位兀數，其中，該至少一非零之第二轉換值係於量 化後才儲存至該記憶體。 29. 如申請專利範圍第24項所述之影像壓縮方法，其中 該選取步驟係依據在該第二模式下，該2k個像素值 之各像素值與其所屬像素組之該平均像素值之差值 的總和，來決定選取該第一模式或該第二模式之哈達 瑪轉換。 30. 如申請專利範圍第29項所述之影像壓縮方法，其中 該選取步驟係將該2&個像素值之各像素值與其所屬 像素組之該平均像素值之差值的總和與一臨界值做 比較’以決定選取該第一模式或該第二模式之哈達瑪 轉換。 31. 如申請專利範圍第24項所述之影像壓縮方法，其中 該選取步驟係依據在該第二模式下，該2k個像素值 之各像素值與其所屬像素組之該平均像素值之差值 中的最大者，來決定選取該第一模式或該第二模式之 哈達瑪轉換。 32·如申請專利範圍第31項所述之影像壓縮方法，其令 該選取步驟係將該#個像素值之各像素值與其所屬 像素組之該平均像素值之差值中的最大者與一臨界 33 201120818 值做比較，以決定選取該第-模式或該第二模式之哈 達瑪轉換。 33.如申請專利範圍第％項所述之影像麼縮方法，其中 該選取步驟還計算在第-模式下，各第—轉換值德 過哈達瑪反轉換後與該2k個像素值中之對應像素值 之差值的總和，來與在該第二模式下該》個像素值 之各像素值與其所屬像素組之該平均像素值之差值 的總和作比較，以決定選取該第一模式或該第二模式 之哈達瑪轉換。 34·如申請專利範圍第24項所述之影像壓縮方法，其中 該選取步驟還計算在第一模式下，各第一轉換值在經 過哈達瑪反雜倾該2k瓣素值巾之對應像素值 之差值中的最大者’來與在該第二模式下該2k個像 素值之各像素值與其所屬像素組之該平均像素值之 差值中的最大者作比較，以決定選取該第一模式或該 第二模式之哈達瑪轉換。 34