계층적 자료구조인 사진트리는 영상을 표현하는데 매우 중요한 자료구조이다. 사진트리를 메모리에 저장하는 방법 중 선형 사진트리 표현 방법은 다른 표현 방법과 비교할 때 저장 공간을 매우 효율적으로 절약할 수 있는 이점이 있기 때문에 사진트리와 관련된 연산의 수행을 위해 선형 사진트리를 사용하는 효율적인 알고리즘 개발에 많은 연구가 진행되어 왔다. 블록위치 계산은 영상에서부터 주어진 블록을 완전히 포함하는 컴포넌트를 추출하는 연산으로, 영상 처리의 응용에서 중요하게 사용되는 기하학적 연산에 속한다. 본 논문에서는 RMESH(Reconfigurable MESH) 구조에서 3-차원 $n imes n imes n$ 프로세서를 사용하여 선형 사진트리로 표현된 영상의 블록위치를 계산하는 상수시간 알고리즘을 제안한다. 이 알고리즘은 $n imes n imes n$ RMESH의 계층구조에서 선형 사진트리의 위치코드들을 효율적으로 처리하는 기본적인 연산들을 이용함으로써 상수시간의 시간복잡도를 갖는다.
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 with quadtrees. The computation of block location is one of important geometry operations in image processing, which extracts a component completely including a given block. In this paper, we present a constant time algorithm to compute the block location of images represented by quadtrees, using three-dimensional $n imes n imes n$ processors on RMESH(Reconfigurable MESH). This algorithm has constant-time complexity by using efficient basic operations to deal with the locational codes of quardtree on the hierarchical structure of $n imes n imes n$ RMESH.
