Вейвлеты на программируемом кремнии
АрхивНе так давно компьютеры и изображения жили самостоятельной жизнью. Фотографии были бумажными, видеозаписи хранились на ленте, а телепрограммы передавались в аналоговом виде. Компьютерам просто не хватало скорости, чтобы управляться с большими объемами информации, заключенными в изображениях.
Похоже, эти времена безвозвратно уходят в прошлое. Цифровые фотокамеры позволяют всем желающим обрабатывать свои снимки на домашнем компьютере, видеофильмы передаются по Паутине, и телевидение в скором времени тоже станет цифровым. И все же объем данных, необходимый для передачи изображений высокого разрешения, пока еще велик непомерно - если изображения предварительно не сжаты.
Между тем, наиболее распространенные методы сжатия (JPEG для неподвижных изображений и MPEG для видео и ТВЧ) были разработаны в 80-е годы, еще до широкого распространения вейвлетов. С тех пор уже не раз демонстрировалось превосходство (в задаче сжатия) вейвлет-преобразования над дискретным косинус-преобразованием, на котором основаны и JPEG, и MPEG.
Процесс сжатия
Для работы с дискретными изображениями используется вариант вейвлет-преобразования, известный как алгоритм Малла, названный в честь его изобретателя Стефана Малла (Stephane Mallat). Исходное изображение раскладывается на две составляющие - детали (состоящие в основном из резких перепадов яркости), и сглаженную уменьшенную версию оригинала. Это достигается применением пары фильтров, причем каждая из полученных составляющих вдвое меньше исходного изображения. Как правило, используются фильтры с конечным импульсным откликом, в которых пикселы, попавшие в небольшое "окно", умножаются на заданный набор коэффициентов, полученные значения суммируются, и окно сдвигается для расчета следующего значения на выходе. Между вейвлетами и фильтрами есть тесная связь. Вейвлеты непосредственно не фигурируют в алгоритмах, но если итерировать соответствующие фильтры на изображениях, состоящих из единственной яркой точки, то на выходе будут все отчетливей проступать вейвлеты.
Поскольку изображения двумерны, фильтрация производится и по вертикали, и по горизонтали. Этот процесс повторяется многократно, причем каждый раз в качестве входа используется сглаженная версия с предыдущего шага. Так как изображения "деталей" состоят обычно из набора резких границ и не содержат обширных участков с плавно меняющейся интенсивностью, большая часть значений пикселов в промежутках между границами близка к нулю. Если допустимо пренебречь некоторым количеством мелких деталей, то все эти значения можно просто обнулить. В результате получается версия исходного изображения, хорошо поддающаяся сжатию. Для восстановления оригинала снова применяется алгоритм Малла, но с парой фильтров, обратной к исходным.
|
Для работы с различными классами изображений могут использоваться различные фильтры. Возможно, поэтому все еще не существует единого стандарта для вейвлетного сжатия. Однако для конкретных приложений такие стандарты существуют; в частности, ФБР ввело стандарт на вейвлетное сжатие изображений отпечатков пальцев (см. обзор и сравнение с JPEG в документе www.c3.lanl.gov/~brislawn/FBI/FBI.html). Впрочем, свобода выбора фильтров может оказаться очень полезной в задаче сжатия: алгоритмы, основанные на принципе "наилучшего базиса", подбирают оптимальный фильтр для отдельных участков изображения, а алгоритмы, использующие вейвлет-пакеты, достигают эффективного представления деталей, варьируя глубину фильтрации на разных участках.
Еще одна проблема состоит в том, как эффективно использовать схожесть последовательных кадров при сжатии видео. В ранних алгоритмах, таких как Motion JPEG, этот фактор игнорировался, и кадры сжимались индивидуально. MPEG использует алгоритм сравнения блоков, который старается выделить участки, изменившиеся при смене кадра. Блоки же, которые не изменились, можно не сохранять. При третьем подходе, удобном для вейвлетного сжатия, время рассматривается как третье измерение массива данных, к которому применяется алгоритм Малла. Отсутствие перемещений проявляется в обнулении соответствующих деталей по временному направлению. Эксперименты показывают, что этот метод дает хорошие результаты, хотя и требует больших вычислений.
Наконец, надо заметить, что вейвлет-преобразование само по себе ничего не сжимает. Оно лишь осуществляет препроцессинг изображения, после которого эффективность обычных методов сжатия резко возрастает, причем даже при использовании универсальных алгоритмов и программ (таких, как LZW и pkzip), не адаптированных к конкретной задаче. Впрочем, использование методов кодирования, учитывающих структуру вейвлет-преобразования, может существенно повысить степень сжатия. Один из широко используемых методов такого типа - метод нуль-дерева (zero-tree compression). Он основан на предположении, что если некоторая область изображения не содержит нетривиальной информации на некотором уровне разрешения, то с большой вероятностью она не будет информативной и на более тонком уровне разрешения. Вейвлет-преобразование изображения можно хранить в виде дерева, корнем которого является сильно сглаженная версия оригинала, а ветви, представляющие отдельные блоки, обрываются на том уровне, где дальнейшая обработка не дает заметного уточнения. Такое дерево можно с успехом сжать обычными методами типа хаффменовского или арифметического кодирования, которые используются почти во всех алгоритмах сжатия.
Аппаратная реализация
Работа с громадными массивами данных, возникающими при сжатии видеопоследовательностей в реальном времени до недавних пор выходила за пределы возможностей обычных универсальных процессоров. Сейчас появились программные MPEG-декодеры, но они работают с ограниченным разрешением и невысокой частотой смены кадров. Программные же MPEG-кодеры не способны пока работать в реальном времени. Несмотря на поразительный рост тактовой частоты процессоров, ситуация не улучшается. Ведь в универсальной системе данные передаются из относительно медленной памяти по относительно медленной шине в процессор - единственное место, где производятся вычисления. Поэтому рост быстродействия процессора не приводит к пропорциональному росту быстродействия компьютера. Применение кэш-памяти может несколько снизить остроту этой проблемы, известной как "бутылка фон-Неймана", но полностью избавиться от нее невозможно. Чисто аппаратные решения, однако, не страдают этим недостатком, присущим классической архитектуре, так как вычисления в них могут (теоретически) производиться в любом количестве точек, соединенных между собой любым образом. На практике, разумеется, возникают некоторые ограничения на степень параллелизма, связанные с предельными размерами устройств.
Реализация трехмерного вейвлет-сжатия телевизионных изображений применяемого сейчас разрешения, с использованием 12-коэффициентных фильтров и глубины в 4 кадра по времени, требует более 7,1 миллиарда умножений в секунду. Единственный способ выполнить это требование - делать как можно больше операций в параллельном режиме. Недавно появившиеся мультимедийные команды (MMX) позволяют параллельно выполнять до 8 умножений, но только на 8-битных данных. Для работы в реальном времени такого уровня параллелизма недостаточно - отсюда решение (если не обращаться к большим и дорогим многопроцессорным системам): реализовать нужное преобразование в специализированной БИС.
В настоящее время на рынке имеются БИС, реализующие основные этапы JPEG- и MPEG-алгоритмов. Сектор рынка для этих устройств достаточно велик, так как соответствующие алгоритмы являются стандартными, и это позволяет окупить затраты на разработку и производство специализированных чипов. Существует устройство такого типа, реализующее вейвлетное сжатие цветных изображений ТВ-качества. Оно было разработано фирмой Aware, но выпускается компанией Analog Devices (www.analog.com). Это устройство использует одну определенную биортогональную пару фильтров, и обрабатывает кадры по очереди. Для кодирования используется метод Хаффмена и кодирование длин серий. Использовать другие фильтры или другие методы кодирования в данном устройстве нельзя.
FPGA (Field Programmable Gate Array)
До недавнего времени разработка нового чипа для вычислительных задач была по силам только крупным компаниям, таким как Analog Devices, имеющим большой штат разработчиков и доступ к дорогим производственным мощностям. Поэтому выпуск таких устройств был оправдан только в случаях, когда объем предполагаемых продаж оценивался миллионами штук.
Изобретение FPGA, основанных на ОЗУ-технологии, изменило ситуацию. Такие устройства продаются "чистыми", и в них, как в обычные чипы памяти, можно записывать двоичные данные, которые определяют логические функции, реализуемые FPGA. В зависимости от типа FPGA, это могут быть вентили для базовых операций И, ИЛИ, НЕ - для "мелкозернистых" (fine-grained) FPGA, производимых, например, фирмой Motorola (www.mot-sps.com/fpga), или более сложные функции, например, регистры и сумматоры - для "крупнозернистых" (coarse-grained) FPGA, например, фирмы Xilinx (www.xilinx.com). Эти устройства являются физическим воплощением концепции однородной вычислительной среды, выдвинутой еще в начале 60-х годов такими учеными, как Е. В. Евреинов (см. www.ssd.sscc.ru/fet/pcr.html).
В случае FPGA реализация той или иной вычислительной функции не входит в стоимость производства - эта функция просто загружается из программируемого ПЗУ или при помощи процессора в момент включения устройства. Это открывает возможность создания устройств, перепрограммируемых на выполнение различных функций в процессе эксплуатации (почти так же, как загрузка программы в память обычного компьютера реализует на некоторое время определенную функцию при помощи процессора).
FPGA и ускорение программ
В силу тьюринг-эквивалентности универсальных процессоров и FPGA (в том смысле, что все вычислимое на обычном процессоре вычислимо и на FPGA), системы на основе FPGA могут быть вполне замкнутыми. На практике бывает более удобно использовать FPGA в сочетании с обычным компьютером, осуществляющим операции ввода-вывода. Такие системы реализованы. Самый известный пример - система PAM, первоначально разрабатывавшаяся по заказу Digital в Париже (http://pam.devinci.fr). На многих задачах (таких как криптография, анализ ДНК, трехмерный JPEG) она показала производительность выше, чем самые быстрые суперкомпьютеры в мире. Типичная скорость работы составляет порядка миллиарда операций в секунду, что соответствует требованиям к реализации трехмерного вейвлет-преобразования в реальном времени.
Большинство производителей FPGA работает на более скромном уровне, выпуская карты, присоединяемые к обычной шине компьютера для реализации определенных функций (нечто вроде традиционного математического сопроцессора, но с преимуществом в виде полной универсальности). В основном такие карты являются скорее экспериментальными, чем коммерческими продуктами.
Главным препятствием на пути широкого применения таких карт являются большие затраты времени на реализацию требуемой функции в FPGA. Эта проблема еще не полностью решена. В принципе, такая реализация не должна быть сложнее, чем написание новой программы для компьютера, но на деле это пока не так. На сегодня существуют три основных подхода к этой проблеме. Первый состоит в применении языков HDL (Hardware Definition Languages), таких как VHDL или Verilog, где разработчик подходит к созданию конфигурации как к задаче программирования, а компилятор обеспечивает все детали конкретного воплощения (аналогично тому, как обычный компилятор генерирует машинные коды). Второй подход заключается в расширении обычного языка программирования, например Си, до HDL. Третий подход использует библиотеки заранее созданных функций, соединяемых затем в новую конфигурацию (по аналогии с принципом многократного использования объектов в объектно-ориентированном программировании).
К сожалению, в настоящее время эти подходы не обеспечивают должной эффективности, и разработчику приходится вручную вносить множество изменений, чтобы заставить конфигурацию работать. Здесь есть нечто общее с обыкновенным программированием, где в течение многих лет компиляторы не были способны генерировать оптимальный (особенно по времени выполнения) код. Поскольку последняя задача уже решена (по крайней мере, для универсальных процессоров), есть надежда, что и проблема программирования функций для FPGA тоже будет решена. Сейчас это обширная область исследований, получающая мощное финансирование от правительства США (список проектов можно посмотреть в www.ito.darpa.html/ResearchAreas/ACS.html).
Особенности аппаратной реализации вейвлетного сжатия
Главное преимущество FPGA перед специализированными СБИС заключается в гибкости конфигурации. В случае вейвлет-преобразования это означает, что в систему можно, например, ввести любые желаемые фильтры, просто загрузив новую версию в FPGA. Таким же образом можно переходить на более совершенные алгоритмы сжатия, не приобретая нового оборудования, как было бы при использовании СБИС. Таким образом, нет необходимости в огромном рынке для того, чтобы окупить разработку таких решений - ведь одно и то же оборудование используется для реализации различных конфигураций. Когда-нибудь, наверное, пользователи смогут просто загружать с вебсайта новую конфигурацию так же, как сейчас загружается какая-нибудь программа на Java. Правда, для этого сами FPGA должны стать более стандартизованными, чем сегодня.
В будущем будет применяться и такое свойство FPGA, как установка новых конфигураций в процессе исполнения, чтобы использовать, например, лучший базис или алгоритм вейвлет-пакетного сжатия. Такое возможно и сейчас, но загрузка новой конфигурации занимает десятки миллисекунд. Однако производители работают над снижением времени реконфигурации, и когда оно станет мало по сравнению с общим временем выполнения программы, алгоритмы такого типа начнут входить в практику.
|
С другой стороны, главное преимущество FPGA над чисто программными решениями состоит в производительности. Сейчас не существует процессоров, способных выполнять миллиарды операций в секунду, что требуется для сжатия видео в реальном времени. Однако разработка систем, достигающих такой производительности, требует совсем других идей, чем создание быстрых алгоритмов.
Создавая быстро работающую программу, программист пытается минимизировать количество последовательных шагов алгоритма, тем самым минимизируя общее число операций. Для создания быстро работающих конфигураций FPGA разработчик старается максимизировать количество операций, выполняемых одновременно, - даже если при этом общее число операций возрастет.
Этого можно добиться двумя основными способами - либо выполнением на каждом шаге как можно большего числа операций параллельно, либо максимальной конвейеризацией, когда поток данных непрерывно движется от начальной к конечной стадии обработки. Например, алгоритм Малла может быть применен к видеоданным либо при помощи трехмерных фильтров (что требует 2L3 умножений на пиксел), либо последовательным применением одномерных фильтров по каждому измерению (что требует _ умножений на пиксел, где L количество коэффициентов фильтра). При втором подходе задержка перед появлением первого результата на выходе будет больше (латентность системы будет выше), но дальнейшие результаты будут появляться с тактовой частотой. В обоих случаях все требуемые умножения выполняются одновременно, и вопрос об эффективности сводится к тому, что более экономно по используемой площади FPGA: иметь больше умножителей, или иметь меньше умножителей, но больше буферов и каналов пересылки данных?
В то время как главным ограничением на применимость программных решений является количество последовательных операций, ограничением для FPGA-решений является используемая площадь кристалла. FPGA, подобно ОЗУ, развиваются по закону Мура: начиная с семидесятых годов размер ОЗУ увеличивался в четыре раза каждые четыре года, и эта тенденция, по-видимому, сохраняется. Этот экспоненциальный рост объема означает, что в долгосрочной перспективе площадь перестанет быть проблемой. Однако сейчас FPGA-конфигурации стараются сделать как можно меньше. В частности, это исключает в обозримом будущем использование плавающей арифметики. Умножители плавающих чисел очень велики, и на один кристалл их помещается мало.
Проблема с плавающими числами возникает при реализации алгоритма Малла, так как на каждом его шаге они растут: перемножение двух n-битовых чисел дает в общем случае 2n-битовый результат. Например, если на вход поступает 8 бит на пиксел, то после всего лишь четырех шагов трехмерного алгоритма Малла на выходе будут 1024-битовые числа. Такая конструкция хотя и возможна (на FPGA можно, в принципе, создать конфигурацию для работы с числами любой длины), но была бы весьма неэффективной.
Такого рода трудности можно преодолеть, например, с помощью грубой силы, отбрасывая на каждом шаге лишние биты и теряя тем самым дробную часть. Установлено, что эти потери несущественны, если речь идет о зрительном восприятии человека - человек не способен заметить улучшения качества изображения, которое начинается примерно после 12 бит. Однако даже если никаких других погрешностей в результат преобразования не вносится, восстановленное изображение уже не будет тождественно исходному.
Более интересным представляется решение на основе недавно разработанной техники, позволяющей выполнять обратимые преобразования типа вейвлетного безо всякой потери точности. Эта техника была создана независимо несколькими исследователями и называется то ступенчатой фильтрацией (ladder filtering), то лифтингом (lifting transform). Хорошее введение в этот предмет можно найти в http://cm.bell-labs.com/cm/ms/who/wim. Суть метода заключается в делении массива данных пополам (на четные и нечетные компоненты), вычитании сглаженной версии массива нечетных компонентов из массива четных (при этом получается массив деталей), и последующем вычитании сглаженной версии массива деталей из массива нечетных компонентов (при этом получается сглаженная версия сигнала). На первый взгляд эта процедура сильно отличается от того, что происходит при работе обычного алгоритма Малла. Но на самом деле любая пара вейвлетных фильтров может быть разложена в композицию промежуточных фильтров такого типа. Достоинство этой процедуры в том, что изменения в оба компонента сигнала вносятся только за счет сложения или вычитания; результаты умножений, производимых при промежуточной фильтрации, могут быть усечены сколь угодно грубо при условии, что такое же усечение делается на этапе восстановления.
Разумеется, при очень сильном усечении результатов умножения мы не получим на выходе настоящего вейвлет-преобразования. Однако результат достаточно близок к вейвлет-преобразованию, чтобы вызывать некоторый ажиотаж среди тех, кто занимается обратимым сжатием (обратимое сжатие всегда менее эффективно, чем необратимое, но в некоторых областях, например, в медицине, где искажения оригинала недопустимы, без него не обойтись).
Далее, нужно найти способ реализации большого параллельного массива целочисленных умножителей. Стандартный целочисленный умножитель требует одного сумматора на бит множителя. В данном случае множители известны заранее, и вместо универсального умножителя можно построить специализированный именно на эти множители. Стандартный вариант: использовать по сумматору на каждую единицу в двоичном представлении числа. Например, 45=101101, и умножение x на 45 эквивалентно сложению x+4x+8x+32x, что требует трех сумматоров и возможности умножать на степени двойки (это легко реализуется сдвигами). Несколько большей эффективности можно добиться, факторизуя множитель: 45x=5(9x), где 5=101, 9=1001, умножение имеет вид (x+4x)+8(x+4x), что требует только двух сложений. Еще повысить эффективность можно, повторно используя результаты умножения на общие множители различных коэффициентов фильтра.
За счет всех этих ухищрений на не очень большой FPGA легко разместить стокоэффициентный фильтр, и главной проблемой становится не число сумматоров, а обмен данными между сумматорами. Производительность сразу возрастает до ста умножений за такт, против тысячи или более тактов, требуемых на такое количество умножений на типичном процессоре. Если постараться, можно добиться подобного роста производительности на большинстве стадий вейвлетного сжатия.
В настоящее время оптимизация такого типа обычно делается вручную. Нет причин, по которым ее нельзя было бы встроить в компиляторы подобно тому, как современные компиляторы производят сложную оптимизацию использования регистров в универсальных процессорах.
FPGA и будущее
Появление FPGA на рынке сопровождалось большим оптимизмом по поводу их использования в обычных вычислительных системах для ускорения практически любых вычислений. В настоящее время отношение к ним стало более взвешенным и реалистичным. Первые FPGA разрабатывались в основном как замена традиционных СБИС, которые обычно используются в качестве альтернативы обычным процессорам, а не в сочетании с ними. Поэтому конструкции первых FPGA не были ориентированы на максимальное ускорение доступа главного процессора к внутренним данным, сокращение времени реконфигурации или быстрый доступ к внешней памяти. В результате, хотя эти FPGA и производили вычисления быстрее, выигрыш сводился на нет потерями при взаимодействии с другими частями системы и был заметен только при очень большом объеме вычислений.
К счастью, сжатие изображений - именно такой случай, когда смешанные системы типа FPGA + процессор имеют огромное преимущество перед обычными. А слабости первых FPGA стимулировали значительные исследования по созданию оптимальной для таких систем структуры FPGA. Большая часть новых типов FPGA, обладающих быстрым доступом к внутренним регистрам, внутренним ОЗУ и малым временем реконфигурации, пока существует только в лаборатории, но в течение нескольких предстоящих лет наиболее удачные конструкции поступят в массовое производство.
Когда это произойдет, FPGA-карта будет, возможно, одним из обычных компонентов массового компьютера. Но уже сейчас FPGA обеспечивают достаточные гибкость и быстродействие для реализации широкого спектра вейвлетных алгоритмов сжатия.
Литература
- Общее введение в вычисления на FPGA:
Configurable Computing, J.Villasenor and W.Mangione-Smith, Scientific American, June 1997.
- Более специальный (и несколько менее оптимистичный) обзор текущего состояния дел:
Seeking Solutions in Configurable Computing, W.Mangione-Smith, B.Hutchings et al., IEEE Computer Vol. 30 No. 12, Dec. 1997.
- История и нынешнее состояние вычислений на реконфигурируемых устройствах в СССР и России:
Ya. I. Fet (Я. И. Фет), Parallel Processing in Cellular Arrays, Research Studies Press: Taunton UK, 1995.
- Работы по вейвлетному сжатию изображений и видео рассеяны по сотням журнальных статей, многие из которых доступны в сети. Хороший источник информации - "Wavelet Digest":
www.wavelet.org/wavelet/. - Сборник указателей на статьи для новичков в вейвлет-анализе:
www-ocean.tamu.edu/~baum/wavelets.html. - Хорошая (и сравнительно несложная) книга, содержащая много информации о вейвлетном сжатии изображений, включая сравнение с дискретным косинус-преобразованием:
G.Strang and T.Nguyen, Wavelets and Filter Banks, Wellesly-Cambridge Press, 1996. Подробнее о ней:
www-math.mit.edu/~gs/books/wfb.html.
