TWI432031B - Distortion-free image compression method - Google Patents

Description

無失真的影像壓縮方法

本發明係關於一種無失真的影像壓縮方法，尤其是一種需要較少記憶體空間的無失真的影像壓縮方法。

隨著電子以及資訊技術的進步，在電腦或各式各樣之電子裝置上處理以及顯示影像的技術發展也越來越普遍。早期之電子資訊技術只能儲存或處理較低畫素之數位影像。然而，人們對高品質影像的需求越來越多，如何處理以及儲存高品質影像也成為非常熱門的重點。為了得到高品質影像，在進行影像壓縮時常採用無失真的壓縮方式。

然而無失真之高品質影像需要儲存較高的畫素，對於計算機之運算速度以及儲存媒體之容量也形成一大挑戰。例如在無失真壓縮演算法中，無失真靜態影像壓縮標準(Joint photographic experts group Lossless，JPEG-LS)是利用預測和前文模式(context modeling)來達到較好的壓縮比。前文模式係需要至少暫存影像的一整排的像素才能夠進行各種模式下的預測，因此需要大量的運算和儲存空間，而使得編碼器(encoder)所需的成本上升。且JPEG-LS對於不需要高壓縮率的應用來說，演算複雜度還是較高，而增加編碼器的負擔。

再加上使用者對於影像的解析度的要求越來越高，亦增加了影像壓縮時的負擔。若使用習知的無失真的壓縮方式，一旦影像的解析度提高，編碼器更得要耗費漫長的時間以及更大量的儲存空間才能處理為高品質影像。換句話說，習知的無失真的壓縮方式具有運算複雜度太高而導致運算效率低落，以及所需暫存空間龐大的問題。

因此，如何設計一種無失真的壓縮方法，能夠兼顧高視覺品質、低運算複雜度以及低暫存空間之需求是工業界相當重要的。

為解決上述問題，本發明提供一種無失真(lossless，亦稱為無損)的影像壓縮方法。無失真的影像壓縮方法僅需使用較少的記憶體空間，且能以較快的速度處理具有多個像素的一影像。其中影像的一影像寬度為W。無失真的影像壓縮方法包括下述步驟：(a)由影像中選取連續的N個像素，其中N為大於或等於2的正整數，且N小於影像寬度W；(b)執行一差異脈波碼調變(Differential pulse code modulation，DPCM)手段，以依據此N個像素的值，得到對應此N個像素的N個非負數差值；(c)依據此N個非負數差值，計算得到一編碼參數(coding parameter)；以及(d)依據編碼參數，將此N個非負數差值進行編碼。

為了壓縮整張影像，無失真的影像壓縮方法另可包括下述步驟：(e)接續選取影像的下N個連續的像素；以及(f)返回步驟(b)，直到壓縮完影像的所有像素。

其中步驟(a)可由一暫存器直接接收影像中被選取的N個像素。

而步驟(b)之差異脈波碼調變手段可包括：依據此N個像素的值，得到個別對應於此N個像素的N個像素差值；以及個別對此N個像素差值執行一變換(mapping)手段，以得到個別對應於此N個像素差值的N個非負數差值。

根據本發明之一實施範例，「依據此N個像素的值，得到個別對應於此N個像素的N個像素差值」的步驟可包括：將此N個像素中的第一個像素的值P₀ 作為第一個像素差值d₀ ；以及分別計算此N個像素中的第i個像素的值P_i 與其前一個像素的值P_i-1 的差，作為其他N-1個像素差值，其中i為正整數，且0<i<N。

變換手段則可包括：當此N個像素差值中的第i個像素差值d_i 大於或等於零時，對應的第i個非負數差值n_i 為像素差值d_i 乘以2，其中0<=i=N；以及當此N個像素差值中的第i個像素差值d_i 小於零時，對應的第i個非負數差值n_i 為像素差值d_i 乘以2再減1。

用以編碼此N個非負數差值的編碼參數可以是，其中n_i 為此N個非負數差值中的第i個非負數差值。

