옥트리

Octree
왼쪽: 큐브를 8진법으로 재귀 분할.오른쪽: 해당하는 8진수.

8진수는 각 내부 노드가 정확히 8명의 자식을 갖는 트리 데이터 구조다.8진법은 8진법으로 재귀적으로 세분하여 3차원 공간을 분할하는 데 가장 많이 사용된다.8진법은 4진법의 3차원 아날로그다.이 단어는 옥트(그리스어 루트 8) + 나무에서 유래되었다.옥트리는 종종 3D 그래픽과 3D 게임 엔진에 사용된다.

공간 표현용

8진수의 각 노드는 그것이 나타내는 공간을 8진법으로 세분한다.점 영역(PR) 8진수에서, 노드는 명시적인 3차원 점을 저장하는데, 이는 해당 노드에 대한 하위 구획의 "중심"이다. 이 점은 8명의 어린이 각각에 대한 코너 중 하나를 정의한다.매트릭스 기반(MX) 8진수에서 하위분할 지점은 노드가 나타내는 공간의 중심이다.PR 8진수의 루트 노드는 무한 공간을 나타낼 수 있다. MX 8진수의 루트 노드는 유한 경계 공간을 나타내야 암묵적 중심이 잘 정의된다.유의할 점은 옥수수는 k-d 나무와 같지 않다는 것이다: k-d 나무는 치수를 따라 갈라지고 옥수수는 한 점을 중심으로 갈라진다.또한 k-d 나무는 항상 2진법으로, 8진법은 그렇지 않다.깊이 우선 검색을 사용하여 노드를 통과하고 필요한 표면만 볼 수 있다.

역사

octrees의 3D컴퓨터 그래픽을 위한 사용은 도널드 마르에 의해 렌셀러 폴리 테크닉 대학교에서 그 이유는 그는 1995년 특허(1984년 우선 순위 날짜와)"고속 이미지 gener를 잡고 있는 1980년 보고서"팔 진트리 인코딩:A 신기술은 표현을 위한, 정보의 교환을 위해와 전시 행해지는 임의의 3D물체의 컴퓨터에"[1]에서 설명한 개척하였다.ati8진수 인코딩을 사용하여 복잡한 고체 물체에서"

공통 용법

색 정량화에 응용

1988년 저바우츠와 푸르가토퍼에 의해 발명된 8진 색 정량 알고리즘은 영상 색 데이터를 최대 9단계 깊이의 8진수로 암호화한다.8진수는 2 = 과(와) RGB 시스템에는 3가지 색상 구성요소가 있기 때문에 사용된다.상위 레벨에서 분기할 노드 색인은 빨간색, 녹색 및 파란색 구성 요소 중 가장 유의미한 비트를 사용하는 공식(예: 4r + 2g + b)에 의해 결정된다.다음 하위 레벨은 다음 비트 중요도를 사용하는 등트리 크기를 줄이기 위해 중요도가 낮은 비트는 무시되기도 한다.

이 알고리즘은 나무의 크기를 제한할 수 있기 때문에 메모리 효율성이 높다.8진수의 하단 레벨은 트리에 표시되지 않는 색상 데이터를 수집하는 리프 노드로 구성된다. 이 노드들은 처음에 단일 비트를 포함한다.원하는 수의 팔레트 색상을 8진수 이상으로 입력하는 경우, 하위 수준의 노드를 찾아 비트 데이터를 리프 노드로 평균화하여 트리의 일부를 가지치기함으로써 그 크기를 지속적으로 줄일 수 있다.일단 샘플링이 완료되면, 나뭇잎 노드로 이어지는 트리의 모든 경로를 탐색하면서, 그 도중에 비트를 참고하면 대략 필요한 색의 수가 산출될 것이다.

점 분해를 위한 구현

아래의 예시 알고리즘 개요(MATLAB 구문)는 일련의 3차원 점들을 8진수 스타일 빈으로 분해한다.구현은 주어진 모든 지점을 둘러싸는 하나의 빈으로 시작되며, 그런 다음 8진수 영역으로 재귀적으로 세분화된다.주어진 출구 조건이 충족되면 재귀가 정지된다.그러한 출구 조건의 예(아래 코드에 표시됨)는 다음과 같다.

  • 빈에 지정된 점 수보다 적은 수의 점 포함
  • 빈이 가장자리의 길이에 따라 최소 크기 또는 볼륨에 도달하는 경우
  • 재귀가 최대 하위 섹션 수에 도달한 경우
