Classic Denoising Techniques : Transformation method

들어가며

지금까지 우리가 직접 눈으로 볼 수 있는 이미지에 대해 직접적으로 계산을 적용하였다. 문제를 해결하는 방법은 여러가지가 있지만 한 가지 방법으로 transformation이 있다.

이는 관심을 가지는 대상을 다른 도메인으로 매핑시켜서 이 도메인 상에서의 표현을 분석하여 다시 원본에 결부된 문제를 해결하는 것이다. 

이런 방법은 공학 문제를 해결하고자 할 때 흔히 쓰이는 전략이다. 예를 들어 쾨니히스베르크 다리 문제는 아마 한번쯤 접해보았을 것이다.

오일러는 이 문제를 그래프로 지도와 다리를 매핑시켰다. 이것 또한 Transformation의 일종으로 볼 수 있을 것이다. 즉 다른 표현으로 접근한다면 문제 해결에 도움이 되는 것을 직관적으로 알 수 있다.

쾨니히스베르크 다리 문제, https://www.mathpark.com/312

이처럼 우리는 노이즈를 제거하는 문제를 풀기 위해서 이미지를  다른 도메인으로 보내고 거기서 어떤 연산을 하여 솔루션을 찾을 수 있지 않을까?

By transforming the original space (left) into a space of increased dimension (right) the two classes to make them more linearly separable, https://www.researchgate.net/publication/305284381_Non-linear_distance_based_large_scale_data_classifications

현재 이미지 자체의 spatial domain에선 우리에게 불필요한 노이즈와 우리가 보존하고자하는 시그널이 마구 뒤섞여서 있다.

위의 그림처럼 노이즈와 시그널을 분명하게 구별할 수 있는 다른 도메인으로 관측된 이미지 y를 보낸다면 큰 도움이 될 수 있을 것이다.

실제로 연구자들이 관측한 사실 중 하나는 이미지 정보와 노이즈의 특성이 변환된 도메인에선 다르게 나타난다는 것이다.

3-1. Wavelet transforms

데이터사이언스에 사용되는 대표적인 transformation에는 Fourier Transform이 있다. basis function으로 sine, cosine같은 여러개의 sinusoidal wave로 signal을 표현할 수 있다.

하지만 이미지에 경계부근이나 고주파영역의 텍스쳐일 경우 주기적으로 진동하는 sinusoidal wave로만 표현하기는 현실적이지 않다.

wavelet transform은 sinusoidal wave대신에 wavelet이라는 것을 basis function으로 사용한다. wavelet은 zero-mean을 가지는 wave로써 급격히 decay가 일어난다.

무한히 주기적으로 반복되는 sinusoidal wave와는 다르게 한정된 영역에서만 나타난다. wavelet은 다양한 basis function을 가지고 있고 그 중 하나를 선택해서 mother wavelet이라고 정한다.

선택된 mother wavelet에 scaling과 shift 연산을 사용하여 추가적인 wavelet을 만들어 낸다.

Wavelet Decomposition, https://shaharkov.github.io/projects/TutorialDenoising/ATCV_Denoise_Publish.pdf

위의 그림에서 왼쪽 파란색 관측 데이터가 있다고 할때 이를 여러가지 wavelet들의 합으로 decomposition할 수 있다.

전체 과정은 다음과 같다. 노이즈가 낀 관측 이미지(y)를 먼저 wavelet transform을 하여 wavelet decomposition을 하도록 한다.

wavelet decomposition, https://youtu.be/F7Lg-nFYooU

여기서 갈색과 파란색 박스에 각각 D, A라고 명시되어 있다. 이는 Detail과 Approximation을 뜻한다.

high pass filter를 거치면 고주파 성분을 잡아내므로 여기에서 나온 계수들을 detail이라고 하고 이후 low pass filter를 거쳐 저주파 성분을 잡아낸 것을 원본 시그널의 근사치로 볼 수 있으므로 approximation이라고 한다.

다음 단계에선 wavelet scale을 높혀서 다시 한번 이 과정을 반복해서 계속 해서 고주파 성분과 저주파 성분을 분리할 수 있다.

노이즈는 대체로 고주파 성분을 띄고 있다. 따라서 부분에 threshold를 적용하여 frequency를 cut-off 한다.

예를 들어 Quantil thresholding Method는 Cutoff frequency를 wavelet coefficient 의 약 30% 정도로 하고 있다. 그런 뒤 Inverse transformation을 하여 원래 이미지로 돌린다.

