Устройство для ассоциативного сжатия информации

 

УСТРОЙСТВО ДЛЯ АССОЦИАТИВНОГО СЖАТИЯ ИНФОРМАЦИИ, содержащее на передающей стороне аналого-цифровой преобразователь, блок буферной памяти, выходы которого подключены к первым информационным входам соответствующих первых умножителей, выкоды которых подключены к соответствующим информационным входам первого сумматора, выход первого сумматора подключен к первому входу вычитателя , кодер, выход которого подключен к каналу связи, синхронизатор , первый, второй, третий, четвертки и пятый выходы которого подключенй соответственно к синхронизирующим входам блока буферной памяти , первым умножителям первого сумматора , кодера и аналого-цифрового преобразователя, на приемной стороне декодер, информационный вход которого подключен к каналу связи, блок буферной памяти, выходы которого подключены к первым информационным входам соответствующих умножителей , выходы которых подключены к соответствукяцим первым информационгшм входам сумматора, выход сумматора подключен к выходу устройства, регистр памяти, выходы которого подключены к вторым информационным входам соответствующих умножителей, синхронизатор, первый, второй, третий , четвертый и пятый выходы которого подключены соответственно к синхронизирующим входам блока буферной памяти, декодеру, регистру памяти, умножителям и сумматору, отличающееся тем, что, с целью повышения информативности устройства , в него введены на передающей стороне вторые умножители, второй и третий сумматоры, ключи, нормализатор , пороговый элемент, блок ключей , вход аналого-цифрового преобразователя является входс 1 устройства, выход аналого-цифрового преобразователя подключен к второму входу вычитателя и объединенным первым информационным входам вторых умножителей , вторые информационные входы которых подключены к соответствукнцим выходам блока буферной памяти, выходы вторых умножителей подключены через соответствующие вторые сумматоры к вторым информационным входам первых умножителей и первым -входам блока ключей, выход которого подключен к первому информационному входу кодера, выход вычитателя подключен через нормализатор к информационным входам первого и второго ключа и через третий сумматор к входу порогового элемента, первый выход которого подключен к второму входу блока ключей , второй выход порогового элемента подключен к управляющим входам первого и второго ключа и третьему входу блока ключей, выход первого ключа подключен к второму информаци-, онному входу кодера, выход второго ключа подключен к информационному входу блока буферной памяти, шестой, .седьмой и восьмой выходы синхрониза

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

А (19) (1!) 3(51) С 08 С 19/28

ОПИСАНИЕ ИЗОБРЕТЕНИЯ н вто сномм св ктильств

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬПИЙ (21) 3608036/18-24 (22) 21.06.83 (46) 23.10.84. Бюл. Ф 39 (72) B.A. Демехин, А.Ф. Зарицкий, Л.П. Кушнаренко и А.А. Хрупало (53) 621.398 (088.8) (56) 1. Авторское свицетельство СССР

9 324638, кл. G 06 J 1/02, 1971.

2. Прэтт У. Цифровая обработка изображений. Пер. с англ. Кн. 2.

М., "Мир", 1982, с. 663-664.

3. Авторское свидетельство СССР

Р 405125, кл. G 08 С 15/00, 1972.

4. Прэтт У. Цифровая обработка изображений. Пер. с англ. Кн. 2.

М., "Мир", 1982, с. 680 (прототип) .

