Способ кодирования-декодирования изображений и устройство для его осуществления

 

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

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

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

Известен ряд способов "сжатия-восстановления" изображений. Так например, адаптивная дифференциальная кодоимпульсная модуляция и методы кодирования с предсказанием [1] обеспечивают простую аппаратную реализацию системы для работы в реальном масштабе времени. Этот метод обеспечивает сжатие в 4-5 раз, но качество восстановления изображений существенно зависит (снижается) от уровня шумов в каналах связи.

Методы сжатия, основанные на ортогональных преобразованиях таких, как преобразования Фурье, Адамара, Каррунена [1] и др. устойчивы к импульсным и высокочастотным помехам каналам связи. Однако сжатие с хорошим качеством посредством этих методов достигается только для простых изображений и не содержит большого количества мелких деталей.

Для повышения качества восстанавливаемых изображений, сжатых с применением ортогональных преобразований, используется блочное кодирование [1] В этом случае сжатию подвергается не все изображение сразу, а его части, на которые оно разбивается (блоки), содержащие определенное (в частности, равное) количество пикселов. Такой способ широко используется при кодировании телевизионных изображений в коммерческих системах видеозаписи и телевизионного вещания, а также при создании компьютерных видеофильмов и положен в основу применяемых во многих странах стандартов сжатия изображений JPEG, MPEG.

Стандарт JPEG является наиболее распространенным методом сжатия и представляет собой следующую последовательность операций: а/ пием изображений в цифровой форме и его буферизация; б/ дискретное косинусное преобразование (Д.К.П.), при котором изображение разбивается на блоки и каждый блок подвергается упомянутой операции. Это операция требует большой вычислительной мощности, причем потери информации при этом не происходит. Д.К.П. представляет собой разновидность преобразования Фурье, имеет обратное преобразование. Смысл этой операции заключается в переходе от пространственного представления изображений к его спектральному представлению и наоборот. Отсекая наиболее высокочастотные элементы преобразованного изображения, можно в ту или иную сторону в зависимости от количества выбирать между качеством изображения (восстановленного) и степенью сжатия. Таким образом, Д.К.П. преобразует матрицу, представляющую исходное изображение, в совокупности матриц частотных коэффициентов. Высокочастотные элементы этих матриц могут быть огрублены или отброшены без особых потерь информации. Время, необходимое для вычисления каждого элемента матрицы Д.К.П. сильно зависит от ее размера, который JPEG рекомендует в виде элементарных матриц размером (8х8) элементов; в/ квантование. После операции Д.К.П. каждый блок изображения подвергается операции квантования, т.е. делится с последующим округлением на соответствующий элемент специальной матрицы квантования. Здесь происходит основная потеря информации за счет округления, при котором результат деления округляется до ближайшего целого с установленным числом двоичных разрядов. Матрица, полученная после квантования, в области высоких частот обычно оказывается заполненной нулями; г/ далее производится RLE-кодирование полученных матриц (кодирование повторов), при котором кодируются оставшиеся частотные коэффициенты. Коэффициенты каждой матрицы обходятся при этом зигзагообразно, нулевые промежутки кодируются также посредством стандартной программы RLE. Далее информация со всех блоков формируется в единый поток; д/ кодирование "энтропии". Поток, полученный при RLE-кодировании подвергается стандартному методу сжатия по Хаффмену или арифметическому кодированию; е/ при декодировании все происходит в строго обратном порядке, т.е. после декодирования по Хаффмену следует декодирование по программе RLE, затем восстановление матрицы Д.К.П. посредством обратного Д.К.П. наконец, сборка изображения из восстановленных блоков.

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

Альтернативой методам блочного кодирования с использованием ортогонального преобразования является сжатие изображений посредством адаптивного квантования векторов [4] В этом случае изображение также делится на блоки и набор пикселов в блоке описывается вектором. Адаптивное квантование векторов (А. К. В. ) обеспечивает кодирование взаимных характеристик пикселов в кодирующем блоке, поэтому восстановленное изображение после такого кодирования сохраняет мелкие детали при достаточно большом сжатии (до 16 раз и более).

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

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

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

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

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

Наиболее близко всем перечисленным требованиям удовлетворяют два последних рассмотренных метода, т.е. JPEG и АКВ. Приведенное сравнение этих методов показало, что JPEG имеет достаточно хорошее качество восстановленных изображений при коэффициенте сжатия до 15, но после 10 начинается исчезновение мелких деталей. Метод АКВ дает результаты, сопоставимые с JPEG, но при коэффициентах сжатия порядка 10 сохраняет мелкие детали. При больших коэффициентах сжатия метод АКВ показывает результаты лучшие, чем у JPEG, поэтому он и принимается за прототип. Отстройка от основного недостатка метода АКВ, т. е. устранение влияния шумов в канале связи, может быть осуществлена использованием для сжатия изображений принципов, заимствованных из нейронных сетей Кохонена [5] при использовании их в задачах сжатия изображений.

