Передискретизація

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Ілюстрація ефекту накладання спектрів (аліасингу) при зменшенні роздільності (децимації) растрового зображення. Зверху — зображення, зменшене без фільтрації. Знизу — зображення, зменшене із застосуванням фільтра нижніх частот.

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

Відліки сигналу, які відповідають новій частоті дискретизації, розраховуються на основі вже відомих відліків та не містять нової інформації.

Підвищення частоти дискретизації називається інтерполяцією, пониження — децимацією.[1]

Загальні принципи[ред. | ред. код]

Обчислення проміжного відліку (в точці −0,5) дискретного сигналу з допомогою ідеального фільтра нижніх частот. Синя крива — вихідний неперервний сигнал, зелена — імпульсна характеристика ідеального ФНЧ. Для інтерполяції підсумовуються значення імпульсної характеристики в точках відліків, помножені на величину відповідних відліків.

У відповідності до теореми Котельникова будь-який неперервний сигнал з фінітним[ru] спектром (тобто таким спектром, в якому спектральні складові, що відповідають частотам вище або рівним деякої частоти , відсутні) може бути поданим у вигляді відліків дискретного сигналу з частотою дискретизації . При цьому таке перетворення є взаємно однозначним, тобто при дотриманні умов теореми Котельникова за дискретним сигналом можна відновити вхідний сигнал з фінітним спектром без спотворень.[2]

При передискретизації відліки сигналу, які відповідають одній частоті дискретизації, обчислюються на основі відомих відліків цього ж сигналу, що відповідають іншій частоті дискретизації (при цьому вважається, що обидві частоти дискретизації відповідають умовам теореми Котельникова). Ідеальна передискретизація еквівалентна відновленню неперервного сигналу за його відліками з наступною дискретизацією його на новій частоті.[3]

Точне обчислення значення вихідного неперервного сигналу у певній точці виконується таким чином:[4][5]

де  — i-й відлік сигналу,  — момент часу, який відповідає цьому відліку,  — циклічна частота дискретизації,  — інтерпольоване значення сигналу в момент часу .

Функція не є фінітною[ru], тому для обчислення значення сигналу у певний момент часу з допомогою вищенаведеного виразу необхідно опрацювати нескінченну кількість його відліків (як у минулому, так і в майбутньому), що не може бути реалізованим на практиці. В реальному житті інтерполяція здійснюється з допомогою інших фільтрів, при цьому вираз для неї набуває такого вигляду:[6][7]

де  — імпульсна характеристика відповідного відновлювального фільтру[en]. Вид цього фільтра вибирається в залежності від задачі.[8]

Пряме обчислення нових відліків сигналу за вищенаведеними формулами потребує значних обчислювальних ресурсів і є небажаним для додатків реального часу. Існують важливі часткові випадки передискретизації, для яких обчислення нових відліків здійснюється простіше:[9]

  • децимація з цілим коефіцієнтом (зменшення частоти дискретизації у ціле число разів);
  • інтерполяція з цілим коефіцієнтом (збільшення частоти дискретизації у ціле число разів);
  • зміна частоти дискретизації в раціональну () кількість разів (цей випадок можна розглядати як комбінацію двох попередніх).

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

Передискретизація з допомогою цифрових фільтрів[ред. | ред. код]

Ілюстрація алгоритму децимації дискретного сигналу (з коефіцієнтом 2). Червоні точки позначають відліки, суцільні лінії — неперервний сигнал, представленням якого є ці відліки. Зверху — вихідний сигнал. Всередині — цей самий сигнал після фільтрації у цифровому фільтрі нижніх частот. Знизу — децимований сигнал.
Ілюстрація алгоритму інтерполяції дискретного сигналу (з коефіцієнтом 2). Червоні точки позначають вихідні відліки сигналу, суцільні лінії — неперервний сигнал, представленням якого є ці відліки. Зверху — вихідний сигнал. Всередині — цей самий сигнал зі вставленими нульовими відліками (зелені точки). Знизу — інтерпольований сигнал (сині точки — інтерпольовані значення відліків).

Вибір фільтра для передискретизації[ред. | ред. код]

Вибір функції зумовлюється компромісом між якістю передискретизації (тобто близькості її до ідеальної) та обчислювальною складністю цього процесу. В принципі, для передискретизації може використовуватися будь-який фільтр нижніх частот з необхідною частотою зрізу[en]. СІХ-фільтри (фільтри зі скінченною імпульсною характеристикою) застосовуються для цих задач частіше, ніж НІХ-фільтри (фільтри з нескінченною імпульсною характеристикою), через можливість побудови СІХ-фільтрів з лінійною фазо-частотною характеристикою.[10]

