РЕФЕРАТ.
Кодування зображень.
Садиков М.Р.
27 липня 1997.
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.
Якщо є один контрольний колір, то за допомогою нього можна отриматидеякі кольори, варіюючи даний контрольний по світлини (за умови, щоне використовується колірний тон і насиченість). Дана процедура називаєтьсяфотометрії і використовується при створенні монохроматичні репродукційкольорових зображень.
За допомогою двох контрольних квітів можна отримати набагато більшекольорів, але не всі. Для отримання видимого набору квітів використовують триконтрольних кольору, дотримуючись умову, що вони знаходяться в різних областяхспектру. Розглянемо такий базис квітів:
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. Перетинвектора C з одиничною площиною R + G + B = 1 дає відносні ваги йогочервоної, зеленої і синьої складових. Їх також називають значеннями абокоординатами кольоровості:
Зауважимо,. Розглянемо зв'язок:. Якщо функції вирівнювання за кольоромперенести в тривимірний простір, то результат не буде цілком лежати впозитивному Октант.
У 1931 був прийнятий стандарт CIE (Commission International del'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 |
| хмарності. | | | |
| Опорний білий стандарт для моніторів | 6400К | 0.313 | 0.329 |
| і NTSC. | | | |
Система (x, y, Y) підкоряється законам Грассман. На малюнку показанаколірна область графіка CIE. Як видно, найбільшу площу займають кольоруз перевагою зеленого, що узгоджується з чутливою вибірковістюлюдського ока.
На колірному графіку CIE зручно демонструвати колірний обхватрізних систем і устаткування: телебачення, типографського друку,фотоплівок і т.п. Кольоровий обхват для адитивних систем - трикутник звершинами, що відповідають основним кольорам RGB. Колір, який можнаотримати в цiй колірної моделі лежить всередині трикутника, кольори, що лежатьпоза - отримати неможливо. Приклади колірних обхватів для деяких моделейможна побачити на малюнку. Зауважимо, що для кольорової плівки обхват єкриволінійний трикутник. Причина цього полягає в нелінійному (у даномувипадку логарифмічної) законі створення кольорового зображення за допомогоюкольорової плівки. Нижче наведена таблиця основних кольорів моделей укоординатах колірного графіка 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 задається такою формулою:
, де - кольору для отриманнякоординати одиничного основного кольору R, аналогічно і для G і B. Якщовідомі координати кольоровості CIE x і y для основних кольорів RGB, то:
, де:
- Дані величини необхідні для повного перетворення міжсистемами основних кольорів, також можна отримати і в такий спосіб:
1. Відомі - яскравості одиничних кількостей основних кольорів:
.
2. Відомий - координати кольоровості опорного білого і його яскравість:
Зворотне перетворення CIE XYZ в RGB задається як:
, де c елементами: < p>
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, S, B, у вигляді чорно/білихзображень з 256 рівнями градації сірого.
Канали: Н - тон, 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, c в сумі дають одиницю.
Іноді, для зберігання grayscale зображень використовують на точку 4-7 і 16бітів. У такому випадку ми маємо 16-128 або 65536 відтінків сірого кольору.
Багатоканальні. У даному випадку 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-65535 |
| | | 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 кольорів з 262144 можливих,так як обрані кольору представляються в RGB форматі і для кожної колірноїкомпоненти кодується 6-ма бітами. Існує багато методів перетвореннябагатоканальних зображення в індексовані (Error diffusion, найближчогокольору ...).
Фільтрація зображення.
Поняття фільтрації в даному випадку досить велике, і включає в себе будь-якийперетворення графічної інформації. Фільтрація може бути задана НЕтільки у вигляді формули, але і у вигляді алгоритму, його реалізує. Людиназапам'ятовує графічну інформацію, в основному, у вигляді трьох її складових
1. Низькочастотні складові зображення. Вони несуть інформацію про локалізацію об'єктів, що складають зображення. Ця складова найбільш важлива, тому що зв'язка очей - мозок їй приділяє першорядну увагу.
2. Високочастотні складові зображення. Вони відповідають за колірні перепади - контури зображення. Збільшуючи їх, ми підвищуємо різкість зображення.
3. Текстура зображення. Щоб зрозуміло пояснити, що це таке проведемо невеличкий експеримент. Розслабтеся, згадайте інтер'єр вашого будинку, наприклад, письмовий стіл. Ви знаєте його обриси, місце розташування, колір
- це низькочастотні характеристики, згадали його загострені кути, невелику подряпину де-небудь ближче до його краю - це високочастотні складові. Також Ви знаєте, що стіл дерев'яний, але не можете в точності розповісти про всі найдрібніших деталях його поверхні, хоча загальні характеристики (коричневий з темними западинами, дві області розбіжності концентричних еліпсів від сучків) - напевно. В даному випадку в дужках - опис текстури. Можна трактувати текстуру як характеристику ділянок в контурах зображення.
Будемо розглядати фільтри у вигляді квадратної матриці A. Нехайвихідне зображення X, а одержана як результат фільтрації - Y. Дляпростоти будемо використовувати матриці 3x3:
рекурсивними фільтрами першого роду будуть такі фільтри, вихід 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 - точок на дюйм). Найчастіше - 300dpi. Якщо взяти аркуш паперу 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:
1. LZ77 - при роботі видає трійки виду (A, B, C), де A - зміщення (адресапопередньої ланцюжка B байтів якої збігаються з кодованої ланцюжком), B --довжина ланцюжка, C - перший символ в кодованої масиві, наступний заланцюжком. Якщо збіг не виявлено то створюється трійка виду (0, 0, С),де C - перший символ кодованої ланцюжка. Недолік такого підходуочевидний - при кодуванні «рідкісних» байтів ми «стискаємо» один байт в три.
Перевага - простота реалізації, велика швидкість декодування.
2. LZSS - створює при роботі вектора виду (прапор, C) і (прапор, A, B). Якщобітовий прапор = 0, то наступний за ним C трактується, як одиничний байт івидається у декодіруемий масив. Інакше, коли прапор = 1, то в декодіруемиймасив видається ланцюжок довжиною B по зсуву A. LZSS кодує набагато більшеефективно, в порівнянні з LZ77, так як використовує бітові прапори і малопрограє при кодуванні одиночних символів. При кодуванні будуєтьсясловник зустрічаються ланцюжків у вигляді довічного впорядкованого дерева.
Швидкість і простота алгоритму декодування масиву у LZSS також висока.
3. LZMX (спрощена LZM) - даний алгоритм призначений для швидкісногокодування і за ефективністю поступається LZSS, помітно випереджаючи його зашвидкості роботи. При роботі кодер LZMX формує кілька векторів виду:
4. (0, A, незжатий потік) - де 00-2х бітовий прапор ознаки даного блоку, A (7 бітів з діапазоном в [1 .. 127]) - довжина наступного за ним нестисненого потоку в байтах ..
5. (0, 0000000, A, B) - де, A - кількість повторює байти B.
Тобто код RLE.
6. (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 ...).< br>Загальна властивість LZ - висока швидкість декодування. Загальна проблема --ефективність пошуку кодованих ланцюжків. Модифікація даного алгоритмувикористовується в графічному форматі GIF.
Ентропійно стиснення.
Ентропійно стиснення на відміну від послідовного, в якості інформації провхідному масиві використовує тільки частоти зустрічальності в ньому окремихбайтів. Цю інформацію він використовує як при кодуванні, так і придекодуванні масиву. Її представляють у вигляді 256 компонентного вектора,координата i якого представляє собою скільки разів байт із значенням iзустрічається у вихідному масиві. Даний вектор займає невеликупростір і майже не впливає на ступінь компресії. Багато методівЕнтропійно кодування видозмінюють даний вектор відповідно довикористовуваним алгоритмом. Розглянемо два найбільш часто використовуванихметодів:
Метод Хаффмана. Даний метод скорочує надмірність масиву, створюючипри кодуванні змінну бітову довжину його елементів. Основний принциптакий: найбільш часто зустрічається байту - найменшу довжину, самомурідкісного - найбільшу. Розглянемо найпростіший приклад кодування методом
Хаффмана - спосіб кінцевого нуля. Будь-який елемент кодується ланцюжком бітів,що складається з одних одиниць і закінчуються нулем. Таким чином, найчастішийзакодіруем одним бітом - 0, наступний за ним по частоті як 10, далі -
110, 1110, 11110 і т.д. Процедура декодування також очевидна.
Розглянемо вищесказане на прикладі. Нехай дана частина зображеннядовжиною 80 біт - десять квітів і кожен з них закодований одним байтом
(індексовані 256 кольорами зображення): КЗСГКСКБСК (де К - червоний, З --зелений і т.д.). Закодіруем його. Побудуємо таблицю частоти зустрічальностікольору та коду йому відповідного:
| Колір | Частота | Код |
| К | 4 | 0 |
| З | 1 | 110 |
| З | 3 | 10 |
| Г | 1 | 1110 |
| Б | 1 | 11110 |
Таким чином, ми закодували вихідний масив як 0 110 10 1110 0 10 0
11110 10 0. Разом: довжина вихідного повідомлення - 22 біта. Ступінь компресії
~ 4.
Метод арифметичного кодування. Даний метод з'явився пізніше. Йогопринцип - кодування вихідного масиву одним числом. Часто вхідний масиврозбивають на однакові невеликі ділянки і кодують їх окремо,отримуючи в результаті послідовність кодових чисел. Закодіруемпопередній приклад числом, які лежать в одиничному діапазоні. Схема кодуваннянаступна. Будуємо таблицю частот, кожному елементу таблиці ставимо ввідповідність діапазон, рівний його частоті поділеної на довжину вхідногомасиву. Встановлюємо верхню межу ВГ в 1, нижню НГ у 1. Далі 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.19008 | 0.00048 |
| 6 | З | 0.18984 | 0.189984 | 0.000144 |
| 7 | К | 0.18984 | 0.1898976 | 0.0000576 |
| 8 | Б | 0.1898918 | 0.1898976 | 0.00000576 |
| | | 4 | | |
| 9 | З | 0.1898947 | 0.189896448 | 0.000001728 |
| | | 2 | | |
| 10 | К | 0.1898947 | 0.189895411 | 0.000000691 |
| | | 2 | 2 | 2 |
Таким чином, будь-яке число в діапазоні [0.18989472 .. 0.1898954112]однозначно кодує вихідний масив. У двійковому дробному вигляді як
0.XXXXXXXX ... Для зберігання такої кількості вистачить n біт (розмірність
XXXXXXXX ....), де n найближчим ціле, яке задовольняє нерівності: 2n>
Інтервал-1 = 0.0000006912-1. Шукалося n одно 21. Тобто ми можемозакодувати вихідний масив 21 бітом. У даному прикладі -
001100001001110111111. Процедура декодування зворотний і полягає ввиконання n раз наступного:
1. Шукаємо в таблиці інтервал, в який потрапляє наше число Ч, і видаємо символ в нього входить до декодіруемий масив.
2. Інтервал И = ВГ символу - НГ символу (обидва значення - з таблиці).
3. Ч = (Ч - НГ)/І.
| Крок | Число | Символ | НГ | ВГ | Інтервал |
| 1 | 0.1898947 | К | 0 | 0.4 | 0.4 |
| | 2 | | | | |
| 2 | 0.4747368 | З | 0.4 | 0.5 | 0.1 |
| 3 | 0.747368 | С | 0.5 | 0.8 | 0.3 |
| 4 | 0.82456 | Г | 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
