Fast Connected Component Labeling Algorithm Using A Divide and Conquer Technique
1. Introduction
Connected component 알고리즘은 Rosenfeld, Pfaltz의 알고리즘이 잘 알려져 있습니다. 2패스로 이루어진 이 알고리즘은 첫번째 단계에서 먼저 요소들을 대강 연결하는 대신, 다른 레이블이지만 같은 물체인 것들을 미리 기록해 두었다가 두번째 단계에서 이를 토대로 완전하게 물체를 연결시키는 방법입니다. 이러한 방법 탓에 이미지가 커지고 복잡해질 수록 같은 물체임을 기록시키는 equivalence array 또한 커지기 때문에 처리 속도가 늦어지게 됩니다.
2. Connected Components
기존의 방법은 너무도 고전이기에 생략하기로 합시다.
3. A Fast Connected Component Labeling Algorithm
Connected Component 작업을 빠르게 하기 위한 기본 아이디어는 이미지를 N * M으로 나누어서 처리하는 것입니다. 큰 크기의 equivalence array가 병목현상의 주 원인이기 때문입니다. equivalence array는 보통 행렬의 형태를 띄기 때문에 이미지를 반으로 나누면 array는 1/4로 줄어들게 됩니다. 때문에 이미지를 나눠서 처리하는 것이 효과가 있게 됩니다.
각 나눠진 이미지 영엑에 기존 알고리즘의 1패스를 적용하고 equivalence array를 구한 뒤에, 영역과 영역이 겹치는 경계 부분에서 서로 연결되는지 여부를 다시 한번 검사합니다.
4. Experiment Results
실험에서는 1760 * 1168 크기의 이미지를 N = 4, 5, 10, 15, 20, 25으로 나눠진 결과를 보여주는데 상당한 시간 단축이 있는 것으로 나타났다고 이야기하고 있습니다.