동적 프로그래밍에 기반한 윤곽선 근사화를 위한 정점 선택 방법 = Vertex Selection Scheme for Shape Approximation Based on Dynamic Programming

다국어 초록 (Multilingual Abstract)

This paper presents a new vertex selection scheme for shape approximation. In the proposed method, final vertex points are determined by "two-step procedure". In the first step, initial vertices are simply selected on the contour, which constitute a subset of the original contour, using conventional methods such as an iterated refinement method (IRM) or a progressive vertex selection (PVS) method. In the second step, a vertex adjustment process is incorporated to generate final vertices which are no more confined to the contour and optimal in the view of the given distortion measure. For the optimality of the final vertices, the dynamic programming (DP)-based solution for the adjustment of vertices is proposed. There are two main contributions of this work. First, we show that DP can be successfully applied to vertex adjustment. Second, by using DP, the global optimality in the vertex selection can be achieved without iterative processes. Experimental results are presented to show the superiority of our method over the traditional methods.

국문 초록 (Abstract)

본 논문은 다각형 기반 윤곽선 근사화를 위한 새로운 정점 선택 방법을 제안한다. 제안된 방법은 초기 정점 선택 단계와 정점 조절 단계로 구성된다. 먼저 기존의 순환적인 정점 선택 기법(Iterative Refinement Method: IRM) 또는 순차적인 정점 선택 기법(Progressive Vertex Selection: PVS)을 사용하여 초기 정점이 윤곽선상에 놓이도록 초기 정점을 선택한다. 이렇게 선택된 초기 정점은 원 윤곽선의 부분 집합을 구성하게 된다. 두번째 단계에서 정점 조절 과정을 수행하게 되는데, 최종 정점의 위치를 윤곽선상으로 국한하지 않고, 주어진 왜곡 척도하에서 최적인 정점들을 얻는다. 이때 전역적인 관점에서 최적인 최종 정점들을 얻기 위하여 동적 프로그래밍을 사용한다. 제안된 방법은 동적 프로그래밍을 사용함으로써 반복적인 과정없이 전역적 관점에서 최적인 정점들을 선택할 수 있다. 실험결과, 제안된 방법이 기존의 방법들보다 우수한 성능을 나타내었다.

참고문헌 (Reference)

1 "Us ing dynamic programmingfor solving variational problems in vision IEEE Transactions on Pat tern Analysis and Machine Intelligence" 1990

2 "Tracking visible boundary of object using occlu sion adaptive motion snake" 9 (9): 2051-2060, Dec.2000

3 "Shape information reduction based on contour prediction and shape coding type" (v) : Nov.1995

4 "Region shape coding" (v) : Nov.1995

5 "Object-adaptive vertex-based shape coding method" 7 (7): 251-255, Feb.1997

6 "Microsoft proposal for MPEG4" Nov.1995

7 "MPEG-4 and Rate-Distortion-Based Shape-Coding Technique s" 86 (86): 1126-1154, June1998

8 "MPEG-4 Video Veri fication Model (VM) version 1.0" -1, Jan.1996

9 "Fundamentals of Digital Image Proces sing" Prentice-Hall INC 1989

10 "Description of core experi ments on shape coding in MPEG-4 video" July1996

11 "Daewoo pro posal for object scalability" Jan.1996

12 "Context -based arithmetic encode of 2D shape sequences" -97, 1997

13 "An iterative procedure for the polygon approximation of planar curves" 244-256,

14 "An efficient tech nique for compressing chain-coded line drawing images" in Conf 717-720, 1992

15 "A binary shape coding method using modified MMR" -97, 1997