[데브코스] 7주차 - OpenCV corner detection and feature point detection

코너 검출

코너의 특징

• 평탄한 영역(flat) & 에지(edge)영역은 고유한 위치를 찾기 어렵다
• 코너(corner)는 변별력이 높은 편이며, 영상의 이동 및 회전 변환에 강인하다.

특징, 즉 feature은 한 이미지를 표현할 수 있는 속성, 다른 영상과 구분할 수 있는 속성을 말한다. 그래서 한 이미지의 feature map은 고유한 속성을 가진 맵이다. 히스토그램 또한 특징이 된다.

openCV에서 제공하는 코너 검출 방법이 있다.

가장 최근 방법이 FAST로 많이 빠르게 동작한다.

harris는 코너 점 좌표를 출력하는 것이 아니라 dst에는 입력 영상과 똑같은 크기의 행렬을 출력한다. 이는 float 타입을 가지고 있는데, 이 값이 충분히 크면 이를 코너라고 간주하는 것이다.

해리스 코너 검출 방법을 기반으로 비최대 억제,NMS를 적용하고, 출력은 vector<Point2f>로 점들의 좌표를 제공해주기 때문에 다소 편하다. 그러나 해리스 방식을 사용하므로 조금 구시대적이다.

주변의 16개 픽셀을 찾아서 그 점보다 9개 정도가 특정 값 이상 이라면 코너라 인식한다.

keypoint클래스라는 것에는 pt.x, pt.y 라는 객체가 포함되어 있다. threshold가 이 특정 값에 해당하고, NMS를 수행할지 결정할 수 있다.

FAST 사이트

• GFTT & FAST 적용 코드

int main()
{
  Mat src = imread("building.jpg", IMREAD_GRAYSCALE);

  vector<Point2f> corners;
  goodFeaturesToTrack(src, corners, 400, 0.01, 10);

  vector<KeyPoint> keypoints;
  FAST(src, keypoints, 60, true);
}

• 결과 비교

FAST 방법은 반복 검출률이 대체로 높다. 즉, 처음에 코너라 인식한 것은 다음에도 검출할 확률이 높다는 것이다. 다만 FAST 방법은 노이즈에 민감하다.

이러한 코너 검출들은 이동, 회전 변환에 강인하지만 크기 변환에는 취약하다. 따라서 크기 변환에도 강인한 다양한 크기 관점에서 특징을 검출할 수 있는 알고리즘을 사용해야 한다.

크기 변환에도 강인한 방법으로는 특징점(feature point) = 키포인트(key point) = 관심점(interest point) 라고 하는 픽셀값으로부터 의미가 있는 정보를 추출하는 방식이 있다. 추출한 후에는 각 픽셀에 대해 정수가 아닌 실수값으로 표현을 하여 더 정밀하게 표현한다. 이 값들을 통해 에지 히스토그램(그래디언트 히스토그램)을 만든다. 이 때, 한 특징점에 대한 값을 특징 벡터(feature vector) = 기술자(desciptor)라 한다.

• 크기 불변 특징점 검출 방법

SIFT, KAZE, AKAZE, ORB 등 다양한 특징점 검출 방법에서 스케일 스페이스, 이미지 피라미드를 구성하여 크기 불변 특징점을 검출한다.

아래 첫번째 이미지는 scalespace에 대한 것이다. 사이즈도 계속 변경하고, 가우시안 블러도 계속 적용해준다. 두번째 이미지는 이미지 피라미드에 대한 이미지이다. 다양한 크기의 이미지들에 대해 처리한다.

이 특징점 검출에 가장 많이 사용하는 알고리즘이 SIFT(Scale Invariant Feature Transform)이다.

