Архивы: по дате | по разделам | по авторам

Ключи и отмычки DSP

Архив

автор : Сергей Козлов 22.11.2000

[i37025]

А что такое реально? Как определить, что реально? Если ты говоришь про то, что можно потрогать, почувствовать, увидеть, тогда реальность - это всего лишь электрические сигналы, которые интерпретирует наш мозг.
Морфей (персонаж фильма «Матрица»)

Окружающую реальность мы воспринимаем с помощью «датчиков» разных типов (органов чувств), на выходе которых в конце концов оказываются электрические сигналы. Процессор, расположенный между ушей, худо-бедно справляется с приходящим к нему потоком сигналов. Но человеческое любопытство идет дальше, за пределы возможностей своих естественных датчиков и собственного процессора. Кроме того, развитие вычислительной техники уже давно привело к тому, что многие виды человеческой деятельности перекладываются на плечи машин. А раз компьютеры должны взаимодействовать с миром, то они должны получать из него информацию сами. Еще один важный аспект - взаимодействие человека и компьютера. Естественные для человека способы коммуникации требуют того же - обработки сигналов.

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

	Быстрое преобразование Фурье	Дискретное косинусное преобразование	Построение гистограммы
Время вычисления, с	0,049	0,205	0,003
Тактов на пиксел	94	391	5,3

Как правило, обработку сигналов и изображений разделяют. Под «сигналами» обычно подразумевают (одномерные) изменения величины во времени, а под «изображениями» - (двумерные) поля в пространстве. Тем не менее, методы их обработки близки и часто основаны на одних и тех же операциях и преобразованиях, хотя, конечно, каждое из направлений имеет свою специфику.

Благодаря ряду преимуществ основным способом обработки сигналов стал цифровой. Электрические сигналы от датчиков (обычно аналоговые, непрерывные во времени и по уровню, если мы не измеряем заряд электрона) подвергаются квантованию (приведению к дискретным значениям по уровню) и дискретизации (привязыванию к фиксированным моментам времени) и превращаются в поток цифр. Как правило, используется равномерная шкала, хотя бывает полезна и неравномерность (например логарифмическая). Сам по себе этот переход небезболезненный, но если верить Котельникову (или Найквисту, на выбор), при определенных условиях цифровой сигнал хорошо соответствует исходному аналоговому. И анализируя цифровой сигнал, мы можем многое сказать об исходном, аналоговом. Реализацию (запись) цифрового сигнала достаточно легко сохранить надолго и без искажений. Теперь осталось лишь его обработать.

Так сложилось, что хорошо разработанным (традиционным) приемом анализа и обработки сигналов (и аналоговых, и цифровых) стало разложение по базису синусов-косинусов - преобразование Фурье. В условиях линейности и стационарности это очень удобный инструмент как для обработки детерминированных, так и стохастических сигналов. Но если линза выполняет преобразование Фурье мгновенно, то выполнение преобразования Фурье для цифрового сигнала на классическом последовательном процессоре требует времени. Кули и Тьюки, разработав в свое время алгоритм быстрого преобразования Фурье (БПФ) и приведя вычислительные затраты к соотношению O(Nlog₂N), сделали революцию в цифровой обработке сигналов. Но аппетиты растут, и умножать все равно надо много и быстро.

В свое время даже делали специализированные устройства для выполнения БПФ (я помню еще сделанные на россыпи, чуть ли не на 155-й серии). Потом появились специализированные одночиповые DSP-процессоры. Они приспособлены для быстрого выполнения примитивов цифровой обработки сигналов, часто используется конвейерная обработка. Характерная их особенность - специализированный набор команд, что в ряде случаев вызывает потребность в универсальном процессоре для взаимодействия с внешним миром. Бывает, что DSP-процессоры содержат встроенные АЦП и ЦАП. Специализированные устройства, как правило, имеют более высокое быстродействие, чем универсальные. Все это хорошо, но, как правило, дорого, требует специальных навыков и инструментов разработки для создания законченного изделия и оправданно лишь при массовом серийном производстве или для специальных применений.

С другой стороны, технология изготовления универсальных процессоров тоже не стоит на месте. Тактовая частота зашкаливает за гигагерц. Набор команд универсальных процессоров дополняется подмножествами команд, правильно, цифровой обработки сигна лов. Для процессоров Intel эти расширения называются MMX, Streaming SIMD Extensions, SSE2. Мультимедиа, Win-модемы, DVD- и MPEG-проигрыватели, распознавание речи и многие другие технологии широко используют эти расширения.

