йснюється за рахунок плавності зміни кольорів у зображенні.
Алгоритм розроблений групою експертів з фотографії спеціально для стиснення 24-бітових зображень. JPEG - Joint Photographic Expert Group - підрозділ у рамках ISO - Міжнародної організації зі стандартизації. Назва алгоритму читається [ jei peg]. В цілому алгоритм заснований на дискретному косинусоидальной перетворенні (надалі ДКП), вживаному до матриці зображення для отримання деякої нової матриці коефіцієнтів. Для отримання вихідного зображення застосовується зворотне перетворення.
ДКП розкладає зображення по амплітудах деяких частот. Таким чином, при перетворенні ми отримуємо матрицю, в якій багато коефіцієнти або близькі, або дорівнюють нулю. Крім того, завдяки недосконалості людського зору, можна апроксимувати коефіцієнти більш грубо без помітної втрати якості зображення.
Для цього використовується квантування коефіцієнтів (quantization). У найпростішому випадку - це арифметичний побітовий зрушення вправо. При цьому перетворенні втрачається частина інформації, але можуть досягатися великі коефіцієнти стиснення.
Як працює алгоритм
Отже, розглянемо алгоритм докладніше. Нехай ми стискаємо 24-бітове зображення.
Крок 1.
Переводимо зображення з колірного простору RGB, з компонентами, що відповідають за червону (Red), зелену (Green) і синю (Blue) складові кольору точки, в колірний простір YCrCb (іноді називають YUV).
У ньому Y - яркостная складова, а Cr, Cb - компоненти, що відповідають за колір (хроматичний червоний і хроматичний синій). За рахунок того, що людське око менш чутливий до кольору, ніж до яскравості, з'являється можливість архівувати масиви для Cr і Cb компонент з великими втратами і, відповідно, великими коефіцієнтами стиснення. Подібне перетворення вже давно використовується в телебаченні. На сигнали, що відповідають за колір, там виділяється більш вузька смуга частот.
Спрощено переклад з колірного простору RGB в колірний простір YCrCb можна представити за допомогою матриці переходу:
Зворотне перетворення здійснюється множенням вектора YUV на зворотну матрицю.
алгоритм стиснення архівація фрактальний
Крок 2.
Розбиваємо вихідне зображення на матриці 8х8. Формуємо з кожної три робочих матриці ДКП - по 8 біт окремо для кожної компоненти. При великих коефіцієнтах стиснення цей крок може виконуватися трохи складніше. Зображення ділиться за компоненті Y - як і в першому випадку, а для компонент Cr і Cb матриці набираються через рядок і через стовпець. Тобто з вихідної матриці розміром 16x16 виходить тільки одна робоча матриця ДКП. При цьому, як неважко помітити, ми втрачаємо 3/4 корисної інформації про колірних складових зображення і отримуємо відразу стиск у два рази. Ми можемо чинити так завдяки роботі в просторі YCrCb. На результуючому RGB зображенні, як показала практика, це позначається несильно.
Крок 3.
Застосовуємо ДКП до кожної робочої матриці. При цьому ми отримуємо матрицю, в якій коефіцієнти в лівому верхньому кутку відповідають низькочастотної складової зображення, а в правому нижньому - високочастотної.
У спрощеному вигляді це перетворення можна представити так:
де
Крок 4.
Виробляємо квантування. В принципі, це просто поділ робочої матриці на матрицю квантування поелементно. Для кожної компоненти (Y, U і V), в загальному випадку, задається своя матриця квантування q [u, v] (далі МК).
На цьому кроці здійснюється управління ступенем стиснення, і відбуваються найбільші втрати. Зрозуміло, що, задаючи МК з великими коефіцієнтами, ми отримаємо більше нулів і, отже, велику ступінь стиснення.
У стандарт JPEG включені рекомендовані МК, побудовані дослідним шляхом. Матриці для більшого чи меншого коефіцієнтів стиску отримують шляхом множення вихідної матриці на деяке число gamma.
З квантуванням пов'язані і специфічні ефекти алгоритму. При великих значеннях коефіцієнта gamma втрати в низьких частотах можуть бути настільки великі, що зображення розпадеться на квадрати 8х8. Втрати у високих частотах можуть проявитися в так званому ефекті Гіббса raquo ;, коли навколо контурів з різким переходом кольору утворюється своєрідний німб .
Крок 5.
Переводимо матрицю 8x8 в 64-елементний вектор за допомогою зигзаг -сканування, тобто беремо елементи з індексами (0,0), (0,1), (1,0), (2,0) ...
Таким чином, ...
