Classic Denoising Techniques : Spatial domain method

들어가며

1편에서 기초적인 배경과 우리가 다루어야 할 대상들에 대해 알아보았으니 본격적으로 디노이징 방법들에 대해 알아보기로 하자.

먼저 딥러닝 이전에 과거에는 신호처리(Signal processing) 혹은 컴퓨터 비전(Computer vision)이라는 분야에서 이와 관련된 연구를 진행하여 다양한 기법들이 제시되었다. 여기서 나온 노이즈를 제거하는 전통적인 기법에 대해 살펴보도록 하자. 바로 최신 기법을 살펴보는 것도 좋겠지만 전반적인 발전 과정을 거쳤는지 알아보는게 인사이트를 얻는데 분명 도움이 될 것이다. 크게 Spatial domain method와 Transformation method로 구분할 수 있는데 이번 2편에선 Spatial domain method를 다루도록 하자.

먼저 노이즈가 낀 이미지가 한 장 주어졌다고 하자. 이때 우린 무엇을 할 수 있을까? 앞서서 이미지에 대한 사전지식을 이야기했는데 주변부 픽셀과 유사한 값을 지닐 것이라는 기대를 하였다. 그렇다면 특정 픽셀이 있을 때 이것의 주변 픽셀값을 어떻게 조합하면 노이즈를 억제시킬 수 있지 않을까?

이 아이디어를 위한 기초적인 방법은 필터라는 것을 이미지에 적용하는 것이다. 이를 이미지의 너비, 높이라는 공간에 적용되기 때문에 공간적 영역(spatial domain)에서 필터링한다고 말한다. 다음 그림과 같이 소스 픽셀에 각 필터(커널)마다 값을 곱해주고 총 합을 더해주어 새로운 값을 찾아낸다.

Convolution, https://aryamansharda.medium.com/image-filters-gaussian-blur-eb36db6781b1

2-1. Gaussian Filtering

주변부 값을 이용한다는 우리의 직관을 평균이라는 수식으로 표현할 수 있을 것이고 다음과 같은 필터를 고안할 수 있을 것이다.

이를 average filter라고 부르는데 이렇게 필터가 인풋으로 사용하는 픽셀정보에 대한 linear function으로 작용하는 형태를 linear filter라고 부른다.

Average filter, https://datahacker.rs/opencv-average-and-gaussian-filter

그런데 문제는 가장자리 정보를 blur 시킨다는 것이다. 앞서서 우리는 성공적인 디노이징을 위해선 blur 효과가 생겨선 안된다고 하였으므로 average filter는 성공적인 필터가 아니다. 따라서 이를 개선할 필요가 있다.

Using a 3×3 kernel (on the left image) and a 7×7 kernel (on the right image)

문제가 무엇이었을까?

주변부 픽셀정보를 활용하는데 우리는 너무 멀리 떨어진 픽셀정보까지 같이 이용하였다. 즉, 특정 픽셀에 가까이 있는 정보와 멀리 있는 정보를 동등하게 대우를 하였는데 이 부분을 개선할 수 있을 것이다. 이를 가우시안 함수 형태로 거리가 멀어질수록 가중치값을 낮추고 근방 정보에 많은 가중치를 주어 가중평균을 계산하도록 하자.

h(u,v) =122(-u2+v222)

https://datahacker.rs/opencv-average-and-gaussian-filter/ 2-d visualization of a Gaussian function

이런 가우시안 필터를 적용한 식을 표현하면 다음과 같다.

이미지내의 특정 위치 p의 디노이징 후 추정값은 다음과 같이 p 주변 값의 집합 에 있는 q들에 대해서 다음과 같은 지수를 곱해준다. 이때 p와 q가 가깝다면 지수값이 1이 되어 q의 위치에 있는 픽셀값을 그대로 반영한다. 반면에 차이가 크면 지수가 0으로 가기 때문에 아주 작은 값만 반영하게 되는 것이다. Cp는 normalization term이다.

두 번째 식은 사실 첫번째 식과 같은 식이지만 표현을 다르게 했을 뿐이다.

