[Computer Vision] Image resizing

해당 글은 건국대학교 지서원 교수님의 컴퓨터 비전 수업 내용을 정리한 글입니다.

 

Interpolation.

 

A note on coordinates in images.

 

위 그림은 디지털 이미지의 가장 기본적인 표현 방식입니다. 이미지는 rows와 columns로 구성된 grid이며, 각 pixel을 불연속적인 정수 좌표를 가집니다. 이 pixel을 단순한 사각형 칸이 아니라, 점의 집합으로 해석하면 다음과 같습니다:

A note on coordinates in images.

 

pixel의 실제 데이터는 해당 정수 좌표 grid의 center에 위치한다고 가정합니다. 이렇게 되면 다음과 같이, 실제 연속적인 물리적 공간인 continuous coordinate system으로 옮겨갈 수 있습니다:

continuous coordinate system.

 

좌표계의 원점과 축을 정의하고, pixel (x,y)의 값은 정확히 좌표 점 (x,y)에 중심을 둡니다. 그리고 격자의 중심점이 아닌, (-0.25, -0.25)와 같은 실수 좌표점들을 정의할 수 있으며, 이미지 좌표를 변경(예: 회전, 스케일링)할 때 이러한 실수 좌표계가 매우 편리합니다:

A note on coordinates in images

 

그렇다면, 이미지는 정수 좌표에만 픽셀 값을 가지고 있는데, 정수가 아닌 실수 좌표(non-integer point)의 픽셀 값은 어떻게 알아낼 수 있는가? 라는 의문이 생깁니다. 이는 interpolation 기술을 통해 달성할 수 있으며, target 이미지를 원본 이미지로 역방향 매핑(backward mapping)할 때 계산된 원본 좌표는 대부분 소수점을 포함하며, 이 빈 공간의 값을 수학적으로 추정하는 과정을 말합니다.

 

* 이때 격자의 중심점들 안에 있지 않은 점들(예: 위 예시에서의 (-0.25, -0.25))은 extrapolation을 사용합니다.

 

Nearest neighbor (NN) interpolation.

 

가장 직관적으로 떠오르는 방식입니다. 이는 target 실수 좌표에서 가장 가까운 정수 픽셀의 값을 그대로 가져와 설정합니다:

NN interpolation.

 

하지만 이는 다음과 같이 이미지가 각지고 픽셀이 깨져 보이는 blocky 현상이 발생합니다. 이 함수는 step function의 형태를 띠므로, 거의 모든 지점에서 미분값이 0이거나 미분이 불가능합니다. 따라서 feature의 미세한 변화가 결과에 반영되지 않아 신경망의 역전파 시 gradient의 흐름을 단절시킬 수 있습니다:

NN interpolation, blocky

 

Bilinear interpolation.

 

Bilinear interpolation.

 

NN interpolation의 단점을 보안하는 방식이며, 목표 실수 좌표를 둘러싼 4개의 인접 정수 픽셀을 모두 고려하여 값을 추정합니다. 이는 NN interpolation 보다 시각적으로 훨씬 부드러운 이미지를 생성합니다:

Bilinear interpolation.

 

Bilinear interpolation은 다음과 같은 순서로 동작합니다:

find 4 neighbor inter pixels

• 인접 픽셀 찾기: 실수 좌표 (x,y) 주변을 둘러싼 4개의 정수 좌표 픽셀을 찾는 과정입니다. 내림 함수를 사용하여 target 실수 좌표의 왼쪽 위(x1), 오른쪽 위(x2), 왼쪽 아래(x3), 오른쪽 아래(x4)에 위치한 정수 좌표를 정의합니다.

compute rectangle areas

