템플릿 매칭

템플릿 매칭(template matching)R. Brunelli, Template Matching Techniques in Computer Vision: Theory and Practice, Wiley, , 2009 ( TM book)은 디지털 화상 처리에서 템플릿 이미지와 일치하는 이미지의 작은 부분을 찾기 위한 기술이다. 이는 제조 현장의 품질 관리, 이동 로봇의 내비게이션,Kyriacou, Theocharis, Guido Bugmann, and Stanislao Lauria. "Vision-based urban navigation procedures for verbally instructed robots ." Robotics and Autonomous Systems 51.1 (April 30, 2005): 69-80. Expanded Academic ASAP. Thomson Gale. 또는 이미지의 윤곽선 검출에 사용될 수 있다.WANG, CHING YANG, Ph.D. "EDGE DETECTION USING TEMPLATE MATCHING (IMAGE PROCESSING, THRESHOLD LOGIC, ANALYSIS, FILTERS)". Duke University, 1985, 288 pages; AAT 8523046

템플릿 매칭 작업의 주요 과제는 찾고자 하는 객체가 이미지에서 부분적으로 가려지는 폐색(occlusion) 감지, 객체가 왜곡되거나 다른 각도에서 촬영되는 비강체 변환(non-rigid transformations) 감지, 조명 및 배경 변화에 대한 민감도, 배경 클러터(background clutter), 그리고 크기 변화이다.

 특징 기반 접근 방식 
섬네일|은닉층은 이미지에 대한 분류 정보를 보유한 벡터를 출력하며, 이는 템플릿 매칭 알고리즘에서 이미지의 특징으로 사용된다.
특징 기반 템플릿 매칭 접근 방식은 대상 이미지 또는 프레임과 일치하는 모양, 질감, 색상과 같은 이미지 특징의 추출에 의존한다. 이 접근 방식은 일반적으로 신경망과 VGG, 알렉스넷, ResNet과 같은 딥 러닝 분류기를 사용하여 달성된다. 많은 현대적 분류기의 기초가 되는 합성곱 신경망(CNN)은 이미지를 서로 다른 은닉층을 통과시켜 처리하며, 각 층에서 이미지에 대한 분류 정보를 담은 벡터를 생성한다. 이러한 벡터들은 네트워크에서 추출되어 이미지의 특징으로 사용된다. CNN과 같은 심층 신경망을 이용한 특징 추출은 매우 효과적인 것으로 입증되었으며 최첨단 템플릿 매칭 알고리즘의 표준이 되었다.

이러한 특징 기반 접근 방식은 아래에 설명된 템플릿 기반 접근 방식보다 종종 더 견고하다. 비강체 및 평면 외 변환은 물론 높은 배경 클러터와 조명 변화가 있는 템플릿을 매칭할 수 있기 때문에 템플릿 매칭의 최첨단 방법이 되었다.Li, Yuhai, L. Jian, T. Jinwen, X. Honbo. “A fast rotated template matching based on point feature.” Proceedings of the SPIE 6043 (2005): 453-459. MIPPR 2005: SAR and Multispectral Image Processing.B. Sirmacek, C. Unsalan. “Urban Area and Building Detection Using SIFT Keypoints and Graph Theory”, IEEE Transactions on Geoscience and Remote Sensing, Vol.47 (4), pp. 1156-1167, April 2009.

 템플릿 기반 접근 방식 
섬네일|회전된 템플릿을 이용한 템플릿 매칭
강력한 특징이 없는 템플릿이나, 템플릿 이미지의 대부분이 매칭 이미지 전체를 구성하는 경우 템플릿 기반 접근 방식이 효과적일 수 있다. 템플릿 기반 매칭은 방대한 양의 데이터 포인트 샘플링이 필요할 수 있으므로, 결과적으로 축소된 이미지에서 연산을 수행하기 전에 검색 이미지와 템플릿 이미지의 해상도를 동일한 비율로 낮추어 샘플링 포인트 수를 줄이는 것이 바람직한 경우가 많다. 이 전처리 방법은 이미지의 다중 스케일 또는 피라미드 표현을 생성하여, 검색 이미지 내 데이터 포인트의 검색 창을 축소함으로써 템플릿을 모든 실행 가능한 데이터 포인트와 비교하지 않아도 되도록 한다. 피라미드 표현은 차원의 저주를 겪는 데이터 세트에 대한 머신러닝의 공통 목표인 차원 축소의 한 방법이다.

 일반적인 과제 

