[논문]보로노이 다이어그램에 기반한 개선된 유클리디언 거리 변환 방법

장석환; 박용섭; 김회율

보로노이 다이어그램에 기반한 개선된 유클리디언 거리 변환 방법
Improved Euclidean transform method using Voronoi diagram 원문보기

한국통신학회논문지. The Journal of Korea Information and Communications Society. 통신이론 및 시스템, v.29 no.12C, 2004년, pp.1686 - 1691

장석환 (한양대학교 전자전기컴퓨터 공학부 영상공학 연구실) , 박용섭 (씨멘스 메디칼 초음파 연구소) , 김회율 (한양대학교 전자전기컴퓨터 공학부)

초록
AI-Helper

본 논문에서는 기존의 고속 유클리디언 거리 변환법을 개선한 새로운 계산 방법을 제안한다. 기존의 고속 유클리디언 거리 변환법이 가지고 있는 단점인 특징점의 수에 비례하여 계산량이 늘어나는 단점을 극복하기 위해서, 본 논문에서는 특징점들 중에서 비특징점과 4방향으로 연결되어 있는 특징점만을 이용하여 보로노이 다이어그램을 계산함으로써 유클리디언 거리 변화도(Euclidean distance map)의 계산 시간을 기존의 방법보다 평균 40%로 감소시켰다. 본 논문에서 제안한 방법의 효율성을 검증하기 위해서 크기의 바이너리 영상 16장에서 대해서 기존의 방법과 제안한 방법으로 똑같이 유클리디언 거리 변화도를 계산하여 계산 시간을 비교함으로써 그 효능을 입증하였다.

Abstract ▼ AI-Helper

In this paper, we present an improved method to calculate Euclidean distance transform based on Guan's method. Compared to the conventional method, Euclidean distance can be computed faster using Guan's method when the number of feature pixels is small; however, overall computational cost increases proportional to the number of feature pixels in an image. To overcome this problem, we divide feature pixels into two groups: boundary feature pixels (BFPs) and non-boundary feature pixels (NFPs). Here BFPs are defined as those in the 4-neighborhood of foreground pixels. Then, only BFPs are used to calculate the Voronoi diagram resulting in a Euclidean distance map. Experimental results indicate that the proposed method takes 40 Percent less computing time on average than Guan's method. To prove the performance of the proposed method, the computing time of Euclidean distance map by proposed method is compared with the computing time of Guan's method in 16 images that are binary and the size of 512${\times}$512.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서 제안한 고속 알고리즘은 Guan의 방법 을 기반으로 하고 있기 때문에 Guan의 방법에 대해 서 간단하게 설명하겠다. Guan방법의 특징은 비특징 점으로부터 가장 가까운 특징점까지의 거리를 계산하 는 기본단위로서 픽셀이 아닌 1차원 분할 정보를 이 용했다는 것이다.
본 논문에서는 Guan의 방법을 개량하여 특징점의 수가 적은 영상뿐 아니라 특징점 수가 많은 영상에 대해서도 효율적으로 유클리디언 거리를 계산할 수 있는 새로운 방법을 제안한다. 제안한 방법은 모든 특징점들 중에서 유클리디언 거리를 계산하는데 영향 을 미치는 특징점 만을 이용해서 보로노이 다이어그 램을 계산한다.
본 논문에서는 유클리디언 거리 변환도를 빠르게 계산하기 위해서 Guan의 분할 리스트(segment list)를 이용한 보로노이 변환 알고리즘을 개량한 새로운 알 고리즘을 제안하였다.

가설 설정

1. BFP: 특정한 특징점을 중심으로 4-이웃한 점들 중 에서 적어도 한 점은 비특징점인 경우.
1. 모든 특징점을 BFP와 NFP로 분류 한다.

제안 방법

