Сравнение объектов контурным анализом.

[2expres 7]

Занимаюсь сравнением объектов методом контурного анализа. Получил 2 периодических последовательности данных, искомый объект и эталон (128 значений последовательности). Последовательность не зависит от местоположения, угла поворота и масштаба. Они отличаются только выбором начальной точки. Если делать сравнение методом перебора, нужно сравнить 128х128 значений. У меня ~3000 контуров в изображении и 200 эталонов. Может кто то знает более быстрый способ совмещения начальных точек или сравнения. График последовательностей на 36 точек представлен ниже, точки периодически повторяются:

[Smorodov 578]

FFT кросскорреляцией можно попробовать. https://dsp.stackexchange.com/questions/736/how-do-i-implement-cross-correlation-to-prove-two-audio-files-are-similar

[2expres 7]

Мне предложили делать сравнение сигналов с эталонами не методом перебора, а с помощью дескрипторов Фурье. Дескрипторы сигналов я вычисляю быстро применяя табличные коэффициенты. Дескрипторы эталонов вычисляю заранее. 
Сколько необходимо дескрипторов и как их сравнивать на подобие?

[Smorodov 578]

Посмотрите здесь: 

Количество дескрипторов, задает насколько детально описывается фигура. Подрезание количества коэффициентов дает сглаживание контуров. 

 

Еще тут посмотрите: https://www.codeproject.com/Articles/196168/Contour-Analysis-for-Image-Recognition-in-C

 

 

[2expres 7]

1 час назад, Smorodov сказал:

Посмотрите здесь: 

Количество дескрипторов, задает насколько детально описывается фигура. Подрезание количества коэффициентов дает сглаживание контуров. 

 

Еще тут посмотрите: https://www.codeproject.com/Articles/196168/Contour-Analysis-for-Image-Recognition-in-C

 

 

Спасибо, за ответ. Ссылку я уже видел ранее. Именно она вдохновила меня на распознавание шрифтов, но другим способом. В данной ссылке автор Pavel Torgashov применяет 30 элементарных векторов. Я считаю, что даже для шрифта это недостаточно и применяю 128.

У меня всегда любой контур описывается 128 элементарными векторами (ЭВ). Соответственно эталоны так же описаны, как 128 ЭВ. В данном случае максимальное число дескрипторов Фурье может быть 128. Я хочу выбрать 8. Это 6,25%, достаточно ли это распознавания шрифта? Так же не понятно, как сравнивать дескрипторы, какую брать погрешность?

 

[Smorodov 578]

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

Вообще еще один метод есть, вычисляются собственные векторы и числа, и оставляют количество векторов, сумма собственных чисел которых равна, скажем 95% от всей суммы чисел.  Смотрите PCA анализ.

[2expres 7]

Дескрипторы можно сравнивать 2 способами: 

1) находим погрешность каждого из дескрипторов, погрешности складываем и сравниваем с порогом. Возможно погрешности возводим в  квадрат и суммируем.

2) сравниваем с порогом каждую погрешность и если один из дескрипторов превышает порог, то сравнения нет.

Какой из двух способов верный?

[Smorodov 578]

Это называется метрики, их не две, а намного больше самые популярные:

1) Евклидова метрика.

2) чем то напоминает дистанцию Хемминга, но там тоже сумма считается. https://ru.wikipedia.org/wiki/Расстояние_Хэмминга 

3)   https://ru.wikipedia.org/wiki/Расстояние_Махаланобиса 

4)  https://ru.wikipedia.org/wiki/Расстояние_городских_кварталов 

Опять же надо подбирать экспериментально.

 

[ArtemBogatov 2]

В контрибах OpenCV реализовано сравнение контуров на основе дескрипторов Фурье. Вот ссылка на пример использования https://github.com/opencv/opencv_contrib/blob/master/modules/ximgproc/samples/fourier_descriptors_demo.cpp

[2expres 7]

Закончил программу контурного анализа. Перепробовал множество вариантов. Применял дескрипторы Фурье - получил не очень хороший результат. Оказалось, что примитивные методы работают значительно лучше. Результат меня порадовал. Удалось получить быстрое распознавание любых замкнутых контуров. В качестве базы данных загружаются изображения в виде силуэта эталонных символов. Программа создает базу данных. Один силуэт это 512 байт в базе данных. Силуэты могут быть любые шрифты (Если буква "В", то без двух белых отверстий), предметы, дорожные знаки, силуэты самолетов и т.д. 

Тренировался на шрифте. Распознает любой шрифт повернутый до углов 45 градусов при условии совпадения начальных точек. Проблему начальной точки решил за счет того что в базу данных загружаю 2 символа один повернут влево на 20, другой вправо на 20 градусов. Теоретически возможно распознавание под любым углом, но при этом будет увеличиваться время обработки. Пример базы цифр ниже:

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