점프 플러딩 알고리즘

점프 플러딩 알고리즘(JFA)은 보로노이 다이어그램과 거리 변환의 구성에 사용되는 플러딩 알고리즘이다.JFA는 2006년 ACM 심포지엄에서 소개되었다.^[1]

JFA는 GPU 계산에서 바람직한 속성, 특히 일정한 시간 성능을 가지고 있다.그러나 실제 오류는 적고 오류의 크기는 일반적으로 작지만 모든 픽셀에 대해 항상 정확한 결과를 계산하지는 않는다.^[1]

실행

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

$N{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle N}$ ${\displaystyle N\time N}$ 픽셀^[2] 그리드를$$ 취하십시오(이미지 또는 텍스처 등).고유 색상의 "씨드" 픽셀이 아닌 한 모든 픽셀은 "정의되지 않은" 색으로 시작할 것이다.JFA가 진행됨에 따라 정의되지 않은 각 픽셀은 시드 픽셀에 해당하는 색상으로 채워지게 된다.

각 단계 크기 $k{\displaystyle \in \{\frac{\mathrm{N}}{}}$ 2,${\displaystyle N\frac{}{}}$ ${\displaystyle \frac{4}{}}$…${\displaystyle }$, ${\displaystyle 1}$ ${\displaystyle \}}$ ${\displaystyle k\in \{{\frac {N}{2}},{\frac {N}{4}},\dots ,1$에 대해 JFA를 한 번 반복 실행하십시오.

$({\displaystyle x}$, ${\displaystyle y}$) ${\displaystyle (x,y)}$에서 모든 픽셀 $p{\displaystyle }$ ${\displaystyle p}$에 반복하십시오$.$

${\displaystyle 각}$ 인접 $q{\displaystyle }$ ${\displaystyle$${\displaystyle }$$q}$에 대해 ( ${\displaystyle x}$+${\displaystyle i}$, y${\displaystyle }$+ ${\displaystyle j}$ ) ${\displaystyle(x+$${\displaystyle i}$$,$${\displaystyle \mathrm{y}}$$+j)$ ${\displaystyle \{\backslash }$displaystyle $i$ 0${\displaystyle ,}$ ${\displaystyle k\}}$ ${\displaystyle$ i$,j\$in \{-$k,0,k$ :

$p{\displaystyle }$ ${\displaystyle p}$이(가) 정의되지 않고 $q{\displaystyle }$ ${\displaystyle q}$이(가) 색상이 지정된 경우 p ${\displaystyle p}$의$$색상을 $q{\displaystyle }$ ${\displaystyle q$s로 변경하십시오.

만약 p{p\displaystyle}와 q{\displaystyle q}.., 만약 d나는 열심인 t(p, s)>p{p\displaystyle}와 q{\displaystyle q}을 위해 각각 어디 s{s\displaystyle}과가 어떻게 되′{s\displaystyle'}은 씨앗은 픽셀 지금 나는 열심인 t(p, s′){\displaystyle dist(p,s)>, dist(p,s의)}.,그리고나서$p{\displaystyle }$ ${\displaystyle p}$의$$색상을 $q{\displaystyle }$ ${\displaystyle q$s로 변경하십시오.

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

JFA는 마지막 단계 크기로 마지막 픽셀을 평가한 후 종료한다.초기 데이터의 내용과 관계없이 가장 안쪽 루프는 $O{\displaystyle ({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {\log }_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$(${\displaystyle N}$ $){$$2(N$)의 전반적인 계산 복잡성에 대해 각 픽셀에 대해 총 9 ${\displaystyle {\log }_{}}$ 2 ${\displaystyle {}_{}}$(N$){$$2($N) $_{2(N)}$의 9 log ${\displaystyle {2\mathrm{}}_{}}$ ⁡ (N$)$를 실행한다$.$

변형

JFA의 일부 변형은 [1] 및 [3]에 제시되어 있다.

• Additional pass at the end: JFA+1 has one additional pass with step size of 1, i.e. the step sizes are N/2, N/4, ..., 1, 1; JFA+2 has two additional passes with step sizes of 2 and 1, i.e. the step sizes are N/2, N/4, ..., 1, 2, 1; JFA${\displaystyle ^{2}}$ has ${\displaystyle \log _{2}(N)}$ additional passes, i.e. 단계 크기는 N/2, N/4, ...1, N/2, N/4, ..., 1. JFA+1은 JFA보다 오류가 훨씬 적고, JFA+2는 오류가 훨씬 적다.

• 초반 추가 패스: 1+JFA는 스텝 사이즈 1인 추가 패스 1개가 있다. 즉, 스텝 사이즈 1, N/2, N/4, ..., 1.+JFA는 에러율(JFA+2와 유사)이 매우 낮고(JFA+1과 유사) 성능이 같다.
• 절반 해상도:이 변형은 일반 JFA를 절반 분해능으로 구동하고 결과를 원래 분해능으로 확대하며 스텝 사이즈 1로 추가 패스를 1회 실행한다.대부분의 패스는 분해능이 절반밖에 되지 않기 때문에 이 변종의 속도는 풀 해상도 JFA보다 훨씬 빠르다.

사용하다

점프 플러딩 알고리즘과 그 변형은 보로노이 맵과^[1][3] 중심 보로노이 테셀레이션(CVT), 거리 필드 생성,^[4][5][how?] 포인트-클라우드 렌더링,^[6] 형상 일치,^[7] 전력 다이어그램 계산 ^[8]및 소프트 섀도 렌더링에 사용할 수 있다.^[9]그랜드 전략 게임 개발사인 패러독스 인터렉티브는 JFA를 이용하여 국가와 지방 사이의 경계를 넓힌다.^[10]

추가 개발

JFA는 수많은 유사한 알고리즘의 개발에 영감을 주었다.어떤 것들은 과학적인 계산에 유용하게 만드는 잘 정의된 오류 속성을 가지고 있다.^[11]

컴퓨터 비전 영역에서, JFA는 다양한 문제의 해결을 가속화하기 위해 새로운 믿음 전파 알고리즘을 고안해냈다.^[12][13]

참조

이 편집에서 이 문서는 다음 의 내용을 사용한다."점프 홍수 알고리즘은 분리가 가능한가?"Stack Exchange의 tricoplax인 Alan-wolfe가 작성했으며, GFDL에 의거하지 않고 Creative Commons Attribution-ShareAlike 3.0 Unported License에 의거하여 재사용을 허용하는 방식으로 라이센스가 부여된다. 모든 관련 조항은 따라야 한다.