Столкнулся с такой задачей. Необходимо оцифровать график, т.е. имеем изобржание(бинарное для начала) графика синусоиды например. Необходимо найти синусоиду на изображению и заполнить таблицу пар значений X/Y(в соответствии точкам, которые располагаются на синусойде с определенным шагом).

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





Присоединённый файл ( Кол-во скачиваний: 60 )
 example.jpg 22,04 Kb

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

Простые прямые можно искать с помощью упомянутых преобразований Хафа. Ну там надо будет немного доработать алгоритм в части ограничения кривой и определения её концов. 

Так в чём именно проблема? 

Не, для такой кривулины Хаф - не пройдет. Я уж не говорю о том, что Хаф только детектирует прямые и окружности (причем совсем не одновременно, нужно делать разные проходы). А выявлять где начался - кончился отрезок данной прямой нужно отдельно... или как-то встраивать в и без того непростой алгоритм. Если фон белый, то делают так: бинаризация (т.е. превращение в черно-белый рисунок), утоньшение (превращение линии в ее скелет), прослеживание скелета. Бинаризация при постоянном фоне элементарна, утоньшение мне больше нравится через distance transform, но это дело вкуса, прослеживание - волновой алгоритм, например.
Если график такой простой, то можно попробовать обойтись без утоньшения, одним волновым алгоритмом. А можно еще проще попробовать: работать горизонтальными сечениями: т.е берем сечение, определяем начало-конец, середина - есть искомая точка. Дальше спускаемся на след. строку, след. сечение и т.д. Сечение - это непрерывная строка пикселов переднего плана. На экстремумах будут некоторые проблемы (нужно менять нарправление сканирования верх-низ), но для такого простого случая можно справиться.

Ну преобразование Хафа я уже понял что не подойдет, ибо для прямых и окружностей там разные аккумуляторы. Как их потом соединить и понять, что это одна линия...Не понятно. Насчет скелетизации тоже читал, насколько я понимаю это один из методов векторизации растровых изображений, почитаем. Что же касается работы с сечениями, то если график будет содержать разные участки(круглые, почти горизонтальные, вертикальные) то вопрос, по какой оси проводить сечение - по X, по Y? Нашел пример по-лучшему. Будем искать алгоритм, который более или менее пристойно оцифровывает такие графики) Пошел читать про скелетизацию.

Присоединённый файл ( Кол-во скачиваний: 27 )
 moroz_graph3.gif 6,63 Kb

Это я и имела в виду, когда говорила о проблемах на экстремумах.
Но для простого случая, когда нет развилок, все просто:
работаем всегда с горизонтальными сечениями (или с вертикальными, как хошь), идем по смежности вверх или вниз. Когда упираемся следующего сечения нет (на перегибе), ищем продолжение с другой стороны. Типа того. Конечно, на широких сечениях будут возникать вопросы с локализацией точки. Скажем, если толщина линии графика больше одного пиксела, то рискуешь получить несколько отсчетов по вертикали... В этом смысле волновой алгоритм гибче - волна идет по смежности в любом направлении, но и там есть похожие проблемы на толстых линиях. Да и в реализации он сложнее. Я бы посоветовала утоньшить растр, это многие проблемы снимет.

Ну так у тебя не аналитическая функция и не прямая тем более. 

Изначально понятно, что нужно задаваться какой-то информацией о кривых. Ну взять хотя бы цвет. Это конечно позволяет разделить два графика, но опять же в том вместе, где они сходятся вообще невозможно в общем случае сказать закачивается там синий график или просто на него накладывается красный.

Так что задача ваша в общем случае неразрешима. 

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

Возможно не совсем правильно описал, что будет требоваться от алгоритма (программы). От него не надо что бы он находил именно синусойды, прямые линии или же окружности. Нужно лишь что бы пробежавших по растру, он создал массив пар точек (X/Y), которые составляют скелет графика. 

Что же касательно того, что задача неразрешима. Существуют бесплатные программы, которые решают ,пускай и не всегда, задачу оцифровки графиков. В связи с этим и возникла мысль, что должен быть какой то алгоритм, ведь не могли же все они быть написаны с нуля и использовать разные алгоритмы. 


p.s. Начал читать про скелетизацию, это ли вы имели ввиду Earnest? Статья


Это сообщение отредактировал(а) Wilko - 22.4.2010, 14:06

И как они оцифровывают приведённый пример?

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

Видела я эту статью. Там мало конкретики для реализации, но основы объясняет, да. 
В общем, это тоже метод. Но под утоньшением я имела в виду несколько другое: получение тонкого растра. Т.е. скелет, но растровый. При его векторизации проблем сопряжениями и поворотами гораздо меньше

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

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


Если цвет хорошо делится, то не вопрос - отдельно. Место пересечения (смешения цвета) остается дыркой и потом сшивается. Например.
Вообще говоря, получить скелет хорошей растровой линии (или кучи линий) не очень сложно. Да, это не очень простой в реализации алгоритм, но вполне формальный, и потому проблемы чисто технические - не соврать при реализации. И получим мы, скажем, граф, состоящий из отдельных линий. А вот что потом с этим добром делать - сложно формализовать в общем случае. В простом случае, как приведенные графики - нет проблем. А представьте, например, топографическую карту... В общем, насколько я знаю, эта задача сейчас решается поэтапно, с привлечением дополнительной информации на каждом этапе. И не совсем автоматически. Скажем, человек говорит: ага, вижу синенькие линии векторизовались. И сказал он, что это реки... И сшивать их надо так-то и так-то (выделять главное русло, пришивать к нему притоки и т.д.) Но сначала хорошо бы удалить все, что не реки. Штрихи болот, к примеру...

В общем, Wilko, задача написания программы для векторизации даже простых графиков - далеко не на один день, так что готовься... 

Если рассматривать distance transform какой метрикой посоветуете пользоваться для скелитизации??

Я использовала самые простые: 2,3 и 3,4. Причем никакой существенной разницы не наблюдала. 
Также не вижу смысла заморачиваться гексогональной решеткой или метриками, дающими лучшее приближение к Евклиду.
Наверное, разница есть, но только не для реальных - довольно-таки грязных растров. 

Всем привет!

Это ржачно, но мне предстоит сделать минимально живучую версию http://potrace.sourceforge.net/potrace.pdf на С# для строго Black & White растров (это планы этажей в зданиях, так что понятная геометрия). 
Мне интересно: я ведь не первый это делаю?


Это сообщение отредактировал(а) podval - 29.9.2015, 00:42