Векторизация контура. Как масштабировать картинку?

Различные алгоритмы, связанные с выводом графики.
arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Векторизация контура. Как масштабировать картинку?

Сообщение arthur2 » 12.11.2010 (Пт) 21:15

Нужно масштабировать картинку такого плана:Изображение

Причем, клава может быть любой самой замысловатой формы, например, такой:
Изображение
На любой изначальной картинке у всех клавиш будет контур в один пиксель.

Как масштабировать так, чтобы при любом масштабе контуры оставались в 1 пиксель? Есть идеи?
Последний раз редактировалось arthur2 15.11.2010 (Пн) 14:13, всего редактировалось 3 раз(а).
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16111
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: как масштабировать картинку?

Сообщение Хакер » 12.11.2010 (Пт) 21:17

1) Векторизовать, отмасштабировать, растеризовать.
2) Ещё более сложный алгоритм. С виду сложный, но по сути с вычислительной точки зрения эквивалентный первому.

Стоит, правда, указать, о каком мастабировании идёт речь. Пропорциональном или непропорциональном. И в каких пределах.

Вот, например, уменьши (вручную!) первую картинку до ширины в 32 px и покажи мне, где там будут границы клавиш в 1 px шириной.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: как масштабировать картинку?

Сообщение arthur2 » 12.11.2010 (Пт) 21:48

Хакер писал(а):Стоит, правда, указать, о каком мастабировании идёт речь. Пропорциональном или непропорциональном. И в каких пределах.
Пропорциональное. Нижний предел - как раз тот, при котором выполняется условие. И даже чуть больше (с запасом) - вообще-то, нижний предел определяется тем, чтобы на клавишах можно было написать символы не меньше чем в 8 пунктов.

В принципе, достаточно было бы сгенерировать по исходной, скажем, 5 или 7 картинок разного масштаба, а потом - в оконцовке - "масштабировать", просто подставляя ближайшую к нужному размеру картинку.

Абстрактно я себе представляю задачу так: векторизирую контуры, стираю их на исходной картинке, масштабирую, рисую контуры заново, выползания за контуры затираю, недотягивания до контура дорисовываю...

Нужно понять: 1. Как векторизовать контур 2. Как дорисовать, если появятся просветы между контуром и кнопкой.
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16111
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: как масштабировать картинку?

Сообщение Хакер » 12.11.2010 (Пт) 22:02

arthur2 писал(а):Абстрактно я себе представляю задачу так: векторизирую контуры, стираю их на исходной картинке, масштабирую, рисую контуры заново, выползания за контуры затираю, недотягивания до контура дорисовываю...

Что за глупость? Векторизировал, умножил на число, нарисова заново. Какие ещё подтирания :pig: ?

arthur2 писал(а):1. Как векторизовать контур

Думай, я в своё время думал и придумал, теперь думай ты. Уверен, что придумаешь.

arthur2 писал(а):Как дорисовать, если появятся просветы между контуром и кнопкой.

Это что-то ненужное.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: как масштабировать картинку?

Сообщение arthur2 » 12.11.2010 (Пт) 22:06

- Как сделать то-то и то-то?
- Думай. Я придумал и ты сможешь.

Помог, спасибо :)
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16111
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: как масштабировать картинку?

Сообщение Хакер » 12.11.2010 (Пт) 22:07

Вселить уверенность в своих силах порой важнее, чем указать на результат приложения чужих сил.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как масштабировать картинку?

Сообщение arthur2 » 12.11.2010 (Пт) 22:18

Да я не страдаю от недостатка уверенности :) И не такие стенки пробивал лбом :oops: Просто кроме моральной поддержки хотелось бы чуть больше конкретики: куда рыть-то? А то пока-что ты сказал более-менее очевидное.
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16111
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как масштабировать картинку?

Сообщение Хакер » 12.11.2010 (Пт) 22:23

Рыть в новом разделе темы. Там есть топик, предметом которого является то, на что ты должен обратить внимание при решении проблемы векторизации замкнутого конутра.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как масштабировать картинку?

Сообщение arthur2 » 12.11.2010 (Пт) 23:02

Нашел это: viewtopic.php?f=73&t=35397&start=0 Очень интересно и доходчиво, но про другое :oops:

Что за привычка говорить намёками - ткни пальцем, если не трудно.
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16111
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как масштабировать картинку?

