최근 Bag of Words (BoW) 기법에 대해 정리를 해 보려고 자료를 봤는데 생각보다 시간이 많이 걸렸습니다. 개념과 주요 접근법에 대해서만 정리하려고 했는데 어느 논문 하나에서 막히는 바람에 몇 주가 흘러버렸네요...

먼저 참고한 자료는 다음과 같습니다.

• 위키피디아: Bag of Words Model in Computer Vision (BoW에 대한 전반적인 내용)
• Li Fei-Fei, Rob Fergues, Antonio Torralba, "Recognizing and Learning Object Categories", ICCV 2005 short course (iccv 2005 best short course award)
• [Csurka04] G. Csurka, C. Dance, L.X. Fan, J. Willamowski, and C. Bray. "Visual categorization with bags of keypoints“, ECCV 2004. (기본적인 BoW 방법)
• [Lazebnik06] Lazebnik, S.; Schmid, C.; Ponce, J., "Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories“ CVPR 2006. (Spatial Pyramid Matching 기법)
• [Lampert08] C. H. Lampert, M. M. Blaschko, and T. Hofmann, "Beyond Sliding Windows: Object Localization by Efficient Subwindow Search" CVPR 2008. (ESS 기법, cvpr 2008 best paper award)

1. Bag of Words 기법

원래 Bag of Words 기법은 문서(document)를 자동으로 분류하기 위한 방법중 하나로서, 글에 포함된 단어(word)들의 분포를 보고 이 문서가 어떤 종류의 문서인지를 판단하는 기법을 지칭한다. 예를 들어, 어떤 문서에서 '환율', '주가', '금리' 등의 단어가 많이 나온다면 이 문서는 경제학에 관련된 문서로 분류하고 '역광', '노출', '구도' 등의 단어가 많다면 사진학에 대한 문서로 분류하는 방식이다.

영상처리, 컴퓨터 비전 쪽에서는 Bag of Words 기법을 주로 이미지를 분류(image categorization)하거나 검색(image retrieval)하기 위한 목적으로 사용하였는데, 최근에는 물체나 씬(scene)을 인식하기 용도로도 폭넓게 활용되고 있다.

<그림 1> 그림출처: Recognizing and Learning Object Categories (ICCV 2005 short course)

영상 분류를 위한 Bag of Words 방법은 먼저 영상에서 feature(주로 SIFT 등의 local feature)들을 뽑은 후, 이들 feature들을 대표할 수 있는 값(code)들로 구성되는 코드북(codebook)을 생성한다. 보통 코드북은 다수의 이미지들로부터 추출한 feature들 전체에 대해 클러스터링(k-means clustering)을 수행하여 획득한 대표 feature(각 cluster의 center)들로 구성된다. 이 코드북은 일종의 단어 사전(dictionary)으로 볼 수 있는데, 이 사전에는 가능한 모든 종류의 단어들이 포함되어 있는 것이 아니라 물체나 이미지를 분류하는데 있어서 중요하다고 생각되는 주요 단어들만이 포함되어 있는 점이 다르다. 코드북에 포함된 단어를 코드워드(codeword)라 부르는데, 코드북을 몇 개의 codeword로 구성할 지는 조절 가능한 파라미터로서 영상 feature들을 몇개의 클러스터로 클러스터링할지에 따라 결정된다.

일단 코드북이 완성되면 이제 각각의 이미지들을 이 코드북을 이용하여 표현(representation)할 수 있게 된다. 어떤 이미지 A가 있을 때, 먼저 A로부터 feature들을 추출한 후 추출된 각각의 feature들에 대해 코드북 내에서 대응되는(가장 유사한) 코드워드(codeword)를 찾는다. 그리고 이렇게 찾은 코드워드들의 히스토그램(histogram)으로 이 이미지의 특징을 표현한다 (그림 1).

이렇게 구한 코드워드의 히스토그램(각각의 코드워드가 이미지에서 몇번 나타났는지 개수를 센 것)이 동일 종류의 물체에 대한 이미지들 사이에서는 유사하고 다른 종류의 물체에 대해서는 서로 다를 것이라는 것이 Bag of Words를 이용한 이미지 분류의 핵심 아이디어이다 (그림 2).

<그림 2> 그림출처: Recognizing and Learning Object Categories (ICCV 2005 short course)

이상의 Bag of Words 방법을 이용한 이미지 분류 과정을 정리해 보면 다음과 같다.

1. Feature Extraction: 이미지들로부터 feature를 추출한다 (SIFT 등)
2. Clustering: 추출된 feature들에 대해 클러스터링을 수행하여 클러스터 센터(center)들인 codeword들을 찾아낸다. 클러스터링 방법은 보통 k-means clustering이 사용된다.
3. Codebook Generation: 찾아진 codeword들로 구성되는 코드북을 생성한다. 코드북은 물체 클래스마다 생성하는 것이 아니라 <그림 2>의 예와 같이 공통적으로 하나만 생성되며 모든 클래스의 codeword들을 포함한다.
4. Image Representation: 각각의 이미지들을 codeword들의 히스토그램으로 표현한다. 이미지 하나당 하나의 히스토그램이 나오며 이 히스토그램의 크기(bin의 개수)는 코드북의 크기(코드북을 구성하는 codeword들의 개수)와 동일하다.
5. Learning and Recognition: BoW 기반의 학습 및 인식 방법은 크게 Bayesian 확률을 이용한 generative 방법과 SVM 등의 분류기를 이용한 discriminative 방법이 있다. Bayesian 방법은 물체 클래스별 히스토그램 값을 확률로서 해석하여 물체를 분류하는 것이고, discriminative 방법은 히스토그램 값을 feature vector로 해석하여 SVM(support vector machine)등의 분류기에 넣고 클래스 경계를 학습시키는 방법이다.

