Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Программирование игр, графики и искусственного интеллекта > Распознавание геометрических фигур на плоскости


Автор: Гость_mln 8.11.2005, 20:02
Всем привет.
Задание это по предмету Системы искусственного интеллекта.
Задача такая: необходимо реализовать распознавание геометрических фигур на плоскости.
Есть bmp картинка треугольника, квадрата, круга или ромба, например. Пусть уже имеется матрица цветов этой картинки, т.е. каждому пикселю bits[i] соответствует его цвет.
Как можно реализовать распознование и по какому алгоритму?
Посоветуйте пожалуйста.

Автор: DragonFire 9.11.2005, 07:26
Ну можно попробовать использовать нейронные сети... Научить нейрон отличать квадрат, от ромба и трейгольник, от круга... Сам я работал только с текстом, но я думаю, тут такая же фишка прокатит...
Вот по этой ссылочке я описывал распознование текста, может поможет: http://forum.vingrad.ru/index.php?showtopic=68416
И еще, размеры картинок должны быть одинаковые... Вот единственный недостаток...

Автор: DENNN 9.11.2005, 15:31
Ищите геометрические примитивы - линии и точки. Потом уже анализ изображения на уровне геометрии, а не растра

Автор: Guest 10.11.2005, 23:40
Цитата(DragonFire @ 9.11.2005, 07:26)
Научить нейрон отличать квадрат, от ромба и трейгольник, от круга... Сам я работал только с текстом, но я думаю, тут такая же фишка прокатит...
Вот по этой ссылочке я описывал распознование текста, может поможет: http://forum.vingrad.ru/index.php?showtopic=68416

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

Автор: Гость_mln 10.11.2005, 23:42
Цитата(DENNN @ 9.11.2005, 15:31)
Ищите геометрические примитивы - линии и точки. Потом уже анализ изображения на уровне геометрии, а не растра

вряд ли, ведь картинка как раз и задана как растр, матрицей пикселей..

Автор: DragonFire 11.11.2005, 08:00
А в том то и дело, что не вектора. Именно простенькая нейронная сетка.
Есть у тебя нейрон. Ты подаешь ему на вход сигналы. Допустим у нас картинка 5х5, поэтому сигналов 25: сигнал "1" - если черная клетка, "0" - если белая. Нейрон твой жует твои сигналы и выдает ответ "Треугольник" это или нет, рассчитывая это по формуле: <РЕЗУЛЬТАТ>=<сигнал1>*<Вес1>+<сигнал2>*<Вес2>+...+<сигнал25>*<Вес25>;
If <РЕЗУЛЬТАТ> > <Порог> then Буква - А, если нет, то не А.
Все здесь сводится к тому, чтобы рассчитать эти <Вес> так, чтобы когда у нас поступали сигналы c треугольника, то выражение <Результат> было больше порога, обычно он берется 1.5 или 0.5. Такой процесс называется обучением нейрона. Вот и вся задача. Обучаешь 4 нейрона - каждый на распознования своей определенной геометрической фигуры...
Теперь об обучении. Для начала создай текстовый файл, в котором будут хранится веса синапсов(изначально поставь им значения по 0.1 и поставь порог в программе 1.5). Далее, в своей программе загрузи этот файл и загрузи рисунки твоих фигур. Для начала попробуй создать нейрон, распознающий треугольник твоя фигура - или нет. Для этого считывай с картинки сигналы каждого пикселя и рассчитывай результат по вышеприведенной формуле. Если он не тот, какой нужен (например ты даешь ему круг, а он пишет, что треугольник), то изменяй вес каждого синапса "ЧЕРНОЙ" клетки на 0.01. И пересчитывай по-новой. Если он стал отвечать правильно, то переходи к следующей картинке и работай с ней. Когда дойдешь до последней картинки, переходи на первую. Кстати, забыл сказать (но я думаю ты и сам догадался) если ты загружаешь след. картинку и результат сразу правильный - сразу переходи с следующей. И если все картинки правильно распознаются, то сохраняй значения в файл и радуйся... smile
Единственное что - нужно прогнать программу раз 100, чтобы нейрон обучился, поэтому можешь придумать какой-нибудь автоматический цикл. И если хочешь, скажи мне свое мыло, я тебе пришлю пример программы, тока для букв. А может (если будет время) и напишу именно прогу для геом. фигур. Если что не понятно объяснил - спрашивай. Я не учитель...

