Scale Space와 이미지 피라미드(image pyramid)

영상처리 2014. 5. 13. 14:16

문일지십. 하나를 들으면 열을 깨닫는다.

 

보통은 머리가 뛰어난 사람을 일컫는 말이지만 꼭 그런 것만은 아니라고 생각한다. 우리가 어떤 잘 모르는 개념 또는 사물을 알고 싶을 때 한눈에 깨닫지 못할 때는 흔히 다양한 각도에서 대상의 실체를 알기 위해 노력한다. 하지만 어떤 설명을 읽어보아도 그 개념이 명확치 않은 경우가 종종 있다. 실체를 깨닫지 못한 상태에서는 아무리 많은 설명을 들어도 모두가 안개속이고 오히려 혼란만 가중되기 때문이다. 공부도 마찬가지이다. 안개속에 있는 사람에게는 아무리 다양한 방법으로 설명해 줘도 별 효과가 없는 경우가 대부분이다. 그런데.. 한가지, 단 한가지를 깨닫는 순간 그 모든 것들이 일시에 깨달아지는 순간이 있다. 핵심으로 향하는 문이 열리는 순간 그동안 자신을 괴롭히던 여러 문제들이 믿을수 없게 다 이해가 되고 낱낱이 흩여져 있던 사실들이 사실은 하나로 관통되어 있음을 깨닫게 된다. 하지만 그 문이 열리는 것은 결코 쉬운 일이 아니다.

 

Scale Space(스케일 스페이스)..

 

근 3주 가까이 머리 속에 맴돌고 있지만 틈틈히 자료를 읽어보아도 뭔가 개운하게 정리가 안된다. 대충은 알것 같은데 잘 정리가 안되는 것이 아무래도 핵심으로 가는 실타래를 아직 발견하지 못한 것 같다. 그래도 일단은 글로 적어보면서 정리해 보고자 한다.

 

 

참고자료

☞ 첫번째 자료가 scale space 이론에 대한 가장 대표적인 참고자료로 알려져 있지만 개인적으로 봤을 때 그렇게 잘 쓰여진 내용은 아니라고 생각합니다 (너무 어렵고 산만함). 오히려 두번째 자료의 9장 내용이 훨씬 좋습니다.

 

 

1. 스케일(scale)

 

우리는 동일한 장면을 보면서도 스케일에 따라서 전혀 다른 것들을 보게 된다. 예를 들어, 똑같은 나무에 대하여 작은 스케일에서는 나뭇잎이나 가지를 보겠지만 큰 스케일로는 나무가 포함된 숲을 볼 수도 있다.

 

영상인식, 컴퓨터 비전에서도 스케일은 중요한 문제 중의 하나이다. 이는 영상에서 물체의 특징을 계산할 때 어떤 스케일에서 보느냐에 따라 전혀 다른 결과가 나올 수 있기 때문이다. 일례로 영상 코너(corner) 검출에서,  아래 그림과 같은 형태의 물체는 큰 스케일(붉은색 박스)에서는 명확히 코너점으로 인식되겠지만 작은 스케일(연두색 박스)에서는 완만한 곡선 또는 직선으로밖에 인식되지 못할 것이다.

 

<그림 1> 스케일 문제 - 코너점 검출 예

 

이러한 스케일(scale) 문제에 있어서 가장 근원적인 해결책은 당연히 대상을 여러 스케일에 걸쳐 표현 (multi-scale representation)하고 분석하는 것이다.

 

영상처리 분야에서는 이미지의 스케일(scale)을 다루는 방법으로 크게 '이미지 파라미드(image pyramid)' 방법과 'scale space 이론' 방법이 있다.

 

☞(2021.8.14) 댓글에 답변을 달다가 내용에도 추가합니다. 흔히 scale을 이미지의 크기로 생각하기 쉬운데, scale은 이미지 크기와는 다른 개념입니다. 이미지 크기는 이미지의 픽셀 수나 물리적인 width, height 크기를 말합니다. 하지만, scale은 이미지의 detail과 관련된 개념입니다. 예를 들어, 산의 모양을 본다면 scale이 큰 것이고, 나뭇잎의 모양을 본다면 scale이 작은 것입니다. 그림 4를 보면 스케일이 증가할수록 블러링(blur)된 영상을 볼 수 있습니다. 그만큼 detail한 것은 무시하고 전체적인 것을 본다는 의미가 됩니다.
그림 6에 보면 한 octave에서 다음 octave로 넘어갈 때 sub sampling을 통해서 이미지의 크기가 1/2로 줄어듭니다. 이 때, 이미지의 크기(size)는 1/2로 줄어듭니다만 이미지의 scale은 sigma = 2로 모두 동일한 것으로 봅니다. subsampling을 통해서 size는 1/2로 줄어들었지만 이미지가 담고있는 정보의 detail(scale)은 동일하다는 의미로 보시면 됩니다.

 

 