Bag of Words 기법은 통상적으로 local feature에 대한 히스토그램을 사용하지만 사실 어떤 영상 feature를 사용하느냐에 따라서 다양한 활용이 가능하다. 예를 들어, 색상(color)을 가지고 과일을 분류하는 문제를 생각해 보자. 먼저 분류하고자 하는 모든 과일 사진들을 한꺼번에 모아놓고 색상 값들을 추출한다. 패치(patch)단위로 색상을 추출할 수도 있고 픽셀 단위로 추출할 수도 있을 것이다. 이렇게 모은 색상값들을 모두 한데 놓고 클러스터링 알고리즘을 적용하여 대표 색상값들을 추출한다. 만일 분류하고자 하는 과일이 사과, 딸기, 수박, 오렌지 였다면 대표 색상값으로는 초록색, 빨강색, 노란색, 오렌지색 계열의 색상들이 뽑혔을 것이다. 이렇게 추출한 대표 색상들을 모아놓은 것이 코드북(codebook)이며 대표 색상을 100개 뽑았다면 이 코드북의 크기는 100이 된다. 만일 RGB 색상 모델을 사용한다고 했을 때, R, G, B 각각이 0 ~ 255 사이의 값을 가질 수 있기 때문에 가능한 모든 색의 종류는 256*256*256 = 16,777,216 가지나 된다. 하지만 이 코드북 상에는 과일색을 대표할 수 있는 색상 100개만이 포함되어 있다. 이제 어떤 새로운 이미지가 들어왔을 때 이 이미지의 색상값들을 코드북상에서 가장 유사한 대표색으로 대체한다. 즉, 입력 이미지 상의 모든 색들 각각을 코드북 상의 100개의 색상 중의 하나로 대체한다. 그리고 이렇게 대체된 색들의 히스토그램이 어떤 과일의 히스토그램과 유사한지를 비교함으로써 새로운 이미지가 어떤 과일인지를 판단한다.

2. Spatial Pyramid Matching

Bag of Words 방법[Csurka04]은 영상의 카테고리를 분류하는 용도, 주어진 이미지와 유사한 영상을 찾는 용도 등으로 성공적으로 적용되어 왔다. 또한 씬 매칭(scene matching) 등을 할 때 가능성이 적은 후보 영상들을 걸러내는 용도로도 효과적으로 활용되고 있다.

하지만 Bag of Words 방법은 기본적으로 feature들의 히스토그램(histogram)으로 이미지를 표현하기 때문에 feature들간의 기하학적인 위치 관계를 잃어버리는 문제점을 가지고 있다. 물론 동물 등과 같이 변형이 심한 물체를 인식하는데는 이 특성이 오히려 장점으로 작용하지만 자동차 등과 같이 형태가 고정된 물체의 경우에는 성능저하의 큰 요인중 하나가 될 수 있다.

2006년 Lazebnik 등이 발표한 Spatial Pyramid Matching 방법[Lazebnik06]은 이러한 Bag of Words 방법의 단점을 보완하기 위한 대표적인 방법 중 하나이다.

Spatial Pyramid Matching 방법은 이미지를 여러 단계의 resolution으로 분할한 후 각 단계의 분할 영역마다 히스토그램을 구하여 이들을 전체적으로 비교하는 방법을 일컫는다. 그림을 통해 보면 <그림 3>의 오른쪽 그림(level 0)은 이미지 전체에 대해서 하나의 히스토그램을 구하는 경우로서 전통적인 Bag of Words 기법이 이에 해당한다. 하지만 Spatial Pyramid Matching 방법에서는 여기에 추가적으로 이미지를 점진적으로 세분(level 1에서는 2x2로 분할, level 2에서는 4x4로 분할, ...)해 가면서 각각의 분할 영역마다 별도로 히스토그램을 구한 후 , 이들 히스토그램들을 전부 모아서 일종의 피라미드(pyramid)를 형성한다. 그리고 이렇게 형성된 히스토그램 피라미드들을 서로 비교함으로써 두 이미지의 유사도를 측정하는 방식이다.

<그림 3> 출처: [Lazebnik06]

물론 히스토그램을 구하는 과정은 Bag of Words 프레임워크 내에서 이루어진다. 즉, 미리 visual feature들에 대한 코드북을 생성한 후 이 코드북 코드들에 대해서 히스토그램을 생성한다 (위 그림 3은 코드북의 크기가 3인 경우의 예를 보여주고 있다). 유사도 측정에 대해 좀더 자세히 설명하면, 입력 이미지에 대해 level 0에서 생성한 히스토그램을 h0, level 1에서 생성한 히스토그램들을 순서대로 h1_0, h1_1, h1_2, h1_3, level 2에서 생성한 히스토그램들을 h2_0, h2_1, ..., h2_15라 하자(문제에 따라서 level 2까지만 구할 수도 있고 그 이상의 level에 대해서 히스토그램을 구할 수도 있다). 이 때, 모델(사전에 학습시킨) 이미지에서 계산한 히스토그램들을 h0', h1_0', h1_1', ..., h2_15'라 한다면 h0와 h0'의 유사도를 측정하고, h1_0와 h1_0'의 유사도를 측정하고, ... 와 같이 서로 대응되는 히스토그램의 유사도를 측정한 후 이들을 전체적으로 종합하여 입력 이미지와 모델(model) 이미지의 유사도를 측정하는 방식이다. 이 때, 높은 레벨(좀더 세분화된 분할)에서 측정된 유사도에 좀더 높은 가중치를 줌으로써 feature 분포의 공간(위치) 정보가 유지될수록 높은 점수를 주는 것이 일반적이다.

☞ Spatial Pyramid Matching에 대한 구체적인 수식이나 세부 구현에 대해서는 [Lazebnik06] 논문을 참조하기 바라며, 이러한 기법은 Bag of Words 프레임워크 내에서 뿐만 아니라 다른 일반적인 히스토그램 기반의 매칭 문제에도 유사하게 적용될 수 있음을 참고하기 바랍니다.

