율-왜곡 이론

1. 개요[편집]

“이 사진 좀 더 줄여 줘”에 대한 물리 법칙. 어디까지 줄일 수 있는지는 취향이 아니라 정리가 정한다.

율-왜곡 이론(rate-distortion theory)은 손실 압축에서 「왜곡을 $D$ 이하로 유지하려면 표본당 최소 몇 비트가 필요한가」를 정보이론적으로 답하는 이론이다. 그 최솟값이 율-왜곡 함수 $R(D)$ 이고, 정의는 놀랄 만큼 짧다.

$$R(D) \;=\; \min_{\,p(\hat{x}\mid x)\,:\; \mathbb{E}[d(X,\hat{X})]\,\le\, D} \; I(X;\hat{X})$$

원천 $X \sim p(x)$ 와 왜곡 척도 $d(x,\hat{x})$ 가 주어졌을 때, 평균 왜곡을 $D$ 이하로 만드는 모든 시험 채널 $p(\hat{x}\mid x)$ 중에서 상호정보량이 최소인 것을 고른다. 섀넌이 1948년 논문의 마지막 부분에서 스케치하고 1959년에 「충실도 기준을 가진 이산 원천의 부호화 정리」로 정리했다.¹

읽는 법이 중요하다. 이것은 알고리즘이 아니라 한계선이다. 어떤 압축기도 이 선 아래로 못 가고, 반대로 블록 길이를 무한히 키울 수 있다면 이 선에 임의로 가까이 갈 수 있다. 엔트로피가 무손실 압축의 하한을 주는 것처럼, $R(D)$ 는 손실을 허용했을 때의 하한을 준다. 실제 부호기 설계는 벡터 양자화 문서가 다루고, 여기서는 그 위에 걸린 천장을 본다.

2. 왜 상호정보량인가[편집]

$R(D)$ 가 최소화하는 대상이 하필 $I(X;\hat X)$ 인 것에는 이유가 있다. 상호정보량은 「$\hat X$ 를 알고 나면 $X$ 에 대한 불확실성이 얼마나 줄어드는가」이고, 부호화란 결국 $X$ 에 관한 정보를 $\hat X$ 에 실어 보내는 일이다. $\hat X$ 가 나르는 정보량이 곧 필요한 비트 수라는 것이 정리의 내용이다.

$R(D)$ 의 성질 몇 개는 정의에서 바로 나온다.

• 비증가. 왜곡 예산을 늘리면 후보 시험 채널의 집합이 커지므로 최솟값이 줄어든다.
• 볼록. 두 최적 채널을 섞으면 왜곡은 선형으로 섞이는데 상호정보량은 입력 분포 고정 시 채널에 대해 볼록이라, 곡선이 아래로 볼록하다. 이 볼록성 덕에 라그랑주 쌍대가 잘 작동하고, 뒤에 나올 $J = D + \lambda R$ 이 정당해진다.
• $D = 0$ 이면 이산 원천에서 $R(0) = H(X)$. 왜곡을 하나도 허용하지 않으면 무손실 압축의 하한으로 되돌아간다. 연속 원천이면 $R(0) = \infty$ — 실수 하나를 정확히 보내려면 무한 비트가 필요하다는 당연한 사실.

최소화 자체는 볼록 최적화 문제라 이산 원천이면 수치적으로 풀 수 있다. 블라후트-아리모토 알고리즘이 표준으로, 조건부 분포와 주변 분포를 번갈아 갱신하는 교대 최소화이며 쿨백-라이블러 발산에 대한 교대 사영으로 해석된다. 채널 용량 계산과 완전히 대칭인 알고리즘이다.

3. 가우시안 — 유일하게 예쁜 닫힌 형태[편집]

원천이 $X \sim \mathcal{N}(0,\sigma^2)$ 이고 왜곡이 제곱오차 $d(x,\hat x) = (x-\hat x)^2$ 이면 최소화가 손으로 풀린다.

$$R(D) \;=\; \begin{cases} \dfrac{1}{2}\log_2 \dfrac{\sigma^2}{D}, & 0 < D \le \sigma^2\\[2mm] 0, & D > \sigma^2 \end{cases} \qquad\Longleftrightarrow\qquad D(R) = \sigma^2 2^{-2R}$$

