6.2. Вплив масштабування

 

Це краще пояснити на прикладі. Припустимо, що відскановану марку розміром 1x1.5 in треба надрукувати розміром 2x3 на струйному принтері із роздільною здатністю 600 dpi. Якщо б сканування відбувалося при 600 dpi, відскановане зображення мало б 600 pixels по вертикалі (1 in на 600dpi) та 900 pixels по горизонталі (1.5 in на 600 dpi). Збільшення зображення до потрібного розміру 2x3 in зменшує ефективну роздільну здатність до 300 dpi, тому що 900 горизонтальних пікселів будуть розподілені на 3 in (900 розділити на 3 дорівнює 300), і так само по вертикалі. Це тільки половина роздільної здатності принтеру, і тому якість кінцевого зображення буде менше оптимальної. Щоб отримати найкращу якість друку, яка використовує 600 dpi цього струйного принтеру, треба сканувати зображення при 1200 dpi.

Подібний підрахунок необхідно зробити, якщо результуюче зображення менше оригіналу. Наприклад, треба відсканувати обкладинку розміром 4x5 in, щоб помістити її на Web сторінку із половинним розміром 2x2.5 in. Монітори ПК мають роздільну здатність 72 or 90 dpi. Сканування обкладинки при 72 dpi дає зображення  розміром 288x360 пікселів. Зменшення удвічі все одно дає роздільну здатність зображення 144 dpi по вертикалі, що удвічі більше, ніж треба. Тому оригінал можна було сканувати при 36 dpi без втрати якості в результуючому зображенні.

Ці міркування можна узагальнити таким чином:

 

SR = (DR x DW) / OW,

 SR – роздільна здатність при скануванні, dpi

 DR - роздільна здатність пристрою виводу, dpi

 DW –розмір зображення при друці або виводі на екран, inches

 OW – розмір оригіналу, inches

 

Кольорові зображення можна зчитувати за один або 3 проходи, як це випливає из моделі RGB.

 

Стиснення інформації за допомогою кодів

Хафмана 

 

Мета роботи: Ознайомитися з теоретичними основами стиснення даних та основними типами алгоритмів стиснення; вивчити принципи побудови кодів Хафмана; побудувати код Хафмана для вказаного джерела інформації.

 

1. Теоретичні відомості

 Кількість інформації в повідомленні з фіксованим алфавітом:

 

Н=р₁ log₂(1/ р₁) + р₂ log₂(1/ р₂)+….+ р_N log₂(1/р_N)

 

Н – середня кількість бітів (ентропія), яка необхідна для представлення одного символу;

р_і – імовірність появи і-го символу;

N – кількість символів.

 

Максимальна кількість інформації:

 

H_max = log₂ N

 

Надмірність джерела інформації:

 

R = 1-Н/Н_max

 

Коди Хафмана. Основні принципи:

• попередній статистичний аналіз джерела інформації (документа), щоб визначити ймовірності окремих символів (повідомлень);

• найбільш ймовірні символи представляють найбільш короткими  кодовими послідовностями, а найменш ймовірні – більш довгими;

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

 

Приклад.

Розглянемо двійкове кодування для джерела з 5 можливими повідомленнями:

Р₁=0.4         Р₂=0.35       Р₃=0.10       Р₄=0.10       Р₅=0.05

Н=1.94        Н_max=log₂ 5=2.32            R= 0.16

Для побудови коду Хафмана, спершу необхідно виписати елементи в порядку спадання ймовірностей (таблиця 1.1). Потім два найменш ймовірних елементи слід об’єднати в один набір, ймовірність якого дорівнює сумі ймовірностей елементів, що увійшли у нього. Аналогічно сортуємо й об’єднуємо елементи, розглядаючи вже отриманий набір як один елемент із відповідною ймовірністю, поки не отримаємо набір 5-и елементів із ймовірністю 1.

 

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

 

1 –     1

2 –     00

3 –     011

4 –     0100

5 –     0101

 

При цьому середня кількість бітів на символ буде дорівнювати:

 

Н = 1 × 0.4 + 2 × 0.35 + 3 × 0.10 + 4 × 0.10  + 4 × 0.05 = 2 біта

 

Код є префіксним, тобто початок коду не може співпасти з коротшим кодом (до кожного повідомлення на графі веде тільки один шлях). Ця властивість забезпечує зворотність кодування.

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

 

Формати стиснення графічних даних

 

Мета роботи: вивчити теоретичні основи стиснення даних; основні формати збереження графічних даних і галузі їх застосування; дослідити властивості форматів стиснення графічних даних та їх залежність від типу зображення.