팔진트리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
3. 공간 표현
4. 주요 용도
5. 색상 양자화 응용
6. 구현 예시 (점 분해)
- 6.1. 예시 코드 (MATLAB)
- 6.2. 색상 양자화 예시 (MATLAB)
참조

1. 개요

팔진트리는 3차원 컴퓨터 그래픽스에서 사용되는 자료 구조로, 공간을 8개의 팔분원으로 재귀적으로 분할하여 표현한다. 1980년 도널드 미어에 의해 처음 사용되었으며, 3차원 객체의 표현, 조작, 표시를 위한 기술로 개발되었다. 팔진트리는 공간 인덱싱, 세부 수준 렌더링, 최근접 이웃 탐색, 충돌 감지 등 다양한 분야에 활용된다. 또한 색상 양자화 알고리즘에도 사용되어 이미지의 색상 데이터를 효율적으로 인코딩한다.

더 읽어볼만한 페이지

컴퓨터 그래픽스 자료 구조 - 래스터 그래픽스
래스터 그래픽스는 이미지를 픽셀 배열로 표현하며 해상도에 종속적인 특징을 갖고 다양한 파일 형식으로 저장되어 여러 분야에 활용된다.
컴퓨터 그래픽스 자료 구조 - 화소
화소는 디지털 이미지를 구성하는 가장 작은 단위로, 이미지 해상도를 결정하며, 디스플레이 장치, 디지털 카메라, 그래픽 디자인 등 다양한 분야에서 활용되는 요소이다.
트리 구조 - 덴드로그램
덴드로그램은 데이터 분석에서 데이터 포인트 간 계층적 관계를 시각적으로 표현하는 나무 형태의 다이어그램으로, 군집 분석에서 클러스터 간 유사성을 나타내기 위해 활용되며 다양한 분야에 응용된다.
트리 구조 - 프림 알고리즘
프림 알고리즘은 그래프의 최소 비용 신장 트리를 찾는 탐욕 알고리즘으로, 최소 가중치를 가진 간선을 선택하여 트리를 확장하며, 시간 복잡도는 사용되는 자료 구조에 따라 달라진다.

팔진트리
개요
8분 트리
유형	트리 데이터 구조
고안자	도널드 미거
고안 연도	1980년
공간 (평균)	O(N)
공간 (최악)	O(N)
검색 (평균)	O(logN+K)
검색 (최악)	O(logN+K)
삽입 (평균)	O(logN)
삽입 (최악)	O(logN)
삭제 (평균)	O(logN)
삭제 (최악)	O(logN)
미리보기 (평균)	O(logN)
미리보기 (최악)	O(logN)
설명
정의	각 내부 노드가 정확히 8개의 자식을 갖는 트리 데이터 구조이며, 3차원 공간을 분할하는 데 사용된다.
용도	공간 파티셔닝에 유용하며, 3차원 공간에서 특정 위치에 있는 객체를 빠르게 찾기 위해 사용된다.
응용 분야	3차원 컴퓨터 그래픽스 공간 데이터베이스 로봇 공학
관련 개념
유사 구조	쿼드 트리 (2차원) 이진 공간 분할 (BSP) 트리

2. 역사

3차원 컴퓨터 그래픽스를 위한 팔진트리의 사용은 렌셀러 폴리테크닉 대학교의 도널드 미어(Donald Meagher)에 의해 개척되었다.^[1] 그는 1980년 보고서 "팔진트리 인코딩: 컴퓨터를 이용한 임의의 3차원 객체의 표현, 조작 및 표시를 위한 새로운 기술"에서 팔진트리 알고리즘을 설명했다.^[1] 그는 또한 1984년 우선일을 기준으로 1995년에 팔진트리에 대한 특허를 받았다.^[2] 팔진트리 색상 양자화 알고리즘은 1988년 Gervautz와 Purgathofer에 의해 발명되었다.

3. 공간 표현

