Lecture 31. 기저 변환과 영상 압축 - 선형대수

지난 강의에서 우리는 기저를 고를 자유를 얻었다. 변환은 실체이고 행렬은 그림자이며, 조명의 각도를 바꾸면 그림자가 달라진다는 것을 보았다.

그런데 자유를 얻었으면 써먹어야 한다. 기저를 잘 고르면 무슨 이득이 있는가. 계산이 쉬워지는 것 말고 또 무엇이 있는가.

사진 한 장을 JPEG으로 저장할 때 실제로 무슨 일이 벌어지는지 생각해 보자. $512 \times 512$ 사진에는 숫자가 262,144개 있다. 픽셀 기저에서는 어느 하나도 버릴 수 없다. 각 숫자가 한 점의 밝기이고, 버리면 그 점이 사라진다.

그런데 좌표계를 코사인 기저로 바꾸면 상황이 완전히 달라진다. 대부분의 계수가 0에 가까워진다. 그러면 버려도 되는 것이 생긴다.

그것이 압축이다. 정보를 줄이는 것이 아니라, 정보가 몇 개의 숫자에 모이는 좌표계로 갈아타는 것이다.

1. 기저 변환의 형식과 좋은 기저의 세 조건¶

형식은 L30에서 이미 다 나왔다. 신호 $\vv{x}$ 를 기저 $\vv{w}_1, \dots, \vv{w}_N$ 으로 전개한 계수가 $\vv{c}$ 라는 것은, 기저벡터를 열에 세운 행렬 $W$ 에 대해

\vv{x} = W\vv{c} = c_1\vv{w}_1 + c_2\vv{w}_2 + \dots + c_N\vv{w}_N

(1)

라는 뜻이다. 압축이란 (1)의 $\vv{c}$ 에서 작은 것들을 0으로 만들어 버리는 일이다.

어떤 기저가 좋은 기저인가. 세 가지를 요구하게 된다.

세 조건을 모두 만족하는 기저를 찾는 것이 신호처리 전체의 목표라 해도 지나치지 않다.

조건 ①이 왜 조건인가¶

$O(N^2)$ 과 $O(N\log_2 N)$ 의 차이는 신호가 커질수록 벌어진다. 비율이

\frac{N^2}{N\log_2 N} = \frac{N}{\log_2 N}

(2)

이므로, (2)의 값은 $8\times8$ 블록( $N=64$ )에서 11배지만 $512\times512$ 사진( $N = 262{,}144$ )에서는 14,564배, 4K 사진( $N = 8{,}294{,}400$ )에서는 36만 배가 된다. 좋은 기저를 찾아 놓고 곱셈에서 지면 아무 소용이 없다.

조건 ③이 조건 ②를 쓸모 있게 만든다¶

조건 ③이 왜 그렇게 중요한지 계산으로 보자. 먼저 정규직교이면 계수를 구하는 일 자체가 간단해진다. (1)의 양변에 $\vv{w}_i$ 를 내적하면, $j \neq i$ 인 항은 전부 0이 되므로

\vv{w}_i^{\mathsf T}\vv{x} = \sum_{j} c_j\,\vv{w}_i^{\mathsf T}\vv{w}_j = c_i

(3)

이다. 계수는 그냥 내적이다. 연립방정식을 풀 필요가 없다.

이제 오차로 가자. $W^{\mathsf T}W = I$ 이므로 임의의 벡터 $\vv{z}$ 에 대해

\lVert W\vv{z}\rVert^2 = (W\vv{z})^{\mathsf T}(W\vv{z}) = \vv{z}^{\mathsf T}W^{\mathsf T}W\vv{z} = \vv{z}^{\mathsf T}\vv{z} = \lVert\vv{z}\rVert^2

(4)

이다. 길이가 보존된다. L17에서 본 직교행렬의 성질이고, 여기서는 파세발 등식이라 부른다.

계수 몇 개를 0으로 만든 것을 $\hat{\vv{c}}$ 라 하고 되돌린 것을 $\hat{\vv{x}} = W\hat{\vv{c}}$ 라 하자. 복원 오차는 (4)의 등식으로 곧바로 계산된다.

