автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Методы и инструментальные средства решения задач сжатия, распознавания и поиска изображений по содержанию на основе дискретных отображений

На правах рукописи

ГОРА Сергей Юрьевич

МЕТОДЫ И ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА РЕШЕНИЯ ЗАДАЧ

СЖАТИЯ, РАСПОЗНАВАНИЯ И ПОИСКА ИЗОБРАЖЕНИЙ ПО СОДЕРЖАНИЮ НА ОСНОВЕ ДИСКРЕТНЫХ ОТОБРАЖЕНИЙ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (технические системы)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

1 8 ДЕК 2014

Рязань 2014 005556963

005556963

Работа выполнена в ФГБОУ ВПО «Курский государственный университет»

Научный руководитель:

Официальны оппоненты:

Лопин Вячеслав Николаевич, доктор технических наук, профессор, ФГБОУ ВПО «Курский государственный университет», г.Курск

Кузнецов Павел Константинович, доктор технических наук, профессор, директор НИИ проблем надежности механических систем ФГБОУ ВПО «СамГТУ», г.Самара

Москвитин Алексей Эдуардович, кандидат технических наук, доцент, ведущий научный сотрудник НИИ «Фотон» ФГБОУ ВПО «РГРТУ», г.Рязань.

Ведущая организация:

ФГБОУ ВПО «Белгородский государственный технологический университет им. В.Г. Шухова», г.Белогород

Защита состоится «18» февраля 2015 года в 12 час.00 мин.на заседании диссертационного совета Д 212.211.01 в ФГБОУ ВПО «Рязанский государственный радиотехнический университет» по адресу:

390005, г. Рязань, ул. Гагарина, д. 59/1.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Рязанский государственный радиотехнический университет».

Автореферат разослан 2014 года.

Ученый секретарь диссертационного совета

кандидат технических наук, доцент

Пржегорлинский В.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Стремительное развитие вычислительной техники, развитие сети Интернет и появление относительно недорогих устройств создания графических данных, применяемых в технических системах: картография, системы дистанционного зондирования, медицинская графика, дизайн, компьютерное зрение и т.д., - привели к появлению баз данных, содержащих большой объем информации, представленной в графических форматах. Следствием этого обстоятельства явилось увеличение нагрузки на каналы связи. В связи с чем актуализировалась задача разработки методов и средств обработки графической информации таких, как распознавание, автоматизированный поиск и сжатие графических данных.

Распознавание образов (pattern recognition) в основном применяется для решения широкого спектра прикладных задач в технических системах автоматизации рутинных операций умственного труда: идентификация личности по отпечаткам пальцев, изображению радужной оболочки глаза, ушной раковины и т.д.; машинное распознавание рукописных символов; в системах автоматизированного анализа качества выпускаемой продукции; анализ ДНК; идентификация летательных аппаратов по их изображению и т.д.

Поиск изображений по содержимому (CBIR - Content-based image retrieval) применяется, прежде всего, для нахождения изображений в больших каталогах графических файлов таких, как: опНпе-каталоги магазинов; личные коллекции фотографий; картография; полиграфия; медицинские изображения, например, каталоги рентгеновских снимков, УЗИ и т.д.

Помимо распознавания и поиска, все данные, представленные в цифровом формате, необходимо хранить и передавать по каналам связи. По статистике, представленной компанией Google, при просмотре сайтов примерно 60-70 % трафика составляют изображения, поэтому сжатие данных (data compression) является так же важной практической и коммерческой задачей.

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

Степень разработанности темы

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

1. К наиболее значимым работам в области распознавания образов следует отнести труды следующих ученых: Ю.И. Журавлева, Б.А. Алпатова, А.И. Галушкина, Я.А.Фурмана, A.JI. Горелика, B.C. Михалевича, B.C. Пугачева, G.Nagy, L.N. Kanal, К. Fukunaga, R.O. Duda, P.E. Hart, К. Фу, J. Kittler, L. Gyorfi, G.Lugosi, C.M. Bishop, В. Ripley и др.

2. Важный вклад в основы сжатия цифровых изображений внесли: Д.С. Ватолин, И.И. Исмагилов, H.H. Пономаренко, C.B. Умняшкин, D.A.Huffman, N. Ahmed, K.R. Rao, I. Daubechies, R.C. Gonzalez, M.W. Marcellin и др.

