Содержание к диссертации
Введение
1 Современные проблемы поиска изображений в базе данных 10
1.1 Актуальность проблемы поиска изображений 10
1.2 Обзор современных методов поиска изображений 14
1.3 Формализация постановки задачи поиска изображений 32
Выводы к разделу 1 41
2 Построение обобщенной модели и разработка методик поиска изображений в базе данных с помощью фрактального кодирования и комбинирования вейвлетного и фрактального методов 42
2.1 Формализованная модель поиска изображений 42
2.2 Разработка методики на основе фрактального кодирования для реализации модели поиска изображений 47
2.3 Разработка методики на основе комбинирования вейвлетного и фрактального методов для реализации модели поиска изображений 57
Выводы к разделу 2 66
3 Разработка алгоритмов поиска растровых изображений на основе полученной формализованной модели 67
3.1 Разработка алгоритма для поиска изображений с помощью методики, предложенной для реализации модели на основе фрактального кодирования 67
3.2 Разработка алгоритма для поиска изображений с помощью методики, предложенной для реализации модели на основе комбини-рования вейвлетного и фрактального методов 73
Выводы к разделу 3 80
4 Реализация алгоритмов и анализ формализованной модели с помощью компьютерного эксперимента
4.1 Концептуальная модель системы поиска растровых изображений. 81
4.2 Разработка интерфейса системы поиска растровых изображений 87
4.3 Выбор программного обеспечения 90
4.4 Программная реализация системы поиска растровых изображений 92
4.5 Выбор параметров фрактального кодирования и функции вейвлета для реализации предложенных алгоритмов 100
4.6 Анализ результатов поиска растровых изображений 106
Выводы к разделу 4 116
Заключение 117
Литература 120
- Формализация постановки задачи поиска изображений
- Разработка методики на основе фрактального кодирования для реализации модели поиска изображений
- Разработка алгоритма для поиска изображений с помощью методики, предложенной для реализации модели на основе комбини-рования вейвлетного и фрактального методов
- Выбор параметров фрактального кодирования и функции вейвлета для реализации предложенных алгоритмов
Введение к работе
Актуальность темы. В настоящее время большой интерес представляет оцифровка и хранение больших объемов визуальных материалов, обеспечение эффективного содержательного доступа к этой информации в электронных коллекциях изображений. Широкое и повсеместное применение Интернет в повседневной жизни человека привело к усложнению запросов пользователей. Существующие поисковые системы, осуществляющие поиск информации не могут удовлетворить эти потребности. В настоящее время, когда в сети расположены не только текстовые, но и всевозможные мультимедийные ресурсы, необходимы новые эффективные средства поиска и навигации по ним. Для привлечения посетителей, музеи все активнее используют современные компьютерные технологии, помещают свои коллекции в Интернете, предоставляют различные услуги по их просмотру. Одной из самых востребованных является возможность быстрого поиска конкретных изображений.
До последнего времени традиционным являлся поиск визуальной информации, опирающийся на индексирование текстовых описаний, ассоциированных с изображением. Неоднозначность соответствия между визуальным содержанием и текстовым описанием снижает показатели точности и полноты поиска. В связи с этим возникает проблема организации доступа к современным электронным коллекциям изображений с использованием комплекса средств, таких, как текстовые описания, характеристики визуального содержания, типа цветовой гаммы, более сложных систем, связанных с распознаванием образов. Текстовое описание и визуальная поисковая информация, как правило, дополняют друг друга, обеспечивая возможность разностороннего поиска. Поиск может выполняться итеративно: сначала на основе ключевых слов, как более быстрый способ, затем среди отобранного множества материалов более трудоемкий поиск с использованием визуальных характеристик.
Разработка системы поиска изображений по изображению-запросу является актуальной и трудоемкой, поскольку, во-первых, отсутствует метод однозначного описания свойств графических объектов; во-вторых, разнообразен математический аппарат для построения и использования этого описания.
Проведенные исследования показали, что задачи поиска изображений отличаются большим разнообразием и выбором средств их решения: преобразование Фурье, метод гистограмм, искусственные нейронные сети, стохастическая геометрия, что является следствием разнообразия областей практического применения: искусство, криминалистика, картография, защита авторских прав.
Среди работ, посвященных данной проблеме можно отметить труды зару
бежных и отечественных исследователей: J. P. Eakins, A. Vailaya, М. Figueiredo,
Т. Kato, Т. Kurita, G. Yang, Т. S. Huang, Е. J. Stolnitz, Т. Derose, Т. Salesin,
Н. Г. Федотова, М. А. Щербакова, И. М. Гостева, А. В. Мирошкина, С. К. Аб
рамова, В. В. Лукина, А. Л. Жизнякова, Н. В. Бакунова, В. П. Дьяконова, дис
сертационные работы А. В. Роя, Н. Е. Козина, И. В. Корябкиной, А. В. Нефёдо
ва, И. П. Тищенко и многих других. . . ,
Представляемые исследования направлены на разработку и исследование модели и алгоритмов поиска изображений на основе визуальных атрибутов, связанных с использованием методов фрактального кодирования и комбинирования вейвлетного и фрактального подходов.
Целью диссертационной работы является разработка и исследование модели и алгоритмов для поиска растровых изображений, представленных в электронных коллекциях, по изображению-образцу.
В диссертационной работе поставлены и решены следующие задачи.
-
Анализ современных методов и проблем поиска изображений в базе данных.
-
Разработка формализованной модели на основе фрактального кодирования и комбинирования вейвлетного и фрактального методов.
-
Разработка методик поиска растровых изображений на основе выбранных методов.
-
Разработка алгоритмов поиска растровых изображений на основе полученных методик.
-
Разработка системы поиска изображений на основе полученных алгоритмов и анализ результатов поиска.
Объект исследования - множество методов поиска растровых изображений.
Предметом исследования являются модель и алгоритмы поиска растровых изображений по изображению-образцу.
Методы исследования. При решении поставленных задач использовались методы фрактального кодирования, вейвлет-преобразований, аппарат математической статистики, теории баз данных, принципы модульного и объектно-ориентированного программирования.
Научная новизна работы. Научная новизна результатов диссертационного исследования представлена совокупностью следующих положений.
-
Разработана формализованная модель поиска изображений, которая отличается от существующих тем, что учитывает взаимоотношения между фрагментами изображения, а также описание изображения в терминах грубого усредненного приближения, что позволяет получить более точный поиск в случаях модификаций изображений, связанных с инвертированием цветов, монохромным представлением и различными способами размытия изображения.
-
Разработаны методики поиска изображений впервые использующие методы фрактального кодирования и комбинирование вейвлетного и фрактального подходов применительно к решению задачи поиска изображений в базе данных по искомому изображению.
-
Предложен критерий эффективности поиска изображений на основе разработанных алгоритмов и системы, который позволяет провести детальную оценку результатов поиска, полученных с помощью компьютерного эксперимента, проведенного на основе предложенных изображений и их модификаций.
Практическая значимость результатов заключается в решении задачи поиска по электронным коллекциям изображений на основе визуальной информации и создании программных средств, обладающих высокой точностью и
скоростью поиска. Разработанные алгоритмы могут использоваться для поиска изображений в Интернете, частных коллекциях, для защиты торговых марок и авторских прав, а также для хранения информации об изображениях в хранилищах данных с контентной адресацией (CAS).
В настоящее время, система поиска изображений, построенная на основе предложенных алгоритмов, внедрена в Мордовском республиканском музее изобразительных искусств им. С.Д. Эрьзи.
Основные положения, выносимые на защиту:
-
Формализованная модель поиска изображений, позволяющая использовать методы фрактального кодирования и комбинирование вейвлетного и фрактального подходов.
-
Методики поиска изображений в базе данных по искомому изображению на основе предложенной формализованной модели.
-
Алгоритмы поиска изображения на основе методик, использующих фрактальное кодирование, а также сочетание вейвлет-преобразования и фрактального подхода.
-
Система поиска изображений с учетом диаграммы последовательности работы системы, концептуальной модели и богатых возможностей фрактальных и вейвлетных методов.
-
Методика оценки эффективности поиска изображений, позволяющая провести детальный анализ результатов поиска, и критерий эффективности для получения обоснованной оценки результатов поиска.
Реализация и внедрение результатов работы. Созданная система поиска растровых изображений на основе фрактального кодирования и совмещения вейвлетного и фрактального подходов опробована и эксплуатируется в Мордовском республиканском музее изобразительных искусств им. С.Д. Эрьзи, что подтверждено актом внедрения.
Результаты работы использованы в НИОКР «Разработка системы поиска растровых изображений из базы данных по изображению-запросу» (программа «Участник молодежного научно-инновационного конкурса 2007» Фонда содействия развитию малых предприятий в научно-технической сфере, государственные контракты 5474/7987 от 03.12.07 и 6653/9110 от 21.01.09)
Апробация работы. Основные результаты докладывались и обсуждались на следующих конференциях:
-
IV, V Международные конференции «Методы и средства управления технологическими процессами», Саранск, 2007,2009 гг.
-
XXXIV, XXXVII Огаревские чтения, Саранск, 2006,2009 гг.
-
XI научная конференция молодых ученых, аспирантов и студентов Мордовского государственного университета имени Н. П. Огарева, Саранск, 2006 г.
-
Международная научная конференция «Проблемы управления, передачи и обработки информации» (АТМ-ТКИ-50), Саратов, 2009г.
-
6-ая Всероссийская научно-практическая конференция «Современные проблемы создания и эксплуатации радиотехнических систем» (с участием стран СНГ), Ульяновск, 2009г.
По результатам 4-ой Международной конференции "Методы и средства управления технологическими процессами» работа «Разработка системы поиска растровых изображений из базы данных по изображению-запросу» признана
победителем программы «Участник молодежного научно-инновационного кон
курса 2007» («УМНИК»). '
Публикации. По теме диссертации опубликовано 16 работ, в том числе 13 статей, среди них 1 в журнале, рекомендованном ВАК РФ; 3 свидетельства о государственной регистрации программы для ЭВМ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 112 наименований и 12 приложений. Работа содержит 131 страницу основного текста, 62 страницы приложений, 27 рисунков, 3 таблицы.
Формализация постановки задачи поиска изображений
При постановке задачи поиска изображений обычно стараются пользоваться формальным языком математики. Основанием для этого является, в первую очередь, стремление получать результаты не путем экспериментирования, а с помощью логических рассуждений и математических доказательств. Другая причина состоит в том, что всякий алгоритм естественнее всего строится на основе исходных данных и предположений в том случае, если им придана математическая форма [53].
При поиске изображений, необходимо представить его как некоторую функцию на плоскости.
Рассмотрим евклидову плоскость Е. Введем следующие обозначения: t = (tlf t2) — точка плоскости Е\Т - ограниченное точечное множество в плоскости Е\ x(t), t Є Т— функция, имеющая областью определения все точки из Т; X - множество всех функций x(t) на Т.
Число х выражает в каждой точке изображения какую-либо из его физических характеристик — яркость, прозрачность, степень зачерненности, оптическую плотность. В этом случае функция x(t) является формальной записью изображения. Точечное множество Т в плоскости называют иногда «полем рецепторов» или «сетчаткой» [53].
Согласно подходу Файн В. С, множество X является математическим описанием множества всех изображений, возможных для данной сетчатки. Сопоставим каждой точке tET некоторую координатную ось, по которой будет откладываться значение х в этой точке. В построенных таким способом координатах каждому изображению x(t) будет соответствовать точка, а все множество функций X отобразится в точечное множество, за которым сохраним то же обозначение X [53].
Одним из центральных понятий в поисковой практике является «сходство» между изображениями. В конструируемой формальной модели этому интуитивному понятию должно соответствовать понятие эквивалентности точек некоторых подмножеств в X. Это позволяет придать понятию «класс» точный теоретико-множественный смысл, определив его как класс эквивалентности по некоторому отношению эквивалентности R. При этом понятие «отношение эквивалентности» образует формальное наименование для главного предмета поисков во всех распознавательных задачах - правила, по которому нужно относить предъявленные изображения в разные классы. В зависимости от природы распознаваемых объектов поиски этого правила могут идти в двух направлениях в соответствии с двумя типами встречающихся распознавательных задач [54].
В задачах 1-го типа классификация производится непосредственно на множестве восприятий, возникающих при взаимодействии рецепторных устройств автомата с объектами окружающего мира. Примером могут служить чувственные восприятия живых существ. В задачах 2-го типа классификация производится на множестве абстрактных понятий с получением еще больших обобщений. Примером может служить задача классификации понятий «самолет, дом, велосипед, поезд, дерево, стул...» на средства транспорта и не средства транспорта [53].
Очевидно, что та или иная ситуация в распознавании изображений либо полностью относится к задачам 1-го типа, либо включает в себя такую задачу как часть. Нетрудно видеть, что и во всякой задаче 2-го типа в качестве необходимого составного элемента содержится задача 1-го типа. В приведенном примере задачи 2-го типа содержится задача 1-го типа, состоящая в распознавании букв в словах, выражающих перечисленные понятия [54]. Ясно, что в задачах этих разновидностей различны мощности множеств распознаваемых объектов. В задаче 1-го типа происходит сопоставление бесконечного множества явлений, взаимодействий, конфигураций природы с конечным объемом памяти любого (в том числе и живого) реального распознающего автомата. Если известно, что существует автомат, способный решать некоторую задачу 1-го типа, то это может означать только, что в бесконечном множестве объектов, фигурирующих в этой задаче, имеются некоторые внутренние закономерности, некоторые объективные внутренние связи, позволяющие при знании конечного числа «представителей» множества правильно классифицировать произвольные предъявляемые объекты. Для того чтобы распознающий автомат успешно решал задачи 1-го типа, используемые в нем алгоритмы должны как-то отображать эти объективные закономерности. Люди, ощущая действие этих закономерностей, создали ряд интуитивных, обычно не уточняемых понятий типа «сходство», «образ» и т. д.
В задачах же 2-го типа классификации подлежит множество понятий, само порожденное автоматами с конечной памятью и потому конечное; здесь классификация в принципе возможна и без наличия связей указанного рода -путем простого перечисления всех относимых в данный класс понятий. В связи с этим такое сопоставление может оказаться вполне произвольным, субъективным.
Применительно к задачам распознавания изображений следует рассматривать такие правила сопоставления, которые обеспечивали бы возможность описания бесконечных (несчетных) множеств в конечных терминах.
Один из наиболее распространенных подходов к построению таких правил базируется на интуитивном ассоциировании понятий «сходство» и «близость» и выражается в предположении о правомерности сопоставления степени сходства изображений со степенью близости соответствующих точек множества X. Доводя такую ассоциацию до логического завершения, приходим к предположению о том, что «очень близким» точкам должны соответствовать «почти неотличимые изображения», то есть столь сходные изображения, что они всегда принадлежат к одному классу (гипотеза «компактности».)
Это приводит к наделению множества X структурой близости с получением пространства (которое мы обозначим х\ в общем случае топологического. Пространство х называют обычно «пространством рецепторов», «пространством наблюдений», «пространством входов».
В работах по поиску изображений часто рассматриваются отображения пространства # на другие, более удобные для дальнейших операций пространства (например, пространство признаков) [56, 86, 89, 111]. В этих случаях используются непрерывные отображения, при которых топология нового пространства не противоречит топологии пространства #. Для задания топологии в пространстве х или в пространстве, являющемся его отображением, используются различные конкретные способы. Наиболее распространенным представляется ввод топологии посредством определения расстояния как метрического, таки не метрического, причем расстояние может определяться неявно через «функции принадлежности». Другой распространенный способ задания топологии - «разделяющие поверхности», «разделяющие функции» — способ задания класса эквивалентности путем указания границ этого множества. Для классов в пространстве # будет использоваться обозначение ХІ(ХІ Є X), где индекс і указывает номер класса в данной классификации.
Разработка методики на основе фрактального кодирования для реализации модели поиска изображений
На сегодняшний день создано достаточно много методик обработки цифровых изображений, основанных на различных теоретических подходах. Тем не менее, по-прежнему актуальна разработка более эффективных и точных методик, использующих максимальное количество полезной информации, получаемой из исходного изображения, для достижения требуемого результата. Необходима разработка новых и усовершенствование известных методик обработки изображений [6]. Кроме того, с каждым годом появляются новые классы прикладных задач, в значительной мере расширяющих границы области их применения [58]. В работе рассматривается методика, использующаяся для реализации модели поиска изображения на основе фрактального кодирования.
Термин «фрактал» был введен Б.Мандельбротом в 1975 г. Согласно Ман-дельброту, «фракталом (от лат. «fractus» - дробный, ломанный, разбитый) называется структура, состоящая из частей, подобных целому» [21]. Термин самоподобие означает наличие тонкой, повторяющийся структуры, как на самых малых масштабах объекта, так и в макромасштабе.
Основной объект фрактальной геометрии - фракталы находят применение в компьютерном дизайне, в алгоритмах сжатия информации. Фрактальные объекты - порождение компьютерного мира, и их сфера применения еще до конца не раскрыта.
В настоящее время нет однозначного определения «фрактала». Следуя Лаверье [90]: «фрактал — это геометрическая фигура, в которой один и тот же фрагмент повторяется при каждом уменьшении масштаба». Фракталы, обладающие этим свойством и получающиеся в результате простой рекурсивной процедуры (комбинации линейных преобразований), называются конструктивными фракталами. Таким образом, конструктивный фрактал - это множество, получающееся в результате линейных (аффинных) сжимающих отображений
подобия. Наряду с конструктивными фракталами были обнаружены множества, которые похожи на фракталы. Как правило, подобные множества возникают в нелинейных динамических системах и, в первую очередь, в дискретных динамических системах. Их построение не так просто, как в случае конструктивных фракталов, и они могут обладать масштабной инвариантностью лишь приближенно. Подобные множества называются динамическими фракталами. В связи с этим Мандельброт ввел другое определение фрактала [21]: «Фрактал - это такое множество, которое имеет хаусдорфову (или фрактальную) размерность, большую топологической». В первом определении слово «фрактал» - от латинского «fractus», означающее изломанный. Во втором определении оно связано с английским «fractional» дробный.
В последние годы появилось большое число книг, посвященных фракталам [21, 23, 90]. В этих книгах приводятся фракталы, полученные с помощью компьютера. В связи с этим, говоря о фракталах, довольно часто используют термины: «компьютерное искусство», «художественный дизайн», «эстетический хаос». Примером конструктивного фрактала может служить дерево, ствол которого разделен на две более мелкие ветви. В свою очередь, каждая из этих ветвей разделяется на две более мелкие ветви и т. д. Можно проделать эту процедуру бесчисленное число раз и получить древовидный фрактал с бесконечным числом ветвей. Каждую отдельную ветвь можно, в свою очередь, рассматривать как отдельное дерево. Эта конструкция имеет сходство с двоичной системой счисления. Другой пример фрактала - это множество Кантора. Это не только один из самых старых фракталов, он является так же существенной частью многих современных фракталов, например, таких, как кривые Коха и Минковского. Структуры, похожие на фракталы, можно обнаружить в окружающей нас природе: границы облаков, границы морских побережий, турбулентные потоки в жидкостях, трещины в некоторых породах, зимние узоры на стекле, изображения структуры некоторых веществ, полученные с помощью электронного микроскопа, кровеносная система сердечной мышцы и т.д. Чтобы пояснить определения конструктивных и динамических фракталов, рассмотрим основные свойства фрактальных множеств PrF, следуя [73]: 1. PrF имеет тонкую структуру, то есть содержит произвольно малые масштабы; 2. PrF слишком нерегулярное, чтобы быть описанным на традиционном геометрическом языке: 3. PrF имеет некоторую форму самоподобия, допуская приближенную или статистическую; 4. Обычно «фрактальная размерность» множества PrF больше, чем его топологическая размерность; 5. В большинстве случаев Ргр определяется очень просто, например, рекурсивно. Таким образом, фракталы можно определить как множества точек, инвариантных относительно полугруппы сжатий. Чтобы применить эти сведения для создания фракталов, необходимо выбрать преобразования, которые будут называться сжимающими отображениями. Система итерируемых функций (Iterated Function System, IFS) состоит из полного метрического пространства (X, d) и конечного множества отображений wIm: X — X с коэффициентами отображения sn. В общей математической модели поисковой системы wIm выступает в роли фушщий преобразования изображений f{. Преобразования, которые использовал Барнсли [62] для систем итерируемых функций — это так называемые аффинные преобразования. Аффинные преобразования могут осуществлять поворот, перемещение и масштабирование.
Процесс обработки изображений на основе фрактального кодирования представим следующим образом. Изображения могут быть воспроизведены с помощью относительно простой системы итерируемых функций, так как они обладают свойством глобального самоподобия. Это значит, что целое изображение состоит из уменьшенных копий его самого или его частей. Увеличивая такое изображение, наблюдают одну и ту же степень детализации независимо от разрешения. Реальные изображения не обладают свойством глобального самоподобия, которое присутствует в изображениях, представленных системой итерируемых функций. Более того, реальные изображения не являются двоичными; каждый пиксел принадлежит диапазону значений (в градациях серого) или вектору значений (в цвете). Если необходимо представить изображение как аттрактор итерационной системы, то, очевидно, что нужна более общая система, чем системы итерируемых функций. Рассмотрим построение и реализацию поисковой системы, которая использует фрактальное кодирование произвольных изображений (для цветного изображения описанные действия необходимо будет повторить для каждого цветового канала в отдельности).
При фрактальном кодировании изображений находится множество сжимающих преобразований, которые отображают доменные блоки (они могут перекрываться) во множество ранговых блоков, которые покрывают изображение. Ранговые блоки могут быть одинакового размера, но чаще используется адаптивное преобразование с переменным размером блоков. Ранговые блоки являются результатом разбиения методом квадродерева[34].
Разработка алгоритма для поиска изображений с помощью методики, предложенной для реализации модели на основе комбини-рования вейвлетного и фрактального методов
Рассмотрим другой вариант, основанный на методике, использующей комбинирование вейвлетного и фрактального методов. Для реализации такого подхода поиска изображения по изображению-образцу первым шагом нужно выполнить вейвлет-преобразование изображения, при этом необходимо учитывать следующую информацию. Нестандартное разложение представляет чередование операций над строками и столбцами, то есть сначала выполняется один этап горизонтального попарного усреднения и нахождения разности значений пикселей в каждой строке изображения, затем — те же операции выполняются над каждым получившимся столбцом. Этот процесс рекурсивно повторяется только на квадрантах, содержащих средние значения в обоих направлениях [48].
Для решения задачи поиска изображения по изображению-образцу можно использовать различные функции вейвлет-разложений. Теоретически, учитывая известные положения [16]: — возможность эффективной реализации алгоритма разложения изображения; — достаточная точность представления изображения для задачи поиска; — возможность использования небольшого количества коэффициентов для анализа; — возможность применения нестандартного разложения, можно предположить, что целесообразнее всего использовать вейвлет Хаара.
Поэтому, на основании изложенных положений, рассмотрим кодирование изображений на основе вейвлета Хаара [35]. Для получения вейвлет-коэффициентов используется кратномасштабное разложение изображения с применением базисной функции Хаара. С помощью масштабирующей функции строится последовательность приближений для изображения, при котором каждое приближение будет отличаться от соседнего масштабным фактором, равного двум. Использование масштабирующей функции позволяет получить представление вейвлет-коэффициентов.
Таким образом, в качестве вейвлета примем полную ортонормальную систему базисных функций с локальной областью определения, предложешгую еще в 1910 году А.Хааром (теперь они называются вейвлетами Хаара) [16]. Значимость этого преобразования обусловлена тем, что его базисные функции образуют первую и простейшую из известных систему ортонормированных вейв-летов:
Ее базисные фикции определяют блок конечной импульсной характеристики фильтров, имеющих лишь пару отличных от нуля коэффициентов (коэффициенты соответствующих фильтров анализа hQ(n) и ht(n) — элементы первой и второй строки матрицы FWz, соответственно). При этом низкочастотный фильтр анализа удовлетворяет условию на сопряженный квадратурный фильтр. Использование масштабирующей функции позволяет построить последовательность приближений для некоторой функции или изображения, причем каждое приближение отличается от соседнего масштабным фактором 2.
Использование других функций вейвлета, в частности Добеши, койфлетов имеют в своей основе более сложные математические выкладки. Поэтому реализация их в алгоритме не рассматривается, а для сравнения их с вейвлетом Хаара в дальнейшем используется пакет Matlab, в котором они вычисляются.
Структура изображения будет определяться как набор коэффициентов, являющихся результатом кратномасштабного разложения. Вейвлеты как математическое средство для иерархического представления функций позволяют описать изображение в терминах усредненного приближения и деталей различного масштаба, поэтому понимание изображений как источника информации будет далеко не полным.
Для разработки алгоритма поиска изображений на основе комбинирования вейвлет-преобразования и фрактального кодирования используем методику, описанную в 2.3. Алгоритм поиска изображений в этом случае будет выглядеть следующим образом [37]:
Как и в случае алгоритма поиска изображений на основе фрактального кодирования, при добавлении нового изображения в базу данных и вводе запрашиваемого изображения они масштабируются до размера 256 х 256 пикселей.
Выбор параметров фрактального кодирования и функции вейвлета для реализации предложенных алгоритмов
Для сжатия доменного блока используется функция ResizeArray (приложение А, листинг А.З). Входным параметром является доменный блок, выходом — преобразованный доменный блок. В системе реализован алгоритм изменения размера с использованием билинейной фильтрации. Для разворота доменного блока используется функция Rotate90 (приложение А, листинг А.4), входным параметром которой является доменный блок, а точнее массив пикселей данного домена. На выходе тот же домен, повернутый на 90 градусов.
Методом наименьших квадратов вычисляются оптимальные параметры яркости и контрастности. Это реализуется при помощи функции SearchContrast (приложение А, листинг А.5), входными параметрами которой являются ранговый и преобразованный доменный блок, для которого вычисляются соответствующая яркость и контрастность. Функция возвращает структуру Contrast, в которой хранится значение яркости и контрастности. Для применения этих значений к доменному блоку используется функция ApplyContrast (приложение А, листинг А.6), которая имеет входные параметры, такие как доменный блок, который надо преобразовать, и значение яркости и контрастности, предаставлен-ные с помощью структуры Contrast. Возвращаемым значением является преобразованный доменный блок.
Сравнение рангового и полученного доменного блоков осуществляется при помощи функции SearchEps (приложение А, листинг А.7), которая возвращает значение погрешности, при передаче ей рангового и полученного доменного блоков. По этому значению можно судить, насколько ранговый блок совпадает с полученным доменным блоком.
Функция FraktalCoding возвращает структуру типа SGod, в которой хранятся все фрактальные коэффициенты. По полученным коэффициентам будут сравниваться два изображения. Функцию FraktalCoding приходится вызывать трижды, для каждого из каналов палитры RGB.
Для получения численных значений коэффициентов, которые используются при поиске растровых изображений в случае комбинированного подхода используем сначала вейвлет-преобразование, а затем описанный выше базовый алгоритм фрактального кодирования изображений. Попытки найти решение любой задачи только с помощью вейвлетов, не всегда себя оправдывают. Хотя практика показывает, что именно их применение позволяет во многих случаях получить более приемлемые (по какому-либо критерию) результаты. Тем не менее, именно комплексный подход к решению проблемы поиска изображений, включающей в себя несколько математических методов, как правило, дает лучшие результаты.
Эти свойства позволяют, используя вейвлет-преобразование в сочетании с фрактальными методами, анализировать изображения на разных масштабах и в разных точках, обобщить их на множество любых размерностей и применить при поиске изображений.
Для реализации комбинированного подхода в реализации поиска изображения по изображению-образцу первым шагом нужно выполнить вейвлет-преобразование изображения NonStandartDecomposition (приложение А, листинг А.8) [45].
При этом необходимо учитывать следующую информацию: нестандартное разложение представляет чередование операций над строками и столбцами. После этого, сначала выполняется один этап горизонтального попарного усреднения и нахождения разности значений пикселей в каждой строке изображения, затем — к каждому получившемуся столбцу. Этот процесс рекурсивно повторяется только на квадрантах, содержащих средние значения в обоих направлениях. С помощью масштабирующей функции строится последовательность приближений для изображения, при котором каждое приближение отличается от соседнего масштабным фактором, равного двум. Использование масштабирующей функции позволяет получить представление вейвлет-коэффициентов. Структура изображения определяется как набор коэффициентов, являющихся результатом кратномасштабного разложения.
Вейвлеты позволяют описать изображение в терминах усредненного при ближения и деталей различного масштаба, поэтому понимание изображений как источника информации будет недостаточным. В отличие от методов вейв-лет-преобразований, фрактальные методы пытаются перестроить изображение, используя взаимоотношения между фрагментами изображения, поэтому вторым шагом при реализации комбинированного алгоритма является фрактальное кодирование вейвлет-представления изображения, при котором находится множество сжимающих преобразований, отображающих доменные блоки во множество ранговых блоков, покрывающих вейвлет-представление изображения. Фрактальное кодирование выполняется с помощью функции fractalCoding_mix (приложение А, листинг А.9) по аналогии с выше описанным кодированием изображения с помощью фракталов, с учетом того, что в качестве входных параметров выступают не пиксели изображений, а вейвлет-коэффициенты [43].
На третьем этапе разработки системы поиска необходимо реализовать поиск изображений по разработанному алгоритму (рисунок 3.2). При сравнении происходит кодирование изображения-образца по тем же правилам, что и при создании базы данных (рисунок 3.1). После этого коэффициенты изображений, принадлежащие искомому изображению сравниваются со значениями коэффициентов изображений, расположенных в базе данных. Сравнение происходит в функции CompareArray (приложение А, листинг АЛО). Входными параметрами являются две структуры типа SCod. Возвращает функция процент соответствия этих двух структур, по которому можно судить, насколько похожи эти два изображения.
