피팅-매칭 문제란?

  • 피팅의 목표:
    • 어떤 파라미터 모델을 통해 데이터로부터 특정 양을 맞추는 것
    • 그 모델의 파라미터를 추정하는 것
  • 모델의 형태
    • 직선
    • 곡선
    • homographic transformation
    • fundamental matrix
    • shape models
  • 예시:
    • 배니싱 포인트 계산을 위해 선을 만드는 점들을 피팅하기
    • 두 이미지 사이의 점들을 통해 homographic transformation을 추정하는 것
    • 8포인트 알고리즘
    • 2차원 모양 템플릿 피팅
    • 3차원 사물 템플릿 피팅
  • 피팅의 문제점:
    • 노이즈
    • 아웃라이어
    • 결측치
    • 인트라클래스 바리에이션(노이즈)

피팅법 1: 최소제곱법

직선 피팅

  • $n$개의 점 페어가 있을때, 모델은 $y_i-mx_i-b=0$, 파라미터는 $m, b$
  • 이 $E=\sum^n_{i=1}(y_i-\hat{y}_i)^2$ 에러(residual)을 최소화하는 파라미터를 찾으시오→$E=\sum^n_{i=1}(y_i-mx_i-b=0)^2$
  • Projective하게 표현하면 $E=||Y-Xh||^2$ 표현도 가능($h=\left[ m,b \right]^\top$)
  • 이를 미분하여 계산하고, $h$에 대해 explicit하게 풀면 $h=(X^\top X)^{-1}X^\top Y$
    • 사실 이건 pseudo-inverse라고 선형대수에서 나오는 계산값임
    • 수직한 선에 대해 못푸는 문제가 있음
  • 수직한 선에 대해 푸는 좀 더 general한 수식표현: projective case에서 직선 $h=(a,b,d)$와 점 $A_i=(x_i, y_i, 1)$ 사이의 관계를 고려→$Ah=0$
  • 실제론 점이 많아서 해가 또 없어지는데? SVD

호모그래피 피팅

  • 여기서도 $Ah=0$으로 모델링

장단점

  • 장점:
    • 노이즈에 강함
  • 단점:
    • 아웃라이어에 약함(에러가 제곱이라 레지듀얼 코스트가 커짐)
  • 아웃라이어에 강해지는 방법
    • 코스트 함수를 큰 값에 대해 너무 커지지 않게 한다: $C(u_i, \sigma) = \frac{u_i^2}{u_i^2+\sigma^2}$→너무 커지면 1로 수렴
    • 다만 이렇게 설정하면 스케일 파라미터 $\sigma$를 정해줘야 함
    • 쨌든 비선형이라 최적화 스텝을 반복적으로 밟아줘야되고, 보통 초기해를 처음 구한 closed form으로 해서 구함

피팅법 2: RANSAC

  • 기본철학(투표 전략): 데이터 원소들이 하나 또는 그 이상의 모델에 투표함
    • 가정 1: 노이즈 포인트는 투표에서 한 모델만 집중적으로 뽑지 못하고 일관적이지 않을 거야(아웃라이어가 거의 없음)
    • 가정 2: 충분히 많은 데이터 포인트가 있어서 좋은 모델을 투표할 수 있을거야(결측치가 거의 없음)
  • 아웃라이어와 결측치에 강하게 하자!