Найчастіше при передискретизації використовуються такі класи цифрових фільтрів:[11]

1. Фільтри, побудовані, на основі критерію близькості частотної характеристики до частотної характеристики ідеального фільтру нижніх частот:
1.1. Віконні sinc-фільтри[en] (англ. windowed-sinc filters) — їх імпульсна характеристика отримується шляхом множення імпульсної характеристики ідеального ФНЧ на віконну функцію.
1.2. Рівнохвильові фільтри Чебишова.
2. Класичні способи інтерполяції функцій (часто застосовуються для зображень)[12]:
2.1. Лінійні інтерполятори.
2.2. Інтерполятори Лагранжа (частковий випадок — кубічна інтерполяція).
3. CIC-фільтри[en] (англ. cascaded integrator-comb filters, каскади гребінчастих фільтрів та інтеграторів).[13] Цей клас фільтрів не використовує множень при обчисленні, що дозволяє зекономити обчислювальні ресурси.

Децимація з цілим коефіцієнтом[ред. | ред. код]

Процес зменшення частоти дискретизації сигналу називається децимацією.[1] Іноді цей термін вживають тільки для зменшення частоти дискретизації в цілу кількість разів (далі ).[14] Децимація цифрового сигналу з цілим коефіцієнтом виконується у два етапи:[10][15]

  1. Цифрова фільтрація сигналу з метою видалення високочастотних складових, що не задовільняють умовам теореми Котельникова для нової частоти дискретизації.
  2. Видалення (відкидання) зайвих відліків (зберігається кожен -й відлік).

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

Перший етап є необхідним для виключення накладання спектрів, природа якого аналогічна накладанню спектрів при початковій дискретизації аналогового сигналу.[15] Накладання спектрів є особливо помітним на тих ділянках сигналу, які мають значні високочастотні спектральні складові. Так, на наведених на початку статті фотографіях небо практично не піддалося накладанню спектрів, але ефект стає помітним, якщо звернути увагу на різкі переходи.

При програмній реалізації алгоритму децимації «зайві» відліки не видаляються, а просто не обчислюються. При цьому кількість звернень до цифрового фільтра зменшується в разів. При апаратній реалізації економії можна досягти шляхом використання поліфазних фільтрів[en].[17]

Інтерполяція з цілим коефіцієнтом[ред. | ред. код]

Інтерполяцією називають збільшення частоти в цілу або дробову кількість разів[1] шляхом обчислення проміжних відліків за вже відомими. Ідеальна інтерполяція дозволяє точно відновити значення сигналу в проміжних відліках.

Стандартний алгоритм інтерполяції сигналу з цілим коефіцієнтом полягає в такому:[18]

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

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

При програмній реалізації інтерполяції нульові відліки не беруть участі в обчисленнях вихідного сигналу фільтра, що дозволяє оптимізувати процес обчислення. При апаратній реалізації для економії ресурсів можна використовувати поліфазні фільтри.[19][20]

Комбінація інтерполяції та децимації[ред. | ред. код]

Для того, щоб змінити частоту дискретизації сигналу в разів ( та  — цілі додатні числа), можна спочатку збільшити частоту дискретизації в разів, а потім зменшити її в разів. Фільтрацію сигналу достатньо здійснити всього один раз — між інтерполяцією та децимацією.[21]

Недоліком даного методу є необхідність фільтрації сигналу на підвищеній в разів частоті дискретизації, що потребує значних обчислювальних ресурсів. При цьому відповідна частота може у багато разів перевищувати як вихідну, так і кінцеву частоту передискретизації, особливо якщо та  — близькі великі числа.[22] Так, наприклад, при передискретизації звукового сигналу з 44 100 до 48 000 Гц цим методом необхідно збільшити частоту дискретизації у 160 разів до 7 056 000 Гц і потім зменшити її в 147 разів до 48 000 Гц. Таким чином, в даному прикладі обчислення доводиться здійснювати на частоті дискретизації понад 7 МГц.

Передискретизація з допомогою поліфазних фільтрів[ред. | ред. код]

Метод передискретизації з допомогою поліфазних фільтрів[en] аналогічний до попереднього, з тією відмінністю, що в ньому замість одного фільтра, що працює на високій частоті дискретизації, використовується декілька фільтрів, які працюють на низькій частоті. При цьому вдається досягти зменшення кількості необхідних обчислень, оскільки для кожного відліку необхідно обчислити вихідний сигнал тільки одного з цих фільтрів.[20][23]

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

