Bag of Words 기법

영상처리 2014.02.19 14:48

최근 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 다크 프로그래머


저작자 표시 비영리 변경 금지
신고
  • BlogIcon Readiz 2014.02.19 20:57 신고 ADDR 수정/삭제 답글

    와 이런 전문적인 글을.. 감사합니다! ㅎㅎ

  • YH 2014.03.30 01:32 신고 ADDR 수정/삭제 답글

    항상 잘보고갑니다! 한글찾아보기 힘든 이 분야에서 다크님의 글을보면서 항상 위안과 감사를 느낍니다.

  • 다크팬 2014.07.30 12:20 신고 ADDR 수정/삭제 답글

    그림2에 보면 히스토그램에 나타난 가로축 그림의 수가 4(가로방향: 자전거, 사람얼굴, 바이올린, 사람눈)인것을 볼 수 있는데요.
    코드북에서 클러스터링을 4로 하였기 때문에 대표 이미지가 4개가 나오는 것인가요?

  • 다크팬 2014.07.30 13:47 신고 ADDR 수정/삭제 답글

    답변 감사합니다.
    추가적으로 질문이 있습니다.
    이미지에 찍히는 특징점이
    사람에는 5개, 자전거에는 3개, 바이올린에는 8개가 찍혔다고 가정을 하고
    클러스터링을 6으로 설정한 후 클러스터링을 하면
    바이올린의 특징점 개수가 제일 많으니까
    대표 이미지로 바이올린 이미지가 많이 추출될 확률이 높을 것 같습니다.
    예를 들어 전체 대표이미지중에 사람 이미지 2개 자전거 이미지 1개
    바이올린 이미지 3개.. 이런식으로요.
    그래서 각 이미지메 공평한 조건(각 이미지에 찍히는 특징점 개수)에서 클러스터링을 해야될 것 같은데
    이것은 어떻게 해야하나요??

    • BlogIcon 다크pgmr 2014.07.30 14:56 신고 수정/삭제

      바이올린에 클러스터가 많이 잡혀도 특별히 문제될 것은 없다고 생각합니다.
      입력이미지가 바이올린이라면 바이올린에서 추출된 codeword들에 대해 높은 히스토그램 값을 갖겠지요... 각각의 이미지들을 codeword를 이용하여 히스토그램으로 표현하고 나면 이후의 classification은 svm 등과 같은 다양한 학습방법을 적용할 수 있을 것입니다.

  • 다크팬2 2014.08.02 17:07 신고 ADDR 수정/삭제 답글

    ㅠ흥미롭게 너무 잘 읽었습니다^^~ 읽다보니 질문드릴게 있는데요. Bag of Words가 기하학적인 위취 관계를 표현해주지 못하기 때문에 이를 보완하기 위해 SPM이 도입되었다고 이해를 했습니다. 그렇다면 BoF가 non-rigid object를 잘 표현해준다는 장점이 있다고 하셨는데요 SPM은 non-rigid, rigid object 모두 잘 표현을 해주나요? 아니면 딱 구분지어서 non-rigid object일 경우는 BoF를 많이 쓰고 rigid object이면 SPM을 쓰는것이가요?^^

    • BlogIcon 다크pgmr 2014.08.03 07:42 신고 수정/삭제

      안녕하세요. 생각할 좋은 지점을 말씀해 주신 것 같습니다. 말씀하신 것처럼 일반적으로는 rigid 물체에는 SPM, rigid가 아니면 BoW를 사용하면 될 것 같습니다. 하지만 사실은 자신이 풀고자 하는 문제의 특성에 따라서 그때 그때 적당한 방법을 선택하면 됩니다. 부분적으로는 형태가 조금씩 변할 수 있는 물체라도 큰 틀에서는 변화가 크지 않다면 SPM의 피라미드 단계를 낮추어서(예를 들어 level0, level1만 사용) 적용할 수 있습니다. 또한 아무리 형태가 고정된 물체라 할지라도 카메라 각도에 따라서 다양한 형태로 이미지에 나타날 수 있다면 BoW가 더 좋을 수 있습니다. 중요한 점은 자신이 풀고자 하는 문제의 특성을 잘 파악하고 또한 사용가능한 여러 알고리즘들의 원리를 잘 이해하는 것이라 생각합니다.

    • 다크팬2 2014.08.04 10:52 신고 수정/삭제

      아하..감사합니다. 참고 논문을 읽어봐야겠네요~^^ 읽어보다가 혹시 모르는 내용이 있으면 질문하겠습니다. ㅠㅠ ㅎ

  • 다크팬 2014.08.04 19:07 신고 ADDR 수정/삭제 답글

    답변에 감사드립니다.
    클러스터링에서 K개의 파라미터값을 정할 때
    최소 이미지의 개수 만큼 K를 정해야 하겠죠?(이미지가 123개면 최소 K는 123이상)
    그럼 적절한 K를 구하기 위해 실험값으로 측정해야 할까요??

    • BlogIcon 다크pgmr 2014.08.04 20:20 신고 수정/삭제

      이미지의 개수가 아니라 클래스(물체)의 개수를 기준으로 해야 하지 않을까요? 적절한 k는 문제마다 달라질 것 같습니다(case by case)..

    • 다크팬 2014.08.14 14:12 신고 수정/삭제

      답변 감사드립니다.
      다시 질문드릴게요.

      K값을 설정할 때 이미지의 개수라고 생각해서
      이미지가 5개면 K는 5개 이상이라고 생각했습니다.

      다크님의 생각은
      예들들어 한 이미지에
      오토바이, 사람이 있을 경우에
      제가 말한 것에 의하면 K=1이상이여야 되는데
      다크님은 한 아미지에 물체가 오토바이, 사람이 있으니깐
      K=2이상이 되어야 된다는 말씀이신가요?

      한 번더 예를들어 이미지 3장에에서 K를 설정할 때
      첫 번째 이미지는 (사람, 오토바이)
      두 번째 이미지는 (시계)
      세 번째 이미지는 (나무, 자전거, 오토바이)에서

      물체의 개수는 총6이므로 K=6이상이 되어야 된다는 말씀이신가요??

    • BlogIcon 다크pgmr 2014.08.14 14:59 신고 수정/삭제

      네 그렇게 생각합니다. 최소 물체의 개수 이상은 클러스터가 있어야 할 것이고 같은 물체 내에도 다양한 종류의 특징이 존재할 수 있으므로 실제로는 훨씬 많은 수의 클러스터가 필요하리라 생각합니다.
      하지만 좀더 정확히 말하면 적정한 클러스터의 개수는 물체의 개수도 아니고 이미지의 개수도 아닙니다. 풀고자 하는 문제 도메인(domain)에 존재하는 모든 가능한 특징점들의 종류 개수가 가장 좋은 클러스터의 개수일 것입니다.

  • 다크팬2 2014.08.04 22:18 신고 ADDR 수정/삭제 답글

    -- 이 때, 높은 레벨(좀더 세분화된 분할)에서 측정된 유사도에 좀더 높은 가중치를 줌으로써 feature 분포의 공간(위치) 정보가 유지될수록 높은 점수를 주는 것이 일반적이다. --
    이것을 수식으로 보기 위해 논문을 찾던 중에 논문에서 pyramid match kernel 부분을 봤습니다. 수식으로 살펴보니 K(phi(X),phi(Y))=summation[1/2i * (number of new matches at level i)]이렇게 나온 수식이 있더라구요.. 여기서 1/2i부분이 위에서 언급하신 가중치라고 생각했는데 level이 세분화 될수록 즉, i가 커질수록 1 -> 1/2 -> 1/4 ..로 진행되면서 높은 레벨의 유사도에 더 낮은 가중치를 주는 것이 아닌가? 라는 의문이 생겨 질문드립니다. 수식을 제대로 적지 못해서 이해가 안가실 수도 있는데, Li-Fei-Fei 의 자료 중에 나온 수식입니다. 질문이 길었네요 ㅠ

    • BlogIcon 다크pgmr 2014.08.04 23:06 신고 수정/삭제

      어떤 논문을 보신 것인지요. 제 생각에는 세분화된 블록에서 매칭이 잘될수록 가중치를 높게 주는게 타당하다고 생각됩니다만.. 제가 글에서 참고한 Lazebnik06 논문에는 level i에 대한 가중치가 1/2^(L-i)로 나오는데, 말씀하신 수식과는 반대인것 같습니다.

    • 다크팬2 2014.08.07 10:51 신고 수정/삭제

      아하..그렇네요ㅠ~ 잘못생각하고 있었습니다.ㅎ 감사합니다!

  • 짜녁님 2014.08.07 22:59 신고 ADDR 수정/삭제 답글

    안녕하세요 다크님 블로그참고하면서 BOVW공부하고 있는 학생입니다
    언급해주신 논문 Visual Categorization with Bags of Keypoints 읽고있는데 중간에 이해가 안되는 부분이있어서요

    전체 과정을 제시해놓은 2장 부분에
    • Detection and description of image patches for a set of labeled training
    images
    • Constructing a set of vocabularies: each is a set of cluster centres, with respect
    to which descriptors are vector quantized.
    • Extracting bags of keypoints for these vocabularies
    • Training multi-class classifiers using the bags of keypoints as feature vectors
    • Selecting the vocabulary and classifier giving the best overall classification
    accuracy.

    이부분에서 2번째인 Vocabulary를 구성하는 부분과 bag of keypoints를 추출한다는 부분이 과정상 어떤 부분이 다른지 도저히 이해가 안되서 질문드려요 ㅜ
    제가 논문과 글읽고 이해한바로는 Vocabulary자체가 각각 이미지들의 대표하는 특징을 모아놓은 bag의 이미인데 여기서 또 bag of keypoints를 추출한다는게 .....

    • BlogIcon 다크pgmr 2014.08.08 06:10 신고 수정/삭제

      안녕하세요. 문맥상 두번째 단계는 클러스터링을 통해 cluster center들을 추출하는 것이고 세번째 단계는 일종의 히스토그램을 구하는 단계로 보입니다. 제가 본문 글에서 적어 놓은 이미지 분류 과정과 대응을 시켜보면 두번째 단계는 2. clustering & 3. codebook generation에 대응되고 세번째 단계는 4. image representation에 대응됩니다.

  • 짜녁님 2014.08.07 23:25 신고 ADDR 수정/삭제 답글

    그리고 하나더 궁금한게 전체(훈련데이터로 쓰일 이미지 모두) 이미지의 특징점에 대해 클러스터링을 한다는것인지 아니면 하나하나의 이미지 특징점을 클러스터링해 나온 센터들을 모아놓는것인지 궁금합니다

    • BlogIcon 다크pgmr 2014.08.08 06:12 신고 수정/삭제

      전체 이미지의 특징점에 대해 클러스터링을 하는 것이 일반적이라 알고 있습니다.

  • 비공개로 담아갈게요~

  • 가시뿐이라고 믿었던 선인장도
    오래고 더딜지는 모르지만 꽃이 핀다
    선인장처럼 오래고 더딜지라도
    내 인생에도 예쁜 꽃이 피었으면, 그랬으면 좋겠다

    인터넷에서 본 글인데
    글이 너무 이쁘더라고요.
    좋은 하루 보내세요~

    • BlogIcon 다크pgmr 2014.08.19 14:15 신고 수정/삭제

      좋은 말이네요. 우리 살아가는 삶에도 종종 예쁜 꽃이 피었으면 좋겠습니다 ^^

  • 다크팬 2015.04.15 15:53 신고 ADDR 수정/삭제 답글

    안녕하세요. 자주 즐겨보고 있는 블로그 입니다.
    다름이 아니라 질문이 있어서요 ^^

    k-means클러스터링할때
    예를들어 물체가 3개가 있다고 가정할게요.
    물체3개에 대해서 sift를 이용하여 특징점들을 추출합니다.
    물체_a = 2, 물체_b = 4 물체_c = 3

    물쳬_a, b, c의 모든 특징점들을 한곳에 모아
    클러스터링을 수행하기 위해 K개수는 4로 설정한다고 가정합니다.

    모든 특징점들 중에서 9개 중에 랜덤으로 4개를 선택하여
    k-means를 수행할텐데

    여기서 질문이 있습니다.
    물체_a 영역에는 K=0개 물체_b영역에는 K=3개, 물체_c 영역에는 K=1개
    이렇게 선택되었을 때
    물체_a 영역에는 하나도 선택이 되어 있지 않다면
    나중에 매칭할 때 물체_b영역에 있는 이미지라면 매칭이 잘될테고
    물체_a영역의 종류라면 매칭이 잘 안되지 않을까 싶습니다.

    현재 제가 이해한 BoW에서 k-mans클러스터링 방법입니다.
    혹시 제가 이해한 부분에 오류가 있는지 확은하고 싶어서 쪽지 남깁니다.^^
    (기본적인 k_means 방법은 알고 있습니다. 초기 K개수를 선택하고 K개를 어떻게 배치가 되어져야 하는지 궁금합니다.)

    • BlogIcon 다크pgmr 2015.04.15 18:18 신고 수정/삭제

      안녕하세요. 흥미로운 논점으로 보입니다. 하지만 결과적으로 큰 문제는 없다고 생각됩니다.
      case1) a에 시작점이 없다고 하더라도 k-mean를 돌리다 보면 클러스터 중의 하나는 자연스럽게 a로 이동하여 수렴할 것입니다 (a가 다른 feature들과 구분되는 상이한 feature로 구성될 경우). 말씀하신 위 경우에 대해 직접 k-means를 적용해 보시기 바랍니다.
      case2) 만일 a의 feature들이 다른 물체들과 잘 구분되지 않은 feature라서 다른 물체의 클러스터와 합쳐진다고 하더라도 큰 문제는 없습니다. BoW는 히스토그램의 형태를 보는 것임을 잘 상기해 보시기 바랍니다. 어떻게 클러스터링 결과가 나오든지 a, b, c의 히스토그램 형태는 모두 다를 것입니다.

  • 코더 2015.04.20 12:54 신고 ADDR 수정/삭제 답글

    다크님 안녕하세요. Bag of Words 기법을 공부 중인 학생입니다.

    히스토그램에서 y축이 나타내는 바가 이미지 상에서 codeword가 발견된 횟수라고 하셨는데요.
    자전거를 예로 들면, codeword로 뽑힌 핸들 부분은 자전거에서 1번 나오니까 y값이 1이고, 나머지 codeword(눈, 코, 입 등)들은 값이 0이어야 하지 않나요?

    이해가 잘안되서 여쭤봅니다 답변 주시면 감사하겠습니다! ㅜㅜ

    • BlogIcon 다크pgmr 2015.04.21 07:59 신고 수정/삭제

      네, 문제에 따라서는 말씀하신 것처럼 될 수 있습니다. 하지만 현실 문제에서는 그렇게 정확히 나누어 떨어지는 경우는 흔치 않습니다. 노이즈라는 것도 있고, 서로 다른 물체라 하더라도 부분적으로는 유사한 부분도 있을 수 있기 때문에 이러한 점을 반영한 그림이라 이해해 주시면 좋을 것 같습니다.

    • 코더 2015.04.21 10:48 신고 수정/삭제

      아 그렇군요 친절한 답변 감사드립니다^^

  • 궁금한아이 2015.05.11 21:25 신고 ADDR 수정/삭제 답글

    다크님 안녕하세요~
    궁금한 게 있는데, 클러스터링을 수행하기 전 작업인 Feature Detection에서
    특징점만 찾는 건가요 아니면 특징점 이후에 특징기술자들까지 찾아서 그것들로 클러스터링 하는건가요??
    귀찮으시더라도 답변 주시면 고맙겠습니다..ㅠ

    • BlogIcon 다크pgmr 2015.05.12 06:10 신고 수정/삭제

      안녕하세요. 특징기술자에 대해서 클러스터링을 하는 것입니다. 예를 들어, SIFT를 사용하면 128 차원 벡터들에 대해 클러스터링을 수행하게 됩니다.

    • 궁금한아이 2015.05.12 11:53 신고 수정/삭제

      아 네 감사합니다 다크님!!

  • seso 2015.11.12 18:09 신고 ADDR 수정/삭제 답글

    내용 정말 좋네요, 잘 보고 갑니다~

  • 덴버러스 2015.12.04 15:38 신고 ADDR 수정/삭제 답글

    안녕하세요. 자세한 설명 정말 감사합니다.
    ESS 를 학습하던 중에 궁금증이 생겼습니다.
    언급하신 [Lampert08] 논문에 2.1절을 보면 ..
    "ESS organizes the search.." 로 시작하는 문단이 있습니다.
    그 문단의 5번째 줄에 forming 2 disjoint candidate sets. 라는 말이 있습니다.
    나누어진 R1, R2 가 disjoint라고 언급하는 부분입니다.
    이 ESS 08년 논문이 09년에 PAMI에 저널화되어 나왔는데, 거기에도 똑같은 문단을 삽입하여 서술하고 있습니다.
    09년 PAMI 09년 ESS 논문에는 그림도 자세히 나와있는데,
    그림으로 설명하는 내용을 보면 R 을 나눠놓은 R1 과 R2 가 꼭 disjoint 라고는 할 수 없을 것 같습니다.
    다크프로그래머님께서는 어찌 생각하시는지 궁금합니다.

    • BlogIcon 다크pgmr 2015.12.04 16:39 신고 수정/삭제

      충분히 혼동스러울 수 있는 문제입니다.. 여기서 disjoint의 의미가 탐색 공간이 disjoint하다는 의미임을 유념하시면 좋을 것 같습니다. 물론 윈도우 자체는 서로 겹칠 수 있습니다. ESS는 영상의 영역을 분할해가면서 탐색을 하는 것이 아니라 탐색공간(search space)을 분할해가면서 탐색하는 방법입니다.

  • wiwi 2016.04.19 15:11 신고 ADDR 수정/삭제 답글

    안녕하세요. 자세한 설명이 되어있어서 이해하기 좋습니다 ㅎㅎ
    제가 Deep filter banks for Texture Recognition and Segmentation라는 논문을 읽던 도중 Fisher Vector를 이용한 Pooling이 Bag-of-Words와 유사한 접근법이어서 Orderless하면서 multi-scale하다고 나와있는데 이것이 의미하는 것이 무엇인지 잘 모르겠습니다.
    BOW나 FV나 어떤 지역적인 특징들(SIFT 또는 CNN Convoultion features)을 가지고 Histogram이나 Gaussian Mixture Model과 같은 방식으로 나타내기 때문인가요?
    SIFT같은 local feature들이 orderless와 multi-scale한 feature를 갖는다는건지 이를 이용해서 모종의 기법을 통해 그러한 특징을 갖는다는 건지 잘 모르겠습니다..

    Bag-of-Words에 대한 것은 아니지만 귀찮으시더라도 답변해주시면 감사하겠습니다.ㅠㅠ

    • BlogIcon 다크pgmr 2016.04.20 06:25 신고 수정/삭제

      안녕하세요. orderless 하다는 것은 말 그대로 순서가 없다는 의미입니다. "이 물체는 이러 이러한 feature들로 구성된다"와 같이 구성비를 나타낼 때에는 순서는 아무런 의미가 없습니다. 즉, SIFT 자체가 orderless한 것이 아니라 SIFT feature들을 집합적으로 orderless하게 이용하기 때문에 orderless합니다.

    • wiwi 2016.04.20 11:05 신고 수정/삭제

      감사합니다! 이제 이해가 되네요!

  • BlogIcon hojak99 2016.07.12 20:06 신고 ADDR 수정/삭제 답글

    안녕하세요. 고등학생 개발자입니다. 제가 이미지 유사도 측정에 대해서 알아보던 중 Spatial Pyramid Matching라는 것을 알게되었습니다. 그래서 이 논문에 대해서 영어 공부도 할 겸 제 블로그에 해석한 것을 조금씩 작성하고 있는데 혹시 다크 프로그래머님의 글을 참고하거나 인용해서 내용을 작성해도 될까요?? 출처는 꼭 밝히겠습니다.

  • BlogIcon SAILING__66 2017.07.20 18:10 신고 ADDR 수정/삭제 답글

    정말 잘읽고 갑니다! 제 블로그에 다크 프로그래머님의 이 글에 대한 주소를 소개해도 될까요?