직선 피팅

  • 위 가정처럼 좋은 점이 많고, 아웃라이어가 일관적 투표를 못할거라고 가정
  • RANSAC(RAndom SAmple Consensus): 점을 인라이어, 아웃라이어로 구분하는 함수 $\pi$를 찾는 알고리즘. 이 함수의 아웃라이어 갯수가 최소가 되도록 하며, 인라이어 residual 값이 $\delta$보다 작아야함.
  • 이 경우 RANSAC 알고리즘은 다음과 같다
    1. 모델을 맞추기 위해 최소 요구되는 사이즈로 랜덤 샘플을 뽑는다.
    2. 샘플로부터 추정모델 계산
    3. 전체 데이터셋에서 이 추정 모델에 속하는 점(인라이어)를 전부 계산한다. 기준은 모델과 인라이어 사이 residual 값이 $\delta$보다 작은 점들
      • 가장 많은 인라이어를 가지는 모델이 나올 때까지 1-3번 반복
  • 근데 샘플을 몇 개씩 집어야함? 다 할 수도 없고 다 할 필요도 없는데
  • $N$번 시행을 반복하면 확률 $p$로 최소 1개는 실제 아웃라이어가 아니게 된다고 하자. 이러한 $N$이면 충분하다. 이 때 보통 $p=0.99$로 잡는다
  • $s$를 피팅에 필요한 최소한의 점 개수, $e$를 아웃라이어 비율이라고 하자.
  • 이 경우 $N=\log(1-p)/\log(1-(1-e)^s)$
  • 다른 예시론 프로젝티브 트랜스포메이션 H 피팅, 펀다멘탈 매트릭스 F 피팅 등이 있다.

장단점

  • 장점:
    • 쉽고 간단하게 적용 가능
    • 다른 컨텍스트에서도 성공적임
  • 단점:
    • 조정할 파라미터가 많음:
    • 정확도와 시간이 반비례
    • 인라이어/아웃라이어 비율이 너무 작으면 사용 불가

피팅법 3: 허프 변환

알고리즘

  • 아이디어: 파라미터를 찾지 말고, 파라미터 공간에 있는 점을 찾자
  • 문제점: 파라미터 공간은 unbounded→극좌표계를 쓰자→이러면 이미지 크기에 의해 반지름 바운드, 각도는 180도로 바운드
  • 즉 허프 공간에서 교점을 구하면 됨. 근데 노이지하면 교점이 안생기지 않아?
  • 허프 공간의 그리드를 그려서 그리드 내부 교점의 갯수를 계산한다.

예시

  • 차선 감지
  • 배니싱 포인트 계산

장단점

  • 장점:
    • 모든 점이 독립적으로 작업되므로, 아웃라이어와 결측치를 처리할 수 있다
    • 노이즈에 어느정도 강함: 노이즈는 어떤 한 셀에 묶여있을 가능성이 낮다
  • 단점:
    • 일관된 노이즈가 있으면 가짜 피크가 생김
    • 노이즈와 그리드 사이즈는 반비례(좋은 답 찾기 힘듦)
    • 고차원 모델을 다루기 힘들다

일반화된 허프 변환

  • 어떤 형태의 중심과 형태 파츠들의 위치를 계산해서 형태를 매개변수화함.
  • 측정값 집합이 주어지면, 허프 공간에서 투표를 함
  • 사물 인지 태스크에 사용됨(implicit shape model)

멀티모델 피팅

  • 종류
    • 점차적인 피팅
    • E.M.(확률 피팅)
    • 허프 변환
  • 점차적인 피팅: 로칼 제약을 걸고 데이터 포인트를 순차적으로 스캔했다고 하자.
    1. $N$개의 포인트를 정하고 직선을 이 점들에 맞춘다
    2. 레지듀얼을 계산한다.
    3. 새 점 하나를 추가하고, 새로 직선을 맞추고 새로 레지듀얼 값을 계산한다.
    4. 레지듀얼이 충분히 작아질 때까지 반복
      • 레지듀얼이 특정 쓰레시홀드를 넘으면, 새 모델(직선) 피팅을 시작한다.
  • 허프 변환: 이전과 동일함

피팅으로부터 매칭을 얻다

  • 두 이미지의 특징을 매칭시킬 수 있다.
  • 생김새로만 매칭시키기:
    • 이미지 1에서 이미지 2로 가는 호모그래피를 피팅한다(RANSAC으로)
    • 나쁜 매칭은 아웃라이어로 계산되므로 자연스럽게 배제된다.