HOG, SIFT Object detection 발전과정

HOG

• 보행자 검출이나 사람의 형태에 대한 검출
• image의 지역적인 Gradient를 해당 영상의 특징으로 사용하는 방법
• 대상 영역을 일정 크기의 셀로 나누고, 각 셀마다 edge 픽셀들의 방향에 대한 히스토그램을 구한 후 이들 히스토그램의 bin 값을 일렬로 연결한 벡터

HOG의 특징

• hog는 위의 (g) 그림처럼 Edge의 양과 방향을 구분하는 특성을 가짐
• overlap을 이용하여 계산하기 때문에 어느 정도 변화에도 적응할 수 있는 능력을 갖춤
  • overlap : gradient 누적값을 의미
• HOG는 Edge를 사용하기 때문에 기본적으로 영상의 밝기 변화, 조명 변화 등에 덜 민감한 특징을 가짐

HOG 과정

1. 입력 영상으로부터 각 pixel의 Gradient의 크기와 방향을 계산

   • 입력 영상의 이미지의 픽셀의 밝기 값은 gray scale로 표현됨
     • gray scale : 가장 밝은 쪽의 흰색에서 검은색에 이르기까지 단색의 음역의 모음 및 범위
   • 이 픽셀들을 x, y 평면에서 gradient가 어떤 방향인지, 크기와 방향성분으로 계산

   

2. 임의의 pixel로 묶은 단위를 cell

3. 각각의 cell로부터 Gradient에 방향에 대한 Gradient 크기 히스토그램을 계산

   • 방향 성분을 20도 단위로 구분하면 총 9개의 bin(히스토그램의 x축), (총 방향의 최대 180도) (bin 개수는 자기 마음)

   • 논문에서 말하는 그림을 보면 방향 성분을 각각의 범주로 구별하는 것 같음

     • 020˚, 2040˚, 4060˚, 6080˚, 80100˚, 100120˚, 120140˚, 140160˚, 160~180˚ 기준

   • 위의 과정으로 구분되는 방향 성분을 통해 하나의 히스토그램으로 표현이 가능해짐

     

     • gradient direction에 맞는 bin에 gradient magnitude 값을 더해서 하나의 Histogram 생성

     • 만약 특정 cell에서 위치기 (x0,y0) 일 때 gradient direction = a, gradient magnitude = b 일 때

       • 방향 a가 0-20, 20-40 ... 의 범주에 속하는 위치를 찾음
       • 해당 범주에 b 크기를 더함
       • 이를 통해 하나의 histogram 생성

     • 위의 개념 gradient magnitude, gradient direction에 대해서

   - gradient는 기울기, 증감, 변화도

   - gradient 계산 수식

     



     - Gx는 수평 방향의 변화, Gy는 수직 방향의 변화를 의미
     - 즉, 위의 식에서는 (x,y) 에서 수평 방향, 수직 방향으로 얼마나 변화했는지를 나타냄

   - gradient magnitude

     - 기울기 벡터의 크기

     



   - gradient direction

     - 기울기 벡터의 방향

     



 - 전체과정을 보여주는 이미지

 



 - 이렇게 만들어진 Orientation Histogram의 특징

   - Edge의 양, 방향을 구분하는 특성을 가짐

   - HOG 자체가 pixel 하나가 아닌 위의 히스토그램처럼   cell 단위의 overlap을 구해서 모델 자체가 robust, noise에도 강함

4. 인접한 4개의 cell을 합쳐서 block으로 정의

   

   • maxpooling padding=1 준거 같은 모양

   • 각 cell 들을 한 칸씩 이동하면서 묶음

   • 이렇게 4개씩 묶은 cell을 block이라고함

   • 위에서 구해진 block을 3번과정과 연결

5. block 안 cell의 histogram을 연결시킨 후 L1,L2 정규화를 하여 최종적인 영상의 특성 백터를 생성

• 실제로 block normalization 방법은 총 4가지

  

