이미지 노이즈 제거 알고리즘 - TV method(3)

 

 

 

이 글에서는 실제 코드로 구현하는 방법에 대해 알아본다. 우리가 해결해야 할 방정식은 (복습하자면)

 

$u - f - \lambda \nabla \cdot \left( \dfrac{\nabla u}{|\nabla u|} \right) = 0$

 

이다.

 

1. 이산화(Discretization)

TV를 코드로 구현하려면 유한차분법(Finite Difference Method)를 써야한다. 정의역(=이미지의 점들의 좌표)을 $\{ (x_i, y_j | 1 \leq i,j \leq n \}$이라 하면 복원된 이미지와 원래 이미지의 각 점에서의 값(=색)은

 

$u_{i,j} = u(x_i, y_j)$

$f_{i,j} = f(x_i,y_j)$

 

이고 $x, y$방향의 미분계수는

 

$\dfrac{\partial u}{\partial x}(x_i, y_j) = u_{i+1, j} - u_{i,j}$

$\dfrac{\partial u}{\partial y}(x_i, y_j) = u_{i, j+1} - u_{i,j}$

 

이다. 실제 코드 구현시, 분모 $|\nabla u|$가 $0$이 될 수 있으므로 아주 작은 양수 $\epsilon$를 더해서 오류를 회피하여야 한다. 즉, 

 

$u - f - \lambda \nabla \cdot \left( \dfrac{\nabla u}{|\nabla u| + \epsilon} \right) = 0$

 

 

2. 경사하강법(Gradient Descent)

사실 Euler-Lagrange 방정식을 풀 수는 없어서 원래의 에너지 함수를 이용해서 경사 하강법(Gradient Descent)으로 조금씩 업데이트하자. 즉,

 

$u^{n+1} = u^n - \Delta t \nabla E$

 

를 계산해야 한다.

 

$u^{new} = u^{old} - \Delta t \left( \underbrace{u^{old} - f}_{\text{데이터 유지}} - \lambda \underbrace{\text{div}\left(\frac{\nabla u^{old}}{|\nabla u^{old}|}\right)}_{\text{평탄화}} \right)$

 

이산화한 것을 이용해 계산하면,

(1) 2차원에서의 에너지 기울기

2차원 이미지 $u_{i,j}$에서 우리가 계산해야 할 핵심 항은 $\text{div}\left(\frac{\nabla u}{|\nabla u|}\right)$입니다. 분모에 들어갈 기울기의 크기(L2 norm)를 먼저 정의자 :

 

$W_{i,j} = \sqrt{(u_{i+1,j} - u_{i,j})^2 + (u_{i,j+1}-u_{i,j})^2 + \epsilon}$

 

(2) 업데이트 수식

경사하강법 스텝을 밟으면, 각 픽셀 $u_{i,j}$는 다음과 같이 갱신된다:

 

$ u_{i,j}^{n+1} = u_{i,j}^{n} - \Delta t \left[ (u_{i,j}^{n} - f_{i,j}) - \lambda \cdot \operatorname{Div}_{i,j} \right] $

 

여기서 $\operatorname{Div}_{i,j}$는 다음과 같은 4개 방향의 조합으로 이루어진다.

 

$\text{Div}_{i,j} = \underbrace{\dfrac{u_{i+1,j} - u_{i,j}}{W_{i,j}} - \dfrac{u_{i,j} - u_{i-1,j}}{W_{i-1,j}}}_{\text{x-direction flow}} + \underbrace{\dfrac{u_{i,j+1} - u_{i,j}}{W_{i,j}} - \dfrac{u_{i,j} - u_{i,j-1}}{W_{i,j-1}}}_{\text{y-direction flow}}$

 

 

3. 초기 값 $u^0$는 무엇으로?

(1) 가장 일반적인 방법 - 원본 이미지 ($u^0 = f$)

이유: 우리가 찾으려는 정답 $u$는 결국 $f$에서 노이즈만 살짝 깎아낸 형태. 즉, $f$는 정답 $u$에서 가장 가까운 '지점'

장점: 반복 횟수(Iteration)를 획기적으로 줄여준다. 멀리서 시작할 필요 없이 정답 근처에서 다듬기만 하면 되므로

(2) 안전한 방법 - 제로 이미지 ($u^0 = 0$)

수치 해석적 안정성을 극도로 중시할 때 사용한다.

 

이유: 간혹 알고리즘이 발산할 위험이 있거나, 수식의 거동을 깨끗하게 확인하고 싶을 때 모든 픽셀을 0(검은색)으로 채우고 시작

장점: 초기 상태가 매우 깨끗하므로 알고리즘의 에너지 감소 과정을 모니터링하기 좋다. 하지만 $u^0 = f$에 비해 수렴 속도가 느리다.

(3) 영리한 방법 - 가우시안 블러 ($u^0 = G * f$)

이미지에 아주 가벼운 가우시안 블러를 한 번 먹인 뒤 시작하는 경우도 있다.

 

이유: 앞서 말한 $L^2$ 기반의 평탄화를 살짝 미리 해두는 것.

장점: 자잘한 고주파 노이즈를 미리 어느 정도 죽여놓고 TV(L1) 연산을 시작하므로, 수치적으로 훨씬 부드럽게 수렴하는 경향있다.

 

4. 하지만..

위 방법대로 정직하게 계산하면 수렴이 굉장히 느리다. 특히 $\left| \nabla u \right|$가 수치해석을 어렵게 만든다. 그래서 이 부분을 해결하기 전까지 TV는 잘 쓰이지 않았다. 그런데 이 부분을 Primal-Dual이라는 방법으로 멋지게 해결해 내어 지금의 TV가 되었다.