2. 이미지 피라미드(image pyramid)

 

이미지를 여러 스케일(scale)에 걸쳐서 분석하는 가장 기본적인 방법은 입력 이미지의 크기를 단계적으로 변화(축소)시켜 가면서 필요한 분석 작업을 하는 것이다. 이 때 이렇게 생성된 일련의 이미지 집합을 이미지 피라미드(image pyramid)라 부른다.

 

예를 들어 영상에서 보행자를 검출하는 경우, 먼저 <그림 2>와 같이 이미지 피라미드를 생성한 후 각 스케일 영상에서 고정된 크기의 윈도우를 이동시켜 가면서 윈도우 내 영역이 보행자인지 여부를 판단하는 것이 일반적이다.

 

<그림 2> 이미지 피라미드

 

※ 스케일이 크다? 작다?

흔히 스케일이 크다는 것은 어떤 사물을 넓은 시야에서 본다는 의미이다. 그렇다면 이미지 피라미드에서 축소된 이미지들은 원본 이미지에 비해 스케일이 큰 것일까? 아니면 작은 것일까? 정답은 '크다'이다. 혼동되기 쉬운 부분이긴 한데 일반적으로 이미지의 크기(size)를 축소시킬수록 detail을 잃어버리기 때문에 이미지의 스케일(scale)은 (반비례로) 큰 값을 갖는다. 조금 다른 예로, 이미지의 크기(size)는 동일한데 scale만 커지는 경우도 있다. 바로 이미지가 smoothing 또는 블러링(bluring)되는 경우로서 이미지가 블러링될수록 detail을 잃어버리고 큰 흐름을 표현하기 때문에 scale이 커진다.

 

※ Gaussian Pyramid

이미지 피라미드를 생성할 때, 일련의 블러링(blurring)과 다운 샘플링(sub sampling)을 통해 이미지를 1/2씩 축소시켜 가면서 피라미드를 생성하는 경우도 있다 (블러링->1/2축소->블러링->1/2축소->...). 블러링에는 Gaussian 필터를 이용하고 다운 샘플링은 짝수번째 픽셀들은 버리고 홀수번째 픽셀들만을 취하는 방식으로 진행한다. 이렇게 생성된 이미지 피라미드를 Gaussian pyramid라 부르는데, Gaussian pyramid에서는 이미지의 크기(size)가 빠르게 줄어들기 때문에(반면에 scale은 빠르게 증가) 피라미드를 구축하기 위한 시간과 메모리 요구량이 낮고 이후 빠른 영상분석이 가능한 장점을 갖는다. 하지만 스케일 축에서 보면 Gaussian pyramid는 물체가 가질 수 있는 연속된 스케일 변화를 매우 coarse하게만 샘플링한 것이기 때문에 스케일 축 상에서 물체를 비교하거나 매칭할 때 알고리즘적으로 문제가 어려워지는 문제점도 있다.

 

<그림 3> Gaussian pyramid (그림출처: Twan Maintz, "Digital and Medical Image Processing")

 

따라서, Gaussian pyramid는 축소된 이미지에서 빠르게 원하는 특징이나 대상을 검출한 후에 점차적으로 원래의 스케일에서 보다 정확한 특징을 계산하는 coarse-to-fine 형태로 주로 사용된다. 일례로, opencv 등에 구현되어 있는 Lucas-Kanade optical flow 알고리즘은 먼저 피라미드의 최상층 이미지에서 optical flow를 대략적으로 계산한 후 이를 좀더 확대된 이미지에서 다시 계산(refine)함으로써 점차적으로 flow의 정확도를 높이는 방법을 사용한다.

 

 

3. Scale Space

 

Scale space... 단어적 의미로 본다면 scale space는 스케일(scale) 축을 따라서 생성되는 공간이다. 즉, 어떤 대상을 볼 때 하나의 스케일 또는 현재의 스케일 만을 보는 것이 아니라 대상이 가질 수 있는 다양한 스케일의 범위를 한꺼번에 표현하는 공간이다.

 

Scale space 이론은 대상의 구조를 여러 스케일에 걸쳐 다루기 위한 공식화된 이론으로서, 대상을 스케일 축을 파라미터로 하는 공간상의 한 점(instance)으로 표현한다. 이미지의 경우 이미지 f(x,y)에 대한 scale space 표현은 Gaussian blurring(2D Gaussian filter와의 convolution)을 통해 생성되는 일련의 스무딩(smoothing)된 이미지 fσ(x,y) 들로 정의된다.

 

 --- (1)

 