而上述步驟(d)可包括：依據編碼參數，以哥倫布-萊斯編碼(Golomb-Rice code)將此N個非負數差值進行編碼。

綜上所述，根據本發明之無失真的影像壓縮方法選取影像中的N個像素，並以可變長度編碼將此N個像素的值編碼。處理此N個像素時並不需要用到影像中的其他像素，因此編碼器之暫存器不需保存其他像素的值。故無失真的影像壓縮方法具有節省大量的暫存空間，且壓縮方式簡單有效率等優點。

以下在實施方式中詳細敘述本發明之詳細特徵以及優點，其內容足以使任何熟習相關技藝者了解本發明之技術內容並據以實施，且根據本說明書所揭露之內容、申請專利範圍及圖式，任何熟習相關技藝者可輕易地理解本發明相關之目的及優點。

本發明提供一種無失真(lossless，亦稱為無損)的影像壓縮方法，用以處理具有多個像素的一影像，以將影像壓縮。無失真的影像壓縮方法係可實作於一編碼器(encoder)。

請參照「第1圖」與「第2圖」，其分別為根據本發明一實施範例之影像之示意圖與無失真的影像壓縮方法之流程圖。

影像20具有WxL個像素，其中W為影像20的一影像寬度，L為一影像長度。例如影像20可以具有640x480個像素，或是128x128個像素的；則影像寬度W則會是640(像素)或是128(像素)。由於處於影像20中同一排的像素彼此之間具有強大的關聯性，因而可被利用於影像壓縮。

執行無失真的影像壓縮方法時，首先由影像20中選取連續的N個像素(步驟S30)；其中N為大於或等於2的正整數，且N小於影像寬度W。為了更有效率地執行無失真的影像壓縮方法，可以取能整除影像寬度W的數值作為N。換句話說，N能夠整除影像20的影像寬度W。例如當影像寬度W為128(像素)時，可取N為16。而選取連續N個像素的步驟S30可以以一處理窗22實作之。處理窗22的長度為N，被處理窗22所框選的N個像素便是依下述流程被壓縮的N個像素。

編碼器具有一暫存器(buffer)，以將影像20中需要被處理的部分暫存於暫存器。更詳細地說，影像20可以是被存放於記憶體中的檔案，亦可以是由一影像擷取裝置的一感光單元傳送之影像資料。而步驟S30則可在由記憶體或是感光單元收到的影像20中選取連續的此N個像素，並由暫存器直接接收此N個像素的值P₀ ～P_N-1 。

因此無失真的影像壓縮方法壓縮影像20時，僅需要用到處理窗22的N個像素，而不需用到影像20中的其他像素。因此編碼器的暫存器中亦僅需要存有此N個像素即可，而不需存放影像20中整排的W個像素。

選取連續的N個像素之後，對此N個像素執行一差異脈波碼調變(Differential pulse code modulation，DPCM)手段；以依據此N個像素的值P₀ ～P_N-1 ，得到對應此N個像素的N個非負數差值n₀ ～n_N-1 (步驟S40)。像素的值例如可以是灰階值、三原色值(RGB value)或是HSL色彩空間的色相(hue)、飽和度(saturation)、與亮度(lightness)。無失真的影像壓縮方法並不對像素的值之內容有所限制。

請參照「第3圖」，其係為根據本發明一實施範例之差異脈波碼調變手段之流程圖。

無失真的影像壓縮方法利用差異脈波碼調變手段得到對應於處理窗22的N個非負數差值n₀ ～n_N-1 ，以進行無失真的壓縮。差異脈波碼調變手段可以先依據此N個像素的值P₀ ～P_N-1 ，得到個別對應於此N個像素的N個像素差值d₀ ～d_N-1 (步驟S41)。接著再個別對此N個像素差值執行一變換(mapping)手段，以得到個別對應於此N個像素差值的N個非負數差值n₀ ～n_N-1 (步驟S46)。

請配合「第3圖」並參照「第4圖」以及「第5圖」，其分別為根據本發明一實施範例之步驟S41之流程圖，以及步驟S46中的變換手段之流程圖。

