[2023-04-28] 1. 템플릿 매칭

템플릿 매칭

• 입력 영상에서 (작은 크기의) 부분 영상 위치를 찾는 기법
• 템플릿(template) : 찾을 대상이 되는 작은 영상

템플릿 매칭 함수

void matchTemplate(InputArray image, InputArray templ, OutputArray result, int method, InputArray mask = noArray());

• image : (입력) 입력 영상. 8비트 or 32비트
• templ : (입력) 템플릿 영상. image보다 같거나 작은 크기, 같은 타입
• result : (출력) 비교 결과를 저장할 행렬. 1채널 32비트 실수형
  • image의 크기는 W x H 이고, templ의 크기는 w x h 이면 result 크기는 (W - w + 1) x (H - h + 1)
• mask : 마스크 영상
• method : 비교 방법
  • TM_SQDIFF / TM_SQDIFF_NORMED : Sum of squared difference
  • TM_CCORR / TM_CCORR_NORMED : (Cross) Correlation
  • TM_CCOEFF / TM_CCOEFF_NORMED : Correlation Coefficent

Sum of Squared Difference

• SQDIFF는 두개의 값이 작을수록 서로 비슷한 것이므로 x와 y가 더 비슷하다고 할 수 있음

Correlation

• Correlation은 두개의 값이 비슷할수록 크게 나타나므로 x와 y가 더 비슷하다고 할 수 있음
• 만약 z대신 z’ 의 값을 x와 비교할 경우 튀는 값이 있다는 이유로 x, y와 비교했을 때보다 높은 값이 나옴 (부정확함)
  • 그래서 정규화된 Correlation을 계산

Normalized Correlation

• x와 z’ 값을 비교했을때 z’의 튀는 값의 제곱이 분모형태로 들어가므로, 정규화된 값은 작아짐
• Normalized Correlation은 두개의 값이 비슷할수록 크게 나타나므로 x와 y가 x와 z’ 보다 더 비슷하다고 할 수 있음

Correlation Coefficient

• 평균값을 빼고 Correlation을 계산
  • x 값에서 평균값 3을 빼면 x’ 이 나옴
  • y 값에서 평균값 4를 빼면 y’ 이 나옴
  • z 값에서 평균값 2를 빼면 z’ 이 나옴
• x와 y의 CCOEFF를 구하는 것은 x’와 y’의 CCORR을 구하는 것 과 같음
• CCOEFF는 두개의 값이 비슷할수록 크게 나타나므로 x와 y가 더 비슷하다고 할 수 있음
• CCOEFF(x, y)를 정규화해서 계산하게 되면 1 값이 나오고, CCOEFF(x, z)를 정규화해서 계산하게 되면 -1 값이 됨
  • Normalized CCOEFF의 결과값은 완전히 일치하면 1, 상호 연관성이 없으면 0, 역일치하면 -1이 나옴

유사도 기준에 따른 템플릿 매칭 결과

• TM_CCORR에서는 로고의 하얀색 값이 크기 때문에 값이 튀어서 로고를 검출함

• TM_SQDIFF와 TM_SQDIFF_NORMED 는 값이 작을수록(검정색) 유사도가 높아지고 나머지는 값이 클수록(흰색) 유사도가 높아짐
• 다양한 비교 방법중 가장 정확도가 높은 방법은 TM_CCOEFF_NORMED
  • 복잡한 수식을 사용하는 만큼 연산의 시간이 더 길어짐

템플릿 매칭 예제 코드

#include <iostream>
#include "opencv2/opencv.hpp"

using namespace std;
using namespace cv;

