쿼드트리: 이미지 분석을 위한 계층적 데이터 구조 탐색

By Fouad Sabry

쿼드트리란 무엇입니까

쿼드트리는 각 내부 노드가 정확히 4개의 하위 노드를 갖는 트리 데이터 구조입니다. 쿼드트리는 옥트리의 2차원 아날로그이며 2차원 공간을 4개의 사분면 또는 영역으로 재귀적으로 세분화하여 분할하는 데 가장 자주 사용됩니다. 리프 셀과 연관된 데이터는 애플리케이션에 따라 다르지만 리프 셀은 "흥미로운 공간 정보의 단위"를 나타냅니다.

혜택을 받는 방법

(I) 다음 주제에 대한 통찰력 및 검증:

1장: 쿼드트리

2장: 옥트리

3장: R-트리

4장: 이진 트리

5장: B-트리

6장: AVL 트리

7장: 레드-블랙 트리

8장: 이진 검색 트리

9장: 바이너리 힙

10장: 세그먼트 트리

(II) 쿼드트리에 관한 대중의 주요 질문에 답변합니다.

(III) 다양한 분야에서 쿼드트리를 사용하는 실제 사례

이 책은 누구를 위한 책인가요?

전문가, 학부 및 대학원생, 열성팬, 취미생활자, 모든 종류의 Quadtree에 대한 기본 지식이나 정보를 넘어서고 싶은 사람들.

 

• Language: 한국어
• Publisher: 10 억 지식이 걸립니다 [Korean]
• Release date: May 14, 2024

Book preview

챕터 1: 쿼드트리

쿼드트리의 데이터 구조는 각 내부 노드에 정확히 4개의 자손이 있는 트리입니다. 쿼드트리는 octree와 동일한 2차원이며 일반적으로 2차원 공간을 4개의 사분면 또는 섹션으로 분할하는 데 사용됩니다. 리프 셀과 관련된 정보는 응용 프로그램에 따라 다르지만 리프 셀은 흥미로운 공간 정보의 단위입니다.

분할된 영역은 임의 또는 정사각형 또는 직사각형 모양을 가질 수 있습니다. 1974년에는 Raphael Finkel과 J.L. Bentley가 이 데이터 구조를 쿼드트리로 지정했습니다. Q-트리는 유사한 파티션 체계의 또 다른 용어입니다. 모든 유형의 쿼드 트리에는 특정 특성이 있습니다.

그들은 공간을 유연한 세포로 나눕니다.

각 구획(또는 콘센트)에는 최대 용량이 있습니다. 버킷의 최대 용량에 도달하면 분리됩니다.

트리 디렉터리는 quadtree의 공간 분해를 따릅니다.

트리 피라미드 (T- 피라미드)는 완전한트리입니다. T-피라미드의 모든 노드에는 리프 노드를 제외한 4개의 하위 노드가 포함됩니다. 모든 나뭇잎은 그림의 개별 픽셀에 해당하는 동일한 수준에 있습니다. 완전한 이진 트리를 배열에 압축적으로 저장할 수 있는 방법과 유사하게 트리 피라미드 데이터는 암시적 데이터 구조로 배열에 압축적으로 저장할 수 있습니다.

Quadtree는 영역, 점, 선 및 곡선과 같이 나타내는 데이터 유형에 따라 분류할 수 있습니다. Quadtree는 트리의 모양이 처리 순서와 무관한지 여부에 따라 분류할 수도 있습니다. 다음은 quadtrees:의 빈번한 형태입니다.

영역 쿼드트리는 영역을 4개의 동일한 사분면, 하위 사분면 등으로 분해하여 공간의 2차원 분할을 보여주며, 각 리프 노드는 특정 하위 영역과 관련된 데이터를 전달합니다. 트리의 각 노드에는 정확히 4개의 자식이 있거나 하나도 없습니다(리프 노드). 이 분해 방법(즉, 더 큰 미세 조정이 필요한 하위 사분면에 관련 데이터가 있는 한 하위 사분면을 세분화)은 쿼드트리의 높이를 분해되는 공간에서 관심 있는 영역의 공간 분포에 민감하고 의존하게 만듭니다. region quadtree는 trie 데이터 구조체의 변형입니다.

