Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Алгоритм стиску зображень JPEG




Алгоритм стиску, використовуваний у форматі зберігання зображень JPEG1)[49],побудований на використанні дискретного косинусного перетворення. Схема стиску в алгоритмі являє собою конвеєр, де дане перетворення - лише одна зі стадій (хоча, можливо, і найважливіша). Опишемо алгоритм, припускаючи, що на вхід дані 24-бітне зображення, значення атрибутів пикселей якого є елементами колірного простору RGB.

1. Переклад у колірний простір YCbCr (докладніше див. лекцію 1). Тут Y - компонента яскравості, Cb і Cr - компоненти кольоровості. Людське око більше чутливе до яскравості, чим до кольору. Тому важливіше зберегти більшу точність при передачі Y, чим при передачі Cb і Cr. Переклад здійснюється по наступній формулі:

зворотний переклад:

2. Субдискретизация компонент кольоровості. Після перекладу в колірний простір YCbCr здійснюється субдискретизация по наступних співвідношеннях: 4:4:4 (відсутність передискретизації), 4:2:2 (компоненти кольоровості міняються через одну по горизонталі), 4:2:0 (компоненти кольоровості міняються через одну по горизонталі; при цьому по вертикалі вони міняються через рядок). Проілюструємо докладніше дані співвідношення на прикладах. Будемо перетворювати блок 4 × 4 пикселя зображення:

1. Y00Cb00Cr00 Y01Cb01Cr01 Y02Cb02Cr02 Y03Cb03Cr03

2. Y10Cb10Cr10 Y11Cb11Cr11 Y12Cb12Cr12 Y13Cb13Cr13

3. Y20Cb20Cr20 Y21Cb21Cr21 Y22Cb22Cr22 Y23Cb23Cr23

4. Y30Cb30Cr30 Y31Cb31Cr31 Y32Cb32Cr32 Y33Cb33Cr33

тоді:

4:4:4. Cубдискретизированный блок буде таким же.

4:2:2. Cубдискретизированный блок буде таким:

Y00Cb00Cr00 Y01Cb00Cr00 Y02Cb02Cr02 Y03Cb02Cr02

Y10Cb10Cr10 Y11Cb10Cr10 Y12Cb12Cr12 Y13Cb12Cr12

Y20Cb20Cr20 Y21Cb20Cr20 Y22Cb22Cr22 Y23Cb22Cr22

Y30Cb30Cr30 Y31Cb30Cr30 Y32Cb32Cr32 Y33Cb32Cr32

4:2:0. Cубдискретизированный блок буде таким:

Y00Cb00Cr00 Y01Cb00Cr00 Y02Cb02Cr02 Y03Cb02Cr02

Y10Cb00Cr00 Y11Cb00Cr00 Y12Cb02Cr02 Y13Cb02Cr02

Y20Cb20Cr20 Y21Cb20Cr20 Y22Cb22Cr22 Y23Cb22Cr22

Y30Cb20Cr20 Y31Cb20Cr20 Y32Cb22Cr22 Y33Cb22Cr22

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

3. Застосування дискретного косинуса-перетворення. Зображення (точніше, отримані після субдискретизации компоненти) розбивається на блоки 8 × 8; до кожного блоку застосовується дискретне косинус-перетворення (окремо для компонентів Y, Cb і Сr). Якщо зображення не ділиться нацело на блоки 8 × 8, то додається відповідна кількість рядків і стовпців по безперервності.

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

де означає покомпонентное множення й узяття цілої частини, тобто Tij = [tijqij ], де tij - вихідні коефіцієнти ДКП, qij - компоненти матриці квантування, [] - операція узяття цілої частини. Таким чином, відбувається квантування області визначення коефіцієнтів вихідної матриці. Матриці квантування різні для компонентів кольоровості і яскравості.

На даній стадії можна задавати ступінь стиску шляхом зміни матриць квантування. Чим ближче до нуля елементи матриці квантування, тим менше буде діапазон значень елементів матриці Tij, а виходить, їх можна закодувати, затративши меншу кількість інформації. Наприклад, якщо елементи qij досить близькі до нуля, то більшість елементів Tij буде нулями.

Матриці квантування застережені в стандарті, а для зміни ступеня стиску їх множать на певний коефіцієнт. Очевидно, що втрати на цій стадії самі більші; якщо забрати занадто багато інформації з низькочастотних компонентів (тобто занадто сильно огрубіти компоненти), те з'являться артефакти: розпадання на квадрати 8 × 8, ефект Гиббса (виникнення ореола поруч із місцями різких колірних переходів) (див. мал. 14.3).

5. Зигзаг-упорядочивание. До кожної квантованной матриці застосовується так зване зигзаг-упорядочивание. Це особливий прохід матриці для одержання послідовності (див. мал. 14.4). Спочатку йде елемент T00, потім T01, T10, T11 . . . Причому для типових фотореалістичних зображень спочатку будуть іти ненульові коефіцієнти, що відповідають низькочастотним компонентам, а потім - безліч нулів.

6. Стиск методом RLE. Отримана послідовність кодується за допомогою модифікованого алгоритму групового кодування. Виводяться пари чисел: перше - число нулів, друге - значення після підпослідовності нулів. Наприклад, закодуємо таку послідовність:

122 0 125 0 0 44 0 0 0 0 -1.

Одержимо: (0, 122) (1, 125) (2, 44) (4, -1). Також існує спеціальний код для позначення того факту, що значення, що залишилися, у послідовності суть нулі.

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

 

Рис. 14.3. Артефакти JPEG. Угорі - вихідне зображення, унизу - зображення, стисле в 30 разів алгоритмом JPEG

 

Рис. 14.4. Зигзаг-упорядочивание

Алгоритм відновлення зображення суть інверсія вищенаведених дій. Ступінь стиску від 5 до 100 і більше раз (варіюється за допомогою матриць квантування й завдання методу субдискретизации). При цьому візуальна якість для більшості фотореалістичних зображень залишається на гарному рівні при стиску до 15 разів.

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

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


Поделиться:

Дата добавления: 2015-04-05; просмотров: 101; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты