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

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

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

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

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

Загальні принципи

Див. також: Теорема Котельникова

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

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

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

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

${\displaystyle \,\!x(t)=\sum _{i}x(t_{i}){\frac {\sin {\frac {\omega _{d}}{2}}(t-t_{i})}{{\frac {\omega _{d}}{2}}(t-t_{i})}},}$

де ${\displaystyle x(t_{i})}$ — i-й відлік сигналу, ${\displaystyle t_{i}}$ — момент часу, який відповідає цьому відліку, ${\displaystyle \omega _{d}=2\pi f_{d}}$ — циклічна частота дискретизації, ${\displaystyle x(t)}$ — інтерпольоване значення сигналу в момент часу ${\displaystyle t}$.

Функція ${\displaystyle {\frac {\sin {\frac {\omega _{d}}{2}}(t-t_{i})}{{\frac {\omega _{d}}{2}}(t-t_{i})}}}$ не є ^[ru], тому для обчислення значення сигналу у певний момент часу з допомогою вищенаведеного виразу необхідно опрацювати нескінченну кількість його відліків (як у минулому, так і в майбутньому), що не може бути реалізованим на практиці. В реальному житті інтерполяція здійснюється з допомогою інших фільтрів, при цьому вираз для неї набуває такого вигляду:

${\displaystyle \,\!x(t)=\sum _{i}x(t_{i})h(t-t_{i}),}$

де ${\displaystyle h(t)}$ — імпульсна характеристика відповідного ^[en]. Вид цього фільтра вибирається в залежності від задачі.

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

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

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

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

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

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

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

Вибір функції ${\displaystyle h(t)}$ зумовлюється компромісом між якістю передискретизації (тобто близькості її до ідеальної) та обчислювальною складністю цього процесу. В принципі, для передискретизації може використовуватися будь-який фільтр нижніх частот з необхідною частотою зрізу. СІХ-фільтри (фільтри зі скінченною імпульсною характеристикою) застосовуються для цих задач частіше, ніж НІХ-фільтри (фільтри з нескінченною імпульсною характеристикою), через можливість побудови СІХ-фільтрів з лінійною фазо-частотною характеристикою.

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

1. Фільтри, побудовані, на основі критерію близькості частотної характеристики до частотної характеристики ідеального фільтру нижніх частот:

1.1. Віконні ^[en] (англ. windowed-sinc filters) — їх імпульсна характеристика ${\displaystyle h(t)}$ отримується шляхом множення імпульсної характеристики ідеального ФНЧ на віконну функцію.

1.2. Рівнохвильові фільтри Чебишова.

2. Класичні способи інтерполяції функцій (часто застосовуються для зображень):

2.1. Лінійні інтерполятори.

2.2. Інтерполятори Лагранжа (частковий випадок — кубічна інтерполяція).

3. ^[en] (англ. cascaded integrator-comb filters, каскади гребінчастих фільтрів та інтеграторів). Цей клас фільтрів не використовує множень при обчисленні, що дозволяє зекономити обчислювальні ресурси.

Децимація з цілим коефіцієнтом

Докладніше: Децимація (обробка сигналів)

Процес зменшення частоти дискретизації сигналу називається децимацією. Іноді цей термін вживають тільки для зменшення частоти дискретизації в цілу кількість разів (далі ${\displaystyle N}$). Децимація цифрового сигналу з цілим коефіцієнтом виконується у два етапи:

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

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

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

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

Інтерполяція з цілим коефіцієнтом

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

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

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

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

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

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

Для того, щоб змінити частоту дискретизації сигналу в ${\displaystyle {\frac {M}{N}}}$ разів (${\displaystyle M}$ та ${\displaystyle N}$ — цілі додатні числа), можна спочатку збільшити частоту дискретизації в ${\displaystyle M}$ разів, а потім зменшити її в ${\displaystyle N}$ разів. Фільтрацію сигналу достатньо здійснити всього один раз — між інтерполяцією та децимацією.

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

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

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

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

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

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

