[영상신호처리] Template matching

2021 - 1 영상신호처리
1. Template matching 알고리즘에 대한 고찰
2. Template Matching 구현을 위해 작성한 subroutine

• Template Matching 코드 구상 과정 및 완성
• Template Matching 결과 출력화면

3. LPR1 구현을 위해 작성한 subroutine 구상 과정 및 완성

• LPR1 코드 구상 과정 및 완성
• LPR1 결과 출력화면

4. LPR2 구현을 위해 작성한 subroutine 구상 과정 및 완성

• LPR2 코드 구상 과정 및 완성
• LPR2 결과 출력화면

5. Disscussion

• 코드를 작성하며 발견했던 문제점 및 해결 과정
• 느낀 점

1. Template matching 알고리즘에 대한 고찰

Template Matching 알고리즘은 제공된 템플릿을 기반으로 분석하려고 하는 이미지가 얼마나 템플릿과 유사한지 알아내는 알고리즘을 의미한다. 본 과제에서는 차량 번호판 숫자 템플릿을 이용해 차량 번호판 이미지로부터 번호판의 숫자를 구별해 내는 것이 목표였다.

본 과제를 진행하며 새롭게 배우게 된 개념이 몇 가지 있었다. 첫 번째는 바로 ‘템플릿’ 이었다. 템플릿이란 분리해내고 싶은 이미지 (나는 이를 target image 라고 명명하겠다.) 의 기준이 되는 이미지 데이터를 의미한다. 예를 들어 차량 번호판에서 숫자만 인식하고 싶다면, 0~9까지의 숫자 이미지를 분리해낸 기준 데이터가 필요할 것이다. 그리고 이 기준 데이터가 바로 템플릿이다.

템플릿을 만들기 위해서는 몇 가지 기준이 필요하다. 먼저 템플릿 내에 속한 데이터들은 모두 같은 크기를 가져야 하며, 구별해내고 싶은 이미지의 대표적인 이미지를 가지고 있어야 한다. 이렇게 템플릿의 개념에 대해 알게 되며, 더 효과 좋은 이미지의 구별을 위해서는 템플릿이 여러 종류가 있으면 좋겠다는 생각이 들었다.

다음으로 새롭게 알게 된 개념은 템플릿 매칭 알고리즘의 원리였다. 원리를 간단하게 소개짚고 넘어가보자. 먼저 타겟 이미지로부터 이미지 레이블링을 통해 임계 픽셀 수 이상의 레이블 이미지를 걸러낸 다음, 레이블 이미지를 템플릿 사이즈로 정규화 시키는 과정이 첫번째다. 그 다음 템플릿 이미지를 픽셀 대 픽셀로 비교하여 템플릿 이미지와 레이블 이미지가 얼마나 유사한지를 탐색해내고, 일정한 유사도 이상의 값을 가졌다면 레이블 이미지가 특정 템플릿에 속하는 이미지라고 판별하는 알고리즘이다.

처음 이 알고리즘을 공부하게 되었을 때, stereo camera에서 이미지를 분석하는 알고리즘과 비슷하다는 생각이 들었었다 픽셀 대 픽셀로 이미지를 대응 시켜보는 방식이기 때문이다. 하지만 위의 템플릿 매칭 알고리즘은 정확도가 매우 높은데 반해, stereo matching은 정확도가 비교적 낮았다. 왜 일까? 바로 템플릿 매칭에서는 이진화 이미지 값(0 또는 255)을 사용하기 때문이다. 그래서 한 픽셀 대 픽셀만 비교해도 같은 값인지 다른 값인지를 명확히 구별해 낼 수 있는데 반해, strereo matching은 0~255의 모든 픽셀 값을 가지기 때문에 한 픽셀 대 픽셀만 비교하는 것으로는 그 값이 동일한지 같은지를 명확히 구별할 수 없다. 유사한 값이 다른 픽셀에서도 연달아 나타날 수 있기 때문이다. 이러한 비교를 통해, template matching 알고리즘의 유용함과 이미지 thresholding의 중요성을 다시 한 번 실감했다.

나아가 Templeate Matching 과정에서 moment invariant function을 엮어서 사용하면 더 성능이 좋아지겠다는 생각이 들었다. 번호판이 회전되든, 축소되든 확대되든 번호판을 인식할 수 있게 되는 것이 그 이유였다. 본 과제에서는 픽셀 대 픽셀 매칭으로만 알고리즘을 구현했으나, 좀 더 코드를 발전시켜 moment invariant function을 이용한 매칭 알고리즘도 구현해보고 싶다.

2. Template Matching 구현을 위해 작성한 subroutine

• Template Matching 코드 구상 과정 및 완성

내가 가장 처음 작성한 코드는 ‘이미지 전처리’ 부분에 해당한다. 구성요소로는 1) 템플릿 확인을 위한 템플릿 출력 함수, 2) 타겟 이미지를 특정 임계치를 기준으로 thresholding 해주는 함수, 3) 타겟 이미지를 템플릿 사이즈로 Normalize 해주는 함수가 있다. 1) 번 코드는 제공된 Template 데이터를 읽고, 읽은 데이터를 기반으로 이진화 이미지(0 또는 255의 픽셀 밝기 값만 가진 이미지)를 구성하는 기능인데, 이 부분은 교수님이 주신 코드를 사용하였다. 이를 제외한 나머지 두 가지 기능을 구현하기 위해 간단하게 생각해본 함수들의 프로토타입은 다음과 같다.

void sizeNormalize(BYTE **img, BYTE **tmp, int w, int h, int tmpW, int tmpH)

sizeNormalize 함수의 parameter를 잠깐 설명하자면, img 는 원본 이미지를 뜻하고, tmp는 원본이미지를 템플릿 사이즈에 맞게 normalize 할 이미지가 담기는 이미지이다. img를 tmp로 변환하기 위해서는 영상 신호처리 이미지 과제 때 연습했었던 영상의 확대 및 축소에서 알고리즘을 적용하면 되겠다는 생각이 들었다. 원본이미지와 템플릿 이미지 간의 비율을 비교한 scale 변수를 만들고, 그에 맞게 원본 이미지를 확대 및 축소 시켜주면 이미지 normalizing이 성공적으로 이루어질 것이다.

void thresholdingImg(BYTE **orimg1, BYTE **orimg2, int w, int h, int thresValue)

• thresHoldingImg 함수의 parameter도 잠깐 설명하자면, orimg1은 원본 이미지이고, thresValue는 기준 임계치 값, orimg2는 thresValue에 따라 orimg1을 이진화 시킨 이미지에 해당한다. thresHolding 되지 않은 이미지로부터 이진화 이미지를 구현해내기 위해 반드시 필요한 알고리즘이다.

위와 같은 구상을 바탕으로 실제 작성한 함수들은 아래와 같다.

void sizeNormalize(BYTE **img, BYTE **tmp, int w, int h, int tmpW, int tmpH) {
int x, y, xp, yp;
double scalex, scaley;

scalex = (double)tmpW / w;
scaley = (double)tmpH / h; 

for(y=0; y<tmpH; y++) {
for(x=0; x<tmpW; x++) {

  xp = (int)(x / scalex);
  yp = (int)(y / scaley);

  if(xp >=0 && xp<w && yp>=0 && yp<h) tmp[y][x] = img[yp][xp];
  else tmp[y][x] = 0;

}
}

}

void thresholdingImg(BYTE **orimg1, BYTE **orimg2, int w, int h, int thresValue) {
//Thresholding
int x, y;

for(y=0; y<h; y++) {
  for (x=0; x<w; x++) {
  if(orimg1[y][x] > thresValue) orimg2[y][x] = 255;
  else orimg2[y][x] = 0;
    }
  }
}

그 다음, 실제 template Matching을 하기 위한 알고리즘에 대해서도 생각을 해보았다. 그 프로토타입은 아래와 같다.

void matchImage(BYTE **img1, int x0, int y0)

• matchImage 함수는 위의 sizeNormalize 함수를 거치고 얻어낸 tmp 이미지를 기반으로, 템플릿과 픽셀 대 픽셀 매칭을 해보는 함수이다. 그래서 함수 내에서 동적으로 템플릿 기준 이미지를 할당한 후 이와 tmp 이미지 간 비교할 수 있도록 코드를 작성하면 될 것이다.
  또한 나아가, tmp와 템플릿 이미지간의 매칭 스코어 값을 계산하는 코드까지 담아봐야겠다는 생각이 들었다. 또한 tmp와 템플릿 이미지의 픽셀 대 픽셀끼리 잘 비교가 되었는지 확인하기 위해, 같은 픽셀 밝기 값을 가졌다면 템플릿 이미지의 밝기를 0으로 바꾸어 출력하는 코드 또한 담아봐야 겠다는 생각을 했다. 그래서 만약 tmp와 템플릿 이미지가 완전히 같은 값을 가진다면 해당 픽셀 좌표에 해당하는 템플릿 이미지의 픽셀 밝기 값을 0 으로 하여, 다시 출력해보기로 결정했다. 만약 템플릿과 tmp 이미지의 픽셀 밝기가 완전히 일치한다면 까만색 템플릿 이미지가 출력될 것이다.

위와 같은 구상을 바탕으로 실제로 작성한 함수는 다음과 같다.

void matchImage(BYTE **tmp, int x0, int y0)
{
CMainFrame *pMainFrame=(CMainFrame *)AfxGetMainWnd();
CChildFrame *pChildFrame= 
(CChildFrame *)pMainFrame->MDIGetActive(NULL);
CImageProcessingView *pView = 
(CImageProcessingView *)pChildFrame->GetActiveView();
CDC *dc = pView->GetDC();

BYTE **img; // img 변수는 템플릿 이미지가 담기는 동적 배열이다.
int i, x, y, w=TmpW, h=TmpH;
int count; // count 변수는 tmp와 img간 비교를 하다가, 동일 픽셀 좌표가 동일 픽셀밝기 값을 가진다면 그 픽셀을 세는 변수이다. 템플릿 이미지의 사이즈가 20*40 이므로, count는 0에서 800까지의 값을 가질 수 있다.
double Rate; // Rate 변수는 matching rate로, 위에서 선언한 count 변수에 집계된 값을 800으로 나눈 값을 의미한다.

// 아래는 template data를 읽어, BYTE 이미지 img에 할당하는 부분이다.
Read_Template();
img = cmatrix(h, w);

for (i=0; i<10; i++) {
for (y=0; y<h; y++) {
for (x=0; x<w; x++) {
if (CharTemplate[i][y][x] == 0) img[y][x] = 0;
else img[y][x] = 255;
}
}
DisplayCimage2D(img, w, h, x0, y0, FALSE);


count = 0;
Rate = 0;

for (y=0; y<h; y++) {
for(x=0; x<w; x++) {
if(img[y][x] == tmp[y][x]) {
img[y][x] = 0; // 아까 언급했듯이, img와 tmp의 픽셀 밝기가 동일하다면 img의 해당 픽셀 좌표 밝기를 0으로 바꿔준다.
count++; // 또한, 같은 픽셀이므로 count 해준다.
}
else
{
img[y][x] = 255; // 픽셀 밝기가 동일하지 않다면 255로 밝기를 바꾼다.
}
}

}
DisplayCimage2D(img, w, h, x0 + w+ 10, y0, FALSE);

Rate = (double) count / 800 ; // 이는 매칭스코어을 계산하기 위한 부분이다.  

char msg[128];
sprintf(msg, "%6.2f", Rate);
dc->TextOut(x0 + 2*w+ 20, y0, msg, strlen(msg));
y0 += h + 10;

}
pView->ReleaseDC(dc);
free_cmatrix(img, h, w);
}

• Template Matching 결과 출력화면
  위의 함수를 실행해 얻은 결과는 다음과 같다.

왼쪽부터 확대된 5 이미지, 축소된 5 이미지, 숫자가 아닌 물체에 template Matching을 적용한 결과