int main()
{
	Mat src = imread("circuit.bmp", IMREAD_GRAYSCALE); // 입력 영상
	Mat tmpl = imread("crystal.bmp", IMREAD_GRAYSCALE); // 템플릿 영상
	// 템플릿 매칭은 반드시 그레이스케일 영상을 사용해야하는 것은 아님
	// 그레이스케일 영상을 사용했을때 디테일이 많고 메모리도 효율적으로 사용하고 연산도 빨리 하는 장점이 있음

#if 0
	src = imread("wheres_wally.jpg", IMREAD_GRAYSCALE); // IMREAD_COLOR
	tmpl = imread("wally.bmp", IMREAD_GRAYSCALE);
#endif

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

#if 1 // 그대로 수행하면 너무 쉽게 찾으므로 영상을 살짝 변형을 함
	src = src + 50; // src의 영상을 바꾸기 위해 밝기를 조절함

	Mat noise(src.size(), CV_32S); // 부호가 있는 정수형 형태로 잡음을 생성
	randn(noise, 0, 10); // 10, 50, 100 // 표준편차가 10인 가우시안 잡음을 발생시킴
	add(src, noise, src, noArray(), CV_8U); // 지저분한 형태의 입력 영상으로 만들고 결과 행렬은 그레이스케일 형식으로 저장하게 함. 
	// 이렇게 설정해야 음수로 설정된 Noise값도 추가가 되므로 조금 더 자연스러운 형태의 잡음이 추가가 됨
#endif

#if 1
	GaussianBlur(src, src, Size(), 1);
	GaussianBlur(tmpl, tmpl, Size(), 1);
#endif

#if 0
	resize(src, src, Size(), 0.9, 0.9); // 0.8, 0.7
#endif

#if 0
	Point2f cp(src.cols / 2.f, src.rows / 2.f);
	Mat rot = getRotationMatrix2D(cp, 10, 1); // 20, 30
	warpAffine(src, src, rot, src.size());
#endif

	Mat res, res_norm;
	matchTemplate(src, tmpl, res, TM_CCOEFF_NORMED);
	// TM_CCOEFF_NORMED로 지정했으므로 res 값은 -1 ~ 1의 값으로 나타는데 1에 가까울수록 좀 더 비슷함
	normalize(res, res_norm, 0, 255, NORM_MINMAX, CV_8U);
	// res의 값이 어떻게 구성되어있는지 그레이스케일로 변환해서 눈으로 확인해보자

	double maxv;
	Point maxloc;
	minMaxLoc(res, 0, &maxv, 0, &maxloc); // 최댓값과 최대위치를 찾기 위해
    // res_norm으로 안하는 이유는 실수형을 정수형으로 바꾸면서 운이 없으면 최댓값 위치가 여러군데서 발생할 수 있음

	cout << "maxv: " << maxv << endl;
	cout << "maxloc: " << maxloc << endl; // 최댓값, 최댓값 위치 출력

	Mat dst;
	cvtColor(src, dst, COLOR_GRAY2BGR); // src 그레이스케일 영상을 dst 컬러영상으로 바꿈

	rectangle(dst, Rect(maxloc.x, maxloc.y, tmpl.cols, tmpl.rows), Scalar(0, 0, 255), 2); 
	// Rect 함수를 이용해서 검출된 위치를 표현
	// 그리는 위치를 사각형의 좌측상단을 지정하고 템플릿 영상의 크기와 동일하게 사각형의 크기를 지정함
	// 빨간색 2pixel의 두께로 사각형을 그림

//	imshow("src", src);
	imshow("tmpl", tmpl);
	imshow("res_norm", res_norm);
	imshow("dst", dst);
	waitKey();
}

• 변형시킨 src의 영상

• matchTemplate()함수를 통해 나온 결과 res의 값이 어떻게 구성되어있는지 그레이스케일로 변환한 res_norm의 영상
  • 눈으로봐도 영상의 우측 중앙 아래에 흰색 부분이 비슷한게 있는 곳이라는 것을 알 수 있음

• 템플릿 매칭을 완료한 dst 결과 영상
  • matchTemplate의 결과의 최대값이 0.976662로 나옴
  • 입력영상을 변형없이 그대로 사용하면 최대값이 1로 나옴

• noise 값을 50으로 올려도 잘 찾는 것을 확인할 수 있음
  • matchTemplate의 결과의 최대값이 0.711416로 나옴

• noise 값을 100으로 올려도 잘 찾는 것을 확인할 수 있음
  • matchTemplate의 결과의 최대값이 0.442244로 나옴

• 사이즈를 조절하면(resize) 0.9, 0.8일때는 찾지만 0.7 일 때는 못 찾고 다른 것을 찾음
  • Correlation Coefficient 값이 상당히 낮아짐

• 입력 영상이 회전해도 찾기는 하지만 Correlation Coefficient 값이 상당히 낮아짐

• 템플릿 매칭시, 입력 영상의 변형이 있을때
  • 잡음은 Gaussian Filter로 해결 가능
  • 밝기/명암비 변화가 있을 경우 Normalization으로 어느정도 괜찮은 결과가 나옴
  • 크기 변환이나 회전 변환은 템플릿 매칭에서는 취약함
    • 크기변환만 있을 경우 미리 여러가지 크기로 만들어 놓거나, 회전 변환만 있을 경우 미리 다양한 각도로 만들어 놓을 수는 있겠지만 다른 방법을 사용하는 것이 더 좋은 대안임

템플릿 매칭 응용

여러 개의 템플릿 매칭

• 입력 영상에 여러개의 템플릿 영상이 존재하는 경우 어떤 방법으로 찾아낼 것 인가?

matchTemplate(src, tmpl, res, TM_CCOEFF_NORMED);
normalize(res, res_norm, 0, 255, NORM_MINMAX, CV_8UC1)	

