- •1. Представлення текстової інформації
- •2. Представлення графічної інформації
- •2.1. Растрова графіка
- •2.2. Методи растрування
- •4. Способи описання кольору
- •4.1. Моделі кольорів
- •4.2. Колірна модель cmyk та розділення кольорів
- •1. Теоретичні основи стиснення даних
- •2. Основні методи стиснення
- •2.1. Стиснення без втрати інформації
- •2.2. Стиснення з втратою інформації
- •3. Алгоритми стиснення без втрати інформації
- •3.1. Алгоритм rle
- •3.2. Коди Хафмана
- •4. Програмні засоби стиснення даних
- •5. Формати графічних даних
- •5.3. Різниця між форматом та алгоритмом стиснення
- •6. Автоматизована обробка документів
- •6.2. Вплив масштабування
- •1. Теоретичні відомості
- •1. Теоретичні відомості
- •1.1 Колір і методи опису кольору
- •1.1. Колірна модель rgb
- •1.3. Колірна модель cmyk та розділення кольорів
- •1.5. Формати графічних даних
- •4. Контрольні запитання
- •1. Теоретичні відомості
- •1.1. Параметри растрових зображень
- •1.2. Методи растрування
- •1.3. Параметри сканування.
- •1. Порядок виконання роботи
- •1.1. Сканування документа.
- •1.2. Перетворення зображення в текстовий документ.
- •1.3. Ручна сегментація документа.
- •1.4. Розрахунок лініатури растру.
- •1.5. Розрахунок роздільної здатності
- •1. Теоретичні відомості
- •1.1. Кодування
- •1.2. Декодування
- •1. Теоретичні відомості
- •1.1. Розмір біта даних на магнітному носії
- •1.2. Способи кодування даних
- •3 Питання з екзамена в якоїсь групи з попередніх років :
- •1)Приклади використання команд simd
- •2)Приклади використання кодів з корекцією помилок і пояснити принцип їх дії
- •3)Принципи архітектури numa–систем і smp–систем
- •1.Теоретичні відомості
- •1.1. Стандартні тести пк.
- •1.2. Деякі фактори, що впливають на швидкодію пк.
- •1.3. Організація роботи кеш-пам’яті.
- •1.1. Магнітні явища, на яких ґрунтується робота жорсткого диску.
- •1.2. Принцип запису інформації.
- •1.3. Принцип зчитування інформації.
- •1.4. Конструктивні елементи нагромаджувача на жорстких дисках.
- •1.5. Організація інформації на жорсткому диску.
- •1.6. Стандарти.
- •Теоретичні відомості
- •1.1. Принцип дії crt-монітору
- •1.2. Маски та їх основні типи
- •1.3. Особливості та переваги окремих типів трубок
- •1.4. Параметри монітору
- •Хід роботи
- •Теоретичні відомості
- •1.1. Динамічна і статична пам'ять.
- •1.2. Структура та призначення sram.
- •1.3. Структура та принцип дії динамічної пам'яті.
- •1.4. Типи динамічної пам'яті.
- •1.5. Специфікації модулів пам’яті.
- •1. Теоретичні відомості
- •1.1. Шинна архітектура
- •1.2. Чіпсети
- •1.3. Програмні засоби для забезпечення моніторингу
- •1.3.1. Core Temp
- •1.3.2. Hard Drive Inspector
- •1.3.3. HddScan
- •Теоретичні відомості
- •1.2.1. Системна шина
1. Теоретичні основи стиснення даних
Теоретичне підґрунтя стиснення інформації було розроблене Клодом Шенноном в кінці 40-х років 20 сторіччя. Його теорія трактує кількість І. як міру зменшення невизначеності відносно певного процесу за результатами спостереження за його реалізацією (зауважимо, що спостереження за відомим процесом не дає І.). З цього виходить, що потрібна міра невизначеності процесу.
Ця міра називається ентропія та оцінюється середньою несподіваністю реалізації процесу. Реалізація процесу тим більш несподівана, чим менше її ймовірність. Тому мірою ентропії могла би бути люба спадна функція цій ймовірності.
Якщо ми маємо символи
х1, х2,…, хN
з ймовірностями появлення
р1, р2,…, рN,
то мірою несподіваності отримання символу могла би бути величина 1/рN. Але при цьому несподіваність отримання повідомлення з декількох символів дорівнювала би добутку несподіваностей отримання окремих символів, а не їх сумі, що бажано з точки зору забезпечення адитивності міри інформації. Тому беруть логарифм log(1/рN)=-log рN, і тоді ентропія повідомлення дорівнює сумі ентропій символів:
log(1/ р1 р2)=-log p1 –logp2
Кількість інформації 1 отримаємо, якщо N=2, р1=р2=1/2 і основа логарифму 2, це і називається біт.
Кількість інформації в повідомленні з фіксованим алфавітом :
Н=р1 (log(1/ р1) + р2 (log(1/ р2)+….+ рN log(1/рN)
Н – середня кількість бітів (ентропія), яка необхідна для представлення одного символу;
рі – імовірність появи і-го символу
N – кількість символів.
Приклад:
Є 4 символи з ймовірностями
Р1=0.5 Р2=0.25 Р3=Р4=0.125
Н= - 0.5 log0.5 …… =1.75 біт
Що є надмірністю? Інтуїтивно зрозуміло, що невизначеність максимальна, якщо усі символи мають рівну ймовірність, 1/N. В нашому прикладі це 0.25, N=4. Тоді максимальна кількість інформації дорівнює
Hmax = log N.
Як можна бачити, співвідношення між Н та Нmax характеризує насиченість символу інформацією, а надмірність визначається як
R = 1-Н/Нmax
В нашому прикладі Нmax= 2, R=1-Н/Нmax=0.125
Стиснення інформації і відбувається за рахунок цієї надмірності, яка обумовлена нерівноймовірністю окремих (символів) повідомлень.
Крім того, це демонструє також, що в межах кожної моделі джерела інформації є теоретична границя стиснення, яку не можна перевищити без втрати інформації. Доведено також, що для любій послідовності даних можна побудувати оптимальний алгоритм (теорема Хафмана). Важливо, що все це вірно для певної моделі джерела інформації (якщо зображення представити як послідовність відрізків або блоків, це дасть різні оцінки).
2. Основні методи стиснення
Не зважаючи на велику кількість алгоритмів стиснення, їх можні розподілити на два великих класи:
Стиснення без втрати інформації
Стиснення з втратою інформації
2.1. Стиснення без втрати інформації
Надмірність усувається лише за рахунок зміни структури даних, тому такі методи є повністю зворотними, тобто із результуючого коду можна відтворити вихідні дані за допомогою зворотного методу. Це потрібно, якщо необхідне повне співпадання вихідних та відтворених даних (коди програм, текстова інформація). Характерні приклади форматів стиснення без втрати інформації: .ZIP, .ARJ, .RAR.