3. Изучением проблемы поиска изображений по содержанию занимались следующие ученые: А. Белков, А. Дольник, И. Марков, Т, Kato, F. Long, H. Zhang,V. Broek, D. Feng, R. С. Veitkamp, Y. Rai, , S.-F. Chang, Т. Коки др.

4. Исследованиям в области динамического хаоса посвятили свои труды А.Н. Колмогоров, В. И. Арнольд, JI.O. Чжуа, Ю. К. Мозер, H.H. Залогин, Р.В. Беляев, A.C. Дмитриев, А.И. Панас, Э.Н. Лоренц, Ж.А. Пуанкаре и др.

В настоящее время ведутся исследования, направленные на разработку алгоритмов распознавания образов, продолжается поиск методов и алгоритмов решения задач сжатия графических данных. Поиск изображений по содержанию — относительно новая область применения компьютерного зрения, получившая свое развитие в начале 90-х годов прошлого века. До появления методов автоматизированного извлечения изображений из баз данных по содержанию поисковые алгоритмы использовали текстовые аннотации.

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

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

Работа выполнялась в рамках основных научных направлений Курского государственного университета, НИР и в рамках государственного задания по теме: «Методы и гибкая алгоритмическая система решения задач защиты, сжатия и классификации информации с использованием механизмов теории хаотических систем».

Цель диссертации заключается в разработке единого подхода, основанного на применении известных дискретных отображений для формирования хаотически рассеянных исходных изображений путем

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

Для достижения поставленной цели необходимо решить следующие основные задачи:

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

- создание единого подхода на основе дискретных отображений к решению задач распознавания, сжатия и поиска изображений по содержанию, включающего в себя:

• системный анализ особенностей изображений, разработку и исследование метода и алгоритмической модели процесса сжатия изображений;

• разработку и исследование метода и алгоритмической модели процесса распознавания изображений;

• разработку и исследование метода и алгоритмической модели процесса поиска изображений по содержанию (search images by content);

- экспериментальные исследования эффективности разработанных схем алгоритмов.

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

Эффективность разработанных методов и алгоритмов подтверждена экспериментально.

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

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

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

Методы исследования. Методы системного анализа, теории хаотических систем вычислительного эксперимента, математического моделирования и средств обработки изображений, распознавания образов и теории алгоритмов. Экспериментальные исследования проводились на общедоступных базах изображений и с использованием свободно распространяемого программного обеспечения.

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

Реализация и внедрение. Основные теоретические результаты использовались в Курском государственном университете в рамках НИР «Методы и гибкая алгоритмическая система решения задач защиты, сжатия и классификации информации с использованием механизмов теории хаотических систем» (Регистрационный номер НИР 8.8045.2013, номер государственной регистрации НИР: 01201354534). Результаты работы внедрены в ЗАО «Автодор», ОГУП «Курскавтодор», используются в учебном процессе Курского государственного университета в составе курса «Экспертные системы. Базы знаний» при обучении студентов дневного отделения по направлению 010500 - "Математическое обеспечение и администрирование информационных систем", что подтверждается актами внедрения.

Апробация работы. Основные положения диссертации докладывались и обсуждались на следующих конференциях: 15-й Международной научно-технической конференции «Физические и компьютерные технологии» (Харьков — 2009); Всероссийской конференции с элементами научной школы для молодежи «Проведение научных исследований в области обработки, хранения, передачи и защиты информации» (Ульяновск - 2009); Международной научно-практической конференции студентов и аспирантов «Математика и ее приложения в современной науке и практике» (Курск - 2011); 3-й

Международной научно-технической конференции «Информационно-измерительные диагностические и управляющие системы. Диагностика 2013» (Курск - 2013); 10-й Международной научно-практической конференции «Теория и практика современной науки» (Москва - 2013). Также фрагменты диссертации рассматривались на семинарах кафедры программного обеспечения и администрирования информационных систем факультета физики, математики и информатики Курского государственного университета в 2012-2013 гг.

Публикации. По теме диссертации опубликовано 12 работ, в том числе 3 в журналах, рекомендованных ВАК. В федеральном государственном бюджетном учреждении «Федеральный институт промышленной собственности» получено три свидетельства (№ 2009612528 от 24.09.2009, №2013661589 от 11.12.2013, №2013661588 от 11.12.2013) о государственной регистрации программ для электронных вычислительных машин и баз данных. Основные положения, выносимые на защиту

