bilety i otvety 1 (1)


Оглавление
TOC \o "1-3" \h \z \u 1. Цифровые фильтры. Основные характеристики фильтров. Децибелы PAGEREF _Toc408162194 \h 22. Цифровые фильтры. Временные характеристики PAGEREF _Toc408162195 \h 43. Цифровые фильтры. Частотные характеристики. PAGEREF _Toc408162196 \h 54. Цифровые фильтры. Построение режекторных и полосовых фильтров. PAGEREF _Toc408162197 \h 75. Однородные нерекурсивные фильтры. PAGEREF _Toc408162198 \h 86. Переходная характеристика и подавление шума. PAGEREF _Toc408162199 \h 97. Модифицированные однородные фильтры. PAGEREF _Toc408162200 \h 108. Однородные рекурсивные фильтры. PAGEREF _Toc408162201 \h 129. Принципы построения оконных фильтров PAGEREF _Toc408162202 \h 1310. Оконные фильтры и их расчет. PAGEREF _Toc408162203 \h 1511. Оконные фильтры. Применение. Сверхвысокая точность. PAGEREF _Toc408162204 \h 1712. Рекурсивные фильтры.Расчет параметров рекурсивных фильтров. PAGEREF _Toc408162205 \h 1913. Однополюсный рекурсивный фильтр. PAGEREF _Toc408162206 \h 2114. ФЧХ рекурсивных фильтров. PAGEREF _Toc408162207 \h 2315. ФЧХ. Двунапрвленная фильтрация. PAGEREF _Toc408162208 \h 2416. Фильтры Чебышева и Батерворда их свойства и применение. PAGEREF _Toc408162209 \h 2617. Переходные характеристики, перерегулирование и устойчивость фильтров Чебышева и Батерворда. PAGEREF _Toc408162210 \h 2818. Сравнительный анализ фильтров. PAGEREF _Toc408162211 \h 3024. Распознавание речи. Фреймы. Разбиение слов. PAGEREF _Toc408162212 \h 33Входные данные PAGEREF _Toc408162213 \h 34Распознавание PAGEREF _Toc408162214 \h 36Фреймы PAGEREF _Toc408162215 \h 37Разбиение слов PAGEREF _Toc408162216 \h 37MFCC PAGEREF _Toc408162217 \h 38Разложение в ряд Фурье PAGEREF _Toc408162218 \h 39Расчёт mel-фильтров PAGEREF _Toc408162219 \h 40Применение фильтров, логарифмирование энергии спектра PAGEREF _Toc408162220 \h 43Косинусное преобразование PAGEREF _Toc408162221 \h 43Алгоритм распознавания PAGEREF _Toc408162222 \h 44Эксперименты PAGEREF _Toc408162223 \h 45Реализация PAGEREF _Toc408162224 \h 4525. Мел-кепстральные коэффициенты. PAGEREF _Toc408162225 \h 4526. Бинеризация изображений. Методы бинаризации. PAGEREF _Toc408162226 \h 5327. Применение ФВЧ и ФНЧ при обработке изображений. PAGEREF _Toc408162227 \h 5828.Медианные фильтры. Адаптивные медианные фильтры. PAGEREF _Toc408162228 \h 76Обобщение медианного фильтра PAGEREF _Toc408162229 \h 76Адаптивная медианная фильтрация PAGEREF _Toc408162230 \h 7929.Вейвлеты. Принципы и применение вейвлета Хаара. PAGEREF _Toc408162231 \h 92Вейвлет-сжатие «на пальцах» tutorial PAGEREF _Toc408162232 \h 9230.Вейвлеты. Принципы и применение вейвлета Добеши. PAGEREF _Toc408162233 \h 10231.Фильтрация контуров. Оператор Кэни. PAGEREF _Toc408162234 \h 104Основные этапы алгоритма PAGEREF _Toc408162235 \h 10632.Фильтрация контуров. Оператор Собеля. PAGEREF _Toc408162236 \h 107Упрощённое описание[править | править вики-текст] PAGEREF _Toc408162237 \h 107Формализация[править | править вики-текст] PAGEREF _Toc408162238 \h 107Строго говоря..[править | править вики-текст] PAGEREF _Toc408162239 \h 108Расширение на другое количество измерений[править | править вики-текст] PAGEREF _Toc408162240 \h 108Технические детали[править | править вики-текст] PAGEREF _Toc408162241 \h 109Примеры[править | править вики-текст] PAGEREF _Toc408162242 \h 110Оператор Щарра[править | править вики-текст] PAGEREF _Toc408162243 \h 110См. также PAGEREF _Toc408162244 \h 11033.Линейная пространственная фильтрация. PAGEREF _Toc408162245 \h 111
1. Цифровые фильтры. Основные характеристики фильтров. Децибелы   К характеристикам фильтров относятся: 1) передаточная функция; 2) амплитудно-частотная характеристика; 3) фазо-частотная характеристика; 4) частота среза ωср (fср ); 5) постоянная времени τ;  6) полоса пропускания (подавления) Δω (?Δf); 7) резонансная частота; 8) добротность .          Передаточная функция это отношение изображения по Лапласу выходной величины изображению по Лапласу входной величины фильтра.a
.    (2.40)
          В общем случае фильтр можно рассматривать как четырехполюсник с передаточной функцией
,                   (2.41)
          где U1(p) U2(p) – входное и выходное напряжение четырехполюсника в операторной форме; a и b – вещественные постоянные величины; m, n = 1,2,3, …; n – определяет порядок фильтра.          Для установившейся частоты р = jω и передаточную функцию можно привести к виду 
.         (2.42)
          Модуль передаточной функции (2.42) называется амплитудно-частотной характеристикой
.              (2.43)
          Фазо-частотная характеристика также может быть найдена из (2.42) и представлена в виде 
                  (2.44)
          Диапазон Δω = ω2 –ω1 (рис. 2.23, в) или полосы частот, в которых проходят сигналы, называются полосами пропускания. В полосе пропускания значение коэффициента передачи фильтра  относительно велико, а в идеальном случае постоянно. Для полосового фильтра частоты ω1 и ω2  определяются при спаде коэффициента передачи  на 3 дБ.          Диапазон частот Δω = ω2 –ω1  (рис. 2.23,г), в которых сигналы подавляются, образуют полосу задержания. В полосе задержания коэффициент передачи фильтра относительно мал, а в идеальном случае равен нулю. Для заграждающего фильтра частоты ?1 и ?2 определяются при спаде коэффициента передачи на 3 дБ.          Частота среза ωср (fср ) – частота на которой наблюдается спад коэффициента передачи на 3 дБ по сравнению с коэффициентом передачи на нулевой (для ФНЧ) или бесконечной (для ФВЧ) частоте.           Резонансная частота fР – частота, на которой коэффициент передачи фильтра имеет максимальное значение (для полосового фильтра) или минимальное значение (для заграждающего фильтра).          Добротность  - добротность полосового фильтра определяется как отношение резонансной частоты к полосе пропускания .
Децибе́л — логарифмическая единица уровней, затуханий и усилений.[1]Величина, выраженная в децибелах, численно равна десятичному логарифму безразмерного отношения физической величины к одноимённой физической величине, принимаемой за исходную, умноженному на десять:

где AdB — величина в децибелах, A — измеренная физическая величина, A0 — величина, принятая за базис.
Децибел — это безразмерная единица, применяемая для измерения отношения некоторых величин — «энергетических» (мощности, энергии, плотности потока мощности и т. п.) или «силовых» (силы тока, напряжения и т. п.). Иными словами, децибел — это не абсолютная величина, как, например, ватт или вольт, а такая же относительная, как кратность («трёхкратное отличие») или проценты, предназначенная для измерения отношения двух других величин, причём к полученному отношению применяется логарифмический масштаб.
Русское обозначение единицы «децибел» — «дБ», международное — «dB»[2] (неправильно: дб, Дб).
2. Цифровые фильтры. Временные характеристикиНаверное, то решающее значение, которое отводится переходной характеристике
при проекmровании фильтров во временной области, является не вполне
очевидным. Действительно, почему же импульсная характеристика такой важности
не представляет? Ответ на этот вопрос кроется в способе работы человеческогомозга по осознаванию и обработке информации. Не забывайте, что переходная,
импульсная и частотная характеристики содержат в себе одну и ту же
информацию, которая отличается только формой её представления. Однако при
анализе во временной области переходная характеристика оказывается самой
важной, потому что она наилучшим образом соответствует человеческому восприятию
информации, содержащейся в сигнале.
Предположим, что имеется запись сигнала какого-либо неизвестного происхождения
и от вас требуется проанализировать этот сигнал. Первым вашим действием
станет попытка разделить сигнал на отдельные фрагменты, на протяжении
которых его параметры слабо изменяются. Вы так поступите, даже не осознавая этого: так устроен наш мозг. Одни области могут оказаться более гладкими, другие
будут характеризоваться значительными перепадами амплитуды, в ряде областей
будут присутствовать сильные шумовые помехи. В результате такой сегментации
определяются граничные точки областей. И вот тут как раз появляется
необходимость введения ступенчатой функции . Ступенчатая функция позволяет
наиболее просто описать переход между двумя различающимися по своим параметрам
областями. Она соответствует началу или окончанию какого-либо события.
Ступенчатая функция всегда указывает на существование некоторого различия
между тем, что находится слева, и тем, что находится справа. Таким образом,
в процессе своего восприятия информации, представленной во временной области,
человеческий мозг неявно использует набор ступенчатых функций, чтобы
разделить имеющуюся информацию на однородные области. В свою очередь переходнаяхарактеристика оказывается необходимой, так как она описывает характер
измения сигнала в точках перехода при обработке фильтром .Основные параметры переходной характеристики, используемые при расчёте
фильтров, показаны на Рис. 14.2. Для разделения присутствующих в сигнале событий
требуется, чтобы длительность переходной характеристики не превышала
интервала между событиями. Следовательно, как показано на (а и б), переходный
процесс должен быть настолько быстрым, насколько это возможно. Как правило,
время установления определяется количеством отсчётов дискретного сигнала, соответствующих
изменению амплитуды сигнала от уровня 10% до 90% от её установившегося
значения. Почему не всегда возможно использовать фильтры с высокимбыстродействием? Причины могут быть самые разные: необходимость
подавления шума, наличие собственных неустранимых ограничений в системах
сбора данных, устранение наложения спектров и т. д.
На (в и г) демонстрируется очень важный параметр фильтра - перерегулирование.
Предпочтительнее использовать фильтры с малым перерегулированием, чтобы
уменьшить вносимые в сигнал амплитудные искажения, которые являются
наиболее значимыми искажениями во временной области. При практическом измерении
сигналов часто возникает следующий вопрос: связан ли наблюдаемый
всплеск амплитуды с самим измеряемым сигналом или он отражает переходный
процесс?
Очень часто требуется обеспечить симметрию верхней и нижней частей переходной
характеристики, как показано на (д и е). Такая симметрия необходима длятого, чтобы передний и задний фронты импульсов получали искажения одинаковойформы. Фильтры с подобной симметрией называются линейно-фазовыми,
поскольку их фазо-частотная характеристика (ФЧХ) имеет вид прямой линии
(Глава 19). Постарайтесь как следует разобраться с тремя вышеперечисленными
показателями, так как они играют важную роль при анализе фильтров во временнойобласти.
3. Цифровые фильтры. Частотные характеристики.
На Рис. 14.3 рассмотрены частотные характеристики четырёх основных типов
фильтров. Эти фильтры предназначены для того, чтобы пропускать без изменения
одни частоты входного сигнала и задерживать другие. Диапазон пропускае-
мых фильтром частот называется полосой пропускания, а диапазон задерживаемых
частот - зоной подавления. Между ними располагается переходная зона фильтра.
Если фильтр имеет узкую переходную зону, то говорят, что он обладает высокой частотной избирательностью. Граничная частота, разделяющая полосу пропускания
и переходную зону, называется частотой среза. Для аналоговых фильтров
частота среза определяется точкой, в которой АЧХ спадает до уровня 0.707
(-3 дБ). Для цифровых фильтров нет таких жестких стандартов, и граничная частота
часто определяется точкой, в которой АЧХ спадает до одного из следующих
уровней: 99, 90, 70.7 и 50%. На Рис. 14.4 показаны три показателя, характеризующие качество работы
фильтра в частотной области. Способность фильтра разделять близкие частоты
называется частотной избирательностью и определяется крутизной спада АЧХ
(а и б). Для устранения искажений, вносимых фильтром в пропускаемый им сигнал,
необходимо, чтобы нерqвномерность АЧХ в полосе пропускания стремилась к
нулю (в и г). Для эффективного подавления частот в зоне непрозрачности необходимвысокий уровень затухания (д и е).
Почему среди этих параметров нет ни одного, характеризующего фазу?
Во-первых, в большинстве практических приложений, связанных с обработкой
сигналов в частотной области, фаза не играет роли. Например, в звуковоспроизводящей
аппаратуре фаза может принимать совершенно случайные значения и
практически не несёт в себе никакой информации. Во-вторых, при расчёте цифровыхфильтров очень легко добиться того, чтобы фазо-частотная характеристика
получилась идеальной, т. е. чтобы все частоты, лежащие в полосе пропускания,
проходили на выход фильтра с нулевым фазовым сдвигом (глава 19). Заметим, что
для аналоговых фильтров данная проблема является «ужасно» сложной.
В предыдущих главах уже говорилось о том, как с помощью ДПФ найти по импульсной
характеристике системы её частотную характеристику. Кратко повторим
здесь этот материал. Самый быстрый способ вычисления ДПФ заключается виспользовании
алгоритма БПФ, описанного в Главе 12. Алгоритм БПФ позволяет для заданной импульсной характеристики фильтра длиной N отсчётов найти его частотнуюхарактеристику, вещественная и мнимая части которой состоят из N дискретных
отсчётов каждая. Но лишь отсчёты с порядковыми номерами O ... N/2 несуг полезную
информацию, а остальные являются их зеркальным отражением и,
следовательно, могут быть исключены из дальнейшего рассмотрения (эти отсчётычастотной характеристики соответствуют отрицательным значениям частоты) . Разделение на вещественную и мнимую компоненты неудобно для человеческого
восприятия, поэтому предпочтительнее оказывается полярная форма представления
комплексных характеристик (Глава 8). Комплексная частотная характеристика
при этом оказывается разбитой на амплитудно-частотную и фазо-частотную характеристики,
каждая из которых представлена дискретными отсчётами с порядковыми
номерами O ... N/2 (всего N/2 + 1 отсчёт). Например, если исходная импульсная
характеристика представлена 256 дискретными отсчётами, то в полученной
частотной характеристике следует оставить отсчёты с номерами 0 ... 128. При этом
отсчёт номер О соответствует постоянной составляющей (нулевой частоте), а отсчёт
номер 128 - половине частоты дискретизации. Запомните, что спектры дискретныхсигналов рассматриваются на частотах, не превышающих половины частоты
дискретизации: спектр дискретного сигнала на более высоких частотах периодически
повторяет спектр основного (низкочастотного) диапазона.
Число отсчётов импульсной характеристики не может быть выбрано произвольным.
Например, требуется найти частотную характеристику КИХ-фильтра,
имеющего 80 весовых коэффициентов. Поскольку БПФ можно применить только
к массиву дискретных отсчётов, размер которого равен степени числа 2, то необходимо
дополнить имеющийся изначально массив из 80 весовых коэффициентов
48 нулями, чтобы получить массив длиной 128 отсчётов. Дополнение нулями
не изменяет импульсную характеристику фильтра. Чтобы лучше понять это,
представьте себе весь процесс выполнения дискретной свёртки . Добавленные к
импульсной характеристике нулевые отсчёты не оказывают влияния на формирование
результирующей последовательности.
Продолжая применять эту операцию, можно и далее добавлять нули к импульснойхарактеристике, доведя её длину, скажем, до 256, 512 или 1024 отсчётов.
Увеличение длины импульсной характеристики обеспечивает более плотное размещение
отсчётов в полученной в результате применения алгоритма БПФ частотной
характеристике. То есть отсчёты полученной частотной характеристики будут
расположены чаще на интервале частот от постоянной составляющей до
половины частоты дискретизации. В пределе при дополнении импульсной характеристики
бесконечным числом нулей расстояние между соседними отсчётами
получаемой частотной характеристики стремится к нулю, а сами отсчёты сливаются
в одну непрерывную кривую. Можно сказать, что частотная характеристика
фильтра является непрерывной функцией, заданной на интервале от постоянной
составляющей до половины частоты дискретизации, а применение БПФ соответствует
её дискретизации с некоторым постоянным шагом. До какой длины
нужно дополнить импульсную характеристику фильтра, для того чтобы найти его
частотную характеристику? Для начала можно попробовать дополнить импульснуюхарактеристику нулями до 1024 отсчётов, а затем уже изменить это значение
в большую или меньшую сторону, если выяснится, что разрешение по частоте
слишком мало или что время вычисления недопустимо велико.
Учтите, что понятия «Хороший» и «Плохой», которыми мы часто пользовались
в этой главе, носят идеализированный характер и в ряде случаев необходим дополнительный
более глубокий анализ. На снятой ЭКГ в рассмотренном выше
примере присутствуют наводки от сети питания. Хотя информация представлена
во временной области, от помех проще всего избавиться, «вырезав» соответствующуюполосу частот, т. е. рассматривая сигнал в частотной области. Наилучшее решение данной проблемы заключается в достижении некоторого компромисса
между повышением качества во временной и частотной областях. Такой комбинированный
критерий несколько отличается от введённых выше показателей качества
фильтра. Запомните первое правило обучения: в любой книжной фразе
следует не раз усомниться и осмыслить её суть, а не принимать утверждения как
неоспоримую истину.
4. Цифровые фильтры. Построение режекторных и полосовых фильтров.
При проектировании высокочастотных, полосовых и режекторных (заграждающих)
фильтров предварительно рассчитывают низкочастотный фильтр
(НЧ-фильтр), а затем преобразуют его к желаемому виду. Именно по этой причине,
говоря о расчёте фильтров, чаще всего описывают только НЧ-фильтры. Существует
два метода преобразования НЧ-фильтра в высокочастотный (ВЧ-фильтр) - инверсия
АЧХи обращение АЧХ Оба метода нашли широкое распространение .Пример инверсии показан на Рис. 14.5. На (а) изображена импульсная характеристика
оконного НЧ-фильтра (Глава 16). Такой КИХ-фильтр имеет 51 весовой
коэффициент, причём многие из коэффициентов настолько малы, что на графике
неотличимы от нуля. АЧХ фильтра (б) можно получить, дополнив импульснуюхарактеристику 13 нулями и применив БПФ 64-го порядка. Преобразование
НЧ-фильтра в ВЧ-фильтр выполняется в два действия: 1) меняем арифметические
знаки всех коэффициентов фильтра; 2) добавляем единицу к среднему отсчёту,
относительно которого импульсная характеристика симметрична. В результате
получаем ВЧ-фильтр, импульсная характеристика и АЧХ которого показаны на
(в и г). Инверсия АЧХ выражается в перевороте графика АЧХ сверху вниз. При
этом полоса пропускания превращается в зону подавления, а зона подавления -
в полосу пропускания. Это значит, что НЧ-фильтр превращается в ВЧ-фильтр,
ВЧ-фильтр - в НЧ-фильтр, полосовой - в режекторный , а режекторный - в полосовой.
Рис. 14.6 помогает разобраться в том, почему рассмотренное нами преобразование
импульсной характеристики фильтра приводит к инверсии его частотной
характеристики. Как показано на (а), входной сигнал х[п] поступает одновременно
на два звена, одним из которых является НЧ-фильтр с импульсной характеристикой
h[n], а другим - звено задержки (всепропускающий фильтр) , импульсная
характеристика которого описывается смещённой дискретной
дельта-функцией 8[п]. Результирующий выходной сигнал у[п] равен разности
сигналов, полученных на выходе звена задержки и на выходе НЧ-фильтра. Так
как низкочастотные компоненты спектра вычитаются из исходного сигнала , то в
выходном сигнале остаются только верхние частоты , а это значит, что мы получи -
ли ВЧ-фильтр.
Программная реализация данного метода предполагает два этапа: сначала
сигнал обрабатывается НЧ -фильтром, а затем результат фильтрации вычитается
из исходного сигнала. Две эти операции могут, однако, быть заменены одной
процедурой, если объединить весовые коэффициенты двух соответствующих
фильтров. Как указывалось в Главе 7, при параллельном соединении двух филь- трав их импульсные характеристики складываются. Как показано на (б), весовые
коэффициенты ВЧ-фильтра могут быть найдены в результате вычитания коэффициентов
НЧ-фильтра из дискретной дельта-функции: 8[п] - h[n]. То есть необходимо
выполнить знаковую инверсию всех элементов массива весовых коэффициентов
исходного ВЧ -фильтра, после чего добавить единицу к коэффициенту,
расположенному в середине массива.
В таком методе очень важно , чтобы низкочастотные компоненты спектра
входного сигнала появлялись на выходе НЧ -фильтра и на выходе линии задержки
в одной фазе. Обеспечить идеальное вычитание сигналов невозможно , поэтому
появляются два требования: 1) импульсная характеристика исходного НЧ -фильтра
должна обладать чётной симметрией (т. е. отвечать требованиям линейностифазы); 2) единицу необходимо добавлять к отсчёту, совпадающему с центром
симметрии .Другой метод получения ВЧ-фильтра - метод обращения АЧХ - проиллюстрирован
на Рис. 14.7. Импульсная характеристика НЧ-фильтра (а) и его АЧХ (б)
остались теми же, что и в приведённом ранее примере. Импульсная характерис- тика ВЧ-фильтра (в) образуется путём изменения арифметического знака у каждого
второго отсчёта исходной импульсной характеристики НЧ-фильтра (а). Из
(г) следует, что АЧХ ВЧ-фильтра получается поворотом АЧХ НЧ-фильтра слева
направо,т. е. точки с абсциссами О и 0.5 меняются местами. Так как граничная
частота НЧ-фильтра равна 0.15, то граничная частота ВЧ-фильтра равна 0.35.
Изменение арифметического знака каждого второго коэффициента эквивалентно
умножению отсчётов импульсной характеристики на отсчёты синусоиды,
имеющей относительную частоту 0.5. В Главе 10 было показано, что такая операция
соответствует сдвигу в частотной области на 0.5. Представим себе, что на (б)
изображены не только положительные, но и отрицательные частоты. Диапазон
частот -0.5 ... 0 является зеркальным отражением диапазона 0."0.5. Именно эти
отрицательные частоты попадают в результате операции обращения АЧХ в тот
диапазон, который мы видим на (г).
На Рис. 14.8 и 14.9 поясняется процесс получения импульсных характеристик
полосовых и режекторных фильтров с помощью комбинации НЧ и ВЧ-фильтров.
Основное отличие в способе получения характеристик полосовых и режекторных
фильтров состоит в том, что для первых выполняется свёртка импульсных характеристик
НЧ и ВЧ-фильтров , тогда как для вторых - простое поэлементное сложение.
Это значит, что в первом случае используется последовательное включение
фильтров, а во втором - параллельное (Глава 7). Один и тот же фильтр можно
получить, используя самые разные комбинации описанных приемов. Например, можно получить полосовой фильтр, выполнив сначала сложение двух импульсных
характеристик, а затем воспользовавшись методом инверсии или обращения
АЧХ. Все описанные нами методы работают замечательно, но и для них существуют
свои особенности.
5. Однородные нерекурсивные фильтры.
Однородные фильтры часто называют фильтрами скользящего среднего, потому
что они основаны на усреднении некоторого множества отсчётов входного сигнала,
что выражается следующим разностным уравнением:

Уравнение однородного нерекурсивного фильтра. Здесь х[ ] - входной сигнал,
у[ ] - выходной сигнал, М - число усредняемых отсчётов. В данном уравнении все используемые
отсчёты расположены по одну сторону от результирующего выходного отсчёта.
Например, для однородного фильтра 5-го порядка 80-й отсчёт выходного сигнала
определяется следующим уравнением:

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

Такой вариант усреднения связан с изменением пределов вычисления суммы
в выражении (15.1). Вместо j = О ... (М - 1) используем новые номера отсчётов
входного сигнала:j = -(М - 1)/2 ... (k/ - 1)/2. В результате при вычислении скользящегосреднего по 11 отсчётам входного сигнала индекс j может меняться либо
от О до 10 (одностороннее усреднение), либо от -5 до 5 (симметричное усреднение).
При симметричном усреднении необходимо, чтобы Мбыло нечётным числом.
Несмотря на то что программа для алгоритма одностороннего усреднения
несомненно проще, данный алгоритм приводит к возникновению относительного
сдвига между входным и выходным сигналами.
Запомните, что однородные фильтры - это фильтры с самой простой импульсной
характеристикой. Например, однородный нерекурсивный фильтр 5-ro порядка
имеет импульсную характеристику вида{ ... , О, О, 1/5, 1/5, 1/5, 1/5, 1/5, О, О, ... }.
То есть в основе однородных нерекурсивных фильтров лежит алгоритм свёртки
входного сигнала с прямоугольным импульсом единичной площади.

