8.3. The Search for a Good Basis

선형대수학 글 목록

연결 강의: MIT 18.06 Linear Algebra - Lecture 31: Change of Basis; Image Compression

1. 이번 강의의 위치

이번 강의는 change of basis, 즉 기저변환을 다룬다.

앞 강의에서는 linear transformation 자체는 좌표 없이도 정의할 수 있지만, 실제 계산을 하려면 basis를 정하고 matrix를 얻어야 한다고 했다.

이번에는 한 걸음 더 나아간다. 같은 linear transformation이라도 어떤 basis를 쓰느냐에 따라 matrix 표현이 달라진다. 그래서 중요한 질문은 단순히 “basis를 바꿀 수 있는가?”가 아니라, “어떤 basis가 좋은가?”이다.

이 질문은 순수한 선형대수 문제처럼 보이지만, 실제 응용에서는 image compression, signal compression, video compression 같은 문제와 바로 연결된다.

핵심 흐름은 다음이다.

data⟶choose a better basis⟶few important coefficients⟶compression\text{data} \quad \longrightarrow \quad \text{choose a better basis} \quad \longrightarrow \quad \text{few important coefficients} \quad \longrightarrow \quad \text{compression}

즉 좋은 basis를 찾는 문제는 데이터를 더 적은 숫자로 표현하는 문제이다.

2. 이미지는 벡터이다

흑백 이미지를 하나 생각하자. 이미지는 작은 pixel들의 모음이다.

예를 들어 512×512512 \times 512 크기의 흑백 이미지는 총

5122=29⋅29=218512^2 =2^9 \cdot 2^9 =2^{18}

개의 pixel을 가진다.

각 pixel은 보통 gray scale 값을 가진다. 예를 들어 검정부터 흰색까지를 00부터 255255까지의 값으로 나타낸다.

xi∈{0,1,2,…,255}x_i \in \{0,1,2,\dots,255\}

여기서 xix_i는 ii번째 pixel의 밝기이다.

따라서 흑백 이미지 하나는 다음과 같은 큰 벡터로 볼 수 있다.

x∈Rn,n=5122x \in \mathbb{R}^n, \qquad n=512^2

컬러 이미지라면 빨강, 초록, 파랑 값을 따로 저장해야 하므로 대략 세 배의 정보가 필요하다.

x∈R3⋅5122x \in \mathbb{R}^{3 \cdot 512^2}

이렇게 보면 image compression은 결국 매우 큰 벡터 xx를 더 적은 정보로 표현하는 문제이다.

3. Standard Basis는 항상 좋은 Basis가 아니다

이미지를 pixel 값 그대로 저장하는 방식은 standard basis를 쓰는 것과 같다.

standard basis는 다음과 같은 벡터들이다.

e1=[100⋮0],e2=[010⋮0],…e_1= \begin{bmatrix} 1\\ 0\\ 0\\ \vdots\\ 0 \end{bmatrix}, \quad e_2= \begin{bmatrix} 0\\ 1\\ 0\\ \vdots\\ 0 \end{bmatrix}, \quad \dots

이 basis에서는 ii번째 좌표가 곧 ii번째 pixel 값이다.

하지만 이미지에서는 가까운 pixel들이 대체로 비슷한 값을 가진다. 예를 들어 칠판만 있는 화면을 생각하면 많은 pixel이 거의 같은 회색 또는 검정색 값이다. 파란 셔츠 부분도 주변 pixel이 거의 비슷한 색이다.

이런 경우 pixel 하나하나를 독립적으로 저장하는 standard basis는 비효율적이다. 서로 비슷한 값이 계속 반복되는데도, 모든 pixel 값을 따로 저장하기 때문이다.

예를 들어 완전히 같은 밝기의 이미지라면, 사실 필요한 정보는 “모든 pixel이 같은 값이다”라는 하나의 정보에 가깝다. 이런 이미지를 표현하기에 좋은 basis vector는 다음과 같은 all-ones vector이다.

[111⋮1]\begin{bmatrix} 1\\ 1\\ 1\\ \vdots\\ 1 \end{bmatrix}

이 벡터 하나만 있으면 일정한 밝기의 이미지를 매우 잘 표현할 수 있다.

반대로 다음과 같은 벡터는 밝고 어두운 값이 계속 번갈아 나타나는 checkerboard pattern을 나타낸다.

[1−11−1⋮]\begin{bmatrix} 1\\ -1\\ 1\\ -1\\ \vdots \end{bmatrix}

이런 벡터는 고주파 성분을 나타낸다. 실제 자연 이미지나 강의 영상에서는 이런 빠른 변화가 전체 정보의 핵심인 경우가 많지 않다.

따라서 좋은 basis는 데이터에 자주 나타나는 패턴을 적은 수의 basis vector로 표현할 수 있어야 한다.

4. JPEG와 Fourier Basis

이미지 압축의 대표적인 표준이 JPEG이다.

JPEG의 핵심 아이디어도 basis를 바꾸는 것이다. 원래 pixel basis로 표현된 이미지를 다른 basis로 표현한 뒤, 중요하지 않은 coefficient를 버린다.

JPEG는 큰 이미지를 한 번에 처리하지 않고 보통 8×88 \times 8 block으로 나눈다.

하나의 block에는 6464개의 pixel이 있다.

8×8=648 \times 8 = 64

따라서 각 block은 R64\mathbb{R}^{64}의 벡터로 볼 수 있다.

JPEG의 첫 단계는 이 6464개의 pixel 값을 다른 basis의 coefficient로 바꾸는 것이다.

64 pixel values⟶64 coefficients\text{64 pixel values} \quad \longrightarrow \quad \text{64 coefficients}

이 단계 자체는 정보를 잃지 않는다. basis만 바꿨을 뿐, 같은 벡터를 다른 좌표로 표현한 것이다.

강의에서는 이 basis로 Fourier basis를 언급한다. Fourier basis는 constant vector, 낮은 frequency 성분, 높은 frequency 성분 등을 포함한다.

constant vector는 다음과 같다.

[111⋮1]\begin{bmatrix} 1\\ 1\\ 1\\ \vdots\\ 1 \end{bmatrix}

전기공학에서는 이것을 DC component라고 부르기도 한다. 이미지 block의 전체 평균 밝기를 나타내는 성분이다.

반대로 빠르게 1,−1,1,−11,-1,1,-1처럼 바뀌는 벡터는 high-frequency component이다. 이런 성분은 세밀한 변화, 잡음, 급격한 경계를 나타낸다.

5. 압축은 Coefficient를 버리는 과정이다

basis를 바꾸는 것만으로는 아직 압축이 아니다.

압축은 basis를 바꾼 뒤에 coefficient 일부를 버릴 때 일어난다.

흐름은 다음과 같다.

x→change basisc→compressionc^→reconstructx^x \quad \xrightarrow{\text{change basis}} \quad c \quad \xrightarrow{\text{compression}} \quad \hat{c} \quad \xrightarrow{\text{reconstruct}} \quad \hat{x}

여기서 xx는 원래 pixel 값 벡터이고, cc는 새 basis에서의 coefficient이다. c^\hat{c}는 작은 coefficient들을 버린 뒤의 압축된 coefficient이다.

작은 coefficient를 버리는 방식은 thresholding이라고 부른다. 어떤 기준값보다 작은 coefficient는 눈에 거의 보이지 않는 차이만 만들 것이라고 보고 00으로 만든다.

예를 들어 6464개의 coefficient 중 중요한 것이 33개 정도만 남고 나머지가 00이 되었다고 하자. 그러면 6464개의 값을 저장하던 것을 33개 정도의 값으로 줄인 셈이다.

643≈21\frac{64}{3} \approx 21

대략 21:121:1 정도의 압축률을 기대할 수 있다.

이 과정은 lossy compression이다. 정보를 일부 잃는다. 하지만 사람의 눈이 잘 구분하지 못하는 정보를 버린다면, 이미지 품질은 크게 떨어지지 않으면서 데이터 크기를 크게 줄일 수 있다.

6. 왜 영상에서는 움직임이 압축의 핵심인가

강의 영상도 압축된다. 칠판에 적힌 글씨는 비교적 잘 보이지만, 사람이 움직이는 부분은 더 많은 정보가 필요하다.

이유는 간단하다. 칠판의 많은 pixel은 한 프레임 안에서도 서로 비슷하고, 다음 프레임에서도 거의 그대로이다. 반면 사람이 움직이면 pixel 값이 시간에 따라 더 많이 변한다.

정지 이미지는 공간적으로 이웃한 pixel들이 비슷하다는 점을 이용한다.