템플릿이 직접적인 일치를 제공하지 못하는 경우, 다양한 원근법, 조명, 색상 대비 또는 객체 포즈와 같은 여러 조건에서 일치하는 객체를 상세히 나타내는 템플릿을 만들기 위해 고유공간(eigenspaces)을 구현하는 것이 유용할 수 있다.Luis A. Mateos, Dan Shao and Walter G. Kropatsch. Expanding Irregular Graph Pyramid for an Approaching Object. CIARP 2009: 885-891. 예를 들어, 알고리즘이 얼굴을 찾는 경우 템플릿 고유공간은 카메라에 대한 위치, 조명 조건 또는 표정(즉, 포즈)이 다른 얼굴 이미지(즉, 템플릿)들로 구성될 수 있다.

또한 매칭되는 이미지가 다른 물체에 의해 가려지거나 폐색될 수 있다. 이러한 경우 가능한 모든 폐색 상황을 다루기 위해 수많은 템플릿을 제공하는 것은 비합리적이다. 예를 들어 검색 대상이 카드인데, 일부 검색 이미지에서 카드가 카드를 잡고 있는 사람의 손가락이나 그 위의 다른 카드, 또는 카메라 앞의 다른 물체에 의해 가려질 수 있다. 객체가 변형 가능하거나 자세를 바꿀 수 있는 경우 동작(motion)이 추가적인 문제가 되며, 동작과 폐색이 모두 포함된 문제는 모호해진다.F. Jurie and M. Dhome. Real time robust template matching. In British Machine Vision Conference, pages 123–131, 2002. 이러한 경우 가능한 해결책 중 하나는 템플릿 이미지를 여러 하위 이미지로 나누고 각 세분화된 부분에 대해 매칭을 수행하는 것이다.

 계산 해부학에서의 변형 가능한 템플릿 
템플릿 매칭은 계산 해부학(CA)의 핵심 도구이다. 이 분야에서는 변형 가능한 템플릿 모델을 사용하여 인간 해부학의 공간과 객체를 부드럽게 변형하는 함수인 미분동형사상 군 아래에서의 그들의 궤도를 모델링한다. 템플릿 매칭은 대상 이미지와 일치시키기 위해 템플릿 이미지에 작용하는 알려지지 않은 미분동형사상을 찾는 접근 방식으로 나타난다.

계산 해부학에서의 템플릿 매칭 알고리즘은 대변형 미분동형 메트릭 매핑(LDDMM)이라고 불리게 되었다. 현재 해부학적 특징점, 곡선, 곡면, 볼륨을 매칭하기 위한 LDDMM 템플릿 매칭 알고리즘이 존재한다.

 상호 상관 또는 절대 차이의 합을 이용한 템플릿 기반 매칭 설명 

때때로 "선형 공간 필터링"이라고 불리는 템플릿 매칭의 기본 방법은 검색 이미지의 감지할 특정 특징에 맞춰진 이미지 패치(즉, "템플릿 이미지" 또는 "필터 마스크")를 사용한다. 이 기술은 색상이라는 추가 변수가 존재하지 않거나 관련이 없는 회색조 이미지 또는 윤곽선 이미지에서 쉽게 수행될 수 있다. 상호 상관 기술은 검색 이미지와 템플릿 이미지의 유사성을 비교한다. 출력은 이미지 구조가 템플릿 구조와 일치하는 위치, 즉 큰 검색 이미지 값과 큰 템플릿 이미지 값이 곱해지는 위치에서 가장 높아야 한다.