\lVert \vv{x} - \hat{\vv{x}} \rVert = \lVert W\vv{c} - W\hat{\vv{c}} \rVert = \lVert W(\vv{c} - \hat{\vv{c}}) \rVert = \lVert \vv{c} - \hat{\vv{c}} \rVert = \sqrt{\sum_{\text{버린 } i} c_i^2}

(5)

여덟 개의 숫자로 확인하기¶

이야기가 추상적이니 $N = 8$ 로 줄여 보자. 어떤 신호가 이렇다고 하자.

\vv{x} = (7,\; 7.5,\; 8,\; 8.2,\; 8,\; 7,\; 5.5,\; 4)

(6)

코사인 기저로 옮기면 계수가 이렇게 나온다.

\vv{c} = (19.52,\; 2.60,\; -2.78,\; 0.51,\; -0.28,\; 0.03,\; -0.07,\; 0.05)

(7)

같은 여덟 개의 숫자를 두 가지로 포장한 것이다. 왼쪽에서는 여덟 개가 고르게 나눠
갖고 있고, 가운데에서는 앞의 세 개가 거의 전부를 갖고 있다. — Figure 1:같은 여덟 개의 숫자를 두 가지로 포장한 것이다. 왼쪽에서는 여덟 개가 고르게 나눠 갖고 있고, 가운데에서는 앞의 세 개가 거의 전부를 갖고 있다.

두 기저에서 각각 큰 것 세 개만 남기고 나머지를 버려 보자.

	남긴 것	오차
픽셀 기저	$8.2,\ 8,\ 8$	14.16
코사인 기저	$19.52,\ -2.78,\ 2.60$	0.59

스물네 배 차이가 난다. 버린 숫자의 개수는 똑같이 다섯 개인데 그렇다. 그리고 0.59 라는 값은 (5)의 식이 예언한 값과 정확히 같다.

\sqrt{0.51^2 + 0.28^2 + 0.03^2 + 0.07^2 + 0.05^2} = 0.588

(8)

2. 코사인 기저 — 모두가 같은 사전을 쓰기로 한다¶

그러면 그 코사인 기저는 무엇인가. L26에서 만든 푸리에 행렬이 여기서 실제로 쓰인다.

DCT 기저를 적어 두자¶

$N$ 점 신호에 대한 코사인 기저벡터는 이렇게 생겼다.

\vv{w}_k[n] = \alpha_k \cos\!\left(\frac{\pi\,(2n+1)\,k}{2N}\right), \qquad \alpha_0 = \sqrt{\tfrac{1}{N}}, \quad \alpha_{k\ge1} = \sqrt{\tfrac{2}{N}}

(9)

$k = 0$ 이면 코사인의 각이 언제나 0이라 $\vv{w}_0$ 은 평평하다. 곧 평균이다. $k$ 가 커질수록 잔물결이 촘촘해진다. $\alpha_k$ 는 길이를 1로 맞추려고 붙인 상수이고, 그렇게 맞추면 $W^{\mathsf T}W = I$ 가 되어 조건 ③이 만족된다.

(9)의 각이 $\pi kn/N$ 이 아니라 $\pi k(2n+1)/2N$ 인 것이 눈에 걸린다. $n$ 에 $\tfrac12$ 이 더해져 있다. 왜 반 칸이 밀려 있는가. 그 반 칸에서 이 강의의 절반이 나온다.

DCT는 거울에 비춘 신호의 푸리에 변환이다¶

푸리에 변환은 신호가 주기적이라고 가정한다. $N$ 개의 표본 뒤에 같은 것이 또 온다고 보는 것이다. 그런데 사진의 한 줄을 떼어다 옆에 이어 붙이면 어떻게 되는가.

가장 매끄러운 신호를 생각해 보자. 0 에서 1 까지 곧게 올라가는 기울기다. 이보다 매끄러운 신호는 없다. 그런데 주기적으로 이어 붙이면 끝에서 $1 \to 0$ 으로 뚝 떨어진다. 없던 절벽이 생겨 버린 것이다.

그러면 절벽이 안 생기게 이어 붙이면 되지 않는가. 거울처럼 뒤집어 붙이면 된다. 길이 $2N$ 의 신호 $\vv{y}$ 를 이렇게 만든다.

