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

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

С целью получения аппроксимаций дискретного вейвлетного преобразования значения входных параметров алгоритмов построения и выбора ортогональных базисов декоррелирующих клеточных преобразований, определяющих размерность базиса и число низкочастотных составляющих среди преобразованных элементов данных, примем N = 8 и г N/2 = 4 соответственно.

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

В качестве вектора значений, обладающих пространственной избыточностью, возьмем вектор F [100 110 120 135 140 150 160 185], моделирующий строку (столбец) пикселей полутонового цифрового изображения с плавным цветовым переходом и двумя отклонениями от линейного приращения значений пикселей, а параметр разброса v будем выбирать в интервале 0,75 ^ ^ 0,85.

Для упрощения последующего изложения изменим вид математической модели блочного клеточного автомата (далее будем иметь в виду блочный клеточный автомат к-го порядка), для чего введем фиксированный набор блочных функций перехода, отдельную функцию в котором определим как ф$'т, где i — номер функции в наборе; к — значение, определяющее порядок клеточного автомата; т — длина блока разбиения. Кроме того, для всех возможных значений т будем использовать последовательность разбиений решетки на блоки вида S [ 0 то/2]. Тогда математическая модель блочного клеточного автомата к- го порядка примет вид С А = (N, ф1*’"1). Пространство координат Z" было опущено, так как рассматриваются только одномерные блочные клеточные автоматы.

Набор правил развития блочных клеточных автоматов, на который ссылается данная математическая модель, вынесен в приложение 2.

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

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

Таблица 4.1

Семейства базисов Декоррелирующих клеточных преобразований (А 0,45)

у.

Семейство

Мощность

Подсемейство

Мощность

семейства

подсемейства

1

S«8,^2>,B,)

84

  • ?|:0,45;0,75((8, V»!'").Bl)
  • 5j4;o,43;0,75({8, Ip,2), B2) ^4;0,45;0,8б((®> ^2 )> B;j)

0

2

?«8,^'2>,В2)

1584

85

3

?«8,я/ф2),В:1)

219501

67

4

?«8,^'2),B.t)

77732

^'4;0,45;0,8o({8>^i- )|8j)

111

5

?«8,^'2>,в.,)

247180

^4:0,4f>:0,8o((8> Ф A ).B-,)

481

6

?«8, я/.2,2), В,,)

1262

^*4:0,45:0,85 №> )> ®»)

0

7

?((wf).Bn)

1020

^4:0,45:0,85 №> )>Вц)

1

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

Было сделано предположение, что причиной появления подобных базисов в построенных семействах является слишком малое значение коэффициента Л. Данное значение было увеличено до 0,51. и для семейства ?((8, ф2'2). ВГ)) из табл. 4.1, содержащего наибольшее количество элементов, было сформировано подсемейство ?,.() 51 0 85 ((8,ф22), В5). Однако в данном подсемействе, мощность которого, равная 473, сопоставима с мощностью подсемейства ?J0 45.0 85({8, ?ф12),Вв), по-прежнему остались базисы, декоррелирующие преобразования на основе которых не обладают должной способностью к разделению элементов данных на частотные составляющие.

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

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

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

Пример «плохого» преобразования

Рис. 4.1. Пример «плохого» преобразования

Таблица 4.2

Семейства базисов декоррелирующих клеточных преобразований (0,15 ^ А ^ 0,25)

Семейство

Мощность

Подсемейство

Мощность

семейства

подсемейства

1

S«8,^’2),B2)

1355

:0,8Г>({8> В2)

Si

1

2

S«8,^2),B2)

Е(<8,ф,В3)

1277

?«*

;о,85((8,Й2),В2)

s2

1

3

229995

? 1:0,2"

:0.8.г>({8, *Лд'2), В.ч)

s.t

14

4

Е«8,^),В,)

80968

^4,0,20,0,85((8» Фщ }, В.})

s,

8

5

?«8,^j2>,B,)

94502

S .1:0,2;

:0,8Г>({8> ’Фй )>®4)

s5

11

6

Е«8,^’2),В5) Е« 8,^'2),в<4

230992

,о,85«8,^2>,ВГ1)

So

213

7

77505

^4,0,20,0,85({8, Ф{ ), Во)

s-

33

8

S(<8,^2),B7)

219092

,0,8Г.({8,^2;2),В7)

S*

216

9

Е«8,^),В„)

739

?.1:0,25

0,8Г)((8, V*15 >>Вц)

s.,

2

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

В табл. 4.2 приведены количественные характеристики непустых семейств базисов декоррелирующих клеточных преобразований, построенных для значения А, находящегося в интервале [0,15;0,25], с использованием динамики блочного клеточного автомата 2-го порядка.

На рис. 4.2 представлена гистограмма усредненных значений мощности семейств ортогональных базисов декоррелирующих клеточных преобразований, полученных для множеств базисных коэффициентов Вj, j - 2,11, соответствующих клеточному автомату 2-го порядка. Множества, соответствующие клеточным автоматам 2-го и 3-го порядков, взяты не были, так как в этом случае количество возможных начальных состояний решетки будет другим, кроме того, базисы на основе клеточных автоматов 3-го порядка строились, главным образом, с помощью кромексровского произведения, как это будет рассмотрено в следующем пункте.

На рис. 4.3, в свою очередь, представлена гистограмма усредненных значений мощности подсемейств ортогональных базисов декоррелирующих клеточных преобразований вида 15<л<0 25.0 85({8,

^>,ВД j - 2ДТ.

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

Усредненная мощность семейств базисов декоррелирующих клеточных

Рис. 4.2. Усредненная мощность семейств базисов декоррелирующих клеточных

11 реобразований

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

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

сио для множеств базисных коэффициентов Вг, { — 1, —3/4, 3/4.1}

и В- {— 3/2, — 1,1,3/2}. Напрашивается вывод, что лучше всего для получения ортогональных базисов декоррелирующих клеточных преобразований подходят симметричные множества, так как непустые подсемейства базисов были получены для каждого из рассмотренных множеств данного типа, в то время как для некоторых асимметричных множеств и множеств, симметричных относительно нуля, не удалось получить ни одного базиса, удовлетворяющего заданным параметрам.

В дальнейшем для упрощения изложения построенные подсемейства базисов г 1,9, будем называть семействами.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >