2014年3月20日 星期四

Block Truncation Coding (BTC) by Matlab

BTC 是一個簡單又有效率的影像壓縮方式,簡單地說就是先將影像切塊,每個區塊的作法完全相同。區塊先經過閥值後二元化,得到一個黑白影像區塊,達到壓縮的效果。還原的時候,將黑點以相同的值(假設是a)取代,白點以相同的值(假設是b)取代,達到還原的目的。需要注意的是每一區塊的閥值不同,還原值(a與b)也不同。

如何求取每一區塊的閥值與還原值就是不同BTC演算法的差異。今天要講的是原始BTC的作法:
假設區塊共有m個影像點,在黑白影像中有q個白點,因此有(m-q)個黑點。原始BTC的目的希望原始影像與解壓縮影像能夠達到一級動差(first moment)與二級動差(second moment)都相同。

假設有n個數x1x2, ..., xn,一級動差及二級動差的定義如下

一級動差=(x1+x2+...+xn)/n
二級動差=(x12+x22+...+xn2)/n

假設原始影像的一級動差為m1, 二級動差為m2, 依BTC的要求,還原影像的一級動差與二級動差也必須與原始影像相同,也就是下列兩式需同時滿足:


由式(1)可得......(3),

將式(3)代入式(2)可得

求上式a之解

令σ為原始影像的標準差,也就是
σ2=m2-m12 =>m2=σ2+m12

代入a之解可得

代入式(3)


a之另一解代入式(3),
可得b之另一解為
由於b為白點的還原值,a為黑點還原值,所以b>a,取第一組解,即

在BTC演算法中,每一區塊的閥值都是該區塊的平均值,也就是m1

------------- 分割線---------以上是理論----以下是實踐---------
程式設計會遇到兩個問題:
(1)影像的長寬不是區塊的整數倍數時?
(2)q=0或(m-q)=0?也就是計算a、b值的分母為0。

問題(1):我們將影像向右及向下擴張,讓擴張後的影像長寬為區塊的倍數。擴張區域的影像值與鄰邊相同。
問題(2):由於q=(原始影像值≥m1的像素個數),所以q≠0;但(m-q)可能為0。此時,只有白點,沒有黑點,b=m1(不用管a)。

程式如下:

程式說明:
2: 如果沒有輸入區塊大小,則預設為4
4: 擴張影像,不需要浪費力氣計算長寬與區塊整數倍的差值,反正最多向右及向下擴增BSIZE-1個像素點;擴充值就是邊緣點的灰度值。
17: 在MATLAB中,函數std的輸入值一要定double或int
25: 最後只要取與輸入影像相同大小的範圍。

實際執行看看!

↓顯示結果
區塊越大,影像就越模糊....
--- END ---


2 則留言:

  1. 十分受用, 謝謝分享, 最近工作有用到 BTC.
    btw, (16-q) 應該是 (m-q)

    回覆刪除