영상은 여기에 시간 방향의 상관관계까지 이용한다. 즉 다음 프레임은 이전 프레임과 거의 비슷하다고 예측하고, 실제로 달라진 correction만 저장한다.

next frame≈previous frame+small correction\text{next frame} \approx \text{previous frame} + \text{small correction}

그래서 video compression은 단순히 정지 이미지를 하나씩 압축하는 것보다 더 많은 구조를 사용한다.

7. 지문 압축 예시

강의에서는 FBI의 fingerprint database 예시도 나온다.

지문은 많은 선과 굴곡을 가진 이미지이다. 과거에는 종이에 찍은 지문을 파일로 보관했지만, 수천만 개의 지문 중에서 하나를 찾으려면 시간이 너무 오래 걸린다.

그래서 지문을 digital image로 바꾸고, 다시 압축하고, 검색 가능한 형태로 저장한다.

하지만 digitize만으로는 충분하지 않다. 512×512512 \times 512 pixel 이미지를 그대로 저장하면 여전히 데이터가 너무 많다. 그래서 어떤 basis를 선택해 지문 이미지를 압축할 것인지가 중요한 문제가 된다.

여기서도 본질은 같다.

fingerprint image⟶change basis⟶important coefficients⟶compressed searchable data\text{fingerprint image} \quad \longrightarrow \quad \text{change basis} \quad \longrightarrow \quad \text{important coefficients} \quad \longrightarrow \quad \text{compressed searchable data}

즉 지문 검색도 좋은 basis를 찾는 선형대수 문제와 연결된다.

8. Fourier의 경쟁자: Wavelet Basis

Fourier basis는 오랫동안 signal과 image compression에서 중요한 역할을 했다.

그런데 Fourier basis의 경쟁자로 wavelet basis가 등장한다.

강의에서는 가장 단순한 wavelet basis를 R8\mathbb{R}^8에서 설명한다. 다음과 같은 88개의 벡터를 생각하자.

w1=[11111111],w2=[1111−1−1−1−1]w_1= \begin{bmatrix} 1\\1\\1\\1\\1\\1\\1\\1 \end{bmatrix}, \quad w_2= \begin{bmatrix} 1\\1\\1\\1\\-1\\-1\\-1\\-1 \end{bmatrix} w3=[11−1−10000],w4=[000011−1−1]w_3= \begin{bmatrix} 1\\1\\-1\\-1\\0\\0\\0\\0 \end{bmatrix}, \quad w_4= \begin{bmatrix} 0\\0\\0\\0\\1\\1\\-1\\-1 \end{bmatrix} w5=[1−1000000],w6=[001−10000]w_5= \begin{bmatrix} 1\\-1\\0\\0\\0\\0\\0\\0 \end{bmatrix}, \quad w_6= \begin{bmatrix} 0\\0\\1\\-1\\0\\0\\0\\0 \end{bmatrix} w7=[00001−100],w8=[0000001−1]w_7= \begin{bmatrix} 0\\0\\0\\0\\1\\-1\\0\\0 \end{bmatrix}, \quad w_8= \begin{bmatrix} 0\\0\\0\\0\\0\\0\\1\\-1 \end{bmatrix}

첫 번째 벡터 w1w_1은 전체 평균을 나타낸다.

두 번째 벡터 w2w_2는 앞 절반과 뒤 절반의 차이를 나타낸다.

w3,w4w_3,w_4는 더 작은 구간에서의 차이를 나타내고, w5,…,w8w_5,\dots,w_8은 아주 국소적인 변화까지 나타낸다.

이 basis는 계층적이다. 큰 scale의 변화부터 작은 scale의 변화까지 차례로 표현한다. 이것이 wavelet의 중요한 직관이다.

9. Wavelet Basis의 좋은 성질

위의 wavelet vector들은 서로 orthogonal이다.

예를 들어 w1w_1과 w2w_2의 dot product는 다음과 같다.

w1Tw2=1+1+1+1−1−1−1−1=0w_1^T w_2 =1+1+1+1-1-1-1-1 =0

w2w_2와 w3w_3도 orthogonal이다.

w2Tw3=1+1−1−1+0+0+0+0=0w_2^T w_3 =1+1-1-1+0+0+0+0 =0

이처럼 basis vector들이 서로 orthogonal이면 coefficient를 구하기가 쉬워진다.

다만 위 벡터들은 아직 orthonormal은 아니다. 길이가 모두 11은 아니기 때문이다. 예를 들어 w1w_1의 길이는 8\sqrt{8}이고, w2w_2의 길이도 8\sqrt{8}이다. 필요한 경우 각 벡터를 자기 길이로 나누면 orthonormal basis가 된다.

orthonormal basis를 열로 가지는 행렬 WW에 대해서는 다음이 성립한다.

W−1=WTW^{-1}=W^T

따라서 inverse를 구하기 쉽고, change of basis 계산도 빠르다.

10. Fourier Vector와 Wavelet Vector의 관계

다음과 같은 빠르게 바뀌는 벡터를 생각하자.

h=[1−11−11−11−1]h= \begin{bmatrix} 1\\-1\\1\\-1\\1\\-1\\1\\-1 \end{bmatrix}

이 벡터는 high-frequency component에 해당한다.

위 wavelet basis에서는 이 벡터를 다음처럼 표현할 수 있다.

h=w5+w6+w7+w8h=w_5+w_6+w_7+w_8

즉 어떤 basis를 쓰더라도 벡터 자체는 그대로이다. 다만 그 벡터를 어떤 coefficient들의 조합으로 표현하느냐가 달라진다.

이것이 change of basis의 핵심이다.

11. Change of Basis의 기본 식

이제 선형대수 구조를 정리하자.

새 basis vector들을 행렬 WW의 column으로 넣는다.

W=[∣∣∣w1w2⋯wn∣∣∣]W= \begin{bmatrix} | & | & & | \\ w_1 & w_2 & \cdots & w_n \\ | & | & & | \end{bmatrix}

어떤 벡터 xx를 새 basis에서 coefficient cc로 표현한다는 것은 다음을 뜻한다.

x=c1w1+c2w2+⋯+cnwnx=c_1w_1+c_2w_2+\cdots+c_nw_n

matrix form으로 쓰면 다음이다.

x=Wcx=Wc

따라서 새 basis에서의 coordinate cc는 다음처럼 구한다.

c=W−1xc=W^{-1}x

이 식이 image compression에서의 transform step이다.

pixel values x⟶new coefficients c\text{pixel values } x \quad \longrightarrow \quad \text{new coefficients } c

만약 WW가 orthonormal matrix라면 W−1=WTW^{-1}=W^T이므로 계산이 훨씬 쉬워진다.

12. 좋은 Basis의 조건

좋은 basis는 두 가지 조건을 만족해야 한다.

첫째, 계산이 빨라야 한다.

c=W−1xc=W^{-1}x

를 빠르게 계산할 수 있어야 하고, 복원할 때 필요한

x=Wcx=Wc

도 빠르게 계산할 수 있어야 한다.

Fourier basis가 강력했던 이유는 Fast Fourier Transform, 즉 FFT가 있기 때문이다. FFT는 Fourier basis로의 변환을 빠르게 계산하게 해준다.

Wavelet basis도 fast wavelet transform을 통해 빠르게 계산할 수 있다.

둘째, 압축이 잘 되어야 한다.

즉 대부분의 정보를 적은 수의 coefficient에 몰아넣을 수 있어야 한다.

standard basis는 계산은 매우 빠르지만 압축에는 좋지 않다. pixel 값 90%90\%를 버리면 이미지 대부분이 사라진다.

반면 좋은 Fourier basis나 wavelet basis에서는 뒤쪽의 작은 coefficient들을 버려도 이미지의 큰 구조가 남는다.

정리하면 좋은 basis란 다음과 같다.

fast transform+few coefficients capture most information\text{fast transform} \quad + \quad \text{few coefficients capture most information}

13. 같은 Linear Transformation, 다른 Matrix

이제 basis change가 matrix 표현에 어떤 영향을 주는지 보자.

linear transformation TT 자체는 좌표와 무관하게 존재한다.

하지만 basis를 정하면 그 transformation은 matrix로 표현된다.

예를 들어 첫 번째 basis v1,…,vnv_1,\dots,v_n에서 TT의 matrix가 AA라고 하자.

두 번째 basis w1,…,wnw_1,\dots,w_n에서 같은 TT의 matrix가 BB라고 하자.

그러면 AA와 BB는 서로 다른 matrix일 수 있다. 하지만 완전히 무관한 matrix는 아니다. 둘은 같은 transformation을 다른 coordinate system에서 표현한 것이므로 similar matrices이다.

즉 어떤 invertible matrix MM에 대해 다음 관계가 성립한다.