깊이가 n인 영역 쿼드트리는 모든 픽셀이 0 또는 1인 2n × 2n 픽셀로 구성된 이미지를 나타내는 데 사용할 수 있습니다.

루트 노드는 이미지 영역의 전체를 나타냅니다.

임의의 영역 내의 픽셀이 완전히 0 또는 1이 아닌 경우, 해당 영역은 유효하지 않은 것으로 간주되어 분할된다.

이것은 응용 프로그램이며, 각 리프 노드는 전적으로 0 또는 1로 구성된 픽셀 블록을 나타냅니다.

이러한 트리를 이미지 저장에 사용할 때 가능한 공간 절약에 유의하십시오. 시각적 묘사의 일반적인 특징은 전체적으로 동일한 색상 값을 가진 수많은 넓은 영역이 존재한다는 것입니다.

이미지의 모든 픽셀로 구성된 큰 2차원 배열을 저장하는 대신 더 작은 배열이 사용되며, 쿼드트리는 픽셀 해상도 크기의 셀보다 훨씬 더 많은 분할 수준에서 동일한 정보를 캡처할 수 있습니다.

트리의 해상도와 크기는 픽셀과 그림 크기에 의해 제한됩니다.

영역 쿼드트리는 변경 가능한 해상도로 데이터 필드를 나타내는 데 사용할 수도 있습니다. 예를 들어, 쿼드트리를 사용하여 지역의 온도를 기록할 수 있으며, 각 리프 노드는 해당 하위 지역의 평균 온도를 저장합니다.

점 쿼드트리

다음은 포인트 쿼드트리가 구축되는 방식입니다. 삽입할 다음 점이 주어지면 해당 셀이 배치되고 점이 트리에 추가됩니다. 새 점이 삽입되어 해당 점을 포함하는 셀이 통과하는 수직선과 수평선에 의해 사분면으로 분할됩니다. 따라서 셀은 직사각형이지만 항상 정사각형은 아닙니다. 이러한 트리의 각 노드에는 입력 지점 중 하나가 있습니다.

평면의 분할은 점 삽입 순서에 따라 결정되기 때문에 트리의 높이는 민감하며 삽입 순서에 따라 달라집니다. 잘못된순서로 삽입하면 높이가 입력 포인트 수에 비례하는 트리가 생성 될 수 있습니다 (이 시점에서 링크 된 목록이됩니다). 전처리는 점 집합이 정적인 경우 균형 잡힌 높이를 가진 트리를 생성하는 데 사용할 수 있습니다.

포인트 쿼드 트리의 노드는 이진 트리의 노드와 유사하며, 주요 차이점은 기존의 이진 트리와 같이 2 개 ( 왼쪽및 오른쪽)와 달리 4 개의 포인터 (각 사분면에 대해 하나씩)가 있다는 것입니다. 또한 키는 일반적으로 x 및 y 좌표를 참조하는 두 개의 구성 요소로 나뉩니다. 따라서 노드에는 다음 데이터가 포함됩니다.

4개 포인터: quad['NW'], quad['NE'], quad['SW'], quad['SE']

점; 여기에는 차례로 다음이 포함됩니다.

식별자; 일반적으로 x, y 좌표로 표시됩니다.

값(예: 이름)

점-지역(PR) 쿼드트리는 영역 쿼드트리와 매우 유사합니다. 차이점은 저장된 셀 관련 데이터의 유형에 있습니다. 영역 쿼드트리에서는 리프 셀의 전체 영역에 적용되는 값이 유지됩니다. 그러나 PR 쿼드트리의 셀에는 리프 셀 내에 있는 점 목록이 있습니다. 앞서 언급했듯이 이 분해 접근 방식을 사용하는 나무의 높이는 점의 공간 분포에 따라 달라집니다. 점 쿼드트리와 유사하게, PR 쿼드트리는 나쁜 집합이 제공될 때 선형 높이를 가질 수 있습니다.