세 가지를 읽어야 한다.

• $D \ge \sigma^2$ 이면 0비트. 왜곡 예산이 분산보다 크면 아무것도 보내지 말고 그냥 평균값(0)을 복원값으로 쓰면 된다. 그때 왜곡이 정확히 $\sigma^2$ 다. 공짜로 얻는 이 구간이 뒤에 나올 역주수의 핵심 부품이다.
• 비트당 6.02 dB. $D(R) = \sigma^2 2^{-2R}$ 이니 1비트마다 왜곡이 4배 줄고, 이것이 양자화 세계의 국룰인 「비트당 6 dB」의 이론적 출처다.
• 가우시안이 최악이다. 분산이 $\sigma^2$ 로 같은 모든 원천 중에서 $R(D)$ 가 가장 큰 것이 가우시안이다. 제곱오차에 대한 섀넌 하한 $R(D) \ge h(X) - \frac{1}{2}\log_2(2\pi e D)$ 에서 미분 엔트로피 $h(X)$ 가 정규분포에서 최대이기 때문이며, 등호도 그때만 성립한다. 실무적 함의가 크다 — 데이터가 가우시안처럼 보이면 그게 압축이 제일 안 되는 경우이고, 반대로 비가우시안성이 곧 압축 여지다.

4. 역주수 — 어느 성분에 비트를 줄 것인가[편집]

성분이 서로 독립이고 분산이 다른 병렬 가우시안 원천 $X_i \sim \mathcal{N}(0,\sigma_i^2)$, $i=1,\dots,n$ 을 총 왜곡 $\sum_i D_i \le D$ 아래 압축한다고 하자. 라그랑주 승수를 붙여 풀면 답이 아름답게 떨어진다.

$$D_i = \min(\theta, \sigma_i^2), \qquad \sum_i D_i = D, \qquad R = \sum_{i:\,\sigma_i^2 > \theta} \frac{1}{2}\log_2 \frac{\sigma_i^2}{\theta}$$

「수위」 $\theta$ 를 하나 정해 놓고,

• 분산이 수위보다 큰 성분($\sigma_i^2 > \theta$)은 왜곡을 정확히 $\theta$ 로 맞춘다. 즉 모든 성분이 같은 왜곡을 갖도록 비트를 배분한다.
• 분산이 수위보다 작은 성분은 비트를 0개 주고 통째로 버린다. 그 성분의 왜곡은 자기 분산 $\sigma_i^2$ 이고, 그게 $\theta$ 보다 작으니 예산 안이다.

채널 용량 쪽의 물 채우기(water-filling)가 「좋은 채널에 전력을 몰아준다」인 데 반해 여기서는 분산이 큰 성분에 비트를 몰아주고 낮은 곳은 물에 잠기게 둔다는 점에서 방향이 뒤집혀 있어 역주수(reverse water-filling)라 부른다.

이 한 문단이 이미지 압축과 오디오 코덱의 설계도 전부다. 신호를 이산 코사인 변환이나 웨이블릿 변환으로 돌리면 에너지가 소수의 저주파 계수에 몰리고 — 이것이 주성분 분석이 하는 일과 같은 탈상관이다 — 나머지 대다수 계수의 분산이 수위 아래로 내려간다. 그 계수들을 0으로 만드는 것이 「고주파를 버린다」의 정체이고, 변환부호화의 부호화 이득은 계수 분산들의 산술평균 대 기하평균의 비로 정확히 계산된다. 분산이 고를수록(=변환이 탈상관에 실패할수록) 이득이 1에 가까워진다.

5. 순정리와 역정리 — 그리고 「블록 길이 무한」의 대가[편집]

정리는 두 방향이다.

• 역정리(converse). 어떤 부호기·복호기 쌍이든 비트율이 $R < R(D)$ 이면 평균 왜곡이 $D$ 이하일 수 없다. 증명은 자료 처리 부등식과 $R(D)$ 의 볼록성 몇 줄이라 놀라울 만큼 짧다.
• 순정리(achievability). 임의의 $R > R(D)$ 와 $\varepsilon > 0$ 에 대해, 블록 길이 $n$ 이 충분히 크면 왜곡 $D+\varepsilon$ 이하를 달성하는 길이 $n$ 부호가 존재한다. 증명은 무작위 부호책 — 최적 시험 채널의 출력 분포에서 코드워드 $2^{nR}$ 개를 무작위로 뽑아 놓고, 입력 블록과 결합 전형적인 코드워드를 찾아 그 인덱스만 보낸다.

