Разработка оптимального алгоритма поиска изображений по образцу
|
Скачать 62.28 Kb.
|
|
А.В. Шаронов, студент МАИ, С.В. Новоселов, доцент МАИ Московский авиационный институт (государственный технический университет) РАЗРАБОТКА ОПТИМАЛЬНОГО АЛГОРИТМА ПОИСКА ИЗОБРАЖЕНИЙ ПО ОБРАЗЦУ Проблема обработки и распознавания изображений является одной из наиболее актуальных проблем при функционировании информационных систем. В [1] разработан метод распознавания изображений и поиска изображения по образцу, использующий двумерное вейвлет-преобразование. Однако, исходя из показателей временных затрат системы на поиск изображения, можно сделать вывод о том, что при решении оперативных задач в реальном масштабе времени, эти показатели не всегда удовлетворяют требуемому быстродействию получения результата. В этой связи интерес представляет задача формирования алгоритма, который не только осуществлял поиск изображения по сжатому образцу, экономя ресурсы информационной системы, но и позволял бы сделать это в оперативной обстановке дефицита времени, удовлетворяя требованию оперативного получения результата в реальном масштабе времени. В статье предлагается метод формирования такого алгоритма, заключающийся в выборе наиболее значимых вейвлет-коэффициентов сжатого изображения. Постановка задачи Рассматривается задача оптимизации алгоритма поиска изображения по образцу, основанного на двумерном вейвлет-преобразовании [2], таким образом, чтобы удовлетворить следующим условиям: - алгоритм должен успевать найти требуемое изображение по предъявляемому пользователем образцу в условиях оперативной обстановки и дефицита выделенного времени на поиск; - качество поиска должно быть максимально приближено к уровню поиска разработанного ранее алгоритма. Формирование алгоритма В [3] показано, что в наибольших по модулю вейвлет-коэффициентах сжатого изображения, содержится основная часть информации о нем. Поэтому логично предположить, что поиск требуемого изображения можно проводить, сравнивая образец с эталонами, из которых мы ищем изображение, только по некоторой части вейвлет-коэффициентов, упорядоченных по модулю. При этом, мера сравнения вычисляется так же, как и в исходном алгоритме поиска: (1) где и - вейвлет-коэффициенты искомого изображения и предъявляемого образца соответственно, Q – число выбранных коэффициентов ля сравнения. Модифицированный алгоритм работает следующим образом:
Пример работы оптимизированного алгоритма Для подтверждения работоспособности сформированного алгоритма решается задача поиска исходного изображения по эскизу в базе данных, в которой хранится несколько эталонов (рисунок 1) [4]. 1.1а 1.1б 1.2а 1.2б 1.3а 1.3б 1.4а 1.4б Рисунок 1 - Эталоны изображений хранящиеся в базе данных (а – исходные, б – сжатые) Для поиска изображения пользователь предъявляет нарисованный от руки эскиз, который представлен на рисунке 2. Рисунок 2 - Эскиз, предъявляемый пользователем для поиска изображения Результатом обработки предъявленного эскиза меры сравнения для каждого эталона с образцом. При этом после упорядочивания вейвлет-коэффициентов по убыванию модуля, взято 30% наибольших из них. Результаты вычислений мер сравнения сведены в таблицу 1. Таблица 1. Вычисленные меры различия эталонов и эскиза
Анализ результатов, приведенных в таблице 1, показывает, что предъявляемому эскизу больше всего соответствует эталон 4. Временные затраты на реализацию сформированного алгоритма Пусть в базе данных информационной системы хранится q изображений размерностью (nхn), тогда временные затраты T(t0,l,q,n) на поиск изображений вычисляются следующим образом , (2) где – время одной элементарной операции, с; h – частота микропроцессора, Гц; l = a∙la+m∙lm (3) - число всех элементарных операций, затрачиваемых на сравнение каждого пикселя 2-х изображений, a – число сложений, m – число умножений, la и lm – число элементарных операций, затрачиваемых на сложение и умножение соответственно. Сравним теперь временные затраты на решение задачи поиска изображений по сжатым вейвлет-преобразованием образцам в зависимости от количества изображений, хранящихся в базе данных. Для упрощения вычислений предположим, что все изображения имеют размерность (n x n), где n = 128, а используемый микропроцессор имеет частоту 1 ГГц, тогда время одной операции будет 1 нс. При этом для сформированного алгоритма сравнивающего 30% наибольших вейвлет-коэффициентов, n приблизительно равно 38. Сложение в среднем состоит из 5 элементарных операций, а умножение – из 25 [5]. Исходя из (1) при сравнении двух пикселей должны выполняться две операции сложения и одна операция умножения, поэтому в соответствие с (3) Подставляя значения в (2) получим следующие зависимости для расчета временных затрат: - для алгоритма со сравнением полных изображений T1(q) = 0.573q (мс) - для алгоритма со сравнением изображений, сжатых вейвлет-преобразованием T2(q) = 0.036q (мс) . График временных затрат представлен на рисунке 3. Рисунок 3 - Изменение общего количества затраченного времени T от числа изображений q в базе для исходного алгоритма (пунктир) и сформированного алгоритма (сплошная линия) сравнения изображений Изменим теперь процент оставленных для сравнения вейвлет-коэффициентов в диапазоне от 10 до 100 процентов, тогда время работы алгоритма будет менять так, как представлено на рисунке 4. Рисунок 4 - Зависимость общего количества затраченного времени T от процента оставляемых вейвлет-коэффициентов Заключение Результаты решения модельной задачи доказывают, что разработанный алгоритм поиска изображения по образцу, основанного на двумерном вейвлет-преобразовании, позволяет значительно улучшить показатель временных затрат системы для поиска требуемого изображения при сохранении показателя качества поиска. Так например при сохранении только 30% вейвлет-коэффициентов, то временные затраты на работу оптимизированного алгоритма сокращаются приблизительно в 11 раз по сравнению с исходным алгоритмом. При этом качество поиска остается практически на том же уровне, что и в исходном алгоритме. Список литературы
|
Добавить документ в свой блог или на сайт
Похожие:
 |
Исследование возможности применения методов нелинейного программирования... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования |
 |
Факультет вычислительной математики и кибернетики Лаборатория вычислительных комплексов «Разработка и исследование эффективности алгоритма формирования содержимого учебных курсов» |
|
Разработка метода оперативной оценки оптимального времени работы... Работа выполнена в Российском Государственном Университете нефти и газа им. И. М. Губкина |
|
Анализ стойкости метода коха-жао стеганографического встраивания... Аннотация: Рассмотрен метод стеганографического встраивания информации Коха-Жао. В статье проведен анализ стойкости данного метода... |
|
Инструкция пользователя. 23 Разработка методов информационного поиска на основе методов интеллектуального анализа данных. 8 |
|
Современные подходы к синтезу оптимального измерителя опасных факторов... Целью работы является синтез и анализ оптимального измерителя опасных факторов пожара с произвольной динамикой, наблюдаемых на фоне... |
|
Методическая разработка тема : «Роль интегрированного занятия в повышении... Это, в свою очередь, потребовало поиска нового подхода к организации образовательно-воспитательного процесса в образовательных учреждениях... |
|
1 Состояние проблемы поиска и анализа текстов на естественном языке 5 Концепция объектно-ориентированного представления семантических знаний и методики анализа, поиска и пополнения базы знаний физических... |
|
Тезисы Вступление Прижизненных изображений Пушкина в скульптуре не было. Эти два портрета имеют большую ценность. Почему? |
|
Кодекс оптимального поведения Введение в психономику, или от приватной психотерапии к магической драматургии бытия |