이 방법은 보통 검색 이미지의 일부를 템플릿으로 선택하여 먼저 구현된다. 를 검색 이미지 픽셀의 값이라 하고, 여기서 는 검색 이미지 내 픽셀의 좌표를 나타낸다. 단순화를 위해 회색조 이미지에서와 같이 픽셀 값이 스칼라라고 가정한다. 마찬가지로 를 템플릿 픽셀의 값이라 하고, 여기서 는 템플릿 이미지 내 픽셀의 좌표를 나타낸다. 필터를 적용하려면 템플릿 이미지의 중심(또는 원점)을 검색 이미지의 각 점 위로 이동시키고, 템플릿이 차지하는 전체 영역에 대해 검색 이미지와 템플릿 이미지의 픽셀 값 사이의 스칼라곱과 유사한 곱의 합을 계산한다. 더 공식적으로, 이 템플릿 이미지의 중심(또는 원점)인 경우, 검색 이미지의 각 점 에서의 상호 상관 는 다음과 같이 계산될 수 있다.편의상 는 템플릿 이미지의 픽셀 값뿐만 아니라 그 정의역, 즉 템플릿의 범위를 나타낸다. 검색 이미지에 대한 템플릿의 가능한 모든 위치가 고려된다는 점에 유의하라. 상호 상관 값은 검색 픽셀과 템플릿 픽셀의 값이 정렬될 때 가장 크므로, 최적의 매칭 위치 은 에 대한 의 최댓값에 해당한다.

템플릿 매칭을 사용하여 이미지의 평행 이동 문제를 처리하는 또 다른 방법은 절대 차이의 합(SAD) 측정값을 사용하여 픽셀의 강도를 비교하는 것이다. 이를 공식화하기 위해 와 를 각각 좌표 와 를 갖는 검색 이미지와 템플릿 이미지 픽셀의 광도라고 하자. 그런 다음 이전과 같이 템플릿의 중심(또는 원점)을 검색 이미지의 한 점 로 이동하면 해당 지점에서의 템플릿과 검색 픽셀 강도 사이의 절대 차이의 합은 다음과 같다.이 측정값을 사용하면 상호 상관에서와 같이 최대치가 아닌 가장 낮은 SAD가 템플릿의 최적 위치를 제공한다. SAD는 구현과 이해가 상대적으로 간단한 경향이 있지만 실행 속도는 상대적으로 느린 경향이 있다. SAD 템플릿 매칭의 간단한 C++ 구현이 아래에 제공된다.

 구현 
이 간단한 구현에서는 위에서 설명한 방법이 회색조 이미지에 적용된다고 가정한다. 이것이 픽셀 강도로 Grey가 사용된 이유이다. 이 구현의 최종 위치는 템플릿 이미지가 검색 이미지와 가장 잘 일치하는 왼쪽 상단 위치를 제공한다.

minSAD = VALUE_MAX;

// 검색 이미지를 반복 조사
for ( size_t x = 0; x <= S_cols - T_cols; x++ ) {
    for ( size_t y = 0; y <= S_rows - T_rows; y++ ) {
        SAD = 0.0;

        // 템플릿 이미지를 반복 조사
        for ( size_t j = 0; j < T_cols; j++ )
            for ( size_t i = 0; i < T_rows; i++ ) {

                pixel p_SearchIMG = S[y+i][x+j];
                pixel p_TemplateIMG = T[i][j];

                SAD += abs( p_SearchIMG.Grey - p_TemplateIMG.Grey );
            }

        // 찾은 최적의 위치를 저장
        if ( minSAD > SAD ) {
            minSAD = SAD;
            // 최소 SAD 값 제공
            position.bestRow = y;
            position.bestCol = x;
            position.bestSAD = SAD;
        }
    }

}

컬러 이미지에서 템플릿 매칭을 수행하는 한 가지 방법은 픽셀을 색상 구성 요소로 분해하고 각 색상에 대해 별도로 계산된 SAD의 합을 사용하여 컬러 템플릿과 검색 이미지 사이의 매칭 품질을 측정하는 것이다.

 프로세스 속도 향상 

과거에는 연산의 복잡성 때문에 이러한 유형의 공간 필터링이 일반적으로 전용 하드웨어 솔루션에서만 사용되었으나,Gonzalez, R, Woods, R, Eddins, S "Digital Image Processing using Matlab" Prentice Hall, 2004 이미지를 주파수 도메인에서 필터링하는 '주파수 도메인 필터링'을 통해 이러한 복잡성을 줄일 수 있으며, 이는 합성곱 정리를 사용하여 수행된다.