Было решено использовать классический метод АКВ и модифицировать его так, чтобы он сохранял топологию кодированных данных подобно нейронным сетям Кохонена. Для реализации этого необходимо следующее. Так же, как для устойчивого обучения нейронных сетей Кохонена, исходное положение кластеров должно быть специальным образом упорядочено так, чтобы по мере нарастания порядкового номера кластера значения пространственных координат его центра изменялись монотонно. Для этого исходные центры кластеров были расставлены по одной диагональной n-мерного векторного пространства, а номера кластеров менялись вдоль диагонали монотонно. Далее, в ходе описанного выше процесса адаптации положения кластеров исходная топология их расположения искажается, кластеры с соседними номерами могут оказываться в разных углах квантуемого векторного пространства. Чтобы этого не происходило, после ликвидации каждого пустого кластера и его открытия вблизи наибольшего из оставшихся производится переназначение номеров всех кластеров следующим образом. Вновь открываемому кластеру дается номер, соседний с номером кластера, подлежащего разбиению, при этом предыдущий или последующие номера кластеров (в зависимости от того, был ли номер ликвидированного кластера больше или меньше распределяемого) сдвигается на единицу, чтобы с номерами уже существующих и чтобы освободившийся номер ликвидированного кластера был приписан одному из оставшихся непустых. В результате были выработаны устойчивые методы обучения нейронных сетей Кохонена для сжатия-восстановления изображений. При 16-кратном сжатии восстановленное изображение сохраняет структуру и мелкие детали исходного, а средне квадратичная ошибка восстановления изображения почти такая же, как у классического метода АКВ при обработке изображений, на которых этот метод был обучен. Если же нейронная сеть используется для сжатия изображений, которые ей ранее не предъявлялись, качество ее работы превосходит качество работы по методу А.К.В.

Таким образом, классический метод А.К.В. базируется на предварительном построении кодовых таблиц (кодовых книг, кодовых библиотек, библиотек эталонов) на основе процесса обучения (адаптации) сжатию конкретных классов изображений. При этом используемые библиотеки не сохраняют топологию кодируемых данных, что приводит к большим ошибкам при декодировании, вызываемым малыми ошибками в кодируемых данных, возникающих, например, при передаче по каналам связи. Предлагаемый процесс обучения сохраняет указанную топологию (близкие по содержанию векторы имеют близкие значения номеров в кодовой библиотеке) и протекает следующим образом. Исходное изображение разбивается на блоки пикселов определенного размера K · L, каждый из которых интерпретируется как вектор в n K · L-мерном пространстве. Необходимо методом адаптивной кластеризации разделить данное пространство на "m" кластеров таким образом, чтобы плотность расположения кластеров соответствовала плотности распределения вероятности векторов в указанном векторном пространстве. Перед началом адаптивной кластеризации назначаются центры указанных "m" кластеров и некоторым упорядоченным образом размещаются в этом векторном пространстве. Затем на основании анализа выборки обучающих данных (n-мерных векторов, т.е. всех блоков-пикселов кодируемого изображения) производится адаптация положения этих центров к статистическим свойствам кодируемых данных. При этом для каждого из предъявленных векторов определяется отклонение от центров упомянутых кластеров по критерию минимума евклидова расстояния. Для каждого из кластеров новое положение центра вычисляется как среднее по всем попавшим в кластер векторам, пустые кластеры ликвидируются и новые кластеры с данным номером создаются с новым пространственным положением путем разбивания надвое самого большого из оставшихся кластеров. Одной из половин при этом приписывается номер материнского кластера, а другой номер вновь создаваемого (ликвидированного в другом месте векторного пространства). В качестве этих двух новых кластеров берется центр материнского, к исходным координатам которого прибавлены два небольших случайных n-мерных противоположно направленных вектора (таким образом, разносятся в пространстве центры вновь создаваемых кластеров). Важным моментом при этом оказывается сохранение принятого ранее порядка расположения кластеров в получаемой кодовой библиотеке, поэтому после образования нового кластера происходит их переупорядочивание с целью сохранения установленного порядка. После этого обучающая выборка векторов вновь предъявляется для кластеризации и этот процесс повторяется итеративно до выполнения критерия его завершения, например, до момента, когда изменение координат центров кластеров не станет по модулю меньше заданного порога.