순정리의 「존재한다」에 함정이 있다. 증명이 주는 것은 무작위로 뽑은 지수 크기의 부호책이라, 저장도 탐색도 불가능하다. 게다가 성능이 $n \to \infty$ 에서만 보장된다 — 유한 블록에서는 유한 블록 길이 보정항만큼 손해를 본다. 그러니 이 이론이 실제로 하는 일은 코덱을 만들어 주는 것이 아니라 채점 기준을 주는 것이다. “우리 코덱이 이 원천에서 한계 대비 0.3비트 위에 있다”는 문장이 성립하려면 $R(D)$ 를 알아야 한다.

실제 부호기가 그 한계에 얼마나 붙는지는 꽤 잘 알려져 있다. 고비트율 극한에서 엔트로피 부호화를 붙인 균일 스칼라 양자기는 어떤 원천에 대해서도 $R(D)$ 보다 약 0.254비트(= 1.53 dB) 위에 붙는다. 이 간격은 스칼라 셀이 공간을 최적으로 채우지 못해 생기는 순수한 기하학적 손실이고, 차원을 키운 벡터 양자화로만 메울 수 있다. 뒤집어 말하면 변환 + 스칼라 양자화 + 엔트로피 부호화라는 흔한 조합이 이미 이론적 한계의 0.25비트 안쪽이라는 뜻이고, JPEG 계열이 벡터 양자화를 이기고 표준이 된 이유가 여기 있다.

6. RDO — 라그랑주로 내려온 이론[편집]

코덱 안에서 이 이론이 실제로 등장하는 자리는 율-왜곡 최적화(RDO)다. 부호기가 매 순간 마주치는 질문 — 이 블록을 어느 모드로 예측할까, 쿼드트리를 여기서 더 쪼갤까, 이 계수를 0으로 만들까 — 은 전부 「비트를 더 쓰고 왜곡을 줄일까」의 형태다. $R(D)$ 곡선이 볼록이므로 제약 문제를 라그랑주 승수법으로 풀 수 있고, 그러면 결정 규칙이 한 줄로 압축된다.

$$\text{후보 } m^\star = \arg\min_m \; J(m), \qquad J(m) = D(m) + \lambda R(m)$$

여기서 $\lambda$ 는 라그랑주 승수이고, 기하학적으로 동작점에서 R-D 곡선의 기울기의 음수 $\lambda = -\,dD/dR$ 이다. 「비트 하나의 값어치를 왜곡 단위로 환산한 환율」이라고 읽으면 정확하다. $\lambda$ 가 크면 비트가 비싸므로 부호기가 화질을 포기하고, 작으면 비트를 펑펑 쓴다.

$\lambda$ 를 양자화 파라미터와 잇는 관계도 위 이론에서 나온다. 스텝 $\Delta$ 인 균일 양자기의 왜곡이 $D \approx \Delta^2/12$ 이고 고비트율에서 $D \propto 2^{-2R}$ 이므로

$$\lambda \;=\; -\frac{dD}{dR} \;=\; 2\ln 2 \cdot D \;\propto\; \Delta^2$$

즉 $\lambda$ 는 양자화 스텝의 제곱에 비례한다. H.264/HEVC는 QP가 6 늘 때 $\Delta$ 가 2배가 되도록 설계돼 있으므로 $\lambda \propto 2^{QP/3}$ 이고, 참조 소프트웨어가 쓰는 $\lambda = 0.85 \cdot 2^{(QP-12)/3}$ 같은 공식의 지수 $1/3$ 이 정확히 이 유래다. 앞의 계수 0.85는 이론이 아니라 실측으로 맞춘 값이다.²

