РАСПРЕДЕЛЕНИЕ САМОПОДОБИЯ НА ЦИФРОВОМ ИЗОБРАЖЕНИИ
27
УДК 004.942
А. Л. ЖИЗНЯКОВ, Д. Г. ПРИВЕЗЕНЦЕВ
РАСПРЕДЕЛЕНИЕ САМОПОДОБИЯ НА ЦИФРОВОМ ИЗОБРАЖЕНИИ
Приведены алгоритмы вычисления признаков изображений, характеризующих внутреннее распределение самоподобия. Ключевые слова: обработка изображений, фрактальные признаки изображений.
Введение. В настоящее время одним из перспективных направлений в цифровой обработке изображений является применение фрактального анализа. Фракталы обладают свойством самоподобия, означающим сохранение (точное или вероятностное) свойств объекта при изменении его масштабов. Свойство самоподобия приводит к определенным закономерностям в статистическом поведении признаков изображений, в результате чего изображения можно с определенной точностью описать фрактальными признаками [1—4].
Любая из процедур обработки изображений опирается на формализованное описание, выполненное с определенной степенью абстрагирования. Модель изображения позволяет получить адекватное описание его существенных свойств, чтобы строить эффективные вычислительные процедуры.
Описание изображений возможно с помощью систем итерируемых функций [5, 6], которые также могут быть использованы для построения фракталов [1, 2, 4].
Для качественной классификации изображений необходим набор признаков, характеризующий их однозначно. Точность классификации зависит от полноты набора [7]. Поэтому
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
28 А. Л. Жизняков, Д. Г. Привезенцев
использование фрактальных характеристик изображений полностью традиционных призна-
ков позволит снизить ошибки и существенно увеличить эффективность распознавания.
Распределение самоподобия изображения. Согласно фрактальной модели, изображе-
ние разбивается на доменные блоки D, с помощью которых будет впоследствии описано изо-
бражение. Затем изображение разбивается на ранговые блоки R таким образом, чтобы каж-
дый его участок был описан с помощью доменного блока с требуемой точностью.
Для аппроксимации ранговых блоков доменными применяется преобразование w ,
включающее операции масштабирования, переноса, изменения яркости:
Ri ≈ wi (Di ) = si (wi (Di )) + oi ,
в итоге такого преобразования получается совокупность ранговых блоков, из которых
строится изображение, для каждого указывается доменный блок и преобразование [5, 6]:
( ) ( ( ))∑ [ ]M
f' =
i=1
Bnrii ,mi
*
⎡ ⎢⎣
si
wi
Bkdii,li
f
+
oi
⎤ ⎥⎦
,
где f — исходное изображение; Bkdii,li и Bnrii ,mi — операторы извлечения и вставки блока изображения размером k×k, левый нижний угол которого находится в точке с координатами
(n,m), si, oi — коэффициенты преобразования яркости изображения; wi — аффинное преобра-
зование; M — число ранговых блоков, на которое разбивается изображение при заданных ус-
ловиях фрактального разложения.
Из множества доменных блоков D = {Di } можно выделить подмножество используе-
{ }мых доменных блоков Dи = Dиi ∈ D , отражающее самоподобные участки изображения.
В качестве характеристики самоподобия изображений можно использовать отношение числа
используемых к общему числу доменных блоков.
Каждый доменный блок из множества Dи используется для формирования фрактально-
го кода определенное количество раз, т.е. каждому доменному блоку можно сопоставить чис-
ло, равное количеству раз использования данного блока во фрактальном коде, которое озна-
чает, сколько других участков изображения подобно этому. Разместив эти числа на изобра-
жении в местах расположения соответствующих доменных блоков, можно увидеть наиболее
часто встречающиеся участки (рис. 1, а — первого, б — второго уровня).
а) б)
Рис. 1
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
Распределение самоподобия на цифровом изображении
29
Если используется несколько уровней доменных блоков, то для отражения подобия участков изображения данные по доменным блокам каждого уровня необходимо отобразить на одном изображении (рис. 2).
Рис. 2
Представив частоту использования доменных блоков в виде карты высот и проведя ап-
проксимацию, можно получить трехмерную поверхность Z (x, y) , где x = 1, …, W , y = 1, …, H ,
( )координата
Z (x, y) = 1, …, max
i
Dиi
которой в каждой точке отражает степень подобия участка
изображения (рис. 3).
z
20 10
8 7 6
5
4
3
2
1 x1
2
3
y 4 5 6 78
Рис. 3
Для лучшего отражения непрерывного изменения исследуемой величины на трехмерных поверхностях обычно применяются изолинии.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
30 А. Л. Жизняков, Д. Г. Привезенцев Построенные для поверхности Z (x, y) и наложенные на исходное изображение изоли-
нии демонстрируют изменения самоподобия участков (рис. 4).
y
50
100
150
200
250
300
350
400
450
500 50 100 150 200 250 300 350 400 450 500 x Рис. 4
Распределение локальных признаков самоподобия внутри изображения лучше всего характеризовать параметрами представленной трехмерной гистограммы использования доменных блоков для восстановления изображения по его фрактальному коду.
Характер распределения самоподобия изображения. Изменение самоподобия участков изображения с помощью изолиний позволяет качественно оценить распределение, но не дает количественной оценки. Для задач автоматической обработки изображений необходимо представить распределение самоподобия в виде характеристик, имеющих числовое или аналитическое выражение. Для этого строится гистограмма использования доменных блоков
HD (i) (рис. 5).
HD 180 160 140 120 100
80 60 40
20
0 40 80 120 160 200 240 280 D Рис. 5
Чем больше значение HD (i) для доменного блока Di , тем более характерным является участок для этого изображения. Следовательно, участки с наибольшим значением HD (i)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
Распределение самоподобия на цифровом изображении
31
можно использовать как шаблоны изображений в задаче распознавания и классификации изображений.
Если значения HD (i) расположить по убыванию, то в общем виде получится следую-
щего вида кривая (рис. 6), которая отражает характер распределения самоподобия на изображении. Если аппроксимировать полученные значения уравнением вида y(x) = k ln(x) + b , то
можно получить аналитическое выражение, характеризующее распределение признаков самоподобия: y = –13,43ln(x) + 77,016 при доверительной вероятности 9,93.
HD
120
100
80 60
40
20
0
1
37
79
121 157
199 241
277 х
Рис. 6
Таким образом, предлагается использовать признаки изображений, характеризующие внутреннее распределение самоподобия участков изображения. Распределение самоподобия позволяет использовать в качестве информативных признаков изображения наиболее харак-
терные его участки, полученные на основе гистограммы HD (i) , которые в большинстве
случаев являются уникальными для каждого изображения или класса изображений, и коэффициенты уравнения k и b , описывающего характер распределения локальных признаков самоподобия.
СПИСОК ЛИТЕРАТУРЫ
1. Новейшие методы обработки изображений / Под ред. А. А. Потапова. М.: ФИЗМАТЛИТ, 2008. 496 с.
2. Шелухин О. И., Осин А. В., Смольский С. М. Самоподобие и фракталы. Телекоммуникационные приложения. М.: ФИЗМАТЛИТ, 2008. 368 с.
3. Методы компьютерной обработки изображений / Под ред. В. А. Сойфера. М.: ФИЗМАТЛИТ, 2003. 784 с.
4. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. М.: Изд-во „Триумф“, 2003. 320 с.
5. Привезенцев Д. Г. Модель цифрового изображения с использованием систем итерируемых функций // Информационные технологии моделирования и управления. 2010. № 6(65). С. 761—769.
6. Привезенцев Д. Г., Жизняков А. Л. Фрактальная модель цифрового изображения // Алгоритмы, методы и системы обработки данных: сб. науч. тр. Муром: Изд.-полиграф. центр МИ ВЛГУ, 2010. Вып. 15. С. 147—152.
7. Жизняков А. Л. Формирование и анализ наборов признаков многомасштабных последовательностей цифровых изображений // Программные продукты и системы. Изд. ЗАО НИИ „Центрпрограммсистем“. 2007. № 4.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
32
Аркадий Львович Жизняков
Денис Геннадьевич Привезенцев
Рекомендована Юго-Западным государственным университетом
Ю. С. Бехтин, Д. В. Титов
Сведения об авторах — д-р техн. наук, профессор; Муромский институт Владимирского госу-
дарственного университета им. А. Г. и Н. Г. Столетовых, кафедра САПР ЭС; заведующий кафедрой; E-mail: lvovich@newmail.ru — аспирант; Муромский институт Владимирского государственного университета им. А. Г. и Н. Г. Столетовых, кафедра САПР ЭС; E-mail: dgprivezencev@mail.ru
Поступила в редакцию 24.10.11 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
УДК 004.942
А. Л. ЖИЗНЯКОВ, Д. Г. ПРИВЕЗЕНЦЕВ
РАСПРЕДЕЛЕНИЕ САМОПОДОБИЯ НА ЦИФРОВОМ ИЗОБРАЖЕНИИ
Приведены алгоритмы вычисления признаков изображений, характеризующих внутреннее распределение самоподобия. Ключевые слова: обработка изображений, фрактальные признаки изображений.
Введение. В настоящее время одним из перспективных направлений в цифровой обработке изображений является применение фрактального анализа. Фракталы обладают свойством самоподобия, означающим сохранение (точное или вероятностное) свойств объекта при изменении его масштабов. Свойство самоподобия приводит к определенным закономерностям в статистическом поведении признаков изображений, в результате чего изображения можно с определенной точностью описать фрактальными признаками [1—4].
Любая из процедур обработки изображений опирается на формализованное описание, выполненное с определенной степенью абстрагирования. Модель изображения позволяет получить адекватное описание его существенных свойств, чтобы строить эффективные вычислительные процедуры.
Описание изображений возможно с помощью систем итерируемых функций [5, 6], которые также могут быть использованы для построения фракталов [1, 2, 4].
Для качественной классификации изображений необходим набор признаков, характеризующий их однозначно. Точность классификации зависит от полноты набора [7]. Поэтому
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
28 А. Л. Жизняков, Д. Г. Привезенцев
использование фрактальных характеристик изображений полностью традиционных призна-
ков позволит снизить ошибки и существенно увеличить эффективность распознавания.
Распределение самоподобия изображения. Согласно фрактальной модели, изображе-
ние разбивается на доменные блоки D, с помощью которых будет впоследствии описано изо-
бражение. Затем изображение разбивается на ранговые блоки R таким образом, чтобы каж-
дый его участок был описан с помощью доменного блока с требуемой точностью.
Для аппроксимации ранговых блоков доменными применяется преобразование w ,
включающее операции масштабирования, переноса, изменения яркости:
Ri ≈ wi (Di ) = si (wi (Di )) + oi ,
в итоге такого преобразования получается совокупность ранговых блоков, из которых
строится изображение, для каждого указывается доменный блок и преобразование [5, 6]:
( ) ( ( ))∑ [ ]M
f' =
i=1
Bnrii ,mi
*
⎡ ⎢⎣
si
wi
Bkdii,li
f
+
oi
⎤ ⎥⎦
,
где f — исходное изображение; Bkdii,li и Bnrii ,mi — операторы извлечения и вставки блока изображения размером k×k, левый нижний угол которого находится в точке с координатами
(n,m), si, oi — коэффициенты преобразования яркости изображения; wi — аффинное преобра-
зование; M — число ранговых блоков, на которое разбивается изображение при заданных ус-
ловиях фрактального разложения.
Из множества доменных блоков D = {Di } можно выделить подмножество используе-
{ }мых доменных блоков Dи = Dиi ∈ D , отражающее самоподобные участки изображения.
В качестве характеристики самоподобия изображений можно использовать отношение числа
используемых к общему числу доменных блоков.
Каждый доменный блок из множества Dи используется для формирования фрактально-
го кода определенное количество раз, т.е. каждому доменному блоку можно сопоставить чис-
ло, равное количеству раз использования данного блока во фрактальном коде, которое озна-
чает, сколько других участков изображения подобно этому. Разместив эти числа на изобра-
жении в местах расположения соответствующих доменных блоков, можно увидеть наиболее
часто встречающиеся участки (рис. 1, а — первого, б — второго уровня).
а) б)
Рис. 1
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
Распределение самоподобия на цифровом изображении
29
Если используется несколько уровней доменных блоков, то для отражения подобия участков изображения данные по доменным блокам каждого уровня необходимо отобразить на одном изображении (рис. 2).
Рис. 2
Представив частоту использования доменных блоков в виде карты высот и проведя ап-
проксимацию, можно получить трехмерную поверхность Z (x, y) , где x = 1, …, W , y = 1, …, H ,
( )координата
Z (x, y) = 1, …, max
i
Dиi
которой в каждой точке отражает степень подобия участка
изображения (рис. 3).
z
20 10
8 7 6
5
4
3
2
1 x1
2
3
y 4 5 6 78
Рис. 3
Для лучшего отражения непрерывного изменения исследуемой величины на трехмерных поверхностях обычно применяются изолинии.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
30 А. Л. Жизняков, Д. Г. Привезенцев Построенные для поверхности Z (x, y) и наложенные на исходное изображение изоли-
нии демонстрируют изменения самоподобия участков (рис. 4).
y
50
100
150
200
250
300
350
400
450
500 50 100 150 200 250 300 350 400 450 500 x Рис. 4
Распределение локальных признаков самоподобия внутри изображения лучше всего характеризовать параметрами представленной трехмерной гистограммы использования доменных блоков для восстановления изображения по его фрактальному коду.
Характер распределения самоподобия изображения. Изменение самоподобия участков изображения с помощью изолиний позволяет качественно оценить распределение, но не дает количественной оценки. Для задач автоматической обработки изображений необходимо представить распределение самоподобия в виде характеристик, имеющих числовое или аналитическое выражение. Для этого строится гистограмма использования доменных блоков
HD (i) (рис. 5).
HD 180 160 140 120 100
80 60 40
20
0 40 80 120 160 200 240 280 D Рис. 5
Чем больше значение HD (i) для доменного блока Di , тем более характерным является участок для этого изображения. Следовательно, участки с наибольшим значением HD (i)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
Распределение самоподобия на цифровом изображении
31
можно использовать как шаблоны изображений в задаче распознавания и классификации изображений.
Если значения HD (i) расположить по убыванию, то в общем виде получится следую-
щего вида кривая (рис. 6), которая отражает характер распределения самоподобия на изображении. Если аппроксимировать полученные значения уравнением вида y(x) = k ln(x) + b , то
можно получить аналитическое выражение, характеризующее распределение признаков самоподобия: y = –13,43ln(x) + 77,016 при доверительной вероятности 9,93.
HD
120
100
80 60
40
20
0
1
37
79
121 157
199 241
277 х
Рис. 6
Таким образом, предлагается использовать признаки изображений, характеризующие внутреннее распределение самоподобия участков изображения. Распределение самоподобия позволяет использовать в качестве информативных признаков изображения наиболее харак-
терные его участки, полученные на основе гистограммы HD (i) , которые в большинстве
случаев являются уникальными для каждого изображения или класса изображений, и коэффициенты уравнения k и b , описывающего характер распределения локальных признаков самоподобия.
СПИСОК ЛИТЕРАТУРЫ
1. Новейшие методы обработки изображений / Под ред. А. А. Потапова. М.: ФИЗМАТЛИТ, 2008. 496 с.
2. Шелухин О. И., Осин А. В., Смольский С. М. Самоподобие и фракталы. Телекоммуникационные приложения. М.: ФИЗМАТЛИТ, 2008. 368 с.
3. Методы компьютерной обработки изображений / Под ред. В. А. Сойфера. М.: ФИЗМАТЛИТ, 2003. 784 с.
4. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. М.: Изд-во „Триумф“, 2003. 320 с.
5. Привезенцев Д. Г. Модель цифрового изображения с использованием систем итерируемых функций // Информационные технологии моделирования и управления. 2010. № 6(65). С. 761—769.
6. Привезенцев Д. Г., Жизняков А. Л. Фрактальная модель цифрового изображения // Алгоритмы, методы и системы обработки данных: сб. науч. тр. Муром: Изд.-полиграф. центр МИ ВЛГУ, 2010. Вып. 15. С. 147—152.
7. Жизняков А. Л. Формирование и анализ наборов признаков многомасштабных последовательностей цифровых изображений // Программные продукты и системы. Изд. ЗАО НИИ „Центрпрограммсистем“. 2007. № 4.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2
32
Аркадий Львович Жизняков
Денис Геннадьевич Привезенцев
Рекомендована Юго-Западным государственным университетом
Ю. С. Бехтин, Д. В. Титов
Сведения об авторах — д-р техн. наук, профессор; Муромский институт Владимирского госу-
дарственного университета им. А. Г. и Н. Г. Столетовых, кафедра САПР ЭС; заведующий кафедрой; E-mail: lvovich@newmail.ru — аспирант; Муромский институт Владимирского государственного университета им. А. Г. и Н. Г. Столетовых, кафедра САПР ЭС; E-mail: dgprivezencev@mail.ru
Поступила в редакцию 24.10.11 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 2