6. Переходная характеристика и подавление шума.
Очень часто учёные и инженеры, используя однородные фильтры, чувствуют
некоторую неуверенность. Дело в том, что однородные фильтры, как самые простые,
всегда стараются применить в первую очередь. И даже когда поставленная
задача уже полностью решена, все равно мучает вопрос: а может стоит перейти к
более сложным типам фильтров? Ситуация довольно забавна. Ведь однородные
фильтры не только находят очень удачное применение во множестве практичес кихприложений, но и являются оптимальными при решении такой распространённойзадачи, как подавление белого шума при одновременном сохранении заданной
скорости нарастания переходной характеристики. Функционирование однородного фильтра иллюстрирует Рис. 15.1. На вход
фильтра поступает сигнал, представляющий собой прямоугольный импульс, искажённый
аддитивной шумовой помехой (а). В результате фильтрации (б и в)
мощность шума заметно уменьшается (положительный эффект), но вместе с тем
снижается крутизна фронтов импульса (отрицательный эффект). Среди всех линейных
фильтров однородные фильтры характеризуются наиболее сильным подавлением
шума при заданной крутизне фронтов импульса. Коэффициент подавления
шума равен квадратному корню из числа отсчётов, участвующих в
усреднении. Так, фильтр 100-го порядка позволяет уменьшить шум в 10 раз. Чтобы понять, почему однородный фильтр обеспечивает наилучшее подавление
шума, присутствующего во входном сигнале, попытаемся рассчитать фильтр,
задав ограничение по скорости нарастания переходного процесса. Пусть протяжённость
переходного процесса составляет 11 отсчётов. Значит, фильтр имеет 11
весовых коэффициентов. Задача оптимизации заключается в ответе на вопрос:
как правильно выбрать значения 11 весовых коэффициентов, чтобы мощность
шума на выходе фильтра оказалась минимальной? Так как шумовая помеха - это
случайный процесс, то ни один из отсчётов не обладает какими-либо уникальными
свойствами по отношению к остальным, т. е. каждый отсчёт подвержен влиянию
шума в той же степени, что и окружающие его отсчёты. Поэтому не имеет смысла отдавать предпочтение какому-либо конкретному отсчёту входного сигнала,
увеличивая с этой целью один из коэффициентов фильтра . Наименьший
шум получается при выравнивании значений всех весовых коэффициентов, а
значит, при использовании однородного фильтра. Ниже в этой главе мы рассмотрим
фильтры, которые практически не уступают по своим характеристикам однородному.
Однако следует помнить, что фильтра, лучшего, чем однородный, с точки
зрения подавления шума не существует.
15.3. Частотная характеристика
На Рис. 15.2 показана АЧХ однородного фильтра. Математически она выражается
преобразованием Фурье от прямоугольного импульса (Глава 11):
H(f) = sin(n/M) .
Msin(nf)
(15.2)
АЧХ однородного фильтра М-го порядка.
Нормированная частота/ меняется от О до 0.5. При/= О, H(j) = 1.
Судя по Рис. 15.2, спад АЧХ очень медленный, а затухание в зоне непрозрачности
слишком далеко от идеала. Совершенно очевидно, что однородный фильтр
не может быть использован для отделения одного частотного диапазона от другого.
Не забывайте, что хорошее качество работы во временной области обычно сопровождается
слабым разрешением в частотной области и наоборот. Проще говоря,
однородный фильтр является самым лучшим сглаживающим фильтром (вовременной области), но вместе с тем и самым худшим НЧ-фильтром (в частотной
области).

7. Модифицированные однородные фильтры.
В своей профессиональной деятельности разработчикам цифровых фильтров
приходится иметь дело с информацией, заложенной либо во временной, либо в
частотной области (кодирование во временной и частотной области), и никогда информация
не размещается в этих двух областях одновременно. Однако встречаются
практические приложения, в которых сигнал все же необходимо рассматривать
сразу в двух областях. Одним из таких «неприятных» примеров служит телевизионныйсигнал. Видеоинформация кодируется во временной области , так как распределение
яркости по элементам изображения закладывается в форму передаваемого
сигнала. Однако в процессе передачи видеосигнала огромное значение
имеет его частотная структура: диапазон занимаемых частот, разделение частотных
диапазонов для изображений и звука, подавление и восстановление постояннойсоставляющей и т. п. Другим примером является учёт электромагнитныхпомех, которые удобнее анализировать в частотной , а не во временной области.
Типовыми помехами, например, для обычных научных и инженерных измерений,
являются: на частоте 60 Гц - помеха от сетей электропитания; на частоте 30 кГц -
от импульсных источников питания; на частоте 1320 кГц - со стороны радиостанций
FМ-диапазона. Модифицированные однородные фильтры отличаются от обычныхболее чёткой частотной локализацией и поэтому могут более эффективно использоваться
в подобных приложениях.
Фильтры с многократной обработкой представляют собой последовательноесоединение нескольких однородных фильтров, т. е. одна и та же процедура однороднойфильтрации повторяется в них последовательно несколько раз. На
Рис. 15.За показаны импульсные характеристики, построенные для фильтров содной, двумя и четырьмя ступенями обработки (каждая ступень - однородныйфильтр 7-го порядка). При наличии двух ступеней фильтр имеет треугольную импульсную
характеристику, поскольку треугольная характеристика может быть
представлена как результат свёртки двух прямоугольных характеристик. При увеличении
количества ступеней до четырёх и более форма импульсной характеристики
приближается к форме кривой Гаусса (согласно центральной предельной теореме).
По переходным характеристикам (б) видно, что для фильтров смногократной обработкой характерен s-образный переходный процесс в отличие
от однородного фильтра, которому соответствует линейно нарастающая реакция.
Частотные характеристики, приведённые на (в и г), получены в результате многократногоумножения АЧХ выражения (15.2) на саму себя. Умножение производится
столько раз, сколько последовательных звеньев содержится в фильтре. Такой
подход оказывается возможным в силу того, что каждой операции свёртки вовременной области соответствует операция умножения в частотной области.
На Рис. 15.4 изображены ЛАЧХ для ещё двух модификаций однородных фильтров.
Как уже говорилось выше (Глава 11), если импульсная характеристика фильтра
имеет вид кривой Гаусса, то и его АЧХ является также гауссовой. Импульсные
характеристики систем как естественного, так и искусственного происхождения
очень часто описываются кривой Гаусса. К примеру, если на вход длинного оптического
кабеля подать короткий импульс света, то на выходе кабеля будет принят
колоколообразный импульс, форма которого описывается функцией Гаусса. Та- кой эффект связан с различием длин траекторий распространения фотонов. Уникальные
свойства гауссовой импульсной характеристики широко используются всистемах обработки изображений при реализации алгоритма вычисления двумерной
свёртки (Глава 24). На Рис. 15.4 рассматривается фильтр с окном Блэкмана
(термин «ОКНО» подразумевает принаД.лежность фильтра Блэкмана к классу оконных
фильтров . ) Подробнее об оконной функции Блэкмана будет сказано в Г.лаве
16 ((16.2) и Рис. 16.2). По своему виду эта функция близка к гауссовой.
Какие же преимуrnества характерны для рассмотренных выше модификаций
однородных фильтров? Основных преимуrnеств - три. Во-первых, модифицированные
однородные фильтры позволяют достичь большего подавления в зоне непрозрачности,
чем обычные однородные фильтры. Во-вторых, их импульсная характеристика
на краях плавно сходится к нулю. Как вы помните, каждый отсчёт
выходного сигнала определяется взвешенной суммой группы входных отсчётов.
Поэтому сходимость к нулю импульсной характеристики означает, что отсчёты,
близкие к центру такой группы, оказывают более сильное влияние на формированиевыходного отсчёта. В-третьих, переходные процессы модифицированныхфильтров оказываются более плавными и не имеют резких изгибов. Последние
два преимуrnества менее важны, хотя, надо заметить, суrnествует ряд приложений,
в которых они оказываются очень полезными.
Модифицированные однородные фильтры и обычные однородные фильтры
проявляют приблизительно равные возможности при решении задачи подавления
шума при одновременном сохранении скорости нарастания переходной характеристики.
Точное решение вопроса, какой из фильтров лучше, связано с тем,
каким образом мы измеряем длительность переходного процесса. Если считать, что
переходный процесс - это время нарастания переходной характеристики от О до
100% её установившегося значения, то преимущество оказьmается на стороне
обычного однородного фильтра, как бьшо показано выше. Если длительность переходногопроцесса измерять интервалом времени, в течение которого переходнаяхарактеристика нарастает от 10 до 90% своей установившейся величины, то
фильтр Блэкмана несомненно превосходит однородный фильтр. Так что спор поэтому вопросу носит исключительно теоретический характер.
Наиболее заметным является различие в объёмах вычислительных затрат. Рекурсивные
однородные фильтры, речь о которых поЙдет далее, могут с лёгкостью
быть реализованы на обычном персональном компьютере. Это самые экономные
по вычислительным затратам фильтры. Затраты на реализацию фильтров с многократной
обработкой несколько больше, но всё же невелики. А вот фильтры Гаусса
и Блэкмана требуют очень большого объёма вычислений, так как основанына операции свёртки. Если считать, что умножение выполняется приблизительно
в 10 раз дольше, чем сложение, то фильтр Гаусса 100-го порядка требует примерно
в 1000 раз больше вычислений, чем рекурсивный однородный фильтр.

8. Однородные рекурсивные фильтры.
Однородные фильтры имеют одно важное преимуrnество перед всеми другими
: для них суrnествует самый простой алгоритм реализации, какой только можно
придумать. Чтобы понять этот алгоритм, рассмотрим следующий пример. Пусть сигнал х[ ] поступает на вход однородного нерекурсивного фильтра седьмого
порядка, ау[] - реакция этого фильтра. Тогда отсчётыу[50] иу[51] выражаются
соотношениями
у[50] =х[47] +х[48] +х[49] +х[50] + х[51] +х[52] +х[53]
и
у[51] =х[48] +х[49] +х[50] +х[51] +х[52] +х[53] +х[54].
Эти выражения во многом повторяют друг друга, поскольку отсчёты 48 ... 53
используются для вычисления и у[50], и у[51]. Если у[50] уже найден, то существует
более эффективный способ вычислить у[ 51]:
у[51] = у[50] + х[54] -х[47].
Если найдено значение у[50], то у[51] проще всего выразить через него. То же
самое относится и к последующим отсчётам выходной последовательности. Если
найден один отсчёт выходного сигнала у[ ] , каждый последующий может быть
найден в результате одной операции сложения и одной операции вычитания:
y[i] = y[i-l]+x[i+ p]-x[i-q],
где р = (М - 1)/2, (15.3)
q = р + 1.
Однородный рекурсивный фильтр. Здесь х[ ] - входной сигнал, у[ ] - выходной
сигнал, М - число (нечётное) усредняемых отсчётов. Перед началом использования
этой формулы необходимо вычислить первый отсчёт выходной последовательности
простым суммированием.
Как видим, этот алгоритм использует два источника данных: отсчёты входной
последовательности и найденные ранее отсчёты выходной последовательности.
Алгоритм, в котором найденные на предшествующих итерациях отсчёты выходной
последовательности также используются для вычисления последующих отсчётов
выходного сигнала, называется рекурсивным .. В Главе 19 подробно рассмотрено
множество рекурсивных фильтров. Однако однородные рекурсивные
фильтры существенно отличаются от остальных рекурсивных фильтров. В частности,
импульсная характеристика однородных фильтров имеет вид прямоугольногоимпульса, т. е. это фильтры с конечной импульсной характеристикой, или
КИХ-фильтры, в то время как рекурсивные фильтры образуют класс БИХ-фильтров,
а их импульсная характеристика имеет бесконечную длину и представляется
набором синусоид и экспонент.
Превосходство по вычислительным затратам однородных фильтров перед другими
объясняется несколькими причинами. Первая: требуется всего две операции
на обработку каждого входного отсчёта. Вторая: используются только сложение и
вычитание, тогда как большинство фильтров использует трудоёмкое умножение.
Третья: процедура вычисления индексов в выражении (15.3) очень проста: достаточно
выполнить сложение и вычитание предварительно найденных констант
(р и q). Четвёртая: все операции можно выполнять полностью в целочисленной
арифметике. Выигрыш по вычислительным затратам зависит от выбранной аппаратной
платформы, и в большинстве случаев эффективность вычислений в формате
с фиксированной точкой оказывается на порядок выше, чем при выполнении тех
же вычислений в формате с плавающей точкой. Удивительно, но целочисленная арифметика позволяет не только сократить
объём вычислительных затрат, но ещё и повышает точность работы алгоритма
фильтрации. При вычислениях в формате с плавающей точкой ошибка округления,
если её не учитывать, может привести к весьма нежелательным последствиям.
Предположим, что фильтр обработал 10 ООО отсчётов входного сигнала. Значит,
следующий отсчёт будет вычислен с ошибкой, накопленной отпредшествующих 10 ООО операций сложения и 10 ООО операций вычитания. Эта
ошибка проявляется в форме «дрейфа» выходного сигнала фильтра. Вычисления
в рамках целочисленной арифметики, как правило , протекают без округлений и
связанных с этим ошибок и не создают подобных трудностей. Но иногда избежать
вычислений в формате с плавающей точкой не удаётся, тогда для решения
проблемы «дрейфа» выходного сигнала приходится использовать двойную точность
вычислений, что проиллюстрировано в Программе 15.2.

9. Принципы построения оконных фильтров.
Оконные фильтры используются для решения задач частотной селекции сигналов.
Эти фильтры обладают высокой устойчивостью, стабильностью характеристик
и оказываются чрезвычайно эффективны для указанного класса задач.
Высокая эффективность фильтров в частотной области сопровождается ухудшением
временных характеристик - увеличиваются перерегулирование и колебательность
переходного процесса. В основе работы оконных фильтров лежит операция
свёртки. Поэтому их программная реализация оказывается довольно
проста, но они требовательны к вычислительным затратам. В Главе 18 будет показано,
каким образом можно значительно уменьшить вычислительную сложность
оконных фильтров, воспользовавшись алгоритмом БПФ.
16.1. Принципы построения оконныхфильтров
Основная идея построения оконных фильтров поясняется на Рис. 16.1. Идеальный
НЧ-фильтр должен иметь единичный коэффициент передачи во всём
диапазоне частот ниже частоты среза fc и полностью подавлять все остальные
частотные компоненты. Изображённая на (б) АЧХ сохраняет постоянное значение
на протяжении всей полосы пропускания и обладает бесконечно большим затуханием
в зоне непрозрачности фильтра. Разделяющая эти две области переходная
зона бесконечно мала. Идеальная импульсная характеристика, полученная врезультате выполнения обратного преобразования Фурье идеальной частотной
характеристики, описывается функцией вида sin(x)/x (а). Согласно выражению
(11.4), идеальная импульсная характеристика может быть представлена в общем

Для того чтобы создать идеальный НЧ-фильтр, необходимо выполнить алгоритм
свёртки входного сигнала с соответствующей ему импульсной характеристикой.
Однако на практике данный алгоритм не может быть реализован, поскольку
колебания функции sin(x)/x не затухают до нулевого значения и
продолжаются как в сторону положительных, так и в сторону отрицательных частот
бесконечно долго. С точки зрения математики, построение идеального фильтра
не представляет сложности, но на практике построение фильтра с бесконечным
числом весовых коэффициентов оказывается неразрешимой задачей. Обойти указанные трудности позволяют следующие два преобразования функции
sin(x)/x (а). На первом шаге выполняется усечение исходной функции до(М + 1) отсчётов по оси абсцисс, расположенных симметрично относительно
главного (основного) лепестка (М - чётное число). Всем остальным отсчётам
присваиваются нулевые значения, т. е. они просто отбрасываются. На втором шаге
полученная последовательность сдвигается вправо так, чтобы номера отсчётов
изменялись в пределах О ... М. В результате индексы всех весовых коэффициентов
становятся неотрицательными. Цель такого сдвига импульсной характеристики
фильтра на М/2 отсчётов состоит в том, чтобы задержать выходной сигнал фильтра
на то же число отсчётов. В результате преобразований получаем импульснуюхарактеристику, показанную на (в).
Выполненные преобразования привели к тому, что фильтр уже не является
идеальным и имеет другую АЧХ. Можно найти АЧХ полученного фильтра (г), выполнив
преобразование Фурье его импульсной характеристики. Как же сильно
она изменилась! Появились большие колебания в полосе пропускания фильтра, а
подавление в зоне непрозрачности стало чрезвычайно малым. Эти неприятные
последствия вызваны наличием разрывов на краях усечённой импульсной характеристики
(эффект Гиббса, описанный в Главе 11). Увеличение длины импульсной
характеристики не решает проблемы, так как не устраняет разрывов.
К счастью, существует простой метод компенсации возникших искажений.
На (д) показана плавно сходящаяся к нулю кривая, названная окном Блэкмана.
Импульсная характеристика оконного фильтра (е) представляет собой результат
поэлементного умножения усечённой идеальной импульсной характеристики (в)
на оконную функцию (д). Главной целью использования оконной функции является
сглаживание усечённой импульсной характеристики на краях. Одновременно
улучшаются и частотные свойства фильтра: АЧХ в полосе пропускания снова
становится плоской, а затухание в зоне непрозрачности значительно увеличивается
(ж).
Широкое применение получили несколько оконных функций, появившихся
в 50-х годах прошлого века и названных по именам их создателей. Наиболее распространены
две из них - окно Хэмминга (16.1) и окно Блэкмана (16.2).
w[i] = 0.54-0.46 cos(2ni / М) .Оконная функция Хэмминга. Данное соотношение справедливо в диапазоне О ... М;
вне этого диапазона значения нулевые.
w[i] = 0.42 - 0.5 cos(2ni / М) + 0.08 cos( 4ni / М).
Оконная функция Блэкмана. Данное соотношение справедливо в диапазоне О ... М;
вне этого диапазона значения нулевые .(16.1)
(16.2)
На Рис. 16.2а изображены обе оконные функции для М = 50 (т. е . для фильтра
51-го порядка). Ответ на вопрос о том, какая из двух функций лучше , . зависит от
конкретно решаемой задачи. Как видно на (б), АЧХ оконного фильтра Хэмминга
спадает в переходной зоне приблизительно на 20% быстрее, чем АЧХ фильтра
Блэкмана. Но, судя по (в), фильтр Блэкмана имеет более сильное затухание в зоне
непрозрачности. В данном случае коэффициент передачи фильтра Блэкмана в зоне
непрозрачности составляет - 74 дБ (- 0.02%), а фильтра Хэмминга – всего лишь -53 дБ (-0.2%). Неразличимый на приведенных графиках уровень неравномерности
АЧХ в полосе пропускания равен приблизительно 0.02% у фильтра
Блэкмана и 0.2% у фильтра Хэмминга. Чаще всего предпочтение отдают фильтру
Блэкмана, так как медленный спад его АЧХ представляется менее серьёзным недостатком,
чем слабое затухание в диапазоне подавляемых фильтром частот.
Имеются и другие оконные функции, о существовании которых необходимо
знать. Приведем ряд функций, уступающих окнам Блэкмана и Хэмминга, но всё
же иногда используемых на практике. Треугольная оконная функция получила
название окн.а Бартлетта. Окно Хеннинга, которое также называют функцией приподнятогокосинуса, описывается выражением w(i] = 0.5 - 0.5 cos(2ni/М).СоответствуюЩие этим двум оконным функциям фильтры практически не отличаются
по скорости спада АЧХ в переходной зоне от фильтра Хэмминга, но заметно
уступают ему по затуханию (коэффициент передачи в зоне подавления равен-25 дБ, или 5.6%, у фильтра Бартлетта и -44 дБ, или 0.63%, у фильтра
Хеннинга). В научной литературе часто встречается понятие прямоугольного окна.
Прямоугольная оконная функция не оказывает никакого формирующего действия,
оставляя усеченную импульсную характеристику (в) без изменений. Скорость
спада АЧХ прямоугольного оконного фильтра в 2.5 раза выше, чем у фильтра
Блэкмана, однако коэффициент передачи в зоне непрозрачности равен всего
лишь -21 дБ (8.9%).

10. Оконные фильтры и их расчет.
Для расчёта оконного фильтра необходимо предварительно задать два
параметра - частоту среза fc и порядок фильтра М. Частота среза может быть задана
отношением к частоте дискретизации. В этом случае она выбирается в диапазоне
0 ... 0.5. Величину М связывает с крутизной АЧХ следующая приближённая формула:

Связь между порядком фильтра и крутизной АЧХ. Величина М определяет ширину
переходной зоны фильтра BW. Равенство является приближённым, так как крутизна
спада зависит от выбора оконной функuии.
Здесь BW (bandwidth) - ширина переходной зоны фильтра, которая определяется
как диапазон, разделяющий область с близким к единице коэффициентом передачи,
и область, в которой коэффициент передачи близок к нулю (границы областейсоответствуют уровням 99 и 1 % от максимального коэффициента усиления). Ширину
переходной зоны можно выразить через приведенную частоту (т.е. через отношениек частоте дискретизации). В этом случае допустимые значения ширины переходной
зоны лежат в интервале 0 ... 0.5. На Рис. 16.3а поясняется смысл
выражения (16.3). Три кривые на графике построены для М = 20, 40 и 200. Из выражения
(16.3) следует, что ддя этих значений BW= 0.2, 0.1и0.02 соответственно.
На Рис. 16.3б показано, что крутизна АЧХ не зависит от выбора частоты среза. Так как объём вычислительных затрат, необходимый для выполнения операции
свёртки, пропорционален порядку фильтра М, то в выражении (16.3) отражается
противоречие между стремлением понизить вычислительную сложность алгоритма
и желанием уменьшить ширину переходной зоны фильтра BW.
Например, чтобы повысить крутизну спада АЧХ фильтра Блэкмана на те самые
20%, которые он проигрывает фильтру Хэмминга, достаточно увеличить количество
его весовых коэффициентов на 20%, что приведёт в свою очередь к такому
же увеличению вычислительных затрат. Но поскольку реализация оконных филь- тров, основанных на выполнении свёртки, и без того требует большого объёма
вычислений, то это очень сутественный недостаток.
На Рис. 16.Зб верхняя граничная частота определяется по уровню половиннойамплитуды. Почему вместо принятого для аналоговых фильтров уровня О. 707 (- 3дБ) в данном случае выбран уровень 0.5? Это объясняется наличием у оконныхфильтров строгой взаимосвязи между полосой пропускания и зоной непрозрачности.
Например, для рассмотренного ранее фильтра Хэмминга уровень неравномерности
в полосе пропускания равен 0.2% и совпадает по величине с уровнем
подавления в зоне непрозрачности, который тоже равен 0.2%. Другие цифровые
фильтры не имеют такой закономерности, и поэтому для них нет никакого преимущества
в определении верхней частоты среза фильтра по уровню половинной
амплитуды . Как будет показано далее, описанная взаимосвязь поведения АЧХ в
полосе пропускания и в зоне непрозрачности обуславливает отличную возможность
применения метода инверсии АЧХ при расчёте оконных фильтров.
После того как заданы параметры/с и М, весовые коэффициенты фильтра могут
быть найдены по формуле
Импульсная характеристика оконного фильтра. Здесь fc = 0 ... 0.5 - приведённая
частота среза (отношение верхней частоты среза в герцах к частоте дискретизации).
Номера весовых коэффициентов фильтра меняются в диапазоне О ... М, т. е. порядок
фильтра равен (М + 1). Параметр К выбирается таким, чтобы обеспечить единичный
коэффициент усиления на нулевой частоте. Чтобы устранить неопределённость приi = М/2, следует выполнить преобразование и получить h[i] = 2nfcK.
Стоящее в правой части сложное выражение не должно вас пугать. Теперь вы
легко можете выделить в нём три важные составляющие: функцию вида sin(x)/x,
сдвиг на М/2 и оконную функцию Блэкмана. Для получения фильтра с единичнымкоэффициентом усиления на нулевой частоте нужно так выбрать параметр
К, чтобы сумма всех весовых коэффициентов фильтра получилась равной единице.
Обычно при программной реализации фильтра избегают использования дополнительной
операции умножения на нормирующий коэффициент К, предварительно
умножая на К все весовые коэффициенты фильтра, как это сделано в
Программе 16.1. Кроме того, следует обратить внимание на вычисление центрального
коэффициента с индексом i = М/2, так как в выражении (16.4) в этом случае
возникает неопределённость вида 0/0.
Выражение (16.4) достаточно громоздко, но использовать его очень просто:
достаточно ввести указанное выражение в код программы и предоставить все вычисления
своему компьютеру. Если вы захотите выполнять все вычисления вручную,
то допустите много ошибок.
Как уже говорилось, весовые коэффициенты КИХ-фильтра совпадают с отсчётами
его импульсной характеристики. Теперь рассмотрим подробнее принцип
размещения отсчётов, найденных в соответствии с выражением (16.4), в памяти
компьютера. Пусть М равно 100. Тогда первый отсчёт импульсной характеристики
размещается в нулевой ячейке выделенного массива, а последний - в сотой
ячейке. То есть для хранения всех весовых коэффициентов достаточно массива,
состоящего из 1О1 элемента. Центральный коэффициент хранится в ячейке с по- рядковым номером М/2 = 50. Левые и правые 50 отсчётов симметричны относительно
центрального . Содержимое ячейки О равно содержимому ячейки 100, а
49-й отсчёт равен отсчёту с номером 51. Во многих случаях важно, чтобы количество
весовых коэффициентов фильтра принадлежало некоторому ряду допустимых
значений. Такая проблема решается введением дополнительных нулевых значений. Например, для алгоритма БПФ необходимо, чтобы число отсчётов было
равно степени двойки. При М = 100 достаточно просто увеличить длину массива
весовых коэффициентов фильтра до 128, записав нули в ячейки с номерами
101 ... 127.
На Рис. 16.4 показано несколько вариантов импульсных характеристик оконных
фильтров и соответствующие им переходные характеристики. Отсчёты, близкие
к краям импульсных характеристик, настолько малы, что на графиках их значения
практически неотличимы от нулевого уровня . Но это вовсе не значит, что
ими можно пренебречь! Будучи малыми по абсолютной величине, взятые в совокупностикрайние отсчёты оказывают большое влияние на частотные характеристики
оконного фильтра. Именно по этой причине для оконных фильтров
больше подходит арифметика с плавающей точкой, в то время как целочисленная
арифметика оказывается неспособной охватить широкий динамический диапазон
значений весовых коэффициентов. Попытаемся теперь ответить на вопрос :насколько хороши оконные фильтры для обработки информации во временной
области? Ответим сразу: они просто непригодны! На графиках, изображённых
справа, заметны ярко выраженный колебательный процесс и большое перерегулирование.
Такие фильтры не подходят для обработки сигналов, в которых информация
заложена во временной области.