전체 과정을 다음과 같이 요약할 수 있다.

Block diagram of wavelet denoising technique, https://medium.com/@koushikc2000/2d-discrete-wavelet-transformation-and-its-applications-in-digital-image-processing-using-matlab-1f5c68672de3

https://www.mathworks.com/help/wavelet/ug/wavelet-denoising.html

이 기법에서 나온 성능이 뛰어난 방법은 BLS-GSM-Wavelet Denoising(J. Portilla et al)이다. 결과를 보면 아래와 같이 왼쪽 위는 원본이고 오른쪽이 노이즈를 가한 이미지이다.

왼쪽 아래는 adaptive local Wiener라는 방법을 사용한 것이고 오른쪽 아래가 BLS-GSM를 적용한 결과이다.

Comparison of denoising results, Image Denoising Using Scale Mixtures of Gaussians in the Wavelet Domain, J. Portilla et al

wavelet transformation을 이용해 성공적으로 이미지 특징을 보존하고 노이즈를 제거할 수 있었다. 하지만 단점은 wavelet basis를 어떤 것을 선택할지 결정해야하는 문제점이 있다.

이미지마다 적합한 basis가 다를 수 있는데 부적합한 wavelet이면 디노이징이 성공적이지 못할 것이다. 또한 wavelet은 만약 노이즈가 아니더라도 고주파 성분이 있으면 이를 잘라내버리기 때문에 정보손실이 있을 수 밖에 없다.

3-2. Sparse representation : Dictionary learning

wavelet이 도메인을 바꾸어서 문제를 해결할 수 있을지 모른다는 실마리를 제공해주긴 하였으나 개별적인 이미지마다 최적화된 wavelet자체를 고안하기란 쉽지 않다.

관점을 데이터자체로 잠시 되돌아 보도록 하자. 이전에 NLM처럼 이미지에 있는 패치를 직접 활용하는 것을 생각해보면 이는 데이터를 활용한다고 볼 수 있다. 이걸 좀 더 확장해서 데이터 기반의 접근을 시도해볼 수 있지 않을까?

Sparse dictionary learning을 통해서 한 이미지를 어떤 구성성분 단위로 표현하는 방법을 학습하도록 한다.

이를 위해 dictionary라는 개념을 도입한다. dictionary는 구체적으로 행렬 형태로 표현한다. 그러면 이미지를 dictionary 행렬의 몇 개의 column을 linear combination한 것으로 표현할 수 있다.

이렇게 몇 개의 구성성분만을 통해 데이터를 표현하는 것을 sparse representation이라고 한다. 이는 마치 원소주기율표상에 세상의 모든 물질을 구성하는 원자들을 표시하고 적절히 조합하여 분자를 만드는 것과 유사하다고 할 수 있다.

Periodic Table of Elements, https://pubchem.ncbi.nlm.nih.gov/periodic-table/

실제로 자연 이미지(natural image)는 몇 개의 기본적인 feature만을 linear combination을 해서 표현할 수 있다고 한다.

dictionary에서 각각의 column이 기본적인 feature역할을 하는 것이다. 이런 dictionary를 찾는 과정을 최적화식으로 쓰면 다음과 같다.

xi는 이미지를 뜻하고 D는 dictionary이다. k개의 이미지를 활용하여 이들을 가장 잘 표현하는 dictionary를 찾는 것이고 sparsity를 강제화하기 위해 l0norm을 사용하였다.

이런 dictionary 행렬을 찾을 수 있는 알고리즘 중 대표적인 것이 K-SVD이다. 이를 통해 효율적으로 이미지를 표현가능하다.

앞에서 본 wavelet 기법처럼 노이즈가 있다고 판단되는 feature를 사용하지 않도록 해당 column을 0으로 하는식으로 디노이징을 하는 것이다.

Michael Elad et al.은 이러한 dictionary learning 프레임워크를 기반으로 디노이징하는 방법은 제안하였다.

그들은 디노이징 과정을 MAP estimator형태로 표현하여 정리하면 다음과 같이 나타내면 앞에서 본 variational approach에서 보았던 식과 유사한 표현을 얻을 수 있다.

이때 Ri는 i번째 위치의 픽셀에서 패치를 얻어내는 연산자이고 는 이미지 패치 Rix에 대한 sparse coding i를 모은 것이다. 첫번째 term은 x가 y와 일관된 semantic을 가지도록 하는 fidelity term으로 볼 수 있다. 이 식에 대한 해는 noncovex라는 문제점때문에 그들은 세 단계의 interation을 거치도록 하였다.

1. sparse coding
2. dictionary update
3. estimation of x 

1,2 단계는 K-SVD와 마찬가지이고 세번째를 다음과 같이 클린이미지의 추정값을 얻게 된다.

K-SVD를 사용하여 100,000개의 8x8 이미지패치에 대한 학습한 globally trained dictionary는 다음과 같다. 다음에 나오는 3장의 이미지는 이런 dictionary에 있는 feature들을 조합해서 실제로 만들어낼 수 있는 이미지들이다. 

Globally trained dictionary

Sample from the images used for training the global dictionar 

본격적인 디노이징 작업에 이용한 결과는 다음과 같은데 확실히 이전 방법보다 시각적으로 더 깔끔해 보일 뿐만 아니라 PSNR을 계산한 표를 보더라도 성능이 좋게 나온다.

표의 4칸중 왼쪽 위는 앞서 살펴보면 BLS-GSM기법이고 오른쪽 위는 DCT(discrete-cosine transform), 왼쪽 아래는 global trained dictionary-denoising, 오른쪽 아래는 노이즈 이미지에 직접 학습시켜 얻은 adaptive dictionary-denosing이다.

Example of the denoising results for the image “Barbara”, Denoising Via Sparse and Redundant Representations Over Learned Dictionaries.

summary of the denoising psnr results in decibels.

정리해서 말하면 wavelet과 비교했을 때 dictionary learning은 basis가 되는 feature들이 이미지에 더 적합하게 학습되어지기 때문에 일일이 wavelet을 고안하지 않아도 된다.

또한 노이즈와 시그널을 더욱 명확하게 구분지을 수 있어 정보손실능 줄여줄 수 있다.

보다 상세한 내용을 알고 싶다면 Michael Elad et al.을 참고하도록 하자.

3-3. BM3D

Paper: Image denoising by sparse 3D transform-domain collaborative ltering, Kostadin Dabov et al. https://webpages.tuni.fi/foi/GCF-BM3D/BM3D_TIP_2007.pdf
Code: https://github.com/legendzhangn/blog/tree/master/color_bm3d 

2007년에 발표된 BM3D(Block Matching 3D collaborative filtering)는 Spatial method와 transformation method의 아이디어를 모두 채택한 방법이다.

Spatial method에선 비슷한 패치를 모아서 활영하는 NLM이 좋은 성능을 보였고 transformation method에선 변환을 통해 sparse representation를 얻음으로써 단순히 linear averaging filter보다 좋은 성능을 보였다.

만약 두 아이디어를 모두 사용하면 어떨까?

BM3D는 이름은 Block matching과 3D collaborative filtering의 합성어로 두 가지 기술 이름이 합쳐진 것이다. 크게 다음과 같은 3가지 과정으로 이루어져 있다.

1. 먼저 비슷한 local structure를 가지는 패치를 그룹화한다. (BM) 

2. 각 그룹별로 일괄적인 디노이징을 적용한다. (3D) 

3. 여러개의 estimates를 smart fusion한다. (Fusion or Aggregation)
  

A Single BM3D Estimate, https://shaharkov.github.io/projects/TutorialDenoising/ATCV_Denoise_Publish.pdf

먼저 Block matching에 대해서 알아보자. Block matching을 통해  유사한 패치들을 모아서 weight로 쓰는게 아니라 모아서 그룹을 형성하게 된다.

모든 noisy reference block에 대해 SSD(sum of squared differences)를 계산하여 SSD가 설정한 threshold보다 낮다면 같은 그룹에 배정한다.

아래 그림 상에 R이라 표시한 빨간색 패치가 the reference current patch이다. 식으로 표현하면 다음과 같다.

이때 hard는 threshold를 의미하고 d(P,Q)는 두 패치간의 거리는 계산하는 SSD 함수이다.

Grouping by Block Matching, Image denoising by sparse 3D transform-domain collaborative filtering, Kostadin Dabov et al.

그룹으로 묶인 패치들에 대해서 한꺼번에 필터를 적용하여 denoised patch를 얻는다. 이렇게 모아서 필터링하는걸 collaborative filtering이라고 한다.

모든 패치에 대해 일괄적인 필터링이 아니라 각 블록간의 특성에 맞춰 필터링이 따로 적용되기 때문에 해당 블록의 unique feature를 보존할 수 있게 해준다.