2. BFP만을 이용하여 Guan이 제안한 방법으로 보로 노이 다이어그램을 계산한다.
(g) 위쪽에서 아래쪽 으로 (top-down scanning) 확산 및 병합을 끝낸 최종 결과 그림에서 각각의 점은 특징점들을 나타내며, 초 기 특징점을 기준으로 1차원 보로노이 다이어그램을 계산한 후, 1차원 보로노이 다이어그램의 세그먼트를 위/아래 방향으로 확산시켜서 2차원 보로노이 다이어 그램을 계산하는 방법을 보여준다. 2차원 보로노이 다 이어그램을 계산한 후 이를 이용해서 유클리디언 거리 변화도를 계산한다.
3. 계산된 보로노이 다이어램을 이용하여 비특징점 들에 대하여 유클리디언 거리를 계산한다.
그러므로 본 논문에서는 아래와 같은 알고리즘을 사 용하여 불필요한 계산을 없앰으로써, 고속으로 유클리 디언 거리를 계산하는 방법을 제안한다
다시 말해, 보로노이 다이어그램을 고속으로 계산 하기 위해서 1차원 보로노이 다이어그램을 먼저 계산 한 후에 1차원 보로노이 다이어그램을 위-아래 방향 과 아래-위 방향으로 확산 및 병합시킴으로써 2차원 보로노이 다이어그램을 고속으로 계산하였다 . 그러나 Guan 방법의 복잡도는 특징점의 숫자에 비례해서 증 가였으며, 0(/兌詠)이었다[12].
보다 정확한 성능 평가를 위해서 다양한 형태의 이 진 영상들에 대헤서 기존의 방법과 본 논문에서 제안 한 방법을 이용하여 유클리디언 거리 변환도를 생성 하는 실험을 수행 하였다. 두 방법의 성능을 비교하 기 위해, 각각의 방법에 의해 생성되는 세그먼트의 개수와 계산 시간을 측정하였다. 실험 영상은 임의로 생성한 영상과 Nova사의 Art Explosion 250, 000에서 발취한 영상을 사용하였다 C++ 언어를 사용하여 알 고리즘을 구현 흐}였고 Intel P4 2.
보다 정확한 성능 평가를 위해서 다양한 형태의 이 진 영상들에 대헤서 기존의 방법과 본 논문에서 제안 한 방법을 이용하여 유클리디언 거리 변환도를 생성 하는 실험을 수행 하였다. 두 방법의 성능을 비교하 기 위해, 각각의 방법에 의해 생성되는 세그먼트의 개수와 계산 시간을 측정하였다.
본 논문에서는 유클리디언 거리를 계산하기 위해서 모든 특징점을 이용해서 보로노이 다이어그램을 계산 하지 않고 유클리디언 거리를 계산하는데 영향을 미 치는 특징점만을 이용해서 보로노이 다이어그램을 계 산하였다. 유클리디언 거리를 계산하는데 영향을 미치 는 특징점을 BFP(boundary feature pixel) 라 정의하고 그렇지 않은 경우를 NFP (non-boundary feature pixel)라 정의한다.
제안한 방법은 모든 특징점들 중에서 유클리디언 거리를 계산하는데 영향 을 미치는 특징점 만을 이용해서 보로노이 다이어그 램을 계산한다. 제안한 계산 방법은 최악의 경우 - 그림 2와 같이 각각의 객체가 한 개의 특징점으로 구 성된 경우 - Guan의 방법과 똑 같은 복잡도를 갖는 다. 그러나 하나의 객체가 여러 개의 특징점으로 구 성된 경우 BFP의 숫자가 특징점의 숫자보다 둘레/면 적의 비율로 감소하기 때문에 계산 복잡도가 현저하 게 감소한다.
본 논문에서는 Guan의 방법을 개량하여 특징점의 수가 적은 영상뿐 아니라 특징점 수가 많은 영상에 대해서도 효율적으로 유클리디언 거리를 계산할 수 있는 새로운 방법을 제안한다. 제안한 방법은 모든 특징점들 중에서 유클리디언 거리를 계산하는데 영향 을 미치는 특징점 만을 이용해서 보로노이 다이어그 램을 계산한다. 제안한 계산 방법은 최악의 경우 - 그림 2와 같이 각각의 객체가 한 개의 특징점으로 구 성된 경우 - Guan의 방법과 똑 같은 복잡도를 갖는 다.

대상 데이터

