Метод замены цвета пикселя ближайшим цветом пикселя, который не является самим собой

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

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

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

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

Вам не придется думать о подходе и писать его код. (никто здесь не будет писать за вас код с нуля. Если у вас есть алгоритм, который вы не можете поместить в код, то вы можете поместить весь код, который у вас есть - этот код должен быть минимальным воспроизводимым примером: поскольку это «Python» включает в себя инструкции импорта, вызовы чтения файлов для получения целевого изображения и вызов вашей функции, чтобы люди могли возиться с вашим кодом и предлагать исправления.

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

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

Это нечто большее, чем «обработка изображений», чем другие, которые ухватились за ваше предложение «BFS».

Я могу предложить два подхода:

1. предполагая палитру цветов
2. если предположить, что нет палитры

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

Это сообщает вам, из любой позиции пикселя, расстояние до любого желаемого цвета в палитре.

Для какого-либо пикселя, который вы хотите заменить, найдите его местоположение во всех полях расстояний и определите тот, который дает второе наименьшее расстояние. Первое наименьшее расстояние — это расстояние его собственного цвета, которое должно быть равно 0. Второе наименьшее расстояние обязательно должно быть больше 0.

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

Другой подход — выполнить эту работу заново для каждого пикселя, который вы хотите изменить. Вычислить маску для цветов, отличных от текущего пикселя. Найдите ближайший пиксель, помеченный как «истина». Преобразование расстояния может сообщить вам расстояние до него (значительно сокращая пространство поиска), а в некоторых реализациях оно может даже указать направление к нему.