점프 플러딩 알고리즘

점프 플러딩 알고리즘(Jump Flooding Algorithm, JFA)은 보로노이 다이어그램 및 distance transform 구성에 사용되는 flooding algorithm이다 . JFA는 2006년 ACM 심포지엄에서 소개되었다.

JFA는 GPU 계산, 특히 상수 시간 성능에서 바람직한 속성을 가지고 있다. 그러나 이것은 대략적인 알고리즘일 뿐이며 모든 픽셀에 대해 항상 올바른 결과를 계산하지는 않는다. 실제로는 오류가 적고 일반적으로 오류의 크기가 작다.

구현

JFA 원래 공식은 구현이 간단하다.

가져가픽셀 그리드  (이미지 또는 텍스처와 같은). 모든 픽셀은 고유한 색상의 "시드" 픽셀이 아닌 한 "정의되지 않은" 색상으로 시작한다. JFA가 진행됨에 따라 정의되지 않은 각 픽셀은 시드 픽셀에 해당하는 색상으로 채워진다.

각 단계 크기에 대해, JFA의 한 반복 실행:

모든 픽셀에 대해 반복~에.

이웃마다~에어디:

만약에정의되지 않은착색, 변화의 색상을'에스

만약에색깔이 있고색깔이 있는 경우어디그리고시드 픽셀은그리고, 각각 변경의 색상을'에스.

픽셀은 각 단계에서 색상을 두 번 이상 변경할 수 있으며 JFA는 거리가 동일한 경우를 해결하는 방법을 지정하지 않으므로 위에서 마지막으로 확인한 픽셀의 색상이 사용된다.

JFA는 마지막 단계 크기의 마지막 픽셀을 평가한 후 완료된다. 초기 데이터의 내용에 관계없이 가장 안쪽 루프는 총전체 계산 복잡성에 대한 각 픽셀에 대한 시간.

변형

JFA의 일부 변형은 다음과 같다.

• 끝에 추가 패스 : JFA+1에는 단계 크기가 1인 추가 패스가 하나 있다. 즉, 단계 크기는 N/2, N/4, ..., 1, 1이다. JFA+2에는 단계 크기가 2와 1인 두 개의 추가 패스가 있다. 즉, 단계 크기는 N/2, N/4, ..., 1, 2, 1이다. JFA가지다추가 패스, 즉 단계 크기는 N/2, N/4, ..., 1, N/2, N/4, ..., 1이다. JFA+1은 JFA보다 오류가 훨씬 적고 JFA+2 오류가 더 적는다.

• 처음에 추가 패스 : 1+JFA에는 단계 크기가 1인 추가 패스가 하나 있다. 즉, 단계 크기는 1, N/2, N/4, ..., 1이다. 1+JFA는 오류율이 매우 낮다(비슷한 JFA+2로) 및 JFA+1과 동일한 성능.
• 절반 해상도: 이 변형은 절반 해상도에서 일반 JFA를 실행하고 결과를 원래 해상도로 확대하고 단계 크기 1로 하나의 추가 패스를 실행한다. 대부분의 패스에는 절반 해상도만 있으므로 이 변형의 속도는 훨씬 빠르다. 전체 해상도 JFA보다.

사용

점프 플러딩 알고리즘 및 그 변형은 보로 노이 맵  및 중심 보로노이 테셀레이션 (CVT),  거리 필드 생성 ,  ^{[ 어떻게? ]} 포인트 클라우드 렌더링,  기능 일치 ,  전력 다이어그램 계산 ,  및 부드러운 그림자 렌더링.  대전략 게임 개발사인 Paradox Interactive는 JFA를 사용하여 국가와 지방 간의 경계를 렌더링한다.

추가 개발

JFA는 수많은 유사한 알고리즘의 개발에 영감을 주었다. 일부는 과학적 계산에 유용하도록 잘 정의된 오류 속성을 가지고 있다.

컴퓨터 비전 영역 에서 JFA는 다양한 문제의 솔루션을 가속화하기 위해 새로운 신념 전파 알고리즘에 영감을 주었다.