SIFT의 계산 단계에는 detector과 descriptor, 2가지가 있다. SIFT에서는 DOG(diffence of gaussian)이라 하여 인접해있는 가우시간 블러를 적용한 2개의 이미지의 차이를 구해준다. 이를 이용하여 가우시안 함수를 만들고, maxima(최댓값)와 minima(최솟값)를 나타낸다. 이 DOG 방식을 사용하기 이전에는 LOG(Laplacian)을 사용했었다. 그러나 이 방식은 연산이 오래 걸려서 그래프가 비슷한 DOG로 근사화시켜 연산을 함으로서 연산 속도를 줄였다.

이 때, low level에서 특징 벡터를 구했는지, high level에서 특징 벡터를 구했는지에 따라 검출의 정확도가 다 달라진다.

한 픽셀의 대표 특징 벡터(키포인트 기술자)는 각 키포인트 위치에서 스케일과 기준 방향을 고려하여 사각형 영역을 선택한다. 이 사각형 영역을 다시 4x4구역으로 만들고, 8개 방향으로 각 방향 성분을 나타내어 히스토그램을 구한다. 그러면 4x4크기의 8방향이므로 4x4x8 = 128바이트 크기에 실수 표현을 하므로 총 4바이트씩 더 곱해져 512바이트의 벡터가 생성된다.

기타 특징점 기법

• BRIEF(Binary Robout Independent Elemetary Features)

이진 기술자를 이용한 빠른 키포인트 기술 방법이다. 이는 detector이 아니다. 부분 영상을 잘라서 그 영상에 대해 키포인트 주변 픽셀 쌍을 미리 정하고, 픽셀 값의 크기를 비교하여 0 또는 1로 특징을 기술한다. 이는 계산이 단순하고, 이진 표현이므로 크기가 다른 것보다 확실히 작아진다.

특정 패치(p)에서 point pair(x,y)의 픽셀 값 크기 비교 표현식:

nd차원 특징 벡터(기술자):

매칭시 Hamming distance를 사용하여 XOR 논리 연산 후 0의 개수를 카운트한다.

• SURF(Speed-Up Robust Features)

SIFT를 기반으로 속도를 향상시킨 크기 불변 특징점 검출 방법이 있다. DOG 함수를 단순한 이진 패턴으로 근사화시켰다. 적분 영상을 이용하여 속도 향상을 하였다.

http://www.vision.ee.ethz.ch/~surf/

그러나 특허가 있어 사용하기 까다롭다.

• KAZE

KAZE : 비선형 scale space에서 공기의 흐름

가우시안 함수 대신 비선형 확산 필터를 이용하여 특징점을 검출한다. SURF보다는 느리지만 SIFT보다는 빠르고 비슷한 성능이라고 한다.

http://www.robesafe.com/persional/pablo.alcantarilla/kaze.html

• ORB(Oriented FAST and Rotated BRIEF)

OpenCV 특징점 클래스

Feature2D 클래스와 파생 클래스들

특징 벡터를 검출하고 두 장의 영상 데이터를 매칭하는 것까지의 흐름이다. 알고리즘이라는 가장 높은 클래스가 있고, 이 클래스를 상속받은 feature2D가 있고, 그것들을 다 상속받는 SIFT, KAZE,AKAZE 등이 있다. SIFT는 무료이나 SURF는 특허가 있어 무료가 아니고, 성능도 다른 것들과 비슷하여 잘 사용하지 않는다. SIFT와 KAZE는 방향 성분에 대한 히스토그램을 사용하고, AKAZE와 ORB는 이진 바이너리를 사용한다. 이렇게 추출된 것들을 keypoint 클래스가 상속받아 사용된다.

검출만 하려면 detect를 사용하고, 계산만 하려면 compute를 하는데, 둘다 진행하려면 detectandcompute를 사용한다.

생성을 할 때는 create라는 함수를 사용하면 된다.

static Ptr<SIFT> cv::SIFT.::create()
static Ptr<KAZE> cv::KAZE::create()
static Ptr<AKAZE> cv::AKAZE::create()
static Ptr<ORB> cv::ORB::create()

이 때, create 함수의 인자가 엄청 많지만, default인자가 다 있어서 이를 사용하면 된다.