於步驟S41中，係可依據下述「式1」以及「式2」計算得到像素差值d₀ ～d_N-1 。

d₀ =P₀ .........................................................................式1

d_i =P_i -P_i-1 ，0<i<N，且i為正整數...................式2

其中P₀ 為處理窗22中的N個像素中的第一個像素的值，P_i 為處理窗22中的N個像素中的第i個像素的值。而d₀ 為對應P₀ 的像素差值，d_i 為對應P_i 的像素差值。

「式1」係將N個像素中的第一個像素的值P₀ 作為第一個像素差值d₀ (步驟S42)。「式2」分別計算此N個像素中的第i個像素的值P_i 與其前一個像素的值P_i-1 的差，作為其他N-1個像素差值d₁ ～d_N-1 ，其中0<i<N(步驟S43)。換句話說，像素差值d₁ ～d_N-1 係將相鄰的像素的值P₀ ～P_N-1 兩兩相減得到。

根據本發明之另一實施範例，可保存有影像20中處理窗22之第一個像素的前一個像素的值P_-1 。而對應處理窗22之第一個像素差值d₀ 的值即為P₀ 與P_-1 的差值。

在步驟S41得到處理窗22對應之像素差值d₀ ～d_N-1 之後，變換手段可先逐一判斷這些像素差值d_i 是否大於或等於0(步驟S47)，再依下述「式3」以及「式4」計算得到非負數差值n₀ ～n_N-1 。

n_i =2×d_i ，if d_i ≧0....................................................式3

n_i =2×d_i －1，if d_i <0.................................................式4

其中n_i 為N個非負數差值n₀ ～n_N-1 中的第i個像素的值，且0≦i<N。

對於大於或等於0的像素差值d_i ，「式3」係將像素差值d_i 乘以2作為非負數差值n_i 。也就是說非負數差值n_i 為像素差值d_i 乘以2(步驟S48)。而對於小於0的像素差值d_i ，「式4」係將像素差值d_i 乘以2再減1的值作為非負數差值n_i 。也就是說非負數差值n_i 為像素差值d_i 乘以2再減1(步驟S49)。

如此一來，便可在步驟S40中依據N個像素的值P₀ ～P_N-1 ，得到對應這N個像素的N個非負數差值n₀ ～n_N-1 。

請回到「第2圖」。接著依據此N個非負數差值n₀ ～n_N-1 ，計算得到一編碼參數(coding parameter)k(步驟S50)；並依據編碼參數k，將此N個非負數差值n₀ ～n_N-1 進行編碼(步驟S60)。

其中步驟S60可包括：依據編碼參數k，以哥倫布-萊斯編碼(Golomb-Rice code)將此N個非負數差值n₀ ～n_N-1 進行編碼。

用以處理此N個非負數差值的編碼參數可以是。

哥倫布-萊斯編碼係為一種可變長度編碼(variable-length code，VLC)，其將出現機率較高的值予以較短的編碼。依據哥倫布-萊斯編碼，係先依據編碼參數k設定一除數m。再將此N個非負數差值n₀ ～n_N-1 除以除數m，得到對應的N個商數Q以及餘數R。其中除數m為2的k次方(2^k )。

哥倫布-萊斯編碼接著將得到的商數Q編碼成一元碼(unary code)，並將於數R編碼成k位元長度的二進位碼(binary code)。

舉例而言，假設非負數差值n₀ 為163，編碼參數k為5。因此可以算出非負數差值n₀ 的商數Q為5，餘數R為3。則非負數差值n₀ 的商數Q可以以一元碼被編碼成「111110」，餘數R則以二進位碼被編碼成「00011」。

如此一來，處理窗22內的N個像素的值P₀ ～P_N-1 即可被壓縮成無失真的可變長度編碼。而整個影像20能夠被無失真的影像壓縮方法壓縮。請參照「第6圖」，其係為根據本發明另一實施範例之無失真的影像壓縮方法之流程圖。

