Кодування зображень

1.Цвет

Людське око складається приблизно з 7 млн. колб і 120 млн. паличок. Функція паличок полягає в "нічному зорі" - світлочутливості і пристосування до навколишнього яскравості. Функція колб - "денний зір" - сприйняття кольору, форми і деталей предмета. У них закладено три типи сприймають елементів, кожен з яких сприймає світлове випромінювання тільки певної довжини хвиль, що відповідають одному з трьох основних кольорів: червоного, зеленого і синього. Інші кольори і відтінки отримуються змішуванням цих трьох.

Людське око сприймає колірну інформацію в діапазоні хвиль приблизно від 380 нм (синій колір) до 770 нм (червоний колір). Причому найкращу чутливість має в районі 520 нм (зелений колір).

На малюнку показана чутливість очі в залежності від довжини приймається хвилі. Область частот, лівіше синьою - ультрафіолетові хвилі, правіше червоною - інфрачервоні хвилі.

Грассман привів закони природи кольору:

тривимірність природи кольору. Око реагує на три різних колірних складових. Приклади: червоний, зелений та синій кольори; колірний тон (домінуюча довжина хвилі), насиченість (чистоту) і яскравість (світлість).

Чотири кольори завжди лінійно залежні, тобто , де . Для суміші двох кольорів і має місце рівність: . Якщо колір дорівнює кольору і колір теж дорівнює кольором , то колір дорівнює кольором незалежно від структури спектрів енергії .

Кольоровий простір безперервно. Якщо в суміші трьох кольорів один безперервно змінюється, а інші залишаються постійними, то колір суміші буде змінюватися безперервно.

Розглянемо основні колірні моделі:

RGB.

Дана модель побудована на основі будови очі. Вона ідеально зручна для світяться поверхонь (монітори, телевізори, кольорові лампи і т.п.). В основі її лежать три кольори: Red-червоний, Green-зелений та Blue-синій. Ще Ломоносов помітив, що за допомогою цих трьох основних кольорів можна одержати майже весь видимий спектр. Наприклад, жовтий колір-це складання червоного і зеленого. Тому RGB називають аддитивной системою змішування кольорів.

Найчастіше дану модель представляють у вигляді одиничного куба з ортамі: (1; 0; 0) - червоний, (0; 1; 0) - зелений, (0; 0; 1) - синій і початком (0; 0 ; 0) - чорний. На малюнку показаний куб і також розподіл квітів уздовж зазначених векторів.

CMY.

Дана модель застосовується для відображають поверхонь (друкарських і принтерних фарб, плівок і т.п.). Її основні кольори: Cyan-блакитний, Magenta-пурпуровий та Yellow-жовтий є додатковими до основних кольорів RGB. Додатковий колір - різниця між білим і даних, наприклад, жовтий = білий - синій.

Тому CMY називають субтрактивной системою змішування кольорів. Наприклад, при пропущенні світла пурпурний об'єкт поглинається зелена частина спектра, якщо далі пропустити через жовтий об'єкт, то поглине синя частина спектру і залишиться лише червоний колір. Даний принцип використовують світлофільтри. На верхньому малюнку в колах - основні кольори системи RGB, на перетинах - їх можна сплутати. Аналогічним чином працюють з фарбами художники, формуючи необхідну палітру. На нижньому малюнку в колах - основні кольори CMY, на перетинах - змішання. Зв'язок між RGB і CMY можна виразити через наступну формулу:

Разом з системою CMY також часто застосовують і її розширення CMYK. Додатковий канал K (від англійського blacK) - чорний. Він застосовується для отримання більш "чистих" відтінків чорного. У кольорових принтерах найчастіше використовується чотири барвника. Дана система широко застосовується в поліграфії.

CIE.

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

За допомогою двох контрольних квітів можна отримати набагато більше кольорів, але не всі. Для отримання видимого набору квітів використовують три контрольних кольору, дотримуючись умову, що вони знаходяться в різних областях спектру. Розглянемо такий базис квітів:

R ed-червоний; лежить в області довгих видимих хвиль ( `700 нм).

G reen-зелений; лежить в області середніх видимих хвиль ( `546 нм).

B lue-синій; лежить в області середніх коротких хвиль ( `436нм).

Розглянемо колір C:

r, g, b-відносні кількості потоків базових кольорів, що входять в інтервал [0; 1]. Але даними складанням можна зрівняти не всі кольори. Наприклад, щоб отримати синьо-зеленого кольору об'єднуємо синій і зелений кольори потоки, але їх сума виглядає світліше, ніж необхідний. Якщо спробувати зробити його темніше за допомогою червоного, то отримаємо ще більш світлий результуючий колір, так як світлові енергії складаються. Тобто ми можемо додавати червоний, для отримання більш світлого зразка. Математично додавання червоного кольору до повчає кольору відповідає вирахуванню його з двох, що залишилися базових потоків (фізично це неможливо, так як негативної інтенсивності світла не існує). Запишемо рівняння таким чином:

На малюнку показані функції r, g, b рівняння за кольором для монохроматичні потоків кольору з довжиною хвиль 436, 546, 770 нм. З їх допомогою можна зрівняти всі довжини хвиль видимого спектру. На графіку присутня негативна область. Значення в даній області відповідають "додавання" інструментального кольору до синтезується. Вивченням даних функцій займається колориметр. Помічено, що один і той же колір можна отримати різними наборами базисних квітів (r1, g1, b1) і (r2, g2, b2). Тобто колір можна зрівняти різними складовими джерелами з неоднаковим спектральним розподілом. (r1, g1, b1) і (r2, g2, b2) - метамерів.

Уявімо колір С як вектор зі складовими rR, gG, bB. Перетин вектора C з одиничною площиною R + G + B = 1 дає відносні ваги його червоною, зеленою і синій складових. Їх також називають значеннями або координатами кольоровості:

Зауважимо, . Розглянемо зв'язок: . Якщо функції вирівнювання за кольором перенести в тривимірний простір, то результат не буде цілком лежати в позитивному Октант.

У 1931 був прийнятий стандарт CIE (Commission International de l'Eclairage - Міжнародна комісія з висвітлення), як основу якого був обраний двовимірний колірної графік і набір з трьох функцій реакції очі, що виключає негативній області і зручний для обробки. Гіпотетичні кольору CIE - X, Y і Z. Трикутник XYZ поставлено так, що в нього входить видимий спектр. Координати кольоровості CIE (x, y, z) задаються наступним чином:

і . При проектуванні трикутника XYZ на площину (x, y) отримуємо колірної графік CIE. Координати x і y - відносні кількості трьох основних кольорів XYZ, необхідних для складання потрібного кольору. Яскравість визначається величиною Y, а X і Y підбираються у відповідному масштабі. Таким чином, тріада (x, y, Y) задає колір. Зворотне перетворення має вигляд:

Комісія вирішила орієнтувати трикутник XYZ таким чином, що рівні кількості гіпотетичних основних кольорів XYZ давали в сумі білий. На малюнку зображено колірної графік. Область на графіку - видиме безліч квітів. На контурі проставлені значення відповідних довжин хвиль у нм, що відповідають чистим, не розведеним квітам. У центрі області знаходиться опорний білий колір - точка рівних енергій, з координатами x = y = 0.33 (3). Часто застосовують такі джерела CIE:

Назва

Температура

Лампа з вольфрамовою ниткою розжарювання.

2856К

0.448

0.408

Сонячне світло опівдні.

5600К

0.349

0.352

Полуденне освітлення при суцільній хмарності.

6300К

0.310

0.316

Опорний білий стандарт для моніторів і NTSC.

6400К

0.313

0.329

Система (x, y, Y) підкоряється законам Грассман. На малюнку показана колірна область графіка CIE. Як видно, найбільшу площу займають кольору з переважанням зеленого, що узгоджується з чутливою вибірковістю людського ока.

На колірному графіку CIE зручно демонструвати колірне охоплення різних систем і устаткування: телебачення, типографського друку, фотоплівок і т.п. Кольоровий обхват для адитивних систем - трикутник з вершинами, що відповідають основним кольорам RGB. Колір, який можна отримати в цiй колірної моделі лежить всередині трикутника, кольори, що лежать поза - отримати неможливо. Приклади колірних обхватів для деяких моделей можна побачити на малюнку. Зауважимо, що для кольорової плівки обхват є криволінійний трикутник. Причина цього полягає в нелінійному (в даному випадку логарифмічної) законі створення кольорового зображення за допомогою кольорової плівки. Нижче наведена таблиця основних кольорів моделей в координатах колірного графіка CIE:

Модель

Колір

CIE XYZ.

Червоний

Зелений

Синій

0.735

0.274

0.167

0.265

0.717

0.009

Стандарт NTSC.

Червоний

Зелений

Синій

0.670

0.210

0.140

0.330

0.710

0.080

Кольоровий монітор.

Червоний

Зелений

Синій

0.628

0.268

0.150

0.346

0.588

0.070

Координати кольоровості CIE представляють точний стандарт визначення кольору. Координати кольоровості CIE корисні при передачі інформації кольорів з однієї кольорової моделі в іншу. Тому необхідно знати перетворення координат CIE в інші колірні моделі, а також і назад. Наприклад, перетворення RGB - CIE XYZ задається наступною формулою:

, де - кольори для отримання координати одиничного основного кольору R, аналогічно і для G і B. Якщо відомі координати кольоровості CIE x і y для основних кольорів RGB, то:

, де:

- дані величини необхідні для повного перетворення між системами основних кольорів, також можна отримати і в такий спосіб:

Відомі - яскравості одиничних кількостей основних кольорів:

Відомий - координати кольоровості опорного білого і його Яскравість:

Зворотне перетворення CIE XYZ в RGB задається як:

, де c елементами:

YIQ.

Для стандарту кольорового телебачення NTSC було пред'явлено дві основних вимоги:

Бути в межах встановленого діапазону в 6 МГц,

Забезпечувати сумісність з чорно-білим телебаченням.

У 1953 була розроблена система YIQ:

Канал

Назва

займає діапазон

яскравість

4 МГц

синфазних

1.4 МГц

інтегрований

0.6 МГц

У каналі Y яскравість підібрана так, що вона відповідає колірній чутливості очі. Канал Y відповідає кольорам від блакитного до помаранчевого (теплих тонів). Канал Q - від зеленого до пурпурного. Як опорний білого був узятий джерело з температурою 6500К. Перетворення між кольоровими системами RGB і YIQ:

RGB в YIQ:

YIQ в RGB:

Крім YIQ зустрічаються й інші колірні моделі у форматі Яскравість, 1-ий колірний канал, 2-ий колірний канал. Наприклад, при колірної корекції використовують формат LAB, в якому:

L (ightness) - яскравість,

A-колірний канал несучий кольори від зеленого до червоного,

колірний канал, що відповідає за кольору у синьо-жовтому діапазоні.

HLS і HSB

Розглянемо інший підхід при описі кольору. У кольорі можна виділити його тон - переважає основний колір (довжину хвилі, що переважає в випромінюванні). Також розглянемо насиченість кольору - чим вона більша, тим "чистіше" колір (тобто ближче до тонової хвилі), наприклад, у білого кольору - насиченість = 0, тому що неможливо виділити його колірний тон. Введемо, нарешті, для завершення яскравість (у чорного кольору = 0, у білого = 1). Таким чином, ми побудували тривимірне колірний простір HSV - Hue, Saturation, Volume (Тон, Насиченість і Яскравість). Зазвичай його представляють у вигляді конуса, зображеного на малюнку. Початок координат - вершина конуса - чорний колір. Висота, спрямована до основи - яскравість. Точка перетину висоти з основою - білий колір. На висоті знаходяться відтінки сірого кольору від чорного (вершина конуса) до білого. На кола, що обмежує підставу конуса, знаходяться чисті колірні тони: від червоного (), через зелений (), до синього (). Радіус конуса - насиченість кольору. З такою системою працюють художники, міняючи насиченість за допомогою білої фарби, його відтінок за допомогою чорної і тон, комбінуючи з основними кольорами. HSV часто представляють і у вигляді шестигранного конуса, у якого в основі лежить правильний шестикутник з вершинами, що відповідають наступним кольорами: червоний - жовтий - зелений - блакитний - синій - пурпурний.

Наведемо формули зв'язку RGB та HSV, представленого у вигляді шестигранного конуса: HSV в RGB:

RGB в HSV:

RGB в HLS:

HLS в RGB:

Приклад перекладу RGB в HSB. У даному форматі RGB має на кожну з компонент R, G, B по 8 біт (256 рівнів градації) - True Color. HSB представлений трьома площинами, відповідними H, S, B, у вигляді чорно/білих зображень з 256 рівнями градації сірого.

Канали: Н - тон, S - насиченість, B - яскравість.

Деякі примітки до колірних моделей

При колірних перетвореннях необхідно також пам'ятати, що між кольоровими моделями CIE, CMY, RGB, YIQ існують афінних перетворення, тоді, як між HLS та HSV-ні. Дана обставина буде помітно, якщо зображення, що містить безперервні колірні переходи, перекладати, наприклад, з HLS в RGB (на зображеннях може з'явитися розрив безперервності).

2.Общая схема цифрової обробки зображень

Розглянемо процес обробки зображень у вигляді такої послідовності:

Отримання початкового, "сирого" зображення.

Фільтрація зображення.

Переклад зображення в необхідну колірну модель.

Форматування та індексування зображення.

Розбиття на блоки.

Обробка графічної інформації, що міститься в блоках.

Послідовне стиснення.

Ентропійно стиснення.

Цей поділ не претендує на повноту, але дає загальну картину процесу обробки. Деякі етапи, наприклад, 5, 7 або 8 можна пропустити. Перед кожним етапом, можливо, буде необхідна спеціальна фільтрація. Етап 3 ми розглянули у попередній частині. Інші етапи ми будемо розглядати не по порядку проходження, а у порядку зростання складності, щоб якомога рідше посилатися на матеріал наступних розділів.

Отримання початкового, "сирого" зображення.

Зображення для обробки умовно можна розбити на чотири класи:

Природні, отримані шляхом сканування, захоплення тілі або відео кадру, зйомкою цифровою апаратурою.

Зображення, намальовані з використанням графічного редактора на комп'ютері, назвемо їх комп'ютерними малюнками.

Тривимірні сцени, синтезовані за допомогою спеціальних програм, таких як: CAD'и (AutoCAD, ArchiCAD ...), 3D генератори (3D Studio, LightWave ...) і т.п.

Зображення - візуалізація даних, отриманих як результат деякого експерименту, досвіду, вимірів (енцефалограма, сейсмографічні карта ...).

Природничі зображення мають некомп'ютерні походження. У них майже немає різких колірних переходів. Комп'ютерні малюнки, як в іншому і будь-які інші, поділяються на два типи: растрові і векторні. У перші зображення зберігається як прямокутна матриця з елементами, що характеризують колірні складові. У векторних зображення - послідовність команд для його побудови. Приклад команди - коло з центром в точці (100,100) і радіусом 50, текстурований матеріалом під дерево. Перевага растрових - простота відтворення та реалістичність, недолік - великий займаний обсяг, проблеми з масштабуванням. У векторних навпаки, перевага - невеликий займаний об'єм, легкість масштабування, недолік - необхідність попередньої обробки перед відтворенням і труднощі створення реалістичних зображень. Тривимірні сцени винесені в окремий клас, так як в процесі їх створення (наприклад, прямої або зворотної трасуванням променя, методом излучательной) можна отримати додаткові дані (характеристики прямого та дифузного відбиття світла, заломлення ... об'єктів сцени) і використовувати їх при подальшій обробці . Зображення, як результат досвіду тощо необхідно обробити, з метою виявити його особливі характеристики, наприклад, виділити частину зображення що лежить в заданому спектрі і т.п. Надалі ми будемо розглядати в основному растрові зображення.

Форматування та індексування зображення.

У даному розділі будемо розглядати зображення як прямокутну матрицю A = (ai, j) з N стовпцями і M рядками, де N - ширина зображення в пікселях, M - висота зображення в пікселях. Розглянемо основні формати, які застосовуються в комп'ютерній обробці зображень:

Чорно-білий. Кожен елемент матриці представлений одним бітом. Якщо він дорівнює одиниці, то він ототожнюється з чорним кольором, якщо дорівнює нулю - з білим. Це самий простий формат, він застосовується при друку газет, розпізнаванні текстів і підписів.

Grayscale (градації сірого) . Відмінність даного формату від попереднього в тому, що для кожного елемента матриці відводиться 8 бітів (байт). Це дозволить нам використовувати 28 = 256 рівнів сірого кольору. Якщо ai, j = 0, то маємо білий колір, з зростанням до 255 ми будемо втрачати яскравість і при ai, j = 255 отримаємо чорний колір. У проміжку від 0 до 255 будуть розташовуватися сірі кольори за правилом: чим ближче значення до 255, тим чорніше буде сірий. Даний формат дозволяє отримувати досить якісні чорно-білі зображення. Значення ai, j містять зворотний яскравість, тобто значення (1 - L) * 255, де L - яскравість, яка може бути отримана, наприклад з RGB колірних зображень за формулою:

L = aR + bG + cG,

де R, G, B лежать в інтервалі [0; 1], а ваги a, b, c в сумі дають одиницю.

Іноді, для зберігання grayscale зображень використовують на точку 4-7 і 16 бітів. У такому випадку ми маємо 16-128 або 65536 відтінків сірого кольору.

Багатоканальні. В даному випадку ai, j представлений у вигляді вектора з координатами використовуваної колірної моделі. Зазвичай вектор тривимірний, тому що природа очі реагує на три різних колірних складових. Кожен компонент вектора найчастіше займає байт. Розглянемо найбільш поширені багатоканальні формати:

Назва

Співвідношення біт

1-ий компонент

2-ий компонент

3-ий компонент

RGB - Truecolor

8:8:8

Красний0-255

Зелений0 .. 255

Сіній0-255

RGB - Highcolor

5:6:5/5:5:5

Красний0-31

Зелений0.63/31

Сіній0-31

RGB - Extended

12:12:12/16:16:16

Червоний 0-4095/0-65535

Зелений 0-4095/0-65535

Сіній0-4095/0-65535

CMY

8:8:8

Голубой0-255

Пурпур0-255

Желтий0-255

LAB

8:8:8

Яркость0-255

Канал A 0-100%

Канал B 0-100%

YIQ

8:8:8

Яркость0-255

синфазних 0-255

Інтегрований 0-255

HLS

8:8:8

Тон 0-3600

Яркость0-100%

Насиченість 0-100%

HSB

8:8:8

Тон 0-3600

Насиченість 0-100%

Яркость0-100%

Зустрічаються чотирьох і більше мірні вектора, наприклад, модель CMYK, вона застосовується, коли є чотири основних колірних барвника. Двовимірні моделі називають дуплекс. Їх застосовують в поліграфії, наприклад, при друку стандартного grayscale зображення, реально в промисловості воно буде виконано лише в ~ 50 градації сірого, і для підвищення числа градацій вводять другий фарбу.

Індексований. Для зменшення обсягів зображення або для використання певних кольорів використовують даний формат. Елемент матриці ai, joman "> є покажчиком на таблицю кольорів. Число використовуваних квітів одно 2K, де K - кількість біт, що використовується для зберігання елемента матриці. Кольори в яку йдеться таблиці можуть кодуватися іншим числом біт. Наприклад, в 256 колірних режимах відеоадаптерів вибирається 256 кольорів з 262144 можливих, тому що обрані кольору представляються в RGB форматі і для кожної колірної компоненти кодується 6-ма бітами. Існує багато методів перетворення багатоканальних зображення в індексовані (Error diffusion, найближчого кольору ...).

Фільтрація зображення.

Поняття фільтрації в даному випадку досить велике, і включає в себе будь-яке перетворення графічної інформації. Фільтрація може бути задана не тільки у вигляді формули, але і у вигляді алгоритму, його реалізує. Людина запам'ятовує графічну інформацію, в основному, у вигляді трьох її складових

Низькочастотні складові зображення. Вони несуть інформацію про локалізацію об'єктів, що складають зображення. Ця складова найбільш важлива, тому що зв'язка очей - мозок їй приділяє першорядну увагу.

Високочастотні складові зображення. Вони відповідають за колірні перепади - контури зображення. Збільшуючи їх, ми підвищуємо різкість зображення.

Текстура зображення. Щоб зрозуміло пояснити, що це таке проведемо невеличкий експеримент. Розслабтеся, згадайте інтер'єр вашого будинку, наприклад, письмовий стіл. Ви знаєте його обриси, місце розташування, колір - це низькочастотні характеристики, згадали його загострені кути, невелику подряпину де-небудь ближче до його краю - це високочастотні складові. Також Ви знаєте, що стіл дерев'яний, але не можете в точності розповісти про всі найдрібніших деталях його поверхні, хоча загальні характеристики (коричневий з темними западинами, дві області розбіжності концентричних еліпсів від сучків) - напевно. В даному випадку в дужках - опис текстури. Можна трактувати текстуру як характеристику ділянок в контурах зображення.

Будемо розглядати фільтри у вигляді квадратної матриці A. Нехай вихідне зображення X, а одержана як результат фільтрації - Y. Для простоти будемо використовувати матриці 3x3:

рекурсивними фільтрами першого роду будуть такі фільтри, вихід Y яких формується перемножуванням вагових множників A з елементами зображення X. Для прикладу розглянемо фільтри низьких частот:

Фільтром низьких частот користуються часто для того, щоб придушити шум у зображенні, зробити його менш різким. Використовуючи фільтр A3, будемо отримувати зображення Y наступним чином:

Вихід фільтра другого роду формується аналогічно першому, плюс фільтра B:

Для простоти розглянемо одновимірний фільтр види: :

Розглянемо і інші фільтри:

Високочастотні (для підкреслення різкості зображення):

Для підкреслення орієнтації:

Підкреслення без урахування орієнтації (фільтри Лапласа):

Кореляційний:

, де

- коефіцієнти кореляції між сусідніми елементами по рядку (колонки). Якщо вони рівні нулю то відфільтроване зображення буде збігатися з вихідним, якщо вони рівні одиниці, то фільтр буде еквівалентний лапласіану. При обробці зображень дуже часто використовують послідовність фільтрів: низькочастотний + Лапласа. Часто використовують і нелінійну фільтрацію. Для контрастування перепадів зображення використовують градієнтний фільтр:

, або її спрощений вигляд:

Ще один часто використовуваний нелінійний фільтр - Собель:

A0 ... A7 - входи, yi, j - результат фільтрації.

рекурсивна версія:

де B0 ... B7 - вихід відфільтрованого зображення.

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

3.Сжатіе.

Зображення, в машинному поданні, - двовимірна матриця N на M, де N - його ширина, M - висота. При скануванні зазвичай використовують дозвіл від 72 до 2400 dpi (dots per inch - точок на дюйм). Найчастіше - 300 dpi. Якщо взяти аркуш паперу 21/29 см із зображенням і відсканувати його в RGB Truecolor, то незжаті зображення буде займати ~ 27300000 байтів або 26 Мбайт. Зазвичай у базах даних застосовують зображення порядку від 320x240 до 640x480. Але і вони займають 76 до 900 Кбайт. А що, якщо таких зображень сотні, тисячі? У даному розділі розглянемо методи стиснення. Вони стосовно для будь-яких масивів даних, а не тільки для зображень. Про методи стиснення, характерних тільки для зображень довідаємося трохи пізніше. Будемо розглядати статичне стиснення, тобто масив даних для стиснення цілком сформований. Методи стискання статичного часто підрозділяють на послідовне і Ентропійно. Послідовне стиснення використовує в роботі наявність повторюваних ділянок. Ентропійно використовується з метою скорочення до мінімуму надмірності інформації. Послідовне застосування цих методів дозволяє отримати гарний результат.

Послідовне стиснення.

Найбільш часто застосовують метод RLE, суть якого розглянемо на зображенні. Майже в будь-якому зображенні, особливо в комп'ютерних малюнках, зустрічаються послідовності однакових байтів. Наприклад, в ділянці зображення, в якому намальована частину неба, йдуть підряд кілька значень блакитного кольору. Для ділянки види: ККККККККЗЗЗЗСЗССССССССС, де К-червоний, З - зелений, С - синій кольори, буде закодовано як (8, К), (4, З), С, З, (10, С). У дужках - пари кількість повторень, значення байта. Ось як даний метод застосовується у форматі PCX. Декодування: якщо код належить безлічі [192 .. 255], то віднімаємо з нього 192 і отримуємо кількість повторень наступного байта. Якщо ж він менше 192, то поміщаємо його в декодіруемий потік без змін. Оригінально кодуються одиничні байти в діапазоні [192 .. 255] - двома байтами, наприклад, щоб закодувати 210 необхідно, представити його як (193, 210). Даний метод дає виграш у середньому в 2 рази. Однак для сканованих зображень, що містять плавні колірні переходи (тобто повторювані ланцюжка майже не зустрічаються), даний метод може піднести сюрприз - розмір масиву з закодованим зображенням буде більше початкового.

Найбільш поширені в даний час модифікації алгоритму LZ (на ім'я їх авторів - Лемпела та Зеева). У порівнянні з RLE зроблено крок вперед - будемо шукати у вихідному матеріалі не послідовності однакових видів, а повторюваних ланцюжків символів. Повторюють ланцюжка в кодованому повідомленні зберігаються як посилання на першу поява цієї ланцюжка. Наприклад, в ланцюжку КЗСЗБСКЗСЗБ починаючи з 7 символу, йде ланцюжок КЗСЗ, яку ми можемо замінити посиланням на 1-ий символ. Розглянемо найбільш поширені реалізації алгоритму LZ:

LZ77 - при роботі видає трійки виду (A, B, C), де A - зміщення (адреса попередньої ланцюжка B байтів якої збігаються з кодованої ланцюжком), B - довжина ланцюжка, C - перший символ в кодованої масиві, наступний за ланцюжком. Якщо збіг не виявлено то створюється трійка виду (0, 0, С), де C - перший символ кодованої ланцюжка. Недолік такого підходу очевидний - при кодуванні "рідкісних" байтів ми "стискаємо" один байт в три. Перевага - простота реалізації, велика швидкість декодування.

LZSS - створює при роботі вектора виду (прапор, C) і (прапор, A, B). Якщо бітовий прапор = 0, то наступний за ним C трактується, як одиничний байт і видається в декодіруемий масив. Інакше, коли прапор = 1, то в декодіруемий масив видається ланцюжок довжиною B по зсуву A. LZSS кодує набагато більш ефективно, порівняно з LZ77, так як використовує бітові прапори і мало програє при кодуванні одиночних символів. При кодуванні будується словник зустрічаються ланцюжків у вигляді довічного впорядкованого дерева. Швидкість і простота алгоритму декодування масиву у LZSS також висока.

LZMX (спрощена LZM) - даний алгоритм призначений для швидкісного кодування і за ефективністю поступається LZSS, помітно випереджаючи його за швидкістю роботи. При роботі кодер LZMX формує кілька векторів виду:

(0, A, незжатий потік) - де 00-2х бітовий прапор ознаки даного блоку, A (7 бітів з діапазоном в [1 .. 127]) - довжина наступного за ним нестисненого потоку в байтах ..

(0, 0000000, A, B) - де, A - кількість повторює байти B. Тобто код RLE.

(1, A, B) - де A (7 бітів з діапазоном в [1 .. 127]) - довжина декодіруемой ланцюжки, B - її зсув.

Для швидкого пошуку повторюваних ланцюжків використовується хеш. Індекс - 12 бітовий, обчислюється як [(a * 4) xor (b * 2)] xor c, де a, b, c - перший символи ланцюжка. Індекс дає зміщення у масиві раніше зустрінутої ланцюжки з тими ж першими символами. Використання хешу і дає високу швидкість кодування.

Декодування також має велику швидкість - читається біт - прапор, якщо він є 0 і наступні за ним 7 бітів також нуль, читаємо наступні два байти - A і B і копіюємо у вихідний масив байт BA - раз: якщо при прапорі = 0 наступні 7 бітів = A більше нуля, то у вихідний масив копіюємо A байтів наступних за A. І, нарешті, якщо прапорець встановлений в одиницю, то читаємо A і наступний за ним байт B і копіюємо у вихідний масив ланцюжок довжиною A байт із зміщення B.

Існують і інші модифікації алгоритму LZ (LZW, LZS, LZ78 ...). Загальна властивість LZ - висока швидкість декодування. Загальна проблема - ефективність пошуку кодованих ланцюжків. Модифікація даного алгоритму використовується в графічному форматі GIF.

Ентропійно стиснення.

Ентропійно стиснення на відміну від послідовного, в якості інформації про вхідному масиві використовує тільки частоти зустрічальності в ньому окремих байтів. Цю інформацію він використовує як при кодуванні, так і при декодуванні масиву. Її представляють у вигляді 256 компонентного вектора, координата i якого представляє собою скільки разів байт із значенням i зустрічається у вихідному масиві. Даний вектор займає невеликий простір і майже не впливає на ступінь компресії. Багато методів Ентропійно кодування видозмінюють даний вектор відповідно до використовуваним алгоритмом. Розглянемо два найбільш часто використовуваних ме?? одов:

Метод Хаффмана . Даний метод скорочує надмірність масиву, створюючи при кодуванні змінну бітову довжину його елементів. Основний принцип такий: найбільш часто зустрічається байту - найменшу довжину, самому рідкісного - найбільшу. Розглянемо найпростіший приклад кодування методом Хаффмана - спосіб кінцевого нуля. Будь-який елемент кодується ланцюжком бітів, що складається з одних одиниць і закінчуються нулем. Таким чином, найчастіший закодіруем одним бітом - 0, наступний за ним по частоті як 10, далі - 110, 1110, 11110 і т.д. Процедура декодування також очевидна.

Розглянемо вищесказане на прикладі. Нехай дана частина зображення довжиною 80 біт - десять квітів і кожен з них закодований одним байтом (індексовані 256 кольорами зображення): КЗСГКСКБСК (де К - червоний, З - зелений і т.д.). Закодіруем його. Побудуємо таблицю частоти зустрічальності кольору та коду йому відповідного:

Колір

Частота

Код

До

110

1110

11110

Таким чином, ми закодували вихідний масив як 0 110 10 1110 0 10 0 11110 10 0. Разом: довжина вихідного повідомлення - 22 біта. Ступінь компресії ~ 4.

Метод арифметичного кодування. Даний метод з'явився пізніше. Його принцип - кодування вихідного масиву одним числом. Часто вхідний масив розбивають на однакові невеликі ділянки і кодують їх окремо, отримуючи в результаті послідовність кодових чисел. Закодіруем попередній приклад числом, які лежать в одиничному діапазоні. Схема кодування наступна. Будуємо таблицю частот, кожному елементу таблиці ставимо у відповідність діапазон, рівний його частоті поділеної на довжину вхідного масиву. Встановлюємо верхню межу ВГ в 1, нижню НГ у 1. Далі N раз виконуємо наступну послідовність дій (де N - довжина кодованого ділянки або всього масиву):

Читаємо з масиву черговий символ.

Установка поточного інтервалу. Інтервал И = ВГ - НГ.

ВГ = НГ + І * ВГ символу (беремо з таблиці).

НГ = НГ + І * НГ символу (беремо з таблиці).

Розглянемо на прикладі: КЗСГКСКБСК. Побудуємо необхідну таблицю:

Колір

Частота

Нижня межа НГ

Верхня межа ВГ

До

0.4

0.5

0.8

0.9

Тепер, власне, сама процедура кодування:

Крок

Символ

НГ

ВГ

Інтервал

До

0.4

0.16

0.2

0.04

0.18

0.192

0.012

0.1896

0.1908

0.0012

До

0.1896

0.19008

0.00048

0.18984

0.189984

0.000144

До

0.18984

0.1898976

0.0000576

0.18989184

0.1898976

0.00000576

0.18989472

0.189896448

0.000001728

До

0.18989472

0.1898954112

0.0000006912

Таким чином, будь-яке число в діапазоні [0.18989472 .. 0.1898954112] однозначно кодує вихідний масив. У двійковому дробному вигляді як 0.XXXXXXXX ... Для зберігання такої кількості вистачить n біт (розмірність XXXXXXXX ....), де n найближчим ціле, яке задовольняє нерівності: 2n> Інтервал-1 = 0.0000006912-1. Шукалося n одно 21. Тобто ми можемо закодувати вихідний масив 21 бітом. У даному прикладі - 001100001001110111111. Процедура декодування зворотний і полягає у виконанні n раз наступного:

Шукаємо в таблиці інтервал, в який потрапляє наше число Ч, і видаємо символ в нього входить до декодіруемий масив.

Інтервал И = ВГ символу - НГ символу (обидва значення - з таблиці).

Ч = (Ч - НГ)/І.

Крок

Число

Символ

НГ

ВГ

Інтервал

0.18989472

До

0.4

0.4747368

0.4

0.5

0.1

0.747368

0.5

0.8

0.3

0.82456

0.8

0.9

0.1

0.2456

До

0.4

0.614

0.5

0.8

0.3

0.38

До

0.4

0.95

0.9

0.1

0.5

0.8

0.3

До

0.4

У даному прикладі арифметичний кодер "обігнав" метод Хаффмана на 1 біт. На відміну від методу Хаффмана трудомісткість алгоритму значна. У чому ж тоді "корисність" алгоритму? Розглянемо послідовність КККККККС. При кодуванні методом Хаффмана отримаємо вихідну послідовність довжиною в 9 біт (можна