Форум программистов, компьютерный форум, киберфорум
Наши страницы

Алгоритмы

Войти
Регистрация
Восстановить пароль
 
 
rst79
0 / 0 / 0
Регистрация: 12.11.2013
Сообщений: 9
#1

Векторизация растровых контуров - Алгоритмы

12.11.2013, 11:46. Просмотров 1160. Ответов 19
Метки нет (Все метки)

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

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


В "лоб" вижу такое решение —
1) "жучком" изнутри каждой области, найти 4-х связанную границу каждого контура
2) проредить точки, там где точки образуют прямую линию (оставить первую и последнюю точку отрезка)
В результате будет получено векторное описание контуров, но общие участки будут не идентичны.
3) совмещать точки из разных контуров, расстояние между которыми окажется меньше чем 1-2-3 пикселя, но сходу есть случаи когда это не поможет добиться 100% идентичности общих участков


Есть ли какие-то альтернативные решения этой задачи?
Есть ли какой-то эффективный подход для решения п.3 из моего предварительного варианта решения?

Заранее благодарен. Возможно материальное вознаграждение за "прорывные" советы. :-)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.11.2013, 11:46
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Векторизация растровых контуров (Алгоритмы):

Векторизация - Программирование
Приветствую! Имеется список пикселей по периметру произвольного полигона. Как вычислить только угловые пиксели? За любую инфу по...

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

Алгоритм поиска контуров изображения и составления многоугольника контура - Алгоритмы
Здравствуйте! Есть у меня какое-то монохромное изображение, например: Моя конечная цель - это составить многоугольник контура. В...

Векторизация - Matlab
x=1:10; y=2:11; z=10:-1:1; z(x:y) ans = 10 9