☞ 히스토그램 간의 유사도를 측정하는 방법에는 Bhattacharyya distance, Earth mover's distance (EMD), histogram intersection 등이 있는데, BoW 계열에서는 histogram intersection(두 히스토그램의 대응되는 bin의 최소값들을 전부 합한 값)이 주로 사용되는 것 같습니다.

3. Beyond Sliding Windows: Efficient Subwindow Search 기법

[Lampert08] C. H. Lampert, M. M. Blaschko, and T. Hofmann, "Beyond Sliding Windows: Object Localization by Efficient Subwindow Search" CVPR 2008

☞ 저를 몇 주간 괴롭히던 논문이자 2008년도 CVPR 학회에서 Best Paper 상을 탔던 논문입니다. 처음 논문을 읽으면서는 '이게 정말 이렇게 돼?', '이게 정말 된다면 엄청난 것 같은데' 하는 생각을 하였고 이제 어느정도 윤곽을 파악한 지금도 참 대단한 논문이라는 생각은 변치 않습니다. 다만 그 적용이 Bag of Words 계열의 문제에 국한된다는 점이 아쉬울 따름입니다.

Sliding Window 기법은 영상에서 물체를 찾는데 가장 기본적으로 사용되는 기법으로서, 영상에서 윈도우(window)를 일정한 간격으로 이동시키면서 윈도우 내의 영상 영역이 찾고자 하는 물체인지 아닌지를 판단하는 방법이다. 찾고자 하는 물체가 영상내 어떤 위치와 어떤 크기로 있는지를 모르기 때문에 가능한 모든 영상 위치 및 크기(image pyramid의 각 scale마다 sliding window 탐색을 적용)에 대해 물체의 존재 여부를 반복적으로 검사하는 exhaustive searching 방법이 Sliding Window 기법의 본질이다.

<그림 4>

이러한 sliding window 탐색은 거의 모든 영상 물체 탐색(object localization) 방법들에서 공통으로 사용하고 있지만 그 엄청난 반복 검사로 인해 알고리즘의 속도를 현저히 느리게 하는 가장 큰 주범이기도 하다.

그런데, [Lampert08] 논문에서는 이러한 반복 검사 없이도 sliding window 방법과 동일한 결과를 낼 수 있는 ESS 탐색 방법을 소개하고 있다 (논문 저자들은 이 탐색 방법을 Efficient Subwindow Search (ESS)라 부르기 때문에 여기서도 이후로는 ESS라 부른다).

Sliding Window 기법에서는 보통 어떤 평가함수 f가 있어서 윈도우 영역(r)마다 f(r)값을 조사하여 임계값(threshold value) 이상이면 대상 물체가 있는 것으로 판단한다. 하지만, ESS에서는 탐색영역 R에 대한 평가함수 F가 존재하여 F(R) 값이 큰 영역을 우선적으로 탐색하는 방법을 사용한다. 먼저, 처음에는 입력 영상 전체를 R로 놓고 F 값을 계산한다. 이후 탐색 영역을 둘로 분할한 후 각각에 대해 F 값을 계산하여 F 값이 최대인 영역을 선택하고 이를 다시 둘로 분할한다. 이와 같이 현재의 후보 영역들 중에서 F 값이 가장 큰 영역을 선택하여 그 영역을 둘로 분할하는 과정을 계속하다가 더이상 쪼갤 수 없는 단위 윈도우가 나올 때까지 진행하면 global optimum을 찾게 된다는 방식이다. 일종의 best first search 방식으로서, 이들의 주장이 맞다면 F 값이 높은 영역들에 대해서만 검사를 진행하기 때문에 훨씬 적은 수의 evaluation 만으로도 대상 물체를 찾을 수 있게 된다.

F 값을 어떻게 잡느냐를 알아보기 전에 이 논문에서 탐색영역을 어떻게 정의하고 또 어떻게 분할하는지를 먼저 살펴보자.

탐색영역 R은 사각형 윈도우들의 집합으로서 4개의 범위 값으로 정의되는데, 아래 그림과 같이 사각형을 정의하는 top, bottom, left, right 4개 값에 대한 상한과 하한으로 정의된다.

<그림 5> 출처: [Lampert08]

즉, 탐색영역 R은 어떤 영상 영역 내에 특정 범위의 모든(scale 변화까지 포함한) window들의 집합으로 볼 수 있으며 탐색영역 R을 둘로 분할하는 방법은 T,B,L,R 중에서 가장 범위가 큰 구간을 둘로(절반으로) 쪼개는 것이다. => 이렇게 탐색영역을 정의하는 방법도 참 기발한 것 같습니다.

다음으로 탐색영역 R에 대한 평가함수 F를 어떻게 잡느냐에 대해 살펴보자. F(R)은 직관적으로는 탐색영역 R 내에 물체가 있을 확률을 추정한 값으로 볼 수 있는데, 논문에서는 F가 다음의 두 가지 조건만 만족하면 앞서 설명한 best first search 방식으로도 sliding window search와 동일한 결과를 얻을 수 있다고 주장한다.

즉, i) F(R)은 탐색영역 R 내에서 가능한 모든 윈도우 r에 대한 f(r) 값들의 상한이 되어야 하고, 또한 ii) 만일 R이 단일 윈도우만으로 구성된 경우에는 해당 윈도우에 대한 f(r) 값과 동일한 값이 나와야 한다는 뜻이다.

f(r)은 어느 하나의 윈도우 영역이 물체인지 아닌지를 평가한 값이지만 F(R)은 R에 포한되는 다양한 윈도우 영역들에 대한 f(r) 값들을 직접 계산하지 않고도 이들의 상한을 추정한 값이다.

처음에는 위 조건이 무언가 문제가 있는 것이 아닌가 하는 생각이 들었다. 왜냐하면 global 해를 찾기 위해서는 다음과 같은 세번째 조건이 추가적으로 필요하다고 생각했기 때문이다.

