[논문리뷰] Histograms of Oriented Gradients for Human Detection

사전지식

1. SVM : support vector machine은 기계 학습의 분야 중 하나로 패턴 인식, 자료 분석을 위한 지도 학습 모델이며, 주로 분류와 회귀 분석을 위해 사용한다. 두 카테고리 중 어느 하나에 속한 데이터의 집합이 주어졌을 때, SVM 알고리즘은 주어진 데이터 집합을 바탕으로 하여 새로운 데이터가 어느 카테고리에 속할지 판단하는 비확률적 이진 선형 분류 모델을 만다. 

출처: https://ko.wikipedia.org/wiki/%EC%84%9C%ED%8F%AC%ED%8A%B8_%EB%B2%A1%ED%84%B0_%EB%A8%B8%EC%8B%A0

 

2. Feature Descriptor 형상 기술자 : 유용한 정보를 추출하고 관계가 없는 정보를 버림으로써 이미지를 단순화하는 이미지 또는 이미지 패치를 표현한 것이다.

일반적으로 이 형상 기술자는 크기 폭 X 높이 X 3(채널)의 이미지를 형상 벡터/길이 n의 배열로 변환한다.

HOG 형상 기술자에서, 그라디언트의 방향(지향성 그라디언트)의 분포(히스토그램들)가 특성으로 사용된다. 그라디언트의 크기가 모서리와 모서리 주위에서 (갑작스런 밝기 변화 영역) 커지기 때문에 이미지의 그라디언트(x 및 y파생물들)가 유용합니다. 모서리와 모서리는 평면 영역보다 객체 모양에 대한 많은 정보를 제공한다.

 

3. HOG(histogram of oriented gradient) 

개념)

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

 

1) gradient를 구한다. (논문에서는 [-1,0,1] , [-1,0,1]T가 가장 효율적이라고 한다.)

2) gradient를 이용해서 Cell크기 별로 histogram을 만든다. ( Bin에 Pixel들의 Gradient magnitude를 더해주면 Histogram이 만들어진다.)

3) Histogram의 Bin을 block크기로 나열한다.(수치적으로 보이면 Feature가 생성되는 것이다.)

특징)

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

출처: https://eehoeskrap.tistory.com/98

http://blog.naver.com/PostView.nhn?blogId=tlaja&logNo=220851600594&redirect=Dlog&widgetTypeCall=true

---

Abstract

우리는 테스트 케이스로 선형 SVM 기반 human detection를 채택하여 강력한 시각적 object recognition을 휘한 feature of sets의 문제를 연구합니다. 기존의 edge 및 gadient 기반 desrptor를 검토한 후에, 우리는 grids of Histograms of Oriented Gradient(HOG) descriptor가 human detection을 위해 기존 feature sets보다 훨씬 뛰어나다는 것을 실험적으로 보여준다. 각 스케일의 성능 계산에 대한 영향은 fine-scale gradients, fine orientation binning, 상대적으로 거친 spatial binning 및 겹치는 descriptor block의 고품질 로컬 대비 정규화가 모두 좋은 결과를 위해 중요하다는 결론을 내립니다. 이 새로운 접근법은 기존의 MIT 보행자 database와 거의 완벽하게 분리된다. 그래서 다양한 자세 변형과 배경을 가진 1800개 이상의 주석이 달린 human images가 포함된 보다 까다로운 dataset를 도입한다.

 

3.Overview of the Method

이 절은 요약된 fig.1에대하여 feature extraction chain의 개요를 제공한다.

이 방법은 밀도가 높은 그리드에서 잘 정규화된 local histogram의 이미지 gradient orientation을 평가하는데 기초한다.

지난 10년동안 유사한 feature의 사용량이 증가해왔다. 기본 아이디어는 local object 외형과 모양이 해당 gradient나 edge 위치에 대한 정확한 지식이 없어도 local intensity gradients 또는 edge 방향의 분포에 의해 다소 잘 특성화 될 수 있다는 것이다. 실제로, 이것은 image window를 작은 spatial region(cell)로 분할함으로써 구현되며, 각각의 cell은 cell의 pixel에 걸쳐 gradient 방향 또는 edge 방향의 local 1D histogram을 축적한다. 이 결합된 histogram 항목이 표현을 형성한다. 조명, 그림자 등에 대한 불변성을 개선하려면 local response을 사용하기 전에 대비 정규화하는 것이 유용하다. 이것은 다소 큰 spatial regions(block)에 대한 local histogram "energe"의 측정값을 누적하고 결과를 사용하여 block의 모든 cell을 정규화하여 수행 할 수 있다. 정규화된 descriptor block을 histogram of Oriented Gradient(HOG) descriptors라고 한다. HOG descriptor의 밀도가 높은 (실제로 겹치는) grid로 detection window을 타일링하고 기존의 SVM 기반 window classifier에서 결합된 feature 벡터를 사용하여 human detection chain을 제공한다.(fig.1 보기)

 

