Способ кодирования и декодирования цифровых данных, основанный на принципах цифровой голографии

Изобретение относится к способам кодирования и декодирования массивов цифровых данных, основанных на принципах цифровой голографии, предназначенных для их хранения на электронных носителях и передачи по каналам связи. Техническим результатом является уменьшение аппаратурных затрат. Способ заключается в следующем: при кодировании исходного двоичного массива длиной n=2^m бит осуществляется его рандомизация побитным суммированием по модулю 2 с битами псевдослучайной двоичной последовательности, и получаемая в результате этого некоррелированная псевдослучайная последовательность такая, что значения нуля и единицы равновероятны, подвергается прямому преобразованию Уолша-Адамара, с использованием только операций суммирования и сдвига, из полученных n=2^m коэффициентов выбирается L<n, и каждый из L коэффициентов вместе со значением его индекса в множестве функций Уолша-Адамара данного порядка 2^m записывается и запоминается на некотором электронном устройстве памяти или передается по каналу связи приемнику, выполняющему декодирование данной последовательности. 1 з.п. ф-лы, 3 ил.

 

Изобретение относится к способам кодирования и декодирования дискретной информации для ее хранения на электронных носителях в сжатом виде и передачи по каналам связи.

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

Голографический принцип кодирования изображений состоит в том, что каждая часть голограммы изображения некоторого объекта содержит информацию о всем изображении (каждом его пикселе). Хотя восстановленное по такой порции голограммы изображение будет в той или иной степени нечетким (расплывчатым, blurred), с потерей некоторых деталей, но качество восстанавливаемого изображения растет с ростом размера части используемой голограммы. При использовании цифровой голографии [L.Yaroslavsky, Digital Holography and Digital Image Processing, 2004, Kluwer Acad. Publisher], при замене некоторого изображения его цифровой версией голограммы, ее отдельные порции представляют собой сжатые (с потерями) версии исходного изображения, и если рассматривать такое представление как кодирование цифрового массива данных (файла), содержащего оцифрованное изображение, то восстановление изображения по порциям голограмм можно рассматривать как его декодирование.

В цифровой голографии массив пикселей, представляющий изображение (bitmap) рассматривается как амплитудный спектр Фурье преобразования голограммы данного изображения. Если I(x, y) - двоичное представление изображения, то голограмма представляет собой обратное Фурье-преобразование, вычисляемое на множестве точек данного изображения:

H(u,ν)=FTⁱ{I(x, y)e^jP(x,y)},

где FTⁱ - обратное преобразование Фурье, P(x, y) - случайная фаза, значения которой равномерно распределены в интервале [-π, π].

Иными словами, изображение рассматривается как амплитудный Фурье-спектр его голограммы. Соответственно, любая порция (часть) голограммы Н_с(u, ν) преобразуется в частотную область, и по этой порции голограммы может быть получена нечеткая версия изображения I(x, y), причем его качество ("четкость") растет с увеличением порции (используемой доли) голограммы. При этом преобразование Фурье выполняется для порции H_c(u, v), дополненной до полной голограммы нулями. При потере части порций возможно получить нечеткое (расплывчатое, blurred) изображение объекта, которого в ряде случаев может оказаться достаточным для решения тех или иных задач. Например, в сетях с использованием передачи пакетов по множественным каналам, если в пакетах передаются порции цифровой голограммы, могут быть снижены требования к пропускной способности каналов. При потере части порций, на приемном конце все равно возможно восстановление изображения, быть может, и с некоторой потерей четкости, тогда как при обычном методе хранения и передаче изображения (например, при использовании формата JPEG) потеря блока будет безвозвратной, то есть приведет к потере целого фрагмента изображения. Погрешность восстановления по голограмме зависит только от объема потерянной информации. Например, голографическое представление изображения оказывается эффективным в ситуациях, когда положение информационного блока, пришедшего на вход, оказывается неизвестным [А.М.Bruckstein, "Holographic Image Representations: The Fourier Transform Method," IEEE Trans. Image Processing, vol.7, 1997]. Кроме того, голографический метод кодирования изображения предоставляет возможность последовательного уточнения восстановленного изображения в распределенных сетях.

