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

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

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

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

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

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

Шаблон:Seealso

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

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

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

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

x (t) = \sum_{i} x (t_{i}) \frac{\sin \frac{ω_{d}}{2} (t - t_{i})}{\frac{ω_{d}}{2} (t - t_{i})},

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

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

x (t) = \sum_{i} x (t_{i}) h (t - t_{i}),

де $h (t)$ — імпульсна характеристика відповідного Шаблон:Нп. Вид цього фільтра вибирається в залежності від задачі.Шаблон:Sfn

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

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

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

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

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

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

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

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

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

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

1.1. Віконні Шаблон:Нп (Шаблон:Lang-en) — їх імпульсна характеристика

h (t)

отримується шляхом множення імпульсної характеристики ідеального ФНЧ на віконну функцію.

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

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

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

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

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

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

Шаблон:Main

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1. якщо

N

непарне:

{\begin{matrix} 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{matrix}

2.2. якщо

N

парне:

{\begin{matrix} y_{i} = x_{i} & 1 \leq i \leq \frac{N}{2} \\ y_{i} = \frac{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} = \frac{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{matrix}

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).

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

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

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

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

Пікселізація (Шаблон:Lang-en);
Дзвін (Шаблон:Lang-en);
Аліасинг (Шаблон:Lang-en) та пов'язаний з ним ефект муару;
Розмивання (Шаблон:Lang-en).

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

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

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

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

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

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

У статистиці

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

Див. також

Примітки

Шаблон:Примітки

Література

Посилання

[im-1] 1,0 ^1,1 ^1,2 Resize and Scaling на сайті програми ImageMagick. Шаблон:Ref-en

[2] Шаблон:Cite web

[upsamp-3] 3,0 ^3,1 Upsampling and interpolation, downsampling and decimation Шаблон:Недоступне посилання.

[4] Polyphase decimation filter.

[5] Polyphase interpolation filters.

[6] Interpolation, Decimation, and Rate Changing by Integer Fractions.

[7] Polyphase resampling with a rational factor.

[8] Interpolation using FFT Шаблон:Недоступне посилання.

[9] Мікросхема GC5016 від Texas Instruments Шаблон:Webarchive.

[10] Перетворювачі частоти дискретизації від Analog Devices Шаблон:Webarchive.

[11] Xilinx XAPP1113: Designing Efficient Digital Up and Down Converters

[12] Шаблон:Cite web

[13] Multirate DSP, part 3: ADC oversampling Шаблон:Webarchive.

[14] Theory of Upsampled Digital Audio.

[15] A complete guide to Foobar 2000

[16] Secret Rabbit Code (aka libsamplerate)

[17] Shibatch Audio Tools

[18] The SoX Resampler library

[19] Порівняння п'яти передискретизаторів для foobar2000 + ASIO4ALL Resampler (2011) Шаблон:Ref-ru

[20] Шаблон:Стаття. Шаблон:Ref-en

[21] Building a QAM Demodulator Шаблон:Недоступне посилання. Шаблон:Ref-en

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

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

Зміст

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