지역 특징

발상

대응점 문제

이웃한 영상에 나타난 같은 물체의 같은 곳을 쌍으로 맺는 일
파노라마, 물체 인식, 물체 추적, 스테레오 비전, 카메라 캘리브레이션 등에 필수

물체 추적에서 대응점 찾기

반복성이 뛰어난 특징 필요

지역 특징의 발상

좁은 지역을 보고 특징점 여부 결정
물체의 실제 모퉁이에 위치해야 한다는 생각을 바꿈
반복성을 더 중요하게 취급하는 발상의 전환

지역 특징의 표현

(위치, 스케일, 방향, 특징기술자)
위치와 스케일은 검출 단계에서
방향과 특징 기술자는 기술 단계에서

지역 특징의 조건

반복성 : 같은 위치에서 높은 확률로 검출
불변성 : 물체에 변환이 가해져도 특징 기술자의 값이 비숫해야됨
분별력 : 물체의 다른 곳에서 추출된 특징과 차이가 있어야 됨
지역성 : 작은 지역을 중심으로 특징 벡터 추출로 가림에 강건한 매칭이 가능
적당한 양 : 특징점이 많으면 정확한 추적이 가능하지만 계산이 과다해짐
계산 효율 : 실시간 추적의 경우 빠른 계산이 필요

이들 조건과 상충 관계 존재

응용에 따라 적절히 조절할 필요가 있음
- 적당한 특징점 vs 계산 효율
- 분별력 vs 지역성

이동과 회전 불변한 지역 특징

모라벡 알고리즘

여러 방향에 대해 색상 변화를 측정하는 제곱차의 합이라는 식 제안 \(S(v, u) = \sum_y\sum_x w(y, x)(f(y + v, x + u) - f(y, x))^2\) \(-1 \leq u, v \leq 1\) w(y, x)는 비교할 범위 바스크
- w(y, x)가 3X3 마스크라면,
\(w(b, a) = \begin{cases} 1, b \in [y-1, y + 1], a\in [x-1, x+1] \\ 0,\ otherwise \end{cases}\)
- 화소 위치 (y, x)가 (4, 3)이고 w(y, x)가 3X3인 경우 \(S(v, u) = \sum_{3 \leq y \leq 5}\sum_{2 \leq x \leq 4}(f(y+v, x + u) - f(y,x))^2\)

식의 의도

c는 모든 방향에서 변화가 없어 S맵의 모든 요소가 0. 지역 특징으로 자격이 없음
b는 수평 방향만 변화가 있어 S맵의 좌우 이웃만 큰 값. 지역 특징으로 부족
a는 모든 방향으로 변화가 있어 S맵의 8이웃 모두 큰 값. 지역 특징으로 훌륭함

특징 가능성 값 측정

S맵에서 상하좌우 네 이웃 화소의 최소값 \(C = min(S(0, 1), S(0, -1), S(1, 0), S(-1, 0))\)

해리스 특징점

모라벡은 지역 특징의 길을 열었지만 현실적이지 않음

실제 세계의 영상은 상하좌우 이웃만 보는 것으로 부족
해리스의 확장
잡음에 대처하기 위해 가우시안 적용하여 가중치 제곱차의 합을 식으로 정의 \(S(v, u) = \sum_y \sum_x G(y, x)(f(y + v, x + u) - f(y, x))^2\)
테일러 급수 \(f(x) = f(a)+f^{(1)}(a)(x-a)+\frac{f^{(2)}(a)(x-a)}{2!}\\+\cdots+\frac{f^{(n)}(a)(x-a)}{n!}\) \(f(x, y) = f(a, b) + f_x(a,b)(x-a)+\frac{f_{xx}(a,b)(x-a)}{2!}+\\ \frac{f_{yy}(a,b)(y-b)}{2!}+\frac{2f_{xy}(a,b)(x-a)(y-b)}{2!}\\+\cdots\)

2차 모멘트 행렬을 통한 특징점 검출

테일러 확장으로 식 성립 \(f(y+v, x+u) \tilde{=} f(y,x)+vd_y(y,x)+ud_x(y,x)\)
이를 가우시안 적용하여 가중치 제곱차의 합의 식에 적용 \(S(v,u) \tilde{=} \sum_y\sum_xG(y,x)(vd_y(y,x)+ud_x(y,x))^2\)

2차 모멘트 행렬 A의 특성

(v, u)는 실수 가능
A는 하소 주위의 영상 구조를 표현하기 때문에 A만 분석하면 지역 특징 여부 알 수 있음((v, u)를 변화시키면서 맵을 생성할 팰요 없음)

