Растр ==> Вектор
От: Mika Soukhov Stock#
Дата: 26.09.03 14:22
Оценка:
Есть растровое изображение с изолиниями. Нужно эти самые изолинии сконвертировать в векторное представление (ну, грубо говоря, массив координат). Как бы мне это лучше сделать. Понимаю, что задачка довольно таки сложнаю, поэтому и не жду прямого ответа. Ждем-с прямых линков Почитать, поднатареть, обматериться (приобрести матерые вид ) я всегда люблю.

Заранее благодарю.
Re: Растр ==> Вектор
От: uzzy Россия  
Дата: 27.09.03 03:12
Оценка: 6 (1)
Здравствуйте, Mika Soukhov, Вы писали:

MS>Есть растровое изображение с изолиниями. Нужно эти самые изолинии сконвертировать в векторное представление (ну, грубо говоря, массив координат). Как бы мне это лучше сделать. Понимаю, что задачка довольно таки сложнаю, поэтому и не жду прямого ответа. Ждем-с прямых линков Почитать, поднатареть, обматериться (приобрести матерые вид ) я всегда люблю.


Возможно поможет первоначальное пропускание растра через фильтр, параметры фильтра скорее всего придется подбирать, хотя может и нет
про фильтры можно узнать поискав "цифровая обработка сигналов (изображений)", возможно даже по этому поиску что-нибудь будет и по твоей задаче

MS>Заранее благодарю.
... << RSDN@Home 1.1 beta 2 >>
Re: Растр ==> Вектор
От: Рома Мик Россия http://romamik.com
Дата: 27.09.03 12:58
Оценка: 24 (2)
Здравствуйте, Mika Soukhov, Вы писали:

MS>Есть растровое изображение с изолиниями. Нужно эти самые изолинии сконвертировать в векторное представление (ну, грубо говоря, массив координат). Как бы мне это лучше сделать. Понимаю, что задачка довольно таки сложнаю, поэтому и не жду прямого ответа. Ждем-с прямых линков Почитать, поднатареть, обматериться (приобрести матерые вид ) я всегда люблю.

Я так понял, что есть картинка и на ней некие линии их надо выделить и представить именно как линии.

Я бы сделал так. Перебираем все точки в изображении. Если в некотором небольшом радиусе от точки больше чем некоторое количество точек у которых больше чем на некую величину отличается хотя бы один компонент цвета, то заливаем эту точку, но не просто, а с некотрым допуском. Потом полученную область преобразуем в линию. Для этого, например, разбиваем область на кусочки и центры кусочков соединяем.
... << RSDN@Home 1.1 beta 2 >>
Re[2]: Растр ==> Вектор
От: uzzy Россия  
Дата: 27.09.03 16:44
Оценка: 18 (1)
Здравствуйте, uzzy, Вы писали:

Здесь представлено исходное изобаржение, и 2 результата применения одного и того же вида фильтров, кажется он имеет название "выделение контуров"). По идее что-то подобное позволит оставить на растре только изолинии, а вот что потом делать?
... << RSDN@Home 1.1 beta 2 >>
Re[3]: Растр ==> Вектор
От: Mika Soukhov Stock#
Дата: 27.09.03 19:54
Оценка:
Здравствуйте, uzzy, Вы писали:

U>Здравствуйте, uzzy, Вы писали:


U>Здесь представлено исходное изобаржение, и 2 результата применения одного и того же вида фильтров, кажется он имеет название "выделение контуров"). По идее что-то подобное позволит оставить на растре только изолинии, а вот что потом делать?


Я что то не уверен в данном подходе. На сколько я понял, "выделение контуров" годиться только для полноценных изображение, у меня же уже фактически контуры. Так же на изображении уже присутствуют изолинии. Единственное что, так это там могут располагаться различные побочные элементы (то скупая засохшая слеза пьяного геолога, положившего под сканер свое творение). Твой же алгоритм сделает только то, что обьведет эти сужности, а так же может и удалить не нужные изолинии.
Re[4]: Растр ==> Вектор
От: Рома Мик Россия http://romamik.com
Дата: 27.09.03 20:44
Оценка: +1
Здравствуйте, Mika Soukhov, Вы писали:

Кстати если бы ты положил пример картинки, то было бы гораздо понятнее что требуется...
... << RSDN@Home 1.1 beta 2 >>
Re: Растр ==> Вектор
От: piAnd Россия  
Дата: 28.09.03 08:13
Оценка: 12 (1)
Здравствуйте, Mika Soukhov, Вы писали:

MS>Есть растровое изображение с изолиниями. Нужно эти самые изолинии сконвертировать в векторное представление (ну, грубо говоря, массив координат). Как бы мне это лучше сделать. Понимаю, что задачка довольно таки сложнаю, поэтому и не жду прямого ответа. Ждем-с прямых линков Почитать, поднатареть, обматериться (приобрести матерые вид ) я всегда люблю.


MS>Заранее благодарю.

Я бы попробовал на MathCad-е отладить алгоритм.
Сначала преобразовать изображение к монохромному(2 цвета) с помощью какого-нибудь фильтра, чтобы исключить случайные всплески и незначительные перепады яркости(смотреть в сторону дифференцирующего фильтра или что-то вроде оператора Собеля и ему подобных).
После чего у нас имеется набор точек одного цвета.
Далее ищем на изображении все точки, расстояния между которыми равны 1 пикселю(вообще определяется качеством исходной картинки и разрешением) — это точки одной изолинии.
Дальше среди выбранных точек изолинии с некоторым шагом (если мин растояние между точками 1 пиксел, то скажем возьмем шаг=10пикселей) ищем точки растояние между которыми =шагу.
Полученный набор точек есть набор узлов изолинии, который собстно и есть векторное представление...
Это просто идея решить задачу "в лоб"
К недостаткам можно отнести —
1) только хорошая исходная картинка даст мин растояние в 1 пиксел между соседними точками.
2) если ширина изолинии больше 1 пикс., то шаг узлов должен быть больше 1 пикселя, что уменьшает точность векторного представления...
Возможно уже существуют алгоритмы, только ссылок незнаю(((
Re[5]: Растр ==> Вектор
От: Mika Soukhov Stock#
Дата: 28.09.03 08:26
Оценка:
Здравствуйте, Рома Мик, Вы писали:

РМ>Здравствуйте, Mika Soukhov, Вы писали:


РМ>Кстати если бы ты положил пример картинки, то было бы гораздо понятнее что требуется...


Re: Растр ==> Вектор
От: klovetski Россия  
Дата: 28.09.03 17:53
Оценка: 6 (1)
Здравствуйте, Mika Soukhov, Вы писали:

MS>Есть растровое изображение с изолиниями. Нужно эти самые изолинии сконвертировать в векторное представление


Попробуй заглянуть на здесь. Там есть демонстрационка Grafula3 для оцифровки графиков и список программ конкурентов. Может и наткнешься на что-то интересное.

Есть еще Graph2Digit
от Вячеслава Плиско.
e-mail: plsoft@narod.ru
http:\\plsoft.narod.ru, http:\\plsoft.chat.ru

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


Константин
Re: Растр ==> Вектор
От: Кирилл Осенков Украина
Дата: 28.09.03 18:40
Оценка: 20 (3)
Adobe Streamline 4.0 занимается векторизацией растровых изображений. Правда там вряд ли есть описание

А что касается алгоритма, мне вспомнились недавние обсуждения Поиска связанных областей в двухмерном массиве
Автор: golyakov
Дата: 29.08.03
. Только там была 4-связность, т.е. соседями считались пикселы строго слева/справа/снизу/сверху, а в твоей задаче нужна 8-связность — т.е. соседями считаются еще и диагональные клетки.

Так что если не вдаваться в детали план может быть такой:

  1. Убить все дефекты на исходном изображении и поприменять всякие фильтры.
  2. Найти все компоненты 8-связности, т.е. такие наборы пикселей, что от каждого пикселя из набора можно перебраться до любого другого пикселя из этого набора, перемещаясь по соседям (8 направлений). Это можно сделать некоторой модификацией алгоритма построчного сканирования (могу дать код на VB.NET). Здесь другая проблема — всякие артефакты, разрывы линий на рисунке и т.д.
  3. В каждой компоненте связности постараться упорядочить пикселы, т.е. выстроить по цепочке — у большинства пикселей два соседа. Получится ломаная.
  4. Пройтись по ломаной — если какой-то из пикселей находится точно посередине между своими соседями — убить
  5. Интерполировать эту ломаную, или приблизить кривыми Безье или еще чем удобнее. Т.е. получить кривые в требуемом представлении (главное добраться хотя бы до ломаных — уже дальше есть наработанная математика — интерполяция и т.д.)

Сорри за убогость, все чем мог...
Re: Растр ==> Вектор
От: zrs  
Дата: 29.09.03 06:42
Оценка: 6 (1)
Здравствуйте, Mika Soukhov, Вы писали:

AutoTrace — converts bitmap to vector graphics http://autotrace.sourceforge.net/
Софт с исходниками и судя по скриншотам вполне достойный. Кроме того есть ссылки на что почитать.
... << RSDN@Home 1.1 beta 2 >>
Re[6]: Растр ==> Вектор
От: Рома Мик Россия http://romamik.com
Дата: 29.09.03 09:18
Оценка: 12 (2)
Здравствуйте, Mika Soukhov, Вы писали:

MS>

Ну для такой-то картинки всякие извраты можно считать лишними. Выделяем связные области черного цвета, считая соседними для точки 8 или даже 16 точек.
Для каждой связной области пытаемся представить ее как линию. Т.е. от любой точки двигаемся по этой связной области стараясь делать как можно более маленькие повороты, одновременно удаляя проходимые и находящиеся сбоку/сзади по ходу движения из области.
Можно сразу пытаться строить квадратичную кривую, т.е. от произвольной точки подбирать ее параметры, так чтобы кривая как можно дальше ( или просто дальше, чем сколько-то ) оставалась в пределах области. Следующую кривую надо уже строить так чтобы первые производные у нее были равны предыдущим.
... << RSDN@Home 1.1 beta 2 >>
Re[2]: Растр ==> Вектор
От: Mika Soukhov Stock#
Дата: 29.09.03 19:27
Оценка:
Здравствуйте, piAnd, Вы писали:

A> Сначала преобразовать изображение к монохромному(2 цвета) с помощью какого-нибудь фильтра, чтобы исключить случайные всплески и незначительные перепады яркости(смотреть в сторону дифференцирующего фильтра или что-то вроде оператора Собеля и ему подобных).


Можно по подробнее про алгоритм?
Re[7]: Растр ==> Вектор
От: Mika Soukhov Stock#
Дата: 29.09.03 19:52
Оценка:
Здравствуйте, Рома Мик, Вы писали:

Кстати, заметил еще такие штуки как прямей линии. Я вот думаю, их бы тоже надобно отфильтровать. Как бы мне это определить? Максимальным углом отклонения по всей ломаной пройтись и если не превышает заданный уровень, то стереть. А есть еще какой нить способ? Что то мне подсказывает что можно и градиентой измерить. Но тогда нужно уравнение составить. Туда ли я копаю?
Re[2]: Растр ==> Вектор
От: Mika Soukhov Stock#
Дата: 29.09.03 19:52
Оценка:
Здравствуйте, Кирилл Осенков, Вы писали:

КО>
  • Интерполировать эту ломаную, или приблизить кривыми Безье или еще чем удобнее. Т.е. получить кривые в требуемом представлении (главное добраться хотя бы до ломаных — уже дальше есть наработанная математика — интерполяция и т.д.)

    Кстати, мне как раз нужно их перевести в кривые Безье. А как это сделать? Я раньше шел наоборот
  • Re[8]: Растр ==> Вектор
    От: Рома Мик Россия http://romamik.com
    Дата: 29.09.03 20:37
    Оценка:
    Здравствуйте, Mika Soukhov, Вы писали:

    MS>Здравствуйте, Рома Мик, Вы писали:


    MS>Кстати, заметил еще такие штуки как прямей линии. Я вот думаю, их бы тоже надобно отфильтровать. Как бы мне это определить? Максимальным углом отклонения по всей ломаной пройтись и если не превышает заданный уровень, то стереть. А есть еще какой нить способ? Что то мне подсказывает что можно и градиентой измерить. Но тогда нужно уравнение составить. Туда ли я копаю?

    Ну проверить является ли некая область прямой очень просто, на через две достаточно удаленные друг от друга точки области провести прямую и проверить, что все точки области лежат недалеко от этой прямой.
    ... << RSDN@Home 1.1 beta 2 >>
    Re[3]: Растр ==> Вектор
    От: Рома Мик Россия http://romamik.com
    Дата: 29.09.03 21:19
    Оценка:
    Здравствуйте, Mika Soukhov, Вы писали:

    MS>Здравствуйте, Кирилл Осенков, Вы писали:


    КО>>
  • Интерполировать эту ломаную, или приблизить кривыми Безье или еще чем удобнее. Т.е. получить кривые в требуемом представлении (главное добраться хотя бы до ломаных — уже дальше есть наработанная математика — интерполяция и т.д.)

    MS>Кстати, мне как раз нужно их перевести в кривые Безье. А как это сделать? Я раньше шел наоборот

    Чего-то я все эти дела подзабыл, Безье — это кривая у которой заданы конечные точки через которые она проходит и некие вектора в этих точках, которых она будет касаться в этих точках?

    Я бы строил так: берем крайнюю точку, находим направление кривой в ней идем вдоль линии и в каждой точке находим направление касательной к кривой, пытаемся строить кривую ( видимо придется подгонять как-то длины векторов или обойтись вторым порядком, что было бы совсем неплохим выбором ИМХО ), пока кривая лежит недалеко от промежуточных точек идем дальше, потом строим следующий отрезок и т.д. пока не дойдем до конца...
    ... << RSDN@Home 1.1 beta 2 >>
  • Re[4]: Подзадача: цепочка пикселов => кривая Безье
    От: Кирилл Осенков Украина
    Дата: 30.09.03 14:02
    Оценка: 44 (3)
    РМ>Чего-то я все эти дела подзабыл, Безье — это кривая у которой заданы конечные точки через которые она проходит и некие вектора в этих точках, которых она будет касаться в этих точках?
    Ага — две точки — концы, еще две — направляющие точки (направления касательных в концах), причем чем дальше направляющая точка от соответствующего конца кривой — тем плотнее прилегает кривая к касательному вектору в точке касания.

    На практике считается так:

    cx=3*(x1-x0)
    bx=3*(x2-x1)-cx
    ax=x3-x0-bx-cx
    
    cy=3*(y1-y0)
    by=3*(y2-y1)-cy
    ay=y3-y0-by-cy
    
    x(t)=ax*t^3+bx*t^2+cx*t+x0
    y(t)=ay*t^3+by*t^2+cy*t+y0
    
    t из [0;1]


    РМ>Я бы строил так: берем крайнюю точку, находим направление кривой в ней идем вдоль линии и в каждой точке находим направление касательной к кривой, пытаемся строить кривую ( видимо придется подгонять как-то длины векторов или обойтись вторым порядком, что было бы совсем неплохим выбором ИМХО ), пока кривая лежит недалеко от промежуточных точек идем дальше, потом строим следующий отрезок и т.д. пока не дойдем до конца...

    Присоединяюсь. Т.е. если предположить, что мы попали в сказку и кто-то подарил нам такую цепочку пикселов (массив пикселов от 1 до n, причем у каждого пиксела кроме концов ровно два соседа (если брать 8-связность)), то задача сводится к тому, чтобы откусывать от цепочки пикселей по одной кривой Безье, пока ее всю не съедим

    А откусывать наверное так. Для описания кривой Безье нам нужны восемь вещественных параметров. Один конец кривой нам известен — пиксел номер 1. Это уже два параметра.
    Направление касательной в первом конце можно посчитать — это третий параметр.

    Теперь в цикле по k от 2 до n пробуем взять пиксел номер k в качестве второго конца кривой и на каждом шаге k получаем еще три параметра.

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

    Кривизна ломаной в ее вершине — это ориентированный угол между двумя выходящими из этой вершины звеньями. А теперь вспомним, что у нас очень выгодная ломаная — дискретная. Эта кривизна в каждом пикселе может принимать только 5 (ну от силы 7) значений. Нарисуйте цепочку из трех пикселов и станет ясно, почему. Поэтому отслеживать изменения знака кривизны цепочки должно быть несложно (надо только наловчиться считать кривизну — ее придется как-то усреднять, потому что помните, какие зубчики в алгоритме Брезенхема — то поворот влево на 90°, то вправо).

    В итоге, чтобы восстановить кривую по цепочке от первого до k-го пиксела недостает два параметра — удаление направляющих точек от соответствующих концов кривой. Их надо находить так, чтобы кривая при рендеринге лучше всего покрывала цепочку от 1 до k. Как это сделать, я сейчас не скажу, т.к. не знаю Но думаю, что каким-то перебором они и найдутся (перебор небольшой, дискретное двумерное пространство, тем более искомые расстояния ограничены сверху).

    Слабые места в этой писанине такие:


    О блин... Одни слабые места
    Re[5]: Подзадача: цепочка пикселов => кривая Безье
    От: Рома Мик Россия http://romamik.com
    Дата: 30.09.03 15:03
    Оценка: 8 (1) +1
    Здравствуйте, Кирилл Осенков, Вы писали:

    РМ>>Я бы строил так: берем крайнюю точку, находим направление кривой в ней идем вдоль линии и в каждой точке находим направление касательной к кривой, пытаемся строить кривую ( видимо придется подгонять как-то длины векторов или обойтись вторым порядком, что было бы совсем неплохим выбором ИМХО ), пока кривая лежит недалеко от промежуточных точек идем дальше, потом строим следующий отрезок и т.д. пока не дойдем до конца...

    КО>попали в сказку и кто-то подарил нам такую цепочку пикселов (массив пикселов от 1 до n, причем у каждого пиксела кроме концов ровно два соседа (если брать 8-связность)),
    Ну составить такую цепочку было бы не проблематично, но ИМХО она и не нужна. И можно брать больше чем 8-связности.

    КО>

    КО>О блин... Одни слабые места

    Ну, это пессимистичный взгляд — люди и не такое оцифровывают...

    Кстати не обязательно использовать именно Безье. Можно и квадратичными кривыми обойтись в данном случае, а считать и перебирать уже меньше.
    ... << RSDN@Home 1.1 beta 2 >>
    Re[6]: Подзадача: цепочка пикселов => кривая Безье
    От: Mika Soukhov Stock#
    Дата: 30.09.03 16:15
    Оценка:
    Здравствуйте, Рома Мик, Вы писали:

    Народ, можно как нить по проще и понятнее (без воды ). Я математику уже стал поздзабывать, так, плиз, еще и по доходчивее
    Подождите ...
    Wait...
    Пока на собственное сообщение не было ответов, его можно удалить.