Передискретизація з допомогою ДПФ використовується для підвищення частоти дискретизації в цілу або дробову кількість разів. Алгоритм працює тільки зі скінченними відрізками сигналу. Нехай ${\displaystyle N}$ — початкова кількість відліків, ${\displaystyle M}$ — кількість відліків у передискретизованому сигналі. Алгоритм включає в себе такі операції:

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

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

2.1. якщо ${\displaystyle N}$ непарне:

${\displaystyle {\begin{cases}y_{i}=x_{i}&1\leq i\leq {\frac {N+1}{2}}\\y_{i}=0&{\frac {N+1}{2}}+1\leq i\leq {\frac {N+1}{2}}+M-N\\y_{i}=x_{i-M+N}&{\frac {N+1}{2}}+M-N+1\leq i\leq M\end{cases}}}$

2.2. якщо ${\displaystyle N}$ парне:

${\displaystyle {\begin{cases}y_{i}=x_{i}&1\leq i\leq {\frac {N}{2}}\\y_{i}={\dfrac {x_{{\frac {N}{2}}+1}}{2}}&i={\frac {N}{2}}+1\\y_{i}=0&{\frac {N}{2}}+2\leq i\leq {\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\leq i\leq M\end{cases}}}$

3. Обчислюється обернене дискретне перетворення Фур'є з нормуванням.

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

Застосування

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

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

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

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

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

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

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

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

• можливість використовувати простіший і дешевший аналоговий фільтр для захисту від накладання спектрів;
• можливість використовувати АЦП з меншою розрядністю.

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

При обробці звуку

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

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

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

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

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

При обробці зображень

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

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

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

• Пікселізація (англ. blocking);
• Дзвін (англ. ringing);
• Аліасинг (англ. aliasing) та пов'язаний з ним ефект муару;
• Розмивання (англ. blurring).

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

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

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

• Зображення, збільшене в 4 рази без фільтра
• Зображення, збільшене в 4 рази з білінійною інтерполяцією
• Зображення, збільшене в 4 рази з фільтром Гауса
• Зображення, збільшене в 4 рази з фільтром Ланцоша

При обробці радіосигналів

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

У статистиці

У статистиці ^[en] — це створення нових вибірок на основі однієї спостережуваної вибірки. Методи повторної вибірки: Перестановочні тести, Початкове завантаження, Перехресна перевірка.

Див. також

• Квантування (обробка сигналів)
• Дискретизація
• Дельта-модуляція
• Сигма-дельта-модуляція
• Аналогово-цифрове перетворення
• Цифро-аналоговий перетворювач
• Масштабування зображення

Примітки

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. . Архів оригіналу за 26 вересня 2007. Процитовано 8 жовтня 2015.
14. Лайонс, 2006, с. 382.
15. Crochiere та Rabiner, 1983, с. 31.
16. Upsampling and interpolation, downsampling and decimation^{[недоступне посилання з квітня 2019]}.
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^{[недоступне посилання з квітня 2019]}.
27. Романюк, 2005, с. 287.
28. Мікросхема GC5016 від Texas Instruments [ 21 жовтня 2010 у Wayback Machine.].
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 [ 2010-02-08 у Wayback Machine.].
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. з джерела 4 липня 2009. Процитовано 2015-10-08.. (англ.)
43. Building a QAM Demodulator^{[недоступне посилання з червня 2019]}. (англ.)

Література

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

Посилання

• Digital Signal Processing (Ohio State EE700).(англ.)
• Digital Audio Resampling Home Page.(англ.)
• Фільтри Фарроу (Farrow filters) на прикладі фільтра третього порядку. Ресемплінг (resampling) сигналів .(рос.)
• Digital Audio Resampling Home Page
• Multi-Rate Processing and Sample Rate Conversion: A Tutorial
• The Quest For The Perfect Resampler (PDF)
• Digital resampling by using polynomial interpolation. Farrow filter
• Using Farrow filter on the basis of piecewise cubic polynomial interpolation for digital signal resampling