2019년 5월 12일 일요일

Image Restoration (IR): inverse problem point of view (1)

제 박사 학위 논문 제목은 "Learning-based approaches for Inverse Scattering Problems"입니다. 이 제목은 제 지도 교수님께서 지어주셨는데, 박사 학위 디펜스를 하면서 committee 교수님들께 학위 논문이 아니라 textbook에나 어울리는 제목이라고 좀 더 범위를 좁혀 수정을 하라는 지적을 다수 받았던 기억이 납니다.
** 그럼에도 불구하고 지도 교수님께서는 차라리 다른 imaging modality에 대한 연구를 추가로 할지언정 이 제목은 꿋꿋히 유지하라고 말씀하셨고, 결국에는 추가 연구를 더 해서 넣고 (하하하...orz...) 결국 제 학위 논문의 제목은 그대로 유지했습니다. 

오늘 소개할 내용은 제 학위 논문 제목에도 나와있는 inverse problem에 대한 얘기입니다. 그 중에서도 영상(image)에 대한 inverse problem에 대한 것으로 좀 더 좁게는 image restoration 문제에 대한 정리를 하고자 합니다.

Inverse Problems

An inverse problem in science is the process of calculating from a set of observations the causal factors that produced them: for example, calculating an image in X-ray computed tomography, source reconstruction in acoustics, or calculating the density of the Earth from measurements of its gravity field. It is called an inverse problem because it starts with the effects and then calculates the causes. It is the inverse of a forward problem, which starts with the causes and then calculates the effects.
어느 정도 감을 잡으셨을지 모르겠습니다만, 사실 committee 교수님들께서 제게 주셨던 의견들은 매우 온당한 것으로 inverse problem이라는 분야는 매우 광범위합니다. 위의 정의에서도 볼 수 있듯이 어떤 물리적 시스템을 묘사하는 문제를 forward modeling이라 한다면 그의 반대 방향을 모델링하고 연구하는 것을 inverse problem이라 할 수 있겠습니다.

하나의 예시로 아래와 같이 어떤 시스템 (e.g., 카메라)을 통과한 자연 이미지(latent original image)가 natural noise (e.g., additive white Gaussian noise, AWGN)뿐만 아니라 blurring 혹은 down-sampling과 같은 시스템의 특성으로 인한 degradation이 추가되어 관측된 이미지를 얻은 상황을 고려해보겠습니다:


이 때, 시스템 함수 혹은 operator $G$에 대한 물리적인 이해를 바탕으로 이를 찾거나 모델링하는 것을 forward problem이라 하고, 반대로 관측한 이미지를 바탕으로 깨끗한 원래 이미지를 찾는 문제를 inverse problem이라 합니다. 시스템에서 일어난 degradation에 따라서 각각 deblurring, denoising, super-resolution 등의 여러 영상 복원 (image restoration) 문제들로 세분화 될 수 있습니다.

Problem statement


General formulation


Image restoration을 수식적으로 모델링하는 방법은 매우 다양하겠으나, 측정 벡터 $y$가 임의의 선형 시스템 행렬 $H$와 가우시안 노이즈 (additive white Gaussian noise, AWGN)에 대해 $$y=Hx+v$$로 표현하는 것이 가장 일반적이며, 시스템 행렬 혹은 operator $H$가 어떤 것이냐에 따라 여러가지 영상 복원 문제가 모델링됩니다.

예를 들어 denoising은 $H=I$, deblurring (deconvolution)은 $H$가 convolution filter로 $Hx = k\circledast x$인 경우가 되며, inpainting은 $H$가 identity matrix이되 missing samples에 해당하는 부분이 듬성듬성 비어있는 degradation matrix로 모델링이 가능합니다. 또한 super-resolution은 $H$가 blur kernel과 sub-sampling (혹은 down-sampling)이 결합된 형태이며, 의료 영상 분야에서 사용되는 tomographic reconstruction은 $H$가 특정한 physical projections (e.g., Radon projections)이라 할 수 있겠습니다. 

