GPU를 위한 Feature Extraction 및 Matching Algorithm 병렬화

Abstract

Feature matching은 image 사이에서 유사한 feature를 찾기 위하여 computer vision 분야에 많이 사용된다. Matching 알고리즘은 feature 사이의 geometry 정보를 사용하는가에 따라 first-order matching과 high-order graph matching 방법으로 분류된다. 일반적으로 사용되는 방법은 first-order matching으로, 각 feature의 주변 영역에 대한 정보를 기반으로 유사한 feature를 찾는다. 그러나, 이 방법은 feature 사이의 geometry 정보를 고려하지 않기 때문에 반복되는 패턴, 텍스쳐 또는 불분명한 주변 영역 등으로 인한 이미지 모호성에 민감하다는 단점이 있다. 반면, high-order graph matching 은 feature 사이의 geometry 정보를 기반으로 matching을 수행한다. 이 algorithm은 first-order matching에 비하여 반복되는 형태나 불분명한 영역에 더 강인하다. 그러나, high-order matching는 높은 연산 복잡도로 인하여 처리 속도가 매우 느리다. 본 논문에서는 GPU를 위한 high-order graph matching의 네 가지 병렬화 방법을 제시한다. 첫째, high-order graph matching의 symmetric 특징을 이용하여 GPU에서 적합하지 않은 memory 접근 pattern을 제거한다. High-order graph matching에서 병렬 처리를 어렵게 하는 것은 같은 memory 위치에서 여러 개의 thread들이 동시에 data를 update함으로써 발생되는 write collision이다. High-order graph matching에서는 같은 solution을 생성할 수 있는 여러 개의 objective function이 존재한다. 이 성질을 이용하여 제안하는 방법은 write collision을 일으키는 operation들을 같은 solution을 갖는 다른 operation들로 교체하여 write collision을 제거한다. 둘째, memory 사용량 감소를 위한 Approximate Spectral Matching algorithm을 적용하고, 이를 GPU에서 효율적으로 처리하기 위한 병렬처리 방법을 제시한다. High-order graph matching은 similarity 값을 저장하기 위하여 매우 큰 memory 사용량을 요구한다. Approximate Spectral Matching 은 feature 사이의 geometry 정보를 approximation함으로써, similarity의 개수를 감소시켰다. 그러나, 이 방법은 sparse tensor를 이용해야 하며, 이는 GPU에서 효율적으로 처리되기 어려운 memory 접근 pattern을 발생시킨다. 본 연구에서는 이 memory 접근 pattern이 나타나는 연산 과정을 graph matching algorithm에서 분리하고, 분리된 연산을 GPU에서 효율적으로 처리하기 위한 thread structure를 제시한다. 셋째, memory 사용량을 추가적으로 감소시키기 위한 approximation 방법을 제시한다. Approximate Spectral Matching을 사용할 때, 높은 matching 정확도를 위해서는 approximation 정도가 낮아야 한다. 그러나, approximation 정도가 낮을 때, memory 사용량은 크게 감소되지 못한다. Approximate Spectral Matching Algorithm이 reference feature set만 approximation한다는 고려하여, 본 연구에서는 query feature set도 함께 approximation하는 방법을 제시한다. 제안하는 방법을 사용함으로써, similarity 개수가 크게 감소되며, memory 사용량은 approximation 정도에 영향을 받지 않는다. 또한, shared memory를 이용하여 제안하는 approximation 방법을 GPU에서 효율적으로 처리하기 위한 방법을 제시한다. 넷째, 제안하는 approximation 방법의 GPU utilization 향상을 위한 tuple clustering 방법을 제안 한다. 제안하는 approximation 방법을 사용할 경우, thread-block 사이의 workload unbalance가 발생한다. 이는 GPU streaming multiprocessor의 workload를 달라지게 하며, streaming multiprocessor의 utilization을 크게 하락 시킨다. Thread-block의 workload unbalance가 발생하는 원인은 각 thread-block이 접근하는 data structure가 sparse하며, 이러한 sparse data structure의 non-zero element 개수가 서로 다르기 때문이다. 본 연구에서는 tuple clustering 방법을 이용하여 sparse data structure들의 non-zero element 개수를 유사하게 만든다. 또한, score 기여도 기반 clustering 방법을 제시하여 matching 정확도 하락을 최소화한다. Scale-invariant feature transform (SIFT)는 computer vision 분야에서 가장 널리 사용되는 feature이다. 이 feature는 크기, 회전 등 다양한 image 변화에 강인하다. 그러나, 이러한 높은 강인함을 위하여 SIFT의 연산 복잡도는 매우 높으며, 이를 실시간으로 처리하는 것은 어렵다. 본 연구에서는 SIFT 알고리즘을 GPU에서 효율적으로 처리되기 위한 방법을 제시한다. SIFT에서 scale-space 생성 과정을 분석하고, Gaussian filter 크기와 scale-space image 크기를 동시에 감소시키는 것이 feature의 강인함을 크게 하락시키지 않으면서 큰 속도 향상을 얻을 수 있음을 확인하였다. 이러한 관찰로부터, 실시간 처리를 위하여 SIFT 알고리즘을 변형하고 구현하였다. CPU와 GPU를 효율적으로 이용하는 최적화 방안을 제시하여, 추가적인 속도 향상을 달성하였다.