가우시안 필터가 적용된 이미지의 p 위치는 G()이라는 가중치가 곱해져서 더해진다고 볼 수 있다. 앞서 본 차량 이미지에 가우시안 필터를 사용하면 average filter에 비해선 좀 더 선명한 이미지를 얻을 수 있다. 문제는 여전히 blurring이 심하다는 부작용때문에 디노이징 알고리즘으로 직접 사용하기 힘들다.

https://datahacker.rs/opencv-average-and-gaussian-filter/

실제 노이즈가 있는 이미지에 가우시안 필터를 적용한 결과는 다음과 같다. 노이즈가 줄어들긴 했으나 전반적으로 이미지가 흐릿해진 것을 볼 수 있다.

Sampling and Reconstruction, Steve Marschner, https://slidetodoc.com/sampling-and-reconstruction-many-slides-from-steve-marschner-3/

2-2. Bilateral filter

어떻게 개선할 수 있을까?

가우시안 필터는 일괄적으로 똑같은 필터를 이미지 픽셀마다 적용시킨다. 이 때문에 가장자리를 기준으로 전혀 다른 semantic이 있을 경우 원하지 않는 정보를 섞이게 한다. 다음과 같이 각각 패치마다 일괄적인 필터가 곱해지는 것이다.

Blur Comes from Averaging across Edges Blur Comes from Averaging across Edges

이미지 컨텐츠에 맞춰서 가장자리를는 smooth 시키지 않는 방법을 고안했는데 이것이 bilateral filter이다.

다음 그림처럼 각각 컨텐츠에 맞춰서 필터가 바뀌는데 특히 두번째 패치의 경우 경계가 있는 부분은 아예 다른쪽 값들이 영향을 미치지 않게끔 0으로 처리되었다.

The kernel shape depends on the image content,

bilateral filter를 식으로 표현하면 다음과 같다.

수식을 보면 알수 있듯이 가우시안 필터에 새로운 term이 하나 추가되었을 뿐이다.

기존의 가우시안 필터의 Gs를 space weight term, Gr을 range weight term이라고 부른다.

range weight term의 역할을 살펴보면 즉 intensity의 값의 차이가 크다면 가중치가 0에 가까워서 해당 픽셀을 반영하지 않는 결과를 줄 수 있다. 그래서 위의 그림에서 두 번째 패치를 보면 빨간색 점이 p인데 여기와 다른 검은색 영역을 반영하지 않는 것이다.

https://people.csail.mit.edu/sparis/bf_course/slides08/03_definition_bf.pdf

이와 더불어 두 개의 파라미터 r , s에의해 컨트롤 할 수 있다. r이 커진다면 range term이 활약을 못하기 때문에 가우시안 필터에 가까워 질것이다. s를 키운다면 더 넓은 영역을 이용해 필터링할 수 있다.

결과를 보면 다음과 같이 경계부분은 대체로 성공적으로 보존하였다.

Left: original image. Right: image processed with bilateral filter https://en.wikipedia.org/wiki/Bilateral_filter#/media/File:Bilateral_Filter.jpg

https://scikit-image.org/docs/0.8.0/auto_examples/plot_denoise.html

보다 자세히 알고싶다면 다음 강의자료(Sylvain Paris et al.)를 참조하도록 하자.

2-3. Non-local Means

• • Paper : A non-local algorithm for image denoising, Baudeset al. (2005), https://www.researchgate.net/publication/4156453_A_non-local_algorithm_for_image_denoising
  • Code : https://github.com/praveenVnktsh/Non-Local-Means

개선한 필터들을 고안하긴 했지만 여전히 edge나 texture같은 high frequency 정보를 보존하는데에는 역부족이다. 주변부에 있는 픽셀이 반드시 같은 statistics를 공유한다는 보장이 없기 때문에 다른 statistics를 가진 픽셀을 믹싱할 경우 blur되는 현상이 일어난다. 이는 좀 더 스마트하게 localization을 하는게 필요하다는 것을 뜻한다.

앞서서 문제 정의를 할때 우리는 이미지를 clean latent image x와 노이즈 n의 합으로 표현하였다. 영상이 아닌 경우 우리가 얻고자하는 x는 시간이 지나도 변화하지 않는다고 할 수 있다. 즉 상수이다. noise는 zero-mean gaussian이라고 했을 경우 촬영할때 마다 다른 noise instance가 realization이 된다.

