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

Question

[Федор]

Собственно, есть некоторое изображение (bmp/jpg/png) которое содержит в себе некоторое количество объектов с ломанными границами. Объекты находятся на изображении как угодно (могут находиться очень близко друг к другу), но не пересекаются.


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

Какие алгоритмы можете посоветовать?
Может есть что-то в OpenCV, что позволит узнать координаты крайних точек (x1,y1,x2,y2) и уже с помощью, например, QImage->copy скопировать выбранный фрагмент и из QImage сохранить его (передать другому компоненту).

P.S> В размышлениях придумал вариант заносить данные в двумерный массив (черный цвет - 0, белый - 1) и уже из него каким-то образом выделять группы нулей и записывать их ещё куда-нибудь. Соответственно, из куда-нибудь опять превращать в файл и сохранять (работать далее с ним). Что может быть лучше этого варианта?

Answer 1

[Федор]

Так как поступают ответы, напишу вариант, на котором я остановился и реализовал.
1. В библиотеке OpenCV берётся алгоритм поиска контуров.
2. Если контур удовлетворяет условиям по размерам (не шум и не слишком маленький) копируем этот контур на новое изображение
3. По имеющимся координатам крайних точек контура просто вырезаем изображение из картинки
4. Сохраняем результат в файл.
Всё оказалось довольно просто

Comments

[Михаил Криницкий]

Есть один изъян в этом алгоритме, с которым случайно столкнулся. При переносе обнаруженного контура на новое изображение:
1. Надо последить за тем, чтобы контур включал все, что есть внутри него. Имеются в виду, например, случаи вложенных фигур. Следите за параметрами метода поиска контуров.
2. При отрисовке обнаруженного контура с заливкой он может отрисоваться не в точном совпадении с оригинальной фигурой. Тут надо, опять же, следить за тем, чтобы заливать только то, что нужно, не заливать пространство между вложенными фигурами. А еще (что самое неприятное) могут теряться или приобретаться пиксели оригинальной фигуры. Например, на очень острых углах.
А в остальном - да, использую тот же подход.

Answer 2

[_ _]

www.fmwconcepts.com/imagemagick/multicrop/index.php

Comments

[Федор]

Насколько я понимаю, там надо всё равно координаты указывать?

Answer 3

[plasticmirror]

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

п.с. пишется за 20 минут, на оптимальность по скорости не претендует, но и условия этого не предполагают...

Comments

[Федор]

Насколько понимаю вас, тут надо найти первую черную точку (0) и дальше искать ближайшие нули по (i,j) до тех пор пока не встретим единицу. Правильно понимаю?

[Алексей Черемисин]

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

[plasticmirror]

https://ru.wikipedia.org/wiki/Волновой_алгоритм

[Федор]

@plasticmirror с описания на вики "Алгоритм предназначен для поиска кратчайшего пути от стартовой ячейки к конечной ячейке, если это возможно, либо, при отсутствии пути, выдать сообщение о непроходимости" - у меня начальные и конечные точки не известны. Если начальную и можно найти, наткнувшись на 0, то всяко разно надо будет искать конечную точку.
@leahch в моем случае символ "#" не расматривается.

[plasticmirror]

конечная точка - белый цвет. т.е. все пути будут пройдены - на выходе массив черных точек = фигура искомая.

[Федор]

@plasticmirror а что скажете по поводу того, что приведённый в вики пример имеет координаты откуда и куда надо пройти?

[plasticmirror]

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

[Федор]

@plasticmirror ну идеи то такие и так в воздухе витают. Вот только насколько хорош данный алгоритм под переделку - другой вопрос.

Answer 4

[Don Kaban]

Для самозамкнутых фигур (если сканлиния, проведенная через фигуру будет прерывистой) поиск в ширину не сработает. Правай нижняя фигура, к примеру

Answer 5

[Виталий]

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

по скорости алгоритм не шибко быстрый выйдет, но и не сильно медленный, сек за 5-10 на HD картинку.

волновой алгоритм можно упростить до простейшей рекурсии, на вход координаты первой точки p
void voln(p){
сделать p-белый в исходной
сделать p-черный в созданном bitmap
для каждой черной точки p2 вокруг точки p
voln(p2)
}

на выходе из рекурсии вторая картинка заполнена тем фрагментом, точка которого подавалась на вход в рекурсию

Answer 6

[Odissey Nemo]

Берётся любой алгоритм заливки одноцветного растрового полигона любым цветом, начиная с любой его точки заданного цвета. Они были ещё под ДОС заготовлены в любом растровой библиотеке (в том-же Борланде).

1. Ищется слева направо сверху вниз первая точка нужного цвета. Если не найдена - выход. Иначе на 2.
2. Точка запоминается на будущее. Начиная от найденной точки, заливается полигон, включающий её каким-либо рабочим цветом (алгоритмом заливки).
3. Определяются bounding box (экстенты) этого найденного полигона (top Y уже известен - как у первой точки) в растровой системе координат. Создаётся растр этого размера (или чуть расширенный для красивых границ). В него перегоняется найденный полигон.
4. Сохраняется найденный полигон в файл.
5. Из оригинального изображения устраняется найденный полигон. Скажем, методом той же заливки, но уже цветом отсутствия. Или вариацией операции XOR по цвету заливки.
6. Начиная с запомненной точки, ищется следующая точка нужного цвета.
7. Если найдена, на шаг 2.
8. Если не найдена, выход.

Не ясным пока остаётся поиск экстентов (Bounding box, BB). Самое простое - сканировать каждый раз весь исходный растр, что не комильфо. Или как-то модифицировать алгоритм заливки - с запоминанием экстентов. Что достаточно просто. И залил и экстенты получил за один раз.