Русская Википедия:Передискретизация

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Decimation-aliasing.jpg
Иллюстрация эффекта наложения спектров (алиасинга) при уменьшении разрешения (децимации) растрового изображения. Сверху — изображение, уменьшенное без фильтрации. Снизу — изображение, уменьшенное с применением фильтра нижних частот.

Шаблон:Аудиостатья введение

Передискретиза́ция в обработке сигналов — изменение частоты дискретизации дискретного (чаще всего цифрового) сигнала. Алгоритмы передискретизации широко применяются при обработке звуковых сигналов, радиосигналов и изображений (передискретизация растрового изображения — это изменение его разрешения в пикселах).

Отсчёты сигнала, соответствующие новой частоте дискретизации, вычисляются по уже имеющимся отсчётам и не содержат новой информации.

Повышение частоты дискретизации называется интерполяцией, понижение — децимацией.Шаблон:Sfn

Общие принципы

Шаблон:Seealso

Файл:Signal-and-sinc.svg
Вычисление промежуточного отсчёта (в точке −0,5) дискретного сигнала с помощью идеального фильтра нижних частот. Синяя кривая — исходный непрерывный сигнал, зелёная — импульсная характеристика идеального ФНЧ. Для интерполяции суммируются значения импульсной характеристики в точках отсчётов, умноженные на величину соответствующих отсчётов.

Согласно теореме Котельникова, любой непрерывный сигнал с конечным спектром (то есть таким спектром, в котором спектральные составляющие, соответствующие частотам выше или равным некоторой частоты <math>f_0</math>, отсутствуют) может быть представлен в виде отсчётов дискретного сигнала с частотой дискретизации <math>f_d>2 f_0</math>. При этом такое преобразование является взаимно однозначным, то есть при соблюдении условий теоремы Котельникова по дискретному сигналу можно восстановить исходный сигнал с конечным спектром без искажений.Шаблон:Sfn

При передискретизации отсчёты сигнала, соответствующие одной частоте дискретизации, вычисляются по имеющимся отсчётам этого же сигнала, соответствующим другой частоте дискретизации (при этом предполагается, что обе частоты дискретизации соответствуют условиям теоремы Котельникова). Идеальная передискретизация эквивалентна восстановлению непрерывного сигнала по его отсчётам с последующей дискретизацией его на новой частоте.Шаблон:Sfn

Точное вычисление значения исходного непрерывного сигнала в определённой точке производится следующим образом:Шаблон:SfnШаблон:Sfn

<math>x(t)=\sum_i x(t_i) \frac{\sin \frac{\omega_d}{2}(t-t_i)}{\frac{\omega_d}{2}(t-t_i)},</math>

где <math>x(t_i)</math> — i-й отсчёт сигнала, <math>t_i</math> — момент времени, соответствующий этому отсчёту, <math>\omega_d=2 \pi f_d</math> — циклическая частота дискретизации, <math>x(t)</math> — интерполированное значение сигнала в момент времени <math>t</math>.

Функция <math>\frac{\sin \frac{\omega_d}{2}(t-t_i)}{\frac{\omega_d}{2}(t-t_i)}</math> не является финитной, поэтому для вычисления значения сигнала в определённый момент времени с помощью вышеприведённого выражения необходимо обработать бесконечное число его отсчётов (как в прошлом, так и в будущем), что нереализуемо на практике. В реальной жизни интерполяция осуществляется с помощью других фильтров, при этом выражение для неё принимает следующий вид:Шаблон:SfnШаблон:Sfn

<math>x(t)=\sum_i x(t_i) h(t-t_i),</math>

где <math>h(t)</math> — импульсная характеристика соответствующего восстанавливающего фильтра. Вид этого фильтра выбирается в зависимости от задачи.Шаблон:Sfn

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

  • децимация с целым коэффициентом (уменьшение частоты дискретизации в целое число раз);
  • интерполяция с целым коэффициентом (увеличение частоты дискретизации в целое число раз);
  • изменение частоты дискретизации в рациональное (<math>M/N</math>) число раз (этот случай можно рассматривать как комбинацию двух предыдущих).

