Всем привет,

Есть такая задача, пусть есть 10 идентичных фигур, в простейшем случае квадратов или кругов, разного размера. Эти фигуры нарисованы вместе с другими фигурами. Задается, например, круг. Решением будет, является все десять найденных кругов на рисунке. В данном случае все пропорции идеальны (предполагается, что человек ничего не рисует от руки)

Какие есть алгоритмы для этой задачи?

Я бы занялся вычислением и сравнением функции аппроксимации. А потом в качестве критерия для сравнения брал бы полученные функции с отброшенными коэффициентами.

Цитата(Royan @ 21.7.2005, 16:35)

Какие есть алгоритмы для этой задачи?

Очень простые. Находятся все точки, принадлежащие одной отдельно взятой фигуре, затем проверяется, соотвествует ли расположение точек геометрическому условию. Т.е., если ищешь круг, то лежат л все эти точки совместно на кривой, удовлетворяющей уравнению x^2+y^2=R^2. В первом приближении все просто пока не начнешь реализовывать

Цитата

Эти фигуры нарисованы вместе с другими фигурами

а они могут пересекаться?
а то ведь

Цитата

Находятся все точки, принадлежащие одной отдельно взятой фигуре

может вызвать трудности...

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

Цитата

Т.е., если ищешь круг, то лежат л все эти точки совместно на кривой, удовлетворяющей уравнению x^2+y^2=R^2

К сожалению этот подход не универсален, а если это восьмиугольник или еще что?
Вот пример
http://polfin.narod.ru/pict/pic1.PNG

Это сообщение отредактировал(а) Royan - 21.7.2005, 17:52

Royan,
как данные заданы?
Эту задачу можно и аналитически решать и численно.

В моем случае это практическая задача. Можно считать, что есть битмап и на нем разные фигурки. Соответственно все точки (пикселы) без проблем можно отличить друг от друга при этом пока условия достаточно просты - все фигуры исключительно черного цвета, а весь фон белый.
Добавлено @ 13:41
Аналитечески или численно мне бы хоть идею подобрать...

Цитата(Royan @ 21.7.2005, 17:51)

Цитата Т.е., если ищешь круг, то лежат л все эти точки совместно на кривой, удовлетворяющей уравнению x^2+y^2=R^2 К сожалению этот подход не универсален, а если это восьмиугольник или еще что?

А если подумать? Восьмиуголник задается как пересечение восьми линий. Просто условие чуть сложней -> при уравнивании по МНК чуть больше гемороя.

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

Сначала ищешь просто замкнутые цепочки точек. Потом "примеряешь" к ним фигуры из списка (окружность, квадрат, и т.д.) и смотришь, на что больше похоже.
"Больше похоже" - это какой-нибудь статистический критерий, например среднеквадратическая ошибка. Конечно, нужно нормировать на размер фигуры.
С окружностью все просто (да и с любой полиномиальной кривой) - строешь ее МНК по всем точкам и смотришь ошибку. С квадратами и треугольниками похуже, поскольку сначала нужно выделить углы. При идеальных линиях это несложно - например, полигональная аппроксимация. По разбиению строишь отрезки, и т.д.

Если все фигуры правильные, можно, как предложил DENNN, сделать предположение о положении углов, и написать уравнения МНК для каждой фигуры, но мне кажется, что проще разбить на отрезки. Да и универсальней это.

Когда шум достаточно велик, или фигуры пересекаются - уже сложнее.
Но в любом случае, начинать нужно с поиска простых цепочек.

Не знаю знаком ли кто из вас с термином "Hough transform" так или иначе вот ссылка на ресурс http://rkb.home.cern.ch/rkb/AN16pp/node122.html, где об этом кое что говорится. Быть может, кто может высказать авторитетную мысль потому сможет ли это пригодится в моем случае или нет?

На самом деле идея у меня была использовать какую-то технологию для обучения нейронной сетки, но похоже такая методика сложна из-за разных размеров фигур. Можно конечно попробовать сети типа SOM (Self organizing map) и таким образом попытаться выделить общие признаки.

Трансформация Хоуга - знаком. Первый патент датирован аж 1968 годом. Пытался использовать в своей научной работе. После различных экспериментов отказался от нее и открестился. Есть масса разных нюансов, которые неочевидны вначале. Например то, что каждая из точек на изображении должна быть посчитанна только одним элементом собирающей матрицы или то, что сама матрица дискретна и тем самым часто разбивает одну протяженную линию на несколько оиентированных совершенно по разному. Лучше всего этот алгоритм реализован в Intel OpenCV. ДЛя устранения многих проблем есть даже модификация, называемая "адоптируемая модель Хоуга" (или нечто такое, могу ошибаться). Но в целом, алгоритм хорошь на лишь на самых элемнтарных задачах, для распознавания фигур и пр. лучше исать более продуктивные решения.

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

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

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

Цитата

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

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

Согласна с DENNN и насчет сетки, и насчет Hough transform. Только по-моему, по русски - это преобразование Хафа, а не Хоуга. Короче, выглядит элегантно и вроде подкупает простотой - на первый взгляд. Но при попытке реализовать быстро выясняется, что идентифицировать факт, что прямая с такими-то параметрами есть, достаточно легко (с учетом шума и т.д.) Но вот какие именно точки составляют прямую, начало-конец отрезка - как только пытаешься все это учесть-запомнить, такой геморрой наступает, что все изящество преобразования как-то теряется. Причем для обнаружения окружностей нужно другое преобразование, уже посложнее.
Поиграться в Хафа можно, даже интересно, с познавательной точки зрения, но с практической, ИМХО, нужно сначала выделить контура, а потом попытаться классифицировать.

Цитата(Earnest @ 28.7.2005, 07:33)

и насчет Hough transform. Только по-моему, по русски - это преобразование Хафа, а не Хоуга.

Да. Только в литературе обычно употребляется "преобразование Хоуг" (например К.Фу, Н.Гонсалес, К.Ли "Робототехника"), а в интернете более жаргонное "преобразование Хафа". ИМХО, первое более верно, т.к. более схоже с ангийским звучанием.