Ptr 이라는 것은 opencv에서 사용하는 스마트 포인터다.

• 특징점 추출 코드

#include "opencv2/opencv.hpp"

#include <iostream>

using namespace cv;
using namespace std;

int main()
{
	Mat src = imread("lenna.bmp", IMREAD_GRAYSCALE);

	if (src.empty()) {
		cerr << "Image load failed!" << endl;
		return -1;
	}

	TickMeter tm;
	tm.start();

	Ptr<SIFT> detector = SIFT::create(); // SIFT, KAZE, AKAZE, ORB

	vector<KeyPoint> keypoints;
	detector->detect(src, keypoints); // shift 연산자

	tm.stop();
	cout << "Elapsed time: " << tm.getTimeMilli() << "ms." << endl;
	cout << "keypoints.size(): " << keypoints.size() << endl;

	Mat dst;
	drawKeypoints(src, keypoints, dst, Scalar::all(-1), DrawMatchesFlags::DRAW_RICH_KEYPOINTS);
  
	imshow("dst", dst);
	waitKey();
	return 0;
}

이 때는 검출만 하기 위해 detect를 사용했다.

Ptr<ORB> detector = ORB::create();

ORB는 동심원이 많다. 즉 같은 픽셀을 참조하는 keypoint가 많다.

Ptr<KAZE> detector = KAZE::create();

Ptr<AKAZE> detector = AKAZE::create();

AKAZE는 SIFT보다 약간 빠르다.

대체로 속도가 필요하다면 ORB, 아니면 SIFT를 사용한다.

drawKeypoints(src, keypoints, dst, Scalar::all(-1), DrawMatchesFlags::DRAW_RICH_KEYPOINTS);

이는 각각의 픽셀에 대해 그림을 그려주는 함수로 for문으로 간단히 구현할 수 있지만, 지원하는 함수를 사용했다. 또, 이 때 scalar::all(-1) 은 Scalar(-1,-1,-1,-1)과 같다.

기술자(dscriptor, feature vector)

기술자란 각각의 특징점 근방의 부분 영상을 표현하는 실수 또는 이진 벡터를 말한다. OpenCV에서는 기술자를 Mat객체로 표현한다. 기술자 알고리즘에 의해 추출된 특징 벡터는 이어 붙여져 행렬로 만들어진다. 이를 기술자 행렬이라 한다.

SIFT의 경우 각 128개의 특징 벡터를 이어 붙여서 행렬로 만든다. KAZE의 경우에는 128이 아닌 64개를 사용한다.

이진 기술자

이진 기술자란 이진 테스트를 통해 부분 영상의 특징을 기술하는 방법을 말한다. 보통 uchar자료형을 사용하여 비트 단위로 영상 특징 정보를 저장한다. 이진 기술자를 사용하는 알고리즘에는 AKAZE,ORB,BRIEF가 있다. 이진 기술자는 해밍 거리(hamming distance)를 사용하여 유사도를 판단한다. 해밍 거리란 두 값과의 차를 합한 것을 말한다.

특정 패치(p)에서 point pair(x,y)의 픽셀 값 크기 비교 표현식:

nd차원 특징 벡터(기술자):

실수 기술자

기술자 사용하려면 compute를 사용하면 된다.

• 함수

virtual void Feature2D::compute(InputArrayOfArrays images, std::vector<std::vector<KeyPoint> >& keypoints, OutputArrayOfArrays descriptors)

• image : (입력) 입력 영상
• keypoints : (입력)검출된 특징점 정보, vector<keypoint> 자료형

• descriptors : (출력)특징점 기술자 행렬, Mat 자료형

• 특징점 계산 코드