執行步驟S30到步驟S60將處理窗22的N個像素壓縮後，另可判斷是否壓縮完影像20的所有像素(步驟S70)。若影像20尚未完全被壓縮完成，則接續選取影像20的下N個連續的像素(步驟S80)，並以步驟S40、S50以及S60處理於步驟S80中被選取的N個像素。若影像20已被壓縮完成為一壓縮影像檔案，則可結束。

也就是說，無失真的影像壓縮方法在於步驟S30中被選取的N個像素之後接續選取另外N個像素，且可將另外選取的N個像素作為新的處理窗22在處理之。

綜上所述，根據本發明之無失真的影像壓縮方法選取影像中N個像素，並將選取的像素的值以可變長度編碼進行編碼。由於在壓縮時並不需要用到影像中的其他像素，因此編碼器之暫存器僅需保存此N個像素的值，而能夠節省大量的暫存空間。且無失真的影像壓縮方法僅逐一處理各影像窗內的N個像素值到壓縮完整個影像，而具有壓縮方式簡單有效率的優點。

20．．．影像

22．．．處理窗

第1圖係為根據本發明一實施範例之影像之示意圖；

第2圖係為根據本發明一實施範例之無失真的影像壓縮方法之流程圖；

第3圖係為根據本發明一實施範例之差異脈波碼調變手段之流程圖；

第4圖係為根據本發明一實施範例之步驟S41之流程圖；

第5圖係為根據本發明一實施範例之變換手段之流程圖；以及

第6圖係為根據本發明另一實施範例之無失真的影像壓縮方法之流程圖。

Claims (8)

1. 一種無失真的影像壓縮方法，用以處理具有多個像素的一影像，其中該影像的一影像寬度為W，該無失真的影像壓縮方法包括：(a)由該影像中選取連續的N個該些像素，其中N為大於或等於2的正整數，且N小於該影像寬度W；(b)執行一差異脈波碼調變手段，以依據該N個像素的值，得到對應該N個像素的N個非負數差值；(c)依據該N個非負數差值，計算得到一編碼參數；以及(d)依據該編碼參數，將該N個非負數差值進行編碼。
2. 如申請專利範圍第1項所述之無失真的影像壓縮方法，另包括：(e)接續選取該影像的下N個連續的該些像素；以及(f)返回步驟(b)，直到壓縮完該影像的所有該些像素。
3. 如申請專利範圍第1項所述之無失真的影像壓縮方法，其中該差異脈波碼調變手段包括：依據該N個像素的值，得到個別對應於該N個像素的N個像素差值；以及個別對該N個像素差值執行一變換手段，以得到個別對應於該N個像素差值的該N個非負數差值。
4. 如申請專利範圍第3項所述之無失真的影像壓縮方法，其中該依據該N個像素的值，得到個別對應於該N個像素的N個像素差值的步驟包括：將該N個像素中的第一個該像素的值P₀ 作為第一個該像素差值d₀ ；以及分別計算該N個像素中的第i個該像素的值P_i 與其前一個該像素的值P_i-1 的差，作為其他N-1個該些像素差值，其中i為正整數，且0<i<N。
5. 如申請專利範圍第3項所述之無失真的影像壓縮方法，其中該變換手段包括：當該N個像素差值中的第i個該像素差值d_i 大於或等於零時，對應的第i個該非負數差值n_i 為該像素差值d_i 乘以2，其中0<=i<N；以及當該N個像素差值中的第i個該像素差值d_i 小於零時，對應的第i個該非負數差值n_i 為該像素差值d_i 乘以2再減1。
6. 如申請專利範圍第1項所述之無失真的影像壓縮方法，其中該編碼參數為，其中n_i 為該N個非負數差值中的第i個該非負數差值。
7. 如申請專利範圍第1項所述之無失真的影像壓縮方法，其中該步驟(d)包括：依據該編碼參數，以哥倫布-萊斯編碼將該N個非負數差值進行編碼。
8. 如申請專利範圍第1項所述之無失真的影像壓縮方法，其中該步驟(a)係由一暫存器直接接收該影像中被選取的該N個像素。