팔진트리의 각 노드는 해당 노드가 나타내는 공간을 8개의 팔분원으로 세분한다. 점 영역(PR, point region) 팔진트리에서, 노드는 명시적인 3차원 점을 저장하며, 이 점은 해당 노드의 세분화 "중심"이 된다. 이 점은 8개의 자식 노드 각각에 대한 모서리 중 하나를 정의한다. 행렬 기반(MX, matrix based) 팔진트리에서 세분점은 암묵적으로 노드가 나타내는 공간의 중심이다. PR 팔진트리의 루트 노드는 무한 공간을 나타낼 수 있지만, MX 팔진트리의 루트 노드는 암묵적 중심이 잘 정의되도록 유한하고 경계가 있는 공간을 나타내야 한다. 팔진트리는 ''k''-d 트리와 다르다는 점에 유의해야 한다: ''k''-d 트리는 차원을 따라 분할되고, 팔진트리는 점을 중심으로 분할된다. 또한 ''k''-d 트리는 항상 이진 트리인 반면, 팔진트리는 그렇지 않다.

4. 주요 용도

팔진트리는 3차원 컴퓨터 그래픽스에서 세부 수준 렌더링, 공간 인덱스, 최근접 이웃 탐색에 사용된다. 또한 3차원에서의 효율적인 충돌 감지, 뷰 프러스텀 컬링, 고속 다중극 방법(Fast Multipole Method), 비정형 그리드, 유한 요소 해석에도 활용된다. 희소 복셀 옥트리, 상태 추정, 집합 추정, 시야 판정 및 유한 요소법에도 사용된다.

5. 색상 양자화 응용

팔진트리 색상 양자화 알고리즘은 1988년 Gervautz와 Purgathofer에 의해 발명되었으며, 이미지의 색상 데이터를 최대 9단계 깊이의 팔진트리로 인코딩한다.^[8] RGB 시스템에는 세 가지 색상 구성 요소(빨강, 녹색, 파랑)가 있기 때문에 $2^3 = 8$ 인 팔진트리가 사용된다. 최상위 레벨에서 분기할 노드 인덱스는 빨강, 녹색 및 파란색 색상 구성 요소의 최상위 비트를 사용하는 수식(예: 4r + 2g + b)으로 결정된다. 다음 하위 레벨은 다음 비트 유의성을 사용하며, 이와 같은 방식으로 진행된다. 덜 중요한 비트는 트리 크기를 줄이기 위해 무시되기도 한다.^[8]

이 알고리즘은 트리의 크기를 제한할 수 있기 때문에 메모리 효율성이 매우 높다. 팔진트리의 최하위 레벨은 트리에 표시되지 않은 색상 데이터를 누적하는 리프 노드로 구성되며, 이러한 노드는 처음에 단일 비트를 포함한다. 원하는 팔레트 색상 수보다 훨씬 많은 색상이 팔진트리에 입력되면 최하위 레벨 노드를 찾아 비트 데이터를 리프 노드로 평균화하고 트리의 일부를 가지치기하여 크기를 지속적으로 줄일 수 있다. 샘플링이 완료되면 트리에서 리프 노드까지 모든 경로를 탐색하여 중간에 있는 비트를 기록하면 대략 필요한 수의 색상이 생성된다.^[8]

6. 구현 예시 (점 분해)

다음은 3차원 점 배열을 옥트리 스타일의 빈(bin)으로 분해하는 재귀 알고리즘 개요 예시이다(MATLAB 구문). 이 구현은 모든 주어진 점을 둘러싸는 단일 빈으로 시작하여 재귀적으로 8개의 옥트리 영역으로 세분화한다. 재귀는 주어진 종료 조건이 충족되면 중지된다. 이러한 종료 조건의 예시는 다음과 같다.

빈에 주어진 수보다 적은 점이 포함된 경우
빈이 모서리의 길이를 기준으로 최소 크기 또는 부피에 도달한 경우
재귀가 최대 분할 횟수에 도달한 경우

