이번에는 비디오에서 물체를 찾고 추적하는 알고리즘인 민시프트와 캠시프트 알고리즘을 배워보자
민시프트
- 민시프트의 개념은 간단합니다. 점들의 집합이 존재하는데(히스토그램 역전파 같은 픽셀 분포가 있다고 합시다), 여기다가 작은 원형 윈도우를 주고, 이 윈도우가 픽셀 밀도가 최대인 방향으로 이동시킵니다(점들의 개수가 최대인 지점). 이를 나타내면 아래와 같습니다.
초기 윈도우는 파란색 원으로 여기서 c1이라고 하겠습니다. 이 원의 중심은 파란색 사각형으로 c1_o라 하겠습니다. 이 윈도우 안에서 중심점을 찾는다면 c1_r로 작은 원으로 그리겠고, 실제 윈도우의 중심이라 할수 있습니다.
원의 중심과 점들의 중심이 맞지 않으면 윈도우는 이동하고, 새로운 윈도우의 중심은 이전의 센트로이드와 동일해질겁니다(c1_r이 새로운 중심점이 됨). 다시 새로운 센트로이드를 찾고 이동하는게 반복됩니다.
아마 매치가 되지않는다면 다시 이동하윈도우의 중심이 반복되는 결과 같은 지점으로 수렴하게 됩니다. 결과적으로 픽셀 분포가 최대가 되는 지점에 윈도우는 존재하게 됩니다. 이를 녹색선으로 그리고 c2라 하겠습니다. 위에서 보시다시피 이 곳이 점들이 최대가 되는 지점이라 할수 있습니다. 전체적인 과정은 아래의 이미지에서 볼수 있겠습니다.
히스토그램 역투영 영상과 초기 목표 위치를 통과할거고, 물체가 움직인다면 히스토그램 역투영 영상에서 반영될겁니다. 그 결과 민시프트 알고리즘은 윈도우를 이동시키고 결과적으로 최대 밀도가되는 지점에 도착하게 됩니다.
opencv meanshift
- opencv에서 민시프트를 하려면 우선 타겟을 설정해야합니다. 그리고 그 타겟의 히스토그램을 구해야 타갯의 역투영을 할수 있고 민시프트 계산이 가능해집니다. 그리고 초기 윈도우의 위치가 필요합니다. 히스토그램에서는 hue만 고려할수 있으니 저조도에 의한 거짓 값을 피하기 위해서 cv2.inRange()함수로 저조도 값들을 제거하겠습니다.
캠시프트
조금전 결과를 자세히 보셧나요? 여기선 문제가 있는데 윈도우가 항상 차가 밖에 나갈때까지도 같은 크기로 되어 카메라 가까이 까지 따라옵니다. 이건 좋지 않으니 윈도우 크기를 타겟의 크기와 회전에 따라 조절해주어야 합니다. 그래서 opencv 연구실에서 CAMshift (continuosly adaptive meanshift)라는 방법을 제안하였습니다.
처음에는 민시프트를 적용합니다. 민시프트가 수렴하고나면, 윈도우 크기를 아래와 같이 조절해줍니다. 이것은 최적의 타원 방향을 계산해 줍니다.
다시 새로운 스케일된 탐색 윈도우와 이전 윈도우 위치로 민시프트를 적용하고고 이를 반복하면 아래와 같이 정밀한 결과를 얻을수 있습니다.
이제 민시프트랑 동일하게 캠시프트를 적용해보겠습니다. 하지만 여기서는 회전된 사각형과 박스 파라미터(다음 반복에 사용할)를 반환해 줍니다.
import numpy as np
import cv2
cap = cv2.VideoCapture('./res/slow.mp4')
# take first frame of the video
ret,frame = cap.read()
# setup initial location of window
r,h,c,w = 135,90,270,125# simply hardcoded the values
track_window = (c,r,w,h)
# set up the ROI for tracking
roi = frame[r:r+h, c:c+w]
hsv_roi = cv2.cvtColor(frame, cv2.COLOR_BGR2HSV)
mask = cv2.inRange(hsv_roi, np.array((0., 60.,32.)), np.array((180.,255.,255.)))
roi_hist = cv2.calcHist([hsv_roi],[0],mask,[180],[0,180])
cv2.normalize(roi_hist,roi_hist,0,255,cv2.NORM_MINMAX)
# Setup the termination criteria, either 10 iteration or move by atleast 1 pt
term_crit = ( cv2.TERM_CRITERIA_EPS | cv2.TERM_CRITERIA_COUNT, 10, 1 )
while(1):
ret ,frame = cap.read()
if ret == True:
hsv = cv2.cvtColor(frame, cv2.COLOR_BGR2HSV)
dst = cv2.calcBackProject([hsv],[0],roi_hist,[0,180],1)
# apply meanshift to get the new location
ret, track_window = cv2.CamShift(dst, track_window, term_crit)
# Draw it on image
pts = cv2.boxPoints(ret)
pts = np.int0(pts)
img2 = cv2.polylines(frame,[pts],True, 255,2)
cv2.imshow('img2',img2)
cv2.imshow('dst',dst)
k = cv2.waitKey(60) & 0xffif k == 27:
breakelse:
cv2.imwrite(chr(k)+".jpg",img2)
else:
break
cv2.destroyAllWindows()
cap.release()
다음 이미지는 캠시프트 한 결과를 보여주는데 아래는 히스토그램 역투영 영상 위는 캠시프트 결과를 보여주고 있습니다.
이번에는 피처 매칭과 호모그래피 탐색을 이용하여 복잡한 이미지상에 있는 물체를 찾아보겠습니다.
지난 시간는 쿼리 이미지를 사용해서 다른 훈련 이미지상에 존재하는 특징점들을 찾았습니다. 정리하자면 다른 이미지에 존재하는 물체 일부의 위치를찾은것이라 볼수 있겠습니다. 이 정보가 있으면 훈련 이미지 상에 존재하는 물체를 찾기에 충분합니다.
그러기 위해서 이번에는 calib3d 모듈에서 cv2.findHomography() 함수를 사용해보겠습니다. 두 이미지 상에서 점집합을 찾았다면 이제 그 물체의 원근 변환을 얻을수 있습니다. 그러고나서 cv2.perspectiveTransform()으로 물체를 찾겠습니다. 이 변환을 얻기 위해서는 4개의 올바른 점들이 필요합니다.
매칭하는 중에 결과에 영향을 주는 에러들이 존재할수도 있지만, 이 부분은 RANSAC이나 LEAST_MEDIAN(플래그로 설정가능)을 사용해서 해결하겠습니다. 좋은 매치를 인라이어라 하고, 아닌것을 아웃라이어라 부르겠습니다. cv2.findHomography()는 인라이어와 아웃라이어 포인트들을 정리하는 마스크를 반환해줍니다.
import numpy as np
import cv2
from matplotlib import pyplot as plt
MIN_MATCH_COUNT = 10
img1 = cv2.imread('./res/box.png',0) # queryImage
img2 = cv2.imread('./res/box_in_scene.png',0) # trainImage# Initiate SIFT detector
sift = cv2.SIFT_create()
# find the keypoints and descriptors with SIFT
kp1, des1 = sift.detectAndCompute(img1,None)
kp2, des2 = sift.detectAndCompute(img2,None)
FLANN_INDEX_KDTREE = 0
index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)
search_params = dict(checks = 50)
flann = cv2.FlannBasedMatcher(index_params, search_params)
matches = flann.knnMatch(des1,des2,k=2)
# store all the good matches as per Lowe's ratio test.
good = []
for m,n in matches:
if m.distance < 0.7*n.distance:
good.append(m)
iflen(good)>MIN_MATCH_COUNT:
src_pts = np.float32([ kp1[m.queryIdx].pt for m in good ]).reshape(-1,1,2)
dst_pts = np.float32([ kp2[m.trainIdx].pt for m in good ]).reshape(-1,1,2)
M, mask = cv2.findHomography(src_pts, dst_pts, cv2.RANSAC,5.0)
matchesMask = mask.ravel().tolist()
h,w = img1.shape
pts = np.float32([ [0,0],[0,h-1],[w-1,h-1],[w-1,0] ]).reshape(-1,1,2)
dst = cv2.perspectiveTransform(pts,M)
img2 = cv2.polylines(img2,[np.int32(dst)],True,255,3, cv2.LINE_AA)
else:
print("Not enough matches are found - %d/%d" % (len(good),MIN_MATCH_COUNT))
matchesMask = None
draw_params = dict(matchColor = (0,255,0), # draw matches in green color
singlePointColor = None,
matchesMask = matchesMask, # draw only inliers
flags = 2)
img3 = cv2.drawMatches(img1,kp1,img2,kp2,good,None,**draw_params)
plt.imshow(img3, 'gray'),plt.show()
우선 찾은 물체에 존재하는 10개의 매치들을 구합니다. 충분히 매치들을 찾았다면, 두이미지에 존재하는 매치된 키포인트의 위치들을 추출하겠습니다.
이제 이 매치들을 사용해서 원근 변환을 찾아보겠습니다. 3 x3 크기의 변환 행렬을 얻을건데, 이 행렬을 사용해서 쿼리 이미지의 키포인트(코너)들을 훈련 이미지 상에 대응지점으로 변환시킬수 있습니다.
findHomography로 변환 행렬을 구하고, 쿼리 이미지의 코너들을 원근 변환 행렬로 훈련 이미지 상에 나타내고 이를 직선으로 이어줍시다.
브루트 포스 매처는 단순합니다. 첫 집합에서 하나의 특징 기술자를 주어지면 거리 계산 방법으로 두번째 집합에 존재하는 모든 특징들과 매치시켜봅니다. 그리고 가장 가까운것을 반환해줘요.
BF 매처에서는 처음 BF매처를 생성시키고 (cv2.BFMatcher())) 여기서 2개의 옵션 파라미터를 줄수 있습니다. 첫번째 옵션은 거리 측정 방법을 명시해주는데 넘어가고, 두번쨰 파라미터는 교차 검증을 하는것으로 기본적으로 false로 되어있습니다.
매처에서는 A 집합에서 i번째 기술자와 B 집합에서 j번째 기술자가 서로 잘맞는지 매치 결과를 반환해주는데, 같은 집합에 대해 두 특징을 한다면 서로 잘 될거고 일관된 결과를 보여줄겁니다.
일단 매처가 만들어지고 나면, 두 중요한 방법으로 BFMatcher.match()와 BFMatcher.knnMatch()가 있습니다. 첫번째는 최적의 매치를 반환하고, 두번째는 사용자가 지정한 k개만큼의 최적의 매치를 반환해줍니다. 하고싶은 데로 하시면 되겠습니다.
그 다음 키포인트를 그리기 위해서 cv2.keypoints()를 사용했지만 cv2.drawMatches()를 사용해서 매치를 그릴수가 있겠습니다. 이걸 사용하면 두 이미지가 평행하게 놓여지고, 첫번쨰 이미지에서 두번째 이미지로 최적의 매치를 하는 선을 그려줄겁니다. k개의 최적 매치에 대해서 cv2.drawMatchsKnn도 사용할수 있겠습니다.
이제 SURF와 OR의 예시를 한번 보겠습니다
ORB 기술자를 이용한 브루트포스 매칭
두 이미지 사이 피처를 매칭시키는 간단한 예시를 보겠습니다. 이 경우에서 쿼리 이미지와 훈련 이미지가 있는데요. 피처 매칭을 사용해서 트레이닝 이미지에 쿼리 이미지가 어디있는지 찾겠습니다.
우선 시프트 기술자를 사용해서 피처를 매치시켜보겠씁니다. 여기서 이미지를 읽고 기술자를 찾겠습니다.
다음으로 할일은 BFMatcher 객체를 생성해서 거리는 cv2.NORM_HAMMING그리고, 더나은 결과를 얻도록 crossCheck를 해줍시다.
10개를 찾아 띄워주면 아래의 결과를 얻을수 있겠습니다.
import numpy as np
import cv2
from matplotlib import pyplot as plt
img1 = cv2.imread('./res/box.png',0) # queryImage
img2 = cv2.imread('./res/box_in_scene.png',0) # trainImage
img3 = img1
# Initiate SIFT detector
orb = cv2.ORB_create()
# find the keypoints and descriptors with SIFT
kp1, des1 = orb.detectAndCompute(img1,None)
kp2, des2 = orb.detectAndCompute(img2,None)
# create BFMatcher object
bf = cv2.BFMatcher(cv2.NORM_HAMMING, crossCheck=True)
# Match descriptors.
matches = bf.match(des1,des2)
# Sort them in the order of their distance.
matches = sorted(matches, key = lambda x:x.distance)
# Draw first 10 matches.
img3 = cv2.drawMatches(img1,kp1,img2,kp2,matches[:10], img3,flags=2)
plt.imshow(img3),plt.show()
플란 기반 매처 FLANN based Matcher
FLANN은 Fast Library for Approximate Nearest Neighbors를 말하며, 크고 고차원 데이터에서 고속 최근접 탐색을 위해 최적화된 알고리즘들의 집합을 가지고 있습니다. 많은 데이터셋에서 BFMatcher보다 더 빠르게 동작하므로 이번에는 플란 기반 매처를 사용해보겠습니다.
플란 기반 매처를 사용하려면, 어떤 알고리즘을 사용할지 명시하는 딕셔너리 두개가 필요합니다. 첫번째는 인덱스 파라미터로 FLANN 문서에 자세히 설명되어있습니다.
import numpy as np
import cv2
from matplotlib import pyplot as plt
img1 = cv2.imread('./res/box.png',0) # queryImage
img2 = cv2.imread('./res/box_in_scene.png',0) # trainImage# Initiate SIFT detector
sift = cv2.SIFT_create()
# find the keypoints and descriptors with SIFT
kp1, des1 = sift.detectAndCompute(img1,None)
kp2, des2 = sift.detectAndCompute(img2,None)
# FLANN parameters
FLANN_INDEX_KDTREE = 0
index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)
search_params = dict(checks=50) # or pass empty dictionary
flann = cv2.FlannBasedMatcher(index_params,search_params)
matches = flann.knnMatch(des1,des2,k=2)
# Need to draw only good matches, so create a mask
matchesMask = [[0,0] for i inrange(len(matches))]
# ratio test as per Lowe's paperfor i,(m,n) inenumerate(matches):
if m.distance < 0.7*n.distance:
matchesMask[i]=[1,0]
draw_params = dict(matchColor = (0,255,0),
singlePointColor = (255,0,0),
matchesMask = matchesMask,
flags = 0)
img3 = cv2.drawMatchesKnn(img1,kp1,img2,kp2,matches,None,**draw_params)
plt.imshow(img3,),plt.show()
OpenCV 연구자로서 가장 중요한 것중 하나로 ORB를 꼽을수 있겠습니다. 이 알고리즘은 Ethan Rublee이 ORB: SIFT나 SURF의 효율적 대안(ORB:An efficient alternative to SIFT or SURF) 이라는 논문에서 2011년에 소개되었습니다.
이 논문 내용은 SIFT나 SURF보다 비용 계산과 매칭 성능 측면에서 좋은 대안임을 보여주고 있습니다. 특히 SIFT와 SURF는 특허로 되어있어 비용을 지불해야되지만 ORB는 그런게 없슴다.
ORB는 기본적으로 FAST 키포인트 검출기와 BRIEF 기술자를 조합하여 성능을 개선한 변형물이라 할수 있겠습니다. 먼저 FAST로 키포인트를 찾아내고, 그다음 맨 위에 있는 N개의 점들을 찾기위해 해리스 코너를 사용하겠습니다. 여기서 멀티 스케일 피처를 만들도록 피라미드를 사용할수도 있겠습니다.
여기서 문제는 FAST는 방향을 계산하지 않는것인데 어떻게 회전 불변이 가능할까요? 저자는 여기서 변형을 해주었습니다.
ORB에서는 코너를 가진 패치 중심의 가중화된 강도를 계산하고, 이 코너점에서 중앙으로 향하는 벡터의 방향을 방위로 보고 있습니다. 회전 불변량을 개선하기 위해서, 반지름의 r인 원형 공간에 존재하는 x와 y에 대한 모멘트를 계산하겠습니다.
이제 기술자를 넘어와서보면 ORB는 BRIEF 기술자를 사용하고 있습니다. 하지만 BRIEF는 회전 변화에 좋지 않은 성능을 보이고 있어, 키포인트의 방향에 따라 브리프를 회전시켜줍니다.
위치 (x_i, y_i)에서 n개의 이진 특징 집합에 대해 테스트를 하기 위해 2 x n 형태의 행렬 S(이 픽셀들의 좌표)를 정의하겠습니다.
ORB는 각도를 2pi/30 (12개)로 이산화시키고, 미리 계산한 BIREF 패턴의 룩업 테이블을 만들어 줍니다. 키포인트 방향 theta가 일관될수록 올바른 점들의 집합 S_theta가 이 기술자를 계산하는데 사용되겠습니다.
BRIEF는 각 비트 특징들이 고분산과 평균이 0.5정도 되는 특성을 가지고 있습니다. 하지만 키포인트 방향으로 향하면 기존의 속성을 잃어버리고 더 분산됩니다. 여기서 고 분산인 경우 입력에 대해 다르게 반응하여 특징을 더 차별하게 만들어 버립니다.
다른 바람직한 특성은 각 테스트들은 결과에 영향을 주기 때문에 테스트의 상관관계를 해재하여야 합니다. 이를 위하여 ORB는 탐욕 탐색을 하여 모든 가능한 이진 시험을 수행하여 고분산과 평균이 0.5, 상관관계가 없는 값들을 찾으며 이를 rBRIEF라 합니다.
import numpy as np
import cv2
from matplotlib import pyplot as plt
img = cv2.imread('./res/simple.jpg',0)
img2 = img
# Initiate STAR detector
orb = cv2.ORB_create()
# find the keypoints with ORB
kp = orb.detect(img,None)
# compute the descriptors with ORB
kp, des = orb.compute(img, kp)
img = cv2.drawKeypoints(img,kp,img)
# draw only keypoints location,not size and orientation
img2 = cv2.drawKeypoints(img2,kp,img2, flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)
plt.subplot(121), plt.imshow(img)
plt.subplot(122), plt.imshow(img2)
plt.show()
지난 시간에 SIFT 기술자가 128차원의 벡터로 되어있다고 했습니다. 한 키포인터의 경우 여기서 부동 소수점을 사용하기 떄문에 기본적으로 512바이트를 차지하고 있고, SURF의 경우 (64차원이므로) 256바이트를 차지하게 됩니다.
그렇다보니 수천개의 특징 백터를 생성하는경우 많은 공간을 차지하게되고 제한된 자원을 가진 경우 실행하기 힘든 문제가 있습니다. 그리고 메모리가 더 많이 필요할수록 매칭하는데 더 많은 시간이 걸리게 되기도 하구요.
하지만 이런 모든 차원들이 실제 매칭하는데 필요한건 아닙니다. 주성분 분석 PCA나 선형 판별 분석 LDA같은 방법으로 그걸 압축시킬수도 있고, LSH Locality Sensitive Hashing을 사용하여 SIFT 기술자를 이진 문자열로 만들수도 있겠습니다. 이러한 이진 문자열들은 해밍 거르로 피처 매칭하는데 사용되기도 하는데 이를 통해 고속화가 될수 있기 때문입니다. 하지만 우선 기술자를 찾아야 해싱이 가능하니 메모리 문제를 해결한다고는 하기 어렵습니다.
BRIEF는 이 개념을 사용한건데, 기술자를 찾지 않은 상태에서 바로 이진 문자열을 찾아내는 방법이라 할수 있습니다. 이 방법에서는 스무스해진 이미지 패치를 가지고 위치 쌍 n_d(x, y)집합에서 선택합니다. 그러고 나서 일부 픽셀 강도 비교가 됩니다.
예를 들자면 첫 위치 쌍을 p, q라 하겠습니다. 만약 I(p) < I(q)이면 결과를 1 아니면 0으로 하겠습니다. n_d 위치쌍에 존재하는 모든 픽셀들에다가 사용하면 n_d 차원의 비트문자열을 얻게 됩니다.
n_d는 128, 256, 512바이트(길이로 16, 32, 64)가 될수 있으며 opencv에서는 모두 사용가능합니다. 하지만 기본 값으로는 256으로 설정되어있어요. 이 비트스트링을 얻으면 이 기술자들을 매칭시키는데 해밍 거리를 사용할수 있겠습니다.
중요한 점은 BRIEF는 특징 기술자이지, 특징을 찾는데 어떠한 방법을 제공하고 있지는 않습니다. 그래서 SIFT, SURF 같은 다른 특징 검출기를 사용해야 합니다.
정리하자면 BRIEF는 빠른 특징기술자를 계산하고 매칭하는 방법이라 할수 있겠고, 큰 이미지 회전만 아니라면 좋은 인식성능을 얻을수가 있겠습니다.
정리하면
- 일단 BRIEF는 특징 기술자 종류 중 하나
- SIFT나 SURF 기술자들은 너무 커서 실시간으로 돌리기힘듬
- 알고리즘 이해하기는 어려우나 키포인트에 대한 이진 문자열을 만드는데, 키포인트 주위 쌍으로 이진값을 할당
- 이렇게 만든 비트스트링으로 나중에 매칭시 해밍 거리를 구하는데 사용 가능
import numpy as np
import cv2
from matplotlib import pyplot as plt
img = cv2.imread('./res/home.jpg',0)
img2 = np.copy(img)
img3 = np.copy(img)
# Initiate FAST object with default values
surf = cv2.SIFT_create()
#find keypoints and descriptors directly
surf_kp, surf_desc = surf.detectAndCompute(img, None)
# Initiate BRIEF extractor
brief = cv2.xfeatures2d.BriefDescriptorExtractor_create()
img2= cv2.drawKeypoints(img2, surf_kp, img2,flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)
print("surf_desc.shape : ", surf_desc.shape)
# compute the descriptors with BRIEF
brief_kp, brief_desc = brief.compute(img, surf_kp)
img3= cv2.drawKeypoints(img3, brief_kp, img3,flags=cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)
print("brief_desc.shape : ", brief_desc.shape)
plt.subplot(121), plt.imshow(img2)
plt.subplot(122), plt.imshow(img3)
plt.show()
이전에 본 특징 검출기들은 대부분 좋지만, 실시간 어플에서 사용하기에는 충분히 빠르지는 않습니다. 그래서 SLAM에서 사용하기 좋은 알고리즘으로 FAST가 있습니다.
FAST Feature from Accelerated Segment Test 알고리즘은 에드워드 로스텐과 톰 드루몬드가 2006년에 재안했는데요. 이알고리즘을 간략하게 정리해보겠습니다.
FAST를 이용한 특징검출
1. 관심점 특정 픽셀 p를 선택하고, 이 픽셀의 강도를 I_p라 합시다.
2. 적절한 임계치 t를 설정해 줍시다.
3. 테스트할 p 주위의 16개의 픽셀을 선정합니다.
4. 위 이미지의 원에서 I_p +t보다 더 밝은 n개의 연결된 픽셀들이 존재하거나 I_p - t 보다 어두운 n개의 연결댜ㅚㄴ 픽셀들이 존재한다면 픽셀 p는 코너라고 판단하겠습니다. 위 예시에서 n은 12가 됩니다.
5. 여기다가 코너가 아닌경우를 제거하기 위해서 고속의 테스트가 진행됩니다. 이 테스트에서는 4개의 픽셀만 조사하는데요 1, 9, 5, 13번 픽셀을 보고, 이들이 더 밝은지 어두운지 보겠습니다. p가 코너라면 적어도 3개는 I_p + t보다 밝거나 I_p -t보다 어두울 겁니다. 하지만 아니라면 p는 코너가 아니라고 할수 있겠습니다. 이 점 p주위의 모든 픽셀들에대해서 수행할수도 있겠지만 고성능을 내기에는 부족하지만 이렇게 사용합니다.
import numpy as np
import cv2
from matplotlib import pyplot as plt
img = cv2.imread('./res/home.jpg',0)
img2 = img
# Initiate FAST object with default values
fast = cv2.FastFeatureDetector_create()
# find and draw the keypoints
kp = fast.detect(img,None)
img2 = cv2.drawKeypoints(img, kp,img2, color=(255,0,0))
plt.subplot(121), plt.imshow(img, cmap="gray")
plt.subplot(122), plt.imshow(img2)
plt.show()
지난번에는 키포인트를 검출하고, 기술하는 SIFT 알고리즘을 살펴보았습니다. 문제는 이 알고리즘이 매우 느리다는 점인데 2006년에 이를 개선한 SURF: Speed Up Robust Feature라는 논문이 나왔는데, 이름 그대로 SIFT의 가속화된 버전이라 할수 있겠습니다.
SIFT에서는 다양한 스케일 공간에대해서 LoG를 근사한 가우시안 차 영상을 사용합니다. SUFT는 여기서 더 나아가 LOG를 박스 필터로 근사해서 사용합니다. 아래의 그림이 근사한 예시를 보여주고 있는데요. 이 근사의 가장 큰 이점은 박스 필터를 컨볼루션하면 적분 영상 계산이 매우 쉬워집니다. 그리고 다른 스케일에서 적용할수 있겠습니다.
방향을 배정하기 위해서 SURF는 수평과 수직 방향에 대해 크기가 6s인 웨이블릿 응답을 사용하는데요.
* 웨이블릿이란?
- 0을 중심으로 증가 감소를 반복하는 진동. 아래의 그림과 같이 짧은 형태로 기존의 신호에 컨볼루션하여 모르는 정보를 추출하는데 사용할 수 있음.
이들을 아래의 이미지에 플로팅시키면 주 방향 dorminant orientation은 60도의 방향의 윈도우를 슬라이딩하여 모든 응답의 합으로 구할수 있는데요, 여기서 주의깊게 볼점은 적분 영상으로 웨이블릿 응답을 얻을수 있다는 점입니다.
많은 어플리케이션에서 회전 불변이 요구되지는 않고 있으니 SURF에서는 방향을 계산하지 않고 속도를 더 높일수 있도록 하는 기능도 제공하고 있습니다.
특징 기술에 있어서 SURF는 수직, 수평 방향에 대해 웨이블릿 응답을 사용하고 있습니다. 키포인트 주위로 20 x 20형태의 이웃을 가지며, 이들을 4 x 4 형태의 하부 영역으로 나눕니다. 각 하부영역에 대해서 수평, 수직 방향 웨이블릿 응답을 얻고, 그 결과를 아래의 형태를 가진 백터로 만들어 줍시다.
이 벡터는 SURF 특징 기술자로 총 64개으 ㅣ차원이 되겠습니다. 차원도 작고, 고속 계산과 매칭이 가능하나 구분 하기 좋은 특징들을 만들어 줍니다.
이전까지는 해리스 같은 코너 검출기들을 살펴보았습니다. 이들은 회전 불변으로, 이미지가 회전이 된다해도 같은 코너점을 찾을수가 있겠습니다. 하지만 크기변화에선 어떨까요?
이미지가 크기가 조정되면 코너가 더이상 코너가 안될수도 있습니다. 예를들자면 아래의 그림을 한번 살펴보세요. 왼쪽 그림에서 코너는 작은 윈도우에 들어갔지만, 줌해서 커진경우에는 여러 부분들을 찾을수가 있겠습니다.
그래서 해리스 코너는 크기 변화에 불변하지 않다고 얘기 합니다.
2004년 D.Lowe는 새로운 알고리즘으로 크기에 불변한 특징 변환 이라고 하는 SIFT 알고리즘을 제안하였습니다. 여기서 크기 불변 키포인트로 이미지 특징이라는 논문에서 키포인트를 추출하고, 기술자를 계산하는 방법에 대해서 소개하고 있습니다.
SIFT 알고리즘에대해서 4단계로 나누어 설명해보겠습니다.
1. 크기 공간 극점 검출 Scale-space Etrema Detection
위 그림을 보시면 다른 스케일의 키포인트를 검출할때 같은 크기의 윈도우를 사용할수가 없는걸 봤었습니다. 작은 코너라면 괜찬겠죠. 하지만ㄴ 큰 코너를 구한다면 큰 윈도우가 필요할겁니다.
이것떄문에 크기 공간 필터가 사용됩니다. 이를 위해서 다양한 분산 값 omega을 가진 이미지의 LoG Laplacian of Gaussian을 구해보겠습니다. LoG는 방울 검출기 처럼 동작을할건데 omega의 값 변화에 따라 다양한 크기의 blob을 검출하게 될겁니다.
여기서 omega는 스케일 파라미터로 사용되어, 위 영상에서 omega가 작은 가우시안 커널을 사용한다면 작은 코너들을 찾아낼것이고, 큰 omega값을 가진 가우시안 커널을 사용시 큰 코너들을 찾아낼 겁니다.
이렇게 해서 다양한 스케일에 대해 지역 극대점을 찾아내고, 이들을 (x, y, omega)값의 목록으로 정리하겠습니다. 이 값의 의미는 omega 스케일의 공간에서 (x, y)에서 키포인트를 의미합니다.
하지만 LoG는 계산하기에는 비용이커 SIFT 알고리즘은 DoG Differeence of Gaussian을 사용하게되는데 이는 LoG를 근사시킨거라고 할수 있겠습니다. DoG 필터는 두개의 다른 omega로 블러링한 가우시안 영상의 차이로 얻을수가 있겠습니다. 이 방법은 가우시안 피라미드에서 다른 옥타브를 가진것끼리 차 연산을해서 얻을수가 있겠습니다.
그래서 DoG를 구하면, 크기와 공간에 대해서 지역 특징들을 찾을겁니다. 어느 이미지에서 한 픽셀들은 주위의 8개 이웃과 비교할거고, 또 이전 스캐일의 9픽셀과 비교하겠습니다. 이 픽셀이 지역적으로 극점이라면, (잠재적인 키포인트라 판단하고) 해당 스케일에서 최적인 키포인트가 되겠습니다. 이에 대한 그림은 아래와 같습니다.
이 논문에서는 4개의 옥타브와 5개의 스케일 레벨이 주어지고, 초기값으로 omega = 1.6, k = root(2)를 줄때 최적의 결과를 얻을수 있다고 합니다.
2. 키포인트 위치 추정 keypoint localization
잠재적 키포인트의 위치를 찾아내었다면, 실제 결과를 얻기 위해 재정의 하겠습니다. 극점의 정확한 위치를 얻기 위해 스케일 공간에 대해 테일러 전개를 사용할건데, 이 극점에서의 강도가 임계값 0.03(논문에서)보다 작다면 극점이 아닌것으로 판단합니다. 여기서 사용하는 임계치를 contrastTrheshold라 부릅니다.
DoG는 에지에서 강한 응답을 보이는데, 그래서 에지를 제거하여야 합니다. 해리스 코너에서 본것과 비슷한 컨샙을 사용할건데, 2 x 2 해시안 행렬을 사용해서 곡률을 계산하겠습니다
. 해리스 코너 검출기에서 에지의 경우 고유값은 다른것보다 크다는 사실을 알고 있으므로, 이를 간단한 함수로 사용할수 있는데, 이 비율이 임계치보다 크면 그 잠재적 키포인트는 제거하겠습니다. 이렇게 하여 차이가 적은 키포인트와 에지들을 제거하여 강인한 점들만 남게 됩니다.
3. 방향 할당 orientation assingment
각각의 키포인트에는 이미지 회전에 강인할수 있도록 방향이 배정됩니다. 키포인트 주위에 있는 이웃점들은 스케일에 의존하고, 그라디언트 크기와 방향은 이 공간에서 계산할수 있겠습니다. 360도 방향을 다루기위해 36개의 이진 값을 가진 방향 히스토그램을 만들겠습니다.
이 히스토그램은 가우시안 크기와 가우시안 가중치 원형 윈도우(oemga는 1.5인)으로 가중화 될건데, 히스토그램의 가장 높은 지점이나 80%이상인 지점을 방향으로 계산하겠습니다. 이를 통해 같은 크기위 위치를 가졌으나 다른 방향인 키포인트가 만들어지겠습니다. 이 개념이 추후 매치하는데 사용되겠습니다.
4. 키포인트 기술자 keypoint descriptor
이제 키포인트 기술자를 만들어보겠습니다. 키포인트 주위에 16 x 16크기의 이웃점들을 사용할건데 이들을 4 x4 크기의 16개 작은 블록으로 나누겠습니다. 각각의 작은 블록들을 8 이진 방향 히스토그램으로 만들겠습니다. 총 128개의 이진 값들을 얻겠습니다. 이렇게 얻은 벡터를 기포인트 기술자라고 부르겠습니다. 키포인트 기술자를 사용해서 조명 변화나 회전에 강인해질수 있겠습니다.
5. 키포인트 매칭
두 영상 사이의 키포인트를 주위의 최근접 이웃들을 확인해서 매치시킬수가 있겠습니다. 하지만 어떤 경우에는 가장 가까운것보다 두번째것들이 가장 가까울수가 있는데요. 이 경우에는 노이즈나 다른 이유로 발생할수도 있겠습니다. 이 경우에는 두번째 최근접 거리에 대한 최근접 거리의 비율이 필요하겠습니다. 0.8보다 크면 이들은 제거되어 90% 오탐을 제거하는 반면에 5%의 정탐만을 제거한다고 합니다.
이번 장의 목표는 피처에 대해서 이해하고 이게 왜 중요한지, 코너가 왜 중요한지 배워나가겠습니다.
많은 분들이 퍼즐을 해보신적이 있을겁니다. 이미지의 여러 조각들이 주어지고 이것들을 모아 큰 임지ㅣ를 만들어야 합니다. 어떻게 이런것들을 할수 있을까요? 이와 같은 논리를 컴퓨터 프로그램으로 할수 있지 않을까요?
이걸 해내기 위해서 고유하고, 쉽게 추적할수 있고, 비교하기 좋은 특정한 패턴/특징들을 찾고자 합니다. 특징은 이미지의 모든 방향으로 변화가 큰 부분을 말하며, 이런 특징들을 찾는것을 특징 검출이라 합니다. 특징들을 찾았다면 다른 영상에서 같은 부분을 찾고싶을 겁니다. 이건 어떻게 할까요?
이 그림에서 한번봅시다. 윗 부분은 파란 하늘이고 아래는 건물들로 되어있는데 여기서, 특징들이 이 이미지의 어디에 있는지 찾아봅시다. 여러분들은 특징에 대해 조사해보고 컴퓨터도 특징에 대해서 살펴볼겁니다. 이에 대한 설명(기술)을 특징 기술자라고 부릅니다.
특징과 기술자를 찾는다면 모든 이미지에서 찾을수 있고, 나열하며 이을수도 있겠습니다. 앞으로 살펴볼 것들은 어떻게 opencv에서 특징들을 찾고, 기술하고, 매치시키는지 배워보겠습니다.