1. 픽셀 별로 간단한 전처리를 수행한다.

2. 각 픽셀의 gradient를 구한다.

3. 방향(orientation)과 크기를 구하고,

   픽셀을 여러 개(eg. 픽셀 8x8개)를 모아서(Cell) weighted voting을 해 방향의 히스토그램을 구한다.

4. 여러개의 Cell을 모아서(eg. Cell 2x2개) block을 구성하고, block에 normalize를 수행한다.

5. 전체 이미지 영역에 대해서 위 과정을 수행해서 여러개의 block이 생길탠데, block의 집합이 descriptor가 된다.

6. SVM을 이용해 사람인지 아닌지 판단한다. (테스트 과정)

 

cell과 block: 영상은 기본적으로 픽셀들의 집합으로 되어있다. 이러한 픽셀들을 묶어서 소그룹을 만들면 Cell이고, 이러한 Cell들을 다시 묶어서 그룹을 만들게 되면 Block이 되는 것이다.

1. 영상에서 Gradient를 구함
Gradient 즉, 영상에서 기울기를 구하기 위해서는 Edge를 먼저 계산해야 한다. 소벨 마스크, 로버츠 마스크, 프리윗 마스크 개념을 등을 숙지한 상태에서 이해를 해야한다. 실제 엣지 검출에서는 소벨 마스크를 제일 많이 사용한다고 한다. 어떤 마스크를 쓸 지는 영상에 따라 판단하여 써야 할 것 같다.

엣지를 검출하기 위해서는 가장 간단한 1D Kernel을 사용한다. 쉽게 말해서 양 옆 픽셀 값을 하나씩 빼준다는 이야기 이다. X축 방향 엣지와 Y축 방향 엣지를 각각 계산했다면 두 값을 계산하여 Orientation(방향)을 계산한다. 삼각함수 중에서 arctan 함수를 이용하면 두 엣지에 의해 발생하는 Orientation을 구할 수 있다. 

그 다음 적당히 Quantization 을 해주어야 한다. 보통은 40도로 나뉘는 9개의 bin을 사용하게 되며, 15개의 bin을 사용해도 된다. 

2. 각 셀로부터 그래디언트 방향 성분에 대한 Local Histogram을 생성
gradient 방향 성분은 0~180으로 하고, 입력 영상을 분할한다.
이 분할된 단위를 셀이라고 하며 각 셀로부터 그래디언트 방향 성분에 대한 히스토그램을 구하여, 각 방향 성분을 20도 단위로 구분한다.(그러면 방향은 9개로 분류 가능하다.(20X9=180)) 
즉, 셀마다 9방향으로 분류된 그래디언트 방향 히스토그램을 계산

3. 인접한 셀을 묶어 블록단위로 만든다.
블록단위로 특징이 추출되어 이를 벡터로 구해내면, 이것을 기반으로 해당 벡터의 '특징'이 추출된 것이다.
이 특징을 사용하여 보행자인지 아닌지의 분류가 가능하다.

4. 분류의 경우에는 두개의 클래스 분류에 특기를 가진 머신러닝 알고리즘인 SVM을 사용한다.

[출처 1]  https://eehoeskrap.tistory.com/122 
[출처 2] https://wiserloner.tistory.com/874

 

5.Overview of Results

우리의 상세한 이행과 성능 분석을 나타내기 전에, 우리는 전반적인 final HOG detectors의 성능을 비교한다. rectangular(R-HOG) 또는 circular log-polar(C-HOG) block과 linear 또는 kernel SVM에 기반한 Detector는 우리의 Harr wavelet, PCA-SIFT와 shape context 접근법와 비교된다. 접근법들은 다음과 같다.

 

Generalized Haar Wavelets.

이것은 Haar-like waveletes에 맞춘 확장set이다. 이 featrues은 45도 간격으로 9X9 및 12X12 지향 1차 및 2차 미분 상자 필터와 해당 2차 미분 xy 필터의 반응을 잘 보여준다.

 

PCA-SIFT