int main()
{
	Mat src = imread("lenna.bmp", IMREAD_GRAYSCALE);
	Ptr<SIFT> detector = SIFT::create(); // SIFT, KAZE, AKAZE, ORB

	vector<KeyPoint> keypoints;
	Mat descriptor;
	detector->compute(src, keypoints, descriptor); // shift 연산자

	Mat dst;
	drawKeypoints(src, keypoints, dst, Scalar::all(-1), DrawMatchesFlags::DRAW_RICH_KEYPOINTS);

	imshow("dst", dst);
	waitKey();
}

검출과 계산을 함께 하기 위해서는 detectAndCompute

• 특징점 검출과 계산 코드

Mat desc;
detector->detectAndCompute(src, Mat(), keypoints, descriptor);

두번째 인자는 마스크 행렬에 해당한다. 그리고 마지막 인자는 출력 인자이다.

• desc.size : [바이트 크기 x 특징점 개수]

특징점 매칭

두 영상에서 추출한 특징점 기술자를 비교하여 유사한 기술자끼리 선택하는 작업을 한다. 즉 두 영상에서 같은 특징 벡터를 계산해서 비교한다. 두 벡터의 비교는 유클리디안 거리(L2 norm)를 사용한다.

원본에는 있지만, 변환한 영상에서 없는 3번의 경우는 3개 중 가장 비슷한 것으로 매칭을 해버린다.

이렇게 지저분하게 처리되므로 후처리를 해줘야 한다.

매칭을 할 때는 descriptorMatcher를 사용한다. 이는 가상 클래스이고, 이를 상속받아 사용되는 BFMatcher이나 FlannBasedMatcher를 사용하면 되는데, 대체로는 BFMatcher를 사용한다. 이 BF(Brute Force)는 전수 조사라 하여 모든 것들을 비교해보는 것을 말한다. Flann(Fast Library for Approximate Nearnest Neighbor)은 근사화시키는 것으로 속도가 빨라보이나 FHD 정도의 크기가 아닌 이상 두 방법의 속도는 비슷하다.

DscriptorMatcher안에는 Match(), knnMatch(), radiusMatch() 가 있다. 많이 사용되는 것은 Match(), knnMatch()이다. knnmatch는 1개가 아닌 2개의 매칭값을 찾는 함수다.

여기에 연관되어 존재하는 DMatch라는 클래스가 있다.

• DMatch 클래스 정의

class DMatch
{
	public:
		DMatch();
		DMatch(int _queryIdx, int _trainIdx, float _distance);
		DMatch(int _queryIdx, int _trainIdx, int _imgIdx, float _distance);

	int queryIdx, trainIdx, imgIdx; // 1th image(compare image), 2th image(compared image), image index

	float distance; // 두 특징점 사이의 거리 

	bool operator<(const DMatch &m) const; //compare 연산자
}

queryIdx가 1번 이미지, trainIdx가 2번 이미지로 이 두개를 비교한다. imgIdx라는 것도 있는데, 이는 비교되는 이미지가 여러 개일 수 있어서 어떤 것에 대해 매칭을 할 것인지에 대한 번호이다.

• 특징점 매칭 결과 영상 생성 함수

void drawMatches(InputArray img1, const std::vector<KeyPoint>& keypoints1,InputArray img1, const std::vector<KeyPoint>& keypoints1, const std::vector<DMatch>& matches1to2, InputOutputArray outImg, const Scalar& matchColor=Scalar::all(-1), const Scalar& singlePointColor=Scalar::all(-1), const std::vector<char>& matchesMask=std::vector<char>(), int flags=DrawMatchesFlags::DEFAULT);

• img1,img2,keypoint1,keypoint2 : img1 영상에서 추출한 키포인트 keypoint1, img2 영상에서 추출한 키포인트 keypoint2
• matches1to2 : 두 키포인트 사이의 매칭 결과
• outImg : 매칭 결과를 저장
• matchesMask : 매칭 정보를 선택하여 그릴 때 사용할 마스크로 그냥 std::vector<char>()를 지정하면 모든 매칭 결과를 그려준다.
• flags : DrawMatchesFlags::NOT_DRAW_SINGLE_POINTS를 지정하면 매칭되지 않은 특징점을 그리지 않는다.