При таких ограничениях становится удобным применение стандартных реализаций цифровых фильтров для передискретизации.

Передискретизация с помощью цифровых фильтров

Файл:Signal-decimation.svg
Иллюстрация алгоритма децимации дискретного сигнала (с коэффициентом 2). Красные точки обозначают отсчеты, сплошные линии — непрерывный сигнал, представлением которого эти отсчеты являются. Сверху — исходный сигнал. В середине — этот же сигнал после фильтрации в цифровом фильтре нижних частот. Снизу — децимированный сигнал.
Файл:Signal-interpolation.svg
Иллюстрация алгоритма интерполяции дискретного сигнала (с коэффициентом 2). Красные точки обозначают исходные отсчеты сигнала, сплошные линии — непрерывный сигнал, представлением которого эти отсчеты являются. Сверху — исходный сигнал. В середине — этот же сигнал со вставленными нулевыми отсчётами (зеленые точки). Снизу — интерполированный сигнал (синие точки — интерполированные значения отсчётов).

Выбор фильтра для передискретизации

Выбор функции <math>h(t)</math> обуславливается компромиссом между качеством передискретизации (то есть близости её к идеальной) и вычислительной сложностью этого процесса. В принципе, для передискретизации может быть использован любой фильтр нижних частот с необходимой частотой среза. КИХ-фильтры применяются для этих задач чаще, чем БИХ-фильтры, из-за возможности построения КИХ-фильтров с линейной фазо-частотной характеристикой.Шаблон:Sfn

Чаще всего при передискретизации используются следующие классы цифровых фильтров:Шаблон:Sfn

1. Фильтры, построенные, исходя из критерия близости частотной характеристики к частотной характеристике идеального фильтра нижних частот:

1.1. Оконные sinc-фильтры — их импульсная характеристика <math>h(t)</math> получается путём умножения импульсной характеристики идеального ФНЧ на оконную функцию,
1.2. Равноволновые фильтры Чебышёва.

2. Классические способы интерполяции функций (часто применяются для изображений)[1]:

2.1. Линейные интерполяторы,
2.2. Интерполяторы Лагранжа (частный случай — кубическая интерполяция).

3. CIC-фильтры (каскады гребёнчатых фильтров и интеграторов).[2] Этот класс фильтров не использует умножений при вычислении, что позволяет сэкономить вычислительные ресурсы.

Децимация с целым коэффициентом

Шаблон:Main

Процесс уменьшения частоты дискретизации сигнала называется децимацией.Шаблон:Sfn Иногда этот термин употребляют только для уменьшения частоты дискретизации в целое число раз (далее <math>N</math>).Шаблон:Sfn Децимация цифрового сигнала с целым коэффициентом производится в два этапа:Шаблон:SfnШаблон:Sfn

  1. Цифровая фильтрация сигнала с целью удаления высокочастотных составляющих, не удовлетворяющих условиям теоремы Котельникова для новой частоты дискретизации;
  2. Удаление (отбрасывание) лишних отсчетов (сохраняется каждый <math>N</math>-й отсчёт).

В англоязычной литературе второй из этих этапов иногда обозначают термином downsampling.[3] В обиходе этот термин может употребляться как синоним термина «децимация».

Первый этап необходим для исключения наложения спектров, природа которого аналогична наложению спектров при первоначальной дискретизации аналогового сигнала.Шаблон:Sfn Наложение спектров особенно заметно на тех участках сигнала, которые содержат значительные высокочастотные спектральные составляющие. Так, на приведённых в начале статьи фотографиях небо практически не подвергнулось наложению спектров, но эффект становится заметным, если обратить внимание на резкие переходы.

При программной реализации алгоритма децимации «лишние» отсчёты не удаляются, а просто не вычисляются. При этом число обращений к цифровому фильтру уменьшается в <math>N</math> раз. При аппаратной реализации экономии можно достичь путём использования полифазных фильтров.[4]