Сообщение Хакер » 13.11.2010 (Сб) 0:27

arthur2 писал(а):Очень интересно и доходчиво, но про другое

«Про другое» — это значит, ты не можешь сообразить, как это применить.

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

При рисовании входящей информацией было: упорядоченное множество вершин (пар координат).
А на выходе после алгоритма получилось: множество закрашенных точек растра (тоже пары координат).

Это сделал алгоритм Брезенхема. Твоя задача написать обратный алгоритм, который из множества закрашашенных точек растра выведет множество вершин.

Иными словами, растеризация замкнутых однопиксельных самонепересекающихся контуров делается так:
  • Составляется список несмежных фигур (по смыслу — клавиш)
  • Для каждой фигуры составляешь список закрашенных пикселов.
  • Для каждой фигуры заводишь изначально пустой список вершин.
  • Сортируешь список закрашенных точек так, чтобы порядок следования точек в списке был таким, чтобы любая пара смежных элементов списка являлась смежными пикселами и в растре. Иными словами, избавляешься от обходческих тупиков:
    pixel_sorting.png
    pixel_sorting.png (4.08 Кб) Просмотров: 11837

    (тупик 13—14—15, слева смежные в списке точки несмежны в растре)
  • При этом появятся неустранимые тупики. Такие места нужно разрешить. Для этого в списке точек дублируешь в обратном порядке точки, мешающие «проходимости». Устранимые тупики тоже можно так разрешать, но это неэффективно. Но для примера: на приведённом выше рисунке для разрешения требуется дублировать точку-13 (в списке) и назначить ей позицию «15» (а точку с 15-ой позиции сдвинуть на 16-ую, с 16-ой — на 17-ую и так далее). Но, повторяю, делать такое надо только с неустранимыми тупиками.
  • Важнейший пункт разрешения неустранимых тупиков: центральную точку неустранимого тупика ты добавляешь в список (изначально пустой) вершин фигуры.
  • Далее берёшь любую точку фигуры, но эффективнее брать точку, являющуюся вершиной (есть в списке вершин). Начинаешь проходить (walk) по списку точек от этой точки в любом направлении (вперёд/по-часовой или назад/против). При этом на каждой итерации делаешь Bresenham Complete Test (я сам придумал термин, читай описание ниже) от выбранной изначально точки (я советовал в качестве такой брать вершину) до текущей точки. Если тест выполнился, берёшь в качестве текущей точки следующую (по списку (отсортированному) точек) точку. Если тест не выполнился, добавляешь текущую точку в список вершин (важное замечание!), назначёшь текущую точку начальной точкой, а новой текущей точкой — следующую в списке точку и продолжаешь шаги с выполнением теста.
  • Когда дойдёшь до самой первой начальной точки — прекращаешь работу. В списке вершин у тебя все вершины фигуры.

Bresenham Complete Test
Тест можно определить как функциональную зависимость.
Математическая формула: bct(p_{from}, p_{to})предикат от двух переменных pfrom и pto над упорядоченным множеством точек P.
Предикат истенен, если подмножество (множества P) точек Математическая формула: [p_{from}, p_{to}] эквивалентно (с точностью до порядка следования) множеству Математическая формула: brez(p_{from}, p_{to}), то есть множеству точек, выдаваемым алгоритмом Брезенхема при нахождении всех точек отрезка от pfrom до pto. И ложный — в противном случае.

Для нашего случая и более простым языком: тест успешен, если набор всех точек от начальной до текущей (включая начальную и текущую) совпадает с набором точек, который возвращается алгоритмом Брезенхема для отрезка от начальной точки до текущей. Совпадает — значит одинаковыый набор элементов и одинаковые порядок их следования.

Важное замечание (см. текст выше)
В случае неуспешности BCT нужно текущую точку добавлять в список вершин. Так вот, добавлять нужно не в конец списка, а используя следующую логику:
  • Если вершина уже есть в списке, не добавлять вообще.
  • Если в списке нет вершин, просто добавлять.
  • В противном случае вставлять между двумя вершинами, такими, что точка, соответствующая добавляемой вершине, в отсортированном списке точек находится между точками, соответствующим паре вершин, между которыми ты собрался добавлять.
.

