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

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

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

Если рассматривать клеточный автомат со значениями параметров |А| 4, N 8, т 2 и г = 4, то мощность пространства наборов входных параметров согласно приведенной формуле составит 288. Мощность соответствующего пространства базисов будет меньше указанной величины, поскольку работа алгоритма построения базиса декоррелирующего преобразования при некоторых наборах входных данных может заканчиваться неудачей, а также существуют отличные друг от друга наборы, приводящие к построению одного и того же базиса, но несмотря на это остается достаточно большой для полного исследования всех содержащихся в данном пространстве базисов.

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

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

Рассмотрим три случая.

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

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

Пусть /(ж) — одномерная дискретная функция, вектор значений которой есть F (/;)"-i- Область определения и область значений функции /(ж) обозначим Е {0,1,..., гп — 1} и D {0,1,...,/ — 1} соответственно.

Рассмотрим m — 1 пар соседних элементов, составляющих вектор F, для чего введем вектор Y (?Уг)^1 > элементы которого будут содержать разницу между значениями элементов каждой пары, т. е. Ух = |/i+i — fi. Будем считать, что между элементами /, и /i+1 наличествует пространственная избыточность, если у,/ maxD < d, где d — это заданное пороговое значение. Обозначим количество таких пар тп' и будем считать, что последовательность значений функции /(ж) обладает пространственной избыточностью, если выполняется условие пп!/(гп — 1) > е, где е — также некоторое пороговое значение. Анализ реальных цифровых изображений, в частности стандартного тестового набора, используемого для оценки эффективности методов сжатия цифровых изображений, который будет задействован позже, показывает, что значения due составляют 0,04...0,1 и 0,6...0,8 соответственно. На данные значения и будем ориентироваться при выборе одномерных функций, моделирующих последовательности (строки или столбцы) пикселей полутонового цифрового изображения, либо последовательности элементов одной из плоскостей непрерывно-тонового цифрового изображения в рассмотренных ранее цветовых моделях, и двумерных функций, моделирующих блоки элементов цифровых изображений.

После преобразования выбранной функции следует обратить внимание на то, что низкочастотные составляющие должны являться наиболее значимыми среди преобразованных элементов данных, кроме того, они должны быть приближены к среднему значению элементов исходной последовательности. Если вычислить математическое ожидание М[/(ж)| и разделить на него частотные составляющие с последующим округлением до ближайшего целого, то но количеству полученных ненулевых значений можно судить о количестве низкочастотных составляющих, в которых сосредотачивается большая часть энергии исходных данных. Либо можно ввести коэффициент Л, отличный от 1/2 и определяющий минимальное отношение элемента данных к М[/(х)], при котором этот элемент может считаться низкочастотной составляющей.

Отсутствие ненулевых значений позволит сделать вывод о том, что низкочастотных составляющих, значения которых превышают АМ[/(х)|, нет, таким образом, исследуемый базис относится ко второму или третьему случаю. Некоторые из низкочастотных составляющих могут быть приближены к локальным средним значениям элементов данных, т. е.математическим ожиданиям некоторых подпоследовательностей исходной последовательности значений. Для выявления таких составляющих делитель должен быть уменьшен вдвое, что приводит нас к итеративному процессу.

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