세선화(Thinning) 세선화란 세선화는 이진화 된 영상에서 골격을 찾는 영상처리 기법 세선화의 조건 두꺼운 영역이 포함된 영상을 입력으로 받아 한 화소 두께의 출력 영상을 만듬 세선화는 문자인식, 지문인식, 물체인식 등의 특징추출 전 단계에 적용되는 기본적인 영상처리 알고리듬 세선화의 조건 화소의 두께는 한 화소(골격선 폭 1) 세선화된 화소의 위치(골격선의 위치)는 도형이나 선에서 항상 중심에 위치 골격선은 원래의 도형에 있어서의 연결성을 유지하여야 한다. 세선화 과정에서 골격선의 길이가 계속해서 줄어서는 안된다. 패턴 윤곽선의 작은 요철로 인한 잡가지의 모양이 골격선에 첨가되지 않아야 한다. 순차적처리 세선화 와 병렬적처리 세선화 순차적 처리 (sequential processing) 방법 병렬적 처리 (parallel processing) 방법 현재의 처리 결과가 과거와 처리값에 영향을 줌 - 버퍼가 대상 화상만 있으면 처리가 가능 - 현재의 처리 결과가 과거나 미래의 처리 결과에 전혀 영향을 받거나 미치지 않음 - 추가로 대상 화상 크기만큼 버퍼가 필요 즉, 병렬 처리 방법에서는 현재의 관심 화소(pixel)에 대한 처리 결과를 버퍼에 저장하는 식으로, 전체 화상에 대한 한차례의 처리가 모두 끝난 다음에, 버퍼에 저장되어 있는 처리 결과를 원래의 대상 화상위에 덮어 쓰게 된다.

그림 3. 화소의 위치 (a) step 3, (b) step 4, (c) step 3’, (d) step 4’ Zhang-Suen Algorithm Zhang-Suen Algorithm은 오랫동안 thinning method에 대한 기본적인 비교자료로 사용되어 왔었고, 구현하기에 빠르고 간단하다. 이 알고리즘은 두 개의 부분반복(two subiterations)를 갖는다. 하나는 픽셀 I(i,j)가 다음 4가지 조건이 모두 True가 될 때, 삭제를 위하여 마크되거나 삭제된다 Rule 1 step 1 : 화소 P가 연결 영역의 수는 1 이어야 한다. step 2 : 화소 P가 적어도 2개 이상의 이웃 화소와 6개 이하의 화소를 이웃하여야 한다. step 3 : 화소P가 적어도 I(i, j+1), I(i-1, j), I(i, j-1)중에 한 개의 화소가 배경이어야 한다(그림 4a). step 4 : 화소P가 적어도 I(i-1, j), I(i+1, j), I(i, j-1)중에 한 개의 화소가 배경이어야 한다(그림 4b). Rule 1을 반복해서 수행하고, 지울 화소를 마크시켜 놓는다. Rule 2 step 1-2는 똑같이 실행하고, step 3’ : 화소P가 적어도 I(i-1, j), I(i, j+1), I(i+1, j)중에 한 개의 화소가 배경이어야 한다(그림 4c). step 4’ : 화소P가 적어도 I(i, j+1), I(i+1, j), I(i, j-1)중에 한 개의 화소가 배경이어야 한다(그림 4d). (a) (b) (c) (d) 그림 3. 화소의 위치 (a) step 3, (b) step 4, (c) step 3’, (d) step 4’

× ○ ● (a) (b) (c) (d) Stentiford Algorithm Stentiford algorithm[1] step 1 : 한 화소의 위치(i, j)를 찾아서 그림1의 M1 창틀과 일치 시킨다. step 2 : 제거 화소 결정. 만약에 중앙 화소가 끝점이 아니고, 연결 영역 수가 1 이면 다음에 제거할 화소 로 지정하여 Buffer에 Mark step 3 : 전체 영상을 처리. 창틀 M1을 이용하여 영상의 모든 부분을 처리할 때 처리 step 1에서 step 2 까지 반복 step 4 : 나머지 3개의 창틀에 처리. 창틀 M2, M3, 그리고 M4에 대한 처리 step 1에서 step 3 까지 반복 step 5 : 화소 제거 위 step에서 제거를 위해 Buffer에 Mark된 부분을 영상에 white 처리 step 6 : 처리 종료 여부 결정 step 5 에서 화소가 제거가 되면 처리를 step 1 로 넘기고, step 5 에서 화소 제거가 이루어지지 않으면 실행을 종료한다. × ○ ● (a) (b) (c) (d) M1 M2 M3 M4

전처리 과정 (smoothing step) 이진화 된 입력 화상 Stentiford / Zhang-Suen / Holt Combined Algorithm 알고리즘의 순서도 전처리 과정 (smoothing step) 이진화 된 입력 화상 Acute angle emphasis (예각에 대한 처리) 세선화 과정(Zhang-Suen 알고리즘) Holt’ Staircase-Removal (North와 South 방향으로 계단모양 처리) 세선화 결과 출력

Templates used for the acute ahgle emphasis preprocessing step   D1 D2 D3 D4 D5 U1 U2 U3 U4 U5 Templates used for the acute ahgle emphasis preprocessing step V(C) && !(V(N) && ((V(E) && !V(NE) && !V(SW) && (!V(W) || !(V(S)) || (V(W) && !(V(NW) && !V(SE) && (!V(E) || !V(S)))))) V함수 : 0, 1를 나타냄 C : Center Pixel N, S, W, E 등 : 방향 Holt’s staircase-removal expression

Steniford의 알고리즘 자체는 Zhang의 알고리즘보다 2번의 부분반복(two subiterations)을 더 반복하므로 속도는 더 느리다. 결과도 비슷하다. 그래서 Stentiford는 전처리로 Smooth을 처리를 제안했다. 또한 예각에 대한 처리로 acute angle emphasis라고 하는 5*5판형을 검사해서 예각에대한 문제를 해결하였다. 계단모양의 처리를 위해서 Holt’staircase removal을 더해줘서 프로그램의 효율을 높였다. 결과적으로 Zhang의 알고리즘보다 더 좋은 세선화를 구할 수 있었다. BIBLIOGRAPHY J. R. Parker Algorithms For Image Processing and Computer Vision: Skeletonization – the Essential Line.Wiley Computer Publishing 176-219

< 이미지처리 결과> (원화상) Zhang Thinning Algorithm Result

Stentiford’preprcessing and Zhang-Suen’Algorithm, with Holt’s staircase removal Result

원 지문 Zhang의 세선화 <지문에 응용 결과> Stentiford’ reprocessing + Zhang Algorithm + Holt’ staircase removal 원 지문 Zhang의 세선화