위에서 했던 지저분한 영상을 후처리할 때 좋은 매칭만 선별하는 방법에는 몇가지 방법이 있다.

1. sort distance matching

• 가장 좋은 매칭 결과에서 DMatch::distance 값을 기준으로 정렬 후 상위 N개 선택
• DMatch 클래스에 크기 비교 연산자(<) 오버로딩이 사용할 수 있도록 미리 정의되어 있다.

Ptr<DescriptorMatcher> matcher = BFMatcher::create(); 
//이진 기술자 사용시 BFMatcher::create(NORM_HAMMING);

vector<DMatch> matches;
matcher->match(desc1, desc2, matches);

std:sort(matches.begin(),matches.end());
vector<DMatch> good_matches(matches.begin(), matches.begin()+80);

오름차순으로 정렬을 한 후 상위 80개만을 선택해서 그림을 그리면 더 깔끔하게 그림이 그려지는 것을 볼 수 있다.

1. using knnMatch()

두 개의 매칭값을 가지고 처리를 하기 위해 knnMatch()를 사용한다. 가장 좋은 매칭 결과의 distance값과 두 번째로 좋은 매칭 결과의 distance 값의 비율을 계산한다. 이 비율이 임계값보다 작으면 선택된다.

Ptr<DescriptorMatcher> matcher = BFMatcher::create(); 

vector<DMatch> matches;
matcher->knnmatch(desc1, desc2, matches,2);

vector<DMatch> good_matches;
for (auto match : matches) {
	if (match[0].distance / match[1].distance < 0.7)
		good_matches.push_back(match[0]);
}

호모그래피(Homography)

원근법이 적용되어 있는 사진을 평평하게 만들고자 한다. 이 과정이 투시 변환과 거의 동일하다. 최소 4개의 대응점(코너 좌표)이 필요하기에 8DOF이다.

투시 변환을 진행한 것처럼 getPerspectiveTransform과 warpPerspective를 통해 변환된 직사각형이 나올텐데, 이 매칭값들 중에서 잘못된 매칭이 조금이라도 존재하게 되면 잘못된 변환이 된다. 그래서 이 때는 RANSAC 알고리즘을 사용하여 잘된 매칭만 골라내어 모델링한다.

• 호모그래피 행렬 구하는 함수

Mat findHomography(InputArray srcPoints, InputArray dstPoints, int method = 0, double ransacRepojThreshold = 3, OutputArray mask = noArray(), const int maxIters = 2000, const double confidence = 0.995);

• srcPoints : src points, CV_32FC2 행렬 또는 vector<Point2f>
• dstPoints : dst points, CV_32FC2 행렬 또는 vector<Point2f>
• method : 호모그래피 행렬 계산 방법
  • 0, LMEDS, RANSAC, RHO
• ransacRepojThreshold : 대응점들을 inlier로 인식하기 위한 최대 허용 에러(픽셀 단위), [RANSAC, RHO]
• mask : 출력 Nx1 마스크 행렬, RANSAC, RHO 방법 사용 시 inlier로 사용된 점들을 1로 표시한 행렬
• maxIters : RANSAC 최대 반복 횟수
• confidence : 신뢰도 레벨, 0~1 사이의 실수로 지정
• 반환값 : 3x3 호모그래피 행렬, CV_64C1, 만약 호모그래피를 계산할 수 없는 상황이면 비어 있는 Mat 객체가 반환된다.

이 함수는 투시 변환과 거의 동일하나 행렬을 계산하는 방법과 출력값이 다르다. method 이후의 값들은 디폴트값을 사용하는 게 좋다.

• find_homography