11. Оконные фильтры. Применение. Сверхвысокая точность.
Электроэнцефалограмма (ЭЭГ) - это запись биотоков мозга. Получение ЭЭГ
связано с измерением напряжений порядка милливольта, возникающих на присоединённых
к голове человека электродах. Or каждой нервной клетки исходят
электрические импульсы. ЭЭГ отражает результат совместного действия огромного
числа электрических импульсов. Хотя взаимосвязь между мыслительнымпроцессом и электрическими колебаниями ещё недостаточно изучена, известно,
что разные частоты в ЭЭГ связаны с разными состояниями подсознания. Если вы
закроете глаза и расслабитесь, в ЭЭГ будут преобладать колебания низкой частоты:
приблизительно 7 ... 12 Гц. Такие колебания получили название альфа-ритма и
соответствуют состоянию удовлетворённости и пониженного уровня внимания.
Как только вы откроете глаза и посмотрите на окружающие предметы, возникнет
бета-ритм. Частота бета-волн лежит в диапазоне 17 ... 20 Гц. Можно _обнаружить и
колебания на других частотах, возникающие у детей , а также в различных фазах
сна и при нарушении работы мозга, например при эпилепсии.
Предположим, что сигнал ЭЭГ усиливается аналоговой частью аппаратуры, а
затем переводится в цифровую форму с частотой дискретизации 100 отсчётов всекунду. Значит, за 50 секунд будет получено 5000 отсчётов сигнала. Задача заключается
в том, чтобы отделить альфа-ритм от бета-ритма. Для этого достаточно
применить цифровой НЧ-фильтр с верхней граничной частотой 14 Гц (приведённаячастота равна 0.14) и с шириной переходной зоны, не превышающей 4 Гц (вединицах приведенных частот - 0.04). Пользуясь выражением (16.3), находим,
что фильтр должен иметь около 101 весового коэффициента. Для повышения
круrизны спада АЧХ в переходной зоне лучше выбрать фильтр Хэмминга. Программа 16.1 реализует такой фильтр. АЧХ фильтра (Рис. 16.5) получена по импульсной
характеристике с помощью преобразования Фурье.
Рассмотрим ещё один пример. Требуется рассчитать полосовой фильтр для выделения
тонШlьного сигнШlа, который возникает в процессе набора номера при
нажатии кнопок на телефонном аппарате . Предположим , что дискретизация производится с частотой 10 кГц и что требуется выделить полосу шириной 80 Гц с
центром на частоте 2 кГц. Измеряя частоту в долях частоты дискретизации, можно
сказать, что необходим цифровой фильтр, подавляющий все частоты ниже
0.196 и все частоты выше 0.204 (эти значения соответствуют 1960 и 2040 Гц). Чтобы
ширина переходных зон на границах полосы пропускания не превышала 50 Гц (относительная ширина 0.005), порядок фильтра должен быть равен 801. В данном
случае предпочтение следует отдать фильтру Блэкмана. Расчёт весовых коэффициентов
выполняется в Программе 16.2, а частотная характеристика полученногофильтра рассмотрена на Рис. 16.6. Процедура расчёта фильтра включает
несколько этапов. Сначала рассчитываются два НЧ-фильтра с частотами среза
0.196 и 0.204 соответственно . Для второго фильтра выполняется инверсия АЧХ, в
результате чего он превращается в ВЧ-фильтр (см. Рис. 14.6). Затем весовые коэффициенты
двух фильтров попарно складываются, образуя режекторный
фильтр (Рис. 14.8). Теперь остаётся лишь выполнить инверсию АЧХ, чтобы фильтр
стал полосовым.
Достижение сверхвысокой точности
Оконные фильтры позволяют достигать невероятной точности. Допустим, вы
хотите выделить сигнал напряжением 1 мВ, принятый по сети переменного тока
120 В. Значит, необходим фильтр с уровнем затухания в зоне подавления по меньшей
мере -120 дБ (одна миллионная в линейном масштабе). Уже было показано
выше, что оконная функция Блэкмана позволяет достичь лишь -74 дБ (приблизительноодна пятитысячная) . Но оказывается, что затухание в зоне подавления
легко увеличить, выполнив процедуру фильтрации ещё раз. При этом коэффициент
подавления станет равным -148 дБ (это одна тридцатимиллионная!). Можно
объединить два использованных фильтра в один , выполнив свёртку их импульсных
характеристик. То есть свёртка импульсной характеристики с самой собой
позволяет значительно увеличить подавление сигнала в зоне непрозрачности. Но
за увеличение подавления придётся заплатить возрастанием числа весовых коэффициентов
(удлинением импульсной характеристики) и уменьшением крутизны
спада АЧХ в переходной зоне. На Рис. 16.7а показана ЛАЧХ НЧ-фильтра 201-го
порядка, полученного в результате выполнения свёртки импульсных характеристик
двух оконных фильтров Блэкмана 101-го порядка. Качество полученногофильтра просто удивительное! Чтобы достичь очень большого затухания (болеесильного, чем -100 дБ), придётся проводить вычисления с двойной точностью.
При обычной точности представления данных обработка сигналов , лежащих в
полосе пропускания, приводит к возникновению шума округления, который вомногих случаях «проникает» в зону подавления фильтра, достигая уровня -100 ... -
120 дБ и более.
Увеличение числа весовых коэффициентов до 32001 позволяет получить
фильтр с невероятно узкой переходной зоной (Рис. 16.76). Её ширина составляет
всего лишь 0.000125 часть от частоты дискретизации. Насколько хорош данный
фильтр? Попытайтесь построить аналоговый фильтр, пропускающий все частоты
в диапазоне 0".1 ООО Гц с максимальной ошибкой по амплитуде 0.02% и подавляющий
все частоты, превышающие 1001 Гц, до уровня 0.02% от их первоначальной
амплитуды. С помощью аналоговых фильтров достичь таких характеристик просто
невозможно! Но ещё больше поражает то, что оба фильтра на Рис. 16. 7 используют
вычисления с обычной точностью, а переход к двойной точности позволяет
повысить качество фильтрации в миллион раз.
Наиболее серьёзный недостаток оконных фильтров связан с высокой вычислительной
сложностью их реализации. На обработку каждого очередного отсчёта
входного сигнала может потребоваться недопустимо большой объём вычислений, т. к. в основе оконных фильтров лежит трудоёмкая операция свёртки. Значительно
сократить вычислительные затраты позволяет использование алгоритма быстройсвёртки (Глава 18). Альтернативу оконным фильтрам представляют рекурсивныефильтры (Глава 19), также обеспечивающие высокое качество частотнойселекции сигналов.
Являются ли оконные фильтры оптимальными фильтрами частотной селекции?
Нет, потому что многие более сложные алгоритмы позволяют получать
фильтры более высокого качества. Но прежде чем перейти к изучению таких алгоритмов,
основанных на сложных математических преобразованиях, постарайтесьпонять, какого именно качества вам требуется достичь. С помощью оконныхфильтров можно добиться практически любого , сколь угодно высокого, качества
фильтрации. Все сложные алгоритмы расчёта и реализации фильтров частотной
селекции созданы лишь для того, чтобы хоть немного уменьшить количество весовых
коэффициентов при заданном качестве фильтрации. Такое уменьшение
порядка фильтра приводит к уменьшению вычислительной сложности. Однако
потребуется разобраться в сложных математических выражениях, чтобы таким
образом хоть немного повысить эффективность вашей системы .
12. Рекурсивные фильтры.Расчет параметров рекурсивных фильтров.
Рекурсивные фильтры, в отличие от нерекурсивных, не используют операцию
свёртки временных последовательностей, требующую значительных вычислительных
затрат. Поэтому их применение повышает вычислительную эффек -
тивность алгоритмов фильтрации, но при этом могут возникать значительные
ограничения по реально достижимой точности воспроизведения желаемых частотных
характеристик. Рекурсивные фильтры относятся к классу цепей с бесконечнойимпульсной характеристикой (БИХ). Импульсная характеристика
БИХ-фильтров складывается из множества синусоид, амплитуда которых убывает
по экспоненциальному закону. Форма импульсной характеристики является
основным отличием рекурсивных фильтров от фильтров, построенных на основе
свёртки, которые образуют, в свою очередь, класс цепей с конечной импульсной
характеристикой (КИХ). Данная глава представляет собой введение в теорию
рекурсивных фильтров. В ней также описана методика расчёта некоторых
простых фильтров этого семейства. Более сложным методам посвящены Главы
20, 26 и 33.
19.1. Рекурсивный метод
Предположим, вам необходимо выделить информационную составляющую,
содержащуюся в сигнале х[ ] . Для вас это очень важно, и вы обращаетесь к очень
крупному специалисту, профессору, доктору математики, чтобы он помог вам вобработке имеющихся данных. Задача профессора состоит в том, чтобы в результате
фильтрации получить из сигнала х[ ] сигнал у[ ] , в котором информация содержится
в форме, доступной для восприятия. Профессор приступает к последовательномувычислению отсчётов сигнала у[], руководствуясь каким-то одному
ему известным алгоритмом, который он нашёл где-то в глубинах своих чрезвычайно
обширных научных знаний . И вдруг на очередном этапе вычислений происходит
неприятное событие. Профессор начинает бессвязно бормотать что-то,
упоминая частные преобразования , аналитические сингулярности и других «чудовищ
» из математического «кошмара» . Совершенно ясно, что профессор «тронулся
умом». С тревогой вы наблюдаете за тем, как его, а вместе с ним и этот алгоритм
увозят люди в белых халатах.
В отчаянии просматривая записи профессора, пытаясь найти там используемыйим алгоритм, вы обнаруживаете, что он уже вычислил отсчёты у[О] ... у[27] и
собрался рассчитать у[28]. Обозначим через п номер отсчёта, вычисляемого на
текущей итерации (Рис. 19.1). Тогда если у[п] - 28-й отсчёт выходной последовательности,
то у[п- 1) - 27-й отсчёт, у[п-2) - 26-й отсчёт и т. д. Аналогично
х[п] - 28-й отсчёт входной последовательности, х[п-1 ] - 27-й и т. д. Чтобы ра- зобраться в алгоритме, попытаемся ответить на вопрос: какая информация бьmа
доступна профессору при вычислении отсчёта у[п] на последней выполняемой
им итерации?

превышает 12, что связано с проблемой устойчивости (на выходе фильтра могутвозникнуть неконтролируемый рост сигнала или свободные колебания). Примером
программной реализации рекурсивного фильтра является Проrрамма 19.1.
Главное достоинство рекурсивных филыров заключается в том, что при их реализации
удаётся избежать использования операции свёртки, требующей большого
количества арифметических операций. Для примера подадим на вход рекурсивного
фильтра дискретную дельта-функцию (единичный импульс). Реакцией
на такое воздействие будет импульсная характеристика фильтра, которая представляет
собой синусоидальные колебания с убывающей по экспоненциальномузакону амплитудой. Поскольку такая импульсная характеристика бесконечна повремени, рекурсивные фильтры называют фильтрами с бесконечной импульсной
характеристикой (БИХ). В действительности происходит свёртка входного сигнала
с бесконечной импульсной характеристикой при конечном числе весовых коэффициентов.
Взаимосвязь между импульсной характеристикой фильтра и его весовыми коэффициентами
определяется при помощи Z-преобразования, о котором пойдёт
речь в Главе 33. Z-преобразование используется для решения следующих задач:
определение частотной характеристики по весовым коэффициентам рекурсивногофильтра, объединение последовательных и параллельных звеньев в единыйфильтр, проектирование рекурсивных систем, повторяющих по своим свойствам
аналоговые фильтры, и т. д. к· сожалению, Z-преобразование требует специальныхзнаний из области высшей математики и оказывается для многих слишком
сложным. Данное преобразование создано для специалистов в области ЦОС и
цифровых систем.
Есть три способа, позволяющих найти коэффициенты рекурсивного фильтра
для тех, кто не владеет Z-преобразованием. Первый способ: в данной главе содержатся
уравнения для расчёта нескольких типов простейших рекурсивных фильтров.
Второй способ: в Главе 20 приводится компьютерная программа для расчёта
более сложных НЧ- и ВЧ-фильтров Чебышева. Третий способ: в Главе 26 рассмотрен
итеративный метод построения рекурсивных фильтров с произвольной формой
частотной характеристики.
13. Однополюсный рекурсивный фильтр.
Пример однополюсного НЧ-фильтра показан на Рис. 19.2. Этот рекурсивный
фильтр имеет всего два весовых коэффициента, принимающих значения а0 = 0.15
и Ь 1 = 0.85. Подадим ступенчатое входное воздействие. Как и следовало ожидать,
выходная реакция НЧ-фильтра плавно нарастает до некоторого установившегося
значения. Этот график, возможно, напомнил вам известный пример из электротехники.
Рекурсивный НЧ-фильтр оказывает на цифровой сигнал точно такое жедействие, какое оказывает обычный RС-фильтр на аналоговый сигнал. Достоинство рекурсивного метода состоит в том, что, меняя всего несколько
параметров, можно создавать самые разные импульсные характеристики.
Фильтр, характеристики которого приведены на Рис. 19.3, имеет три коэффициента:
а0 = 0.93, а 1 = -0.93 и Ь 1 = 0.86. Подавая разнообразные тестовые воздействия,
можно показать, что он полностью повторяет свойства аналогового
ВЧ-фильтра, построенного на основе RС-цепи.
Разумеется, такие фильтры вам очень хотелось бы иметь в наборе доступныхинструментов ЦОС. Их можно использовать при обработке цифровых сигналов
так же, как RС-цепи используются в аналоговой обработке. Решаемые задачи точно
те же : устранение постоянной составляющей, подавление высокочастотного

Характеристики таких фильтров определяются параметром х =О ... 1. Физический
смысл параметрах - относительное затухание на интервале между соседними отсчётами.
Например, у фильтра на Рис. 19.3 х = 0.86, вследствие чего каждый очередной
отсчёт импульсной характеристики равен предыдущему, умноженному на 0.86. Чем
больще х, тем медленнее спад. Если х больще единицы, фильтр оказывается неустойчивым.
В этом случае появление любого ненулевого отсчёта на входе фильтра приведёт
к переполнению (появлению слищком больщих значений) на выходе.
Параметр х может быть задан непосредственным образом, а также может быть
выражен через постоянную времени фильтра. Величина RxC имеет размерность
времени, и в простейщих RС-цепях она соответствует интервалу времени, черезкоторый отклонение амплитуды выходного сигнала от установивщегося значения
сокращается в ходе переходного процесса до 36.8% от первоначальной величины .Если d - постоянная времени, измеряемая числом отсчётов дискретного сигнала
, то имеет место следующее равенство:

Постоянная времени однополюсного фильтра. Взаимосвязь между относительным затуханием х
(за период дискретизации) и постоянной времени фильтра d.
Относительному затуханию х = 0.86 соответствует постоянная времени
d = 6.63 дискретных отсчётов (Рис. 19.3). Кроме того, между х и частотой среза,
определяемой на уровне -3 дБ, существует взаимосвязь:

Частота среза однополюсного фильтра. Взаимосвязь между относительным затуханием х
и частотой среза фильтра fc = 0 ... 0.5.
Из сказанного следует, что коэффициенты ai и bi могут быть выражены черезследующие три параметра: постоянную времени , частоту среза и непосредственно
через относительное затухание х.
Пример работы рекурсивных однополюсных фильтров иллюстрируется наРис. 19.4. Входной сигнал (а) представляет собой гладкую кривую, на которую на протяжении короткого интервала времени накладывается всплеск более высокой
частоты. С помощью НЧ- и ВЧ-фильтров можно разделить компоненты входного
сигнала (б), но всё же качество фильтрации оказывается низким, как и при использовании
аналоговых RС-цепей.
На Рис. 19.5 показаны АЧХ однополюсных рекурсивных фильтров. Чтобы получить
частотную характеристику рекурсивного фильтра, сначала находят его импульсную
характеристику как реакцию на единичное импульсное воздействие .Затем применяют БПФ, чтобы перейти от импульсной характеристики к частотной.
Теоретически импульсная характеристика имеет бесконечную длину, но вреальности через интервал, в 15 ... 20 раз превышающий постоянную времени, она
затухает ниже уровня шумов округления. Например, для d = 6.63 отсчёта в импульснойхарактеристике значащими остаются только около 128 отсчётов.
На Рис. 19.5 хорошо заметна важная особенность однополюсных рекурсивных
фильтров, заключающаяся в слабых возможностях разделения частотных диапазонов.
Эти фильтры отлично проявляют себя при обработке сигналов во временной
области, но оказываются недостаточно мощными в задачах частотной селекции.
Некоторого улучшения частотных характеристик позволяет достичь
использование последовательного (каскадного) соединения нескольких однополюсных
фильтров. Здесь возможны два способа. Во-первых, сигнал можно пропускать
через один и тот же фильтр несколько раз. Во- вторых, воспользовавшись
Z-преобразованием, можно найти весовыекоэффициенты цифрового рекурсив- ного фильтра, эквивалентного по своим свойствам последовательному соединению
нескольких звеньев. Оба метода хорошо работают и находят широкое применение.
На Рис. 19 .Sв показаны А ЧХ 4-каскадных рекурсивных НЧ-фильтров. Хотя
затухание в зоне подавления при переходе к каскадной форме построения значительно
увеличивается, переходная зона по-прежнему оставляет желать лучшего.
Если вам необходимо повысить качество в частотной области, ориентируйтесь наиспользование фильтров Чебышева, речь о которых пойдет в следующей главе.
Многокаскадный НЧ -фильтр сопоставим с фильтрами Блэкмана и Гаусса, являющимися
модификациями однородных КИХ-фШ1ьтров (Глава 15), но при этом
он требует существенно меньших вычислительных затрат. Для расчёта 4-каскадного
НЧ-фильтра можно воспользоваться следующими уравнениями:


14. ФЧХ рекурсивных фильтров.
С позиции воспроизводимой ФЧХ существует три типа фильтров: с нулевой
фазой, с линейной ФЧХ и с нелинейной ФЧХ (Рис. 19.7). Фильтр с нулевой фазой
имеет симметричную относительно нуля импульсную характеристику (а). Конкретная
форма импульсной характеристики не играет роли , главное , чтобы отсчёты
слева от оси ординат были зеркальным отражением отсчётов, расположенных
справа. При такой характеристике преобразование Фурье приводит к получению
отсчётов со строго нулевой фазой (б).
Недостатком фильтров с нулевой фазой является наличие отрицательных индексов,
которое означает физическую нереализуемость цепи. Устранить указанный
недостаток позволяет переход к фильтрам с линейной ФЧХ. Импульсная характеристика
линейно-фазового фильтра (г) имеет ту же форму, что и
характеристика фильтра с нулевой фазой (а), за исключением такого сдвига пооси абсцисс , который делает все индексы положительными. Сохраняется и симметрия
импульсной характеристики, но теперь уже ось симметрии смещена относительно
оси ординат. Этот сдвиг во временной области приводит к изменению
наклона ФЧХ (д), которая имеет форму прямой линии, что отражено в названии
фильтра: фильтр с линейной ФЧХ. Тангенс угла наклона ФЧХ прямо пропорционален
сдвигу импульной характеристики. Так как единственным следствием
сдвига импульсной характеристики является задержка выходной реакции фильтра,
то фильтр с линейной фазой во многих приложениях можно считать эквивалентным
фильтру с нулевой фазой.
Импульсная характеристика на (ж) не симметрична, поэтому ФЧХ такого
фильтра (з) отличается от линейной. Не пугайте линейность и нелинейность ФЧХ
с понятием «линейная система», введённым в Главе 5. Хотя в обоих случаях говорится
о линейности, это совершенно разные понятия.
Какая разница, линейная фаза или нет? Ответ очевиден из (в, е и и), на которых
показаны реакции фильтров на прямоугольный импульс. Реакция на прямо- угольный импульс представляет собой комбинацию двух переходных характеристик,
из которых первая формирует передний фронт импульса, а вторая -
перевёрнутая переходная характеристика - формирует его задний фронт. Как это
видно по графикам, при обработке фильтрами с нулевой фазой и с линейной
ФЧХ оба фронта получают одинаковые искажения, в то время как при нелинейнойФЧХ фронты импульса различаются. Во многих практических приложениях
подобная асимметрия недопустима. Например, при снятии осциллограммы подобное
различие может быть ошибочно приписано свойствам измеряемого сигнала.
Приведем ещё более интересный пример из области обработки изображений.
Представьте себе, что, включив телевизор, вы обнаруживаете, что у вашего
любимого актёра или актрисы левое ухо не похоже на правое.
Получить КИХ-фильтр с линейной ФЧХ не представляет труда. Это объясняется
тем, что отсчёты импульсной характеристики КИХ-фильтра (его весовые коэффициенты)
определяются непосредственно в процессе его расчёта, и для линейности
ФЧХ достаточно ввести требование симметрии импульсной
характеристики. Весовые коэффициенты БИХ-фильтров не совпадают с отсчётами
импульсной характеристики, которая оказывается несимметричной, что выражается
в свою очередь в нелинейности ФЧХ.
15. ФЧХ. Двунапрвленная фильтрация.
В аналоговой схемотехнике тоже приходится решать проблему нелинейности
ФЧХ. Представьте на своём рабочем столе электрическую схему с резисторами и
конденсаторами. Пока сигнал на входе равен нулю, выходной сигнал тоже сохраняет
нулевое значение. Если на вход подать короткий импульс, конденсаторы
мгновенно зарядятся и далее начнут разряжаться по экспоненциальному закону
через резисторы. Импульсная характеристика (наблюдаемый выходной сигнал)
представляет собой комбинацию этих спадающих с разными скоростями экспонент.
Импульсная характеристика никак не может оказаться симметричной, поскольку
до поступления импульса на вход схемы на её выходе сигнал равнялся нулю,
а экспоненты убывают до бесконечности, так и не достигая нуля.
Разработчики аналоговых фильтров решают эту проблему при помощи фильтра
Бесселя (Глава 3). При построении фильтра Бесселя ставите~ задача сделать ФЧХ
как можно более линейной. Но такие фильтры всё равно сильно уступают по качеству
цифровым фильтрам, для которых обеспечение линейной ФЧХ - элементарная
задача.
К счастью, есть очень простой способ построения рекурсивного фильтра с нулевой
фазой (Рис. 19.8). Пусть, для примера, на вход однополюсного НЧ-фильтра
поступает прямоугольный импульс (а). Так как ФЧХ фильтра является нелинейной,
передний и задний фронты импульса оказываются несимметричными после
выполнения фильтрации: точнее говоря , задний фронт по форме совпадает с перевёрнутым
передним фронтом импульса (б). Данный фильтр вычисляет отсчёты
выходного сигнала, начиная с нулевого и заканчивая 150-м, аналогично тому, как
это происходило и в других рассмотренных ранее при мерах.
Теперь предположим, что вместо продвижения от нулевого отсчёта к 150-му,
фильтр производит обработку с,игнала в обратном направлении: от 150-го отсчёта
к нулевому. Другими словами, каждый отсчёт выходного сигнала выражается черезотсчёты входного и выходного сигналов, расположенные на временной оси
справа от него. Тогда уравнение рекурсивного фильтра (19.1) приобретает новуюформу:

Само по себе изменение направления фильтрации не приносит никакой
пользы: передний и задний фронты импульса по-прежнему отличаются друг отдруга. Но когда фильтрация производится в обоих направлениях, происходит чудо.
Импульс, изображённый на (z), получен при выполнении фильтрации сначала
в прямом, а затем в обратном направлении. Ну, как вам такой фокус?! Получается
рекурсивный фильтр с нулевой фазой. Рассмотренный метод двунаправленнойфильтрации позволяет получить фильтр с нулевой фазой практически из любого
рекурсивного фильтра. Единственной «платой» за улучшение ФЧХ является усложнение
кода программы и увеличение вдвое времени её выполнения.
Как определить импульсную и частотную характеристики полученного фильтра
с двунаправленной фильтрацией? При изменении направления фильтрации
АЧХ фильтра остаётся прежней, а все отсчёты ФЧХ меняют свой знак на противоположный.
В результате объединения двух таких фильтров в один все отсчёты
АЧХ возводятся в квадрат, а отсчёты ФЧХ обращаются в ноль. Во временной области
объединение фильтров выражается в свёртке исходной импульсной харак -
теристики с её отражением в направлении «слева направо». Для примера возьмем
однополюсный НЧ-фильтр с экспоненциально спадающей ФЧХ. Чтобы определить
импульсную характеристику соответствующего двунаправленного фильтра,
нужно выполнить свёртку экспоненты, которая спадает «слева направо», с экспонентой,
имеющей такую же скорость спада, но в направлении «справа налево».
После выполнения нескольких математических преобразований выясняется, что
импульсная характеристика результирующего фильтра имеет вид импульса, образованного
двумя экспонентами: сначала возрастающей, а затем убывающей. При
этом по скорости спада обе экспоненты повторяют исходную импульсную характеристику.
Во многих практических приложениях данные обрабатываются отдельнымиблоками. В таких случаях двунаправленная фильтрация может быть использована
совместно с методом секционирования, о котором говорилось в предыдущей главе.
Если вас спросят, какова в этом случае длина импульсной характеристики, не говорите,
что она бесконечна, потому что это означало бы , что каждый сегмент дополняется
бесконечным числом нулевых отсчётов. Помните, что импульсную характеристику
можно ограничить интервалом, за пределами которого она
становится ниже уровня шумов округления, т. е. периодом, в 15 ... 20 раз превышающим
постоянную времени. Для согласования длины сегмента и длины импульсной
характеристики двунаправленного фильтра справа и слева добавляется необходимоеколичество нулевых отсчётов.
16. Фильтры Чебышева и Батерворда их свойства и применение.
Фильтры Чебышева предназначены для частотной селекции сигналов. Несмотря
на то что они уступают по некоторым показателям фильтрам , полученным
оконными методами, для многих практических приложений такие фильтры оказываются
предпочтительнее. Самым главным достоинством чебышевских фильтров
является значительное уменьшение количества вычислений . По этому параметру
они более чем на порядок превосходят оконные фильтры. Это связано срекурсивной структурой фильтров Чебышева, обеспечивающей более высокоебыстродействие по сравнению со свёрткой. В основе расчёта фильтров Чебышева
лежит математический аппарат, получивший название Z-преобразования, о котором
пойдет речь в Главе 33. В этой главе мы постараемся рассказать о практике
использования фильтров Чебышева, обходя по мере возможности тернии высшей
математики.
20.1. Частотные характеристики фильтров
Чебышева и Баттерворта
При расчёте фильтров Чебышева за счёт допущения неравномерности амплитудно-
частотной характеристики (АЧХ) удаётся увеличить крутизну спада на границе
полосы пропускания. Такой подход характерен как для аналоговых, так и для
цифровых фильтров Чебышева. Аналоговые чебышевские фильтры применяются,
например, в аналого-цифровых и цифро-аналоговых преобразователях, речь о
которых шла в Главе 3. Название этих фильтров происходит от полиномов Чебышева,
положенных в основу их математического описания. Данные полиномы были
получены русским математиком Пафнутием Чебышевым (1821-1894) 1>.
На Рис. 20.1 показаны характеристики низкочастотных фильтров Чебышева снеравномерностью в полосе пропускания: О, 0.5 и 20%. Увеличение неравномерности
АЧХ в полосе пропускания позволяет повысить крутизну её спада в переходной
зоне . Расчёт фильтра Чебышева связан с нахождением некоторого компромисса
между этими двумя параметрами. Фильтр с нулевым уровнем
неравномерности, т. е. с максимально гладкой АЧХ, называют фильтром Баттерворта
(по имени английского инженера С. Баттерворта, впервые описавшего егохарактеристики в 1930 году). Как правило, используют цифровые фильтры суровнем неравномерности АЧХ 0.5%, которые по точности и качеству работы наилучшим
образом соответствуют компонентам аналоговой электронной техники. В этой главе рассматриваются чебышевские фильтры первого типа, для которых
допускается наличие колебаний АЧХ только в полосе пропускания. Заметим,
что фильтры второго типа имеют колебания только в зоне подавления. Мы не будем
подробнее останавливаться на фильтрах второго типа, так как они редко используются
на практике . Существует ещё один тип фильтров - эллиптические. Для них
характерно наличие колебаний и в полосе пропускания, и в зоне подавления. Описание
этого типа фильтров также остаётся за рамками книги, но следует помнить,
что очень часто профессиональные разработчики выбирают именно эти фильтры
(как аналоговые, так и цифровые). Если вам требуются эллиптические фильтры,
вы можете найти необходимое для их расчёта программное обеспечение.
20.2. Расчёт фильтра
Расчёт фильтра Чебышева предполагает выбор четырёх параметров: 1) тип
фильтра (высокочастотный или низкочастотный); 2) частота среза; 3) уровень неравномерности
АЧХ в полосе пропускания; 4) количество полюсов. Что такое полюсы?
Приведём далее два варианта ответа на этот вопрос. Если будет непонятен
первый - обратитесь ко второму.
Ответ 1. Преобразование Лапласа и Z-преобразование позволяют описать импульснуюхарактеристику фильтра с помощью набора синусоид и убывающих экспонент.
Для этого требуется предварительно представить частотную характеристику
в форме отношения двух многочленов. Корни числителя передаточнойфункции называют нулями, а корни знаменателя - полюсами. Полюсы и нули могут
выражаться комплексными числами, поэтому говорят, что они «располагаются
» на комплексной плоскости. Чем больше нулей и полюсов, тем выше качество
системы. Расчёт рекурсивных фильтров начинают с размещения полюсов и нулей,
а уже затем находят подходящие весовые коэффициенты . Например , полюсы
фильтра Баттерворта лежат в комплексной плоскости на окружности, тогда
как у фильтра Чебышева они расположены по эллипсу. Подробнее об этом говорится
в Главах 32 и 33.
Ответ 2. Каждый полюс - это этакий «сундучок» с магической силой. Чем
больше полюсов у фильтра, тем лучше он работает. Но если серьёзно, то вам просто следует усвоить, что можно научиться эффективно
использовать фильтры, не углубляясь в «занудную» математику. Расчёт
фильтров - это отдельная задача, требующая специальных знаний . Большинство
же инженеров и программистов представляют себе фильтры в повседневной своей
работе скорее на уровне ответа 2, чем ответа 1.
На Рис. 20.2 показаны частотные характеристики фильтров Чебышева с уровнем
неравномерности АЧХ - 0.5%. Использованный метод расчёта требует чётного
числа полюсов. Граница полосы пропускания определяется точкой пересечения
амплитудно-частотной характеристикой уровня 0.707 (-3 дБ). Крутизна
спада АЧХ фильтров, частота среза которых близка к О или 0.5, оказывается выше,
чем у фильтров с частотой среза ближе к середине частотного диапазона. Например,
двухполюсный фильтр, у которого fc = 0.05, оказывается близким по крутизне
спада к четырёхполюсному фильтру с частотой среза fc = 0.25. Отсюда появляется
замечательная возможность уменьшения числа полюсов у фильтров с очень
узкой или, наоборот, с очень широкой (близкой к 0.5) полосой пропускания. Но
об этом чуть позже .Существуют два способа нахождения коэффициентов обратной связи без использования
Z-преобразования. Первый способ для «чайников» - можно воспользоваться
справочной таблицей. В Табл. 20.1и20.2 приводятся коэффициенты обратной связи для низкочастотных и высокочастотных фильтров с неравномерностью
в полосе пропускания на уровне 0.5%. Если вам нужно быстро спроектировать
более или менее нормальный фильтр, достаточно просто скопировать эти
коэффициенты в свою программу.
Однако использование табличных значений приводит к двум серьёзным проблемам.
Первая связана с ограничением в выборе параметров: в таблицах представленылишь 12 значений граничной частоты полосы пропускания; фильтры
имеют не более 6 полюсов; совершенно отсутствует возможность выбора уровня
неравномерности АЧХ в полосе пропускания. Не имея возможности выбора этих
параметров из непрерывного ряда значений , нельзя получить оптимальный
фильтр, подходящий вам наилучшим образом. Вторая проблема состоит в том,
что табличные коэффициенты придётся вводить в программу вручную, что оказывается
весьма трудоёмким и не даёт возможности экспериментировать, выбирая
то один, то другой фильтр.
Чтобы облегчить свой труд, попробуйте вместо ввода табличных данных воспользоваться
программой расчёта коэффициентов. Примером такой программы
может служить Программа 20.1. Достоинство этой программы состоит в относительной
её простоте: необходимо только ввести упомянутые нами ранее четыре
параметра фильтра, и программа сама запишет коэффициенты ai и bi в массивы
А[ ] и В[ ] . Но есть и недостаток: программа должна обращаться к подпрограмме
(Программа 20.2). После первого беглого просмотра эта подпрограмма может
привести вас в ужас. Но не отчаивайтесь: она совсем не такая уж страшная, как
это кажется на первый взгляд! В ней всего лишь один оператор условного перехода
в строке 1120. Всё остальное - это последовательно выполняемые сложные
математические операции. Подпрограмма использует шесть входных, пять выходных
и пятнадцать временных переменных. В Табл. 20.4 имеется два набора
тестовых данных, необходимых для отладки подпрограммы. Подробнее работа
программы рассмотрена в Главе 31.

17. Переходные характеристики, перерегулирование и устойчивость фильтров Чебышева и Батерворда.
Величина перерегулирования для фильтров Баттерворта и Чебышева лежит вдиапазоне 5".30% и возрастает по мере увеличения количества полюсов. Рис. 20.Запозволяет сравнить переходные характеристики двух фильтров Чебышева, На (б)
отражена характерная черта цифровых фильтров , которая не проявляется у аналоговых:
величина перерегулирования переходной характеристики зависит (хоть и внебольшой степени) от частоты среза фильтра. Следовательно, оптимизация параметров
чебышевских фильтров в частотной области без учёта их временных характеристик
может привести к недопустимому увеличению перерегулирования и
колебаний переходного процесса.
20.4. Устойчивость
Область применения цифровых фильтров, основанных на использовании
операции свёртки, ограничивается в большинстве случаев временем , требуемым
на обработку сигнала. Можно достичь воспроизведения практически любых желаемых
характеристик, но при условии, что вы можете достаточно долго ждать результата
обработки. Для рекурсивных фильтров всё обстоит иначе. Обработка
сигнала происходит почти молниеносно, но качество работы ограничено. В качестве
примера рассмотрим низкочастотный фильтр с верхней граничной частотой,
равной 0.01, характеризующийся наличием шести полюсов и уровнем неравномерности
АЧХ 0.5%. Его коэффициенты можно найти по данным Табл. 20.1:

Посмотрите внимательно на эти коэффициенты . Значения bi по абсолютной
величине близки к 10. С помощью простейших подсчётов можно найти, что вносимыйкаждым из них шум округления составляет около одной десятимиллионной
доли от абсолютной величины, т. е. 10-6. А теперь обратим внимание на коэффициенты
ai, абсолютная величина которых близка к 10- 9. Тут явно кроется какая-то
ошибка. Полезный сигнал на выходе фильтра с учётом коэффициентов ai оказывается
в 1000 раз меньше шума, который вносят ранее полученные отсчёты выходного
сигнала, умноженные на коэффициенты bi. Такой фильтр просто не может
работать! На практике максимальное число полюсов слабо зависит от уровня неравномерности АЧХ и типа фильтра (низкочастотный или высокочастотный).
В Табл. 20.3 даны приблизительные оценки максимального количества полюсов
для случая вычислений с обычной точностью.
Таблица 20.3. Максимальное число полюсов при работе с обычной точностью

Превышение этих максимальных значений приводит к тому, что качество
фильтра начинает ухудшаться. Перерегулирование возрастает, затухание в зоне
подавления снижается, а неравномерность АЧХ становится недопустимо большой.
Если продолжать увеличивать количество полюсов фильтра при неточномпредставлении его коэффициентов, то на выходе могут возникнуть свободные
колебания, сохраняющиеся до тех пор, пока в фильтре происходят переполнения.
Существует два способа увеличения максимального числа полюсов. Первый
способ заключается в применении вычислений с двойной точностью. В этом случае
потребуется также выбор двойной точности при вычислении весовых коэффициентов
(и двойной точности для записи числа тт).
Второй способ, которым фактически пользуются специалисты, состоит в разбиении
фильтра на несколько звеньев. Например, фильтр, имеющий шесть полюсов,
можно представить в виде последовательного соединения трёх фильтров,
каждый из которых имеет два полюса. Программа 20.1 объединяет (для упрощения)
весовые коэффициенты этих трёх фильтров в один набор, соответствующий
результирующему фильтру. Следует помнить, что фильтр, представленный в виде
совокупности отдельных простых звеньев, значительно более устойчив. Найти
значения весовых коэффициентов ai и bi для каждого звена позволяет та же
Проrрамма 20.1. Отдельно для каждого звена вызывается Программа 20.2. Для
фильтра с шестью полюсами подпрограмму (Программа 20.2) необходимо вызывать
трижды. После своего завершения подпрограмма возвращает пять параметров:
АО, Al, А2, В 1 и В2 . Это и есть весовые коэффициенты одного из двухполюсных
фильтров, входящих в состав результирующеrо многокаскадного фильтра.
Приведенная программа вычисляет коэффициенты ai и bi для рекурсивныхфильтров Чебышева. Четыре параметра вводятся в строках 270 ... 300. Предполагается,
что частота среза FC выражается в долях частоты дискретизации и принимает
значения 0 ... 0.5. Переменная LH принимает два значения: единица - для высокочастотного
фильтра и нуль - для низкочастотного фильтра. Переменная PR
выражает уровень неравномерности АЧХ фильтра в процентах и ограничена значениями
0 ... 29. Количество полюсов задается переменной NP, которая может
принимать чётные значения в диапазоне 2 ... 20. По завершении выполнения программы
значения коэффициентов ai и bi размещаются в массивах А[ ] и В[ ] (аО =
= А[О], al = A[l] и т. д.). Программа 20.2 должна быть вызвана из строки 340 главной
программы. Подпрограмма (Программа 20.2) использует шесть входных и
пять выходных переменных. В Табл. 20.4 содержатся два набора данных для от-
20.4. Устойчивость • 391
ладки программы. Функции SIN и COS работают с радианами, а не с градусами.
Функция LOG - натуральный логарифм (по основанию е). Все переменные представлены
в формате с плавающей точкой (включая константу п) с двойной точностью,
что позволяет увеличить число полюсов фильтра. Данные Табл. 20.1 и 20.2
получены с помощью приведенной программы и могут быть использованы для еётестирования. Математическое описание программы можно найти в Главе 33.

