На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! Правила раздела "Программирование графики"
1) Данный раздел предназначен для обсуждения проблем, возникающих при программировании задач, связанных с чтением, сохранением, обработкой, созданием, отрисовкой графической информации (в том числе - 3D [OpenGL, Direct3D] и анимации [в т.ч. VFW, DirectShow, OpenDML]).
Флэш обсуждают здесь!.

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

3) Уважаемые новички! Мы приветствуем Ваше желание научить всех посетителей раздела правильному программированию. Но огромная просьба, перед тем, как писать поучения в старых (последний ответ - "старее" месяца, а особенно, если вопрошавший не появляется на форуме уже не первый месяц, в чем можно убедиться в его профиле) темах, хорошо подумать, будет ли кому-нибудь, кроме Вас cамих, это интересно.



Ваше мнение о модераторах: user posted imageBarazuk, user posted imageOpenGL, user posted imageMikle
Модераторы: OpenGL, Mikle
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Простейшая векторизация растра.
    Дана картинка вроде такой:

    [прилагается]

    Задача: распознать в картинке простейшие примитивы (пока ограничимся отрезками линий и arc'ов).
    то есть, на выходе должно быть что-то вроде такого списка объектов:

    1) линия из точки (х,у) в точку (х2,у2)
    2) линия из точки (х3,у3) в точку (х4,у4)
    3) arc' с центром в точке (х5,у5), обрезан по углам ...
    и т.д.

    Изображение рассматриваем пока как чистое, без шумов и искажений.

    Вроде задача несложная, но найти хошь какое-нибудь приличное описание "для чайников" мне так и не удалось вот уже несколько дней, если что-то и есть, то слишком сложное, в основном ориентированное на оптимизацию, обработку в условиях искажений и т.п., своя голова изобретать метод тоже что-то отказывается. Прошу либо помочь направлением, где про это почитать, либо подкинуть идею, как это можно было бы организовать.
    Прикреплённая картинка
    Прикреплённая картинка
      Используй Преобразование Хафа (Hough transform).
      В литературе чаще всего рассматриваются как раз случаи прямых и дуг.
        Гениально!!! Правда, чувствуется, быстро это работать в чистом виде не будет, особенно с кругами, но это мы че-нить придумаем. Спасибо огромное, ты меня офигенно выручил, а то по запросам "Алгоритмы векторизации", и "Распознавание линий" поисковики ничего похожего не выдают...
          _____месяц спустя______

          Я вот никак не догоню: это что ж получается, этот метод тупо простым перебором линии выделяет? Так число вариантов стремится к бесконечности, а хоть сколько-нибудь приличная дискретизация в данном случае не спасает. Или все-таки я не понял, и выделение происходит как-то иначе? Ибо перепробовал возможные реализации, ну уж ооооочень медленно получается.
          Сообщение отредактировано: PVoLan -
            PVoLan
            Преобразования Хафа тут не спасают. Лучше почитать про алгоритма векторизации. Самой простой для линий это на основе волны.
            Вот почитай, думаю поможет http://ocrai.narod.ru/vectory.html
            Есть еще одна статья.
            http://www.ict.edu.ru/ft/004456/35.pdf
            Дальше почитать подумать и пофантазировать и вконец концов придумать свой алгоритм.
            А вообще поищи в английском Интернете там наверняка есть получше алгоритмы.

            Цитата PVoLan @
            Я вот никак не догоню: это что ж получается, этот метод тупо простым перебором линии выделяет? Так число вариантов стремится к бесконечности, а хоть сколько-нибудь приличная дискретизация в данном случае не спасает. Или все-таки я не понял, и выделение происходит как-то иначе? Ибо перепробовал возможные реализации, ну уж ооооочень медленно получается.

            Скорее всего, ты не понял сути. Работает это не медленно, даже скорее быстро. Если изменить малость алгоритм. Всего один проход по изображению и один по фазовому пространству.
            Есть два преобразования Хафа и Радона. Я их не особо отличаю. Но суть в следующем.

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

            1. Заводим фазовое пространство.
            Фазовое пространство это такое пространство, которое описывает все многообразие эталонов.
            Для прямую, линии нужно всего два параметра, для окружности три если радиус известен то два.
            К примеру, уравнение прямой y=k*x+b
            Нас интересуют только два параметра k,b они и будут координатами фазового пространство.
            Насколько разбить это пространство об этом отдельно.

            2. Идем по изображению ищем черные пиксели, как только нашли черный пиксель работаем с ним.

            3. Дальше перебираем координаты фазового пространства и проверяем нашу формулу y=k*x+b y,x фиксированы k,b варьируем.
            И если совпали значения то увеличиваем счетчик на 1. Это очень медленно получаются 4 вложенных цикла. Но этот легко с оптимизировать.
            Представим уравнение как
            -b=x*k-y переобозначим y2=-b; x2=k; k2=x; b2=-y
            y2=k2*x2+b2

            это же уравнение прямой, но на этот раз нам известны k2 и b2, а y2 и x2 это значения которые должны удовлетворять прямой.
            Т.е вместо того чтобы перебирать всё фазовое пространство нам достаточно всего-навсего "нарисовать" преобразование примитива.
            Когда будешь рисовать преобразование примитива в фазовом пространстве просто вместо установки значения цвета будешь инкрементировать значение ячейки.
            Это позволяет ускорить алгоритм рисование линии занимает один цикл. Ура мы избавились от вложенного цикла.
            Самое интересно преобразования линии является линия преобразования окружности тоже.


            4. Проходим по фазовому пространству проверяем значения все что выше порога является примитивом.

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

            В такой реализации время обработки снижается в розы. Так как мы перебираем не все линии, а только нужные.
            Сообщение отредактировано: Pavia -
              Хммммм... [ушел стучать по клавишам]
                Нет, Хаф определенно не катит.

                Во-первых, размер фазового пространства (рассматриваем картинки 600х400). 360 вариантов углов Х 720 значений R. (для линий используется не y=kx+b, a x*cosθ + y*sinθ = R, потому как первый не определяет вертикальную прямую). Даже в варианте разбора, указанном Pavia, на заполнение пространства тратится секунда-две как минимум, причем время заполнения пропорционально количеству черных пикселов, значит, резко увеличивается при увеличении кол-ва линий либо (что хуже) увеличении толщины линий.

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

                Третье - порог. Если рассматривать однопиксельные линии, то порог нельзя выбирать (хотя бы!) меньше 20ти - иначе линии длиной 20 пикселов не распознаются, только линии в полкартинки, что малоинтересно. Однако при таком пороге в результирующий список попадает дофига шуму.

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

                За окружности еще даже не брался...
                _____

                Волны - оригинальная идея, но для линий толщиной меньше 5ти пикселов явно не подходит

                http://www.ict.edu.ru/ft/004456/35.pdf - читал еще до того, ничего не понял. :idiot, yes, i know:

                Цитата
                Дальше почитать подумать и пофантазировать и вконец концов придумать свой алгоритм.

                Уже месяц придумываю, даже кое-что придумал. Работает около минуты, качество кхм...

                Цитата
                А вообще поищи в английском Интернете там наверняка есть получше алгоритмы.

                Принял к сведению, processing... Правда, пока не очень успешно - эти ребята имеют нехорошую привычку приличные статьи делать платными...
                Сообщение отредактировано: PVoLan -
                  PVoLan
                  Цитата PVoLan @
                  потому как первый не определяет вертикальную прямую

                  Математику учити все он определяет.
                  Цитата PVoLan @
                  секунда-две как минимум

                  На чем тестируем? У меня на пару порядков быстрее.

                  Цитата PVoLan @
                  Четвертое - хаф определяет только, что "на данной прямой есть N черных точек", но он никак не определяет, есть это точки одного отрезка (расположены рядом), или они равномерно рассеяны по рисунку, и отрезком на самом деле не являются. Этот момент приходится обрабатывать дополнительно, что тоже оччень долго.

                  Определяет. Просто надо 4 мерное пространство и смотерть соотношение числа пикселей на длину отрезка. И нужно будет делать поиск экстремумов, а не просто через порог проверять.

                  Цитата PVoLan @
                  Волны - оригинальная идея, но для линий толщиной меньше 5ти пикселов явно не подходит

                  Должно нормально работать в чем проблема? Там просто идет группировка соседних пикселий в срединную. Даже если у тебя линия будет толщиной 1 то все будет работать. Волна она для линий различной талщины подходит.

                  Цитата PVoLan @
                  Уже месяц придумываю, даже кое-что придумал. Работает около минуты, качество кхм...

                  Минуту на каком тесте? Вообще приемлимое время дальше только оптимизировать.
                  Сообщение отредактировано: Pavia -
                    Цитата
                    Математику учити все он определяет.

                    Не определяет. Только если к=бесконечность.

                    Цитата
                    На чем тестируем? У меня на пару порядков быстрее.

                    С#, amd 3400+ (частота 2,4 Ггц) 1,5 гига памяти. Картинки типа (прилагаются, +1 в след посте)
                    Сообщение отредактировано: PVoLan -

                    Прикреплённая картинка
                    Прикреплённая картинка
                      Цитата
                      Просто надо 4 мерное пространство и смотерть соотношение числа пикселей на длину отрезка

                      Какую длину отрезка? Там же линия! Прямая, без учета границ отрезка. Я лично так делаю: в фазовом пространстве вместо счетчиков я в список загоняю сами точки (исходного изображения), которые туда попадают. Далее в полученном списке проверяю отдельно: если стоят рядом, значит отрезок.

                      Добавлено
                      Про волны: смотри, там же по черным пикселям прогоняется волна (вместо пикселей ставятся номера последовательно), далее анализируется рисунок, полученный этими номерами, так? А если толщина 1 пиксел, откуда рисунок-то?

                      Цитата
                      нужно будет делать поиск экстремумов

                      А как их искать-то? Ведь если линии отличаются на 1 R, то да, точки, по которым мы нашли эту линию, они рядом, а если на θ, то это могут быть точки разных линий могут отстоять друг от друга далеко.

                      Сейчас ниже попробую сформулировать ту идею, которую я "придумал"...
                      Сообщение отредактировано: PVoLan -

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

                        Основной недостаток: диапазон приходится корректировать в том числе и на расширение, так как линии могут, например, иметь характер (иллюстр часть 3). При этом линия может плавненько сползти с угла совсем в другую сторону.

                        ПС. Наверное, не очень доступно рассказал, но я это себе в основном образом представляю, а не словами.
                        Прикреплённая картинка
                        Прикреплённая картинка
                          Передо мной стоит схожая задача. Нужно создать массивы в которых будут храниться набор пикселей которые расположены наиболее близко друг к другу.
                          Картинка приложена. Черая область это начения =0. Цветные линии = 1. Их мне и нужно найти.

                          Требования к алгоритму.

                          Даны интервалы поиска dx(1,10),dy(-10,10) размерность в пикселях. На картинке отображен преобразованный спектр сигнала. Где ось X это ось времени и поиск возможен только в прямом направлении. Имеется в виду что точка X=i может быть соеденина только с точами от i+1 до i+10. По оси Y это частота поиск возможен как в положительном так и в отрицательном направлении оси.

                          Данную задачу очень легко решить. Но у меня есть проблемы со скоростью.

                          Мой алгоритм выглядит следующим образом:

                          0. Начало
                          1. Находим точку не равную 0. Так как эта точка может быть не в начале линии то поиск ведем в двух направлениях по оси Х.
                          2. Составляем массивы с ближайшими пикселами для обоих направлений поиска. Для положительного направления шаг поиска dxpos(1,10); для отрицательного направления dxneg(-1,-10); полученныем пиксели записываем в массивы VecPos,VecNeg.
                          3. объденяем VecNeg и VecPos в один массив Vec.
                          4. Удаляем из картинки все точки которые входят в Vec
                          5. Если еще остались точки на картинке идем к шагу 1.
                          6. Конец.

                          Этот алгоритм работает очень медленно. Если кто может подсказать как ускорить алгоритм или в посоветовать литературу на данную тему буду признателен.

                          Добавлено
                          Соединяемые в массив пикселы не обязательно должны прилегать друг к другу они могут находиться на расстоянии в 10ть пикселей друг от друга. Нужно найти ближайший пиксел и соединить его с предидущим. Поиск ведется только в положительном направлении оси X!!!
                          Прикреплённая картинка
                          Прикреплённая картинка
                            Что понимается под фразой "набор пикселей которые расположены наиболее близко друг к другу"? И, как это: "Составляем массивы с ближайшими пикселами для обоих направлений поиска?"

                            Если я правильно понял из картинки, требуется выделить отдельные линии спектра. Это можно сделать примерно так:

                            1. Берем точку а=некая_начальная_точка.
                            2. Заносим а в результирующий список и помечаем ее как прройденную
                            3. Находим точку b, близко расположенную к а (с учетом указанных ограничений) и не пройденную
                            4а. Если не нашли, то конец алгоритма, результат в списке
                            4b. Если нашли, a=b, переход в 2. (либо вызвать алгоритм рекурсивно)
                              Skif Если честно из вашего описания ничего непоянтно. Много лишнего.

                              Если тебе надо найти группы пикселей. То это делается за один проход.
                              Пусть картинка чернобелая.

                              В зависимости от свзяности проверям
                              Если 4-х связные то левый и верхний пиксель.
                              Если 8 то еще и тот который на искосок слева и вверху.

                              Если эти три пикселя белые, а наш черный то помечаем его. Пишем в него номер из счетчика счетчик увеличиваем.
                              Если есть хоты бы один соседний пиксель черный, и тот ка тором мы стоим тоже, то помечаем этот пиксель числом из соседнеего.
                              Если так случилось что пиксели слева и вверху имеют разные номера то ставишь любой. Тут происходит слияние групп. Это надо будет както пометить к примеру вернуться обратным ходом и заполнить все пиксели другого номера нужным.
                              Сообщение отредактировано: Pavia -
                                Цитата Pavia @
                                Skif Если честно из вашего описания ничего непоянтно. Много лишнего.

                                Я тоже ничего не понял, как это сделать за один проход. Я нарисовал пример. На рисунке группа пикселей. Они расположены на некотором расстоянии друг от друга. Тоесть после того как точка найдена. Нужно еще поискать есть ли пиксел в заданном диапазоне поиска. И из всех пикселей которые есть в диапазоне поиска найти ближайший и перейти к нему. То, что должен сделать алгоритм это, разбить пикселы на три группы. Они на рисунке выделены цветами. И каждый последующий пиксел обязательно должен быть правее предыдущего. Так как интересуют горизонтальные линии а не вертикальные. Так как на рисунке много неиспользуемых точек. На примере они обозначены белым. То "бегать" по ним нет смысла. Я думал может быстрее будет запомнить все нужные пикселы и напрямую искать уже не по всей картинке а только по координатам в которых есть пикселы. Я вот о чем спрашивал.
                                Прикреплённая картинка
                                Прикреплённая картинка
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,1529 ]   [ 15 queries used ]   [ Generated: 19.03.24, 03:32 GMT ]