Методы и алгоритмические модели (АМ) на основе хаотического рассеивания пикселей изображений с использованием дискретных отображений:

• метод и АМ сжатия изображений, обеспечивающие дополнительное сжатие после использования известных алгоритмов компрессии;

• метод и АМ распознавания изображений, отличающиеся использованием хаотически рассеянных форм представления изображений, обеспечивающих существенное сокращение затрат времени при массовой обработке и распознавании изображений;

» метод и АМ поиска изображений по содержанию путем восстановления объектов поиска в изображениях, обеспечивающее сокращение затрат времени и памяти

Результаты экспериментальных исследований эффективности алгоритмов и программных средств.

Представленная диссертация соответствует паспорту специальности 05.13.01 преимущественно по пунктам 5, 10 и 12.

Струкггура и объем диссертации: диссертация состоит из введения, четырех глав, заключения, списка литературы (167 источников) и приложений, изложенных на 195 страницах, содержит 71 рисунок и 3 таблицы. В приложениях приведены копии актов о внедрении, дипломов и исходные тексты программ, реализованных по разработанным алгоритмам.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Прежде всего, необходимо отметить, что под термином «инструментальные средства» в данной работе понимаются алгоритмические схемы и программные средства решения поставленных задач.

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

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

Рассмотрены основные подходы, применяющиеся для определения особенностей изображений при использовании методов поиска изображений по содержанию. Выделены наиболее распространенные на сегодняшний день методы (SIFT и SURF) СВГО. — поиска, дано краткое описание этих методов.

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

Во второй главе дано математическое описание предлагаемого подхода, существующих методов поиска изображений по содержанию (SIFT и SURF), используемых для сопоставления разработанного алгоритма CBIR-поиска. Также даны описания фрактальной размерности (ФР) и зависимости степени сжатия бинарных изображений от значений ФР. Приведено краткое описание теории хаотических систем и особенностей детерминированно-хаотических процессов.

Рассмотренные методы (SIFT и SURF) основаны на поиске и описании с помощью так называемых дескрипторов, особых (ключевых) точек, позволяющих однозначно идентифицировать изображение или его фрагмент.

В этой главе дано определение фрактальной размерности, применяемой для нахождения размеров различных множеств (в том числе самоподобных). Для ограниченного множества X в пространстве R" идея заключается в следующем: разделим R" на регулярную сетку кубов с длиной S и посчитаем количество кубов, пересекающих X, если это число принадлежит N(s), то определяем «ячеистое измерение» (box-counting dimension) X как:

i^MW). (i)

Для исследования коэффициента сжатия (КС) от значения фрактальной размерности (ФР) были созданы два класса изображений: класс А включал в себя изображения, имеющие значительное количество повторяющихся блоков, класс Б - изображения, содержащие незначительное число повторяющихся фрагментов, к данному классу изображений были отнесены фракталы и изображение, полученное в результате работы хаотического генератора. Экспериментально было установлено следующее: средний коэффициент сжатия

изображений класса А составил 225.12 (самый большой КС = 1417,37 зафиксирован при сжатии изображения шахматной доски, при ФР=1,866); среднее значение ФР для данного класса - 1,886; средний коэффициент сжатия изображений класса Б составил 74,56, среднее значение ФР для данного класса -1,9127 (наименьший КС наблюдался при сжатии хаотического изображения -11,67, при ФР=1,9999). При проведении эксперимента были зафиксированы случаи, когда при одинаковом значении ФР изображения имели схожий размер после сжатия. Нужно отметить, что все изображения сжимались алгоритмом CCITG4.

Разработанные методы основаны на хаотической трансформации изображений (хаотическая тасовка местоположений пикселей), поэтому на первом этапе во всех предлагаемых методах осуществляется представление изображений в виде ХПИ (хаотически преобразованного изображения).

Метод сжатия изображений можно условно разделить на несколько этапов.

Этап 2. Преобразование ХПИ в нуль - единичный массив. В данном массиве черному пикселю соответствует ноль, белому — единица.

ЭтапЗ. Аннуляции фрагмента массива путем замещения нулями соответствующих элементов.

Этап 4. Конвертация изображения из бинарного массива в файл формата bmp без включения аннулированного фрагмента.

Этап 5. Маркировка изображения для осуществления возможности последующего восстановления путем добавления к названию полученного файла размера изображения в пикселях (его высоты и ширины).