y_n = x_n \quad (0 \le n < N), \qquad y_{2N-1-n} = x_n \quad (0 \le n < N)

(10)

(10)의 $\vv{y}$ 는 끝과 시작이 같은 값이므로 주기적으로 이어 붙여도 절벽이 없다. 이제 이 $\vv{y}$ 를 푸리에 변환해 보자. L26에서 배운 그대로다.

Y_k = \sum_{n=0}^{2N-1} y_n\, e^{-2\pi i k n / (2N)} = \sum_{n=0}^{N-1} x_n \left( e^{-i\pi k n/N} + e^{-i\pi k (2N-1-n)/N} \right)

(11)

(11)의 괄호 안 두 번째 항을 정리한다. $e^{-2\pi i k} = 1$ 이므로

e^{-i\pi k (2N-1-n)/N} = e^{-2\pi i k}\,e^{i\pi k(1+n)/N} = e^{i\pi k(n+1)/N}

(12)

이다. 이제 괄호에서 $e^{i\pi k/(2N)}$ 을 밖으로 빼내면 두 지수의 각이 부호만 다르게 된다.

e^{-i\pi kn/N} + e^{i\pi k(n+1)/N} = e^{i\pi k/(2N)} \left( e^{-i\pi k(2n+1)/(2N)} + e^{i\pi k(2n+1)/(2N)} \right)

(13)

(13)의 괄호는 오일러 공식에 의해 코사인의 두 배다. $e^{i\theta} + e^{-i\theta} = 2\cos\theta$ 이므로

Y_k = 2\,e^{i\pi k/(2N)} \sum_{n=0}^{N-1} x_n \cos\!\left(\frac{\pi\,(2n+1)\,k}{2N}\right)

(14)

절벽 하나가 계수를 얼마나 잡아먹는가¶

절벽이 왜 그렇게 비싼지도 계산으로 잡을 수 있다. 계수 $c_k$ 를 부분적분으로 한 번 정리하면 경계항과 도함수 항이 나온다.

\int_0^{2\pi} f(t)\,e^{-ikt}\,dt = \underbrace{\left[\frac{f(t)e^{-ikt}}{-ik}\right]_0^{2\pi}}_{\text{경계항}} + \frac{1}{ik}\int_0^{2\pi} f'(t)\,e^{-ikt}\,dt

(15)

(15)의 경계항은 $f(0) = f(2\pi)$ 일 때, 곧 절벽이 없을 때만 사라진다. 사라지면 남은 항이 $1/k$ 배이므로 다시 부분적분할 수 있고, 매끄러운 만큼 반복된다. 사라지지 않으면 거기서 멈춘다.

\lvert c_k \rvert \sim \begin{cases} \dfrac{1}{k} & \text{절벽이 있으면} \\[2mm] \dfrac{1}{k^{p+1}} & \text{$p$ 계도함수까지 이어져 있으면} \end{cases}

(16)

톱니 신호로 실제로 재 보면 로그-로그 기울기가 -0.98 이 나온다. (16)의 첫 줄 그대로다.

왼쪽이 DFT의 가정, 가운데가 DCT의 가정이다. 오른쪽은 그 결과다.
에너지의 99.9%를 담으려면 DFT는 64개 중 59개가 필요하고
DCT는 3개면 된다. 같은 기울기 하나를 두고 그렇다. — Figure 2:왼쪽이 DFT의 가정, 가운데가 DCT의 가정이다. 오른쪽은 그 결과다. 에너지의 99.9%를 담으려면 DFT는 64개 중 **59개**가 필요하고 DCT는 3개면 된다. 같은 기울기 하나를 두고 그렇다.

8×8 블록으로 자르는 이유¶

JPEG은 사진 전체에 DCT를 걸지 않는다. $8 \times 8$ 블록으로 잘라 각각 따로 변환한다. 왜인가.

첫째, 국소성이다. 사진의 왼쪽 위는 하늘이고 오른쪽 아래는 잔디라면, 두 곳에 필요한 주파수가 전혀 다르다. 전체를 한꺼번에 변환하면 하나의 계수 목록으로 둘을 다 감당해야 한다. 블록으로 나누면 각 블록이 자기 동네에 맞는 계수만 쓴다.

