[계산사진학] Image Alignment - Direct Alignment

Example - Panorama

Image alignment에 대해서 알아보기에 앞서서 다음의 image를 보도록 하자.
Image alignment는 여러 image를 정확하게 겹치기 위해서 image들을 정렬하는 기법이다. Image alginment의 적용 사례 중 하나가 panorama image generation이다. 위의 예시를 보면 여러 이미지들이 있을 때, image alignment 서비스 등을 이용하면 자동으로 panorama image를 만들어낸다. Image들은 무작위로 준비가 되었기에 카메라의 위치나 방향 등과 같은 다른 정보들이 없었다. 그러나 요즘 기술을 보면 이를 알아서 찾아서 image들을 정렬시키고, panorama image를 만들어내는 것을 볼 수 있다.

Example - Removing Background Motion

위와 같이 image 여러개를 찍었다고 해보자. 다시 이 image들을 Google photo와 같은 서비스를 이용하면 원래 image를 촬영할 때 삼각대와 같은 도구를 사용하지 않고 단순히 연속 촬영을 했음에도 불구하고 연속 촬영 된 image들만을 이용해서 움직이는 동영상을 만들 수가 있다. 그 결과 삼각대를 이용한 것과 같이 고정 된 자연스러운 영상이 만들어지게 된다. 이 예시에서 보았듯이 image alignment는 background motion을 제거할 수 있고, stablized video를 만들어낼 수 있다.

Example - Video Stabilization

어떠한 촬영 장비도 없이 손에 카메라만을 들고 간단하게 영상을 촬영했을 때, 촬영 된 영상이 매우 흔들릴 가능성이 있다. 이러한 문제를 해결하기 위해서 video stablilization이라는 video processing 기법을 사용할 수 있다. Video stabilization을 사용하게 되면 마치 전문가가 촬영하거나 장비를 사용한 것처럼 흔들리지 않는 결과를 만들어낼 수 있다. Video stabilization은 여러 곳에서 쉽게 볼 수 있다. 특히 video 편집 도구를 보면 기본적으로 들어가있다. 하물며 요즘은 스마트폰에도 기본적으로 video stabilization 기법이 도입되어 있다. 스마트폰같은 경우 카메라도 작고 그래서 이러한 기법이 없다면 아마 매우 흔들린 영상을 얻게 될 것이다.

Example - Object Detection/Localization

또 다른 예시로는 object detection, localization 등이 있다. 여기서 우리가 하고 싶은 것은 해당하는 개체를 찾는 것이다. 그래서 image alignmnent는 image 속 특정한 개체를 localization하는 방법을 제공해준다.

Image Alignment

이제 image alginment가 어떻게 동작하는지 볼 것이다. Image alignment는 image registration으로도 불린다. 여기서 우리가 관심있는 것은 2개의 image를 자동으로 정렬하는 것이다. 구체적으로는 하나의 image를 warping하는 transformation parameter들을 찾아야 한다. Warping 후에는 image 내의 내용물들이 정확하게 겹쳐질 것이다. 그래서 2개의 image가 주어졌을 때 transformation parameter를 찾는데 접근하는 방식은 기본적으로 2가지가 있다. 하나는 feature-based alginment이고, 다른 하나는 direct(pixel-based) alignment이다.

Feature-based alginment는 2개의 image로부터 여러개의 matching feature들을 찾아야 한다. 찾은 뒤에는 matching feature를 이용해서 transformation parameter들을 계산해야 한다.
그래서 여기 예시를 보면 image로부터 두드러지게 나타나는 feature point들을 찾은 것이다. 그리고 찾은 점들로부터 matching을 찾아서 transformation parameter를 계산하면 완전히 겹쳐지는 것을 볼 수 있다.
그래서 feature-based alginment는 transformation parameter를 얻기 위해서 이러한 correspondence들을 찾아서 구할 수 있다.

2번째 접근 방식인 directe alignment는 transformation parameter를 찾는데 2개의 image로부터 모든 pixel들을 비교해야 한다.

Direct Alignment

그래서 이번에는 direct alginment에 대해서 자세하게 알아보려고 한다. Direct alignment는 2개의 image로부터 모든 pixel들을 비교해서 최적의 parameter를 찾는 것이다. Direct alginment 기법들 중에서 가장 간단한 방법은 brute force search이다. Brute force search는 2개의 image의 translation을 찾는데 종종 사용된다.
Template image $T$와 image $I$가 있다고 해보자. 그러면 image $I$ 속 template image $T$의 위치를 찾고 싶다. 구체적으로 translation vector $u$를 추가로 가정할 것이다.

우리는 이러한 가정으로부터 가장 작은 error를 만드는 $u$를 찾고싶다. Brute force search에서 template image $T$를 비교하고 움직이면서 최적의 parameter $u$를 찾을 수 있다.
이러기 위하여 2중 반복문을 위와 같이 사용하면 된다. 각각의 $ty, tx$에 대해서 우리는 template image $T$를 image $I$와 비교할 수 있다. 또한, 이를 위해서 올바른 parameter $y_0,y_1,ystep,x_0,x_1,xstep$을 고를 필요가 있다.

Error Metrics

