СПОСОБ СЖАТИЯ И ВОССТАНОВЛЕНИЯ СООБЩЕНИЙ Российский патент 2006 года по МПК H04N7/30 

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

Известны способы кодирования видеоизображений на основе импульсно-кодовой модуляции, дифференциальной импульсно-кодовой модуляции, статистического кодирования и кодирования с предсказанием, см., например, книгу: У.Претт. Цифровая обработка изображений. Часть 2. - М.: Мир, 1982, с.641-688. Данные способы подразумевают кодирование изображений с поэлементной обработкой, когда непрерывный видеосигнал преобразуется в последовательность квантованных отсчетов и затем представляется кодовыми словами в виде нулей и единиц.

Известны также способы кодирования на основе преобразования, см., например, книгу: Н.Ахмед, К.Р.Рао. Ортогональные преобразования при обработке цифровых сигналов. - М.: Радио и связь, 1980, с.192-201, включающие выполнение трех операций: сначала изображение подвергается двумерному ортогональному преобразованию, полученные в результате коэффициенты преобразования квантуют и кодируют для передачи по каналу связи.

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

Известен способ сжатия и восстановления речевых сообщений, описанный в патенте РФ №224463, МПК⁷ G 10 L 19/00, от 2005 г., который обеспечивает исправление ошибок, возникающих в передаваемых цифровых последовательностях под влиянием нестабильности параметров канала связи и позволяет осуществлять передачу информации по низкоскоростным цифровым каналам связи. Недостатком данного способа является относительно низкое качество восстановления информации при вероятности ошибки в канале связи 10^-4.

Наиболее близким по своей технической сущности к заявленному способу является способ сжатия и восстановления речевых сообщений, описанный в патенте РФ №2244963, МПК⁷ Н 04 N 7/30, от 2005 г.

Известный способ-прототип, заключающийся в том, что предварительно на передающей и приемной сторонах идентично генерируют случайную квадратную матрицу размером m×m элементов. Представляют информационный цифровой сигнал в виде матрицы нормированных значений. Генерируют случайные прямоугольные матрицы размером N×m и m×N элементов, преобразуют их путем деления элементов каждой строки случайной прямоугольной матрицы размером Nxm элементов на сумму единиц соответствующей строки и деления элементов каждого столбца случайной прямоугольной матрицы размером m×N элементов на сумму единиц соответствующего столбца. Затем вычисляют результирующую матрицу размером N×N элементов, путем последовательного умножения преобразованной случайной прямоугольной матрицы размером Nxm на случайную квадратную матрицу размером m×m и на преобразованную случайную прямоугольную матрицу размером m×N элементов. Далее вычисляют среднеквадратическую ошибку между элементами результирующей матрицы размером NxN элементов и элементами матрицы нормированных значений размером N×N элементов. После чего последовательно инвертируют каждый элемент случайных прямоугольных матриц размером N×m и m×N элементов, и после инверсии каждого элемента в случайной прямоугольной матрице преобразуют ее путем деления элементов каждой строки случайной прямоугольной матрицы с инвертированным элементом размером N·m элементов на сумму единиц соответствующей строки и деления элементов каждого столбца случайной прямоугольной матрицы с инвертированным элементом размером m×N элементов на сумму единиц соответствующего столбца. Повторно вычисляют результирующую матрицу размером N×N элементов, путем последовательного умножения преобразованной случайной прямоугольной матрицей с инвертированным элементом размером N×m на случайную квадратную матрицу размером m×m и на преобразованную случайную прямоугольную матрицу с инвертированным элементом размером m×N. После чего вычисляют среднеквадратическую ошибку между элементами повторно вычисленной результирующей матрицы размером N×N элементов с элементами матрицы нормированных значений размером N×N элементов. Передают по каналу связи случайную прямоугольную матрицу размером N×N. Принимают из канала связи эту матрицу и на приемном конце преобразуют принятые случайные прямоугольные матрицы N×m и m×N путем деления элементов строки каждой случайной прямоугольной матрицы размером N×m элементов на сумму единиц соответствующей строки и деления элементов каждого столбца случайной прямоугольной матрицы размером m×N элементов на сумму единиц соответствующего столбца. Вычисляют результирующею матрицу размером N×N элементов, путем последовательного умножения преобразованной случайной прямоугольной матрицы размером N×m на случайную квадратную матрицу размером m×m и на преобразованную случайную прямоугольно матрицу размером m×N. Формируют цифровой информационный сигнал. На приемной и передающей сторонах дополнительно генерируют по k случайных ключевых матриц размером N×m и m×N элементов. Каждый элемент случайной квадратной матрицы размером mxm элементов принадлежит диапазону -500 ÷ +500, в качестве цифрового информационного сигнала принимают k матриц квантованных отсчетов неподвижного полутонового изображения размерами М×М, где k>1.