이때 활용할 수 있는 통계법칙은 The law of large number이다. 샘플이 iid이고 같은 분포에서 온 것이라고 한다면 샘플의 갯수가 커질수록 sample mean이 true mean으로 수렴한다. 즉 여러장의 이미지를 다 더해 평균을 낸다면 n 0가 되어 y x가 됨을 뜻한다.

Temporal Denoising, https://shaharkov.github.io/projects/TutorialDenoising/ATCV_Denoise_Publish.pdf

그런데 이미지의 특성을 잘 살펴보면 비슷한 형태의 영역을 나타내는 부분이 단순히 주변부 뿐만 아니라 더 멀리 떨어진 영역에서도 나타날 수 있다.

Redundancy in natural images, https://shaharkov.github.io/projects/TutorialDenoising/ATCV_Denoise_Publish.pdf

여러 시간에 걸쳐 이미지를 확보하기 보단 한 장의 이미지에 있는 같은 statistics를 가지는 작은 단위의 패치(patch)들을 모아서 평균을 내는 것을 고려해 볼 수 있을 것이다.

Single image “time-like” denoising

하지만 엄밀하게 따지면 각 패치들이 정확히 같은 것은 아니므로 단순 평균은 제대로 동작하지 않을 것이다. 앞서 우리는 가중치라는 개념을 도입하였는데 이번에는 각 패치들의 유사도를 따져서 가중치를 도입할 수 있을 것이다.

예를 들어 다음 lena 이미지에서 p를 중심으로 하는 이미지 패치는 q_1, q_2와 유사도를 지닌다. 따라서 이 영역의 정보를 활용하는 것이다. 반면 q_3을 중심으로 한 이미지 패치는 유사도가 떨어지므로 여기에는 가중치를 적게 부여한다.

https://towardsdatascience.com/gcnet-non-local-network-meets-squeeze-excitation-network-and-beyond-review-f3f3e4035e4d

이런 과정을 수식으로 표현하면 다음과 같다.

p, q는 이미지내의 점을 표현하고, B(p), B(q)는 각각 p, q를 중심으로 한 패치를 뜻한다. d는 어떤 Euclidean distance를 뜻하고 패치간의 유사도를 측정한다고 할 수 있다. f는 weighting function이자 decreasing function인데 패치간의 차이가 클수록 낮은 가중치를 부여할 수 있게끔 한다. C(p)는 normalizing factor이다.

weighting function으로 대표적으로 gaussian weighting function을 사용하는데 평균이 p를 중심으로 한 패치이고 h는 filtering parameter이다.

이러한 NLM 기법은 아무래도 이용하는 정보의 양이 많은 덕분에 일반적인 local filter를 사용하는 것보다 성능이 좋지만 계산량이 늘어나서 상대적으로 속도가 느리다.

Denoising experience on a natural image. From left to right and from top to bottom: noisy image (standard deviation 20), Gauss filtering, anisotropic filtering, Total variation, Neighborhood filtering and NL-means algorithm. The removed details must be compared with the method noise experience, A non-local algorithm for image denoising, Baudeset al. (2005)

Mean square error table. A smaller mean square error indicates that the estimate is closer to the original image, A non-local algorithm for image denoising, Baudeset al. (2005)

2-4. Variational denoising method

• • Paper : Nonlinear total variation based noise removal algorithms, Leonid I. Rudin, https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.1675

  • Code : https://www.youtube.com/watch?v=G39dVoiivZk

  • Reference : https://www.edwith.org/optimization2017/lecture/10558?isDesc=false

지금까지 직접 이미지에 필터를 적용하여 디노이징을 하고 그 결과를 판단하여 더 나은 필터를 고안하였다. 이 과정을 되새겨 보자면 우리는 implicitly하게 이미지는 어떻게 되어야 한다는 우리의 지식이 반영하여 필터를 고안한 것이다. 또한 MSE라는 지표를 이용하여 우리가 찾은 해가 적합한지를 보며 더 나은 아이디어를 제안한 것이다.

이런 과정을 보다 엄밀하고 수학적으로 모델링할 수는 없을까? 그리고 그렇게 하여 모델로 나온 수식을 풀어내어 해를 구하는 방법이 있지 않을까? 이를 위해 우리는 variational approach 도입할 수 있다.

