Recognition (Yeremeyev method)

EDV

Доброго всем времени суток!

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

Моё имя - Еремеев Дмитрий Владимирович (EDV). Будем пока называть метод распознавания – чёрным ящиком, а что бы было удобнее, конкретизируем название так:
Associative Video Memory - Yeremeyev method или AVMY.

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

Ну что же, а теперь коротко описание пакета. Файл RcgEDV_Demo.zip содержит демонстрационную версию метода AVMY в бинарном виде (файл RcgExample.exe) и в виде исходного текста программы (файл RcgExample.dsw). Реализация самого метода AVMY представлена в виде статической библиотеки rcg.lib.

По поводу ассоциативной видео памяти вам необходимо знать только одно: входное изображение используется в качестве ключа для доступа к данным для операции чтение/запись. В данной реализации память хранит значения целого типа (int).

Интерфейс с ассоциативной памятью прост:

Код:

// Associative memory class for integer data
class CvAssociativeMemory16S {
   void* p;
public:
   CvAssociativeMemory16S();
   ~CvAssociativeMemory16S();
   
   // Creating of associative memory
   bool Create(CvSize aKeyImgSize, CvMemStorage*  apMemStorage, short aLevelMax = 0);

   // Set an image for processing
   void SetImage(const void* apSrcImg);

   // Reading from associative memory cell (associative base)
   bool Read(CvRect aInterestArea, int** appData,
            uint64* apIndex = NULL, uint64* apHitCounter = NULL);

   // Writing to associative memory cell
   void Write(CvRect aInterestArea, int* apData);

   // Object recognition
   void Recognition(CvRcgAMFunc16S RcgAMFunc, void *args = NULL);

   // Saving of recognition data
   bool Save(char* aFileName);
   // Loading of recognition data
   bool Load(char* aFileName);
   
   // Get current index of associative base
   uint64 GetCurIndex();
   // Get total number of associative bases
   long   GetTotalABases();
   // Get total number of memory levels
   short  GetTotalLevels();
};

Ну что же, вот пожалуй и всё. Если будут вопросы, пишите

EDV

Я закончил работу над следующей версией ассоциативной видео памяти (v0.2).

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

EDV

Ну что же, пришло время немного рассказать о принципах работы «AVMY» (но исходников не ждите). Ассоциативная видеопамять основана на многоуровневой декомпозиции матриц распознавания. «AVMY» состоит из дерева ассоциативных ядер и использует входное изображение как ключ для доступа к данным. Это означает, что для каждого объекта «AVMY» ставит в соответствие набор образов. Образная информация содержится в «ассоциативном ядре» в виде матрицы распознавания, так же ядро содержит данные, которые были записаны методом “Write”.
Одна небольшая фирма, даже провела серию тестов, так что интерес к идее есть.

Цитата:

Hello

We tested your algorithm by different ways and conditions, and provide you with
the best results we manage to achieve. We test on a selection of 32 object from ALOI
database and best test results have been gotten with the following conditions:

Minimum rectangle dimensions is 181 pixels for ‘Write’ method
Entire image is taken as interest rectangle for the ‘Read’ method
Each different object is stored in the separate associative network
We tested 2 key image sizes - 80, 160 pixels
We tested with 2 search steps, 15, 5 pixels
Some test details are in the table below and in attached graph with rocs.
http://keep4u.ru/full/080109/72b147b41724eba246/jpg

Код:

|----------+-------------------------+-------------------------|
|times in  |       Extraction        |        Matching         |
|mls.      |-------+--------+--------|-------+--------+--------|
|          |  Min  |   Max  |average |  Min  |   Max  |average |
|----------+-------+--------+--------+-------+--------+--------|
|{-rival-} |280.174|1648.029|533.0843| 1.844 |101.077 |14.40634|
|          |       |        |        |       |        |        |
|AVM 80X80 | 2.425 | 3.717  |3.08875 | 7.402 |169.343 |20.02165|
|ST 15     |       |        |        |       |        |        |
|          |       |        |        |       |        |        |
|AVM 80X80 | 2.425 | 3.717  |3.08875 |73.678 |1272.533|208.5516|
|ST 5      |       |        |        |       |        |        |
|----------+-------+--------+--------+-------+--------+--------|

Our test shows what significantly better recognition quality is for smaller (80 pixels)
key image size and for smaller (5 pixels) search step. However with smaller search step
the algorithm becomes much slower. As comparing with {rival method}, {rival method} has better
recognition quality, slower extraction and at least comparable matching speed.

Demo:
http://edv-detail.narod.ru/RcgEDV.html
http://edv-detail.narod.ru/RcgEDV_Demo_v0-2.zip

Similarity diagram for different key image size:
http://keep4u.ru/full/071218/b02041500f4484436b/jpg - key size 80x80;
http://keep4u.ru/full/071218/50049c0688ae2a67e9/jpg - key size 160x160;
http://keep4u.ru/full/071218/26f9022e8ba56386a7/jpg - key size 320x320;
http://keep4u.ru/full/071218/3026c2b866440371b8/jpg - key size 640x640;
or download all JPG from: http://edv-detail.narod.ru/KeySizeCmp.zip

=DeaD=

Если я правильно понимаю - речь идёт о том, что вы придумали метод сопоставления двух изображений одинакового размера - так? А чтобы искать их на картинке - вам требуется перебор, так?

