[Image Processing] HOG Algorithm

참고자료 1 : http://sijoo.tistory.com/75

참고자료 2 : http://jangjy.tistory.com/163

참고자료 3 : http://web.mit.edu/vondrick/ihog/ (HOG Demo page)

참고자료 4 : https://en.wikipedia.org/wiki/Histogram_of_oriented_gradients

참고자료 5 : Histograms of Oriented Gradients for Human Detection (HOG 원 논문)

HOG (Histogram of Oriented Gradients) Algorithm

HOG의 개념

  HOG Algorithm은 일반적으로 보행자 검출이나 사람의 형태에 대한 검출 즉, Object Tracking에 많이 사용되는 Feature 중 하나이다. Image의 지역적인 Gradient를 해당 영상의 특징으로 사용하는 방법이다. 

HOT의 특징

  가장 중요한 특징은 Edge의 양과 방향을 구분하는 특성을 가지고 있다. 또한, Overlap을 이용하여 계산하기 때문에 어느 정도 Shift에도 적응할 수 있는 능력이 있다. 마치 Haar-like가 영역으로 특징을 구하기 때문에 잡음에 둔감한 것과 같이 HOG의 Overlap의 이유는 어느정도의 변화를 받아 들일 수 있다는 것이다.

HOG의 수행 방법

  먼저 이 방법은 Edge Orientation Histograms의 방법과 유사하다. 영상에서 Gradient를 계산하고 계산 된 값을 이용하여 Local Histogram을 생성한다. 이렇게 생성된 Histogram을 이여 붙여 1차원 vector를 생성한다. 

  HOG 알고리즘을 이해하기 위하여 Cell과 Block의 개념을 숙지해야한다. 영상은 기본적으로 픽셀들의 집합으로 되어있다. 이러한 픽셀들을 묶어서 소그룹을 만들면 Cell이고, 이러한 Cell들을 다시 묶어서 그룹을 만들게 되면 Block이 되는 것이다. 

  영상에서 Gradient를 계산 할 때 영상에서 edge를 계산하여야 한다. 전에 포스팅 하였던 Sobel Edge 추출과, Roberts Edge 추출, Prewitt Edge 추출 방법과 같은 다양한 Edge Kernel들을 사용할 수 있다. 실제 Edge 검출에서는 Sobel 에지 추출 방법을 많이 쓴다고 한다. 

  HOG 알고리즘에서는 아래와 같은 Mask(Derivative mask)를 사용한다. 1차원 vector를 생성하기 위해 discrete derivative mask를 사용하는데, 수평적, 수직정 방향 둘 다 적용하게 되고, filtering된 color와, data의 intensity가 필요하다. 

Sobel Mask & Prewitt Mask 관련 포스팅 : http://eehoeskrap.tistory.com/37

  x 축 방향 에지와 y축 방향 에지를 계산한 뒤, 두 값을 이용하여 Orientation을 계산한다. 이렇게 계산된 Orientation은 360개가 넘게 되는데, 40도 단위로 나뉘는 9개의 bin이나 24도 단위로 나누는 15개의 bin을 사용하여 Quantization(양자화)을 해주도록 한다. 

  Block normalization은 다음과 같은 식에 의해 수행된다. HOG 알고리즘의 저자인 Dalal 와 Triggs은 Block normalization을 위한 4가지 방법을 탐구하였다. v는 비정규화된 벡터다. ||v||k는 k-norm(k=1,2), 그리고 e는 어떤 작은 constant(exact value) 이다. normalization factor는 다음 네가지 중 하나로 수행된다. 

  영상으로부터 Orientation map을 만들어 냈으니, Cell 단위로 Histogram을 생성하고, 이를 이어 붙이는 방식이 Block의 움직임에 의해 결정된다.(?) 각 Cell 별로 Histogram을 만드는데 Orientation을 몇 개의 bin으로 나누었냐에 따라서 index 설정이 된다. 이런 식으로 모든 Cell에 대해 histogram을 생성한다. 

SVM classifier

  마지막으로 HOG를 사용하여 Object Recognition을 하기 위해 필요한 것은 Supervised learning을 기반으로 한 어떤 Recognition으로의 Descriptors이다. SVM(Support vector machine) 분류기는 binary classifier이며, optimal hyperplane을 찾아야 한다. SVM에 대한 내용은 아래 포스팅을 참고하기를 바란다.  

SVM 관련 포스팅 : http://eehoeskrap.tistory.com/45