CV 6. Classification

Computer Vision [6]

 

Computer가 어떤 사진을 보고 이해하고, 이해한 결과를 표현할 때 Classification은 매력적이다. 강아지 혹은 고양이의 특징들을 학습한 Computer가 자동적으로 강아지와 고양이를 구분해준다면, 수천장 수만장되는 사진을 우리가 직접 구분하지 않더라도, Computer가 빠르게 진행해 줄 수 있을 것이다! 최근 Deep Neural Network의 등장으로 기존의 Hand-crafted feature방법보다 더 정확할 뿐만 아니라, General Purprose GPU로 인해 매우 빠르게 진행된다. (나중에 CUDA관련된 Image Processing Topic을 다루고 싶다. CPU에 비해서 정말 빠르다.)

1. Image Representation

먼저, Computer가 이미지를 "이해"하려면, 이미지를 표현하는 방법이 중요하다.

1) Bag of Visual Words

Image에서 SIFT등으로 hand-crafted features를 추출한 다음에, 이 features들을 clustering하여 Visual words를 만든다. 그 다음 새로 들어온 Test image를 SIFT등으로 Features를 추출한 다음 각 Visual words에 해당하는 Histogram을 그려서 가장 histogram의 크기가 큰 visual word의 class로 classification을 할 수 있다. 간단하게 표현하면, 학습 이미지에서 그럴듯한 특징들 (강아지라면 코?)을 뽑아낸 다음 그들의 대표적인 특성을 찾아내서 Visual words를 구축한다. 그 다음 새로운 이미지가 입력되면 특성을 뽑고, 특정 Visual Word와 비슷한경우 그 Visual word에 해당하는 수를 더해가고, 최종적으로 Class가 분류된다.

이 방법은 읽어봐도 직관적인데, 문제는 공간 정보를 잃어버린 다는 것이다. 단순히 Histogram을 구한 것이니 공간에 대한 고려가 없는 것이다. 이를 해결하기 위해서 Spatial Pyramid Matching이 사용될 수 있는데, 이는 전체 이미지에서 하나의 histogram을 얻고 (level 0), 전체 이미지를 4등분 하여 각 등분에서 histogram을 얻고 (level 1), 전체 이미지를 16등분 하여 각 등분에서 histogram을 얻는 (level 2) 등의 방식으로 level에 따라 전체 이미지를 여러 구간으로 나누는 것이 특징이다. 그리고 각 level에서 얻은 histogram에 weight을 곱하여 세부적인 spatial information을 추출할 수 있다는 장점이다.

2) Histogram of Oriented Gradients (HoG)

Face detection을 한다고 HoG feature를 사용하는 regression tree를 사용한 적이 있어서 간략하게만 알고 있었는데, 꽤 유용한 feature extraction방법이라고 생각했다.

HoG는 먼저 이미지에서 x축으로 gradient를, y축으로 gradient를 다음 필터를 사용해서 계산한다.

만약, RGB channel이라면, 각 Channel에 해당하는 Gradient를 계산한 다음에 가장 큰 Gradient를 선택한다.

x축, y축 Gradient를 얻고나면, 이 Gradient를 갖고 방향을 구할 수 있다. 8 bin의 histogram (8개의 quantized direction)내의 각 방향에 대한 "크기"를 앞에서 구한 Gradient를 각 방향에 "Projection"에 시키면 voting을 할 수 있다. (Soft voting)

HoG는 전체 이미지에서 histogram을 얻는 방법 대신에, 8 x 8 pixel로 이루어진 cell과 2 x 2 로 구성되는 block을 단위로 histogram을 구한다. 먼저 cell에서 histogram을 구하고 block에서는 이 4개의 cell의 histogram을 concatenation을 한다. 그 다음에 block 단위로 histogram을 normalization하는데, 이는 spatial information을 유지시키기 위함이다. (cell 단위로 normalization하여 붙이는 경우, 특수한 형태의 edge or gradient의 정보가 block단위에서 의미가 없을 수 있다.) block은 overlapped이 되는데, 이는 좀더 공간의 정보를 얻고자함이다.

block의 histogram을 모두 concatenate하면 HoG Feature를 얻을 수 있다. HoG feature의 특징은 gradient기반이기 때문에 illumination change에 강인하다는 것이며, cell단위 대신에 block단위의 normalization을 하기 때문에 특수한 edge 정보들을 유지할 수 있다는 것이다.

 

2. Image Classification

1의 과정으로 우리는 Image를 표현하는 "정보 혹은 특징"을 얻었다. 즉, Computer가 이해할 수 있는 무엇인가를 만든 것이다. 그렇다면 이제 이 정보를 바탕으로 분류를 할 수 있는 "모델"이 필요하다. 다양한 모델이 있겠지만, Support Vector Machine은 Deep Neural Network 이전에 state-of-the-art를 보여주었다. 그 유명한 SVM을 알아보도록 하자.

1) SVM