• 위 공식에 사용설명

  • v = 정규화 되지 않은 vector
  • 주어진 block에서 cell 들을 연결해 histogram 생성(3번과정)
  • Vk 는 k-norm vector를 의미
  • e는 vk가 0이 되면 분모가 0이기에 넣은 상수

  

  논문에서 L2-hys, L2-norm 및 L1-sqrt는 비슷한 성능을 제공, L1-norm은 덜 안정적인 성능을 제공함

  → 주로 L2-norm 사용

• 정규화를 통해 각 cell이 포함된 각각의 block이 서로 다른 값으로 정규화됨

• 이를 통해 영상의 특징을 잘 설명하게 됨

• 모든 block 각각에서 정규화된 histogram을 가져와 최종 feature vector로 처리

6. 5번에서 나온 특성 벡터를 label과 함께 svm 분류기에 학습

HOG 요약

1. input 이미지에서 cell을 나누고, cell에서 각 pixel마다의 gradient 크기, 방향 구함
2. 구한 gradient 방향을 bin 범주에 맞게 gradient 크기 값을 더해 histogram 생성
3. cell 4개씩 묶어서 block 생성, bin 개수 * 4 가 됨 → 이것을 vector라고 할 때 vector 절댓값을 나눠줌(L1, L2 norm 수행)
4. 각각의 block은 36개의 특성을 가지고 image 전체에서 block 수 * 36이 전체 이미지의 특성 벡터
5. 이미지와 label로 이루어진 쌍을 SVM을 통해 학습
6. test 이미지를 주면, feature vector를 가지고 detection window에서 내가 찾고자 하는 label이 있는지 파악하고 그 위치를 알려줌

SIFT

• 이미지의 크기, 회전에 Robust 한 특징점을 추출하는 알고리즘
• 이미지 유사도 평가나 이미지 정합에 활용할 수 있는 알고리즘

SIFT 과정

1. Scale space 생성

   • Scale-space : 영상처리 시 단 하나의 스케일의 이미지가 아니라 여러 스케일로 본 이미지들을 가지고 필요한 작업을 수행, 이때 여러 스케일의 이미지를 모아놓은 것을 의미

   • 원본 이미지를 두 배로 크게 만든 다음에 점진적으로 blur 적용, 그 후 원본 이미지 절반으로 축소한 이미지에서 점진적으로 blur적용, 다시 반으로 축소 후 점진적으로 blur적용

   • 과정 이미지

     

   • 가우시안 연산자와 이미지 컨볼루션을 연산해서 blurring 적용

     • blur 처리 공식

       

       L = blur 처리된 이미지 , G = 가우시안 필터, I = 이미지

       x,y = 이미지 픽셀 좌표값 , σ = scale parameter

       • σ = (scale parameter) : 블러링의 정도를 결정하는 파라미터, 클 수록 이미지를 더 blur 시킴

     • 가우시안 필터 공식

       

     • 위에서 점진적으로 blur 처리된 이미지를 얻기위해서 σ값을 k배씩 증가시킴

       • 처음 σ = $1/\sqrt{2}$, k = $\sqrt{2}$ 설정
       • 2배로 키운 이미지에서는 처음에는 $1/\sqrt{2}$값으로 blur, 다음에는 1, 다음에는 $\sqrt{2}$ , 다음에는 2 이런식으로 점진적으로 blur 처리 → 점점 이미지 흐려짐

     • 원본이미지는 2σ 에서 시작해서 k배씩 점차적으로 blur처리 그다음 원본이미지를 절반으로 줄이고 4σ에서 시작해서 k배씩 blur처리

       • 이를 통해 같은 크기의 다른 blur 처리 정도를 가지는 이미지 5장씩 총 4개의 그룹생성
       • 같은 사이즈의 이미지 그룹을 octave

       —> 이렇게 하는 이유는 물체를 볼 때 거리에 따라 명확하거나 흐리게 볼수도 있고, 크거나 작게 보이기도 하는 현상을 반영하려고 수행

   • 1번의 과정을 통해 다양한 scale 값으로 가우시안 blur 처리된 4그룹의 octave, 총 20장 이미지 생성

