Цифрова обробка графіки

РЕФЕРАТ.

Кодування изображений.

Садыков М.Р.

27 липня 1997 года.

1.Цвет.

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

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

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

Грассман навів закони природи цвета:

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

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

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

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

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 можна сформулювати через таку формулу:

[pic].

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

CIE.

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

З допомогою двох контрольних квітів можна отримати роботу вулицю значно більше квітів, але не. Для отримання видимого набору квітів використовують три контрольних кольору, дотримуючись умова, що вони у різних галузях спектра. Розглянемо наступний базис квітів: 1. Redчервоний; лежать у області довгих видимих хвиль (`700 нм). 2. Greenзелений; лежать у області середніх видимих хвиль (`546 нм). 3. Blueсиній; лежать у області середніх коротких хвиль (`436нм).

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

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

[pic] .

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

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

[pic] Зауважимо, [pic]. Розглянемо зв’язок: [pic]. Якщо функціями урівнювання за кольором перенести в тривимірне простір, то результат досягнуто не цілком лежатиме в позитивному октанте.

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

[pic].

[pic].

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

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

|Название |Температура|x |y | |Лампа з вольфрамової ниткою |2856К |0.448|0.408| |розжарювання. | | | | |Сонячний світ у полудень. |5600К |0.349|0.352| |Полуденне висвітлення при суцільний |6300К |0.310|0.316| |хмарності. | | | | |Опорний білий стандарт для моніторів |6400К |0.313|0.329| |і NTSC. | | | |.

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

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

|Модель |Колір |x |y | | |Красный|0.735|0.265| |CIE XYZ. | | | | | |Зеленый|0.274|0.717| | | | | | | |Синій |0.167|0.009| | |Красный|0.670|0.330| |Стандарт NTSC. | | | | | |Зеленый|0.210|0.710| | | | | | | |Синій |0.140|0.080| | |Красный|0.628|0.346| |Кольоровий | | | | |монітор. |Зеленый|0.268|0.588| | | | | | | |Синій |0.150|0.070|.

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

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

[pic], де: [pic]- дані величини необхідні повного перетворення між системами основних квітів, [pic]также можна отримати й так: 1. Відомі [pic]- яскравості одиничних кількостей основних цветов:

[pic]. 2. Відомий [pic] - координати кольоровості опорного білого та її яркость:

[pic].

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

[pic], де [pic]c элементами:

[pic].

[pic].

[pic].

YIQ.

Для кольорового телебачення стандарту NTSC було пред’явлено дві основні вимоги: 1. Бути не більше встановленого діапазону в 6 МГц, 2. Забезпечувати сумісність з чорно-білим телебаченням. У 1953 було розроблено систему YIQ:

|Канал |Назва |Яку Він Обіймав | | | |діапазон | |Y |яскравість |4 МГц | |I |синфазный |1.4 МГц | |Q |интегрированны|0.6 МГц | | |і | |.

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

RGB в YIQ:

[pic].

YIQ в RGB:

[pic] Крім YIQ трапляються й інші колірні моделі у форматі Яскравість, 1-ый колірної канал, 2-ой колірної канал. Наприклад, при колірної корекції використовують формат LAB, у якому: L (ightness) — яскравість, Aколірної канал що має кольору від зеленого до червоного, Bколірної канал, відповідальний за кольору ще на сине-желтом диапазоне.

HLS і HSB.

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

[pic] RGB в HSV:

[pic] RGB в HLS:

[pic] HLS в RGB:

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

Канали: М — тон, P. S — насиченість, B — яркость.

Деякі примітки до колірною моделям.

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

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

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

Получение вихідного, «сирого» зображення. Фільтрація зображення. Переклад зображення на необхідну колірну модель. Форматування і індексування зображення. Розбивка на блоки. Обробка графічної інформації, котра міститься в блоках. Послідовне стиснення. Энтропийное сжатие.

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

Одержання вихідного, «сирого» изображения.

Изображения в обробці умовно може бути розбитий чотирма класса:

1. Природні, отримані шляхом сканування, захоплення тілі чи відео кадру, зйомкою цифровий апаратурою. 2. Зображення, намальовані з допомогою графічного редактора на комп’ютері, назвемо їх комп’ютерними малюнками. 3. Тривимірні сцени, синтезовані з допомогою спеціальних програм, таких як: CAD’ы (AutoCAD, ArchiCAD …), 3D генератори (3D Studio, LightWave …) тощо. 4. Зображення — візуалізація даних, отриманих як наслідок деякого експерименту, досвіду, виміру (енцефалограма, сейсмографическая карта …).

Естественные зображення мають некомпьютерное походження. Вони майже немає різких колірних переходів. Комп’ютерні малюнки, як і втім й зняти будь-які інші, поділяються на два типу: растрові і векторні. У першому зображення зберігається як прямокутна матриця із елементами, котрі характеризують колірні складові. У векторних зображення — послідовність команд щодо його побудови. Приклад команди — коло з центром у точці (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, з у сумі дають одиницю. Іноді, для зберігання grayscale зображень використовують на точку 4−7 і 16 бітов. У разі маємо 16−128 чи 65 536 відтінків сірого цвета.

Многоканальные. У разі ai, j подано у вигляді вектора з координатами використовуваної колірної моделі. Зазвичай вектор тривимірний, так як природа очі реагує втричі різних колірних складових. Кожен компонент вектора найчастіше займає байт. Розглянемо найбільш поширені многоканальные формати: |Назва |Соотношен|1-ый |2-ой |3-ий | | |не біт |компонент |компонент |компонент | |RGB — |8:8:8 |Красный0−255|Зеленый0.25|Синий0−255 | |Truecolor | | |5 | | |RGB — |5:6:5/5:5|Красный0−31 |Зеленый0.63/|Синий0−31 | |Highcolor |:5 | |31 | | |RGB — |12:12:12/|Красный |Зелений |Синий0−4095 | |Extended |16:16:16 |0−4095/0−655|0−4095/0−655|/0−65 535 | | | |35 |35 | | |CMY |8:8:8 |Голубой0−255|Пурпур0−255 |Желтый0−255 | |LAB |8:8:8 |Яркость0−255|Канал A |Канал B | | | | |0−100% |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, j є покажчиком на таблицю квітів. Кількість використовуваних квітів одно 2K, де K — кількість біт, використовуваний для зберігання елемента матриці. Кольори в указываемой таблиці можуть кодуватимуть іншим числом біт. Наприклад, в 256 колірних режимах видеоадаптеров вибирається 256 квітів з 262 144 можливих, оскільки обирані кольору видаються в RGB форматі для кожної колірної компоненти кодується 6-ту бітами. Є багато методів перетворення багатоканальних зображення на індексовані (Error diffusion, найближчого кольору …).

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

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

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

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

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

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

[pic].

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

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

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

[pic] Для простоти розглянемо одновимірний фільтр вида:[pic]: [pic]Рассмотрим та інші фильтры:

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

[pic].

2. Для підкреслення ориентации:

[pic].

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

[pic].

4. Корреляционный:

[pic], где.

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

[pic], або його спрощений вид:

[pic].

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

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

[pic] [pic].

Рекурсивная версія: [pic]где B0 … B7 — вихід відфільтрованого зображення. Нелінійна фільтрація — досить загадкова область цифровий обробки сигналів, багато у ній доки вивчено. Важливість її бракує сумнівів, оскільки навколишній світ за своєю сутністю негаразд линеен, як часом хочеться його нам интерпретировать.

3.Сжатие.

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

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

Найчастіше застосовують метод RLE, суті якого розглянемо на зображенні. Майже у кожному зображенні, особливо у комп’ютерних малюнках, зустрічаються послідовності однакових байтів. Наприклад, в ділянці зображення, у якому намальована частина неба, йдуть поспіль кілька значень блакитного кольору. Для ділянки виду: ККККККККЗЗЗЗСЗССССССССС, де Дочервоний, З — зелений, З — синій кольору, буде закодований як (8,К); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (4,З), С, З,(10,С). У дужках — пари кількість повторень, значення байта. Ось як даний метод застосовується у форматі PCX. Декодування: якщо код належить безлічі [192.255], то віднімаємо потім із нього 192 й одержуємо кількість повторень наступного байта. Якщо ж вона менше 192, то поміщаємо їх у декодируемый потік не змінювалась. Оригінально кодуються поодинокі байти буде в діапазоні [192.255] - двома байтами, наприклад, щоб закодувати 210 необхідно, подати його як (193, 210). Він дає виграш в середньому у 2 разу. Проте задля отсканированных зображень, містять плавні колірні переходи (тобто повторювані ланцюжка майже зустрічаються), даний метод може піднести сюрприз — розмір масиву з закодованим зображенням буде більше исходного.

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

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

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

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

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

5. (0, 0, A, B) — де, A — кількість який повторює байта B.

Тобто код RLE.

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

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

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

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

Энтропийное сжатие.

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

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

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

|Цвет |Частота |Код | |До |4 |0 | |З |1 |110 | |З |3 |10 | |Р |1 |1110 | |Б |1 |11 110|.

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

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

1. Читаємо з масиву черговий символ. 2. Установка поточного інтервалу. Інтервал І = ВГ — НГ. 3. ВГ = НГ + И*ВГ символу (беремо з таблиці). 4. НГ = НГ + И*НГ символу (беремо з таблицы).

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

|Цвет |Частота|Нижняя кордон |Верхня кордон | | | |НГ |ВГ | |До |4 |0 |0.4 | |З |1 |0.4 |0.5 | |З |3 |0.5 |0.8 | |Р |1 |0.8 |0.9 | |Б |1 |0.9 |1 |.

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

|Шаг |Символ |НГ |ВГ |Інтервал | |0 | |0 |1 |1 | |1 |До |0 |0.4 |0.4 | |2 |З |0.16 |0.2 |0.04 | |3 |З |0.18 |0.192 |0.012 | |4 |Р |0.1896 |0.1908 |0.0012 | |5 |До |0.1896 |0.19 008 |0.48 | |6 |З |0.18 984 |0.189 984 |0.144 | |7 |До |0.18 984 |0.1 898 976 |0.576 | |8 |Б |0.1 898 918|0.1 898 976 |0.576 | | | |4 | | | |9 |З |0.1 898 947|0.189 896 448|0.1 728| | | |2 | | | |10 |До |0.1 898 947|0.189 895 411|0.691| | | |2 |2 |2 |.

Таким чином, будь-яке число буде в діапазоні [0.18 989 472. 0.1 898 954 112] однозначно кодує вихідний масив. У двоичном дробовому вигляді як 0. XXXXXXXX…Для зберігання такого числа вистачить n біт (розмірність XXXXXXXX…), де n найближче ціле, що задовольнить нерівності: 2N > Интервал-1=0.6 912−1. Дані n одно 21. Тобто ми можемо закодувати вихідний масив 21 битому. У цьому прикладі - 1 100 001 001 110 111 104. Процедура декодування зворотна і полягає у виконанні n раз следующего:

1. Шукаємо в таблиці інтервал, куди потрапляє наше число Ч, і видаємо символ до нього входить у декодируемый масив. 2. Інтервал І = ВГ символу — НГ символу (обидва значення — з таблиці). 3. Ч = (Ч — НГ) / И.

|Шаг |Кількість |Символ |НГ |ВГ |Інтервал| |1 |0.1 898 947|К |0 |0.4|0.4 | | |2 | | | | | |2 |0.4 747 368|З |0.4|0.5|0.1 | |3 |0.747 368 |З |0.5|0.8|0.3 | |4 |0.82 456 |Р |0.8|0.9|0.1 | |5 |0.2456 |До |0 |0.4|0.4 | |6 |0.614 |З |0.5|0.8|0.3 | |7 |0.38 |До |0 |0.4|0.4 | |8 |0.95 |Б |0.9|1 |0.1 | |9 |0.5 |З |0.5|0.8|0.3 | |10 |0 |До |0 |0.4|0.4 |.

В даному прикладі арифметичний кодер «обігнав» метод Хаффмана на 1 біт. У на відміну від методу Хаффмана трудомісткість алгоритму значна. У чому тоді «корисність» алгоритму? Розглянемо послідовність КККККККС. При кодування методом Хаффмана одержимо вихідну послідовність у 9 біт (можна 8, оскільки масив складається з 2 різних байт). При арифметическом кодування цю послідовність можна закодувати числом 0.4375 чи двоичном вигляді як 0111, займаної 4 біта. Тобто за арифметическом кодування можливо отримувати щільність кодування менше біта на символ. Це властивість проявляється, коли у вхідному масиві частоти деяких символів значно вища остальных.

Обробка графічної информации.

Для простоти викладу нехай зображення зберігається в квадратної матриці X із елементами xi, j N рядків на N шпальт. Для деяких методів застосовують розбивку вихідного зображення на блоки. Обробляючи матрицю, ми мати тимчасову складність алгоритму принаймні кратної N3. Для її зменшення надходять так: розбивають зображення сталася на кілька малих розміром n на n, n.