Pattern matching plays an important role in various fields such as image registration, stereo matching, image coding, texture synthesis, image retrieval, object tracking, etc. Since the pattern matching process have been a time-consuming work, many fast pattern matching algorithms have been proposed. They can be categorized into several groups: 1) candidate sampling; 2) simplification of matching criterion; 3) bitwidth reduction; 4) hierarchical search; and 5) fast full-search. By adopting mathematical inequality, fast full-search can be boosted while preserving the same result of full search algorithm.
In this dissertation, fast full-search pattern matching schemes based on four different criteria (sum of absolute difference, sum of squared error, normalized cross correlation, and pixel difference classification) are further investigated and compared to several conventional schemes. Key tools of proposed schemes are the Minkowski inequality, the Cauchy-Schwarz inequality, and the concept of integral image. Simulation results show that proposed schemes outperform conventional schemes.
패턴 정합 (Pattern Matching)은 주어진 후보 패턴들 (Candidate Patterns) 중에서 질의 패턴 (Query Pattern)과 가장 닮은 후보 패턴을 찾는 과정으로써, 영상 정합, 스테레오 정합, 영상 압축, 텍스쳐 합성, 영상 검색, 영상 추적 및 인식 등 많은 응용 분야를 가지고 있다. 하지만, 질의 패턴이나 후보 패턴들의 차원이 높고 후보 패턴들의 수가 많기 때문에, 패턴 정합 과정은 일반적으로 시간이 오래 걸리는 작업에 속했다. 이를 극복하기 위해 많은 연구들이 이루어졌으며 이러한 연구들은 1) 후보군 샘플링; 2) 질의 패턴의 차원 축소; 3) 정합 기준의 단순화; 4) 근사값과 참값 사이의 부등식 관계를 이용한 정합 고속화 등으로 정리할 수 있다.
이 중 1), 2), 3) 방법의 경우, 전역 검색에 의한 패턴 정합의 결과와 다른 값이 도출될 수 있으나 4) 방법의 경우, 전역 검색에 의한 결과와 완전히 동일한 결과를 내면서도 고속으로 이를 수행하는 장점을 가진다. 이것은 패턴 정합에 주로 사용하는 정합 기준, 곧 화소차합 (Sum of Absolute Difference: SAD)이나 화소차 제곱합 (Sum of Squared Error: SSE) 대신 하한값을 구하여 서로 비교함으로써 이루어진다.
본 논문에서는 네가지 정합 기준: 화소차합, 화소차 제곱합, 정규상관도 (Normalized Cross Correlation: NCC), 화소차 판별 (Pixel Difference Classification: PDC) 에 대해 고속으로 이를 수행할 수 있는 기법들을 제안하고 서로 비교하였다. 먼저, 화소차합 (SAD) 고속화를 위해서는 Minkowski 부등식에 기반하여 다층의 하한값을 생성한 후 서로 비교하는 형태를 취하였고, 이것은 승자 갱신 방식 (Winner-Update Algorithm: WUA) 으로 효율적으로 수행될 수 있었다. 더불어, 블록합 피라미드 (Block Sum Pyramid) 를 이용하여 패턴 정합을 하던 기존의 접근 방법에 비해 적분 영상 (Integral Image) 을 이용하여 패턴 정합을 수행함으로써, 필요로하는 메모리의 크기를 줄이고, 정합 전 준비 단계에 걸리는 시간을 줄임으로써, 기존 기법 대비 속도 향상을 가져왔다.
화소차 제곱합을 고속화하기 위해서는 Cauchy-Schwarz 부등식에 근거한 서로 다른 특성의 두가지 다층 하한값을 얻었다. 이 중 하나는 비교하는 두 패턴간의 차이가 일정할 때 정확한 화소차 제곱합을 빠르게 알아낼 수 있고, 다른 하나는 두 패턴간의 비율이 일정할 때 정확한 화소차 제곱합을 알아낼 수 있다. 이 두 다층 하한값은 정규상관도를 고속화하는데에도 사용되어, 정규상관도를 기준으로 빠르게 정합할 수 있는 기법도 제안되었다. 또한, 정규상관도의 실험 결과에 따라, 두 가지 방식의 장점을 모은 기법도 함께 제안되었다.
화소차 판별을 위해서는 투표 방식에 기반한 접근 방식이 이루어졌고, 이것은 부분적으로 패턴이 가려지는 경우나 반점성 모양의 잡음 (Speckle Noise) 에 강인한 특성을 가진다. 앞서 기술된 패턴 정합 기법들은 제안된 비디오 분석 시스템의 영상 안정화 부분과 추적 부분에 탑재되었다.