function [binDepths,binParents,binCorners,pointBins] = OcTree(points)   binDepths = [0] % Initialize an array of bin depths with this single base-level bin binParents = [0] % This base level bin is not a child of other bins binCorners = [min(points) max(points)] % It surrounds all points in XYZ space pointBins(:) = 1 % Initially, all points are ass이 첫번째 통 divide(1)%로 Igned 시작 이 통 어떤 출구 조건을 충족하 divide(binNo)%이 첫번째 통 기능을 나누고 조금이라도 더.;값분(binEdgeL 그것 binPointCount)nnz(pointBins==binNo)binEdgeLengths)binCorners(binNo,1:3)-binCorners(binNo,4:6)binDepth)binDepths(binNo)exitConditionsMet)binPointCount< 나누지 않는다.eng저희 조가 선택)<>값 binDepth>, 값exitConditionsMet 반환,%퇴직 귀납적 함수 끝% 그렇지 않으면, 나는 1:8이하로 돌출 newBinNo원 8 새로운 sub-bins에 새로운 분기점. newDiv =(binCorners(binNo,1:3)+binCorners(binNo,4:6))/2이 쓰레기 통을 나누다)length(binDepths)+1binDepths(newBinNo))binDepths(binNo)+1binParents(newBinNo))binNo.binCorners(newBinNo) = [one of the 8 pairs of the newDiv with minCorner or maxCorner]  oldBinMask = pointBins==binNo  % Calculate which points in pointBins==binNo now belong in newBinNo   pointBins(newBinMask) = newBinNo  % Recursively divide this newly created bin  divide(newBinNo) end

색상 정량화 예제

위에서 설명한 옥트리 포인트 분해 구현에 대한 포인트 입력으로 24비트 RGB 영상의 전체 색상 목록을 보면, 다음 예는 옥트리 색 정량화의 결과를 보여준다.첫 번째 이미지는 원본(532818 구별되는 색상)이고, 두 번째 이미지는 옥트리 분해를 사용한 정량화된 이미지(184 구별되는 색상)이며, 각 픽셀은 떨어지는 옥트리 빈의 중앙에 색상을 할당한다.또는 각 8진수 빈에 있는 모든 색의 중심에서 최종 색상을 선택할 수 있지만, 이 추가된 계산은 시각적 결과에 거의 영향을 미치지 않는다.[8] 

원본 RGB 이미지 읽기 비율 임그 = imread('IMG_9980.CR2'); % 픽셀을 RGB 포인트 3중으로 추출 pts = 모양을 바꾸다(임그,[],3); % 대상 빈 용량을 사용하여 OcTree 분해 개체 생성 OT = OcTree(pts,'BinCapacity,천장을 치다((사이즈를 맞추다(pts,1) / 256) *7)); % 8진수 객체에서 "리프 노드"인 빈 찾기 잎사귀 = 찾아내다(~ismember(1:OT.빈카운트, OT.빈파운트) & ...     ismember(1:OT.빈카운트,OT.포인트빈스)); % 각 리프 빈의 중앙 RGB 위치 찾기 빈센트 = 심술궂다(모양을 바꾸다(OT.빈바인더리(잎사귀,:),[],3,2),3);   % 색상 맵으로 새 "인덱싱된" 이미지 만들기 임기덱스 = 0(사이즈를 맞추다(임그,1), 사이즈를 맞추다(임그,2)); 을 위해 i = 1:길이(잎사귀)     pxNos = 찾아내다(OT.포인트빈스==잎사귀(i));     임기덱스(pxNos) = i; 종지부를 찍다 임그맵 = 빈센트 / 255; 8비트 색상을 MATLAB rgb 값으로 변환 비율   원본 532818 컬러 영상 및 결과 184 컬러 영상 표시 비율 형상을 나타내다 하위 플롯(1,2,1), 임쇼(임그) 칭호를 붙이다(단거리 경주('원래 %d 컬러 이미지', 사이즈를 맞추다(독특한(pts,'행'),1))) 하위 플롯(1,2,2), 임쇼(임기덱스, 임그맵) 칭호를 붙이다(단거리 경주('Octree-quantized %d color image', 사이즈를 맞추다(임그맵,1)))

참고 항목

참조

  1. ^ Meagher, Donald (October 1980). "Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer". Rensselaer Polytechnic Institute (Technical Report IPL-TR-80-111).
  2. ^ Meagher, Donald. "High-speed image generation of complex solid objects using octree encoding". USPO. Retrieved 20 September 2012.
  3. ^ David P. Luebke (2003). Level of Detail for 3D Graphics. Morgan Kaufmann. ISBN 978-1-55860-838-2.
  4. ^ 엘스버그, 얀 등"효율적인 형상 등록을 위한 가장 근접한 검색 전략과 구현의 비교." Journal of Software Engineering for Robotics 3.1(2012) : 2-12.
  5. ^ Akenine-Mo ̈ller, Tomas; Haines, Eric; Hoffman, Naty (2018-08-06). Real-Time Rendering, Fourth Edition. CRC Press. ISBN 978-1-351-81615-1.
  6. ^ 헤닝 에버하르트, 베사 클룸프, 우베 D.효율적인 비선형 상태 추정을 위한 해네벡, 밀도 나무, 2010년 7월 영국 에든버러에서 열린 제13차 정보융합 국제회의의 개최.
  7. ^ V. 드레벨, L. 자울린, B.Zerr, Subpavings, NOLCOS 2013을 사용하여 모바일 로봇의 탐색된 공간의 특성화 보장.
  8. ^ 블룸버그, Dan S. "옥타리를 이용한 색 정량화.", 2008년 9월 4일.2014년 12월 12일에 검색됨

외부 링크