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

Тип роботи:
Реферат
Предмет:
Інформатика


Дізнатися вартість нової

Детальна інформація про роботу

Витяг з роботи

1. Цвет
Людський очей полягає з майже 7 млн. колбочек і 120 млн. паличок. Функція паличок залежить від «нічному зір» — світлочутливість і пристосуванні до оточуючої яскравості. Функція колбочек — «денний зір» — сприйняття кольору, форми і деталей предмета. Вони закладено три типу сприймають елементів, кожна з яких сприймає світлове випромінювання лише певної довжини хвиль, відповідних одного з з трьох основних квітів: червоному, зеленому і синьому. Інші кольори і відтінки виходять змішанням цих.
Людський очей сприймає колірну інформацію буде в діапазоні хвиль приблизно від 380 нм (синій колір) до 770 нм (червоний колір). Причому найкращу чутливість має у районі 520 нм (зелений колір).
На малюнку показано чутливість очі залежно від довжини прийнятої хвилі. Область частот, лівіше синьої - ультрафіолетові хвилі, правіше червоною — інфрачервоні хвилі.
Грассман навів закони природи цвета:
1. Тривимірність природи кольору. Око реагує втричі різних колірних складових. Приклади: червоний, зелений і синій кольору; колірної тон (домінуюча довжина хвилі), насиченість (чистоту) і яскравість (светлость).
2. Чотири кольору завжди лінійно залежні, тобто, де. Для суміші двох квітів і має місце рівність:. Якщо колір дорівнює кольору і колір теж дорівнює кольору, то колір дорівнює кольору незалежно від структури спектрів енергії.
3. Колірне простір безупинно. Якщо суміші трьох квітів один безупинно змінюється, інші залишаються постійними, то колір суміші змінюватиметься непрерывно.
Розглянемо основні колірні модели:
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.
Якщо є один контрольний колір, те з допомогою нього можна отримати деякі кольору, варіюючи даний контрольний по светлоте (за умови, що ні використовується колірної тон і насиченість). Ця процедура називається фотометрией і використовується під час створення монохроматичних репродукцій кольорових зображень.
З допомогою двох контрольних квітів можна було одержати вулицю значно більше квітів, але не. Для отримання видимого набору квітів використовують три контрольних кольору, дотримуючись умова, що вони у різних галузях спектра. Розглянемо наступний базис квітів:
1. Red- червоний; лежать у області довгих видимих хвиль (`700 нм).
2. Green- зелений; лежать у області середніх видимих хвиль (`546 нм).
3. Blue- синій; лежать у області середніх коротких хвиль (`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. Перетин вектора З з одиничної площиною 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:

Название
Температура
x
y
Лампа з вольфрамової ниткою накаливания.
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. Колір, який виникає у цій колірної моделі лежить всередині трикутника, кольору, що лежать поза — отримати неможливо. Приклади колірних обхватів декому моделей помітні малюнку. Зауважимо, що з кольорової плівки обхват є вигнутий трикутник. Причина цього в нелінійному (у разі логарифмическом) законі створення кольорового зображення з допомогою кольорової плівки. Нижче приведено таблиця основних квітів моделей в координатах колірного графіка CIE:

Модель
Цвет
x
y

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, то:
, где:
— дані величини необхідні повного перетворення між системами основних квітів, теж можна отримати й наступним образом:
1. Відомі - яскравості одиничних кількостей основних цветов:
.
2. Відомий — координати кольоровості опорного білого та її яркость:

Протилежне перетворення CIE XYZ в RGB задається как:
, де з элементами:



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

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

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

YIQ в RGB:

Крім YIQ трапляються й інші колірні моделі у форматі Яскравість, 1-ый колірної канал, 2-ой колірної канал. Наприклад, при колірної корекції використовують формат LAB, в котором:
L (ightness) — яркость,
A- колірної канал що має кольору від зеленого до красного,
B- колірної канал, відповідальний за кольору ще на сине-желтом диапазоне.
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, P. S, B, як черно/белых зображень з 256 рівнями градації серого.
Канали: М — тон, P. S — насиченість, B — яркость.
Деякі примітки до колірною моделям
При колірних перетвореннях слід також пам’ятати, що колірними моделями CIE, CMY, RGB, YIQ існують аффинные перетворення, тоді, як між HLS і HSV- немає. Ця обставина буде помітно, якщо зображення, що містить безперервні колірні переходи, переводити, наприклад, з HLS в RGB (на зображеннях може з’явитися розрив непрерывности).
2. Общая схема цифровий обробки изображений
Розглянемо процес обробки зображень як наступній последовательности:
1. Одержання вихідного, «сирого» изображения.
2. Фільтрація изображения.
3. Переклад зображення на необхідну колірну модель.
4. Форматування і індексування изображения.
5. Розбивка на блоки.
6. Обробка графічної інформації, котра міститься в блоках.
7. Послідовне сжатие.
8. Энтропийное сжатие.
Дане розподіл не претендує на повноту, але не дає загальне полотно процесу обробки. Деякі етапи, наприклад, 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 — 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−65 535
Зелений 0−4095/0−65 535
Синий0−4095 /0−65 535
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, j є покажчиком на таблицю квітів. Кількість використовуваних квітів одно 2K, де K — кількість біт, використовуваний для зберігання елемента матриці. Кольори в указываемой таблиці можуть кодуватимуть іншим числом біт. Наприклад, в 256 колірних режимах видеоадаптеров вибирається 256 квітів з 262 144 можливих, оскільки обирані кольору видаються в RGB форматі для кожної колірної компоненти кодується 6-ту бітами. Є багато методів перетворення багатоканальних зображення на індексовані (Error diffusion, найближчого кольору …).
Фільтрація зображення.
Поняття фільтрації у разі дуже широке, і включає у собі будь-яке перетворення графічної інформації. Фільтрація то, можливо задана у вигляді формули, а й у вигляді алгоритму, його реалізує. Людина запам’ятовує графічну інформацію, переважно, у трьох її составляющих
1. Низькочастотні складові зображення. Вони несуть інформацію локалізацію об'єктів, складових зображення. Ця складова найважливіша, оскільки зв’язка очей — мозок приділяє їй першорядне увагу.
2. Високочастотні складові зображення. Вони за колірні перепади — контури зображення. Збільшуючи їх, ми підвищуємо різкість изображения.
3. Текстури зображення. Щоб зрозуміло пояснити, що це таке проведемо невеличкий експеримент. Розслабтеся, згадайте інтер'єр вашого вдома, наприклад, парта. Ви знаєте його обриси, місце розташування, колір — це низькочастотні характеристики, згадали його загострені кути, невелику подряпини де-небудь ближчі один до його крайці - це високочастотні складові. Також Ви знаєте, що стіл дерев’яний, але з можете з точністю розповісти про дрібних деталях поверхні, хоча загальні характеристики (коричневий з темними западинами, дві області розбіжності концентричних еліпсів від сучків) — напевно. У разі в дужках — опис текстури. Можна трактувати текстуру як характеристику ділянок в контурах зображення.
Будемо розглядати фільтри як квадратної матриці A. Нехай вихідне зображення X, а одержуване як наслідок фільтрації - Y. Для простоти використовуватимемо матриці 3×3:

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

Для простоти розглянемо одновимірний фільтр вида: :
Розглянемо та інші фильтры:
1. Високочастотні (для підкреслення різкості изображения):

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

3. Підкреслення не враховуючи орієнтації (фільтри Лапласа):
.
4. Корреляционный:
, где
— коефіцієнти кореляції між сусідніми елементами по рядку (стовпцю). Якщо вони самі рівні нулю то відфільтроване зображення збігатиметься із вихідним, якщо вони рівні одиниці, то фільтр буде еквівалентний лапласиану. Після обробітку зображень часто-густо використовують послідовність фільтрів: низькочастотний + Лапласа. Часто використовують і нелінійну фільтрацію. Для контрастування перепадів зображення використовують градиентный фильтр:
, або його спрощений вид:
.
Ще одна часто використовуваний нелінійний фільтр — Собела:
A0 … A7 — входи, yi, j — результат фильтрации.

Рекурсивна версія:
де 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 формує кілька векторів виду:
1. (0, A, несжатый потік) — де 00 -2х бітовий прапор ознаки цього блоку, A (7 бітов з діапазоном в [1. 127]) — довжина наступного його несжатого потоку в байтах.
2. (0, 0, A, B) — де, A — кількість який повторює байта B. Тобто код RLE.
3. (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. 18 989 184
0. 1 898 976
0. 576
9
С
0. 18 989 472
0. 189 896 448
0. 1 728
10
К
0. 18 989 472
0. 1 898 954 112
0. 6 912

Отже, будь-яке число буде в діапазоні [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. 18 989 472
К
0
0. 4
0. 4
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
У розділі розглядатимемо стиснення графічної інформації з утратами. Тобто з стиснутого вихідного масиву неможливо при декодуванні отримати вихідний. Але стискати в такий спосіб, щоб втрати якнайменше сприймалися оком під час демонстрування даної графічної інформації.
Найперший спосіб, який спадає на думку, наступний. Зменшимо кількість біт для зберігання одного пикселя (елемента вихідної матриці). Нехай пикселы вихідного зображення мають формат RGB Truecolor 8: 8:8 (кожну колірну складову відводиться по 8 біт). Перекодируем зображення у формат 5: 5:5 (тобто кожна колірна складова матиме 25 =32 градації), відкидаючи молодші чотири біта зображення. Ми також можемо використати властивість очі найкраще розрізняти колір у сфері зеленого і кодувати зображення у формат RGB 4: 5:4 й у піксел займатиме два байта.
Можна піти ще: перевести вихідне зображення у іншу колірну модель і відформатувати його. Наприклад, в YIQ 6: 3:3 — відводимо на яскравість 6 біт, на синфазный і інтегрований канали по 3, використовуючи те, що важливіша інформація про інтенсивності, ніж про кольорі. При «жадібний» кодування, коли використовуємо невелика кількість біт на піксел, відразу після декодування, перед висновком зображення можна навести так званий anti-aliasing — згладити різкі колірні переходи, виниклі через малої кількості градацій колірних складових. Подальше вдосконалення залежить від индексировании квітів. RGB Truecolor формат може підтримувати більш 16 млн. квітів. Виберемо n (зазвичай n — ступінь 2) індексних квітів cK те щоб мінімізували сумму:
.
Далі створюємо вихідний масив B N на N, елемент якого bi, j дорівнює k, де k= m — номер кольору такий, що виконується. Вихідна інформація — масив B та власне таблиця індексних квітів з. Результати такого підходу можна подивитися розділ «Форматування і індексування изображений».
Розглянемо сімейство кодеров зображення, заснованих на виключно отбросе коефіцієнтів перетворення. Усі вони використовують розбивку на блоки. Нехай Y — одержуване зображення, A — матриця перетворення.
.
Після перетворення, зберігаємо тільки п’яту частину коефіцієнтів, рахунок чого здійснюється стиснення. Найбільш ефективним буде метод, здатний мінімізувати оценку:
. Найоптимальніший метод — Карунена-Лоэва. Рядки матриці перетворення A — нормовані власні вектора Kx, тобто є рішенням рівняння виду Kxx = ?ix, Kx = E{(x- Ex)(x-Ex)T} - ковариация, E — мат. очікування, T — знак транспонування. Коефіцієнти перетворення y=Ax мають матрицю перетворення вида:
, де … ???- власні значення Kx. Відкидаючи малі власні значення отримуємо стиснення. Він, хоч і дає найменшу помилку наближення з-поміж подібних кодеров, використовується рідко, оскільки потребує великого лікарського обсягу обчислень за всієї роботі. Перетворення Карунена-Лоэва називають також оптимальним кодуванням. Розглянемо інші кодеры даного семейства:
1. Фур'є, для даного перетворення існує алгоритм, з тимчасової складністю n2log2n. Перетворення Фур'є є розкладання по спектру.
2. Дискретне косинусное перетворення (ДКП).
. Найбільш используемый
нині метод, оскільки він надає результат помилку наближення трохи більш ніж розкладанню Карунена-Лоэва. Існує алгоритм, який реалізує даний метод складності 2n2log2n-1. 5n+4.
3. Симетричний перетворення Адамара.
, где
il і jl — стан розрядів двоичного уявлення чисел і і j. Для n=2 матриця буде такою:. Хоча метод Адамара це не дає настільки хороших результатів як і попередні, зате усі фінансові операції перетворення зводиться до сложениям і вычитаниям.
При відборі коефіцієнтів користуються такими способами:
1. Граничний відбір. Відкидаються коефіцієнти, котрі за модулю, нижчих за встановлений порога.
2. Зональний відбір. Відкидаються коефіцієнти, належать до малокритичному спектру. Наприклад, при ДКП чи перетворення Фур'є можемо відкинути частина коефіцієнтів, які належать до высокочастотному спектру, оскільки чутливість очі вище в низькочастотної области.
Зазвичай отбрасываемые коефіцієнти обнуляют. Далі застосовують послідовне і энтропийное стиснення. Так працює алгоритм JPEG кодування. Усе це дає зниження розміру масиву, при прийнятному ролі зображення, в 5−16 раз. На наведеному прикладі використовувалося вихідне зображення у вирішенні 240 на 362 пикселя в RGB Truecolor і займало 240*362*3=260 640 байт. Ліва стислий зображення займає 46 000 байт і зовні не відрізняється від вихідного. Ліва нижнє зображення має розмір 8004 байт і має помітні різкі колірні переходи у сфері неба. Права нижнє зображення має розмір 5401 байт (!) і було зображення стало занадто мозаїчним, ми можемо зрозуміти його зміст. З використанням разбивок на блоки інколи складається побічний ефект: стають помітними кордону блоків. Для боротьби з нею розбивку проводять те щоб блоки «наїжджали» до кордонів сусідніх із ним блоков.
Інший принцип є основою пірамідального кодування. Нехай x (k, l) — вихідне зображення. Одержимо потім із нього його низкочастотную, із частотою зрізу f1, «версію» x1(k, l) з допомогою локального усереднення з одномодовым гауссоподобным
двовимірним імпульсним відгуком. x1(k, l) можна як пророцтво для з. e1(k, l) = x (k, l) — x1(k, l) — помилка передбачення, далі повторюємо для частоти зрізу f2: e2(k, l) = x1(k, l) — x2(k, l) — помилка передбачення менш як для e1 в f1/f2 раз. Отримуємо у результаті послідовність e1, e2, ., et. В кожній ітерації розмірність зображення скорочується в fi /fi+1 раз. Він зменшує яку він обіймав розмір в 10. 20 раз при прийнятному ролі зображення. Але складність алгоритму вище проти попередніми методами.
Розглянемо іще одна метод стискування зображення — вирощування областей, що у корені відрізняється від інших. Він розглядає зображення як набір що межують друг з одним текстурных контурів, усередині кожного у тому числі немає різкої зміни рівня колірної складової. Перед роботою методу, можливо кілька разів доведеться зробити предобработку, яка полягає зі скороченнями зернистості, але зберігає контури у виконанні (тобто малі перепади рівня усредняем, а великі - залишаємо). Для цього зазвичай застосовують зворотний градиентный фільтр. Далі починаємо розмітку областей. Область — частина зображення, пикселы якою володіють якимось загальним властивістю — належать лише до смузі частот, мають близьким значенням певної колірної складової. Розмітка ввозяться два этапа:
1. Починаючи з даного пикселя зображення, щодо його сусіда перевіряємо: чи має він загальним властивістю області. Якщо це, він входить у дану галузь, і далі перевіряються його сусіди тощо. Коли большє нє залишається елементів, суміжних з цим контуром процедура зупиняється і розпочинається знову для пикселей, які у цю область.
2. Послаблення областей. Зазвичай, у зображенні 70% створених областей зберігають у 4% зображення. Сусідні області об'єднують, якщо вони мають близькими властивостями, також видаляють незначні (за величиною), області. Алгоритми створення і видалення областей — завдання проста і то, можливо оптимізована на багатьох напрямах у різний спосіб. Саме неї залежить подальша ефективність алгоритма.
Розглянемо власне кодування. Вона складається з двох етапів: 1 — кодування контурів і 2 — текстур, що у них. Контури видаються як матриці з битовыми елементами, що дорівнює 1, якщо точка входить у кордон області - контур і 0 — інакше. Цю матрицю можна энтропийно стиснути з ефективністю ~1.2. 1.3 біта на піксел контуру. Текстура (вміст) кожної сфери наближається середнім рівнем властивості її ділянці і двовимірним полиномом (лінійним, квадратним чи кубічним — залежно від й виконання вимог до якості). При декодуванні додамо зернистость в текстуру з допомогою гауссова псевдослучайного фільтра з роботи вже відомої середньоквадратичної помилкою. Він дозволяє домогтися стискування зображення на 20. 75 разом із прийнятним якістю зображення. Тимчасові витрати за його реалізації дуже великі. Працюючи цього методу ми також можемо (з невеликими додатковими обчисленнями) паралельно перевести зображення у векторну форму.

Литература
1. Ендрюс. Застосування обчислювальних машин в обробці изображений.
2. Гаррі. Обробка зображень з допомогою ЦВМ.
3. Яншин. Аналіз та обробка зображень. Принципи і алгоритмы.
4. Джад, Вышецки. Колір у науці й технике.
5. Мартінес. Обробка изображений.
6. Роджерс. Алгоритмічні основи машинної графики.
7. Оппенхейм. Цифрова обробка сигналов.
8. Фрини, Кайзер. Застосування цифровий обробки сигналов.
9. ТИИЭР. Том 73. Досягнення у сфері кодування изображений.
10. ТИИЭР. Том 68. Кодування изображений.
11. ТИИЭР. Том 63. Цифрова обробка изображений.
12. Журнал «Монітор» за 94 рік. Мастрюков. Алгоритми стискування информации.
13. Эхоконференции FidoNet.

Показати Згорнути
Заповнити форму поточною роботою