• 코드

#include <iostream>
#include "opencv2/opencv.hpp"

using namespace std;
using namespace cv;

int main()
{
	Mat src = imread("cookierun.png"); // 입력 영상
	Mat tmpl = imread("item.png"); // 템플릿 영상

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

	Mat res, res_norm;
	matchTemplate(src, tmpl, res, TM_CCOEFF_NORMED);
	normalize(res, res_norm, 0, 255, NORM_MINMAX, CV_8UC1); // 위의 템플릿 매칭의 결과 행렬을 그레이스케일로 보여줌

	Mat local_max = res_norm > 220; // res_norm의 행렬이 220보다 큰 부분을 찾음

	Mat labels;
	int num = connectedComponents(local_max, labels); 
	// connectedComponent 함수를 이용해서 local_max에 6개의 하얀색 객체가 있음을 알기 때문에 num에는 7이라는 값이 전달됨

	Mat dst = src.clone();

	for (int i = 1; i < num; i++) { // for문을 통해 배경인 0번은 건너뛰고 1번 객체부터..
		Point max_loc;
		Mat mask = (labels == i); // labels 에서 i번 객체가 있는 부분만 하얀색으로 되는 마스크 행렬이 생성됨
		minMaxLoc(res, 0, 0, 0, &max_loc, mask); 
		// res에서 min값, max값을 찾는 것이 아닌 mask 부분이 흰색으로 된 부분에서만 최댓값 위치를 찾음
		

		cout << max_loc.x << ", " << max_loc.y << endl;

		Rect b_rect = Rect(max_loc.x, max_loc.y, tmpl.cols, tmpl.rows);
		rectangle(dst, b_rect, Scalar(0, 255, 255), 2);
	}

//	imshow("src", src);
//	imshow("templ", templ);
//	imshow("res_norm", res_norm);
	imshow("local_max", local_max);
	imshow("dst", dst);
	waitKey();
}

• dst 결과 영상

• res_norm의 결과 영상

• local_max = res_norm > 220로 지정하고 local_max 영상
  • 220이라는 임의의 임계값보다 큰 부분만 표현
  • 여기 위치 근방에 아이템이 있음

• 위 local_max 영상의 하얀색 부분을 통해 저기에 대략적으로 아이템의 위치가 있음을 알 수 있음
  • 하지만 수십개의 픽셀이 뭉쳐서 만들어진 6개의 영역이므로, 각각 6개의 영역 안에서 어떤 좌표가 아이템이 있는 좌표인지 판단해야함

템플릿 매칭을 이용한 숫자 인식

인식이란?

• Classifying a detected object into different categories
• 여러 개의 클래스 중에서 가장 유사한 클래스를 선택

숫자 템플릿 영상 생성

• Consolas 폰트(가로의 크기가 동일한 크기가 되도록 글씨가 써지는 폰트)로 쓰여진 숫자 영상을 digit0.bmp ~ digit9.bmp로 저장

• 각 숫자 영상의 크기는 100 x 150 크기로 정규화

digit_consolas 를

#include <iostream>
#include "opencv2/opencv.hpp"

using namespace std;
using namespace cv;

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

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

	Mat src_bin;
	threshold(src, src_bin, 128, 255, THRESH_BINARY_INV); // THRESH_BINARY_INV를 진행

	Mat labels, stats, centroids;
	int label_cnt = connectedComponentsWithStats(src_bin, labels, stats, centroids);
	// 각각의 바운딩 박스를 stats 행렬로 받아옴
	
	for (int i = 1; i < label_cnt; i++) {
		int sx = stats.at<int>(i, 0);
		int sy = stats.at<int>(i, 1);
		int w = stats.at<int>(i, 2);
		int h = stats.at<int>(i, 3);
		// 바운딩 박스의 정보를 받아옴

		Mat digit;
		resize(src(Rect(sx, sy, w, h)), digit, Size(100, 150)); 
		// 부분영상을 추출하고 가로 100, 세로 150으로 resize 한 후 digit에 저장함
		String filename = cv::format("temp%d.bmp", i - 1); // filename을 temp0.bmp부터 temp9.bmp까지로 작성 
		imwrite(filename, digit); // 위에 지정한 filename으로 저장
		cout << filename << " file is generated!" << endl;
		//imshow("digit", );
		//waitKey();
	}
}

• 코드를 실행하면 다음과 같이 0부터 9까지 숫자 bmp 파일이 생성됨

• 5번 사진에 숫자 8이, 6번 사진에 숫자 9가 저장됨
  • 8, 9 숫자가 다른 숫자들보다 픽셀이 한 조금 더 높기 때문에 발생한 현상
  • 몇개 안되니 직접 수정해서 사용

