8.4.3. Непрерывные по времени источники и обобщения

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

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

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

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

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

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

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

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

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

а алфавит представления как множество

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

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

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

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

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

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

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

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

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

где

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

также может быть представлена через коэффициенты разложения Карунена — Лоэва 00

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

удовлетворяет равенству

Неравенство (8.4.20) обращается в равенство тогда и только тогда, когда процесс гауссовский. Предположим теперь, что процесс и (0 стационарный и его спектральная плотность равна 00

Тогда, полагая в соответствии теоремой Теплица для случая непрерывного времени (Бергер

[1971], теорема 4.5.4) находим, что

где определяется из равенства 00

Равенство в (8 4.23) достигается в том и только в том случае, если процесс гауссовский.

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

где определяется соотношением (8.24), часто служит основой для сравнения различных схем сжатия данных.

Пример. (Ограниченный по полосе гауссовский источник Для идеального ограниченного по полосе гауссовского источника с постоянной спектральной плотностью

скорость как функция погрешности определяется

Это классическая формула Шеннона [1948]. Легко видеть, что она задает также скорость как функцию погрешности для любого гауссовского источника средней мощности спектральная плотность которого постоянна в любом множестве частот, имеющем меру

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

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

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

Может показаться несколько странным, что, пользуясь квадратично-разностной мерой, мы собираемся кодировать е. логарифм интенсивности. Но существуют указания на то (Кэмпбелл и Робсон [1968] и Ван Несс и Боуман [1965]), что субъективная способность наблюдателя различать два поля интенсивностей зависит от различия между полями, преобразованными в соответствии с логарифмом интенсивности.

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

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

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

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

где

ортогональные (собственные) функции, являющиеся решениями интегрального уравнения

Каждое собственное число А, соответствующее собственной функции неотрицательно и удовлетворяет условию

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

и мера погрешности записывается

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

где удовлетворяет уравнению

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

Так как вычисление собственных чисел часто связано с определенными трудностями, то такая форма функции не очень удобна для применений. Перейдем к пределу при Обозначая

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

Это есть двумерное условие стационарности. Оно позволяет определить двумерную спектральную плотность соотношением

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

Применяя эту теорему к выражениям (8.4.39) и (8.4.40), находим

где определяется изуравнения 00 00

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

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

Определяя как полярные координаты, где

находим

где - функция Бесселя нуцевого порядка первого рода.

Так как величина

где

не зависит от то функции связаны преобразованием Ханкеля нулевого порядка.

Спектральная плотность телевизионных изображений довольно хорошо представляется функцией

которой соответствует

где когерентное расстояние поля (Сакрисон и Алгази [1971]).

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

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

означает выходной символ источника в момент времени. Вновь применим обычное разложение Карунена-Лозва

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

Скорость как функция погрешности дискретного по времени стационарного эргодического источника запишется

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

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

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

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

и соответствующую спектральную плотность

Закодируем последовательность в соответствии с квадратично-разностной мерой погрешности. Из (8.2.69) и (8.2.70) следует, что для достижения погрешности требуется скорость

где 0 удовлетворяет уравнению

Здесь измеряется в натах на выходной символ подысточника.

Напомним, что общая мера погрешности определяется соотношением

Следовательно, для достижения средней погрешности надо выбрать так, чтобы 00

Общая скорость, отнесенная к единице площади, равна

Отсюда находим

где выбрано, так, чтобы выполнялось равенство

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

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

где

Нэпомним, что в разложенш Карунена—Лоэва любые два коэффициента и и определяются соотношениями

Следовательно, корреляция запишется

Это значит, что

и для любых

Так как источник обладает гауссовской статистикой, то некоррелированные случайные величины независимы и различные последовательности коэффициентов разложения Карунена — Лоэва могут рассматриваться как независимые подысточники. Лемма 8.1.1 показывает, что верхняя граница, определяемая (8.4.65), является точной, так что

где выбирается удовлетворяющей соотношению

Переходя к пределу при с помощью (8.4.44) находим предельное значение скорости как функцию погрешности

где удовлетворяет соотношению

определяется согласно а

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