Edge quadtree(PM quadtree와 유사)는 점이 아닌 선을 유지하는 데 사용됩니다. 세포는 곡선을 근사화하기 위해 매우 미세한 해상도로 세분화되며, 셀당 단일 선분이 있을 때까지 정확하게 세분화됩니다. 가장자리 쿼드트리는 모서리/정점 근처에서 최대 분해 수준에 도달할 때까지 계속 분할됩니다. 이로 인해 인덱싱 목표를 무효화하는 심각한 불균형 트리가 발생할 수 있습니다.

다각형 맵 quadtree(또는 PM Quadtree)는 잠재적으로 퇴화될 수 있는 다각형 그룹(즉, 고립된 꼭짓점 또는 가장자리가 있음)을 보유하는 데 사용되는 quadtree의 변형입니다. PM 쿼드트리와 에지 쿼드트리의 중요한 차이점은 셀 내의 세그먼트가 꼭짓점에서 교차하는 경우 검사 중인 셀이 분할되지 않는다는 것입니다.

PM 쿼드트리에는 세 가지 기본 종류가 있으며, 각 블랙 노드에 저장된 데이터에 따라 다릅니다. PM3 쿼드 트리는 임의의 수의 교차하지 않는 가장자리와 최대 단일 점을 보유 할 수 있습니다. PM2 쿼드트리는 모든 모서리가 동일한 위치에서 종료되어야 한다는 점을 제외하고는 PM3 쿼드트리와 동일합니다. PM1 쿼드트리는 PM2 쿼드트리와 유사하지만 검은색 노드에는 점과 해당 가장자리 또는 점을 공유하는 가장자리 집합만 포함될 수 있지만 점을 포함하지 않는 점과 가장자리 집합은 허용되지 않습니다.

이 섹션은 Sariel Har-book의 한 챕터를 요약합니다. 펠레드.

세분화된 셀에 해당하는 모든 노드를 저장해야 하는 경우 저장 필요성이 엄청날 수 있으며 상당한 수의 빈 노드를 저장하게 될 수 있습니다.

이러한 희소 나무의 크기를 줄이려면 잎에 흥미로운 데이터가 포함된 하위 트리만 저장할 수 있습니다(즉,

중요한 하위 분기).

실제로 크기를 훨씬 더 줄일 수 있습니다.

필수 하위 트리만 유지하는 경우 가지치기 절차는 2차 중간 노드(한 부모와 한 자식에 대한 링크)가 있는 트리에 긴 경로를 남길 수 있습니다.

이 경로의 시작 부분에 노드를 저장하고 제거된 노드를 나타내기 위해 일부 메타데이터를 연결하고, 끝에 뿌리를 둔 하위 트리 u 를 에 연결하기만 하면 됩니다 u .

나쁜 입력 지점이 주어지면 그럼에도 불구하고 이러한 압축된 트리가 선형 높이를 가질 수 있습니다.

이 압축 중에 상당한 양의 트리가 정리되지만 Z 순서 곡선을 사용하여 로그 시간 검색, 삽입 및 삭제가 여전히 가능합니다.

Z 순서 곡선은 전체 쿼드트리(따라서 압축된 쿼드트리)의 각 셀 을 O(1) 시간적으로 1차원 선에 매핑하고(시간적으로도 다시 매핑 O(1) ) 요소에 대한 완전한 순서를 설정합니다.

따라서 쿼드트리를 정렬된 집합 데이터 구조(트리의 노드를 저장하는 구조)에 저장할 수 있습니다.

계속하기 전에 합리적인 가정을 진술해야 합니다: 이진수로 표현된 두 개의 실수가 주어졌 을 때, {\displaystyle \alpha ,\beta \in [0,1)} 서로 다른 첫 번째 비트의 인덱스를 시간에 O(1) 따라 계산할 수 있다고 가정합니다.

또한 O(1) 쿼드트리에 있는 두 점/셀의 가장 낮은 공통 조상을 시간에 계산하고 상대 적인 Z 순서를 설정할 수 있다고 가정하고 시간에 따라 바닥 함수를 계산할 수 있습니다 O(1) .