Хотя голографический принцип кодирования был сформулирован для хранения и передачи изображений, имеются также примеры его использования для кодирования произвольных цифровых файлов. Примером использования голографических принципов для кодирования произвольных файлов является Information additive code generator and decoder [Michael Luby, Information additive code generator and decoder for communication systems. United States Patent 6373406, Publication Date: 04/16/2002]. Кодовые слова генерируются из исходного файла с использованием весовых функций W(I), где I-ключ, присваиваемый каждому кодовому слову, и некоторой выбранной заранее функцией F(I). Кодовые слова независимы друг от друга, и генерируются случайным образом. Ключ I известен декодеру. Число кодовых слов, необходимых для декодирования незначительно превышает число слов (блоков) исходного файла. Данный процесс кодирования-декодирования является квазиголографическим, поскольку каждый передаваемый пакет содержит образ всего передаваемого файла, и по любой части этих пакетов можно реконструировать исходный файл с определенной вероятностью ошибок. Существенным достоинством данного способа является возможность начинать прием в произвольное время. При этом при потере пакетов в некотором случайном наборе передаваемых данных имеется высокая вероятность того, что большинство принятых данных могут быть использованы в процессе восстановления информации. Однако качество декодированного сигнала в данном способе зависит от соотношения от свойств исходного файла. Особенно это влияет на качество передаваемых изображений.

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

В большей степени голографическому свойству удовлетворяет способ кодирования цифровых массивов изображений, основанный на цифровой голографии, предложенный в [Alfred M. Bruckstein, Robert J. Holt, and Arun N. Netravali, Holographic Representations of Images I IEEE Trans. Image Processing, vol.7, №11, November,1998. pp.1583-1598], рассматриваемый нами как возможный аналог.

Технически эта идея реализуется следующим образом. Изображение I(x, у) случайным образом разбивают на блоки 8×8 пикселей, каждый из которых представляют набором пар матриц, соответствующих реальной и мнимой частям комплекснозначного представления пикселей, квантуются (аналогично JPEG), причем случайная выборка организуется так, что мнимые части обеспечивают равномерное распределение фазы в интервале [-π, π]. Те или иные подмножества случайно выбранных блоков образуют порции голограмм, из которых обратным преобразованием Фурье могут быть получены указанные выше нечеткие изображения. Существенно, что при восстановлении изображения по порциям голограмм неважен порядок выбора порций.

Однако рассмотренные способы кодирования-декодирования изображений требуют значительных вычислительных затрат, связанных с вычислением комплексного Фурье-преобразования, поскольку необходимо использовать арифметику комплексных чисел (вычислять действительную и мнимые части) с плавающей точкой. Также данные способы не используют явные параметры выбора числа используемых в данной порции спектральных коэффициентов для обеспечения заданного сжатия файла. Существенно, что точность восстановления (декодирования) обоих указанных выше способов зависит от структурных свойств кодируемых файлов, а в случае использования способа [Alfred M. Bruckstein, Robert J. Holt, and Arun N. Netravali, Holographic Representations of Images I IEEE Trans. Image Processing, vol.7, №11, November, 1998. pp.1583-1598] и от свойств человеческого зрения, что затрудняет управление объемом информации, используемой при кодировании и декодировании информации для передачи и хранения наборов данных.

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