Этап 6. Восстановление изображения, полученного на этапе 3, из хаотической формы представления.

Этап 7. Коррекция изображения, позволяющая восстановить часть удаленного фрагмента:

Ки =/„„•_, +/„_, +4,,н +4к, + W, +!,.„ (2)

где К,j - количество черных пикселей вокруг анализируемого, / -изображение, /,. - анализируемый пиксель изображения.

Метод распознавания состоит из следующих этапов.

Этап 2. Выбор величины информативного блока.

Этап 3. Задание порогового значения, при превышении которого два пикселя изображения считаются различными.

Этап 4. Попиксельное сравнение ХПИ с использованием евклидова расстояния D и подсчет количества идентичных пикселей:

D=J(iu.R-i;.Rf+(iu.G-i;x}f+(i!rB-\;.Br, (з)

где I - ХПИ эталонного изображения; Г - ХПИ изображения из поисковой базы; i,j - индекс текущего пикселя изображения; R, G, В - значения интенсивности цветов в соответствии с моделью RGB.

Этап 5. Нахождение максимального количества идентичных пикселей. Изображение, имеющее наибольшее количество совпадений с эталоном, является искомым.

Этап 6. Восстановление искомого изображения из ХПИ.

Процедуру поиска изображений по содержимому можно разделить на нижеперечисленные этапы.

Этап 2. Выделение искомого образа. Данный этап по своей сути схож с этапом 4 разработанного способа распознавания.

Этап 3. Обнаружение контуров. Нахождение всех контуров на изображениях и выделение самого длинного.

Этап 4. Вычисление моментов контуров, инвариантных к масштабированию и повороту.

Этап 5. Нахождение изображения, имеющего максимальное совпадение с эталонным, путем сравнения моментов контуров (4),

.7

К!' = sign (N!1) * log Nl', (4)

k!! =sign(N'*)* logjV/J,

где />,/, - сравниваемые изображения;N.',Л'/: - моменты контуров соответствующих изображений.

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

В основе предлагаемого подхода лежит трансформирование входного изображения в хаотически преобразованное изображение (ХПИ). Основой для преобразования изображений в ХПИ служат дискретные отображения, используемые в качестве генераторов детерминированно-хаотических числовых последовательностей. В данной работе для генерации ХЧП было использовано детально исследованное разработчиками дискретное отображение Хенона. Функция, реализующая генератор хаотической последовательности чисел, имеет следующий вид:

К, =1-1.4*^,

где XnY: - предшествующие значения хаотической последовательности; XM,YM - текущие; 1.4, 0.3 - параметры отображения; X,0,Yi0 - начальные значения, являющиеся ключами для генерации хаотической последовательности.

Реализацию метода хаотического преобразования можно представить следующей алгоритмической моделью в вербальной форме.

Шаг 1. Вычислить количество пикселей входного изображения.

Шаг 2. Сгенерировать хаотический ряд пар значений и сохранить пары X и Y в отдельные массивы. Далее хаотический ряд представляется в виде нуль - единичных массивов, полученных путем двоичного представления чисел хаотического отображения независимо по X и Y координатам. Бинарное представление хаотического ряда, так же запоминается в строковых массивах: хып>Yb:n ~ гДе индекс bin означает бинарное представление. Длина массивов Хь«,>*&■» должна соответствовать количеству пикселей в изображении.

ШагЗ. Представить изображение в виде одномерного массива (Pic). Для этого необходимо полученное на входе изображение сканировать построчно, извлечь значения интенсивности цветов (согласно модели RGB) и присвоить элементам промежуточного двумерного массива (Img), каждая ячейка которого содержит три байтовых элемента для хранения значений.

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

Шаг 4. Выполнить процедуру хаотического рассеивания изображения. Для этого каждому элементу массива Pic ставится во взаимнооднозначное соответствие элементы строковых массивов ХШ,УШ, что позволяет сократить затраты времени на процедуру хаотической тасовки местоположения пикселей изображения.

Каждый из массивов ХЫп,Уш анализируется с начала и конца, если i-й элемент равен м -i +1, где i-номер анализируемого элемента от начала массива, a M - размер массива, то Pic[i]:=Pic[M -i + 1], процесс повторяется до тех пор, пока ¡'<М2.

Шаг 5. Восстановить двумерное представление изображения. Алгоритм восстановления аналогичен алгоритму, описанному во втором шаге, за тем исключением, что выполнение алгоритма осуществляется в обратном порядке. То есть вначале необходимо выполнить обход массива Img по спирали и копирование элементов из Pic в Img, затем преобразовать байтовые элементы массива Img, содержащие значения трех базовых цветов, в значение цвета RGB.

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

Шаг 1. Сгенерировать хаотический ряд пар значений.

Шаг 2. Представить изображение в одномерном виде.

ШагЗ. Произвести процедуру хаотического рассеивания, но в обратном порядке. То есть в результате прямого выполнения алгоритма рассеивания вначале анализируется массив Хь<п, затем Ytm. В данном же случае необходимо первым обработать массив уш, в результате элементы массива Pic примут свои первоначальные позиции.

Шаг 4. Восстановить двумерное представление изображения.

Приведена алгоритмическая модель предлагаемого метода распознавания. Входными данными рассматриваемого алгоритма является искомое изображение в формате bmp. Следует отметить, что предварительно все изображения поисковой базы должны быть представлены в виде ХПИ.

Алгоритмическую модель процесса распознавания можно представить следующим алгоритмом в вербальной форме.

Шаг 1. Представить входное изображение в ХПИ.

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

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

Шаг 3. Восстановить изображение, имеющее наибольшее совпадение с эталоном из ХПИ.

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

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

Шаг 1. Представить изображения в виде ХПИ.

Шаг 2. Перевести изображения в массив нулей и единиц. Массив должен иметь тот же размер, что и исходное изображение, черному пикселю на изображении соответствует единица в массиве, белому - ноль.

Шаг 3. Удалить часть изображения путем обнуления соответствующего участка массива. Перевести изображения из нуль-единичного массива в изображение формата Ьшр, за исключением аннулированного фрагмента (рис. 1, б). В название выходного файла внести маркер, в котором сохранить исходный размер изображения. В данном виде изображение может быть сохранено на диск, передано по каналам связи и т.д.

Шаг 4. Для восстановления изображения необходимо восстановить изображения из ХПИ (рис. 1, в) и произвести процедуру коррекции (рис. 1, г): проанализировать каждый белый пиксель изображения и подсчитать количество смежных черных пикселей. Если количество черных пикселей больше заданного порога, то присвоить анализируемому пикселю значение черного цвета.

а б в г

Рисунок 1 - Пример сжатия изображения: а - входное изображение; б - ХПИ с удалением части изображения; в - восстановленное; г - скорректированное Описана алгоритмическая модель предлагаемого процесса поиска изображений по содержанию, позволяющего выделить изображение из поисковой базы, содержащее в себе вхождение искомого изображения. Предлагаемый метод состоит из двух этапов.

На первом этапе производится выделение искомых образов (рис. 2). Алгоритм выделения образов можно разделить на несколько шагов: Шаг 1. Представить все изображения в виде ХПИ. Шаг 2. Извлечь изображение из эталонной базы. Произвести анализ каждого пикселя искомого фрагмента с каждым пикселем изображения из эталонной базы (ЭБ) путем вычисления евклидова расстояния. Если полученное значение больше либо равно введенному коэффициенту, то перенести соответствующий пиксель ЭБ в буферный массив (Ьи() с сохранением местоположения, исключить координаты перенесенного пикселя из поиска.

ШагЗ. После окончания анализа восстановить массив Ьи£ из ХПИ. Сохранить полученное изображение.

Шаг 4. Если проанализированы все изображения из эталонной базы, завершить работу алгоритма. Иначе, перейти к шагу 2.

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

Шаг 1. Произвести поиск контуров на искомом изображении.

Шаг 2. Произвести поиск контуров на всех эталонных изображениях.

Шаг 3. Вычислить моменты найденных контуров.

Шаг 4. Найти лучшее совпадение контуров по их моментам.

1/ Щ

л *

а б в

Рисунок 2 - Пример изображений используемых в процедуре выделения контуров: а -эталонное изображение; б - изображение из поисковой базы; в - результат выделения образа

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

При экспериментальном исследовании предлагаемого метода распознавания было произведено сравнение разработанного метода и алгоритма с уже существующей на данный момент системой «Неадаптивного распознавания образов в условиях ограниченного количества информации». Для тестирования была использована общедоступная база человеческих лиц Со1огРЕКЕТ, поскольку тестирование системы неадаптивного распознавания осуществлено автором именно на данной базе изображений. Были проведены аналогичные эксперименты с использованием помех: сокрытие части изображения квадратом различного размера и гауссово размытие (с радиусом: 3x3, 5x5, 7x7 пикселей) как распознаваемых изображений, так распознаваемых и эталонных изображений совместно.

В результате эксперимента было установлено (см. таблицу): при размытии распознаваемых изображений ошибок первого рода, значительно меньше по сравнению с аналогичным методом. За исключением размытия с размером ядра 7x7 пикселей, в данном случае значения ошибок первого рода примерно равны. Значения ошибок второго рода также меньше, чем у сопоставляемого метода; в случае размытия распознаваемых и эталонных изображений наблюдается существенное уменьшение ошибок как первого, так и второго рода по сравнению с размытием только распознаваемого изображения. Сопоставляемый метод, также уступает предлагаемому подходу; внесение помех по средствам сокрытия части изображения не оказывает существенного влияния на качество распознавания в отличие от метода, с которым осуществляется сопоставление.

Результаты экспериментальных исследований предлагаемого метода распознавания

Тип помех Система адаптивного распознавания Предлагаемый подход

Ошибка 1-го рода Ошибка 2-го рода Ошибка 1-го рода Ошибка 2-го рода

Гауссово размытие распознаваемых изображений (3x3) 7,81 % 4,1 % 0,667 % 0,77 %

Гауссово размытие распознаваемых изображений (5x5) 8,782 % 8,31 % 4,33 % 2,67 %

Гауссово размытие распознаваемых изображений(7x7) 10,009 % 18,74% 9,66 % 8,01 %

Гауссово размытие распознаваемых и эталонных изображений (3x3) 1,972 % 8,03 % 0,33 % 0,77 %

Гауссово размытие распознаваемых и эталонных изображений (5x5) 2,279 % 10,51 % 0,66 % 1,445 %

Гауссово размытие распознаваемых и эталонных изображений (7x7) 2,42 % 6,97 % 2,33 % 3,07 %

Черный квадрат 3 % 1,178 % 6,79 % 0% 0,96 %

Черный квадрат 5 % 1,471 % 5,39 % 0% 1,07%

Черный квадрат 10 % 1,679% 3,63 % 0,33 % 1,35 %

Черный квадрат 15 % 2,356 % 3,63 % 0,33 % 1,47 %

Черный квадрат 20 % 3,796 % 3,63 % 0,67 % 1,56 %

Также нужно отметить, что предлагаемый метод, анализирует не все изображение, а лишь 30 % от исходного размера (величина информативного блока изображения установлена экспериментальным путем). Предлагаемый метод демонстрирует лучшие показатели при искажении изображений гауссовым размытием, следовательно, при распознавании изображений, переданных по зашумленным каналам связи, предпочтительно использование данного метода. Также было проведено исследование применимости данного алгоритма к поиску схожих (однородных) изображений.

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

Прежде всего, следует отметить, что предлагаемый подход не является альтернативой уже существующим методам сжатия изображений. Разработанный алгоритм позиционируется как дополнительное средство сжатия данных в совокупности с уже существующими методами компрессии, поэтому проведены исследования зависимости качества получаемых изображений от величины удаления его части. Метрикой визуального качества изображений была выбрана МБ-ЗБМ, так как она является одной из адекватных метрик, поскольку учитывает восприятие изображения человеком и для данной метрики определены граничные значения, при которых искажения практически незаметны (0,99).

Для тестирования предлагаемого метода была создана база изображений, включающих в себя изображения различной природы: блок-схемы алгоритмов и схемы электрических цепей; лица людей; изображения дикой природы (лес); фракталы.

Бинаризация соответствующих изображений осуществлялась с порогом отсечения, равным 150, если значение интенсивности цвета больше 150, то пиксель считается черным, иначе — белым. В результате эксперимента установлено, что без визуально заметной потери качества, т.е. при значении метрики MS-SSIM не ниже 0.99, можно удалить от 2 до 5 % изображения в зависимости от его фактуры. Лучше всего предлагаемый метод показал себя при обработке блок-схем алгоритмов и человеческих лиц. Это обусловлено тем, что изображения данных классов в большинстве своем имеют небольшое количество неоднородных фрагментов, что позволяет производить коррекцию, улучшая качество изображения.

Необходимо отметить, что оценку качества сжимаемого изображения и его восстановления может дать только эксперт в конкретной области применения. В качестве примера можно привести сжатие буквы А (рис. 3) разработанным алгоритмом. Путем опроса группы из 20 человек установлено, что даже после удаления 70 % от исходного размера изображения человеческий глаз безошибочно распознает букву «А» за 0,5 секунды от времени предъявления.

А" А А""

-70

/Л

Рисунок 3 - Исходное изображение и с удалением 30. 50.70 процентов от исходного размера (слева

направо) после применения процедуры коррекции

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

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

1. вращение эталонного изображения относительно центра (40, 135, 215, 250 и 300 градусов);

2. изменение яркости (50, 70,100, 120, -30, -50, -70, -90);

3. добавление к эталону гауссового шума (5 %, 10 % и 20 %);

4. масштабирование изображения (уменьшение на 30 %, 50 % и 70 % от исходного размера);

Для определения затрат времени анализируемых методов использовалась документация, представленная на официальном сайте компании Intel, содержащая информацию о скорости выполнения команд ассемблера (в тактах) процессорами серии Atom. Также осуществлялась оценка затрат времени путем многократного прогона (до 5000 раз) решения одной и той же задачи и фиксацией времени решения по таймеру с последующим вычислением числа тактов, затраченных на решения, принимая во внимание тактовую частоту исполнительного устройства. Данный механизм оценки является затратным по времени, но зато он дает возможность получить оценки числа тактов для всего многообразия задач при осуществлении экспериментальных исследований.

По результатам проведенных испытаний была построена квалиметрическая диаграмма, представленная на рис 4. На основании визуального анализа диаграммы можно сделать вывод о том, что все представленные алгоритмы имеют примерно равные параметры во всех произведенных тестах, за исключением вычислительной сложности, в данном тесте лидером оказывается алгоритм на основе предлагаемого в диссертации метода.

Квалиметрическая диаграмма

Вращение

100а \ ! sm

Обр.велич. 5(2-затрат, в p. V^ftL I -«-Surf ^xj^» Освещен! ..............V........у | Предлагаемый \ I И метод

Масштаб- Шум

где «обратная велич. затрат вр.» означает обратную величину числа тактов, затраченных на решение задачи Рисунок 4 - Квалиметрическая диаграмма

Принимая во внимание результаты экспериментальных данных, получены следующие выводы.

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

Хаотическое рассеивание пикселей осуществляется для всех трех решаемых задач путем использования известных и детально исследованных дискретных отображений, используемых в качестве генераторов детерминированно-хаотических числовых рядов. На основе хаотически рассеянных форм представления изображений были разработаны и исследованы: метод и алгоритмическая модель процесса сжатия изображений, позволяющие удалить часть изображения с последующим восстановлением и коррекцией, исследованы зависимости качества сжатия при вычисленной фрактальной размерности изображений и влияние размеров удаляемой части изображения на меру визуального качества изображений (МБ-ЗБГМ); метод и алгоритмическая модель процесса распознавания изображений при их сопоставлении со множеством эталонов, в данном методе, используя хаотическое рассеивание (тасовка) пикселей изображений, осуществляется анализ не всего объема в байтах распознаваемого изображения, а его монотонно увеличивающейся части с остановкой работы алгоритма при достижении приоритетной величины совпадений пикселей распознаваемого изображения с пикселями эталонов, хранящихся в графической базе данных, что существенно сокращает затраты времени, установлена линейная зависимость затрат времени в тактах от числа пикселей в изображениях; метод и алгоритмическая модель процесса поиска изображений по содержанию, установлено, что по сравнению с прототипом выигрыш по затратам времени в тактах составляет более трех раз без значимых негативных изменений других параметров (вращение, масштаб, уровень шума, освещенность), влияющих на интегральный показатель качества при сопоставительном анализе с существующими аналогами.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Работы, опубликованные в научных журналах, входящих в перечень ведущих рецензируемых журналов и изданий ВАК РФ:

1. Галахов Д.И., Гора С.Ю., и др. Алгоритм ассоциативного поиска изображений на основе хаотических последовательностей // Известия Юго-Западного государственного университета №3 (36). - Курск, 2011. - С. 105-107.

'2. Гора С.Ю., Довгаль В.М. Метод и инструментальные средства решения задачи сжатия изображений с использованием механизмов хаотической динамики // Ученые записки. Электронный научный журнал Курского государственного университета. № 4-2. -Курск, 2012.-С. 25-28.

3. Гора С.Ю., Довгаль В.М. Об одном подходе к поиску изображений по содержимому // В мире научных открытий. 2013. - №6.1(42). - С. 23-38

Работы, опубликованные в сборниках научных трудов, материалах международных и всероссийских конференций:

4. Гордиенко В.В., Гора С.Ю. и др. Алгоритм сжатия и восстановления изображений по заданному фрагменту // Труды 15-й Международной научно-технической

конференции "Физические и компьютерные технологии".- Харьков: ХНПК "ФЭД". - 2009. -С. 460-463.

5. Довгаль В.М., Гора С.Ю. и др. К вопросу о применении хаотических последовательностей для сжатия и восстановления изображений // сборник научных трудов. В 4 т. Т. 1. Всероссийской конференции с элементами научной школы для молодежи. -Ульяновск, 2009. - С. 38-42.

6. Гора С.Ю. Прикладная теория хаотических систем: обработка изображений // Математика и ее приложения в современной науке и практике: сборник научных статей по материалам Международной научно-практической конференции студентов и аспирантов. -Курск, 2011.-С. 180-187.

7. Гора С.Ю., Довгаль В.М. Дискретные хаотические процессы и обработка информации. Сжатие и распознавание изображений // Lap Lambert Academic Publishing GmbH & Co. KG Saarbrucken, Germany, 2012. - 84 с. ISBN: 978-3-659-23131-5

8. Гора С.Ю. Обработка фотоизображений зрачка глаза для идентификации личности с использованием теории хаотических систем // Информационные системы: Теория и практика: сб. науч. работ. Вып.З фак. физики, математики и информатики Курск, гос. ун-та. -Курск, 2013.-С. 19-23.

9. Гора С.Ю. Способ генерации проверочных изображений на WEB-pecypcax, основанный на механизмах хаотической динамики // Информационные системы: Теория и практика: сб. науч. работ. Вып.З фак. физики, математики и информатики Курск, гос. ун-та. -Курск, 2013.-С. 24-29.

10. Гора С.Ю., Лопин В.Н. Алгоритм поиска изображений по содержанию // Информационно-измерительные диагностические и управляющие системы. Диагностика -2013: сб. материалов III Междунар. Науч. - техн. конф. Юго - зап. гос. ун-т. - Курск, 2013. -С. 68-73.

11. Гора С.Ю., Лопин В.Н. К вопросу о применении и перспективах использования достижений теории хаотических систем в процессах обработки данных // Молодой ученый. -2013,-№8.-С. 82-85.

12. Гора С.Ю. Проблемы сжатия изображений на основе механизмов хаотической динамики // Теория и практика современной науки: материалы X Международной научно-практической конференции. - Москва, 2013. - С. 78-82.

Свидетельства о регистрации програлш:

13. Гора С.Ю., Галахов Д.И. и др. Программный продукт для распознавания изображений по заданному фрагменту. М.: ОФАП. 2009 (свидетельство о регистрации К» 2009615280 от 24.09.2009).

14. Гора С.Ю., Довгаль В.М.Программа распознавания образов для идентификации личности на основе биометрических данных. М.: ОФАП. 2013 (свидетельство о регистрации №2013661588 от 11.12.2013).

15. Гора С.Ю., Довгаль В.М.Программа распознавания изображений с использование дискретных отображений. М.: ОФАП. 2013 (свидетельство о регистрации №2013661589 от 11.12.2013).

Гора Сергей Юрьевич

МЕТОДЫ И ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА РЕШЕНИЯ ЗАДАЧ

СЖАТИЯ, РАСПОЗНАВАНИЯ И ПОИСКА ИЗОБРАЖЕНИЙ ПО СОДЕРЖАНИЮ НА ОСНОВЕ ДИСКРЕТНЫХ ОТОБРАЖЕНИЙ

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 01.12.2014 Бумага офисная. Формат бумаги 60x84 1/16. Гарнитура Тайме. Усл. печ. л. 1,0. Тираж 100 экз. Печать цифровая. Заказ № 4717.

Отпечатано: «Деловая полиграфия», г. Курск, ул. К.Маркса, 61 Б. Тел./факс (4712) 36-09-45.