Есть растровое изображение с изолиниями. Нужно эти самые изолинии сконвертировать в векторное представление (ну, грубо говоря, массив координат). Как бы мне это лучше сделать. Понимаю, что задачка довольно таки сложнаю, поэтому и не жду прямого ответа. Ждем-с прямых линков Почитать, поднатареть, обматериться (приобрести матерые вид ) я всегда люблю.
Здравствуйте, Mika Soukhov, Вы писали:
MS>Есть растровое изображение с изолиниями. Нужно эти самые изолинии сконвертировать в векторное представление (ну, грубо говоря, массив координат). Как бы мне это лучше сделать. Понимаю, что задачка довольно таки сложнаю, поэтому и не жду прямого ответа. Ждем-с прямых линков Почитать, поднатареть, обматериться (приобрести матерые вид ) я всегда люблю.
Возможно поможет первоначальное пропускание растра через фильтр, параметры фильтра скорее всего придется подбирать, хотя может и нет
про фильтры можно узнать поискав "цифровая обработка сигналов (изображений)", возможно даже по этому поиску что-нибудь будет и по твоей задаче
MS>Заранее благодарю.
Здравствуйте, Mika Soukhov, Вы писали:
MS>Есть растровое изображение с изолиниями. Нужно эти самые изолинии сконвертировать в векторное представление (ну, грубо говоря, массив координат). Как бы мне это лучше сделать. Понимаю, что задачка довольно таки сложнаю, поэтому и не жду прямого ответа. Ждем-с прямых линков Почитать, поднатареть, обматериться (приобрести матерые вид ) я всегда люблю.
Я так понял, что есть картинка и на ней некие линии их надо выделить и представить именно как линии.
Я бы сделал так. Перебираем все точки в изображении. Если в некотором небольшом радиусе от точки больше чем некоторое количество точек у которых больше чем на некую величину отличается хотя бы один компонент цвета, то заливаем эту точку, но не просто, а с некотрым допуском. Потом полученную область преобразуем в линию. Для этого, например, разбиваем область на кусочки и центры кусочков соединяем.
Здесь представлено исходное изобаржение, и 2 результата применения одного и того же вида фильтров, кажется он имеет название "выделение контуров"). По идее что-то подобное позволит оставить на растре только изолинии, а вот что потом делать?
Здравствуйте, uzzy, Вы писали:
U>Здравствуйте, uzzy, Вы писали:
U>Здесь представлено исходное изобаржение, и 2 результата применения одного и того же вида фильтров, кажется он имеет название "выделение контуров"). По идее что-то подобное позволит оставить на растре только изолинии, а вот что потом делать?
Я что то не уверен в данном подходе. На сколько я понял, "выделение контуров" годиться только для полноценных изображение, у меня же уже фактически контуры. Так же на изображении уже присутствуют изолинии. Единственное что, так это там могут располагаться различные побочные элементы (то скупая засохшая слеза пьяного геолога, положившего под сканер свое творение). Твой же алгоритм сделает только то, что обьведет эти сужности, а так же может и удалить не нужные изолинии.
Здравствуйте, Mika Soukhov, Вы писали:
MS>Есть растровое изображение с изолиниями. Нужно эти самые изолинии сконвертировать в векторное представление (ну, грубо говоря, массив координат). Как бы мне это лучше сделать. Понимаю, что задачка довольно таки сложнаю, поэтому и не жду прямого ответа. Ждем-с прямых линков Почитать, поднатареть, обматериться (приобрести матерые вид ) я всегда люблю.
MS>Заранее благодарю.
Я бы попробовал на MathCad-е отладить алгоритм.
Сначала преобразовать изображение к монохромному(2 цвета) с помощью какого-нибудь фильтра, чтобы исключить случайные всплески и незначительные перепады яркости(смотреть в сторону дифференцирующего фильтра или что-то вроде оператора Собеля и ему подобных).
После чего у нас имеется набор точек одного цвета.
Далее ищем на изображении все точки, расстояния между которыми равны 1 пикселю(вообще определяется качеством исходной картинки и разрешением) — это точки одной изолинии.
Дальше среди выбранных точек изолинии с некоторым шагом (если мин растояние между точками 1 пиксел, то скажем возьмем шаг=10пикселей) ищем точки растояние между которыми =шагу.
Полученный набор точек есть набор узлов изолинии, который собстно и есть векторное представление...
Это просто идея решить задачу "в лоб"
К недостаткам можно отнести —
1) только хорошая исходная картинка даст мин растояние в 1 пиксел между соседними точками.
2) если ширина изолинии больше 1 пикс., то шаг узлов должен быть больше 1 пикселя, что уменьшает точность векторного представления...
Возможно уже существуют алгоритмы, только ссылок незнаю(((
Здравствуйте, Рома Мик, Вы писали:
РМ>Здравствуйте, Mika Soukhov, Вы писали:
РМ>Кстати если бы ты положил пример картинки, то было бы гораздо понятнее что требуется...
Здравствуйте, Mika Soukhov, Вы писали:
MS>Есть растровое изображение с изолиниями. Нужно эти самые изолинии сконвертировать в векторное представление
Попробуй заглянуть на здесь. Там есть демонстрационка Grafula3 для оцифровки графиков и список программ конкурентов. Может и наткнешься на что-то интересное.
Есть еще Graph2Digit
от Вячеслава Плиско.
e-mail: plsoft@narod.ru
http:\\plsoft.narod.ru, http:\\plsoft.chat.ru
Этой я пользовался. Если убрать текст и цифры на твоих графиках, то она, может быть и справится. Я, правда, пробовал ее только для однозначных функций, понравилось.
. Только там была 4-связность, т.е. соседями считались пикселы строго слева/справа/снизу/сверху, а в твоей задаче нужна 8-связность — т.е. соседями считаются еще и диагональные клетки.
Так что если не вдаваться в детали план может быть такой:
Убить все дефекты на исходном изображении и поприменять всякие фильтры.
Найти все компоненты 8-связности, т.е. такие наборы пикселей, что от каждого пикселя из набора можно перебраться до любого другого пикселя из этого набора, перемещаясь по соседям (8 направлений). Это можно сделать некоторой модификацией алгоритма построчного сканирования (могу дать код на VB.NET). Здесь другая проблема — всякие артефакты, разрывы линий на рисунке и т.д.
В каждой компоненте связности постараться упорядочить пикселы, т.е. выстроить по цепочке — у большинства пикселей два соседа. Получится ломаная.
Пройтись по ломаной — если какой-то из пикселей находится точно посередине между своими соседями — убить
Интерполировать эту ломаную, или приблизить кривыми Безье или еще чем удобнее. Т.е. получить кривые в требуемом представлении (главное добраться хотя бы до ломаных — уже дальше есть наработанная математика — интерполяция и т.д.)
Сорри за убогость, все чем мог...
AutoTrace — converts bitmap to vector graphics http://autotrace.sourceforge.net/
Софт с исходниками и судя по скриншотам вполне достойный. Кроме того есть ссылки на что почитать.
Здравствуйте, Mika Soukhov, Вы писали:
MS>
Ну для такой-то картинки всякие извраты можно считать лишними. Выделяем связные области черного цвета, считая соседними для точки 8 или даже 16 точек.
Для каждой связной области пытаемся представить ее как линию. Т.е. от любой точки двигаемся по этой связной области стараясь делать как можно более маленькие повороты, одновременно удаляя проходимые и находящиеся сбоку/сзади по ходу движения из области.
Можно сразу пытаться строить квадратичную кривую, т.е. от произвольной точки подбирать ее параметры, так чтобы кривая как можно дальше ( или просто дальше, чем сколько-то ) оставалась в пределах области. Следующую кривую надо уже строить так чтобы первые производные у нее были равны предыдущим.
Здравствуйте, piAnd, Вы писали:
A> Сначала преобразовать изображение к монохромному(2 цвета) с помощью какого-нибудь фильтра, чтобы исключить случайные всплески и незначительные перепады яркости(смотреть в сторону дифференцирующего фильтра или что-то вроде оператора Собеля и ему подобных).
Кстати, заметил еще такие штуки как прямей линии. Я вот думаю, их бы тоже надобно отфильтровать. Как бы мне это определить? Максимальным углом отклонения по всей ломаной пройтись и если не превышает заданный уровень, то стереть. А есть еще какой нить способ? Что то мне подсказывает что можно и градиентой измерить. Но тогда нужно уравнение составить. Туда ли я копаю?
Здравствуйте, Кирилл Осенков, Вы писали:
КО>Интерполировать эту ломаную, или приблизить кривыми Безье или еще чем удобнее. Т.е. получить кривые в требуемом представлении (главное добраться хотя бы до ломаных — уже дальше есть наработанная математика — интерполяция и т.д.)
Кстати, мне как раз нужно их перевести в кривые Безье. А как это сделать? Я раньше шел наоборот
Здравствуйте, Mika Soukhov, Вы писали:
MS>Здравствуйте, Рома Мик, Вы писали:
MS>Кстати, заметил еще такие штуки как прямей линии. Я вот думаю, их бы тоже надобно отфильтровать. Как бы мне это определить? Максимальным углом отклонения по всей ломаной пройтись и если не превышает заданный уровень, то стереть. А есть еще какой нить способ? Что то мне подсказывает что можно и градиентой измерить. Но тогда нужно уравнение составить. Туда ли я копаю?
Ну проверить является ли некая область прямой очень просто, на через две достаточно удаленные друг от друга точки области провести прямую и проверить, что все точки области лежат недалеко от этой прямой.
Здравствуйте, Mika Soukhov, Вы писали:
MS>Здравствуйте, Кирилл Осенков, Вы писали:
КО>>Интерполировать эту ломаную, или приблизить кривыми Безье или еще чем удобнее. Т.е. получить кривые в требуемом представлении (главное добраться хотя бы до ломаных — уже дальше есть наработанная математика — интерполяция и т.д.)
MS>Кстати, мне как раз нужно их перевести в кривые Безье. А как это сделать? Я раньше шел наоборот
Чего-то я все эти дела подзабыл, Безье — это кривая у которой заданы конечные точки через которые она проходит и некие вектора в этих точках, которых она будет касаться в этих точках?
Я бы строил так: берем крайнюю точку, находим направление кривой в ней идем вдоль линии и в каждой точке находим направление касательной к кривой, пытаемся строить кривую ( видимо придется подгонять как-то длины векторов или обойтись вторым порядком, что было бы совсем неплохим выбором ИМХО ), пока кривая лежит недалеко от промежуточных точек идем дальше, потом строим следующий отрезок и т.д. пока не дойдем до конца...
РМ>Чего-то я все эти дела подзабыл, Безье — это кривая у которой заданы конечные точки через которые она проходит и некие вектора в этих точках, которых она будет касаться в этих точках?
Ага — две точки — концы, еще две — направляющие точки (направления касательных в концах), причем чем дальше направляющая точка от соответствующего конца кривой — тем плотнее прилегает кривая к касательному вектору в точке касания.
На практике считается так:
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. Как это сделать, я сейчас не скажу, т.к. не знаю Но думаю, что каким-то перебором они и найдутся (перебор небольшой, дискретное двумерное пространство, тем более искомые расстояния ограничены сверху).
Слабые места в этой писанине такие:
Точность поиска направления касательной к цепочке пикселей. Она очень сомнительная, потому что если в вычислении учавствует один следующий пиксел — то касательная получится направленной в одну из 4-х сторон света , если брать два следующих пиксела и усреднять — получится уже больше направлений — но проблема остается — восстановить точное направление касательной так не получится.
Мои воздушные рассуждения о том, что поиск второго конца можно прерывать после нахождения третьего обнуления кривизны.
Опять же, достаточно точно оценить кривизну в нашей дискретной задаче скорее всего не удастся.
Как искать удаление направляющих точек от концов кривой — вообще неясно (ну т.е. мне не ясно )
Да и вообще, нам никто такую идеальную цепочку не даст — будут разрывы, изломы, самопересечения, замкнутость в кольцо, толщина в 2 и больше пиксела (а толщина в два пиксела, зараза, сплошь и рядом встречается на приведенной картинке), раздавленные комары, пыль и вообще все плохо
Здравствуйте, Кирилл Осенков, Вы писали:
РМ>>Я бы строил так: берем крайнюю точку, находим направление кривой в ней идем вдоль линии и в каждой точке находим направление касательной к кривой, пытаемся строить кривую ( видимо придется подгонять как-то длины векторов или обойтись вторым порядком, что было бы совсем неплохим выбором ИМХО ), пока кривая лежит недалеко от промежуточных точек идем дальше, потом строим следующий отрезок и т.д. пока не дойдем до конца... КО>попали в сказку и кто-то подарил нам такую цепочку пикселов (массив пикселов от 1 до n, причем у каждого пиксела кроме концов ровно два соседа (если брать 8-связность)),
Ну составить такую цепочку было бы не проблематично, но ИМХО она и не нужна. И можно брать больше чем 8-связности.
КО>
КО>Точность поиска направления касательной к цепочке пикселей. Она очень сомнительная, потому что если в вычислении учавствует один следующий пиксел — то касательная получится направленной в одну из 4-х сторон света , если брать два следующих пиксела и усреднять — получится уже больше направлений — но проблема остается — восстановить точное направление касательной так не получится.
Совсем точно не найдем, найдем менее точно: кусочки кривой безье будут покороче, но все равно будут. А искать, я бы искал так: берем прямую, проходящую нашу точку и вращаем ее ( вариантов углов поворота не так много, так как прямая наша довольно коротка ), какой вариант покрывает наибольшее число точек нашей кривой, тот и есть искомое направление. Кроме того количество покрытых пикселей явно должно коррелировать с длиной вектора от первой ко второй точке. А более точного направления нам не надо, так как его просто и нет в природе, поскольку задана то нам только множество точек в которое можно вписать сколько хочешь кривых. КО>Мои воздушные рассуждения о том, что поиск второго конца можно прерывать после нахождения третьего обнуления кривизны.
ИМХО поиск можно прерывать, когда например из десяти наскоро посчитанных точек кривой две окажутся вне множетсва точек. КО>Опять же, достаточно точно оценить кривизну в нашей дискретной задаче скорее всего не удастся. КО>Как искать удаление направляющих точек от концов кривой — вообще неясно (ну т.е. мне не ясно )
Я там выше писал про покрытие точек прямой, так вот их кол-во после какого-то несложного преобразования ( возможно по таблице, полученной эмпирически ) должно дать примерное значение, вокруг которого можно искать перебором или даже оставить так. КО>Да и вообще, нам никто такую идеальную цепочку не даст — будут разрывы,
Ну использование более чем 8-связности от маленьких разрывов убережет, а большие пусть и остаются — получится две линии вместо одной и все. КО>изломы, самопересечения,
В принципе при вращении кривой эти штуки опредятся как два максимума только в одной стороне ( изломы ) два максимума с обеих сторон ( пересечения ). В изломах можно и прервать кривую, а в пересечениях продолжатьь в нужном направлении. КО>замкнутость в кольцо,
Где тут проблема? КО>толщина в 2 и больше пиксела (а толщина в два пиксела, зараза, сплошь и рядом встречается на приведенной картинке),
Не страшна. Какие проблемы она создает? КО>раздавленные комары, пыль и вообще все плохо
Комаров я там не заметил, а пыль — можно просто выкидывать слишком мелкие куски. КО>
КО>О блин... Одни слабые места
Ну, это пессимистичный взгляд — люди и не такое оцифровывают...
Кстати не обязательно использовать именно Безье. Можно и квадратичными кривыми обойтись в данном случае, а считать и перебирать уже меньше.
Здравствуйте, Mika Soukhov, Вы писали:
MS>Здравствуйте, Рома Мик, Вы писали:
MS>Народ, можно как нить по проще и понятнее (без воды ). Я математику уже стал поздзабывать, так, плиз, еще и по доходчивее
Да вроде никакой воды...
А расписать все подробно и по пунктам — это как код написать, а код написать — это за деньги и потом, или за большие деньги...
КО>>попали в сказку и кто-то подарил нам такую цепочку пикселов (массив пикселов от 1 до n, причем у каждого пиксела кроме концов ровно два соседа (если брать 8-связность)), РМ>Ну составить такую цепочку было бы не проблематично, но ИМХО она и не нужна. И можно брать больше чем 8-связности.
Если честно, я плохо представляю себе, а как без цепочки?
Было бы классно знать более-менее конструктивный способ, использующий такой массив с утолщениями и аномалиями (а не цепочку):
"толщина" массива может быть 2 и более пикселя
могут быть самопересечения и вообще всякие утолщения, как на рисунке
буквы, пятна и прочие дефекты вырезаны не были
Я бы в принципе мог выложить код, который разбивает Микину картинку на примерно такие массивы
А связности — да, согласен, я порассматривал Микину картинку через лупу — конечно, ужас Но ты прав, отчаиваться не стоит — вон люди из Adobe как умеют, не говоря уже об орлах из Abbyy... Понятно, задача решаемая. Но сложная.
Так вот. Предлагаю взять такую связность:
01110
11111
11*11
11111
01110
Здесь для пиксела "*" соседними будут считаться пикселы "1". Так мы соединим разрывы в 1 пиксел, но не более (а этого и достаточно, остальные разрывы будем считать двумя кусками).
РМ>Совсем точно не найдем, найдем менее точно: кусочки кривой безье будут покороче, но все равно будут. А искать, я бы искал так: берем прямую, проходящую нашу точку и вращаем ее ( вариантов углов поворота не так много, так как прямая наша довольно коротка ), какой вариант покрывает наибольшее число точек нашей кривой, тот и есть искомое направление. Кроме того количество покрытых пикселей явно должно коррелировать с длиной вектора от первой ко второй точке. А более точного направления нам не надо, так как его просто и нет в природе, поскольку задана то нам только множество точек в которое можно вписать сколько хочешь кривых.
Да, вообще да. Я подумал, твой фокус с прямой можно оптимизировать. Подбирать ее не нужно — ее можно восстановить по алгоритму Брезенхема. Смотри — прямая рисуется как набор горизонтальных или вертикальных отрезков примерно равной длины. Я имею ввиду:
Здесь на рисунке + это начало нашей будущей кривой, а звездочки — пикселы, которые надо покрыть. Минусом на рисунке отмечен пиксел, где цепочка начинает уклоняться от прямой. Смотрим — ага, первое время это состыкованные горизонтальные отрезки по два пиксела — вот и будем продолжать этот "паттерн" (узор), пока вписываемся в алгоритм Брезенхема. Как получим очередной отрезок неправильной длины (там, где минус — горизонтальная полоска из 1 пиксела, а не из двух) — значит цепочка отклонилась от прямой. Теперь то, что уже насчитали (от плюса до минуса) — часть нужной нам касательной прямой. Ее уравнение найти просто — она проходит через исходную точку (+ на рисунке) и угловой коэффициент — разделить разность игреков плюса и минуса на разность иксов.
КО>>Мои воздушные рассуждения о том, что поиск второго конца можно прерывать после нахождения третьего обнуления кривизны. РМ>ИМХО поиск можно прерывать, когда например из десяти наскоро посчитанных точек кривой две окажутся вне множетсва точек.
Это эмпирика. К тому же мне кажется, ты как-то скромно берешь — с таким же успехом отлично можно и отрезками приближать.
КО>>Опять же, достаточно точно оценить кривизну в нашей дискретной задаче скорее всего не удастся. КО>>Как искать удаление направляющих точек от концов кривой — вообще неясно (ну т.е. мне не ясно ) РМ>Я там выше писал про покрытие точек прямой, так вот их кол-во после какого-то несложного преобразования ( возможно по таблице, полученной эмпирически ) должно дать примерное значение, вокруг которого можно искать перебором или даже оставить так.
Да, но перебор все-таки достаточно большой...
РМ>Ну использование более чем 8-связности от маленьких разрывов убережет, а большие пусть и остаются — получится две линии вместо одной и все.
ОК.
КО>>изломы, самопересечения, РМ>В принципе при вращении кривой эти штуки опредятся как два максимума только в одной стороне ( изломы ) два максимума с обеих сторон ( пересечения ). В изломах можно и прервать кривую, а в пересечениях продолжатьь в нужном направлении.
Щас, я не понял. Что ты имеешь ввиду? Здесь можешь поподробнее плз?
КО>>замкнутость в кольцо, РМ>Где тут проблема?
ОК ОК согласен
КО>>толщина в 2 и больше пиксела (а толщина в два пиксела, зараза, сплошь и рядом встречается на приведенной картинке), РМ>Не страшна. Какие проблемы она создает?
Да понимаешь — вот у нас массив пар (x,y) от 1 до 10000. Больше ничего не знаем. И что с этим делать? Как ты поймешь, что кривую нужно направлять в "самую тонкую сторону"? И глянь на рисунок — там есть жирные перекрестки из пяти и больше таких "кишок"... Че с ними делать, я не знаю...
КО>>раздавленные комары, пыль и вообще все плохо РМ>Комаров я там не заметил, а пыль — можно просто выкидывать слишком мелкие куски.
Не знаю. Там кусок 6х6 — мы-то с тобой понимаем, что его надо выкинуть, а компу как объяснить?
КО>>О блин... Одни слабые места РМ>Ну, это пессимистичный взгляд — люди и не такое оцифровывают...
Согласен, у страха глаза велики
РМ>Кстати не обязательно использовать именно Безье. Можно и квадратичными кривыми обойтись в данном случае, а считать и перебирать уже меньше.
Ну да, это Mika просто упомянул, что ему кривые Безье нужны — а так конечно, с квадратичными проблем гораздо меньше. Дело в том, что квадратичная кривая — это кривая Безье, у которой две направляющие точки совпадают, а следовательно, находятся на пересечении двух касательных прямых в концах кривой. Все наши рассуждения остаются, более того: как только мы отыщем касательные прямые в концах с достаточной точностью, сразу появится третья точка (в точке их пересечения) — и квадратичная кривая найдена.
Есть одно из лучших собраний алгоритмов компьютерной графики: пятитомник Graphics Gems. Очень советую. И еще, говорят, что в пятом томе на стр. 323 лежит то, что тебе нужно
Кстати, я еще погуглил "vectorization line tracing algorithm" — вроде кое-что там есть, хотя алгоритма я пока не видел.
Здравствуйте, Кирилл Осенков, Вы писали:
КО>>>попали в сказку и кто-то подарил нам такую цепочку пикселов (массив пикселов от 1 до n, причем у каждого пиксела кроме концов ровно два соседа (если брать 8-связность)), РМ>>Ну составить такую цепочку было бы не проблематично, но ИМХО она и не нужна. И можно брать больше чем 8-связности. КО>Если честно, я плохо представляю себе, а как без цепочки? КО>Было бы классно знать более-менее конструктивный способ, использующий такой массив с утолщениями и аномалиями (а не цепочку):
Как определить направление в данной точке без цепочки я уже писал. Вторая проблема — это движение вдоль линии. Но имея направление, разве это проблема? Третья проблема — это выкидывать те точки, для которых кривая уже построена, так как при движении вдоль мы будем проходить не через все точки. Но в принципе и это не проблема, так как можно помечать все находящиеся рядом с проходимыми.
КО>Так вот. Предлагаю взять такую связность:
Ну это вопрос не принципиальный имхо, но я себе именно такую и представлял.
КО>Я подумал, твой фокус с прямой можно оптимизировать. Подбирать ее не нужно — ее можно восстановить по алгоритму Брезенхема.
Правильно, только надо для случаев с более чем единичной толщиной расширить. Т.е. рассамтривать не одну прямую, а множество возможных, потихоньку их одну за одной отбрасывая.
КО>>>Мои воздушные рассуждения о том, что поиск второго конца можно прерывать после нахождения третьего обнуления кривизны. РМ>>ИМХО поиск можно прерывать, когда например из десяти наскоро посчитанных точек кривой две окажутся вне множетсва точек. КО>Это эмпирика. К тому же мне кажется, ты как-то скромно берешь — с таким же успехом отлично можно и отрезками приближать.
Ну это я так, к примеру, а вообще изначально мне казалось, что надо всю кривую в масшатабе рисунка восстанавливать и чтобы она вся укладывалась в наши точки.
КО>>>Опять же, достаточно точно оценить кривизну в нашей дискретной задаче скорее всего не удастся. КО>>>Как искать удаление направляющих точек от концов кривой — вообще неясно (ну т.е. мне не ясно ) РМ>>Я там выше писал про покрытие точек прямой, так вот их кол-во после какого-то несложного преобразования ( возможно по таблице, полученной эмпирически ) должно дать примерное значение, вокруг которого можно искать перебором или даже оставить так. КО>Да, но перебор все-таки достаточно большой...
В том-то и штука, что перебор вокруг приблизительного значения, то есть сильно меньший, чем мог бы быть.
А вообще отказавшись от Безье, в пользу кривых второго порядка, можно избежать перебора вообще.
КО>>>изломы, самопересечения, РМ>>В принципе при вращении кривой эти штуки опредятся как два максимума только в одной стороне ( изломы ) два максимума с обеих сторон ( пересечения ). В изломах можно и прервать кривую, а в пересечениях продолжатьь в нужном направлении. КО>Щас, я не понял. Что ты имеешь ввиду? Здесь можешь поподробнее плз?
Если мы имеем излом, и попытаемся найти направление фокусом с кривой, то ничего не выйдет, направления будет два и односторонних, а для пересечения будет просто два направления. Оба случая можно корректно обработать.
КО>>>толщина в 2 и больше пиксела (а толщина в два пиксела, зараза, сплошь и рядом встречается на приведенной картинке), РМ>>Не страшна. Какие проблемы она создает? КО>Да понимаешь — вот у нас массив пар (x,y) от 1 до 10000. Больше ничего не знаем. И что с этим делать? Как ты поймешь, что кривую нужно направлять в "самую тонкую сторону"?
А фокус с прямой зачем? КО>И глянь на рисунок — там есть жирные перекрестки из пяти и больше таких "кишок"... Че с ними делать, я не знаю...
Не начинать с перекрестков. А на ходу, когда уже известно предыдущее направление проще выбрать правильное.
КО>>>раздавленные комары, пыль и вообще все плохо РМ>>Комаров я там не заметил, а пыль — можно просто выкидывать слишком мелкие куски. КО>Не знаю. Там кусок 6х6 — мы-то с тобой понимаем, что его надо выкинуть, а компу как объяснить?
Выкидывать те, где не прошел фокус с кривой...
РМ>>Кстати не обязательно использовать именно Безье. Можно и квадратичными кривыми обойтись в данном случае, а считать и перебирать уже меньше. КО>Ну да, это Mika просто упомянул, что ему кривые Безье нужны — а так конечно, с квадратичными проблем гораздо меньше. Дело в том, что квадратичная кривая — это кривая Безье, у которой две направляющие точки совпадают, а следовательно, находятся на пересечении двух касательных прямых в концах кривой. Все наши рассуждения остаются, более того: как только мы отыщем касательные прямые в концах с достаточной точностью, сразу появится третья точка (в точке их пересечения) — и квадратичная кривая найдена.
Во-во, и я о том же.
РМ>Как определить направление в данной точке без цепочки я уже писал. Вторая проблема — это движение вдоль линии. Но имея направление, разве это проблема? Третья проблема — это выкидывать те точки, для которых кривая уже построена, так как при движении вдоль мы будем проходить не через все точки. Но в принципе и это не проблема, так как можно помечать все находящиеся рядом с проходимыми.
Ну, от этих рассуждений до алгоритма еще довольно далеко (еще много неясностей), но путь ты указал — и я с тобой согласен. Теперь уже наверное можно пробовать кодить
P.S. Здесь очень важны дизайн и структуры данных — в процессе написания алгоритм будет сильно эволюционировать.
Почитать, поднатареть, обматериться (приобрести матерые вид 
) я всегда люблю.
Я раньше шел наоборот 
