Как я могу улучшить производительность моей процедуры заливки?

Question

Я реализую в своем приложении четырехстороннюю заливку, псевдокод приведен ниже

Flood-fill (node, target-color, replacement-color):
 1. If the color of node is not equal to target-color, return.
 2. Set the color of node to replacement-color.
 3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the south of node, target-color, replacement-color).
 4. Return

Это довольно медленно и иногда заполняет стек вызовов! И мне действительно не удалось рассчитать сложность этого алгоритма.

Может кто-нибудь предложить лучший алгоритм для его реализации?

Answer 1

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

Answer 2

Я не могу помочь вам с C #, так как я делал это только в Delphi, но я могу помочь вам с проблемой стека вызовов. Хитрость заключается в том, чтобы не использовать рекурсивный алгоритм. Вместо этого используйте подход на основе стека, поддерживая набор точек, которые необходимо проанализировать.

По сути, вы добавляете «начальную точку» в стек (и меняете ее цвет). Затем, пока стек не пуст, снимите последнюю точку со стека (т.е. вставьте ее). Сделайте ваши сравнения для всех 4 направлений (влево, вправо, вверх, вниз). Если какой-либо из соседних пикселей необходимо перевернуть на новый цвет, выполните переворот, а затем добавьте эту соседнюю точку в стек. На следующем цикле должно быть больше точек, чем в стеке. Продолжайте цикл, пока стек не станет пустым.

Answer 3

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

Сложность этогоАлгоритм, выраженный в Big O, равен O (4 ^ n), поэтому я бы порекомендовал вам попытаться реализовать алгоритм BFS, таким образом вы могли бы избежать оставления несвязанного узла без changind, а также избегать прохождения более одного раза на любой вершине.Таким образом, вы должны быть в состоянии выполнить что-то вроде O (| E | + | V |), где | E |число ребер и | V |это число вершин.

Здесь ссылка на объяснение Википедии , и это довольно просто, так что проверьте это!

PS: Если вам нужно иметь сАлгоритм, я был бы более чем рад помочь вам!

Answer 4

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

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

Начальная точка также должна быть расширена до линии восток и запад перед добавлением в очередь.

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

Answer 5

Вы можете попробовать реализовать эту процедуру, она заполняет 4 миллиона пикселей в секунду.

На I7 с 2017 года это эквивалентно 9 миллионам затопленных пикселей в секунду, поэтому изображение с разрешением 1024x1024 пикселей можно обработать примерно за 0,1 секунды, используя 10-15 МБ памяти:

https://www.youtube.com/watch?v=4hQ1wA4Sl4c&feature=youtu.be

http://unity3dmc.blogspot.com/2017/02/ultimate-3d-floodfill-scanline.html?m=1