2. Difference of Gaussian (DoG)연산

   • 이미지에서 엣지, 코너 정보를 도출하는데 사용하는 방법

   • Difference of Gaussian (DoG) 과정

     

     

     • 각 단계에서 인접한 두 개의 blur 이미지들간의 차를 구함
     • 중간단계의 DoG 이미지는 검은색 이미지가 아닌 희미하게 얼룩말 형태를 나타냄 (정규화 수행시 더 잘보임)
     • 모든 octave의 총 20장이미지에서 4장씩 16장의 DoG 이미지 생성

3. keypoint들 찾기

   • 전 단계의 과정을 통해 총 16장의 DOG이미지 에서 극대값,극소값들의 대략적인 위치를 구함

     • 극소값, 극대값 찾는방법

       

       • 한 픽셀에서 극대값, 극소값을 찾기위해 동일한 octave 3장의 DOG 이미지가 필요
       • X로 체크된 픽셀 주변의 8개 픽셀 + 위아래 9개 픽셀 = 총 26개 픽셀을 사용
       • X로 체크된 픽셀과 26개의 픽셀을 비교해 X픽셀이 가장 작거나, 가장클때 keypoint로 선정
       • 이 방법을 통해서 DoG 이미지들 사이에서 극대값들을 찾음

     • DoG 이미지들 사이에서 극대값, 극소값을 찾는과정

       Octave중 1개에 대해서 과정을 확인

       • 1차 극대값 극소값 찾기

         

         • 극대값, 극소값에 흰색점이 있다고 하는데 잘안보이지만 위의 (극대값,극소값을 찾는과정)의 단계를 통해 일차적으로 keypoint를 찾아냅니다.
         • 여기서 4장의 DoG를 만들기위해서 5장의 scale space를 만들고 최종적으로 4장의 DoG를 사용해 2장의 극대값, 극소값 이미지를 생성
         • 총 4그룹의 octave에서 각각 2장씩 총 8장이 됩니다.
         • 이 과정에서 얻은 keypoint는 1차적인 극대값, 극소값이고 이를 사용해 실제 극대값, 극소값을 추정

       • 2차 극대값, 극소값 찾기

         

         • 파란색 X가 1차적으로 찾은 극대값이면 빨간별이 실제 극대값

         • 1차적으로 얻은 극대값으로 실제 값을 추정할수 없음 이를 해결하기 위해 테일러 2차 전개를 사용

           • 테일러 2차 전개

             

             • D = DoG 이미지, x = $(x, y, σ)^T$
             • 위에 식을 x에 대한 미분을 수행하면 밑의 식 도출

             

             이 과정을 통해 안정적인 성능을 나타나게 함

4. 나쁜 keypoint들 제거

   • 3번 단계에서 얻은 keypoint 중에서 활용가치가 떨어지는 것을 제거하는 단계

   • 총 두 가지 기준으로 나쁜 keypoint 제거

     • 낮은 contrast를 가지고 있는 것을 제거

       contrast = 밝은 곳과 어두운 곳 사이에 나타나는 밝기차이, 명암비

     • DoG 이미지에서 keypoint들의 픽셀의 값이 threshold(특정 값)보다 작으면 제거

       • 테일러 전개를 활용해 픽셀을 구함

         

         위 x는 3단계에서 구한 x 미분값 이걸 다시

         

         에 대입해서 밑의 식을 도출

         

         이 값의 절대값이 특정 값보다 작으면 그 값은 keypoint에서 제외

     • Edge 위에 존재하는 keypoint를 제거

       • DoG가 Edge를 찾을때 픽셀에 매우 민감하게 찾음, 이로인해서 약간의 noise에도 반응할 위험존재

       • noise를 edge를 통해 찾는것 그래서 edge 위에 있는 극값들을 keypoint로 사용하기에는 위험성이 생김, 이걸 방지하기 위해 코너 부분의 극값들만 남김

       • 위에서 설명한 과정을 수행하기위해 keypoint에서 수직 수평 그레디언트 계산

         • 이미지 gradient 계산식

           

           이를 통해 gx = 수평 gradient, gy = 수직 gradient

         • 위에서 얻은 gx,gy로 코너, flat, 엣지 검출

           

         • 이렇게 얻은 코너, flat, 엣지 중 코너만을 남김

           • Hessian Matrix 사용하여 코너 검출

   • 최종적으로 나쁜 keypoint 제거 그림

     