트리 구조에서는 이 최적화가 특히 잘 풀린다. 쿼드트리 분할처럼 「쪼갤까 말까」가 재귀적으로 중첩된 결정이면, 잎에서 뿌리로 올라오며 $J$ 를 비교하는 동적 계획법 한 번으로 주어진 $\lambda$ 에 대한 전역 최적 분할이 나온다. 같은 논리를 트렐리스 위에서 계수 하나하나에 적용한 것이 비터비 알고리즘 기반의 트렐리스 양자화(TCQ/RDOQ)이며, 「이 계수를 반올림 대신 0으로 죽이면 뒤따르는 런렝스가 짧아져 비트가 더 절약된다」 같은 판단을 정확하게 해 준다.

7. MSE라는 골칫거리[편집]

이론 자체는 왜곡 척도 $d(\cdot,\cdot)$ 에 대해 중립이다. 문제는 닫힌 형태가 나오는 척도가 사실상 제곱오차뿐이고, 그래서 70년 넘게 모두가 MSE를 썼다는 것이다. 그런데 MSE는 사람의 지각과 잘 안 맞는다.

• 이미지를 한 픽셀 평행이동하면 MSE는 폭발하지만 사람은 차이를 못 느낀다.
• 밝은 영역의 오차와 어두운 영역의 같은 크기 오차를 동등하게 센다. 사람 눈은 그렇지 않다.
• 구조적으로 다른 두 열화(흐림 vs. 블록 노이즈)가 같은 MSE를 가질 수 있는데, 보기에는 전혀 다르다.

그래서 SSIM·MS-SSIM·VMAF 같은 지각 척도가 쓰이지만, 이들은 대개 볼록하지도 가법적이지도 않아 $J = D + \lambda R$ 의 깔끔한 구조를 깨뜨린다. 실무의 타협은 「최적화는 MSE(또는 SATD)로 하고 평가만 지각 척도로 한다」거나, 심리시각 모형으로 계산한 가중치를 MSE에 곱하는 것이다. HEVC 이후 코덱의 「심리시각 튜닝」이 대체로 이 가중치 장난이다.

더 근본적인 지적도 있다. 블라우와 미카엘리(2019)는 왜곡을 낮추는 것과 「진짜처럼 보이는 것」이 서로 다른 목표이며 둘 사이에 명시적인 상충이 있음을 보였다 — 복원 분포를 원본 분포와 일치시키라고 요구하면(지각 품질), 같은 비트율에서 왜곡은 반드시 나빠진다. 생성 모형 기반 코덱이 낮은 비트율에서 「원본에 없던 디테일을 지어내며」 보기에는 훨씬 좋은 이유를 이 율-왜곡-지각 삼각형이 설명한다. 신경 압축기가 실질적으로 최적화하는 목적함수도 결국 율(잠재 표현의 엔트로피)과 왜곡의 라그랑주 합이며, 변분 오토인코더의 ELBO를 율과 왜곡의 합으로 읽는 관점도 정확히 여기서 온다.

8. 관련 문서[편집]

• 벡터 양자화 · 곱양자화 · 신경망 양자화 · k-평균 군집화
• 쿨백-라이블러 발산 · 정보 기하 · 상호정보량 · 엔트로피 부호화
• 이산 코사인 변환 · 웨이블릿 변환 · 푸리에 변환 · 주성분 분석 · 특이값 분해
• 라그랑주 승수법 · 볼록 최적화 · 동적 계획법 · 비터비 알고리즘
• 쿼드트리 · 이미지 압축 · 변분 오토인코더

9. Footnotes[편집]

1. Shannon (1948) A Mathematical Theory of Communication 의 후반부, 그리고 Shannon (1959) Coding theorems for a discrete source with a fidelity criterion. 1948년 논문 하나로 무손실 압축·채널 부호화·손실 압축의 세 한계선을 다 그어 놓은 셈인데, 나머지 인류는 그 뒤 70년 동안 그 선에 얼마나 가까이 갈 수 있는지를 실험해 온 것에 가깝다. ↩

2. 계수 0.85가 어디서 왔냐고 물으면 “실험에서 잘 나왔다”가 정직한 답이다. 게다가 이 값은 프레임 종류(I/P/B)와 계층 깊이에 따라 다시 곱해지는 보정 계수들을 줄줄이 달고 다닌다. 이론이 지수를 주고 실측이 앞 계수를 준다는 구도는 이 바닥에서 아주 흔하며, 그 앞 계수를 만지는 것이 코덱 튜닝의 절반이다. ↩