[Computer Vision] BoVW Scene Recognition and Spatial Pyramid
Scene recognition
어떤 이미지를 입력하였을때 이 이미지가 나타내는것이 무엇인지를 출력하는 것을 scene recognition 이라고 한다. 요즘은 VGG나 ResNet과 같은 딥러닝을 활용하지만, 2000년대 초반에는 GPU 파워가 뛰어나지 못해 딥러닝을 사용하여도 계산 시간이 너무 오래 걸려 실용적이지 못하였다. 그래서 사용한 방법이 bag of visual words이다.
Bag of visual words algorithm (BoVW)
Bag of words는 본래 NLP에서 사용되는 방법이다. NLP도 마찬가지로 transformer를 사용하지만, 예전에는 bag of words라는 알고리즘을 사용하였다. 어떤 글에서 사전에 나오는 단어들의 frequency들을 측정하여 수치화 하는 방법이다. 이 방법 역시 비전에서도 적용할 수 있다.
위 그림과 같이 visual vocabulary를 추출하여 visual word들의 히스토그램을 만들면 마찬가지로 이미지 데이터를 수치화 시킬 수 있다. 여기서 visual vocabulary는 우리가 만들 사전에서 정의되는 단어들이고, visual word는 이미지에서 나오는 데이터들이다.
BoVW Feature Extraction
우선 저번에 이야기한대로 이미지 전체를 수치화 시키는 것은 불필요하기 때문에 feature point를 잡아준다. Blob detector를 사용할 수도 있고 특별한 알고리즘 없이 regular grid 방법을 사용하여도 무방하다. 각각의 feature point들을 원으로 normalize를 해준 뒤 128 dimensional vector로 feature extraction을 진행해준다. Structure tensor를 활용한 normalization과 feature extraction은 blob detection 포스트와 SIFT 포스트를 참고하면 된다.
BoVW Visual Vocabulary Construction
이제 우리가 사용할 사전에 들어갈 단어들을 정의하여야 한다. 우선 모든 feature point들을 128차원 공간에서 한 점을 갖는다. 사전에 들어갈 만큼의 vocabulary의 개수를 지정하고 이 점들을 K-means clustering을 사용하여 묶어준다. 각각의 cluster에서 평균값을 계산하여 centroid를 찾고, 그 centroid가 visual vocabulary가 된다.
BoVW Decision boundary construction
Visual vocabulary가 완성되었으면 히스토그램의 x축이 만들어 진 것이다. 히스토그램의 y축은 vocabulary의 frequency를 의미한다. 이미지의 feature point가 input으로 들어왔을때 각각 cluster centroid에 KNN으로 간단하게 class label을 붙여주고 visual vocabulary의 frequency count를 올려주면 된다. 이미지의 모든 feature point들을 같은 방식으로 하면 visual vocabulary의 frequency를 나타내는 히스토그램이 완성된다. 마지막으로 image size와 number of features가 히스토그램에 큰 영향을 주지 않도록 이 히스토그램을 L2 normalize 해준다.
만들어진 히스토그램은 이미지 한개를 나타내는 히스토그램이다. 여러장의 training dataset 이미지들도 마찬가지로 히스토그램으로 extract하면 k-dimensional vector와 class label을 가진 데이터로 바꿀 수 있다. Class label이 존재하므로 supervised multiclass classification 방법중 OvA linear SVM을 사용하여 decision boundary를 구축한다.
Spatial Pyramid
어떤 color 이미지 히스토그램을 살펴보았을때, 한가지 문제점을 찾을 수 있다. 이 세 그림 모두 같은 color histogram을 가지고 있는데, 공통점이라고는 하나도 없다. 바로 histogram 자체가 spatial information을 포함하고 있지 않기 때문에 한개의 히스토그램만으로는 한계가 있다. 이 문제를 해결하기 위한 방법이 spatial pyramid 이다.
아래 그림과 같이 한 이미지를 4등분이나 16등분 같이 $2^n$ 개수만큼 쪼개준 후, 각각의 subimage들의 히스토그램을 구한 뒤 concatenate을 해주면 spatial information 역시 같이 담긴 히스토그램을 만들어 낼 수 있다.
Experiment Result
본인이 직접 이미지 classification task를 수행해 본 결과이다. 이미지에서 regular grid method을 사용하여 SIFT와 HoG로 각각 feature extraction을 하였고, K-means clustering으로 visual vocabulary를 만든 후 KNN으로 한개의 이미지 히스토그램을 만들었다. 이 과정을 전체 image dataset에 적용하였고 마지막으로 각각의 히스토그램을 OvA SVM classifier로 분류하였다. SVM 특성상 decision boundary가 linear 하기 때문에 non-linearity를 적용하기 위해 RBF kernel function을 적용하였다.
$$K_{RBF}(x,y) = e^{-\gamma ||x-y||^2}$$
Spatial pyramid는 이미지를 $l$ 개의 층으로 나누어 각 층의 subimage의 히스토그램을 이어붙였다. 여기서 중요한 점은 subimage의 사이즈가 layer가 커질수록 작아지기 때문에 feature point들의 사이즈도 같이 작아진다. 따라서 subimage의 히스토그램에 layer에 따른 weight을 걸어주어야 한다. 이때의 weight은 아래와 같은 함수를 사용했다.
$$w_l=\begin{cases}
2^{-l_{\text{max}}}, & \text{if } l = 0, \\
2^{-l_{\text{max}} + l - 1}, & \text{if } l \geq 1.
\end{cases}$$
아래와 같이 RBF커널을 사용하고 spatial pyramid방법을 사용한 classification accuracy가 가장 높게 나온것을 확인할 수 있다.
References
KAIST CS484 MinHKim Introduction to Computer Vision
리디렉션 알림
www.google.com
https://medium.com/@aybukeyalcinerr/bag-of-visual-words-bovw-db9500331b2f
Bag of Visual Words(BoVW)
BoVW is a commonly used technique in image classification. The idea behind this technique, is similar to the bag of words in NLP but in…
medium.com
https://figures.semanticscholar.org/d55bf8b8eba06866f7e34731319bde3800971d7d/2-Figure1.1-1.png