5. Глазман И.М., Любич (0.И. Конечномерный линейный анализ. М., "Наука", 1969, с. 476. (54)(57) УСТРОЙСТВО ДЛЯ АССОЦИАТИВНОГО СЖАТИЯ ИНФОРМАЦИИ, содержащее на передающей стороне аналого-цифровой преобразователь, блок буферной памяти, выходы которого подключены к первым информационным входам соответствующих первых умножителей, выходы которых подключены к соответствующим информационным входам первого сумматора, выход первого сумматора подключен к первому входу вычитателя, кодер, выход которого подключен к каналу связи, синхронизатор, первый, второй, третий, четвертйй и пятый выходы которого подключенй соответственно к синхронизирующим входам блока буферной памяти, первым умножителям первого сумматора, кодера и аналого-цифрового преобразователя, на приемной стороне декодер, информационный вход которого подключен к каналу связи, блок буферной памяти, выходы которого подключены к первым информационным входам соответствующих умножителей, выходы которых подключены к соответствующим первым информационйьпч входам сумматора, выход сумматора подключен к выходу устройства, регистр памяти, выходы которого подключены к вторым информационным входам соответствующих умножителей, синхронизатор, первый, второй, третий, четвертый и пятый выходы которого подключены соответственно к синхронизирующим входам блока буферной памяти, декодеру, регистру памяти, умножителям и сумматору, о т л и ч а ю щ е е с я тем, что, с целью повышения информативности устройства, в него введены на передающей стороне вторые умножители, второй и третий сумматоры, ключи, нормализатор, пороговый элемент, блок клю- Pg чей, вход аналого-цифрового преобразователя является входом устройства, выход аналого-цифрового преобразователя подключен к второму входу вычитателя и объединенным первым информационным входам вторых умножи- Я телей, вторые информационные входы которых подключены к соответствующим выходам блока буферной памяти, выходы вторых умножителей подключены через соответствующие вторые сумма- торы к вторым информационным входам первых умножителей и первым .входам блока ключей, выход которого подключен к первому информационному входу кодера, выход вычитателя подключен через нормализатор r, информационным входам первого и второго ключа и через третий сумматор к входу порогового элемента, первый выход которого подключен к второму входу блока ключей, второй выход порогового элемента подключен к управляющим входам первого и второго ключа и третьему входу блока ключей, выход первого ключа подключен к второму информаци, онному входу кодера, выход второго ключа подключен к информационному входу блока буферной памяти, шестой, .седьмой и socbMoA выходы синхрониза1120390

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

Изобретение относится к области телемеханики и может быть использовано в технике связи, телеметрии, а также кибернетике.

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

Недостатком устройства является невысокая степень сжатия информации вследствие отсутствия учета пространственно-временных корреляционных связей в исследовательности передаваемых блоков информации, например кадров радиолокационной информации с индикатором РЛС или телевизионных изображений.

Известны устройства сжатия информации изображений с пополнением кадров, в которых используется межкадровая информация. Принцип их построения основан на том, что передача большинства блоков информации сопровождается относительно небольшими изменениями в деталях изображения от одного кадра к другому и, если передавать одни лишь изменения в v.çîápàжении по отношению к некоторому первоначально выбранному кадру, то можно получить существенный выигрыш в сжатии информации. Такое устройство содержит блок запоминания кадра, селекторный переключатель, блок вычитания кадров, адресный генератор, логический блок и буферный наполниТель кадров. В данном устройстве для каждого последующего кадра яркость элементов сравнивается с яркостями соответствующих элементов запомненного образца изображения. Голи обнаруживается значительное расхождение, то на месте соответствующего элемен та образца прежнее значение яркости заменяется новым и поступает в буфер ный накопитель для передачи в канал связи (2) . первому входу формирователя импульсов, первому входу ключа и второму информационному входу сумматора, выход сумматора подключен к второму входу формирователя импульсов, выход которого подключен к второму входу ключа, выход ключа подключен к информационному входу блока буферной:памяти.

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

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

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

35 изображения (строки), так и предшествующим им строкам. Такое предсказание на основе пространственновременного более полного учета сведений позволяет улучшить качество ,)О изображений как для объективного контроля на основе уменьшения среднеквадратической ошибки, так и для визуального наблюдения среднеквадратической ошибки (3) .

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

xoT< рого соединены с первым входом группы умножителей, вторые входы руины умножителей подключеHH K cooT ветствующим выходам регистра памяти коэффициентов, первый выход которого и выходы группы умножителей подключены к входам другого сумматора, вых"ц которого соединен с вторым входом первого сумматора и вторьм входом блока вычитания, вход которого явля- 10 ется входом устройства, а ныходом ян. ляется выход блока кодирования, котоpbli. подключен к выходу квантователя; на приемной стороне устройство содержит сумматор, подключенный ко входам

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

Целью изобретения является повышение информативности устройства.

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

На фиг.. 1 и 2 изображены блок-ñõåмы устройства для ассоциативного сжатия информации соответственно пере- . дающей и приемной стороны.

Устройство содержит на передающей стороне блок 1 буферной памяти, умножители 2 и 3, вычитатель 4, аналого-цифровой преобразователь 5, кодер 6, сумматоры 7-9, блок 10 ключей, ключи 11 и 12, нормалиэатор 13, пороговый элемент 14, синхронизатор 15, на приемной стороне декодер 1á, ключ 17, регистр 18 памяти, формирователь 19 импульсов, блок 20 буферной памяти, умножители 21, сумматор 22, синхронизатор 23.

Устройство работает следующим образом.

1120390

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

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

Поскольку коэффициенты формируются адаптивно — по ассоциативным базисным функциям, которые наиболее соответствуют характеру сжимаемой информации (по сравнению с системами Фурье, Хаара и т.д.), и поскольку последовательность передаваемых кадров изображения сильно коррелирована (R=O 93-0,96), для представления очередного кадра в ассоциативном базисе необходимо всего 6-10 коэффициентов при точности 2-3Ъ. Для сравнения при достижении той же точности того же изображения необходимо порядка 600-2000 коэффициентов

Фурье. Это позволяет существенно повысить сжатие информации. Формирова- ние новых ассоциаций при существенных изменениях в последовательности кадров производится путем "выталкивания" из буфера памяти старых ассоциативных остатков у; информации и формирования новых по последним входным кадрам. При этом на время адаптация к изменениям B последователь . ности кадров телевизионного изображе- 45 ния с коэффициентами будут передаваться и различия между изображениями и их линейной ассоциацией. Это позволяет расширить возможности устройства при работе с разнохарактерными изображениями, т.е. последовательностями изображений с разными уровнями предсказуемости (коэффициентами авторегрессии) . При этом не требуется рассчитывать каждый раз необходимое число коэффициентов или глубину памяти и жестко обуславливать их величины, так как это происходит адаптивно к входной последовательности.

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

Рассмотрим принципы сжатия информации на основе ассоциативного преобразования информации и техническую реализацию устройства, построен-. ного на базе этих гринципов. Изображение будем представлять либо в векторной форме, либо в виде набора векToPoB cTPOK Sf S » S »,» S1(($В =(У1 У2 ° ° ° ° Ъг ° ° ° . 0.Мг>, ответствующих полному кадру разме ром N, N, элементов, либо в виде набора векторов-кадров иэображений

1 1 1

S, » »$2» ° ° » $МФ, . °, $И1, где каждый вектор $2„, включает в себя построчI

1 ную развертку одного кадра $« =($1, ° - S 1 ° 2 $ "» ) (Ui «0» ° »

0Мг 0 - 2 "2»г. - Ж 1; д (щ S М, ° Я . В первом случае имеет место ассоциативное сжатие иэображений по межстрочной информации (внутри кадра), во втором случае — ассоциативное сжатие по информации взаимосвязей между кадрами. Принципиальных отличий между ними нет, в аппаратурном исполнении во втором случае необходим больший объем памяти для заполнения нескольких кадров.

В дальнейшем для удобства анализа под векторами $, S, ..., $» ... будем понимать вектора-столбцы с нумерацией, принятой в векторной алгебре.

Каждый следующий кадр изображения

$k (строки $1 ) на последовательности

1, 2, ..., k ..., N кадров можно рассматривать как элемент некоторого функционального пространства L noстроенного из набора базисных некто-, ров, образованных с помощью оператора проектирования Р из совокупности предыдущих S,S,,..., $ 1 каРРов, образующих множество векторов R..

Оператор проектирования Р определяется симметричной матрицей со следующими свойствами

1. S PS $6R

2. s (1-p) s s e acR л И где S — вектор изображения в виде ортогональной проекции вектора S на пространство L, т.е. sJ.L;

1120390

$ — ортогональная проекция вектора S íà L т.е. на ортогональное дополнение пространства (1-Р) — оператор ортогонального проектирования на пространство L, построенное в данном случае из набора всех векторов в R ортогональн ных L.

Таким образом, последовательность кадров иэображений (S;), i=1,2,...,k

k)N можно представить в виде матри- 16 цы Z и вектор-столбцами S<еК, образующими пространство„ ).. Представление каждого кадра S=-S+S в.этом про/% странстве однозначно, при этом S можно определить исходя иэ требова- 15 ния ортогональности всем столбцам матрицы Z лТ

$ Е 0

Решение матричного уравнения для проекции кадра Sт определяется выражением S 7Т(! - ZZ*), (4) где Z* - матрица псевдообратная Z т. е.

Z*=1im(Z Е+с 1) Z lie Z (ZZ +б 1) т.тт1-»

60 согласно определению (5);

V - произвольный вектор, размерность которого соответствует размерности кадра S.

Вследствие свойств симметрии ZZ* и свойств операции псевдообращения, исходя из (4) можно записать

35 тл т Т Я

S S-S (1-ZZ*)V=S S=V (1 †Z)V

Полагая 7$, получим

$ SS (1-ZZ*) S S (1 — ZZ*) S

Т Т Я i

40 или

$ (1-ZZ*) Z

Так как S определяется однознач- 45 но, то (I-Р) I-ZZ*; P=ZZ">

Таким образом, проекционная матрица оператора проектирования Р симмет 50 .Рична и идемпотентна.

В более общем случае она необязательно должна быть симметрична !5) .

Для конструктивного использования опеРатоРа оРтогонального проектирования при построении устройств для сжатия информации можно испольэовать любую процедуру псевдообращения, например, исходя из теоремы ГревилЛяе если z матрица со столбцами (кад- 60 рами) S», S,, ..., Sg РазДелена на блоки (Ек»; $»), то

Е„Е* Е Е* (I S„= > > . ? >l и веитав

-k.l к-» к (1-Е», „) $» нУлевой! если (I-Z„, Z, ) $„-0, то формула (б) упрощается

zzk Z»k =- Ек. » Е k.»

Для обоих случаев (I- Е „. » Е"„,1&к 5 к (1- Е к-»Е y-»)

)-Е„ "„.(I-Z..- ) (7)

Сравнивая (7) с выражением (5) для оператора P ортогонального проектиI рования, видно, что оператор (1-Е»Е ) в {7), построенный на базе всей последовательности векторов-кадров

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

° . ° ° $к.» ° $» ° $ > ° ° ° > $к-г " т.д. до $» включительно. Таким образом, оператор ортогонального проектирования Р можно формировать адаптивно, по мере поступления S -ro вектора изображения.

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

S„, ..., S». Поэтому каждый вновь поступающий вектор-кадр может быть ассоциирован с любь»» из предыдущих и их линейной комбинацией с помощью оператора P.

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

Р» > Р„ P„.<. .Это означает, что очередной вектор изображения S» окажется лежащим в предыдущем подлространстве низшей размеренности, т.е. ассоциируется линейной комбинацией предыдущих. В данном случае нет смысЛа передавать все иэображение или даже те его участки, которые изменились.

Достаточно передавать только k-1 коэффициентов ассоциаций после операции ортогонального проектирования вместо (N» xN, ) отсчетов иэображения.

Причем следует отметить, что в слу9 °

1120390

l лт

S»: 8»» т" « КПэ Н (8) 20 (9) к- » к» к

"(10)

И5,Ц»

)( л к

Б

)(5 И

5 «б»

30 (12) т

5» 5 -(6,5 )5»

)!

Мк 8к ° к«1 °

1к NK., S„«0 (14) т 5к(к-») к-» т

М! 2"„.„э,)) (15) чае использования какого-либо другого не ассоциативного преобразования для сжатия данных, например, Фурье, Хаара, т.е. систем, в которых базисные функции не согласованы с переда,ваемыми изображениями, число коэффИ, циентов возрастает приблизительно в 10 раэ при достижении одного порядка точности.

Ассоциативное преобразование, используемое для сжатия информаций, не- 1О посредственно связано с процедурой оптимального предсказания последующего вектора-кадра иэображения по серии предыдущих т.«1, 2, ..., *-1

Уравнение (7) можно преобразовать к виду (11) и рекурсия начинается с « »» «1. После

k-кратного применения рекурентной формулы оператор ортогонального проектирования P будет равен Р =Х-Ф»(. Этот же алгоритм можно вывести из формулы ортогонализации Сонина-Шмидта

Если ввести обозначение

6 5т (11)

)(5.))2 " » . 4О

I причем SK «»Р„S»» то уравнения (10) непосредственно приводят к (B) и (9) .

Таким образом, процесс ассоциатив- 5 ного сжатия информации задается в виде некоторого линейного преобразования (матрицы) М где S — очередной входной векторК кадр;

