Распознавание геометрических фигур на плоскости

На плоскости появляются фигуры (их окаймления) в виде массива координат X, Y. Каждый раз появляется какая то одна фигура. Требуется определить к какому классу она принадлежит. Всего 9 классов. Фигура может быть большой или маленькой, повернутой на какой то угол, но принадлежность к классу на глаз определяется однозначно.

Как на основании массива координат точек определить класс к которому принадлежит конкретная фигура?
Здесь примерные данные, наборы координат X, Y для каждого класса http://antifile.ru/9804148

Можно делать по разному. Окружности легко находить методом Хафа. Фигуры типа 9 - обходим контур, если вектор обхода часто меняется - значит точно оно Для эллипсов - тож хафа пойдёт. Тип 7 - это две кривых, вот их и нужно искать. ТИп 2,3 и 4 - находим прямые отдельные, из них пробуем собрать эти фигуры.

Можно ввести несколько простых статистических оценок, вроде компактности (отношение квадрата периметра к площади) и эксцентриситета области. Это позволит если и не определить однозначно класс фигуры, но сразу исключить классы, которым фигура не может принадлежать. Ну и преобразование Хафа тоже поможет.

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

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

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

С сердем немного сложновато, надо подумать.

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

Tur
Тут лучше всего подойдут коэфициенты фурье.Для контура, делаем преобразование фурье нормируем на первый член, получаем инвориантные(независещее) от поворота и маштаба коэффициенты. Дальше я думою проверять принадлежность к классу припомощи корреляции. Этот метод мне кажется наиболее подходящим так как сразу дает ответ для всех типов фигур.

Добавлено 30.12.08, 14:36
Еще в дагонку. Можно также еще оценивать через вайвлеты.

Цитата

Все продвинутые методы (LDA, SVM, нейронные сети, деревья решений и случайные леса) в моем понимании предназначены для случаев когда человеческая интуиция не годится (например, интуиция обычно пасует перед многомерными задачами).

Да, спасибо, хорошо, что вы это сказали. Метод Хафа пока не понял. Сделал вот что. Нашел для каждой фигуры центр масс и от него все радиусы, для каждой точки. Вот что получилось

Здесь по Х номер точки из массива, а по Y радиус от центра масс до текущей точки из входного массива. Самое простое это окружность: если макс - мин < 0.05 значит окружность. Следующий график квадрат 2. Четыре максимума, четыре минимума. Расстояние между минимумами или максимумами не совпадают потому что точки исходного массива квадрата расположены не равномерно по углу от центра масс.

Эта же непредсказуемая неравномерность относится ко всем массивам, ко всем фигурам. Эти исходные массивы получаются из матрицы пикселей. Расстояние между пикселями 5 микрон. Число точек на линии зависит от ее расположенности на матрице. Следующий график 3 квадрат с обрезанными углами. У него также срезаны максимумы. Следующий 4-тый график с выраженными изломами сверху. Пока неясно как определить точки этих изломов. Следующий эллипс и т.д. пока неясно по каким параметрам отличать. Programmer768, albom, shadeofgray, что вы думаете по такому моему заходу? Быть может он достаточен, только его надо продуманно завершить? Может быть есть предложения как, какие параметры вычислять?

Pavia, я не понял про фурье. Фурье для меня связано с сигналами, а тут контур. Что это такое фурье для контура?

Сообщение отредактировано: Tur - 30.12.08, 16:19

Цитата Tur @ 30.12.08, 16:11

Pavia, я не понял про фурье. Фурье для меня связано с сигналами, а тут контур. Что это такое фурье для контура?

У тебя есть контур

Цитата Tur @ 29.12.08, 16:18

их окаймления

Он, описывается точками x,y пусть p=x+iy. Тем самым имеем комплексный набор данных. Тоесть по сути сигнал.
Дальше считаем Фурье получаем так называемые Фурье дескрипторы или коэфициенты Фурье. Дальше чтобы применить их к распознованию их нормируют. Делят на первый член. Деления комплексное. Тем самым когда мы делим у нас получается что Ai/A1 амплитуды норируются значит фигура не будет зависить от маштаба. И второе когда мы делем у нас происходит вычитание фазы фi-ф1 тем самым мы уходим от поворота. Получается что в зависимости от количества углов у нас будут разные частоты. вытенутые фигуры должны отличаться амплитудами в положительном и отрицательных частотах.
И еще нуливой коэфициент не учитываем для инвариантности к перемещению.

Не забывайте что метод Хафа имеет очень много ограничений:

Wiki:
Преобразование Хафа эффективно только при значительном количестве "попаданий" в соответствующий элемент пространства Хафа, только тогда можно с уверенностью определить фигуру пренебрегая фоновым шумом. Это значит что размер элемента не должен быть очень маленьким, иначе некоторые значения попадут в соседние элементы, уменьшая видимость нужного элемента.

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

И последнее, эффективность алгоритма в большой степени обусловлена качеством входных данных: границы должны быть четко определены. Использование преобразования Хафа на зашумленных изображениях затруднено. Для зашумленных изображений необходим этап предобработки с целью подавления шума. В случае если изображение повреждено speckle, как в случае с изображением с радара, Преобразование Радона предпочтительнее для определения линий, т.к. она имеет хороший эффект шумоподавления при суммировании.


Я считаю использование нейронных сетей будет предпочтительней(ну конечно это зависит от предпочитаемой степени точности и гибкости вашей программы).

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

Цитата Dethlord @ 31.12.08, 05:05

Я считаю использование нейронных сетей будет предпочтительней(ну конечно это зависит от предпочитаемой степени точности и гибкости вашей программы).

Основной причиной, по которой я не рекомендую использование продвинутых методов, является то, что они требуют формирования обучающей выборки, причем довольно-таки обширной. Условно говоря, если у вас есть квадрат и прямоугольник, то в выборке должны быть и квадраты, и прямоугольники самых разных пропорций, чтобы нейронная сеть могла определить, что считать квадратом, а что - прямоугольником. Граница между этими двумя классами должна быть довольно-таки плотно покрыта элементами обучающего множества, чтобы было ясно - с какого именно момента прямоугольник становится квадратом (понятно, что если квадрат "немного вытянут", то он остается квадратом - но чему равно "немного"?). Т.е. придется вручную составлять большое количество разнообразных случаев и решать, что к какому классу относится. И даже тогда в пространстве между классами останется большое белое пятно - "то ли угловатый круг, то ли квадрат с очень сильно закругленными краями", "то ли сердце, то ли эллипс с заостренным концом" и т.д.

Здесь на самом деле конкурируют друг с другом два подхода. Первый - в каком-то смысле имитация человеческого зрения, обнаружение на изображении различных элементов, строительных блоков высокого уровня (углы, лучи, окружности). Это то, о чем я говорил в начале, и здесь лучше сработает ручное составление решающих правил (ИМХО). Второй подход - это то, что вы сейчас делаете с Фурье - выделение сравнительно низкоуровневых особенностей (коэффициентов Фурье).

Если уж вы начали возиться с Фурье, то здесь ручная работа не годится - действительно, лучше использовать стандартные алгоритмы машинного обучения. Либо нейронные сети, либо SVM. Правда, здесь придется изучить ряд сопутствующих техник для улучшения качества решения и проверки способности к обобщению (feature selection, регуляризация, кросс-валидация). Без этого вы вполне можете получить нейронную сеть, которая абсолютно точно классифицирует образы из обучающего множества, но вот то, что к обучающему множеству не относится, она классифицирует из рук вон плохо. Т.е. просто взять нейронную сеть побольше, обучить и удовлетвориться этим нельзя. В википедии есть статья http://en.wikipedia.org/wiki/Runge's_phenomenon в которой приведен пример чего-то отдаленно похожего - интерполяционный полином в точности проходит через все предписанные точки, но между ними ведет себя непредсказуемо.

Исходники для работы с нейронными сетями можно посмотреть по адресу http://alglib.sources.ru/neuralnetworks/multilayerperceptron.php Там не самая свежая версия (как раз сейчас у меня в разработке находится новая версия нейросетевой библиотеки), но она достаточно хороша и содержит возможности, которые отсутствуют во многих нейросетевых пакетах с открытым кодом (современный квази-Ньютоновский алгоритм обучения вместо устаревшего и тормозного градиентного спуска, регуляризация, кросс-валидационная оценка ошибки обобщения). Если захотите использовать Support Vector Machine, то надо поискать в инете, но возможно вам хватит и нейронных сетей. На самом деле ещё куча методов есть (random forests, например, очень интересный алгоритм), но наверное хватит и НС. Главное помните - ваша задача составить как можно более разнообразную обучающую выборку, обойтись как можно меньшим количеством используемых переменных (возьмете сто тысяч коэффициентов Фурье - и вы получите нулевую ошибку на обучающем множестве, но ужасную ошибку обобщения) и как можно меньшим количеством нейронов в сети. советую почитать http://www.faqs.org/faqs/ai-faq/neural-nets/

Добавлено 31.12.08, 08:08
Можно кстати взять те графики, которые вы построили, нормировать, взять от них Фурье - и вы получите независимость от поворота и масштабирования. Взять несколько коэффициентов Фурье (достаточно много, чтобы классы было можно разделить - но достаточно мало, чтобы не было проблем с обобщением), и уже их загонять в НС.

Я бы взял на вооружение метод, предложенный Pavia. С ним будет проще разбираться и реализовывать в программе.

Спасибо всем за отклик. Вот что получилось. Алгоритм Pavia на матлабе.

Цитата

p = x + j*y;
Y = fft(p);
Y2 = Y./Y(1);
Y3 = Y2(2:end);
X = ifft(Y3);
AX = abs(X);

subplot(1,4,1); plot(x,y,'-');
subplot(1,4,2); plot(real(X),imag(X),'r-');
subplot(1,4,3); stem(Y3(1:20),'-');
subplot(1,4,4); plot(AX,'-');

Назовем это Рис.4
Все ли я сделал верно? Не видно какие корреляции считать. Надо еще проверить fft к графикам R от центра фигуры до ее контура от номера точки на рисунке 2 в этой теме.
shadeofgray, НС не хочу, с выборками замучаюсь, а вот этим

Цитата

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

займусь в ближайшее время.

Да, Pavia, хороший подарочек на новый год (без иронии, хотя бы fft вспомнил, несколько функций написал).

Цитата Tur @ 08.01.09, 17:18

Все ли я сделал верно?

Неверно. Нужно было занулить нуливой элемент Y2 вместо того, чтобы копировать со второго элемента.
И еще чутье мне говорит, что там у тебя не комплексное деление. И частоты выведи также отрицательные так как от положительных они отличаются.
С матлабом почти не работал. Теория есть в книге "Яне Цифровая обработка изображений" и в интернете пару раз натыкался на подобный матерьял.

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

Цитата

p = x + j*y;
Y = fft(p);
Y2 = Y./Y(1); % деление комплексное, проверял
Y2(1) = 0;
X = ifft(Y2); % обратное fft
AX = abs(X); % амплитуды, дескрипторы
ang = angle(Y2); % это фаза

subplot(1,4,1); plot(x,y,'-');
subplot(1,4,2); plot(X,'r-');
subplot(1,4,3); plot(ang,'-');
subplot(1,4,4); plot(AX,'-');

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

Сейчас уже стало ясно, что задача эта как и говорил shadeofgray сравнительно простая. Позднее выложу решение.

Tur
Вначале идут положительный частоты. А после половины отрицательные.
0,1,2,3...N/2, -(N/2-1),-(N/2-2),...-2,-1

Перечитал книжку оказыывается с делением я ошибся. Для независимости от фазы нужно вычестить фазы фi-i*ф1.
А для инвариантности к маштабу делить на модуль первого члена.

PS. А не моглибы скинуть вашу базу данных. Если это возможно. Можно и в приват.

Сообщение отредактировано: Pavia - 11.01.09, 20:09

Pavia, спасибо тебе за внимание и за книжку, правда не было времени пока посмотреть ее внимательно. На какой стр там все это изложено?

Цитата

Вначале идут положительный частоты. А после половины отрицательные.
0,1,2,3...N/2, -(N/2-1),-(N/2-2),...-2,-1

Как найти хотя бы одну частоту для контура и что такое частота в данном случае когда времени нет?

Цитата

Для независимости от фазы нужно вычестить фазы фi-i*ф1.

Может быть ты здесь ошибся и надо вычесть из каждой фазы первую фазу, т.е. записать это так ф(i) - ф(1) ?
Базу данных я уже в первом посту выложил, но видимо неудачно. Ты не знаешь куда ее можно закачать? Вот с картинками я пользуюсь вот этим http://www.radikal.ru/ удобным сервисом, но кроме картинок он ничего не принимает.
Сейчас я подготовлю новую базу данных в экселе и закачаю куда укажешь, лучше на общий обзор. Это все пока модельные данные, настоящие файлы пойдут через пару недель.

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

Вот база данных в экселе, и вот код в матлабе ее открывающий

Цитата

function openexcel
[data, headertext] = xlsread('D:\Prog\MAT\Projects\Ver13\private\Formy2-8_3.xls');
[row,col]=size(data); data = data(3:row,1:col); f = [];
for i = 1:21
f(i).d = data(:,(2*i-1):2*i); f(i).d(any(isnan(f(i).d),2),: ) = [];
f = radiuses(f,i);
end
end

function f = radiuses(f,ind)
f(ind).Mc = centermass(f(ind).d); X = f(ind).Mc.X; Y = f(ind).Mc.Y;
for i = 1:length(f(ind).d)
f(ind).r(i) = sqrt((X-f(ind).d(i,1))^2+(Y-f(ind).d(i,2))^2);
end
end

function M = centermass(a)
n = length(a); M.X = sum(a(:,1))/n; M.Y = sum(a(:,2))/n;
end

В структуре f все данные и результаты вычислений: f.d - исходные данные, f.Mc - центр фигуры(точка О на графике эллипса), f.r - расстояния от центра фигуры до точек ее контура.
Идея решения состоит в движении от графика радиусов к контуру. Как определить, например, что данная фигура эллипс? Вычисляется максимальный радиус max(f.r), допустим точка А. Продолжаем АО до пересечения в точке В. Если eps < abs(AO - OB), то это не эллипс (eps - вычисляется опытным путем), иначе проводим СD. Находим а и b и ур-е эллипса. Теперь любую точку на контуре можно проверить на принадлежность к этому уравнению. Вычисляем напр x^2/a^2 + y^2/b^2 = F(i) для всех точек и проверяем девиацию F.

Сообщение отредактировано: Tur - 13.01.09, 10:13

Tur не могли бы Вы скинуть вашу базу данных, если это возможно, на email: rrazer@mail.ru. Хотел бы попробовать решить эту задачу с помощью нейросетей. Заранее спасибо