Стиснення информации

М.Кононов © 2009 E-mail: [e-mail]
Загальні відомості про стиснення даних

М.Кононов © 2009 E-mail: [e-mail]
Загальні відомості про стиснення даних
 Термін стиснення даних (безвтратне) передба-чає зменшення об’єму даних для передачі того ж об’єму інформації
 Є типи інформації, які допускають часткове зменшення кількості інформації після відновлення - втрантість, як плата за високу ефективність стиснення даних
 Коефіцієнт стиснення визначається співвідно-шенням первинного та стисненого блоків даних
 Надлишковість даних

М.Кононов © 2009 E-mail: [e-mail]
Для стиснення інформації використовуються методи двох груп:
 Безвтратні методи (використовуються для довільного потоку бінарних даних, в тому числі і до графічного)
 Втратні методи, (використовуються для потоку бінарних даних, що мають інформацію, якою можна знехтувати) Такі методи можуть бути обтимізовані виходячи з особливостей типу даних (наприклад, акустичний сигнал, зображення)
Загальні відомості про стиснення даних

М.Кононов © 2009 E-mail: [e-mail]
Загальні відомості про стиснення даних
Надлишковість довільних даних визначається
 Нерівномірністю статистичного розпо-ділу значень пікселів
 Корельованістю окремих фрагментів даних
AABCBDCBBAAABBCCCCACCCAAACAAACD
A-12
B-6
C-11
D-2
AAAAAACDDAAACDAAAAAAAAAABBBBBB
AAADCAAACDDAAADCAAAAAAAAADCAAA

М.Кононов © 2009 E-mail: [e-mail]
Загальні відомості про стиснення даних

М.Кононов © 2009 E-mail: [e-mail]
Загальні відомості про стиснення даних
Критерій вірності відновлення

М.Кононов © 2009 E-mail: [e-mail]
Безвтратне стиснення

М.Кононов © 2009 E-mail: [e-mail]
Безвтратне стиснення
Групове стиснення

М.Кононов © 2009 E-mail: [e-mail]
Групове стиснення
Безвтратне стиснення
. PackBits для Apple Macintosh.
Перший байт -127 – -1 це кількість повторень, другий байт - значення.
Величини, що не повторюються кодуються таким чином: починаються з байту 0 – 127 – довжина коду, і далі послідовність байтів.
Стискання не переходить з одного рядка в інший

М.Кононов © 2009 E-mail: [e-mail]
Безвтратне стиснення
Групове стиснення
RLE - зображення складається з груп трьох видів- повторююча, літеральна, спеціальна.
 Повторююча - першій байт кількість пікселів, другий значення.
 Літеральна - перший 00, далі кількість пікселів у групі, дані літерала. Доповнюється нулями до парного (не менше трьох пікселів).
 Спеціальна - 00 00 -кінець рядка, 00 01 - кінець тіла зображення, 00 02 хх уу зміщення позиції.

М.Кононов © 2009 E-mail: [e-mail]
Метод Хафмана
Є представником так званих статистичних алгоритмів
Безвтратне стиснення
Кожному вхідному символу привласнюється визначений код, не вирівняний на довжину байту.
При цьому найбільше часто використо-вуваному символу привласнюється найбільш короткий код, а найбільш рідкому - більш довгий. Таблиці кодування створюються заздалегідь і мають обмежений розмір. Цей алгоритм забезпечує найбільшу швидкодію і найменші затримки.

М.Кононов © 2009 E-mail: [e-mail]
Метод Хафмана
Безвтратне стиснення

М.Кононов © 2009 E-mail: [e-mail]
Арифметичне кодування
Безвтратне стиснення

М.Кононов © 2009 E-mail: [e-mail]
LZW (Lempel-Ziv-Welch)
Даний метод припускає заміну потоку символів кодами, записаними в пам'яті як словник (таблиця перекодування). Співвідношення між символами і кодами міняється разом зі зміною даних.
Безвтратне стиснення
Таблиці кодування періодично міняються, що робить метод більш гнучким. Розмір невеликих словників лежить у межах 2-32 кілобайт, але більш високих коефіцієнтів стиснення можна досягти при помітно великих словниках - до 400 кілобайт.

М.Кононов © 2009 E-mail: [e-mail]
Втратне стиснення
2

Втратне стиснення
Алгоритм JPEG
М.Кононов © 2009 E-mail: [e-mail]

● поле зображення розбивається на квадратні блоки розміром 8х8 точок, для кожного з яких виконується дискретне косинусне перетворення (варіант переходу до площини просторових частот)
● Далі виконується перенормування амплітуд, отриманих на першому етапі просторових частот так, що більш ємні за інформацією компоненти (з меншими індексами) залишаються практично без втрат округлення, а високі гармоніки округлюються зі значним зменшенням кількості значущих цифр. Саме цей етап і є фактично єдиним втратним при препаруванні зображення
При втратному алгоритмі стиснення JPEG для «сірих» зображень
Алгоритм JPEG
Втратне стиснення
М.Кононов © 2009 E-mail: [e-mail]

Втратне стиснення
Алгоритм JPEG
М.Кононов © 2009 E-mail: [e-mail]

Втратне стиснення зображень
Алгоритм JPEG
Дискретне косинусне перетворення (DCT)
М.Кононов © 2009 E-mail: [e-mail]

Алгоритм JPEG
Втратне стиснення
М.Кононов © 2009 E-mail: [e-mail]

● Перенормовані дані в блоку перепози-ціануються таким чином, щоб сусідами в результуючому потоку були амплітуди, для яких сума індексів просторових частот мало відрізнялась
Втратне стиснення
Алгоритм JPEG
● Призначення перерахованих етапів фак-тично є високоефективною підготовкою даних за рахунок зміни їх розподілу за значеннями, тобто для дії безвтратних ентропійних алгоритмів, розглянутих раніше. Частіше за все використовується метод Хафмана або арифметичне стискання
М.Кононов © 2009 E-mail: [e-mail]

● Серед інших найвідоміших методів, можна назвати Wavelet. Цей метод розглядається як один із перспективних, перевищує JPEG за співвідношенням стиснення/якість, хоча значно програє за часом кодування, що дещо заважає його розповсюдженню на сучасному етапі.
● На відміну від розглянутого косинусного базису, цей метод використовує базис аперіодичних хвилькових функцій, які мають просторову обмеженість. Саме це більш повно враховує просторові особливості зображень і забезпечує більшу ефективність.
Втратне стиснення
Wavelet
М.Кононов © 2009 E-mail: [e-mail]

Київський національний університет імені Тараса Шевченка
14. Синтез зображень
М.Кононов © 2009 E-mail: [e-mail]
Комп’ютерна обробка
медичних зображень
М. Кононов

М.Кононов © 2009 E-mail: [e-mail]
Потреби використання комп’ютерного синтезу зображень

М.Кононов © 2009 E-mail: [e-mail]
Реалізація GUI
Використання комп’ютерного синтезу зображень
2D

М.Кононов © 2009 E-mail: [e-mail]
CAD
Використання комп’ютерного синтезу зображень
2D - 3D

М.Кононов © 2009 E-mail: [e-mail]
Відтворення результатів моделювання
Використання комп’ютерного синтезу зображень
3D

М.Кононов © 2009 E-mail: [e-mail]
Візуалізація досліджень
Використання комп’ютерного синтезу зображень
2D та 3D

М.Кононов © 2009 E-mail: [e-mail]
Сфера розваг (кіно)
Використання комп’ютерного синтезу зображень
Динамічна 3D

М.Кононов © 2009 E-mail: [e-mail]
Використання комп’ютерного синтезу зображень
Швидка Динамічна 3D

М.Кононов © 2009 E-mail: [e-mail]
Навчання та тренування з використанням віртуальної реальності
Використання комп’ютерного синтезу зображень
Швидка Динамічна 3D

М.Кононов © 2009 E-mail: [e-mail]
Реалізація 2D-графіки

М.Кононов © 2009 E-mail: [e-mail]
Реалізація 2D-графіки
Геометричні примитиви
 точка
 лінії
 відрізок прямої
 прямокутник
 багатокутник
 еліпс (дуга)
 фігури (з заповненням)
 прямокутник
 багатокутник
 еліпс (дуга)
 растрова область
 літера
 бітмеп

М.Кононов © 2009 E-mail: [e-mail]
Реалізація 2D-графіки
Атрибути геометричних примитивів
 координати (x0 ,y0); (x1 ,y1)
 колір лінії
 стиль лінії
 товщина лінії
 спосіб заповнення області

М.Кононов © 2009 E-mail: [e-mail]
3D-конвеєр

М.Кононов © 2009 E-mail: [e-mail]
3D-конвеєр
Процес переносу тривимірної сцени на площину має назву 3D конвеєра.
 Математичний опис тривимірної сцени
Незалежно від того, як він організован, можна віділити три головних етапи:
 Геометричні перетворенням
 Рендерінг

М.Кононов © 2009 E-mail: [e-mail]
3D-конвеєр
Опис тривимірної сцени

3D-конвеєр
Геометричні перетворення
Проеціювання
М.Кононов © 2009 E-mail: [e-mail]

3D-конвеєр
М.Кононов © 2009 E-mail: [e-mail]

3D-конвеєр
М.Кононов © 2009 E-mail: [e-mail]

М.Кононов © 2009 E-mail: [e-mail]
Опис сцени

