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

Изобретение относится к обработке двухмерных сигналов, а именно к области выполнения дискретного вейвлет-преобразования и может использоваться в системах обработки изображений, их сжатия, техническом зрении.

В настоящее время в алгоритмах обработки сигналов и изображений широко используется вейвлет-преобразование, которое переводит входные данные в вид, более удобный для выполнения ряда алгоритмов обработки.

При выполнении вейвлет-преобразования сигнал раскладывается на ряд частотных полос, для чего задается набор низко- и высокочастотных фильтров для выполнения декомпозиции сигнала. После выполнения требуемых действий над коэффициентами преобразованных данных сигнал может быть восстановлен с различной степенью точности. При выполнении быстрого преобразования используются неполные - прореживающие и сгущающие выборки [1, 2]. Для изображений и двухмерных сигналов могут использоваться «сепарабельные свертки», являющиеся основой разделимых фильтров, которые позволяют обрабатывать многомерный сигнал на основе последовательной одномерной фильтрации [1, 2].

Из существующего уровня техники известны способ и устройство вейвлет-преобразования (см. патент на изобретение US 6591017 B, публикация 08.07.2003) и способ сжатия данных, в которых используется вейвлет-преобразование (см. заявка на изобретение US 2010/0232723 А1).

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

Наиболее близким по технической сущности способом к заявляемому изобретению является способ прямого и обратного быстрого двухмерного вейвлет-преобразования. Способ выполнения прямого и обратного быстрого двухмерного вейвлет-преобразования, основанный на свертке входных данных по строкам с низкочастотным и высокочастотным фильтрами, на выходах которых производится неполная выборка, с получением в результате низкочастотных и высокочастотных значений одномерного преобразования, далее к ним по столбцам применяется свертка с низкочастотными и высокочастотными фильтрами с последующей неполной выборкой, причем к низкочастотным коэффициентам может быть применена описанная последовательность действий для выполнения следующего уровня прямого преобразования, а обратное вейвлет-преобразование выполняется по столбцам на основе сгущающей выборки, применяемой к низкочастотной и высокочастотным составляющим, полученным в результате прямого вейвлет-преобразования, с последующей сверткой с низкочастотным и высокочастотным фильтрами и суммированием, затем производится обработка по строкам на основе сгущающей выборки, применяемой к полученным низкочастотной и высокочастотной составляющим, с последующей сверткой с низкочастотным и высокочастотным фильтрами и суммированием, при этом полученный результат может быть использован с соответствующими высокочастотными составляющими для выполнения следующего уровня обратного вейвлет-преобразования (см. Малла С. Вэйвлеты в обработке сигналов / С. Мала; Пер. с англ. - М.: Мир, 2005. - С.332-336), принято за прототип.

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

Задачей, на решение которой направлено заявленное изобретение, является обеспечение инвариантности к повороту вейвлет-преобразования.

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

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

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

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

Сущность изобретения поясняется чертежами, на которых изображено:

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

на фиг.2 - структурная схема блока выполнения обратного быстрого вейвлет-преобразования;

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

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

Сущность изобретения заключается в следующем.

Быстрое вейвлет-преобразование представляет собой эффективный метод реализации вычислений дискретного вейвлет-преобразования [1]. Оно может быть представлено в виде произведения блочной матрицы на вектор-столбец [3]:

где j - уровень преобразования;

A_j, D_j - блоки матрицы преобразования;

a_j, a_j+1 и d_j+1 - векторы-столбцы аппроксимирующих и детализирующих коэффициентов преобразования.

Блочная матрица преобразования формируется с использованием значений масштабирующей (φ) и вейвлет-функций (ψ), которые являются основой для формирования низкочастотного и высокочастотного фильтров [1, 3].

Для решения заявленной технической задачи увеличивается количество частотных диапазонов за счет внесения следующих принципиальных изменений:

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

где a1_j и a2_j - первая и вторая части входной последовательности соответствующего уровня преобразования.

- Для формирования матрицы преобразования используются пары высокочастотных и низкочастотных фильтров, коэффициенты которых связаны следующими соотношениями:

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

Выражение (3) показывает, что при формировании первой и второй пары фильтров используются коэффициенты с прямым и обратным порядком следования.

В результате использования данных фильтров создаются по две низкочастотные и высокочастотные группы коэффициентов преобразования, принадлежащих разным частотным диапазонам, а выражение (1) с учетом (2) и (3) принимает следующий вид:

где D1_j, A1_j, A2_j и D2_j - части матрицы блочной преобразования, каждая размером 2^n/2×2ⁿ;

a1_j+1, a2_j+1 и d1_j+1 d2_j+1 - аппроксимирующие и детализирующие части вектора-столбца прямого преобразования, каждая длиной 2^n-2.

В соответствии с (2), (4) с заменой входных данных могут последовательно обрабатываться данные, принадлежащие различным частотным диапазонам.

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

На их основе формируется блочная матрица обратного преобразования. Использование ортогональных функций [1, 2] при формировании фильтров может использоваться выражение:

С заменой входных данных в (6) могут последовательно обрабатываться данные, принадлежащие различным частотным диапазонам.

В соответствии с заявленным способом прямое быстрое двухмерное вейвлет-преобразование выполняется с использованием 5 однотипных блоков фильтров F1-F5 (фиг.1), каждый из которых содержит переключатель - Sw, выполняющий функции демультиплексирования, две пары низкочастотных и высокочастотных фильтров - , и , с реализацией неполной выборки на выходе 12. На выходах 1, 4 и 2, 3 блоков фильтров формируются прореженные высокочастотные и низкочастотные значения обработанных данных соответственно. При этом блок фильтров F1 производит обработку по строкам, а блоки фильтров F2-F5 производят обработку по столбцам.

На вход блока фильтров F1 поступают входные данные a_j по строкам.

Первая часть каждой строки через выход 1 переключателя Sw блока фильтров F1 поступает на низкочастотный и низкочастотный фильтры и . После свертки с данными фильтрами данные прореживаются через один отсчет ↓2 и на выходах 1 и 2 блока фильтров F1 формируются высокочастотная d1_j+1 и низкочастотная a1_j+1 составляющие соответственно.

Вторая часть каждой строки через выход 2 переключателя Sw блока фильтров F1 поступает на низкочастотный и низкочастотный фильтры и . После свертки с данными фильтрами данные прореживаются через один отсчет ↓2 и на выходах 3 и 4 блока фильтров F1 формируются низкочастотная a2_j+1 и высокочастотная d2_j+1 составляющие соответственно. Распределение по частотам результатов одномерного прямого быстрого вейвлет-преобразования представлено на фиг.3,а.

Первая высокочастотная составляющая d1_j+1 с выхода 1 блока фильтров F1 поступает на вход блока фильтров F2, который обрабатывает данные по столбцам.

Первая часть столбца входных данных с выхода 1 переключателя Sw блока фильтров F2 свертывается с фильтрами и и после прореживания через один отсчет ↓2 на выходах 1 и 2 данного блока формируются значения и соответственно.

Вторая часть столбца входных данных с выхода 2 переключателя Sw блока фильтров F2 свертывается с фильтрами , и после прореживания через один отсчет ↓2 на выходах 3 и 4 данного блока формируются значения и соответственно. Блоки фильтров F3-F5 обрабатывают входные данные аналогично блоку F2. Низкочастотная составляющая a1_j+1 с выхода блока фильтров F1 поступает на вход блока F3, на выходах 1, 2, 3. 4 которого формируются составляющие прямого быстрого вейвлет-преобразования , a11_j+1, a12_j+1 и соответственно. Низкочастотная составляющая a2_j+1 с выхода блока фильтров F1 поступает на вход блока F4, на выходах 1, 2, 3, 4 которого формируются составляющие прямого быстрого вейвлет-преобразования , a21_j+1, a22_j+1 и соответственно. Высокочастотная составляющая d2_j+1 с выхода блока фильтров F1 поступает на вход блока F5, на выходах 1, 2, 3, 4 которого формируются составляющие прямого быстрого вейвлет-преобразования , , и , соответственно. Распределение по частотам результатов двухмерного прямого быстрого вейвлет-преобразования представлено на фиг.3,б.

Совокупность значений 16-ти составляющих на всех выходах блоков фильтров F2-F4 является результатом прямого быстрого вейвлет-преобразования j+1 и может использоваться для последующей обработки на основе различных алгоритмов, включая и повороты на фиксированные углы. Совокупность 4-х низкочастотных составляющих a11_j+1, a12_j+1, a21_j+1 и a22_j+1 на выходах 2, 3 блоков фильтров F3 и F4 соответственно может использоваться для выполнения прямого быстрого вейвлет-преобразования следующего уровня.

В соответствии с заявленным способом обратное быстрое двухмерное вейвлет-преобразование выполняется с использованием 5 однотипных блоков фильтров Fb-Fb5 (фиг.2), каждый из которых имеет 4 входа, две пары низкочастотных и высокочастотных фильтров h1, g1 и h2, g2 с реализацией сгущающее выборки ↑2 на входе каждого, 2 сумматора ⊕ на выходе каждой пары фильтров для формирования первой и второй части выходной последовательности, содержит переключатель - Sw, выполняющий функции мультиплексирования для формирования одной полной частотной составляющей.

На входы 1-4 блока фильтров Fb1 поступают частотные составляющие , , и соответственно. Значения составляющих , подвергаются сгущающей выборке ↑2, далее осуществляется фильтрация на основе свертки с h1 и g1 и в результате суммирования на ⊕ формируется первая часть столбца d1_j+1. Значения составляющих , подвергаются сгущающей выборке ↑2, далее осуществляется фильтрация на основе свертки с h2, g2 и в результате суммирования на ⊕ формируется вторая часть столбца d1_j+1.

Первая и вторая части столбца d1_j+1 подаются на входы 1, 2 переключателя Sw блока фильтров Fb1, на выходе которого формируется полная высокочастотная составляющая d1_j+1 по столбцам, поступающая на вход 1 блока фильтров Fb5. Блоки фильтров Fb2-Fb4 работают аналогично.

На входы 1-4 блока фильтров Fb2 поступают частотные составляющие , a11_j+1, a12_j+1 и соответственно, и на выходе данного блока формируется полная низкочастотная составляющая a1_j+1 по столбцам, поступающая на вход 2 блока фильтров Fb5. На входы 1-4 блока фильтров Fb3 поступают частотные составляющие , a21_j+1, a22_j+1 и соответственно, и на выходе данного блока формируется полная низкочастотная составляющая a2_j+1 по столбцам, поступающая на вход 3 блока фильтров Fb5.

На входы 1-4 блока фильтров Fb4 поступают частотные составляющие , , и соответственно, и на выходе данного блока формируется полная высокочастотная составляющая d2j+i по столбцам, поступающая на вход 4 блока фильтров Fb5. Значения составляющих по столбцам d1_j+1 и a1_j+1 подвергаются сгущающей выборке ↑2 по строкам, далее осуществляется фильтрация на основе свертки с h1 и g1 и в результате суммирования на ⊕ формируется первая часть строк a_j. Значения составляющих по столбцам a2_j+1 и d2_j+1 подвергаются сгущающей выборке ↑2 по строкам, далее осуществляется фильтрация на основе свертки с h2, g2 и в результате суммирования на ⊕ формируется вторая часть столбца a_j. Первая и вторая части строк a_j подаются на входы 1, 2 переключателя Sw блока фильтров Fb5, на выходе которого формируется полная составляющая a_j по строкам. Данная низкочастотная составляющая a_j является результатом выполнения обратного быстрого вейвлет-преобразования и может использоваться в реализации алгоритмов обработки изображений или в совокупности с соответствующими высокочастотными составляющими участвовать в вейвлет-преобразовании следующего уровня.

На фиг.4 представлены результаты моделирования прямого и обратного быстрого двухмерного вейвлет-преобразования с использованием базиса Добеши в соответствии с заявленным способом. На фиг.4,а представлено исходное тестовое изображение. На фиг.4,б представлен результат прямого быстрого вейвлет-преобразования первого уровня по строкам. На фиг.4,в представлен результат прямого быстрого вейвлет-преобразования первого уровня по строкам и столбцам.

На фиг.4,г представлена разность между результатом прямого быстрого вейвлет-преобразования первого уровня, выполненным в соответствии с прототипом и с заявленным способом. Здесь проведено совмещение частотных диапазонов и, как видно, значения могут отличаться на 3/4 площади (75%). Совпадает 1/4 значений, соответствующая правому нижнему темному квадранту.

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

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

Список использованных источников

1. Гонсалес Р. Цифровая обработка изображений / Р. Гонсалес, Р. Вудс. - М.: Техносфера, 2005. - 1072 с.

2. Добеши И. Десять лекций по вейвлетам / И. Добеши. - Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. - 464 с.

3. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии / С. Уэлстид. - М.: Триумф, 2003. - 320 с.