Сам метод сопоставления более менее понятно как реализован (экспертная система для изображений раскладывающая возможные варианты образов в дерево), - тут тоже правильно понял?

EDV

=DeaD= писал(а):

Если я правильно понимаю - речь идёт о том, что вы придумали метод сопоставления двух изображений одинакового размера - так? А чтобы искать их на картинке - вам требуется перебор, так?

Сам метод сопоставления более менее понятно как реализован (экспертная система для изображений раскладывающая возможные варианты образов в дерево), - тут тоже правильно понял?

Ну не совсем так. Матрица распознавания содержит пространственное распределение участков яркости, представленное в инвариантном виде. Распознавание такой матрицей хорошо масштабируется, устойчиво к шумам камеры и не зависит от изменения освещения (больше света/меньше света). В принципе, просто набора матриц вполне достаточно для самого процесса распознавания, а многоуровневая декомпозиция матриц (дерево), нужно только для увеличения скорости поиска в памяти.

Виталий

Цитата:

и не зависит от изменения освещения (больше света/меньше света)

Наверное все-таки мало зависит =)

А что за инвариантное представление?

=DeaD=

EDV писал(а):

Ну не совсем так. Матрица распознавания содержит пространственное распределение участков яркости, представленное в инвариантном виде. Распознавание такой матрицей хорошо масштабируется, устойчиво к шумам камеры и не зависит от изменения освещения (больше света/меньше света).

Инвариантность выполняется относительно чего, кроме мелких шумов и общего уровня освещения?

EDV

Виталий писал(а):

Цитата:

и не зависит от изменения освещения (больше света/меньше света)

Наверное все-таки мало зависит =)

А что за инвариантное представление?

Имеется в виду, что в матрице хранятся не сами значения яркости (конкретные значения параметров), а соотношения между ними (инварианты).

=DeaD= писал(а):

Инвариантность выполняется относительно чего, кроме мелких шумов и общего уровня освещения?

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

=DeaD=

EDV писал(а):

Имеется в виду, что в матрице хранятся не сами значения яркости (конкретные значения параметров), а соотношения между ними (инварианты).

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

А в чем ноу-хау тогда? В нормализации яркости и поиске объекта в разных масштабах? Так это же не ахти какая производительность...

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

EDV

=DeaD= писал(а):

А в чем ноу-хау тогда? В нормализации яркости и поиске объекта в разных масштабах? Так это же не ахти какая производительность...

Ноу-хау в простоте метода, почему-то господа учёные склоны всё усложнять

Быстродействие достаточно высокое, можете сами в этом убедиться

Цитата:

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

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

=DeaD=

EDV писал(а):

Ноу-хау в простоте метода, почему-то господа учёные склоны всё усложнять

Быстродействие достаточно высокое, можете сами в этом убедиться

Прошу прощения за резкий скептицизм!

просто видимо у меня были завышеные ожидания в связи с кажущейся мне сложностью описания вашего метода

EDV писал(а):

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

Не спорю

А всё-таки повороты под разными углами вы получается перебираете?

EDV

Цитата:

А всё-таки повороты под разными углами вы получается перебираете?

Да, приходится ассоциировать сразу несколько матриц распознавания с одним и тем же объектом, который был показан под различными углами. Соответственно, когда система распознавания видит этот объект, под углом, с которым проассоциирована одна из матриц, то происходит распознавание, если показать тот же объект, но под другим углом, под которым его не показывали в процессе обучения, то объект не будет распознан (не одна матрица с ним не совпадёт).

=DeaD=

EDV писал(а):

Цитата:

А всё-таки повороты под разными углами вы получается перебираете?

Да, приходится ассоциировать сразу несколько матриц распознавания с одним и тем же объектом, который был показан под различными углами. Соответственно, когда система распознавания видит этот объект, под углом, с которым проассоциирована одна из матриц, то происходит распознавание, если показать тот же объект, но под другим углом, под которым его не показывали в процессе обучения, то объект не будет распознан (не одна матрица с ним не совпадёт).

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

Еще может быть хитрый ход как дерево должно самоорганизовываться... тут никаких вещей серьезных не сделано?

EDV

Цитата:

Еще может быть хитрый ход как дерево должно самоорганизовываться... тут никаких вещей серьезных не сделано?

Да, и тут есть одна хитрость. Господа учёные часто используют в методах распознавания различные алгоритмы кластеризации/классификации (Кохонен, метод K средних, иерархическая кластеризация, дендрограммы). В ассоциативном дереве «AVMY» по ходу обучения выполняется оптимизация, в процессе которой, малоиспользуемые образы удаляются из дерева. Получается, некоторая кластеризация по образам, что бы образ закрепился в «AVMY», он должен часто встречаться (устойчивая ассоциация).

=DeaD=

EDV писал(а):

Да, и тут есть одна хитрость. Господа учёные часто используют в методах распознавания различные алгоритмы кластеризации/классификации (Кохонен, метод K средних, иерархическая кластеризация, дендрограммы). В ассоциативном дереве «AVMY» по ходу обучения выполняется оптимизация, в процессе которой, малоиспользуемые образы удаляются из дерева. Получается, некоторая кластеризация по образам, что бы образ закрепился в «AVMY», он должен часто встречаться (устойчивая ассоциация).

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

roboforum.ru

Recognition (Yeremeyev method)

Кто сейчас на конференции