그래야만, F(R) 값이 높은 R을 선택했을 때 실제 f(r) 값이 높은 윈도우가 포함된 R이 선택될 거라고 생각했다. 하지만 나중에는 조건 iii)은 전혀 필요가 없으며 조건 i) & ii) 만으로 충분함을 깨닫게 되었는데, 그 오해의 원인은 ESS 탐색 과정을 일부 잘못 이해하고 있었기 때문이었다. ESS 알고리즘을 다시 적어보면 다음과 같다.

1. 현재의 후보 탐색영역들을 R1, R2, ..., Rk라 하자 (초기에는 하나의 후보 탐색영역만이 존재하며 그것은 입력영상 전체이다)
2. 후보 탐색영역들 중에서 F(Ri) 값이 가장 큰 Ri을 선택한 후, 만일 Ri이 단일 윈도우로 구성된다면 global optimum으로 Ri을 반환하고 탐색을 종료한다. 그렇지 않은 경우에는 Ri을 두개의 영역으로 분할하여 후보 리스트에 추가한 후 탐색 과정을 반복한다.

즉, 핵심은 어떤 탐색영역(실제 물체가 포함되어 있는)이 현재 단계에서는 선택받지 못했더라도 후보 리스트 내에서 계속 경쟁을 하다보면 언젠가는 선택을 받게 된다는 점이다. 예를 들어, 두 탐색영역 R1, R2가 있고 R1에 포함된 윈도우들의 f값의 최대값이 30, R2에 포함된 윈도우들의 f값의 최대값이 40, R1의 추정값이 F(R1) = 60, R2에 대한 추정값이 F(R2) = 50라 하자. 그러면 현재는 추정값이 더 큰 R1을 선택하여 탐색을 진행하겠지만 R1을 계속 분할해 나가다 보면 조건 ii)에 의해서 언젠가는 반드시 추정값이 F(R2)보다 작아지는 순간이 오고 그 때부터는 R2가 선택되어 탐색이 진행된다. 결국 최종적으로는 f가 최대인 윈도우가 선택되게 된다.

이상으로, 조건 i), ii)만 만족하면 ESS 탐색으로 global 해를 찾을 수 있음은 알게 되었다. 하지만 문제는 이러한 F를 실제 어떻게 잡을 수 있느냐이다.

사실 이러한 조건을 만족하는 F는 무수히 많이 존재한다. 먼저, F를 잡는 한 극단적인 예는 F를 R에 관계없이 굉장히 큰(모든 가능한 r에 대한 f(r) 값보다 큰) 상수값으로 잡고 R이 단일 윈도우로 구성될 때에만 F(R) = f(r)이 되도록 하는 것이다. 이 경우 F(R)은 항상 동일한 값이므로 어떤 유용한 정보도 제공하지 않기 때문에 결과적으로 ESS는 exhaustive 탐색과 같게 된다. 다른 극단적인 예는 F(R)이 R에 포함된 윈도우들의 f값의 실제 최대값이 되도록 잡는 것이다. 이 경우 ESS 자체는 global 해가 있는 쪽으로 일직선으로 탐색이 진행되는 가장 효율적인 탐색이 되겠지만 F(R)을 계산하기 위해서는 R에 포함된 모든 윈도우들의 f값을 계산해야 하기 때문에 결과적으로는 exhaustive 탐색이 되어 버린다. 즉, 결론적으로 F는 이 두 양극단의 사이에 있는 어떤 값이 되어야 하며 F가 실제 f값의 최대값에 근접할수록 ESS 탐색은 효율적이 되지만 그만큼 F를 계산하기는 더 어려워지는 trade off가 존재한다.

[Lampert08] 논문에서는 세가지 실제 문제들에 대해서 구체적으로 F를 잡는 예를 설명하고 있다. 보다 자세한 내용은 [Lampert08] 논문을 참조하기 바란다.

A. 전통적인 bag of words 방법에의 적용

기존의 bag of words 방법은 물체의 존재 여부만 확인해 줄 뿐 물체의 정확한 위치는 알 수 없었다. 하지만 ESS 방법을 적용하면 빠르게 물체를 찾을 수 있을 뿐만 아니라 물체의 정확한 위치까지도 파악이 가능하다. 즉, object localization 목적으로 적용이 가능해진다. 그 방법은 다음과 같다.

학습 영상에서 bag of words 방식으로 추출한 feature 히스토그램들을 feature 벡터로 보고 SVM(support vector machine)으로 학습시켜서 나온 support vector들을 hi, 대응되는 weight를 αi라 했을 때, 어떤 입력 윈도우 r에 대한 SVM evaluation 값 f(r)은 r에서 계산한 feature 히스토그램을 h라 했을 때 f(r) = ∑αi*(h·hi) + β = ∑j (∑i αi*hcji) + β가 된다 (단, cj는 feature j가 속하는 cluster index, j = 1, 2, ..., n는 r 내의 모든 feature). 이 때, f = f+ + f- (f+: ∑i αi*hcji가 +인 term들의 합, f-: ∑i αi*hcji가 -인 term들의 합)로 f를 분해했을 때, F(R) = f+(r_max) + f-(r_min)로 정의하면 조건 i) & ii)를 만족시키기 때문에 ESS 적용이 가능해진다 (단, r_max는 R 내에서 가장 큰 윈도우, r_min은 최소 윈도우).

B. Spatial Pyramid Matching 방식에의 적용

ESS를 spatial pyramid matching에 적용하는 방법은 약간 더 복잡하긴 하지만 기본적으로는 bag of words 경우와 동일하다.