필터링을 할때에는 wiener filter나 hard thresholding을 사용하게 된다.

NLM과의 차이점을 짚어보자면 NLM에서는 단 하나의 중앙 점을 업데이트하기 위해 모든 패치 정보를 활용하였다면 이번 BM3D에선 패치그룹에 대해 한꺼번에 적용하여 더 계산 효율적이다.

Collaborative Filtering, https://shaharkov.github.io/projects/TutorialDenoising/ATCV_Denoise_Publish.pdf

디노이징이 완료된 패치들을 다시 위치에 맞게 합쳐주어야 하는데 이를 Fusion 혹은 aggregation이라고 한다. 그런데 이 과정에서 한 위치의 픽셀이 여러그룹에 걸치게 되는 경우 mutiple estimates를 가지게 된다.

모든 estimates를 단순 평균을 하기 보단 훨씬 더 reliable estimates에 가중치를 부여하도록 한다.

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

가중치를 부여하는 방법은 각 그룹의 디노이징 퀄리티에 비례해서 부여하도록 한다. 퀄리티는 hard threshold를 쓰는지 weiner filter를 쓰는지에 따라 다르다.

그런데 이 과정을 한번만 하지말고 두번 하는것이 어떨까?

실전에선 2 phase로 구성하도록 한다. 첫번째 과정에선 hard thresholding을 사용하고 두 번째 과정에선 wiener filtering을 사용하도록 한다.

이 두번째 과정을 통해 더 많은 디테일과 디노이징 퍼포먼스를 올릴 수 있다.

두 번째 과정에선 첫번째 과정의 결과물인 basic estimate 뿐만 아니라 원본 noisy image까지 이용하도록 한다.

전체 과정을 플로우 차트로 나타내면 아래와 같다.

Two phase BM3D Denoising, Image denoising by sparse 3D transform-domain collaborative ltering, Kostadin Dabov et al.

이때 이전 첫번째 단계에서 계산한 estimate를 통해 wiener coefficient를 계산하고 original noisy image에서 다시 stacking한 패치들에 대해 transform을 한 뒤에 winer coefficient를 적용한다.

이후 inverse trasformation을 하여 다시 2D 이미지로 되돌리게 된다.

먼저 첫번째 단계의 결과물을 basic estimate ubasic라고 명한다.

⦁  : basic estimates ubasic의 패치를 stacking 

⦁  : original noisy image u에서 패치를 stacking 

⦁  : basic estimates의 패치를 stacking한 것으로 부터 weiner coefficient를 계산한다. 

3D는 3D transformation이고 이것을 위에서 구한 weiner coefficient를 사용해서 collaborative filtering을 하도록 한다.

BM3D는 디노이징 기법에서 굉장히 기념비적이라고 할 수 있다. 다음과 같이 뛰어난 성능을 낼뿐만 아니라 계산 효율적인 측면에서 사람이 직접 고안한 기법에서 좋은 성과를 보인다고 할 수 있다. 이미지 패치 사이즈나 threshold와 같은 hyper parameter가 다양한 노이즈 레벨에 어떤 영향을 주는지 연구한 상세한 실험은 Marc Lebrun의 논문을 참조하도록 하자.

Denoising results 1, Image denoising by sparse 3D transform-domain collaborative ltering, Kostadin Dabov et al.

Denoising results 2, An Analysis and Implementation of the BM3D Image Denoising, Method Marc Lebrun

마치며

지금까지 전통적인 방법론의 마지막 부류인 Transformation 테크닉에 대해서 알아보았다.

비록 과거의 기술이라고는 하나 상용으로 사용할 정도로 발전을 이룬 머신러닝 알고리즘들이다.

특히 BM3D의 경우는 초창기 딥러닝 모델조차도 성능을 쉽게 뛰어넘기 힘들 정도로 한 동안 수문장의 역할을 한 알고리즘이다.

또한 Wavelet transformation이나 Dictionary learning은 머신러닝의 핵심적인 철학을 딥러닝과 여전히 공유한다고 볼 수 있으며 최신 연구에서도 아직도 이런 방법을 활용하는 모습을 보여주기도 한다. 다음편부턴 본격적으로 딥러닝 방법론에 대해서 알아보도록 한다.

About Author 

Taeyeop Kim

​Pro, AI 1팀

tykim@cubox.ai