• 면적 기반 가중치 연산: 4개의 정수 픽셀을 꼭짓접으로 하는 사각형 안에서, 실수 좌표 (x,y)를 기준으로 4개의 작은 직사각형 면적(w1, w2, w3, w4)을 계산합니다. 핵심은 특정 정수 픽셀의 가중치로 그 픽셀과 대각선으로 마주보는 직사각형의 면적으로 사용한다는 점입니다. 목표 좌표가 정수 픽셀에 가까울수록 반대편 대각선 방향의 면적이 커지게 됩니다. 즉, 거리가 가까울수록 해당 픽셀의 데이터가 최종 결과에 더 큰 비율로 반영되도록 하는 매우 직관적이고 합리적인 가중 평균입니다.

weighted sum based on area of opposite rectangle areas.

• 가중 합산 및 최종 공식: 앞서 구한 4개 픽셀 값(x_i)에 대각선 반대편 면적 가중치 w_i를 각각 곱하여 모두 더합니다:

weighted sum based on area of opposite rectangle areas.

 

interpolation의 종류는 매우 많으며, 다음과 같습니다:

many types of interpolations.

 

이는 interpolation 방법에 따른 결과 이미지의 차이입니다:

ex.

 

Image resizing.

we want to make image larger.

 

이미지를 확대하기 위한 3단계 알고리즘 프로세스는 다음과 같습니다:

1. 목표 해상도 크기의 새로운 빈 이미지를 생성합니다.
2. 새 이미지의 좌표계와 원본 이미지의 좌표계를 수학적으로 매칭시킵니다.
3. 새 이미지의 픽셀 좌표를 순회하며, 해당 좌표를 원본 이미지의 연속 좌표계로 역방향 매핑(map to old coordinate)한 뒤, interpolation을 통해 픽셀 값을 채워 넣습니다.

 

구체적인 이해를 돕기 위해 4x4 이미지를 7x7 이미지로 확대하는 예시를 들겠습니다. 다음은 1단계 규칙에 따라 7x7 크기의 새로운 빈 격자(grid)를 준비합니다:

create new image

 

2단계 좌표계 매칭을 위해, 원본 이미지의 좌표(검은색 선, 0~3)와 새로운 이미지의 좌표(핑크색 선, 0~6)를 겹칩니다. 그리고 픽셀의 값은 그 픽셀 공간의 정중앙에 위치한다는 규칙을 적용하면 다음과 같습니다:

match up coordinates

 

새로운 이미지(7x7)의 픽셀 좌표(xnew)를 원본 이미지(4x4)의 좌표(xold)로 변환하기 위한 1차 선형 방정식 x_old = a*(x_new) + b를 수립하고, 경계 조건(boundary condition)을 이용해 선형 방정식의 두 미지수(a,b)를 결정합니다. 이때 경계 조건이란, 이미지의 양 끝점, 즉 가장자리 픽셀이 차지하는 물리적 공간의 외곽선을 일치시키는 것을 말합니다(왼쪽 위의 경계는 늘 항상 (-0.5, -0.5)로 동일하며, 오른쪽 아래의 경계는 new(6.5, 6.5) -> old(3.5, 3.5)입니다).

 

경계 조건에 따라 도출된 두 좌표를 연립방정식으로 풀면 기울기 a = 4/7, 절편 b = -3/14가 도출되어 최종 매핑 공식 x_old = 4/7*(x_new) - 3/14를 완성합니다:

system of equation

system of equation

 

생성된 빈 7x7 이미지의 각 픽셀(정수 좌표)을 순회하며, 원본 좌표계에서의 위치를 찾습니다. 아래의 그림은 새로운 이미지의 특정 픽셀 좌표 (1,3)의 픽셀 값을 구하는 과정입니다:

iteration over new points

 

내부의 모든 픽셀에 대해 interpolation을 마친 후, 외곽 가장자리 픽셀들에 대한 처리를 진행합니다. x_new = 0과 같은 가장자리 픽셀을 변환 공식에 넣으면 x_old = -3/14와 같이 원본 이미지의 0~3 인덱스 범위를 벗어나는 좌표가 나옵니다. 이 경우 4개의 인접 픽셀을 구할 수 없습니다. 따라서 padding을 사용하여 값을 채워 넣습니다:

fill in the rest: on outer edges use padding

 

다음은 결과 이미지 입니다:

resize 4x4 -> 7x7

 

Downsampling

resize 448x448 -> 64x64

 

이미지를 축소하고 싶을 때와 확대할 때의 알고리즘은 동일합니다(downsampling을 통해 저장공간을 줄일 수 있고, computation cost를 줄일 수 있습니다. 또한 이미지의 details 보다는 semantic한 정보에 집중하기 위해서 downsampling할 수 있습니다). 다음은 448x448 자전거와 개 이미지를 64x64 이미지로 축소한 예시입니다:

ex

 

결과적으로 다음과 같은 이미지가 만들어집니다:

result

 

결과 이미지는 정보 손실이 너무 큽니다. 다음과 같은 3x3 격자 안에는 분명히 초록색 잎이 대부분이지만, 단순 샘플링을 하면 우연히 그 자리에 있던 검은색 픽셀 하나만 대표로 뽑히게 되며, 이로 인해 해당 격자의 특성을 잃어버리고, 더 나아가서 이미지 전체의 특성을 잃어버릴 수 있습니다. 이렇게 노이즈가 튀는 현상을 Aliasing이라고 부릅니다:

Image downsampling and aliasing effect

 

Averaging.

 

더 나은 downsampling 방법은 averaging입니다. 픽셀 하나만 무작위로 고르는 것이 아니라 주변 픽셀들의 값을 모두 더해 평균을 내면 정보 손실을 줄일 수 있습니다. 이는 결국 먼저 smoothing을 한 다음 sampling하는 것입니다. 단순 평균 외에도 gaussian filter 등 다양한 smoothing filter를 사용할 수 있습니다:

we can use gaussian filtering

 

다음은 반 고흐의 초상화를 예시로, 원하는 해상도가 될 때까지 smoothing -> downsampling 과정을 반복하는 구조입니다:

smoothing and downsampling

 

다음은 smoothing 없이 downsampling만 한 결과와 smoothing을 거친 후 downsampling을 거친 결과입니다. 단순 downsampling은 픽셀이 깨지고 형태를 알아보기 힘든 반면, smoothing을 거치면 detail은 흐려지더라도 전체적인 형태와 색감은 안정적으로 보존됩니다:

just downsampling vs. smoothing and downsampling

 

다음은 gaussian pyramid로, 512x512 해상도부터 8x8 크기까지 점진적으로 이미지를 줄여나가는 계층적인 구조를 보여줍니다. smoothing filter로 gaussian을 사용했기 때문에 이를 gaussian pyramid라고 부릅니다:

gaussian pyramid

 

만약 human detection을 한다고 가정했을 때, target image에는 여러 크기의 사람이 존재할 것입니다(멀리있는 사람은 작게 보이고, 가까이 있는 사람은 크게 보인다). 이 모든 사람들을 detection하기 위해, 사람 모양의 kernel(kernel과 target pattern과의 유사하면 convolution response가 크다는 것을 기억하자)을 사람 크기에 맞게 여러개를 만들어야합니다. 하지만 gaussian pyramid를 사용하면 여러 크기의 kernel을 사용하지 않아도 됩니다.

 

같은 크기의 kernel을 이용해 convolution을 수행했을 때, 만약 저해상도(예: 8x8)의 이미지에서 response가 크다면 해당 kernel이 큰 크기의 사람을 detection한 것이며, 고해상도(예: 512x512)의 이미지에서 reponse가 크다면 해당 kernel이 작은 크기의 사람을 detection했다고 판단할 수 있습니다. 그리고 그 결과를 원본 이미지(예: 512x512)로 크기에 따라 복원하면, 다양한 크기의 target pattern을 detection할 수 있습니다.