Поліфазні фільтри застосовуються для передискретизації як із цілим, так і з дробовим коефіцієнтом.[24]

Передискретизація з допомогою дискретного перетворення Фур'є[ред. | ред. код]

Передискретизація з допомогою ДПФ використовується для підвищення частоти дискретизації в цілу або дробову кількість разів. Алгоритм працює тільки зі скінченними відрізками сигналу. Нехай  — початкова кількість відліків,  — кількість відліків у передискретизованому сигналі. Алгоритм включає в себе такі операції:[25][26]

1. Обчислюється ДПФ вихідного сигналу (найчастіше з використанням алгоритму швидкого перетворення Фур'є).
2. В середину спектра вставляється необхідна кількість нульових компонент:
2.1. якщо непарне:
2.2. якщо парне:
3. Обчислюється обернене дискретне перетворення Фур'є з нормуванням.

Будь-який метод, що базується на ДПФ, призначений в першу чергу для періодичних дискретних сигналів. Для обробки неперіодичних сигналів необхідно вибирати відрізки сигналу для обчислення ДПФ таким чином, щоб їх кінці перекривалися.[27]

Застосування[ред. | ред. код]

Широко використовується як апаратна (на основі спеціалізованих мікросхем[28][29] або FPGA[30]), так і програмна (на базі процесорів загального призначення (див. нижче) або сигнальних процесорів[31]) реалізація алгоритмів передискретизації.

Вибір конкретної реалізації алгоритму передискретизації є результатом компромісу між якістю перетворення та його обчислювальною складністю. Основним параметром, що впливає на ці характеристики, є близькість використовуваних цифрових фільтрів до ідеальних. Якісніші фільтри потребують більших ресурсів для обчислення.[32]

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

  • при зменшенні частоти дискретизації сигнал необхідно відфільтрувати з метою видалення високочастотних спектральних складових, які не відповідають умовам теореми Котельникова для нової частоти дискретизації;
  • неминуча неідеальність застосовуваних цифрових фільтрів;[33]
  • обчислення, що виконуються над цифровими (квантованими за рівнем) сигналами призводять до необоротних похибок заокруглення.[34]

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

Дискретизація сигналів з запасом по частоті дискретизації[ред. | ред. код]

Див. також: Дискретизація

Під дискретизацією сигналів з запасом по частоті дискретизації (англ. oversampling) розуміють дискретизацію сигналу на частоті, яка в декілька разів перевищує частоту Котельникова з наступною децимацією. Цей підхід дає змогу отримати такі переваги[35]:

Аналогічний підхід застосовується і при відновленні сигналу за його відліками для спрощення аналогового фільтра відновлення.[36]

При обробці звуку[ред. | ред. код]

Обладнання, призначене для відтворення цифрового звуку, як правило, розраховане на цілком певну частоту дискретизації сигналу безпосередньо перед цифро-аналоговим перетворенням. Всі звукові сигнали з іншими частотами дискретизації повинні бути рано чи пізно передискретизовані[37].

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

Існують програмні передискретизатори звукових сигналів з відкритим початковим кодом:

  • SRC (Secret Rabbit Code) або libsamplerate[38] — існує плагін для foobar2000;
  • SSRC[39] — існують плагіни для Winamp та foobar2000.
  • SOXR[40] — якісний, швидкий, з мінімальними вимогами до ресурсів[41]. Містить бібліотеку для заміни SRC, підключається до foobar2000, використовується в FFmpeg (з версії 1.1.1), Audacity та інших проектах.

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

При обробці зображень[ред. | ред. код]

Ілюстрація ефекту муару, викликаного накладанням спектрів при зменшенні роздільності зображення. Зверху — оригінал, знизу зліва — зображення, зменшене у 2 рази без фільтрації, знизу справа — зображення, зменшене у 2 рази з фільтрацією.

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

Типові артефакти при зміні роздільності зображення[12]:

Для передискретизації зображень використовується велика кількість фільтрів, які можна класифікувати таким чином[12]:

  1. Фільтри інтерполяційного типу, що мають порівняно вузьку імпульсну характеристику. До них належать, зокрема, трикутний фільтр, що виконує білінійну інтерполяцію та поліном Лагранжа, з допомогою якого можна реалізувати бікубічну інтерполяцію[en]. Застосування таких фільтрів дозволяє здійснити передискретизацію зображення достатньо швидко.
  2. Фільтри з дзвоноподібною характеристикою, такі як фільтр Гауса. Ці фільтри добре справляються з пікселізацією, дзвоном та аліасингом, а також відфільтровують високочастотні шуми. Їх недоліком є помітне розмивання зображення.
  3. Віконні sinc-фільтри[en]. Sinc-фільтр — це ідеальний фільтр нижніх частот. Як зазначалося вище, він не може бути реалізованим. Однак якщо частотну характеристику sinc-фільтра помножити на віконну функцію[en], отримаємо фільтр з хорошими спектральними властивостями, який можна реалізувати. При застосуванні даних фільтрів до зображень вдається зберегти відносно високу чіткість (навіть при збільшенні роздільності), але може бути сильно помітним ефект дзвону. Одним з найчастіше використовуваних фільтрів цього типу є фільтр Ланцоша[en].

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

При обробці радіосигналів[ред. | ред. код]

При демодуляції цифрових сигналів бажано, щоб частота дискретизації сигналу була кратна його швидкості маніпуляції[ru] (інакше кажучи, щоб на кожен символ припадала однакова кількість відліків сигналу). Однак частота дискретизації вхідного сигналу з АЦП, як правило, є фіксованою, а швидкість маніпуляції може змінюватися. Вирішенням цієї проблеми є передискретизація сигналу.[43]

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. а б в Crochiere та Rabiner, 1983, с. 3
  2. Crochiere та Rabiner, 1983, с. 19
  3. Crochiere та Rabiner, 1983, с. 22
  4. Crochiere та Rabiner, 1983, с. 20
  5. Романюк, 2005, с. 136
  6. Crochiere та Rabiner, 1983, с. 21
  7. Романюк, 2005, с. 149
  8. Crochiere та Rabiner, 1983, с. 180
  9. Crochiere та Rabiner, 1983, с. 29
  10. а б Лайонс, 2006, с. 383
  11. Crochiere та Rabiner, 1983, с. 143
  12. а б в Resize and Scaling на сайті програми ImageMagick. (англ.)
  13. Understanding cascaded integrator-comb filters
  14. Лайонс, 2006, с. 382
  15. а б Crochiere та Rabiner, 1983, с. 31
  16. а б Upsampling and interpolation, downsampling and decimation.
  17. Polyphase decimation filter.
  18. Лайонс, 2006, с. 387
  19. Polyphase interpolation filters.
  20. а б Лайонс, 2006, с. 391
  21. Лайонс, 2006, с. 389
  22. Interpolation, Decimation, and Rate Changing by Integer Fractions.
  23. Crochiere та Rabiner, 1983, с. 79
  24. Polyphase resampling with a rational factor.
  25. Романюк, 2005, с. 233
  26. Interpolation using FFT.
  27. Романюк, 2005, с. 287
  28. Мікросхема GC5016 від Texas Instruments.
  29. Перетворювачі частоти дискретизації від Analog Devices.
  30. Xilinx XAPP1113: Designing Efficient Digital Up and Down Converters
  31. ADSP-21000 Family Applications Handbook (Vol 1.0)
  32. Лайонс, 2006, с. 181
  33. Crochiere та Rabiner, 1983, с. 33
  34. Рабинер та Гоулд, 1978, с. 327
  35. Multirate DSP, part 3: ADC oversampling.
  36. Theory of Upsampled Digital Audio.
  37. A complete guide to Foobar 2000
  38. Secret Rabbit Code (aka libsamplerate)
  39. Shibatch Audio Tools
  40. The SoX Resampler library
  41. Порівняння п'яти передискретизаторів для foobar2000 + ASIO4ALL Resampler (2011) (рос.)
  42. Don P. Mitchell, Arun N. Netravali. Reconstruction Filters in Computer Graphics. — Computer Graphics, 1988. — Т. 22, № 4. — С. 221—228.. (англ.)
  43. Building a QAM Demodulator. (англ.)

Література[ред. | ред. код]

  • Crochiere, Ronald E.; Rabiner, Lawrence R. (1983). Multirate digital signal processing. Prentice-Hall. с. 411. (англ.)
  • Лайонс, Ричард (2006). Цифровая обработка сигналов: второе издание = Understanding digital signal processing, 2nd edition. Бином-Пресс. с. 656. ISBN 5-951-80149-4. (рос.)
  • Рабинер, Л.; Гоулд, Б. (1978). Теория и применение цифровой обработки сигналов = Theory and Application of Digital Signal Processing. Москва: Мир. с. 848. (рос.)
  • Романюк, Ю.А. (2005). Основы цифровой обработки сигналов. В 3-х ч. Ч.1. Свойства и преобразования дискретных сигналов: Учебное пособие. Москва: МФТИ. с. 332. ISBN 5-74-170144-2. (рос.)

Посилання[ред. | ред. код]