Патент на изобретение №2342704

(54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ ДВУХМЕРНОГО ПРЯМОГО ДИСКРЕТНОГО ВЕЙВЛЕТ ПРЕОБРАЗОВАНИЯ В СИСТЕМАХ КОМПРЕССИИ ВИДЕОДАННЫХ

(57) Реферат:

Изобретение относится к вычислительной технике, а именно к области выполнения прямого дискретного вейвлет преобразования в системах компрессии видеоданных. Техническим результатом является уменьшение требуемого объема буфера памяти менее 4,5N в результате того, что в устройство включены блоки фильтров для выполнения одномерного вейвлет преобразования (ОВП) по столбцу видеоизображения (по вертикали), требующие меньшего объема буфера памяти. Предложено устройство для выполнения двухмерного прямого дискретного вейвлет преобразования в системах компрессии видеоданных, содержащее мультиплексор сигналов для формирования входного потока на первый и второй блоки фильтров либо из входного потока видеоданных, либо из блока буфера памяти, первый блок фильтров для выполнения ОВП по строке видеоизображения по горизонтали для вычисления НЧ составляющей, второй блок фильтров для выполнения ОВП по строке видеоизображения по горизонтали для вычисления высокочастотной составляющей, причем в устройство включают третий блок фильтров для выполнения ОВП по столбцу видеоизображения по вертикали для вычисления НЧ и ВЧ составляющих над данными, поступающими с первого блока фильтров и с первого и второго блоков буферов памяти, первый блок буфера памяти для хранения поступающих с третьего блока фильтров промежуточных данных, необходимых для вычисления НЧ и ВЧ составляющих, второй блок буфера памяти для хранения поступающих с третьего блока фильтров промежуточных данных, необходимых для вычисления НЧ и ВЧ составляющих, четвертый блок фильтров для выполнения ОВП по столбцу видеоизображения по вертикали для вычисления НЧ и ВЧ составляющих над данными, поступающими со второго блока фильтров и с третьего и четвертого блоков буферов памяти, третий блок буфера памяти для хранения поступающих с четвертого блока фильтров промежуточных данных, необходимых для вычисления НЧ и ВЧ составляющих, четвертый блок буфера памяти для хранения поступающих с четвертого блока фильтров промежуточных данных, необходимых для вычисления НЧ и ВЧ составляющих, а пятый блок буфера памяти для хранения низкочастотной составляющей после выполнения третьим блоком фильтров вейвлет преобразования используют в качестве блока буфера памяти, с которого данные поступают на мультиплексор сигналов. 3 ил.

(56) (продолжение):

CLASS=”b560m”set of lifting based wavelet filters, Acoustics, Speech, and Signal Processing 2001, ICASSP, 2001 IEEE International Conference on Volume 2, Issue, 2001, c.1101-1104. CHAKRABARTI С. et al. Efficient realizations of encoders and decoders based on the 2-Ddiscrete wavelet transform, Very Large Scale Integration Systems, IEEE Transactions on Volume 7, Issue 3, Sep 1999, c.289-298. УЭЛСТИД С. Фракталы и вейвлеты для сжатия изображений в действии. – М.: Триумф, 2003, с.183-201.

Изобретение относится к вычислительной технике, а именно к области выполнения прямого дискретного вейвлет (wavelet) преобразования (FDWT – Forward discrete вейвлет transform) в системах компрессии видеоданных.

Дискретное двумерное вейвлет преобразование широко используется в системах компрессии видеоданных, в частности, его применение описано в стандарте JPEG200 [1]. В таких системах каждая цветовая компонента входного кадра размером N·M, где N – ширина кадра, а М – высота, представляется в виде массива данных из М строк и N столбцов. Далее, для каждой строки выполняется одномерное преобразование, представляющее собой низкочастотную и высокочастотную фильтрацию данных. Затем над результатами преобразования, для каждого из столбцов, выполняются аналогичные преобразования.

Таким образом каждая цветовая компонента преобразуется в набор 2-мерных Sub-band сигналов, представляющих интенсивность сигнала в различных полосах частот, в различных пространственных областях. Под Sub-band понимают набор коэффициентов, полученных с помощью одной и той же последовательности низкочастотных и высокочастотных фильтрующих операций по горизонтали и вертикали. Sub-bands обозначаются следующим образом: LL, HL, LH или НН.

Коэффициенты в sub-band HL являются коэффициентами преобразования, полученными низкочастотной фильтрацией по вертикали и высокочастотной фильтрацией по горизонтали. Коэффициенты в sub-band LH являются коэффициентами преобразования, полученными высокочастотной фильтрацией по вертикали и низкочастотной фильтрацией по горизонтали.

Коэффициенты в sub-band НН являются коэффициентами преобразования, полученными высокочастотной фильтрацией по вертикали и высокочастотной фильтрацией по горизонтали.

Коэффициенты в sub-band LL являются коэффициентами преобразования, полученными низкочастотной фильтрацией по вертикали и низкочастотной фильтрацией по горизонтали.

Далее над коэффициентами LL выполняются преобразования, описанные выше. Количество итераций по обработке LL компонент задает число уровней декомпозиции J входного изображения. Число полученных sub-bands 3·J+1.

Для обозначения коэффициентов полученных после преобразований над LL компонентой, используют обозначения: (LL)^aL, (LL)^aH, (LL)^aLL, (LL)^aLH, (LL)^aHL, (LL)^aHH, где индекс a – уровень декомпозиции и 0а

Увеличение числа уровней декомпозиции позволяет увеличивать степень сжатия (компрессии) видеоданных.

Применение FDWT для сжатия изображения описано в [1]. Данное обратимое преобразование является обратимой реализацией фильтрации 5/3, где 5 и 3 длина низкочастотного и высокочастотного фильтров соответственно.

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

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

Сначала вычисляются нечетные коэффициенты выходного сигнала Y для таких значений n, что i₀-12n+11+1:

где i₀ – индекс первого элемента в массиве X, i₁ – индекс элемента, следующего за последним элементом массива X.

Затем вычисляются четные коэффициенты выходного сигнала Y из четных коэффициентов сигнала Х и нечетных коэффициентов сигнала Y для таких значений n, что i₀2n1:

Четные коэффициенты сигнала Y представляют собой низкочастотную прореженную версию сигнала X, нечетные являются высокочастотной прореженной версией сигнала X.

Известны технические решения устройств [2, 3], выполняющих двухмерное вейвлет преобразование и использующих для хранения промежуточных данных блоки памяти с объемом N·M, где N – ширина кадра, а М – высота. Недостатком данных решений является большой объем требуемой памяти, что приводит либо к существенному увеличению площади, потребляемой мощности и стоимости кристалла интегральной схемы, реализующей функции компрессии видеоданных, либо к необходимости использовать внешние устройства памяти, которые увеличивают стоимость и объем аппаратуры.

Наиболее близким техническим решением предлагаемого изобретения является устройство для выполнения компрессии видеоданных с использованием вейвлет преобразования, приведенное в [4], включающее:

– мультиплексор сигналов для формирования входного потока на первый и второй блок фильтров либо из входного потока видеоданных либо из третьего блока буфера памяти,

– первый блок фильтров для выполнения одномерного вейвлет преобразования по строке видеоизображения (по горизонтали) для вычисления низкочастотной составляющей (LL)^aL,

– второй блок фильтров для выполнения одномерного вейвлет преобразования по строке видеоизображения (по горизонтали) для вычисления высокочастотной составляющей (LL)^aH,

– первый блок буфера памяти объемом KN(1-(1/2)^J)5N отсчетов, для хранения промежуточных данных, необходимых для вычисления низкочастотных и высокочастотных составляющих (LL)^aLL и (LL)^aLH при выполнении вейвлет преобразования по столбцу видеоизображения (по вертикали),

– второй блок буфера памяти объемом KN(1-(1/2)^J)5N отсчетов для хранения промежуточных данных, необходимых для вычисления низкочастотных и высокочастотных составляющих (LL)^aHL и (LL)^aHH при выполнении вейвлет преобразования по столбцу видеоизображения (по вертикали),

– третий блок фильтров для выполнения одномерного вейвлет преобразования по столбцу видеоизображения (по вертикали) для вычисления низкочастотной составляющей (LL)^aLL,

– четвертый блок фильтров для выполнения одномерного вейвлет преобразования по столбцу видеоизображения (по вертикали) для вычисления высокочастотной составляющей (LL)^aLH,

– пятый блок фильтров для выполнения одномерного вейвлет преобразования по столбцу видеоизображения (по вертикали) для вычисления низкочастотной составляющей (LL)^aHL,

– шестой блок фильтров для выполнения одномерного вейвлет преобразования по столбцу видеоизображения (по вертикали) для вычисления высокочастотной составляющей сигнала (LL)^aHH,

– третий блок буфера памяти объемом N(1-(1/2)^J-1)N отсчетов для хранения низкочастотной составляющей (LL)^aLL после выполнения вейвлет преобразования по столбцу видеоизображения (по вертикали).

Функциональная схема устройства согласно прототипу [4] иллюстрируется на фиг.1. Устройство содержит: 1 – мультиплексор сигналов для формирования входного потока на первый и второй блок фильтров либо из входного потока видеоданных, либо из третьего блока буфера памяти, 2 – первый блок фильтров для выполнения одномерного вейвлет преобразования по строке видеоизображения (по горизонтали) для вычисления низкочастотной составляющей (LL)^aL, 3 – второй блок фильтров для выполнения одномерного вейвлет преобразования по строке видеоизображения (по горизонтали) для вычисления высокочастотной составляющей (LL)^aH, 4 – первый блок буфера памяти объемом KN(1-(1/2)^J)5N отсчетов для хранения промежуточных данных, необходимых для вычисления низкочастотных и высокочастотных составляющих (LL)^aLL и (LL)^aLH при выполнении вейвлет преобразования по столбцу видеоизображения (по вертикали), 5 – второй блок буфера памяти объемом KN(1-(1/2)^J)5N отсчетов для хранения промежуточных данных, необходимых для вычисления низкочастотных и высокочастотных составляющих (LL)^aHL и (LL)^aHH при выполнении вейвлет преобразования по столбцу видеоизображения (по вертикали), 6 – третий блок фильтров для выполнения одномерного вейвлет преобразования по столбцу видеоизображения (по вертикали) для вычисления низкочастотной составляющей (LL)^aLL, 7 – четвертый блок фильтров для выполнения одномерного вейвлет преобразования по столбцу видеоизображения (по вертикали) для вычисления высокочастотной составляющей (LL)^aLH, 8 – пятый блок фильтров для выполнения одномерного вейвлет преобразования по столбцу видеоизображения (по вертикали) для вычисления низкочастотной составляющей (LL)^aHL, 9 – шестой блок фильтров для выполнения одномерного вейвлет преобразования по столбцу видеоизображения (по вертикали) для вычисления высокочастотной составляющей сигнала (LL)^aHH, 10 – третий блок буфера памяти объемом N(1-(1/2)^J-1)N отсчетов для хранения низкочастотной составляющей (LL)^aLL после выполнения вейвлет преобразования по столбцу видеоизображения (по вертикали).

Как следует из описания устройства указанного в прототипе [4], требуемый объем блоков памяти составляет:

– первый блок буфера памяти KN(1-(1/2)^J), где К длина фильтра;

– второй блок буфера памяти KN(1-(1/2)^J), где К длина фильтра;

– третий блок буфера памяти N(1-(1/2)^J-1).

Таким образом, суммарный объем памяти, требуемой для выполнения преобразования, равен 2KN(1-(1/2)^J)+N(1-(1/2)^J-1), что стремится к 2KN+N при увеличении количества уровней декомпозиции J.

В [1] величина длины фильнров К равны 5 и 3 для низкочастотного и высокочастотного фильтров соответственно. Поэтому для выполнения преобразования требуются буферы памяти суммарным объемом 2KN+N=11N, при К=5. Размер буффера определяется по максимальной длине фильтра.

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

Задачей, на решение которой направлено изобретение, является достижение технического результата, заключающегося в уменьшении требуемых объемов буферов памяти до 4N(1-(1/2)^J)+N/2, что составляет менее 4,5N, что снижает размеры, мощность потребления и стоимости устройства, в результате того, что в устройство включены блоки фильтров для выполнения одномерного вейвлет преобразования по столбцу видеоизображения (по вертикали), требующие меньшего объема буфера памяти.

Для достижения названного технического результата в устройство [4], содержащее:

– мультиплексор сигналов для формирования входного потока на первый и второй блок фильтров либо из входного потока видеоданных либо из блока буфера памяти, а первый блок фильтров для выполнения одномерного вейвлет преобразования по строке видеоизображения (по горизонтали) для вычисления низкочастотной составляющей (LL)^aL,

– второй блок фильтров для выполнения одномерного вейвлет преобразования по строке видеоизображения (по горизонтали) для вычисления высокочастотной составляющей (LL)^aH,

включают следующие блоки, являющиеся отличительными признаками предлагаемого устройства:

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

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

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

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

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

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

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

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

Функциональная схема устройства согласно предлагаемому решению иллюстрируется на фиг.2.

Предлагаемое устройство содержит: 1 – мультиплексор сигналов для формирования входного потока на первый и второй блок фильтров либо из входного потока видеоданных либо из пятого блока буфера памяти, 2 – первый блок фильтров для выполнения одномерного вейвлет преобразования по строке видеоизображения (по горизонтали) для вычисления низкочастотной составляющей (LL)^aL, 3 – второй блок фильтров для выполнения одномерного вейвлет преобразования по строке видеоизображения (по горизонтали) для вычисления высокочастотной составляющей (LL)^aH, 11 – третий блок фильтров для выполнения одномерного вейвлет преобразования по столбцу видеоизображения (по вертикали) для вычисления низкочастотной (LL)^aLL и высокочастотной составляющей (LL)^aLH, 12 – первый блок буфера памяти объемом N отсчетов, для хранения промежуточных данных необходимых для вычисления низкочастотной (LL)^aLL и высокочастотной составляющей (LL)^aLH при выполнении вейвлет преобразования по столбцу видеоизображения (по вертикали), 13 – второй блок буфера памяти объемом N отсчетов, для хранения промежуточных данных необходимых для вычисления низкочастотной (LL)^aLL и высокочастотной составляющей (LL)^aLH при выполнении вейвлет преобразования по столбцу видеоизображения (по вертикали), 14 – четвертый блок фильтров для выполнения одномерного вейвлет преобразования по столбцу видеоизображения (по вертикали) для вычисления низкочастотной (LL)^aHL и высокочастотной составляющей (LL)^aHH, 15 – третий блок буфера памяти объемом N отсчетов для хранения промежуточных данных, необходимых для вычисления низкочастотной (LL)^aHL и высокочастотной составляющей (LL)^aHH при выполнении вейвлет преобразования по столбцу видеоизображения (по вертикали), 16 – четвертый блок буфера памяти объемом N отсчетов для хранения промежуточных данных, необходимых для вычисления низкочастотной (LL)^aHL и высокочастотной составляющей (LL)^aHH при выполнении вейвлет преобразования по столбцу видеоизображения (по вертикали), 17 – пятый блок буфера памяти объемом N/2 отсчетов для хранения низкочастотной составляющей (LL)^aLL после выполнения вейвлет преобразования по столбцу видеоизображения (по вертикали).

Предлагаемое устройство работает следующим образом:

1. Входные видеоданные, строка за строкой, поступают на первый вход мультиплексора сигналов, с выхода которого данные подаются на первый и второй блоки фильтров;

2. Первый и второй блоки фильтров выполняют одномерное вейвлет преобразование по строке видеоизображения для вычисления низкочастотной L и высокочастотной составляющей Н для первого уровня декомпозиции соответственно;

3. С выхода первого блока фильтров данные поступают на третий блок фильтров для выполнения одномерного вейвлет преобразования по столбцу видеоизображения для вычисления низкочастотной LL и высокочастотной составляющей LH;

4. С выхода второго блока фильтров данные поступают на четвертый блок фильтров для выполнения одномерного вейвлет преобразования по столбцу видеоизображения для вычисления низкочастотной HL и высокочастотной составляющей НН;

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

6. С выхода четвертного блока фильтров результаты преобразования (HL и НН составляющие сигнала) поступают на выход устройства;

7. С выхода третьего блока фильтров LH составляющая поступает на выход устройства, а LL составляющая поступает либо на пятый блок буфера памяти, либо на выход устройства, если LL составляющая вычислена для последнего уровня декомпозиции;

8. С выхода пятого буфера памяти данные (LL составляющая) поступают на второй входа мультиплексора сигналов, обработка этих данных осуществляется аналогичным образом.

Последовательность выполнения вычислений в третьем и четвертом блоках фильтров представлен на фиг.3.

Здесь принято, что на a-ом уровне декомпозиции обрабатываются матрицы данных размером n строк на m столбцов, a Xi,j элемент этой матрицы, где i – номер строки, j – номер столбца. LBuf, HBuf – буфер памяти для низкочастотной и высокочастотной составляющей соответственно, tempL, tempH – внутренние буферы блока фильтров для хранения временных данных, Out – выходные данные фильтра. Для третьего блока фильтров буферы LBuf, HBuf реализованы в первом и втором блоках буфера памяти соответственно. Для четвертого блока фильтров буферы LBuf, HBuf реализованы в третьем и четвертом блоках буфера памяти соответственно.

Рассмотрим работу блоков фильтров на примере третьего блока фильтров. Видеоданные Xi,j поступают последовательно, строка за строкой, на вход блока фильтров 2. В зависимости от номера строки обработка данных осуществляется разными способами. Первая строка 3 записывается в буфер LBuf без изменений 3.1. Вторая строка 4 обрабатывается совместно с данными из буфера LBuf, и результат вычислений записывается в буфер HBuf 4.1. Третья строка 5, обрабатываясь совместно с данными из буферов LBuf, HBuf, используется для вычисления выходных данных фильтра Out 5.1 и новых значений промежуточных данных, записываемых в буферы LBuf, HBuf 5.2. Последняя строка кадра 6, в зависимости от того четная она или нечетная 7, обрабатывается совместно с данными из буферов LBuf, HBuf, используется для вычисления выходных данных фильтра Out (7.1 для четных строк, 7.3 для нечетных строк) и новых значений промежуточных данных, записываемых в буферы LBuf, HBuf (7.2 для четных строк, 7.4 для нечетных строк). Все остальные строки (8) обрабатываются в соответствии с (8.1 и 8.2) для четных строк и (8.3 и 8.4) для нечетных строк.

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

Литература

1. TITLE: JPEG 2000 Part I Final Committee Draft Version 1.0 SOURCE: ISO/IEC JTC1/SC29 WG1, JPEG 2000 Editor Martin Boliek, Coeditors Charilaos Christopoulos, and Eric Majani.

2. Патент US 4943855.

3. Патент US 5014134.

4. Chaitali Chakrabarti, Member, 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.

Формула изобретения

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

РИСУНКИ