М.Кононов © 2009 E-mail: [e-mail]
Опис сцени
Об’єкти в просторі можуть бути задані:
 як набір вокселів
 як поверхня

Воксель
М.Кононов © 2009 E-mail: [e-mail]
Во́ксель (Voxel) — від слів: об’ємний volumetric) і піксель (pixel). — це елемент об'ємного зображення, що містить значення елементу на регулярній гратці в тривимірному просторі, аналогічно пікселю у двомірному просторі
Нагадаємо

Опис сцени
Недоліки воксельного завдання
 Велика кількість елементів, що суттєво збільшує ресурсоємність математичної обробки
 Отримання поверхні все одно потрібно

Опис сцени
Полігональна модель
Як приклад (2D-аналогія) Наближення гладкої кривої за допомогою ламаної

Опис сцени
Полігональна модель

Полігони описуються у просторі наборами вершин (vertex)
1: v1, v2, v4
2: v2, v3, v4
. . .
12: v3, v9, v10
Опис сцени
Полігональна модель

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

М.Кононов © 2009 E-mail: [e-mail]
Геометричні перетворення

Геометричні перетворення
Проеціювання

М.Кононов © 2009 E-mail: [e-mail]
спостерігач
Геометричні перетворення

n1
θ1
n2
θ2
Геометричні перетворення
Видалення невидимих поверхонь

Геометричні перетворення

В буфер кадра отбирается точка с минимальным значением z-координаты.
Геометричні перетворення

М.Кононов © 2009 E-mail: [e-mail]
Геометричні перетворення
Рендерінг
(rendering) - візуалізація, відтво-рення (додавання характеристик поверхонь, геометрії освітлення, спецефектів, врахування прозорості).

М.Кононов © 2009 E-mail: [e-mail]
Геометричні перетворення
Рендерінг Гуро
Проста модель освітлення: дифузне відбиття

М.Кононов © 2009 E-mail: [e-mail]
Геометричні перетворення
Рендерінг Гуро
Проста модель освітлення: дзеркальне відбиття

М.Кононов © 2009 E-mail: [e-mail]
Геометричні перетворення
Рендерінг Гуро

М.Кононов © 2009 E-mail: [e-mail]
Геометричні перетворення
Рендерінг Гуро

М.Кононов © 2009 E-mail: [e-mail]
Складові реалістичності

М.Кононов © 2009 E-mail: [e-mail]
Складові реалістичності

М.Кононов © 2009 E-mail: [e-mail]
Складові реалістичності
 Об’ємні ефекти (заломлення)
 Тіні (з півтінями)
 Відбиття
 Текстури
 Реалістичність руху (для динамічної графіки)
 Спецефекти постобробки

Складові реалістичності
Відбиття
Текстури
Відтворення форми поверхні
Відтворення властивостей поверхні
Модель освітлення
Тіні (з півтінями)
Об’ємні ефекти (заломлення)
Перспективні спотворення
Спецефекти постобробки
М.Кононов © 2009 E-mail: [e-mail]

М.Кононов © 2009 E-mail: [e-mail]
Складові реалістичності
 Модель освітлення

М.Кононов © 2009 E-mail: [e-mail]
Складові реалістичності
 Динамічна графіка
 Статична графіка
 Інтерактивна графіка
Порівняння обмежень з ресурсоємності:

Використовуються поверхні другого порядку:
Ax2+ By2 + Cz2 + Dxy + Exz + Fyz + Gx + Hy + Jz + K=0
Статична модель
Аналітичні поверхні
М.Кононов © 2009 E-mail: [e-mail]

Поверхня довільної форми розділяється на шматки (patch), кожен з яких апроксімується бікубічною поверхнею із умови неперервності на стиках крім не тільки значення а й першої похідної
Статична модель
Бікубічні поверхні
М.Кононов © 2009 E-mail: [e-mail]

М.Кононов © 2009 E-mail: [e-mail]
Модель освітлення

М.Кононов © 2009 E-mail: [e-mail]
Модель освітлення
Модель освітлення Торренса-Сперроу

М.Кононов © 2009 E-mail: [e-mail]
Модель освітлення
Модель освітлення Торренса-Сперроу

М.Кононов © 2009 E-mail: [e-mail]
Відтворення властивостей поверхні
Модель матеріалу

М.Кононов © 2009 E-mail: [e-mail]
Нанесення текстур

М.Кононов © 2009 E-mail: [e-mail]
Нанесення текстур
Прості текстури
Текстура - Растрове зображення, що накладається на поверхню полігона для наданя їй кольору, ознаки матеріалу, імітації рельєфу
Тексель (Texture element) - мінаімальна одиниця текстури

М.Кононов © 2009 E-mail: [e-mail]
Трансляція текстури
Нанесення текстур