--- (2)

 

식 (1)에서 scale parameter σ는 convolution에 사용된 Gaussian 필터의 표준편차에 해당하며, σ=0일 때 f0(x,y) = f(x,y)로 정의된다.

 

<그림 4> Scale Space 예 (그림출처: 위키피디아)

 

☞ 참고로 원래는 t = σ2을 scale parameter로 잡고 scale space를 L(x,y;t) = g(x,y;t)*f(x,y)와 같이 표기하는 것이 보다 일반적이다. 하지만 이는 단지 표기상의 차이일 뿐이며 σ를 scale parameter로 표기하는 것이 보다 직관적이라 생각되어 이 글에서는 식 (1)과 같이 scale space를 정의한다.

 

이와 같이 어떤 이미지의 scale space는 Gaussian 블러링을 통해 생성되는 일련의 이미지들로 구성된다. 그런데 이렇게 블러링된 이미지가 스케일과 무슨 관계가 있을까?

 

이미지의 스케일(scale)을 변화시키는 방법은 앞서 봤듯이 이미지를 확대시키거나 축소시키는 것이다. 그런데, 이미지를 직접 확대, 축소시키지 않고도 스케일을 변화시키는 방법이 바로 이미지를 블러링(blurring)시키는 것이다. 이미지를 블러링시킬수록 세부적인 detail이 사라지고 보다 큰 스케일에서의 이미지의 구조를 파악할 수 있게 된다.

 

그렇다면 블러링된 이미지의 스케일 값은 얼마일까? 블러링된 이미지의 스케일은 사용된 Gaussian 필터의 시그마(σ)에 비례한다. 즉, 만일 σ2 = kσ1라면 fσ2(x,y)의 스케일은 fσ1(x,y)의 스케일의 k배가 된다. 그래서 위 <그림 4>는 scale 값이 계속 2배씩 증가되는 예에 해당한다.

 

☞ 스케일이 2배가 되는 지점은 앞서 설명한 Gaussian pyramid를 생성할 때 중요한 포인트가 된다. 왜냐하면 스케일이 2배가 되는 지점에서 이미지의 크기를 1/2로 축소하면 다운 샘플링에 따른 정보의 손실을 최소화하면서 해당 스케일의 이미지 구조를 유지할 수 있기 때문이다.

 

이미지를 블러링시키는 방법은 여러가지가 있지만 그중 Gaussian 필터를 이용한 방법만이 제대로된 scale space를 생성할 수 있는 유일한 방법이라고 한다 (Tony Lindeberg, "Scale-space theory: A basic tool for analyzing structures at different scales"). 그 기준은 블러링 과정에서 원래 이미지에 없던 새로운 구조가 나타나서는 안되며 coarse한 스케일에서의 이미지 구조는 원래의 fine 스케일에 있던 이미지의 구조에 대한 일종의 단순화(simplification)이어야 한다는 것이다. 그리고 이러한 조건을 만족하는 필터는 Gaussian 필터가 유일하다고 한다.

 

<그림 5> Gaussian Blurring (그림출처: Tony Lindeberg, "Scale-space theory: A basic tool for analyzing structures at different scales")

 

<그림 5>의 왼쪽 그림을 보면 Gaussian 블러링에 따라 점차적으로 큰 스케일의 구조만 남게 됨을 볼 수 있다. 또한 오른쪽 그림은 블러링에 따른 신호의 극대, 극소점의 위치변화를 보여주는데, 블러링에 따라 그 위치가 변함이 없음을 보여준다. 즉, Gaussian 블러링이 신호의 구조를 보존함을 보여준다.

 

또한 Gaussian 필터는 이미지의 구조를 유지시키는 외에도 scale space 생성에 매우 유용한 성질을 가지고 있다. 그것은 작은 크기의 Gaussian 필터를 중첩하여 적용(convolution)하면 큰 크기의 Gaussian 필터를 적용한 것과 동일한 효과를 갖는다는 것이다.

 

 --- (3)

 

식 (3)을 이용하면 scale space를 생성할 때 작은 크기의 Gaussian 필터들을 중첩하여 적용함으로써 일련의 scale space를 생성할 수 있게 된다. 즉, f(x,y)에 gσ(x,y)를 적용하면 fσ(x,y)가 나오고, fσ(x,y)에 다시 gσ(x,y)를 적용하면 fsqrt(2)σ(x,y), 여기에 다시 gsqrt(2)σ(x,y)를 적용하면 f(x,y), ... 와 같은 식으로 scale space를 생성할 수 있다.

 

 

4. Scale Space와 Octave 표현

 

Scale space 자체는 연속적으로 정의되지만 현실적으로 모든 스케일에 대해 분석하는것은 불가능하다. 따라서scale space를 영상처리에 활용하기 위해서는 스케일 축을 따라서 일정한 간격으로 샘플링된 scale space를 생성해야 한다. 이 때의 샘플링 간격을 scale step이라 부르는데 흔히 사용되는 scale step은

이다. 이 때, scale step은 +, -의 개념이 아니라 *, /의 개념임에 주의해야 한다. 즉, scale step을 s라 하면 σ, s*σ, s*s*σ, ...와 같은 형태로 샘플링이 이루어진다.

 

또한 scale space를 생성할 때, 메모리의 효율성과 연산의 효율성을 위해서 Gaussian 블러링과 다운 샘플링(sub sampling)을 혼용하여 사용하는 것이 일반적이다. 즉, Gaussian 필터를 단계적으로 적용하여 이미지의 스케일을 증가시켜 가다가 스케일이 2배가 되는 시점에서 1/2 크기로 다운 샘플링한다. 이후 다운 샘플링된 이미지에서 다시 Gaussian 필터를 적용해 가는 방식이다. 이 때, 스케일이 2배가 되기까지 Gaussian 블러링으로 생성되는 스케일 공간을 octave라고 부르며 scale step이 작을수록 한 octave를 구성하는 이미지의 개수가 많아진다.

 

<그림 6> scale space의 octave pyramid 샘플링 예

 

 

5. Scale Space의 활용

 

Scale space를 구축하는 목적은 다양한 스케일에 걸쳐서 이미지 특성을 분석하기 위함이다. 그런데 scale space 이미지에 직접 어떤 연산자(operator)를 적용하는 것은 몇가지 문제점이 있다.

 

Scale space 이론에 의해 생성되는 이미지들은 기본적으로 블러링만 되었을 뿐 원래 이미지와 크기(resolution)는 동일한다. 따라서 스케일별 특성을 분석하는 것이 목적이기 때문에 모든 이미지에 고정 크기의 연산자를 적용하는 적은 적합하지 않다. 그렇다고 이미지마다 서로 다른 크기의 연산자를 적용하는 것은 구현적인 측면에서 적합하지 않다. 또한 스케일이 원본 이미지의 정수배인 경우에는 다운 샘플링된 이미지에 연산자를 적용하면 되지만 정수배가 아닌 경우에는 이러한 적용도 쉽지 않다.

 

Scale space 관련하여 여러 자료를 찾아보았지만 이 문제에 대해 명확하게 설명되어 있는 자료는 찾지 못하였다. Twan Maintz의 저서 "Digital and Medical Image Processing" 9장(p.251)에 보면 differential operator를 사용하면 이 문제를 해결할 수 있다고 언급되어 있지만 왜 그런지에 대해서는 설명되어 있지 않다.

 

어쨌든 실제로 scale space가 활용되는 방식은 고정된 크기의 연산자를 모든 스케일의 이미지에 동일하게 적용하는 것이다. 그리고 이러한 연산자로는 그레디언트(gradient), 라플라시안(Laplacian), 헤시안(Hessian) 등과 같은 1차 또는 2차 미분을 기반으로 한 연산자가 주로 이용된다.

 

미분 연산자는 영상의 밝기변화 특성을 분석하기 위한 연산자로서 edge 검출에 사용되는 Sobel 필터 등이 대표적인 미분 연산자이다. 그런데, 미분 연산자는 블러링된 이미지에 미분을 적용하는 것과 Gaussian 필터에 미분을 적용한 후 블러링시키는 것이 동일한 결과를 갖는 매우 좋은 특성을 가지고 있다.

 

 --- (4)

 

즉, scale space 상의 이미지들에 직접 미분 연산자를 적용하는 것(좌변)과 Gaussian 필터에 미분을 적용한 후 convolution을 시키는 것(우변)이 동일하다는 것이다. 식 (4) 좌변과 같이 디지털 이미지에 직접 미분을 적용하는 것은 기본적으로 잘 정의되지 않는 ill-posed 문제이지만 우변과 같이 Gaussian 함수의 미분을 구하는 것은 수학적으로 잘 정의되는 well-posed 문제이다. 또한 직접 미분을 구하지 않고 Gaussian 필터에 미분을 적용한 후 블러링시키는 것이 계산상으로도 이득이다. 그리고 이러한 성질은 1차 미분 뿐만 아니라 모든 차수의 미분에 대해 성립한다.

 