Генерируют на приемной и передающей сторонах идентичную нормировочную матрицу размером N×N элементов, элементы которой C(i,j) вычисляют по формуле где i=1, 2, ..., N, j=1, 2, ..., N. В качестве случайной прямоугольной матрицы размером mxN элементов принимают на передающей стороне транспонированную случайную прямоугольную матрицу размером N×m элементов. Формируют k матриц коэффициентов двумерного дискретно-косинусного преобразования размером М×М элементов путем последовательного перемножения матрицы дискретно-косинусного преобразования размером М×М элементов на каждую матрицу квантованных отсчетов неподвижного полутонового видеоизображения размером М×М элементов и на транспонированную матрицу дискретно-косинусного преобразования размером М×М элементов. Далее формируют k матриц коэффициентов двумерного дискретно-косинусного преобразования размером N×N элементов, по формуле A_g(i,j)=L_g(i,j), где i=1, 2, ..., N, j=1, 2, ..., N, g=1, 2, ..., k, Lg(i,j)-i,j-й элемент g-й матрицы коэффициентов двумерного дискретного косинусного преобразования размером М×М элементов, Ag(i,j)-i,j-й элемент g-й матрицы коэффициентов двумерного дискретно-косинусного преобразования размером N×N элементов, причем выбирают N<M. Затем формируют k матриц нормированных значений размером N×N элементов путем умножения каждого коэффициента матрицы коэффициентов двумерного дискретно-косинусного преобразования размером N×N элементов A_g(I,j) на соответствующий ему элемент нормировочной матрицы размером N×N элементов. Каждую из ключевых матриц размерами N×m и m×N элементов суммируют по модулю 2 соответственно с прямой и транспонированной случайной прямоугольной матрицей размерами N×m и m×N элементов, а после вычисления среднеквадратической ошибки между соответствующими элементами каждой результирующей матрицы размером N×N элементов и матрицы нормированных значений размером N×N элементов, вычисляют их итоговую сумму. После инвертирования каждого элемента случайной прямоугольной матрицы размером N×m полученную итоговую сумму сравнивают с предыдущей итоговой суммой. По каналу связи передают случайную прямоугольную матрицу размером N×m элементов, а на приемной стороне после перемножения k случайных матриц размерами N×m на случайную матрицу размером m×m и на k случайных матриц размерами m×N преобразуют результирующие матрицы размерами N×N элементов путем поэлементного деления их элементов на соответствующие элементы нормировочной матрицы размером N×N элементов. Полученные k матрицы восстановленных коэффициентов размерами N×N элементов дополняют нулями до размеров М×М элементов. Восстанавливают k матриц неподвижных полутоновых изображений путем последовательного перемножения транспонированной матрицы дискретно-косинусного преобразования размером М×М элементов на k матриц восстановленных коэффициентов двумерного дискретно-косинусного преобразования размером М×М элементов и на матрицу дискретно-косинусного преобразования размером М×М элементов. Для формирования k матриц квантованных отсчетов неподвижного полутонового видеоизображения размерами М×М элементов каждому ее элементу S_g(x,y), где х=1, 2, ..., М, у=1, 2, ..., М, g=1, 2, ..., k, присваивают квантованное значение соответствующего пиксела g неподвижных полутоновых видеоизображений, размером N×N. Для представления k матриц квантованных отсчетов неподвижного полутонового видеоизображения размером М×М элементов в виде k неподвижных полутоновых видеоизображений каждому пикселу k неподвижных полутоновых видеоизображений присваивают значение соответствующего элемента k матриц восстановленных квантованных отсчетов неподвижных полутоновых видеоизображений размером М×М элементов.

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

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

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