smile Прошу модератора разрешить прикрепить рисунок к этому сообщению, а то то что я написал не очень понятно... Плиз... DENNN рисунки помещать хочу!

Автор: DENNN 11.11.2005, 11:35
Цитата
Цитата (DENNN @ 9.11.2005, 15:31)
Ищите геометрические примитивы - линии и точки. Потом уже анализ изображения на уровне геометрии, а не растра

вряд ли, ведь картинка как раз и задана как растр, матрицей пикселей..

Я, собственно, и предлагаю искать из по растру. К примеру, уже давно для различного подвида задач используются алгоритмы определения координат точки (или площадного объекта) по изображению с подпиксельной точностью.

Автор: Тима 15.3.2006, 23:40
Привет.
Мне надо собрать различные алгоритмы распознавания геометрических фигур(чисто теорию, не реализовывая).
Можешь чем-нибудь почомь?

Автор: DragonFire 16.3.2006, 19:34
Вот - с помощью сеток нейронных...

Автор: mr.DUDA 16.3.2006, 22:42
DragonFire, нажми "предварительный просмотр", там снизу кнопка "Обзор" для прикрепления файлов... smile

Автор: DragonFire 18.3.2006, 20:21
Класс, тока криво как то... на главную нельзя вынести было, чтобы нубы как я не парились ? smile

Автор: Мурлыкатам_ 4.11.2007, 20:31
А может поможете найти алгоритм для определения количества углов в фигуре, во время обхода границы фигуры методом Жука?

Автор: Мурлыкатам_ 6.11.2007, 19:33
DENNN, 
Цитата

Я, собственно, и предлагаю искать из по растру. К примеру, уже давно для различного подвида задач используются алгоритмы определения координат точки (или площадного объекта) по изображению с подпиксельной точностью.


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

Автор: DragonFire 6.11.2007, 21:24
м.б. самому попробовать придумать? Задачка же вроде скорее геометрическая чем на н.с... Сам угол можно найти скажем так: берем 2 соседние точки пишем уравнение прямой и проходим по всем точкам в линии, как тока какая то точно не принадлежит прямой значит это угол, и мы стоим новую прямую и идем дальше...
Ну это навскидку, я люблю просто велосипеды((( 

Автор: Мурлыкатам_ 7.11.2007, 14:05
DragonFire, приколист smile)) велосипеды smile))

Я уже придумал smile Даже работает.
Если кому интерестно или нужно, могу поделиться идеей.

Автор: DragonFire 7.11.2007, 14:57
Ну поделись)) в 2х словах)) вдруг кому-то понадобиться))

Автор: SHShadow 16.11.2007, 10:57
Обещал же поделиться, а сам молчит. Ну же.