5. keypoint들에 방향 할당

   • 위의 과정을 통해 keypoint를 얻었고 이 keypoint들은 scale invariance를 만족함, 이제 rotation invariance를 갖게 하는 것이 목적

     • scale invariance : 척도가 적용되도 값이 변하지 않는 특성
     • rotation invariance : 회전이 적용되도 값이 변하지 않는 특성

   • keypoint 주변의 그레디언트 방향과 크기를 모음, 그후에 가장 두드러지는 방향을 찾아서 keypoint 방향으로 할당

     

     • keypoint 주변에 노란색 윈도우 만들어 주고 가우시안 blur 처리수행

     • 그안의 모든 픽셀의 그레디언트 방향과 크기를 공식을 통해 구함

     

     • 위에서 봤던 그레디언트 크기,방향 공식임
     • 공식 적용 후 그림

     

     • 그레디언트 크기에는 가우시안 가중함수(σ)를 keypoint에 가까울수록 더 큰값, 멀수록 작은값 할당

       • 그레디언트 크기에 가우시안 가중함수 곱한 그림

         

     • 각 keypoint 방향 할당 방법

       • 36개의 bin을 가진 히스토그램 생성

       • 360도를 0-9,10-19....350-359도로 10도씩 36개

       • 구해진 그레디언트 방향이 위에 속하는 범주에 그레디언트 크기를 더해줌

         

       • 여기서 가장 높은 bin의 방향이 keypoint 방향으로 할당

       • 만들어진 히스토그램에서 80%이상을 넘는 bin이 각각 keypoint 방향으로 설정(위그림에서는 2개의 keypoint로 분리)

       • 이런식으로 keypoint 방향 할당

6. 최종적으로 SIFT 특징 산출

   • 위에서 keypoint 결정했고 각각의 keypoint의 위치와 스케일,방향을 알고있음

   • 얻은 keypoint는 scale invariance,rotation invariance을 만족함

   • 각각의 keypoint의 특징을 128개의 숫자로 표현, 전체를 1616 윈도우로 세팅하고 다시 각각 작은 44 윈도우로 설정 고유한 128개 특성 추출

     

     • 이제 16개의 작은 윈도우에 속한 픽셀들의 gradient의 크기,방향 계산
     • 전단계와 유사하게 bin을 8개만(0-44,45-89,90-134...320-539)
     • gradient 방향과 크기로 bin 할당
     • 16개의 윈도우가 각각 히스토그램을 가지고 있음 (16개 * 8 = 128)
     • 얻어진 128이 keypoint 고유 특성

   • 128개 특성 벡터는 이미지가 회전하면 변하기 때문에 회전 의존문제를 해결하기 위해 keypoint의 방향을 각각의 gradient 방향에서 빼줌 → 각각의 gradient 방향은 keypoint 방향에 대해 상대적이게 됨

     • 예시
       • keypoint 방향이 20-29도 24.5도를 keypoint 주변 16개의 4x4 윈도우 방향에서 빼주면, 16개의 윈도우 방향은 keypoint 방향에 상대적이됨

   • 밝기 의존성 해결하기위해 정규화 수행

   • 최종적으로 keypoint에게 고유특성을 얻음

SIFT 이미지 매칭 방법

• 위 과정에서 얻은 고유특성을 통해 두 이미지 사이 각각의 keypoint를 찾고 두 이미지 사이 고유특성의 차이가 작은곳 끼리 매칭

HOG, SIFT을 통해 현재의 object-detection으로 발전하게 됨