코딩 더 매트릭스 - 11장 특수 기저 (1)

필립 클라인의 저서 코딩 더 매트릭스 11장 특수 기저

1. 직교행렬과 벡터의 곱이 원래 벡터의 norm을 보존하는 원리를 이해합니다.
2. 이미지 압축에 활용되는 웨이브릿 기저를 이해합니다.

이미지 압축

이미지를 저장하는 보통의 방법은 각 픽셀을 명시하는 것입니다. 이러한 포맷은 이미지 벡터의 표준 기저에 대한 표현이라고 할 수 있습니다. 하지만 다른 기저로 스파스한 표현이 (값이 0인 데이터는 저장하지 않는) 가능하다면 압축을 이룰 수 있습니다. 만약 표준 기저에 대한 표현이 스파스하지 않으면 표현된 엔트리 중 영에 가까운 것을 억제(suppress)하여 스파스하게 만들 수 있습니다.

원래의 이미지 벡터 $b$를 표준 기저 $A$에 의해 다음과 같이 표현할 수 있습니다.

여기서 $x$는 $b$의 표준 기저 $A$에 대한 좌표 표현입니다. 기저 $u_1, ..., u_n$에 대한 표현으로 바꾸고자 한다면 $u_1, ..., u_n$가 열벡터인 행렬 $Q$에 대해 다음과 같이 표현할 수 있습니다.

이 때 $Q$의 열벡터들이 모두 정규직교한다면, 즉 직교 행렬이라면 $y$를 다음과 같이 구할 수 있습니다.

한편 정규직교 벡터는 norm을 보존하는 좋은 성질을 가지고 있습니다. 임의의 벡터 $u$, $v$, 열-직교 행렬 $Q$에 대해 다음이 성립합니다.

$\langle Qu, Qv \rangle$은 다음과 같이 표현됩니다.

$Q^TQ$는 단위행렬이므로 $\langle Qu, Qv \rangle = \langle u, v \rangle$입니다. 만약 $u = v$라면 $\langle u, u \rangle$는 norm $\parallel u \parallel$의 제곱을 뜻하고 $\langle Qu, Qu \rangle = \langle u, u \rangle$이므로 $\parallel Qu \parallel = \parallel u \parallel$입니다. 따라서 직교행렬 $Q$에 대해 norm은 보존됩니다.

아래 챕터에서는 정규직교 벡터, 웨이브릿 기저에 의한 이미지 벡터의 압축 적용과정을 살펴보겠습니다.

웨이브릿 Wavelets

512 X 512 이미지를 256 X 256 로 다운샘플링 할 수 있습니다. 2 X 2 픽셀들을 그들의 평균인 하나의 픽셀로 대체하는 방식입니다. 웨이브릿은 이 개념에서 비롯되었습니다.

다음과 같이 밝기를 가진 16픽셀 이미지 벡터가 있습니다.

아래는 위 이미지의 표준 기저라고 할 수 있습니다.

표준 기저를 이용해 선형결합으로 $\alpha_0 b_0^{16} + \alpha_1 b_1^{16} + ... + \alpha_{15} b_{15}^{16}$ 와 같이 16픽셀 이미지를 표현할 수 있습니다. 이 기저들을 $V_{16}$에 대한 기저라고 하겠습니다.

16픽셀 이미지의 두 픽셀의 평균을 이용해 다운샘플링한 8픽셀 이미지는 다음과 같습니다.

0번째와 1번째, 2번째와 3번째 픽셀이 같은 값이므로 8픽셀 이미지의 기저는 다음과 같이 표현할 수 있습니다.

위 기저는 $V_8$에 대한 기저입니다. 마찬가지로 $V_4, V_2, V_1$에 대한 기저를 만들 수 있습니다.

$V_{2k}$를 $V_{k}$로 다운샘플링했을 때 $V_{k}$의 $V_{2k}$에 대한 직교여공간을 웨이브릿 공간 $W_k$라 하겠습니다. 즉, 다음과 같이 쓸 수 있습니다.