해리스의 특징 가능성 계산

A의 고유값 \(\lambda_1, \lambda_2\) \(C = \lambda_1 \lambda_2 - k(\lambda_1 + \lambda_2)^2\)

\(C = (pq - r^2)-k(p+q)^2\) \(A = \begin{pmatrix} p & r \\ r & q \end{pmatrix}\)

해리스 특징점의 분석

물체의 실제 모퉁이 뿐 아니라 블롭에서도 검출
이후에는 모퉁이 대신 특정점 또는 관심점으로 부름
이동과 회전에 불변
스케일에는 불변 아님

스케일 불변한 지역 특징

사람은 스케일 불변인 특징 사용

거리에 상관없이 같은 물체를 같다고 인식
거리에 따라 세세한 내용에만 차이가 있음

스케일 공간 이론은 컴퓨터 비전에 스케일 불변 가능성 열어줌

다중 스케일 영상 구현하는 방법

입력은 영상 한 장. 여러 거리에서 보았을 때 나타나는 현상을 흉내 내는 수밖에 없음
가우시안 스무딩과 피라미드 방법

가우시안 스무딩은 스케일을 연속값으로 조절할 수 있는 장점

스케일 공간의 미분은 정규 라플라시안 사용

라플라시안 : \(\nabla^2 f = d_{yy}+d_{xx}\)
정규 라플라시안 : \(\nabla_{normal}^2 f = \sigma^2 \left\vert d_{yy} + d_{xx}\right\vert\)

SIFT

구축

1단계 : 다중 스케일 영상 구축

가우시안 스무딩과 피라미드 방법을 결합해 사용

2단계 : 다중 스케일 영상에 미분 적용

식의 정규 라플라시안 사용. 시간이 많이 걸려 유사한 DOG 사용
DOG는 가우시안 영상은 이미 있고 이웃한 가우시안을 빼면 되기 때문에 획기적으로 빠름

3단계 : 극점 검출

3차원에서 비최대 억제 적용

특징점은 (y, x, o, i)로 표현

(y, x)는 위치 표현, 옥타브 o와 DOG 번호 i는 스케일 표현

SIFT 기술자

특징점 주위를 살펴 풍부한 정보를 가진 기술자 추출

불변성 달성이 매우 중요
기술자 추출 알고리즘
o와 i로 가장 가까운 가우시안 영상을 결정, 거기서 기술자를 추출하여 스케일 불변성 달성
기준 방향을 정하고 기준 방향을 중심으로 특징을 추출하여 회전 불변성 달성 -> 주변을 10도 간격으로 양자화하여 히스토그램을 만들고 최대값에서 세타 추출
특성 기술자 x는 세타를 중심으로 16X16의 윈도우의 각 칸을 다시 4X4로 나누고 그래디언트를 계산 방향을 8개로 양자화하여 히스토그램을 그릴 때 각 방향의 크기를 고려해서 만들고 x를 단위 벡터로 바꿈으로써 조명 불변성 달성 -> \(\frac{x}{ \parallel x \parallel}\)
이러한 과정을 거치면 이제 특징점은 \((y, x, \sigma, \theta, X)\)가 됨 -> 하나의 이미지에서 여러 특징점을 찾아 각각이 특징점을 표시

SIFT 검출

import cv2 as cv

img = cv.imread('img.jpg')
gray = cv.cvtColor(img, cv.COLOR_BGR2GRAY)

sift = cv.SIFT_create()
kp, des = sift.detectAndCompute(gray, None)

gray = cv.drawKeypoints(gray, kp, None, flags = cv.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)
cv.imshow('sift', sift)
k = cv.waitKey()
cv.destroyAllWindows()

SIFT_create함수를 호출하여 SIFT특징점을 추출하는데 쓸 sift객체를 생성
- nfeatures : 검출할 특징점 개수 지정
- nOctaveLayers : 옥타브 개수 지정
- contrastThreshold : 테일러 확장으로 미세 조정할 때 쓰는 매개변수, 값이 클 수록 적은 수의 특징점이 검출됨
- edgeThreshold : 에지에서 검출된 특징점을 걸러내는데 쓰는 매개변수, 값이 클수록 덜 걸러내 더 많은 특징점이 발생
- sigma : 옥타브 0으 입력 영상에 적용할 가우시안의 표준펴ㅕㄴ차
detectAndCompute 함수를 호출 -> 특징점과 기술자를 찾아 각각 kp, des 객체에 저장