Конечно, уже написано множество программ для обработки сигналов и изображений. Но бывает, что возникают задачи, которые еще не решены, либо требуется встраивание средств обработки в программную систему, либо нужно создать специализированный инструмент (опять возвращаемся от универсального к специализированному, но на программном уровне). Что для этого требуется? Приобретать специализированный DSP-процессор плюс средства разработки для него? Не обязательно. Многие задачи можно успешно решать на уже имеющемся компьютере с процессором Intel inside.

Но тут возникает проблема: а как его запрограммировать для целей обработки сигналов?

В качестве одного из решений можно назвать FFTW (The Fastest Fourier Transform in the West) - разработку, выполненную Маттео Фриго (Matteo Frigo) и Стивеном Джонсоном из Массачусетского технологического института. Это переносимая (способная работать на множестве платформ) библиотека, написанная на C, свободная (GPL) и доступная (www.fftw.org [1]), позволяющая вычислять одно- и многомерные дискретные преобразования Фурье по алгоритму Кули-Тьюки. Изюминка FFTW заключается в очень хитрой технологии оптимизации вычисления БПФ в зависимости от особенностей процессора и длины реализации. На этапе компиляции библиотеки генерируются вычислительные примитивы (codelets) на С, учитывающие особенности процессора. Затем на этапе выполнения для заданного размера выборки планировщик (planer) соединяет эти примитивы оптимальным образом (генерируя байт-код алгоритма). А исполнительный блок (executor) этот план реализует, обращаясь к вычислительным примитивам. Получается, что программа сама приспосабливается к условиям и работает оптимально на любом процессоре без переписывания исходника. Авторы утверждают, что интерпретация байт-кода не слишком накладна («наши результаты противоречат обывательской теореме, что байт-код медленный»).

Вот так схематично выглядит программа на С, выполняющая БПФ с использованием FFTW:

fftw_plan plan;
int n = 1024;
COMPLEX A[n], B[n];
/* создание плана */
plan = fftw_create_plan(n);
/* исполнение плана */
fftw(plan, A);
/* повторное использование плана */
fftw(plan, B);

Тест FFTW на моем компьютере [2] вычисляет комплексное прямое преобразование на реализации длиной 1024 отсчета за 411-415 мкс (402-405 нс на точку), обратное преобразование - за 414-518 мкс (404-530 нс на точку) в зависимости от нюансов (например, вычисляя «по месту» или в отдельном массиве).

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

В этом отношении интересен пакет решений от Intel.

С сайта www.intel.com/vtune/perflibst можно скачать несколько библиотек из коллекции Intel Performance Library Suite (набор высокопроизводительных библиотек), предназначенной для цифровой обработки сигналов и изображений:

Signal Processing Library (библиотека для обработки сигналов);
Image Processing Library (библиотека для обработки изображений);
JPEG Library (библиотека для работы с изображениями в формате JPEG);
Recognition Primitives Library (библиотека примитивов распознавания образов);
Math Kernel Library (базовая математическая библиотека);
Integrated Performance Primitives (интегрированная библиотека примитивов обработки сигналов).

Подборка довольно массивна (дистрибутивы весят в сумме более 85 Мбайт), но и много в себя включает. Библиотеки включают наборы типовых функций обработки сигналов и изображений, во многом аналогичные тем, которые используются в DSP-процессорах. Функции оптимизированы для процессоров Intel (Pentium III, Pentium II, Pentium Pro, Pentium MMX), то есть широко используют расширенные наборы команд этих процессоров, что делает их впечатляюще быстродействующими.

Библиотеки (как правило, динамические [DLL] и статические [lib]) предназначены для операционных систем Microsoft (Windows 95, 98, 2000, Windows NT 3.51 и 4.0). Для каждого типа процессора, как правило, имеется свой набор библиотек (хотя есть возможность объединить в одном файле наборы для нескольких типов процессоров либо для компактности использовать только подмножество библиотек). Библиотеки рассчитаны на разработку приложений с помощью C/C++ компиляторов Intel, Borland (С++ v.5.0) и Microsoft (Visual C++ v6.0). Но для некоторых из этих библиотек есть интерфейсы для разработки с помощью Microsoft Visual Basic, Borland Delphi, Microsoft Visual J++ и Digital Visual FORTRAN. Помимо собственно библиотек (исходников, конечно же, нет), в дистрибутивы входит масса документации по библиотекам в форматах PDF и HTML, а также примеры приложений с исходниками (скриншоты которых послужили иллюстрациями).