Поставленная цель достигается тем, что в известном способе сжатия и восстановления сообщений предварительно на передающей и приемной сторонах идентично генерируют случайную квадратную матрицу размером m×m элементов, каждый элемент которой принадлежит диапазону -500 ÷ +500. Генерируют по k случайных ключевых матриц размером N×m и m×N элементов. Затем формируют нормировочную матрицу размером N×N элементов, элементы которой C(i,j) вычисляют по формуле где i=1, 2, ..., N, j=1, 2, ..., N, и формируют матрицу квантованных отсчетов неподвижного полутонового видеоизображения размером М×М элементов, в которой каждому ее элементу S(x,y) присваивают квантованное значение соответствующего пиксела неподвижного полутонового видеоизображения, размером М×М пикселов, где x=1, 2, ..., M; y=1, 2, ..., M. Далее формируют матрицу коэффициентов двумерного дискретно-косинусного преобразования размером М×М элементов путем последовательного перемножения матрицы дискретно-косинусного преобразования размером М×М элементов на матрицу квантованных отсчетов неподвижного полутонового видеоизображения размером М×М элементов и на транспонированную матрицу дискретно-косинусного преобразования размером М×М элементов. Формируют матрицу коэффициентов двумерного дискретно-косинусного преобразования размером N×N элементов, по формуле A(i,j)=L(i,j), где L(ij)-i,j-й элемент матрицы коэффициентов двумерного дискретного косинусного преобразования размером M×M элементов, A(i,j)-I, j-й элемент матрицы коэффициентов двумерного дискретно-косинусного преобразования размером N×N элементов, причем выбирают N<M, после чего формируют матрицу нормированных значений размером N×N элементов путем умножения каждого коэффициента матрицы коэффициентов двумерного дискретно-косинусного преобразования размером N×N элементов А(i,j) на соответствующий ему элемент нормировочной матрицы размером N×N элементов. Затем генерируют случайную прямоугольную матрицу размером N×m элементов, а в качестве случайной прямоугольной матрицы размером m×N элементов принимают транспонированную случайную прямоугольную матрицу размером N×m элементов, затем каждую из ключевых матриц размерами N×m и m×n элементов суммируют по модулю 2 соответственно с прямой и транспонированной случайной прямоугольной матрицей размерами N×m и m×N элементов. Преобразуют полученные матрицы путем деления элементов каждой строки случайной прямоугольной матрицы размером N×m элементов на сумму единиц соответствующей строки и деления элементов каждого столбца случайной прямоугольной матрицы размером m×N элементов на сумму единиц соответствующего столбца. Далее вычисляют k результирующих матриц V(g), где g=1, 2, ..., k, размером N×N элементов путем последовательного умножения k преобразованных случайных прямоугольных матриц размером N×m на случайную квадратную матрицу размером m×m и на k преобразованных случайных прямоугольных матриц размером m×N элементов. Последовательно инвертируют каждый элемент случайных прямоугольных матриц размерами N×m и m×N элементов и после инверсии преобразуют их путем деления элементов каждой строки случайной прямоугольной матрицы с инвертированным элементом размером N×m элементов на сумму единиц соответствующей строки и деления элементов каждого столбца случайной прямоугольной матрицы с инвертированным элементом размером m×N элементов на сумму единиц соответствующего столбца. Повторно вычисляют k результирующих матриц размером N×N элементов, путем последовательного умножения k преобразованных случайных прямоугольных матриц с инвертированным элементом размером N×m на случайную квадратную матрицу размером m×m и на k преобразованных случайных прямоугольных матриц с инвертированным элементом размером m×N. Передают по каналу связи случайную прямоугольную матрицу размером N×m и принимают из канала связи эту матрицу. Затем каждую из ключевых матриц размерами N×m и m×N элементов суммируют по модулю 2 соответственно с прямой и транспонированной случайными прямоугольными матрицами размерами N×m и m×N элементов. Преобразуют принятые случайные прямоугольные матрицы размерами N×m и m×N путем деления элементов строки каждой случайной прямоугольной матрицы размером N×m элементов на сумму единиц соответствующей строки и деления элементов каждого столбца случайной прямоугольной матрицы размером m×N элементов на сумму единиц соответствующего столбца. Затем вычисляют k восстановленных результирующих матриц где g=1, 2, ..., k, размером N×N элементов путем последовательного умножения k преобразованных случайных прямоугольных матриц размером N×m на случайную квадратную матрицу размером m×m и на k преобразованных случайных прямоугольных матриц размером m×N соответственно, а матрицу восстановленных коэффициентов размером N×N элементов дополняют нулями до размеров М×М элементов. Получают матрицу восстановленных коэффициентов дискретно-косинусного преобразования размером М×М элементов, восстанавливают матрицу неподвижного полутонового изображения путем последовательного перемножения транспонированной матрицы дискретно-косинусного преобразования размером М×М элементов на матрицу восстановленных коэффициентов двумерного дискретно-косинусного преобразования размером М×М элементов и на матрицу дискретно-косинусного преобразования размером М×М элементов. Формируют цифровой информационный сигнал, каждому пикселу^{неподвижного полутонового видеоизображения присваивают значение соответствующего элемента матрицы восстановленных квантованных отсчетов неподвижных полутоновых видеоизображений размером М×М элементов. После вычисления k результирующих матриц вычисляют суммарную матрицу размером N×N элементов V_s по формуле Затем вычисляют среднеквадратическую ошибку между элементами матрицы нормированных значений размером N×N элементов и элементами суммарной матрицы V_s размером N×N элементов. После инверсии каждого элемента случайных прямоугольных матриц размерами N×m и m×N повторно вычисляют k результирующих матриц, суммарную матрицу V_s и среднеквадратическую ошибку между элементами матрицы нормированных значений размером N×N элементов и элементами повторно вычисленной суммарной матрицы V_s размером N×N элементов. Полученную среднеквадратическую ошибку вычитают от предыдущей среднеквадратической ошибки и в случае положительной разности запоминают инвертированный элемент, а после вычисления k восстановленных результирующих матриц вычисляют восстановленнуюсуммарную матрицу размером N×N элементов _s по формуле а для получения матрицы восстановленных коэффициентов размером N×N элементов преобразуют восстановленную суммарную матрицу размером N×N элементов путем поэлементного деления ее элементов на соответствующие элементы нормировочной матрицы размером N×N элементов.}

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

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

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

Заявленный способ поясняется чертежами.

- Фиг.1а. Формирование случайной квадратной матрицы размером m×m элементов.

- Фиг.1б. Вариант случайной квадратной матрицы размером m×m элементов.

- Фиг.2. Формирование матрицы коэффициентов двумерного дискретно-косинусного преобразования размером М×М элементов.

- Фиг.3. Формирование матрицы коэффициентов двумерного дискретно-косинусного преобразования размером N×N элементов.

- Фиг.4а, 4б. Формирование нормировочной матрицы размером N×N элементов.

- Фиг.5. Формирование матрицы нормированных значений размером N×N элементов.

- Фиг.6а. Формирование k случайных ключевых матриц размером Nxm элементов.

- Фиг.6б. Вариант k случайных ключевых матриц размером N×m элементов.

- Фиг.6в. Формирование k случайных ключевых матриц размером m×N элементов.

- Фиг.6г. Вариант k случайных ключевых матриц размером m×N элементов.

- Фиг 7а. Формирование случайной прямоугольной матрицы размером N×m элементов.

- Фиг.7б. Вариант случайной прямоугольной матрицы размером N×m элементов.

- Фиг.7в. Формирование k случайных прямоугольных матриц размером N×m элементов.

- Фиг 7г. Формирование k случайных прямоугольных матриц размером m×N элементов.

- Фиг.7д. Преобразование k случайных прямоугольных матриц размером N×m элементов.

- Фиг.7е. Преобразование k случайных прямоугольных матриц размером m×N элементов.