먼저, SVM 학습 단계에서는 pyramid matching kernel을 구성하는 각각의 분할별로 각각 SVM을 학습시킨다. 즉, 원래의 모델 영상을 level 0에서는 1x1 블록으로 분할하고, level 1에서는 2x2 블록으로 분할하고, ..., level l에서는 2lx2l 블록으로 분할한다고 했을 때, 모든 level의 모든 블록에 대해 각각 SVM을 하나씩 학습시킨다. 그리고 이렇게 얻어진 SVM의 decision hyperplane들을 모두 더하여(선형 결합) 최종 SVM classifier를 구성한다. 만일 level l의 (i,j) 번째 블록에 대한 SVM decision hyperplane이 f_l,(i,j)(r) = ∑α_l,(i,j)k*(h·h_l,(i,j)k) + β_l,(i,j)라면 최종 SVM classifier는 f(r) = ∑_l,i,j f_l,(i,j)(r_l,(i,j))가 된다 (r_l,(i,j)는 윈도우 r을 pyramid 형태로 분할했을 때, level l의 (i,j)번째 분할 영역을 나타낸다). 이제 탐색영역 R에 대한 추정값 F(R)은 R을 pyramid 형태로 분할했을 때 각각의 분할영역에서 계산된 F_l,(i,j) 값들을 모두 합한 값으로 계산한다. 이 때, 각각의 분할영역에서의 F_l,(i,j) 값은 그 영역에서의 최대 윈도우를 r_max, 최소 윈도우를 r_min이라 했을 때 f+_l,(i,j)(r_max) + f-_l,(i,j)(r_min)로 계산된다 (=> 사실 논문에서는 이렇게까지 구체적으로 설명되어 있지는 않습니다만 나름의 방식으로 정리해 보았습니다).

C. Image Retrieval에의 응용

마지막으로 ESS를 이미지 검색에 활용하는 예에 대해 살펴보자. 어떤 질의(query) 이미지 패치(patch) Q가 있을 때 비디오나 이미지 DB에서 Q를 포함하는 이미지를 모두 검색하는 것이 풀고자 하는 문제이다.

기본적으로는 Q에 대한 feature 히스토그램 hQ와 이미지 I의 모든 가능한 윈도우 영역 r에 대해 생성한 feature 히스토그램 hr을 비교하여 계산된 히스토그램 유사도의 최대값이 높은 이미지들을 선택하는 방법을 사용한다. 두 히스토그램간의 유사도 측정은 Χ2-distance를 사용한다. 이 때, Q와 이미지 I의 유사도는 Similarity(Q,I) = max{ -Χ2(hQ, hr) | r⊆I }로 계산된다. 그런데, 실제 Similarity(Q,I)를 계산하기 위해서는 I 내의 모든 가능한 r에 대해서 Χ2(hQ, hr) 값을 계산해야만 하지만 ESS를 적용하면 exhaustive evaluation을 하지 않고도 유사도를 측정할 수 있으며 또한 I 내에서 가장 유사도가 높은 윈도우를 찾아낼 수 있다. 이를 위해서는 유사도에 대한 추정값이 실제 유사도에 대한 상한이 되도록 식을 정의해야 하는데, 그 구체적인 수식은 논문을 참조하기 바란다.

4. 맺음말

영상에서 물체를 찾는 방법은 feature들 간의 기하학적인 관계를 정확하게 매칭하는 방법(homography를 이용한 SIFT 매칭 등)과 bag of words 기법을 이용하여 feature들의 히스토그램을 매칭하는 방법으로 크게 구분할 수 있습니다. 초창기에는 기하학적 매칭 방법이 대세를 이루었으나 이후 bag of words 방식이 출현한 이후로는 한동안은 사람들의 관심이 BoW 쪽으로 집중되었던 것 같습니다. 이러한 배경에는 기존의 기하학적 매칭 방법이 동일 물체의 인식에만 국한되고 또한 카메라의 시점 변화에 매우 민감한 문제가 있기 때문일 것입니다. 반면에 BoW 방법은 동일 물체가 아니라 동일 카테고리의 물체를 식별하는데 적용될 수 있고 또한 시점 변화에 매우 강인한 특성을 가지고 있기 때문에 좀더 높은 평가를 받은 것으로 보입니다. 하지만 최근에는 feature들 간의 spatial 정보를 잃어버린다는 BoW의 장점이자 단점이 갖는 성능상의 한계를 극복하기 위하여 다시 기하학적인 관계를 활용하는 방향으로의 연구가 활성화되고 있다고 합니다. 개인적으로는 어쩌면 이 두가지 특성을 모두 결합하여 활용하는 방안을 연구하는 것이 가장 좋은 방향이 아닌가 생각됩니다.

by 다크 프로그래머

최근에 조금 재미있는 경험을 했다.

작년 초에 해외 학회에 논문을 하나 낸 적이 있다. 그 분야에서는 나름 메이저 학회 중의 하나긴 하지만 그리 어려운 학회는 아니기에 내심 아마도 되겠지.. 하고 기대하고 있었다.

그런데 결과는 reject. 심사평은 한결같이 적대적이었다. 심지어 약간은 무시당하는 느낌도 들어있었다. 당시에는 '이 사람들이 무슨 심사를 발로 하나' 하며 분개하는 마음밖에는 들지 않았다.

그동안 내는 족족 떨어졌던 터라 그 이후로는 논문을 쓰는 것 자체에 대해서 거의 마음을 접어 버렸다. 그러던 차에 작년 말경 애라 모르겠다는 심정으로 떨어졌던 논문을 그대로 다른 학회에 제출했다.

새로 논문을 제출한 학회는 그 분야에서는 가장 메이저 학회로서 꽤 힘든 곳이었기에 당연히 떨어질 것이라고 생각했다. 그런데 얼마전 논문이 채택되었다는 메일이 도착했다.

이번 심사평은 정 반대로 상당히 호의적이었다. 그러니까 붙었겠지 하겠지만, 내가 말하고 싶은 것은 심사평 자체보다는 그 속에서 묻어나는 느낌이 그렇다는 것이다. 즉, 같은 글을 쓰더라도 적대감을 가지고 썼는지 아니면 밑바탕에 호의를 가지고 썼는지의 차이이다.