Поставленная цель достигается за счет того, что вместо кодирования путем рандомизации исходного массива случайной выборкой фрагментов массива и их преобразования Фурье (как [Bruckstein, Robert J. Holt, and Arun N. Netravali, Holographic Representations of Images, IEEE Trans. Image Processing, vol.7, №11, November, 1998. pp.1583-1598]), или взвешивания по специальным функциям (как в [Michael Luby, Information additive code generator and decoder for communication systems. United States Patent 6373406, Publication Date: 04/16/2002]), используется преобразование Уолша-Адамара псевдослучайной некоррелированной двоичной последовательности, получаемой суммированием по модулю 2 исходного массива с векторами некоторой псевдослучайной двоичной матрицей, с использованием ограниченного числа коэффициентов Уолша-Адамара, восстановлением псевдослучайной последовательности выполнением обратного преобразования Уолша-Адамара, округлением получаемых результатов и суммированием по модулю 2 с векторами исходной псевдослучайной матрицей. При этом используются только операции суммирования и сдвига, что уменьшает требования к затратам на кодирование-декодирование ресурсов. Благодаря применению ортогональных преобразований к некоррелированной последовательности, качество восстановления незначительно зависит от структуры (состава) спектра исходного массива и может применяться к файлам произвольной структуры.

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

На фиг.1 дано графическое представление способа кодирования и декодирования, где обозначены:

1 - исходный массив данных или файл, предназначенный для записи на электронный носитель или передачи по каналу связи,

2 - блок суммирования по модулю 2 исходного двоичного файла данных F (в частности, пикселей изображения) размера n=2^m бит, где m некоторое натуральное число, и задаваемой некоторой двоичной матрицей псевдослучайной последовательности (блок 3), не коррелированной с F, формирующий некоррелированную псевдослучайную двоичную последовательность (блок 4) с равной вероятностью появления 0 и 1,

5 - блок вычисления коэффициентов преобразования Уолша-Адамара (УА), и формирования пар {c_i, i} коэффициентов с_i и их индексов i, по функциям Уолша-Адамара (блок 6), принимающих только значения 1 и -1 [Л.Рабинер и Б.Гоулд. Теория и применение цифровой обработки сигналов. - M.: Мир, 1978 г.],

7 - блок выбора L≤2^m коэффициентов и их индексов i преобразования Уолша-Адамара по заданному значению L и по некоторому коду критерия выбора и их записи на соответствующий носитель или передачи по каналу связи,

8 - набор L коэффициентов преобразования Уолша-Адамара и их индексов,

9 - кодированные согласно фиг.1 данные, представляющие собой набор L коэффициентов преобразования Уолша-Адамара и их индексов,

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

11 - обратное преобразование Уолша-Адамара по полученным на этапе кодирования 1 из 2^m коэффициентов и округление полученных результатов до двоичных значений,

12 - суммирование по модулю 2 полученной псевдослучайной последовательностью с двоичной псевдослучайной последовательности (блок 13), используемой при кодировании,

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

Исходный двоичный файл (например, изображение в формате bitmap или другом пиксельном формате, или ASCII файл) кодируется преобразованием в двоичную псевдослучайную некоррелированную последовательность суммированием побитно по модулю два с битами псевдослучайной последовательности, генерируемой при данном начальном исходном значении первого генерируемого числа (известного подсистеме декодирования данного кода), выполнения быстрого преобразования Уолша-Адамара полученной псевдослучайной, некоррелированной дискретной случайной последовательности, выбора заданного числа L коэффициентов из всех 2^m коэффициентов преобразования, исходя из требований к ресурсам системы при решении той прикладной задачи, для которой выполняется кодирование и декодирование, записи на электронный носитель и/или передачи по каналу связи выбранных спектральных коэффициентов и их индексов, и декодируется посредством выполнения обратного преобразования Уолша-Адамара по подмножеству L коэффициентов, округлением полученных значений до двоичных значений 0 или 1, сложением по модулю 2 полученной двоичной последовательности с псевдослучайной последовательностью, использовавшейся при кодировании исходного файла, оценкой пригодности полученного файла при передаче части коэффициентов преобразования, с точки зрения возможности распознавания и использования информации, содержащейся в файле, например, для визуального распознавания необходимых графических объектов. Каждый набор коэффициентов и индексов обладает, с точки зрения восстановления по нему исходного массива (в частности, изображения), свойствами порции цифровой голограммы данного массива.