영상에 가해진 degradation으로 인해 이를 되돌리는 것은 매우 "어려운데", 여기서 어렵다는 것은 image restoration (IR)은 "ill-posed" inverse problem (**)이라는 뜻입니다. 예를 들어 Single Image Super-Resolution (SISR)은 대표적인  ill-posed problem으로 방정식의 변수가 독립적으로 구성할 수 있는 식의 갯수보다 많은 경우입니다. 좀 더 구체적으로는 $H$의 row 수에 비해 column의 수가 훨씬 많기에 $x$의 해가 무한히 많을 수 있어서 진짜 $x^*$를 특정하기 어렵다는 것으로, 한 장의 저해상도 이미지에 대응할 수 있는 고해상도 이미지는 다양한 경우의 수가 있다는 예시로 이해하시면 쉽습니다.
** ill-posedness를 알고 싶다면 well-posed problem이 무엇인지를 알면 됩니다. 이는 wikipedia를 참고하시면 되겠습니다. 

특히나 natural image와 같이 전체 공간(search space)이 매우 큰 경우 해를 찾는 일이 더 지난하기 때문에, 가능한 해가 살고 있는 공간(solution space)을 좁히기 위해서 문제에 따라 시스템에 따라 적절한 constraint를 바탕으로 제약(regularize)을 걸어주는 방식을 취하게 됩니다. 따라서 관측된 데이터 $y$로부터 $x$를 구하기 위해서는 $$\min_x\frac{1}{2}||Hx-y||^2_2+\lambda\rho (x)$$를 푸는 것이 일반적이며 $\rho(x)$는 우리가 고른 regularization 항이 되겠습니다.

Bayesian perspective


이를 Bayesian 관점으로 표현하면, likelihood function $P(y|x)=exp(-\frac{1}{2\sigma^2}||y-Hx||^2_2)$에 적절한 image prior $P(x)$를 사용하여 $P(x|y)$를 구하는 maximum a posteriori (MAP) estimation으로 생각할 수 있습니다:$$\begin{align*} \hat{x} &=\arg\min_x\{-\log P(y|x)-\log P(x)\} \\ &= \arg\min_x\{\frac{1}{2\sigma^2}||y-Hx||^2_2+\lambda\rho(x)\}\end{align*}$$ 여기서 $\sigma^2$는 $\lambda$에 흡수될 수 있으므로 결과적으로 같은 형태가 된다는 것을 알 수 있죠.

이런 MAP framework로 IR 분야에 연구들을 살펴보면, image에 대한 prior를 어떤 것으로 정하느냐가 모델링의 주안점이 되어왔다는 것을 알 수 있습니다. 대표적인 image prior 모델로는 sparsity-inducing prior나 low-rank prior가 있겠으며, 이를 이용하여 optimization 문제를 푸는 전통적인 방식을 model-based optimization이라는 하나의 큰 카테고리로 묶을 수 있습니다.

한편 model-based optimization과는 조금 다른 갈래가 최근 트랜드인 deep learning입니다. 이를 MAP framework 관점에서 생각하면 deep learning 역시도 일종의 discriminative learning prior로써 image prior 모델링의 한 종류라고 생각할 수 있겠습니다.

지금부터는 이런 분류를 바탕으로 각 카테고리의 방식들을 하나씩 소개하겠습니다.

Sparse representation


많은 IR 알고리즘들이 sparsity prior를 사용하고 있습니다. 대표적인 예로는 total variation (TV)이 있으며, wavelet transform 이후 soft-thresholding을 하는 간단하지만 강력한 denoising 기법들이 있습니다. (이 방식은 natural image에 대한 wavelet domain representation이 일반적으로 sparse하다는 것을 근거로 합니다.)

또한 이미지 patch들이 sparse dictionary representation이 가능하다는 것 역시도 잘 알려진 사실이며 이를 이용하는 대표적인 알고리즘이 sparse coding입니다. IR에 대한 일반적인 sparse representation 모델은 overcomplete dictionary $D$와 이에 대응하는 coding (coefficients) vector $\alpha$에 $l_1$-norm을 취한 sparsity regularization이 더해진 형태입니다 (i.e., $\min_\alpha ||\alpha||_1$ s.t. $x=D\alpha$): $$\hat{\alpha}=\arg\min_\alpha||y-HD\alpha||+\lambda||\alpha||_1$$ 즉, sparse coding에서는 $x$에 대한 문제를 $\alpha$에 대한 estimation으로 문제를 바꾸어 풉니다. 