같은 논문인데 그 차이가 뭘까? 고친 거라고는 영어를 좀더 다듬고 표현을 좀더 부드럽게 한 것이 다이다. 그런데 지금 생각해 보면 그 작은 차이가 어쩌면 결과를 바꾼 가장 큰 원인인 듯도 싶다.

사실 어디에 명함을 내밀만한 논문 실적도 없고 떨어지는게 다반사인 사람이 '논문 잘 쓰는 법' ('논문 잘 붙도록 쓰는 법')에 대해 얘기하는게 조금은 어불성설일 지도 모른다.

그래도 그동안 이래 저래 논문을 써본 경험, 간혹 다른 논문들을 심사하면서 느꼈던 점들, 그리고 최근에서야 생긴 무언가 논문은 이렇게 써야 하지 않을까 싶은 어떤 막연한 감 같은 것들을 나름 정리해 보고자 한다.

1. Related Works and Positioning

논문들을 보면 대부분 related works라고 자신의 논문이 다루는 주제에 대해 기존에 어떤 관련 연구들이 있었는지를 설명하는 부분이 있다. 그런데, 정작 이 Related Works이 왜 중요한지 그리고 왜 필요한지 잘 알지 못하는 경우가 있다. 먼저 Related Works에 대한 잘못된 인식에는 어떤 것들이 있는지 살펴보자.

a. 남들이 하니까 나도 한다.

자신이 연구한 것만 잘 설명하면 되지 뭐하러 이런 귀찮을 짓을 하는지 잘 모르겠다. 그래도 다들 논문에 그런 내용을 포함하니까 왠지 나도 2~3개 정도는 관련 연구 내용을 적어야 될 것 같다. 어차피 관련연구야 다 비슷한 것이니까 괜찮은 학회 논문에 있는 related works 파트 전체를 그대로 복사해다가 붙여넣고 싶은 마음이 굴뚝같다. 하지만 그건 또 표절이라고 할 테니까 여기 저기 괜찮은 논문들을 참조하여 적당히 Related Work 파트를 작성한다. 물론 Related Works에 있는 대부분의 논문은 읽어 본 적도 없다.

b. 내 논문 주제와 관련된 기존의 주요 연구들을 쭉 정리하는 것이다.

Related Works란 내 논문 주제에 대한 기존의 관련 연구들을 심사자(reviewer)와 독자들에게 소개하는 것이다. 어차피 형식적인 것이므로 survey 논문 등을 참조하여 주요 방법들을 잘 정리하면 된다. 또한 Related Works는 내가 얼마나 이 분야에 대해서 잘 알고 있는지 보여주는 것이므로 이를 잘 정리하면 심사결과에도 긍정적인 영향을 미칠 것이다.

a는 논문을 처음 써 볼 때나 가질 수 있는 생각이며 b는 좀더 낫긴 하지만 그래도 아직은 부족하다.

Related Works의 궁극적인 목적은 자신의 논문에 대한 positioning이다. 자신의 접근법이 기존 접근법들 중에서 어디에 위치하는지에 대한 positioning 뿐만 아니라 자신의 연구가 어떤 의미를 가지고 있으며 어떤 문제를 풀려고 하는 것인지, 그리고 왜 중요한지를 그 분야의 관련 연구 흐름속에서 위치시키는 것이 Related Works이다.

흔히 내 논문은 이 분야의 전문가가 심사할 것이므로 굳이 이런 저런 설명을 하지 않아도 내 논문이 얼마나 중요한지를 잘 알 수 있을 것이라고 생각한다면 큰 오판이다. 심사자가 전문가가 아닐 수도 있으며 설령 같은 분야 전문가라 하더라도 세부적으로 여러 지류가 있기 때문에 어떤 부분에 대해서는 잘 모를 수도 있다. 또한 정말로 그 분야에 대해 잘 아는 사람이 심사를 맡은 경우라 할지라도 positioning이 잘 된 논문을 보면 상당한 호의를 가지고 논문을 보게 될 것이다.

경험에 의하면 Reviewer의 입장에서 봤을 때, 자신의 내용만 열심히 설명한 논문을 보면 도대체 이 연구가 중요한 것인지 아닌지, 기존에 있었던 방법인지 아닌지, 뭐가 새로운 것이고 어떤 문제를 풀려고 하는 것인지 알 수가 없기 때문에 그 방법이 아무리 좋더라도 좋은 평가를 내리기 힘들게 된다.

만일 자신의 연구가 기존에 관련 연구 자체가 없을 정도로 정말 새롭고 독창적인 것이라면 '기존에는 이런 저런 연구가 있었을 뿐 이러한 내용에 대해서는 연구 자체가 없었다'고 분명하게 명시해 주어야 한다.

2. 실험

대부분의 좋은 논문들을 보면 실험 파트가 거의 논문의 50% 이상을 차지한다. 그만큼 실험이 중요하다는 의미일 것이다. 논문에서 실험은 자신이 제안한 방법이 정말로 효과적인지 여부를 실제 데이터(증거)를 가지고 보이는(증명하는) 것이다.

그런데, 말이 쉽지 자신이 뛰어남을 보이는 것은 쉽지 않은 문제이고 정말 많은 시간과 고민이 들어가야 하는 부분이다. 가장 안좋은 방법은 오로지 자신이 개발한 방법의 최종 성능만을 제시하는 것이다. 논문을 심사하다 보면 가끔 '내가 개발한 방법을 이런 이런 문제에 적용해 보았더니 결과가 이렇게 나왔다. 엄청 좋다. 끝' 이런 식으로 실험을 하는 경우가 있는데 이건 아니다.  수치적으로 아무리 좋은 값이 나오더라도 그것 만으로는 (다른 기존 방법들과 비교하여 상대적으로) 그게 정말로 좋은 것인지 아닌지 혹은 효과적인지 여부를 전혀 알 수 없기 때문이다.

