Mid level features: Shapes

Shapes

• Shape은 Color, Texture보다 고차원적인 피처임.
• Color, Texture는 이미지 전체에 나타나는 속성이지만, Shape은 specific region에만 나타나기 때문임.
• Segmentation 문제 해결에서 shape description을 위한 interests operator가 사용됨. 

Shape descriptor

Shape은 Region descriptors, Boundary, Interest points (corners)로 정의함.

Region based shape descriptors

모양의 기하학적 속성

• 크기, 무게중심, 둘레, 둘레의 길이, 원형성, 연장선, 반경의 평균 및 표준편차, 2차 모멘트(행, 열, mixed), 바운딩 박스, 바운딩 박스로부터 좌표 상의 거리, 데이터 분포를 모델링한 타원의 축의 길이와 방향   
• position(위치), orientation(방향), scale(크기)에 독립적인 피처를 추출해야 좋음.

Zero-order moment

• 모멘트 사용 이유: 기하학적 모멘트는 이미지 분포의 공간적 특성을 표현함.
• Zero-order moment: 이미지의 모든 픽셀의 합 (2차원 이미지에서는 공간.)

Centroid

• 이미지에서 객체의 공간적 위치를 결정하는 1차 모멘트 
• 2차원 이미지에서 기하학적 중심 (작성중!!!!!)

Second Moments

• 2차 공간 모멘트 3종류 (row, mixed, column)

Perimeter and Perimeter Length

• Perimeter는 점의 리스트이고, Perimeter Length는 그 점들이 이루는 둘레의 길이로 의미가 다름.

• 4-connected adjacency와 8-connected adjacency의 차이
  둘레를 표현할 때 사용하는 픽셀 방향 개수에 차이가 있음.

Circularity

• Circularity1: 원에 가까울수록 둘레는 줄어듬.
• Circularity2: 평균이 주어졌을 때, 분산이 적을수록 원에 가깝고 분산이 클수록 타원에 가까움.

Orientation

• Orientation은 연장선의 방향을 통해 객체의 방향을 정의하는 것으로, 최소 2차 모멘트.
• 카이제곱 값을 최소화하는 로우와 세타를 찾아야 함.
• 센터를 지나는 무수히 많은 직선을 그릴 수 있지만, 그 중에서 거리차가 가장 적은 것이 orientation.

 

Topological region descriptors

• Topological properties로는 구멍의 개수(H), 연결되어 있는 요소 개수(C)가 있음.

• Hole counting 패턴 정의: 1은 빛이 통과하지 않는 부분(검은색) & 0은 빛이 통과하는 hole(흰색)
  
  1. External corner: 1(3개)와 0(1개)
  2. Internal corner: 0(3개)와 1(1개)
• 홀 카운팅 알고리즘
  • M은 이진 이미지로 R개의 행과 C개의 열이 있음. E는 external corner의 개수, I는 internal corner의 개수
  • 홀의 개수: (E-I) / 4

integer procedure Count_Holes(M)
{
    examine entire image, 2 rows at a time;
    count external corners E;
    count internal corners I;
    return (number_of_holes = (E-I)/4);
}

 

Boundary based descriptors

Freeman의 Chain code

Tangent-Angle histogram

Interest Operator + Descriptors (중요)

Interest operator

• 코너나 중요한 영역(Salient region) 등 이미지에서 중요한 영역을 찾음.
• Matching과 recognition에서 활용도가 높음. Search, Object recognition, Image alignment & stitching, Stereo, Tracking 등의 과제에서 사용됨.
• Interest points
  1. 0차원 구조 (점): Matching에 쓸모가 없음.
  2. 1차원 구조 (선): Edge처럼 일부분만 관찰하면 Aperture problem 발생.
  3. 2차원 구조 (코너): 코너는 Interest point임. Matching에 활용도 높음.
• Local invariant photometric descriptors
  1. Local: 물체가 가려지거나 복잡한 배경이 있어도 잘 동작하며, Segmentation 없이 이미지를 한 번에 처리함.
  2. Photometric: 픽셀의 밝기와 색상 정보를 기반으로 독특한 피처를 추출함.
  3. Invariant: 피처가 이미지 변환 및 조명 변화에 영향을 받지 않음. 
• Zhang Approach
  • Harris detector로 Interest points 추출 → Cross-correlation으로 점들을 비교 → Fundamental matrix로 검증
  • Fundamental matrix: 이미지 A(Matrix 1)의 점들을 이미지 B(Matrix 2)의 대응되는 점들에 연결함. 이때 Homography가 사용되며, least square error를 최소화하는 방정식들이 사용됨.
• 일반적인 Detector 및 Descriptor의 접근
  Interest points 추출  → Local descriptors 계산 → Correspondences 결정  → 비슷한 이미지 선별

Harris operator

• Harris detector는 Auto-correlation의 아이디어에 기반하며, 여러 방향에서의 차이를 Interest point로 인식함.

• Harris detector의 Background: Moravec Corner Detector
  • 이미지에서 Window가 4가지 방향으로 이동하며, 이들 간의 차이를 계산. → (1,0),(0,1)(1,1),(-1,1)
  • 각 픽셀의 Min difference를 계산.
  • Min images에 있는 Local maxima가 코너임.

• Harris가 Moravec를 기준으로 보완한 부분
  1. 4방향 Shift가 아닌, 모든 방향으로의 Shift를 수행.
  2. 사각형 Window 대신, Smooth한 원형 Window 사용.
  3. 간단한 Min 함수 대신, 방향에 따라 변화하는 특성을 분석.
• Harris detector의 수학적 요소

• Auto-correlation & Summed Square Difference(SSD)  ( point (x,y) & shift (Δx,Δy) )

• Auto-correlation matrix를 이용하면 discrete한 shift를 안 할 수 있음.

• 내적 값을 Rewrite.

• 중앙에 2 × 2 matrix 있음.

• Auto-correlation matrix: local neighborhood의 구조를 알 수 있음. Matrix의 eigenvalues(고유값)를 측정함.
  • 2 strong eigenvalues → Interest point
  • 1 strong eigenvalues  →  Contour
  • 0 eigenvalue  →  Uniform region 

• Corner strength: R은 코너, 엣지, 작고 평평한 영역에 대해 positive 함.

• Harris Corner 장단점 요약

장점	단점
local information discriminant greyvalue information invariance to image rotation and illumination	Not invariant to scale and affine changes

Multi-scaled operator

• 이미지에서 다양한 크기의 패치를 이용해 피처를 캡쳐하며, 방향 지향된 패치를 추출함.
• 예를 들어, 40 X 40 픽셀의 영역을 8 X 8 픽셀의 패치로 축소 가능함. (5X)
• 활용: 이미지 여러 장을 하나의 이미지로 결합하는 Image Stitching에 사용됨.
• 장점: Invariant to scale and rotation

Scale Invariant Feature Transform (SIFT)

• Harris operator의 단점을 보완하여, scale과 rotation에 invariant한 Interest Operator를 개발.
• 이미지를 Local feature coordinates로 변환. 이는 이미지가 translation, rotation, scale 및 기타 imaging parameters에 invariant할 수 있게 함.
• 특징: 피처가 local 하기 때문에 물체가 가려지거나 배경이 복잡해도 잘 동작함. 개별 피처는 객체의 큰 데이터베이스에 매칭됨. 적은 양의 객체로부터 많은 양의 피처를 추출할 수 있음. 실시간 성능이 높고, 피처 타입을 구별하는 넓은 범위로 확장될 수 있음.

출처: LOWE, David G. Distinctive image features from scale-invariant keypoints.  International journal of computer vision , 2004, 60: 91-110.

• Scale-space extrema detection: multiple scale 및 location으로 stable features를 탐색.
  • Gaussian Pyramid의 가우시안 필터로 subsampling하여, 이미지 사이즈를 줄임.
  • 기존의 LoG 필터는 시그마가 작으면 작은 객체가 detect 되고, 시그마가 크면 큰 객체가 detect 됨. LoG는 시그마 값을 바꿔가며 하나의 scale에서 여러 번 실행해야 하는 번거로움이 있음. → SIFT에서는 서로 다른 scale을 가진 2개의 가우시안을 뺀, DoG를 사용함.
  • Scale space는 옥타브로 분리됨. 예를 들어, 옥타브1은 scale σ를, 옥타브2는 scale 2σ를 사용함.  

• Keypoint localization: location과 scale을 결정하기 위해 model에 fit 함.
  • 가우시안 필터를 통한 difference에서 최대값과 최소값을 감지함. 각각의 픽셀은 인접한 8개의 픽셀과 비교됨.
  • Scale < 3 이면 stable keypoints 증가, Scale > 3 이면 stable keypoints 감소, Scale = 3 이면 최대 stable keypoints 발견.
  • Keypoint 후보가 발견되면 detailed fit을 수행함.
  • Edge response를 제거함.
• Orientation assignment: 각각의 keypoint 영역에 대해 최적의 orientation을 계산함.
  
  • Local gradient directions의 히스토그램 제작함.
  • Smoothed histogram의 peak에 표준적인 방향을 부여함.
  • 각각의 key는 stable한 2D coordinates를 만듬. (필터링에서 선택된 변수의 주된 orientation 방향을 확인함.)
• Keypoint description: keypoint 영역을 나타내기 위해 선택된 scale과 rotation에서 local image gradient를 사용함.
  • Keypoint는 위치, 크기, 방향의 3가지 정보를 가지고 있으며, 각각의 keypoint에 대해 Local image region의 descriptor를 계산함.
  • Normalization: Window를 standard orientation으로 회전시킴. 점이 발견된 scale을 기반으로 윈도우 사이즈를 Scaling 함.

Histogram of Oriented Gradient (HOG)

• 사용 방법 
  1. 패치를 Crop 및 Resize 함.
  2. 표현해야 하는 영역의 수평, 수직 gradients를 계산함. Gradient의 magnitude와 direction을 찾음. 이미지 패치를 여러 개의 셀로 분할함.
  3. 8 X 8 셀들의 gradient에 대한 히스토그램을 만듬. 9개의 bins 중 해당하는 방향에 따라 값을 넣음. 
  4. 셀들을 큰 블록으로 그룹화 함.
  5. 각각의 블록을 정규화 함. 4개의 셀들을 이용해서 histogram vectors를 정규화 함. 전체 이미지 패치에 대해 HOG feature vector를 계산함.
  6. 사람의 일부인지 판별하기 위해, SVM 분류기를 학습시킴. SVM은 Maximum margin discriminator로서 feature vector를 real number score에 맵핑함. 점수는 타겟을 배경이나 다른 물체들로부터 분리하는 목적으로 디자인 됨.
• SIFT descriptor와 비교
  R-HOG는 SIFT와 매우 유사하지만, 블록들이 orientation alignment 없이 single scale에서 dense grid로 계산되는 점이 다름. 

 

* 참고 자료

컴퓨터비전 강의자료(김은이 교수님)