둘째, 계산량이다. 다만 여기서는 생각보다 이득이 작다. $M \times M$ 사진을 $B \times B$ 블록으로 나누면 비용의 비가

\frac{M^2 \log_2 M^2}{\left(M/B\right)^2 \cdot B^2 \log_2 B^2} = \frac{\log_2 M^2}{\log_2 B^2} = \frac{\log_2 M}{\log_2 B}

(17)

이다. (17)의 값은 $M = 256$ , $B = 8$ 에서 $8/3 \approx 2.7$ 배에 지나지 않는다. 속도는 부차적인 이유다. 진짜 이유는 국소성과, 블록 하나가 캐시에 들어가고 병렬화가 쉽다는 실무적인 사정이다.

8 \times 8 DCT의 기저 64장이다. 왼쪽 위가 의 k=0, 곧 평균이고
오른쪽·아래로 갈수록 잔물결이 촘촘해진다. 사진의 모든 8 \times 8 조각은 이 64장의
조합으로 적힌다. — Figure 3: $8 \times 8$ DCT의 기저 64장이다. 왼쪽 위가 (9)의 $k=0$ , 곧 평균이고 오른쪽·아래로 갈수록 잔물결이 촘촘해진다. 사진의 모든 $8 \times 8$ 조각은 이 64장의 조합으로 적힌다.

Figure 3의 그림이 이 강의에서 가장 중요한 그림일지도 모른다. 세상의 모든 JPEG 복호기가 이 표를 이미 갖고 있다. 그래서 이 표는 한 번도 전송되지 않는다. 이 사실이 4절에서 승부를 가른다.

손실이 실제로 발생하는 곳¶

DCT 자체는 손실이 없다. 정규직교 변환이니 되돌리면 원본이 정확히 나온다. 손실은 양자화에서 생긴다.

양자화는 계수를 정해진 간격 $\Delta$ 로 나누고 반올림한 뒤 다시 곱하는 일이다.

\hat{c} = \Delta \cdot \operatorname{round}\!\left(\frac{c}{\Delta}\right) \qquad\Longrightarrow\qquad \lvert c - \hat{c} \rvert \le \frac{\Delta}{2}

(18)

(18)의 부등식과 (5)의 식을 함께 보면, $\lvert c\rvert$ 가 $\Delta/2$ 보다 작은 계수는 통째로 0이 되고 그때 잃는 것이 정확히 $\lvert c\rvert$ 다. 그래서 간격 $\Delta$ 를 정하는 표가 곧 화질을 정하는 손잡이가 된다.

고주파일수록 $\Delta$ 를 크게 잡는데, 사람의 눈이 고주파에 둔감하기 때문이다. 실제로 재 보면 표준 JPEG 표를 쓸 때 계수의 95% 이상이 0이 된다.

3. 웨이블릿 — 언제인지도 알려주는 기저¶

DCT에는 치명적인 약점이 하나 있다. 경계를 못 잡는다.

코사인 함수는 신호 전체에 걸쳐 퍼져 있다. 그러니 " $n = 24$ 지점에서 값이 튄다"는 사실을 표현하려면, 그 지점에서만 살아남고 나머지에서 서로 상쇄되도록 모든 주파수를 미세하게 조율해야 한다. 계수가 통째로 필요해진다.

하르 웨이블릿을 만드는 규칙 하나¶

가장 단순한 웨이블릿은 하르 웨이블릿이다. 만드는 규칙이 하나뿐이다. 이웃끼리 평균을 내고, 차이를 낸다. 그것을 반복한다.

규칙을 행렬로 적으면 재귀식이 된다. 크기 $m$ 의 하르 행렬 $H_m$ 을 알고 있을 때

\sqrt{2}\,H_{2m} = \begin{pmatrix} H_m \otimes (1,\ 1) \\[1mm] I_m \otimes (1,\ -1) \end{pmatrix}

(19)

