고속 고차원 필터링을 위한 가우시안 KD-트리

우리는 양방향, 비국소 평균 및 기타 관련 필터를 포함하는 광범위한 비선형 필터를 가속화하기 위한 방법을 제안합니다. 이러한 필터는 모두 유사한 방식으로 표현될 수 있습니다: 먼저 필터링할 각 값에 대해 일부 벡터 공간에서 위치를 할당합니다. 그런 다음 각 값을 모든 값의 가중 선형 조합으로 교체하며, 가중치는 위치 간의 거리의 가우시안 함수에 의해 결정됩니다. 값이 픽셀 색상이고 위치가 (x, y) 좌표인 경우 이는 가우시안 블러를 설명합니다. 위치가 대신 다섯 차원 색상 공간에서 (x, y, r, g, b) 좌표인 경우 이는 양방향 필터를 설명합니다. 대신 위치를 연관된 픽셀 주변의 색상 로컬 패치로 설정하면 이는 비국소 평균을 설명합니다. 우리는 이러한 방식으로 표현될 수 있는 필터를 효율적으로 계산하는 몬테카를로 kd-트리 샘플링 알고리즘과 이 기술의 GPU 구현을 설명합니다. 우리는 이 알고리즘을 사용하여 전체 3D 색상 거리를 준수하는 가속 양방향 필터를 구현하고, 단일 이미지, 볼륨 및 이미지의 비정렬 버스트에 대한 가속 비국소 평균을 사용하여 노이즈 제거를 수행하며, 비국소 평균의 기하학에 대한 빠른 적응을 수행합니다. 필터링할 값이 n개이고 각 값이 d 차원 공간에 위치가 할당되어 있으면, 우리의 공간 복잡도는 O(dn)이고 시간 복잡도는 O(dn log n)입니다. 반면, 기존 방법은 일반적으로 d에 대해 지수적이거나 n에 대해 제곱적입니다.