매칭 프로세스를 가속화하는 또 다른 방법은 이미지 피라미드를 사용하는 것이다. 이는 감소된 해상도의 이미지 시퀀스를 생성하기 위해 원본 이미지를 반복적으로 필터링하고 서브샘플링하여 형성된 서로 다른 스케일의 일련의 이미지이다.E. H. Adelson, C. H. Anderson, J. R. Bergen, P. J. Burt and J. M. Ogden, Pyramid methods in image processing http://web.mit.edu/persci/people/adelson/pub_pdfs/RCA84.pdf 이러한 저해상도 이미지에서 (마찬가지로 해상도가 낮아진) 템플릿을 검색하여 더 큰 스케일에서 검색을 시작할 가능한 위치를 확보할 수 있다. 그런 다음 더 큰 이미지의 시작 위치 주변의 작은 창에서 최적의 템플릿 위치를 검색할 수 있다.

다른 방법들은 평행 이동, 스케일, 이미지 회전 및 모든 아핀 변환과 같은 문제들을 처리할 수 있다.Yuan, Po, M.S.E.E. "Translation, scale, rotation and threshold invariant pattern recognition system". The University of Texas at Dallas, 1993, 62 pages; AAT EP13780H. Y. Kim and S. A. Araújo, "Grayscale Template-Matching Invariant to Rotation, Scale, Translation, Brightness and Contrast," IEEE Pacific-Rim Symposium on Image and Video Technology, Lecture Notes in Computer Science, vol. 4872, pp. 100-113, 2007.Korman S., Reichman D., Tsur G. and Avidan S., "FAsT-Match: Fast Affine Template Matching", CVPR2013.

 매칭 정확도 향상 

하나 이상의 템플릿(고유공간)을 사용하여 매칭 방법을 개선할 수 있으며, 이러한 다른 템플릿들은 서로 다른 스케일과 회전 각도를 가질 수 있다.

또한 특징 기반 접근 방식과 템플릿 기반 접근 방식을 혼합하여 매칭 방법의 정확도를 높일 수도 있다.C. T. Yuen, M. Rizon, W. S. San, and T. C. Seong. “Facial Features for Template Matching Based Face Recognition.” American Journal of Engineering and Applied Sciences 3 (1): 899-903, 2010. 당연히 이는 검색 이미지와 템플릿 이미지가 특징 매칭을 지원할 만큼 충분히 뚜렷한 특징을 가지고 있어야 한다.

 유사한 방법 

유사한 다른 방법으로는 '스테레오 매칭', '영상 정합' 및 '척도 불변 특징 변환'이 있다.

 사용 예 

템플릿 매칭은 다양한 응용 분야를 가지고 있으며 얼굴 인식(얼굴 인식 시스템 참조) 및 의료 영상 처리와 같은 분야에서 사용된다. 과거에는 일정 시간 동안 다리의 일부를 걸어가는 얼굴의 수를 세는 시스템이 개발되어 사용되기도 했다. 다른 시스템으로는 디지털 흉부 X선 내의 자동화된 석회화 결절 감지가 있다.Ashley Aberneithy. "Automatic Detection of Calcified Nodules of Patients with Tuberculous". University College London, 2007
최근에 이 방법은 빠른 알고리즘을 제공할 수 있는 지구 통계학적 시뮬레이션에서 구현되었다.Tahmasebi, P., Hezarkhani, A., Sahimi, M., 2012, Multiple-point geostatistical modeling based on the cross-correlation functions, Computational Geosciences, 16(3):779-79742.

 같이 보기 
 얼굴 인식 시스템
 패턴 인식
 컴퓨터 비전
 탄성 매칭

 각주 

 외부 링크 
 OpenCV에서의 템플릿 매칭
 템플릿 매칭을 이용한 시각적 객체 인식
 회전, 스케일, 평행 이동 불변 템플릿 매칭 시연 프로그램
 원근 불변 템플릿 매칭
 2009년까지의 광범위한 템플릿 매칭 참고 문헌

분류:영상 처리