18. Сравнительный анализ фильтров.
Как при столь широком разнообразии фильтров выбрать из них наиболее подходящий?
Ответить на этот вопрос поможет данная глава, в которой мы устроим
для фильтров «спортивное состязание». Для участия в турнире выберем лучшихпредставителей в каждой группе. В первом раунде будут сражаться цифровой и
аналоговый фильтры, чтобы выяснить, какая из двух технологий лучше. Во втором
раунде за звание сильнейшего в частотной области будут бороться оконный
фильтр и фильтр Чебышева. И наконец, в заключительной схватке столкнутся
временные фильтры: однородный и однополюсный. Однако довольно слов! Начнём
турнир!
21.1. Первый раунд:
аналоговый фильтр против цифровогоВ большинстве случаев сигналы, используемые в цифровой обработке, поступают
с аналоговых схем. Что эффективнее: использовать аналоговый фильтр додискретизации сигнала или цифровой фильтр после неё? Итак, выпускаем на ринг
по одному лидеру из этих групп.
Пусп~ наша задача заключается в построении НЧ-фильтра с частотой среза
1 кГц. Со стороны аналоговых фильтров на «бой» выходит шестиполюсный
фильтр Чебышева с неравномерностью в полосе пропускания 0.5 дБ (6%). Для такого
фильтра требуется 3 операционных усилителя, 12 резисторов и 6 конденсаторов
(см. Главу 3). В другом углу ринга разминается и вот уже готов к «бою» оконныйфильтр с частотой дискретизации 10 кГц, т. е. частотой среза в приведенных
единицах, равной 0.1. Порядок цифрового фильтра должен быть равен 129, что
обеспечит одинаковую крутизну спада между уровнями 0.9 и 0.1 для аналогового
и цифрового фильтров. Все должно быть справедливо: оба соперника поставлены
в равные условия. АЧХ, ЛАЧХ и переходные характеристики фильтров показаны
на Рис. 21.1.
Итак, «бой» начат. Неравномерность в полосе пропускания аналогового
фильтра достигает 6% (а), в то время как у цифрового фильтра визуально она
практически незаметна, а в действительности не превышает 0.02% (6). Сторонники
аналоговых фильтров могут оспорить такое неравенство и потребовать сравнения
фильтров с одинаковыми уровнями неравномерности. Подобное заявление
является совершенно необоснованным. Неравномерность АХЧ аналоговыхфильтров ограничена точностью параметров выбранных резисторов и конденсаторов.
Даже при использовании фильтра Баттерворта, А ЧХ которого теоретически
не содержит колебаний, в реально действующей аналоговой схеме колебания могут достигать порядка 1 %. Что касается цифровых фильтров, то для них гладкость
АЧХ ограничена главным образом ошибками округления, поэтому они в сотни
раз превосходят аналоговые фильтры. Итак, один-ноль, либо счёт 1:0 в пользу
цифрового фильтра.
Далее рассмотрим частотную характеристику в логарифмическом масштабе
(в и г). Цифровой фильтр снова одерживает убедительную победу: по спаду АХЧ и
по затуханию в зоне подавления. Даже улучшая качество аналогового фильтра путём
введения дополнительных каскадов, нам всё равно не достичь сравнимых сцифровым фильтром характеристик. Пусть, к примеру, требуется улучшить два
вышеупомянуть1х параметра в 100 раз. В случае оконного фильтра это достигается
с помощью простых преобразований, а для аналоговой схемы оказывается фактически
невозможно. Ещё два балла в пользу цифрового фильтра.
Переходные характеристики показаны на (д и е). У цифрового звена наблюдается
симметричный переходной процесс, т. е. фильтр имеет линейную ФЧХ. Переходная
характеристика аналогового фильтра явно несимметрична, т. е. ФЧХ далека
от линейной. Перерегулирование аналогового фильтра составляет 20%, но
колебания возникают только после подъёма переходной характеристики. У цифрового
фильтра колебания достигают примерно 10%, но наблюдаются как передподъемом, так и после него. На этот раз ни одному из фильтров не удалось превзойти
соперника, и счёт остаётся прежним.
Несмотря на столь явную победу цифрового фильтра, во множестве приложений
следует и даже необходимо использовать аналоговые фильтры. Это связано
не с самой работой фильтра (т. е. с тем, что у него на входе и на выходе), а с преимуществами
общего характера, которые аналоговые схемы имеют перед цифровыми.
Первое преимущество - скорость: цифровые фильтры медленнее аналоговых.
Например, персональный компьютер способен при использовании быстройсвёртки обрабатывать около 1 О ООО отсчётов в секунду, тогда как даже простой
операционный усилитель может работать на частотах 100 ... 1000 кГц, т. е. надва-три порядка быстрее цифровой системы!
Второе неотъемлемое преимущество, обусловленное природой аналоговыхфильтров, - это динамический диапазон. Здесь различают два показателя: амплитудныйи частотный динамические диапазоны. Амплитудный динамический диапазон
- это отношение максимального уровня сигнала, который способна обработать
система, к уровню собственного шума. Если разрядность АЦП составляет
12 бит, то уровень насыщения равен 4095, а среднеквадратическое отклонение
шума квантования не превышает 0.29 цены младшего бита, следовательно, динамическийдиапазон приблизительно равен 14000. Для сравнения: напряжение насыщения
стандартных операционных усилителей достигает 20 В, а уровень собственного
шума - около 2 мкВ, что позволяет реализовать систему сдинамическим диапазоном , равным 10 миллионам . Опять же простой операционный
усилитель явно превосходит цифровую систему.
Теперь перейдем ко второму показателю, которым является частотный динамический
диапазон. На основе операционного усилителя довольно просто создать
схему, позволяющую обрабатывать одновременно частоты 0.01 ... 100 кГц (семь декад).
При попытке применить цифровую обработку система просто оказывается
«заваленной» входными данными: при частоте дискретизации 200 кГц один период
сигнала частотой 0.01 Гц простирается на 20 миллионов отсчётов. Возможно, вы уже заметили, что частотная характеристика цифровых фильтров почти всегда
строится на линейной частотной шкале, в то время как для аналоговых обычно
применяют логарифмическую. Причина в том, что линейная шкала больше подходит
для отображения замечательных фильтрующих свойств цифровых фильтров,
а логарифмическая позволяет показать широкий динамический диапазон
аналоговых схем.
21.2. Второй раунд:
оконный фильтр против фильтра
Чебышева
И оконные фШ1ьmры, и фильтры Чебышева предназначены для частотной селекции.
Разница в том, что оконные фильтры относятся к классу КИХ-фильтров и
используют операцию свёртки, а фильтры Чебышева относятся к классу
БИХ-фильтров и имеют рекурсивную структуру. Какой же из фильтров окажется
лучшим в частотной области? Начнём поединок!
Претендентом на победу со стороны рекурсивных фильтров будет 6-полюсный
НЧ-фильтр Чебышева с неравномерностью 0.5%. Сопоставимость фильтров
осложнена тем, что частотная характеристика фильтра Чебышева зависит от верхнейграничной частоты. Пусть для определённости частота среза равна 0.2, а порядок
оконного фильтра равен 51. При таких условиях оба фильтра имеют одинаковуюскорость спада АЧХ между уровнями 0.9 и 0.1 (Рис. 21.2а). Посмотрим, какой из фильтров окажется сильнее в этой «схватке» . Уровень
колебаний АЧХ в полосе пропускания фильтра Чебышева составляет 0.5%; у
оконного фильтра колебания отсутствуют. Однако при необходимости можно задать
нулевой уровень неравномерности и для фильтра Чебышева, поэтому оба
фильтра оказываются в равном положении. Зато по уровню затухания в зоне по-
396 • Глава 21. Сравнительный анализ фильтров
давления побеждает оконный фильтр, что хорошо видно по Рис. 21.2б. Счёт
«ОДИН-НОЛЬ» в пользу оконного фильтра.
На Рис. 21.3 сравниваются переходные характеристики фильтров. Как и следовало
ожидать, для фильтров частотной селекции временные характеристики
оказались очень невысокого качества. Рекурсивный фильтр имеет нелинейную фазу,
но это может быть легко исправлено применением двунаправленной фильтрации.
Объявляем ничью: на этот раз ни один из фильтров не имеет явных преимуществ.
До настоящего момента мы не обнаружили никакого существенного различия
в работе фильтров, т. е. в приложениях со средними требованиями оба фильтра
работают одинаково хорошо. Заметное преимущество проявляется только в двух
крайних случаях: при достижении максимальной разрешающей способности
фильтра по частоте и вычислительной эффективности. Оконный фильтр обеспечивает
наивысшее разрешение (можно сказать, что он более «мощный»), а
фильтр Чебышева является в свою очередь более быстрым и «проворным». Представьте,
что возникла по-настоящему серьёзная проблема: нужно выделить сигнал
напряжением 100 мВ с частотой 61 Гц, распространяющийся по сети электропитания
120 В/60 Гц. На Рис. 21.4 сравниваются частотные характеристики двух
рассмотренных фильтров, рассчитанных с целью достижения наивысшего разрешения
по частоте. Фильтр Чебышева имеет 6 полюсов и уровень неравномерности
0.5%. Такое число полюсов является максимально возможным при частоте
среза 0.05 и одинарной точности вычислений. Оконный фильтр 1001-го порядка
получен в результате свёртки импульсной характеристики фильтра 501-го порядка
с самой собой. В Главе 16 говорилось, что данное преобразование повышает
уровень затухания в зоне подавления оконного фильтра.
Какой же из фильтров победит при необходимости получить максимальноеразрешение по частоте? Оконный фильтр отправляет фильтр Чебышева в нокаут!
Любые попытки улучшить рекурсивный фильтр (увеличение числа полюсов, введениедополнительных каскадов, переход к двойной точности и т. д.) не позволяют
достичь характеристик, близких к характеристикам КИХ-фильтра. Это осо- бенно впечатляет, если учесть, что оконный фильтр нанёс сейчас лишь свой
первый удар. Рекурсивные фильтры отличаются ограниченной точностью воспроизведения
желаемых частотных характеристик. Напротив, при использовании
оконных фильтров она может достичь невероятной степени точности. Сказанное
справедливо при одном условии: если у вас достаточно времени навычисления. Теперь пора рассмотреть второй критический параметр - вычислительнуюэффективность.
Сравнивать быстроту обработки отсчётов входного сигнала 6-полюсным рекурсивнымфильтром и оконным фильтром - всё равно что наблюдать состязание
Феррари и карта (Рис. 21.5). Известно, что крутизна спада АЧХ рекурсивного
фильтра повышается по мере приближения частоты среза либо к нулевой частоте ,либо к половине частоты дискретизации. В силу сохранения равенства по разрешающейспособности (чтобы соревнования между фильтрами проводились «честно» ) необходимо увеличивать порядок оконного фильтра. В результате вблизи частот О и 0.5 время обработки оконным фильтром увеличивается. Таким образом,
при сравнимых точностных характеристиках КИХ-фильтры работают на порядок
медленнее, чем БИХ-фильтры (карт - 25 км/ч; Феррари - 250 км/ч).
21.3. Третий раунд:
однородный фильтр противоднополюсного
В третьем «бою» сразятся фильтры, работающие во временной области. Первым
на ринг выходит однородный фильтр с усреднением по 9 отсчётам. Его соперник
- однополюсный рекурсивный фильтр, построенный по двунаправленной технологии.
Для получения сопоставимой частотной характеристики коэффициент
«забывания» однополюсного фильтрах = О. 70. Состязание между фильтрами начинается
с Рис. 21.6, где показаны АЧХ обоих фильтров. Характеристики явно не
впечатляют, что и понятно, так как фильтры предназначены вовсе не для частотнойселекции. Поэтому баллы не присуждаются ни одному из фильтров. Переходные характеристики фильтров изображены на Рис. 21.7. Переходный
процесс однородного фильтра (а) имеет вид отрезка прямой, что соответствует наиболее
быстрому переходу с одного уровня на другой. Переходная характеристика
рекурсивного фильтра (б) имеет гладкий переходный процесс, что в некоторых
случаях обеспечивает преимущество. По одному баллу получают оба фильтра.
Фильтры мало отличаются по качеству работы, поэтому выбор часто зависит
только от предпочтений разработчика. Тем не менее некоторое преимущество обнаруживается
при анализе двух характеристик - времени разработки фильтра и
времени обработки отсчётов входного сигнала. В первом случае требуется сократить
время разработки фильтра, пренебрегая увеличением вычислительных затрат.
Например, необходимо всего один раз воспользоваться фильтром, порядок
которого равен нескольким тысячам. Поскольку вся программа фильтрации вы- полняется всего за несколько секунд, бессмысленно тратить время на оптимизацию
алгоритма. Ясно, что предпочтение следует отдать вычислениям в формате сплавающей точкой. Остаётся выбрать из двух вариантов : либо однородный
фильтр, реализуемый на базе свёртки, либо однополюсный рекурсивный фильтр.
Победителем здесь будет рекурсивный фильтр. Его несколько проще программировать
и настраивать, а его вычислительные затраты намного меньше.
Во втором случае всё наоборот: необходимо минимизировать вычислительные
затраты, а времени на разработку достаточно. Например, фильтр может входить
в состав серийно выпускаемого изделия, где будет использован миллионы
раз. Для ускорения обработки, вероятно, нужно ~удет использовать целые числа .Выбор здесь производится между однородным фильтром на основе рекурсивногоалгоритма и однополюсным рекурсивным фильтром, использующим справочную
таблицу (таблицу соответствия) или целочисленную математику. Победителем
оказывается однородный фильтр. Он работает быстрее и не создаёт проблем, связанных
с целочисленной математикой, на стадиях расчёта и обработки.
24. Распознавание речи. Фреймы. Разбиение слов.Начнём с того, что наша речь — это последовательность звуков. Звук в свою очередь — это суперпозиция (наложение) звуковых колебаний (волн) различных частот. Волна же, как нам известно из физики, характеризуются двумя атрибутами — амплитудой и частотой. Для того, что бы сохранить звуковой сигнал на цифровом носителе, его необходимо разбить на множество промежутков и взять некоторое «усредненное» значение на каждом из них.Таким вот образом механические колебания превращаются в набор чисел, пригодный для обработки на современных ЭВМ.Отсюда следует, что задача распознавания речи сводится к «сопоставлению» множества численных значений (цифрового сигнала) и слов из некоторого словаря (русского языка, например).Давайте разберемся, как, собственно, это самое «сопоставление» может быть реализовано.
Входные данныеДопустим у нас есть некоторый файл/поток с аудиоданными. Прежде всего нам нужно понять, как он устроен и как его прочесть. Давайте рассмотрим самый простой вариант — WAV файл.Формат подразумевает наличие в файле двух блоков. Первый блок — это заголовка с информацией об аудиопотоке: битрейте, частоте, количестве каналов, длине файла и т.д. Второй блок состоит из «сырых» данных — того самого цифрового сигнала, набора значений амплитуд.Логика чтения данных в этом случае довольно проста. Считываем заголовок, проверяем некоторые ограничения (отсутствие сжатия, например), сохраняем данные в специально выделенный массив. Пример.
РаспознаваниеЧисто теоретически, теперь мы можем сравнить (поэлементно) имеющийся у нас образец с каким-нибудь другим, текст которого нам уже известен. То есть попробовать «распознать» речь… Но лучше этого не делать :)Наш подход должен быть устойчив (ну хотя бы чуть-чуть) к изменению тембра голоса (человека, произносящего слово), громкости и скорости произношения. Поэлементным сравнением двух аудиосигналов этого, естественно, добиться нельзя.Поэтому мы пойдем несколько иным путём.
ФреймыПервым делом разобьём наши данные по небольшим временным промежуткам — фреймам. Причём фреймы должны идти не строго друг за другом, а “внахлёст”. Т.е. конец одного фрейма должен пересекаться с началом другого.Фреймы являются более подходящей единицей анализа данных, чем конкретные значения сигнала, так как анализировать волны намного удобней на некотором промежутке, чем в конкретных точках. Расположение же фреймов “внахлёст” позволяет сгладить результаты анализа фреймов, превращая идею фреймов в некоторое “окно”, движущееся вдоль исходной функции (значений сигнала).Опытным путём установлено, что оптимальная длина фрейма должна соответствовать промежутку в 10мс, «нахлёст» — 50%. С учётом того, что средняя длина слова (по крайней мере в моих экспериментах) составляет 500мс — такой шаг даст нам примерно 500 / (10 * 0.5) = 100 фреймов на слово.
Разбиение словПервой задачей, которую приходится решать при распознавании речи, является разбиение этой самой речи на отдельные слова. Для простоты предположим, что в нашем случае речь содержит в себе некоторые паузы (промежутки тишины), которые можно считать “разделителями” слов.В таком случае нам нужно найти некоторое значение, порог — значения выше которого являются словом, ниже — тишиной. Вариантов тут может быть несколько:
задать константой (сработает, если исходный сигнал всегда генерируется при одних и тех же условиях, одним и тем же способом);
кластеризовать значения сигнала, явно выделив множество значений соответствующих тишине (сработает только если тишина занимает значительную часть исходного сигнала);
проанализировать энтропию;
Как вы уже догадались, речь сейчас пойдёт о последнем пункте :) Начнём с того, что энтропия — это мера беспорядка, “мера неопределённости какого-либо опыта” (с). В нашем случае энтропия означает то, как сильно “колеблется” наш сигнал в рамках заданного фрейма.Для того, что бы подсчитать энтропию конкретного фрейма выполним следующие действия:
предположим, что наш сигнал пронормирован и все его значения лежат в диапазоне [-1;1];
построим гистограмму (плотность распределения) значений сигнала фрейма:
рассчитаем энтропию, как ;Пример.И так, мы получили значение энтропии. Но это всего лишь ещё одна характеристика фрейма, и для того, что бы отделить звук от тишины, нам по прежнему нужно её с чем-то сравнивать. В некоторых статьях рекомендуют брать порог энтропии равным среднему между её максимальным и минимальным значениями (среди всех фреймов). Однако, в моём случае такой подход не дал сколь либо хороших результатов.К счастью, энтропия (в отличие от того же среднего квадрата значений) — величина относительно самостоятельная. Что позволило мне подобрать значение её порога в виде константы (0.1).Тем не менее проблемы на этом не заканчиваются :( Энтропия может проседать по середине слова (на гласных), а может внезапно вскакивать из-за небольшого шума. Для того, что бы бороться с первой проблемой, приходится вводить понятие “минимально расстояния между словами” и “склеивать” близ лежачие наборы фреймов, разделённые из-за проседания. Вторая проблема решается использованием “минимальной длины слова” и отсечением всех кандидатов, не прошедших отбор (и не использованных в первом пункте).Если же речь в принципе не является “членораздельной”, можно попробовать разбить исходный набор фреймов на определённым образом подготовленные подпоследовательности, каждая из которых будет подвергнута процедуре распознавания. Но это уже совсем другая история :)MFCCИ так, мы у нас есть набор фреймов, соответствующих определённому слову. Мы можем пойти по пути наименьшего сопротивления и в качестве численной характеристики фрейма использовать средний квадрат всех его значений (Root Mean Square). Однако, такая метрика несёт в себе крайне мало пригодной для дальнейшего анализа информации.Вот тут в игру и вступают Мел-частотные кепстральные коэффициенты (Mel-frequency cepstral coefficients). Согласно Википедии (которая, как известно, не врёт) MFCC — это своеобразное представление энергии спектра сигнала. Плюсы его использования заключаются в следующем:
Используется спектр сигнала (то есть разложение по базису ортогональных [ко]синусоидальных функций), что позволяет учитывать волновую “природу” сигнала при дальнейшем анализе;
Спектр проецируется на специальную mel-шкалу, позволяя выделить наиболее значимые для восприятия человеком частоты;
Количество вычисляемых коэффициентов может быть ограничено любым значением (например, 12), что позволяет “сжать” фрейм и, как следствие, количество обрабатываемой информации;
Давайте рассмотрим процесс вычисления MFCC коэффициентов для некоторого фрейма.Представим наш фрейм в виде вектора , где N — размер фрейма.
Разложение в ряд ФурьеПервым делом рассчитываем спектр сигнала с помощью дискретного преобразования Фурье (желательно его “быстрой” FFT реализацией).Так же к полученным значениям рекомендуется применить оконную функцию Хэмминга, что бы “сгладить” значения на границах фреймов.То есть результатом будет вектор следующего вида:Важно понимать, что после этого преобразования по оси Х мы имеем частоту (hz) сигнала, а по оси Y — магнитуду (как способ уйти от комплексных значений):
Расчёт mel-фильтровНачнём с того, что такое mel. Опять же согласно Википедии, mel — это “психофизическая единица высоты звука”, основанная на субъективном восприятии среднестатистическими людьми. Зависит в первую очередь от частоты звука (а так же от громкости и тембра). Другими словами, эта величина, показывающая, на сколько звук определённой частоты “значим” для нас.Преобразовать частоту в мел можно по следующей формуле (запомним её как «формула-1»):Обратное преобразование выглядит так (запомним её как «формула-2»):График зависимости mel / частота:Но вернёмся к нашей задаче. Допустим у нас есть фрейм размером 256 элементов. Мы знаем (из данных об аудиоформате), что частота звука в данной фрейме 16000hz. Предположим, что человеческая речь лежит в диапазоне от [300; 8000]hz. Количество искомых мел-коэффициентов положим M = 10 (рекомендуемое значение).Для того, что бы разложить полученный выше спектр по mel-шкале, нам потребуется создать “гребёнку” фильтров. По сути, каждый mel-фильтр это треугольная оконная функция, которая позволяет просуммировать количество энергии на определённом диапазоне частот и тем самым получить mel-коэффициент. Зная количество мел-коэффициентов и анализируемый диапазон частот мы можем построить набор таких вот фильтров:Обратите внимание, что чем больше порядковый номер мел-коэффициента, тем шире основание фильтра. Это связано с тем, что разбиение интересующего нас диапазона частот на обрабатываемые фильтрами диапазоны происходит на шкале мелов. Но мы опять отвлеклись. И так для нашего случая диапазон интересующих нас частот равен [300, 8000]. Согласно формуле-1 в на мел-шкале этот диапазон превращается в [401.25; 2834.99].Далее, для того, что бы построить 10 треугольных фильтров нам потребуется 12 опорных точек:
m[i] = [401.25, 622.50, 843.75, 1065.00, 1286.25, 1507.50, 1728.74, 1949.99, 2171.24, 2392.49, 2613.74, 2834.99]
Обратите внимание, что на мел-шкале точки расположены равномерно. Переведём шкалу обратно в герцы с помощью формулы-2:
h[i] = [300, 517.33, 781.90, 1103.97, 1496.04, 1973.32, 2554.33, 3261.62, 4122.63, 5170.76, 6446.70, 8000]
Как видите теперь шкала стала постепенно растягиваться, выравнивая тем самым динамику роста “значимости” на низких и высоких частотах.Теперь нам нужно наложить полученную шкалу на спектр нашего фрейма. Как мы помним, по оси Х у нас находится частота. Длина спектра 256 — элементов, при этом в него умещается 16000hz. Решив нехитрую пропорцию можно получить следующую формулу:
f(i) = floor( (frameSize+1) * h(i) / sampleRate)
что в нашем случае эквивалентно
f(i) = 4, 8, 12, 17, 23, 31, 40, 52, 66, 82, 103, 128
Вот и всё! Зная опорные точки на оси Х нашего спектра, легко построить необходимые нам фильтры по следующей формуле:
Применение фильтров, логарифмирование энергии спектраПрименение фильтра заключается в попарном перемножении его значений со значениями спектра. Результатом этой операции является mel-коэффициент. Поскольку фильтров у нас M, коэффициентов будет столько же.Однако, нам нужно применить mel-фильтры не к значениям спектра, а к его энергии. После чего прологарифмировать полученные результаты. Считается, что таким образом понижается чувствительность коэффициентов к шумам.
Косинусное преобразованиеДискретное косинусное преобразование (DCT) используется для того, что бы получить те самые “кепстральные” коэффициенты. Смысл его в том, что бы “сжать” полученные результаты, повысив значимость первых коэффициентов и уменьшив значимость последних.В данном случае используется DCTII без каких-либо домножений на  (scale factor).Теперь для каждого фрейма мы имеем набор из M mfcc-коэффициентов, которые могут быть использованы для дальнейшего анализа.Примеры код для вышележащих методов можно найти тут.
Алгоритм распознаванияВот тут, дорогой читатель, тебя и ждёт главное разочарование. В интернетах мне довелось увидеть множество высокоинтеллектуальных (и не очень) споров о том, какой же способ распознавания лучше. Кто-то ратует за Скрытые Марковские Модели, кто-то — за нейронные сети, чьи-то мысли в принципе невозможно понять :)В любом случае немало предпочтений отдаётся именно СММ, и именно их реализацию я собираюсь добавить в свой код… в будущем :)На данный момент, предлагаю остановится на гораздо менее эффективном, но в разы более простом способе.И так, вспомним, что наша задача заключается в распознавании слова из некоторого словаря. Для простоты, будем распознавать называния первых десять цифр: “один“, “два“, “три“, “четыре“, “пять“, “шесть“, “семь“, “восемь“, “девять“, “десять“.Теперь возьмем в руки айфон/андроид и пройдёмся по L коллегам с просьбой продиктовать эти слова под запись. Далее поставим в соответствие (в какой-нибудь локальной БД или простом файле) каждому слову L наборов mfcc-коэффициентов соответствующих записей.Это соответствие мы назовём “Модель”, а сам процесс — Machine Learning! На самом деле простое добавление новых образцов в базу имеет крайне слабую связь с машинным обучением… Но уж больно термин модный :)Теперь наша задача сводится к подбору наиболее “близкой” модели для некоторого набора mfcc-коэффициентов (распознаваемого слова). На первый взгляд задачу можно решить довольно просто:
для каждой модели находим среднее (евклидово) расстояние между идентифицируемым mfcc-вектором и векторами модели;
выбираем в качестве верной ту модель, среднее расстояние до которой будет наименьшим;Однако, одно и тоже слово может произносится как Андреем Малаховым, так и каким-нибудь его эстонским коллегой. Другими словами размер mfcc-вектора для одного и того же слова может быть разный.К счастью, задача сравнения последовательностей разной длины уже решена в виде Dynamic Time Warping алгоритма. Этот алгоритм динамическо программирования прекрасно расписан как в буржуйской Wiki, так и на православном Хабре.Единственное изменение, которое в него стоит внести — это способ нахождения дистанции. Мы должны помнить, что mfcc-вектор модели — на самом деле последовательность mfcc-“подвекторов” размерности M, полученных из фреймов. Так вот, DTW алгоритм должен находить дистанцию между последовательностями эти самых “подвекторов” размерности M. То есть в качестве значений матрицы расстояний должны использовать расстояния (евклидовы) между mfcc-“подвекторами” фреймов.Пример.
ЭкспериментыУ меня не было возможности проверить работу данного подхода на большой “обучающей” выборке. Результаты же тестов на выборке из 3х экземпляров для каждого слова в несинтетических условиях показали мягко говоря нелучший результат — 65% верных распознаваний.Тем не менее моей задачей было создание максимального простого приложения для распознавания речи. Так сказать “proof of concept” :)
РеализацияВнимательный читатель заметил, что статья содержит множество ссылок на GitHub-проект. Тут стоит отметить, что это мой первый проект на С++ со времён университета. Так же это моя первая попытка рассчитать что-то сложнее среднего арифметического со времён того же университета… Другими словами it comes with absolutely no warranty (с) :)25. Мел-кепстральные коэффициенты.Основные понятия
Объяснение начну с первого же слова в названии. Что такое мел? Википедия говорит нам, что мел – единица высоты звука, основанная на восприятии этого звука нашими органами слуха. Как известно, АЧХ человеческого уха даже отдаленно не напоминает прямую, и амплитуда – не совсем точная мера громкости звука. Поэтому, и ввели эмпирически подобранные единицы громкости, например, фон. Аналогично, воспринимаемая человеческим слухом высота звука не совсем линейно зависит от его частоты.Такая зависимость не претендует на большую точность, но зато описывается простой формулойПодобные единицы измерения часто используют при решении задач распознавания, так как они позволяют приблизиться к механизмам человеческого восприятия, которое пока что лидирует среди известных систем распознавания речи.Нужно немного рассказать и про второе слово в названии – кепстр.В соответствии с теорией речеобразования речь представляет собой акустическую волну, которая излучается системой органов: легкими, бронхами и трахеей, а затем преобразуется в голосовом тракте. Если предположить, что источники возбуждения и форма голосового тракта относительно независимы, речевой аппарат человека можно представить в виде совокупности генераторов тоновых сигналов и шумов, а также фильтров. Схематично это можно представить так:1. Генератор импульсной последовательности (тонов)2. Генератор случайных чисел (шумов)3. Коэффициенты цифрового фильтра (параметры голосового тракта)4. Нестационарный цифровой фильтрСигнал на выходе фильтра (4) можно представить в виде свертки где s(t) — изначальный вид акустической волны, а h(t) — характеристика фильтра (зависит от параметров голосового тракта)В частотной области это выглядит такПроизведение можно прологарифмировать, чтобы получить вместо него суммуТеперь нам нужно преобразовать эту сумму так, чтобы получить непересекающиеся наборы характеристик исходного сигнала и фильтра. Для этого есть несколько вариантов, например обратное преобразование Фурье даст нам вот чтоТакже в зависимости от целей можно использовать прямое преобразование Фурье или дискретное косинусное преобразованиеНадеюсь, я немного прояснил основные понятия. Осталось понять, как преобразовать речевой сигнал в набор коэффициентов MFCC.
Пример
В качестве подопытной возьмем простую цифру 1, вот ее временное представлениеПервым делом нам нужен спектр исходного сигнала, который мы получаем с помощью преобразования Фурье. Для простоты примера, не будем разбивать сигнал на части, поэтому берем спектр по всей временной осиТеперь начинается самое интересное, полученный спектр нам нужно расположить на мел-шкале. Для этого мы используем окна, равномерно расположенные на мел-оси.Если перевести этот график в частотную шкалу, можно увидеть такую картинуНа этом графике заметно, что окна «собираются» в области низких частот, обеспечивая более высокое «разрешение» там, где оно необходимо для распознавания. Простым перемножением векторов спектра сигнала и оконной функции найдем энергию сигнала, которая попадает в каждое из окон анализа. Мы получили некоторый набор коэффициентов, но это еще не те MFCC, которые мы ищем. Пока их можно было бы назвать Мел-частотными спектральными коэффициентами. Возводим их в квадрат и логарифмируем. Нам осталось только получить из них кепстральные, или «спектр спектра». Для этого мы могли бы еще раз применить преобразование Фурье, но лучше использовать дискретное косинусное преобразование. В результате получаем последовательность примерно такого вида:
Заключение
Таким образом мы имеем очень небольшой набор значений, который при распознавании успешно заменяет тысячи отсчетов речевого сигнала. В книгах пишут, что для задачи распознавания слов возможно брать первые 13 из 24 вычисленных коэффициентов, но сколько-нибудь годные результаты в моем случае начинались с 16. В любом случае это намного меньший объем данных, чем спектрограмма или временное представление сигнала. Для лучшего результата можно разбить исходное слово на отрезки небольшой длительности, и вычислять коэффициенты для каждого из них. Также может помочь «взвешивание» оконных функций. Все зависит от алгоритма распознавания, которому вы скармливаете результат.
Формулы
Не хочется грузить основную часть статьи большим количеством формул, но вдруг они будут кому-то интересны. Поэтому приведу их здесь.Исходный речевой сигнал запишем в дискретном виде какПрименяем к нему преобразование ФурьеСоставляем гребенку фильтров, используя оконную функциюДля которой частоты f[m] получаем из равенстваB(b) — преобразование значения частоты в мел-шкалу, соответственно,Вычисляем энергию для каждого окнаПрименяем ДКППолучаем набор MFCC
26. Бинеризация изображений. Методы бинаризации.Сегментация изображения
Одной из основных задач обработки и анализа изображений является сегментация, т.е. разделение изображения на области, для которых выполняется определенный критерий однородности, например, выделение на изображении областей приблизительно одинаковой яркости. Понятие области изображения используется для определения связной группы элементов изображения, имеющих определенный общий признак (свойство).Один из основных и простых способов — это построение сегментации с помощью порога. Порог — это признак (свойство), которое помогает разделить искомый сигнал на классы. Операция порогового разделения заключается в сопоставлении значения яркости каждого пикселя изображения с заданным значением порога. 
Бинаризация
Операция порогового разделения, которая в результате дает бинарное изображение, называется бинаризацией. Целью операции бинаризации является радикальное уменьшение количества информации, содержащейся на изображении. В процессе бинаризации исходное полутоновое изображение, имеющее некое количество уровней яркости, преобразуется в черно-белое изображение, пиксели которого имеют только два значения – 0 и 1 Пороговая обработка изображения может проводиться разными способами.
Бинаризация с нижним порогом
Бинаризация с нижним порогомБинаризация с нижним порогом является наиболее простой операцией, в которой используется только одно значение порога:Все значения вместо критерия становятся 1, в данном случае 255 (белый) и все значения(амплитуды) пикселей, которые больше порога t — 0 (черный).Бинаризации с верхним порогомИногда можно использовать вариант первого метода, который дает негатив изображения, полученного в процессе бинаризации. Операция бинаризации с верхним порогом:Бинаризация с двойным ограничениемДля выделения областей, в которых значения яркости пикселей может меняться в известном диапазоне, вводится бинаризация с двойным ограничением (t1<t2):Так же возможны другие вариации с порогами, где пропускается только часть данных (средне полосовой фильтр).Неполная пороговая обработкаДанное преобразование дает изображение, которое может быть проще для дальнейшего анализа, поскольку оно становится лишенным фона со всеми деталями, присутствующими на исходном изображении.Многоуровневое пороговое преобразованиеДанная операция формирует изображение, не являющееся бинарным, но состоящее из сегментов с различной яркостью.Что касается бинаризации, то по сути все. Хотя можно добавить, что есть глобальная, которая используется для всего изображения и так же существует локальная, которая захватывает часть картинки (изображения).
Локальная пороговая обработка
Метод ОтсаМетод использует гистограмму распределения значений яркости пикселей растрового изображения. Строится гистограмма по значениям pi=ni/N, где N – это общее кол-во пикселей на изображении, ni – это кол-во пикселей с уровнем яркости i. Диапазон яркостей делится на два класса с помощью порогового значения уровня яркости k,k — целое значение от 0 до L. Каждому классу соответствуют относительные частоты ω0ω1:Средние уровни для каждого из двух классов изображения:Далее вычисляется максимальное значение оценки качества разделения изображения на две части:где (σкл)2=ω0ω1(μ1-μ0)2, – межклассовая дисперсия, а (σобщ)2 – это общая дисперсия для всего изображения целиком.Определение порога на основе градиента яркости изображенияПредположим, что анализируемое изображение можно разделить на два класса – объекты и фон. Алгоритм вычисления порогового значения состоит из следующих 2 шагов:1. Определяется модуль градиента яркости для каждого пикселяизображения2. Вычисление порога:Метод использования энтропии гистограммыМетод приобрел свои различные формы описания и возможные вариации. Распределения общей массы порогов на определенное количество с использованием различных законов и форм распределения.
Глобальная пороговая обработка
Метод Бернсена1. Обычная квадратная апертура с нечетным числом пикселей пробегает в цикле по всем пикселям исходного изображения. На каждом шаге находится Min и Max.2. Находится среднее значение Avg= (Min + Max) /2.3. Если текущий пиксель больше Avg<E — он становится белым, иначе — чёрным. E — некая константа заданная пользователем.4. Если среднее меньше порога контраста — то текущий пиксель становится того цвета, который задавался параметром «цвет сомнительного пикселя».Имеет ряд недостатков: после обработки монотонных областей яркости формируются сильные паразитные помехи, в некоторых случаях приводит к появлению ложных черных пятенМетод ЭйквилаОдним из самых производительных методов является метод Эйквеля. Его часто применяют для обработки четких и контрастных изображений. Согласно данному методу изображение обрабатывается с помощью двух концентрических окон: маленького – S, и большого L. Обычно форма окон принимается квадратной. Оба окна последовательно слева направо сверху вниз накладываются на изображение с шагом равным стороне маленького окна S. Для окна L рассчитывается порог B так, чтобы поделить пиксели на два кластера. Если математические ожидания уровня яркости в двух кластерах имеют разницу, превышающую некоторый заданный пользователем уровень /μ1-μ2/≥l, то все пиксели внутри окна S бинаризуются в соответствии с порогом T. В противном случае, яркость пикселей из окна S заменяется некоторым близким значением.Метод НиблэкаИдея данного метода состоит в варьировании порога яркости B бинаризации от точки к точке на основании локального значения стандартного отклонения. Порог яркости в точке (x, y) рассчитывается так:где μ(x, y) – среднее и s(x, y) — среднеквадратичное отклонение выборки для некоторой окрестности точки. Размер окрестности должен быть минимальным, но таким, чтобы сохранить локальные детали изображения. В то же время размер должен быть достаточно большим, чтобы понизить влияние шума на результат. Значение k определяет, какую часть границы объекта взять в качестве самого объекта. Значение k=-0.2 задает достаточно хорошее разделение объектов, если они представлены черным цветом, а значение k=+0.2, – если объекты представлены белым цветом.Метод Яновица и БрукштейнаВ качестве пороговой поверхности бинаризации используется поверхность потенциалов, строящаяся на основе локальной максимизации градиента яркости. начение градиента яркости часто рассчитывается с помощью контурного оператора Собеля или Кэнни. Изображение фильтруется с целью получения контурных линий толщины в 1 пиксель, а затем усредняющим фильтром 3×3. Потенциальная поверхность, теперь, строится по итерационной интерполирующей схеме. Расчет поверхности идет в порядке, начиная от контурных пикселей. Для каждого не контурного пикселя рассчитывается интерполяционный остаток R(x, y) и новое значение пикселя P(x, y) на n+1-ом шаге должно рассчитываться в соответствии с формулами:β в пределах 1≤β≤2 для быстрой сходимости.
Итого
Что нашел с радостью выложил вам, в дальнейшем, если получится и будет время, постараюсь реализовать часть алгоритмов. Это лишь малая часть всего, что сегодня существует, но я рад поделится и этим.Спасибо за внимание.
27. Применение ФВЧ и ФНЧ при обработке изображений.Давно хотел написать общую статью, содержащую в себе самые основы Image Recognition, некий гайд по базовым методам, рассказывающий, когда их применять, какие задачи они решают, что возможно сделать вечером на коленке, а о чём лучше и не думать, не имея команды человек в 20.

Какие-то статьи по Optical Recognition я пишу давненько, так что пару раз в месяц мне пишут различные люди с вопросами по этой тематике. Иногда создаётся ощущение, что живёшь с ними в разных мирах. С одной стороны понимаешь, что человек скорее всего профессионал в смежной теме, но в методах оптического распознавания знает очень мало. И самое обидное, что он пытается применить метод из близрасположенной области знаний, который логичен, но в Image Recognition полностью не работает, но не понимает этого и сильно обижается, если ему начать рассказывать что-нибудь с самых основ. А учитывая, что рассказывать с основ — много времени, которого часто нет, становится всё ещё печальнее.Эта статья задумана для того, чтобы человек, который никогда не занимался методами распознавания изображений, смог в течении 10-15 минут создать у себя в голове некую базовую картину мира, соответствующую тематике, и понять в какую сторону ему копать. Многие методы, которые тут описаны, применимы к радиолокации и аудио-обработке.Начну с пары принципов, которые мы всегда начинаем рассказывать потенциальному заказчику, или человеку, который хочет начать заниматься Optical Recognition:
При решении задачи всегда идти от простейшего. Гораздо проще повесить на персону метку оранжевого цвета, чем следить за человеком, выделяя его каскадами. Гораздо проще взять камеру с большим разрешением, чем разрабатывать сверхразрешающий алгоритм.
Строгая постановка задачи в методах оптического распознавания на порядки важнее, чем в задачах системного программирования: одно лишнее слово в ТЗ может добавить 50% работы.
В задачах распознавания нет универсальных решений. Нельзя сделать алгоритм, который будет просто «распознавать любую надпись». Табличка на улице и лист текста — это принципиально разные объекты. Наверное, можно сделать общий алгоритм(HYPERLINK "http://habrahabr.ru/post/208330/"вот хороший пример от гугла), но это будет требовать огромного труда большой команды и состоять из десятков различных подпрограмм.
OpenCV — это библия, в которой есть множество методов, и с помощью которой можно решить 50% от объёма почти любой задачи, но OpenCV — это лишь малая часть того, что в реальности можно сделать. В одном исследовании в выводах было написано: «Задача не решается методами OpenCV, следовательно, она неразрешима». Старайтесь избегать такого, не лениться и трезво оценивать текущую задачу каждый раз с нуля, не используя OpenCV-шаблоны.
Очень сложно давать какой-то универсальный совет, или рассказать как создать какую-то структуру, вокруг которой можно строить решение произвольных задач компьютерного зрения. Цель этой статьи в структуризации того, что можно использовать. Я попробую разбить существующие методы на три группы. Первая группа это предварительная фильтрация и подготовка изображения. Вторая группа это логическая обработка результатов фильтрации. Третья группа это алгоритмы принятия решений на основе логической обработки. Границы между группами очень условные. Для решения задачи далеко не всегда нужно применять методы из всех групп, бывает достаточно двух, а иногда даже одного.Список приведённых тут методов не полон. Предлагаю в комментариях добавлять критические методы, которые я не написал и приписывать каждому по 2-3 сопроводительных слова.
Часть 1. Фильтрация
В эту группу я поместил методы, которые позволяют выделить на изображениях интересующие области, без их анализа. Большая часть этих методов применяет какое-то единое преобразование ко всем точкам изображения. На уровне фильтрации анализ изображения не производится, но точки, которые проходят фильтрацию, можно рассматривать как области с особыми характеристиками. 
Бинаризация по порогу, выбор области гистограммы
Самое просто преобразование — это бинаризация изображения по порогу. Для RGB изображения и изображения в градациях серого порогом является значение цвета. Встречаются идеальные задачи, в которых такого преобразования достаточно. Предположим, нужно автоматически выделить предметы на белом листе бумаги:Выбор порога, по которому происходит бинаризация, во многом определяет процесс самой бинаризации. В данном случае, изображение было бинаризовано по среднему цвету. Обычно бинаризация осуществляется с помощью алгоритма, который адаптивно выбирает порог. Таким алгоритмом может быть выбор матожидания или моды. А можно выбрать наибольший пик гистограммы.Бинаризация может дать очень интересные результаты при работе с гистограммами, в том числе в ситуации, если мы рассматриваем изображение не в RGB, а в HSV . Например, сегментировать интересующие цвета. На этом принципе можно построить как детектор метки так и детектор кожи человека. 
Классическая фильтрация: Фурье, ФНЧ, ФВЧ
Классические методы фильтрации из радиолокации и обработки сигналов можно с успехом применять во множестве задач Pattern Recognition. Традиционным методом в радиолокации, который почти не используется в изображениях в чистом виде, является преобразование Фурье (конкретнее — БПФ ). Одно из немногих исключение, при которых используется одномерное преобразование Фурье, — компрессия изображений. Для анализа изображений одномерного преобразования обычно не хватает, нужно использовать куда более ресурсоёмкое двумерное преобразование.Мало кто его в действительности рассчитывает, обычно, куда быстрее и проще использовать свёртку интересующей области с уже готовым фильтром, заточенным на высокие (ФВЧ) или низкие(ФНЧ) частоты. Такой метод, конечно, не позволяет сделать анализ спектра, но в конкретной задаче видеообработки обычно нужен не анализ, а результат.Самые простые примеры фильтров, реализующих подчёркивание низких частот (фильтр Гаусса) и высоких частот (Фильтр Габора).Для каждой точки изображения выбирается окно и перемножается с фильтром того же размера. Результатом такой свёртки является новое значение точки. При реализации ФНЧ и ФВЧ получаются изображения такого типа:
Вейвлеты
Но что если использовать для свёртки с сигналом некую произвольную характеристическую функцию? Тогда это будет называться "Вейвлет-преобразование". Это определение вейвлетов не является корректным, но традиционно сложилось, что во многих командах вейвлет-анализом называется поиск произвольного паттерна на изображении при помощи свёртки с моделью этого паттерна. Существует набор классических функций, используемых в вейвлет-анализе. К ним относятсявейвлет Хаара, вейвлет Морле, вейвлет мексиканская шляпа, и.т.д. Примитивы Хаара, про которые было несколько моих прошлых статей (1, 2), относятся к таким функциям для двумерного пространства.   Выше приведено 4 примера классических вейвлетов. 3х-мерный вейвлет Хаара, 2х-мерные вейвлет Мейера, вейвлет Мексиканская Шляпа, вейвлет Добеши. Хорошим примером использования расширеной трактовки вейвлетов является задачка поиска блика в глазу, для которой вейвлетом является сам блик:Классические вейвлеты обычно используются для сжатия изображений, или для их классификации (будет описано ниже). Корреляция
После такой вольной трактовки вейвлетов с моей стороны стоит упомянуть собственно корреляцию, лежащую в их основе. При фильтрации изображений это незаменимый инструмент. Классическое применение — корреляция видеопотока для нахождения сдвигов или оптических потоков. Простейший детектор сдвига — тоже в каком-то смысле разностный коррелятор. Там где изображения не коррелируют — было движение.  
Фильтрации функций
Интересным классом фильтров является фильтрация функций. Это чисто математические фильтры, которые позволяют обнаружить простую математическую функцию на изображении (прямую, параболу, круг). Строится аккумулирующее изображение, в котором для каждой точки исходного изображения отрисовывается множество функций, её порождающих. Наиболее классическим преобразованием является преобразование Хафа для прямых. В этом преобразовании для каждой точки (x;y) отрисовывается множество точек (a;b) прямой y=ax+b, для которых верно равенство. Получаются красивые картинки:(первый плюсег тому, кто первый найдёт подвох в картинке и таком определении и объяснит его, второй плюсег тому, кто первый скажет что тут изображено)Преобразование Хафа позволяет находить любые параметризуемые функции. Например окружности. Есть модифицированное преобразование, которое позволяет искать любые фигуры. Это преобразование ужасно любят математики. Но вот при обработке изображений, оно, к сожалению, работает далеко не всегда. Очень медленная скорость работы, очень высокая чувствительность к качеству бинаризации. Даже в идеальных ситуациях я предпочитал обходиться другими методами.Аналогом преобразования Хафа для прямых является преобразование Радона . Оно вычисляется через БПФ, что даёт выигрыш производительности в ситуации, когда точек очень много. К тому же его возможно применять к не бинаризованному изображению.
Фильтрации контуров
Отдельный класс фильтров — фильтрация границ и контуров . Контуры очень полезны, когда мы хотим перейти от работы с изображением к работе с объектами на этом изображении. Когда объект достаточно сложный, но хорошо выделяемый, то зачастую единственным способом работы с ним является выделение его контуров. Существует целый ряд алгоритмов, решающих задачу фильтрации контуров:
Оператор КэнниОператор СобеляОператор ЛапласаОператор ПрюиттОператор РобертсаЧаще всего используется именно Кэнни, который хорошо работает и реализация которого есть в OpenCV (Собель там тоже есть, но он хуже ищёт контуры).
Прочие фильтры
Сверху приведены фильтры, модификации которых помогают решить 80-90% задач. Но кроме них есть более редкие фильтры, используемые в локальных задачах. Таких фильтров десятки, я не буду приводить их все. Интересными являются итерационные фильтры (напримерHYPERLINK "http://habrahabr.ru/post/155759/" активная модель внешнего вида), а так же риджлет и курвлетпреобразования, являющиеся сплавом классической вейвлет фильтрации и анализом в поле радон-преобразования.Бимлет-преобразование красиво работает на границе вейвлет преобразования и логического анализа, позволяя выделить контуры:Но эти преобразования весьма специфичны и заточены под редкие задачи.
Часть 2. Логическая обработка результатов фильтрации
Фильтрация даёт набор пригодных для обработки данных. Но зачастую нельзя просто взять и использовать эти данные без их обработки. В этом разделе будет несколько классических методов, позволяющих перейти от изображения к свойствам объектов, или к самим объектам.
Морфология
Переходом от фильтрации к логике, на мой взгляд, являются методы математической морфологии (1, 2 , 3). По сути, это простейшие операции наращивания и эрозии бинарных изображений. Эти методы позволяют убрать шумы из бинарного изображения, увеличив или уменьшив имеющиеся элементы. На базе математической морфологии существуют алгоритмы оконтуривания, но обычно пользуются какими-то гибридными алгоритмами или алгоритмами в связке.
Контурный анализ
В разделе по фильтрации уже упоминались алгоритмы получения границ. Полученные границы достаточно просто преобразуются в контуры. Для алгоритма Кэнни это происходит автоматически, для остальных алгоритмов требуется дополнительная бинаризация. Получить контур для бинарного алгоритма можно например алгоритмом жука.Контур является уникальной характеристикой объекта. Часто это позволяет идентифицировать объект по контуру. Существует мощный математический аппарат, позволяющий это сделать. Аппарат называется контурным анализом (1, 2 ).Если честно, то у меня ни разу ни получилось применить контурный анализ в реальных задачах. Уж слишком идеальные условия требуются. То граница не найдётся, то шумов слишком много. Но, если нужно что-то распознавать в идеальных условиях — то контурный анализ замечательный вариант. Очень быстро работает, красивая математика и понятная логика.
Особые точки
Особые точки это уникальные характеристики объекта, которые позволяют сопоставлять объект сам с собой или с похожими классами объектов. Существует несколько десятков способов позволяющих выделить такие точки. Некоторые способы выделяют особые точки в соседних кадрах, некоторые через большой промежуток времени и при смене освещения, некоторые позволяют найти особые точки, которые остаются таковыми даже при поворотах объекта. Начнём с методов, позволяющих найти особые точки, которые не такие стабильные, зато быстро рассчитываются, а потом пойдём по возрастанию сложности:Первый класс. Особые точки, являющиеся стабильными на протяжении секунд. Такие точки служат для того, чтобы вести объект между соседними кадрами видео, или для сведения изображения с соседних камер. К таким точкам можно отнести локальные максимумы изображения, углы на изображении (лучший из детекторов, пожалуй, детекторХариса), точки в которых достигается максимумы дисперсии, определённые градиенты и.т.д.Второй класс. Особые точки, являющиеся стабильными при смене освещения и небольших движениях объекта. Такие точки служат в первую очередь для обучения и последующей классификации типов объектов. Например, классификатор пешехода или классификатор лица — это продукт системы, построенной именно на таких точках. Некоторые из ранее упомянутых вейвлетов могут являются базой для таких точек. Например, примитивы Хаара, поиск бликов, поиск прочих специфических функций. К таким точкам относятся точки, найденные методом гистограмм направленных градиентов (HOG).Третий класс. Стабильные точки. Мне известно лишь про два метода, которые дают полную стабильность и про их модификации. Это SURF и SIFT. Они позволяют находить особые точки даже при повороте изображения. Расчёт таких точек осуществляется дольше по сравнению с остальными методами, но достаточно ограниченное время. К сожалению эти методы запатентованы. Хотя, в России патентовать алгоритмы низя, так что для внутреннего рынка пользуйтесь.
Часть 3. Обучение
ретья часть рассказа будет посвящена методам, которые не работают непосредственно с изображением, но которые позволяют принимать решения. В основном это различные методы машинного обучения и принятия решений. Недавно Яндыкс выложил на Хабр курс по этой тематике, там очень хорошая подборка. Вот тут оно есть в текстовой версии. Для серьёзного занятия тематикой настоятельно рекомендую посмотреть именно их. Тут я попробую обозначить несколько основных методов используемых именно в распознавании образов.В 80% ситуаций суть обучения в задаче распознавания в следующем:Имеется тестовая выборка, на которой есть несколько классов объектов. Пусть это будет наличие/отсутствие человека на фотографии. Для каждого изображения есть набор признаков, которые были выделены каким-нибудь признаком, будь то Хаар, HOG, SURF или какой-нибудь вейвлет. Алгоритм обучения должен построить такую модель, по которой он сумеет проанализировать новое изображение и принять решение, какой из объектов имеется на изображении. Как это делается? Каждое из тестовых изображений — это точка в пространстве признаков. Её координаты это вес каждого из признаков на изображении. Пусть нашими признаками будут: «Наличие глаз», «Наличие носа», «Наличие двух рук», «Наличие ушей», и.т.д… Все эти признаки мы выделим существующими у нас детекторами, которые обучены на части тела, похожие на людские. Для человека в таком пространстве будет корректной точка [1;1;1;1;..]. Для обезьяны точка [1;0;1;0...] для лошади [1;0;0;0...]. Классификатор обучается по выборке примеров. Но не на всех фотографиях выделились руки, на других нет глаз, а на третьей у обезьяны из-за ошибки классификатора появился человеческий нос. Обучаемый классификатор человека автоматически разбивает пространство признаков таким образом, чтобы сказать: если первый признак лежит в диапазоне 0.5<x<1, второй 0.7<y<1, и.т.д., тогда это человек.По существу цель классификатора — отрисовать в пространстве признаков области, характеристические для объектов классификации. Вот так будет выглядеть последовательное приближение к ответу для одного из классификаторов (AdaBoost) в двумерном пространстве:  Существует очень много классификаторов. Каждый из них лучше работает в какой-то своей задачке. Задача подбора классификатора к конкретной задаче это во многом искусство. Вот тут немножко красивых картинок на тему.
Простой случай, одномерное разделение
Разберём на примере самый простой случай классификации, когда пространство признака одномерное, а нам нужно разделить 2 класса. Ситуация встречается чаще, чем может представиться: например, когда нужно отличить два сигнала, или сравнить паттерн с образцом. Пусть у нас есть обучающая выборка. При этом получается изображение, где по оси X будет мера похожести, а по оси Y -количество событий с такой мерой. Когда искомый объект похож на себя — получается левая гауссиана. Когда не похож — правая. Значение X=0.4 разделяет выборки так, что ошибочное решение минимизирует вероятность принятия любого неправильного решения. Именно поиском такого разделителя и является задача классификации.Маленькая ремарка. Далеко не всегда оптимальным будет тот критерий, который минимизирует ошибку. Следующий график — это график реальной системы распознавания по радужной оболочке. Для такой системы критерий выбирается такой, чтобы минимизировать вероятность ложного пропуска постороннего человека на объект. Такая вероятность называется «ошибка первого рода», «вероятность ложной тревоги», «ложное срабатывание». В англоязычной литературе «False Access Rate ».
Что делать если измерений больше двух?
Алгоритмов много. Даже очень много. Если хотите подробно узнать про каждый из них читайте курс Воронцова, ссылка на который дана выше, и смотрите лекции Яндыкса. Сказать, какой из алгоритмов лучше для какой задачи часто заранее невозможно. Тут я попробую выделить основные, которые в 90% помогут новичку с первой задачей и реализацию которых на вашем языке программирования вы достоверно найдёте в интернете.k-means (1, 2, 3 ) — один из самых простых алгоритмов обучения. Конечно, он в основном для кластеризации, но и обучить через него тоже можно. Работает в ситуации, когда группы объектов имеют неплохо разнесённый центр масс и не имеют большого пересечения.AdaBoost (1, 2, 3) АдаБуста — один из самых распространённых классификаторов. Например каскад Хаара построен именно на нём. Обычно используют когда нужна бинарная классификация, но ничего не мешает обучить на большее количество классов.SVM (1, 2, 3, 4 ) Один из самых мощных классификаторов, имеющий множество реализаций. В принципе, на задачах обучения, с которыми я сталкивался, он работал аналогично адабусте. Считается достаточно быстрым, но его обучение сложнее, чем у Адабусты и требуется выбор правильного ядра.Ещё есть нейронные сети и регрессия. Но чтобы кратко их классифицировать и показать, чем они отличаются, нужна статья куда больше, чем эта.________________________________________________Надеюсь, у меня получилось сделать беглый обзор используемых методов без погружения в математику и описание. Может, кому-то это поможет. Хотя, конечно, статья неполна и нет ни слова ни о работе со стереоизображениями, ни о МНК с фильтром Калмана, ни об адаптивном байесовом подходе.Если статья понравится, то попробую сделать вторую часть с подборкой примеров того, как решаются существующие задачки ImageRecognition.
И напоследок
Что почитать?1) Когда-то мне очень понравилась книга «Цифровая обработка изображений» Б. Яне, которая написана просто и понятно, но в то же время приведена почти вся математика. Хороша для того, чтобы ознакомиться с существующими методами.2) Классикой жанра является Р Гонсалес, Р. Вудс " Цифровая обработка изображений ". Почему-то она мне далась сложнее, чем первая. Сильно меньше математики, зато больше методов и картинок.3) «Обработка и анализ изображений в задачах машинного зрения» — написана на базе курса, читаемого на одной из кафедр ФизТеха. Очень много методов и их подробного описания. Но на мой взгляд в книге есть два больших минуса: книга сильно ориентирована на пакет софта, который к ней прилагается, в книге слишком часто описание простого метода превращается в математические дебри, из которых сложно вынести структурную схему метода. Зато авторы сделали удобный сайт, где представлено почти всё содержание — wiki.technicalvision.ru/4) Почему-то мне кажется, что хорошая книжка, которая структурирует и увязывает картину мира, возникающую при занятии Image Recognition и Machine Learning — это «Об интеллекте» Джеффа Хокинса. Прямых методов там нет, но есть много мыслей на подумать, откуда прямые методы обработки изображений происходят. Когда вчитываешься, понимаешь, что методы работы человеческого мозга ты уже видел, но в задачах обработки видео.
28.Медианные фильтры. Адаптивные медианные фильтры.
Обобщение медианного фильтраОбработка изображений*
Аннотация
В данной статье рассказывается об уникальном фильтре, статья о котором появилась в 1990 году: Маслов А.М., Сергеев В.В. Идентификация линейной искажающей системы с использованием ранговой обработки сигналов // Компьютерная оптика. — М., 1990. — Вып.6. — С.97-102. Данный алгоритм получил название «Алгоритм ранговой обработки» и по факту является обобщением медианного фильтра.Применение данного фильтра оправдано в двух случая — для подавления шума и для уменьшения смаза.Рисунок 1 — исходное изображение, 2 — смазанное и зашумленное солью.
Алгоритм ранговой обработки сигнала — экстремальный фильтр
Алгоритм заключается в обработке изображения локальным окном с записью результата обработки в новое изображение:
Пусть мы находимся в точке изображения с координатами (I,J) - текущий отсчет
Вокруг текущего отсчета рассматривается локальная окрестность размера NxN
По значениям точек в лоальной окрестности строится вариационный ряд, который обозначим p. Размер данного рядаN*N.
В результирующем изображении текущий отсчет принимает значение по следующему правилу:
где k — параметр алгоритма, N — нечетное число, Im1 — исходное изображение, Im2 — результирующее изображение.Если k = (N^2+1)/2 — то есть центр вариационного ряда — данный фильтр становится известным медианным фильтром. В дальнейшем этот параметр будем называть отступом.
Свойства экстремального фильтра
Свойства данного фильтр очень полезны на практике, так как фильтр позволяет компенсировать не только шум но устранять (частично) последствия смаза изображения. Предельным случаем этого фильтра при k = (N^2+1)/2 мы имеем медианный фильтр, который только устраняет шум, но не трогает границы, и если изображение смазанное, то смаз так и останется.При k < (N^2+1)/2 шум фильтруется несколько хуже, зато повышается резкость изображения, а при k = 0 шум и вовсе не фильтруется, но смаз устранятся самым сильным образом.Дабы не утруждать читателей элементарной реализацией данного алгоритма, я приведу здесь код на Matlab. Тестирующий скрипт будет читать изображение, смазывать его, и добавлять шум. Затем изображение восстанавливается данным экстремальным фильтров.
I1 = imread('coins.png');
h = ones(3,3) / 9;
I2 = imfilter(I1,h) ;I3 = imnoise(I2,'salt & pepper',0.02);
I4 = im2_rang_filter (I3, 1, 2);
 
figure; imagesc(I1);
colormap gray;
figure; imagesc(I3);
colormap gray;
figure; imagesc(I4)
colormap gray;
* This source code was highlighted with Source Code Highlighter.
Код функции фильтра im2_rang_filter:
function outImage= im2_rang_filter (aImage, aHalfWindowSize, aOtsup)
[ver,hor] = size(aImage);
wsize = (aHalfWindowSize*2+1)^2;
result = zeros(ver,hor);
for i = aHalfWindowSize+1 : (ver - aHalfWindowSize)
  for j = aHalfWindowSize+1 : (hor - aHalfWindowSize)
    
    wind = aImage((i-aHalfWindowSize) : (i + aHalfWindowSize), (j-aHalfWindowSize) : (j + aHalfWindowSize));
    vec = reshape(wind,1,wsize);
    vec = sort(vec);
    
    if (abs(vec(aOtsup+1) - aImage(i,j)) < abs(vec(wsize - aOtsup) - aImage(i,j)) )
      result(i,j) = vec(aOtsup+1);
    else result(i,j) = vec(wsize - aOtsup);
    end;
    
  end;
end;
outImage = result;
* This source code was highlighted with Source Code Highlighter.
Адаптивная медианная фильтрацияРассмотрим операции, осуществляемые в пространственной области над отсчетами цифрового изображения (пикселями) с целью повышения качества этого изображения. А именно класс операций, относящийся к методу нелинейной медианной фильтрации.
Этот метод наиболее эффективен, если шум на изображении имеет импульсный характер и представляет собой ограниченный набор пиковых значений на фоне нулей. Медианный фильтр реализуется как процедура локальной обработки скользящим окном различной формы (маской), которое включает нечетное число отсчетов изображения, и заключается в том, что для каждого положения окна попавшие в него отсчеты упорядочиваются по возрастанию (убыванию) значений. Средний отчет в этом списке называется медианой рассматриваемой группы из Nотсчетов. Эта медиана заменяет центральный отсчет в окне для обработанного сигнала. В результате применения медианного фильтра наклонные участки и резкие перепады значений яркости на изображениях не изменяются. Это очень полезное свойство именно для изображений, на которых, как известно, контуры несут основную информацию. В то же время импульсные помехи, протяженность которых составляет менее половины окна, будут подавлены.
Медианная фильтрация имеет и свои недостатки. В частности, экспериментально установлено, что у данного метода относительно слабая эффективность при фильтрации так называемого флуктуационного шума. Кроме того, при увеличении размера маски происходит размытие контуров изображения и, как следствие, снижение четкости изображения.
Указанные недостатки метода можно уменьшить до минимума, если воспользоваться медианной фильтрацией с динамическим размером маски (адаптивной медианной фильтрацией).
Принцип вычисления центрального отсчета при локальной обработке изображения скользящим окном остается все тот же. Эта медиана из набора упорядоченных отсчетов, попавших в окно (маску), а размер скользящего окна (маски) динамический и зависит от яркости соседних пикселей.
Введем пороговый коэффициент отклонения яркости Sthreshold = [0, 1]. Величины отклонения яркости соседних пикселей A(r, n, m), попавших в окно размером n x m, относительно яркости центрального отсчетаA(r) запишутся в виде (1)

Тогда критерий, согласно которому необходимо увеличивать размер маски с центральным отсчетом r, будет иметь вид (2)

На основе описанного алгоритма была разработана компьютерная программа, подтвердившая на практике преимущества адаптивной медианной фильтрации.
ВВЕДЕНИЕ
Медианные фильтры достаточно часто применяются на практике как средство предварительной обработки цифровых данных. Специфической особенностью фильтров является явно выраженная избирательность по отношению к элементам массива, представляющим собой немонотонную составляющую последовательности чисел в пределах окна (апертуры) фильтра, и резко выделяющихся на фоне соседних отсчетов. В то же время на монотонную составляющую последовательности медианный фильтр не действует, оставляя её без изменений. Благодаря этой особенности, медианные фильтры при оптимально выбранной апертуре могут, например, сохранять без искажений резкие границы объектов, эффективно подавляя некоррелированные или слабо коррелированные помехи и малоразмерные детали. Это свойство позволяет применять медианную фильтрацию для устранения аномальных значений в массивах данных, уменьшения выбросов и импульсных помех. Характерной особенностью медианного фильтра является его нелинейность. Во многих случаях применение медианного фильтра оказывается более эффективным по сравнению с линейными фильтрами, поскольку процедуры линейной обработки являются оптимальными при равномерном или гауссовом распределении помех, что в реальных сигналах может быть далеко не так. В случаях, когда перепады значений сигналов велики по сравнению с дисперсией аддитивного белого шума, медианный фильтр дает меньшее значение среднеквадратической ошибки по сравнению с оптимальными линейными фильтрами. Особенно эффективным медианный фильтр оказывается при очистке сигналов от импульсных шумов при обработке изображений, акустических сигналов, передаче кодовых сигналов и т.п. Однако детальные исследования свойств медианных фильтров как средства фильтрации сигналов различного типа являются довольно редкими.
16.1. МЕДИАННая ФИЛЬТРАЦИя одномерных сигналов [44, 46, 2i, 3i].
Принцип фильтрации. Медианы давно использовались и изучались в статистике как альтернатива средним арифметическим значениям отсчетов в оценке выборочных средних значений. Медианой числовой последовательности х1, х2, … , хn при нечетном n является средний по значению член ряда, получающегося при упорядочивании этой последовательности по возрастанию (или убыванию). Для четных n медиану обычно определяют как среднее арифметическое двух средних отсчетов упорядоченной последовательности.
Медианный фильтр представляет собой оконный фильтр, последовательно скользящий по массиву сигнала, и возвращающий на каждом шаге один из элементов, попавших в окно (апертуру) фильтра. Выходной сигнал yk скользящего медианного фильтра шириной 2n+1 для текущего отсчета k формируется из входного временного ряда …, xk-1, xk, xk+1,… в соответствии с формулой:
yk = med(xk-n, xk-n+1,…, xk-1, xk, xk+1 ,…, xk+n-1, xk+n), (16.1.1)
где med(x1, …, xm, …, x2n+1) = xn+1, xm – элементы вариационного ряда, т.е. ранжированные в порядке возрастания значений xm: x1 = min(x1, x2,…, x2n+1) ≤ x(2) ≤ x(3) ≤ … ≤ x2n+1 = max(x1, x2,…, x2n+1).
Таким образом, медианная фильтрация осуществляет замену значений отсчетов в центре апертуры медианным значением исходных отсчетов внутри апертуры фильтра. На практике апертура фильтра для упрощения алгоритмов обработки данных, как правило, устанавливается с нечетным числом отсчетов, что и будет приниматься при рассмотрении в дальнейшем без дополнительных пояснений.
Одномерные фильтры. Медианная фильтрация реализуется в виде процедуры локальной обработки отсчетов в скользящем окне, которое включает определенное число отсчетов сигнала. Для каждого положения окна выделенные в нем отсчеты ранжируются по возрастанию или убыванию значений. Средний по своему положению отчет в ранжированном списке называется медианой рассматриваемой группы отсчетов. Этим отсчетом заменяется центральный отсчет в окне для обрабатываемого сигнала. В силу этого медианный фильтр относится к числу нелинейных фильтров, заменяющим медианным значением аномальные точки и выбросы независимо от их амплитудных значений, и является устойчивым по определению, способным аннулировать даже бесконечно большие отсчеты.Алгоритм медианной фильтрации обладает явно выраженной избирательностью к элементам массива с немонотонной составляющей последовательности чисел в пределах апертуры и наиболее эффективно исключает из сигналов одиночные выбросы, отрицательные и положительные, попадающие на края ранжированного списка. С учетом ранжирования в списке медианные фильтры хорошо подавляют шумы и помехи, протяженность которых составляет менее половины окна. Стабильной точкой является последовательность (в одномерном случае) или массив (в двумерном случае), которые не изменяются при медианной фильтрации. В одномерном случае стабильными точками медианных фильтров являются "локально-монотонные" последовательности, которые медианный фильтр оставляет без изменений. Исключение составляют некоторые периодические двоичные последовательности.
Рис. 16.1.1.
Благодаря этой особенности, медианные фильтры при оптимально выбранной апертуре могут сохранять без искажений резкие границы объектов, подавляя некоррелированные и слабо коррелированные помехи и малоразмерные детали. При аналогичных условиях алгоритмы линейной фильтрации неизбежно «смазывает» резкие границы и контуры объектов. На рис. 16.1.1 приведен пример обработки сигнала с импульсными шумами медианным и треугольным фильтрами с одинаковыми размерами окна N=3. Преимущество медианного фильтра очевидно.
В качестве начальных и конечных условий фильтрации обычно принимаются концевые значения сигналов, либо медиана находится только для тех точек, которые вписываются в пределы апертуры.

Рис. 16.1.2.
На рис. 16.1.2 приведен пример медианной фильтрации модельного сигнала ak, составленного из детерминированного сигнала sk в сумме со случайным сигналом qk, имеющим равномерное распределение с одиночными импульсными выбросами. Окно фильтра равно 5. Результат фильтрации – отсчеты bk.
Подавление статистических шумов медианными фильтрами в связи с их нелинейностью обычно рассматривается только на качественном уровне. Нельзя также четко разграничить влияние медианных фильтров на сигнал и шум.
Если значения элементов последовательности чисел {xi} в апертуре фильтра являются независимыми одинаково распределенными (НОР) случайными величинами со средним значением m
x = m + z,
то математическое ожидание M{z} = 0 и, следовательно, M{x}=m.
Пусть F(x) и f(x)=F'(x) обозначают функции распределения и плотности вероятностей величин х. Согласно теории вероятностей, распределение у = med(х1, ... , хn) для больших n является приблизительно нормальным N(mt, n), где mt - теоретическая медиана, определяемая из условия F(mt) = 0.5, при этом дисперсия распределения:
n2 = 1/(n 4f2(mt)). (16.1.2)
Приведенные результаты справедливы как для одномерной, так и для двумерной фильтрации, если n выбирать равным числу точек в апертуре фильтра. Если f(x) симметрична относительно m, то распределение медиан также будет симметрично относительно m и, таким образом, справедлива формула:
M{med(х1, ... , хn)} = M{xi} = m.
Если случайные величины х являются НОР и равномерно распределены на отрезке [0, 1], то можно найти точное значение дисперсии медианы по формуле:
n2 = 1/(4(n+2)) = 3x /(n+2).
Если случайные величины х являются независимыми, одинаково распределенными с нормальным распределением N(m, ), то mt = m. Модифицированная формула дисперсии медианы для малых нечетных значений n:
g 2/(2n-2+). (16.1.2')
Значение дисперсии шумов для случайных величин в скользящем n-окне арифметического усреднения (фильтр МНК первого порядка) имеет значение 2/n. Это означает, что для нормального белого шума при равных значениях n окон медианного фильтра и фильтра скользящего усреднения, дисперсия шумов на выходе медианного фильтра приблизительно на 57% больше, чем у фильтра скользящего среднего. Чтобы медианный фильтр давал ту же дисперсию, что и скользящее усреднение, его апертура должна быть на 57% больше. При этом следует иметь в виду, что искажение полезных сигналов, особенно при наличии в них скачков и крутых перепадов, даже при большей апертуре медианного фильтра может оказаться меньше, чем у фильтров скользящего среднего.
Положение изменяется, если плотность распределения случайных величин существенно отличается от нормального и имеет длинные хвосты, которые и ликвидируются медианным фильтром, что обеспечивает оптимальную и наиболее правдоподобную оценку текущих значений сигнала по минимуму среднеквадратического приближения. Так, при экспоненциальном (по модулю) распределении плотности шумов
f(x) = ( SKIPIF 1 < 0 / exp(- SKIPIF 1 < 0 |x-m| /)дисперсия шумов после медианного фильтра на 50% меньше, чем после фильтра скользящего среднего.
Предельным случаем таких распределений является импульсный шум, случайный по амплитудам и месту появления, который и подавляется медианными фильтрами с наибольшей эффективностью.
Импульсные и точечные шумы. При регистрации, обработке и обмене данными в современных измерительно-вычислительных и информационных системах потоки сигналов кроме полезного сигнала s(t-0) и флуктуационных шумов q(t) содержат, как правило, импульсные потоки g(t)= SKIPIF 1 < 0 (t-k) различной интенсивности с регулярной или хаотической структурой
x(t) = s(t-0) + g(t) + q(t). (16.1.3)
Под импульсным шумом понимается искажение сигналов большими импульсными выбросами произвольной полярности и малой длительности. Причиной появления импульсных потоков могут быть как внешние импульсные электромагнитные помехи, так и наводки, сбои и помехи в работе самих систем. Совокупность статистически распределенного шума и потока квазидетерминированных импульсов представляет собой комбинированную  помеху. Радикальный метод борьбы с комбинированной помехой - применение помехоустойчивых кодов. Однако это приводит к снижению скорости и усложнению систем приемо-передачи данных. Простым, но достаточно эффективным альтернативным методом очистки сигналов в таких условиях является двухэтапный алгоритм обработки сигналов x(t), где на первом этапе производится устранение из потока x(t) шумовых импульсов, а на втором – очистка сигнала частотными фильтрами от статистических шумов. Для сигналов, искаженных действием импульсных шумов, отсутствует строгая в математическом смысле постановка и решение задачи фильтрации. Известны лишь эвристические алгоритмы, наиболее приемлемым из которых является алгоритм медианной фильтрации.
Допустим, что шум q(t) представляет собой статистический процесс с нулевым математическим ожиданием, полезный сигнал s(t-0) имеет неизвестное временное положение 0 [0, T], а поток шумовых импульсов g(t) имеет вид:
g(t) = SKIPIF 1 < 0 k ak g(t-k), (16.1.4)
где ak - амплитуда импульсов в потоке, k - неизвестное временное положение импульсов, k=1 с вероятностью pk и k=0 с вероятностью 1-pk. Такое задание импульсной помехи соответствует потоку Бернулли /44/.
При применении к потоку x(t) скользящей медианной фильтрации с окном N отсчетов (N – нечетное) медианный фильтр полностью устраняет одиночные импульсы, удаленные друг от друга минимум на половину апертуры фильтра, и подавляет импульсные помехи, если количество импульсов в пределах апертуры не превосходит (N-1)/2. В этом случае, при pk = p для всех импульсов помехи, вероятность подавления помех может быть определена по выражению /3i/:
R(p) = SKIPIF 1 < 0 pm(1-p)N-p. (16.1.5)

Рис. 16.1.3.
На рис. 16.1.3 приведены результаты расчетов вероятности подавления импульсной помехи медианным фильтром. При p<0.5 результаты статистического моделирования процесса показывают хорошее соответствие расчетным значениям. Для интенсивных импульсных шумовых потоков при p>0.5 медианная фильтрация становится мало эффективной, т.к. происходит не подавление, а усиление и трансформация его в поток импульсов другой структуры (со случайной длительностью).
Если вероятность ошибки не очень велика, то медианная фильтрация даже с достаточно малой апертурой значительно уменьшит число ошибок. Эффективность исключения шумовых импульсов повышается с увеличением апертуры фильтра, но одновременно может увеличиваться и искажение полезного сигнала.
Перепад плюс шум. Рассмотрим фильтрацию перепадов при наличии аддитивного белого шума, т. е. фильтрацию последовательностей, или изображений, с
x = s + z,

Рис. 16.1.4.
где s - детерминированный сигнал, равный 0 по одну сторону or перепада и h — по другую, a z - случайные значения белого шума. Предположим, что случайные значения шума z распределены по нормальному закону N(0, ). Для начала рассмотрим одномерную фильтрацию и будем считать, что перепад происходит в точке i = 1, таким образом, что для i0 величина xi есть N(0, ), а для i≥1 величина хi есть N(h, ).
На рис. 16.1.4 показана последовательность значений математического ожидания медиан и скользящего среднего вблизи перепада высотой h = 5 при N = 3. Значения скользящего среднего следуют по наклонной линии, что свидетельствует о смазывании перепада. Поведение математического ожидания значений медианы также свидетельствует о некотором смазывании, хотя в гораздо меньше, чем для скользящего среднего.
Если воспользоваться мерой среднеквадратичной ошибки (СКО), усредненной по N точкам вблизи перепада, и вычислить значения СКО в зависимости от значений h, то нетрудно зафиксировать, что при малых значениях h<2 СКО для скользящего среднего немного меньше, чем для медианы, но при h>3 СКО медианы значительно меньше, чем СКО среднего. Этот результат показывает, что скользящая медиана значительно лучше, чем скользящее среднее, для перепадов большой высоты. Похожие результаты можно получить и для апертуры N=5, и для двумерной фильтрации с апертурами 3x3 и 5x5. Таким образом, математические ожидания медианы для малых h близки к математическим ожиданиям для соответствующих средних, но для больших h они асимптотически ограничены. Объясняется это тем, что при больших h (скажем, h>4) переменные х со средним значением 0 (для данного примера) будут резко отделены от переменных х со средним h.
Использованная мера точности может характеризовать только резкость поперек перепада и ничего не говорит о гладкости фильтрованного изображения вдоль перепада. Скользящее усреднение дает сигналы, гладкие вдоль перепада, тогда как при обработке с помощью медианным фильтром протяженные перепады оказываются слегка изрезанными.
Ковариационные функции при белом шуме на входе. Нормализованные функции автокорреляции выходных сигналов медианных и усредняющих фильтров подобны друг другу. Сходство функций корреляции объясняется относительно высокой корреляцией между медианой и средним, которая достигает 0.8 при больших N.
Приближенная формула функции автоковариации для последовательности, подвергнутой медианной фильтрации определяется выражением:
K() = 2/(N+(/2)-1)) SKIPIF 1 < 0 (1-|j|/N) arcsin((j+)). (16.1.6)
Скользящая медиана почти не сглаживает процессы, ведущие себя на больших интервалах, как функции вида xi = (-1)i y. Скользящее усреднение оказывает большое сглаживающее действие на подобный процесс, так как регулярные флуктуации значений х полностью уничтожаются. В целом можно ожидать, что приближенные формулы ковариационных функций скользящих медиан будут полезны только для последовательностей, на которые медианные фильтры действуют так же, как и скользящее усреднение. В случае с сильно осциллирующими последовательностями и последовательностями перепадов большой пользы от них ждать не следует.
Преобразование статистики шумов. Медианная фильтрация является нелинейной операцией над входным процессом, которая наряду с исключением импульсных помех изменяет и распределение статистических шумов q(t), что может быть нежелательным для построения последующих фильтров. Аналитический расчет преобразования статистики шумов затруднителен из-за слабой разработанности соответствующего математического аппарата.

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

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

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

Рис. 16.1.8.
Медианный фильтр можно применять и по прямо противоположному назначению – обнаружению в сигналах и выделению квазидетерминированных помех.
Частотные свойства фильтра. Для описания линейных фильтров используют импульсную реакцию на единичный импульс, на ступенчатую функцию, и частотные передаточные функции в главном частотном диапазоне. Так как медианный фильтр ликвидирует единичные импульсы и сохраняет перепады, то можно говорить, что импульсная реакция фильтра равна нулю, а отклик на ступенчатую функцию равен 1. Что касается частотной характеристики фильтра, то, в силу нелинейности фильтра, ее нельзя представить какой-либо детерминированной функцией апертуры и частоты. В какой-то мере можно говорить о реакции фильтра на косинусоидальные функции, которая также существенно различается для низких и высоких частот главного частотного диапазона и фазы гармоник в апертуре фильтра, что можно видеть на рис. 16.1.9.

Рис. 16.1.9.
На рисунке приведено моделирование однотональных гармоник со случайной начальной фазой. Математические модели сигналов задавались в главном диапазоне спектральной области (0-2количество точек дискретизации спектра - 2000). Модуль гармоники устанавливался равным 1, при этом модуль спектра выходного сигнала после фильтрации, по-существу, отображает передаточную функцию фильтра. Окно медианного фильтра равно 3.
Как показывает моделирование, для низких частот, когда период гармоники много больше окна апертуры фильтров, скользящая медиана и скользящее среднее имеют сходные характеристики, коэффициент передачи Кп однотональных сигналов равен 1. По мере роста частоты гармоники и в зависимости от фазы сигнала в апертуре фильтра начинается искажение сигнала на экстремальных значениях (занижение экстремальных значений), и значение Кп начинает уменьшаться. Когда значение апертуры медианного фильтра становится соизмеримым с периодом сигнала, в спектре выходного сигнала появляются "ложные" гармоники, вызванные интерференцией частоты входного сигнала с частотой его дискретизации (нижние графики на рисунке 16.1.9).

Рис. 16.1.10. Медианная фильтрация многотональных сигналов
Для многотональных входных сигналов начинается также интерференция частот гармоник между собой, что приводит к появлению многочисленных ложных высокочастотных гармоник (верхние графики на рис. 16.1.10), а при наличии во входном сигнале высокочастотных гармоник искажаются также и коэффициенты передачи низкочастотных гармоник (нижние графики на рисунке), т.е. частотные отклики для одиночных гармонических функций не соответствуют передаточным характеристикам для произвольных сигналов, являющихся суммой косинусоидальных функций, т.к. передаточные функции становятся резко нерегулярными в силу интерференции разных частот.
Картина частотной интерференции зависит также от фазы гармоник, что усиливает нерегулярность конечных результатов и наглядно видно на рис. 16.1.11 при различных случайных реализациях фазы гармоник. При увеличении размеров апертуры фильтров нерегулярность передачи фильтров увеличивается.

Рис. 16.1.11.
Разновидности медианных фильтров.
Взвешенно-медианные фильтры применяют, если желательно придать больший вес центральным точкам. Это достигается путем повторения ki раз каждого набора отсчетов в апертуре фильтра. Так, например, при N=3 и k-1=k1=2, k0=3 вычисление взвешенной медианы входного числового ряда производится по формуле:
yi = med (xi-1, xi-1, x0, x0, x0, x1, x1).
Такая растянутая последовательность также сохраняет перепады сигнала и в определенных условиях позволяет увеличить подавление дисперсии статистических шумов в сигнале. Ни один из весовых коэффициентов ki не должен быть значительно больше всех других.
Итерационные медианные фильтры выполняются последовательным повторением медианной фильтрации. Если апертура единичной медианной фильтрации сохраняет перепады в сигнале, то они сохраняются при итеративном применении фильтра вплоть до тех пор, пока не прекратятся изменения в фильтруемом сигнале, при этом конечный результат существенно отличается от итеративного применения скользящего среднего, где в пределе получается постоянная числовая последовательность. При использовании итерационных фильтров можно изменять апертуру фильтра при каждом шаге итерации.
Достоинства медианных фильтров.
Простая структура фильтра, как для аппаратной, так и для программной реализации.
Фильтр не изменяет ступенчатые и пилообразные функции.
Фильтр хорошо подавляет одиночные импульсные помехи и случайные шумовые выбросы отсчетов.
Недостатки медианных фильтров.
Медианная фильтрация нелинейна, так как медиана суммы двух произвольных последовательностей не равна сумме их медиан, что в ряде случаев может усложнять математический анализ сигналов.
Фильтр вызывает уплощение вершин треугольных функций.
Подавление белого и гауссового шума менее эффективно, чем у линейных фильтров. Слабая эффективность наблюдается также при фильтрации флюктуационного шума.
При увеличении размеров окна фильтра происходит размытие крутых изменений сигнала и скачков.
Недостатки метода можно уменьшить, если применять медианную фильтрацию с адаптивным изменением размера окна фильтра в зависимости от динамики сигнала и характера шумов (адаптивная медианная фильтрация). В качестве критерия размера окна можно использовать, например, величину отклонения значений соседних отсчетов относительно центрального ранжированного отсчета /1i/. При уменьшении этой величины ниже определенного порога размер окна увеличивается.
16.2. МЕДИАННая ФИЛЬТРАЦИя изображений [47, 48, 3i].
Шумы в изображениях. Никакая система регистрации не обеспечивает идеального качества изображений исследуемых объектов. Изображения в процессе формирования их системами (фотографическими, голографическими, телевизионными) обычно подвергаются воздействию различных случайных помех или шумов. Фундаментальной проблемой в области обработки изображений является эффективное удаление шума при сохранении важных для последующего распознавания деталей изображения. Сложность решения данной задачи существенно зависит от характера шумов. В отличие от детерминированных искажений, которые описываются функциональными преобразованиями исходного изображения, для описания случайных воздействий используют модели аддитивного, импульсного и мультипликативного шумов.
Наиболее распространенным видом помех является случайный аддитивный шум, статистически независимый от сигнала. Модель аддитивного шума используется тогда, когда сигнал на выходе системы или на каком-либо этапе преобразования может рассматриваться как сумма полезного сигнала и некоторого случайного сигнала. Модель аддитивного шума хорошо описывает действие зернистости фотопленки, флуктуационный шум в радиотехнических системах, шум квантования в аналого-цифровых преобразователях и т.п.
Аддитивный гауссов шум характеризуется добавлением к каждому пикселю изображения значений с нормальным распределением и с нулевым средним значением. Такой шум обычно появляется на этапе формирования цифровых изображений. Основную информацию в изображениях несут контуры объектов. Классические линейные фильтры способны эффективно удалить статистический шум, но степень размытости мелких деталей на изображении может превысить допустимые значения. Для решения этой проблемы используются нелинейные методы, например алгоритмы на основе анизотропной диффузии Перрона и Малика, билатеральные и трилатеральные фильтры. Суть таких методов заключается в использовании локальных оценок, адекватных определению контура на изображении, и сглаживания таких участков в наименьшей степени.
Импульсный шум характеризуется заменой части пикселей на изображении значениями фиксированной или случайной величины. На изображении такие помехи выглядят изолированными контрастными точками. Импульсный шум характерен для устройств ввода изображений с телевизионной камеры, систем передачи изображений по радиоканалам, а также для цифровых систем передачи и хранения изображений. Для удаления импульсного шума используется специальный класс нелинейных фильтров, построенных на основе ранговой статистики. Общей идеей таких фильтров является детектирование позиции импульса и замена его оценочным значением, при сохранении остальных пикселей изображения неизменными.
Двумерные фильтры. Медианная фильтрация изображений наиболее эффективна, если шум на изображении имеет импульсный характер и представляет собой ограниченный набор пиковых значений на фоне нулей. В результате применения медианного фильтра наклонные участки и резкие перепады значений яркости на изображениях не изменяются. Это очень полезное свойство именно для изображений, на которых контуры несут основную информацию.

Рис. 16.2.1.
При медианной фильтрации зашумленных изображений степень сглаживания контуров объектов напрямую зависит от размеров апертуры фильтра и формы маски. Примеры формы масок с минимальной апертурой приведены на рис. 16.2.1. При малых размерах апертуры лучше сохраняются контрастные детали изображения, но в меньшей степени подавляется импульсные шумы. При больших размерах апертуры наблюдается обратная картина. Оптимальный выбор формы сглаживающей апертуры зависит от специфики решаемой задачи и формы объектов. Особое значение это имеет для задачи сохранения перепадов (резких границ яркости) в изображениях.
Под изображением перепада понимаем изображение, в котором точки по одну сторону от некоторой линии имеют одинаковое значение а, а все точки по другую сторону от этой линии - значение b, ba. Если апертура фильтра симметрична относительно начала координат, то медианный фильтр сохраняет любое изображение перепада. Это выполняются для всех апертур с нечетным количеством отсчетов, т.е. кроме апертур (квадратные рамки, кольца), которые не содержат начала координат. Тем не менее квадратные рамки и кольца будут лишь незначительно изменять перепад.

Рис. 16.2.2.
Для упрощения дальнейшего рассмотрения ограничимся примером фильтра с квадратной маской размером N × N, при N=3. Скользящий фильтр просматривает отсчеты изображения слева-направо и сверху-вниз, при этом входную двумерную последовательность также представим в виде последовательного числового ряда отсчетов {x(n)} слева-направо сверху-вниз. Из этой последовательности в каждой текущей точке маска фильтра выделяет массив w(n), как W-элементный вектор, который в данном случае содержит все элементы из окна 3×3, центрированные вокруг x(n), и сам центральный элемент, если это предусмотрено типом маски:
w(n) = [x1 (n),x2(n), …, xW (n)]. (16.2.1)
В этом случае значения xi соответствует отображению слева-направо и сверху-вниз окна 3×3 в одномерный вектор, как показано на рис. 16.2.2.
Элементы данного вектора, как и для одномерного медианного фильтра, также могут быть упорядочены в ряд по возрастанию или убыванию своих значений:
r(n) = [r1(n), r2(n), …, rW (n)], (16.2.2)
определено значение медианы y(n) = med(r(n)), и центральный отсчет маски заменен значением медианы. Если по типу маски центральный отсчет не входит в число ряда 16.2.1, то медианное значение находится в виде среднего значения двух центральных отсчетов ряда 16.2.2.
Приведенные выражения не объясняют способа нахождения выходного сигнала вблизи конечных и пограничных точек в конечных последовательностях и изображениях. Один из простых приемов состоит в том, что нужно находить медиану только тех точек внутри изображения, которые попадают в пределы апертуры. Поэтому для точек, расположенных рядом с границами, медианы будут определены, исходя из меньшего числа точек.
На рис. 16.2.3 приведен пример очистки зашумленного изображения медианным фильтром Черненко /2i/. Зашумление изображения по площади составляло 15%, для очистки фильтр применен последовательно 3 раза.

Рис. 16.2.3.
Медианная фильтрация может выполняться и в рекурсивном варианте, при котором значения сверху и слева от центрального отсчета в маске (в данном случае x1(n)-x4(n) на рис. 16.2.2) в ряде 16.2.1 заменяются на уже вычисленные в предыдущих циклах значения y1(n)-y4(n).
Адаптивные двумерные фильтры. Противоречие по зависимости степени подавления шумов и искажения сигнала от апертуры фильтра в некоторой степени сглаживается при применении фильтров с динамическим размером маски, с адаптацией размеров апертуры под характер изображения. В адаптивных фильтрах большие апертуры используются в монотонных областях обрабатываемого сигнала (лучшее подавление шумов), а малые – вблизи неоднородностей, сохраняя их особенности, при этом размер скользящего окна фильтра устанавливается в зависимости от распределения яркости пикселей в маске фильтра. В их основе лежит, как правило, анализ яркости окрестностей центральной точки маски фильтра.
Простейшие алгоритмы динамического изменения апертуры фильтра, симметричного по обеих осям, обычно работают по заданному на основании эмпирических данных пороговому коэффициенту яркости Sпорог = [0, 1]. В каждом текущем положении маски на изображении итерационный процесс начинается с апертуры минимального размера. Величины отклонения яркости соседних пикселей A(r, n), попавших в окно размером (n x n), относительно яркости центрального отсчета A(r) вычисляются по формуле:
Sn(r) = |A(r,n)/A(r) – 1|. (16.2.3)
Критерий, согласно которому производится увеличение размера маски с центральным отсчетом r и выполняется следующая итерация, имеет вид:
max[Sn(r)] < Sпорог. (16.2.4)
Максимальный размер маски (количество итераций), как правило, ограничивается. Для неквадратных масок, имеющих размеры (n x m), итерации могут вычисляться с раздельным увеличением параметров n и m, а также с изменением формы масок в процессе итераций.
Фильтры на основе ранговой статистики. В последние два десятилетия в цифровой обработке изображений активно развиваются нелинейные алгоритмы на основе ранговой статистики для восстановления изображений, поврежденных различными моделями шумов. Подобные алгоритмы позволяют избежать дополнительного искажения изображения при удалении шума, а также значительно улучшить результаты работы фильтров на изображениях с высокой степенью зашумленности.
Сущность ранговой статистики обычно заключается в том, что ряд 16.2.1 не включает центральный отсчет маски фильтра, и по ряду 16.2.2 производится вычисление значения m(n). При N=3 по рис. 16.2.2:
m(n) = (x4(n)+x5(n))/2. (16.2.5)
Вычисление выходного значения фильтра, которым заменяется центральный отсчет, выполняется по формуле:
y(n) =  x(n) + (1-) m(n). (16.2.6)
Значение коэффициента доверия  связывается определенной зависимостью со статистикой отсчетов в окне фильтра (например, полной дисперсией отсчетов, дисперсией разностей x(n)-xi(n) или m(n)-xi(n), дисперсией положительных и отрицательных разностей x(n)-xi(n) или m(n)-xi(n), и т.п.). По существу, значение коэффициента  должно задавать степень поврежденности центрального отсчета и, соответственно, степень заимствования для его исправления значения из отсчетов m(n). Выбор статистической функции и характер зависимости от нее коэффициента  может быть достаточно многообразным и зависит как от размеров апертуры фильтра, так и от характера изображений и шумов.
29.Вейвлеты. Принципы и применение вейвлета Хаара.Вейвлет-сжатие «на пальцах» tutorialОбработка изображений*
Введение
left140335Вейвлеты сейчас на слуху. Даже неискушённые в математике люди наверняка слышали, что с их помощью удаётся сжимать изображения и видео сохраняя приемлемое качество. Но что же такое вейвлет? Википедия отвечает на этот вопрос целым ворохом формул за которыми не так-то легко увидеть суть.Попробуем на простых примерах разобраться, откуда же вообще берутся вейвлеты и как их можно использовать при сжатии. Предполагается, что читатель знаком с основами линейной алгебры, не боится слов вектор и матрица, а также умеет их перемножать.
Сжатие изображений
Упрощённо, изображение представляют собой таблицу, в ячейках которой хранятся цвета каждого пикселя. Если мы работаем с чёрно-белым (или, точнее, серым) изображением, то вместо цвета в ячейки помещают значения яркости из отрезка [0, 1]. При этом 0 соответствует чёрному цвету, 1 — белому. Но с дробями работать неудобно, поэтому часто значения яркости берут целыми из диапазона от 0 до 255. Тогда каждое значение будет занимать ровно 1 байт.Даже небольшие изображения требуют много памяти для хранения. Так, если мы кодируем яркость каждого пикселя одним байтом, то изображение одного кадра формата FullHD (1920×1080) займёт почти два мегабайта. Представьте, сколько памяти потребуется для хранения полуторачасового фильма!Поэтому изображения стремятся сжать. То есть закодировать таким образом, чтобы памяти для хранения требовалось меньше. А во время просмотра мы декодируем записанные в память данные и получаем исходный кадр. Но это лишь в идеале.Существует много алгоритмов сжатия данных. О их количестве можно судить по форматам, поддерживаемым современными архиваторами: ZIP, 7Z, RAR, ACE, GZIP, HA, BZ2 и так далее. Неудивительно, что благодаря активной работе учёных и программистов в настоящее время степень сжатия данных вплотную подошла к теоретическому пределу.Плохая новость в том, что для изображения этот теоретический предел не так уж и велик. Попробуйте сохранить фотографию (особенно с большим количеством мелких деталей) в формате PNG — размер получившегося файла может вас расстроить.Это происходит из-за того, что в изображениях из реального мира (фотографиях, например) значения яркости редко бывают одинаковыми даже у соседних пикселей. Всегда есть мельчайшие колебания, которые неуловимы человеческим глазом, но которые алгоритм сжатия честно пытается учесть.Алгоритмы сжатия «любят», когда в данных есть закономерность. Лучше всего сжимаются длинные последовательности нулей (закономерность тут очевидна). В самом деле, вместо того, чтобы записывать в память 100 нулей, можно записать просто число 100 (конечно, с пометкой, что это именно количество нулей). Декодирующая программа «поймёт», что имелись в виду нули и воспроизведёт их.Однако если в нашей последовательности в середине вдруг окажется единица, то одним числом 100 ограничится не удастся.Но зачем кодировать абсолютно все детали? Ведь когда мы смотрим на фотографию, нам важен общий рисунок, а незначительные колебания яркости мы и не заметим. А значит, при кодировании мы можем немного изменить изображение так, чтобы оно хорошо кодировалось. При этом степень сжатия сразу вырастет. Правда, декодированное изображение будет незначительно отличаться от исходного, но кто заметит?
Преобразование Хаара
Итак, наша цель — преобразовать изображение так, чтобы оно хорошо сжималось классическими алгоритмами. Подумаем, как нужно изменить его, чтобы получить длинные цепочки нулей.У «реальных» изображений, таких как фотографии, есть одна особенность — яркость соседних пикселей обычно отличается на небольшую величину. В самом деле, в мире редко можно увидеть резкие, контрастные перепады яркости. А если они и есть, то занимают лишь малую часть изображения.Рассмотрим фрагмент первой строки яркостей из известного изображения «Lenna» (на рисунке). 
154, 155, 156, 157, 157, 157, 158, 156
right259715Видно, что соседние числа очень близки. Чтобы получить желаемые нули или хотя бы что-то близкое к ним, можно закодировать отдельно первое число, а потом рассматривать лишь отличия каждого числа от предыдущего.Получаем:
154, 1, 1, 1, 0, 0, 1, -2.
Уже лучше! Такой метод в самом деле используется и называется дельта-кодированием. Но у него есть серьёзные недостаток — он нелокальный. То есть нельзя взять кусочек последовательности и узнать, какие именно яркости в нём закодированы без декодирования всех значений перед этим кусочком.Попробуем поступить иначе. Не будем пытаться сразу получить хорошую последовательность, попробуем улучшить её хотя бы немного.Для этого разобьём все числа на пары и найдём полусуммы и полуразности значений в каждой из них.
(154, 155), (156, 157), (157, 157), (158, 156)

(154.5, 0.5), (156.5, 0.5), (157, 0.0), (157, -1.0)
Почему именно полусуммы и полуразности? А всё очень просто! Полусумма — это среднее значение яркости пары пикселей. А полуразность несёт в себе информацию об отличиях между значениями в паре. Очевидно, зная полусумму a и полуразность d можно найти и сами значения:первое значение в паре = a — d,второе значение в паре = a + d.Это преобразование было предложено в 1909 году Альфредом Хааром и носит его имя.
А где же сжатие?
Полученные числа можно перегруппировать по принципу «мухи отдельно, котлеты отдельно», разделив полусуммы и полуразности:
154.5, 156.5, 157, 157; 0.5, 0.5, 0.0, -1.0.
Числа во второй половине последовательности как правило будут небольшими (то, что они не целые, пусть пока не смущает). Почему так?Как мы уже выяснили раньше, в реальных изображениях соседние пиксели редко отличаются друг от друга значительно. Если значение одного велико, то и другого велико. В таких случаях говорят, что соседние пиксели коррелированы.В самом деле, рассмотрим первые 2000 пар соседних пикселей и каждую пару представим на графике точкой.Все точки выстраиваются вдоль одной прямой линии. И так практически во всех реальных изображениях. Верхний левый и нижний правый углы изображения практически всегда пусты.А теперь рассмотрим график, точками в котором будут полусуммы и полуразности.Видно, что полуразности находятся в гораздо более узком диапазоне значений. А это значит, что на них можно потратить меньше одного байта. Какое-никакое, а сжатие.
Применим математику!
Попробуем записать математические выражения, описывающие преобразование Хаара.Итак, у нас была пара пикселей (вектор) , а мы хотим получить пару .Такое преобразование описывается матрицей .В самом деле , что нам и требовалось.Внимательный читатель наверняка заметил, что рисунки из точек на двух последних графиках одинаковы. Разница лишь в повороте на угол в 45°.В математике повороты и растяжения называются аффинными преобразованиями и описываются как раз при помощи умножения матрицы на вектор. Что мы и получили выше. То есть, преобразование Хаара — это просто поворот точек таким образом, чтобы их можно было удобно и компактно закодировать.Правда, тут есть один нюанс. При аффинных преобразованиях может меняться площадь фигуры. Не то, чтобы это было плохо, но как-то неаккуратненько. Как известно, коэффициент изменения площади равен определителю матрицы. Посмотрим, каков он для преобразования Хаара.Для того, чтобы определитель стал равен единице достаточно умножить каждый элемент матрицы на . На угол поворота (а значит, и на «сжимающую способность» преобразования) это не повлияет.Получаем в итоге матрицу
А как декодировать?
Как известно, если у матрицы определитель не равен нулю, то для неё существует обратная матрица, «отменяющая» её действие. Если мы найдём обратную матрицу для H, то декодирование будет заключаться просто в умножении векторов с полусуммами и полуразностями на неё.Вообще говоря, поиск обратной матрицы — не такая простая задача. Но, может, удастся как-то эту задачу упростить?Рассмотрим поближе нашу матрицу. Она состоит из двух вектор-строк:  и . Назовём их v1 и v2.Они обладают интересными свойствами.Во-первых, их длины равны 1, то есть . Здесь буква T означает транспонирование. Умножение вектор-строки на транспонированный вектор-строку — это скалярное произведение.Во-вторых, они ортогональны, то есть .Матрица, строки которой обладают указанными свойствами называется ортогональной. Чрезвычайно важным свойством таких матриц является то, что обратную матрицу для них можно получить простым транспонированием.В справедливости этого выражения можно убедиться умножив H обратную матрицу. На диагонали мы получим скалярные произведения вектор-строк на самих себя, то есть 1. А вне диагоналей — скалярные произведения вектор-строк друг на друга, то есть 0. В итоге произведение будет равно единичной матрице.Мы любим ортогональные матрицы!
Увеличиваем число точек
Всё сказанное хорошо работает для двух точек. Но что делать, если точек больше?В этом случае тоже можно описать преобразование матрицей, но большей по размеру. Диагональ этой матрицы будет состоять из матриц H, таким образом в векторе исходных значений будут выбираться пары, к которым независимо будет применяться преобразование Хаара.То есть. исходный вектор просто обрабатывается независимо по парам.
Фильтры
Итак, когда мы знаем, как выполнять преобразование Хаара, попробуем разобраться с тем, что же оно нам даёт.Полученные «полусуммы» (из-за того, что делим не на 2, приходится использовать кавычки) — это, как мы уже выяснили, средние значения в парах пикселей. То есть, фактически, значения полусумм — это уменьшенная копия исходного изображения! Уменьшенная потому, что полусумм в два раза меньше, чем исходных пикселей.Но что такое разности?Полусуммы усредняют значения яркостей, то есть «отфильтровывают» случайные всплески значений. Можно считать, что это некоторый частотный фильтр.Аналогично, разности «выделяют» среди значений межпиксельные «всплески» и устраняют константную составляющую. То есть, они «отфильтровывают» низкие частоты.Таким образом, преобразование Хаара — это пара фильтров, разделяющих сигнал на низкочастотную и высокочастотную составляющие. Чтобы получить исходный сигнал, нужно просто снова объединить эти составляющие.Что нам это даёт? Пусть у нас есть фотография-портрет. Низкочастотная составляющая несёт в себе информацию об общей форме лица, о плавных перепадах яркости. Высокочастотная — это шум и мелкие детали.Обычно, когда мы смотрим на портрет, нас больше интересует низкочастотная составляющая, а значит при сжатии часть высокочастотных данных можно отбросить. Тем более, что, как мы выяснили, она обычно имеет меньшие значения, а значит более компактно кодируется.Степень сжатия можно увеличить, применяя преобразование Хаара многократно. В самом деле, высокочастотная составляющая — это всего лишь половина от всего набора чисел. Но что мешает применить нашу процедуру ещё раз к низкочастотным данным? После повторного применения, высокачастотная информация будет занимать уже 75%.Хоть мы пока и говорили об одномерных цепочках чисел, этот подход хорошо применим и для двумерных данных. Чтобы выполнить двумерное преобразование Хаара (или аналогичное ему), нужно лишь выполнить его для каждой строки и для каждого столбца.После многократного применения к, например, фотографии замка Лихтенштейн, получим следующий рисунок.Черные области соответствуют низкой яркости, то есть значениям, близким к нулю. Как показывает практика, если значение достаточно мало, то его можно округлить или вообще обнулить без особого ущерба для декодированного рисунка.Этот процесс называется квантованием. И именно на этом этапе происходит потеря части информации. (К слову, такой же подход используется в JPEG, только там вместо преобразования Хаара используется дискретное косинус-преобразование.) Меняя число обнуляемых коэффициентов, можно регулировать степень сжатия!Конечно, если обнулить слишком много, то искажения станут видны на глаз. Во всём нужна мера!После всех этих действий у нас останется матрица, содержащая много нулей. Её можно записать построчно в файл и сжать каким-то архиватором. Например, тем же 7Z. Результат будет неплох.Декодирование производится в обратном порядке: распаковывем архив, применяем обратное преобразование Хаара и записываем декодированную картинку в файл. Вуаля!
Где эффективно преобразование Хаара?
Когда преобразование Хаара будет давать наилучший результат? Очевидно, когда мы получим много нулей, то есть, когда изображение содержит длинные участки одинаковых значений яркости. Тогда все разности обнулятся. Это может быть, например, рентгеновский снимок, отсканированный документ.Говорят, что преобразование Хаара устраняет константную составляющую (она же — момент нулевого порядка), то есть переводит константы в нули.Но всё же в реальных фотографиях областей с одинаковой яркостью не так много. Попробуем усоврешенствовать преобразование, чтобы оно обнуляло ещё и линейную составляющую. Иными словами, если значения яркости будут увеличивать линейно, то они тоже обнулятся.Эту задачу и более сложные (устранение моментов более высоких порядков) решила Ингрид Добеши — один из создателей теории вейвлетов.
30.Вейвлеты. Принципы и применение вейвлета Добеши.Преобразование Добеши
Для нашего усовершенствованного преобразования уже будет мало двух точек. Поэтому будем брать по четыре значения, смещаясь каждый раз на два.То есть, если исходная последовательность — 1, 2, 3, 4, 5, 6,…, N-1, N, то будем брать четвёрки (1, 2, 3, 4), (3, 4, 5, 6) и т. д. Последняя четвёрка «кусает последовательность за хвост»: (N-1, N, 1, 2).Точно так же попробуем построить два фильтра: высокочастотный и низкочастотный. Каждую четвёрку будем заменять на два числа. Так как четвёрки перекрываются, то количество значений после преобразования не изменится.Для того, чтобы было удобно считать обратную матрицу потребуем также ортогональности преобразования. Тогда поиск обратной матрицы сведётся к транспонированиюПусть значения яркостей в четвёрке равны x, y, z, t. Тогда первый фильтр запишем в видеЧетыре коэффициента, образующих вектор-строку матрицы преобразования, пока нам неизвестны.Чтобы вектор-строка коэффициентов второго фильтра был ортогонален первому, возьмём те же коэффициенты но переставим их и поменяем знаки:Матрица преобразования будет иметь вид.Требование ортогональности выполняется для первой и второй строк автоматически. Потребуем, чтобы строки 1 и 3 тоже были ортогональны:Векторы должны иметь единичную длину (иначе определитель будет не единичным):Преобразование должно обнулять цепочку одинаковых значений (например, (1, 1, 1, 1)):Преобразование должно обнулять цепочку линейно растущих значений (например, (1, 2, 3, 4)):Получили 4 уравнения, связывающие коэффициенты. Решая их, получаем:Подставив их в матрицу, получаем искомое преобразования. После его применения к фотографиям получим больше нулей и малых коэффициентов, что позволит сжать изображение сильнее.Другая приятная особенность — артефакты после квантования будут не так заметны.Это преобразование получило название вейвлета D4 (читателю предлагается самостоятельно разгадать тайну этого буквенно-цифрового названия).
Другие вейвлеты
Мы, конечно, можем не остановиться на этом, и потребовать устранения параболической составляющей (момент 2-го порядка) и так далее. В результате получим вейвлеты D6, D8 и другие.Чтобы не считать всё вручную, коэффициенты можно посмотреть в википедии.Добеши открыла весьма интересный способ получения коэффициентов этих преобразований, но увы, это уже выходит за рамки нашей статьи.
31.Фильтрация контуров. Оператор Кэни.
Отдельный класс фильтров — фильтрация границ и контуров . Контуры очень полезны, когда мы хотим перейти от работы с изображением к работе с объектами на этом изображении. Когда объект достаточно сложный, но хорошо выделяемый, то зачастую единственным способом работы с ним является выделение его контуров. Существует целый ряд алгоритмов, решающих задачу фильтрации контуров:
Оператор КэнниОператор СобеляОператор ЛапласаОператор ПрюиттОператор РобертсаЧаще всего используется именно Кэнни, который хорошо работает и реализация которого есть в OpenCV (Собель там тоже есть, но он хуже ищёт контуры).
Оператор Кэнни (детектор границ Кэнни, алгоритм Кэнни; часто в другой транскрипции - Канну) в дисциплине компьютерного зрения — оператор обнаружения границ изображения. Был разработан в 1986 году Джоном Кэнни (англ. John F. Canny) и использует многоступенчатый алгоритм для обнаружения широкого спектра границ в изображениях.Кэнни изучил математическую проблему получения фильтра, оптимального по критериям выделения, локализации и минимизации нескольких откликов одного края. Он показал, что искомый фильтр является суммой четырёх экспонент. Он также показал, что этот фильтр может быть хорошо приближен первой производной Гауссианы. Кэнни ввёл понятие подавления немаксимумов (англ. Non-Maximum Suppression, которое означает, что пикселями границ объявляются пиксели, в которых достигается локальный максимум градиента в направлении вектора градиента.Хотя его работа была проведена на заре компьютерного зрения, детектор границ Кэнни до сих пор является одним из лучших детекторов. Кроме особенных частных случаев трудно найти детектор, который бы работал существенно лучше, чем детектор Кэнни.

Удаление слабых границДля чего используются два порога?1. Чтобы уменьшить влияние шума для инициализации кривой, используем верхний порог;2. Чтобы «не потерять хвост», используем нижний порог при прослеживании.

Поиск локальных максимумовПроверяя, является ли пиксель локальным максимумом вдоль направления градиента, приходится интерполировать «нецелые» пиксели p и r
Целью Кэнни было разработать оптимальный алгоритм обнаружения границ, удовлетворяющий трём критериям:
хорошее обнаружение (Канни трактовал это свойство как повышение отношения сигнал/шум);
хорошая локализация (правильное определение положения границы);
единственный отклик на одну границу.
Из этих критериев затем строилась целевая функция стоимости ошибок, минимизацией которой находится «оптимальный» линейный оператор для свёртки с изображением.
Алгоритм детектора границ не ограничивается вычислением градиента сглаженного изображения. В контуре границы оставляются только точки максимума градиента изображения, а не максимальные точки, лежащие рядом с границей, удаляются. Здесь также используется информация о направлении границы для того, чтобы удалять точки именно рядом с границей и не разрывать саму границу вблизи локальных максимумов градиента. Затем с помощью двух порогов удаляются слабые границы. Фрагмент границы при этом обрабатывается как целое. Если значение градиента где-нибудь на прослеживаемом фрагменте превысит верхний порог, то этот фрагмент остается также «допустимой» границей и в тех местах, где значение градиента падает ниже этого порога, до тех пор пока она не станет ниже нижнего порога. Если же на всем фрагменте нет ни одной точки со значением большим верхнего порога, то он удаляется. Такой гистерезис позволяет снизить число разрывов в выходных границах. Включение в алгоритм Кэнни шумоподавления с одной стороны повышает устойчивость результатов, а с другой — увеличивает вычислительные затраты и приводит к искажению и даже потере подробностей границ. Так, например, таким алгоритмом скругляются углы объектов и разрушаются границы в точках соединений.
Основные этапы алгоритмаСглаживание. Размытие изображения для удаления шума. Оператор Кэнни использует фильтр который может быть хорошо приближен к первой производной гауссианы.  = 1.4:

Поиск градиентов. Границы отмечаются там, где градиент изображения приобретает максимальное значение. Они могут иметь различное направление, поэтому алгоритм Кэнни использует четыре фильтра для обнаружения горизонтальных, вертикальных и диагональных ребер в размытом изображении.


Угол направления вектора градиента округляется и может принимать такие значения: 0, 45, 90, 135.

Направление градиента
Подавление немаксимумов. Только локальные максимумы отмечаются как границы.
Двойная пороговая фильтрация. Потенциальные границы определяются порогами.
Трассировка области неоднозначности. Итоговые границы определяются путём подавления всех краёв, несвязанных с определенными (сильными) границами.
Перед применением детектора, обычно преобразуют изображение в оттенки серого, чтобы уменьшить вычислительные затраты. Этот этап характерен для многих методов обработки изображений.
32.Фильтрация контуров. Оператор Собеля.Оператор Собеля используется в области обработки изображений. Часто его применяют в алгоритмах выделения границ. По сути, это дискретный дифференциальный оператор, вычисляющий приближенное значение градиентаяркости изображения. Результатом применения оператора Собеля в каждой точке изображения является либо вектор градиента яркости в этой точке, либо его норма. Оператор Собеля основан на свёртке изображения небольшими сепарабельными целочисленными фильтрами в вертикальном и горизонтальном направлениях, поэтому его относительно легко вычислять. С другой стороны, используемая им аппроксимация градиента достаточно грубая, особенно это сказывается на высокочастотных колебаниях изображения.
Упрощённое описание[править | править вики-текст]Если проще, то оператор вычисляет градиент яркости изображения в каждой точке. Так находится направление наибольшего увеличения яркости и величина её изменения в этом направлении. Результат показывает, насколько «резко» или «плавно» меняется яркость изображения в каждой точке, а значит, вероятность нахождения точки на грани, а также ориентацию границы. На практике, вычисление величины изменения яркости (вероятности принадлежности к грани) надежнее и проще в интерпретации, чем расчёт направления.
Математически, градиент функции двух переменных для каждой точки изображения (которой и является функция яркости) — двумерный вектор, компонентами которого являются производные яркости изображения по горизонтали и вертикали. В каждой точке изображения градиентный вектор ориентирован в направлении наибольшего увеличения яркости, а его длина соответствует величине изменения яркости. Это означает, что результатом оператора Собеля в точке области постоянной яркости будет нулевой вектор, а в точке, лежащей на границе областей различной яркости — вектор, пересекающий границу в направлении увеличения яркости.
Формализация[править | править вики-текст]Строго говоря, оператор использует ядра 3×3, с которыми сворачивают исходное изображение для вычисления приближенных значений производных по горизонтали и по вертикали. Пусть A исходное изображение, а Gx и Gy — два изображения, где каждая точка содержит приближенные производные по x и по y. Они вычисляются следующим образом:

где  обозначает двумерную операцию свертки.
Координата x здесь возрастает «направо», а y — «вниз». В каждой точке изображения приближенное значение величины градиента можно вычислить, используя полученные приближенные значения производных:
 (имеется в виду поэлементно)
Используя эту информацию, мы также можем вычислить направление градиента:

где, к примеру, угол Θ равен нулю для вертикальной границы, у которой тёмная сторона слева.
Строго говоря..[править | править вики-текст]Поскольку функция яркости известна только в дискретных точках, мы не можем определить производные до тех пор, пока не положим яркость дифференцируемой функцией, которая проходит через эти точки. С этой дополнительной предпосылкой производную дифференцируемой функции яркости можно вычислить как от функции, с которой взяты замеры — точки изображения. Оказывается, что производные в любой отдельной точке есть функции яркости от всех точек изображения. Однако приближения их производных можно определить с большей или меньшей степенью точности.
Оператор Собеля представляет собой более неточное приближение градиента изображения, но он достаточно качественен для практического применения во многих задачах. Точнее, оператор использует значения интенсивности только в окрестности 3×3 каждого пиксела для получения приближения соответствующего градиента изображения, и использует только целочисленные значения весовых коэффициентов яркости для оценки градиента…
Расширение на другое количество измерений[править | править вики-текст]Оператор Собеля состоит из двух отдельный операций [1]:
Сглаживание треугольным фильтром в перпендикулярном к производной направлении: 
Нахождение простого центрального изменения в направлении производной: 
Фильтры Собеля для производных изображения в разных пространствах для  :1D: 
2D: 
3D: 
4D: 
Вот пример трёхмерного ядра Собеля для оси z:

Технические детали[править | править вики-текст]Как следует из определения, оператор Собеля можно реализовать простыми техническими и программными средствами: для приближения вектор-градиента нужны только восемь пикселов вокруг точки изображения и целочисленная арифметика. Более того, оба дискретных фильтра, описанных выше, можно разделить:

и две производные, Gx и Gy, теперь можно вычислить как

Раздельность этих вычислений может привести к уменьшению арифметических действий с каждым пикселом.
Применение свертки K к группе пикселей P можно представить псевдокодом:
N(x, y) = Сумма { K(i, j).P(x-i, y-j)}, для i, j от −1 до 1.N(x, y) представляет собой результат применения матрицы свёртки K к P.
Программная реализация оператора Собела может эффективно использовать SIMD-расширения системы команд современных процессоров (т. н. векторизация кода), при этом выигрыш в скорости вычисления оператора может составлять до 5 раз по сравнению с высокоуровневой реализацией [2]. Ручное кодирование на языке ассемблера позволяет обогнать по скорости такие компиляторы как Microsoft Visual C++ и Intel C++ Compiler. Вычисление оператора Собела элементарно распараллеливается на произвольное число потоков (в пределе каждую точку результирующего изображения можно вычислять независимо от соседних). Например, при наличии двух процессоров (ядер) верхний полукадр изображения может быть обработан одним из них, а нижний — другим.
Примеры[править | править вики-текст]Результат применения оператора Собеля есть двумерная карта градиента для каждой точки. Её можно обработать и показать как картинку, на которой участки с большой величиной градиента (в основном, грани) будут видны как белые линии. Нижеприведённые изображения иллюстрируют это на примере простого изображения:

Полутоновое изображение кирпичной стены и стойки для велосипеда
Нормализованный Собелев градиент изображения кирпичной стены и стойки велосипеда

Нормализованный Собелев градиент изображения по x
Нормализованный Собелев градиент изображения по y
Оператор Щарра[править | править вики-текст]Оператор Собеля сглаживает паразитные эффекты на изображении, вызываемые чисто центрально-дифференциальным оператором, но не обладает полной вращательной симметрией. Щарр исследовал улучшение этого свойства и нашёл, что лучшие результаты даёт следующее ядро[3] [4]:

См. также33.Линейная пространственная фильтрация.






Часть 1. Фильтрация
В эту группу я поместил методы, которые позволяют выделить на изображениях интересующие области, без их анализа. Большая часть этих методов применяет какое-то единое преобразование ко всем точкам изображения. На уровне фильтрации анализ изображения не производится, но точки, которые проходят фильтрацию, можно рассматривать как области с особыми характеристиками. 
Маленькая ремарка. Далеко не всегда оптимальным будет тот критерий, который минимизирует ошибку. Следующий график — это график реальной системы распознавания по радужной оболочке. Для такой системы критерий выбирается такой, чтобы минимизировать вероятность ложного пропуска постороннего человека на объект. Такая вероятность называется «ошибка первого рода», «вероятность ложной тревоги», «ложное срабатывание». В англоязычной литературе «False Access Rate ».
Что делать если измерений больше двух?
Алгоритмов много. Даже очень много. Если хотите подробно узнать про каждый из них читайте курс Воронцова, ссылка на который дана выше, и смотрите лекции Яндыкса. Сказать, какой из алгоритмов лучше для какой задачи часто заранее невозможно. Тут я попробую выделить основные, которые в 90% помогут новичку с первой задачей и реализацию которых на вашем языке программирования вы достоверно найдёте в интернете.k-means (1, 2, 3 ) — один из самых простых алгоритмов обучения. Конечно, он в основном для кластеризации, но и обучить через него тоже можно. Работает в ситуации, когда группы объектов имеют неплохо разнесённый центр масс и не имеют большого пересечения.AdaBoost (1, 2, 3) АдаБуста — один из самых распространённых классификаторов. Например каскад Хаара построен именно на нём. Обычно используют когда нужна бинарная классификация, но ничего не мешает обучить на большее количество классов.SVM (1, 2, 3, 4 ) Один из самых мощных классификаторов, имеющий множество реализаций. В принципе, на задачах обучения, с которыми я сталкивался, он работал аналогично адабусте. Считается достаточно быстрым, но его обучение сложнее, чем у Адабусты и требуется выбор правильного ядра.Ещё есть нейронные сети и регрессия. Но чтобы кратко их классифицировать и показать, чем они отличаются, нужна статья куда больше, чем эта.________________________________________________Надеюсь, у меня получилось сделать беглый обзор используемых методов без погружения в математику и описание. Может, кому-то это поможет. Хотя, конечно, статья неполна и нет ни слова ни о работе со стереоизображениями, ни о МНК с фильтром Калмана, ни об адаптивном байесовом подходе.Если статья понравится, то попробую сделать вторую часть с подборкой примеров того, как решаются существующие задачки ImageRecognition.

Приложенные файлы

  • docx 24052510
    Размер файла: 3 MB Загрузок: 3

Добавить комментарий