eng
Выпуск #3/2007
М.Чобану, М.Волков.
Цифровая обработка многомерных сигналов: предпосылки прорыва
Цифровая обработка многомерных сигналов: предпосылки прорыва
Просмотры: 2835
Сегодня мир переживает рождение нового научно-технического направления в области информационно-телекоммуникационных технологий и обработки сигналов. Это разработка теории многомерных систем и методов обработки многомерных сигналов, развитие которых стимулируют важные практические задачи. Возможна ли эффективная обработка в реальном времени сигналов, объем которых достигает десятков гигабайт? В данной статье рассказано о впервые разработанном иерархическом алгоритме кодирования многомерных сигналов с помощью неразделимой системы. Предложенный метод может стать прорывным для таких направлений, как трехмерное телевидение, медицинская техника, телекоммуникации и т.п.
Современные подходы к обработке многомерных сигналов
Интерес к решению задач анализа, синтеза и обработки многомерных (ММ) сигналов непрерывно растет. Это связано с бурным развитием таких областей, как мультимедиа-технологии и телекоммуникации, в которых необходимы обработка и сжатие неподвижных изображений, видеосигналов и меняющихся во времени трехмерных сигналов.
Под многомерными (ММ) понимаются сигналы, зависящие от нескольких координат, пространственных и/или временной. Это двумерные (2-D) неподвижные изображения, трехмерные (3-D) томографические снимки или видеосигналы, четырехмерные (4-D) томографические сигналы, зависящие от времени. Эффективным способом преобразования таких сигналов является применение так называемых многомерных многоскоростных систем. С их помощью сигнал может быть представлен в виде, более удобном для решения многих прикладных задач, таких, как сжатие (с потерями или без потерь), удаление шумов, распознавание образов и др. Многомерные сигналы зачастую обрабатываются как одномерные, после замены всех переменных на одну. До недавнего времени многомерные операторы цифровых систем были представлены в виде прямого (или тензорного) произведения одномерных функций координат. Но это не соответствует природе реальных сигналов, являющихся неразделимыми многомерными. Под неразделимым многомерным сигналом понимают такой, который нельзя задать в виде прямого произведения одномерных функций. Например, обычный круг, задаваемый функцией х2 + у2 ≤ R2 невозможно представить в виде произведения функций от одной координаты, т.е. в виде f1(x) f2(y).
Одно из направлений, которое может получить мощный импульс развития при создании эффективных программно-аппаратных средств обработки ММ-сигналов, – трехмерное телевидение (3D-TV).
Трехмерное телевидение (3D-TV)
Известно несколько систем 3D-TV. Первыми были 3-D мониторы австралийской компании DDD с 7–9 точками съемки, а также европейская система ATTEST (Advanced Three-Dimensional Television Systems Technologies), разрабатываемая в рамках проекта IST. В последней системе сигнал включает как видеоинформацию, так и сведения о глубине. Для сжатия подобных сигналов используется стандарт MPEG-2 [1]. Впервые система трехмерного телевидения была представлена Фраунгоферовским институтом (Fraunhofer Nachrichtentechnik Heinrich-Hertz-Institut) на Международной конференции International Broadcast Convention в 2004 году.
В Токийском Университете (Япония) создан монитор для удаленного просмотра 3-D изображений компьютерной графики без каких-либо дополнительных очков [2, 3]. С помощью элементарных линз многопучковой системы монитор передает 3-D изображения глубиной до 5,7 м перед монитором и до 3,5 м вглубь монитора (рис.1).
В Национальном Институте AIST (National Institute of Advanced Industrial Science and Technology) и в Университете Кейо в сотрудничестве с компанией Burton было создано устройство отображения 3-D изображений, состоящих из массивов точек в воздухе [4]. Разработанное устройство отображения использует эффект плазменной эмиссии около точки фокусировки лазерного луча. Управляя положением фокусной точки по трем осям, можно изображать массивы точек (рис.2). Аналогичных результатов достигла и компания IO2 Technology с устройством Heliodisplay. К тому же, Heliodisplay является интерактивным устройством – по объемному изображению можно перемещать палец, используя его как указатель курсора.
Одна из основных задач, которые встают перед разработчиками 3D-TV, – сжатие 4-D и 5-D сигналов. Существует два подхода к сжатию световых полей с учетом компенсации разницы между видами с различных точек съемки: кодеры, основанные на предсказании, и кодеры, которые параметризуют виды в различные текстуры. Кодеры первого типа допускают параметризацию по числу точек съемки, однако они не масштабируемы по качеству и разрешению. В кодерах второго типа используется явная геометрическая модель системы регистрации многомерного сигнала, чтобы привести все виды к единой системе координат. Световые поля сначала приводятся к поверхности геометрической модели и формируют так называемое поверхностное световое поле. При этом создаются частичные текстуры объектов, видимые с различных точек, – MVV-текстуры (Multi-View Video). В результате формируется 4-D массив по координатам: вид/камера (или угол поворота камеры), время и две пространственные координаты. Такой массив может быть сжат далее с помощью методов обработки ММ-сигналов на основе иерархических алгоритмов [5], например 4-D иерархического метода, подобного SPIHT [6, 7].
Отметим, что на сегодня реализованы только простейшие разделимые иерархические 4-D SPIHT-кодеры, например основанные на вейвлетах Хаара. Более сложные неразделимые схемы кодирования обладают значительно лучшими характеристиками. Такие методы уже реализуются, поскольку имеют проработанный научный, алгоритмический и аппаратный базис. В частности, авторами предложен иерархический алгоритм кодирования ММ неразделимых сигналов с помощью неразделимой системы, который может быть применен для сжатия ММ-сигналов световых полей [16, 18].
Перспективные методы обработки ММ-сигналов
Один из наиболее перспективных подходов к обработке ММ-сигналов заключается в применении многоскоростных систем. Они состоят из многомерных цифровых фильтров и устройств изменения плотности отсчетов в пространственно-временной области. При этом сигнал раскладывают на частотные составляющие (подполосы) в соответствующих каналах устройства обработки и рассматривают на различных шкалах – более редкой (путем его прореживания или децимации) или более частой (путем его интерполяции, заключающейся в добавлении нулей между отсчетами сигнала). Поскольку в каждом из каналов плотность отсчетов сигнала различна, отличаются и скорости обработки. Потому подобные системы называют многоскоростными. Совокупность цифровых фильтров и устройств децимации/интерполяции называют банком фильтров (БФ).
Цифровые многоскоростные БФ были впервые описаны в работе [8], где они использовались для сжатия речи.
В дальнейшем они стали применяться шире, главным образом для кодирования подполос речи, статических изображений и видео [9]. При этом обычно предполагалось, что нет искажения сигнала.
Независимо от этих работ в прикладной математике была создана теория вейвлетов. С работами Добеши [10], Малла и Мейера стало ясно, что банки фильтров и вейвлеты связаны неразрывно. БФ вычисляют эквивалент дискретного вейвлет-преобразования (ДВП) и могут использоваться для получения непрерывных вейвлет-базисов.
Вейвлет-преобразования все шире применяют в задачах сжатия и обработки изображений и видео – нестационарных по своей природе. В этой области они позволяют снизить сложность кодеков и одновременно повысить их эффективность. Однако в действительно массовых приложениях, например в стандартах обработки и сжатия изображений, этот метод практически не используется. На сегодня только стандарт JPEG-2000 основывается на вейвлет-преобразовании, причем одномерном. А потенциал "истинной" (или неразделимой) обработки ММ-сигналов не реализован ни в одном стандарте по сжатию многомерных сигналов. Такие популярные стандарты, как MPEG-2 и MPEG-4 для видеосигналов, JPEG и JPEG-2000 для изображений, являются разделимыми системами. Поэтому исключительно важна задача синтеза и реализации многомерных многоскоростных систем и схем кратномасштабного вейвлет-анализа на их основе.
Известны уже многие области удачного и предпочтительного применения неразделимых БФ. Их основное достоинство – неразделимые вейвлеты позволяют эффективно обрабатывать детали изображения с произвольной (например, радиальной) пространственной ориентацией, в то время как разделимые алгоритмы хорошо работают лишь с ортогональными объектами. Это важно, в частности, при визуализации и анализе томографических изображений [11]. Успешно применяются неразделимые вейвлеты в 3-D вращательной ангиографии [12]. В некоторых случаях желательно использовать неразделимую децимацию, чтобы получить полезные 2-D вейвлет-представления. Например, неразделимые ортонормальные вейвлет-базисы могут использоваться для распознавания текстур и фрактального анализа [13]. В [14] показано, что неразделимые вейвлеты инвариантны к вращению изображения текстуры. Именно поэтому классификация и результаты сегментации оказываются лучше при использовании неразделимых симметричных вейвлетов. В области телевидения высокой четкости при преобразовании между прогрессивным и чересстрочным видео для оценки параметра движения широко используются трехмерные неразделимые фильтры [15]. Трехмерная согласованная фильтрация приводит к неразделимым фильтрам с наилучшим соотношением сигнал/шум среди всех линейных фильтров, когда пространственные характеристики объекта известны.
Многоскоростные системы обработки ММ-сигналов
Многоскоростные системы состоят из двух наборов (банков) фильтров – банка анализа и банка синтеза. Соединяя их в различном порядке (рис.3), можно получить различные устройства. Если сигнал в банке анализа раскладывается на подполосовые составляющие, а затем восстанавливается в банке анализа, такая система называется банком фильтров анализа/синтеза (рис.3а) – это устройство будем называть "многоскоростной системой" (устоявшегося названия нет).
Можно поменять местами банки анализа и синтеза так, чтобы набор сигналов подавался на вход банка синтеза (рис.3б). С его выхода комбинированный сигнал попадает в банк анализа, раскладывающий его на составляющие. Такая система называется банком фильтров синтеза/анализа или трансмультиплексором. Важно, что обе системы описываются одними и теми же типами уравнений. Поэтому решения, полученные для многоскоростных систем, в равной степени применимы как к трансмультиплексорам, так и к системам со многими входами и многими выходами MIMO (multiple inputs multiple outputs), интенсивно развиваемым с 1980-х годов и перспективных в современных телекоммуникационных приложениях. Задачу синтеза таких систем, включая случай, когда число входных сигналов отличается от числа выходных сигналов, позволяет решать аппарат многомерных полиномиальных полифазных матриц, развитый М.К.Чобану.
Банк анализа состоит из m фильтров Hi(z) и дециматоров ↓(Γ:Λ), осуществляющих переход от решетки Γ, на которой задан исходный сигнал, к более редкой подрешетке Λ. Банк синтеза состоит из интерполяторов ↑(Γ:Λ), реализующих переход от подрешетки Λ к более частой решетке Γ, и фильтров Fi(z), где z =(z1,..., zD) – D-мерная переменная z-преобразования сигнала, i = 0,...,m – 1. Мы рассмотрим максимально децимированную многоскоростную систему, когда число каналов m = |det M|, где M – матрица децимации, описывающая переход между Γ и Λ. На рис.3а показан только один уровень декомпозиции входного сигнала x(z) на m поддиапазонов (или подполос) Si(z). В общем случае такому разложению можно многократно подвергнуть любой из таких подполосовых сигналов.
В банке анализа каждый подполосовой сигнал несет в себе информацию о спектральной составляющей исходного ММ-сигнала при некотором пространственно-временном масштабе. Для его реконструкции (обратного синтеза) выполняется интерполяция подполосовых сигналов, их фильтрация и сложение. Большинство методов синтеза фильтров направлено на устранение искажений сигналов и наложений спектров (aliasing), возникающих при децимации.
Данная многоскоростная система может быть представлена ее эквивалентной эффективной схемой через полифазные полиномиальные матрицы [9]. В z-области фильтры банков анализа записываются через полифазные составляющие как
,
где сj ∈ N(M) – классы смежности матрицы децимации M [9, 16]. Тогда полифазная полиномиальная матрица фильтров банков анализа будет иметь вид
...
Аналогичные соотношения записываются для банков синтеза. Свойство точного восстановления сигнала теперь будет иметь вид
...,
где – выходной сигнал, zS -операция многомерного сдвига: . Выигрыш в эффективности данной системы обусловлен тем, что фильтруется не входной сигнал, а сигнал после децимации, который имеет в m раз меньше отсчетов. Если многоскоростная система реализована на параллельных структурах, то требования к быстродействию каждого вычислителя в m раз меньше, чем при реализации на одном вычислителе.
Основные процедуры синтеза фильтров банков анализа и синтеза сводятся к синтезу полифазных матриц Hp(z) и Fp(z) [17–23]. Причем различают два класса банков фильтров. В биортогональных БФ фильтры в банке анализа Hp(z) и синтеза Fp(z), различны, но Hp⋅Fp = I. Ортогональные БФ используют параунитарные полифазные матрицы Hp(z) и Fp(z), такие что Fp(z) = H-1p(z) = H~Tp(z-1), где H~p– комплексно-сопряженная с Нp матрица, H~ Tp(z-1)⋅Hp(z) = I. Поэтому для синтеза ортогональных БФ достаточно построить меньшее число фильтров, чем для биортогональных.
Новые результаты в неразделимом кодировании ММ-сигналов
В последнее время самые эффективные из кодеров используют вейвлет-декомпозицию сигнала, например таким является стандартизованный кодер JPEG-2000. Однако известно немало не стандартизованных, но не менее эффективных алгоритмов. Один из них – алгоритм иерархического кодирования, который уже можно считать классическим. На его базе развиваются новые алгоритмы, и в оценках эффективности любого нового вейвлет-кодера обязательно есть сравнительные тесты с данным алгоритмом. Кодеры, работающие с вейвлет-декомпозицией, принято делить на два класса: межполосные (inter-band) и внутриполосные (intra-band). Алгоритм иерархического кодирования относится к классу межполосных кодеров, т.е. в своей работе он использует избыточность, связанную с корреляцией между уровнями декомпозиции (уровнями вейвлет-преобразования).
Одним из важных свойств вейвлет-преобразования является его способность перераспределять энергию сигнала, концентрируя ее в малом числе каналов. Для пояснения рассмотрим простейшее вейвлет-преобразование с помощью БФ Хаара над одномерной выборкой х = (х1, х2,..., х8) например (1, 2, 3, 4, 5, 6, 7, 8). Суть преобразования – выборка разбивается на пары (х1 и х2, х3 и х4, х5 и х6, х7 и х8), для каждой из них вычисляется полусумма [(х1 + х2)/ 2,...,(х7 + х8)/2] и полуразность [(х2 – х1)/2,...(х8 – х7)/2]). В нашем примере вектор полусумм и полуразностей выгдядит как (1,5; 3,5; 5,5; 7,5; 0,5; 0,5; 0,5; 0,5). Это – первый уровень декомпозиции выборки. Далее аналогичный алгоритм применяется к вектору полусумм (второй уровень преобразования) –
получается (2,5; 6,5; 1; 1; 0,5; 0,5; 0,5; 0,5). На третьем уровне, по аналогии, получаем (4,5; 2; 1; 1; 0,5; 0,5; 0,5; 0,5) – т.е. крайний левый элемент принял значение среднего для всей исходной выборки. Зная алгоритм и значения, можно восстановить исходную последовательность. Если же применить вейвлет-декомпозицию также к последней четверке отсчетов, то выигрыш заметен на глаз –
на втором уровне получим (2,5; 6,5; 1; 1; 0,5; 0,5; 0; 0),
а после третьего – (4,5; 2; 1; 1; 0,5; 0; 0; 0) – то есть три коэффициента из восьми в точности равны нулю! При сжатие с потерей данных можно задаться неким порогом и отбросить (приравнять 0) элементы, модуль которых меньше порога.
В двумерном случае (например, для изображения) используется разделимое вейвлет-преобразование. Один из возможных вариантов сводится к поочередному применению одномерных преобразований сначала ко всем строкам, затем –
к получившимся столбцам и т.д. (рис.4), до тех пор, пока в левом верхнем углу (LL) не окажутся значения, которые нельзя далее преобразовывать.
С точки зрения цифровой фильтрации это эквивалентно тому, что исходный сигнал разбивается на подполосы,
и энергия сигнала концентрируется в одной, низкочастотной (НЧ, LL – Low-Low) подполосе (см. рис.4). Для квантования областей с низкой энергией отводится меньше бит, что обеспечивает сжатие. Однако такой подход не учитывает того факта, что в высокочастотных (ВЧ, H – High) подполосах коэффициенты сохраняют структуру резких переходов яркости (контуров изображения). Действительно, области с высокой энергией повторяют от подполосы к подполосе свои очертания и местоположение. И это неудивительно, так как они появляются вокруг контуров в исходном изображении – там, где вейвлет-преобразование на высоких уровнях не может адекватно представить сигнал в НЧ-областях, что приводит к "утечке" части энергии в ВЧ-подполосы. Медленно же изменяющиеся гладкие области (например, фон) исходного изображения полностью описывают коэффициенты НЧ-подполос (концентрация энергии в НЧ-областях), что позволяет их представить малым числом коэффициентов. Это справедливо на всех уровнях декомпозиции, что и приводит к визуальному подобию различных подполос.
Априорное знание того, что изображение состоит из гладких областей, текстур и контуров, позволяет строить эффективные алгоритмы, учитывающие подобие подполос. Первыми использовать это свойство вейвлет-разложения предложили Льюис и Ноулес [24]. Их алгоритм базировался на построении пространственных деревьев над полем вейвлет-коэффициентов (граф, связывающий подобные группы коэффициентов на различных уровнях вейвлет-разложения). В 1993 году Шапиро [25] разработал алгоритм вложенных нуль-деревьев (embedded zero-tree wavelets – EZW) для сжатия изображения –
очень эффективный и с малой вычислительной сложностью. На этой работе основано семейство алгоритмов, построенных на сортировке вейвлет-коэффициентов по степени их вклада в качество результирующего изображения (для их последующей последовательной передачи).
В 1996 году Саид и Пирлманн [26] создали улучшенный метод кодирования изображений при помощи пространственно-упорядоченных иерархических деревьев (SPIHT – set partitioning into hierarchical trees). Полученные результаты не уступали EZW, однако структура алгоритма была существенно проще, а скорость выше. Алгоритм SPIHT получил широкую известность и де-факто стал одним из стандартных алгоритмов сжатия изображений на основе вейвлетов. Однако до недавнего времени была известна только его одномерная версия, на основе разделимых фильтров.
Свойство видимого подобия различных уровней декомпозиции лежит в основе алгоритмов на основе разделимых БФ, так как метод построения деревьев (поиск подобия) подразумевает определенную структуру и расположение подполос на плоскости. Однако при использовании неразделимого банка фильтров подобие между подполосами нарушается (рис.5). Ведь если используется два БФ (с НЧ- и ВЧ-фильтром), то для сохранения общего числа отсчетов в каждом из каналов необходима децимация на 2 (нужно отбросить каждый второй отсчет после фильтра) – в данном случае применяется "шахматная" матрица децимации (рис.6). На нечетных уровнях декомпозиции после неразделимой фильтрации и децимации изображение поворачивается на 45° (принимает вид ромба) и зеркально отображается. Действительно, коэффициенты в двумерном массиве должны располагаться без "пропусков", связанных с удалением отсчетов при децимации. При "шахматной" матрице децимации такое возможно, только если считать, что строки массива пикселов располагаются по диагоналям "шахматной доски" – т.е. повернуть картинку на 45°. Если же, например, сдвинуть ("схлопнуть") отсчеты продецимированного сигнала (см. рис. 6б), то сигнал исказится. Его дальнейший анализ будет правомерным, только если соответствующим образом исказить импульсные характеристики фильтров. Иначе нарушатся геометрические соотношения и относительное расположение коэффициентов (пикселов).
Таким образом, неразделимое преобразование нарушает принцип подобия вейвлет-разложения. То есть подобие высокочастотных подполос при неразделимой фильтрации сохраняется, но процесс построения деревьев с переходом через раз от прямоугольных к ромбическим формам изображения неоправданно сложен и трудоемок – нельзя использовать уже наработанные методы, такие структуры сложнее хранить в памяти, визуализировать, существенно затруднен их анализ. Это затрудняет практическое применение данного класса фильтров, несмотря на компактность структуры.
Авторами предложено простое и эффективное решение этой проблемы [18]. Ведь можно искажать и сам сигнал,
и импульсную характеристику фильтра так, чтобы сохранить все геометрические соотношения. При этом сдвиг отсчетов будет только визуальным (рис.7)– "растянутое" по вертикали изображение из-за его схлопывания (см.рис.6б),
но с точки зрения фильтрации все остается на своих местах [18]. Сохраняется подобие полос вейвлет-коэффициентов для различных уровней декомпозиции, при этом возможно ненулевое расширение сигнала при фильтрации.
Результаты моделирования
Авторами создана система кодирования ММ-сигналов (двумерных изображений, видеосигналов, результатов компьютерной томографии) на основе разработанных ММ БФ,
а также специальных иерархических алгоритмов и методов вложенного кодирования. На первом этапе (рис.8) цветные изображения преобразуются из системы RGB в YIQ (или другую). Затем каждая из составляющих проходит дискретное вейвлет-преобразование, квантование и кодирование. Работа кодеров существенно зависит от используемых БФ (рис.9). Синтезированные нами неразделимые фильтры (биортогональный bern3.3 и ортогональный K5.3) в основном дают лучшие результаты сжатия, чем разделимые (биортогональный bior3.3) с той же степенью гладкости. Тесты говорят о большей приспособленности иерархического алгоритма к изображениям с малым числом контуров и резких переходов, которые хорошо аппроксимируются вейвлетами. Результаты кодирования изображений с помощью разработанного алгоритма (используя разделимые фильтры и аналитически синтезированный ортогональный фильтр) лучше результатов применения JPEG-2000 по пиковому соотношению сигнал / шум на 1–1,5 дБ в зависимости от коэффициента сжатия и обрабатываемого изображения (рис.10).
Аппаратная реализация алгоритма сжатия изображений
Процесс разработки неразделимого метода сжатия сопровождался его программной реализацией. Приложение позволяет кодировать изображения в формате BMP – как цветные, так и в градации серого. Степень сжатия задается произвольно, также можно задавать точный размер выходного файла в байтах, что является несомненным преимуществом кодера. Выходной файл в оригинальном формате SPT можно декодировать в формат BMP.
Для реализации сложных алгоритмов необходима адекватная вычислительная платформа. Поскольку задачи обработки ММ-сигналов широко распространены, вычислительные платформы должны быть массовыми и относительно недорогими. В качестве таких платформ можно рассматривать процессоры современных видеокарт для персональных компьютеров – "графические" процессоры (GPU). Сама идея применения графического процессора в качестве базы для параллельных вычислений не нова. В современной информатике образовалось новое направление – вычисления общего назначения на GPU (GPGPU – General-Purpose computations on GPUs, см. www.gpgpu.org).
Благодаря мировой многомиллиардной индустрии компьютерных игр высокопроизводительные видеокарты развиваются чрезвычайно интенсивно. Фактически они представляют собой процессор параллельной обработки. По вычислительной мощности видеокарты намного опережают процессоры общего назначения, их производительность растет быстрее, чем предполагается законом Мура. Причем в отличие от специального оборудования (спецвычислителей, видеоускорителей и т.п.) на основе сигнальных процессоров, ПЛИС и др., видеокарты – это массовый продукт, а потому относительно дешевый. Например, одну из наиболее мощных видеокарт GeForce 7950 GX2 можно купить за 560 долл., чуть менее производительную GeForce 7900 GT – за 300 долл. Более простые видеокарты, например GeForce 6200, стоят 60 долл.
Самая мощная на момент написания статьи игровая видеокарта Nvidia GeForce 7950 GX2 имеет 16 вершинных и 48 пиксельных конвейеров и способна одновременно обрабатывать 48 пикселов. Входными массивами для видеокарты служат текстуры, т.е. двух- или трехмерные изображения с 32-разрядными отсчетами с плавающей точкой. Современные видеокарты обеспечивают программный доступ как минимум к 12 различным массивам (текстурам). Выходными массивами данных также являются текстуры. Одновременно можно выводить от четырех и более таких массивов.
Используя возможности современных видеокарт, мы реализовали как неразделимые, так и разделимые алголритмы двумерной фильтрации. Для наглядности рассмотрим алгоритм двумерной разделимой вейвлет-обработки на GPU (рис.11). Один уровень ДВП на GPU выполняется в два прохода. Сначала исходная картинка фильтруется двумя 1-D фильтрами, децимируется по горизонтали и выводится в виде двух промежуточных текстур. Затем обе эти текстуры параллельно фильтруются и децимируются по вертикали,
в результате получается четыре массива – подполосы первого уровня ДВП. LL-подполосу можно вновь пропустить через ту же систему обработки и получить еще четыре подполосы второго уровня и т.д. Тем самым реализуется многоуровневое вейвлет-преобразование.
С помощью GPU можно совместить подполосы в пределах одной текстуры. Для этого достаточно последовательно нарисовать четыре прямоугольника с текстурой подполосы и вывести в виде новой текстуры. И, наоборот, чтобы разделить подполосы (для обратного преобразования), достаточно для вершин прямоугольника задать соответствующие текстурные координаты.
Описанный алгоритм 2-D обработки изображения был реализован (рис.12) на двух различных видеокартах (nVidia GeForce 7900 GТ и GeForce 6600 GТ) и на базе универсального центрального процессора Intel PentiumD 945 Dual Core 3,4 ГГц персонального компьютера с 2 Гбайт ОЗУ (667 MГц). Видеокарта nVidia GeForce 7900 GТ (производитель – XFX) содержала 1 Гбайт ОЗУ (550/1300 МГц). Операционная система – Windows XP SP2; DirectX 9.0c (август 2006). Тестовая программа написана с использованием Direct3D. Исходные изображения были в формате RGB (24 бит/пиксел), промежуточные текстуры – в формате A16B16G16R16F (64 бит/ пиксел). Время расчета одного уровня ДВП включает также время загрузки/выгрузки текстуры по шине.
С увеличением размера картинки производительность системы возрастает и достигает своего максимального значения. Это обусловлено тем, что резко уменьшается что доля "накладных расходов" (в виде времени на пересылку данных и др.).
Таким образом, нам удалось на практике реализовать многоскоростную систему неразделимой фильтрации для многомерных сигналов, включая процедуры синтеза фильтров. Предложенные алгоритмы реализуются на массовых и недорогих вычислительных платформах – видеокартах персональных компьютеров. Это доказывает, что современный уровень достижений в области цифровой обработки многомерных сигналов – теоретических, алгоритмических, програмно-аппаратных – позволяет создавать принципиально новые цифровые телекоммуникационные и мультимедийные системы, в том числе – системы трехмерного телевидения.
Работа выполнена при содействии совместного гранта РФФИ и японского общества JSPS №06-07-91751-ЯФ_а
Литература
1. Fehn C. Depth-Image-Based Rendering (DIBR), compression and transmission for a new approach on 3D-TV. – Proc. SPIE Stereoscopic Displays and Virtual Reality Systems XI. – San Jose, CA: 2004, p.93–104.
2. Liao H., Nomura K., Dohi T. Long visualization depth autostereoscopic display using light field rendering based integral videography. – Proc. Virtual Reality Conference, 2006, p.8–11.
3. H. Liao, I. Makoto, K. Takefumi et al. Scalable high-resolution integral videography autostereoscopic display with a seamless multiprojection system. – Applied Optics, 2005, Vol. 44, N.3, p.305–315.
4. Three Dimensional Images in the Air. – Advanced Industrial Science and Technology. – ww.aist.go.jp/aist_e/latest_research/2006/20060210/20060210.html.
5. C.Chang, X.Zhu, P.Ramanathan, B.Girod. Light field compression using disparity-compensated lifting and shape adaptation. – IEEE Trans. Image Proc., 2006, Apr., Vol. 15, N. 4, p.793–806.
6. Чобану М. К., Черников А. В. Современный метод сжатия изображений на базе вейвлет-преобразования и иерархического алгоритма кодирования. – Цифровая обработка сигналов, 2005, №3, с. 40–59.
7. H. Lensch, M. Magnor, H.-P.Seidel, G. Ziegler. Multi-Video Compression in Texture Space using 4D SPIHT. – Proc. MMSP'04б, Siena, Italy, 2004.
8. Croisier A., Esteban D., Galaud C. Perfect channel splitting by use of interpolation/deci-mation/tree decomposition techniques. – Intern. Confer. Inform. Sci. Syst. Greece: 1976, p.443-446.
9. Vaidyanathan P.P. Multirate Systems and Filter Banks. – Englewood Cliffs: Prentice Hall, 1993.
10. Добеши И. 10 лекций по вейвлетам. – Ижевск: НИЦ: Регулярная и хаотическая динамика, 2001.
11. S. Bonnet, F. Peyrin, F. Turjman, R. Prost. Tomographic reconstruction using nonseparable wavelets. – IEEE Trans. Image Proc., 2000, Aug., Vol. 9, N. 8, p.1445–1450.
12. S. Bonnet, F. Peyrin, F. Turjman, R. Prost. Nonseparable wavelet-based cone-beam reconstruction in 3-D rotational angiography. – IEEE Trans. Medical Imaging. 2003, Mar., Vol. 22, N. 3, p.360–367.
13. Meyer Y. Ondelettes et fonctions splines. – em. Equations aux Derivees Parielles edition, 1986.
14. Wang J.-W., Chen C.-H., Pan J.-S. Genetic feature selection for texture classification using 2-D non-separable wavelet bases. – IEICE Trans. Fundament, 1998, Aug., Vol. E81-A, N.8, p.1635–1644.
15. F. Mujica, J.-P.Leduc, R. Murenzi, M. Smith. A new motion parameter estimation algorithm based on the continuous wavelet transform. – IEEE Trans. Image Proc. 2000, May, Vol. 9, N. 5, p.873–888.
16. Чобану М. К., Максименко И. Е. Синтез двухканальных многомерных вейвлетов и их применение для сжатия изображений. – Вестник МЭИ, 2006, №2, с. 88–96.
17. Чобану М. К. Многомерные многоскоростные системы и многомерные вейвлет функции. Часть II. Синтез. – Вестник МЭИ, 2003, №3, с. 69–78.
18. Чобану М. К. Иерархический алгоритм кодирования для неразделимых решеток и банков фильтров. – Вычислительные технологии, 2007, №8.
19. Чобану М. К. Синтез многомерных банков фильтров с помощью методов компьютерной алгебры. – Известия вузов. Электроника, 2007, №2, с. 50–59.
20. Чобану М. К. Синтез ортогональных многомерных банков фильтров с помощью преобразования Кэли. – Электричество, 2007, №4, с. 57–60.
21. Чобану М. К. Синтез оптимизированных многомерных банков фильтров. – Научный Вестник МГТУ ГА/ Серия Радиофизика и радиотехника, 2007, №117.
22. Чобану М. К. Системы многоскоростной обработки многомерных сигналов. Часть II. Методы полиномиального синтеза. – Проблемы управления, 2007, №3, с. 46–53.
23. Чобану М. К. Аналитический синтез многомерных многоскоростных систем. – Успехи современной радиоэлектроники, 2007, №4, с. 61–80.
24. Lewis A., Knowles G. Image compression using the 2-d wavelet transform. – IEEE Trans. Image Proc., 1992, Vol. 2, p.244-250.
25. Shapiro J. M. Embedded image coding using zerotrees of wavelets coefficients. – IEEE Trans. Signal Proc., 1993, Dec., Vol. 41, p.3445–3462.
26. Said A., Pearlman W. A. A new fast and efficient image codec based on set partitioning in hierarchical trees. – IEEE Trans. Circ., Syst. for Video Technol., 1996, Vol. 6, p.243–250.
Интерес к решению задач анализа, синтеза и обработки многомерных (ММ) сигналов непрерывно растет. Это связано с бурным развитием таких областей, как мультимедиа-технологии и телекоммуникации, в которых необходимы обработка и сжатие неподвижных изображений, видеосигналов и меняющихся во времени трехмерных сигналов.
Под многомерными (ММ) понимаются сигналы, зависящие от нескольких координат, пространственных и/или временной. Это двумерные (2-D) неподвижные изображения, трехмерные (3-D) томографические снимки или видеосигналы, четырехмерные (4-D) томографические сигналы, зависящие от времени. Эффективным способом преобразования таких сигналов является применение так называемых многомерных многоскоростных систем. С их помощью сигнал может быть представлен в виде, более удобном для решения многих прикладных задач, таких, как сжатие (с потерями или без потерь), удаление шумов, распознавание образов и др. Многомерные сигналы зачастую обрабатываются как одномерные, после замены всех переменных на одну. До недавнего времени многомерные операторы цифровых систем были представлены в виде прямого (или тензорного) произведения одномерных функций координат. Но это не соответствует природе реальных сигналов, являющихся неразделимыми многомерными. Под неразделимым многомерным сигналом понимают такой, который нельзя задать в виде прямого произведения одномерных функций. Например, обычный круг, задаваемый функцией х2 + у2 ≤ R2 невозможно представить в виде произведения функций от одной координаты, т.е. в виде f1(x) f2(y).
Одно из направлений, которое может получить мощный импульс развития при создании эффективных программно-аппаратных средств обработки ММ-сигналов, – трехмерное телевидение (3D-TV).
Трехмерное телевидение (3D-TV)
Известно несколько систем 3D-TV. Первыми были 3-D мониторы австралийской компании DDD с 7–9 точками съемки, а также европейская система ATTEST (Advanced Three-Dimensional Television Systems Technologies), разрабатываемая в рамках проекта IST. В последней системе сигнал включает как видеоинформацию, так и сведения о глубине. Для сжатия подобных сигналов используется стандарт MPEG-2 [1]. Впервые система трехмерного телевидения была представлена Фраунгоферовским институтом (Fraunhofer Nachrichtentechnik Heinrich-Hertz-Institut) на Международной конференции International Broadcast Convention в 2004 году.
В Токийском Университете (Япония) создан монитор для удаленного просмотра 3-D изображений компьютерной графики без каких-либо дополнительных очков [2, 3]. С помощью элементарных линз многопучковой системы монитор передает 3-D изображения глубиной до 5,7 м перед монитором и до 3,5 м вглубь монитора (рис.1).
В Национальном Институте AIST (National Institute of Advanced Industrial Science and Technology) и в Университете Кейо в сотрудничестве с компанией Burton было создано устройство отображения 3-D изображений, состоящих из массивов точек в воздухе [4]. Разработанное устройство отображения использует эффект плазменной эмиссии около точки фокусировки лазерного луча. Управляя положением фокусной точки по трем осям, можно изображать массивы точек (рис.2). Аналогичных результатов достигла и компания IO2 Technology с устройством Heliodisplay. К тому же, Heliodisplay является интерактивным устройством – по объемному изображению можно перемещать палец, используя его как указатель курсора.
Одна из основных задач, которые встают перед разработчиками 3D-TV, – сжатие 4-D и 5-D сигналов. Существует два подхода к сжатию световых полей с учетом компенсации разницы между видами с различных точек съемки: кодеры, основанные на предсказании, и кодеры, которые параметризуют виды в различные текстуры. Кодеры первого типа допускают параметризацию по числу точек съемки, однако они не масштабируемы по качеству и разрешению. В кодерах второго типа используется явная геометрическая модель системы регистрации многомерного сигнала, чтобы привести все виды к единой системе координат. Световые поля сначала приводятся к поверхности геометрической модели и формируют так называемое поверхностное световое поле. При этом создаются частичные текстуры объектов, видимые с различных точек, – MVV-текстуры (Multi-View Video). В результате формируется 4-D массив по координатам: вид/камера (или угол поворота камеры), время и две пространственные координаты. Такой массив может быть сжат далее с помощью методов обработки ММ-сигналов на основе иерархических алгоритмов [5], например 4-D иерархического метода, подобного SPIHT [6, 7].
Отметим, что на сегодня реализованы только простейшие разделимые иерархические 4-D SPIHT-кодеры, например основанные на вейвлетах Хаара. Более сложные неразделимые схемы кодирования обладают значительно лучшими характеристиками. Такие методы уже реализуются, поскольку имеют проработанный научный, алгоритмический и аппаратный базис. В частности, авторами предложен иерархический алгоритм кодирования ММ неразделимых сигналов с помощью неразделимой системы, который может быть применен для сжатия ММ-сигналов световых полей [16, 18].
Перспективные методы обработки ММ-сигналов
Один из наиболее перспективных подходов к обработке ММ-сигналов заключается в применении многоскоростных систем. Они состоят из многомерных цифровых фильтров и устройств изменения плотности отсчетов в пространственно-временной области. При этом сигнал раскладывают на частотные составляющие (подполосы) в соответствующих каналах устройства обработки и рассматривают на различных шкалах – более редкой (путем его прореживания или децимации) или более частой (путем его интерполяции, заключающейся в добавлении нулей между отсчетами сигнала). Поскольку в каждом из каналов плотность отсчетов сигнала различна, отличаются и скорости обработки. Потому подобные системы называют многоскоростными. Совокупность цифровых фильтров и устройств децимации/интерполяции называют банком фильтров (БФ).
Цифровые многоскоростные БФ были впервые описаны в работе [8], где они использовались для сжатия речи.
В дальнейшем они стали применяться шире, главным образом для кодирования подполос речи, статических изображений и видео [9]. При этом обычно предполагалось, что нет искажения сигнала.
Независимо от этих работ в прикладной математике была создана теория вейвлетов. С работами Добеши [10], Малла и Мейера стало ясно, что банки фильтров и вейвлеты связаны неразрывно. БФ вычисляют эквивалент дискретного вейвлет-преобразования (ДВП) и могут использоваться для получения непрерывных вейвлет-базисов.
Вейвлет-преобразования все шире применяют в задачах сжатия и обработки изображений и видео – нестационарных по своей природе. В этой области они позволяют снизить сложность кодеков и одновременно повысить их эффективность. Однако в действительно массовых приложениях, например в стандартах обработки и сжатия изображений, этот метод практически не используется. На сегодня только стандарт JPEG-2000 основывается на вейвлет-преобразовании, причем одномерном. А потенциал "истинной" (или неразделимой) обработки ММ-сигналов не реализован ни в одном стандарте по сжатию многомерных сигналов. Такие популярные стандарты, как MPEG-2 и MPEG-4 для видеосигналов, JPEG и JPEG-2000 для изображений, являются разделимыми системами. Поэтому исключительно важна задача синтеза и реализации многомерных многоскоростных систем и схем кратномасштабного вейвлет-анализа на их основе.
Известны уже многие области удачного и предпочтительного применения неразделимых БФ. Их основное достоинство – неразделимые вейвлеты позволяют эффективно обрабатывать детали изображения с произвольной (например, радиальной) пространственной ориентацией, в то время как разделимые алгоритмы хорошо работают лишь с ортогональными объектами. Это важно, в частности, при визуализации и анализе томографических изображений [11]. Успешно применяются неразделимые вейвлеты в 3-D вращательной ангиографии [12]. В некоторых случаях желательно использовать неразделимую децимацию, чтобы получить полезные 2-D вейвлет-представления. Например, неразделимые ортонормальные вейвлет-базисы могут использоваться для распознавания текстур и фрактального анализа [13]. В [14] показано, что неразделимые вейвлеты инвариантны к вращению изображения текстуры. Именно поэтому классификация и результаты сегментации оказываются лучше при использовании неразделимых симметричных вейвлетов. В области телевидения высокой четкости при преобразовании между прогрессивным и чересстрочным видео для оценки параметра движения широко используются трехмерные неразделимые фильтры [15]. Трехмерная согласованная фильтрация приводит к неразделимым фильтрам с наилучшим соотношением сигнал/шум среди всех линейных фильтров, когда пространственные характеристики объекта известны.
Многоскоростные системы обработки ММ-сигналов
Многоскоростные системы состоят из двух наборов (банков) фильтров – банка анализа и банка синтеза. Соединяя их в различном порядке (рис.3), можно получить различные устройства. Если сигнал в банке анализа раскладывается на подполосовые составляющие, а затем восстанавливается в банке анализа, такая система называется банком фильтров анализа/синтеза (рис.3а) – это устройство будем называть "многоскоростной системой" (устоявшегося названия нет).
Можно поменять местами банки анализа и синтеза так, чтобы набор сигналов подавался на вход банка синтеза (рис.3б). С его выхода комбинированный сигнал попадает в банк анализа, раскладывающий его на составляющие. Такая система называется банком фильтров синтеза/анализа или трансмультиплексором. Важно, что обе системы описываются одними и теми же типами уравнений. Поэтому решения, полученные для многоскоростных систем, в равной степени применимы как к трансмультиплексорам, так и к системам со многими входами и многими выходами MIMO (multiple inputs multiple outputs), интенсивно развиваемым с 1980-х годов и перспективных в современных телекоммуникационных приложениях. Задачу синтеза таких систем, включая случай, когда число входных сигналов отличается от числа выходных сигналов, позволяет решать аппарат многомерных полиномиальных полифазных матриц, развитый М.К.Чобану.
Банк анализа состоит из m фильтров Hi(z) и дециматоров ↓(Γ:Λ), осуществляющих переход от решетки Γ, на которой задан исходный сигнал, к более редкой подрешетке Λ. Банк синтеза состоит из интерполяторов ↑(Γ:Λ), реализующих переход от подрешетки Λ к более частой решетке Γ, и фильтров Fi(z), где z =(z1,..., zD) – D-мерная переменная z-преобразования сигнала, i = 0,...,m – 1. Мы рассмотрим максимально децимированную многоскоростную систему, когда число каналов m = |det M|, где M – матрица децимации, описывающая переход между Γ и Λ. На рис.3а показан только один уровень декомпозиции входного сигнала x(z) на m поддиапазонов (или подполос) Si(z). В общем случае такому разложению можно многократно подвергнуть любой из таких подполосовых сигналов.
В банке анализа каждый подполосовой сигнал несет в себе информацию о спектральной составляющей исходного ММ-сигнала при некотором пространственно-временном масштабе. Для его реконструкции (обратного синтеза) выполняется интерполяция подполосовых сигналов, их фильтрация и сложение. Большинство методов синтеза фильтров направлено на устранение искажений сигналов и наложений спектров (aliasing), возникающих при децимации.
Данная многоскоростная система может быть представлена ее эквивалентной эффективной схемой через полифазные полиномиальные матрицы [9]. В z-области фильтры банков анализа записываются через полифазные составляющие как
,
где сj ∈ N(M) – классы смежности матрицы децимации M [9, 16]. Тогда полифазная полиномиальная матрица фильтров банков анализа будет иметь вид
...
Аналогичные соотношения записываются для банков синтеза. Свойство точного восстановления сигнала теперь будет иметь вид
...,
где – выходной сигнал, zS -операция многомерного сдвига: . Выигрыш в эффективности данной системы обусловлен тем, что фильтруется не входной сигнал, а сигнал после децимации, который имеет в m раз меньше отсчетов. Если многоскоростная система реализована на параллельных структурах, то требования к быстродействию каждого вычислителя в m раз меньше, чем при реализации на одном вычислителе.
Основные процедуры синтеза фильтров банков анализа и синтеза сводятся к синтезу полифазных матриц Hp(z) и Fp(z) [17–23]. Причем различают два класса банков фильтров. В биортогональных БФ фильтры в банке анализа Hp(z) и синтеза Fp(z), различны, но Hp⋅Fp = I. Ортогональные БФ используют параунитарные полифазные матрицы Hp(z) и Fp(z), такие что Fp(z) = H-1p(z) = H~Tp(z-1), где H~p– комплексно-сопряженная с Нp матрица, H~ Tp(z-1)⋅Hp(z) = I. Поэтому для синтеза ортогональных БФ достаточно построить меньшее число фильтров, чем для биортогональных.
Новые результаты в неразделимом кодировании ММ-сигналов
В последнее время самые эффективные из кодеров используют вейвлет-декомпозицию сигнала, например таким является стандартизованный кодер JPEG-2000. Однако известно немало не стандартизованных, но не менее эффективных алгоритмов. Один из них – алгоритм иерархического кодирования, который уже можно считать классическим. На его базе развиваются новые алгоритмы, и в оценках эффективности любого нового вейвлет-кодера обязательно есть сравнительные тесты с данным алгоритмом. Кодеры, работающие с вейвлет-декомпозицией, принято делить на два класса: межполосные (inter-band) и внутриполосные (intra-band). Алгоритм иерархического кодирования относится к классу межполосных кодеров, т.е. в своей работе он использует избыточность, связанную с корреляцией между уровнями декомпозиции (уровнями вейвлет-преобразования).
Одним из важных свойств вейвлет-преобразования является его способность перераспределять энергию сигнала, концентрируя ее в малом числе каналов. Для пояснения рассмотрим простейшее вейвлет-преобразование с помощью БФ Хаара над одномерной выборкой х = (х1, х2,..., х8) например (1, 2, 3, 4, 5, 6, 7, 8). Суть преобразования – выборка разбивается на пары (х1 и х2, х3 и х4, х5 и х6, х7 и х8), для каждой из них вычисляется полусумма [(х1 + х2)/ 2,...,(х7 + х8)/2] и полуразность [(х2 – х1)/2,...(х8 – х7)/2]). В нашем примере вектор полусумм и полуразностей выгдядит как (1,5; 3,5; 5,5; 7,5; 0,5; 0,5; 0,5; 0,5). Это – первый уровень декомпозиции выборки. Далее аналогичный алгоритм применяется к вектору полусумм (второй уровень преобразования) –
получается (2,5; 6,5; 1; 1; 0,5; 0,5; 0,5; 0,5). На третьем уровне, по аналогии, получаем (4,5; 2; 1; 1; 0,5; 0,5; 0,5; 0,5) – т.е. крайний левый элемент принял значение среднего для всей исходной выборки. Зная алгоритм и значения, можно восстановить исходную последовательность. Если же применить вейвлет-декомпозицию также к последней четверке отсчетов, то выигрыш заметен на глаз –
на втором уровне получим (2,5; 6,5; 1; 1; 0,5; 0,5; 0; 0),
а после третьего – (4,5; 2; 1; 1; 0,5; 0; 0; 0) – то есть три коэффициента из восьми в точности равны нулю! При сжатие с потерей данных можно задаться неким порогом и отбросить (приравнять 0) элементы, модуль которых меньше порога.
В двумерном случае (например, для изображения) используется разделимое вейвлет-преобразование. Один из возможных вариантов сводится к поочередному применению одномерных преобразований сначала ко всем строкам, затем –
к получившимся столбцам и т.д. (рис.4), до тех пор, пока в левом верхнем углу (LL) не окажутся значения, которые нельзя далее преобразовывать.
С точки зрения цифровой фильтрации это эквивалентно тому, что исходный сигнал разбивается на подполосы,
и энергия сигнала концентрируется в одной, низкочастотной (НЧ, LL – Low-Low) подполосе (см. рис.4). Для квантования областей с низкой энергией отводится меньше бит, что обеспечивает сжатие. Однако такой подход не учитывает того факта, что в высокочастотных (ВЧ, H – High) подполосах коэффициенты сохраняют структуру резких переходов яркости (контуров изображения). Действительно, области с высокой энергией повторяют от подполосы к подполосе свои очертания и местоположение. И это неудивительно, так как они появляются вокруг контуров в исходном изображении – там, где вейвлет-преобразование на высоких уровнях не может адекватно представить сигнал в НЧ-областях, что приводит к "утечке" части энергии в ВЧ-подполосы. Медленно же изменяющиеся гладкие области (например, фон) исходного изображения полностью описывают коэффициенты НЧ-подполос (концентрация энергии в НЧ-областях), что позволяет их представить малым числом коэффициентов. Это справедливо на всех уровнях декомпозиции, что и приводит к визуальному подобию различных подполос.
Априорное знание того, что изображение состоит из гладких областей, текстур и контуров, позволяет строить эффективные алгоритмы, учитывающие подобие подполос. Первыми использовать это свойство вейвлет-разложения предложили Льюис и Ноулес [24]. Их алгоритм базировался на построении пространственных деревьев над полем вейвлет-коэффициентов (граф, связывающий подобные группы коэффициентов на различных уровнях вейвлет-разложения). В 1993 году Шапиро [25] разработал алгоритм вложенных нуль-деревьев (embedded zero-tree wavelets – EZW) для сжатия изображения –
очень эффективный и с малой вычислительной сложностью. На этой работе основано семейство алгоритмов, построенных на сортировке вейвлет-коэффициентов по степени их вклада в качество результирующего изображения (для их последующей последовательной передачи).
В 1996 году Саид и Пирлманн [26] создали улучшенный метод кодирования изображений при помощи пространственно-упорядоченных иерархических деревьев (SPIHT – set partitioning into hierarchical trees). Полученные результаты не уступали EZW, однако структура алгоритма была существенно проще, а скорость выше. Алгоритм SPIHT получил широкую известность и де-факто стал одним из стандартных алгоритмов сжатия изображений на основе вейвлетов. Однако до недавнего времени была известна только его одномерная версия, на основе разделимых фильтров.
Свойство видимого подобия различных уровней декомпозиции лежит в основе алгоритмов на основе разделимых БФ, так как метод построения деревьев (поиск подобия) подразумевает определенную структуру и расположение подполос на плоскости. Однако при использовании неразделимого банка фильтров подобие между подполосами нарушается (рис.5). Ведь если используется два БФ (с НЧ- и ВЧ-фильтром), то для сохранения общего числа отсчетов в каждом из каналов необходима децимация на 2 (нужно отбросить каждый второй отсчет после фильтра) – в данном случае применяется "шахматная" матрица децимации (рис.6). На нечетных уровнях декомпозиции после неразделимой фильтрации и децимации изображение поворачивается на 45° (принимает вид ромба) и зеркально отображается. Действительно, коэффициенты в двумерном массиве должны располагаться без "пропусков", связанных с удалением отсчетов при децимации. При "шахматной" матрице децимации такое возможно, только если считать, что строки массива пикселов располагаются по диагоналям "шахматной доски" – т.е. повернуть картинку на 45°. Если же, например, сдвинуть ("схлопнуть") отсчеты продецимированного сигнала (см. рис. 6б), то сигнал исказится. Его дальнейший анализ будет правомерным, только если соответствующим образом исказить импульсные характеристики фильтров. Иначе нарушатся геометрические соотношения и относительное расположение коэффициентов (пикселов).
Таким образом, неразделимое преобразование нарушает принцип подобия вейвлет-разложения. То есть подобие высокочастотных подполос при неразделимой фильтрации сохраняется, но процесс построения деревьев с переходом через раз от прямоугольных к ромбическим формам изображения неоправданно сложен и трудоемок – нельзя использовать уже наработанные методы, такие структуры сложнее хранить в памяти, визуализировать, существенно затруднен их анализ. Это затрудняет практическое применение данного класса фильтров, несмотря на компактность структуры.
Авторами предложено простое и эффективное решение этой проблемы [18]. Ведь можно искажать и сам сигнал,
и импульсную характеристику фильтра так, чтобы сохранить все геометрические соотношения. При этом сдвиг отсчетов будет только визуальным (рис.7)– "растянутое" по вертикали изображение из-за его схлопывания (см.рис.6б),
но с точки зрения фильтрации все остается на своих местах [18]. Сохраняется подобие полос вейвлет-коэффициентов для различных уровней декомпозиции, при этом возможно ненулевое расширение сигнала при фильтрации.
Результаты моделирования
Авторами создана система кодирования ММ-сигналов (двумерных изображений, видеосигналов, результатов компьютерной томографии) на основе разработанных ММ БФ,
а также специальных иерархических алгоритмов и методов вложенного кодирования. На первом этапе (рис.8) цветные изображения преобразуются из системы RGB в YIQ (или другую). Затем каждая из составляющих проходит дискретное вейвлет-преобразование, квантование и кодирование. Работа кодеров существенно зависит от используемых БФ (рис.9). Синтезированные нами неразделимые фильтры (биортогональный bern3.3 и ортогональный K5.3) в основном дают лучшие результаты сжатия, чем разделимые (биортогональный bior3.3) с той же степенью гладкости. Тесты говорят о большей приспособленности иерархического алгоритма к изображениям с малым числом контуров и резких переходов, которые хорошо аппроксимируются вейвлетами. Результаты кодирования изображений с помощью разработанного алгоритма (используя разделимые фильтры и аналитически синтезированный ортогональный фильтр) лучше результатов применения JPEG-2000 по пиковому соотношению сигнал / шум на 1–1,5 дБ в зависимости от коэффициента сжатия и обрабатываемого изображения (рис.10).
Аппаратная реализация алгоритма сжатия изображений
Процесс разработки неразделимого метода сжатия сопровождался его программной реализацией. Приложение позволяет кодировать изображения в формате BMP – как цветные, так и в градации серого. Степень сжатия задается произвольно, также можно задавать точный размер выходного файла в байтах, что является несомненным преимуществом кодера. Выходной файл в оригинальном формате SPT можно декодировать в формат BMP.
Для реализации сложных алгоритмов необходима адекватная вычислительная платформа. Поскольку задачи обработки ММ-сигналов широко распространены, вычислительные платформы должны быть массовыми и относительно недорогими. В качестве таких платформ можно рассматривать процессоры современных видеокарт для персональных компьютеров – "графические" процессоры (GPU). Сама идея применения графического процессора в качестве базы для параллельных вычислений не нова. В современной информатике образовалось новое направление – вычисления общего назначения на GPU (GPGPU – General-Purpose computations on GPUs, см. www.gpgpu.org).
Благодаря мировой многомиллиардной индустрии компьютерных игр высокопроизводительные видеокарты развиваются чрезвычайно интенсивно. Фактически они представляют собой процессор параллельной обработки. По вычислительной мощности видеокарты намного опережают процессоры общего назначения, их производительность растет быстрее, чем предполагается законом Мура. Причем в отличие от специального оборудования (спецвычислителей, видеоускорителей и т.п.) на основе сигнальных процессоров, ПЛИС и др., видеокарты – это массовый продукт, а потому относительно дешевый. Например, одну из наиболее мощных видеокарт GeForce 7950 GX2 можно купить за 560 долл., чуть менее производительную GeForce 7900 GT – за 300 долл. Более простые видеокарты, например GeForce 6200, стоят 60 долл.
Самая мощная на момент написания статьи игровая видеокарта Nvidia GeForce 7950 GX2 имеет 16 вершинных и 48 пиксельных конвейеров и способна одновременно обрабатывать 48 пикселов. Входными массивами для видеокарты служат текстуры, т.е. двух- или трехмерные изображения с 32-разрядными отсчетами с плавающей точкой. Современные видеокарты обеспечивают программный доступ как минимум к 12 различным массивам (текстурам). Выходными массивами данных также являются текстуры. Одновременно можно выводить от четырех и более таких массивов.
Используя возможности современных видеокарт, мы реализовали как неразделимые, так и разделимые алголритмы двумерной фильтрации. Для наглядности рассмотрим алгоритм двумерной разделимой вейвлет-обработки на GPU (рис.11). Один уровень ДВП на GPU выполняется в два прохода. Сначала исходная картинка фильтруется двумя 1-D фильтрами, децимируется по горизонтали и выводится в виде двух промежуточных текстур. Затем обе эти текстуры параллельно фильтруются и децимируются по вертикали,
в результате получается четыре массива – подполосы первого уровня ДВП. LL-подполосу можно вновь пропустить через ту же систему обработки и получить еще четыре подполосы второго уровня и т.д. Тем самым реализуется многоуровневое вейвлет-преобразование.
С помощью GPU можно совместить подполосы в пределах одной текстуры. Для этого достаточно последовательно нарисовать четыре прямоугольника с текстурой подполосы и вывести в виде новой текстуры. И, наоборот, чтобы разделить подполосы (для обратного преобразования), достаточно для вершин прямоугольника задать соответствующие текстурные координаты.
Описанный алгоритм 2-D обработки изображения был реализован (рис.12) на двух различных видеокартах (nVidia GeForce 7900 GТ и GeForce 6600 GТ) и на базе универсального центрального процессора Intel PentiumD 945 Dual Core 3,4 ГГц персонального компьютера с 2 Гбайт ОЗУ (667 MГц). Видеокарта nVidia GeForce 7900 GТ (производитель – XFX) содержала 1 Гбайт ОЗУ (550/1300 МГц). Операционная система – Windows XP SP2; DirectX 9.0c (август 2006). Тестовая программа написана с использованием Direct3D. Исходные изображения были в формате RGB (24 бит/пиксел), промежуточные текстуры – в формате A16B16G16R16F (64 бит/ пиксел). Время расчета одного уровня ДВП включает также время загрузки/выгрузки текстуры по шине.
С увеличением размера картинки производительность системы возрастает и достигает своего максимального значения. Это обусловлено тем, что резко уменьшается что доля "накладных расходов" (в виде времени на пересылку данных и др.).
Таким образом, нам удалось на практике реализовать многоскоростную систему неразделимой фильтрации для многомерных сигналов, включая процедуры синтеза фильтров. Предложенные алгоритмы реализуются на массовых и недорогих вычислительных платформах – видеокартах персональных компьютеров. Это доказывает, что современный уровень достижений в области цифровой обработки многомерных сигналов – теоретических, алгоритмических, програмно-аппаратных – позволяет создавать принципиально новые цифровые телекоммуникационные и мультимедийные системы, в том числе – системы трехмерного телевидения.
Работа выполнена при содействии совместного гранта РФФИ и японского общества JSPS №06-07-91751-ЯФ_а
Литература
1. Fehn C. Depth-Image-Based Rendering (DIBR), compression and transmission for a new approach on 3D-TV. – Proc. SPIE Stereoscopic Displays and Virtual Reality Systems XI. – San Jose, CA: 2004, p.93–104.
2. Liao H., Nomura K., Dohi T. Long visualization depth autostereoscopic display using light field rendering based integral videography. – Proc. Virtual Reality Conference, 2006, p.8–11.
3. H. Liao, I. Makoto, K. Takefumi et al. Scalable high-resolution integral videography autostereoscopic display with a seamless multiprojection system. – Applied Optics, 2005, Vol. 44, N.3, p.305–315.
4. Three Dimensional Images in the Air. – Advanced Industrial Science and Technology. – ww.aist.go.jp/aist_e/latest_research/2006/20060210/20060210.html.
5. C.Chang, X.Zhu, P.Ramanathan, B.Girod. Light field compression using disparity-compensated lifting and shape adaptation. – IEEE Trans. Image Proc., 2006, Apr., Vol. 15, N. 4, p.793–806.
6. Чобану М. К., Черников А. В. Современный метод сжатия изображений на базе вейвлет-преобразования и иерархического алгоритма кодирования. – Цифровая обработка сигналов, 2005, №3, с. 40–59.
7. H. Lensch, M. Magnor, H.-P.Seidel, G. Ziegler. Multi-Video Compression in Texture Space using 4D SPIHT. – Proc. MMSP'04б, Siena, Italy, 2004.
8. Croisier A., Esteban D., Galaud C. Perfect channel splitting by use of interpolation/deci-mation/tree decomposition techniques. – Intern. Confer. Inform. Sci. Syst. Greece: 1976, p.443-446.
9. Vaidyanathan P.P. Multirate Systems and Filter Banks. – Englewood Cliffs: Prentice Hall, 1993.
10. Добеши И. 10 лекций по вейвлетам. – Ижевск: НИЦ: Регулярная и хаотическая динамика, 2001.
11. S. Bonnet, F. Peyrin, F. Turjman, R. Prost. Tomographic reconstruction using nonseparable wavelets. – IEEE Trans. Image Proc., 2000, Aug., Vol. 9, N. 8, p.1445–1450.
12. S. Bonnet, F. Peyrin, F. Turjman, R. Prost. Nonseparable wavelet-based cone-beam reconstruction in 3-D rotational angiography. – IEEE Trans. Medical Imaging. 2003, Mar., Vol. 22, N. 3, p.360–367.
13. Meyer Y. Ondelettes et fonctions splines. – em. Equations aux Derivees Parielles edition, 1986.
14. Wang J.-W., Chen C.-H., Pan J.-S. Genetic feature selection for texture classification using 2-D non-separable wavelet bases. – IEICE Trans. Fundament, 1998, Aug., Vol. E81-A, N.8, p.1635–1644.
15. F. Mujica, J.-P.Leduc, R. Murenzi, M. Smith. A new motion parameter estimation algorithm based on the continuous wavelet transform. – IEEE Trans. Image Proc. 2000, May, Vol. 9, N. 5, p.873–888.
16. Чобану М. К., Максименко И. Е. Синтез двухканальных многомерных вейвлетов и их применение для сжатия изображений. – Вестник МЭИ, 2006, №2, с. 88–96.
17. Чобану М. К. Многомерные многоскоростные системы и многомерные вейвлет функции. Часть II. Синтез. – Вестник МЭИ, 2003, №3, с. 69–78.
18. Чобану М. К. Иерархический алгоритм кодирования для неразделимых решеток и банков фильтров. – Вычислительные технологии, 2007, №8.
19. Чобану М. К. Синтез многомерных банков фильтров с помощью методов компьютерной алгебры. – Известия вузов. Электроника, 2007, №2, с. 50–59.
20. Чобану М. К. Синтез ортогональных многомерных банков фильтров с помощью преобразования Кэли. – Электричество, 2007, №4, с. 57–60.
21. Чобану М. К. Синтез оптимизированных многомерных банков фильтров. – Научный Вестник МГТУ ГА/ Серия Радиофизика и радиотехника, 2007, №117.
22. Чобану М. К. Системы многоскоростной обработки многомерных сигналов. Часть II. Методы полиномиального синтеза. – Проблемы управления, 2007, №3, с. 46–53.
23. Чобану М. К. Аналитический синтез многомерных многоскоростных систем. – Успехи современной радиоэлектроники, 2007, №4, с. 61–80.
24. Lewis A., Knowles G. Image compression using the 2-d wavelet transform. – IEEE Trans. Image Proc., 1992, Vol. 2, p.244-250.
25. Shapiro J. M. Embedded image coding using zerotrees of wavelets coefficients. – IEEE Trans. Signal Proc., 1993, Dec., Vol. 41, p.3445–3462.
26. Said A., Pearlman W. A. A new fast and efficient image codec based on set partitioning in hierarchical trees. – IEEE Trans. Circ., Syst. for Video Technol., 1996, Vol. 6, p.243–250.
Отзывы читателей