지금까지 한 방법을 statstical inference관점에서 다시 살펴 볼 수 있다. 디노이징 모델은 다음과 에너지를 낮게 하는 에너지 함수 E(x)를 이용해서 이 값을 제일 낮추는 x를 찾는다고 할 수 있다. 다시말해 y가주어졌을 때 에너지를 낮추어주는 x를 찾는 문제로 프레이밍할 수 있다.

왜 에너지 함수를 최소화시켜야 하는지 문제는 사실 더 이전의 확률론에서 풀려던 문제에서 기원한다. variational denoising의 동기는 MAP(maximum a posterior)에서 유도되는데 MAP estimates로 x를 표현하게 되면 다음과 같다.

이때 p(x|y)는 노이즈가 낀 y라는 이미지에서 클린 이미지 x를 얻을 확률이다. 지금까지 우리의 목적이 노이즈 이미지 y를 보았을때 클린 이미지 x를 찾고자 했던것을 확률적으로 모델링했다고 생각할 수 있다. 이를 bayes formula로 풀어서 만든 확률식을 최대화 하는 x를 찾는 것을 MAP estimation이라고 한다. 이때 p(y|x)를 likelihood, p(x)를 prior이라고 부른다.

p(x|y)를 찾는것 보단 p(y|x)를 찾는게 훨씬 쉽다. 왜냐하면 클린 이미지에서 노이즈 이미지를 얻는 것은 가우시안으로 모델링할 수 있기 때문이다. 또한, prior knowledge란 클린 이미지면 이렇게 해야된다라는 기존의 우리가 알고 있는 지식을 넣어준다고 할 수 있다. 예를 들어 픽셀간의 intensity나 컬러값의 차이가 작다라는 smootheness prior를 넣어줄 수 있다.

이를 수학적으로 모델링하면 다음과 같다.

노이즈 이미지가 주어졌을 때 기본적으로 클린 이미지와 구조적인 특성이 너무 멀리 떨어지면 안될 것이고 또한 클린이미지 자체는 부드러운 형태를 띌 것이다.

즉 우리가 앞에서 했던 가정들이 수학적으로 표현한 것이다. 두 식의 지수부분을 전통적으로 에너지함수라고 하는데 이걸 최소화시키는 것은 전체 estimation을 최대화하는 것과 동일하다. 이때 p(y|x)가 제일 처음에 본 에너지 함수에서 D(x,y)의 역할(fidelity term)을 하고 p(x)가 $R(x)$의 역할(regularization term)을 한다. 이렇게 보면 지금까지 smoothness prior을 필터를 디자인하면서 implicitly하게 주입했음을 알 수 있다.

likelihood와 piror의 곱을 우리가 최대화하는데 결국 지수부분을 최소화하는 것과 같으므로 우리가 처음에 본 에너지함수 식으로 전개할 수 있게 된다.

만약 오른쪽에 있는 MSE term만 존재했다면 결과물 x가 노이즈 이미지 y와 똑같이 나올테지만 왼쪽에 있는 prior knowledge가 주변 픽셀간의 차이가 적어야 한다는 regularization으로 작용하여 y와 내용물은 비슷하면서도 노이즈가 없는 이미지를 찾는걸 기대해볼 수 있다.

디노이징은 대표적인 inverse problem이다. 관측된 노이지 이미지에서 클린 이미지를 찾아내야 하기 때문이다.

이때 inverse problem은 종종 해가 유일하지 않은 ill-posed problem인데 디노이징 뿐만 아니라 많은 컴퓨터비전 문제들이 그러하다. 영어 속담 중 “It’s no use crying over spilt milk”라는 말이 있다. 이미 엎질러진 우유는 다시 주워담기 힘들기 때문에 울어도 소용없다는 뜻인데 이처럼 노이즈가 있는 영상에서 원본 영상을 찾기가 쉬운 것은 아니다. 하지만 variational approach는 ill-posed problem을 풀기에 매우 적합한 프레임워크를 제안하기 때문에 큰 인기를 끄는 방법론이 되었다.

https://www.123rf.com/photo_146498135_stock-vector-english-idiom-with-picture-description-for-dont-cry-over-spilt-milk-on-white-background-illustration.html