kp = sift.detect(gray, None)
des = sift.compute(gray, kp)

특징점 검출과 기술자 추출을 나누어 처리

SIFT의 변종

특징점 검출에 SURF, FAST, AGAST 등
기술자 추출에 PCA-SIFT, GLOH, 모양 컨텍스트, 이진 기술자 등

매칭

매칭은 컴퓨터 비전의 다양한 문제에서 핵심 역할

물체 인식
물체 추적
스테레오
카메라 캘리브레이션

매칭 전략

매칭은 까다로운 문제
- 두 영상 모두 특징점이 많아 후보 쌍이 아주 많음
- 잡음이 섞인 기술자
문제의 이해
- 두 영상에서 추출한 기술자 집합에서 같은 물체의 같은 곳에서 추출된 쌍을 모두 찾는 문제
- 매칭을 적용하는 다양한 상황
  - 물체 인식에서는 물체의 모델 영상이 A고 장면 영상이 B
  - 물체 추적이나 스테레오는 두 영상이 동등한 입장
- 가장 쉬운 매칭 방법
  - mn개 쌍 각각에 대해 거리 계산하고 거리가 임계값보다 작은 쌍을 모두 취함
두 기술자의 거리 계산 \(d(a,b) = \sqrt{\sum_{k = 1,d}(a_k-b_k)^2} = \parallel a-b \parallel\)
매칭 전략
- 고정 임계값 : 식을 만족하는 모든 쌍을 매칭으로 간주
- 최근접 이웃 : ai는 가장 가까운 bj를 찾고 ai와 bj가 식을 만족하면 매칭 쌍
  - 식 \(d(a_i, b_j) < T\)
- 최근접 이웃 거리비율 : ai는 가장 가까운 bj와 두번째 가까운 bk를 찾음. bj와 bk가 식을 만족하면 ai와 bj는 쌍. 세가지 전략 중 가장 높은 성능 \(\frac{d(a_i, b_j)}{d(a_i, b_k)} < T\)

매칭 성능 측정

성능 측정은 아주 중요
- 알고리즘 개선이나 최선의 알고리즘을 선택하는 기준
- 현장 투입 여부 결정하는 기준
정밀도와 재현율 정밀도 : \(\frac{TP}{TP + FP}\) 재현율 : \(\frac{TP}{TP+FN}\) F1 : \(\frac{2X정밀도X재현율}{정밀도 + 재현율}\) 정확률 : \(\frac{TP+TN}{TP+TN+FP+FN}\)
ROC 곡선과 AUC
- 식에서 T를 작게하면 거짓 긍정률은 작아짐
- T를 크게하면 거짓 긍정률이 커지는데 참 긍정률도 따라 커지는 경향

빠른 매칭

속도라는 성능 지표
- 실시간 요구되는 응용에서 양보할 수 없는 강한 조건
- 컴퓨터 과학에서 개발한 빠른 자료 구조 도입하여 사용
  - 이진 탐색 트리, 해싱
kd트리
- 특징점 매칭의 독특한 성질 때문에 이진 탐색 트리 그대로 적용 불가능
  - 특징점은 여러 값으로 구성된 특징 벡터
  - 같은 값이 아니라 최근접 이웃을 찾음
- kd트리는 이런 경우에 적합한 자료구조
  - 예시 d = 2, m = 10인 상황
    - X = {x1 = (3, 1), x2 = (2,3), x3 = (6,2), x4 = (4,4), x5 = (3,6), x6 = (8, 5), x7 = (7, 6.5), x8 = (5,8), x9 = (6,10), x10 = (6,11)}
    - 두 축의 값은 (3, 2, 6, 4, …, 6), (1, 3, 2, 4, …, 11). 두번째 축의 값의 분산이 더 큼->두번째 축 선택
    - 두번째 축 정렬. 중앙값은 j = 5. 즉 다섯번째 기술자 x5가 분할 기준
    - 루트 노드에 x5를 배치. 2번 축을 기준으로 분할했다는 정보 기록
위치 의존 해싱
- 일반적인 해싱
  - 해시 함수로 O(1) 시간에 탐색 달성
  - 효율적인 해시 함수와 충돌 해결 기법이 개발되어 있음
- 특징점 매칭에 사용하려면 개조 필요
  - 특징 벡터이고 최근접 이웃 찾아야 하기 때문
  - 충돌을 최소화하는 일반 해싱과 달리 비슷한 특징 벡터를 같은 칸에 담아야 함
  - 위치 의존 해싱은 이런 조건을 만족하는 방법