이다. (19)의 위쪽은 "이웃끼리 더한 뒤 다시 하르"이고 아래쪽은 "이웃끼리 뺀 것"이다. $N = 8$ 까지 펴 보면 이렇게 생겼다(보기 좋게 $\sqrt{8}$ 을 곱했다).

\sqrt{8}\,H = \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\ \sqrt2 & \sqrt2 & -\sqrt2 & -\sqrt2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \sqrt2 & \sqrt2 & -\sqrt2 & -\sqrt2 \\ 2 & -2 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & -2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & -2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 2 & -2 \end{pmatrix}

(20)

(20)의 행렬을 보면 0이 몰려 있다. 첫 두 행은 전체에 걸쳐 있지만, $\vv{h}_2, \vv{h}_3$ 은 절반씩만, $\vv{h}_4$ 부터는 두 칸씩만 차지한다. 그 두 칸 바깥에서는 아무 일도 하지 않는다. 이것이 국소성이다.

하르 변환은 FFT보다도 빠르다¶

(19)의 재귀에서 비용도 바로 읽힌다. 단계마다 남은 $n$ 개를 반씩 짝지어 합과 차를 만드니 덧셈이 $n$ 번이고, 다음 단계는 절반만 남는다.

T(N) = N + \frac{N}{2} + \frac{N}{4} + \dots + 2 = 2N - 2

(21)

(21)의 값은 $O(N\log N)$ 도 아니고 $O(N)$ 이다. 실제로 세어 보면 $N = 4096$ 에서 덧셈이 정확히 $8190 = 2N-2$ 회다. 같은 크기에서 FFT는 약 49,000회를 쓴다. 조건 ①은 웨이블릿이 압도적으로 이긴다.

계단 하나에 계수가 몇 개 드는가¶

국소성의 값어치도 셀 수 있다. 어느 한 자리에 계단이 하나 있는 신호를 생각하자. $\vv{h}_4$ 부터는 각 기저벡터가 두 칸만 보므로, 그 계단을 걸치는 것은 각 크기마다 정확히 하나뿐이다. 크기가 $N, N/2, \dots, 2$ 로 $\log_2 N$ 단계 있고 여기에 평균 하나를 더하면

(\text{0이 아닌 하르 계수의 개수}) \le \log_2 N + 1

(22)

이다. $N = 64$ 면 7개, $N = 1024$ 라도 11개다. 신호가 길어져도 거의 늘지 않는다. 실제로 계단을 모든 위치에 놓아 보면 (22)의 한계에 정확히 붙는다.

왼쪽이 하르 기저이고 가운데가 각 기저벡터가 차지하는 구간이다. 사인파라면
가운데 그림의 모든 막대가 끝에서 끝까지 뻗어 있어야 한다.
오른쪽은 계단 하나짜리 신호를 두 기저로 적어 본 결과다. — Figure 4:왼쪽이 하르 기저이고 가운데가 각 기저벡터가 차지하는 구간이다. 사인파라면 가운데 그림의 모든 막대가 끝에서 끝까지 뻗어 있어야 한다. 오른쪽은 계단 하나짜리 신호를 두 기저로 적어 본 결과다.

64점 계단 신호로 두 기저를 견줘 보면 이렇게 갈린다.

	0이 아닌 계수	에너지 99.9%에 필요한 개수
DCT	57개 / 64	42개
하르	4개 / 64	4개

2차원으로 올려도 마찬가지다. 세로 경계 하나뿐인 $256\times256$ 그림에서 DCT는 0이 아닌 계수가 253개인데 하르는 7개다.

4. SVD 대 DCT — 이 강의의 결론¶

이제 정면으로 붙여 보자.

L29에서 우리는 에카르트-영 정리를 확인했다. 랭크 $k$ 인 모든 행렬 $X$ 에 대해

\lVert A - A_k \rVert \le \lVert A - X \rVert

(23)

이고, (23)의 부등식은 무작위 행렬 3000개와 겨뤄도 한 번도 깨지지 않았다.

SVD는 이 사진 전용 기저를 계산해 준다. DCT는 모든 사진에 같은 기저를 쓴다. 당연히 전용 기저가 유리해야 한다. 실제로 그런지 보자.

첫 번째 재기 — 알맹이 개수를 맞추면¶

