Идеята: два съседни пиксела
Съседните пиксели на снимката почти винаги си приличат: 100 и 101, 37 и 39. Ако ги нанесем като точки (x₁, x₂), облакът лежи по диагонала. Да завъртим осите на 45°: новите числа са „сумата“ y₁ и „разликата“ y₂. Почти цялата енергия отива в y₁, а y₂ е малко число около нулата – него можем да запишем грубо или изобщо да не го пазим.
корелация на съседите ρ = 0,97
ъгъл на завъртане θ = 45°
Преди: точките лежат по диагонала
двойка (x₁, x₂)
След завъртане: 98,4 % от енергията е в y₁
двойка (y₁, y₂)
Ляво – двойки съседни пиксели; дясно – същите след завъртане на θ. Най-много енергия в y₁ има точно при 45°. Намали корелацията ρ към 0 – облакът става кръг и никое завъртане не помага: печелим само защото съседите си приличат.
Пример: 100 и 101 → y₁ ≈ 142,1, y₂ ≈ 0,7; енергията 20 201 е същата. Без y₂ възстановяваме 100,5 и 100,5 – грешка 0,5, а пазим половината числа.
Ортогонални трансформации и базис
Завъртането се записва с матрица: Y = T·X. Ако матрицата е ортогонална, обратната е просто транспонираната – връщането е „безплатно“. Редовете ѝ са базисните вектори – шаблоните. Всеки коефициент yₖ казва „колко от k-тия шаблон има в сигнала“.
| Трансформация | Шаблоните | Защо се ползва |
|---|---|---|
| DCT (косинусна) | косинуси | почти оптимална; JPEG, MPEG, MP3 |
| DFT (Фурие) | комплексни синусоиди | спектър; комплексна |
| WHT (Уолш–Адамар) | стъпала ±1 | само събиране и изваждане – най-бърза |
| KLT (Карунен–Лоев) | собствени вектори на данните | оптимална, но зависи от данните |
По качество: KLT > DCT > DFT > WHT.
k = 0
k = 1
k = 2
k = 3
k = 4
k = 5
k = 6
k = 7
k = 0 е постоянен (средното), всеки следващ се люшка по-бързо. Смени на WHT: шаблоните са стъпала ±1, подредени по брой смени на знака.
Кодиране чрез трансформация
Трансформацията сама не компресира: N числа стават N числа. Компресира следващата стъпка – малките коефициенти се изхвърлят или записват с малко битове. Схемата: трансформация → квантуване → кодиране → … → обратна трансформация.
Думата „Здравей“ на блокове по 256 отчета: от всеки блок пазим само 24 най-големи коефициента с DCT – 10,7 пъти по-малко числа, SNR = 12,6 dB.
Входът: звукът, както е записан
входът x(n)
Изходът: звукът от малко коефициенти
изходът y(n)
С DCT и 24 от 256 думата се разбира ясно (≈ 10 пъти по-малко числа). Под ~8 звучи „металически“ – остават само няколко честоти във всеки блок. WHT при същия брой звучи по-зле: стъпалата не приличат на гласа. Така, но с по-хитра трансформация (MDCT) и модел на слуха, работи MP3.
пазим M = 8 от 64
шум = 0,05
Пазим 8 от 64 → компресия 8:1, PSNR = 17,1 dB
оригинал възстановен
|Y(k)|: запазените носят 91,2 % от енергията
изхвърлени запазени
Горе – сигналът и възстановеният от M коефициента; долу – коефициентите (червените са запазените). Правоъгълен сигнал: на WHT стига един коефициент, на DCT – много. Шумът се разпилява по всички коефициенти и не се компресира.
2D трансформация и JPEG
Снимката е двумерна: блок 8×8 се трансформира първо по редове, после по колони (разделимост). Резултатът са 64 коефициента F(u, v): горе вляво е DC – средната яркост, надясно и надолу – все по-фини шарки. При снимки почти цялата енергия е горе вляво.
Тук папагалът е нарязан на 24 × 24 блока и от всеки блок пазим 6 коефициента с DCT: 10,7 пъти по-малко числа, PSNR = … dB.
С 6 от 64 (≈ 10 пъти) разликата почти не се вижда. С 1 остава само DC – мозайка от квадратчета 8×8: така изглежда силно компресиран JPEG. Зоната губи ръбовете (клюна, перата), които праговото кодиране намира. WHT дава стъпаловидни блокове.
зона K = 4
Ляво – блок 8×8; среда – |F(u, v)| (по-синьо = по-голям); дясно – възстановеният. „Вертикален ръб“ има енергия само в първия ред – зоната го реже, праговото кодиране го пази.
Праговото кодиране в JPEG: (1) коефициентите под праг стават 0; (2) останалите се делят на таблица Γ(u, v) – голям делител за високите честоти; (3) закръгляне; (4) много нули → почти без битове. Пример: [620, 41, −12, 6, 3] с праг 5 и Γ = [16, 11, 10, 16, 24] → [38, 3, −1, 0, 0].
Бързи алгоритми
Директно умножение по матрица струва N² операции. Бързите алгоритми разлагат матрицата на log₂N прости стъпки от „пеперуди“ (a + b, a − b) – N·log₂N операции. При N = 1024 това е ≈ 100 пъти по-бързо. Бързата DCT за N = 8 (Arai–Agui–Nakajima) иска само 5 умножения вместо 64.
Самопроверка
1. Компресира ли сама по себе си DCT?
Не – N числа стават N числа. Компресира изхвърлянето и грубото квантуване на малките коефициенти.
2. Пиксели 100 и 101 – колко са y₁ и y₂ при завъртане на 45°?
y₁ ≈ 142,1, y₂ ≈ 0,7; енергията 20 201 се запазва.
3. Защо JPEG при силна компресия показва квадратчета?
Остава почти само DC на всеки блок 8×8 – блокът става равномерен, а съседните блокове имат различни средни.
4. WHT на [5, 5, 4, 4]?
С H(4) (без нормиране): [18, 0, 2, 0] – „средно“ и „една смяна по средата“.