Устройство для выполнения двухмерного симметричного четного вейвлет-преобразования
Настоящая полезная модель относится вычислительной технике, а именно к области выполнения дискретного вейвлет-преобразования и может использоваться в области обработки изображений. Технической задачей является снижение времени выполнения вейвлет-преобразования для получения заданных размеров низкочастотной составляющей. Указанная задача достигается за счет формирования одной низкочастотной и двух высокочастотных составляющих одномерного вейвлет-преобразования по строкам изображения и одной низкочастотной и восьми высокочастотных составляющих при последующем одномерном вейвлет-преобразовании по столбцам полученных коэффициентов на каждом этапе декомпозиции, что позволяет снизить количество итераций для достижения заданного размера низкочастотной составляющей и соответственно время выполнения. Устройство содержит мультиплексор, двенадцать блоков фильтров и четыре блока буферной памяти. Мультиплексор формирует входной поток на три блока фильтров либо из входного потока, либо из блока буфера памяти, принимающего низкочастотную составляющую с выхода устройства. Три блока фильтров выполняют одномерное вейвлет-преобразование по строкам с формированием одной низкочастотной и двух высокочастотных составляющих. Три блока буферной памяти осуществляют хранение промежуточных данных. Девять блоков фильтров выполняют вейвлет-преобразования по столбцам на основе коэффициентов, получаемых с трех блоков буферной памяти, и формируют одну низкочастотную и восемь высокочастотных составляющих, поступающих на выход устройства. При этом низкочастотная составляющая может поступать в блок буферной памяти для выполнения следующего уровня декомпозиции.
Полезная модель относится вычислительной технике, а именно к области выполнения дискретного вейвлет-преобразования и может использоваться в области обработки изображений.
В настоящее время в алгоритмах обработки сигналов и изображений широко используется вейвлет-преобразование, использующее симметричный нечетный базис Хаара или несимметричный базис Добеши. Дискретное двухмерное вейвлет-преобразование переводит входное изображение в вид более удобный для выполнения ряда алгоритмов обработки изображений.
Указанное двухмерное вейвлет-преобразование производится следующим образом. Каждая цветовая компонента входного изображения представляет собой двухмерный массив, элементы которого определяются координатами (положение в строке и столбце) и яркостью (уровнем интенсивности). Для каждой строки выполняется одномерное преобразование, по сути своей представляющее собой низкочастотную и высокочастотную фильтрацию данных. После этого низкочастотные и высокочастотные коэффициенты подвергаются аналогичным преобразованиям, но уже по столбцам. Таким образом, после двухмерного вейвлет-преобразования изображение представляет собой набор из четырех групп коэффициентов, представляющих интенсивность в различных диапазонах частот. Группа коэффициентов, подвергнутая низкочастотной фильтрации по строкам и столбцам, может быть вновь обработана по описанному выше алгоритму, составляя следующий уровень разложения. Количество подобных итераций определяет число уровней декомпозиции входного изображения. Для обозначения групп коэффициентов используются следующие обозначения: L и Н - низкочастотные и высокочастотные коэффициенты одномерного преобразования; LL LH HL НН - одна низкочастотная и три высокочастотные составляющие двухмерного преобразования. При этом количество низкочастотных коэффициентов LL среди общего количества коэффициентов одного уровня разложения составляет 25%, а суммарное количество высокочастотных коэффициентов LH, HL и НН составляет соответственно 75% [1, 2].
Из существующего уровня техники известны технические решения устройств RU 2342704 С1, опубл. 27.12.2008, US 6424986 B1, Jul. 23, 2002, US 6844830 B1, Jan. 18, 2005, использующие нечетные и несимметричные схемы выполнения вейвлет-преобразования. Недостатком данных устройств является, то что на каждом уровне разложения количество низкочастотных коэффициентов, подвергающихся последующей обработке на следующем уровне разложения является достаточно большим и при заданных размерах формируемой низкочастотной составляющей требуют большее количество итераций, а следовательно и больше время для выполнения.
Наиболее близким к заявленному техническому решению является устройство для выполнения двухмерного дискретного вейвлет-преобразования, приведенное в Ч.Чакрабарти и К.Мамфорда «Эффективные реализации кодеров и декодеров, основанных на двухмерном дискретном вейвлет-преобразовании» (Chaitali Chakrabarti and Clint Mumford «Efficient Realizations of Encoders and Decoders Based on the 2-D Discrete wavelet Transform» IEEE Transactions on very large scale integration (VLSI) systems, Vol 7, No 3, September 1999, Fig 5. pp 293.) включающее:
- мультиплексор сигналов для формирования входного потока на первый и второй блок фильтров либо из входного потока видеоданных либо из третьего блока буфера памяти;
- первый блок фильтров для выполнения одномерного вейвлет-преобразования по строке изображения (по горизонтали) для вычисления низкочастотной составляющей (LL)aL;
- второй блок фильтров для выполнения одномерного вейвлет-преобразования по строке изображения (по горизонтали) для вычисления высокочастотной составляющей (LL)aH;
- первый блок буфера памяти для хранения промежуточных данных, необходимых для вычисления низкочастотных и высокочастотных составляющих (LL)a LL и (LL)aLH при выполнении вейвлет-преобразования по столбцу изображения (по вертикали);
- второй блок буфера памяти для хранения промежуточных данных, необходимых для вычисления низкочастотных и высокочастотных составляющих (LL)aHL и (LL)aHH при выполнении вейвлет-преобразования по столбцу изображения (по вертикали);
- третий блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления низкочастотной составляющей (LL)aLL;
- четвертый блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления высокочастотной составляющей (LL)aLH;
- пятый блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления низкочастотной составляющей (LL)aHL;
- шестой блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления высокочастотной составляющей сигнала (LL)aHH;
- третий блок буфера памяти для хранения низкочастотной составляющей (LL) aLL после выполнения вейвлет-преобразования по столбцу изображения (по вертикали).
Структурная схема указанного устройства иллюстрируется на фиг.1. Устройство содержит: 1 - мультиплексор сигналов для формирования входного потока на первый и второй блок фильтров либо из входного потока данных, либо из третьего блока буфера памяти, 2 - первый блок фильтров для выполнения одномерного вейвлет-преобразования по строке изображения (по горизонтали) для вычисления низкочастотной составляющей (LL) aL, 3 - второй блок фильтров для выполнения одномерного вейвлет-преобразования по строке изображения (по горизонтали) для вычисления высокочастотной составляющей (LL)aH, 4 - первый блок буфера памяти для хранения промежуточных данных, необходимых для вычисления низкочастотных и высокочастотных составляющих (LL)aLL и (LL)aLH при выполнении вейвлет-преобразования по столбцу изображения (по вертикали), 5 - второй блок буфера памяти для хранения промежуточных данных, необходимых для вычисления низкочастотных и высокочастотных составляющих (LL)a HL и (LL)aHH при выполнении вейвлет-преобразования по столбцу изображения (по вертикали), 6 - третий блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления низкочастотной составляющей (LL)aLL, 7 - четвертый блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления высокочастотной составляющей (LL) aLH, 8 - пятый блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления низкочастотной составляющей (LL)aHL, 9 - шестой блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления высокочастотной составляющей сигнала (LL)aHH, 10 - третий блок буфера памяти для хранения низкочастотной составляющей (LL)a LL после выполнения вейвлет-преобразования по столбцу изображения (по вертикали).
Недостатком данного устройства является достаточно большое количество низкочастотных коэффициентов на каждом уровне преобразования, увеличивающее время выполнения для достижения заданного размера низкочастотной составляющей LL.
Технической задачей, на решение которой направлена заявленная полезная модель, является снижение времени выполнения для получения заданных размеров низкочастотной составляющей вейвлет-преобразования.
Данная задача решается за счет того, что заявленное устройство для выполнения двухмерного симметричного четного вейвлет-преобразования содержащее: мультиплексор сигналов для формирования входного потока на первый и второй блок фильтров либо из входного потока видеоданных либо из третьего блока буфера памяти, первый блок фильтров для выполнения одномерного вейвлет-преобразования по строке изображения для вычисления низкочастотной составляющей (LL)aL, второй блок фильтров для выполнения одномерного вейвлет-преобразования по строке изображения для вычисления высокочастотной составляющей (LL)aH, первый блок буфера памяти для хранения промежуточных данных, необходимых для вычисления низкочастотных и высокочастотных составляющих (LL)aLL и (LL) aLH при выполнении вейвлет-преобразования по столбцу изображения, второй блок буфера памяти для хранения промежуточных данных, необходимых для вычисления высокочастотных составляющих (LL) aHL. и (LL)aHH при выполнении вейвлет-преобразования по столбцу изображения, третий блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения для вычисления низкочастотной составляющей (LL)aLL, четвертый блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения для вычисления высокочастотной составляющей (LL)aLH, пятый блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения для вычисления высокочастотной составляющей (LL)aHL шестой блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения для вычисления высокочастотной составляющей сигнала (LL)aHH, третий блок буфера памяти для хранения низкочастотной составляющей (LL)aLL после выполнения вейвлет-преобразования по столбцу изображения, отличающееся тем, что дополнительно имеет седьмой блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения для вычисления дополнительной высокочастотной составляющей (LL)aLH1, вход которого выполнен с возможностью поступления данных из первого блока буфера памяти, восьмой блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения для вычисления дополнительной высокочастотной составляющей (LL)aHH1, вход которого выполнен с возможностью поступления данных из второго блока буфера памяти, девятый блок фильтров для выполнения одномерного вейвлет-преобразования по строке изображения для вычисления дополнительной высокочастотной составляющей (LL)aH1, вход которого выполнен с возможностью поступления данных с выхода мультиплексора, четвертый блок буфера памяти для хранения промежуточных данных, необходимых для вычисления дополнительных высокочастотных составляющих (LL)aНL1, (LL)aHH2 и (LL)aHH3 при выполнении вейвлет-преобразования по столбцу изображения, десятый, одиннадцатый и двенадцатый блоки фильтров для выполнения одномерных вейвлет-преобразований по столбцу изображения для вычисления трех дополнительных высокочастотных составляющих (LL)aHL1, (LL)aHH1 и (LL) aНН3, соответственно, вход которого выполнен с возможностью поступления данных из четвертого блока буфера памяти.
Техническим результатом, обеспечиваемым приведенной совокупностью признаков, является формирование одной низкочастотной и двух высокочастотных составляющих одномерного вейвлет-преобразования по строкам изображения и одной низкочастотной и восьми высокочастотных составляющих при последующем одномерном вейвлет-преобразований по столбцам полученных коэффициентов на каждом этапе декомпозиции, что позволяет снизить количество итераций для достижения заданного размера низкочастотной составляющей и соответственно время выполнения.
Приведенная совокупность признаков также обеспечивает получение двух дополнительных технических результатов.
Первым дополнительным техническим результатом, обеспечиваемым приведенной совокупностью признаков, является уменьшенное время передачи низкочастотной составляющей по различным сетям передачи данных, содержащей наиболее важную информацию об изображении за счет ее меньшего размера.
Вторым дополнительным техническим результатом, обеспечиваемым приведенной совокупностью признаков, является увеличение количества высокочастотных коэффициентов на каждом этапе преобразования, наиболее часто используемых в различных алгоритмах обработки изображений, например при их сжатии.
Для пояснения предполагаемого технического решения предложены чертежи.
На фиг.1. приведена структурная схема устройства согласно прототипу.
На фиг.2. приведена структурная схема заявленного устройства для выполнения симметричного четного вейвлет преобразования.
На фиг.3. представлены результаты одномерного симметричного четного вейвлет-преобразования согласно работе заявленного устройства в первом, втором и четвертом блоках памяти.
На фиг.4. представлены результаты двухмерного симметричного четного вейвлет-преобразования согласно работе заявленного устройства на выходах блоков фильтров с третьего по восьмой, а также с десятого по двенадцатый.
Предлагаемое устройство (см. фиг.2.) содержит: 1 - мультиплексор сигналов для формирования входного потока на первый, второй и девятый блок фильтров либо из входного потока, либо из третьего блока буфера памяти; 2 - первый блок фильтров для выполнения одномерного вейвлет-преобразования по строке изображения (по горизонтали) для вычисления низкочастотной составляющей (LL)aL; 3 - второй блок фильтров для выполнения одномерного вейвлет-преобразования по строке изображения (по горизонтали) для вычисления высокочастотной составляющей (LL)aH; 4 - первый блок буфера памяти для хранения промежуточных данных, необходимых для вычисления низкочастотных и высокочастотных составляющих (LL)aLL, (LL)a LH и (LL)aLH1 при выполнении вейвлет-преобразования по столбцу изображения (по вертикали); 5 - второй блок буфера памяти для хранения промежуточных данных, необходимых для вычисления высокочастотных составляющих (LL)aHL, (LL)a HH, и (LL)aHH1 при выполнении вейвлет-преобразования по столбцу изображения (по вертикали); 6 - третий блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления низкочастотной составляющей (LL)aLL; 7 - четвертый блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления высокочастотной составляющей (LL) aLH; 8 - пятый блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления высокочастотной составляющей (LL)aHL; 9 - шестой блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления высокочастотной составляющей (LL)aHH; 10 - шестой блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления высокочастотной составляющей (LL) aHH; 11 - седьмой блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления высокочастотной составляющей (LL)aLH1; 12 - восьмой блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления высокочастотной составляющей (LL)aHH1; 13 - девятый блок фильтров для выполнения одномерного вейвлет-преобразования по строке изображения (по горизонтали) для вычисления высокочастотной составляющей (LL)aH1; 14 - четвертый блок буфера памяти для хранения промежуточных данных, необходимых для вычисления высокочастотных составляющих (LL)aHL1, (LL)aHH2 и (LL) aHH3 при выполнении вейвлет-преобразования по столбцу изображения (по вертикали); 15 - десятый блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления высокочастотной составляющей (LL)aHL1; 16 - одиннадцатый блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления высокочастотной составляющей (LL)aHH2; 17 - двенадцатый блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения (по вертикали) для вычисления высокочастотной составляющей (LL)aHH3.
Работает устройство следующим образом. Данные из входного потока, строка за строкой, поступают первый вход мультиплексора, с выхода которого данные подаются на первый, второй и девятый блоки фильтров. Первый, второй и девятый блоки фильтров выполняют одномерное вейвлет-преобразование по строке изображения для вычисления низкочастотной составляющей L, высокочастотной составляющей Н и высокочастотной составляющей H1 для первого уровня декомпозиции соответственно. С выхода первого, второго и девятого блоков фильтров результаты одномерного вейвлет-преобразования поступают на первый, второй и четвертый блоки буферов памяти соответственно. В первом, втором и четвертом блоках буферной памяти хранятся промежуточные данные, необходимые для вычисления низкочастотных и высокочастотных составляющих LL, LH, LH1, HL, HL1, НН, НН1, НН1 и НН3 при выполнении вейвлет-преобразования по столбцу изображения (по вертикали). Из первого блока буфера памяти значения низкочастотной составляющей L подаются на третий, четвертый и седьмой блоки фильтров. Третий, четвертый и седьмой блоки фильтров выполняют одномерное вейвлет-преобразование по столбцу изображения для вычисления низкочастотной и двух высокочастотных составляющих LL, LH и LH1 для первого уровня декомпозиции соответственно. С выхода четвертого и седьмого блоков фильтров высокочастотные составляющие LH и LH1 поступают на выход устройства, а низкочастотная составляющая LL с выхода третьего фильтра поступает или на третий блок буфера памяти, или на выход устройства, если достигнут последний уровень декомпозиции. Из второго блока буфера памяти значения высокочастотной составляющей Н подаются на пятый, шестой и восьмой блоки фильтров. Пятый, шестой и восьмой блоки фильтров выполняют одномерное вейвлет-преобразование по столбцу изображения для вычисления высокочастотных составляющих HL, НН и НН1 для первого уровня декомпозиции соответственно. С выхода пятого, шестого и восьмого блоков фильтров высокочастотные составляющие HL, НН и НН1 поступают на выход устройства. Из четвертого блока буфера памяти значения высокочастотной составляющей H1 подаются на десятый, одиннадцатый и двенадцатый блоки фильтров. Десятый, одиннадцатый и двенадцатый блоки фильтров выполняют одномерное вейвлет-преобразование по столбцу изображения для вычисления высокочастотных составляющих HL1, НН2 и НН3 для первого уровня декомпозиции соответственно. С выхода десятого, одиннадцатого и двенадцатого блоков фильтров высокочастотные составляющие HL1, НН2 и НН3 поступают на выход устройства. С третьего блока буфера памяти низкочастотная LL составляющая поступает на второй вход мультиплексора, и дальнейшая обработка этих данных осуществляется аналогичным образом.
Как следует из вышеизложенного, при выполнении преобразований на каждом уровне разложения формируются дополнительные высокочастотные составляющие. Формирующаяся низкочастотная составляющая имеет размер в 1/9, т.е. примерно 11% от общего количества коэффициентов, а количество высокочастотных коэффициентов составляет примерно 89% от общего количества коэффициентов, что и обеспечивает выполнение заявленного основного и дополнительных технического результатов в предлагаемой полезной модели.
Литература
1. Р.Гонсалес, Р.Вудс. Цифровая обработка изображений. М.: Техносфера, 2006. 1072 с.
2. Добеши И. Десять лекций по вейвлетам. - Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001.
Устройство для выполнения двухмерного симметричного четного вейвлет-преобразования, содержащее мультиплексор сигналов для формирования входного потока на первый и второй блок фильтров либо из входного потока видеоданных либо из третьего блока буфера памяти, первый блок-фильтров для выполнения одномерного вейвлет-преобразования по строке изображения для вычисления низкочастотной составляющей, второй блок фильтров для выполнения одномерного вейвлет-преобразования по строке изображения для вычисления высокочастотной составляющей, первый блок буфера памяти для хранения промежуточных данных, необходимых для вычисления низкочастотных и высокочастотных составляющих при выполнении вейвлет-преобразования по столбцу изображения, второй блок буфера памяти для хранения промежуточных данных, необходимых для вычисления высокочастотных составляющих при выполнении вейвлет-преобразования по столбцу изображения, третий блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения для вычисления низкочастотной составляющей, четвертый блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения для вычисления высокочастотной составляющей, пятый блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения для вычисления высокочастотной составляющей, шестой блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения для вычисления высокочастотной составляющей сигнала, третий блок буфера памяти для хранения низкочастотной составляющей после выполнения вейвлет-преобразования по столбцу изображения, отличающееся тем, что дополнительно имеет седьмой блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения для вычисления дополнительной высокочастотной составляющей, вход которого выполнен с возможностью поступления данных из первого блока буфера памяти, восьмой блок фильтров для выполнения одномерного вейвлет-преобразования по столбцу изображения для вычисления дополнительной высокочастотной составляющей, вход которого выполнен с возможностью поступления данных из второго блока буфера памяти, девятый блок фильтров для выполнения одномерного вейвлет-преобразования по строке изображения для вычисления дополнительной высокочастотной составляющей, вход которого выполнен с возможностью поступления данных с выхода мультиплексора, четвертый блок буфера памяти для хранения промежуточных данных, необходимых для вычисления дополнительных высокочастотных составляющих при выполнении вейвлет-преобразования по столбцу изображения, десятый, одиннадцатый и двенадцатый блоки фильтров для выполнения одномерных вейвлет-преобразований по столбцу изображения для вычисления трех дополнительных высокочастотных составляющих соответственно, вход которого выполнен с возможностью поступления данных из четвертого блока буфера памяти.