기저 저장은 세지 않고, 순수하게 "몇 개의 숫자로 내용을 담았는가"만 보면 이렇다.

알맹이 $k$ 개	DCT 상위 $k$ 개	SVD 랭크 $k$
5	21.8%	8.2%
20	13.8%	4.4%
100	9.4%	1.5%

SVD의 압승이다. (23)의 정리가 약속한 그대로다. 여기서 멈추면 "JPEG은 SVD를 써야 한다"는 결론이 나온다.

두 번째 재기 — 저장할 숫자의 개수를 맞추면¶

그런데 SVD로 압축한 파일을 받은 사람은 그것을 어떻게 펴는가. $U$ 와 $V$ 를 알아야 편다. 그 기저가 이 사진 전용이므로 함께 보내야 한다.

$m \times n$ 사진을 랭크 $k$ 로 근사할 때 저장할 숫자의 개수를 세어 보자.

\underbrace{mk}_{U} + \underbrace{nk}_{V} + \underbrace{k}_{\sigma} = k(m + n + 1)

(24)

(24)에서 실제 내용물은 $\sigma$ 뿐이고 그것은 $k$ 개다. 나머지 $k(m+n)$ 개는 전부 사전이다. 사전이 차지하는 몫은

이고, $256 \times 256$ 이면 (25)의 값이 $512/513 = 99.8\%$ 다. $1920 \times 1080$ 이면 $99.97\%$ 다.

예산 $B$ 개의 숫자가 주어졌을 때 두 쪽이 쓸 수 있는 것을 적어 보면 이렇다.

k_{\text{DCT}} = B, \qquad k_{\text{SVD}} = \frac{B}{m+n+1}

(26)

(26)의 두 값은 $256\times256$ 에서 513배 차이가 난다. 예산의 5%를 준다면 DCT는 계수 3,276개를 쓰고 SVD는 랭크 6에 그친다. 결과가 뒤집힌다.

예산 (전체 대비)	DCT 오차	SVD 오차	이긴 쪽
1%	5.3%	22.0%	DCT
2%	4.3%	11.4%	DCT
5%	3.1%	7.8%	DCT
10%	2.5%	6.0%	DCT

같은 예산에서 나온 결과다. 아래 막대가 그 예산이 어디에 쓰였는지 보여 준다.
SVD 막대에서 빨간 부분(내용물)이 거의 보이지 않는다. 예산의 99.8%가 사전이다. — Figure 5:같은 예산에서 나온 결과다. 아래 막대가 그 예산이 어디에 쓰였는지 보여 준다. SVD 막대에서 빨간 부분(내용물)이 거의 보이지 않는다. 예산의 99.8%가 사전이다.

DCT가 이긴 진짜 이유를 한 줄로 적으면 이렇다. DCT의 사전은 이미 상대방이 갖고 있어서 값이 0이다. 성능이 아니라 약속이 승부를 갈랐다.

블록 자국은 결함이 아니다¶

JPEG을 세게 걸면 $8 \times 8$ 격자가 눈에 보인다. 이것이 알고리즘의 버그처럼 보이지만 아니다. 필연이다.

각 블록이 따로 압축되므로, 이웃한 두 블록이 경계에서 값을 맞춰야 할 이유가 아무데도 없다. 각자 자기 블록 안에서만 최선을 다한다. 그러니 이음매에서 어긋난다.

실제로 재 보면 양자화를 세게 걸수록 블록 경계에서의 밝기 낙차가 블록 안쪽 낙차의 6배를 넘어간다.

주황색 격자가 8\times8 경계다. 오른쪽으로 갈수록 격자를 따라 계단이 생긴다.
이것을 없애려면 블록으로 자르지 말아야 하고, 그러면 국소성을 잃는다. — Figure 6:주황색 격자가 $8\times8$ 경계다. 오른쪽으로 갈수록 격자를 따라 계단이 생긴다. 이것을 없애려면 블록으로 자르지 말아야 하고, 그러면 국소성을 잃는다.

5. 왜 자연 이미지는 압축되는가¶

마지막 질문이 남았다. 왜 되는가?

