link: https://www.sciencedirect.com/science/article/pii/S1077314203001401
Abstract ~ 1.Introduction:
제안하는 방법의 이점:
1. 이미지에 대해 1-pass만 필요함. 본 논문에서 제안한 contour tracing 절차로 인해서 contour point들은 한번 이상 방문이 되지만, 단지 일정한 시간에 불과함.
2. 어떠한 re-labeling 메커니즘도 필요로 하지 않음. 일단 하나의 pixel에 labeling index가 할당되면, 해당 값은 변하지 않음.
3. 모든 contour들과 sequential order의 contour pixel들을 product함으로써 얻을 수 있음.
4. 실험 결과 전통적인 component-labeling 알고리즘 보다 빠른 결과를 보임.
2. Review of Traditional Component-Labeling Algorithms: 간략하게 리뷰
component labeling을 위한 1)~5)개의 중요한 방법들에 대해서 리뷰함.
2)~5)는 1)의 개선된 목적으로 나온 방법들임.
1)~5)번째 모두 8-connectivity에 따라서 component pixel들에 대한 re-labeling을 수행함.
- 1) Rosenfeld and Pfaltz [13]: 이진 영상에 대해 2-pass 를 수행.
- 2) Haralick [8]: 1의 방법에서 array pair에 필요한 여분의 저장 공간을 제거하기 위한 방법을 제안, 메모리는 절약되었으나, 영상의 복잡도에 따라서 전반적인 처리속도가 변화함.
- 3) Lumia, Shapiro, and Zuniga[11]: 1)과 2) 사이의 절충안으로 나온 기법임.
- 4) Fiorio and Gustedt [4]: component-labeling problem에 대해 linear-time으로 동작하기 위해 union-find algorithm의 special version을 적용함. 2-pass로 구성이 되어 있음.
- 5) Shima, Murakami, Koga, Yashiro, and Fujisawa [14]: 압축된 영상에 대해 특별히 적합한 방법임.
3. Our Method
이진 영상에 대해 각 line 마다 top->bottom 및 left->right 으로 scan을 수행함. 그림 1의 a~d까지 4개의 주요 단계로 제안한 알고리즘의 operation을 개념적으로 나눔.
- 1) 그림 1의 a에서 external contour point A를 처음 만나게 되면, A를 반환할 때까지 완전한 contour trace를 생성함. 하나의 label을 A와 contour를 구성하는 모든 점들에 대해 할당함.
- 2) 그림 1의 b에서 labeled된 external contour point A`을 만나게 되면, 바로 다음에 이어지는 모든 black pixel들을 찾기 위해 scan line을 따라가며, 이들에게 A`과 동일한 label을 할당함.
- 3) 그림 1의 c에서 internal contour point B를 처음 만나게 되면, B에 external contour의 동일한 component로서 동일한 label을 할당함. 그 다음에 B를 포함하고 있는 internal contour를 trace하며, 또한 모든 contour point들에게 B와 동일한 label을 할당함.
- 4) 그림 1의 d에서 labeled된 internal contour point B`을 만나게 되면, 바로 다음에 이어지는 모든 black pixel들을 찾기 위해 scan line을 따라가며, 이들에게 B`과 동일한 label을 할당함.
위의 절차에서 본 논문에서는 단지 이미지에 대해 single pass만을 수행하며, 각 component point에게 scan line 상에 이전의 point로서 하나의 새로운 label 또는 동일한 label을 할당함.
알고리즘의 세부 사항:
단순함을 위해, 가장 상위의 row에 위치한 pixel들은 모두 white pixel이라고 가정함. 하나의 주어진 문서 이미지 I에 대해, label 정보를 저장하는 이미지 L을 연관지음. 초기에, 이미지 L의 모든 점들은 0으로 설정됨(labeling이 안된 상태). 그 다음에 black pixel을 찾기 위해 이미지 I의 scan을 시작함. C는 component에 대한 label의 index를 말하며, 초기에 C는 1이 되도록 설정함. 이전에 언급한 그림 1의 a~d 단계는 논리상 3개의 단계로 줄어들 수 있음.
- 단계 1: 새롭게 만난 external point들과 이들을 구성하는 contour의 모든 point들을 다룸.
- 단계 2: 새롭게 만난 internal point들과 이들을 구성하는 contour의 모든 point들을 다룸.
- 단계 3: 단계 1과 단계 2에서 다뤄지지 않은 모든 black pixel들에 대해 다룸.
- P: 본 논문에서 다뤄지는 current point를 의미함.
- C: component에 대한 label의 index를 말하며, 초기에 C는 1이 되도록 설정되어 있음.
단계 1: 만약 P가 unlabeled 되었고, P의 위에 있는 pixel이 그림 2와 같이 white pixel이라면, P는 새롭게 만난 component의 external contour 상에 존재해야 함. external contour를 찾기 위해 contour tracing(이후에 해당 절차는 언급될 예정임)을 수행하면서, label C를 P에 할당하도록 모든 contour pixel들에게 label C를 할당함. 그 다음에 C의 값을 1씩 증가시킴.
단계 2: 만약 P의 아래에 있는 pixel이 unmarked 된 white pixel이라면 P는 새롭게 만난 internal contour 상에 있어야 함. 2가지의 가능성이 있는데 첫 번째로 P가 그림 3의 a와 같이 이미 labeled된 경우이며, 이 경우에 P는 또한 external contour pixel이 됨. 두 번째로 그림 3의 b와 같이 P가 unlabeled 된 경우이며, 이 경우에 scan line 상에 있는 이전의 point N(P의 좌측 이웃)은 labeled 되어 있어야 함. 그러한 경우라면, P에게 N과 동일한 label을 할당하며, 그렇지 않은 경우라면 P를 포함하고 있는 internal contour를 찾기 위해 계속해서 contour tracing을 수행하고 동일한 label을 모든 contour pixel들에게 할당함.
단계 3: 만약 P가 단계 1~2에서 다뤄진 점이 아니라면(예: P는 contour pixel이 아님), P의 좌측 이웃 N은 그림 4와 같이 labeled된 pixel이 되어야 함. P에 N과 동일한 label을 할당함.
point Q에서 Contour tracing의 수행을 피하기 위해서는 그림 5와 같이 하나의 component 인근의 white pixel들을 음수(-)로 mark 함. 따라서 scan line이 Q를 sweep 할 때, Q 아래의 픽셀은 더 이상 unmarked된 white pixel이 아니게 됨. 반면에, 처음 만났던 internal contour pixel P의 아래에 있는 이웃 픽셀은 internal contour를 포함하고 있는 pixel이 아직 traced 되지 않았기 때문에 여전히 unmarked 되어 있음.
인근의 white pixel들을 marking 함으로써, 각각의 internal contour는 단지 한번만 traced 된다는 것을 보증할 수 있음. 그림 6에서 설명하듯이, internal contour가 traced 되면, R 아래에 있는 이웃 픽셀들은 더 이상 unmarked pixel이 아니며, 따라서 scan line에 따라 R을 만났을 때, 또 다시 internal contour의 tracing을 하는 것을 피할 수 있음.
- 인근의 white pixel들을 음수로 marking 하는 연산은 Tracer 절차에 포함되어지며, 이러한 절차는 앞으로 Contour Tracing이라고 부를 것임.
3.1 Contour Tracing
Contour Tracing 절차의 목적은 하나의 주어진 point에 대해 external 또는 internal contour를 찾는 것임. point S에서, Tracer라고 부르는 절차를 수행함. 만약 Tracer가 S를 하나의 고립된 point로 식별한다면, Contour Tracing의 끝에 도달함. 그렇지 않으면 Tracer는 S 다음의 contour point를 출력할 것이며, 이러한 point를 T라고 칭함. 그 후 T 다음에 contour point를 찾기 위해 다음의 2가지 조건이 만족될 때까지 계속해서 Tracer를 수행함.
- 1) Tracer가 S를 출력하고,
- 2) S 다음의 contour point가 T임.
- 이러한 절차는 조건 1)과 조건 2)가 모두 만족할 때만 멈추게 됨.
그림 7에서 볼 수 있듯이, S가 starting point이며, T가 다음 contour point 일 때, Tracer에 의해 추적된 path는 STUTSVWVS가 됨.
3.2 Tracer
하나의 주어진 contour point P에 대해서, Tracer의 목적은 P를 둘러싸고 있는 8개의 이웃 points들 중에서 P 다음의 contour point를 찾는 것임. P에 대한 각각의 이웃 point의 위치는 그림 8의 a와 같이 하나의 index로서 할당되어짐. 검색은 다음과 같은 방법으로 결정이 되는 초기 위시에서 시계 방향으로 진행이 됨.
- 만약 P가 external contour의 starting point이면, P의 위에 있는 point는 white pixel이 되도록 알려져 있으며, 시계 방향에서 다음 point는 위치 7이 되기 때문에 초기 위치는 7(우측 상단)로 설정이 됨.
- 하지만 만약, P가 internal contour의 starting point이면, P의 아래에 있는 point는 또한 white pixel이 되도록 알려져 있으며, 시계 방향에서 다음 point의 위치는 3이 되기 때문에 초기 위치는 3(좌측 하단)으로 설정이 됨.
- 반면에, 만약 이전의 contour point가 존재하며, 위치 3(좌측 하단)에 놓여 있는 경우라면, 위치 4에서의 pixel은 그림 8의 b와 같이 이미 방문했기 때문에 그 다음의 초기 위치는 5로 설정이 됨.
- 일반적으로 P가 contour의 starting point가 아닐 때, contour가 외부 또는 내부에 있는 것과 관계 없이, 초기 검색 위치는 d+2(mod 8)가 되며, 여기서 d는 이전 contour point의 위치가 됨.
일단 초기의 위치가 결정되면, 첫 번째 black pixel을 찾기 위해 시계 방향으로 계속해서 진행이 됨. 이 pixel은 P 다음의 contour point가 되며, 만약 전체 원 안에서 발견된 black pixel이 없는 경우에는 P는 고립된 point가 되도록 식별되어짐. white pixel들 인근에 marking(음수로 표시)하는 것은 다음의 contour point에 대한 탐색을 하기 때문에 수행될 수 있음. 그림 9에서 볼 수 있듯이, A는 current point이며, C는 다음의 contour point임. A로부터 C로 추적될 때, white pixel B를 음수로 mark 함.
4. Complexity and Efficacy: Theorem 5개만 요약
- 1) 제안한 알고리즘은 각 pixel을 일정한 회수로 방문함.
- 2) 제안한 알고리즘은 linear-time으로 동작함.
- 3) 동일한 component에 있는 모든 pixel들은 동일한 label을 할당 받음.
- 4) 다른 component에 있는 픽셀들은 다른 label을 할당 받음.
- 5) 제안한 알고리즘은 component에 대해 옳바른 labeling 결과를 보임.