Sparse representation이 IR에서 성공적이었던 이유는 여러 가지로 방향으로 설명이 가능한데,
  1. Bayesian 관점에서 보면 sparsity prior를 이용하여 MAP 문제를 매우 잘 풀었다고 할 수 있고,
  2. neuroscience 측면에서 보면 실제로 인간의 primary visual cortex의 simple cells들이 들어오는 시각 신호에 대해 spatially localized, oriented 혹은 band-passed 형태로 각각 특화되어 있는데, wavelet filter를 사용한 sparsity-inducing representation이 이를 잘 모사하기 때문일 수도 있으며,
  3. compressed sensing 관점에서는 image patch들이 $k$-sparse한 신호들이라서 애초에 sparse optimization 형태로 가장 잘 풀 수 있는 문제이므로 여러 모로 성격이 잘 맞았다고 설명할 수도 있습니다. 

Sparse Dictionary Learning


Sparse representation 방식이 잘 통하려면 이를 표현할 atom들이 모인 dictionary를 잘 만드는 것이 가장 기본이 되겠습니다. 초기에는 DCT나 wavelets, curvelets 등을 사용한 analytical dictionary 구성이 주를 이루었으나 natural image의 복잡성을 충분히 표현하기에는 이런 hand-crafted analytical dictionary로는 한계가 있었습니다. 즉, 복잡한 이미지에 대해서는 더 많은 atom들이 필요했고 자연스럽게 sparseness가 떨어지는 문제가 있었죠.

이를 해결하기 위해 다음으로 연구된 것이 dictionary에 들어갈 atom들을 이미지들로부터 학습하는 것이었습니다. 즉, $Y=[y_1,\cdots,y_n]$과 같은 학습 샘플들이 있을 때, $m<n$인 atom을 갖는 dictionary $D=[d_1,\cdots, d_m]$을 $Y$로부터 배우되 $Y=D\Lambda,~\Lambda=[\alpha_1,\cdots, \alpha_n]$을 만족하는 code $\alpha$에 $l_0$-norm sparsity constraint를 주어 학습시킵니다. 여기서 $y_i$는 vectorized된 이미지 patch로 생각하시면 됩니다. 이 카테고리의 가장 대표적인 알고리즘으로는 K-SVD가 있습니다. 

Dictionary learning 방식은 analytically designed dictionary에 비해 특정 task나 data에 좀 더 adaptive한 표현이 가능했기에 일반적으로 더 좋은 성능을 보여주었고, multi-scale dictionary learning, double sparsity, adaptive PCA dictionaries, semi-coupled dictionary learning 등 다양한 알고리즘들이 개발되었으며 많은 연구 분야에서 애용되어 왔습니다. 

Low-rank minimization


Natural image에서 patch를 뽑으면 생각보다 패턴이 반복되는 경우가 많습니다. 이런 경험적인 지식을 바탕으로 non-local self-similarity (NSS) prior를 사용하는 연구들이 있는데요. 이런 방법들은 보통 이미지 내에 correlated patch들을 여러 장 모아 사용합니다. 각각의 이미지 patch를 따로따로 처리하는 sparse representation과는 확실히 다르다는 것을 알 수있습니다.

Non-local self-similarity in natural image

그림과 같이 이미지로부터 patch들을 뽑은 다음 column의 형태로 옆으로 쌓아 matrix 형태로 만들면, 이렇게 만든 matrix는 correlated patch들로 인해 low-rank한 특징을 갖게 됩니다.

이런 특징을 이용하는 IR 방법을 low-rank minimization이라 합니다. 예를 들어 이미지에 Gaussian noise가 더해지는 denoising 문제를 생각해보겠습니다. Noise는 패치들을 여럿 모은다고 해서 서로 correlate 할 이유가 없으므로 일반적으로 full-rank한 특성을 갖겠지만, 우리가 원하는 실제 이미지는 low-rank한 특성이 있을테니 데이터 행렬을 low-rank한 행렬로 approximation하므로써 denoising이 가능합니다. 즉, corrupted patch를 다른 patch로부터 수집한 redundant information을 바탕으로 수정하는 것이죠. 

