| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Распознавание идентичных фигур разного размера |
| Автор: Royan 21.7.2005, 16:35 |
| Всем привет, Есть такая задача, пусть есть 10 идентичных фигур, в простейшем случае квадратов или кругов, разного размера. Эти фигуры нарисованы вместе с другими фигурами. Задается, например, круг. Решением будет, является все десять найденных кругов на рисунке. В данном случае все пропорции идеальны (предполагается, что человек ничего не рисует от руки) Какие есть алгоритмы для этой задачи? |
| Автор: val 21.7.2005, 16:46 |
| Я бы занялся вычислением и сравнением функции аппроксимации. А потом в качестве критерия для сравнения брал бы полученные функции с отброшенными коэффициентами. |
| Автор: DENNN 21.7.2005, 16:46 | ||
Очень простые. Находятся все точки, принадлежащие одной отдельно взятой фигуре, затем проверяется, соотвествует ли расположение точек геометрическому условию. Т.е., если ищешь круг, то лежат л все эти точки совместно на кривой, удовлетворяющей уравнению x^2+y^2=R^2. В первом приближении все просто пока не начнешь реализовывать  |
| Автор: maxim1000 21.7.2005, 16:53 | ||||
а они могут пересекаться? а то ведь
может вызвать трудности... |
| Автор: Alex101 21.7.2005, 17:13 |
| Тут главный вопрос - что является исходными данными. Когда ответ будет, тогда будет ясно как решать. |
| Автор: Royan 21.7.2005, 17:51 | ||
К сожалению этот подход не универсален, а если это восьмиугольник или еще что? Вот пример http://polfin.narod.ru/pict/pic1.PNG |
| Автор: Alex101 21.7.2005, 18:25 |
| Royan, как данные заданы? Эту задачу можно и аналитически решать и численно. |
| Автор: Royan 26.7.2005, 13:40 |
| В моем случае это практическая задача. Можно считать, что есть битмап и на нем разные фигурки. Соответственно все точки (пикселы) без проблем можно отличить друг от друга при этом пока условия достаточно просты - все фигуры исключительно черного цвета, а весь фон белый. Добавлено @ 13:41 Аналитечески или численно мне бы хоть идею подобрать... |
| Автор: DENNN 26.7.2005, 13:56 | ||
А если подумать?  Восьмиуголник задается как пересечение восьми линий. Просто условие чуть сложней -> при уравнивании по МНК чуть больше гемороя.Отдельно ищешь круги, отдельно квадраты, отдельно треугольники. Можешь сперва начать просто с поиска отдельных прямых отрезков. |
| Автор: Earnest 26.7.2005, 18:33 |
| Сначала ищешь просто замкнутые цепочки точек. Потом "примеряешь" к ним фигуры из списка (окружность, квадрат, и т.д.) и смотришь, на что больше похоже. "Больше похоже" - это какой-нибудь статистический критерий, например среднеквадратическая ошибка. Конечно, нужно нормировать на размер фигуры. С окружностью все просто (да и с любой полиномиальной кривой) - строешь ее МНК по всем точкам и смотришь ошибку. С квадратами и треугольниками похуже, поскольку сначала нужно выделить углы. При идеальных линиях это несложно - например, полигональная аппроксимация. По разбиению строишь отрезки, и т.д. Если все фигуры правильные, можно, как предложил DENNN, сделать предположение о положении углов, и написать уравнения МНК для каждой фигуры, но мне кажется, что проще разбить на отрезки. Да и универсальней это. Когда шум достаточно велик, или фигуры пересекаются - уже сложнее. Но в любом случае, начинать нужно с поиска простых цепочек. |
| Автор: Royan 27.7.2005, 12:52 |
| Не знаю знаком ли кто из вас с термином "Hough transform" так или иначе вот ссылка на ресурс http://rkb.home.cern.ch/rkb/AN16pp/node122.html, где об этом кое что говорится. Быть может, кто может высказать авторитетную мысль потому сможет ли это пригодится в моем случае или нет? На самом деле идея у меня была использовать какую-то технологию для обучения нейронной сетки, но похоже такая методика сложна из-за разных размеров фигур. Можно конечно попробовать сети типа SOM (Self organizing map) и таким образом попытаться выделить общие признаки. |
| Автор: DENNN 27.7.2005, 13:36 |
| Трансформация Хоуга - знаком. Первый патент датирован аж 1968 годом. Пытался использовать в своей научной работе. После различных экспериментов отказался от нее и открестился. Есть масса разных нюансов, которые неочевидны вначале. Например то, что каждая из точек на изображении должна быть посчитанна только одним элементом собирающей матрицы или то, что сама матрица дискретна и тем самым часто разбивает одну протяженную линию на несколько оиентированных совершенно по разному. Лучше всего этот алгоритм реализован в Intel OpenCV. ДЛя устранения многих проблем есть даже модификация, называемая "адоптируемая модель Хоуга" (или нечто такое, могу ошибаться). Но в целом, алгоритм хорошь на лишь на самых элемнтарных задачах, для распознавания фигур и пр. лучше исать более продуктивные решения. Нейронная сетка могла бы помочь, если у тебя просто есть изображение с одной фигурой. Иначе слишком это сложная задача - не ясно сколько слоев необходимо, как обучать и пр.. Очень интересные результаты дают методы, в которых фигуры и эталоны координируются не декартовыми координатами, а полярными. Но мой тебе совет: займись сначала задачей просто выделения контура, а уже после интерпертацией групп пикселей. |
| Автор: Royan 27.7.2005, 17:40 | ||
Нет, идея не в лоб учить сетку. В такой задаче надо последовательно использовать несколько сеток, одна выделяет регионы, где находятся фигуры другая, например, выполняет классификацию каких одних фигур, далее третья уже распознает настоящие фигуры. |
| Автор: Earnest 28.7.2005, 07:33 |
| Согласна с DENNN и насчет сетки, и насчет Hough transform. Только по-моему, по русски - это преобразование Хафа, а не Хоуга. Короче, выглядит элегантно и вроде подкупает простотой - на первый взгляд. Но при попытке реализовать быстро выясняется, что идентифицировать факт, что прямая с такими-то параметрами есть, достаточно легко (с учетом шума и т.д.) Но вот какие именно точки составляют прямую, начало-конец отрезка - как только пытаешься все это учесть-запомнить, такой геморрой наступает, что все изящество преобразования как-то теряется. Причем для обнаружения окружностей нужно другое преобразование, уже посложнее. Поиграться в Хафа можно, даже интересно, с познавательной точки зрения, но с практической, ИМХО, нужно сначала выделить контура, а потом попытаться классифицировать. |
| Автор: DENNN 28.7.2005, 08:51 | ||
Да. Только в литературе обычно употребляется "преобразование Хоуг" (например К.Фу, Н.Гонсалес, К.Ли "Робототехника"), а в интернете более жаргонное "преобразование Хафа". ИМХО, первое более верно, т.к. более схоже с ангийским звучанием. |
| Автор: Earnest 28.7.2005, 13:54 |
Английское "hough" читается вовсе не "хоуг", а [hok], причем в середине не [о], а такой знак с дыркой слева, нечто среднее между a и о. Насчет "в литературе" ... это ведь англо-язычные источники, а что там переводчик написал - его проблемы. "Хаф" или "Хоф", конечно, не очень правильно, но "Хоуг" - это уже вообще беда  . Сама знаю, что офф-топик.  |