위와 같이 matchImage 함수, sizeNormalize 함수가 잘 동작하는 것을 확인할 수 있었다. 또한 함수가 잘 작동이 되는지 궁금하여, 숫자가 아닌 물체의 경우에도 template Matching을 시켜보았는데 모두 잘 동작되는 것을 확인할 수 있었다. 또한 숫자가 아닌 물체의 경우에는 매칭스코어 최댓값이 0.75 이하 정도로 매우 낮게 나오는 현상 또한 확인할 수 있었는데, 이를 이용해 번호판 인식에 사용해보면 좋겠다는 생각이 들었다.

3. LPR1 구현을 위해 작성한 subroutine 구상 과정 및 완성

LPR1을 구현하기 위해서는 다음과 같은 과정을 생각해보았다.

• 타겟 이미지를 thresholding 해야 한다. 이를 위해 위에서 작성한 thresholdingImg 알고리즘을 사용해 볼 것이다.

• 타겟 이미지로부터, 특정 픽셀 수 이상의 이미지 레이블만 추출해야한다. 이는 지난 시간에 작성한 Image_Labeling 함수를 이용할 것이다.

• 특정 픽셀 수 이상을 갖는다는 조건을 만족하는 레이블 중, 이미지의 가로 길이가 세로길이보다 길고 세로픽셀이 50 이상인 것들만 추려낸다. 이를 구현하기 위해, 지난 과제에서 작성한 display_labeled_images의 함수를 참고해서 새로운 함수, Display_Labeled_LPR를 작성해보고자 한다.

• 추려낸 이미지들에 대해, 템플릿 사이즈(20*40)로 이미지 크기를 Normalize 시켜준다. 이는 위에서 정의한 sizeNormalize 함수를 사용할 것이다.

• 0~9 까지의 숫자 템플릿들과 추려낸 레이블 이미지들을 템플릿 매칭 시키고, matching score를 구한다. 그 후 임의의 1*10 사이즈 배열에 0~9까지의 템플릿과 매칭 시킨 matching score를 담는다. 이를 구현하기 위해, 위에서 작성한 matchImg 함수에 코드를 추가할 것이다. 기존의 matchImg 함수는 각 템플릿과 타겟 이미지와의 matching score를 출력하고 끝나는 함수였으나, 이 부분을 수정하여 배열에 matching score를 넣고 끝내는 함수로 수정할 것이다.

// 변경 이전

void matchImage(BYTE **tmp, int x0, int y0)
// tmp라는 이미지를 template matcing하고, 그 때 나오는 matching score를 
// 출력하기만 하는 함수, 출력을 위한 기준 좌표 x0, y0를 parameter로 받는 형태이다.


// 변경 이후

void matchImageLPR1(BYTE **tempNorm, double *RateArr)
// tempNorm 이라는 이미지를 template matching하고, 
// 그 때 나오는 matching  score를 1*10 배열, RateArr에 넣어주는 형태의 함수로 고쳐볼 것이다.

• matching score가 담긴 배열을 조회하면서, matching score의 최댓값이 담긴 배열 위치를 찾아내고 그때의 배열 index 값도 찾아낸다. 그 후 matching score와 레이블 이미지가 어떤 숫자로 예측되었는지를 화면에 출력한다. 이 때 matching score의 최댓값이 0.75 이상이어야 숫자로 간주하고, 그보다 낮을 시에는 물체로 간주할 것이다. 물체로 간주된다면 최대 matching score와 예측 결과를 출력하지 않는다. 이를 구현하여 위에서 언급한 Display_Labeled_LPR 에 넣어보고자 한다.

이와 같이 생각하고, 간단하게 추가해야할 함수들, 수정해야할 함수들이 무엇이 있을지 구상해 보았다. 그 함수들의 프로토 타입은 다음과 같다.

void matchImageLPR1(BYTE **tempNorm, double *RateArr)

void Display_Labeled_LPR(int **Label, BYTE **orimg2, int w, int h, int *Area, int &Num, int m_LPR, double *RateArr, int &x0, int &y0)