Edge, ridge, corner, blob 등과 같은 영상 feature들은 대부분 이러한 미분 연산자를 기반으로 검출될 수 있다. 따라서 실제 scale space의 주 응용은 미분 연산자를 기반으로 edge, ridge, corner, blob 등과 같은 영상 특징들을 여러 스케일에 걸쳐 분석하는 것으로 볼 수 있다.

 

예를 들어, scale space 상에서 Laplacian을 이용하여 blob을 찾는 문제를 생각해 보자. 기본적으로 Laplacian은 이미지의 밝기 변화의 곡률(curvature)를 계산해 주는 연산자로서 이미지의 밝기가 지역적으로 극대(극소)인 점에서 최소(최대)값을 갖는다.

 

--- (5)

 

이 때, scale space 상의 이미지들에 대한 Laplacian은 원본 이미지에 LoG(Laplacian of Gaussian) 필터를 적용함으로써 얻어질 수 있다.

 

<그림 7> Gaussian 블러링(상단 그림)과 LoG 결과 (하단 그림)

 

<그림 7>에서 윗쪽 그림은 검은색 blob 이미지에 대한 Gaussian 블러링 결과이고 아래쪽은 윗 이미지에 3 x 3 Laplacian을 적용한 결과 이미지이다. 그림에서 볼 수 있듯이 원본 스케일에서는 blob 특성이 Laplacian으로는 잘 드러나지 않는다. 하지만 점차 이미지를 블러링시킴에 따라서 blob 영역의 밝기 변화가 완만한 곡선을 이루면서 blob 중심에서 Laplacian 값이 극대가 되는 순간이 존재한다. 그리고 이 순간을 넘어서서 더욱 더 블러링을 시키게 되면 그 곡선이 점차 완만해지기 때문에 Laplacian 값 또한 줄어들게 된다. 이 때, Laplacian 값이 극대가 되는 이미지 스케일은 blob의 크기에 비례하여 증가하므로 어떤 스케일 이미지에서 Laplacian이 극대가 되었는지를 알면 blob의 크기(경계)를 결정할 수 있게 된다.

 

이와 같이, 이미지에서 Laplacian을 이용한 blob 검출은 각각의 스케일 이미지 내에서 뿐만 아니라 스케일 축을 따라서도 Laplacian 값이 극대가 되는 지점을 찾음으로써 검출이 가능하다 (blob의 위치뿐만 아니라 크기까지 결정할 수 있음).

 

 

6. Scale Invariance

 

사실 scale space의 가장 큰 활용은 영상에서 스케일에 불변(scale invariant)인 특징을 뽑는 것으로 볼 수 있다. 스케일에 불변인 특징이라 하면 이미지를 어떤 스케일에서 찍었든 간에 (즉, 카메라가 물체 가까이서 찍었든 멀리서 찍었든) 동일한 물체 지점에 대해 계산된 영상 특징은 서로 동일해야 함을 의미한다. 그런데, 이미지의 스케일이 바뀌면 계산된 영상 특징은 당연히 바뀌기 때문에 일반적으로는 scale invariance를 만족시키기 어렵다. 하지만 다음과 같이 scale space 이론을 활용하면 scale invariant한 영상 특징 추출이 가능해진다.

 

그 방법은 먼저 현재 이미지 내에서뿐만 아니라 스케일 축 상에서 특징점(keypoint)을 찾은 후, 해당 특징점이 발견된 스케일 이미지에서 영상 특징을 계산하는 것이다. 이러한 영상 특징점(keypoint)으로는 카메라 시점이 바뀌어도 쉽게 반복 검출이 가능한 코너점(corner point)이 주로 사용된다(영상 특징점(keypoint) 추출방법 글 참조). 코너점을 찾는 방법에는 여러 가지가 있지만 그중 한 방법은 Laplacian이 극대 또는 극소인 점을 찾는 것이다. 즉, 이미지 내에서 뿐만 아니라 스케일 축을 따라서도 Laplacian이 극대 또는 극소가 되는 점을 찾으면 해당 점이 스케일에 불변인 특징점이 된다. 그리고 이렇게 찾아진 특징점 위치 및 스케일에서 영상 특징량(descriptor)을 계산하면 스케일에 불변인 영상 특징량이 된다. 이렇게 찾아진 특징점 및 특징량이 스케일에 불변인 이유는 입력 이미지가 어떤 스케일에서 촬영되었다 하더라도 스케일 공간 탐색을 통해서 해당 스케일을 찾아냄으로써 동일한 특징량 계산이 가능해지기 때문이다.

 

by 다크 프로그래머