Автор: SHShadow 20.11.2007, 00:44
Есть у меня один алгорим по определению объектов методом жука. Выкладываю на обозрение. Правда на оптимальность не претендую:
Код

                Current=Start;
                int Direction=DIR_BOTTOM;
                if ((pDoc->m_imgMain.GetPixel(Current.x-1,Current.y-1)==RGB(255,255,255))&&
                    (pDoc->m_imgMain.GetPixel(Current.x,Current.y-1)==RGB(255,255,255))&&
                    (pDoc->m_imgMain.GetPixel(Current.x+1,Current.y-1)==RGB(255,255,255))&&
                    (pDoc->m_imgMain.GetPixel(Current.x-1,Current.y)==RGB(255,255,255))&&
                    (pDoc->m_imgMain.GetPixel(Current.x+1,Current.y)==RGB(255,255,255))&&
                    (pDoc->m_imgMain.GetPixel(Current.x-1,Current.y+1)==RGB(255,255,255))&&
                    (pDoc->m_imgMain.GetPixel(Current.x,Current.y+1)==RGB(255,255,255))&&
                    (pDoc->m_imgMain.GetPixel(Current.x+1,Current.y+1)==RGB(255,255,255))) break;
                do
                {

                    switch(Direction)
                    {
                    case DIR_BOTTOM:
                        while((pDoc->m_imgMain.GetPixel(Current.x-1,Current.y)==RGB(255,255,255))&&
                            (pDoc->m_imgMain.GetPixel(Current.x,Current.y+1)!=RGB(255,255,255))) 
                        {

                            if (Current.y+1==Heigth) break;
                            Current.y++;
                            
                        }
                        if (Start==Current) break;
                        if (pDoc->m_imgMain.GetPixel(Current.x-1,Current.y)!=RGB(255,255,255)) {Current.x--;Direction=DIR_LEFT;}
                        else if (pDoc->m_imgMain.GetPixel(Current.x+1,Current.y)!=RGB(255,255,255)) {Current.x++;Current.y;Direction=DIR_RIGTH;}
                        else if (pDoc->m_imgMain.GetPixel(Current.x-1,Current.y+1)!=RGB(255,255,255)) {Current.x--;Current.y++;}
                        else if (pDoc->m_imgMain.GetPixel(Current.x+1,Current.y+1)!=RGB(255,255,255)) {Current.x++;Current.y++;}
                        else Direction=DIR_UP;
                        if (Current.y>Bottom) Bottom=Current.y;
                        break;
                    case DIR_RIGTH:
                        while((pDoc->m_imgMain.GetPixel(Current.x,Current.y+1)==RGB(255,255,255))&&
                            (pDoc->m_imgMain.GetPixel(Current.x+1,Current.y)!=RGB(255,255,255))) 
                        {
                            if (Current.x+1==Width) break;
                            Current.x++;
                            
                        }
                        if (Start==Current) break;
                        if (pDoc->m_imgMain.GetPixel(Current.x,Current.y+1)!=RGB(255,255,255)) {Current.y++;Direction=DIR_BOTTOM;}
                        else if (pDoc->m_imgMain.GetPixel(Current.x,Current.y-1)!=RGB(255,255,255)) {Current.y--;Direction=DIR_UP;}
                        else if (pDoc->m_imgMain.GetPixel(Current.x+1,Current.y-1)!=RGB(255,255,255)) {Current.x++;Current.y--;}
                        else if (pDoc->m_imgMain.GetPixel(Current.x+1,Current.y+1)!=RGB(255,255,255)) {Current.x++;Current.y++;}
                        else Direction=DIR_LEFT;
                        if (Current.x>Rigth) Rigth=Current.x;
                        break;
                    case DIR_UP:
                        while((pDoc->m_imgMain.GetPixel(Current.x+1,Current.y)==RGB(255,255,255))&&
                            (pDoc->m_imgMain.GetPixel(Current.x,Current.y-1)!=RGB(255,255,255))) 
                        {
                            Current.y--;
                            if (Current.y==0) break;
                        }
                        if (Start==Current) break;
                        if (pDoc->m_imgMain.GetPixel(Current.x+1,Current.y)!=RGB(255,255,255)) {Current.x++;Direction=DIR_RIGTH;}
                        else if (pDoc->m_imgMain.GetPixel(Current.x-1,Current.y)!=RGB(255,255,255)) {Current.x--;Direction=DIR_LEFT;}
                        else if (pDoc->m_imgMain.GetPixel(Current.x+1,Current.y-1)!=RGB(255,255,255)) {Current.x++;Current.y--;}
                        else if (pDoc->m_imgMain.GetPixel(Current.x-1,Current.y-1)!=RGB(255,255,255)) {Current.x--;Current.y--;}
                        else Direction=DIR_BOTTOM;
                        if (Current.y<Top) Top=Current.y;
                        break;
                    case DIR_LEFT:
                        while((pDoc->m_imgMain.GetPixel(Current.x,Current.y-1)==RGB(255,255,255))&&
                            (pDoc->m_imgMain.GetPixel(Current.x-1,Current.y)!=RGB(255,255,255))) 
                        {
                            Current.x--;
                            if (Current.x==0) break;
                        }
                        if (Start==Current) break;
                        if (pDoc->m_imgMain.GetPixel(Current.x,Current.y-1)!=RGB(255,255,255)) {Current.y--;Direction=DIR_UP;}
                        else if (pDoc->m_imgMain.GetPixel(Current.x,Current.y+1)!=RGB(255,255,255)) {Current.y++;Direction=DIR_BOTTOM;}
                        else if (pDoc->m_imgMain.GetPixel(Current.x-1,Current.y+1)!=RGB(255,255,255)) {Current.x--;Current.y++;}
                        else if (pDoc->m_imgMain.GetPixel(Current.x-1,Current.y-1)!=RGB(255,255,255)) {Current.x--;Current.y--;}
                        else Direction=DIR_RIGTH;
                        if (Current.x<Left) Left=Current.x;
                        break;
                    default :MessageBox("Ошибка направления обхода."); return;
                        break;
                    }

                }while (Start!=Current);


pDoc->m_imgMain это CImage объект
Left, Rigth, Top, Bottom - координаты определенного объекта (описывающего квадрата)

количество углов будет равно числу проходов цикла + 1.

Автор: Paguo86PK 5.3.2011, 02:45
Поиски в гугле про оконтуровании объектов изображения чаще приводят к фильтрам с матрицами 3x3 на каждый пиксел. Что совсем не подходит из-за сильного снижения скорости. Тем более весь этот массив координат пограничных пикселей потом очень трудоёмко отсортировать в многоугольник с линейным расположением координат, чтобы Polygon выглядил действительно как контур, а не паутина.
Достаточно долго и упорно я работал над собственным алгоритмом, основой которого стал "бот" бегущий вдоль границы и тянущий за собой стройный ряд координат. Основой поведения "бота" стала таблица постулатов. Однако, я столкнулся с огромными проблемами в сложных объектах, где происходили сбои.

Логика "жука"(бота) моего алгоритма строится так:
A) Жук может ползти в одном из восьми направлений, кратному 45°;
B) Жук имеет пять сенсоров(усиков) для получения сведений об окружающем пространстве. Все они собирают информацию о пяти соседних клетах по направлениям W,NW,N,NE,E (З,СЗ,С,СВ,В) относительно направления движения;
C) Имеется таблица, где перечисляются все возможные постулаты, в соответствии состояний пяти усиков жука в каком направлении он должен развернуться.

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

Ниже привожу этот алгоритм. Может кого-то он заинтересует, кому-то будет полезен. Ну а кто-нибудь поможет доработать.

Работает так: Вначале строится фигура (параметры можно менять в теле алгоритма в секции WM_CREATE) в Bitmap 640x480 32bpp и выводится на экран. Далее, клавиша ПРОБЕЛ делает один шаг "жука". Причём справа-вверху отображается Zoom региона с жуком, а справа-внизу выводятся пять Check-Box'ов - "усиков" жука. Галочкой помечается текущая обстановка, а серостью - предыдущее. В центре - Hex-код предыдущей и текущей ситуации. Всё это нужно для отладки и построения кодов таблицы постулатов.
Клавиша ENTER делает серию шагов, а ESC бежит до тех пор, пока контур не замкнётся.
Ну, в самом начале можете смело нажать на ESC и получить контур, так-как всё исправно сработает. Однако, если геометрию фигуры изменить, придётся "отлаживать" от проскоков и зацикливания.

Автор: Snakedon 26.5.2016, 22:55
 У меня диплом на похожую тему) )и чесно говоря не оч понимаю как реализовать разпознавание просто фигур нейронной сетью)

Автор: Bitter 26.5.2016, 23:39
Snakedon, так же как и распознавание рукописных букв, примеров которых полно

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)