Индивидуальный выбор оптимального количества особенностей при распознавании графических образов / Теория распознавания образов / Recog.ru - Распознавание образов для программистов


Индивидуальный выбор оптимального количества особенностей при распознавании графических образов

         Существует целый класс алгоритмов распознавания графических образов, основанных на сопоставлении некоторых особенностей («особых» точек) неизвестного объекта с эталонными образами. Один из наиболее известных механизмов выделения особенностей представлен в работе [4] и реализован в популярной программной библиотеке OpenCV. Достоинством алгоритма распознавания на базе особенностей является возможность находить объекты на изображениях, где они повёрнуты на произвольные углы и могут частично перекрываться. Вероятность правильного распознавания в данном алгоритме, прежде всего, зависит от количества и содержимого эталонных образов, а также от числа сравниваемых особенностей.
         При применении алгоритмов на базе особенностей существенное влияние оказывает проблема быстродействия, которая усиливается при увеличении числа эталонных образов, когда особенности неизвестного изображения необходимо сравнить со всеми особенностями всех эталонных образов. Чрезмерное увеличение количества особенностей ведёт к снижению производительности алгоритма, поэтому возникает идея выбирать количество особенностей индивидуально для каждого эталонного образа, что позволит снизить время распознавания при сохранении качества. Целью настоящей работы является оптимизация алгоритма распознавания на основе особенностей путём оптимального выбора количества особенностей.
         Задача выбора алгоритма распознавания в каждой конкретной ситуации была сформулирована Ю.И. Журавлевым [1], а подход к её решению получил название алгебраического. В работе [3] был предложен подход к управлению процессом распознавания в реальном времени, в котором для каждого неизвестного образа предлагается выбирать индивидуальные режимы алгоритмов, в зависимости от сложности распознавания этого образа. Понятно, что основным вопросом при оптимизации алгоритма является выбор меры, которая позволяла бы оценить сложность распознавания – т.е. какими затратами можно решить задачу распознавания конкретного образа.
         Суть описываемого алгоритма на основе особенностей заключается в следующем. На сравниваемых друг с другом изображениях находятся особенности (функция cvExtractSURF в OpenCV), после чего они сравниваются друг с другом с целью нахождения совпадающих пар. Чем больше особенностей, тем дольше время сравнения. Но если особенностей будет мало, то нельзя будет распознать объекты. В работе [4] показано, что наиболее точными и эффективными по производительности являются особенности на основе Гессиана. Для каждой точки изображения p = (x, y) вычисляется Гессиан H(p,σ), где σ – масштаб, следующим образом:
center
         где Lxx(p,σ) – Гауссовы частные производные второго порядка для изображения в точке p, аналогично для Lxy(p,σ) и Lyy(p,σ).
         Для ограничения количества особенностей выбирается порог, и каждая точка изображения, чей Гессиан меньше уровня порога, отбрасывается.
         Пусть имеются 10 объектов (Рис. 1), которые можно распознать с использованием особенностей (есть достаточное количество и качество особенностей). Все тестовые изображения были взяты с сайта [5]. Размеры изображений 384 на 288 пикселей в градациях серого. Необходимо, по одному эталонному изображению для каждого образа, распознать остальные образы. Для тестирования использовался типичный персональный компьютер с процессором Intel Core 2 Duo 2.2 ГГц.

         Рис. 1. Эталонные образы

         Получив 10 групп особенностей для 10 различных образов, эти особенности сравнивались с особенностями, получавшимися от 100 входных образов. Проводились сравнения результатов распознавания при задании различного порогового значения Гессиана. В таблицах 1-2 представлены построчно результаты распознавания 10 образов (по 10 на каждый объект), полученные для определенных ранее особенностей эталонных образов (столбцы). Тестовые образы сравнивались с эталонами (столбцы). Таблица 1 построена для порогового значения Гессиана равного 4000, время распознавания всех 100 образов составило 10.9 секунды при достоверности распознавания 0.66.

         Таблица 1. Результаты распознавания при пороговом Гессиане равном 4000

         При пороговом значении Гессиана равном 800 (табл. 2) время распознавания 100 образов составило 18.6, а достоверность распознавания – 0.96.

         Таблица 2. Результаты распознавания при пороговом Гессиане равном 800

         Критерием эффективности системы распознавания образов реального времени является не только достоверность распознавания образов, но и производительность [2]. Поэтому желательно, чтобы достоверность стремилась к 100%, а время распознавания к минимуму. В работе [3] показано, что, выбирая для каждого образа свой режим работы системы, можно добиться оптимальных значений этих параметров. Однако для того, чтобы можно было выбирать режим работы алгоритма необходимо примерно знать сложность распознаваемого образа [2, 3]. Если поток поступающих на систему образов как-то связан друг с другом, то можно использовать значение сложности предыдущего образа. Но в данной задаче образы никак не связаны друг с другом. Не смотря на это, в рассматриваемом алгоритме для уменьшения времени распознавания и увеличении достоверности распознавания можно модифицировать подход к управлению процессом распознавания.
         Если будет известен пороговый уровень для каждого эталонного образа, при котором образы распознаются с требуемым уровнем достоверности, то при поступлении неизвестного образа его можно сравнивать с особенностями, полученными для разных пороговых уровней Гессиана, что уменьшит общее время распознавания. В таблице 3 представлено количество ошибок для каждого образа (в строках), уровни достоверности и времени распознавания для различного порогового уровня. Тёмными областями обозначен оптимальный пороговый уровень Гессиана для каждого образа.
         Когда на вход алгоритма поступает неизвестный образ, то он сравнивается с каждым эталоном, особенности которого получены для различных пороговых уровней. Используя оптимальный пороговый уровень, отмеченный в таблице 3, подход был протестирован на тех же 100 образах. Достоверность составила 100% при времени распознавания 15.9 секунд. Это на 17% быстрее, чем при пороговом уровне 800, на 25% быстрее, чем при уровне 700, и на 45% быстрее, чем при уровне 500. При этом достоверность распознавания выше.

         Таблица 3. Количество ошибок, достоверность (D) и время (T) распознавания при различном пороговом уровне Гессиана


         Недостатком описанной выше оптимизации алгоритма является необходимость экспериментального вычисления требуемого режима для каждого эталонного образа. При увеличении количества эталонных образов на порядок возникает необходимость автоматического выбора порогового уровня Гессиана. Критерием при выборе порогового уровня предлагается использовать общее количество особенностей.
         Пусть имеются N эталонных образов ω1, ω2, …, ωN, для каждого из которых можно выбрать один из M возможных пороговых уровней Гессиана Ht1, Ht2, …, HtM, причем
