Алгоритм стиснення даних JPEG
Кодування зображення по алгоритму JPEG виконується в декілька етапів. Починається воно з перетворення колірного простору з представлення RGB в представлення YUV, яке звичайне для телебачення. Компоненту Y є яскравістю, а U і V - цветоразності. Формули для перетворень RGB в YUV і назад такі:
RGB -> YUV:
Y = 0.299*red + 0.587*green + 0.114*blue
U = -0.147*Red - 0.289*green + 0.436*blue ~(BLUE-Y)/2
V = 0.615*red - 0.515*green - 0.100*blue; ~(Red -y)
YUV -> RGB:
Red = Y + 1.140*v
Green = Y - 0.396*u - 0.581*v
Blue = Y + 2.029*u.
Цей етап не погіршує якості зображення і не зменшує об'єм даних.
Система зору людини влаштована так, що набагато чутливіша до яскравості і менше чутлива до двох іншим компонентам. Тому повна і детальна інформація про яскравість навіть при значно біднішою кольоровості дозволяє отримати зображення цілком прийнятної якості. Ця особливість людського зору використовується в методі JPEG при визначенні "зайвої" інформації. Система стиснення зображення стискатиме компонент Y менший, ніж компоненти U і V, беручи до уваги, той факт що люди значно менше розрізняють зміну кольоровості, чим зміна яскравості.
На другому етапі проводиться проріджування даних кольоровості. При проріджуванні відкидаються дані з рядків або стовпців пікселів з певними номерами для компонентів цветоразностей. На яскравості проріджування ніяк не позначається. Тут вже відбувається безповоротна втрата даних, і, відповідно, зменшення їх об'єму, тим більше, ніж більше рядків і стовпців відкидається.
Наступний етап процедури стиснення даних полягає в перетворенні невеликих блоків кожній з компонент зображення дискретним косинусним перетворенням (ДКП), яке подібно до перетворення Фурье. Обробка проводиться блоками 8х8 пікселів (тобто обробляються відразу по 64 піксела). Такий розмір блоку був вибраний з кількох причин, в тому числі тому, що ділянка 8х8 достатньо великий і з великою достовірністю повинен містити піксели близького кольору. При виконанні цій операції інформація 64 початкових пікселів перетвориться в матрицю з 64 коефіцієнтами, які характеризують "енергію" початкових пікселів. Сенс перетворення ДКП, як і перетворення Фурье, полягає в визначенні частотних характеристик початкового сигналу. Для зображення це означає визначення переважних масштабів в нім присутніх. Оскільки в типових зображеннях зміни яскравості і кольору досить плавні, в них переважають низькі частоти, і в матриці коефіцієнтів ДКП значущі коефіцієнти згрупуються в лівому верхньому кутку. На цьому етапі об'єм даних залишається незмінним і втрат інформації практично немає.
Та обставина, що в отриманій матриці коефіцієнти сильно різняться по величині, наводить на думку відкинути ті з них, які значно менше останніх. Особливо, якщо пригадати, що коефіцієнти є відносними долями частот зміни сигналу, а не сам сигнал. Отже, якщо частка деякої частоти в сигналі мала, то її відкидання не приведе до помітного спотворення початкового сигналу. Саме це і виконується на наступному етапі - етапі квантування. Квантування означає ділення кожного з коефіцієнтів матриці на деяке число з
відкиданням дробової частини. При цьому кількість можливих градацій коефіцієнтів скорочується, а маленькі коефіцієнти звертаються в нуль. Для компонентів кольоровості квантування зазвичай виконується грубішим чим для яскравості. Саме на цьому етапі відбувається найбільш значна втрата інформації. Відкидаються невеликі зміни коефіцієнтів і звертаються в нуль маленькі коефіцієнти, які унаслідок ДКП групуються в правому нижньому кутку.
Квантування забезпечує можливість подальшого ефективного стиснення даних за допомогою будь-якого способу стиснення без втрат, яке виконується на останньому етапі. Причому, спочатку отримана матриця коефіцієнтів витягується в рядок так, щоб коефіцієнти, що залишилися ненульовими лівого верхнього кута опинилися на початку, а нульові коефіцієнти правого нижнього кута в кінці. Потім виконується стиснення даних методом групового кодування. Послідовність обходу матриці від лівого верхнього кута до правого ніжнего може бути, наприклад, такий:
1- 2 6- 7 15-16
/ / / / /
3 5 8 14 ...
|/ / /
4 9 13
/ /
10 12
|/
При відновленні зображень всі ці етапи виконуються в зворотному порядку. Тому для стиснення і відновлення даних методом JPEG необхідний однаковий об'єм обчислень.
Структура файлів JPEG
У розглянутих нами файлах старих форматів заголовки строго фіксовані. Для забезпечення можливості майбутніх розширень в них вводяться порожні місця, яких, проте, не завжди хапає. Подивитеся, наприклад, на заголовок файлу формату PCX. У нім було передбачено порожнє місце для розширень, але, коли знадобилося таке розширення зробити - додати палітру для 256-кольорових зображень, цього місця не вистачило. Довелося записувати палітру в кінці файлу, а порожнє місце так і залишилося "для подальших розширень".
Зараз заголовки файлів будуються гнучкіше. Причому порожніх місць "для
подальших розширень" в них немає зовсім. Всі дані, які записані в файл, включаючи і заголовок представляються у вигляді окремих записів або сегментів. Кожен сегмент має особлива ознака - маркер або ТЕГ (від англійського tag - ярлик). У сегменті визначається також його довжина і містяться специфічні для нього дані. Нові сегменти для забезпечення "подальших розширень" можуть додаватися дуже легко. Знадобилося записати у файл що-небудь нове - визнач новий маркер і пиши на здоров'я. Програми, які цю інформацію використовують, зможуть її знайти по введеному вами маркеру, а ті, яким вона не потрібна, просто пропустять цей сегмент, оскільки вони не знають цього маркера. Ніяких порожніх резервних
полів при цьому не потрібно.
Саме так будуються файли JPEG. Кожен з них містить декілька сегментів заголовка і один або декілька сегментів даних зображень. Маркер кожного сегменту файлу JPEG складається з двох байт, перший з яких - шістнадцятиричне "FF", а другою визначає тип маркера. Зараз визначено декілька десятків маркерів з номерами від "C0" і більше.
Файл починається маркером SOI ("Start Of Image" - Початок зображення) значення якого "FF D8", а закінчується маркером EOI ("End Of Image" - Кінець зображення) - "FF D9". Сегменти, помічені цими маркерами не містять ніякій інформації, тільки маркери. Інші сегменти інформацію містять і мають наступний загальний вигляд:
<FF> <маркер> <довжина (2 байти)> <дані (довжина-2 байта)>.
Відразу за маркером слідують 2 байти, що визначають довжину сегменту (включаючи їх самих і виключаючи маркер). Знати довжину сегменту потрібно для двох цілей:
1) для правильного прочитування даних сегменту і
2) для пропуску сегменту, який не потрібний даній програмі.
Звертаю вашу увагу на те, що байти в двобайтовому слові довжини записані в незвичному для РС порядку - спочатку старший, потім молодший.
Це пов'язано з тим, що формат JPEG створювався в першу чергу для "Макінтошів", але зроблений загальним для всіх комп'ютерів. Мак'овськие файли JPEG читаються на РС, і навпаки. Взагалі, всі двобайтові параметри у файлах JPEG записуються СТАРШИМ БАЙТОМ ВПЕРЕД.
Заголовок файлу JPEG
Отже, файл JPEG починається сегментом SOI. За ним слідує заголовок що складається з декількох сегментів, кількість яких не визначена. Порядок проходження для деяких сегментів заданий, для деяких довільний.
Першими сегментами заголовка повинні бути сегменти App0, порядок яких частково визначений: спочатку сегмент App0-jfif, за ним може слідувати сегмент App0-jfxx, а за ним інші сегменти App0, які специфічні для застосування.
Далі слідують сегменти з різними таблицями, необхідними для раськодірованія зображення: таблиця квантування, таблиця, що визначає стиснення, та інші. Можуть бути присутніми сегменти, вказуючі, яка програма створила зображення, і багато всякого іншого. Ми не будемо розглядати всі можливі сегменти - на це просто не вистачить часу. Розглянемо тільки ті, які містять найбільш загальну інформацію. Охочі розібратися докладніше можуть викачати з якого-небудь сервера FTP поточну версію пакету підтримки JPEG, який розповсюджується групою JPEG, і вивчити таблиці, що все є там.
Сегмент App0-jfif
Це обов'язковий перший сегмент заголовка. Він починається маркером "FF E0", за яким слідує двобайтова довжина сегменту. Як правило довжина цього сегменту 16 байт, але в подальших версіях вона може бути збільшена за рахунок додаткових даних. Оскільки ця довжина явно міститься в сегменті, її збільшення не позначиться на роботі старих програм.
Перші п'ять байт поля даних сегменту App0-jfif - це що закінчується нулем рядок рядок "JFIF" (4a 46 49 46 00). Це ідентифікатор формату файлу: "JPEG File Interchange Format" - формат переносимих файлів JPEG. Що означає JPEG ви вже знаєте. Слово "переносимих" означає, що файли такого формату можуть бути перенесені на будь-яку платформу без змін.
Далі слідують два байти, вказуючі версію стандарту JFIF. Старший (перший) байт указує головний номер, молодший (другий), - той, що після крапки. Так, наприклад, "01 02" означає версію 1.2.
Після цього в полі даних сегменту App0-jfif слідує інша інформація, про яку я тут не говоритиму.
Сегмент App0-jfxx
Цей сегмент, якщо він є, слідує відразу за сегментом App0-jfif. Він називається сегментом розширення. Цей сегмент також містить маркер App0 ("FF E0"), довжину, і дані. Перші п'ять байт поля даних сегменту – це рядок, що закінчується нулем, рядок "JFXX" (4a 46 58 58 00). Далі в полі даних цього сегменту записується зменшене зображення – так званий, THUMBNAIL ("ніготь великого пальця"), яке може використовуватися для швидкого перегляду картинки. Зображення Thumbnail може бути закодовано jpeg'ом або записано без кодування в 256-кольоровому або Truecolor'ном вигляді.
Специфічний сегмент App0
Відразу за сегментами App0-jfif і App0-jfxx може слідувати специфічний для застосування сегмент App0. Його поле даних винне починатися рядком, що закінчується нулем, який ідентифікує застосування. Зрозуміло, що цей рядок повинен бути відмінна від "JFIF" і "JFXX". Стандарт не рекомендує використовувати також родові назви такі як "кішка", "собака", "дерево" і тому подібне Коди всіх символів рядка повинні мати "0" в старшому біті, тобто їх значення повинні бути менше шістнадцятиричного "80". Це, зокрема, значить, що в рядку не можна використовувати російські букви.
У цьому сегменті може бути записана будь-яка інформація, яка потрібна застосуванню і не впливає на декодування зображення.
Якщо ви робите програму читання файлів JPEG, ви повинні передбачити можливість наявності в читаному файлі специфічних сегментів App0. Їх треба просто пропустити.
Сегменти SOF
Цими сегментами починаються власне зображення. Їх у файлі може бути декілька, хоча мені більше одного зустрічати не доводилося. SOF - це "Start of Frame" (Початок кадру). Маркери сегментів SOF мають значення від C0 до CF.
У полі даних сегменту SOF записуються:
1) розрядність даних (1 байт) - зазвичай рівна 8, але може бути також 12 або 16;
2) вертикальний розмір зображення (2 байти) (нагадаю - старший байт попереду);
3) горизонтальний розмір зображення (2 байти);
4) кількість компонент (1 байт) - рівне 3 для кольорових зображень і 1 для сірих;
5) масив структур з інформацією про компоненти (по 3 байти на кожну компоненту). Перший байт структури - номер компоненти. Другий - ступені проріджування по горизонталі (старший півбайт) і по вертикалі (молодший півбайт). Третій байт структури - номер таблиці квантування.
Сегмент SOS
Заголовок закінчується, а зображення починається сегментом SOS ("Start of Scan" - Початок розгортки), маркер якого - "FF DA". У полі даних цього сегменту міститься знову кількість компонент і деяка інша інформація про кожну компоненті. Відразу за цим сегментом без якого-небудь маркера слідують дані зображення, які закінчуються маркером EOI (End Of Image) - "FF D9".
Апроксимація кривих.
Роздивимось сукупність точок (xі,yi), яка взята на межі двохмірного об’єкту. Матимемо на увазі, що ці точки впорядковані, xі,yi та xі+1, yi+1 сусідні на межі об’єкта. Наша задача апроксимувати ці точки або кривою замкнутою або замкнутим многогранником. Існує різноманітні методи апроксимуваня. Роздивимось підхід, оснований на інтерактивному відборі кінцевих точок. Є точки і їх потрібно апроксимувати повільно. З’єднуємо кінці відрізків прямою, при цьому нам потрібно знайти порог. Якщо всі точки знаходяться на відстані меншій від порогу, то вважаємо, що ми знайшли ломану. Обираємо точку найбільш віддалену від відрізка і замінюємо відрізок двома ломаними. Далі процедуру повторюємо для кожного відрізка.