Последние записи

made in programmersforum 1

Интенсив по Python: Работа с API и фреймворками 24-26 ИЮНЯ 2022. Знаете Python, но хотите расширить свои навыки?
Slurm подготовили для вас особенный продукт! Оставить заявку по ссылке - https://slurm.club/3MeqNEk

Online-курс Java с оплатой после трудоустройства. Каждый выпускник получает предложение о работе
И зарплату на 30% выше ожидаемой, подробнее на сайте академии, ссылка - ttps://clck.ru/fCrQw

22nd
Сен

Алгоритм поиска картики в картинке

Posted by Chas under Delphi

Есть целое изображение:

фоновый цвет, это: Fuchsia

Изображения могут быть любой формы.
Правило одно: граница между объекта — 1 пиксель цвета Fuchsia, либо нет цвета(-1) если изображение граничит с краем картинки.

Моя задача:
Юзер мышкой выбирает картинку, и её края подсвечиваются, записываются координаты этой картинки.

Как это делает волшебная палочка в Paint.Net и фотошопе.

Какой алгоритм применить, как лучше искать?

blackstrip
Изображение состоит по сути из 2 цветов: ярко-фиолетового и другого. Алгоритм заливки третьим цветом с затравкой в месте клика обозначит площадь конкретного объекта, на который кликнули. После этого у нас получилось изображение из 3 цветов: фиолетового, другого, 3-го цвета объекта. А потом 1 пиксельная обрисовка в прямоугольнике в пределах этого объекта (по пикселям 3-го цвета можно определить размер, т.е. по их наиболее дальнему расположению относительно места клика) с проверкой разнообразных условий «если этот пиксель не 3-го цвета, а правее на один — 3-го цвета», «если этот пиксель 3-го цвета, а правее на один — не 3-го либо граница рисунка», и также в другие стороны (левее, выше, ниже) позволит нарисовать 1-пиксельный контур снаружи объекта 3-го цвета либо на краю внутри объекта 3-го цвета, и, таким образом, подсветить его.

Все дела с 2 или 3 цветами делаются на отдельной маске либо на логике if (цвет = ). На исходном рисунке конечно не надо помечать ничего цветами, т.к. можно налететь на цвет какой нибудь точки, точно совпадающий с выбранным для пометки цветом. Т.е. можно это вообще превратить в отдельную маску 3-х цветную. Делаем новый рисунок, в него в цикле перекопируем пиксели все с первоначального рисунка с условиями:
1) если пиксель фиолетовый Fuchsia — то кладем в точку 0
2) если пиксель не фиолетовый Fuchsia, а другой — то кладем в точку 1.

Затем при работе алгоритма заливки лазим по этой маске и помечаем залитые точки цветом 2.

Вот и получается трехцветная маска. Просто если время работы алгоритма критично, тогда лучше не делать этих лишних действий, а сделать так:
1) создаем новый рисунок, заливаем цветом 0 весь этот рисунок.
2) при работе алгоритма заливки цвета 0 (Fuchsia) и 1 (не Fuchsia) отличаем на исходном рисунке с помощью простого условия (цвет = Fuchsia), а результат заливки кладем не в исходный рисунок, а в новый, созданный в п.1, при том помечаем залитые точки на этом новом рисунке, допустим, цветом 1.

В итоге получим в новом рисунке 2-х цветную маску выбранного объекта. Дальше уже дело техники: обрисовка 1-пиксельная цветом 2 на этом рисунке и перенос всех пикселей цвета 2 (т.е. полученного контура) в цикле на исходный рисунок в виде пикселей уже нужного цвета (rgb-шного, желтого какого-нибудь, смотря какого цвета контур нужен).

Примерно так:

StriderX
Быстрее идеи предложенной blackstrip ничего не существует (ибо в пределе метод blackstrip даёт строгий O(1)). Сама суть идеи blackstrip в смещении баланса память\скорость в сторону занимаемой памяти — чем больше обсчитаем заранее, тем меньше делать потом =-)

Атлас — это картинка на которую мы собираем другие каритнки. То, что у вас показано изначально. Итого, алгоритм на словах у нас такой:
1) выкладываем на атлас исходные изображения так, чтобы их баундбоксы не пересекались;
2) готовим маску размером с атлас, заливаем её нулём;
3) идем по каждому пикселю атласа, везде пускаем «волну». Задача «волны» — вывести на маску объект цветом «номер объекта». Соответственно запускается волна только если в этой точке маска равна нулю и исходник не равен выбранному ключу. Наша «волна» должна еще обрисовать баундбокс (x, y, width, height) и занести эти данные в некий массив\лист (по индексу «номер объекта»)

Теперь пред-процессинг можно считать завершенным. Если юзер куда-то сунулся мышой, то делаем так:
1) Смотрим на маске цвет пиксела, это наш «номер объекта»
2) С массива по номеру вытягиваем баунд бокс
3) Блиттим указанный регион маски в некий temp, меняем «номер объекта» на чистый белый
4) Этот temp рисуем в некий contour 8 раз со всевозможными смещениями (+-1 по x,y)
5) Размываем contour, если есть желание
6) При необходимости вычитаем из contour temp
7) Если не вычитали, то рисуем сначала contour (там у нас залитый силует), а поверх уже блиттим регион с исходного атласа. Красим контур стандартным субстрактом (dest_color = src_color — ($FFFFFFFF — user_color))
Если чувствуем провал по производительности (а его быть не должно, но мало ли), то придется где-нибудь хранить и контуры.

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

тема на форуме