출처: Wikipedia, 서포트 벡터 머신, https://ko.wikipedia.org/wiki/서포트_벡터_머신

SVM의 핵심적인 아이디어는 위 그림에서 H2를 찾아내는 것이다. 검정색과 흰색을 나누는 기준은 H1과 H2가 있지만, 우리는 "직관적"으로 H2가 더 나은 것이라고 이해한다. H1과 H2를 decision boundary, hyperplane이라고 부르는데, decision boundary로 부터 각 class의 sample이 멀리 있다면 좋다고 본다. H1에 비해서 H2는 sample과 멀리 있으므로 H2가 더나은 model이라고 본다. 각 class에서 decision boundary와 가장 가까운 점들과 decision boundary의 거리를 margin이라하고 이를 최대화하는 것이 SVM의 핵심이다.

왜 Margin을 최대화하는 것이 좋은 모델인가? 이는 test set의 분포가 train set의 분포와 살짝 다를 수 있기 때문이다. test set은 우리가 알지 못하는 정보이기 때문에, H1의 경우 상당히 많은 수가 잘못 분류될 수 있을 것이다. (Margin이 작으니까) 반면에 H2는 충분한 Margin (e.g., Safety Margin)을 갖고 있으므로, test set의 분포가 train set과 다르더라도 Margin안에만 있다면 분류가 잘 되는 것이다. 이러한 성질은 SVM의 Generalization capability를 상당히 끌어올린다.

SVM은 maxmin problem인데, 가장 가까운 point (min)과의 거리를 최대화(max)하는 것이 SVM이기 때문이다.

xi에서 특정 hyperplane사이의 거리는 위의 식으로 표현된다. 이 식을 Margin으로 표현하면 다음과 같아진다.

이를 최대화하는 것이 SVM이 풀어야할 문제이다.

먼저, maxmin은 풀기 힘드니, 이 문제를 쉽게 만들어야한다.

Margin을 1로 scaling하고나면, 위와 같이 간단한 convex optimization문제가 된다. 

Maximum-margin hyperplane and margins for an SVM trained with samples from two classes. Samples on the margin are called the support vectors. 출처: Wikipedia, Support vector machine, https://en.wikipedia.org/wiki/Support_vector_machine

Contrained된 문제를 풀기 위해서, 다음과 같이 식을 변환한다.

너무 복잡하게 느껴지겠지만, 위의 식을 한번더 변환시키면,

이 식을 Quadratic Programming으로 풀면 lambda에 대한 값을 얻게된다.

긴 식이 많았지만, 중요한건 Matlab이나 Sklearn에서 충분히 다 해준다. 그러면 각 parameter가 무슨 의미를 갖고 있는지 아는게 중요한데, SVM에서 lambda는 support vector가 아니면 모두 0이다. 따라서 weight도 support vector가 아닌 point는 기여가 없다.

이러한 특징이 Margin을 최대화한다는 것이다. 그리고 중요한 부분은 training points가 모두 사용된다는 것이다. (단, 의미있는건 support vector) 다음 식은 test set에 적용시킬 때의 class 분류를 보여준다.

전체 train point와 test point를 inner product하는 것을 위의 식을 보고 알 수 있다.

2) Soft margin

위의 그림에서 H2와 H1에 의해서 딱 구분이 되면 좋겠지만, 사실 전혀 그렇지 않다. 서로 다른 class가 decision boundary 반대에 있어서 잘못 분류하는 case도 있다. 이 부분을 얼마나 인용해줄수 있을지를 결정 짓는 방법이 soft margin이다. soft margin은 다음 식으로 표현된다.

각 train point에 1보다 적은 margin을 갖을 수 있는 여유를 주어 margin을 더 유연하게 만들 수 있다. 이 식에서 C는 soft margin의 정도를 결정하는 hyper-parameter이다.

3) Non-linear SVM

데이터가 linear hyperplane으로 구분되면 좋겠지만, 사실 또 그렇지 않다. 비선형적으로 구분되는 경우가 있다. SVM에서는 kernel이라는 trick을 사용하여 데이터의 차원을 높이는 방법으로 비선형적으로 데이터를 구분하는 방법을 사용한다. Kernel은 다음 식의 k를 의미한다.

Kernel trick에서는 K를 구하고 phi에 대한 식을 구하지 않는다. 이 방법을 통해서 매우 간단하게 비선형 모델을 구현할 수 있으며 polynomial kernel, radial basis function등의 유명한 kernel들이 있다.

하지만 선형 kernel에 비해서 시간이 많이 걸리는데, 이는 선형과 달리 비선형은 kernel이 test set에 의존하고 있기 때문이다. 선형 kernel은 독립적이기 때문에 한번 구하면 끝이지만, 비선형은 매 test set에 대해서 계산해야한다.

Bag of Visual Words, BoW, SVM, Support Vector Machine, HoG, Histogram of Oritented Gradient, Kernel, Non-linear SVM