[Digital Image Processing] 09. Geometric Processing

해당 글은 건국대학교 김은이 교수님의 디지털 영상 처리 수업 내용을 정리한 글입니다.

 

Geometric Operations

 

일반적인 영상 처리는 I(x,y)에서 I'(x,y)로 픽셀 값만 변하지만, 기하학적 처리는 I(x,y)에서 I(x',y')으로 좌표 자체가 이동합니다. 입력 좌표 (x,y)를 새로운 좌표 (x',y')으로 매핑하는 함수 T를 정의하는 것이 목표입니다:

geometric operation

 

기하학적 변환에는 네 가지 기본 변환과 행렬이 존재합니다:

• Translation(이동): 단순히 더하기 연산입니다.
• Mirroring(미러링): 축 대칭입니다. x축 대칭은 y좌표의 부호를, y축 대칭은 x좌표의 부호를 반대로 뒵집고 원점 보정을 위해 x0, y0 등을 더합니다.
• Scaling(스케일링): 곱하기 연산입니다.
• Rotation(회전): 삼각함수를 이용한 선형 변환입니다.

Basic Geometric Transformation. Rotation의 경우 counter clock-wise 방향으로 theta만큼 회전시키는 행렬입니다. 만약 clock-wise 방향으로 theta만큼 회전하고 싶다면, theta에 -를 붙인 행렬을 이용해야 합니다.

 

Rotation

 

이때 기본 회전 수식은 원점(0,0)을 기준으로 돕니다. 하지만 보통 이미지를 회전할 때는 이미지의 중심(center)을 축으로 돌리고 싶어 합니다. 따라서 1) 중심점을 원점으로 이동시킨 후(X - CenterX, Y - CenterY), 2) 회전 행렬을 적용합니다. 3) 그 후 다시 원래 위치로 이동시킵니다(결과에 +CenterX, +CenterY 를 수행함):

rotation

 

다음은 회전 행렬의 유도 과정입니다:

rotation

 

Shift(Translation)

 

이미지를 이동시키면 원래 이미지 경계 밖으로 나가는 부분은 잘리고, 빈 공간이 생깁니다. 이를 프로그래밍을 할 때, 단일 버퍼를 사용하면 안됩니다. 원본 배열 A의 값을 읽어서 이동한 위치에 다시 A에 덮어쓰면, 나중에 읽어야 할 원본 데이터가 이미 덮어씌워져 오염됩니다. 따라서 원본을 저장할 메모리와 결과를 저장할 메모리를 따로 두거나, 덮어쓰지 않는 방향(예: 역순)으로 처리해야 합니다:

shift example

 

Mirroring

 

다음은 미러링의 예시입니다:

example mirroring

 

Affine Transformation

 

Affine Transformation은 직선을 직선으로, 평행선을 평행선으로 유지하는 변환을 말합니다. 회전, scaling, shearing, shift 모두 affine transformation에 포함됩니다.

Affine transformation function T()

 

이때 각각의 transformation function T()는 다음과 같이 정의됩니다:

T()

 

Tx()같은 경우는 x와 y의 linear combination과 m02(shift를 위한 계수)의 합으로 이뤄집니다. Ty()도 마찬가지입니다. 이를 행렬로 나타낸 것을 Homogeneous transformation matrix라고 부릅니다.

 

회전/스케일링은 x와 y좌표의 선형 조합으로 구현할 수 있습니다. 따라서 이는 2x2 행렬의 곱셈으로 표현할 수 있지만, 이동(shift)는 덧셈입니다. 수학적으로 곱셈과 덧셈이 섞이면 여러 변환을 하나의 행렬로 합치기 어렵습니다. 따라서 2차원 좌표 (x,y)에 가상의 차원 1을 추가하여 (x,y,1)로 만듭니다. 이렇게 하면 덧셈이었던 이동 연산도 3x3 행렬의 곱셈으로 흡수시킬 수 있습니다. 이를 통해 모든 기하학적 변환을 행렬 곱 하나로 통일할 수 있습니다:

homogeneous transformation matrix

 

다음은 이동, 스케일링, 회전, 전단(shear) 변환이 3x3 행렬 내에서 어떤 계수(a0, ..., b2)를 건드리는지를 정리한 표입니다:

homogeneous tranformation coefficient table

 

다음은 각 변환들의 예시입니다:

ex

 

homogeneous matrix를 사용하면, "회전하고 나서 이동한다"라는 복합 연산을 행렬의 곱셈으로 미리 계산해둘 수 있습니다(여러개의 geometric transformatioon에 대한 변환 행렬들을 하나 하나 처리(곱셈)하는 것 보다는 한 번의 행렬로 미리 만들어둔 다음 처리하는 것이 계산효율적이며, buffer도 한 번만 사용하기 때문에 메모리 효율적이다). 하지만 이때 행렬 곱셈은 교환 법칙이 성립하지 않는다는 것을 유의해야 합니다. 따라서 변환 순서에 맞춰 행렬을 곱하는 순서를 주의해야 합니다:

shearing + rotation

 

Issues w/ geometric ops

 

기하학적 변환을 코드로 짤 때 중요한 구현상의 딜레마가 존재합니다:

• source image와 destination image의 크기가 다를 수 있습니다. 이는 이미지의 크기를 맞춤으로써 해결할 수 있습니다.
• output location이 실수가 아닐 수 있습니다. 하지만 모니터의 픽셀은 정수 좌표에만 찍힐 수 있는데, 이를 어떻게 처리할 지 정해야합니다.
• input을 output에 매핑하는 과정에서 gap이 발생할 수 있습니다.

 

예를 들어, 이미지를 clock-wise로 30도 회전하는 경우:

ex

 

output의 좌표가 float입니다. 이는 실제 output의 좌표로서 사용할 수 없기 때문에 후처리를 해줘야합니다. 위에서 제기한 딜레마를 두 개로 정리하면 다음과 같습니다:

• Dimensionality: output image의 크기가 처리된 이미지를 담아내기 충분히 크기 않을 수 있습니다.
• Tranformed locationos are not integers: 만약 output image의 좌표가 실수가 아니라면 output image의 어디에 해당 값을 매핑해야 하는가?

 

이미지를 회전하는 경우 destination이 회전한 전체 이미지를 포함하지 않을 수 있습니다. 이런 경우 처리된 이미지에 맞게 이미지의 width와 height를 조절함으로써 dimensionality 문제를 해결할 수 있습니다:

dimensionality problem

 

Mapping problem

 

우선 처리된 이미지의 픽셀값이 integer value가 아니라면, 반올림을 통해 억지로 integer 좌표로 변환할 수 있습니다. 원본 픽셀 (x,y)를 하나씩 가져와서 변환 공식에 넣고, 나온 결과 (x',y')를 반올림하여 결과 영상에 찍으면 아래의 그림처럼 구멍이 생길 수 있습니다:

mapping problem

 

이를 forward mapping이라고 합니다. 우리가 원래 알고있는 transformation의 방향으로 처리된 좌표값을 찾은 후, interger value가 아니라면 rounding을 하는 것입니다. 예를 들어, 이미지를 2배 확대한다고 했을 때, 원본 (0,0) -> (0,0), (1,0) -> (2,0)이 됩니다. 결과 영상의 (1,0) 좌표는 아무도 채워주지 않아 비어있게 됩니다. 아래는 회전하는 경우의 gap이 발생하는 예시입니다:

image rotation example

 

하지만, 이는 poor results(gap으로 인해)를 생성할 수 있으므로 좋은 방법은 아닙니다. 따라서 이를 해결하기 위해 backward mapping을 수행할 수 있습니다.

 

Backward mapping

 

이는 결과 영상의 픽셀 (x',y')을 기준으로, 원본의 어디에서 왔는지를 반대로 묻는 것을 말합니다. transformation matrix의 역행렬을 이용합니다:

Backward Mapping

 

이는 결과 영상의 모든 픽셀을 순회하며 원본을 찾기 때문에, 빈 구멍이 절대 생기지 않습니다. 하지만 역변환된 원본 위치 (x,y)가 (10.5, 20.7)과 같은 실수가 나올 수 있습니다. 원본 이미지에는 정수 좌표만 있기 때문에, 해당 간격을 극복하기 위해서는 interpolation을 사용할 수 있습니다:

backward mapping

 

Interpolation

 

실수 좌표 (u,v)에 있는 가상의 픽셀 값을 주변 정수 픽셀들을 이용해 추정하는 방법입니다. scaling을 할 때도 interpolation을 사용해야하는데, scale을 줄이는 경우에는 interpolation이 반드시 필요하지는 않습니다(interpolation 연산 자체가 계산 비용이 비싸기 때문에, averaging 정도를 이용합니다). 반면, scale을 늘리는 경우에는 interpolation이 필요합니다.

 

interpolation에는 종 4가지의 방법이 존재합니다:

• Nearest Neighbor interpolation: (u,v)에서 가장 가까운 정수 좌표 픽셀을 그냥 가져옵니다.
• Bilinear interpolation: 주변 4개의 픽셀(2x2)을 사용합니다. x축 방향으로 두 번 선형 보간하고, 그 결과를 y축 방향으로 보간합니다.
• Cubic Convolution interpolation: 주변 16개의 픽셀(4x4)을 사용합니다.
• B-Spline interpolation: 종 모양(Bell-shaped)의 부드러운 기저 함수를 사용합니다.

 

Nearest Neighbor Interpolation

 

destination location (x',y')에 해당하는 backward source location (x,y)가 있다고 했을 때, I(x',y')값을 I(round(x), round(y))로 설정합니다:

NN interpolation

 

이는 다른 보간법들에 비해 계산 효율적이지만, poor quality를 생성합니다. 또한 jagging 현상이 발생할 수 있습니다:

jagging

 

위 그림은 5배 scaling up하는 경우의 예시입니다. 검은색 화살표는 source image pixel value이고, 회색 화살표는 destination image pixel value입니다. NN 방법을 사용하는 경우, 그냥 가장 가까운 source image pixel value를 복사하는 것이기 때문에, 아래의 (c)와 같은 결과가 발생할 수 있습니다.

ex

 

Bilinear Interpolation

 

양선형 보간법은 (x,y)의 주변 4개 pixel값들을 가중 합하여 보간하는 방법입니다. 이때 (x,y)의 거리에 따라서 반영되는 수준이 달라집니다(거리가 가까우면 높은 가중치, 거리가 멀면 낮은 가중치):

Bilinear Interpolation. 이때 보간식은 최대한 곱셈의 개수를 줄이기 위해서 해당 식을 사용한 모습입니다.

 

이는 NN 방식보다 훨씬 더 부드러운 영상을 만들어내지만, 그 만큼 계산 비용이 든다는 단점이 존재합니다. 따라서 NN 방식과 같은 jagging 현상이 줄어듭니다:

ex

NN vs. Bilinear

 

High-order Interpolation

 

이는 주변 16개의 점들을 이용하기 때문에 계산 비용이 비싸지만, 어디든 continuous한 결과를 볼 수 있다는 장점이 있습니다. 이는 비선형 보간 함수(interpolation function)을 사용하여, 행 축으로 4번의 보간, 열 축으로 1번의 보간을 통해 구현됩니다:

high-order interpolation

 

아래는 cubic convolution interpolation에서 사용하는 보간 함수의 모습입니다. 이때 a를 조절함으로써 sharpening 정도를 조절할 수 있습니다(음수가 들어가 있기 때문에).

cubic convolution interpolation

 

다음은 cubic convolution interpolation의 코드입니다:

algorithm