ハールのウェーブレット変換
ハールの基底を使った画像のウェーブレット変換のプログラムを作ってみた。DCTより単純で楽。記録を残しておく。
順変換のアルゴリズム:
(1)
画像を用意する。
(2)
画像の一行分のピクセルに対して、平均と差分を計算し、左側に平均をおき、右側に差分を置いていく。この処理を上の行から、下へ1行ずつ順番に行っていく。
このような処理を行い、左側に平均、右側に差分が集まった画像を新しく作る。
[ a, b, c, d ] →[ ( a+b)/2, (c+d)/2, (a-b)/2, (c-d)/2]
(3)
(2)の結果の画像における、一列分のピクセルに対して、平均と差分を計算し、上側に平均をおき、下側に差分を置いていく。この処理を左の列から、右の列へ1列ずつ順番に行っていく。このような処理を行い、上側に平均、下側に差分が集まった画像を新しく作る。
(4)
結果として、次のような画像が作られる。
・左上には、元の画像の行方向の平均をし、列方向に平均をした画像(元の画像を1/2にした画像)。
・左下には、元の画像の行方向の平均をし、列方向の差分をした画像。
・右上には、元の画像の行方向の差分をし、列方向の平均をした画像。
・右下には、元の画像の行方向の差分をし、列方向の差分をした画像。
これで、一つの階層の処理の終了となる。
さらに、階層を深くすることができる。
さらに階層を深くする場合は、左上の元の画像の行方向の平均をし、列方向に平均をした画像に対して、(2)と(3)の処理を行っていけばよい。
before after
逆変換のアルゴリズム:
順変換と逆の工程を行えば、元の画像に戻すことができる。
列の走査をして、行の走査をすればよい。
[ ( a+b)/2, (c+d)/2, (a-b,)/2 (c-d)/2] == [A, B, C, D] とすると、
a = A+C;
b = A-C;
c = B+D;
d = B-D;
を行うことで、もとのデータ[ a, b, c, d ] に戻せる。
圧縮について:
順変換の結果画像に対して、適切な量子化を行い、各種符号化すればよい。適切な量子化については、まだ調査中。
例:順変換の結果画像の高周波成分(左下、右上、右下の画像の部分)を0にするとか。
思ったこと:
・ハール以外の基底があるので、他の基底も試して見る必要がある。
・ハールは、整数で演算できるから良いと思う。
・SURFやいろんな所でも使われてるみたいだから、勉強の価値あり。
・適切な量子化の方法を勉強しなければいけない。
参考:
『画像圧縮アルゴリズム (8) ウェーブレット変換 -1-』
http://www2.starcat.ne.jp/~fussy/algo/algo8-8.htm
『画像圧縮アルゴリズム (9) ウェーブレット変換 -2-』
http://www2.starcat.ne.jp/~fussy/algo/algo8-9.htm
『直交ウェーブレット変換について』
http://laputa.cs.shinshu-u.ac.jp/~yizawa/InfSys1/advanced/daubechies/
『ウェーブレット変換の基礎と応用』
http://wwwmp.jwu.ac.jp/mine/SemPPT/2005sem/2005FoundationOfWaveletTransformRevised.pdf
わかりやすいスライドでした。
『USC-SIPI Image Database』
レナとかの画像処理で使われる画像がおいてあるサイト。