Есть ли обратный алгоритм

← →
AM (2002-10-10 10:45) [0]

Доброго времени суток! Подскажите пожалуйста, вот есть множество алгоритмов перевода вектора в растор, имеется ввиду перевод векторной прямой в растровое множество точек.
Т. е. алгоритмы показывающие какие именно точки надо отобразить между двумя точками, чтобы отобразилась прямая соединяющая эти две точки. (не помню точные их названия, но кажется Кируса-Бека).

А есть вот обратный алгоритм? Вот у меня есть линия (точнее в формате bmp множество точек идущих друг за другом ). Мне надо разбить ее на ломанную, а точнее получить последовательное множество точек, которые если соединить последовательно приямыми линиями (согласно вышеописанному алгоритму) и получится эта линия.

Если есть какие-нибудь соображени, ссылки по этой тематике, буду благодарен.

← →
MBo © (2002-10-10 13:44) [1]

ищешь точку, отличающуюся по цвету от фона, рекурсивно смотришь соседние, если есть, идешь дальше, занося в список.

← →
AM (2002-10-10 14:20) [2]

Это то я делаю. Но задача чуть-чуть в другом:
Есть белый фон по нему проведена линия (толщиной в один пиксель) черного цвета. Линия - не прямая, а ломанная, а потачнее кривая Бизье.
Я делаю также как Вы ( MBo © (10.10.02 13:44) ) сказали:
"ищешь точку, отличающуюся по цвету от фона, рекурсивно смотришь соседние, если есть, идешь дальше, занося в список."

Но мне хочется данные не хранить в виде такого большого массива. Изображение ОЧЕНЬ большое, наборы точек получаются очень большими. Мне хочется хранить набор точек, которые я потом бы потом соединить с помощью алгоритма (Кируса-Бека)
прямыми линиями и получить свою кривую.
1) Ведь это все в растре и любую кривую можно разделить на множество ломанных.
2)А множество ломанных - это множество отрезком.
3) А отрезок можно определить двумя точками.
Зачем тогда хранить все точки?
А вот как это разделение на отрезки сделать?

ХХХХХХХХХХХХХХХХХХХ - прямая

XX
XX
XX - тоже прямая
XX
XX
XX
X
XX
Х
XХ - тоже прямая
X
XX
X

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

← →
MBo © (2002-10-10 14:35) [3]

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

← →
Pumpkin (2002-10-10 14:35) [4]

> Надо сделать очень сложный анализ кривой.
Этого не могут по человечески делать даже такие монстры как Adobe или Corel (StreamLine и OCRTrace).
Апроксимируй ломаной. Из своего большого множества точек выкинь точки, в которых изгиб небольшой (величина угла A[N-1]A[N]A[N+1])
Потом построишь сплайн напр.

← →
Reanimator © (2002-10-14 16:55) [5]

Если эта прямая была ниросована чем то типа DrawLine, то пойдёт то что сказал МВо. Иначе народ любит для этого дела преобразование Хафа, у нас парень целый дисер по нему написал %)

← →
AM (2002-10-14 17:53) [6]

>> Reanimator © (14.10.02 16:55)

А если не сложно, где можно найти информацию о "преобразование Хафа"?
Поискал на Yandex, Rambler - нашел только статьи, которые ссылаются на это самое преобразование, либо на самого Хафа. А вот по сути, описание самого преобразования нигде нет.

Если кто знает литературу, ссылкы... буду презнателен.

← →
KA_ (2002-10-16 08:56) [7]

Посмотри Intel Image Processing Library и Intel Computer Vision Library: это библиотеки по предобработке и распознаванию изображений. Там есть функции поиска контуров (а ведь прямая - это незамкнутый контур :) ) и еще много чего хорошего. Но желательно иметь минимальные знания по этой области. Есть там и преобразование Хафа (Хоуга).
Вот ссылки:
http://www.intel-inside.com.ru/support/performancetools/libraries/ipl/index.htm
http://sourceforge.net/project/showfiles.php?group_id=22870

← →
KA_ (2002-10-16 09:50) [8]

По твоей задаче: насколько я понимаю картинка не зашумлена - предобработка практически отпадает. Картинка двухцветная - можно сразу выделять линии. Мне кажется разумно использовать цапной алгоритм (посмотри описалово к Intel CVL). Или какой-нибудь из алгоритмов поиска границ. Для цепного алгоритма толстые линии в несколько пикселов - плохо. Но можно использовать например медианный фильтр - и получить тонкие линии. А уж потом искать их.
Вот еще ссылки:
http://alife-soft.narod.ru
http://documents.cfar.umd.edu/
http://www.cse.msu.edu/prip/
http://cgm.cs.mcgill.ca/~godfried/teaching/pr-web.html
http://www-2.cs.cmu.edu/afs/cs/project/cil/ftp/html/vision.html
http://www.ph.tn.tudelft.nl/PRInfo.html

← →
KA_ (2002-10-16 09:52) [9]

← →
AM (2002-10-16 12:28) [10]

KA_, спасибо большое за ссылки и информацию.

← →
KA_ (2002-10-16 15:41) [11]

Sorry, коннект подводит и рученки трясутся.
Не цапной, а цепной алгоритм.
По преобразованию Хоуга (он же Хаф) могу кинуть статейку про использование одними японцами (они в этом деле большие доки) при поиске линий на картах дорог. Там используются и описаны и другие алгоритмы, кот. реализуются без сложной математики. И еще могу статью про само преобразование, где описана вся математика, ее физический смысл и куда ее можно применить - на русском. Нарисуй свое мыло или мыль мне.

← →
AM (2002-10-16 16:20) [12]

>> могу кинуть статейку
Было бы очень классно, KA_!

мой адрес:
arayvazyan@yahoo.com

заранее благодарен!

> KA_ (16.10.02 15:41)

Если несложно, то намыльте и мне, я примерно ту же проблему решаю. Заранее спасибо!

← →
KA_ (2002-10-17 17:55) [14]

По книгам:
на русском выходили -
Пратт (или Прэтт) "Цифровая обработка изображений" - прямо-таки библия (W.K.Pratt Digital Image Processing),
Чен, По, Ванг Распознавание образов и машинное зрение (Chen, Pau, Wang Pattern Recognition and Computer Vision) - оч.хорошая книга,
Хорн Зрение роботов (Horn Robot Vision) - не читал,
Розенфельд Цифровая обработка изображений - тоже класс, но без деталей,
и вроде Фукунага - название не помню.

Есть ли обратный алгоритм Найти похожие ветки