| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Связные области |
| Автор: artysite 12.7.2007, 15:04 |
| Подскажите, пожайлуста алгоритм, позволяющий идентифицировать связные области. Например. отличать одно желтое пятно от другого. |
| Автор: JUmPER 12.7.2007, 15:09 |
| можно "в лоб": стартовать в некоторой точке и бежать во все стороны, помечая пиксели не отличающиеся от текущего (отличающегося не больше, чем на eps)... |
| Автор: artysite 12.7.2007, 15:19 | ||
Контуры извилисты и тогда, если просто пробегать, непонятно это уже следущее пятно или это продолжение встречавшегося ранее пятна. |
| Автор: JUmPER 12.7.2007, 15:31 |
| например, имеем часть изображения с пятном 1 2 3 4 5 1 # # # # # 2 # # # # # 3 # # # # # 4 # # # # # 5 # # # # # начинаем, например, в 3х3 помечаем её (например, чёрным цветом или заносим в список отмеченных) 1 2 3 4 5 1 # # # # # 2 # # # # # 3 # # Х # # 4 # # # # # 5 # # # # # помечаем её соседей, если они: - ещё не отмечены - не отличаются от текущей точке по цвету 1 2 3 4 5 1 # # # # # 2 # # Х # # 3 # Х Х Х # 4 # # Х # # 5 # # # # # дальше делаем то же самое для её соседей... 1 2 3 4 5 1 # # Х # # 2 # Х Х Х # 3 Х Х Х Х Х 4 # Х Х Х # 5 # # Х # # вот такая рекурсия. таким образом всё пятно окажется помеченным и можно будет приступать к другим пятнам. только сходимость у такого метода ужасная... |
| Автор: Sartorius 12.7.2007, 15:35 |
| Кроме такого "FloodFill" можно предложить посчитать градиент цвета для каждой точки, что бы выделить контуры. |
| Автор: artysite 12.7.2007, 15:47 |
| Хм.., непонятно, что значит "приступать к другим пятнам", количество пятен и их положение заранее неизвестно. Вот, например, на самом большом пятне на рисунке, допустим мы идем от центра пятна к краям и одновременно в трех точках касаемся желтого цвета, как узнать разные идентификаторы им давать или они являются частями большого желтого сектора? |
| Автор: JUmPER 12.7.2007, 15:52 | ||
например, выбираем другой жёлтый пиксель (ещё не отмеченный) можно же начинать именно с жёлтых пятен, тогда будет известно разные ли это пятна или одинаковые. |
| Автор: artysite 12.7.2007, 15:57 | ||
Если начинать с желтых, то неопределенность будет на красных, вообще на изображении будут пятна 14-ти цветов, "вписанные" друг в друга |
| Автор: JUmPER 12.7.2007, 16:25 |
| тогда так: Матрица = новая матрица размера Ширина изображения х Высота изображения, заполненная нулями номер_текущего_пятна = 1 пока есть неотмеченные пиксели (НП) { // отмечаем первый пиксель: Матрица(Х НП, Y НП) = номер_текущего_пятна // дальше отмечаем рекурсивно по приведённому выше алгоритму всё текущее пятно ... увеличиваем на единицу номер_текущего_пятна } итого имеем матрицу, где каждая ячейка содержит номер пятна, в котором она находится. |
| Автор: artysite 13.7.2007, 10:12 |
| Надо попробовать, только как правильно всё организовать чтобы работало? пока есть неотмеченные пиксели (НП) { // отмечаем первый пиксель: Матрица(Х НП, Y НП) = номер_текущего_пятна i=1//шаг //организуем цикл Пока есть соседи с таким же цветом делаем { если цвет(x,y+i)==цвет(x,y) { то, матрица(x,y+i)==матрица(x,y) } если цвет(x+i,y)==цвет(x,y) { то, матрица(x+i,y)==матрица(x,y) } если цвет(x,y-i)==цвет(x,y) { то, матрица(x,y-i)==матрица(x,y) } если цвет(x-i,y)==цвет(x,y) { то, матрица(x-i,y)==матрица(x,y) } } если ни одно условие не выполняется, то уходим из цикла увеличиваем на единицу номер_текущего_пятна } При таком алгоритме проверка будет проводится только в влево, вправо, вверх и вниз. А как сделать так чтоб из каждой новой точки проверка шла во все стороны? |
| Автор: esperant0 13.7.2007, 10:38 |
| Можно запустить алгоритм для поиска границ. И в полученом изображении искать области. Если области кругловатые можно использовать хауфтрансформ. |