두번째 경우는 자신의 방법을 기존의 대표적인 방법들과 비교하여 평가하는 것으로서 가장 무난하지만 또한 평이한 방법이기도 하다. 이 방법은 일종의 진검승부라고 볼 수 있는데 그 실체는 결국 휴리스틱이든 짬밥이든 내가 할 수 있는 모든 노력을 쏟아넣은 최종 성능과 너의 모든 능력이 발휘된 성능을 비교해서 누가 더 나은지 재보자는 의미가 된다. 따라서 이러한 성능비교만으로는 그 논문의 가치, 효과를 제대로 표현했다고 보기 힘들다.

세번째 경우로 개인적으로 가장 좋은 방법이라 생각하는 방법은 기존 방법들과 비교하는 것과 더불어 자신이 제안하는 방법의 핵심 아이디어만을 따로 떼어서 평가하는 것이다. 이게 무슨 말이냐 하면 예를 들어 영상에서 자동차를 검출하는 알고리즘을 개발했다고 했을 때, 대부분의 경우 자신의 핵심 아이디어는 자동차 검출 전체 과정이 아니라 어떤 일부 과정에 관한 것일 것이다. 따라서, 자신의 핵심 아이디어에 관련된 과정을 제외한 다른 부분은 모두 동일하게 하고 자신의 아이디어를 적용했을 때와 적용하지 않았을 때의 성능을 비교하는 것이 어쩌면 자신의 방법을 가장 정확하게 평가하는 것일 것이다.

즉, 그 분야에서 통상적으로 사용되는 기본적인 방법의 성능을 측정한 후 여기에 자신의 아이디어를 추가했을 때 성능이 크게 향상되었다면, 그리고 자신이 건드린 부분이 다른 방법들에서도 공통적으로 사용되는 부분이라면 이 실험만으로도 자신의 방법이 효과적임을 충분히 보이는 셈이 된다. 물론 여기에 더불어서 자신의 방법을 적용한 최종 성능이 다른 기존의 대표적인 방법들보다 뛰어나다면 그 이상 좋을 수 없다.

즉, 실험파트에서는 다른 방법들과의 단순 비교뿐만 아니라 자신의 방법의 효과를 어떻게 잘 실험적으로 평가할 것인지도 같이 고민해 봐야 한다. 또한 최종적으로 제안한 방법뿐만 아니라 연구과정에서 시행착오를 거쳤던 방법들도 버리지 말고 잘 선별하여 실험에서 같이 비교한다면 그 자체도 좋은 정보이기 때문에 심사자나 독자로부터 좋은 평가를 받을 수 있다.

3. 이론

이 부분에 대해서는 정말로 할 말이 없다. 반드시 넘어야할 벽이지만 정말 넘기 힘든 벽이기도 하다. 흔히 그들만의 세상을 형성하고 있는 cvpr이나 iccv에 진입하기 위해서는 이 벽을 넘지 않고는 거의 불가능하다.