Векторизация кода - C++
Задание: Написать программу с ручной векторизацией (выбрать любой вариант из возможных трех: ассемблерная вставка, встроенные функции ...

НЕ работает ВЕКТОРИЗАЦИЯ - Matlab
Не работает векторизация. В чем ошибка ??? задаем масивы: x=; n=ones(28,1); v=1:28; y=zeros(max(x),1);

19
rst79
0 / 0 / 0
Регистрация: 12.11.2013
Сообщений: 9
12.11.2013, 11:48  [ТС] #2
пример
0
Изображения
 
Qwertiy
821 / 629 / 75
Регистрация: 20.08.2013
Сообщений: 2,524
12.11.2013, 13:15 #3
Делать обход не белых областей, а чёрной.
0
rst79
0 / 0 / 0
Регистрация: 12.11.2013
Сообщений: 9
13.11.2013, 10:20  [ТС] #4
Qwertiy, в этом случае тоже будет несовпадение общих границ и п.3 по прежнему будет актуален.
0
Qwertiy
821 / 629 / 75
Регистрация: 20.08.2013
Сообщений: 2,524
13.11.2013, 11:07 #5
Как могут не совпадать границы, если мы их обходим?
0
rst79
0 / 0 / 0
Регистрация: 12.11.2013
Сообщений: 9
13.11.2013, 19:20  [ТС] #6
Qwertiy, есть две причины несовпадения:

- разная стартовая точка для прореживателя из п.2, а соответственно разный контекст прихода прореживателя на общий участок;
- точечное место стыковки трех областей (тут жучок+прореживатель вместо 3х идентичных точек (по одной для каждого контура) могут сделать 3 пары по 2 точки, которые не будут между собой совпадать).
0
Qwertiy
821 / 629 / 75
Регистрация: 20.08.2013
Сообщений: 2,524
13.11.2013, 19:32 #7
rst79, нет, я говорил о векторизации чёрной области как единого объекта и последующем делении по границам на 3 объекта. В таком случае границы гарантированно совпадут.
0
rst79
0 / 0 / 0
Регистрация: 12.11.2013
Сообщений: 9
14.11.2013, 11:59  [ТС] #8
Qwertiy, тогда не понятно как векторизовать черную область единым объектом. Жучок тут не справится. И не понятно по какому принципу из такого "сеточного векторного объекта" выделить контура.
0
Qwertiy
821 / 629 / 75
Регистрация: 20.08.2013
Сообщений: 2,524
14.11.2013, 12:37 #9
Например, группируем точки в некотором количестве, чтобы получить дискретную границу и каждый раз идём в ближайшие из расположенных в некотором радиусе. Потом обрезаем торчащие хвосты.
0
rst79
0 / 0 / 0
Регистрация: 12.11.2013
Сообщений: 9
14.11.2013, 19:43  [ТС] #10
Qwertiy, не могли бы вы чуть подробней пояснить последний пост. Я прочитал его много раз и попробовал прикинуть, что означают все эти слова, но ничего не понял. Заранее благодарю.
0
Qwertiy
821 / 629 / 75
Регистрация: 20.08.2013
Сообщений: 2,524
14.11.2013, 19:59 #11
Группируем точки так, чтобы разрушить контур. Т. е. он становится не линией, а множеством несоприкасающихся точек. теперь из некоторой точки начинаем обход и проводим вектора во все точки, которые находятся достаточно близко от неё. Получится граф. Все хвосты из него удаляем. Если будут лишные циклы, то их тоже, но об этом я бы думал в последнюю очередь. Вероятно это вообще можно решить подбором радиуса. Ну и получившийся контур уже делим на требуемые циклы.
0
rst79
0 / 0 / 0
Регистрация: 12.11.2013
Сообщений: 9
14.11.2013, 21:37  [ТС] #12
Qwertiy, я представляю, что такое граф. Отдельный контур или всю сетку в векторном виде можно представить в виде ненаправленного графа. Хвост это дуга в узел, из которого нет других дуг. Но вот общую суть предлагаемого вами подхода я не понимаю.

"группировка точек" - каких точек? исходных черных или недообработанных узлов? что значит группировка?
"проведение вектора во все точки, недалеко лежащие от текущей" - с какой целью?


Если не трудно напишите еще чуть более подробно шаги начиная от исходного состояния. Буду крайне благодарен.
0
Qwertiy
821 / 629 / 75
Регистрация: 20.08.2013
Сообщений: 2,524
14.11.2013, 22:59 #13
Цитата Сообщение от rst79 Посмотреть сообщение
"группировка точек" - каких точек?
Исходных точек - того что на картинке. Как вариант - разделить всё на клетки и для кажой клетки поставить точку в центре масс. Или использовать какую-либо эмуляцию гравитации. Или послойно удалять все граничные точки рядами до тех пор, пока все точки не окажутся граничными.

Цитата Сообщение от rst79 Посмотреть сообщение
что значит группировка?
Что мы преобразуем контур в множество независимых точек.

Цитата Сообщение от rst79 Посмотреть сообщение
"проведение вектора во все точки, недалеко лежащие от текущей" - с какой целью?
Чтобы построить граф, который представляет собой искомый векторный контур.

Кстати, возникла другая идея. Проверять точки на заданном расстоянии от данной и брать середину каждой дуги как связанную точку. Возможно, игнорировать небольшие дырки в дуге. Или обрабатывать это потом отдельно.
0
rst79
0 / 0 / 0
Регистрация: 12.11.2013
Сообщений: 9
15.11.2013, 00:34  [ТС] #14
Qwertiy, я кажется понял!

Нарезаем исходное изображение на небольшие области (например, 3x3 точки). Каждая область, в которой есть хотя бы одна черная точка формирует некую векторную точку (усредненные координаты всех черных точек в области), которая пока ни с чем не связана и помещается в некий список несвязаных векторных точек.
Вторым этапом начинаем связывать полученные векторные точки в граф. Если расстояние между двумя точками меньше некоторой величины, то прописываем между ними связь.
В результате такую структуру (граф) можно обходить, в узлах откуда ведут несколько дуг можно уходить по дуге ближайшей "слева" от дуги прихода. Обойдя граф столько раз сколько в нем узлов, можно найти все одиночные контура.

Я правильно понял общую идею?
0
Qwertiy
821 / 629 / 75
Регистрация: 20.08.2013
Сообщений: 2,524
15.11.2013, 00:47 #15
Цитата Сообщение от rst79 Посмотреть сообщение
Я правильно понял общую идею?
Да. Правда я не уверен относительно последней фразы про обходы, но если что, то понятно как с этим разбираться
0
15.11.2013, 00:47
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.11.2013, 00:47
Привет! Вот еще темы с ответами:

Как производится векторизация BITMAP? - C++
Народ поможите! Как производится векторизация BITMAP и тому подобное.

Векторизация цикла заполнения массива структур - Matlab
Возможна ли векторизация цикла (например, for i = 1 : count) заполнения полей структуры my_struct(i) для всего массива структур...

Программа для обработки растровых изображений - Visual C++
Всем привет!)) Мне задали курсач по программированию на Visual Studio C++. Разработать программу для обработки растровых изображений,...

Маштабирование мувиклипа движущихся растровых частей - Flash
1.Есть например мувиклип, состоящий из нескольких движущихся растровых частей. Припустим размер его 100*100 (без маштаба, в оригинале). ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru