Local Invariant features

Image matching

• 어떠한 image에 대해서 같은 특징을 가지고 있지만 다른 구도로 찍거나 주변 다른 feature들이 달라졌음에도 같은 feature를 matching할 수 있는지?
  

Example : panorama stitching

• AUTOSTITCH : image를 자동으로 꼬매준다.
  그렇기 위해서는 연속된 두 image 사이의 공유하는 feature가 있어야 한다.
  

Image Matching에 왜 local feature를 사용하는가?

• gloabl representation은 한계점이 있다.
  • loss of spatial information
  • difficulty in handling varied object sizes
  • diffifulty with occlusion (퇴색, 가려지는 것)
  • reduced discriminative power
• instead describe and match only local regions
  • spatial information preservation
  • robustness on occlusion and intra-category variations
  • discriminative power
  • hierarchical information processing
  • interpretability
    

잘못된 matching 절차

• step 1 : find a set of distinctive key points (x)
• step2 : define a region around each keypoint (N x N)
• step3 : extract and normalize the region context
• step4 : compute a local descriptor from the normalized region
• step5 : match local descriptors
  image를 표현할 수 있는 vector 형태를 local descriptor로 추출.
  local descriptor : 특징을 추출하는 알고리즘
  해당 vector들의 유사도를 측정하여 similarity Threshold(T)보다 작으면? matching.아니면? 다르다.
  

local features and alignment

• align : image1의 feature들과 image2의 feature들이 각각 어떻게 match되는지 구하는 과정
  1. detect point feature
  2. find corresponding pairs
  3. use these pairs to align the image
• 하지만 위 과정은 문제점이 발생한다.
  1. 두 image에 대해서 독립적으로 feature를 뽑아내는데, image가 달라졌을 때도 동일한feature를 detect해야 한다.
     즉, repeatable detector여야 한다.
  2. 대응되는 점들을 찾아야 하는데,
     그러기 위해 image에 대해 geometric, illumination 변화에 대해 robust해야 한다.
     즉, reliable and distinctive feature descriptor(geometric, illumination 변화에 강인한)여야 한다.
     • gemoetric 변화 : 
       같은 물체를 rotation, scale, view point를 달리 하여 찍었을 때도 detect할 수 있어야 함.
       
     • illumination 변화 :
       같은 물체에 대해 조명을 달리 해서 찍어도 detect할 수 있어야 함.
       

• Invariant local feature :
  geometric, illumination 변화 등에 대해서 강인하게 똑같은 feature를 뽑을 수 있어야 한다.
  이러한 것들을 Local descriptor를 통해서 특징화하여 뽑아낼 수 있다. (계속 공부할 것임)
  
• Main question :
  • what point are distinctive? and they are repeatable?
    • distinctive -> features, keypoints, salient points
    • repeatable -> it can be re-detected from othe views
  • how to describe a local region?
  • how to establish correspondence? = compute matches?

---

Keypoint Localization

Point features : corners vs. blob detectors

• corner :
  하나 이상의 edge들이 만들어 내는 특징이다.

  • high localization accuracy
  • better for visual odometry
  • less distinctive than a blob
  • e.g : Harris, Shi-Tomasi, SUSAN, FAST

• blob :
  물방울처럼 동그란 패턴을 blob이라고 한다.

  • less localization accuracy than a corner
  • better for place recognition
  • more distinctive than a corner
  • MSER, LOG, DOG, SURF

Moravec corner detector

• small window를 움직이면서 sum of squared difference(SSD)를 측정한다.
  
  • flat : 아무런 SSD의 변화가 없다
  • edge : 한 방향에 대한 SSD 변화가 있다.
  • corner : 적어도 2개 이상의 방향에 대한 SSD 변화가 있다.

Harris corner detector

• differential calculus를 이용한다.
• $P$ size를 갖는 patch의 center $(x, y)$를 $(x+\Delta x, y+\Delta y)$로 옮긴다.
  그리고나서 SSD를 구한다.
  이는 approximate 1st order Taylor expansion에 의해 다음과 같이 쓸 수 있다.
  approximate 1st order Taylor expansion : 그러면 두 변수$(\Delta x, \Delta y)$에 대한 quadratic function이 된다.그러면 이 식을 Matrix form을 바꿀 수 있다.

what does this M matrix reveal?

• consider an edge or region :
  

• now, let's consider an axis-aligned corner :
  

• Genral case
  SSD의 eigen vector, eigen value로 elipse를 구함.

• Interpreting the eigenvalues
  classification of image points using eigenvalues of $M$

  • Shi-Tomasi detector :
    $R=min(\lambda_1, \lambda_2) > threshold$ 라는 corner response function을 이용하여
    corner detection.
    

Harris corner detector

• 하지만 한 image의 모든 patch에 대해 eigenvalue를 계산하는 것은 비용이 큼.
  과정을 단순화시키기 위해서 corner response functionHarris corner detector가 나옴.

• $(\lambda_1, \lambda_2)$을 이용했던 corner response function과는 달리,
  $det(M), trace(M)$를 이용함.
  

algorithm

• compute derivatives in $x$ and $y$ directions $(I_x, I_y)$ with Sobel filter :
  noise 제거 작업
• matrix $M$을 구하기 위해, compute $I^2_x, I^2_y, I_x, I_y$
• convolve $I^2_x, I^2_y, I_x, I_y$ with a box filter to get matrix $M$
• compute Harris corner measure $R$ (Shi-Tomashi or Harris)
• find points with large corner response $(R > threshold)$
• take the points of local maxima of $R$

workflow

• Harris detector는
  두 개의 서로 다른 Image에 대해서, corner를 탐지하는 역할.
  • 특정한 window size에 대해서, 해당 image들을 옮겨가면서 해당 영역에 대한 SSD를 계산
  • 미리 정해놓은 corner response $R$을 계산하여 threshold와 비교.
  • non-maxima suppression 적용하여 해당 pixel값보다 큰값을 supression.

some properties

• rotation invariance :
  ellipse rotates but its shape(eigenvalues) remains the same
  ➡️ corner response $R$ is invariant to image rotation
  

• but, scale non-invariance :
  image의 scale이 줄면, 정해진 patch가 적용되는 부분도 달라짐.
  

• repeatability = #correspondence detected / # correspondences present
  (scale 후 corner 수 / scale 전 corner 수)
  다른 image에 대해서 동일한 속성을 찾아낼 수 있는지에 대한 지표.
  
  scale 변화에 따라서 탐지되는 corner의 수는 급격히 줄어든다.
  따라서 어느정도 scaling을 할 것인지 타협점을 찾아야 한다.