РАСПОЗНАВАНИЕ ИЗОБРАЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ ХАОТИЧЕСКОЙ ТРАНСФОРМАЦИИ ЭТАЛОНОВ И ОБЪЕКТОВ
16 В. В. Гордиенко, В. М. Довгаль, Р. А. Пузына
УДК 681.3
В. В. ГОРДИЕНКО, В. М. ДОВГАЛЬ, Р. А. ПУЗЫНА
РАСПОЗНАВАНИЕ ИЗОБРАЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ ХАОТИЧЕСКОЙ ТРАНСФОРМАЦИИ
ЭТАЛОНОВ И ОБЪЕКТОВ
Приведен метод распознавания изображений объектов путем использования дискретных хаотических отображений для трансформации эталонов и объектов распознавания изображения, а также для выбора их информативных фрагментов с целью восстановления и распознавания. Ключевые слова: распознавание изображения, хаотический, отображение, эталон, объект, трансформация, таксон восстановления, отказ, матрица.
Настоящая статья посвящена разработке метода распознавания искаженных изображений (объектов), поступающих в графическую базу данных, в которой содержится определенное количество различающихся по Хеммингу эталонных изображений.
Очевидно, что прямое сопоставление эталона и искаженного изображения, выступающего в роли объекта распознавания, с использованием расстояния по Хеммингу обычно неприемлемо. Это обстоятельство послужило отправной точкой для разработки нового метода распознавания. В течение ряда лет авторы предлагаемого метода, имея опыт в области распознавания образов, разрабатывали методы компьютерной стеганографии на основе теории хаотических систем.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Распознавание изображений с использованием хаотической трансформации эталонов и объектов 17
При исследовании хаотического рассеивания сообщения по пространству изображения-
контейнера с последующим восстановлением был обнаружен эффект восстановления исход-
ного изображения с визуально не воспринимаемыми отличиями (изменениями). При этом
восстановление выполнялось не по всему изображению, а по случайным образом выбранному
малому участку с предварительным хаотическим рассеиванием (трансформацией) исходного
изображения.
Представим основные термины и введем аббревиатуры. Все изображения являются чер-
но-белыми, они адекватно замещаются 0,1-матрицами размером N×N. Эталонные изображе-
ния, хранящиеся в графической базе данных (ГБД), калиброваны по центру размещения и уг-
лу поворота. Такие изображения будем называть форматированными и обозначать „ЭФИ“.
Поступающие в ГБД и полученные, например, в результате сканирования, фотографирования
и т.д., как правило искаженные, изображения, являющиеся объектами распознавания, будем
называть входными „ВИ“.
Основное существенное отличие предлагаемого метода распознавания ВИ заключается
в том, что в нем используются положения теории хаотических систем [см. лит.]. Сегодня в
достаточной степени изучены одномерные дискретные отображения, являющиеся генерато-
рами хаотических числовых рядов (ХЧР). В качестве генератора ХЧР будем использовать
отображение Э. Лоренца, имеющее минимальную вычислительную сложность по числу опе-
раций следующего вида:
Xt+1 =1−2 Xt .
(1)
Начальное (стартовое) значение ХЧР Х0 задается в виде правильной десятичной дроби. Как известно, каждому стартовому значению соответствует один и только один ХЧР.
Установленным фактом является то, что все ХЧР при различных стартовых значениях не
повторяются и не имеют совпадающих элементов как внутри себя, так и между собой. При
этом необходимо иметь представительную разрядную сетку не менее 32 двоичных разрядов, тогда в рядах будет содержаться R = 232 чисел. Очевидно, что строгое упорядочение не
может быть осуществлено для числового ряда, имеющего одинаковые по значимости эле-
менты, поэтому никакие генераторы, кроме хаотических, не могут быть использованы в
предлагаемом методе.
На первом этапе распознавания выполняется предварительная обработка ЭФИ. С этой
целью для всех ЭФИ из ГБД выполним операцию хаотического рассеивания в пространстве
формата. Операция хаотического рассеивания содержит следующие процедуры. 1. Все элементы формата каждого ЭФИ нумеруются от 1 до N2. 2. Запускается генератор ХЧР (1) с заданного стартового значения и формируется N2 чи-
сел, которые ставятся во взаимно однозначное соответствие номерам позиций элементов
формата.
3. Выполняется быстрая сортировка полученного ХЧР с алгоритмической сложностью О = N2log(N2).
4. Все значения (0 или 1) в каждой имеющей свой порядковый номер позиции (от 1 до N2) для каждого ЭФИ переносятся в новые позиции, расположение которых теперь одно-
значно определяется строго равными значениями элементов упорядоченного ХЧР и исходно-
го ХЧР.
Полученные в результате формы представления ЭФИ будем называть хаотическими
трансформантами эталонов и обозначать „ХТЭ“.
На втором этапе распознавания при поступлении ВИ в ГБД оно вначале калибруется
по центру и углу поворота, а затем над ним также выполняется операция хаотического рас-
сеивания. Полученное ВИ будем называть частичным трансформантом и обозначать „ХТВИ“.
На третьем этапе предлагаемого метода выполняется операция хаотического выбора
подмножества мощностью Р элементов изображений ХТЭ или ХТВИ, которые условимся
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
18 В. В. Гордиенко, В. М. Довгаль, Р. А. Пузына
называть таксонами восстановления и обозначать „ТВ“. Механизм хаотического выбора подмножества из формата изображения реализуется также с помощью отображения (1) с некоторым заданным значением Х0, одинаковым для всех изображений. Полученный ХЧР преобразуется в битовую строку, из которой сохраняются биты с номерами позиций с 1 до Р ≤ N2, но при Р, не меньшем значения N2/α. Параметр α через Р задает ту минимальную часть трансформанта, которая после восстановления изображения (см. ниже) позволяет по нему осуществить визуальное распознавание исходного изображения.
Формирование ТВ для всех ХТЭ осуществляется один раз после завершения загрузки ГБД. Для каждого изображения вычленяется множество ТВj при j = 1, 2, ..., S, где S = N2/α. После формирования ТВ все многообразие ЭФИ при реализации предлагаемого метода распознавания в общем объеме не используется. На заключительном этапе метода обрабатывается только малая часть изображения. Это обстоятельство существенно снижает емкостную сложность (затраты памяти) метода и соответственно его алгоритмической реализации.
На четвертом этапе метода распознавания выполняется сопоставление по расстоянию Хемминга между выбранным таксонами из ХТВИ и всеми — из ХТЭ. Если осуществляется выбор одного или нескольких (до пяти) W ХТЭ по минимуму расстояния Хемминга, то реализуется следующий этап метода, в противном случае выполнятся присоединение к выбранному одного, любого, ТВ для всех ХТВИ и ХТЭ. При невыполнении условий перехода к следующему этапу метода выполняется очередное присоединение ТВ.
Сформулируем важное утверждение: „Поскольку ТВ являются высокоспецифичными для каждого изображения и строго различаются на основании свойства ХЧР не повторять значения собственных элементов, а также в силу исходного различия по расстоянию Хемминга эталонов ГБД между собой, то итерация присоединения очередного ТВ завершается за конечное число шагов на основании того, что объединение разных ТВ из их множества в совокупности, например при S = N2, приводит к его полному совпадению с исходным трансформантом изображения“.
На пятом этапе метода распознавания выполняются процедура восстановления ВИ и его классификация на основании нового множества ТВj, которое формируется для каждой пары ТВj из ХТВИ и ТВj из ХТЭ для каждого из выбранного на предыдущем этапе метода применением операции конъюнкции всех пар элементов (каждая определяется одинаковым порядковым номером от 1 до N2). Формируется новый трансформант промежуточного изображения (ТПИ), в который строго на свои позиции переносятся только единичные значения из нового ТВj в строгом соответствии с их размещением в ХТВИ. После этого выполняется процедура восстановления ВИ по полученному ТПИ.
Процедура восстановления (обратная операции хаотического рассеивания, с сохранением используемых для него исходного и упорядоченного ХЧР) выполняется в следующей последовательности.
1. Каждому элементу из упорядоченного ХЧР, имеющего свой порядковый номер, ставится во взаимно однозначное соответствие каждая позиция значения из ТПИ, имеющая одинаковый номер от 1 до N2.
2. Из исходного ХЧР позиции элементов изображения переносятся из ТПИ в позиции, строго соответствующие совпадающим значениям элементов упорядоченного ХЧР. Перенос осуществляется для всех элементов изображения.
3. Восстановление осуществляется для всех полученных ТПИ. В результате получаются новые изображения, число которых равно РW.
На шестом этапе выполняется соотнесение каждого из Р восстановленных изображений по их ТПИ с одним и только одним ЭФИ. С этой целью определяется расстояние по Хеммингу между первым восстановленным ТПИ и ЭФИ. Затем выбирается второй ТВ из ХТВИ и повторяется построение ТПИ, а также выполняется процедура восстановления ВИ. После
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Распознавание изображений с использованием хаотической трансформации эталонов и объектов 19
этого выполняется операция дизъюнкции для всех пар элементов, имеющих равные порядковые номера в двух восстановленных изображениях, и формируется третье изображение. Это изображение назовем аккумулятором. Вновь вычисляется расстояние по Хеммингу между полученным аккумулятором и выбранным ЭФИ. Осуществляется построение всех Р восстановленных ВИ с промежуточным и обязательным формированием аккумуляторов с определением расстояния по Хеммингу от него до выбранного ЭФИ. Аналогичным образом выполняются все построения для всех W ЭФИ.
Если хотя бы для одного фиксированного ЭФИ из множества W расстояние по Хеммингу от него до последовательно формирующихся Р аккумуляторов убывает, то рассматриваемое ВИ относится к этому эталону. Но если для всех ЭФИ из множества W указанное расстояние возрастает, то процесс распознавания прекращается. В этом случае пользователь или выбраковывает ВИ, или включает его в исходном виде в качестве эталона, пополняя графическую базу данных.
Представленный метод распознавания алгоритмизирован и был разработан программный продукт „Haos-DGP“, использование которого показало, что при распознавании чернобелых изображений размером 500×500 при α = 100 все искаженные до 40 % тестовые входные изображения, полученные из эталонов (в количестве 1000), распознавались. При этом количество W = 2, а максимальное наблюдаемое значение — 24. Коэффициент качества распознавания для общего случая имеет оценку не ниже 0,94.
Вместе с тем затраты времени в некоторых случаях достигали 5 с при среднем показателе затрат времени 0,8 с. Основным источником завышенных затрат времени является сортировка, поэтому для ее реализации рекомендуется использовать многоядерные вычислители или эффективно использовать для сортировки и слияния процессоры видеокарты (пиксельные и шейдерные), не занятые при реализации разработанного метода распознавания.
В настоящее время авторский коллектив завершает разработку программного продукта для распознавания изображений в формате .bmp с тремя байтами на пиксел.
ЛИТЕРАТУРА
Паркер Т. С., Чжуа Л. О. Введение в теорию хаотических систем для инженеров // ТИИЭР. 1987. Т. 75, № 8. C. 6—40.
Сведения об авторах
Виктория Викторовна Гордиенко — канд. техн. наук, доцент; Курский государственный технический
университет, кафедра уголовного права
Виктор Митрофанович Довгаль — д-р техн. наук, профессор; Курский государственный технический
университет, кафедра программного обеспечения вычислительной
техники; заведующий кафедрой; E-mail: vmdovgal@yandex.ru
Роман Андреевич Пузына
— аспирант; Курский государственный технический университет,
кафедра программного обеспечения вычислительной техники
Рекомендована кафедрой программного обеспечения вычислительной техники
Поступила в редакцию 12.09.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
УДК 681.3
В. В. ГОРДИЕНКО, В. М. ДОВГАЛЬ, Р. А. ПУЗЫНА
РАСПОЗНАВАНИЕ ИЗОБРАЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ ХАОТИЧЕСКОЙ ТРАНСФОРМАЦИИ
ЭТАЛОНОВ И ОБЪЕКТОВ
Приведен метод распознавания изображений объектов путем использования дискретных хаотических отображений для трансформации эталонов и объектов распознавания изображения, а также для выбора их информативных фрагментов с целью восстановления и распознавания. Ключевые слова: распознавание изображения, хаотический, отображение, эталон, объект, трансформация, таксон восстановления, отказ, матрица.
Настоящая статья посвящена разработке метода распознавания искаженных изображений (объектов), поступающих в графическую базу данных, в которой содержится определенное количество различающихся по Хеммингу эталонных изображений.
Очевидно, что прямое сопоставление эталона и искаженного изображения, выступающего в роли объекта распознавания, с использованием расстояния по Хеммингу обычно неприемлемо. Это обстоятельство послужило отправной точкой для разработки нового метода распознавания. В течение ряда лет авторы предлагаемого метода, имея опыт в области распознавания образов, разрабатывали методы компьютерной стеганографии на основе теории хаотических систем.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Распознавание изображений с использованием хаотической трансформации эталонов и объектов 17
При исследовании хаотического рассеивания сообщения по пространству изображения-
контейнера с последующим восстановлением был обнаружен эффект восстановления исход-
ного изображения с визуально не воспринимаемыми отличиями (изменениями). При этом
восстановление выполнялось не по всему изображению, а по случайным образом выбранному
малому участку с предварительным хаотическим рассеиванием (трансформацией) исходного
изображения.
Представим основные термины и введем аббревиатуры. Все изображения являются чер-
но-белыми, они адекватно замещаются 0,1-матрицами размером N×N. Эталонные изображе-
ния, хранящиеся в графической базе данных (ГБД), калиброваны по центру размещения и уг-
лу поворота. Такие изображения будем называть форматированными и обозначать „ЭФИ“.
Поступающие в ГБД и полученные, например, в результате сканирования, фотографирования
и т.д., как правило искаженные, изображения, являющиеся объектами распознавания, будем
называть входными „ВИ“.
Основное существенное отличие предлагаемого метода распознавания ВИ заключается
в том, что в нем используются положения теории хаотических систем [см. лит.]. Сегодня в
достаточной степени изучены одномерные дискретные отображения, являющиеся генерато-
рами хаотических числовых рядов (ХЧР). В качестве генератора ХЧР будем использовать
отображение Э. Лоренца, имеющее минимальную вычислительную сложность по числу опе-
раций следующего вида:
Xt+1 =1−2 Xt .
(1)
Начальное (стартовое) значение ХЧР Х0 задается в виде правильной десятичной дроби. Как известно, каждому стартовому значению соответствует один и только один ХЧР.
Установленным фактом является то, что все ХЧР при различных стартовых значениях не
повторяются и не имеют совпадающих элементов как внутри себя, так и между собой. При
этом необходимо иметь представительную разрядную сетку не менее 32 двоичных разрядов, тогда в рядах будет содержаться R = 232 чисел. Очевидно, что строгое упорядочение не
может быть осуществлено для числового ряда, имеющего одинаковые по значимости эле-
менты, поэтому никакие генераторы, кроме хаотических, не могут быть использованы в
предлагаемом методе.
На первом этапе распознавания выполняется предварительная обработка ЭФИ. С этой
целью для всех ЭФИ из ГБД выполним операцию хаотического рассеивания в пространстве
формата. Операция хаотического рассеивания содержит следующие процедуры. 1. Все элементы формата каждого ЭФИ нумеруются от 1 до N2. 2. Запускается генератор ХЧР (1) с заданного стартового значения и формируется N2 чи-
сел, которые ставятся во взаимно однозначное соответствие номерам позиций элементов
формата.
3. Выполняется быстрая сортировка полученного ХЧР с алгоритмической сложностью О = N2log(N2).
4. Все значения (0 или 1) в каждой имеющей свой порядковый номер позиции (от 1 до N2) для каждого ЭФИ переносятся в новые позиции, расположение которых теперь одно-
значно определяется строго равными значениями элементов упорядоченного ХЧР и исходно-
го ХЧР.
Полученные в результате формы представления ЭФИ будем называть хаотическими
трансформантами эталонов и обозначать „ХТЭ“.
На втором этапе распознавания при поступлении ВИ в ГБД оно вначале калибруется
по центру и углу поворота, а затем над ним также выполняется операция хаотического рас-
сеивания. Полученное ВИ будем называть частичным трансформантом и обозначать „ХТВИ“.
На третьем этапе предлагаемого метода выполняется операция хаотического выбора
подмножества мощностью Р элементов изображений ХТЭ или ХТВИ, которые условимся
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
18 В. В. Гордиенко, В. М. Довгаль, Р. А. Пузына
называть таксонами восстановления и обозначать „ТВ“. Механизм хаотического выбора подмножества из формата изображения реализуется также с помощью отображения (1) с некоторым заданным значением Х0, одинаковым для всех изображений. Полученный ХЧР преобразуется в битовую строку, из которой сохраняются биты с номерами позиций с 1 до Р ≤ N2, но при Р, не меньшем значения N2/α. Параметр α через Р задает ту минимальную часть трансформанта, которая после восстановления изображения (см. ниже) позволяет по нему осуществить визуальное распознавание исходного изображения.
Формирование ТВ для всех ХТЭ осуществляется один раз после завершения загрузки ГБД. Для каждого изображения вычленяется множество ТВj при j = 1, 2, ..., S, где S = N2/α. После формирования ТВ все многообразие ЭФИ при реализации предлагаемого метода распознавания в общем объеме не используется. На заключительном этапе метода обрабатывается только малая часть изображения. Это обстоятельство существенно снижает емкостную сложность (затраты памяти) метода и соответственно его алгоритмической реализации.
На четвертом этапе метода распознавания выполняется сопоставление по расстоянию Хемминга между выбранным таксонами из ХТВИ и всеми — из ХТЭ. Если осуществляется выбор одного или нескольких (до пяти) W ХТЭ по минимуму расстояния Хемминга, то реализуется следующий этап метода, в противном случае выполнятся присоединение к выбранному одного, любого, ТВ для всех ХТВИ и ХТЭ. При невыполнении условий перехода к следующему этапу метода выполняется очередное присоединение ТВ.
Сформулируем важное утверждение: „Поскольку ТВ являются высокоспецифичными для каждого изображения и строго различаются на основании свойства ХЧР не повторять значения собственных элементов, а также в силу исходного различия по расстоянию Хемминга эталонов ГБД между собой, то итерация присоединения очередного ТВ завершается за конечное число шагов на основании того, что объединение разных ТВ из их множества в совокупности, например при S = N2, приводит к его полному совпадению с исходным трансформантом изображения“.
На пятом этапе метода распознавания выполняются процедура восстановления ВИ и его классификация на основании нового множества ТВj, которое формируется для каждой пары ТВj из ХТВИ и ТВj из ХТЭ для каждого из выбранного на предыдущем этапе метода применением операции конъюнкции всех пар элементов (каждая определяется одинаковым порядковым номером от 1 до N2). Формируется новый трансформант промежуточного изображения (ТПИ), в который строго на свои позиции переносятся только единичные значения из нового ТВj в строгом соответствии с их размещением в ХТВИ. После этого выполняется процедура восстановления ВИ по полученному ТПИ.
Процедура восстановления (обратная операции хаотического рассеивания, с сохранением используемых для него исходного и упорядоченного ХЧР) выполняется в следующей последовательности.
1. Каждому элементу из упорядоченного ХЧР, имеющего свой порядковый номер, ставится во взаимно однозначное соответствие каждая позиция значения из ТПИ, имеющая одинаковый номер от 1 до N2.
2. Из исходного ХЧР позиции элементов изображения переносятся из ТПИ в позиции, строго соответствующие совпадающим значениям элементов упорядоченного ХЧР. Перенос осуществляется для всех элементов изображения.
3. Восстановление осуществляется для всех полученных ТПИ. В результате получаются новые изображения, число которых равно РW.
На шестом этапе выполняется соотнесение каждого из Р восстановленных изображений по их ТПИ с одним и только одним ЭФИ. С этой целью определяется расстояние по Хеммингу между первым восстановленным ТПИ и ЭФИ. Затем выбирается второй ТВ из ХТВИ и повторяется построение ТПИ, а также выполняется процедура восстановления ВИ. После
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2
Распознавание изображений с использованием хаотической трансформации эталонов и объектов 19
этого выполняется операция дизъюнкции для всех пар элементов, имеющих равные порядковые номера в двух восстановленных изображениях, и формируется третье изображение. Это изображение назовем аккумулятором. Вновь вычисляется расстояние по Хеммингу между полученным аккумулятором и выбранным ЭФИ. Осуществляется построение всех Р восстановленных ВИ с промежуточным и обязательным формированием аккумуляторов с определением расстояния по Хеммингу от него до выбранного ЭФИ. Аналогичным образом выполняются все построения для всех W ЭФИ.
Если хотя бы для одного фиксированного ЭФИ из множества W расстояние по Хеммингу от него до последовательно формирующихся Р аккумуляторов убывает, то рассматриваемое ВИ относится к этому эталону. Но если для всех ЭФИ из множества W указанное расстояние возрастает, то процесс распознавания прекращается. В этом случае пользователь или выбраковывает ВИ, или включает его в исходном виде в качестве эталона, пополняя графическую базу данных.
Представленный метод распознавания алгоритмизирован и был разработан программный продукт „Haos-DGP“, использование которого показало, что при распознавании чернобелых изображений размером 500×500 при α = 100 все искаженные до 40 % тестовые входные изображения, полученные из эталонов (в количестве 1000), распознавались. При этом количество W = 2, а максимальное наблюдаемое значение — 24. Коэффициент качества распознавания для общего случая имеет оценку не ниже 0,94.
Вместе с тем затраты времени в некоторых случаях достигали 5 с при среднем показателе затрат времени 0,8 с. Основным источником завышенных затрат времени является сортировка, поэтому для ее реализации рекомендуется использовать многоядерные вычислители или эффективно использовать для сортировки и слияния процессоры видеокарты (пиксельные и шейдерные), не занятые при реализации разработанного метода распознавания.
В настоящее время авторский коллектив завершает разработку программного продукта для распознавания изображений в формате .bmp с тремя байтами на пиксел.
ЛИТЕРАТУРА
Паркер Т. С., Чжуа Л. О. Введение в теорию хаотических систем для инженеров // ТИИЭР. 1987. Т. 75, № 8. C. 6—40.
Сведения об авторах
Виктория Викторовна Гордиенко — канд. техн. наук, доцент; Курский государственный технический
университет, кафедра уголовного права
Виктор Митрофанович Довгаль — д-р техн. наук, профессор; Курский государственный технический
университет, кафедра программного обеспечения вычислительной
техники; заведующий кафедрой; E-mail: vmdovgal@yandex.ru
Роман Андреевич Пузына
— аспирант; Курский государственный технический университет,
кафедра программного обеспечения вычислительной техники
Рекомендована кафедрой программного обеспечения вычислительной техники
Поступила в редакцию 12.09.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 2