인쇄체 숫자 인식 과정

• 레이블링을 수행하면 각각의 객체에 바운딩 박스를 얻어냄
• 각각의 숫자들을 부분영상으로 추출
• 가로 100 세로 150으로 resize 해서 앞의 템플릿과 크기를 일치하게 함
• matchTemplate()를 시행할 때 입력영상과 template 영상의 사이즈가 같으면, 1 x 1 하나의 element만 있는 결과 행렬이 나타남
  • 값이 가장 큰 레퍼런스 이미지를 찾아내면 그 숫자의 값을 예측할 수 있음

#include "opencv2/opencv.hpp"
#include <iostream>

using namespace cv;
using namespace std;

Mat img_digits[10];

bool load_digits();
int  find_digit(const Mat& img);
void set_label(Mat& img, int idx, vector<Point>& contour);

int main()
{
	Mat src = imread("digits.png");

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

	if (!load_digits()) {
		cerr << "Digit image load failed!" << endl;
		return -1;
	}

	Mat src_gray, src_bin;
	cvtColor(src, src_gray, COLOR_BGR2GRAY);
//	GaussianBlur(src_gray, src_gray, Size(11, 11), 2.);
	threshold(src_gray, src_bin, 0, 255, THRESH_BINARY_INV | THRESH_OTSU);
	// Inverse를 해서 이진화를 진행함

	vector<vector<Point>> contours;
	findContours(src_bin, contours, RETR_EXTERNAL, CHAIN_APPROX_NONE);
	// findContours를 이용해서 각각의 객체에 외곽선 좌표를 얻어낼 수 있음

	Mat dst = src.clone();

	for (unsigned i = 0; i < contours.size(); i++) { // 각각의 외곽선 객체들에 대해서
		if (contourArea(contours[i]) < 1000) // 면적이 1000보다 작으면.. (이미지의 dot를 걸러내기 위해 입력)
			continue;

		Rect rect = boundingRect(contours[i]); // 바운딩 박스 정보를 추출할 수 잇음
		int digit = find_digit(src_gray(rect)); // 부분영상을 추출
		// 추출한 부분영상을 find_digit 함수에 넣어 해당하는 숫자를 찾아 digit에 저장함

		drawContours(dst, contours, i, Scalar(0, 255, 255), 1, LINE_AA);
		set_label(dst, digit, contours[i]);
	}

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

bool load_digits()
{
	for (int i = 0; i < 10; i++) {
		String filename = format("./digits/digit%d.bmp", i); 
		img_digits[i] = imread(filename, IMREAD_GRAYSCALE); // 0~9 bmp 파일을 img_digits 배열에 저장 
		if (img_digits[i].empty())
			return false;
	}

	return true;
}

int find_digit(const Mat& img) // 0 부터 9까지 어느 숫자랑 가장 비슷한지 찾는 함수
{
	int max_idx = -1;
	float max_ccoeff = -9999;

	for (int i = 0; i < 10; i++) {
		Mat src, res;
		resize(img, src, Size(100, 150)); // 부분 영상을 가로 100 세로 150으로 resize 진행
		matchTemplate(src, img_digits[i], res, TM_CCOEFF_NORMED);
		// 부분 영상을 img_digits 배열에 들어있는 10개의 template 영상과 matchTemplate를 10번 진행하고 결과를 res 행렬에 넣음

		float ccoeff = res.at<float>(0, 0); // res 행렬에 들어있는 하나의 element를 불러옴

		if (ccoeff > max_ccoeff) { 
			max_idx = i; // 이 값이 최대인 위치에 대해서 max_idx에 저장함
			max_ccoeff = ccoeff;
		}
	}

	return max_idx; // 최대인 인덱스 값을 반환함
}

void set_label(Mat& img, int digit, vector<Point>& contour)
{
	int fontface = FONT_HERSHEY_SIMPLEX;
	double scale = 0.8;
	int thickness = 1;
	int baseline = 0;

	String label = format("%d", digit);

	Size text = getTextSize(label, fontface, scale, thickness, &baseline);
	Rect r = boundingRect(contour);

	Point pt(r.x + ((r.width - text.width) / 2), r.y + ((r.height + text.height) / 2));
	rectangle(img, pt + Point(0, 2), pt + Point(text.width, -text.height), Scalar(255, 255, 255), -1);
	putText(img, label, pt, fontface, scale, Scalar(0, 0, 0), thickness, LINE_AA);
}

• Consolas 폰트를 쓴 위 숫자는 잘 인식했지만 다른 폰트를 사용한 숫자는 부분적으로 잘못 인식함