```matlab

function [binDepths, binParents, binCorners, pointBins] = OcTree(points)

binDepths = [0] % 이 단일 기본 수준 빈으로 빈 깊이 배열을 초기화합니다.

binParents = [0] % 이 기본 수준 빈은 다른 빈의 자식이 아닙니다.

binCorners = [min(points) max(points)] % XYZ 공간의 모든 점을 둘러쌉니다.

pointBins(:) = 1 % 처음에 모든 점은 이 첫 번째 빈에 할당됩니다.

divide(1) % 이 첫 번째 빈을 분할 시작

function divide(binNo)

% 이 빈이 모든 종료 조건을 충족하는 경우 더 이상 분할하지 않습니다.

binPointCount = nnz(pointBins == binNo)

binEdgeLengths = binCorners(binNo, 1:3) - binCorners(binNo, 4:6)

binDepth = binDepths(binNo)

exitConditionsMet = binPointCount value

if exitConditionsMet

return; % 재귀 함수 종료

end

% 그렇지 않으면 이 빈을 새로운 분할점을 가진 8개의 새로운 하위 빈으로 분할합니다.

newDiv = (binCorners(binNo, 1:3) + binCorners(binNo, 4:6)) / 2

for i = 1:8

newBinNo = length(binDepths) + 1

binDepths(newBinNo) = binDepths(binNo) + 1

binParents(newBinNo) = binNo

binCorners(newBinNo) = [one of the 8 pairs of the newDiv with minCorner or maxCorner]

oldBinMask = pointBins == binNo

% pointBins == binNo에서 어떤 점이 이제 newBinNo에 속하는지 계산합니다.

pointBins(newBinMask) = newBinNo

% 새로 생성된 이 빈을 재귀적으로 분할합니다.

divide(newBinNo)

end

6. 1. 예시 코드 (MATLAB)

6. 2. 색상 양자화 예시 (MATLAB)

24비트 RGB 이미지의 전체 색상 목록을 점 입력으로 사용하여 옥트리 색상 양자화를 구현하면 다음과 같은 결과를 얻을 수 있다.^[8]

첫 번째 이미지는 원본(532818개의 고유 색상)이고, 두 번째는 옥트리 분해를 사용하여 양자화된 이미지(184개의 고유 색상)이다. 각 픽셀은 해당 픽셀이 속한 옥트리 빈의 중심에 있는 색상으로 할당된다. 각 옥트리 빈의 모든 색상의 중심에서 최종 색상을 선택할 수도 있지만, 이 추가적인 계산은 시각적 결과에 거의 영향을 미치지 않는다.^[8]

```matlab

% 원본 RGB 이미지 읽기

Img = imread('IMG_9980.CR2');

% 픽셀을 RGB 점 삼중항으로 추출

pts = reshape(Img, [], 3);

% 대상 빈 용량을 사용하여 OcTree 분해 객체 생성

OT = OcTree(pts, 'BinCapacity', ceil((size(pts, 1) / 256) * 7));

% 옥트리 객체에서 "리프 노드"인 빈을 찾기

leafs = find(~ismember(1:OT.BinCount, OT.BinParents) & ...

ismember(1:OT.BinCount, OT.PointBins));

% 각 리프 빈의 중심 RGB 위치 찾기

binCents = mean(reshape(OT.BinBoundaries(leafs,:), [], 3, 2), 3);

% 색상 맵을 사용하여 새로운 "인덱싱된" 이미지 만들기

ImgIdx = zeros(size(Img, 1), size(Img, 2));

for i = 1:length(leafs)

pxNos = find(OT.PointBins==leafs(i));

ImgIdx(pxNos) = i;

end

ImgMap = binCents / 255; % 8비트 색상을 MATLAB rgb 값으로 변환

% 원본 532818색 이미지와 결과 184색 이미지 표시

figure

subplot(1, 2, 1), imshow(Img)

title(sprintf('원본 %d색 이미지', size(unique(pts,'rows'), 1)))

subplot(1, 2, 2), imshow(ImgIdx, ImgMap)

title(sprintf('옥트리-양자화된 %d색 이미지', size(ImgMap, 1)))

참조

_[1] 논문 Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer 1980-10
_[2] 웹사이트 High-speed image generation of complex solid objects using octree encoding https://patents.goog[...] USPO 2012-09-20
_[3] 서적 Level of Detail for 3D Graphics https://books.google[...] Morgan Kaufmann
_[4] 논문 Comparison of nearest-neighbor-search strategies and implementations for efficient shape registration https://www.research[...] 2012
_[5] 서적 Real-Time Rendering, Fourth Edition https://books.google[...] CRC Press 2018-08-06
_[6] 간행물 Density Trees for Efficient Nonlinear State Estimation http://isas.uka.de/P[...] Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom 2010-07
_[7] 간행물 Guaranteed Characterization of the Explored Space of a Mobile Robot by using Subpavings http://www.ensta-bre[...] NOLCOS 2013
_[8] 뉴스 Color quantization using octrees. http://leptonica.org[...] 2008-09-04

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com