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