int main()
{
	Mat src1 = imread(file1, IMREAD_GRAYSCALE);
	Mat src2 = imread(file2, IMREAD_GRAYSCALE);

	if (src1.empty() || src2.empty()) {
		cerr << "Image load failed!" << endl;
		return;
	}

	vector<KeyPoint> keypoints1, keypoints2;
	Mat desc1, desc2;
	feature->detectAndCompute(src1, Mat(), keypoints1, desc1);
	feature->detectAndCompute(src2, Mat(), keypoints2, desc2);

	Ptr<DescriptorMatcher> matcher = BFMatcher::create();

	vector<DMatch> matches;
	matcher->match(desc1, desc2, matches);

	std::sort(matches.begin(), matches.end());
	vector<DMatch> good_matches(matches.begin(), matches.begin() + 80);

	Mat dst;
	drawMatches(src1, keypoints1, src2, keypoints2, good_matches, dst,
		Scalar::all(-1), Scalar::all(-1), vector<char>(),
		DrawMatchesFlags::NOT_DRAW_SINGLE_POINTS);

	vector<Point2f> pts1, pts2;
	for (size_t i = 0; i < good_matches.size(); i++) {
		pts1.push_back(keypoints1[good_matches[i].queryIdx].pt);
		pts2.push_back(keypoints2[good_matches[i].trainIdx].pt);
	}

	Mat H = findHomography(pts1, pts2, RANSAC);

	vector<Point2f> corners1, corners2;
	corners1.push_back(Point2f(0, 0));
	corners1.push_back(Point2f(src1.cols - 1.f, 0));
	corners1.push_back(Point2f(src1.cols - 1.f, src1.rows - 1.f));
	corners1.push_back(Point2f(0, src1.rows - 1.f));
	perspectiveTransform(corners1, corners2, H);

	vector<Point> corners_dst;
	for (Point2f pt : corners2) {
		corners_dst.push_back(Point(cvRound(pt.x + src1.cols), cvRound(pt.y)));
	}

	polylines(dst, corners_dst, true, Scalar(0, 255, 0), 2, LINE_AA);

	imshow("dst", dst);

	waitKey();
	destroyAllWindows();
}

• RANSAC이란?

RANSAC : RANdom SAmple Consensus

이상치(outlier)가 많은 원본 데이터로부터 모델 파라미터를 예측하는 방법으로 다양한 점들에 대해 적절한 직선을 찾고자 할 때, 직선과 점들과의 거리를 오차로 두고, 오차가 가장 작은 직선을 구한다. 그러나 점의 분포가 너무 다양하다면 점들의 분포를 가장 잘 표현할 수 있는 직선을 찾기는 어려울 수 있다.

그래서 RANSAC 알고리즘을 통해 찾는다. 방법은 다음과 같다.

1. 무작위로 2개의 점을 골라 직선을 구한다.
2. 모든 점들과 이 직선의 거리를 다 구해서 거리가 특정값(margin)안에 들어오는 점들의 개수를 구한다. 이 margin안에 들어오는 점을 inlier, 밖에 있는 점을 outlier 라 한다.
3. 또 다른 무자구이의 2개 점을 골라 직선을 골라 1~2번을 반복한다.
4. 그렇게 계속 찾다보면 가장 높은 수를 가진 직선을 찾게 될 것이다.

무작위로 찾기에 미세하게 값이 달라질수는 있다.

이진 기술자를 사용할 경우 create(NORM_HAMMING);으로 작성해야 한다. hamming distance를 사용하라는 인자다. 이 인자를 주지않아도 동작을 하긴 하나 조금 변형된 결과를 얻을 수도 있다.

요약

• OpenCV 주요 특징점 알고리즘과 기술자 특성

특징점 알고리즘	기술자 차원	depth	이진 기술자	Extra Module	비고
SIFT	128	CV_32F	x	x
SURF	64	CV_32F	x	o	알고리즘 특허 -> 사용 시 비용
KAZE	64	CV_32F	x	x
AKAZE	61	CV_8U	o	x	SIFT와 ORB의 중간 정도 성능 및 속도
ORB	32	CV_8U	o	x	가장 빠름

• 연산 시간 비교