Алгоритм скачкового флуда

Алгоритм скачкообразной заливки ( JFA ) — это алгоритм лавинной заливки, используемый при построении диаграмм Вороного и дистанционных преобразований . JFA был представлен Ронг Годуном на симпозиуме ACM в 2006 году. ^[1]

JFA обладает желательными качествами в вычислениях на графическом процессоре , особенно из-за его эффективной производительности. Однако это лишь приблизительный алгоритм, и он не всегда вычисляет правильный результат для каждого пикселя, хотя на практике ошибок немного, а величина ошибок, как правило, невелика. ^[1]

Выполнение

Исходная формулировка JFA проста в реализации.

Возьмите $N\times N$ сетка пикселей ^[2] (например, изображение или текстура). Все пиксели начинаются с «неопределенного» цвета, если только это не «начальный» пиксель уникального цвета. По мере выполнения JFA каждый неопределенный пиксель будет заполнен цветом, соответствующим цвету исходного пикселя.

Для каждого размера шага $k\in \{{\frac {N}{2}},{\frac {N}{4}},\dots ,1\}$ , запустите одну итерацию JFA:

Перебирать каждый пиксель

p

в

(x,y)

.

Для каждого соседа

q

в

(x+i,y+j)

где

i,j\in \{-k,0,k\}

:

если

p

является неопределенным и

q

окрашен, изменить

p

цвет для

q

's

если

p

окрашен и

q

окрашен, если