Другой важной отличительной особенностью предлагаемого способа сжатия является использование режима псевдоплавающей точки при хранении и применении библиотек эталонов. Дело в том, как показали исследования, что при подготовке кодовых библиотек любым из применяемых способов наилучшие результаты по качеству восстановленных после сжатия изображений достигаются в том случае, когда значения векторов библиотеки рассчитываются и используются в формате с плавающей точкой. Однако это очень неэффективно с вычислительной точки зрения при реализации процедуры кодирования. В данном изобретении предлагается использовать при кодировании библиотеку, подготовленную в режиме с плавающей точкой. Затем полученные значения векторов умножаются на 64 и округляются до ближайшего целого. При этом, во-первых, используются двухбайтовые числа с 14 значащими разрядами, которые хорошо эмулируют режим работы с плавающей точкой. Во-вторых, двух оставшихся разрядов (недостающих до двух байт) достаточно, чтобы при расчете минимального эвклидова расстояния в процессе кодирования сумма квадрата разностей векторов (эталонного и кодируемого) не превышала двух байт, что обеспечивает удобную программную и аппаратную реализацию алгоритма. В-третьих, при вычислениях используется только целочисленная арифметика. Естественно, что при выполнении кодирования значения векторов изображения сдвигаются предварительно на 6 разрядов.

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

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

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

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

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

На чертеже представлена функциональная схема устройства кодирования-декодирования.

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

Устройство кодирования-декодирования функционирует следующим образом. Входное изображение в виде цифровой выборки входных данных поступает в первый и второй блоки оперативной памяти 2 и 3 на 4 строки для обеспечения информацией последующих блоков. Далее в блоке вычитания 6 формируется разность эталонного и текущего значений выборки сигнала изображения. Далее в квадраторе 7 формируется сигнал квадрата разности параллельно с 4-х строк (с 1 по 4 отсчеты). Результаты вычислений на дальнейшую обработку поступают по 8 каналам одновременно. Результаты накапливаются в накопителях 9, 10, 11, 12. Так как размер кодируемого блока составляет 4х4, то получение квадрата разности для всего вектора осуществляется за 2 прохода. При этом считываются следующие 8 отсчетов из буфера. Полученные восемь сумм передаются в блок суммирования, где они дважды попарно складываются для получения общей суммы. Результат запоминается в решающем блоке 16 и используется для выбора минимального значения вектора в библиотеке эталонов кодирования. Далее процедура повторяется для данного блока кодируемого изображения до тех пор, пока не будет обработана требуемая часть библиотеки эталонов и не будет выбран код данного блока изображения. Таким образом, архитектура строится по конвейерному принципу с применением внутри узлов распараллеливания обработки. Такт конвейерной структуры определяется наибольшим временем обработки данных в одном из узлов конвейера. После определения наиболее близкого вектора из библиотеки эталонов формируется кодированная строка изображения. Блок кодирования реализуется с использованием следующих элементов: регистр выбора входных данных, коммутаторы, блок управления и выборки микросхемы серий 1533, 1564, блоки оперативной памяти 1 и 2 микросхемы типа MS6264-20NS фирмы Texas Instruments, блок вычитания 6 и квадратор 7, сумматоры 13, 14, 15 на микросхемах TMS2210, блоки оперативной памяти 5. Библиотеки эталонов строятся на микросхемах MS62256-20NC, управляющий процессор типа TMS320C10Nh или TMS3220C25FNh. Входной регистр блока декодирования изображений обеспечивает связь с шиной, откуда поступает информация в виде кодированного изображения. Строка кодированного изображения поступает в буферную память блоков 18 и 19, которые обеспечивают постоянный прием и выдачу данных. Через коммутатор данные из одного из ОЗУ направляются в блок генерации физического адреса эталона в памяти, где номер вектора из библиотеки эталонов преобразуется в начальный адрес расположения в пространстве ОЗУ. Начальный адрес эталона поступает в блок формирования и счетчик адреса памяти. После считывания одной строки эталонного блока в устройство формирования адреса поступает начальный адрес следующего вектора и происходит считывание строки эталонного блока по данному адресу и т.д. Считанная информация направляется из памяти эталонов, поступает на входной регистр и далее на формирование строки выходного изображения.

Декодер может быть реализован на следующих элементах: входной регистр, коммутатор, блок формирования и счетчик адреса эталонной памяти, выходной регистр (выполняется на основании микросхем серий 1553, 1554, 55PT17), ОЗУ эталона на основе MS62256-20NC (блок формирования изображений на основе микросхем серий 174 и 1118).

Литература
1. Уинту Р.А. Кодирование изображений посредством преобразований, ТИИЭР, 1972 г. т.60, N7, с. 69-81.

2. Радчеев Р. Фразер Р. Средство сжатия изображений для работы со сканером МИР ПК, N 4, 1992 г. с.53-45.

3. Nasrebadi N. M. King R.A. Image Coding Using Vector Quantization A. Review JEEE Trans. on Cjmm 76 vol. 36(8), 1988, pp.81-93.

4. Кун С. Матричные процессоры на СВИС. Пер. с англ. М. Мир, 1991 г. с. 672.

5. Патент США N 5010401, HO4N 7/12, 1991. Устройство кодирования-декодирования с использованием векторного квантования.

6. PCT N WO-90-09079, HO4N 7/12. Метод и аппаратура для квантования.

Формула изобретения

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

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

РИСУНКИ

Рисунок 1