JFA (алгоритм, описанный здесь: http://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf ) можно использовать для получения аппроксимации диаграммы Вороного или преобразования расстояния. Это происходит в логарифмическом времени на основе размера полученного изображения, а не на количестве семян.

Что вы делаете, если ваше изображение не одинакового размера на каждой оси?

Если бы они были одинакового размера, я уверен, что вы могли бы просто позволить более короткой оси иметь дополнительные шаги JFA размера 1, в то время как большая ось закончила свою работу (например, изображение размером 512 x 256). Для размеров осей очень разных размеров это может быть гораздо более неэффективно - скажем, у вас была объемная текстура, которая была 512 x 512 x 4.

Можно ли запустить JFA на каждой оси отдельно и при этом получить приличные результаты?

Или в этот момент более подходящий алгоритм? Если так, то какой это может быть алгоритм?

В моей ситуации, в идеале, я стараюсь поддерживать как точечные семена, так и семена произвольной формы. Возможно даже взвешенные семена, где расстояние до семени регулируется множителем и / или сумматором, чтобы оказать на него более или менее влиятельное влияние.

Быстрые ответы на ваши индивидуальные вопросы

Что вы делаете, если ваше изображение не одинакового размера на каждой оси?

В статье используются квадратные изображения с длинами сторон, равными степени 2. Это для простоты объяснения, но не является обязательным для работы алгоритма. Смотрите раздел 3.1:

Без ограничения общности можно предположить, что n является степенью 2.

То есть это предположение не требуется для того, чтобы алгоритм работал.

Можно ли запустить JFA на каждой оси отдельно и при этом получить приличные результаты?

Запуск по каждой оси по отдельности может дать более неправильные результаты в пикселях, и в большинстве случаев он занимает больше времени. В крайних случаях, когда длина одной из сторон изображения меньше 8 (количество направлений прыжка), это может быть быстрее, поскольку алгоритм обрабатывает эти 8 направлений последовательно, но для любого более широкого изображения разделение осей теряет преимущество обработки их в параллели.

В моей ситуации, в идеале, я стараюсь поддерживать как семена с одной точкой, так и семена произвольной формы

В статье упоминаются семена произвольной формы в разделе 6 под подзаголовком «Обобщенная диаграмма Вороного»:

... наши алгоритмы обрабатывают такие обобщенные начальные числа как коллекции точечных начальных значений и, таким образом, ожидают наследования хорошей производительности, полученной для точечных начальных чисел.

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

Возможно, даже взвешенные семена, где расстояние до семян регулируется с помощью множителя и / или сумматора, чтобы дать ему более или менее влиятельное влияние.

Что касается «взвешивания на семенах, таких как мультипликативные и аддитивные», в статье упоминается только возможность прохождения в разделе 8, как потенциальная будущая работа. Тем не менее, это должно быть просто реализовать при условии, что желаемый вес может быть включен в начальные данные, которые передаются от пикселя к пикселю.

Текущий алгоритм проходит <s, position(s)>для указания начального числа и его положения, и в каждый момент времени на пиксель сохраняется только одно начальное число. Расширение этого для сохранения <s, position(s), weight(s)>предоставляет всю информацию, необходимую для взвешивания функции расстояния и вычисления, ближе ли к нему новое начальное число, передаваемое в пиксель, чем то, которое оно хранит в данный момент.

Вы можете даже включить два веса, один мультипликативный и один аддитивный, и просто установить мультипликативный один на 1, а аддитивный один на 0, когда это не требуется. Тогда ваш алгоритм будет включать возможность использования для мультипликативно взвешенных семян, аддитивно взвешенных семян или даже для комбинации обоих сразу или некоторых из них. Это просто нужно

<s, position(s), multiplicative(s), additive(s)>

и текущий алгоритм будет эквивалентен этому новому алгоритму, используя

<s, position(s), 1, 0>

Подробное объяснение почему

Как и в статье, все случаи использования относятся к основному логарифму 2.$\log()$

Алгоритм не нужно адаптировать к разным длинам сторон

Если длины сторон не равны и не являются степенями 2, нет необходимости адаптировать алгоритм. Он уже имеет дело с пикселями на краю изображения, для которых некоторые направления прыжка ведут за пределы изображения. Поскольку алгоритм уже опускает начальную информацию для направлений, которые ведут за пределы изображения, ширина или высота, не являющиеся степенью 2, не будут проблемой. Для изображения шириной W и высотой H максимальный требуемый размер прыжка будет

Для случая равной ширины и высоты N это уменьшает до

В случае длины стороны N, которая равна степени 2, это уменьшает до

как используется в статье.

В более интуитивном смысле округлите максимальную длину стороны до следующей степени 2, а затем уменьшите ее вдвое, чтобы получить максимальный размер прыжка.

Этого всегда достаточно, чтобы покрыть каждый пиксель в изображении от каждого другого пикселя в изображении, поскольку смещение любого пикселя будет в диапазоне от 0 до N-1, если длина самой длинной стороны равна N. Комбинации степеней 2 из От 0 до N / 2 будет охватывать каждое целое число вплоть до N-1, если N является степенью 2, а если N не является степенью 2, покрываемый диапазон может быть только больше, чем требуется, из-за превышения логарифма ( округление до следующей степени 2).

Изображения со сторонами не степени 2 не будут значительно менее эффективными

Количество прыжков зависит от длины самой длинной стороны, скажем L. Если L - степень 2, то количество прыжков равно . Если L не является степенью 2, то количество прыжков равно . Для достаточно большого изображения это не будет большой разницей.⌈ log ( L ) $\log(L)$$\lceil\log(L)\rceil$

Например, для изображения 1024 на 1024 потребуется 10 итераций перехода. Изображение 512 на 512 потребует 9 итераций перехода. Все, что находится между двумя размерами, также потребует 10 итераций. Даже в наихудшем случае для изображения, имеющего только степень 2, например, изображение 513 на 513, потребуется только 1 дополнительная итерация, которая в этом масштабе примерно на 11% больше (10 вместо 9).

Неквадратные изображения менее эффективны для каждой области

Поскольку количество требуемых итераций определяется самой длинной стороной, время, необходимое для изображения 1024 на 1024, будет таким же, как и для изображения 1024 на 16. Квадратное изображение позволяет охватить большую площадь за то же количество итераций.

Разделение осей может снизить качество

Раздел 5 статьи описывает возможные ошибки. Каждый пиксель доступен путем от любого другого пикселя, но некоторые пути не приносят правильного ближайшего начального числа, поскольку это начальное число не является ближайшим к предыдущему пикселю в пути. Говорят, что пиксель, который не позволяет семени проходить мимо, «убил» это семя. Если ближайший начальный элемент к пикселю уничтожен на всех путях к этому пикселю, то этот пиксель запишет какой-либо другой начальный элемент, и в конечном изображении будет неправильный цвет.

Должен существовать только один путь, который не убивает семя, чтобы окончательный результат был правильным. Неправильные цвета появляются только тогда, когда все пути от правильного начального числа до данного пикселя заблокированы.

Если путь включает в себя чередование горизонтальных и вертикальных прыжков, разделение осей сделает этот путь невозможным (все горизонтальные прыжки будут выполнены до всех вертикальных прыжков, что сделает чередование невозможным). Диагональные прыжки не будут возможны вообще. Таким образом, любой путь, который чередуется или содержит диагональные переходы, будет исключен. Каждый пиксель по-прежнему будет иметь путь к каждому другому пикселю, но, поскольку теперь стало меньше путей, существует большая вероятность того, что данный пиксель будет заблокирован для получения правильного начального числа, поэтому конечный результат будет более подвержен ошибкам.

Разделение осей, вероятно, заставит алгоритм занять больше времени

Эффективность, вероятно, будет снижена путем разделения осей, поскольку затопление больше не будет выполняться параллельно, а вместо этого будет повторяться для каждой оси. Для 2D это, вероятно, займет примерно вдвое больше времени, а для 3D примерно в 3 раза больше.

Это может быть несколько смягчено отсутствием диагональных скачков, но я все же ожидал бы общего снижения эффективности.