P.S. Делать BCT для каждой итерации, на каждой итерации пересчитывая с нуля множество точек Бр.-отрезка — крайне неэффективно. Придумай «дифференциальную» форму теста, такую, что ты оперируешь разницей между аргументами прошлого теста и аргументами текущего теста и на основе этой разницы определяешь, будет ли разница между результатом текущего BCT и результатом прошлого BCT. Это куда эффективнее. Для этого медитируй над «фактором ошибки».

P.P.S. Прошу, не надо больше просить меня говорить не «намёками». Я умею отвечать только в двух режимах: «намёками» и подобными постами.

P.P.S-2. Описанный алгоритм векторизации — придуман мною весной этого года и сформулирован/описан впервые здесь и сейчас. Если кто-то придумал это и опубликовал раньше (это вполнее вероятно) — тогда я не претендую на авторство.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как масштабировать картинку?

Сообщение arthur2 » 13.11.2010 (Сб) 17:38

Здорово! Правда, с ходу не разобрался - пошел медитировать :)
Артур
 
   

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как масштабировать картинку?

Сообщение arthur2 » 14.11.2010 (Вс) 14:30

Разобрался до этого места:
Хакер писал(а):тест успешен, если набор всех точек от начальной до текущей (включая начальную и текущую) совпадает с набором точек, который возвращается алгоритмом Брезенхема для отрезка от начальной точки до текущей.

Тут получается непонятно:
ИзображениеНа отрезке от синей до синей точки алгоритм выполняется, а вот от синей до зеленой - нет, хотя зеленая - ну никак не вершина. Я понимаю, что чего-то недопонял :oops: А с порядком добавления вершин - вообще не понял:
В противном случае вставлять между двумя вершинами, такими, что точка, соответствующая добавляемой вершине, в отсортированном списке точек находится между точками, соответствующим паре вершин, между которыми ты собрался добавлять.


У меня родился другой вариант:
1. Составляем список всех закрашенных пикслелей и избавляемся от тупиков - по твоему варианту.

2. Добавляем в список вершин все точки, которые стыкуются с предыдущей точкой не так, как со следующей.

3. Берем три вершины подряд. Если между первой и третьей BCT выполняется, то вторую вершину исключаем из списка. Если не выполняется - вторая вершина подтвердила право быть вершиной.

Ещё такое соображение: так мы векторизируем только прямые линии. То есть, если этим способом векторизировать растровую окружность, а потом увеличить - получится многоугольник.
Вложения
kk.GIF
(1.41 Кб) Скачиваний: 977
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16111
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как масштабировать картинку?

Сообщение Хакер » 14.11.2010 (Вс) 15:41

arthur2 писал(а):На отрезке от синей до синей точки алгоритм выполняется, а вот от синей до зеленой - нет, хотя зеленая - ну никак не вершина. Я понимаю, что чего-то недопонял

Зря, это особенность алгоритма. Действительно, проблема есть, но она не такая страшная: можно после обхода пройтись по списку вершин и удалить все коллинеарные тройки. Это не сложно, если точек много, а вершин — мало. Другой способ: вместо того, чтобы ждать первого неуспешного BCT, обходишь список точек с конца до первого успешного BCT. Тогда до зелёной вершины дело не дойдёт, а ложных срабатываний (если нет смыкающихся участков контура вообще не будет никогда) не произойдёт. Но здесь ́б́ольшая вычислительная сложность. Третий вариант: так видиозменить дифференциальный BCT, что для зелёной точки срабатывания не произойдёт. И ещё вариант: вместо того, чтобы действовать при первом 1-пиксельном сбое BCT, замечать такие сбои, но не останавливаться на них, а идти дальше до 2-пиксельного сбоя BCT. При двухпиксельном сбое останавливаться и брать во внимание как вершину from-точку, которая дала последний успешный BCT. При таком случае зелёная точка «обнаружится», но проскочится, и выполнение дойдёт до истинной вершины (она зафиксируется как «последняя успешная»), а потом после этой точки как ни крути произойдёт 2-px-сбой BCT. Последний вариант при правильной реализации выглядит наиболее привлекательным. В общем, вариантов я предложил море.

arthur2 писал(а):А с порядком добавления вершин - вообще не понял

Список вершин надо реализовывать не как список пар координат точек, а как список указателей/индексов на элементы отсортированного списка точек. При добавлении элемента в список вершин надо перебирать его с начала до пункта, значение (а это указатель/индекс элемента в др. списке (точек)) которого будет меньше или равно порядковому номеру элемента списка точек, который (элемент) соответствует текущей точке, то есть точке, которая детектирована как вершина и как раз сейчас добавляется в список.

Фразу «перебирать его с начала» надо воспринимать условно. Конечно, так можно делать, формально это праивльно, но страшно неэффективно по той причине, что нет смысла в следующий раз перебирать список с начала, потому до уже обойдённого элемента ничего гарантированно измениться не может. Иначе получается «алгоритм маляра Шлемеля» (прочитать о явлении можно тут).

В принципе, можно «не заморачиваться» на этом, а добавлять вершины в список вершин в том порядке, в котором они находятся (обнаруживаются). В конце обхода просто отсортировать этот список по значениям элементов (это указатели/индексы). Но и это неэффективно. Любая сортировка превращает хаос в порядок. Вместо того, чтобы сначала преднамеренно создавать хаос, а потом вынужденно устранять его, я предлагаю изначально создавать порядок, а потом не тратить ресурсы на его создание (он уже есть) из хаоса.

В общем, на шаге фильтрации списка точек, очень вероятно, возникнут неустранимые тупики. Они будут разрешены (resolved), а как побочный эффект — в списке вершин ещё до циклических BCT уже появятся вершины. К моменту начала этапа циклических BCT нужно завести указатель/индекс на элемент списка вершин и установить его на первый элемент списка (если он есть, потому что список запросто может к этому моменту быть пока ещё пустым).

