Цифровая обработка сигналов
Содержание
Введение
Глава 1. Характеристика сигналов в системах цифровой обработки
Глава 2. Специализированный процессор цифровой обработки сигналов СПФ СМ
2.1 Области применения
2.2 Структура и основные характеристики
2.3 Алгоритмы и программное обеспечение
2.4 Разработчики и промышленная история
Глава 3. Применение цифровой обработки сигналов
3.1 Шумоподавление для звука
3.2 Передискретизация
3.3 Антиалиасинг изображений
3.4 Псевдотонирование изображений
3.5 Выравнивание освещенности изображений
3.6 Другие применения
Заключение
Список литературы
Введение
Цифровой обработкой сигналов принято называть в вычислительной технике арифметическую обработку последовательностей равноотстоящих во времени отсчетов. Под цифровой обработкой понимают также обработку одномерных и многомерных массивов данных.
Безусловно, данная обработка может быть выполнена с помощью обычных вычислительных средств. Например, на современном персональном компьютере с процессором типа Pentium IV обработка не представляет никаких трудностей. Однако именно специфика последовательности предоставляет дополнительные возможности для достижения высокой эффективности при жестких ограничениях систем реального времени.
Не секрет, что первые вычислительные машины были созданы в 40-х годах прошлого столетия для решения задач криптографии, баллистики, ядерной физики, практического построения систем противовоздушной обороны. Системы и методы цифровой обработки также разрабатывались в оборонных отраслях в первую очередь для решения задач радиолокации, обработки гидроакустических и тепловизионных сигналов.
Для обнаружения и уничтожения летательных аппаратов служили комплексы, состоящие из радиолокаторов, управляющих вычислительных машин и ракетных установок. В области военного морского приборостроения системы цифровой обработки использовались, в частности, для анализа гидроакустических сигналов, определения шумовых паспортов кораблей на основе спектральных характеристик, вычисления корреляционных зависимостей паспорта и реального гидроакустического сигнала.
В статье представлены две разработки отечественных вычислительных систем цифровой обработки, выполненные инженерами и учеными в 70–80 годах прошлого века. Спецпроцессор преобразования Фурье СПФ СМ для семейства управляющих ЭВМ линии СМ3 – СМ4 был создан в 1983 году для обработки изображений поверхности планеты Венера в рамках выполнения соответствующей программы. Разработка проводилась Институтом электронных управляющих машин (ИНЭУМ) совместно с Институтом радиоэлектроники Академии наук СССР – ИРЕ АН.
Цифровые вычислительные системы «Напев» и «Айлама» предназначались для обработки гидроакустического сигнала и были предложены ЦНИИ «Агат» в 1978-1979 годах по техническому заданию Военно-морского флота (ВМФ) СССР.
Вышеприведенные разработки в силу исторических причин не послужили непосредственной основой создания аппаратной части современных микропроцессоров цифровой обработки сигналов, однако приобретенный опыт проектирования программных и аппаратных компонентов позволяет коллективам-разработчикам поддерживать мировой уровень в своих дальнейших исследованиях.
Современное гражданское применение методов цифровой обработки лежит в области мультимедийных технологий, то есть обработки звука и изображений, включающей их сжатие, кодировку. В области цифровой связи цифровыми методами выполняется модуляция и демодуляция данных для передачи по каналам связи. Сегодня многие пользователи, имеющие на своем рабочем столе персональный компьютер, даже и не подозревают о наличии вычислительных средств – микропроцессоров, построенных на принципах цифровой обработки сигналов, находящихся на расстоянии вытянутой руки.
Процессоры цифровой обработки сигналов, как добрые гномы или мифические демоны Максвелла, перерабатывают в «недрах» компьютера цифровую информационную руду: без устали фильтруют, анализируют, распознают, модулируют/демодулируют, уплотняют и разуплотняют, кодируют/декодируют – всего не перечислишь.
А беря в руку трубку сотового телефона, от Motorolla например, вы наверное и не знаете, что держите в руках специализированное вычислительное устройство, основу которого составляет процессор обработки цифровых сигналов.
Глава 1. Характеристика сигналов в системах цифровой обработки
Цифровая обработка, в отличие от аналоговой, традиционно используемой во многих радиотехнических устройствах, является более дешевым способом достижения результата, обеспечивает более высокую точность, миниатюрность и технологичность устройства, температурную стабильность.
Наиболее жесткие требования к аппаратной части цифровой обработки предъявляют радиолокационные системы. Основным содержанием цифровой обработки здесь является фильтрация входных сигналов антенны, частоты сигналов от 10 МГц до 10 ГГц. Размеры преобразований могут достигать до 214 комплексных точек, требования по быстродействию составляют 109 умножений в секунду.
При обработке цифровых сигналов радиолокатора используются алгоритмы цифровой фильтрации и спектрального анализа (вычисление дискретного и быстрого преобразования Фурье – ДПФ и БПФ), алгоритмы корреляционного анализа, обратной свертки, специальные алгоритмы линейного предсказания. В системах обработки звука цифровые процессоры обработки сигнала решают задачи анализа, распознавания и синтеза речи, сжатия речи в системах телекоммуникации. Для систем обработки изображений типовыми задачами являются улучшение изображений, сжатие информации для передачи и хранения, распознавание образов. При обработке цифровых звуковых сигналов используются алгоритмы цифровой фильтрации и спектрального анализа (вычисление ДПФ и БПФ), алгоритмы корреляционного анализа, обратной свертки, специальные алгоритмы линейного предсказания. В большинстве случаев удовлетворительные результаты обеспечивает формат данных с фиксированной запятой, длина слова 16 бит, частоты сигналов от 4 до 20 кГц (до 40 кГц в случае обработки музыки), требуемая производительность – до 10x106 операций в секунду – 10 MIPS по компьютерной терминологии.
Характерным для систем обработки изображений является восстановление и улучшение изображений с помощью инверсной свертки, обработка массивов отсчетов с помощью алгоритмов быстрого преобразования Фурье. При восстановлении трехмерной структуры объектов, получаемых методами проникающего излучения в дефектоскопии и медицинской интраскопии, применяются методы пространственно-частотной фильтрации. Другой класс алгоритмов – преобразование контрастности, выделение контуров, статистическая обработка изображений. Для сжатия информации наиболее эффективны ортогональные преобразования Фурье, Адамара и Уолша. Требуемая производительность оценивается величинами 100–1000 MIPS, массивы данных – 105–106 отсчетов.
Таблица 1 Характеристики сигналов в системах цифровой обработки
Назначение
Характеристика
Диапазон частот, размерность
Требуемое быстродействие
Пример, разработчик
Радиолокационные системы
Фильтрация сигналов антенны
10 МГц – 10 ГГц, до 214 точек
109 умножений в секунду
Обработка звуковых сигналов
Анализ и синтез речи, сжатие и распознавание
20 кГц (40 кГц), 16 бит
10 MIPS
«Напев», ЦНИИ «Агат»
Системы обработки изображений
Восстановление и улучшение изображений
105–106 отсчетов
100-1000 MIPS
СПФ СМ, ИНЕУМ, ИРЕ АН СССР --PAGE_BREAK--
Ниже приводятся описания двух отечественных систем цифровой обработки сигнала, которые, однако, предваряются небольшим экскурсом в математические и алгоритмические основы обработки последовательностей сигналов.
Глава 2. Специализированный процессор цифровой обработки сигналов СПФ СМ
Специализированный процессор Фурье – СПФ СМ – предназначен для выполнения алгоритмов быстрого преобразования Фурье и других специфических операций цифровой обработки сигналов. Процессор был разработан Институтом электронных управляющих машин (ИНЭУМ) совместно с Институтом радиоэлектроники АН СССР в 1983 году.
Специализированный процессор представлял собой высокопроизводительное аппаратное средство расширения возможностей управляющих компьютеров линии СМ ЭВМ.
2.1 Области применения
СПФ СМ в силу универсальности реализуемых алгоритмов применялся в различных областях науки и техники. При использовании спецпроцессора существенно ускорялось время решения, и были получены показатели производительности, недостижимые без данного устройства, сравнимые с соответствующими показателями супер-ЭВМ.
Краткий перечень областей эффективного применения СПФ СМ с указанием выполняемых алгоритмов приведен ниже.
Радио- и гидролокация – обнаружение и измерение координат, профилирование, построение радиоизображения, полоса сигнала 100 кГц – 1 МГц. Применяются следующие алгоритмы:
согласованная фильтрация, база сигнала 102–104;
спектральный анализ, разрешение 10-4;
двумерное ДПФ, двумерная фильтрация;
фазирование сигналов, ограничение выбросов в сигналах.
Радиосвязь – обеспечение надежности систем наземной и космической связи за счет оптимизации алгоритмов выделения, кодирования для сжатия и увеличения помехозащищенности, подавление помех, полоса сигнала до 100 кГц. Применяемые алгоритмы и операции: спектральный анализ, одномерное и двумерное дискретное преобразование Фурье, взаимная корреляция и согласованная фильтрация.
Радиоастрономия – спектры линий, радиоинтерферометрия со сверхбольшими базами для разрешения радиоисточников, полоса сигнала 1–10 МГц. Применяемые алгоритмы:
спектральный анализ, разрешение 10–4;
взаимная корреляция;
фильтрация.
Обработка изображений – улучшение качества снимков – резкости и контрастности, подавление помех, сжатие и восстановление после сжатия, восстановление изображений из оцифрованных голограмм, размер изображений 103x103. При обработке изображений применяется двумерное ДПФ и двумерная фильтрация.
Геофизика – анализ естественных сейсмосигналов для контроля и предсказания землетрясений, обработки результатов сейсморазведки для описания геологической структуры под поверхностью. Применяемые алгоритмы:
взаимная корреляция и автокорреляция;
фильтрация;
восстановление из свертки в частотной области;
двумерное ДПФ для восстановления распределения отражений из проекций, размер 103x103.
Обработка речевых и звуковых сигналов в полосе сигнала 50 кГц – анализ и синтез речи, улучшение качества звукозаписи, акустики помещений и систем.
Медицина, биология – анализ кардиограмм и энцефалограмм, томографические исследования, анализ звуков животных, полоса сигнала до 400 кГц.
Анализ вибраций для контроля качества двигателей и механических систем, полоса сигнала 100 кГц – 1 МГц.
Моделирование физических явлений и цифровых систем – проверка гипотез, подбор параметров при проектировании.
2.2 Структура и основные характеристики
Функциональные узлы спецпроцессора СПФ СМ построены по конвейерной схеме и соединены между собой в общий конвейер, «смещающийся» на одно слово при поступлении на вход очередного отсчета, благодаря чему пропускная способность достигает до 400 тыс. комплексных отсчетов в секунду.
Основной узел – блок выполнения ДПФ, алгоритм БПФ по основанию 2, аппаратурная задержка приблизительно равна размеру преобразуемого массива.
Обмен данными между оперативным запоминающим устройством и спецпроцессором обеспечивается блоком сопряжения прямого доступа. Скорость обмена – 400 тыс. 32-разрядных слов в секунду.
В структуру спецпроцессора введены два дополнительных умножителя. Первый из них предназначен для перемножения преобразуемого и взвешиваемого массива, второй – для нахождения мощности – то есть квадрата модуля.
Конструктивно СПФ СМ был выполнен в одной стойке СМ ЭВМ с габаритами 947x600x1800 мм. Потребляемая мощность – 2 кВт.
2.3 Алгоритмы и программное обеспечение
С помощью СПФ СМ выполняются следующие алгоритмы:
Прямое преобразование комплексного массива. Размер массива N = 2n (n = 1, 2, …, 12).
Прямое ДПФ с получением энергетического спектра с вышеуказанными параметрами.
Прямое ДПФ с предварительным взвешиванием преобразуемого массива. При выполнении предварительного взвешивания время увеличивается на 30%.
Обратное ДПФ.
Операции масштабирования массивов: а)увеличение отсчета массива в 2a раз и выявление числа переполнений, числа значащих битов максимального по абсолютной величине числа (мнимые и действительные части рассматриваются как независимые числа, при переполнении производится ограничение); б)управление делением в 2 раза после каждого этапа БПФ в блоке БПФ; в)уменьшение значений энергетического спектра в 4b раза.
Основное назначение операций a) и б) состоит в минимизации погрешности ДПФ, а операции в) – в уменьшении разрядности результата и экономии ОЗУ за счет укороченного формата мощности. Кроме того, операция а) позволяет ограничить массив сигнала и выявить статистику его амплитуды.
Дополнительные операции над массивами:
а) поэлементное перемножение двух комплексных массивов;
б) вычисление суммы произведений элементов двух комплексных массивов.
Размещение массивов в ОЗУ. Действительные и мнимые части данных располагаются последовательно. Шаг размещения массива произвольный, что позволяет исключать лишние пересылки при совместном анализе нескольких сигналов или при обработке двумерных массивов.
Управление спецпроцессором со стороны операционной системы СМ3 или СМ4 осуществляется программой-драйвером, выполняющей за одно обращение следующие команды:
прямое и обратное БПФ;
БПФ и вычисление энергетического спектра;
ОБПФ и вычисление массива из квадратов модулей значений результата;
умножение на массив весовых коэффициентов и БПФ;
умножение на массив весовых коэффициентов и ОБПФ;
умножение на массив весовых коэффициентов, БПФ и вычисление энергетического спектра; продолжение
--PAGE_BREAK--
умножение на массив весовых коэффициентов, ОБПФ и вычисление массива из квадратов модуля значений результата;
скалярное произведение двух массивов;
вычисление квадрата модуля скалярного произведения двух массивов;
вычисление массива квадратов модулей поэлементного произведения.
Наборы макрокоманд и модулей системной библиотеки позволяют спецпроцессору выполнять следующие операции ДПФ: свертку двух действительных массивов, двумерное ДПФ массива, расположенного на магнитном носителе, ДПФ массива большого размера, находящегося на магнитном носителе; взвешивание преобразуемого массива.
2.4 Разработчики и промышленная история
Разработка спецпроцессора СПФ СМ осуществлялась в Институте электронных управляющих машин, в отделе возглавлявшемся к. т. н. Фельманом Борисом Яковлевичем. Разработка выполнялась совместно с ИРЭ АН СССР. Спецпроцессор СПФ СМ выпускался малой серией. Общее количество выпущенных силами предприятий-разработчиков экземпляров – 30-40.
Интересным примером применения спецпроцессора СПФ СМ явилась обработка радиолокационных сигналов зондирования поверхности планеты Венера, которое проводилось со спутника.
Глава 3. Применение цифровой обработки сигналов.
3.1 Шумоподавление для звука
Звуковой сигнал, записываемый в реальных акустических условиях, часто содержит нежелательные шумы, которые могут порождаться окружающей средой или звукозаписывающей аппаратурой. Один из классов шумов — аддитивные стационарные шумы.
Аддитивность означает, что шум суммируется с «чистым» сигналом и не зависит от него.
Стационарность означает, что свойства шума (мощность, спектральный состав) не меняются во времени.
Примерами таких шумов могут являться постоянное шипение микрофона или усилительной аппаратуры, гул электросети. Работа различных приборов, не меняющих звучания по времени (вентиляторы, компьютеры) также может создавать шумы, близкие к стационарным. Не являются стационарными шумами различные щелчки, удары, шелест ветра, шум автомобилей.
Для подавления аддитивных стационарных шумов существует алгоритм спектрального вычитания. Он состоит из следующих стадий:
1. Разложение сигнала с помощью кратковременного преобразования Фурье (STFT) или другого преобразования, компактно локализующего энергию сигнала.
2. Оценка спектра шума.
3. «Вычитание» амплитудного спектра шума из амплитудного спектра сигнала.
4. Обратное преобразование STFT — синтез результирующего сигнала.
В качестве банка фильтров рекомендуется использовать STFT с окном Ханна длиной порядка 50 мс и степенью перекрытия 75%. Амплитуду весового окна надо отмасштабировать так, чтобы при выбранной степени перекрытия окон банк фильтров не менял общую амплитуду сигнала в отсутствие обработки.
Оценка спектра шума может осуществляться как автоматически, путем поиска участков минимальной энергии в каждой частотной полосе, так и вручную, путем анализа спектра на временном сегменте, который пользователь идентифицировал как шум.
Одна из проблем метода спектрального вычитания – т.н. «музыкальный шум». Он появляется вследствие того, что коэффициенты STFT шумовых сигналов статистически случайны, что приводит к их неравномерному подавлению. В результате, очищенный сигнал содержит кратковременные и ограниченные по частоте всплески энергии, которые на слух воспринимаются как «колокольчики» или «льющаяся вода». В некоторых случаях этот эффект даже менее желателен, чем исходный подавляемый шум.
Для подавления этого артефакта можно применять следующие методы:
• Завышение оценки шумового порога (увеличение k). Приводит к подавлению слабых компонент полезного сигнала, звук становится глуше.
• Неполное подавление шума (ограничение снизу константой, отличной от нуля). Часть шума остается в сигнале и отчасти маскирует «музыкальный шум».
• Сглаживание по времени оценок спектра. Приводит к размытию или подавлению транзиентов (резких всплесков в сигнале: ударов, атак музыкальных инструментов).
• Адаптивное сглаживание оценок спектра по времени и частоте. Наиболее качественный, но и трудоемкий метод.
Наиболее распространенный способ подавления «музыкального шума» – использует сглаживание спектра по времени. Для этого к STFT-коэффициентам исходного сигнала применяется рекурсивная фильтрация по времени. Более качественного подавления можно достичь, применяя к спектрограмме адаптивные двумерные алгоритмы фильтрации, такие как билатеральный фильтр или алгоритм нелокального усреднения, используемые в шумоподавлении для изображений.
3.2 Передискретизация
Ресамплинг (передискретизация, resampling) – это изменение частоты дискретизации цифрового сигнала. Применительно к цифровым изображениям ресамплинг означает изменение размеров изображения. Существует множество различных алгоритмов ресамплинга изображений. Например, для увеличения изображения в 2 раза можно просто продублировать каждую из его строк и каждый из его столбцов (а для уменьшения – выкинуть). Такой метод называется методом ближайшего соседа (nearest neighbor). Можно промежуточные столбцы и строки получить линейной интерполяцией значений соседних столбцов и строк. Такой метод называется билинейной интерполяцией (bilinear interpolation). Можно каждую точку нового изображения получить как взвешенную сумму большего числа точек исходного изображения (бикубическая и другие виды интерполяции).
Наиболее качественный ресамплинг получается при использовании алгоритмов, учитывающих необходимость работы не только с временной, но и с частотной областью изображения. Сейчас мы рассмотрим алгоритм ресамплинга, который основан на идее максимального сохранения частотной информации изображения. Алгоритм построен по принципу интерполяция / фильтрация / прореживание (interpolation / filtering / decimation).
Работу алгоритма будем рассматривать на одномерных сигналах, так как двумерное изображение можно сначала растянуть или сжать по горизонтали (по строкам) а потом – по вертикали (по столбцам). Таким образом, ресамплинг двумерного изображения сводится к ресамплингу одномерного сигнала.
Пусть нам нужно «растянуть» одномерный сигнал от длины n точек до длины m точек, т.е. в nm раз. Для выполнения этой операции необходимо выполнить 3 шага. Первый шаг – интерполяция нулями, увеличивающая длину сигнала в m раз. Нужно умножить все отсчеты исходного сигнала на m, а потом после каждого отсчета сигнала нужно вставить m-1 нулевое значение. При этом спектр сигнала изменяется следующим образом. Та часть спектра, которая изначально содержалась в цифровом сигнале, остается без изменения (именно этого мы добиваемся). Но выше старой половины частоты дискретизации возникают помехи (отраженные копии спектра), от которых необходимо избавиться с помощью фильтрации.
Второй шаг – это отфильтровывание этих помех с помощью НЧ-фильтра. Теперь мы получили сигнал, который в m раз длиннее исходного, но сохранил его частотную информацию и не приобрел посторонней частотной информации (ее мы отфильтровали). Если бы нашей задачей было удлинение сигнала в m раз, то на этом шаге можно было бы остановиться. Но наша задача требует теперь уменьшить длину сигнала в n раз. Для этого нужно выполнить 2 шага. Первый шаг – это антиалиасинговая фильтрация. Так как частота дискретизации уменьшается в n раз, то из спектра сигнала, согласно теореме Котельникова, удастся сохранить только его низкочастотную часть. Все частоты выше половины будущей частоты дискретизации нужно удалить с помощью антиалиасингового фильтра с частотой среза равной n1 от текущей половины частоты дискретизации. Второй шаг – это прореживание полученного сигнала в n раз. Для этого достаточно выбрать из сигнала каждый n-й отсчет, а остальные – отбросить. Этот алгоритм очень схож с работой АЦП, который тоже сначала отфильтровывает ненужные частоты из сигнала, а потом замеряет Заметим, что две НЧ-фильтрации, применяемые в этом алгоритме друг за другом, можно (и нужно) заменить одной. Для этого частоту среза единого НЧ -фильтра нужно выбрать равной минимуму из частот среза двух отдельных НЧ-фильтров. Еще одно существенное улучшение алгоритма – это поиск общих делителей у чисел m и n. Например, очевидно, что для того, чтобы сигнал из 300 точек сжать до 200 точек, достаточно положить в алгоритме m=2 и n=3.
Заметим, что приведенный алгоритм требует очень большого объема вычислений, т.к. промежуточный размер одномерного сигнала при ресамплинге может быть порядка сотен тысяч. Существует способ существенно повысить быстродействие алгоритма и сократить расход памяти. Этот способ называется многофазной фильтрацией (polyphase filtering). Он основан на том, что в длинном промежуточном сигнале совсем необязательно вычислять все точки. Ведь большая часть из них все равно будет отброшена при прореживании. Многофазная фильтрация позволяет непосредственно выразить отсчеты результирующего сигнала через отсчеты исходного сигнала и антиалиасингового фильтра.
Отметим, что здесь мы не рассматриваем такие детали алгоритма, как коррекция границ изображения, выбор фазы сигнала при интерполяции и прореживании и построение хорошего антиалиасингового фильтра. Отметим только, что для ресамплинга изображений требуется уделить особое внимание как частотной, так и пространственной характеристике фильтра. Если оптимизировать фильтр только в частотной области, то это приведет к большим пульсациям в ядре фильтра. А при ресамплинге изображений пульсации в ядре фильтра приводят к пульсациям яркости вблизи резких перепадов яркости в изображении (эффект Гиббса, Gibbs phenomenon)
3.3 Антиалиасинг изображений продолжение
--PAGE_BREAK--
Избежать алиасинга при генерации изображений – важная задача компьютерной графики. Алиасинг в изображениях приводит к зубчатости краев фигур, муару, плохой читаемости текста и графиков. Одним из основных способов предотвращения алиасинга является так называемый суперсамплинг (super-sampling). Этот прием заключается в генерации изображения с большим разрешением и ресамплингу этого изображения до нужного размера. Рассмотрим пример. Пусть нам нужно сгенерировать трехмерное изображение шахматной доски с разрешением 200x150 пикселей. Если сделать это непосредственно (например, трассировкой лучей через каждую точку экрана), то результат может быть существенно искажен алиасингом (рис. 13). Применим метод суперсамплинга. Сгенерируем нужное нам изображение с четырехкратным размером 800x600 пикселей, а затем уменьшим его до размера 200x150. Заметим, что качество получаемого таким образом изображения существенно лучше и зависит от качества алгоритма ресамплинга и от степени суперсамплинга (во сколько раз большее изображение мы сгенерировали). Желательно применять алгоритм ресамплинга, обеспечивающий хороший антиалиасинг.
/>/>
Рис. 13. Изображение, сгенерированное без антиалиасигна и с антиалиасингом.
Рассмотренный алгоритм широко применяется в компьютерной графике, несмотря на большие вычислительные затраты. Выбирая степень суперсамплинга, можно варьировать производительность алгоритма. Очевидно, что сложность алгоритма квадратично зависит от степени суперсамплинга. Обычно используются степени суперсамплинга от двух до четырех.
3.4 Псевдотонирование изображений
Псевдотонирование (half-toning) – это создание иллюзии полноцветности изображения с помощью небольшого реального числа цветов. Пример псевдотонирования – фотографии в газетах, где любые оттенки серого передаются с помощью чередования мелких черных и белых точек.
Мы рассмотрим вариант псевдотонирования для черно-белых изображений. Нашей задачей будет представить изображение с оттенками серого в виде монохромного (двухцветного) изображения.
Пусть мы имеем изображение в оттенках серого, интенсивность точек которого может принимать произвольные значения от 0 до 1. Рассмотрим некоторые алгоритмы приведения такого изображения к монохромному, яркость точек которого может принимать 2 значения: 0 или 1.
Первый самый простой алгоритм – это усечение (порог). Все пиксели с яркостью больше 0.5 получают яркость 1, все остальные – яркость 0. Такой алгоритм обычно дает наихудшие результаты (рис. 15).
Более качественные алгоритмы стремятся так распределить черные и белые пиксели в полученном изображении, чтобы на каждом участке изображения концентрация белых пикселей была пропорциональна яркости этого участка в исходном изображении.
Один из таких методов – упорядоченное псевдотонирование. В этом методе исходное изображение разбивается на небольшие блоки одинакового размера (например, 3x3). Затем в каждом блоке находится средняя яркость изображения. В соответствии с этой средней яркостью выбирается количество белых пикселей в соответствующем блоке получаемого монохромного изображения. Обычно эти белые пиксели упорядочиваются в соответствии с некоторым регулярным шаблоном (рис. 15).
Существуют другие алгоритмы достижения нужной концентрации белых пикселей в получаемом монохромном изображении. Например, существует класс алгоритмов, которые достигают этого в 2 стадии. Сначала к изображению добавляется случайный шум необходимой амплитуды, а затем применяется порог. Такие алгоритмы называют диттерингом (dithering).
Шум представляет собой некий достаточно случайный сигнал, не зависящий от изображения. Например, белый шум – это просто последовательность случайных чисел с математическим ожиданием 0. Спектр такого шума приблизительно равен константе на всех частотах (в пределах половины частоты дискретизации). Последовательные отсчеты такого шума не коррелируют между собой.
Существуют другие виды шума. Например, у розового шума энергия обратно пропорциональна частоте (в определенном рассматриваемом диапазоне частот). Другими словами, амплитуда его гармоник падает на 3 дБ при удвоении частоты. У голубого шума энергия наоборот растет с частотой. Существуют и другие виды шума, однако определения для них могут быть различны в разных областях.
Будем называть ошибкой квантования изображение, равное разности исходного и псевдотонированного изображений.
При псевдотонировании изображений стремятся добиться того, чтобы спектр изображения-ошибки по возможности не содержал низкочастотных и среднечастотных компонент. В этом случае ошибка будет менее заметна человеческому глазу. Например, при диттеринге розовым шумом спектр ошибки тоже близок к светло-розовому, и результирующее изображение выглядит значительно искаженным (рис. 15). При диттеринге белым шумом спектр ошибки белый. Поэтому результирующее изображение выглядит лучше. При диттеринге с диффузией ошибки спектр ошибки получается близок к голубому шуму, т.е. содержит мало низкочастотных компонент. В результате получается приятное глазу изображение.
Нетрудно видеть, что просто диттеринг голубым шумом не приводит к желаемому результату, т.к. ошибка квантования при этом имеет спектр, содержащий значительное количество низкочастотных и среднечастотных компонент. Для избавления от них нужно применить рекурсивный фильтр. Этот метод псевдотонирования называется диффузией ошибки (error diffusion). Его идея в том, что ошибка квантования, возникшая при квантовании данного пикселя, распространяется с обратным знаком на соседние пиксели и таким образом как бы компенсируется.
3.5 Выравнивание освещенности изображений
Часто некоторые участки на изображении бывают слишком темными, чтобы на них можно было что-то разглядеть.
Если прибавить яркости ко всему изображению, то изначально светлые участки могут оказаться совсем засвеченными. Чтобы улучшить вид изображения в таких случаях, применяется метод выравнивания освещенности.
Этот метод не является линейным, т.е. не реализуется линейной системой. Действительно, рассмотрим модель типичную освещенности для фотографии. Фотографируемый пейзаж обычно освещен по-разному в разных точках. Причем обычно освещенность меняется в пространстве достаточно медленно.
Мы хотим, чтобы все детали на фотографии были освещены более однородно, но при этом оставались достаточно контрастными друг относительно друга.
А на реальной фотографии получается произведение той картинки, которую мы хотим видеть и карты освещенности. Там где освещенность близка к нулю, все предметы и детали тоже близки к нулю, то есть практически невидимы.
Поскольку освещенность меняется в пространстве достаточно медленно, то можно считать ее низкочастотным сигналом. Само же изображение можно считать в среднем более высокочастотным сигналом. Если бы в процессе фотографии эти сигналы складывались, то их можно было бы разделить с помощью обычного фильтра.
Например, применив ВЧ-фильтр, мы бы «избавились от перепадов освещенности» (НЧ-сигнала), а оставили «само изображение». Но поскольку эти сигналы не складываются, а перемножаются, то избавиться от неравномерностей освещенности простой фильтрацией не удастся.
Для решения таких задач применяется гомоморфная обработка. Основной метод гомоморфной обработки заключается в сведении нелинейной задачи к линейной с помощью каких-либо преобразований. Например, в нашем случае можно свести задачу разделения перемноженных сигналов к задаче разделения сложенных сигналов. Для этого нужно взять логарифм от произведения изображений.
Логарифм от произведения равен сумме логарифмов сомножителей. Если учесть, что логарифм от НЧ-сигнала остается НЧ-сигналом, а логарифм от ВЧ-сигнала остается ВЧ-сигналом, то мы свели задачу разделения произведения сигналов к задаче разделения суммы НЧ- и ВЧ-сигналов. Очевидно, эту задачу можно решить с помощью ВЧ-фильтра, который удалит из суммы сигналов низкие частоты. После этого останется только взять от полученного сигнала экспоненту, чтобы вернуть его к исходному масштабу амплитуд.
ВЧ-фильтр можно реализовать следующим образом. Сначала к изображению применяется операция размытия (НЧ-фильтр), а потом из исходного изображения вычитается размытое.
Наилучший радиус размытия зависит от конкретного изображения. Можно начать эксперименты с радиуса порядка десяти пикселей.
Обычно для размытия изображения применяется двумерный гауссовский фильтр.
Непосредственное вычисление двумерной свертки с таким ядром потребует огромных вычислений даже при сравнительно небольшом размере ядра. Однако приведенное гауссово ядро обладает свойством сеперабельности.
Это означает, что эквивалентного эффекта можно достичь, отфильтровав сначала все строки изображения одномерным гауссианом, а затем отфильтровав все столбцы полученного изображения таким же одномерным гауссианом.
Полученный от выравнивания освещенности эффект может оказаться слишком сильным (темные области станут по яркости такими же, как и светлые). Чтобы уменьшить эффект, можно просто смешать обработанное изображение с исходным в определенной пропорции.
3.6 Другие применения
Улучшение изображений и художественные эффекты
Для улучшения изображений и создания различных художественных эффектов часто применяется фильтрация. Например, для придания изображению резкости можно воспользоваться фильтром, который усиливает сигнал на высоких частотах. Существуют фильтры для выделения или нахождения границ в изображении, размытия, направленного смазывания изображений, создания различных эффектов, таких как акварель, тиснение. продолжение
--PAGE_BREAK--
Поиск фрагментов в изображениях
Для поиска фрагментов в изображениях применяется двумерная корреляция. Сигналом для поиска является изображение, а искомым сигналом – искомый фрагмент изображения. Эффективное вычисление корреляции стало возможным благодаря двумерному БПФ.
Компрессия изображений
Методы цифровой обработки сигналов позволяют достаточно эффективно сжимать изображения в частотной области. Например, алгоритм JPEG действует следующим образом (упрощенно). Изображение разбивается на фрагменты размером 8x8 пикселей, и каждый фрагмент переводится в частотную область. После этого в каждом фрагменте те высокочастотные составляющие, амплитуда которых мала, выкидываются, а все остальные – кодируются. Ясно, что для тех областей изображения, где яркость изменяется, не очень быстро (а таких большинство), высокочастотных компонент почти нет. Таким образом, удается выкинуть из спектра существенную часть не очень важной информации. В JPG-файле кодируются оставшиеся «существенные» амплитуды.
В алгоритме JPEG применяется модификация ДПФ: дискретное косинусное преобразование (ДКП). ДКП от двумерного сигнала можно вычислить, отразив четным образом сигнал относительно нулевой точки и вычислив двумерное ДПФ полученного сигнала с двукратными размерами. В полученном спектре будут содержаться только «косинусные» коэффициенты.
Восстановление изображений
При съемке движущегося объекта неподвижной камерой полученное изображение получается смазанным. Если знать параметры движения объекта, то можно построить ядро свертки, которое камера «применила» к снимаемому сигналу. Затем с помощью метода деконволюции можно в значительной степени устранить эффект размытия.
Иногда при съемке камера может вносить в изображение интерференцию – периодический муар, накладываемый на изображение. Часто оказывается, что спектр этой интерференции состоит из одной – двух гармоник. В этом случае ее можно эффективно удалить с помощью фильтра, который подавляет заданные частоты (notch filter).
Заключение
Работая над данным обзором, по долгу службы что называется, мне пришлось посетить ряд отечественных фирм, специализирующихся на создании аппаратных и программных средств обработки цифровых сигналов. Впечатления – самые приятные. Уровень разработок – мировой, общее ощущение от фирм – как во вложениях хорошего хозяина: прочность, ухоженность и стабильность, настроение – рабочее, никакого нытья и уныния!
Иными словами, цифровая обработка – это одна из перспективных областей высоких наукоемких технологий – high tech – привлекательная для приложения сил. В исторической ретроспективе, лет этак через 20, в «Российской компьютерной энциклопедии – 2020» может быть напишут: «В конце ХХ века, с падением „железного занавеса“ и началом перехода к рыночным отношениям, компьютерная промышленность России пережила глубокий кризис. Однако после известных событий августа 1998 года начался бурный рост прикладных направлений, связанных с разработкой промышленных контроллеров, цифровых средств связи и мультимедийных устройств для персональных компьютеров».
Для истинных талантов – это чудесная возможность проявить себя, заставить «мир прогнуться». В среднем на уровне обычного активного человека с инженерным дипломом цифровые методы обработки сигналов – это рабочие места для специалистов оборонных НИИ. Для молодежи – мультимедийные технологии или цифровая связь – благодатнейшие области, где порхают «жар-птицы», которых нужно ухватить за хвост.
Вспомните еще раз историю вычислительной техники. У истоков персональных вычислений стояли два молодых (чуть больше 20 лет) человека – Стив Джобс и Стив Возняк, которые, если верить компьютерной мифологии, сделали свой первый персональный компьютер – прототип Apple-I – в гараже, а потом захватили значительную часть мирового рынка продаж персональных компьютеров.
А деньги где взяли? Автомобильчик – тот самый, что в гараже стоял, – продали. А папаша Билл Гейтс, стабильно занимающий одно из первых мест в списке богатейших людей Америки? А изобретатель мыши Дуглас Энгельбарт? А разработчик звуковых карт? В общем – список бесконечен.
А мы чем хуже? Гараж есть, автомобильчик есть, образование – на зависть Биллу и Стиву. Опять ничего не понимаю. Климат, что ли, у нас не тот? Но ничего, будем надеяться, что старшие товарищи – генералы компьютерной индустрии меня публично высекут и поправят. Кто поднимет перчатку? Или в своей стране мы никогда не дождемся ответа на неправильные вопросы и никогда не выйдем из состояния «неграждан»?
Список литературы
1. Специализированный процессор для выполнения быстрого преобразования Фурье и обработки сигналов СПФ СМ. Рекламные материалы. М.: ИНЭУМ, 1984.
2. Корнеев В. В., Киселев А. В. Современные микропроцессоры. М.: НОЛИДЖ, 1998. 240 с.
3. Цифровые процессоры обработки сигналов. Справочник. Остапенко А. Г., Лавлинский С. И., Сушков А. В. и др. Под ред. А. Г. Остапенко. М.: Радио и связь, 1994. 264 с.
4. Клингман Э. Проектирование специализированных микропроцессорных систем. Пер. с англ. М.: Мир, 1985. 363 с.
5. Белоус А. И. и др. Микропроцессорный комплект БИС серии К1815 для цифровой обработки сигналов. Справочник. Белоус А. И., Поддубный О. Б., Журба В. М. Под ред. А. И. Сузопарова. М.: Радио и связь, 1992. 256 с.
6. Лапа В. Г. Математические основы кибернетики. Киев, Высшая школа, 1974. 452 с.