참고로 variational이라는 뜻은 우리가 변수를 변화시키면서 최적값을 찾는게 아니라 함수를 바꾸어가면서 목표를 향해 가기 때문에 variational이라고 이름 붙였다.

디노이징의 대상이 되는 이미지가 함수이므로 functional에 대한 최적화라고 할 수 있다.

이런 variational approach를 도입해서 처음으로 등장한 것은 1980년대에 MIT lab에서 나온 Tikhonov regularization이다.

문제는 주변부까지 blurring되는 부작용이 발생하였다. 이후 이런 점을 개선하여 1992년에 Total variation(TV) regularization이 등장하게 되었다. 차이점은 R을 다음과 같이 RTV(x) = ||x||1로 바꾸어준 것이다.

주변부와 값이 비슷하다는 smoothness prior에 제곱을 있던 것을 삭제하였는데 gradient 절대값의 합을 total variation이라고 부른다.

과도한 디테일이 있는 signal의 경우 높은 total variation을 가지는데 이를 낮추면 edge같은 중요한 정보는 보존하면서 불필요한 디테일을 줄일 수 있다.

Total variation denoising technique to an image corrupted by Gaussian noise, https://en.wikipedia.org/wiki/Total_variation_denoising

왜 Tiknov보다 TV regularization이 더 엣지를 많이 살리는지는 알아보자. 먼저 예시를 통해 살펴보면 다음과 같이 4개의 픽셀값이 있는 1차원 signal이 있다고 하자.

1D signal example, 영상이해를 위한 최적화 기법, 김창익영상이해를 위한 최적화 기법

이때 Tikhonov는 |x|2을 계산하면 왼쪽 값이 300이고 오른쪽 값이 900이다. 즉 왼쪽이 더 낮은 값이므로 부드러운 형태의 이미지를 더 선호하게 된다.

반면에 TV는 |x|를 계산하면 왼쪽값과 오른쪽 둘 다 30이다. 즉 두 형태 중 특별히 더 선호하는 것 없이 원본에 좀 더 가깝게 최적화가 이루어지기 때문에 구조를 보존하면서 디노이징이 이루어질 수 있는 것이다.

이렇게 우리는 x라는 이미지를 이리저리 바꾸어가며 에너지함수의 최소값을 찾아야한다는 목적에 맞추려고 할때 어떻게 x를 바꾸어야 할까?

실제 x를 찾을 때에는 최적화 기법을 사용하게 된다. 최적화 방법에는 여러가지 방법 사용가능한데 초기에는 calculus of variation을 사용하여 풀었다. 이후 ADMM(alternating direction method of multipliers) 같은 최적화 기법들을 사용하였다.

가장자리 정보 보존에 굉장한 성공을 거두었지만 flat regions에서 staircase effect를 일으켰다. 다음 그림처럼 디노이징이후 계단처럼 값들이 변화하는 현상을 보인다.

또한 contrast 정보의 손실을 일으켰다. 이후 조금씩 더 개선하면서 TV-L1, WLS, RTV 등 variational approach를 활용한 디노이징 기법들이 많이 등장하였다.

staircase effect, Image restoration with a high-order total variation minimization method, Xiao-Guang Lv et al.,https://www.sciencedirect.com/science/article/pii/S0307904X13001832

Loss of contrast in restorations from TV model, Edge and contrast preserving in total variation image denoising, Liming Tang et al.

마치며 

이렇게 전통적인 방법론에서 가장 처음으로 등장한 Spatial Method에 대해 알아보았다.

처음에는 국소적인 정보를 활용하였고 이후 전역적인 정보를 활용하는 식으로 발전하다가 Variational Inference라는 statistaical inference 프레임워크까지 나오게 되었다. Pixel 공간에 직접 작용하는 알고리즘들이라 직관적이긴 하나 현재 기준에선 성능이 그다지 만족스럽다고 볼 수는 없어보인다.

그렇다면 어떻게 해야할까?

문제를 해결하는 방법은 여러가지가 있으나 한 방법은 우리가 관심을 가지는 대상에 대해 표현을 다르게 하는 것이다. 따라서 다음편에선 전통적 방법론 중 또 다른 부류인 Transformation Method에 대해서 알아보기로 한다.