Способ формирования целочисленных неортогональных декоррелирующих матриц заданных размеров и устройство для его осуществления
Владельцы патента RU 2485592:
Федеральное государственное унитарное предприятие "Государственный научно-исследовательский институт авиационных систем" (RU)
Изобретение относится к технике передачи телевизионных сигналов с использованием кодирования. Техническим результатом является минимизация вычислительной сложности обработки цифровых видеоизображений без потерь декорреляции. Для матричного преобразования видеоизображений, характеризующегося выбором порождающей матрицы и последующим формированием неортогональной матрицы заданного размера, в качестве порождающей матрицы выбирают равнобедренный треугольник Паскаля с размерами боковых сторон, равными заданным размерам формируемой матрицы, а формирование неортогональной матрицы осуществляют посредством заполнения выбранного треугольника Паскаля по строкам, параллельным основанию треугольника. 2 н. и 1 з.п. ф-лы, 3 ил.
Предлагаемое изобретение относится к технике передачи телевизионных сигналов с использованием кодирования и может быть использовано для анализа и восстановления изображения.
Известен способ шифрования с исправлением ошибок канала связи (см., например, патент РФ №2204886 с приоритетом от 19.12.2000 г., МПК: H04K 1/02), заключающийся в зашифровании на передающей стороне данных путем поразрядного суммирования по модулю 2 с гаммой шифра и в расшифровании данных на приемной стороне, причем на передающей стороне гаммой шифра заполняют ключевую матрицу, которую перемножают с вектором данных, а на приемной стороне сортируют элементы полученного кодового вектора в соответствии с порядком десятичного представления столбцов ключевой матрицы, после чего к получившимся кодовым векторам применяют преобразование Адамара, векторы коэффициентов поэлементно складывают и сравнивают с пороговым значением, а из получившегося выбирают максимальное значение вектора.
Недостатком известного способа является невозможность построения целочисленных неортогональных декоррелирующих матриц размерами, заданными числами натурального ряда, поскольку он ориентирован на работу с матрицами Адамара, имеющими размерность, равную натуральной степени числа «два».
Наиболее близким к заявляемому аналогом-прототипом является способ рекуррентного построения ортогональных целочисленных матриц (см., например, Э.Е.Дагман и Г.А.Кухарев, Быстрые дискретные ортогональные преобразования, НАУКА, Сибирское отделение Новосибирск, 1983, с.с.79-86), основанный на формировании последовательности ортогональных целочисленных матриц Хаара, причем началом формирования последовательности ортогональных целочисленных матриц является матрица Адамара размером 2×2, а затем матрицы следующего порядка размером вдвое большее, чем матрицы текущего порядка, формируют с помощью последовательности матричных операций, при которой матрицу текущего порядка умножают кронеккеровским произведением слева на первый вектор-строку матрицы Адамара размером 2×2, потом единичную матрицу размером, равным размеру матрицы текущего порядка, умножают слева на вторую вектор-строку матрицы Адамара размером 2×2, а результат второго кронеккеровского произведения располагают внизу под результатом первого кронеккеровского произведения, образуя матрицу размером вдвое больше текущего, так как площадь полученной на данном шаге формирования матрицы возрастает по сравнению с площадью предыдущей матрицы в 4 раза.
Данный способ также не обеспечивает возможности формирования целочисленных неортогональных декоррелирующих матриц размерами, заданными числами натурального ряда, так как ориентирован на работу с матрицами Адамара, требующими ортогональности обрабатываемого изображения.
Известно устройство для шифрования с исправлением ошибок канала связи (см., например, патент РФ №2204886 с приоритетом от 19.12.2000 г., МПК: H04K 1/02), содержащее на передающей стороне генератор ключа, цифрующий блок, блоки формирования ключевой матрицы и информационного вектора, а на приемной стороне блок сортировки элементов вектора, входом соединенный с выходом блока формирования ключевой матрицы, входом подключенного к выходу генератора ключа, и последовательно связанные блок замены элементов кодового вектора, блок умножения кодового вектора на матрицу Адамара и блок принятия решения, входом соединенный с выходом блока формирования порождающей матрицы, а также блок обратного преобразования, выход которого является информационным выходом устройства.
Известное устройство обеспечивает возможность передачи информации с высокой помехозащищенностью, однако, поскольку оно ориентировано на работу с матрицами Адамара, требующими ортогональности обрабатываемого изображения, формирование с его помощью целочисленных неортогональных декоррелирующих матриц размерами, заданными числами натурального ряда, не представляется возможным.
Наиболее близким аналогом - прототипом является устройство для формирования ортогональных целочисленных матриц (см., например, Э.Е.Дагман и Г.А.Кухарев, Быстрые дискретные ортогональные преобразования, НАУКА, Сибирское отделение Новосибирск, 1983, с.14), содержащее блок порождающей матрицы, а также блок умножения матриц и блок формирования последовательности целочисленных матриц.
Известное устройство не обеспечивает возможности формирования с его помощью целочисленных неортогональных декоррелирующих матриц размерами, заданными числами натурального ряда, так как оно ориентировано на работу с матрицами Адамара.
Задача изобретения состоит в разработке способа формирования целочисленных неортогональных декоррелирующих матриц и устройства для его осуществления, обеспечивающих возможность обработки цифровых видеоизображений любого формата.
Сущность изобретения состоит в том, что в способе формирования целочисленных неортогональных декоррелирующих матриц для матричного преобразования видеоизображений, характеризующемся выбором порождающей матрицы и последующим формированием неортогональной матрицы заданного размера, в качестве порождающей матрицы выбирают равнобедренный треугольник Паскаля с размерами боковых сторон, равными заданным размерам формируемой матрицы, а формирование неортогональной матрицы осуществляют посредством заполнения выбранного треугольника Паскаля по строкам, параллельным основанию треугольника, причем после выбора порождающей матрицы формируют промежуточную квадратную матрицу, своими размерами соответствующую выбранным размерам боковых сторон треугольника Паскаля, и в эту матрицу переносят элементы треугольника Паскаля полосами, параллельными его, например, левой боковой стороне, путем сдвига по столбцам соответственно слева направо, а нулями заполняют элементы этой матрицы, расположенные выше ее главной диагонали, причем для прямого матричного преобразования видеоизображений элементам второй и всех последующих четных диагоналей квадратной матрицы, расположенных выше главной диагонали, присваивают знаки «минус», а для матриц обратного декоррелирующего преобразования этим элементам присваивают знаки «плюс».
Сущность изобретения состоит в том, что в устройство для осуществления способа формирования целочисленных неортогональных декоррелирующих матриц для матричного преобразования видеоизображений, включающего блок формирования порождающей матрицы, дополнительно введены блок формирования промежуточной матрицы, три блока памяти, два блока задания структуры целочисленной неортогональной декоррелирующей матрицы, а также блок управления и коммутатор, при этом выход блока формирования порождающей матрицы соединен с первым входом блока формирования промежуточной матрицы, выходом подключенного к первому входу первого блока памяти, своими вторым и третьим входами соединенного с выходами соответственно первого и второго блоков задания структуры целочисленной неортогональной декоррелирующей матрицы, а первым и вторым выходами подключенного соответственно к первому и второму входам коммутатора, первым и вторым выходами соединенного соответственно с первыми входами второго и третьего блоков памяти, вторыми входами соединенными соответственно с первым и вторым выходами блока управления, третьим, четвертым и пятым выходами подключенного к первым входам соответственно блока формирования порождающей матрицы и первого и второго блоков задания структуры целочисленной неортогональной декоррелирующей матрицы, а шестым, седьмым и восьмым выходами соединенного со вторым и третьими входами соответственно блока формирования промежуточной матрицы, коммутатора и первого блока памяти, четвертым входом подключенного к первому входу устройства для осуществления способа формирования целочисленных неортогональных декоррелирующих матриц для матричного преобразования видеоизображений, вторым, третьим, четвертым и пятым входами соединенного со вторыми входами соответственно блока формирования порождающей матрицы, первого и второго блоков задания структуры целочисленной неортогональной декоррелирующей матрицы и входом блока управления, а первым и вторым выходами подключенного к выходам соответственно второго и третьего блоков памяти.
При этом порождающая матрица блока формирования порождающей матрицы устройства для осуществления способа формирования целочисленных неортогональных декоррелирующих матриц для матричного преобразования видеоизображений выбрана в виде треугольника Паскаля заданных размеров.
Техническим результатом использования предлагаемого изобретения «Способ формирования целочисленных неортогональных декоррелирующих матриц» является возможность обработки цифровых видеоизображений без потерь декорреляции.
Техническим результатом использования предлагаемого изобретения «Устройство для осуществления способа формирования целочисленных неортогональных декоррелирующих матриц» является минимизация вычислительной сложности обработки цифровых видеоизображений.
На фиг.1 представлена блок-схема устройства для осуществления способа формирования целочисленных неортогональных декоррелирующих матриц.
Устройство для осуществления способа формирования целочисленных неортогональных декоррелирующих матриц содержит (фиг.1) блок 1 формирования порождающей матрицы, блок 2 формирования промежуточной матрицы, три блока (соответственно 3, 4 и 5) памяти, два блока (соответственно 6 и 7) задания структуры целочисленной неортогональной декоррелирующей матрицы, а также блок 8 управления и коммутатор 9, при этом выход блока 1 формирования порождающей матрицы соединен с первым входом блока 2 формирования промежуточной матрицы, выходом подключенного к первому входу первого блока 3 памяти, своими вторым и третьим входами соединенного с выходами соответственно первого и второго блоков (соответственно 6 и 7) задания структуры целочисленной неортогональной декоррелирующей матрицы, а первым и вторым выходами подключенного соответственно к первому и второму входам коммутатора 9, первым и вторым выходами соединенного соответственно с первыми входами второго и третьего блоков (соответственно 4 и 5) памяти, вторыми входами соединенными соответственно с первым и вторым выходами блока 8 управления, третьим, четвертым и пятым выходами подключенного к первым входам соответственно блока 1 формирования порождающей матрицы и первого и второго блоков (соответственно 6 и 7) задания структуры целочисленной неортогональной декоррелирующей матрицы, а шестым, седьмым и восьмым выходами соединенного со вторым и третьими входами соответственно блока 2 формирования промежуточной матрицы, коммутатора 9 и первого блока 3 памяти, четвертым входом подключенного к первому входу устройства для осуществления способа формирования целочисленных неортогональных декоррелирующих матриц для матричного преобразования видеоизображений, вторым, третьим, четвертым и пятым входами соединенного со вторыми входами соответственно блока 1 формирования порождающей матрицы, первого и второго блоков (соответственно 6 и 7) задания структуры целочисленной неортогональной декоррелирующей матрицы и входом блока 8 управления, а первым и вторым выходами подключенного к выходам соответственно второго и третьего блоков (соответственно 4 и 5) памяти.
Блок 1 формирования порождающей матрицы и блок 2 формирования промежуточной матрицы выполнены в виде блоков ввода информации вычислительного устройства 386 серии фирмы IBM PC (см., например, B.C.Петрухин и др. Персональные ЭВМ на основе архитектуры INTEL 80386, книга 2, «Инвеско», Обнинск, 1993, с.120), при этом порождающая матрица блока 1 формирования порождающей матрицы устройства для осуществления способа формирования целочисленных неортогональных декоррелирующих матриц для матричного преобразования видеоизображений выбрана в виде треугольника Паскаля (см., например, http://ru.wikipedia.org/wiki/) заданных размеров.
Каждый из блоков (соответственно 3, 4 и 5) памяти выполнен в виде, например, твердотельного диска на Flash-памяти типа SD25B1-350-101 фирмы SanDisk (см., например, справочник «Передовые технологии автоматизации», Москва, апрель 1999, с.25, составитель справочника и поставщик продукции фирма ProSoft, адрес в Web-http://www.prosoft.ru).
Блоки (соответственно 6 и 7) задания структуры целочисленной неортогональной декоррелирующей матрицы выполнены в виде блоков ввода информации вычислительного устройства 386 серии фирмы IBM PC (см., например, B.C.Петрухин и др. «Персональные ЭВМ на основе архитектуры INTEL 80386», книга 2, «Инвеско», Обнинск, 1993, с.120), блок 8 управления выполнен в виде соответствующего устройства (см., например, описание патента РФ №2117326), а коммутатор 9 выполнен в виде, например, демультиплексора МС 14555 (см., например, У.Титце и К.Шенк. Полупроводниковая схемотехника, М., Мир, 1982, с.328-330).
Устройство для осуществления способа формирования целочисленных неортогональных декоррелирующих матриц работает следующим образом:
В блоке 1 формирования порождающей матрицы в качестве порождающей матрицы выбирают и, соответственно, формируют опирающийся на основание равнобедренный треугольник Паскаля с задаваемыми размерами боковых сторон, равными заданным размерам формируемой неортогональной матрицы, которую создают посредством заполнения выбранного треугольника Паскаля по строкам, параллельным основанию треугольника. Затем с помощью блоков 6 и 7 задания структуры целочисленной неортогональной декоррелирующей матрицы в блоке 2 формирования промежуточной матрицы путем сдвига по столбцам, например, слева направо переносят в формируемую промежуточную матрицу элементы треугольника Паскаля полосами, параллельными его, соответственно, левой боковой стороне и осуществляют формирование этой промежуточной матрицы в виде квадратной матрицы, размер которой соответствует (равен) ранее выбранным размерам боковой стороны сформированного треугольника Паскаля, причем элементы этой промежуточной матрицы, расположенные выше ее главной диагонали заполняют нулями (выполняют в виде соответствующих сигналов).
При этом для формирования матрицы прямого матричного преобразования видеоизображений в блоке 3 элементам второй и всех последующих четных диагоналей, расположенных выше главной диагонали квадратной матрицы, присваивают знаки «минус», а при формировании матрицы для обратного декоррелирующего преобразования этим элементам присваивают знаки «плюс».
Сформированную матрицу прямого матричного преобразования через коммутатор 9 переносят в блок 4 памяти, матрицу обратного матричного преобразования видеоизображений переносят в блок 5 памяти, а затем с их помощью производят соответствующую обработку видеоизображений.
В приложении приведены структурные схемы, иллюстрирующие способ формирования целочисленных неортогональных декоррелирующих матриц заданных размеров для обратного (фиг.1 приложения) и прямого (фиг.2. приложения) декоррелирующего преобразования видеоизображений.
1. Способ формирования целочисленных неортогональных декоррелирующих матриц для матричного преобразования видеоизображений, характеризующийся выбором порождающей матрицы и последующим формированием неортогональной матрицы заданного размера, при этом в качестве порождающей матрицы выбирают равнобедренный треугольник Паскаля с размерами боковых сторон, равными заданным размерам формируемой матрицы, а формирование неортогональной матрицы осуществляют посредством заполнения выбранного треугольника Паскаля по строкам, параллельным основанию треугольника, причем после выбора порождающей матрицы формируют промежуточную квадратную матрицу, своими размерами соответствующую выбранным размерам боковых сторон треугольника Паскаля, и в эту матрицу переносят элементы треугольника Паскаля полосами, параллельными его, например, левой боковой стороне, путем сдвига по столбцам соответственно слева направо, а нулями заполняют элементы этой матрицы, расположенные выше ее главной диагонали, причем для прямого матричного преобразования видеоизображений элементам второй и всех последующих четных диагоналей квадратной матрицы, расположенных выше главной диагонали, присваивают знаки «минус», а для матриц обратного декоррелирующего преобразования этим элементам присваивают знаки «плюс».
2. Устройство для осуществления способа формирования целочисленных неортогональных декоррелирующих матриц для матричного преобразования видеоизображений, включающее блок формирования порождающей матрицы, отличающееся тем, что в него дополнительно введены блок формирования промежуточной матрицы, три блока памяти, два блока задания структуры целочисленной неортогональной декоррелирующей матрицы, а также блок управления и коммутатор, при этом выход блока формирования порождающей матрицы соединен с первым входом блока формирования промежуточной матрицы, выходом подключенного к первому входу первого блока памяти, своими вторым и третьим входами соединенного с выходами соответственно первого и второго блоков задания структуры целочисленной неортогональной декоррелирующей матрицы, а первым и вторым выходами подключенного соответственно к первому и второму входам коммутатора, первым и вторым выходами соединенного соответственно с первыми входами второго и третьего блоков памяти, вторыми входами соединенными соответственно с первым и вторым выходами блока управления, третьим, четвертым и пятым выходами подключенного к первым входам соответственно блока формирования порождающей матрицы и первого и второго блоков задания структуры целочисленной неортогональной декоррелирующей матрицы, а шестым, седьмым и восьмым выходами соединенного со вторым и третьими входами соответственно блока формирования промежуточной матрицы, коммутатора и первого блока памяти, четвертым входом подключенного к первому входу устройства для осуществления способа формирования целочисленных неортогональных декоррелирующих матриц для матричного преобразования видеоизображений, вторым, третьим, четвертым и пятым входами соединенного со вторыми входами соответственно блока формирования порождающей матрицы, первого и второго блоков задания структуры целочисленной неортогональной декоррелирующей матрицы и входом блока управления, а первым и вторым выходами подключенного к выходам соответственно второго и третьего блоков памяти.
3. Устройство для осуществления способа формирования целочисленных неортогональных декоррелирующих матриц для матричного преобразования видеоизображений по п.2, отличающееся тем, что порождающая матрица блока формирования порождающей матрицы выбрана в виде треугольника Паскаля заданных размеров.