Изобретение осуществляется следующим образом. Исходный передаваемый файл F=(b₁, b₂,…,b_n) размера n=2^m (блоков или бит, если блок однобитовый), хранящийся на том или ином электронном носителе информации, и предназначенный для передачи по каналу как двоичный файл, или как упорядоченное множество наборов битов, структурированных в блоки (символы), подвергается побитному суммированию по модулю 2 с битами псевдослучайной последовательности, с целью получения некоррелированной псевдослучайной дискретной последовательности, которая подвергается прямому преобразованию Уолша-Адамара (УА):

где W(h,i) - функция Уолша индекса h.

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

Исходя из текущих требований к максимально-возможному объему информации, записываемой на носитель и/или передаваемому по каналу (требований к сжатию информации), записываются или передаются L<n коэффициентов из n=2^m, где n - длина (число бит) хранимого/передаваемого файла (или его фрагмента), идентификатор псевдослучайной последовательности, использованной для рандомизации, выполняется обратное преобразование Уолша-Адамара, используя полученные L коэффициентов:

где - оценка i-го символа файла приемником.

Если число используемых при восстановлении файла коэффициентов меньше n, то значения восстанавливаемых величин оказываются рациональными числами, расположенными между 0 и 1, и требуется округление до ближайших битовых значений. Величины округляются по правилу: биту с индексом i присваивается 0, если абсолютное значение , и 1 в противном случае. При этом вероятность ошибки округления, то есть вероятности того, что при округлении к левой (правой) границе интервала, истинное значение восстанавливаемого символа соответствует правой (левой) границе, убывает по мере роста соотношения L/n. Величина L выбирается из требований к ресурсам системы при решении той прикладной задачи, для которой выполняется кодирование и декодирование. Например, если целью является сжатие информации при фиксированном уровне потерь, эффективным оказывается выбор L максимальных по абсолютной величине коэффициентов среди всех n. При передаче порций голограмм к приемнику в виде пакетов по отдельным каналам некоторой распределенной системы связи, более эффективным оказывается псевдослучайный выбор чисел коэффициентов при вычислении в каждой порции.

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

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

Фиг.2 и фиг.3 показывают, что для разных исходных двоичных файлов, различающихся размеров, доля правильно восстанавливаемых бит зависит только от доли используемых коэффициентов разложения Уолша-Адамара. Как видно из этих фигур, при использовании, например, 10% максимальных по абсолютной величине коэффициентов, в обоих случаях примерно 80% бит восстанавливается правильно, и при 25%-30% используемых коэффициентов имеет место полное или почти полное (>95%) восстановление.

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

В случаях, если передачу массива (файла) предполагается осуществлять в виде пакетов, передаваемых к приемнику по нескольким каналам, то для каждого канала выполняется кодирование со своим числом коэффициентов L_i, где i=1,…, k - число каналов, согласно Фиг.1, и декодирование выполняется по всем поступающим к приемнику коэффициентам. При этом имеется возможность последовательного уточнения декодируемого и восстанавливаемого массива (файла).

1. Способ кодирования и декодирования массивов цифровых данных, основанный на принципах цифровой голографии, заключающийся в том, что для кодирования исходного двоичного массива длиной n=2^m бит осуществляется его рандомизация побитным суммированием по модулю 2 с битами псевдослучайной двоичной последовательности, и получаемая в результате этого некоррелированная псевдослучайная последовательность такая, что значения нуля и единицы равновероятны, подвергается прямому преобразованию Уолша-Адамара, с использованием только операций суммирования и сдвига, из полученных n=2^m коэффициентов выбирается L<n, где значение L выбирается исходя из требований к ресурсам системы при решении той прикладной задачи, для которой выполняется кодирование и декодирование, и каждый из L коэффициентов вместе со значением его индекса (порядкового номера) в множестве функций Уолша-Адамара данного порядка 2^m записывается и запоминается на некотором электронном устройстве памяти, или передается по каналу связи приемнику, выполняющему декодирование данной последовательности.

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