VK - выходной вектор, предна зна-; ченный для передачи по каналам связи °

Vg может быть либо нулевым, если сжатие по ассоциации наиболее эффективно, либо отличным от нуля в противном случае. Возникает проблема, фО как определить поправку к Мк, так, чтобы новое значение Мк»» было оптимальным не только в отношении любых предыдущих пар взаимосвязей между кадрами в поступившей последователь-: 65 ности S(, S,, ..., S, но и в отношении последйих, новых пар связей (ассоциаций), связывающих последний передаваемый кадр с остальными (фиг. 2) 1

Очевидно, что новое оптимальное значение Мм»» будет являться функцией от предыдущего оптимального значения N и новых векторов-кадров. В

K такой рекурентной форме эта проблема по существу является проблемой оптимального предсказания УК. действительно, если S»; — очередной входной вектор-кадр, то М S < будет оценкой будущего вектор-кадра VK по их запомненной последовательности $V Ä

1, „1„... 1,; . 2 » 3 » » к-f к

При этом ошибка предсказания d K запишется в виде

Ьk = (ЧМ-М„-8)

Вводя коррекцию ошибки минимизирующего hK в виде, например, векто,ра коэффициентов коррекции Ст, получим раэностное матричное управление для определения оптимального М

MK «М„, + (Ч„-Ик» 8„) С„ т

Решение этого уравнения исходя из теоремы Гревилля описывается следующим образом м„*м„» „(м„,;uД)(»", " ")= <1з>

С„

»тк»Е"„.»»(Ок-"»: » T ê-»5w)0к йк»+(Vк-M„»S„) Ст, где запоминаемая матрица U образована векторами V«V<, ...,7 из входной последовательности векторов-кадров 8», S, ..., Як с соответствующими блоками )Чк,; Ч„)иэ k векторовстолбЦов УК . В том слУчае, если передаваемый кадр Я.к ассоциирован линейной комбинацией предыдущих k-1 кадров изображения, то вектор ЧК равен кулю, что соответствует нулевой ошибке предсказания

Поэтому по каналам связи достаточно передавать только вектор коэффит циентов ассоциации C определяемый по Р< в (б) по которому при имеющейся на приемной стороне матрице предыдущих (переданных). кадров изображений Z<» с помощью оператора предсказания М„ „

1120390 (22) (16) 10 (17) т

„ мк.. +(ч,„-м„,$„)

К

Емк»,, еслибы„/ C если (3к = Е 40 (20) ь„-O S,,q,-1, ь,-б, т »ьк (P 43

lE t,. ll" (21)

50 одинакового на передающей и приемной сторонах, восстанавливается по ассоциации согласно (14) изображение кадра Sк. В противном случае передается ошибка предсказания (к "к

f и коэффициенты С„, определяемые по

Р„в (6) При этом оператор предсказания по ассоциациям МК корректируется на приемной и передающей сторонах в соответствии с (12)

М к М к-3 (ук Мк.,б»15„(2 к-31 к 3(1 (18 )

11 .„$„Ц ) Действительно, поскольку ll Z3 S>ll > О, то это уравнение. может удовлетворяться только при (vk™к4$к) =О, что и эк-; 25

;вивалентно (14) . Представляя (14) в (13), получим Мк=ИК(. Если обозначить с учетом (17) Зк=(I z> 1 z к 1 ) sk 9y „sg (19) $0 то выражение (16) при условии bк =О будет соответствовать линейной зависимости векторов (S;), i=1,k в матрице Ек. Таким образом, для оператора предсказания.по ассоциациям И)(можно записать где Š— требуемый порог точности представления очередного кадра изображения, задаваемый допустимой ошибкой передачи информации по каналам 45 связи (с + О) .

При этом

С точки зрения конструктивной при разработке аппаратуры сжатия информации вместо уравнения (21) целесооб. разнее ошибку предсказания (Ь;, i=-1,k определять исходя из процедуры

Сонина-Шмидта (10). В этом случае с учетом обозначений оценки 7;М, „$; на i-ом цикле передачи очередного 60

S, -го кадра изображения и ошибки а", =Ч; -V можно исключить трудоемкий расчет матричного оператора М в выражении (20). Умножая (20) на Мк, пере ставляя члены и меняя индексы, полу-,. б5 чим процедуру Сонина-Шмидта (10) в виде где (, ) — операция скалярного произведения векторов. Таким образом, можно запомнить на передающем и при- . емном пункте и передавать только ошибки предсказания Ь<, 3.=1,2,..., N на что требуется уже в два раза меньше двоичных разрядов, чем передача полных кадров изображений S S

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

С каждьм шагом i вместе с передачей ошибки А; степень оператора предсказания М возрастает до того момента, 1 пока не станет равной порядку коррелированности (авторегрессии) процесса из последовательности кадров (S;"1

i-= 1,N изображения. После этого ошибками; становится меньше заданной (E)0) и передается только вектор коэффициентов СК ассоциативного преобразования, по которым восстанавливается все исходное иэображение. Таким образом, математический аппарат, используемый оператором.ортогонального проектирования Р, позволяет построить конструктивные с точки зрения технической реализации процедуры ассоциативного сжатия информации (изображений). Причем процедуры (8), (9) оказались непосредственно связанными с оператором оптимального предсказания (20) и интеративной схемой ортогонализации векторов СонинаШмидта (22). На основе предложенного математического аппарата можно разрабатывать высокоэффективные адаптивные системы ассоциативного сжатия информации для передачи по каналам связи.

Рассмотрим технические принципы построения таких систем сжатия информации.

Последовательность основных операций, выполняемых цифровым устройством для ассоциативного сжатия информации, основана на процедуре (22), полученной из выражений (14-17, 20, 21), и включает в себя следующие операции, соответствующие: A - передающей стороне, Б — приемнбй стороне.

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

S)% S3 %S3 9 7 S 1 j $Ц

1120390

1А. Поступает первый кадр изображения S,, который запоминается в виде 5» нормируется по энергии

V, кодируется и передается по

Ца,й каналу связи (КС) N-разрядным кодом

4 S(, 4(-" V(, V) — в КС

1 Б. Переданный сигнал при нимается, декодируется и поступает к потребителю, одновременно запоминается кс чВ„Ь

Б

2А. Поступивший второй кадр изображения S умножают на нормированНЫй преднцущий кадр Ч1 покоординатНЬ (скалярно}, а координаты суммируются. Полученное скалярное произведение в виде коэффициента предсказания (ассоциации) С (умножают на запоминаемый в g< в вйде V< первый кадр и затем вычитают из поступившего второго кадра изображения. ПолученHBR разность нормируется по энергии

Ьг V В том случае, если сумма квадратов компонент вектора остатка изображения V, меньше заданного по- рога точности 0

А1

Если 1)ЧД 6Г„, то С „KC нет

V КС и С 1 КС

kD kD

2Б. На приемной стороне сигналы декодируются. В том случае, если принят только один коэффициент Сг„ исходное изображение S восстанавливается по предыдущему запомненному V Sг V) Сг . Если принят коэффициент вместе с остатком V,, то запоминается, а исходное йзображение восстанавливается путем s, =v„c +

Vg .

ЗА. Следующий кадр изображения

S, аналогично 2А ассоциируется с каждым из запомненных U и V, в ðåзультате чего получаются коэффициенты предсказания С 1 и С . Далее вычисляется векторная ошибка предсказания Ь, между исходным изображением

S„a линейной. комбинацией ассоциаций v и

U,.OøHáêà нормируется по энергии Ь, v, и сравнивается с порогом „1)Ч,1 г 1 „.

При превышении порога в кс передаются кодированные значения коэффициентов С 1 и С и вектора-остатка V, двоичным "/2-разрядным кодом. В про-тивном случае в КС передаются только

НОды КОэффициентОв С и с12

3 3 ) э г ) А

С 5i с,7, з "> 11

kD

1 нет kD kD

Ч - КС И С, Сг — +КС

Если

ЗБ. На приемной стороне сигналы декодируются. В том случае, если

1О поступили одни только коэффициенты, то исходный кадр иэображения восста навливается по запомненным предыдущим ассоциациям Чг и Ч, (15 г .р Ц

Если поступил и вектор V то восстанавливается

S3 C V! C v2 V3 °

В общем случае на любом этапе передачи k-го кадра изображения происходит следующее.

КА. Иа передающей стороне

Ф-1 — Е. (S„,V. ) V„ ., rpe С, =

Л=1

=(Б„,v, ) к

gk U<

kD 1"К )1

ЗО Если ВЦ г,, то C — ь КС нет

kD kD

U — -ъ KC и С YC

З5 КБ. Иа приемной стороне - если поступают одни коэффициенты Ck,, то после декодирования -4

Б„= ",> C U

Если вместе с коэффициентами С „ передачи и вектор Ч„, то после декодирования

К-1

s -" с:v+v

45 К 1, к

Рассмотрим более подробно работу устройства.

В начальном состоянии все регистры сумматоров, умножителей и. блоков буферной памяти обнулены. То же самое касается и приемной стороны.

Вследствие этого при поступлении первого кадра информации на вход устройства чере" аналого-цифровой преобразователь вектор-кадр умножится умножителями 2 на нулевые векторы из блока 1 буферной памяти. В Результате этого на выходных регистрах группы сумматоров 8 и на выходе сумматора 7 также установятся нуле6() вые значения сигналов. Поэтому при

° вычитаний из входного векторакадра S(нулевого вектора на выходе вычитателя 4 появится вектор-кадр S, который пронумеруется нормализатором 13 и через открытые ключи 12 и

16

11 попадет соответственно но входной регистр кодера 6 и блока 1 буферной памяти. Вследствие того, что сумма квадратов компонент изображения, образованная в квадративном сумматоре 9, будет существенно выше порога E потенциал несовпадения с второго выхода порогового элемента

14 откроет ключи 10-12 ° Кодер 6 кодирует входную информацию (нуленые коэффициенты и первое изображение) 10 и передает в КС.

В том случае, когда в блоке 1 буферной памяти уже имеется информация о последовательности кадров, очередной входной вектор-. кадр St 15 умножится на запомненные векторыассоциации изображений в виде их остатков (невязок) Ч1, Ч,, ..., Ч„ умножителями 2, и полученные свертки покоординатно просуммируются сум- 20 маторами 8. При этом на.выходных регистрах сумматоров фиксируется величины коэффициентов ассоциаций

С1, =(S„,Ч ), з 1, 2. ..,, k-1. Исходное иэображение S< восстанавливается по коэффициентам С„ путем суммирования в сумматоре 7 и умножения векторов-ассоциаций (ЧД -1, k-1 из

:блока 1 буферной памяти на соответст вующие коэффициенты С „ от сумматоров

8 с помощью умножителей 3. Восстанов-30 ленный кадр S поступает на входной

I ,регистр вычитателя 4, на втором входном регистре которого находится исходный кадр S ., 35

Разность S-Б квадра инно суммиру:ется покоординатно сумматором 9. Одновременно эта же разность нормиру ется нормализатором 13 по энергии и поступает на информационные входы клю- 40 чей 1.2 и 11. Величина несоответствия исходного и ассоциированного кадров сравнивается с допустимой величиной отличий (искажений) с помощью порогового элемента 14. При непревышении 45 порога допуска с первого выхода порогового элемента на управляющий вход блока 10 ключей поступает импульс разрешения, и информация о коэффициентах С ассоциации поступает с выходных регистров сумматоров 8 на первый вход кодера -б, в котором кодируется и передается в КС. В случае превышения допуска импульс превышения с второго выхода порогоВого элемента 14 открывает нсе три ключа 1012. При этом наряду с -коэффициентами

С>, на второй вход кодера б через ключ 12 поступает вектор V - остаток ассоциации. В кодере б последний кодируется и передается н КС.после сообщения о коэффициентах С1„ . Одновременно этот же вектор поступает от нормалиэатора 13 через ключ 11 на вход блока 1 буферной памяти. При этом 1 k-й кадр V, "выталкивает" 65

1t-é кадр, информация о котором теря ется. Остальные кадры меняют ассоциацию на 1. Таким образом, обновляется информация н блоке 1 буферной памяти. Синхронизатор 15 обеспечинает синхронизм работы устройства таким образом, чтобы не нарушалась последовательность выполнения операций 1А-KA.

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

18 памяти коэффициентон и на вектор vz . В случае отсутствия вектора

Vk c второго выхода декодера снимаются нулевые отсчеты, по которым

Формирователь 19 импульсов блокируется до тех пор, пока не появятся нулевые отсчеты на выходе декодера 16. При этом ключ 17 находится в закрытом состоянии. Векторы V

i=1, k-1, запомненные ранее в блоке 1 буферной памяти, умножаются умножителями 21 на коэффициенты из регистра 18 памяти. После этого результаты суммируются сумматором 22, на выходе которого и образуется переданаемое изображение !

S K, С „; V;+V„, где Ч„=о

1 =

После появления информации на выходе сумматора 22 с помощью формирователя 19 импульсов формируется импульс разрешения записи в том случае, если формирователь не блокиронан. При появлении вектора Ч„ /О он суммируется на сумматоре,22 вместе с линейной комбинацией .К С V; и, так как в этом случае Формирователь

19 импульсов не блокируется, то по наличию информации на выходе сумматора 22 импульс разрешения с выхода формирователя открывает ключ 17, и вектор V< c выходного регистра декодера записывается в блок 20 буферной памяти. Хранение информации в блоке 20 буферной памяти организу.ется аналогично, как и на передающей стороне. Синхронизатор 23 обеспечивает синхронизм работы устройства приемной части таким образом, что не нарушается последовательность операций 1Б-КБ.

Таким образом, введение новых блоков и связей позволило обеспечить адаптивный ассоциативный процесс сжатия информации. Это привело к повышению степени сжатия информации. Действительно, если по данным (4) удельное сжатие достигает 1 дв.ед. на элемент изображения при нормированной среднеквадратической ошибке 2Ф. при передаче последовательности кадров подвижного изображения (диктора) в виде матриц из 256х256 элементов, 1120390

18 17 разбитых на блоки размером 16х16 эле. ментом 6-разрядным кодом, то с помощью предложенного изобретения возможно достижение степени сжатия информации 0,0012...0,6 дв.ед. на элемент при тех же условиях. Пусть сред- 5 няя продолжительность динамики изменения иэображения (без его смены) составляет 5 с при коэффициенте межкадровой корреляции k=0,96 и частоте кадров 25 Гц. В этом случае необходи-10 ма передача 125 кадров по 65,536х8 единиц каждый, т.е. всего 6,5i .

10 дв. ед. на 8,2 ° 106 элементов иЗображения, Ва время адаптации устройства, т.е. для- Формирования 15 ассоциативного базиса, необходимо запОмнить и передать объем информации, равный приблизительно первым десяти кадрам, т.е. 5,2.10 дв.ед., включая коэфФицйенты ассоциаций (по 10 коэффициентов на кадр). Пусть также скорость забывания (" обновления" ) ассоциативного базиса соответствует

2 кадрам в секунду. При этом необходима передача корректирующей информа- 25 цим объемом 5,2 ° 10 дв.ед. Практичес кн эта величина может быть в 2 раза меньше, так как передается не сам сигнал, а разность 4"-разрядным кодом. Поэтому всего необходимо

5,215, 2 106

1 —иэображения, а для передачи оставшИхся 105 кадров необходимо 105,10,8

8,4 .10 дв.ед. Таким образом, для передачи более 80% информации затра- З5 ты на кодирование составляют

8 4 ° 10 8 4 10 4 ; : а k

- 1,2 10 Д"д = 0,0012 д ед элем элем йа остальные 20% приходится

5 2 ° 10

5 2i10 - 4 дв,ед ь тЬт:я;ч в случае сильно подвижного объекта иэображения н 2 дв.ед./элем. прн ма- лоподвижном иэображении, так как в этом случае коррекции не потребуется, т.е. не надо передавать 2,6r .

« 10 дв.ед. На всю последователь6 ность кадров затраты кодирования составят

Ь

5 2 10 = 0 63

1У элем

0,32 дв.ед,/элем. при менее подвижном изображении.

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

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

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

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

16х16 элементов с 8-разрядным кодированием каждого элемента изображения.

Объем буферной памяти кадров (строк) изображения достаточен для передачи изображений с погрешностью 3% восьмиразрядным кодом. При этом удельные затраты на кодирование при передаче изображений после процесса адаптации составляют для 8-разрядных коэффициентов ассоциации 0,32 дв.ед./элем. изображения.

1120390

Подписное

Заказ 8422 Тираж 568

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г ° Ужгород, ул. Проектная, 4

Составитель В. Черединцев

Редактор Т. Кугрышева Техред М. Гергель Корректор А. Тяско