dist(p,s)>dist(p,s')

где

s

и

s'

являются исходными пикселями для

p

и

q

соответственно, то измените

p

цвет для

q

х.

Обратите внимание, что пиксели могут менять цвет более одного раза на каждом этапе и что JFA не определяет метод разрешения случаев, когда расстояния равны, поэтому выше используется цвет пикселя, проверенного последним.

JFA завершается после оценки последнего пикселя в последнем размере шага. Независимо от содержимого исходных данных, самый внутренний цикл выполняет в общей сложности $9\log _{2}(N)$ раз по каждому пикселю, при общей вычислительной сложности $O(N^{2}\log _{2}(N))$ .

Варианты

Некоторые варианты JFA:

Дополнительный проход в конце : JFA+1 имеет один дополнительный проход с размером шага 1, т.е. размеры шага составляют N/2, N/4,..., 1, 1; JFA+2 имеет два дополнительных прохода с размерами шагов 2 и 1, т.е. размеры шагов составляют N/2, N/4,..., 1, 2, 1; JFA $^{2}$ имеет $\log _{2}(N)$ дополнительные проходы, т. е. размеры шага составляют N/2, N/4,..., 1, N/2, N/4,..., 1. JFA+1 имеет гораздо меньше ошибок, чем JFA, и JFA+2. имеет еще меньше ошибок. ^[1]

Дополнительный проход в начале : 1+JFA имеет один дополнительный проход с размером шага 1, т.е. размеры шага составляют 1, N/2, N/4, ..., 1. 1+JFA имеет очень низкий уровень ошибок (аналогично для JFA+2) и той же производительности, что и JFA+1. ^[3]
Половинное разрешение: этот вариант запускает обычный JFA с половинным разрешением, увеличивает результат до исходного разрешения и запускает один дополнительный проход с размером шага 1. Поскольку большинство проходов имеют только половину разрешения, скорость этого варианта намного выше. чем JFA в полном разрешении. ^[3]

Использование

Алгоритм скачкообразной заливки и его варианты могут быть использованы для расчета карт Вороного. ^[1]^[3] и центроидальные мозаики Вороного (CVT), ^[4] генерация полей расстояний , ^[5] рендеринг облаков точек , ^[6] соответствие характеристик , ^[7] расчет силовых диаграмм , ^[8] и мягкая рендеринг теней. ^[9] грандиозных стратегических игр Разработчик Paradox Interactive использует JFA для визуализации границ между странами и провинциями. ^[10]

Дальнейшие разработки

JFA вдохновил на разработку множества подобных алгоритмов. Некоторые из них имеют четко определенные свойства ошибок, что делает их полезными для научных вычислений. ^[11]

В области компьютерного зрения JFA вдохновила на создание новых алгоритмов распространения убеждений для ускорения решения множества проблем. ^[12]^[13]

Ссылки

^ Перейти обратно: ^а ^б ^с ^д Ронг, Годун; Тан, Тиоу-Сенг (14 марта 2006 г.). «Переполнение графического процессора приложениями к диаграмме Вороного и дистанционному преобразованию» (PDF) . Материалы симпозиума 2006 г. по интерактивной 3D-графике и играм — SI3D '06 . Редвуд-Сити, Калифорния: Ассоциация вычислительной техники. стр. 109–116. дои : 10.1145/1111411.1111431 . ISBN 978-1-59593-295-2 . S2CID 7282879 .
^ В исходной статье в качестве примера используется оптимальный случай - квадратная сетка, но работает сетка любого размера. Хоть и с пониженной эффективностью. Дополнительную информацию см . в этом вопросе StackOverflow .
^ Перейти обратно: ^а ^б ^с Ронг, Годун; Тан, Тиоу-Сенг (июль 2007 г.). «Варианты алгоритма Jump Flooding для вычисления дискретных диаграмм Вороного» . 4-й Международный симпозиум по диаграммам Вороного в науке и технике (ISVD, 2007) . стр. 176–181. дои : 10.1109/ИСВД.2007.41 . ISBN 978-0-7695-2869-4 . S2CID 386735 .
^ Годун Ронг; Ян Лю; Венпин Ван; Сяотянь Инь; Гу, XD; Сяоху Го (25 марта 2011 г.). «Вычисление центроидальной тесселяции Вороного с помощью графического процессора» . Транзакции IEEE по визуализации и компьютерной графике . 17 (3): 345–356. дои : 10.1109/TVCG.2010.53 . hdl : 10722/132211 . ISSN 1077-2626 . ПМИД 21233516 . S2CID 11970070 .
^ Голус, Бен (01 апреля 2021 г.). «В поисках очень широких очертаний» . Середина . Проверено 19 августа 2021 г.
^ Фариас, Ренато (2014). «Визуализация облаков точек с использованием затопления» (PDF) .
^ Ю, Пей; Ян, Сяокан; Чен, Ли (2012). «Параллельный патч-матч на основе Jump Flooding» . В Чжане, Вэньцзюнь; Ян, Сяокан; Сюй, Чжисян; Ан, Пинг; Лю, Цичжэнь; Лу, Юэ (ред.). Достижения в области цифрового телевидения и беспроводной мультимедийной связи . Коммуникации в компьютерной и информатике. Том. 331. Берлин, Гейдельберг: Шпрингер. стр. 15–21. дои : 10.1007/978-3-642-34595-1_3 . ISBN 978-3-642-34595-1 .
^ Чжэн, Липин (01 мая 2019 г.). «Эффективное вычисление диаграммы мощности на базе графического процессора» . Компьютеры и графика . 80 : 29–36. дои : 10.1016/j.cag.2019.03.011 . ISSN 0097-8493 . S2CID 131923624 .
^ Ронг, Годун; Тан, Тиоу-Сенг (1 ноября 2006 г.). «Использование скачкообразной заливки в мягких тенях на основе изображений» . Материалы симпозиума ACM по программному обеспечению и технологиям виртуальной реальности . ВРСТ '06. Лимассол, Кипр: Ассоциация вычислительной техники. стр. 173–180. дои : 10.1145/1180495.1180531 . ISBN 978-1-59593-321-8 . S2CID 15339123 .
^ Бочула, Бартош; Эрикссон, Дэниел (2020). «Оптимизированный рендеринг градиентных границ в Imperator: Rome» . Интел . Проверено 28 марта 2021 г.
^ Шнайдер, Йенс; Краус, Мартин; Вестерманн, Рюдигер (2010). «Преобразования евклидовых расстояний на основе графического процессора и их применение для объемного рендеринга» . В Ранчордасе — АлпешКумар; Перейра, Жуан Мадейрас; Араужо, Хелдер Дж.; Таварес, Жоау Мануэль РС (ред.). Компьютерное зрение, обработка изображений и компьютерная графика. Теория и приложения . Коммуникации в компьютерной и информатике. Том. 68. Берлин, Гейдельберг: Шпрингер. стр. 215–228. дои : 10.1007/978-3-642-11840-1_16 . ISBN 978-3-642-11840-1 .
^ Альхацидис, Ставрос; Сотирас, Аристейдис; Парагиос, Никос (6 ноября 2011 г.). «Эффективное параллельное вычисление сообщений для вывода MAP» . Международная конференция по компьютерному зрению 2011 г. (PDF) . стр. 1379–1386. дои : 10.1109/ICCV.2011.6126392 . ISBN 978-1-4577-1102-2 . S2CID 17554205 .
^ Чхве, Чонгук; Рутенбар, Роб А. (29 августа 2016 г.). «Настраиваемый и масштабируемый ускоритель распространения убеждений для компьютерного зрения» . 2016 26-я Международная конференция по полевой программируемой логике и приложениям (FPL) . стр. 1–4. дои : 10.1109/FPL.2016.7577316 . ISBN 978-2-8399-1844-2 . S2CID 10923625 .

На момент редактирования в этой статье используется контент из раздела «Разделим ли алгоритм Jump Flood?» , автором которого является alan-wolfe , trichoplax в Stack Exchange, который лицензируется таким образом, что разрешает повторное использование по лицензии Creative Commons Attribution-ShareAlike 3.0 Unported License , но не по GFDL . Все соответствующие условия должны быть соблюдены.

[Rong2006-1] Перейти обратно: ^а ^б ^с ^д Ронг, Годун; Тан, Тиоу-Сенг (14 марта 2006 г.). «Переполнение графического процессора приложениями к диаграмме Вороного и дистанционному преобразованию» (PDF) . Материалы симпозиума 2006 г. по интерактивной 3D-графике и играм — SI3D '06 . Редвуд-Сити, Калифорния: Ассоциация вычислительной техники. стр. 109–116. дои : 10.1145/1111411.1111431 . ISBN 978-1-59593-295-2 . S2CID 7282879 .

[2] В исходной статье в качестве примера используется оптимальный случай - квадратная сетка, но работает сетка любого размера. Хоть и с пониженной эффективностью. Дополнительную информацию см . в этом вопросе StackOverflow .

[Rong2007-3] Перейти обратно: ^а ^б ^с Ронг, Годун; Тан, Тиоу-Сенг (июль 2007 г.). «Варианты алгоритма Jump Flooding для вычисления дискретных диаграмм Вороного» . 4-й Международный симпозиум по диаграммам Вороного в науке и технике (ISVD, 2007) . стр. 176–181. дои : 10.1109/ИСВД.2007.41 . ISBN 978-0-7695-2869-4 . S2CID 386735 .

[4] Годун Ронг; Ян Лю; Венпин Ван; Сяотянь Инь; Гу, XD; Сяоху Го (25 марта 2011 г.). «Вычисление центроидальной тесселяции Вороного с помощью графического процессора» . Транзакции IEEE по визуализации и компьютерной графике . 17 (3): 345–356. дои : 10.1109/TVCG.2010.53 . hdl : 10722/132211 . ISSN 1077-2626 . ПМИД 21233516 . S2CID 11970070 .

[5] Голус, Бен (01 апреля 2021 г.). «В поисках очень широких очертаний» . Середина . Проверено 19 августа 2021 г.

[6] Фариас, Ренато (2014). «Визуализация облаков точек с использованием затопления» (PDF) .

[7] Ю, Пей; Ян, Сяокан; Чен, Ли (2012). «Параллельный патч-матч на основе Jump Flooding» . В Чжане, Вэньцзюнь; Ян, Сяокан; Сюй, Чжисян; Ан, Пинг; Лю, Цичжэнь; Лу, Юэ (ред.). Достижения в области цифрового телевидения и беспроводной мультимедийной связи . Коммуникации в компьютерной и информатике. Том. 331. Берлин, Гейдельберг: Шпрингер. стр. 15–21. дои : 10.1007/978-3-642-34595-1_3 . ISBN 978-3-642-34595-1 .

[8] Чжэн, Липин (01 мая 2019 г.). «Эффективное вычисление диаграммы мощности на базе графического процессора» . Компьютеры и графика . 80 : 29–36. дои : 10.1016/j.cag.2019.03.011 . ISSN 0097-8493 . S2CID 131923624 .

[9] Ронг, Годун; Тан, Тиоу-Сенг (1 ноября 2006 г.). «Использование скачкообразной заливки в мягких тенях на основе изображений» . Материалы симпозиума ACM по программному обеспечению и технологиям виртуальной реальности . ВРСТ '06. Лимассол, Кипр: Ассоциация вычислительной техники. стр. 173–180. дои : 10.1145/1180495.1180531 . ISBN 978-1-59593-321-8 . S2CID 15339123 .

[10] Бочула, Бартош; Эрикссон, Дэниел (2020). «Оптимизированный рендеринг градиентных границ в Imperator: Rome» . Интел . Проверено 28 марта 2021 г.

[:0-11] Шнайдер, Йенс; Краус, Мартин; Вестерманн, Рюдигер (2010). «Преобразования евклидовых расстояний на основе графического процессора и их применение для объемного рендеринга» . В Ранчордасе — АлпешКумар; Перейра, Жуан Мадейрас; Араужо, Хелдер Дж.; Таварес, Жоау Мануэль РС (ред.). Компьютерное зрение, обработка изображений и компьютерная графика. Теория и приложения . Коммуникации в компьютерной и информатике. Том. 68. Берлин, Гейдельберг: Шпрингер. стр. 215–228. дои : 10.1007/978-3-642-11840-1_16 . ISBN 978-3-642-11840-1 .

[12] Альхацидис, Ставрос; Сотирас, Аристейдис; Парагиос, Никос (6 ноября 2011 г.). «Эффективное параллельное вычисление сообщений для вывода MAP» . Международная конференция по компьютерному зрению 2011 г. (PDF) . стр. 1379–1386. дои : 10.1109/ICCV.2011.6126392 . ISBN 978-1-4577-1102-2 . S2CID 17554205 .

[13] Чхве, Чонгук; Рутенбар, Роб А. (29 августа 2016 г.). «Настраиваемый и масштабируемый ускоритель распространения убеждений для компьютерного зрения» . 2016 26-я Международная конференция по полевой программируемой логике и приложениям (FPL) . стр. 1–4. дои : 10.1109/FPL.2016.7577316 . ISBN 978-2-8399-1844-2 . S2CID 10923625 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]