Интерполяция с целым коэффициентом

Интерполяцией называют увеличение частоты в целое или дробное число разШаблон:Sfn путём вычисления промежуточных отсчетов по уже имеющимся. Идеальная интерполяция позволяет точно восстановить значения сигнала в промежуточных отсчётах.

Стандартный алгоритм интерполяции сигнала с целым коэффициентом заключается в следующем:Шаблон:Sfn

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

В англоязычной литературе первый из этих этапов иногда обозначается термином upsampling.[3] При этом в обиходе этот термин может употребляться как синоним термина «интерполяция».

При программной реализации интерполяции нулевые отсчёты не участвуют в вычислении выходного сигнала фильтра, что позволяет оптимизировать процесс вычисления. При аппаратной реализации для экономии ресурсов возможно использование полифазных фильтров.[5]Шаблон:Sfn

Комбинация интерполяции и децимации

Для того, чтобы изменить частоту дискретизации сигнала в <math>\frac{M}{N}</math> раз (<math>M</math> и <math>N</math> — целые положительные числа), можно сначала увеличить частоту дискретизации в <math>M</math> раз, а затем уменьшить её в <math>N</math> раз. Фильтрацию сигнала достаточно произвести всего один раз — между интерполяцией и децимацией.Шаблон:Sfn

Недостатком данного метода является необходимость фильтрации сигнала на повышенной в <math>M</math> раз частоте дискретизации, что требует значительных вычислительных ресурсов. При этом соответствующая частота может во много раз превосходить как исходную, так и окончательную частоту передискретизации, особенно если <math>M</math> и <math>N</math> — близкие большие числа.[6] Так, например, при передискретизации звукового сигнала с 44100 Гц до 48000 Гц этим методом необходимо увеличить частоту дискретизации в 160 раз до 7056000 Гц и затем уменьшить её в 147 раз до 48000 Гц. Таким образом, в данном примере вычисления приходится производить на частоте дискретизации более 7 МГц.

Передискретизация с помощью полифазных фильтров

Метод передискретизации с помощью полифазных фильтров аналогичен предыдущему, с тем отличием, что в нём вместо одного фильтра, работающего на высокой частоте дискретизации, используется несколько фильтров, работающих на низкой частоте. При этом удаётся добиться сокращения количества необходимых вычислений, так как для каждого отсчёта необходимо вычислить выходной сигнал только одного из этих фильтров.Шаблон:SfnШаблон:Sfn

Полифазный фильтр представляет собой набор небольших фильтров, работающих параллельно, каждый из которых обрабатывает только подмножество отсчётов сигнала (если всего имеется <math>N</math> фильтров, каждый фильтр будет обрабатывать только каждый <math>N</math>-й отсчёт).

Полифазные фильтры применяются для передискретизации как с целым, так и с дробным коэффициентом.[7]

Передискретизация с помощью дискретного преобразования Фурье

Передискретизация с помощью ДПФ используется для повышения частоты дискретизации в целое или дробное число раз. Алгоритм работает только с конечными отрезками сигнала. Пусть <math>N</math> — начальное число отсчётов, <math>M</math> — число отсчётов в передискретизованном сигнале. Алгоритм включает в себя следующие операции:Шаблон:Sfn[8]

1. Вычисляется ДПФ исходного сигнала (чаще всего по алгоритму быстрого преобразования Фурье).

2. В середину спектра вставляется необходимое число нулевых компонент:

2.1. если <math>N</math> нечётное:
<math>\begin{cases} y_i=x_i & 1 \le i \le \frac{N+1}{2} \\ y_i=0 & \frac{N+1}{2}+1 \le i \le \frac{N+1}{2}+M-N\\ y_{i}=x_{i-M+N} & \frac{N+1}{2}+M-N+1 \le i \le M \end{cases} </math>
2.2. если <math>N</math> чётное:
<math>\begin{cases} y_i=x_i & 1 \le i \le \frac{N}{2} \\ y_i=\dfrac{x_{\frac{N}{2}+1}}{2} & i=\frac{N}{2}+1 \\ y_{i}=0 & \frac{N}{2}+2 \le i \le \frac{N}{2}+M-N \\ y_i=\dfrac{x_{\frac{N}{2}+1}}{2} & i=\frac{N}{2}+M-N+1 \\ y_i=x_{i-M+N} & \frac{N}{2}+M-N+2 \le i \le M \end{cases} </math>

3. Вычисляется обратное дискретное преобразование Фурье с нормировкой.

Любой метод, основанный на ДПФ, предназначен в первую очередь для периодических дискретных сигналов. Для обработки непериодических сигналов необходимо выбирать отрезки сигнала для вычисления ДПФ таким образом, чтобы их концы перекрывались.Шаблон:Sfn

Применения

Широко применяется как аппаратная (на основе специализированных микросхем[9][10] или FPGA[11]), так и программная (на базе процессоров общего назначения (см. ниже) или сигнальных процессоров[12]) реализация алгоритмов передискретизации.

Выбор конкретной реализации алгоритма передискретизации является результатом компромисса между качеством преобразования и его вычислительной сложностью. Основным параметром, влияющим на эти характеристики, является близость используемых цифровых фильтров к идеальным. Более качественные фильтры требуют больших ресурсов для вычисления.Шаблон:Sfn

На практике передискретизация в большинстве случаев ведёт к потере информации о сигнале по следующим причинам:

  • при уменьшении частоты дискретизации сигнал необходимо отфильтровать с целью удаления высокочастотных спектральных составляющих, которые не соответствуют условиям теоремы Котельникова для новой частоты дискретизации;
  • неизбежная неидеальность применяемых цифровых фильтров;Шаблон:Sfn
  • вычисления, производимые над цифровыми (квантованными по уровню) сигналами ведут к необратимым ошибкам округления.Шаблон:Sfn

Таким образом, при увеличении частоты дискретизации с последующим уменьшением её до исходного значения качество сигнала будет потеряно (если только высокая частота не кратна низкой).

Дискретизация сигналов с запасом по частоте дискретизации

Шаблон:Seealso

Дискретизация сигналов с запасом по частоте дискретизации (Шаблон:Lang-en) подразумевает дискретизацию сигнала на частоте, в несколько раз превышающей частоту Котельникова с последующей децимацией. Такой подход позволяет добиться следующих преимуществ[13]:

Аналогичный подход применяется и при восстановлении сигнала по его отсчётам для упрощения аналогового фильтра восстановления.[14]

При обработке звука

Оборудование, предназначенное для воспроизведения цифрового звука, как правило, рассчитано на вполне определённую частоту дискретизации сигнала непосредственно перед цифро-аналоговым преобразованием. Все звуковые сигналы с другими частотами дискретизации должны быть рано или поздно передискретизованы[15].

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

Существуют программные передискретизаторы звуковых сигналов с открытым исходным кодом:

  • SRC (Secret Rabbit Code) или libsamplerate[16] — существует плагин для foobar2000;
  • SSRC[17] — существуют плагины для Winamp и foobar2000.
  • SOXR[18] — качественный, быстрый, с минимальными требованиями к ресурсам[19]. Содержит библиотеку для замены SRC, подключается к foobar2000, используется в FFmpeg (с версии 1.1.1), Audacity и других проектах.

Также передискретизация поддерживается программами-редакторами звука (такими как Adobe Audition, Sony Sound Forge или Audacity).

При обработке изображений

Файл:Decimation-moire.png
Иллюстрация эффекта муара, вызванного наложением спектров при уменьшении разрешения изображения. Сверху — оригинал, снизу слева — изображение, уменьшенное в 2 раза без фильтрации, снизу справа — изображение, уменьшенное в 2 раза с фильтрацией.