В момент добавления вершины в список вершин нужно сдвигать этот указатель (можно называть его «курсором вставки» (insertion cursor) вперёд до тех пор, пока элемент, на который он указывает, не станет по значение больше индекса текущей точки. При этом (сдвигах курсора) элементы в списке вершин могут кончиться, в этом случае курсорный указатель/индекс нужно обнулить, т.е. привести его в такое состояние, как если бы список вершин вообще был изначально пуст.

А после этого:
  • курсор сброшен (список вершин был пуст или достигнут его конец) — добавляем новый элемент в конец списка.
  • курсор установлен на какой-то элемент — проверяем, отличается ли индекс добавляемой точки от значения элемента, на который указывает курсор:
    • отличается — вставляем в список вершин новый элемент до элемента, на который указывает курсор
    • не отличается — ничего не добавляем (нет смысла плодить дубли), но сдвигаем указатель на следующий элемент списка, либо сбрасываем курсор, если дальше ничего нет.

Ну, надеюсь, теперь понятно? Я уже не знаю, как более доступно разжевать.

arthur2 писал(а):То есть, если этим способом векторизировать растровую окружность, а потом увеличить - получится многоугольник.

Увы и ах: это не практически, а теоретически неразрешимая проблема. Извлечь из растра информацию, которой там в принципе нет, — невозможно. Что на самом деле нарисовано — окружность или 10-угольник — не может достоверно сказать никто, кроме растеризатора, если такой был.

Впрочем, можно и это решить: после векторизации полигон превратив в Безье-сплайн, подобрав длину «усиков» по специальному хитрому алгоритму.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как масштабировать картинку?

Сообщение arthur2 » 15.11.2010 (Пн) 8:49

Про порядок добавления вершин - вроде, понял, что ты имел ввиду.

Вот ещё сложность: какую точку считать вершиной?
ИзображениеЕсли провести идеальные линии, то вообще-то ни одна из четырех под вершину не подходит. Если ввести "дробные пиксели", то вершина будет где-то внутри третьего пикселя чуть выше середины и чуть правее края.
Вложения
lll.gif
(1.95 Кб) Скачиваний: 1359
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16111
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как масштабировать картинку?

Сообщение Хакер » 15.11.2010 (Пн) 8:51

arthur2 писал(а):Вот ещё сложность: какую точку считать вершиной?

На каком этапе?

На сортировке — центры неустранимых тупиков (центры относительно последовательсости точек после разрешения).
На тестах — точку, давшую последний успешный тест.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16111
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как масштабировать картинку?

Сообщение Хакер » 15.11.2010 (Пн) 8:58

Вот ещё что: логика с 1px- и 2-px сбоями должна быть описана другими словами, потому что числа 1 и 2 являются частными случаями.

Рекомендую всё-таки следующую модифицированную логику: определение BCT не менять, кроме того момента, что BCT будет не предикатом. Искать последний успешный BCT, пропускать сбойные BCT и стопать только на таких сбоях BCT, когда появляется точки, которые смежны с точками, составляющими разность множеств Математическая формула: [p_{from}, p_{to}] и Математическая формула: brez(p_{from}, p_{to}).
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как масштабировать картинку?

Сообщение arthur2 » 15.11.2010 (Пн) 13:59

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

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

И всё-таки, если после первого прохода ни одна вершина не выявилась, возникает вопрос: а с какой же точки начать проверку по тесту?
Изображение
Если начать с точки 1 по часовой стрелке, то все следующие скругленные углы прочитаются не так, как первый. Хотя... если несколько отрезков подряд получились слишком короткими, то по-хорошему, нужно бы все точки этих отрезков заносить в список вершин.

Хакер писал(а):Действительно, проблема есть, но она не такая страшная: можно после обхода пройтись по списку вершин и удалить все коллинеарные тройки
Как? Тем более, что это будут не обязательно тройки, а и четвёрки и пятерки...
Вложения
lll.gif
(1.37 Кб) Скачиваний: 930
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16111
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Векторизация контура. Как масштабировать картинку?

Сообщение Хакер » 15.11.2010 (Пн) 14:46

arthur2 писал(а):Вершины на выходе всё равно нужны в виде массива поинтов (чтобы передавать в АПИ) Так что предлагаю такой подход: завести массив флагов той же размерности, что и массив точек. При нахождении вершины просто поднимать флаг по тому же индексу, а при лишении точки статуса вершины - флаг опускать. В конце пройти по списку точек, и если флаг поднят, собирать точки в выходной массив (можно прямо в тот же массив точек - дальше он всё равно не понадобится).

Глупо. Флаг потребует 1 бит, а отожрётся паразитно при этом от 7 до 31. В конце ты вынужден будешь бегать по всем точкам и смотреть на флаг. При этом собирать новый массив POINTAPI-вершин. Я предлагаю вести список указатель на элементы массива вершин. Потом так же проходить по нему и на основании его создавать список. Единственный плюс: при этом не надо заботиться пот порядки вставки в список вершин.

Если ввести битовый банк, это может оказаться лучше.


arthur2 писал(а):если точка соседствует по сторонам с тремя белыми полями - она заведомо вершина.

Что за поля? Если имелись в виду белые точки, то это не так, потому что у 45°-наклонной все точки имеют три белых соседа.

Если у точки два белых соседа по сторонам и три - по диагонали - она заведомо вершина.

Такие условия слишком сложные, чтобы применять их ко всем точкам полигональной фигуры.


И всё-таки, если после первого прохода ни одна вершина не выявилась, возникает вопрос: а с какой же точки начать проверку по тесту?

С первой в отсортированном списке точек, например.

Если начать с точки 1 по часовой стрелке, то все следующие скругленные углы прочитаются не так, как первый.

Это так, от этого не уйти. Имеет вообще значение, по или против часовой стрелки ты будешь обходить (раз), по или против часовой стрелки ты будешь рисовать (два) и как именно реализован алгоритм рисования линии (Брезенхема) (три). Об этом момент, связанном с неопределённостями, я уже писал в своём блоге.

Как? Тем более, что это будут не обязательно тройки, а и четвёрки и пятерки...

Коллинеарные тройки превращаются в двойки.
Чётверки обрабатываются как тройка и единица. Тройка даёт двойку, двойка и единциа даёт новую тройку, новая тройка (возможно) даёт новую двойку. Итеративное упрощение.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Векторизация контура. Как масштабировать картинку?

Сообщение arthur2 » 15.11.2010 (Пн) 17:40

Хакер писал(а):Что за поля? Если имелись в виду белые точки, то это не так, потому что у 45°-наклонной все точки имеют три белых соседа.
Нет, в этом случае у точек по сторонам - только два белых соседа. Третий сосед - по диагонали.

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

Во-первых, во время обхода контура у каждой точки всё равно смотреть соседей - иначе как вычленить контур. Во-вторых, это не сложнее, чем ВСТ для каждой точки, так что если некоторые вершины удастся вычислить без теста, это окупится.

Хакер писал(а):Флаг потребует 1 бит, а отожрётся паразитно при этом от 7 до 31. <...> Я предлагаю вести список указатель на элементы массива вершин.
Упс... а список ты в чём хранить будешь? Это по меньшей мере массив интеджей (если хранить просто индексы).

Да и потом, не так уж и много с флагами - по байту на точку. Зато не нужно будет вставлять элементы в середину массива (а для этого ведь придется сдвигать весь массив после места вставки). По-моему, расход окупится. И код получится проще.

Если ввести битовый банк, это может оказаться лучше.
Что такое битовый банк? догадываюсь, что что-то вроде битового поля, но как это реализовать на бейсике? Тем более - с индексами отдельных битов?
Вложения
lll.gif
(5.48 Кб) Скачиваний: 937
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16111
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Векторизация контура. Как масштабировать картинку?

Сообщение Хакер » 15.11.2010 (Пн) 19:03

arthur2 писал(а):Во-первых, во время обхода контура у каждой точки всё равно смотреть соседей - иначе как вычленить контур.

Контур можно обходить грубо, а потом приводить в правильный вид сортировкой. Но есть классный способ обходить растр построчно и при этом получать правильную последовательность точек. Здесь весь смысл в том, что последовательный (serial) обход растра на порядок эффективнее случайного (random-access).

arthur2 писал(а):Во-вторых, это не сложнее, чем ВСТ для каждой точки, так что если некоторые вершины удастся вычислить без теста, это окупится.

Это почти бесполезное занятие. Обнаружение вершин не спасает от циклических BCT. Допустим ты найдёшь вершины, но нет никакой гарантии, что между парой смежных вершин нет ещё одной — не обнаруженной вершины. Поэтому всё равно придётся делать BCT. BCT выполняется не на растре, а на списке точек. Нет случайного доступа к памяти. В общем, это намного эффективнее, чем тесты соседей.
То есть ты не прав, что это не сложнее. Это намного «дороже», чем BCT. А пользы — меньше.

Понимаешь?

arthur2 писал(а):Упс... а список ты в чём хранить будешь? Это по меньшей мере массив интеджей (если хранить просто индексы).

Конечно, но они у меня будут хранить полезную информацию, а у тебя — оставаться почти пустыми.

Да и потом, не так уж и много с флагами - по байту на точку.

А на координаты точки — 3 байта? По 12 бит (!!!) на координату? :roll:

arthur2 писал(а):По-моему, расход окупится.

Неа, не окупится.

arthur2 писал(а):Что это? догадываюсь, что что-то вроде битового поля, но как это реализовать на бейсике? Тем более - с индексами отдельных битов?

Реализовать с помощью битовых операций. Удобно это сделать не получится.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Векторизация контура. Как масштабировать картинку?

Сообщение arthur2 » 15.11.2010 (Пн) 19:18

Хакер писал(а):А на координату точки — 3 байта? По 12 бит (!!!) на координату?
Не понял :) Поинт - это ведь два лонга. Ну ладно, пусть будет два интеджа - всё равно 4 байта.

Хакер писал(а):Контур можно обходить грубо, а потом приводить в правильный вид сортировкой. Но есть классный способ обходить растр построчно и при этом получать правильную последовательность точек. Здесь весь смысл в том, что последовательный (serial) обход растра на порядок эффективнее случайного (random-access).

Это как? не понял принципа
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16111
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Векторизация контура. Как масштабировать картинку?

Сообщение Хакер » 15.11.2010 (Пн) 19:22

arthur2 писал(а):Не понял :) Поинт - это ведь два лонга. Ну ладно, пусть будет два интеджа - всё равно 4 байта.

Два лонга и один бит на флаг. Итого 65 битов. Сколько надо лишних битов, чтобы «поинт» стал «круглым»? 31 или 63? Лишних-то бита, только для выравнивая до кратной границы...

arthur2 писал(а):Это как? не понял принципа

Боже упаси. Ты хочешь, чтобы я и этот свой принцип тебе расписал?
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Векторизация контура. Как масштабировать картинку?

Сообщение arthur2 » 15.11.2010 (Пн) 19:27

Хакер писал(а):Два лонга и один бит на флаг. Итого 65 битов. Сколько надо лишних битов, чтобы «поинт» стал «круглым»? 31 или 63? Лишних-то бита, только для выравнивая до кратной границы...
Ничего не понял. У меня - массив байтов-флагов (по байту добавки на точку) У тебя - массив интеджей-индексов (по два байта). У меня экономней. Ну ладно - у тебя массив короче, потому что там не все точки, а только вершины... Всё равно почти поровну.