이러한 전제에서 주어진 지점의 지점 위치 q (즉,

), 삽입 및 삭제 작업을 포함하는 셀을 결정하는 q 것은 모두 시간 내에 수행될 수 있습니다 O(\log {n}) (즉,

기본 정렬된 집합 데이터 구조 내에서 검색을 수행하는 데 필요한 시간).

에 대한 점 위치를 수행하려면 q (즉,

압축된 트리에서 해당 셀 찾기):

압축된 트리에서 Z 순서로 앞에 오는 기존 셀 q 을 찾습니다.

이 셀을 . v

만약에 {\displaystyle q\in v} , 를 반환합니다 v .

그렇지 않으면 압축되지 않은 쿼드 트리에서 점 q 과 셀의 v 가장 낮은 공통 조상이 될 수있는 것을 찾으십시오.

이 조상 셀을 라고 합니다 u .

압축된 트리에서 Z 순서로 앞에 오는 기존 셀을 찾아 u 반환합니다.

세부 사항을 파고들지 않고 삽입 및 삭제를 수행하려면 먼저 삽입 또는 삭제할 항목에 대한 점 배치를 수행한 다음 삽입하거나 제거합니다. 노드를 추가하거나 제거하여 필요에 따라 트리의 모양을 변경하도록 주의해야 합니다.

이미지 표현

Bitmap and its compressed quadtree representation

이미지 처리

메쉬 생성

공간 인덱싱, 포인트 기반 및 범위 기반 검색

2차원 충돌 감지 효율

지형에 대한 데이터 절두체 컬링 보기

희소 데이터 저장소(예: 스프레드시트 또는 행렬 계산을 위한 형식 정보)

다차원장 솔루션(전산 유체 역학, 전자기학)

Conway의 Game of Life 시뮬레이션 프로그램.

상태 추정

Quadtree는 프랙탈 사진 분석에도 활용됩니다.

최대 분리 세트

쿼드트리, 즉 영역 쿼드트리는 이미지 처리의 응용 분야에 잘 적응했습니다. 영역 쿼드트리와 쿼드트리에서 수행되는 이미지 처리 절차는 컬러 이미지에도 동일하게 적용할 수 있지만, 여기서는 이진 이미지 데이터로 논의를 제한하겠습니다.

사진 처리를 위해 쿼드 트리를 사용하는 이점은 합집합 및 교차와 같은 집합 연산을 빠르고 쉽게 수행 할 수 있다는 것입니다. 두 개의 이진 영상이 주어졌을 때, 이미지 합집합(오버레이라고도 함)은 입력 영상 중 하나가 같은 위치에 검은색 픽셀을 포함하는 경우 픽셀이 검은색인 이미지를 생성합니다. 즉, 출력 이미지의 픽셀은 두 입력 이미지에서 일치하는 픽셀이 흰색인 경우에만 흰색입니다. 그렇지 않으면 검은색입니다. 픽셀 단위로 작업을 수행하는 대신 쿼드트리의 용량을 사용하여 단일 노드로 여러 픽셀을 표현함으로써 합집합을 효율적으로 계산할 수 있습니다. 다음 설명의 목적을 위해 하위 트리에 검은색 픽셀과 흰색 픽셀이 모두 포함된 경우 하위 트리의 루트가 회색이라고 주장합니다.

이 알고리즘은 출력 quadtree를 작성하는 동안 T_{1} 두 개의 입력 쿼드트리(및 )를 순회하는 방식으로 작동합니다 T_{2} T .

비공식적으로 알고리즘은 다음과 같이 설명됩니다.

{\displaystyle v_{1}\in T_{1}} 이미지에서 동일한 영역에 해당하는 {\displaystyle v_{2}\in T_{2}} 노드를 고려 합니다.

v_{1} or v_{2} 가 검은색이면 해당 노드가 검 T 은색으로 생성되고 검은색으로 표시됩니다.

하나는 검은색이고 다른 하나는 회색이면