Template image $T$와 image $I$를 비교하기 위해서는 error metric이 필요하다. 우리가 사용할 수 있는 error metric으로는 sum of squared differences(SSD), sum of absolute differences(SAD), cross-correlation, zero-mean normalized cross-correlation(ZNCC) 등이 있고, 이 중에서 SSD는 template image와 image 사이에 L2-norm을 사용한다.

$T$와 $I$는 서로 다른 lighting condtion을 가지는 것이 가능해서 이들의 brightness나 contrast가 다를 수 있다. 이러한 경우에는 SSD에 bias와 gain을 도입하여 exposure difference를 반영할 수 있다.

여기서 $\alpha$는 gain이고 $\beta$는 bias이다. $\alpha$는 contrast difference를 보상하고, $\beta$는 average brgitness difference를 보상한다. 이 2개의 값은 SSD를 계산하기 전에 미리 추정되어야 한다.

또 다른 널리 사용되는 metric으로 cross-correlation이 있다.

이 metric은 효율적으로 하나의 correlation operation이나 동등하게 convolution operation으로 사용된다. 그리고 이는 Fourier transform을 통해서 더 가속하여 사용될 수 있다. 그리고 다음은 zero-mean normalized cross-correlation이다.

이는 cross-correlation을 간단하게 확장한 것으로, template $T$와 image $I$를 정규화 한 것이다. 그래서 이들의 평균은 0이고, 표준 편차는 1이 된다. 이 정규화는 두 image 사이의 exposure difference의 효과를 제거할 수 있으므로, 다른 lighting condition의 image를 다룰 때 zero-mean normalized cross-correlation이 SSD보다 더 효과적일 수 있다.

More Complex Motion Model

기본적은 brute force search에서 최적의 조합을 찾기 위해서 parameter의 모든 가능한 조합을 테스트해본다. 그러나 종종 rigid-body transformation, affien transformation, homography와 같은 더 복잡한 motion model을 필요로 한다. 그래서 이러한 경우에 template image $T$와 image $I$를 가정하고 다음과 같은 관계식을 가지게 된다.

여기서 $H$는 homography와 같은 warping function이고, $\theta$는 warping parameter이고, 우리는 이 최적의 parameter $\theta$를 찾는 것이 목적이다.

Direct Alignment(Brute Force)

Homography는 8개의 parameter를 필요로 한다. 그래서 brute force search를 이용해서 8개의 parameter를 찾기 위해서 다음과 같이 8개의 nested for loop를 사용 할 필요가 있다.
이렇게 하면 time complexity가 아무래도 $O(N^8)$이기 때문에 아마도 속도는 엄청 느릴 것이다. 또한 각 parameter에 대한 searching 범위를 설정하는 것도 간단하지 않을 것이다. 그렇다면 우리는 무엇을 해야할까? 하나 가능한 방법은 seraching 범위를 제한하는 image pyramid를 사용하는 것이다. 그러나 이렇게 해도 속도는 느릴 것이다.

Lucas-Kanade Method

운이 좋게도 더 나은 방법으로 Lucas-Kanade 방법이 있다. 이 내용에 대해서 깊게 다루지는 않을 것이고 이 방법에 대해서 기본 아이디어를 간단하게 이해해 볼 것이다. Lucas-Kanade method에서 template image $T$와 image $I$ 사이의 alignment error를 다음과 같이 식으로 나타낼 수 있다.

여기서 template image $T$는 warping function $W$에 의해서 휘어지게 된다. 그리고 warping function $W$는 parameter $\theta+\bigtriangleup\theta$에 의해서 조절되게 된다. 이 error function은 $\bigtriangleup\theta$의 function이다. 그리고 Lucas-Kanade method는 error function을 최소로 하는 $\bigtriangleup\theta$를 찾고, warping parameter $\theta$를 업데이트한다. 그러면 업데이트 된 $\theta$는 Lucas-Kanade method는 다시 반복해서 warping parameter $\theta$를 업데이트 하기 위해서 $\bigtriangleup\theta$를 찾는다. 그래서 최적의 $\bigtriangleup\theta$를 찾기 위해서 Lucas-Kanade method는 Taylor expansion을 이용해서 error function을 approximation한다.

그러면 approximated error function은 $\bigtriangleup\theta$의 quadratic function이 되고, $\bigtriangleup\theta$는 least-square problem을 풀어서 찾을 수 있다. 전체 algorithm은 다음과 같다.
먼저 초기 parameter $\theta$를 설정해준다. 그리고 반복적으로 $\bigtriangleup\theta$에 관한 least-square problem을 풀어서 $\theta$를 $\theta + \bigtriangleup\theta$로 업데이트 해준다.
이는 Lucas-Kanade method가 어떻게 동작하는지에 대한 diagram이다. Image $I$와 template image $T$가 있고, 또한 초기의 warping parameter $p$가 있다. 그러면 parameter $p$를 이용해서 image $I$를 휘어지게 하고, warped image와 template image 사이의 difference를 계산한다. 이 difference로부터 우리는 least square problem을 해결하는 위의 모든 step들을 거쳐서 끝내 업데이트 된 $\bigtriangleup p$를 얻는다. 그런 다음 이 $\bigtriangleup p$를 사용하여 warping parameter $p$를 업데이트한다.