Приятная особенность библиотек - они бесплатны (royalty-free), а DLL (Redistributable Code) можно включать в дистрибутивы разработанных на их основе продуктов [3].

Библиотека обработки сигналов (SPL) содержит функции для реализации фильтров с конечным (FIR), бесконечным (IIR) импульсным откликом, фильтров со скользящим средним (LMS - метод наименьших квадратов), быстрые преобразования Фурье (FFT - Fast Fourier Transforms), дискретные косинусные преобразования (DCT - Discrete Cosine Transforms), вэйвлетные преобразования (wavelet transforms), генераторы сигналов (tone generation), а также реализации многих арифметических и векторных операций.

Для иллюстрации возможностей библиотеки приведу примеры работы генератора сигнала (равномерное распределение), дискретное косинусное преобразование, быстрое преобразование Фурье с окном Хемминга (рис. 1).

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

Для сравнения с FFTW: тест показал, что вычисление комплексного БПФ для длины реализации 1024 отсчета занимает 155 мкс для одинарной точности и 190 мкс для двойной точности. Все-таки низкоуровневая оптимизация с использованием расширенного набора команд процессора дает о себе знать. (Следует заметить, что цифры получены для набора MMX. Я думаю, что на более новых процессорах с SSE и большей тактовой частотой цифры были бы существенно меньше.)

Библиотека обработки изображений (IPL) обеспечивает фильтрацию, пороговую обработку (thresholding), различные преобразования (FFT, DCT, геометрические), а также арифметические операции (сложение, вычитание) и морфинг. Используется гибкий формат изображений, поддерживающий различную глубину цвета (с каналами цветности в 1, 8, 16, 32 бит в целых числах, а также 32-битные с плавающей точкой, причем число каналов может быть произвольным). Поддерживается преобразование в формат Windows DIB (Device Independent Bitmap) и обратно, преобразование из цветного изображение в серое и обратно. Кроме того, возможно маскирование изображения и преобразование в различные цветовые пространства. Кстати, преобразование серого изображения в цветное не оговорка. Это очень полезный прием, который используется, например, при анализе снимков в ИК-диапазоне (для поиска утечек тепла и т. п.), в томографии и др.

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

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

Время выполнения некоторых операций над изображением размером 256x256 с 24-битным цветом приведено в таблице.

JPEG-библиотека (IJL) обеспечивает быстрое кодирование и декодирование для цветных и серых JPEG-изображений. Еще одна интересная возможность - вэйвлет-компрессия изображений (рис. 5). [4]

Библиотека примитивов распознавания образов (RPL) содержит набор примитивов для распознавания речи и символов (например рукописных).

Базовая математическая библиотека (MKL) включает функции линейной алгебры и БПФ в виде статической библиотеки. Пока доступна только бета-версия.

Накопленный при разработке этих библиотек опыт привел к созданию библиотеки нового поколения - Integrated Performance Primitives, где собраны низкоуровневые примитивы обработки сигналов и изображений: манипуляции с векторами и изображениями, преобразования и фильтрация, маскирование (windowing), пороговая обработка (thresholding), трансформации, арифметические операции и морфинг. В каком-то смысле это упорядочение, обобщение, интеграция SPL и IPL на новой основе. Пока доступна лишь первая бета-версия.

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

Да, мне кажется, будет полезно привести ссылку на www.dspguide.com, откуда можно скачать в формате PDF книгу Стивена Смита «Справочник инженера и ученого по цифровой обработке сигналов» («The Scientist and Engineer‘s Guide to Digital Signal Processing» by Steven W. Smith).

Теперь вы вооружены и очень опасны.

1 (обратно к тексту) - Не нравится или по каким-то причинам не подходит FFTW? На страничке www.fftw.org/benchfft/doc/ffts.html можно сравнить около сорока (на все случаи жизни) пакетов для вычисления FFT, заметная часть которых доступна в исходниках. - Г.Б.
2 (обратно к тексту) - Windows 98, Celeron 300A на экзотической частоте 375 МГц.
3 (обратно к тексту) - «При условии, что продукт добавляет существенную и оригинальную функциональность», как написано в лицензии.
4 (обратно к тексту) - О вэйвлетах и их приложениях можно прочитать в теме номера «Всплеск» («КТ» #236).