Как автоматически разбить изображение на отдельные фрагменты?

Question

[MegaMufa]

Добрый день.
Есть небольшое цветное изображение и набор паттернов (расположение группы пикселей). Надо разбить изображение на эти паттерны, так чтобы в каждый из них входили пиксели, похожих цветов.

Например, есть вот такое изображение:
И такие паттарны:

Скармливаю программе это изображение и она говорит, что здесь можно разместить второй паттерн вот так: В идеале при большом количестве паттернов программа должна разбивать на них все изображение без

Я не знаю что конкретно мне надо искать? Какие алгоритмы, как называется задача? Может кто-нибудь сталкивался с подобной задачей, подскажите, как это делается?

Answer 1

[GavriKos]

Похоже на задачу об укладке рюкзака. С дополнительными условиями. Можете посмотреть алгоритмы ее решения.

Ну и на всякий случай - посмотрите генетические алгоритмы.

Comments

[MegaMufa]

Проблема не в том, как сложить блоки так, чтобы заполнить все пространство. А как распознать на изображении блоки схожих пикселей.

[GavriKos]

HaruAtari Обычно в таком случае надо начать с точного определения термина "схожие пиксели". Т.е. вот зеленый и темно-зеленый - это схожие? Почему? ;-)

[MegaMufa]

GavriKos: Цвет похож. Т.е. средняя разница в значении всех каналов не превышает определенную величину.

Answer 2

[FoxInSox]

Для начала можно просто подумать, а не искать готовое решение/алгоритм. На это и нацелены задачи, зачем их вообще решать если все сводится к поиску алгоритма?
"Похожий цвета" это те цвета в которых схожи RGB модели. Т.е. RGB(255, 0, 0) и RGB(150, 0, 0) - схожи (второй оттенок красного, более темный), RGB(255, 0, 0) и RGB(0, 255, 0) - напротив, первый красный, второй зеленый.
Алгоритм может выглядеть так:
1. Сначала создаете карту блоков/прямоугольников/RGB моделей. Можно банальным перебором пикселей.
2. Берете первый блок и проверяете на "схожесть" с соседним блоком.
3. Повторяете предыдущий пункт пока не обойдете все блоки со схожим цветом и составляете фигуру.

Comments

[MegaMufa]

1. rgb не очень хорошо подходит для нахождения визуально похожих цветов. Но перевести в другую схему - не проблема.
2. Вот в нахождении групп схожих цветов и проблема. Если делать так, как вы предложили, то цвета могут сильно различаться. Например, первый отличается от второго, скажем, на 10 оттенков. Третий от второго тоже на 10. А в итоге первый отличается от третьего на 20 оттенков. И хотя они считаются похожими, они уже таковыми не являются.

[FoxInSox]

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

Answer 3

[Василий]

напомнило
habrahabr.ru/post/274527