지금까지 우리는 "좋은 기저를 고르면 계수가 몇 개에 몰린다"고 말해 왔다. 그런데 그것이 항상 되는 일인가. 아니다.

백색잡음은 어떤 정규직교 기저에서도 압축되지 않는다¶

무작위 잡음 그림을 생각하자. 각 픽셀이 서로 독립인 정규분포를 따른다면, 그 벡터 $\vv{x}$ 는 $N(\vv{0}, \sigma^2 I)$ 를 따른다. 여기에 정규직교 기저 $W$ 를 씌우면 계수는 $\vv{c} = W^{\mathsf T}\vv{x}$ 다. 정규분포의 선형변환은 다시 정규분포이고, 공분산은 이렇게 변한다.

\operatorname{Cov}(\vv{c}) = W^{\mathsf T}\operatorname{Cov}(\vv{x})\,W = W^{\mathsf T}\left(\sigma^2 I\right)W = \sigma^2 W^{\mathsf T}W = \sigma^2 I

(27)

Theorem 1의 정리는 압축의 한계를 그어 준다. 아무리 영리한 기저를 만들어도 백색잡음 앞에서는 소용이 없다. 실제로 재 보면 DCT든 하르든 무작위 직교행렬이든, 잡음 그림은 에너지 99%를 담는 데 **전체 계수의 73%**를 요구한다.

L29에서 무작위 그림을 SVD로 압축하면 원본보다 커진다는 것을 이미 보았다. 이제 그 이유가 정리로 정리되었다.

그렇다면 사진은 왜 다른가¶

사진은 백색잡음이 아니다. 이웃한 픽셀이 서로 닮았기 때문이다. 공분산이 $\sigma^2 I$ 가 아니라, 이웃끼리 큰 값을 갖는 행렬이다.

\operatorname{Cov}(\vv{x})_{ij} \approx \sigma^2 \rho^{\,\lvert i-j\rvert}, \qquad \rho \approx 0.98

(28)

(28)처럼 대각에서 멀어질수록 천천히 줄어드는 행렬은 고윳값이 급격히 치우친다. 그것이 곧 "몇 개의 계수가 거의 전부를 갖는다"는 말이다.

	이웃 픽셀 상관계수	DCT 계수 99%에 필요한 개수
시험 사진	0.984	82개 (0.1%)
무작위 잡음	-0.001	38,286개 (58%)

오른쪽 그림에서 주황색 점들은 대각선에 딱 붙어 있다. 한 픽셀을 알면 그 옆 픽셀을
거의 안다는 뜻이다. 회색 점들은 정사각형 전체에 흩어져 있다. — Figure 7:오른쪽 그림에서 주황색 점들은 대각선에 딱 붙어 있다. 한 픽셀을 알면 그 옆 픽셀을 거의 안다는 뜻이다. 회색 점들은 정사각형 전체에 흩어져 있다.

6. 자주 하는 오해¶

① 압축은 정보를 줄이는 것이다. 반은 맞고 반은 틀리다. 둘을 갈라야 한다.

무손실 압축은 정보를 하나도 안 줄인다. 표현만 바꾼다. 1절에서 본 기저 변환이 그것이고, 되돌리면 원본이 정확히 나온다. 손실 압축은 정보를 줄이는데, 아무거나 줄이는 것이 아니라 (5)의 식에 따라 오차에 가장 덜 기여하는 것부터 고른다. "줄인다"가 아니라 고른다가 정확한 말이다.

② SVD가 항상 더 좋다. 4절이 답이다. 같은 알맹이 개수라면 SVD가 이기고, 같은 저장량이라면 DCT가 이긴다. 무엇을 예산으로 세느냐에 따라 답이 뒤집힌다. 벤치마크를 읽을 때 늘 물어야 할 질문이다.

③ JPEG 격자 자국은 알고리즘의 결함이다. 아니다. 블록을 따로 압축하기로 한 순간 이음매의 불연속은 피할 수 없다. 결함이 아니라 설계상의 맞바꿈이다. 국소성을 얻는 대가로 이음매를 내준 것이다.