예전에 cvpr 2012 학회에서 재미있는 일이 있었는데, 한 논문의 저자가 cvpr 심사결과에 불만을 표하면서 자신들은 이 풍토가 개선되기 전까지는 앞으로 컴퓨터 비전계를 떠나겠다는 글이 인터넷에 공개되면서 이슈가 된 적이 있었다 (CVPR 2012: One Author's Withdrawal Statement).

논문의 저자들은 자신들이 제시한 방법이 그 분야의 기존 어떤 방법들보다도 뛰어난 성능을 보였음에도 불구하고 cvpr 학회에서 reject된 점에 불만을 품고 비전계를 떠나겠다고 선언한 것이었다. 관련하여 당시 심사평 중 3번째 reviewer의 평이 인상적이다: '그들의 방법이 뛰어난 성능을 보인 점은 인정하지만 후학들이 이 논문을 읽고 무엇을 배울지는 의문이다'.

4. 영어 & 문장력

비영어권인 우리나라 사람들이 공통적으로 안고 있는 가장 불리한 조건 중의 하나가 바로 언어적 문제이다.

예전에 국내 저널에 투고된 국문 논문을 심사한 적이 있었다. 그런데, 문장이 어색한 것이 아무래도 우리나라 사람이 쓴 논문은 아닌 것 같고 한글로 번역하여 제출한 논문이 아닌가 싶다. 예를 들어 이런 식이다. '기존의 접근 방법을 크게 2가지가 나누는데, 하나은 모델 방법이고 둘이 통계 방법이다'. 우리가 쓴 영어 논문을 영어권 사람들이 봤을 때에도 이와 비슷한 느낌을 가질 것이라 생각한다.

같은 말을 해도 어떤 사람이 하면 참 멋있어 보이고 또 누가 하면 참 없어 보이는 경우가 있다. 아무리 내용이 좋아도 영어에 문제가 있으면 일단 50%는 깎이고 들어간다고 봐야 한다. 여기에 문장력까지 별로거나 문제가 심각할 경우에는 아에 논문을 제대로 보지도 않고 심사를 해 버릴수도 있다.

사실 어쩔수 없는 부분이기도 하지만 그래도 몇 가지 방법은 있다고 생각한다. 영어 교정을 받는 것도 좋은 방법이지만 해당분야 비전공자의 영어교정은 한계가 있기 때문에 결국은 자기 자신이 감당해야 할 부분이 있다.

그 하나는 최소한 마감일 2주, 아무리 늦어도 1주 이전에는 논문 초안을 완성해야 한다. 그리고 남은 기간에 끊임없이 표현을 가다듬고 교정하는 과정을 거쳐야 한다. 현실적으로는 정말 어려운 일이긴 하지만 이것만 지킬 수 있어도 논문의 accept 확률은 크게 올라가리라 생각한다.

예전에 해마다 cvpr, iccv에 한편씩은 꼬박 꼬박 논문을 발표하는 친구를 본 적이 있다. 그 친구는 외국에서 학위를 받은 친구라서 영어에는 전혀 문제가 없었지만 옆에서 보면 일찌감치 초안을 써 놓고는 계속해서 수정하는 작업을 한다. 문장의 어순을 바꾸기도 하고, 단락의 순서를 바꿔 보기도 하면서 어떤게 좋은지 살펴보고 또 그림의 스케일, 형태을 가지고 한참을 고민하기도 한다. 그 친구가 한 말중에 아직도 기억에 남는 말이 있는데, '결과를 바꾸는 것은 사실 1%의 차이이다. 1%의 차이지만 그 결과는 완전히 달라진다'라는 말을 했다. 이런 말도 했다. '급한 일을 먼저 하지 말고 가장 중요한 일을 먼저 하라'. 참 대단한 친구라고 생각한다..

또 하나, 영어가 안될 경우에는 최대한 간결하고 단순한 표현을 사용하는 것이 좋다고 생각한다. 개인적으로도 워낙 영어가 일천하기 때문에 멋진 어휘나 문장은 꿈도 꾸지 않는다. 멋이 없고 정말 없어 보이더라도 내가 말하고자 하는 바를 가장 정확하게 나타낼 수 있는 그리고 다른 (오해의) 해석의 여지가 없는 단어와 문장을 선택한다. 즉, 해석에 있어서 모호성이 없는 어휘 및 문장 선택이 중요하다는 것이다.

조금 다른 얘기이긴 하지만 예전에 비전 분야에서 통상적으로 사용되는 성능지표를 논문에서 사용하면서 'introduce'라는 단어를 사용했다가 reviewer들의 뭇매를 맞은 적이 있다. 원래 의도는 그냥 알고리즘의 성능지표가 이 수식으로 주어진다는 것이었는데, 기존에 있는 평가방법인데 왜 네가 그것을 새로 개발했다고 하는 것이냐며 뭇매를 맞고 말았다.

마지막으로 너무 강한 표현보다는 정제된, 조금은 완곡한 표현을 쓰는 것이 논문을 좀더 있어 보이게 하고 심사자들에게 호감을 이끌어 내는 것 같다.

5. 기타 소소한 것들

논문은 흔히 간결하게 쓰라고 한다. 그런데 여기서 간결하게 쓰라는 말이 글을 축약해서 쓰라는 말은 아니다. 오히려 논문에서 핵심적인 내용 또는 강조하고 싶은 부분은 자세히 적는 것이 오히려 효과적이다. 설명은 세세하게 하되 그 표현은 간결하게 하는게 가장 좋다고 생각한다.

글을 쓴 직후에는 모든 것이 다 좋아보인다. 하지만 어느 정도 시간이 지난 후에 그 글을 다시 보면 보이지 않던 것들이 보이기 시작한다.

by 다크 프로그래머

배움은 어느 곳에나 있다는 말을 새삼 깨우치는 하루이다.

오늘 하루 큰 기대없이 들었던 강연에서 많은 것을 느낀다.

좋은 교수법에 대한 내용이었는데, 강연자의 경험에 의하면 학생들이 수업이나 지도교수에게서 바라는 것에는 논문 잘쓰는 법, 연구 잘하는 법, 전문지식 등의 실질적인 기술도 있지만, 그와 함께 잘 표현은 하지 않지만 숨겨진 바램으로 궁극적인 목표에 관한 것이 있다고 한다.

마음 깊은 곳에서는 내가 나아가야 할 길, 방향을 세우는데 있어서 가르침을 주고 동기를 부여해 줄 수 있는 사람을 원한다는 것이다.

Teaching is an act of love. 누군가가 한 말이라고 했는데 이름은 기억이 안난다. 누군가를 가르치고 지도한다고 하는 것은 단순한 지식, 기술의 전달이 아니라 사랑의 행위라는 의미이다.

학생을 한명 받아보고 싶어서 교원 신청을 했건만 강연자의 말을 듣다보니 덜컥 겁이 난다...

또 하나, 강연자의 말에서 인상 깊었던 것.

독일에서는 초등학교에서 정규교과과정의 하나로 자전거 타기를 배운다고 한다. 그들이 자전거 타기를 통해 학생들에게 가르치는 것, 그리고 학생들이 배우는 것에는 자전거 타기 그 이상의 것이 있다는 것이 요지이다.

Failure. 많이 넘어져본 사람이 자전거를 잘 타고 또, 많이 넘어질수록 자전거를 더 빨리 배우게 된다. 실패란 실패가 아니라 과정이다.

Risk. 자전거가 넘어지려고 할 때 그걸 피하려고 핸들을 틀면 바로 넘어진다. 오히려 넘어지려는 방향을 향할 때 넘어지지 않을 수 있다.

그 외에도 계속 페달을 밟아야만 한다는 것, 자신이 원하는 곳에서 멈출 줄 알아야 한다는 것 등을 자전거를 통해 직접 몸으로 체득하면서 교육한다는 것이다.

개인적으로는 이들 중 실패란 과정이다 라는 말이 특히 인상적이었다.

우리 아들놈은 아직 자전거를 타지는 못한다. 예전에 자전거를 가르친다면서 넘어지지 않는 법을 가르쳤다. '핸들은 넘어지려는 쪽으로 틀어라, 페달은 계속 굴려야 한다, 아빠가 뒤에서 꼭 잡고 있을 터이니 걱정하지 말아라'.

오늘 저녁 아들에게 다시 정정하여 얘기를 했다.

'OO야, 자전거를 타다가 넘어지는게 자전거를 배우는 과정이다. 자전거는 넘어지면서 배우는 것이고 그러다 더 이상 넘어지지 않게 되면 그 때 자전거를 배운 것이다. 우리 날이 풀리면 다시 연습하러 나가보자'

스스로도 말을 하면서 무언가가 다름을 느꼈는데, 아내에게 물어보니 아내도 그런 느낌을 받았다고 한다.

by 다크 프로그래머