$k = 8, 4, 2, 1$을 대입하면 다음을 얻습니다.

대입을 모두 적용하면 다음을 얻습니다.

$V_{16}$의 하나의 기저는 $V_1$, $W_1$ $W_2$, $W_4$, $W_8$의 기저의 합집합입니다. 이러한 형태를 가지는 기저를 Haar 기저라고 합니다.

$V_8$의 직교여공간 $W_8$의 기저부터 구해보겠습니다. $W_8$의 기저는 $V_{16}$에 속하면서 $b_0^8, b_1^8, ..., b_7^8$에 모두 직교하는 벡터입니다. 첫번째 기저는 $b_0^{16}$의 $b_0^8, b_1^8, ..., b_7^8$에 대한 직교 투영을 구함으로서 찾을 수 있습니다. $b_0^{16}$과 $b_0^8, b_1^8, ..., b_7^8$은 다음과 같습니다.

$b_0^{16}$의 $b_0^8, b_1^8, ..., b_7^8$에 대한 직교 투영은 $b_0^{16}$에서 $b_0^{16}$의 $b_0^8, b_1^8, ..., b_7^8$에 대한 투영을 뺀 $b_0^{16} - b_0^{16^{\parallel V_8}} = b_0^{16} - \sigma_0 b_0^8 - \sigma_1 b_1^8 - ... - \sigma_7 b_7^8$ 입니다. 이 때 $b_0^{16}$은 $V_8$의 기저 중 $b_0^8$을 제외한 다른 모든 기저에 직교하므로 $b_0^{16^{\parallel V_8}} = \sigma_0 b_0^8 - 0 - 0 - ... - 0 = \sigma_0 b_0^8$입니다. 따라서 $b_0^{16^\perp V_8} = b_0^{16} - \frac{1}{1 + 1} b_0^8$이고 다음과 같습니다.

$b_1^{16}$의 $V_8$에 대한 직교 투영은 단순히 $w_0^8$의 음수값을 제공합니다. $b_2^{16}$의 직교 투영, $w_1^8$은 다음과 같습니다.

따라서 $W_8$의 모든 기저는 다음과 같습니다.

다음으로 $W_4$는 $V_4$의 직교여공간입니다. 따라서 $V_8$의 기저 $b_0^8, b_1^8, ..., b_7^8$을 $V_4$에 직교 투영한 벡터를 찾습니다. 예를 들어 $W_0^4 = b_0^8 - b_0^{8^{\parallel V_4}}$ 입니다. $b_0^8$과 $V_4$의 기저는 다음과 같습니다.

$b_0^8 - b_0^{8^{\parallel V_4}} = b_0^8 - \frac{1 + 1}{1 + 1 + 1 + 1} b_0^4$이므로 $w_0^4$는 다음과 같습니다.

위와 같은 패턴은 반복되어 이후 다음 웨이브릿 기저들을 갖습니다.

웨이브릿 기저가 어떤 값들을 가지는지 알아보았습니다. 이제 16픽셀 이미지 벡터가 웨이브릿 기저에 의해 어떻게 표현되는지 그 계수들을 알아보겠습니다. 예를 들어 다음과 같은 16픽셀 이미지 벡터가 있습니다.

이것을 초기의 기저에 의해 표현하면 다음과 같습니다.

그리고 새로운 기저 $b_0^8, ..., b_7^8, w_0^8, ..., w_7^8$에 의해 다음과 같이 쓸 수 있습니다.

우변의 벡터들은 서로 직교하므로 각각의 항은 각각의 벡터에 대한 $v$의 투영입니다. 따라서 계수를 다음 식을 이용해 찾을 수 있습니다.

계수 $x_i$는 박스벡터 계수, $y_i$는 웨이브릿 계수라 합니다. $x_i$와 $y_i$를 매번 도트곱으로 구해야 할 것 같지만 사실 간단한 패턴이 있습니다. 아래는 $v$의 $V_{16}$의 기저에 대한 계수들과 그들을 바탕으로 구한 $V_8$의 기저에 대한 계수 $x_i$를 나타냅니다.

