RMESH 구조에서 선형 사진트리의 영역 확장과 스케일링을 위한 상수시간 알고리즘
Constant Time Algorithms for Region Expansion and Scaling of Linear Quadtrees on RMESH
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
계층적 자료구조인 사진트리는 영상을 표현하는데 매우 중요한 자료구조이다. 사진트리를 메모리에 저장하는 방법 중 선형 사진트리 표현 방법은 다른 표현 방법과 비교할 때 저장 공간을 매우 효율적으로 절약할 수 있는 이점이 있기 때문에 사진트리와 관련된 연산의 수행을 위해 선형 사진트리를 사용하는 효율적인 알고리즘 개발에 많은 연구가 진행되어 왔다. 영역 확장은 영상을 주어진 거리만큼 확장시키는 연산이고, 스케일링은 영상을 주어진 크기만큼 증폭시키는 연산으로 영상의 기하학적 연산에 속한다. 본 논문에서는 RMESH(Reconfigurable MESH) 구조에서 3-차원 프로세서를 사용하여 선형 사진트리로 표현된 영상의 영역 확장과 스케일링을 수행하는 효율적인 알고리즘을 제안한다. 이 알고리즘은 RMESH의 계층구조에서 선형 사진트리의 위치코드들을 효율적으로 전송할 수 있는 기본적인 연산들을 이용함으로써 상수 시간의 시간복잡도를 갖는다.
Abstract
Quadtree, which is a hierarchical data structure, is a very important data structure to represent images. The linear quadtree representation as a way to store a quadtree is efficient to save space compared with other representations. Therefore, it has been widely studied to develop efficient algorithms to execute operations related to quadtrees. The region expansion is an operation to expand images by a given distance and the scaling is an operation to scale images by a given scale factor. In this paper, we present algorithms to perform the region expansion and scaling of images represented by quadtrees, using three-dimensional n times n times n
참고문헌 (16)
- "Application of Spatial Data Structures" (1990)
- "The Design and Analysis of Spatial Data Structures" (1990)
- I. Gargantini, "and superposition of linear quadtrees International Journal of Man-Machine Studies", 18(3), pp.253~263 (1985)
- "Efficient axis-trnaslation of binary digital pictures by blocks in linear quadtree representation", 41(3), pp.282~292 (1988)
- "재구성가능 매쉬에서 Omicron 1 시간 복잡도를 갖는 이진영상 사진트리 변환 알고리즘", 제23-A권(제5호), pp.454~466 (1996)
- "RMESH 구조에서의 선형 사진트리 구축을 위한 상수 시간 알고리즘", 제4권(제9호), pp.2247~2258 (1997)
- "RMESH 구조에서 선형 사진트리의 윈도우 연산을 위한 상수시간 알고리즘", 제29권(제3 ,4호), pp.134~142 (2002)
- R. Miller,V. Prasanna-Kumar,D. Reisis, "Parallel Computation on Reconfigurable Meshes", 42(6), pp.678~692 (1993)
- "Reconfigurable Mesh Algorithms for The Hough Transform", ⅲ, pp.34~41 (1991)
- "구멍이 있는 다각형에서 가시성 다각형을 구하는 상수 시간 RMESH 알고리즘" (2000)
- "단순다각형의 내부점 가시도를 위한 효율적인 RMESH 알고리즘", 20(11), pp.1693~1701 (1993)
- "A Fast Algorithm for Computing Histogram on a Reconfigurable Mesh", 17(2), pp.97~106 (1995)
- "The Power of Reconfiguration", pp.139~153 (1991)
- J. Jang, "An Optimal Sorting Algorithm on Reconfigurable Meshes" (1992)
- M. Nigam, "Sorting n Numbers On n times n Reconfigurable Meshes With Buses", pp.174~181 (1993)
- Sanjay Ranka, "Hypercube algorithms with applications to image processing and pattern recognition 1989년 미국 University of Minnesota 전산학과 1980년-1983년 대한항공 및 국토개발연구원 전산실 근무1989년-현재 단국대학교 정보컴퓨터학부 교수관심분야：알고리즘 및 병렬알고리즘", Springer-Verlag