Изменение разрешения является одной из распространённых операций обработки изображений. Передискретизация, приближенная к идеальной, не всегда является желательной. Наоборот, результаты работы фильтров с частотной характеристикой, далёкой от идеальной, могут визуально восприниматься как хорошие.[20] Выбор фильтра для передискретизации является результатом компромисса между типом и выраженностью артефактов и вычислительной сложностью преобразования (актуальной для приложений реального времени).

Типичные артефакты при изменении разрешения изображения:[1]:

Для передискретизации изображений применяется большое число фильтров, которые можно классифицировать следующим образом[1]:

  1. Фильтры интерполяционного типа, обладающие сравнительно узкой импульсной характеристикой. К ним относятся, в частности, треугольный фильтр, производящий билинейную интерполяцию и полином Лагранжа, с помощью которого можно реализовать бикубическую интерполяцию. Применение таких фильтров позволяет осуществить передискретизацию изображения достаточно быстро.
  2. Фильтры с колоколообразной характеристикой, такие как фильтр Гаусса. Эти фильтры хорошо справляются с пикселизацией, звоном и алиасингом, а также отфильтровывают высокочастотные шумы. Их недостаток — заметное размытие изображения.
  3. Оконные sinc-фильтры. Sinc-фильтр — это идеальный фильтр нижних частот. Как говорилось выше, он не может быть реализован. Однако если частотную характеристику sinc-фильтра умножить на оконную функцию, получится реализуемый фильтр с хорошими спектральными свойствами. При применении данных фильтров к изображениям удаётся сохранить относительно высокую чёткость (даже при увеличении разрешения), но может быть сильно заметен эффект звона. Одним из наиболее часто применяемых фильтров данного типа является фильтр Ланцоша.

Нижеприведённые изображения иллюстрируют применение наиболее часто используемых фильтров изменения размера изображений. При увеличении размера изображения без фильтра изображение получается чётким, но пикселизованным. При билинейной интерполяции пикселизация меньше заметна, но изображение размыто. При использовании фильтра Гаусса изображение размыто, но пикселизации практически не заметно. При использовании фильтра Ланцоша пикселизация отсутствует, изображение также размыто и заметен звон (видимый как светлая каёмка вокруг фигур).

При обработке радиосигналов

При демодуляции цифровых сигналов желательно, чтобы частота дискретизации сигнала была кратна его скорости манипуляции (иначе говоря, чтобы на каждый символ приходилось одинаковое число отсчётов сигнала). Однако частота дискретизации входного сигнала с АЦП, как правило, фиксирована, а скорость манипуляции может меняться. Решением является передискретизация сигнала.[21]

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Хорошая статья

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 1,2 Resize and Scaling Шаблон:Wayback на сайте программы ImageMagick.
  2. ↑ Шаблон:Cite web
  3. ↑ 3,0 3,1 Upsampling and interpolation, downsampling and decimationШаблон:Недоступная ссылка.
  4. ↑ Polyphase decimation filter Шаблон:Wayback.
  5. ↑ Polyphase interpolation filters Шаблон:Wayback.
  6. ↑ Interpolation, Decimation, and Rate Changing by Integer Fractions Шаблон:Wayback.
  7. ↑ Polyphase resampling with a rational factor Шаблон:Wayback.
  8. ↑ Interpolation using FFTШаблон:Недоступная ссылка.
  9. ↑ Микросхема GC5016 от Texas Instruments Шаблон:Wayback.
  10. ↑ Преобразователи частоты дискретизации от Analog Devices Шаблон:Wayback.
  11. ↑ Шаблон:Cite web
  12. ↑ Шаблон:Cite web
  13. ↑ Multirate DSP, part 3: ADC oversampling Шаблон:Wayback.
  14. ↑ Theory of Upsampled Digital Audio Шаблон:Wayback.
  15. ↑ Шаблон:Cite web
  16. ↑ Шаблон:Cite web
  17. ↑ Шаблон:Cite web
  18. ↑ Шаблон:Cite web
  19. ↑ Шаблон:Cite web
  20. ↑ Шаблон:Статья.
  21. ↑ Building a QAM DemodulatorШаблон:Недоступная ссылка.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Передискретизация&oldid=10576094