B=M−1AMB=M^{-1}AM

여기서 MM은 basis를 바꾸는 change-of-basis matrix이다.

이 관계는 이전에 배운 similar matrices와 연결된다. 같은 linear transformation을 다른 basis에서 보면 similar matrix가 나온다.

14. Matrix를 만드는 법 다시 보기

마지막으로 linear transformation에서 matrix를 만드는 방법을 다시 정리하자.

basis v1,…,vnv_1,\dots,v_n이 주어져 있다고 하자. transformation TT의 matrix를 만들려면 각 basis vector가 어디로 가는지 보면 된다.

첫 번째 basis vector에 대해

T(v1)=a11v1+a21v2+⋯+an1vnT(v_1)=a_{11}v_1+a_{21}v_2+\cdots+a_{n1}v_n

라고 쓰면, 이 coefficient들이 matrix의 첫 번째 column이 된다.

두 번째 basis vector에 대해

T(v2)=a12v1+a22v2+⋯+an2vnT(v_2)=a_{12}v_1+a_{22}v_2+\cdots+a_{n2}v_n

라고 쓰면, 이 coefficient들이 matrix의 두 번째 column이 된다.

계속 반복하면 matrix AA는 다음과 같이 만들어진다.

A=[a11a12⋯a1na21a22⋯a2n⋮⋮⋱⋮an1an2⋯ann]A= \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}

즉 matrix의 jj번째 column은 T(vj)T(v_j)를 basis v1,…,vnv_1,\dots,v_n으로 표현한 coordinate이다.

15. 최고의 Basis는 Eigenvector Basis이다

가장 좋은 basis의 대표적인 예는 eigenvector basis이다.

만약 basis vector들이 모두 TT의 eigenvector라면,

T(vi)=λiviT(v_i)=\lambda_i v_i

가 성립한다.

이때 T(vi)T(v_i)는 다른 basis vector 방향으로 섞이지 않고, 자기 자신 방향으로만 늘어나거나 줄어든다.

따라서 이 basis에서 matrix는 diagonal matrix가 된다.

A=[λ10⋯00λ2⋯0⋮⋮⋱⋮00⋯λn]A= \begin{bmatrix} \lambda_1 & 0 & \cdots & 0\\ 0 & \lambda_2 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & \lambda_n \end{bmatrix}

이것이 diagonalization의 의미이다.

choose eigenvector basis⟶matrix becomes diagonal\text{choose eigenvector basis} \quad \longrightarrow \quad \text{matrix becomes diagonal}

이미지 처리에서도 이상적으로는 데이터를 가장 잘 표현하는 basis를 찾고 싶다. 하지만 실제 pixel data에서 완벽한 eigenvector basis를 계산하는 것은 너무 비싸다.

그래서 Fourier basis나 wavelet basis처럼 계산이 빠르고 압축 성능이 좋은 basis를 선택한다.

16. 정리

이번 강의의 핵심은 basis가 단순한 표현 방식이 아니라, 계산과 압축의 성능을 결정한다는 점이다.

같은 벡터라도 standard basis에서는 많은 coordinate가 필요할 수 있지만, 좋은 basis에서는 몇 개의 coefficient만으로도 충분히 잘 표현될 수 있다.

image compression의 흐름은 다음과 같다.

x=Wc,c=W−1xx=Wc, \qquad c=W^{-1}x

여기서 WW의 column들이 선택한 basis vector이다. Fourier basis나 wavelet basis는 WW와 W−1W^{-1}을 빠르게 계산할 수 있고, 실제 이미지에서 많은 coefficient를 작게 만들어 압축에 유리하다.

한편 linear transformation의 matrix 표현도 basis에 의존한다. 같은 transformation을 다른 basis에서 표현하면 서로 similar한 matrix가 나온다.

B=M−1AMB=M^{-1}AM

결국 “좋은 basis를 찾는다”는 말은 두 가지를 동시에 의미한다.

첫째, 벡터나 데이터를 적은 coefficient로 잘 표현하는 basis를 찾는 것이다.

둘째, linear transformation을 가능한 한 단순한 matrix로 표현하는 basis를 찾는 것이다.

이 관점에서 eigenvector basis는 matrix를 diagonal로 만드는 가장 이상적인 basis이고, Fourier와 wavelet basis는 실제 signal과 image compression에서 계산 가능성과 압축 성능을 함께 만족시키는 실용적인 basis이다.