$V_8$의 기저에 대한 계수 $x_i$는 $V_{16}$의 기저에 대한 계수들의 평균에 의해 만들어집니다. 이는 이후 $V_4$, $V_2$, $V_1$에 대해서도 똑같이 적용됩니다.

실제 계수가 위 트리의 값과 같은지 $b_0^2$에 대한 계수 $\frac{44}{8}$을 확인해 보겠습니다.

한편 웨이브릿 기저에 대한 계수 $y_i$는 한 쌍의 계수들의 차분값입니다.

실제 계수가 위 트리의 값과 같은지 $w_1^2$에 대한 계수 $\frac{13}{4}$을 확인해 보겠습니다.

16픽셀 이미지를 15개의 웨이브릿 기저와 1개의 박스 기저에 대해 표현하는 법을 알아보았습니다. 압축을 위해서는 벡터들을 정규직교 기저에 대해 표현하는 것이 좋습니다. 따라서 기저들을 각각의 norm으로 나누고 선형결합의 항등을 위해 계수들에 norm을 곱함으로서 정규화합니다. 벡터 $v$를 정규화해 다음과 같이 바꿔 씁니다.

이 때 박스 벡터 $b_0^1$을 제외한 나머지 웨이브릿 기저의 norm은 다음과 같습니다.

n픽셀 이미지에 대해 각각의 norm 값이 $\frac{n}{4s}$ 라 할 수 있습니다.

웨이브릿 기저 프로시저

이제 웨이브릿 기저와 그의 계수, norm의 곱셈, 나눗셈을 이용해 1차원 이미지의 압축을 구현해보겠습니다. 이미지 압축은 다음 순서대로 진행됩니다.

• 계산의 편의를 위해 2의 제곱승 픽셀 이미지를 선택합니다.
• 표준 기저에 대해 표현한 이미지 벡터를 웨이브릿 기저에 대한 표현으로 바꿉니다.
• 스파스한 표현을 위해 억제(suppress) 압축을 적용합니다.
• 압축한 이미지 벡터를 다시 표준 기저에 대한 표현으로 되돌립니다.

16픽셀 이미지가 있을 때 정규화되지 않은 Haar 웨이브릿 기저는 다음 벡터들로 구성됩니다.

각각의 벡터에 대응하는 계수들은 딕셔너리에 다음과 같은 키값을 가지고 저장될 것입니다.

예를 들어 키 $(8,0)$에 연관된 값은 $w_0^8$에 대한 계수이고 $(1,0)$에 연관된 값은 $w_0^1$에 대한 계수입니다. $(0,0)$에 대한 계수는 $b_0^1$에 대한 계수이고 편의상 $b_0^1$은 $w_0^0$라 하겠습니다.

• 정규화되지 않은 웨이브릿 기저에 대한 계수를 구하는 프로시저 forward_no_normalization