- Фиг.8. Формирование k результирующих матриц размером N×N элементов.

- Фиг.9а. Вариант инверсии элемента случайной прямоугольной матрицы размером N×m элементов.

- Фиг.10. Передача случайной прямоугольной матрицы размером N×m элементов по цифровому каналу связи.

- Фиг.11а. Вариант матрицы коэффициентов двумерного дискретно-косинусного преобразования размером М×М элементов.

- Фиг.11б. График абсолютных значений первой строки матрицы коэффициентов двумерного дискретно-косинусного преобразования размером М×М элементов.

- Фиг.12. Формирование матрицы восстановленных коэффициентов двумерного дискретно-косинусного преобразования размером N×N элементов.

- Фиг.13. Формирование матрицы восстановленных коэффициентов двумерного дискретно-косинусного преобразования размером М×М элементов.

- Фиг.14. Формирование матрицы восстановленных квантованных отсчетов неподвижного полутонового видеоизображения.

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

Например, (см. книгу: У. Претт. Цифровая обработка изображений. Часть 1. - М.: Мир, 1982, с.96-118) кодируемое сообщение представляют в виде произведения матрицы опорных векторов на матрицу коэффициентов разложения. Для этой цели используют один из известных приемов: дискретное косинусное преобразование, быстрое преобразование Фурье, преобразование Карунена-Лоэва, Вейвлет-преобразование и другие.

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

На приемном конце принятое сообщение восстанавливают.

Таким образом, при некотором ухудшении качества передаваемой информации обеспечивают снижение объема информации, необходимого для передачи. В то же время объем передаваемой информации о матрице опорных векторов и матрице коэффициентов разложения все еще велик, что не соответствует требованиям к современным каналам связи при сохранении требуемого качества, а также данные приемы не обеспечивают устойчивость к ошибкам в канале связи. Для повышение устойчивости к ошибкам в канале связи применяют помехоустойчивое кодирование, описанное, например, в книге: У. Питерсон, Э. Уэлдон. Коды, исправляющие ошибки. - М.: Мир, 1976. Данное помехоустойчивое кодирование основано на разделении всех возможных кодовых комбинаций на разрешенные и запрещенные. Такой подход предполагает введение в передаваемую цифровую последовательность избыточности. Это приводит к существенному снижению степени сжатия передаваемой информации и соответственно повышению требований к скорости передачи цифрового канала связи. Известен также способ борьбы с помехами на основе метода накопления, описанный, например, в книге: А.А.Харкевич. Борьба с помехами. - М.: ГИФМЛ, 1963. Данный метод основан на передаче одного сообщения по нескольким независимым каналам. Данный метод увеличивает отношение сигнал-помеха в k раз без увеличения мощности сигнала. Однако за этот выигрыш приходится расплачиваться k кратным использованием канала. При временном разделении каналов увеличивается в k раз время передачи, при частотном - в k раз занимаемая полоса частот и т.д.

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

Предлагаемый способ реализуют следующим образом.

Формирование на передающей и приемной сторонах случайной квадратной матрицы размером m×m элементов (в дальнейшем обозначим ее как [B]_m×m), каждый элемент которой принадлежит диапазону -500 ÷ +500 (см. фиг.1а, 1б). Размер m матрицы [B]_m×m выбирают опытным путем исходя из размера передаваемого сообщения - М. Экспериментальные исследования показывают, что для качественной аппроксимации передаваемого сообщения размер m составляет 1/5-1/4 размера передаваемого сообщения. Операция формирования матрицы [B]_m×m может быть выполнена с использованием датчика случайных чисел. Для выполнения требования идентичности матрицы [B]_m×m приемника аналогичной матрице передатчика элементы матрицы [В]_m×m могут быть сгенерированы на передающей стороне и переданы по цифровому каналу связи на приемную сторону, например, в составе синхропосылки.

В качестве сообщения, подлежащего сжатию и восстановлению, далее рассматривается неподвижное полутоновые видеоизображение, из которого формируют матрицу квантованных отсчетов неподвижного полутонового видеоизображения размером М×М элементов, присвоив каждому ее элементу S(x,y), где x=1, 2, ..., M; y=1, 2, ..., M, квантованное значение соответствующего пиксела неподвижного полутонового видеоизображения (см. фиг.15).

С целью уменьшения объема информации, передаваемой по каналу связи, используют дискретное косинусное преобразование, описанное, например, в книге: Н.Ахмед, К.Р.Рао. Ортогональные преобразования при обработке цифровых сигналов. - M.: Связь, 1980, с.156-159.

Матрицу коэффициентов двумерного дискретно-косинусного преобразования размером М×М элементов формируют на основании выражения