Ht1 < Ht2 < … < HtM.
         Можно выбрать минимальное количество особенностей ©, при котором проводить распознавание образов. Тогда при обучении классификатора необходимо последовательно перебирать пороговые уровни Гессиана, начиная с HtM, пока количество особенностей не станет большим или равным C.
         При тестировании использовались 100 эталонных образов с сайта [5], и 1000 тестовых образов (по 10 для каждого эталонного образа). При обучении применялись следующие пороговые уровни Гессиана: 200, 500, 800, 1400, 4000. При тестах уровень Гессиана брался равным 200 (использование других значений порога, например 500, увеличивает производительность, но снижает уровень достоверности распознавания). Переменная C выбиралась равной 30.
         На рисунке 2 представлены зависимости средней достоверности распознавания образов и общего времени распознавания 100 образов при фиксированном значении порога, а также при использовании автоматического выбора порогового уровня по описанному выше методу. При использовании автоматического подхода: а) значение достоверности намного больше, чем в остальных режимах; б) производительность системы распознавания увеличивается по сравнению со всеми режимами, кроме 4000.

         Рис. 2. Зависимость достоверности распознавания образов D (а) и общего времени распознавания T (б) от порогового уровня Гессиана H

         Важным при использовании индивидуального порогового уровня Гессиана является вопрос выбора оптимального количества особенностей. Так, в предыдущем примере было выбрано примерное значение 30, однако желательно выбрать такое количество особенностей, при котором будет достигаться максимальная эффективность работы системы распознавания, т.е. максимум достоверности при минимуме времени на распознавание.
         Для определения зависимостей между достоверностью, временем распознавания и количеством особенностей при формировании эталонных образов был проведён вычислительный эксперимент. Для того, чтобы определить одинаковое количество особенностей для каждого образа подбирался свой уровень порогового Гессиана в пределах от 200 до 4000. При проведении эксперимента использовались те же образы, что и в предыдущем случае. На рисунке 3 представлены полученные зависимости достоверности распознавания образов от количества особенностей для каждого эталонного образа, общего времени распознавания тысячи тестовых образов от количества особенностей.

         Рис. 3. Зависимости достоверности распознавания образов D (а) и общего времени распознавания T (б) от количества особенностей C

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

Литература:
1. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания и классификации //Проблемы кибернетики. – 1978. – Т.33. – С. 5–68.
2. Кручинин, А.Ю. Оптимизация систем распознавания образов реального времени / А.Ю. Кручинин // Автоматизация в промышленности. – 2010. – №10. – С. 6-9.
3. Кручинин, А.Ю. Управление процессом распознавания образов в реальном времени / А.Ю. Кручинин // Автоматизация и современные технологии. – 2010. – №3. – С. 33-37.
4. H. Bay, T. Tuytelaars, and L. Van Gool. Surf: Speeded up robust features. In 9th European Conference on Computer Vision, Graz Austria, May 2006.
5. http://staff.science.uva.nl/~aloi/

Оригинал статьи:
Кручинин, А.Ю. Индивидуальный выбор оптимального количества особенностей при распознавании графических образов: Сборник статей XV международной научно-технической конференции «Информационно-вычислительные технологии и их приложения» / А.Ю. Кручинин. – Пенза: РИО ПГСХА, 2011. – С. 83-91.
http://vidikon.com/doc/text1011.doc
  • 0
  • 06 июля 2011, 11:12
  • vidikon

Комментарии (0)

RSS свернуть / развернуть

Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.