문제는 행렬의 rank를 minimize하는 것이 매우 잘 알려진 NP-hard 문제라는 것입니다. 따라서 rank minimization 문제는 rank penalty의 convex relaxation인 nuclear norm을 사용해서 문제를 풀게 됩니다: $$\hat{X}=\arg\min_X ||Y-X||^2_F+\lambda||X||_*$$ 이 때, $X$의 nuclear norm은 $||X||_*=\sum_i||\sigma_i(X)||_1$로써 singular value의 합입니다. 이런 formulation의 장점은 문제의 closed-form solution이 존재한다는 것입니다. $Y=U\Sigma V^T$일 때, $$\hat{X}=US_{\frac{\lambda}{2}}(\Sigma)V^T$$이며, $S_{\frac{\lambda}{2}}(\Sigma)_{ii}=\max(\Sigma_{ii}-\frac{\lambda}{2},0)$으로 일종의 thresholding operator입니다. 이렇게 보면 행렬 $X$에 low-rankness도 다르게 말하면 행렬의 singular value들이 sparsely distribute할 것이라는 가정에서 시작하는 것이므로 sparsity prior라고 할 수 있겠습니다.

지금까지 매우 간결하게 Image restoration에서 사용되어 온 큰 줄기를 훑어보았는데요. 다음 글에서는 이런 model-based optimization 방식과는 좀 다른 결을 보여주는 learning-based approach를 소개하겠습니다.

간단히만 소개하자면, MAP estimation이라는 관점에서 discriminative learning 방식은 MAP inference를 predefined nonlinear function으로 대체하여 문제를 푸는 것으로 생각할 수 있습니다: $$\min_\theta l(\hat{x},x),~\text{s.t}~\hat{x}=\mathcal{F}(y,H;\theta)$$ 여기서 $\mathcal{F(\cdot)}$는 CNN이라고 생각하시면 됩니다.

이런 discriminative learning 방식은 model-based optimization 방식에 비해 유연성이 떨어지지만, 대신 test time에서 inference 속도가 빠르다는 장점이 있습니다. 이 외에도 여러 장단점과 특징이 있는데 왜 그러한 특징이 생기는지 등 자세한 것은 다음 글에서 다루겠습니다.

결국 하고 싶은 말은 deep learning을 사용하는 방식이 절대로 기존에 연구되어 온 많은 연구들과 완전 다른 길을 걷고 있는 것이 아니고, 이 역시도 크게는 image prior $P(x)$를 모델링하는 방식 중 하나라는 관점에서 설명할 수 있다는 것입니다.

그럼 곧 다음 글에서 뵙겠습니다.

다음 읽을 거리






댓글 4개:

  1. 작성자가 댓글을 삭제했습니다.

    답글삭제
  2. 안녕하세요, 사소한 질문인데 궁금해서 댓글 남깁니다..
    Sparse Dictionary Learning에서 Y=DA (lambda 대신 A로 표기했습니다)에서 Y, D, A의 차원들이 각각 어떻게 되나요?
    Y = n x n (n차원으로 vectorized 된 image patch n개),
    D = n x m, A = m x n 이면 말이 될 것 같긴 한데요,
    문제는 m < n인 경우를 상정하셨다고 하셨는데
    이렇게 되면 row 수가 column 수보다 많은 상황이 됩니다...

    제가 어느 부분에서 잘못 이해하고 있는 것일까요ㅠ
    답변해 주실 수 있나요? 미리 감사드립니다.

    답글삭제
    답글
    1. 예를 들어 3 by 3 patch n장을 사용할 때 Y의 크기는 9 x n, D는 9 x m, 마지막으로 A는 m x n이 되는데요. 어떤 부분이 문제가 되시는지요? row 수가 column 수보다고 많다고 말씀하시는 것으로 미루어 볼 때 아마도 처음에 Y의 patch size dimension을 sample 갯수인 n과 동일하게 놓으신 것 때문에 헷갈리신게 아닐까 짐작해봅니다.

      삭제
    2. 아~~~ 추측하신 부분이 오해한 부분과 정확히 일치합니다!
      댓글 달아주셔서 감사드립니다. 좋은 하루 되세요!

      삭제