М.Кононов © 2009 E-mail: [e-mail]
Нанесення текстур
Прості текстури

М.Кононов © 2009 E-mail: [e-mail]
Нанесення текстур
Процедурні текстури

М.Кононов © 2009 E-mail: [e-mail]
Нанесення текстур
Об’ємні текстури (bump mapping)

- це програми, які виконує графічний процесор під час растерізації кожного пікселя коли виконується вибірка з текстур, операції з кольором та значенням глибини (Z). В результаті виконання щейдер видає значення кольору і модифіковане значення глибини для наступного етапу обробки
Забезпечує виконання мультітекстурування, (bump mapping), накладання карти освітлення (lightmap)
М.Кононов © 2009 E-mail: [e-mail]
Піксельні шейдери
Нанесення текстур

М.Кононов © 2009 E-mail: [e-mail]
Піксельні шейдери
Нанесення текстур
Приклад: текстура деревини без освітлення та з освітленням

М.Кононов © 2009 E-mail: [e-mail]
Нанесення текстур

М.Кононов © 2009 E-mail: [e-mail]
Побудова тіней

М.Кононов © 2009 E-mail: [e-mail]
Побудова тіней

М.Кононов © 2009 E-mail: [e-mail]
Побудова тіней
Створення списку неосвітлених полігонів
Подвійне використання Z-буферу

М.Кононов © 2009 E-mail: [e-mail]
Трасування променів

М.Кононов © 2009 E-mail: [e-mail]
Трасування променів

М.Кононов © 2009 E-mail: [e-mail]
Трасування променів

М.Кононов © 2009 E-mail: [e-mail]
Трасування променів

Київський національний університет імені Тараса Шевченка
15. Розпізнавання образів
М.Кононов © 2009 E-mail: [e-mail]
Комп’ютерна обробка
медичних зображень
М. Кононов

М.Кононов © 2009 E-mail: [e-mail]
Потреби використання розпізнавання образів

Потреби використання розпізнавання образів
Приклади використання:
 Введення друкованого тексту
 Введення рукописного тексту
 Аналіз зображень аеро- та космічної фотографії
 Комп’ютерний зір
М.Кононов © 2009 E-mail: [e-mail]
 Медичні та наукові застосування
 Розпізнавання облич (системи спостереження і внутрішньо-камерна обробка)
 Автентифікація

М.Кононов © 2009 E-mail: [e-mail]
Загальні принципи розпізнавання

М.Кононов © 2009 E-mail: [e-mail]
Загальні принципи розпізнавання
Приклад виявлення руху

М.Кононов © 2009 E-mail: [e-mail]
Загальні принципи розпізнавання
Співставлення з еталоном

М.Кононов © 2009 E-mail: [e-mail]
 Зменшення ресурсоємності подальшого аналізу
 Поліморфізм об’єктів
Загальні принципи розпізнавання
Необхідність використання простору ознак

М.Кононов © 2009 E-mail: [e-mail]
Загальні принципи розпізнавання

М.Кононов © 2009 E-mail: [e-mail]
Виділення ознак

М.Кононов © 2009 E-mail: [e-mail]
Виділення ознак
 Препарування
Основні етапи
 Виділення границь об’єктів (сегментація)
 Виділення ознак
 Аналіз ознак та їх зв’язків

М.Кононов © 2009 E-mail: [e-mail]
Виділення ознак
 Метричні
Типи ознак
 Топологічні
 Аналітичні
 Текстурні

М.Кононов © 2009 E-mail: [e-mail]
Виділення ознак
Набір параметрів, що характеризують розміри об’єкту
(метричні)

М.Кононов © 2009 E-mail: [e-mail]
Виділення ознак
Зв’язність
(топологічні)

М.Кононов © 2009 E-mail: [e-mail]
Виділення ознак
Сегментація форми
(топологічні)

М.Кононов © 2009 E-mail: [e-mail]
Виділення ознак
(топологічні)
Побудова остова

М.Кононов © 2009 E-mail: [e-mail]
(топологічні)

М.Кононов © 2009 E-mail: [e-mail]
Виділення ознак
Топологічні параметри
(топологічні)
 Топологічна еквівалентність
 Врахування зв’язності
 Модель “гумової стрічки”

М.Кононов © 2009 E-mail: [e-mail]
Виділення ознак
Опис елементів об’єкта аналітичними залежностями
(аналітичні)

М.Кононов © 2009 E-mail: [e-mail]
Виділення ознак
 Гістограмні (статистичні) ознаки текстури
Основні ознаки
(текстурні)
 Кількість перепадів яскравості в околі точки
 Особливості просторового спектру

М.Кононов © 2009 E-mail: [e-mail]
Використання нейронних мереж

М.Кононов © 2009 E-mail: [e-mail]
Використання нейронних мереж