빠른 매칭을 보장하는 라이브러리 : FLANN, FAISS

호모그래피 추정

SIFT 검출과 기술자 추출 이후에 해야 할 일

물체 위치 찾기
호모그래피는 이런 일을 해줌

3차원 투영

3차원 공간에 있는 평면 P의 두 점 p1, p2 그리고 카메라 A, B가 있는 상황
p1, p2가 카메라의 2차원 영상 평면에 투영 반환됨

투영 반환

3차원 점 p를 동차 좌표로 표현하면 (x, y, z, 1). 투영 변환 행렬은 4X4
p1, p2가 같은 평면 상에 있다고 가정하고 z = 0으로 간주하면 3*3 행렬로 표현 가능
이런 제한된 상황에서 이루어지는 투영 변환을 평면 호모그래피라 부름

세 개의 평면이 있다 가정

물체가 놓인 평면 P, 카메라 A, B의 영상 평면
어떤 평면의 점 a를 다른 평면의 점 b로 투영하는 변환 행렬을 H \(b^T = \begin{pmatrix} b_x \\ b_y \\1 \end{pmatrix} = \begin{pmatrix} h_{00} & h_{01} & h_{02} \\ h_{10} & h_{11} & h_{12} \\ h_{20} & h_{21} & 1 \end{pmatrix} \begin{pmatrix} a_x \\ a_y \\ 1 \end{pmatrix} = Ha^T\)

방정식을 풀어 H 구하기

매칭쌍을 가지고 품
알아내야 할 값은 8개. 매칭 쌍 하나가 두 방정식을 제공 -> 최소 4개 매칭쌍이면 됨
실제에서는 많은 매칭쌍을 이용하여 최적의 H를 계산

매칭쌍을 가지고 H 추정

매칭쌍 n개를 (a1, b1), (a2, b2),…(an, bn)으로 표기하면 식이 성립
- B는 bi를 i번째 열에 배치한 3n행렬이고 A는 ai를 i번째 열에 배치한 3n행렬 \(B = HA\)

최소평균제곱오차 방법

식의 E가 최소인 H를 찾음
- numpy의 lstsq 또는 scipy의 leastsq 함수를 사용하여 풀 수 있음
- 모든 매칭 쌍이 같은 자격으로 참여하므로 강인함 없음 \(E = \frac{1}{n}\sum_{i = 1, n}\parallel Ha_i^T - b_i \parallel_2^2\)
식의 평균 대신 중앙값 사용하면 강인함 확보 가능
- 아웃라이어는 중앙값 계산까지만 영향을 미치고 수렴 여부 결정에서는 빠짐

Jayiuk Blog

지역특징

지역 특징

발상

대응점 문제

물체 추적에서 대응점 찾기

지역 특징의 발상

지역 특징의 표현

지역 특징의 조건

이들 조건과 상충 관계 존재

이동과 회전 불변한 지역 특징

모라벡 알고리즘

식의 의도

특징 가능성 값 측정

해리스 특징점

모라벡은 지역 특징의 길을 열었지만 현실적이지 않음

2차 모멘트 행렬을 통한 특징점 검출

2차 모멘트 행렬 A의 특성

해리스의 특징 가능성 계산

해리스 특징점의 분석

스케일 불변한 지역 특징

사람은 스케일 불변인 특징 사용

스케일 공간 이론은 컴퓨터 비전에 스케일 불변 가능성 열어줌

다중 스케일 영상 구현하는 방법

가우시안 스무딩은 스케일을 연속값으로 조절할 수 있는 장점

스케일 공간의 미분은 정규 라플라시안 사용

SIFT

구축

1단계 : 다중 스케일 영상 구축

2단계 : 다중 스케일 영상에 미분 적용

3단계 : 극점 검출

특징점은 (y, x, o, i)로 표현

SIFT 기술자

특징점 주위를 살펴 풍부한 정보를 가진 기술자 추출

기술자 추출 알고리즘

SIFT 검출

SIFT의 변종

매칭

매칭은 컴퓨터 비전의 다양한 문제에서 핵심 역할

매칭 전략

매칭 성능 측정

빠른 매칭

호모그래피 추정

SIFT 검출과 기술자 추출 이후에 해야 할 일

3차원 투영

투영 반환

세 개의 평면이 있다 가정

방정식을 풀어 H 구하기

매칭쌍을 가지고 H 추정

최소평균제곱오차 방법