def forward_no_normalization(v):
    D = {(0,0): sum(v)/len(v)}
    while len(v) > 1:
        k = len(v)
        for i in range(k // 2):
            D[(k // 2, i)] = v[2 * i] - v[2 * i + 1]
		vnew = [ (v[2 * i] + v[2 * i + 1]) / 2 for i in range(k // 2) ]
        v = vnew
    return D

프로시저 forward_no_normalization의 변수 vnew는 박스 기저에 대한 계수를 나타냈던 트리의 각각의 레이어를 뜻합니다. 예를 들어 $b_0^16, ..., b_{15}^{16}$에 대한 계수를 한 쌍씩 묶어 평균을 구한 $b_0^8, ..., b_7^8$에 대한 계수가 한 번의 이터레이션에서 저장됩니다. 한 번의 이터레이션을 통해 바뀐 vnew는 다음과 같습니다.

v = [ 4,5,3,7,4,5,2,3,9,7,3,5,0,0,0,0]

# 첫번째 이터레이션 후 v와 vnew
v = vnew = [ (4 + 5) / 2, (3 + 7) / 2, ..., (0 + 0) / 2 ]

웨이브릿 기저에 대한 계수는 변수 v의 한 쌍의 엔트리의 차분값이므로 D[(k // 2, i)] = v[2 * i] - v[2 * i + 1]와 같이 작성합니다.

• 정규화를 위해 계수들에 norm을 곱하는 프로시저 normalize_coefficients

import math

def normalize_coefficients(n, D):
    new_D = {(0,0) : D[(0,0)] * math.sqrt(n)}
    for k, v in D.items():
        if k[0] != 0:
            new_D[k] = v * math.sqrt(n / (4 * k[0]))
    return new_D

프로시저 normalize_coefficients에서 주의해야 할 것은 $w_0^1, ..., w_7^8$의 norm은 $\frac{n}{4s}$이지만 $w_0^0$의 norm은 $\sqrt{n}$이라는 것입니다.

• forward_no_normalization와 normalize_coefficients를 이용해 정규화된 웨이브릿 기저에 대한 계수를 구하는 프로시저 forward

def forward(v):
    return normalize_coefficients(len(v), forward_no_normalization(v))

프로시저 forward를 이용해 표준 기저에 대해 표현한 이미지 벡터를 웨이브릿 기저에 대해 표현할 수 있게 되었습니다. 이미지 압축의 첫 단계가 끝난 것입니다. 이제 새로운 기저에 대해 표현된 계수들 중 작은 값들을 억제하는 프로시저를 작성해 보겠습니다.

• 억제 압축 프로시저 suppress

def suppress(D, threshold):
    return {
        k: v if abs(v) > threshold else 0
        for k, v in D.items()
    }

간단히 딕셔너리 형태로 저장된 계수들 중 threshold보다 작은 값을 0으로 만듦으로서 억제 압축을 구현합니다. 이 때 0으로 만드는 것은 벡터를 스파스하게 표현하는 것입니다.

• 스파스의 정도를 측정하는 프로시저 sparsity

def sparsity(D):
    return len([ k for k in D if D[k] != 0 ]) / len(D)

만약 D에 0이 하나도 없다면 1의 sparsity를, 10개의 엔트리 중 2개의 0을 가지면 0.8의 sparsity를 갖게 됩니다.

프로시저 suppress를 이용해 웨이브릿 기저에 대한 이미지 벡터 표현을 압축할 수 있게 되었습니다. 이제 압축된 이미지 벡터를 다시 표준 기저에 대한 표현으로 바꾸는 과정을 구현해 보겠습니다.

• 계수들을 대응하는 웨이브릿 기저의 norm으로 나누는 프로시저 unnormalize_coefficients

import math

def unnormalize_coefficients(n, D):
    new_D = {}
    new_D[(0,0)] = D[(0,0)] / math.sqrt(n)
    for k, v in D.items():
        if k[0] != 0:
            new_D[k] = v / math.sqrt(n / (4 * k[0]))
    return new_D

단순히 프로시저 normalize_coefficients와 반대의 연산을 진행합니다.

• 엔트리의 평균과 차분을 이용해 표준 기저에 대한 계수를 구하는 프로시저 backward_no_normalization

def backward_no_normalization(D):
    n = len(D)
    v = [ D[(0,0)] ]
    while len(v) < n:
        k = len(v)
        vnew = [
            v[i // 2] + (-1)**i * D[(k, i // 2)] / 2
            for i in range(k * 2)
        ]
        v = vnew
        k *= 2
    return v

1-벡터를 2-벡터로, 2-벡터를 4-벡터로, ..., 8-벡터를 16-벡터로 되돌리는 방법은 한 쌍의 엔트리들의 평균과 차분을 이용해 역연산할 수 있습니다. 이는 v[i // 2] + (-1)**i * D[(k, i // 2)] / 2에 잘 구현되어 있습니다.

• unnormalize_coefficients, backward_no_normalization를 이용해 표준 기저에 대한 계수를 구하는 프로시저 backward

def backward(D):
     return backward_no_normalization(unnormalize_coefficients(len(D), D))

짐작하셨다시피 프로시저 forward, backward는 표준기저에 대한 계수와 웨이브릿 기저에 대한 계수 사이에서 서로 반대되는 변환 역할을 합니다.

2차원이미지로의 확장

웨이브릿 기저에 대한 이해와 1차원 이미지에 대한 프로시저를 바탕으로 2차원 이미지를 위한 프로시저를 작성해보겠습니다. 압축의 과정은 1차원 이미지의 경우와 같습니다.

• 표준기저에 대한 계수를 웨이브릿 기저에 대한 계수로 바꾸는 프로시저 forward2d

def dictlist_helper(dlist, k):
    return [ d[k] for d in dlist ]

def forward2d(listlist):
    D_list = [ forward(li) for li in listlist ]
    L_dict = {}
    for k in D_list[0]:
        L_dict[k] = dictlist_helper(D_list, k)
    D_dict = { k: forward(v) for k, v in L_dict.items() }
    return D_dict

forward2d는 다음 순서로 진행됩니다.

1. 리스트의 리스트로 받은 인자 listlist를 딕셔너리의 리스트 형태로 바꿉니다. 이 때 forward 프로시저를 이용해 각각의 표준기저에 대한 계수 리스트를 웨이브릿 기저에 대한 계수 딕셔너리로 바꿉니다.
2. 딕셔너리의 리스트를 리스트의 딕셔너리 형태로 바꿉니다. 이 때 프로시저 dictlist_helper를 보조 프로시저로 활용합니다. 이는 행벡터로 이루어진 행렬을 열벡터로 이루어진 행렬로 바꾸는 것과 같습니다.
3. 리스트의 딕셔너리를 딕셔너리의 딕셔너리 형태로 바꿉니다. 이 때 리스트를 딕셔너리로 바꾸는 작업은 forward로 이루어집니다.

• 2차원 이미지를 억제 압축하는 프로시저 suppress2d

def suppress2d(D_dict, threshold):
    for d in D_dict:
        D_dict[d] = { k: v if abs(v) > threshold else 0 for k, v in D_dict[d].items() }
    return D_dict

• 2차원 이미지의 sparsity를 구하는 프로시저 sparsity2d

def sparsity2d(D_dict):
    first = [ v for k, v in D_dict.items() ][0]
    return len([ v for km, d in D_dict.items() for kn, v in d.items() if v != 0 ]) / (len(D_dict) * len(first.keys()))

• 웨이브릿 기저에 대한 계수로 부터 표준 기저에 대한 계수를 구하는 프로시저 backward2d

def listdict2dict(L_dict, i):
    return { k: L_dict[k][i] for k in L_dict }

def listdict2dictlist(L_dict):
    li = [ v for k, v in L_dict.items() ][0]
    D_list = []
    for i, v in enumerate(li):
        D_list.append(listdict2dict(L_dict, i))
    return D_list

def backward2d(dictdict):
    listdict = { k: backward(v) for k, v in dictdict.items() }
    dictlist = listdict2dictlist(listdict)
    listlist = [ backward(d) for d in dictlist ]
    return listlist

프로시저 backward2d는 forward2d와 반대의 순서로 진행됩니다.

완성된 프로시저를 활용해 이미지를 압축해 보겠습니다.

from image import file2image, color2gray, image2display

listlist = color2gray(file2image('../assets/flag.png'))
image2display(listlist)

dictdict = forward2d(listlist)
print('sparse1 : ', sparsity2d(dictdict))
suppressed = suppress2d(dictdict, 20)
print('sparse2 : ', sparsity2d(suppressed))
new_listlist = backward2d(suppressed)
image2display(new_listlist)

>>>
sparse1 :  0.4568977355957031
sparse2 :  0.10197830200195312

원본 이미지

압축된 이미지