Modified Haar Wavelet 변환에 대한 간단한 고찰

1. Wavelet 변환 기저함수

Wavelet 변환이란 wavelet 기저함수를 이용해 데이터를 변환하는 것을 말한다.
여기서 wavelet 기저함수라는 건 적분하면 0이 되고, 진동하면서 진폭이 0으로 수렴하는 함수라는 뜻이다.

뭔가 굉장히 어렵게 들리는데, 쉽게 그림으로 보면, 대략 아래와 같이 생긴 놈들은 다 쓸 수 있다.

Created by Kileen Cheng in Example Wavelets (http://cnx.org/content/m11150/2.3/)

이러한 wavelet 기저함수는 다양하게 구성할 수 있고, 학계에서 다양하게 연구되고 있다.

하지만, 실제 산업계에서 적용된 것은 가장 단순한 Haar Wavelet 한 종류밖에 없다.
바로, 그 유명한 JPEG2000 포맷에 사용된 기저함수인데, 그래프로 보면 아래와 같다.

Created by Kileen Cheng in Example Wavelets (http://cnx.org/content/m11150/2.3/)

뭐가 이리 단순한가 싶지만, 앞에 적은 기준^[각주:1]을 모두 만족하는 대표적인 wavelet 기저함수이다.

2. Wavelet 변환

Modified Haar wavelet 변환은 간단히 예제와 함께 설명하면 아래와 같다.
아래와 같은 원본 데이터가 있다.

[1, 3, 5, 7, 7, 1, 5, 3] - (a)

여기서, 인접한 두 값의 평균과 그 차이값을 적어보자,

[(1+3)/2, (5+7)/2, (7+1)/2, (5+3)/2, (1-3)/2, (5-7)/2, (7-1)/2, (5-3)/2]

정리하면,

[2, 6, 4, 4, -1, -1, 3, 1] - (b)

가 된다. 여기서 왼쪽 4개의 항을 L(저주파 성분), 오른쪽 4개의 항을 H(고주파 성분)이라고 한다.
여기서 한발짝 더 나가서^[각주:2] 왼쪽 4개의 항에 대해 같은 연산을 한번 더 하면 이렇게 된다.

[4, 4, -2, 0, -1, -1, 3, 1] - (c)

그리고, 마지막으로 왼쪽 2개의 항을 또 한번 처리(?)한다.

[4, 0, -2, 0, -1, -1, 3, 1] - (d)

이런 형태가 된다.
이렇게 저장된 데이터는 원본 데이터와 개수는 같지만, 0에 가까운 값들로 정리가 된다.

이 과정을 간단하게 행렬로 구성하면 아래와 같다.

Modified Haar Wavelet matrix

이 행렬은 또 하나의 굉장한 특성을 갖고 있는데, 한번에 계산할 때마다 계수는 단 하나만 사용하면 된다는 것이다.
즉,최종 결과물인 (d)의 첫번째 항을 계산하기 위해서는 (a)의 모든 항을 더한 뒤 8로 한번만 나눠주면 된다는 뜻이다.

※ 원래 Haar Wavelet은 계수가 1/8 아니라, 1/√8 임.
    이것을 순수하게 정수 연산만 수행하도록 1/8 등으로 수정한 것이 Modified Haar Wavelet임^[각주:3].

3. Wavelet 역변환

앞의 2번에서 적은 내용을 그대로 역셈을 하면 된다.
하지만, 더 간단하게는 Modified Haar Wavelet Matrix의 역행렬을 구하면 된다.

역행렬은 무려 아래와 같다.

0과 1 그리고, -1로만 구성된 역행렬. ㄷㄷㄷ

즉, 이 행렬은 그냥 해당되는 항에 대해 덧셈, 뺄셈만으로 계산할 수 있는 것이다.
다시 말해, 구형 8비트 CPU에서도 쌩쌩 돌아가는 변환을 구현할 수 있다.

4. 실제 적용

설명은 간단하게 1차원 데이터를 기준으로 했지만, 실제 Wavelet 변환은 2차원 데이터에서 더 많이 사용된다.
이렇게 2차원 데이터(A)를 Wavelet 변환할 때는 아래와 같이 변환하면 된다.

그리고, 이렇게 변환된 S를 다시 원래의 데이터(A)로 복원할 때는 아래와 같이 변환하면 된다.

1. 적분하면 0이 되고, 진동하며, 진폭이 0으로 수렴함 [본문으로]
2. [나는 꼼수다]의 한발짝 더를 상상하신 건가? [본문으로]
3. Lossy compression with modified Haar wavelet for early processors By Daniel Bienvenu: http://goo.gl/Avu1m [본문으로]