Хакер писал(а):Боже упаси. Ты хочешь, чтобы я и этот свой принцип тебе расписал?
Ну я-то хочу, но если тебе в лом, то не надо :)
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16111
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Векторизация контура. Как масштабировать картинку?

Сообщение Хакер » 15.11.2010 (Пн) 19:40

arthur2 писал(а):У меня экономней. Ну ладно - у тебя массив короче, потому что там не все точки, а только вершины... Всё равно почти поровну.


Дело не в том, что он короче. Он действительно короче. Но мне его не нужно обходить чтобы что-то там искать. А у тебя он мало того, что больше, так в нем ещё и положительные элементы искать надо.

Ну как тебя переубедить. Представь, что у тебя квадрат 50×50 px. У меня будет 4 индекса/указателя, а у тебя 196 байтов-флагов. Чуешь разницу? Причём я, используя индексы/указатели, сразу смогу обратиться к 4 элементам списка точек. А тебе надо будет пробегать по 196 элементам, делать 196 проверок флага, чтобы найти всего-лишь 4 установленных флажка. Что, эффективно? :?


arthur2 писал(а):Ну я-то хочу, но если тебе в лом, то не надо :)

Концепция островков/мозайки. Сканируешь строку, находишь непрерывные последовательности черных точек. Это и есть островки. На следующей строке будут новые островки. Фишка в соединении островков. То, что левее прошлого островка — добавлять (в списке!) перед, а то, что права — после. А островок, соединяющий два вырхних островка, соединяет два несвязанных списка в один. Или замыкает список.

Дальше сам.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Векторизация контура. Как масштабировать картинку?

Сообщение arthur2 » 15.11.2010 (Пн) 20:25

Хакер писал(а):Дальше сам.
Круто! Попробую :)

Хакер писал(а):Что, эффективно?

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

В общем, не знаю - может ты и прав. Но в моём варианте код понятнее. Подумаю про битовое поле :)
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16111
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Векторизация контура. Как масштабировать картинку?

Сообщение Хакер » 15.11.2010 (Пн) 20:31

Короче, если у тебя получится, отпишись сюда.

Я это придумал ещё весной, но испытать и реализовать, как обычно, времени нет. Будет хорошо, если всё это отлично сработает. Контурообход и векторизация — небольшая часть задуманного мною алгоритма (и формата) сжатия изображений без потерь, который, по моим оценками, имеет большие шансы обогнать существующие форматы.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16111
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Векторизация контура. Как масштабировать картинку?

Сообщение Хакер » 18.11.2010 (Чт) 18:01

Ну как?
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Векторизация контура. Как масштабировать картинку?

Сообщение arthur2 » 18.11.2010 (Чт) 19:28

Ещё никак - времени нет :(
Кстати, условия несколько изменились: контура у каждой клавиши теперь нет. Есть только сама клавиша и фон, так что контур сначала нужно вычислить :) Это мне несколько подпортило построчное считывание контура - теперь не соображу, как его реализовать.

А флаги-биты, кстати, можно хранить, например, в первом бите икса :) Всё равно лонга для одной координаты - слишком уж дофига.
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16111
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Векторизация контура. Как масштабировать картинку?

Сообщение Хакер » 18.11.2010 (Чт) 19:29

arthur2 писал(а):Это мне несколько подпортило построчное считывание контура - теперь не соображу, как его реализовать.
Вместо цвета обращаешь внимание на изменение цвета. Опять дифференцируешь, иными словами.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Векторизация контура. Как масштабировать картинку?

Сообщение arthur2 » 24.11.2010 (Ср) 22:41

Победил пока только построчное чтение контура. Блин, чуть разрыв мозга не заработал :oops: Кстати, тупиков при таком методе обхода не возникает :)

Осталась пара нерешенных вопросов: как вычленить разные фигуры и как вычленить контуры дырок.
Артур
 
   

След.

Вернуться в Графика

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

    TopList