가우시안 스무딩 방법 : 거리가 멀어지면 세부 내용이 점점 흐려지는 현상 모방. 표준편차를 조절하여 스케일을 연속값으로 세밀하게 조절할 수 있는 장점
연속 공간에서 유도한 수식/알고리즘을 디지털(스케일)공간으로 변환해 사용할 수 있음.
스케일 공간의 미분은 정규 라플라시안 사용
피라미드 방법 : 거리가 멀어짐에 따라 물체의 크기가 작아지는 현상을 모방.
대강 구하고 싶을 때 이용
SIFT 특징점을 검출하는 과정
스케일 영상 구축 : 한 옥타브 내에서는 가우시안 스무딩 이용하여 세밀하게 조정, 옥타브를 건너뛸 때는 피라미드 방법 이용하여 영상을 반으로 줄임.
사진 여섯 장 - 0옥타브***~ . 0옥타브를 구축하려면 컨볼루션을 6번 수행해야 함. 옥타브는 표준편차=1.6으로 스무딩한 영상에서 출발하여 주어진 값 k를 곱해 다음 영상을 구한다
다중 스케일 영상에 미분 적용 : SIFT는 정규 라플라시안을 사용하는데, 이는 계산량이 많기에 시간이 오래 소요됨. 이와 유사한 DOG(그림 b)를 이용할 수 있는데, 이는 이웃한 영상을 화소별로 빼면 되는 것으로 속도가 빠르고 한 옥타브에 다섯 장의 DOG영상이 생김. (스케일이 같은 한 옥타브 내에서만 사용 가능.)
극점 검출:i번째DOG영상에서8개 이웃 화소,이웃인i-1,i+1번째 영상의18개 이웃 화소를 조사한 뒤X화소가26개 이웃 화소보다 크면(=더 많은 정보를 가지고 있다는 것)극점으로 인정하여 특징점(=키포인트)으로 취함
특징점 표현법 : (y, x, o, i)
👉🏻 위 방법을 이용하여 SIFT 특징점의 위치와 스케일 정보를 알아내면, 특징점 주위를 살펴 기술자 description(특징 벡터)를 추출함.
물체가 회전해도 같은 기술자를 추출하는 회전 불변성을 달성하기 위해 기준 방향을 정하고, 방향을 중심으로 특징을 추출하면 됨. 기준 방향은 그래디언트를 이용한 특징점을 이용.
이후, 각 블록은 자신이 속한 16개 화소의 그래디언트 방향을 8단계로 양자화하여 히스토그램을 구함. (히스토그램의 x축은 방향, y축은 각 방향의 크기를 의미) 히스토그램의 가장 큰 값은 해당 블록을 대표하는 방향이 됨(=서술자).
그림 b의 경우, 위 과정을 16번 거침. 각 구역별로 8개의 방향정보가 나오고, 16*8의 정보들 중 가장 큰 값이 특징점의 서술자가 됨.
해당 점이 어떤 특성을 가지고 있는지 알 수 있게 됨
한 픽셀(피쳐 포인트)을 기술하기 위해 만들어진 벡터의 사이즈 : 16*8개의 메트릭스
🙂 특징점 검출 방법으로는 SIFT가 가장 성능이 좋지만 계산량이 많기에 이후 다양한 변형된 알고리즘이 발표되었다.
매칭 : 두 영상에서 추출한 기술자 집합A={a1, a2,... a’m}와 같은 물체의 같은 곳에서 추출된 a’j와 b’j쌍을 모두 찾는 것
A와 B를 조합한 nm개의 쌍 각각에 대해 유클리디안을 이용하여 거리 계산하고 거리가 임계값보다 작은 쌍을 모두 취하는 매칭 알고리즘
계산 양이 많아 소요시간이 오래 걸리며 물체의 같은 곳이 아닌데 매칭되는 쌍(거짓 긍정)과 같은 곳인데 매칭에 실패하는 경우(거짓 부정)가 자주 발생
한계 : 방향은 같고 크기는 다를 경우 유클라디안 거리는 실제와 달리 매우 다르다고 여김
<매칭 전략>
고정 임계값 : 두 기술자 a’j, b’j의 거리가 임곗값보다 작으면 매칭되었다고 간주하는 고정 임곗값 방법 - 임곗값 T를 정하는 것이 중요. 너무 작으면 아주 가까운 쌍만 조건을 만족하므로 진짜 매칭 쌍이 조건을 통과하지 못해 거짓 부정이 많이 발생. 너무 크면 거짓 긍정이 너무 발생
최근접 이웃 : a’j는 B에서 거리가 가장 작은 b’j를 찾고 a’j와 b’j가 위의 식을 만족하면 매칭쌍으로 취함.
최근접 이웃 거리 비율 : a’j는 가장 가까운 b’j와 두 번째 가까운 b’k를 찾고, b’j와b’k가 아래 식을 만족하면 a’j와 b’j는 매칭쌍.
성능이 가장 좋다.
매칭 성능 측정 : 최선의 알고리즘을 선택하는 기준
참 긍정 ) 알고리즘이 긍정으로 예측한 결과값이 참인 경우
거짓 부정 ) 알고리즘이 부정으로 예측한 결과값이 거짓인 경우
거짓 긍정
참 긍정
정밀도 : 매칭 알고리즘이 긍정으로 예측한 개수 중에 진짜 쌍인 비율
재현율 : 진짜 쌍 중에 알고리즘이 찾아낸 쌍의 비율
정확률 : 옳게 예측한 비율
특징점 매칭에서는 부정이 긍정보다 월등히 많기에 정확률이 의미가 없는 경우가 많음.
👉🏻 자신의 상황에 맞는 기준을 이용해야 함.
ROC 곡선 (시각적으로 확인하는 방법)
고정 임곗값 방법이나 최근접 이웃 거리 비율 방법에서는 임곗값T를 사용하는데, T를 작게 하면 거짓 긍정률이 작아지고, T를 크게 하면 거짓 긍정/참 긍정이 커지는 경향
가상의 매칭 알고리즘으로 측정한 세 가지의곡선중 왼쪽 위 꼭짓점에 가까운 c2의 성능이 가장 뛰어남.
만약 꼭짓점을 지나면 완벽한 매칭 알고리즘
수치가 아닌 AUC (ROC곡선의 아래쪽 면적)를 측정하여 계산
이진 탐색 트리 :루트에서 시작하여 루트보다 작으면 왼쪽 크면 오른쪽으로 이동하는 일을 재귀적으로 반복.
특징점을 빠르게 구현하는 방법
한계점 : 이진 탐색 트리는 값 하나를 비교 but 특징점 매칭에서는 여러 값으로 구성된 기술자를 비교해야 함.
이진 탐색 트리는 정확히 같은 값을 찾는 반면 특징점 매칭에서는 최근접 이웃을 찾아야 함.
kd트리 : 이진 탐색을 특징점 매칭에 적합하게 개조한 모형
i번째 기술자 x’i의 d개 축중에 분산 값이 가장 큰 축 k를 선택한 다음 k번째 축의 값이 x’k보다 작으면 왼쪽 크면 오른쪽으로 분류한 뒤 왼쪽값 중 중앙값을 트리의 원 안에 위치시키고 원의 색과 같은 특징을 이용하여 몇 번째 축을 사용하였는지 기록
해싱 : 해시 함수 h가 키 값을 키가 저장될 칸의 번호로 매핑
한 번만 계산하면 되기에 속도 매우 빠름
but 서로 다른 키가 같은 주소로 매핑되어 충돌이 일어날 수 있음.
의존 해싱 : 해싱을 특징점 매칭에 활용하기 위해 변형한 기법
호모그래피 : SIFT 검출과 기술자를 추출한 뒤에 아웃라이어를 걸러내어 물체의 위치를 찾아줌.
3차원 공간에 있는 평면 P의 두 점 p1, p2가 카메라의 2차원 영상 평면에 투영변환됨
*투영변환 : 3차원 점이 2차원 평면으로 변환되는 기하 관계
투영변환은 어파인 변환과 달리 먼 곳의 물체를 작게 나타내기 때문에 평행을 유지하지 못함
어파인 변환은 3*3동차행렬의 세 번째 행의 값이 (0,0,1)이지만 투영 변환은 그렇지 않음
3차원 점p를 동차 좌표로 표현하면4차원 벡터가 되고,투영을 위한 변환 행렬이4*4가 됨.이때, p1과p2를 같은 평면 상에 있다고 가정하여z=0으로 여기면 3*3행렬로 표현할 수 있는데,이러한 제한된 상황에서 이루어지는 투영 변환을 평면 호모그래피라 부름
어떤 평면의 점 a를 다른 평면의 점 b로 투영하는 변환 행렬을 H라 하면, 아래의 식으로a, b의 관계를 표현할 수 있음. 이때 세 번째 요소를 1로 만들기 위해 5.19와 같은 식 이용 - 위 식을 보면, H에는 9개의 변수 요소가 있는데 하나의 매칭쌍이 두 방정식을 제공하기에 최소 4개의 매칭쌍으로 방정식 H를 구할 수 있다.- 방정식의 개수가 변수의 개수보다 많으면 독립적인 변수의 값을 구할 수 없음.화이트 가우시안 노이즈(노이즈에 오염된 데이터)라고 가정을 해야 문제를 풀 수 있음 → 최소 자승법 이용 : 데이터의 집합에 가장 근접한 추세선을 찾아줌. but 아웃라이어에 취약. - 현실에서는 거짓 매칭, 위치 오류등이 있기에 많은 매칭쌍을 사용하여 오류가 최소 되는 최적의 H를 구함.
최소평균제곱오차 : 중앙값을 이용한 강인한 호모그래피 추청 방법
* 강인하다 : 모든 매칭 쌍이 같은 자격으로 참여하였기에 일부 매칭 쌍이 전체 최적화 결과에 과도한 영향을 미치지 않도록 설계되어 있다는 것.
H는 a’i를 H*a’i로 투영하는데, H*a’i와 b’i값의 차이를 오차라고 함. 아래 식은 모든 점의 오차를 평균함. 최소평균제곱오차는 E가 최소인 H를 찾아준다. *n은 매칭 쌍의 수를 의미함
위 식을 사용하는 최소평균제곱오차는 모든 매칭쌍이 같은 자격으로 참여했기에 아웃라이어로 인한 호모그래피의 정확도가 떨어질 수 있음.
이때, 아웃라이어를 걸러내기 위한 방법은 모든 쌍의 오차를 계산한 다음 평균 대신 중앙값을 사용하는 것이다. 가운데 위치한 오차를 E로 취했을 경우, 틀린 매칭 쌍(아웃라이어)은 중앙값 계산까지만 영향을 미치고 해를 계산하는 과정에서는 빠지기 때문에 보다 강인한 해를 얻을 수 있음.
중앙값보다 더 강인한 추정 기법으로는 RANSAC이 있는데, 이는 샘플을 랜덤 하게 뽑아서 계산하는 과정을 반복하여 최적해를 구하는 기법이다. -> 노이즈에 강인함. 반복 횟수 많을수록 정확도 up