④ 정규직교가 아닌 기저를 써도 되지 않나. 쓸 수는 있다. 그러나 (4)의 등식이 깨지므로 (5)의 식도 깨진다. 그러면 "큰 것부터 남긴다"는 규칙 자체가 최선이 아니게 된다.

$N = 8$ 이면 $k$ 개를 고르는 방법이 많아야 70가지뿐이므로 전부 뒤져서 확인할 수 있다. 기저를 무작위로 기울여 가며 200개씩 재 보면 이렇다.

기울인 정도	조건수	"큰 것부터"가 최선이 아닌 비율	최악의 손해
0 (정규직교)	1.00	$0\%$	1.00배
0.05	1.31	$5.6\%$	1.11배
0.15	2.38	$20.8\%$	1.86배
0.35	14.7	$61.4\%$	22.7배
0.60	17.9	$73.5\%$	36.8배

정규직교에서는 한 번도 어긋나지 않는다. 조금만 기울여도 무너지기 시작하고, 많이 기울이면 열에 일곱은 최선이 아니다. 그때는 어느 것을 버릴지 알아내려고 매번 실제로 복원해 재 봐야 하고, 역변환도 전치가 아니라 진짜 역행렬을 구해야 한다. 값을 치를 이유가 없다.

⑤ 특이값이 빨리 줄면 좋은 사진이다. 아니다. 압축이 잘 되는 것과 사진이 좋은 것은 아무 상관이 없다. 온통 회색인 사진은 랭크 1이라 완벽하게 압축되지만 볼 것이 없다. 특이값의 감소 속도는 그 사진에 얼마나 구조가 있는가를 잴 뿐이다.

마치며...¶

이번 강의에서는 기저 변환이 곧 압축이라는 것을 확인하였다.

정규직교 기저에서는 계수가 그냥 내적이고, 버린 계수의 크기가 곧 오차다. 그래서 작은 것부터 버리면 된다.
DCT는 새로운 변환이 아니라 거울로 이어 붙인 신호의 푸리에 변환이다. 그래서 실수이고, 그래서 경계에 가짜 절벽이 없다. 기울기 하나를 담는 데 DFT는 59개, DCT는 3개를 쓴다.
$8\times8$ 블록으로 자르는 것은 국소성 때문이고, 그 대가가 격자 자국이다.
하르 변환은 $O(N)$ 으로 FFT보다도 빠르고, 계단 하나에 $\log_2 N + 1$ 개만 쓴다. "언제인지"를 알기 때문이다.
SVD는 알맹이당으로는 이기지만 예산의 99.8%를 사전에 쓰느라 실무에서 진다.
그리고 압축이 되는 것은 세계가 매끄럽기 때문이다. 백색잡음은 어떤 기저에서도 압축되지 않는다.

L30에서 얻은 "기저를 고를 자유"가 여기서 값을 했다. 그리고 그 자유에는 값이 붙어 있다는 것도 보았다. 좋은 기저를 새로 만들면 그 기저를 함께 들고 다녀야 한다.

이제 남은 질문은 하나뿐이다. 정방행렬이 아니어서, 혹은 랭크가 모자라서 역행렬이 아예 존재하지 않는 행렬을 어떻게 되돌릴 것인가?

놀랍게도 우리는 그 답을 이미 알고 있다. L30에서 미분 행렬 $D$ 를 만들었을 때, 적분 행렬 $S$ 가 한쪽으로만 역이 되는 것을 보았다. 그때 이름을 붙이지 않고 넘어간 그 $S$ 가 L33의 주인공이다.

다만 그 전에 한 번 숨을 고른다. 다음 강의는 새 내용이 아니라 정리다. 행렬 하나를 손에 쥐었을 때 무엇부터 물어야 하는지, 지금까지의 도구를 하나의 판단 절차로 묶는다.

이번 강의의 내용을 파이썬으로 확인해 보려면 L31 실습 노트북으로 넘어가면 된다. 버린 계수의 크기가 정말 오차와 같은지 재 보고, 거울 확장의 푸리에 변환이 정말 DCT인지 확인하고, 압축률을 슬라이더로 올려 가며 격자 자국이 생기는 순간을 보고, SVD와 DCT를 같은 예산에서 직접 겨뤄 볼 수 있다.