matchImageLPR1 함수는 아까도 언급했 듯, tempNorm 이라는 이미지를 template matching하고, 그 때 나오는 matching score를 1*10 배열, RateArr에 넣어주는 형태의 함수로 고쳐볼 것이다. Display_Labeled_LPR 함수는 내부에서 matchImageLPR1 함수를 실행시키고, 주어진 조건에 맞는 레이블 이미지, 레이블 값 예측 결과, matching score를 찾아내어 출력시키는 함수이다.

• LPR1 코드 구상 과정 및 완성
  이를 바탕으로 실제로 수정, 추가한 코드는 다음과 같다.

void matchImageLPR1(BYTE **tempNorm, double *RateArr)
{
// RateArr의 값을 수정해주는 함수이다
BYTE **img;
int i, x, y, w=TmpW, h=TmpH;
double count;
double Rate;

Read_Template();
img = cmatrix(h, w);

for (i=0; i<10; i++) {
for (y=0; y<h; y++) {
for (x=0; x<w; x++) {
if (CharTemplate[i][y][x] == 0) img[y][x] = 0;
else img[y][x] = 255; // 여기서 img은 template의 기준 이미지
}
}

count = 0;
Rate = 0;
for (y=0; y<h; y++) {
for(x=0; x<w; x++) {
if(img[y][x] == tempNorm[y][x]) {
count = count + 1;
}
}

}
Rate = count / 800;
RateArr[i] = Rate; // 임의의 배열에 matching score를 넣어주는 모습

}

}

• LPR1 결과 출력화면

위와 같이 구상한 함수를 실제로 적용시켜본 결과는 다음과 같다.

다음과 같이 결과 값이 올바르게 출력되었으며 (숫자와 물체가 완벽하게 구별되었고, 가로길이보다 세로길이가 더 긴 이미지들에 대해서 분류가 잘 되었기 때문이다, template matching을 한 결과도 좋게 나온다는 사실을 확인할 수 있었다. 실제로 100개의 픽셀보다 많은 픽셀 수를 가진 레이블 들은 훨씬 많이 존재하는데, 숫자만 걸러진 것으로 보아 내가 작성한 template matching 알고리즘이 잘 작동된다는 것을 확인할 수 있었다.

왼쪽 이미지와 같이, 픽셀수가 100을 넘는 레이블들은 훨씬 더 많지만 LPR1 시행결과에는 조건을 만족하는 숫자 이미지 레이블들만 출력된 것을 확인할 수 있다.

4. LPR2 구현을 위해 작성한 subroutine 구상 과정 및 완성

• LPR2 코드 구상 과정 및 완성

LPR2 과제에서는 DC Notch filter가 적용된 이미지에 대한 template matching을 해야 했으므로, Notch 필터 이미지를 이진화 한 이미지와, 그 이미지를 반전시킨 이미지를 만들어주는 함수가 추가적으로 필요하겠다는 생각이 들었다. 이를 위해 구상하고, 제작한 추가적인 함수는 다음과 같다.

void reverseImg(BYTE **orimg2, int w, int h)
{
int x, y;
for(y=0; y<h; y++) {
for (x=0; x<w; x++) {
orimg2[y][x] = 255 - orimg2[y][x];
}
}
}

• LPR2 결과 출력화면

LPR2의 threshold 임계 밝기를 130으로 주었을 때의 결과는 다음과 같다.

위에서 보는 것처럼 출력이 매우 잘 나오는 것을 확인할 수 있다. 이를 통해 Notch 필터를 사용하면 고정된 임계밝기를 갖지 않는 이미지를 일괄적으로 비슷한 밝기 값을 갖도록 만들 수 있다는 사실을 알게 되었고, 이를 통해 이미지 matching을 더 용이하게 할 수 있다는 사실을 깨닫게 되었다.

또한, 이정도의 임계 밝기로는 더 많은 숫자들을 걸러내는데 효과적이지 않다는 생각이 들어,
다음과 같이 임계 밝기를 126으로 조정해 다시 한 번 매칭을 시도해보았다. 그랬더니 훨씬 더 좋은 결과가 출력되는 것을 확인 할 수 있었다. 이를 통해, 더 많은 숫자를 걸러내기 위해서는 적당한 임계값을 찾는 과정이 필수적이라는 생각이 들었다.