[L(x,y)]_M×M=[Г([x,y)]_M×M×[S(x,y)]_M×M, ([Г(x,y)_M×M, где [L(x,y)]_M×M - матрица коэффициентов двумерного дискретно-косинусного преобразования неподвижного полутонового видеоизображения размером М×М элементов, [S(x,y)]_M×M - матрица квантованных отсчетов неподвижного полутонового видеоизображения размером М×М элементов, [Г(х,y)]_M×M - матрица прямого дискретного косинусного преобразования, [Г(х,у)]'_M×M - матрица обратного дискретного косинусного преобразования (см. фиг.2).

Наиболее информативными, с точки зрения восстановления передаваемого видеоизображения, являются коэффициенты двумерного дискретно-косинусного преобразования с максимальной энергией, располагающиеся в левом верхнем квадранте матрицы коэффициентов двумерного дискретно-косинусного преобразования размером М×М элементов (см. фиг.11a). Их выделяют, формируя матрицу коэффициентов двумерного дискретно-косинусного преобразования размером N×N элементов (в дальнейшем обозначим ее как [A]_N×N), на основании выражения A(i,j)=L(i,j), где i=1, 2, ..., N, j=1, 2, ..., N, L(i,j)-i,j-й элемент матрицы коэффициентов двумерного дискретного косинусного преобразования неподвижного полутонового видеоизображения размером M×M элементов, A (i,j)-i,j-й элемент матрицы коэффициентов двумерного дискретно-косинусного преобразования неподвижного полутонового видеоизображения размером N×N элементов, причем выбирают N≤M (см. фиг.3).

Величина коэффициентов двумерного дискретно-косинусного преобразования в большой степени зависит от их порядкового номера, о чем можно судить исходя из графика (см. фиг.11б), где по оси абсцисс отложены порядковые номера коэффициентов первой строки матрицы коэффициентов двумерного дискретно-косинусного преобразования размером М×М элементов, а по оси ординат - их абсолютные значения. Для того чтобы устранить зависимость величины элементов матрицы коэффициентов двумерного дискретно-косинусного преобразования размером N×N элементов от их местоположения в матрице и в дальнейшем более точно их аппроксимировать, необходимо произвести операцию нормирования. Суть данной операции заключается в том, что на передающей и приемной сторонах идентично формируют нормировочную матрицу размером N×N элементов (в дальнейшем обозначим ее как [С]_N×N), элементы которой C(i,j) вычисляют по формуле (см. фиг.4), полученную опытным путем. При этом учтена особенность матрицы коэффициентов двумерного дискретно-косинусного преобразования размером М×М элементов, заключающаяся в расположении коэффициентов с максимальной энергией в левом верхнем квадранте и зависимости значений коэффициентов от их порядкового номера (i и j).

Затем формируют матрицу нормированных значений двумерного дискретно-косинусного преобразования размером N×N элементов (в дальнейшем обозначим ее как [V]_N×N) путем умножения каждого элемента A(i,j) матрицы коэффициентов двумерного дискретно-косинусного преобразования неподвижного полутонового видеоизображения размером N×N элементов на соответствующий ему элемент C(i,j) нормировочной матрицы размером N×N элементов (см. фиг.5).

Далее, аналогично способу-прототипу используют подход, основанный на представлении g-й - результирующей матрицы размером NxN элементов (в дальнейшем обозначим ее как ) в виде произведения трех матриц: преобразованной прямоугольной матрицы размером N×m элементов (в дальнейшем обозначим ее как ), случайной квадратной матрицы размером m×m элементов [B]_m×m и преобразованной прямоугольной матрицы размером m×N элементов (в дальнейшем обозначим ее как ) (см. фиг.8): где [Y_pr(g)] и [X_pr(g)] находятся таким образом, чтобы суммарная матрица размером N×N элементов (в дальнейшем обозначим ее как [V_s]_N×N) полученная путем суммирования соответствующих элементов всех матриц и деления на k, была наиболее близкой по заданному критерию к матрице [V]_N×N.

Матрицы и формируют путем суммирования по модулю 2 случайной прямоугольной матрицы [Е]_N×m со случайной ключевой матрицей [Y_кл(g)]_N×m и транспонированной прямоугольной матрицы [Е]^T _N×m со случайной ключевой матрицей [X_кл(g)]_m×N соответственно, где матрицы [Y_кл(g)]_N×m и [X_кл(g)]_m×N являются идентично генерируемыми на передающей и приемной сторонах размерами N×m и m×N соответственно (см. фиг.7в, 7 г), где знак означает суммирование по модулю 2.

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

- элементы матриц и принимают значения в диапазоне от нуля до единицы;

- ненулевые элементы каждой строки матрицы равны между собой и в сумме образуют единицу;

- ненулевые элементы каждого столбца матрицы равны между собой и в сумме образуют единицу;

При таких ограничениях если элементы каждой строки матрицы умножить на количество ненулевых элементов в этой строке, то будет получена матрица [Y_pr(g)]_N×m элементы которой определены только на множестве "1" и "0". Аналогично, если элементы каждого столбца матрицы умножить на количество ненулевых элементов в столбце, то будет получена матрица [X_pr(g)]_m×N элементы которой определены только на множестве "1" и "0".

Процедура, реализующая поиск на передающей стороне оптимальных матриц и подробно описана в способе-прототипе (см. патент РФ №2244963, МПК⁷ Н 04 N 7/30, от 2005 г.).

Таким образом, представление матрицы нормированных значений двумерного дискретно-косинусного преобразования размером N×N элементов [V]_N×N в цифровом виде на передающей стороне осуществляют на основе генерирования множества нулевых и единичных элементов в виде случайной прямоугольной матрицы размером N×m (матрица [E]_N×N) (^см- фиг.7а, 7б) и k случайных ключевых матриц размером m×N и N×m элементов (матрицы [X_кл(g)] и [Y_кл(g)]_N×m (см. фиг.6б, 6г) Затем случайные прямоугольные матрицы [X(g)_m×N] и [Y(g)]_N×m преобразуют путем деления элементов каждой строки случайной прямоугольной матрицы размером N×m элементов на сумму единиц соответствующей строки, т.е. ее вес - v_y(g) (см. книгу: Э. Берлекэмп. Алгебраическая теория кодирования. - М.: Мир, 1971. с.12) (см. фиг.7д) и деления элементов каждого столбца случайной прямоугольной матрицы размером m×N элементов на сумму единиц соответствующего столбца, т.е. его вес - v_x(g). Тем самым формируют матрицы и (см. фиг.7д, 7е).

Аналогично способу-прототипу вычисляют k результирующих матриц размером N×N элементов, т.е. путем последовательного перемножения полученной после преобразования прямоугольной матрицы размером N×m элементов случайной квадратной матрицы размером m×m элементов [B]_m×m и полученной после преобразования прямоугольной матрицы размером m×N элементов (см. фиг.8).

Далее полученные результирующие матрицы суммируют по правилу где - i,j - элемент g-й результирующей матрицы.

Матрица [V_s]_N×N должна быть наиболее близкой к матрице [V]_N×N по некоторому критерию. Известно (см., например, книгу: У.Претт. Цифровая обработка изображений. Часть I. - М.: Мир, 1982, с.121-127), что одним из основных объективных критериев близости является среднеквадратическая ошибка. Минимизируя среднеквадратическую ошибку добиваются минимальных расхождений между матрицами [V]_N×N и [V_s]_N×N. Поэтому, рассчитывают сумму квадратов разностей между элементами суммарной результирующей матрицы размером N×N элементов [V_s]_N×N и соответствующими им элементами матрицы нормированных значений двумерного дискретно-косинусного преобразования размером N×N элементов [V]_N×N. Затем последовательно инвертируют каждый элемент случайной прямоугольной матрицы размером N×m элементов (см. фиг.9) и преобразуют их аналогичным образом, как было описано при преобразовании матриц [Y(g)] _N×m и [X(g)]_m×N (см. фиг.7б, 7в, 7г, 7д, 7е). Последовательно перемножают полученные после преобразования k случайных прямоугольных матриц размером Nxm элементов, случайную квадратную матрицу размером m×m элементов и полученные после преобразования k случайных прямоугольных матриц размером m×N элементов. Полученные k результирующие матрицы размером N×N элементов поэлементно суммируют и усредняют по формуле

Поскольку в матрице [E]_N×m содержался инвертированный элемент, что после преобразования привело к изменению значений элементов матриц [Y(g)] _N×m и [X(g)]_m×N и соответственно привело к изменениям матриц и изменятся значения элементов результирующей матрицы тем самым изменяя значения матрицы Затем для оценки степени приближения матрицы к [V]_N×N повторно рассчитывают сумму квадратов разностей между элементами суммарной результирующей матрицы размером N×N элементов и элементами матрицы нормированных значений двумерного дискретно-косинусного преобразования размером N×N элементов. Затем вычитают полученную сумму квадратов разности от аналогичной суммы, полученной на предыдущем шаге. В случае положительной разности, т.е. уменьшения среднеквадратической ошибки, сохраняют инвертированное значение элемента, а в противном случае - выполняют его повторную инверсию.

Подобным образом производят инверсию всех битов в матрицы [Е]_N×m и добиваются минимальной среднеквадратической ошибки между матрицами и [V]_N×N, что однозначно указывает на оптимальность сформированных матриц [Y(g)] _N×m, [X(g)]_m×N и и т.e. достижение наилучшего качества при заданном фиксированном объеме передаваемой информации.

Передают множество нулевых и единичных элементов случайной прямоугольной матрицы [Е]_N×m по каналу связи (см. фиг.10). На фиг.10 знак · обозначает перемножение матриц.

На приемной стороне принимают из канала связи множество нулевых и единичных элементов случайной прямоугольной матрицы [E]_N×m. Затем вычисляют матрицы [Y(g)]_N×m и [X(g)]_m×N путем суммирования по модулю 2 матрицы [E]_N×m на матрицу [Y_кл(g)]_N×m и суммирования по модулю 2 транспонированной матрицы [E]_N×m на матрицу [X_кл(g)]_m×N соответственно. Затем преобразуют матрицы [Y(g)]_N×m и [X(g)]_m×N путем деления элементов каждой строки прямоугольной матрицы размером N×m элементов на сумму единиц соответствующей строки, т.е. ее вес v_y (см. фиг.7е) и деления элементов каждого столбца прямоугольной матрицы размером m×N элементов на сумму единиц соответствующего столбца, т.е. его вес v_x (см. фиг.7д). Тем самым на приемной стороне формируют матрицы и

Формируют k восстановленных результирующих матриц размером N×N элементов путем последовательного перемножения k случайных прямоугольных матриц случайной квадратной матрицы [B]_m×m и k случайных прямоугольных матрицы (см. фиг.8). Затем формируют матрицу восстановленных нормированных значений двумерного дискретно-косинусного преобразования размером N×N элементов путем суммирования и усреднения k матриц восстановленных результирующих матриц размером N×N элементов по формуле

Для получения восстановленных коэффициентов реальной размерности необходимо произвести операцию денормирования. Учитывая, что на приемной стороне была сформирована нормировочная матрица [C]_N×N, матрицу восстановленных значений двумерного дискретно-косинусного преобразования размером N×N элементов (в дальнейшем обозначим ее как _M×M) формируют путем деления значения каждого i,j-го элемента матрицы на соответствующий элемент нормировочной матрицы размером N×N элементов (см. фиг.12).

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

Далее формируют матрицу восстановленных квантованных отсчетов неподвижного полутонового видеоизображения путем перемножения транспонированной матрицы дискретно-косинусного преобразования размером М×М элементов на матрицу восстановленных коэффициентов двумерного дискретно-косинусного преобразования размером М×М элементов и на матрицу дискретно-косинусного преобразования размером М×М элементов (см. фиг.14), т.е. на основании формулы: [(х,y)]_M×M=[Г(x,у)]'_M×M×[(x,y)]_M×M×[Г(x,y)]_M×M, где - матрица восстановленных квантованных отсчетов неподвижного полутонового видеоизображения размером МхМ элементов.

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

Для оценки возможности достижения сформулированного технического результата при использовании заявленного способа сжатия и восстановления сообщений было проведено имитационное моделирование на ПЭВМ. Размер случайной квадратной матрицы [B]_m×m составлял 128×128 элементов. Такой размер матрицы [B]_m×m выбран исходя из того, что в качестве исходного сообщения использовано неподвижное полутоновое видеоизображение размером 512×512 пикселов. В предлагаемом способе высокая степень сжатия исходного сообщения достигнута за счет того, что для формирования на приемной стороне неподвижного полутонового видеоизображения в цифровой канал связи необходимо передать количество двоичных единиц, определяемое размерами матрицы [E]_N×m. Для повышения помехоустойчивости использовался подход, который

основан на методе накопления, компенсация ошибки происходила за счет суммирования и усреднения k образов восстановленного сообщения, которые формировались на основе известных на передающей и приемной сторонах k случайных взаимонезависимых ключевых матриц и полученной из канала связи одной матрицы [E]_N×m, таким образом метод накопления был реализован без многократной передачи матрицы [E]_N×m. В общем случае матрица [E]_N×m является прямоугольной. Но в ходе имитационного моделирования N взята равной 128, а m=128. Такая величина N обусловлена требованиями к качеству восстановленного видеоизображения. Практические исследования показывают, что при оставлении 1/16 спектральных коэффициентов двумерного дискретно-косинусного преобразования из левого верхнего квадранта матрицы коэффициентов двумерного дискретно-косинусного преобразования размером 512×512 элементов пиковое отношение сигнал/шум для исходного и восстановленного видеоизображения составляет порядка 30 дБ. В ходе имитационного моделирования параметр число k было выбрано опытным путем, k=12, уменьшение этого параметра приводит к резкому уменьшению величины компенсации ошибки. При увеличение данного параметра выигрыш увеличивается незначительно, но качество восстановления неподвижного полутонового изображения снижается.

Достигаемый коэффициент сжатия может быть найден по формуле:

Цифра 8 в числителе указанной формулы говорит о том, что для кодирования впрямую неподвижного полутонового видеоизображения, т.е. значение каждого пиксела лежит в диапазоне 0÷255, требуется 8 бит. При выборе N=128, m=128 и М=512 результирующий коэффициент сжатия составил 16 раз. При использовании способа-прототипа для сжатия сообщений результирующий коэффициент сжатия составил 16 раз при пиковом отношении сигнал/шум порядка 29,5 дБ, но при имитации ошибок в канале связи качество восстановления составило 16 дБ. Объективная оценка качества восстановленного при помощи заявленного способа видеоизображения показывает, что пиковое отношение сигнал/шум для исходного и восстановленного видеоизображений составляет 28,4 дБ, а при имитации ошибок в канале связи 10^-2 пиковое отношение сигнал/шум для исходного и восстановленного видеоизображения составляет порядка 25,8 дБ. Полученные восстановленные видеоизображения изображены на фиг.16.

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

Изобретение относится к области электросвязи, а именно к методам цифровых вычислений и обработки данных с сокращением избыточности передаваемой информации. Сущность способа сжатия и восстановления сообщений состоит в том, что предварительно на передающей и приемной сторонах идентично генерируют случайную квадратную матрицу размером m×m элементов и по k случайных ключевых матриц размером N×m и m×N элементов и формируют матрицу квантованных отсчетов неподвижного полутонового видеоизображения размером М×М элементов. Полученные матрицы преобразуют к цифровому виду на основе суммирования и усреднения А-образов, каждый образ представляют в виде произведения трех матриц: двух случайных прямоугольных матриц размером N×m и m×N элементов и случайной квадратной матрицы размером m×m элементов. В канал связи передают элементы прямоугольной матрицы размером N×m элементов. На основе принятой из канала связи случайной прямоугольной матрицы размером N×m элементов, а также случайной квадратной матрицы размером m×m элементов и случайной прямоугольной матрицы m×N элементов формируют матрицу восстановленных квантованных отсчетов неподвижного полутонового видеоизображения размером М×М элементов, из которой формируют неподвижное полутоновое видеоизображение. Технический результат - повышение устойчивости к ошибкам в цифровом канале связи при сжатии и восстановлении сообщений. 1 з.п. ф-лы, 26 ил.

1. Способ сжатия и восстановления сообщений, заключающийся в том, что предварительно на передающей и приемной сторонах идентично генерируют случайную квадратную матрицу размером m×m элементов, каждый элемент которой принадлежит диапазону -500 ÷ +500, генерируют по k случайных ключевых матриц размером N×m и m×N элементов, формируют нормировочную матрицу размером N×N элементов, элементы которой C(i, j) вычисляют по формуле

где i=1, 2, ..., N, j=1, 2, ..., N, формируют матрицу квантованных отсчетов неподвижного полутонового видеоизображения размером M×M элементов, в которой каждому ее элементу S(x,y) присваивают квантованное значение соответствующего пиксела неподвижного полутонового видеоизображения, размером М×М пикселов, где х=1, 2, ..., М; у=1, 2, ...,М, формируют матрицу коэффициентов двумерного дискретно-косинусного преобразования размером М×М элементов путем последовательного перемножения матрицы дискретно-косинусного преобразования размером M×M элементов на матрицу квантованных отсчетов неподвижного полутонового видеоизображения размером М×М элементов и на транспонированную матрицу дискретно-косинусного преобразования размером М×М элементов, формируют матрицу коэффициентов двумерного дискретно-косинусного преобразования размером N×N элементов, по формуле A(i,j)=L(i,j), где L(i,j)-i,j-й элемент матрицы коэффициентов двумерного дискретного косинусного преобразования размером М×М элементов, A(i,j)-i,j-й элемент матрицы коэффициентов двумерного дискретно-косинусного преобразования размером N×N элементов, причем выбирают N×M, после чего формируют матрицу нормированных значений размером N×N элементов, путем умножение каждого коэффициента матрицы коэффициентов двумерного дискретно-косинусного преобразования размером N×N элементов A(i,j) на соответствующий ему элемент нормировочной матрицы размером N×N элементов, генерируют случайную прямоугольную матрицу размером N×m элементов, а в качестве случайной прямоугольной матрицы размером m×N элементов принимают транспонированную случайную прямоугольную матрицу размером N×m элементов, затем каждую из ключевых матриц размерами N×m и m×N элементов суммируют по модулю 2 соответственно с прямой и транспонированной случайной прямоугольной матрицей размерами N×m и m×N элементов, преобразуют полученные матрицы путем деления элементов каждой строки случайной прямоугольной матрицы размером N×m элементов на сумму единиц соответствующей строки и деления элементов каждого столбца случайной прямоугольной матрицы размером m×N элементов на сумму единиц соответствующего столбца, вычисляют k результирующих матриц V(g), где g=1, 2, ..., k, размером N×N элементов, путем последовательного умножения k преобразованных случайных прямоугольных матриц размером N×m на случайную квадратную матрицу размером m×m и на k преобразованных случайных прямоугольных матриц размером m×N элементов, последовательно инвертируют каждый элемент случайных прямоугольных матриц размерами N×m и m×N элементов, и после инверсии преобразуют их путем деления элементов каждой строки случайной прямоугольной матрицы с инвертированным элементом размером N×m элементов на сумму единиц соответствующей строки и деления элементов каждого столбца случайной прямоугольной матрицы с инвертированным элементом размером m×N элементов на сумму единиц соответствующего столбца, повторно вычисляют k результирующих матриц размером N×N элементов, путем последовательного умножения k преобразованных случайных прямоугольных матриц с инвертированным элементом размером N×m на случайную квадратную матрицу размером m×m и на k преобразованных случайных прямоугольных матриц с инвертированным элементом размером m×N, передают по каналу связи случайную прямоугольную матрицу размером N×m, принимают из канала связи эту матрицу, затем каждую из ключевых матриц размерами N×m и m×N элементов суммируют по модулю 2 соответственно с прямой и транспонированной случайными прямоугольными матрицами размерами N×m и m×N элементов, преобразуют принятые случайные прямоугольные матрицы размера N×m и m×N путем деления элементов строки каждой случайной прямоугольной матрицы размером N×m элементов на сумму единиц соответствующей строки и деления элементов каждого столбца случайной прямоугольной матрицы размером m×N элементов на сумму единиц соответствующего столбца, вычисляют k восстановленных результирующих матриц (g), где g=1, 2, ..., k размера N×N элементов, путем последовательного умножения k преобразованных случайных прямоугольных матриц размером N×m на случайную квадратную матрицу размером m×m и на k преобразованных случайных прямоугольных матриц размером m×N соответственно, матрицу восстановленных коэффициентов размером N×N элементов дополняют нулями до размеров М×М элементов, получают матрицу восстановленных коэффициентов дискретно-косинусного преобразования размером М×М элементов, восстанавливают матрицу неподвижного полутоновых изображения, путем последовательного перемножения транспонированной матрицы дискретно-косинусного преобразования размером М×М элементов на матрицу восстановленных коэффициентов двумерного дискретно-косинусного преобразования размером М×М элементов и на матрицу дискретно-косинусного преобразования размером М×М элементов, формируют цифровой информационный сигнал, каждому пикселу неподвижного полутонового видеоизображения присваивают значение соответствующего элемента матрицы восстановленных квантованных отсчетов неподвижных полутоновых видеоизображений размером М×М элементов, отличающийся тем, что после вычисления k результирующих матриц, вычисляют суммарную матрицу размером N×N элементов V_s по формуле

затем вычисляют среднеквадратическую ошибку между элементами матрицы нормированных значений размером N×N элементов и элементами суммарной матрицы V_s, размером N×N элементов, а после инверсии каждого элемента случайных прямоугольных матриц размерами N×m и m×N повторно вычисляют k результирующих матриц, суммарную матрицу V_s и среднеквадратическую ошибку между элементами матрицы нормированных значений размером N×N элементов и элементами повторно вычисленной суммарной матрицы V_s размером N×N элементов, а полученную среднеквадратическую ошибку вычитают от предыдущей среднеквадратической ошибки и в случае положительной разности запоминают инвертированный элемент, а после вычисления k восстановленных результирующих матриц (g) вычисляют восстановленную суммарную матрицу размером N×N элементов _s по формуле