이 descriptor들은 PCA를 사용하여 훈련이미지에서 얻은 기초로 gradient image를 투사하는 것을 기반으로한다. Ke& Sukthankar은 SIFT가 핵심 포인트 기반 일치를 능가한다는 것을 발견했지만 논란의 여지가 있다. 우리의 구현은 HOG descriptor와 동일한 파생 scale,overlap 등의 설정으로 16X16 block을 사용한다.

이 PCA 기초는 positive 훈련 이미지를 사용하여 계산된다.

 

Shape Contexts

original Shape Context는 가장자리 방향에 관계없이 이진 edge-presence voting을 log-polar spaced bins에 사용했다.

우리는 단지 1 orientation bin을 가진 C-HOG descriptor을 사용하여 가장한다. 

내부 반경이 2 픽셀이고 외부 반경이 8픽셀인 16개의 각도와 3개의 방사형 간격이 최상의 결과를 제공한다.

 

Results

Fig 3은 MIT와 INRIA data set에 대한 다양한 detector의 성능을 보여준다. HOG기반 detector은 wavelet, PCA-SIFT 및 Shape context보다 훨씬 뛰어나 MIT 테스트 세트에서 거의 완벽한 분리를 제공하고 INRIA에서 FPPW의 크기를 최소한으로 줄입니다. Harr-like wavelets은 2차 도함수를 사용하고 대비되는 출력 벡터를 정규화하기 때문에 MIT wavelet보다 성능이 뛰어나다. Fig 3은 또한 MIT 최고 parts 기반 및 단일 검출기를 보여준다. 하지만 database가 훈련(train) 및 test 파트로 어떻게 구분되어 있는지와 사용된 negative image를 사용할 수 없기 때문에 정확한 비교가 불가능 하다는 점에 유의해라.

 

 

7. Summary and Conclusions

우리는 밀도가 높은 중첩 grid에서 SIFT descriptor와 유사한 gradient orientations feature의 지역적으로 정규화된 histogram을 사용하면 person detection에 대한 좋은 결과를 얻을 수 있으며, 최상의 Haar 파장 기반 detector에 비해 false positive rate 를 줄일 수 있다는 것을 보여왔다. 우리는 다양한 descriptor parameter의 영향력을 연구했고 fine-scale gradients, fine orientation binning, 상대적으로 거친 spatial binning 및 겹치는 descriptor block의 고품질 로컬 대비 정규화가 모두 좋은 성능 위해 중요하다고 결론냈다. 우리는 또한 공개적으로 이용가능한 새롭고 더 까다로운 보행자 dataset을 도입했다.

 

Future work

우리의 현재 linear SVM detector는 합리적으로 효과적이지만 여전히 최적화의 여지가 있고 탐지 속도를 더 높이기 위해 HOG descriptor에 기반한 a coarse-to-fine 또는 rejection chain style detector를 개발하는 것이 유용할 것이다. 우리는 또한 block matching 또는 빛의 흐름을 사용하여 움직임 정보를 포함하는 detector에 기반한 HOG에 대해 연구중이다. 마지막으로 현재 fixed-template-style detector은 완전히 보이는 보행자를 감지할 수 없는 것으로 입증해왔다. 인간은 관절로 이어져있고 우리는 local spatial 불변도가 큰 기반 모델을 포함하면 보다 일반적인 상황에서 탐지 결과를 개선하는데 도움이 된다고 믿는다.

 

Acknowledgements

이 일은 European Union 연구 프로젝트에 의해 지원되었다. SVM-Light 는 믿을 수 있는 큰 규모의 SVM의 훈련을 제공했다.

 

---

느낀점 ) HOG에 대해 알아보면서 '알고리즘'이라고 하는 설명과 '특징(reature) 중 하나'라는 설명이 보여 개념에 대해 헷갈렸다.
후자는 샘플 데이터인 학습 시킬 데이터, 즉 찾아내고자 하는 특징을 담은 데이터(Positive,Good data)와 찾고싶지 않은 데이터(Negative,bad data)를 SVM 등과 같은 학습 분류기로 학습을 시켜 하나의 특징을 만들어 내는 것이다. 이와 같은 특징 중 하나가 바로 HOG Featrue라고 할 수 있다. 또한 SIFT 객체 검출기와 비교하여 지역적인 특징들 보다는 전역적인 특징을 사용한다는 것이 특징이다.
이는 이미지의 지역적인 Gradient(기울기 정보)를 해당영상의 특징으로 사용하는 방법이다.라고 나와있다.

또한 보행자 dataset을 이용하여 gradient를 구하는것이 인상깊다.