Устройство доменного вычисления коэффициентов прямого двухмерного вейвлет-преобразования Хаара

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДОМЕННОГО ВЫЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ ПРЯМОГО ДВУХМЕРНОГО ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ ХААРА(71) Заявитель Учреждение образования Белорусский государственный университет информатики и радиоэлектроники(72) Авторы Борискевич Анатолий Антонович Цветков Виктор Юрьевич Борискевич Илья Анатольевич Руис Эченагусия Луис Альфонсо(73) Патентообладатель Учреждение образования Белорусский государственный университет информатики и радиоэлектроники(57) Устройство доменного вычисления коэффициентов прямого двухмерного вейвлетпреобразования Хаара, состоящее из мультиплексора, регистра сдвига, трех блоков двухэлементного преобразования Хаара, двух регистров и стека для хранения промежуточных значений аппроксимирующих вейвлет-коэффициентов, причем первый вход мультиплексора является входом устройства, выходы второго блока двухэлементного преобразования Хаара и первый выход третьего блока двухэлементного преобразования Хаара являются выходами устройства, выход мультиплексора соединен со входом регистра сдвига, выходы регистра сдвига соединены со входами первого блока двухэлементного преобразования Хаара, первый выход первого блока двухэлементного преобразования Хаара соединен 98882014.02.28 со вторым входом второго блока двухэлементного преобразования Хаара, второй выход первого блока двухэлементного преобразования Хаара соединен со вторым входом третьего блока двухэлементного преобразования Хаара, отличающееся тем, что содержит два регистра и стек для хранения промежуточных значений аппроксимирующих вейвлеткоэффициентов, первый выход первого блока двухэлементного преобразования Хаара соединен со входом первого регистра, второй выход первого блока двухэлементного преобразования Хаара соединен со входом второго регистра, выход первого регистра соединен с первым входом второго блока двухэлементного преобразования Хаара, выход второго регистра соединен с первым входом третьего блока двухэлементного преобразования Хаара, второй выход третьего блока двухэлементного преобразования Хаара соединен со входом стека, выход стека соединен со вторым входом мультиплексора.(56) 1.,2/18,. - 2007. - . 169-177. 2... 2-/ .17. - 2003. - . 228-232. 3. Борискевич А.А., Цветков В.Ю. Компактное описание и формирование -мерных рекурсивных разверток // Информатика. - 2007. -2. - С. 5-15. Полезная модель относится к области цифровой обработки сигналов и может быть использована в системах обработки изображений для вычисления коэффициентов прямого двухмерного вейвлет-преобразования Хаара. Целью полезной модели является повышение скорости вычисления коэффициентов прямого двухмерного вейвлет-преобразования Хаара и сокращение объема оперативной памяти для хранения промежуточных значений вейвлет-коэффициентов. Данная цель достигается введением двух регистров и стека для хранения аппроксимирующих вейвлет-коэффициентов, а также подачи на вход устройства пикселов изображения в порядке, задаваемом траекторией рекурсивной -развертки. Известно устройство вычисления коэффициентов прямого двухмерного вейвлетпреобразования Хаара на основе метода(-), использующее обработку сначала строк, а затем столбцов пикселов изображения и аппроксимирующих вейвлет-коэффициентов, требующее буферизации всех промежуточных значений вейвлет-коэффициентов, полученных в результате обработки строк, и состоящее из блоков двухэлементного преобразования Хаара, а также оперативной памяти для хранения промежуточных значений вейвлет-коэффициентов 1. Однако данное устройство обладает низким быстродействием скорость вычислений резко падает с увеличением размера изображения из-за быстрого роста числа операций обращения к оперативной памяти. Наиболее близким к предлагаемой полезной модели является устройство вычисления коэффициентов прямого двухмерного вейвлет-преобразования Хаара на основе метода(-), использующее поочередную обработку строк и неполных столбцов пикселов изображения и аппроксимирующих вейвлет-коэффициентов со сдвигом вдоль столбцов, позволяющее сократить объем оперативной памяти и число операций доступа к ней за счет буферизации со сдвигом только части строк массива промежуточных значений вейвлет-коэффициентов 2 и состоящее из мультиплексора, трех регистров сдвига, трех блоков двухэлементного преобразования Хаара и оперативной памяти для хранения промежуточных значений аппроксимирующих вейвлет-коэффициентов,причем первый вход мультиплексора является входом устройства, выходы второго блока 2 98882014.02.28 двухэлементного преобразования Хаара и первый выход третьего блока двухэлементного преобразования Хаара являются выходами устройства, выход мультиплексора соединен со входом первого регистра сдвига, выходы первого регистра сдвига соединены со входами первого блока двухэлементного преобразования Хаара, первый выход первого блока двухэлементного преобразования Хаара соединен со входом второго регистра сдвига и вторым входом второго блока двухэлементного преобразования Хаара, второй выход первого блока двухэлементного преобразования Хаара соединен со входом третьего регистра сдвига и вторым входом третьего блока двухэлементного преобразования Хаара, выход второго регистра сдвига соединен с первым входом второго блока двухэлементного преобразования Хаара, выход третьего регистра сдвига соединен с первым входом третьего блока двухэлементного преобразования Хаара, второй выход третьего блока двухэлементного преобразования Хаара соединен со входом оперативной памяти, выход оперативной памяти соединен со вторым входом мультиплексора. Однако данное устройство использует буферизацию строк промежуточных значений вейвлет-коэффициентов и всех промежуточных значений аппроксимирующих вейвлет-коэффициентов, что приводит к снижению скорости вейвлет-преобразования и росту объема оперативной памяти с увеличением размера изображения. Техническая задача, на решение которой направлена полезная модель, - создание устройства для быстрого вычисления коэффициентов прямого двухмерного вейвлетпреобразования Хаара, использующего доменную обработку пикселов изображения и аппроксимирующих вейвлет-коэффициентов. Техническим результатом, который может быть получен при использовании данной полезной модели, является повышение быстродействия и минимизация объема оперативной памяти для хранения промежуточных значений вейвлет-коэффициентов по сравнению с известными устройствами вычисления коэффициентов прямого двухмерного вейвлет-преобразования Хаара. Поставленная задача решается тем, что предлагается устройство доменного вычисления коэффициентов прямого двухмерного вейвлет-преобразования Хаара, состоящее из мультиплексора, регистра сдвига, трех блоков двухэлементного преобразования Хаара,двух регистров и стека для хранения промежуточных значений аппроксимирующих вейвлет-коэффициентов, причем первый вход мультиплексора является входом устройства,выходы второго блока двухэлементного преобразования Хаара и первый выход третьего блока двухэлементного преобразования Хаара являются выходами устройства, выход мультиплексора соединен со входом регистра сдвига, выходы регистра сдвига соединены со входами первого блока двухэлементного преобразования Хаара, первый выход первого блока двухэлементного преобразования Хаара соединен со вторым входом второго блока двухэлементного преобразования Хаара, второй выход первого блока двухэлементного преобразования Хаара соединен со вторым входом третьего блока двухэлементного преобразования Хаара, и отличающееся тем, что содержит два регистра и стек для хранения промежуточных значений аппроксимирующих вейвлет-коэффициентов, первый выход первого блока двухэлементного преобразования Хаара соединен со входом первого регистра, второй выход первого блока двухэлементного преобразования Хаара соединен со входом второго регистра, выход первого регистра соединен с первым входом второго блока двухэлементного преобразования Хаара, выход второго регистра соединен с первым входом третьего блока двухэлементного преобразования Хаара, второй выход третьего блока двухэлементного преобразования Хаара соединен со входом стека, выход стека соединен со вторым входом мультиплексора. Сущность заявляемой полезной модели заключается в том, что предлагаемое устройство позволяет осуществить быстрое преобразование двухмерного массива пикселов в многоуровневую последовательность аппроксимирующих и детализирующих вейвлеткоэффициентов Хаара. 98882014.02.28 Предложение иллюстрируется следующими фигурами. На фиг. 1 представлена структурная схема устройства доменного вычисления коэффициентов прямого двухмерного вейвлет-преобразования Хаара, на фиг. 2 - траектория рекурсивной -развертки, на фиг. 3 реверсивный порядок и последовательность обработки доменов, на фиг. 4 - структурная схема блока двухэлементного преобразования Хаара, на фиг. 5 - структурные схемы блоков вычисления аппроксимирующих и детализирующих коэффициентов вейвлет-преобразования Хаара, на фиг. 6 - фрагмент временной диаграммы записи/считывания стека для хранения промежуточных значений аппроксимирующих вейвлет-коэффициентов, на фиг. 7 - зависимость объемабуферной памяти от числаисходных значений в строке для предложенного устройства и устройств на основе методови . Устройство доменного вычисления прямого двухмерного вейвлет-преобразования Хаара состоит из мультиплексора (1), регистра сдвига (2), трех блоков двухэлементного преобразования Хаара (3, 6, 7), двух регистров (4, 5) и стека для хранения промежуточных значений аппроксимирующих вейвлет-коэффициентов (8), причем первый выход 11 первого блока двухэлементного преобразования Хаара соединен со входом 13 первого регистра, второй выход 12 первого блока двухэлементного преобразования Хаара соединен со входом 14 второго регистра, выход 15 первого регистра соединен с первым входом второго блока двухэлементного преобразования Хаара, выход 16 второго регистра соединен с первым входом третьего блока двухэлементного преобразования Хаара, второй выход 17 третьего блока двухэлементного преобразования Хаара соединен со входом 18 стека, выход 19 стека соединен со вторым входом 10 мультиплексора (фиг. 1). Необходимым условием для функционирования предложенного устройства доменного вычисления прямого двухмерного вейвлет-преобразования Хаара является поступление на вход мультиплексора векторазначений матрицы исходного двухмерного сигнала В, упорядоченного по закону рекурсивной -перестановки 3. Матрица( ,) ( 0,1, 0,1) рекурсивной -перестановки преобразует матрицу( ,) ( 0,1, 0,1) исходных значений размеромв вектор(0,1) переставленных исходных значений длиной, где(,( - -й компонент вектораи- координаты перестановки, получаемые из векторов(0,1) и( 0,1) координат перестановок, формируемых на основе матрицырекурсивной -перестановки. На фиг. 2 представлен пример траектории рекур 1 1 4 5 сивной -развертки, соответствующей матрице 2 3 6 7 рекурсивной -пере 8 9 12 13 10 11 14 15 становки размером 44. Векторпереставленных исходных значений состоит из следующих друг за другом четверок, принадлежащих соответствующим доменным блокам (фиг. 3). Необходимым условием формирования вектораявляется соответствие размеров матриц исходных значенийирекурсивной -перестановки при выполнении равенства 2. Устройство доменного вычисления прямого двухмерного вейвлет-преобразования Хаара работает следующим образом. На мультиплексор (1) поступают элементы( ) (,) -го доменного вейвлет-блока( )(,)-го уровня вейвлет-декомпозиции, который формируется из че тырех элементов векторапереставленных исходных значений (вход 9) или векторапромежуточных аппроксимирующих вейвлет-коэффициентов (вход 10) в соответствии с выражением 4(1,1)(1),(1,0)(2),(0,1)(3),(0,0)(4) при (1)(( 41)0), где- логическая операция И- операция поразрядного логического умножения 0,1 - номер доменного вейвлет-блока 22(-) - число доменных вейвлет-блоков на -м уровне вейвлет-декомпозиции. С мультиплексора (1) последовательность( ) (,) записывается в регистр сдвига (2), из которого элементы( ) (,) поступают в первый блок двухэлементного преобразования Хаара (3), где производится вычисление горизонтальных внутридоменных вейвлет-коэффициентов. Структурная схема блока двухэлементного преобразования Хаара представлена на фиг. 4. Аппроксимирующийи детализирующийвейвлет-коэффициенты вычисляются для каждой -й строки домена(1)1)4 -1)0, где- логическая операция ИЛИ. Структурная схема блоков вычисления аппроксимирующих и детализирующих коэффициентов вейвлетпреобразования Хаара представлена на фиг. 5. Промежуточные вейвлет-коэффициенты записываются в регистры хранения (4, 5), из которых они поступают на второй и третий блоки одномерного вейвлет-преобразования Хаара (6, 7), где производится вычисление вертикальных внутридоменных вейвлет-коэффициентов. Аппроксимирующийи детализирующие , ,вейвлет-коэффициенты вычисляются с помощью системы соотношений(1)(0),(0),Аппроксимирующий вейвлет-коэффициентпоступает в стек (8). Фрагмент временной диаграммы записи/считывания стека длятактов представлен на фиг. 6. Детализирующие вейвлет-коэффициенты , ,поступают на выход устройства. На последнем уровне вейвлет-декомпозиции на выход схемы также поступает аппроксимирующий вейвлеткоэффициент . В результате вычисления двухмерного дискретного вейвлет-преобразования Хаара на выходе устройства формируются вектораи , содержащие соответственно результирующие аппроксимирующиеи детализирующие , ,вейвлет-коэффициенты. Значения вейвлет-коэффициентов, вычисляемые с помощью предложенного устройства,в точности совпадают со значениями вейвлет-коэффициентов, получаемыми с помощью устройств на основе методови , но переставлены согласно рекурсивной перестановки и последовательности обработки стека, что не влияет на результат обратного вейвлет-преобразования. Поэтому для сравнения эффективности данных методов используются зависимости размеров ,ибуферов от размеров матрицы исходных значений (фиг. 7). Технико-экономическое преимущество предложенного устройства доменного вычисления коэффициентов прямого вейвлет-преобразования Хаара по сравнению с прототипом заключается в повышении быстродействия за счет минимизации объема буферной памяти для временного хранения промежуточных аппроксимирующих вейвлет-коэффициентов и сокращения числа обращений к ней. При размере матрицы исходных значений 6464 предложенное устройство требует объема буферной памяти в 6,7 раза меньше по сравне 5 98882014.02.28 нию с устройством на основе метода . Получаемый при этом выигрыш в быстродействии в первом приближении можно считать пропорциональным выигрышу в объеме буферной памяти (т.к. на каждую ячейку приходятся одна операция записи и одна операция считывания). При размере матрицы исходных значений 512512 выигрыш в объеме буферной памяти по отношению к прототипу увеличивается и составляет примерно 33 раза. Таким образом, предложенное устройство обеспечивает компактную аппаратную реализацию прямого вейвлет-преобразования Хаара и высокую скорость вычислений. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 7