두 방법의 성능을 비교하 기 위해, 각각의 방법에 의해 생성되는 세그먼트의 개수와 계산 시간을 측정하였다. 실험 영상은 임의로 생성한 영상과 Nova사의 Art Explosion 250, 000에서 발취한 영상을 사용하였다 C++ 언어를 사용하여 알 고리즘을 구현 흐}였고 Intel P4 2.4G (DDR 512M) 에서 실험을 수행하였다.
실험은 인위적으로 생성한 패턴 영상과 Art Explosion 250, 000에 포함된 크기의 16장의 영상을 이용하여 실험을 수행하였다. 실험결과 본 논문에서 제안한 계산 방법을 이용하였을 때, 기존의 방법보다 분할 개수는 절반으로 감소하였고 전체 계산 시간은 평균 40%로 감소하였다

데이터처리

먼저 제안한 방법의 효율성을 검증하기 위해서 Guan의 논문에서 실험에 사용된 그림 6-a를 이용해 서 실험하였다[13]. 그림 6-a에 대해서 기존의 방법을 이용해서 2차원 보로노이 다이어그램을 생성하기 위 해서는 70, 932개의 1차원 분할이 필요하다.

성능/효과

(b) BFPs. (c) BFP를 이용해서 계산한 유클리디언 거리 변환도 Guan이 유클리디언 거리를 계산 하기 위해서 논문에서 인용한 그림을 이용하여 계산한 유클리디언 거리 변환도 Guan의 방법처럼 모든 특징 점을 이용해서 계산한 유클리디언 거리 변화도와 BFF 를 이용해서 계산한 유클리디언 거리 변환도가 똑 같 음을 보여준다.
그러나 Guan의 방법은 특징점의 수가 적은 경우에 는 효과적이지만, 특징점의 수가 증가할수록 계산 효 율이 떨어지는 단점이 있었다. 대부분의 이진 영상은 특징점을 많이 포함하고 있기 때문에 Guan의 방법을 일반 영상에 적용하기 위해서는 좀 더 효율적인 계산 방법이 필요하다.
기존의 Guan의 방법에서는 입력 영상에 존재하는 모든 특징점을 사용하여 보로노이 다이어그램을 계산 하기 때문에 전체 계산량이 특징점에 숫자에 비례하 여 증가하는 반면에 본 논문에서 제안한 방법은 유클 리디언 거리에 영향을 미치는 특징점만을 이용하여 보로노이 다이어그램을 계산하였기 때문에 계산량을 현저하게 감소시킬 수 있었다. 최상의 경우 본 논문 에서 제안한 방법이 기존의 방법에 비해서 90%이상 계산량을 감소시켰으며, 최악의 경우(그림 2-(a)와 같 은 경우) 기존의 방법과 똑 같은 계산량을 나타냈다.
그림 6-a에 대해서 기존의 방법을 이용해서 2차원 보로노이 다이어그램을 생성하기 위 해서는 70, 932개의 1차원 분할이 필요하다. 반면에 본 논문에서 제안한 BFP를 이용해서 2차원 보로노이 다이어그램을 생성하면 1차원 분할의 개수가 48, 831 로 줄어든다. 초기 특징점의 숫자가 줄어들었기 때문 에 그림 6-a의 유클리디언 거리 변환도를 계산하기 위한 전체 계산량은 69% 줄어들었다.
본 논문에서 제안한 BFP를 이용해서 1차원 보로노 이 다이어그램을 계산하면 전체 보로노이 영역의 개 수는 특징점들이 이루는 객체의 둘레/면적의 비율로 감소하였으며 결과적으로 전체 복잡도는 0(寸切袞) 에서 冨丽로 감소하였다. 여기서 /는 BFP의 개수이다.
(c) 본 논문에서 제안한 BFP. 본 논문에서는 비특징점과 4-이웃한 특징 점만을 추출하여 이를 BFP라 정의하고 BFP를 이용 해서 계산한 유클리디언 거리 변환도와 모든 특징점을 이용해서 계산한 유클리디언 거리 변환도가 똑 같음을 보였다.
실험은 인위적으로 생성한 패턴 영상과 Art Explosion 250, 000에 포함된 크기의 16장의 영상을 이용하여 실험을 수행하였다. 실험결과 본 논문에서 제안한 계산 방법을 이용하였을 때, 기존의 방법보다 분할 개수는 절반으로 감소하였고 전체 계산 시간은 평균 40%로 감소하였다
기존의 Guan의 방법에서는 입력 영상에 존재하는 모든 특징점을 사용하여 보로노이 다이어그램을 계산 하기 때문에 전체 계산량이 특징점에 숫자에 비례하 여 증가하는 반면에 본 논문에서 제안한 방법은 유클 리디언 거리에 영향을 미치는 특징점만을 이용하여 보로노이 다이어그램을 계산하였기 때문에 계산량을 현저하게 감소시킬 수 있었다. 최상의 경우 본 논문 에서 제안한 방법이 기존의 방법에 비해서 90%이상 계산량을 감소시켰으며, 최악의 경우(그림 2-(a)와 같 은 경우) 기존의 방법과 똑 같은 계산량을 나타냈다.
여기서, 계산 시 간은 보로노이 다이어그램을 이용하여 유클리디언 거 리 변환도를 구하는 데 소요된 전체 계산 시간을 나 타낸다. 특징점의 분포에 따라 차이가 있으나 전반적 으로 본 논문에서 제안한 방법의 분할 개수와 계산시 간이 크게 감소했음을 알 수 있다. 그러나 그림 7-h 의 실험결과에서 알 수 있듯이 BFP들이 수평 방향으 로 연결되어 있는 경우 BFP의 1차원 보로노이 다이 어그램을 확산병합 시켜서 2차원 보로노이 다이어그 램을 계산했을 때 모든 특징점을 이용해서 보로노이 다이어그램을 계산한 것과 분할 개수와 계산 시간이 같아진다.

참고문헌 (13)

G. Borgefors, 'Distance Transformations in Digital Images,' Computer Graphics and Image Processing, vol. 34, pp. 344-371, 1986

상세보기
D. W. Paglieroni, 'Distance Transforms,' Computer Vision, Graphics, and Image Processing: Graphical Models and Image Processing, vol. 54, pp. 56-74, 1992
J. M. Fitzpatrick, D. L. G. Hill, and C. R. Maurer, Jr., 'Image Registration', Handbook of Medical Imaging, vol. 2, pp. 447-513, SPIP Press, 2000
Y. Ge, C. R. Maurer, Jr., and J. M. Fitzpatrick, 'Surface-Based 3-D Image Registration Using the Iterative Closest Point Algorithm with a Closest Point Transform,' Medical Imaging: Image Processing, vol2710, pp.358-367, 1996
P. P. Das and P. P Chakrabarti, 'Distance functionsin digital geometry,' Information Sciences, vol. 42, pp. 113-136, 1987

상세보기
M. Yamashita and T. Ibaraki, 'Distances defined by neighborhood sequences,' Pattern Recognition, vol. 19, pp. 237-246, 1986

상세보기
I. Ragnemalm, The Euclidean Distance Transform, Ph.D. Thesis, Linkoping University, Linkoping, Sweden, 1993
L. Ji and J. Piper, 'Fast Homotopy-Preserving Skeletons Using Mathematical Morphology,' IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.14, no.6, pp.653-664, 1992

상세보기
U. Montanari, 'A Method for Obtaining Skeletons Using A Quasi-Euclidean Distance,' Journal of ACM, vol.15, no.4, pp.600-624, 1968

상세보기
C. L. Orbert, Algorithms in 2D for Detection of Object Orientation Using Distance Transformations, Ph.D. Thesis, Uppsala University, 1993
F. Aurenhammer, 'Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure,' ACM Computing Surves, vol.23, no.3, pp.345-405, 1991

상세보기
W. Guan, and S. Ma, 'A list-processing approach to compute Voronoi diagrams and the Euclidean distance transform,' IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.20, no.7, pp.757-761, 1998

상세보기
김덕욱, 김덕수, 조동수, Kokichi Sugihara, '점집합의 보로노이 다이어그램을 이용한 원 집합이 보로노이 다이어그램의 계산. I. 위상학적측면', 한국 CAD/CAM 학회 논문집, 제 6권 제 1호, pp.24-30, 2001

원문보기 상세보기

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증