Главная
База знаний "Allbest"
Программирование, компьютеры и кибернетика
Система стиснення відеоданих на основі аналізу ентропійності
Система стиснення відеоданих на основі аналізу ентропійності
Програмний продукт "Графічний кодер чорно-білих зображень". Аналіз технологій одержання компактних подань відеоінформації способом організації кодування й пошук шляхів підвищення їх ефективності. Кодування зображень на основі зміни градації яскравості.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | украинский |
| Дата добавления | 29.06.2009 |
| Размер файла | 1,8 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
“ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ"
Кафедра Обчислювальна техніка та програмування
Спеціальність Системне програмування
До захисту допускаю
Завідувач кафедри
ДИПЛОМНИЙ ПРОЕКТ
Освітньо-каліфікаційного рівня спеціаліст
Тема проекту: Cистема стиснення відеоданих на основі аналізу ентропійності
Харків 2009
ЗАВДАННЯ
на виконання дипломного проекту
1. Тема проекту Система стиснення відеоданих на основі аналізу ентропійності______________________________________________________
2. Зміст завдання Дослідити проблеми кодування відеоінформації, призначення й мету створення системи. Розробити загальну структуру програми та алгоритм. Розробити програмне забезпечення. Вивести результати роботи та тестування. Ознайомитись з питаннями охорони праці та навколишнього середовища. Зробити економічну оцінку проекту у вигляді бізнес-плану.
3. Вихідні дані для виконання проекту Айвазян С.А., Мхитарян.В.С. Прикладная статистика и основы эконометрики; Дидэ Э. и др. Методы анализа данных; Кричевский Р.Е. Сжатие и поиск информации; Куренков Н.И. Ананьев С.Н. Энтропийный подход к решению задач классификации многомерных данных; Левенштейн В.И. Об избыточности и замедлении разделимого кодирования натуральных чисел; Семенюк В.В. Применение вероятностного моделирования в методах экономного кодирования видеоинформации; Сакоян С.А. Об оптимальных разбиениях на градации в задачах классификации; Семенюк В.В. Экономное кодирование дискретной информации
4. Скласти звіт і виконати необхідні документи (програмні, плакати) відповідно до плану виконання дипломної роботи
Найменування програмного продукту "Графічний кодер чорно-білих зображень”. Розробляється для дипломного проекту "Система стиснення відеоданих на основі аналізу ентропійності".
Область застосування програмного продукту вищі учбові заклади, книжкові та газетні видавництва, служби охорони, та державна служба безпеки. Програмний продукт дозволяє будь-які 256-кольорові чорно-білі зображення, які зберігаються у форматі. jpeg або. bmp, у зображення. bmp з меншою кількістю кольорів (від 2 до 16) із зберіганням інформативності зображення. Для покращення результатів обробка зображення виконується декількома методами, з метою отримати найбільш вигідне зображення.
1. ПІДСТАВА ДЛЯ РОЗРОБКИ
Розробка ведеться відповідно до наказу по Національному технічному університету "Харківський політехнічний інститут"
№_3001 - ІІІ_ від “_21_" _листопада_ 2008 р. Найменування програмного продукту: "Графічний кодер чорно-білих зображень".
Розробляється для дипломного проекту "Система стиснення відеоданих на основі аналізу ентропійності".
2. ПРИЗНАЧЕННЯ РОЗРОБКИ
Розроблюваний програмний продукт повинен розв'язувати важливі питання в галузі роботи з графічними зображеннями чорно-білого формату, з метою запропонувати користувачам метод кодування інформації на основі аналізу ентропійності, який дозволяє стиснути зображення у менший розмір, з меншою кількістю кольорів, але при цьому зберігаючи інформативність зображення.
Програма може використовуватися у вищих учбових закладах для проведення практичних занять з теорії кодування відеоінформації, у книжкових та газетних видавництвах для покращення чорно-білих малюнків на сторінках, та у службах охорони та безпеки, для зберігання фотоінформації, відбитків пальців, тощо.
3. ВИМОГИ ДО ПРОГРАМНОГО ПРОДУКТУ
Функціональні характеристики
Розроблюваний програмний продукт повинен забезпечувати:
Відкриття зображення з його виводом на екран;
Кодування відеоінформації методами на основі аналізу ентропійності;
Кодування інформації методом рівномірної розбивки;
Вивід отриманого зображення на екран;
Зберігання інформації у формат. bmp з кількістю кольорів 16.
Вивід гістограми початкового та кінцевого зображення
3.2 Вимоги до надійності
Розроблений програмний продукт повинен відповідати наступним вимогам за критерієм надійності:
коректно працювати, тобто не призводити до припинення роботи ПЕОМ, яке може виникнути у ході роботи програмного продукту;
відмова в роботі не повинна призвести до втрати даних у базі даних тестів.
3.3 Умови експлуатації
Програмний продукт повинен функціонувати у нормальних умовах для персоналу:
температура навколишнього середовища від 100 С до 320 С;
вібрації, зовнішні магнітні, радіаційні та електричні поля не повинні перевищувати норми.
Для нормальної експлуатації програмного продукту обслуговуючому персоналу необхідні знання по експлуатації ПК.
3.4 Вимоги до складу і параметрів технічних засобів.
Для експлуатації програмного продукту необхідна ПЕОМ з наступними апаратними характеристиками:
1) стандартна конфігурація IBM-сумісних ПК;.
2) процесор з частотою не менше 750 МГц;
3) ОЗП обсягом не менше 256 Мбайт;
4) жорсткий диск обсягом не менше 100 Гбайт;
5) сумісні монітор та відео адаптер;
6) маніпулятор типа “миша”;
7) мережна карта
8) зв`язок з іншими машинами за допомогою кабелів (витої пари, або оптоволокна), або радіозв`язку.
3.5 Вимоги до інформаційній та програмної сумісності
Розроблений програмний продукт повинен функціонувати на ПЕОМ з операційними системами Microsoft Windows 2000/XP.
3.6. Вимоги до маркування та упаковки
Вимоги до маркування та упаковки програмного продукту, розробленого в роботі на тему: “ Система стиснення відеоданих на основі аналізу ентропійності ” не пред'являються.
3.7. Вимоги до транспортування та збереження.
Вимоги до транспортування та збереження програмного продукту “ Графічний кодер чорно-білих зображень ” не пред'являються.
4. ВИМОГИ ДО ПРОГРАМНОЇ ДОКУМЕНТАЦІЇ
Для дипломної роботи, що розробляється, повинні бути складені наступні програмні документи:
1. Специфікація.
2. Опис програми.
3. Текст програми.
4. Керівництво оператора.
5. ТЕХНІКО-ЕКОНОМІЧНІ ПОКАЗНИКИ
Техніко-економічні показники повинні бути визначені в процесі розробки і зазначені у відповідному розділі звіту про виконання дипломного проекту.
6. СТАДІЇ ТА ЕТАПИ РОЗРОБКИ
Розробка програмного продукту відповідає стадії робочого проекту. Етапи розробки виконують в наступному порядку:
отримання завдання;
збір початкових матеріалів;
огляд літератури й обґрунтування необхідності розробки;
визначення областей застосування;
розробка технічного завдання;
техніко-економічне обґрунтування розробки;
розробка алгоритму розв'язання задачі;
розробка структури програмного продукту;
визначення конфігурації програмних засобів;
розробка звіту дипломного проекту;
програмування і відлагодження програмного продукту;
розробка програмних документів;
тестування програмного продукту;
коректування програми та програмних документів за результатами тестування.
7. ПОРЯДОК КОНТРОЛЮ І ПРИЙМАННЯ
При прийманні дипломної роботи перевіряється:
1. Комплектність, зміст та оформлення документації згідно розділу 4 цього документу.
2. Відповідність програмного продукту згідно вимогам до програмного продукту розділу 3 цього документу.
РЕФЕРАТ
Звіт про ДП: 98 стр., 15 рис., 18 табл., 32 джерела
КЛЮЧОВІ СЛОВА: ентропія, квантування, гістограма яскравості, кодування, стиснення, оптимальна градація, зображення.
У даній роботі розглянуті питання кодування відеоінформації, а точніше, 256-кольорових зображень на основі аналізу ентропійності, сформульовані умови градації яскравості зображення, знайдено коефіцієнт оптимального співвідношення яскравості кластерів, розроблено алгоритм зберігання отриманого зображення та побудови гістограм яскравостей.
Розроблено алгоритм і програма реалізації завдання. Чітко сформульовані основні проблеми, існуючи при кодуванні відеоінформації, та визначено новий комплексний підхід для їх вирішення.
Розглянуті питання охорони праці й навколишнього середовища, проведена техніко-економічна оцінка роботи. На підставі аналізу результатів зроблені висновки й рекомендації для подальшої роботи в даному напрямку.
Зміст
- ЗАВДАННЯ на виконання дипломного проекту
- РЕФЕРАТ
- Вступ
- 1. Імовірнісний підхід у теорії кодування відеоінформації
- 1.1 Інформаційний опис
- 1.2 Імовірнісний підхід
- 1.2.1 Ентропія
- 1.2.2 Дешифровані коди
- 1.2.3 Оптимальна довжина коду
- 1.3 Методи генерації коду
- 1.3.1 Префіксне кодування
- 1.3.2 Алгоритм Шеннона
- 1.3.3 Алгоритм Хаффмана
- 1.4 Основні результати і висновки
- 2. Розробка імовірнісних методів для підвищення ефективності кодування
- 2.1 Квантування
- 2.2 Побудова інформаційного критерію
- 2.2.1 Оцінка інформативності ознак
- 2.2.2 Оптимальна градація ознак.
- 2.2.3 Градація перших 100 чисел натурального ряду
- 2.2.4 Градація яскравостей зображень
- 3. Розробка ефективного алгоритму кодування зображень на основі зміни градації яскравості
- 3.1 Загальна структура програми
- 3.3 Розробка алгоритму завантаження зображення з файлу
- 3.4 Розробка перетворення кольорового зображення у чорно-біле
- 3.5 Розрахунки гістограми яскравостей
- 3.6 Розробка функції обчислення порогового значення відрізку масиву яскравостей зображення
- 3.7 Розробка рекурсивної процедури розділення масиву гістограми яскравостей та складання масиву відповідностей елементів палітри
- 3.8 Розробка функції ентропійного кодування зображення
- 3.9 Опис використаних компонентів
- 4. Тестування програми
- 5. Техніко-економічна частина
- 5.1 Позначка й призначення
- 5.2 Оцінка ринку збуту
- 5.3 Оцінка конкурентноздатності
- 5.4 Стратегія маркетингу
- 5.4.1 Оцінка витрат на розробку продукту
- 5.4.2 Реклама
- 5.5 Оцінка ризику і страхування
- 5.6. Фінансовий план
- 5.7 Висновок
- 6. Охорона праці і навколишнього середовища
- 6.1 Основні питання охорони праці
- 6.2 Промислова санітарія
- 6.2.1 Мікроклімат
- 6.2.2 Виробниче освітлення
- 6.2.3 Шум
- 6.2.4 Випромінювання від екрана
- 6.3 Техніка безпеки на робочому місці
- 6.3.1 Електробезпека
- 6.3.2 Ергономічні вимоги до робочого місця
- 6.4 Пожежна безпека
- 6.5 Охорона навколишнього середовища
- Висновки
- Список джерел інформації
- Додаток
- Текст програми
- Керівництво оператора
- Опис програми
Вступ
На сьогоднішній день актуальна проблема зберігання й передачі інформації в цифровому виді. Для одержання компактних інформаційних подань застосовуються технології ощадливого кодування. Використання цих технологій дозволяє істотно знизити вимоги, пропоновані до обсягу інформаційних носіїв, а також відчутно збільшує швидкість передачі інформації з каналів зв'язку.
Передача інформації є основною областю застосування ощадливого кодування. На даний момент першочергове завдання - організація ефективного телевізійного й мультимедійного віщання. Як відомо, відеоінформація являє собою найбільш об'ємний тип інформації. З обліком обмеженої пропускної здатності цифрових каналів, щоб гарантувати високу якість передачі зображень, необхідно забезпечити їх досить ефективне подання (якість передачі прямо залежить від обсягу інформації, переданого в одиницю часу). Як наслідок, протягом уже більше 15 років значні зусилля направляються на розробку технологій ефективного подання зображень. Цій проблемі присвячена й дана дипломна робота.
Основна мета роботи - аналіз існуючих технологій одержання компактних подань відеоінформації з погляду способу організації кодування й пошук можливих шляхів підвищення їхньої ефективності.
Вибір напрямку дослідження заснований на результатах порівняльного аналізу існуючих алгоритмів ощадливого кодування. Алгоритм ощадливого кодування являє собою певний спосіб генерації ощадливого коду на основі наближеної моделі породження кодуємої інформації. З метою зниження обчислювальної складності на практиці довгий час застосовувалися спрощені методи інформаційного моделювання й генерації коду. Як моделі бралися найпростіші комбінаторні моделі, а генерація коду здійснювалася з використанням найбільш швидких реалізацій префіксного кодування. У цей час постановка завдання змінилася: на перший план стала всі частіше виходити ефективність кодування. Сьогодні стає доцільним застосування більше складних технологій кодування, які дозволяють досягти максимально компактного інформаційного подання.
Одним з найбільш ефективних методів інформаційного моделювання є імовірнісне контекстно-залежне моделювання. При використанні даного методу вибір інформаційної моделі в кожен момент часу здійснюється на основі значення деякого контексту, що формується з елементів уже обробленої інформаційної вибірки. Уводячи контексти, ми фактично вирішуємо завдання ідентифікації станів інформаційного джерела. Для кожної моделі зберігається статистична інформація про появу різних символів інформаційного алфавіту в контексті, що відповідає даної моделі. На основі цієї інформації формується розподіл імовірнісних оцінок появи символів на виході джерела, що є основою для генерації коду.
Арифметичне кодування являє собою найбільш ефективний метод генерації коду по заданому імовірнісному розподілі. Використання цього методу дозволяє одержувати коди, довжини яких мало відрізняються від теоретично оптимальних значень.
Таким чином, сполучення контекстно-залежного імовірнісного моделювання й арифметичного кодування найбільше вигідно з погляду ефективності. При цьому найбільш ефективним буде кодування інформації на основі аналізу її ентропійності - завдяки такому підходу, ми зможемо гарантувати зменшення обсягу відеоінформації, за умови зберігання достатнього рівня інформаційності, тобто зображення залишається досить чітким, але кількість кольорів зображення зменшується, при цьому чоловіче око може аналізувати цю інформацію на рівні із попередньою.
Тому в дипломній роботі приділимо увагу до кодування найпростішого виду відеоінформації - чорно-білого зображення, що дає можливість отримати основи алгоритмів для кодування більш складних видів зображень, як кольорові картинки та відео файли.
1. Імовірнісний підхід у теорії кодування відеоінформації
1.1 Інформаційний опис
Теорія ощадливого кодування займається проблемою створення ефективних подань інформаційної вибірки. Мова в більшості випадків іде про вибірку джерел дискретної інформації з кінцевим алфавітом. Ефективне кодування стає можливим завдяки наявності в інформації певних особливостей, тому однієї з найбільш важливих задач є одержання як можна більше точного опису властивостей інформаційних джерел.
Існує кілька підходів до такого роду опису. Найбільше часто використовувані - комбінаторний й імовірнісний.
У рамках комбінаторного підходу символи розглядаються не обособлено, а групами, іменованими інформаційними повідомленнями. Покладається, що з виходу джерела інформації можуть надходити не всі можливі повідомлення, а тільки повідомлення з деякого виділеної множини. При цьому повідомлення, що належати даній множині, уважаються зовсім рівнозначними, тобто їхня поява покладається рівноймовірним. Конкретний вибір множини припустимих повідомлень виконує роль інформаційного опису.
Комбінаторний підхід одержавши досить широке поширення на практиці. Основним його достоїнством є простота опису інформаційних особливостей, тому практичні реалізації методів ощадливого кодування, в основі яких лежить даний підхід, мають низьку обчислювальну складність.
Недолік полягає в тім, що точність опису годиною прямо залежить потужності множини припустимих повідомлень - для одержання досить точного опису може знадобитися розглянути дуже велика кількість повідомлень. Комбінаторний підхід також не дозволяє одержувати інформаційні характеристики для окремих символів усередині повідомлення.
Суть імовірнісного підходу полягає у використанні імовірнісних оцінок фактів появи різних символів на виході джерела інформації. У порівнянні з комбінаторним підходом імовірнісний підхід є більше точним способом опису властивостей інформаційних джерел. У тієї ж година імовірнісний підхід менш вигідний з обчислювальної крапки зору, тому що його застосування сполучене з обчисленням складних імовірнісних оцінок. Таким чином, з одному боку, імовірнісний опис, як правило, більш ефективно в порівнянні з комбінаторним описом, з іншого боку, імовірнісний опис не завжди можна використати на практиці через існуючі обчислювальні обмеження. Постійне збільшення продуктивності обчислювальних систем робить останній фактор менш значимим, внаслідок чого імовірнісний підхід останнім годиною всі частіше й частіше береться за основу при розробці алгоритмів ощадливого кодування.
1.2 Імовірнісний підхід
1.2.1 Ентропія
Основоположником імовірнісного підходу є Шеннон. Він запропонував ввести характеристику невизначеності інформації H (p1; p2; …; pN), що залежить від імовірностей p1; p2; …; pN появи символів алфавіту A потужності N на виході інформаційного джерела. Шеннон зажадав, щоб міра невизначеності, за аналогією з аналогічною фізичною характеристикою названа їм ентропією, мала наступні властивості:
величина H (p1,p2,...,pn) інваріантна щодо перестановок аргументів p1,p2,...,pn;
функція H (p1,p2,...,pn) безперервна по шкірному з аргументів своїх аргументів p1,p2,…,pn]
функція A (N) = H (1/N,…1/N) з кількістю елементів 1/N=N, монотонно зростає по N
виконується співвідношення: H (p1; p2; …; pk; pk+1; …; pk+l) = H (p1; p2; …; pk; ps) + psH (pk+1/ ps,…, pk+l/ps), де ps = сума від 1 до l (pk+1).
Як показав Шеннон, функція, що задовольняє зазначеним властивостям, має вигляд H (p1; p2; …; pN) = - K?pi logm pi, де K та m - деякі позитивні константи. Для зручності пропонується вибирати K рівним одиниці, а в якості m брати основу системи подання інформації. Як показує практика, такий вибір багато в чому виправданий. Наприклад, у системі подання інформації з підставою 2 невизначеність появи одного із двох символів, що з'являються з рівною ймовірністю, виявляється рівної 1 біту. Це добрі погодиться з визначенням біта як одиниці інформації, необхідної для подання вибору одного із двох равновероятных подій. Таким чином, підсумкова формула для обчислення ентропії інформаційного джерела з імовірнісним розподілом появи символів {pi}Ni=1 виглядає в такий спосіб:
|
(1.1) |
Формула (1.1) дозволяє визначити ентропію джерела, що перебуває в деякому конкретному стані. Ентропія джерела в цілому - безвідносно до конкретного стану - може бути визначена далеко не завжди. Можливість визначення ентропії залежить від імовірностей тихнув або інших станів і відповідних цих станів ансамблів перехідних імовірностей (перехід зі стану в стан здійснюється при породженням джерелом чергового символу). Розглянемо окремий випадок, коли інформаційне джерело S може перебувати в одному з T станів, причому чітко відомі всі ймовірності переходів джерела з будь-якого стану i у стан j (pij). Якщо існує межа , де Р - матриця з компонентами pi,j, величина ентропії джерела S може бути обчислена по формулі
|
(1.2) |
Отут pi - імовірність знаходження джерела S в i-м стані (pi є значення i - елемента будь-якого рядка матриці P?), a m - підстава системи подання інформації.
Множина станів інформаційного джерела в сукупності з ансамблем перехідних імовірностей прийнято називати моделлю станів або марковской моделлю. Для визначення ентропії джерела інформації в рамках даної моделі необхідно правильно підібрати її структуру й параметри, які повинні повною мірою відповідати джерелу. На практиці це досить важко, тому що параметри інформаційних джерел, як правило, апріорі не відомі1. Визначити їх можна тільки приблизно, тому при рішенні практичних задач доводити прибігати до емпіричних способів оцінки ентропії. Як правило, мова йде про усереднення величини ентропії за годиною.
Нехай джерело послідовно перебуває в станах s1, s2,..., sn, які відповідають розподілу ймовірностей появи символів
Через рі1, і2, іn позначимо ймовірність появи на виході джерела послідовності символів з індексами i1, i2,..., in (символ ik породжується джерелом у стані sk). Очевидно, що
|
(1.3) |
Напівемпіричною ентропією джерела назвемо величину
|
(1.4) |
З урахуванням тотожності (1.3) формула (1.4) приводитися до більше зручного для обчислення виду
Приставка "напів" означає, що для отримання ентропії частино використовуються апріорні дані про імовірнісні характеристики джерела (відомий розподіл імовірностей появи символів у різних станах), а частина, що залишилася, інформації - конкретна послідовність станів - виходить емпіричним шляхом. У реальних задачах, як правило, подібної апріорної інформації ні, тому доцільно ввести поняття емпіричної ентропії, визначивши її величину по формулі:
|
(1.6) |
У цьому випадку ri (sj) - емпірична оцінка ймовірності появи символу з індексом i при породженні j-й вибірки джерела інформації1. Причина, по якій особлива увага приділяється способах обчислення ентропії, полягає в тім, що величина ентропії є чисельною границею ефективності ощадливого кодування вибірки інформаційного джерела. Знаючи ентропію, можна оцінити ефективність того або іншого методу або алгоритму. В ідеалі ефективність винна збігатися з величиною ентропією. При цьому, якщо природа інформаційного джерела не є імовірнісної, тобто чітко виділити ті або інші імовірнісні стани не можна, мова може йти тільки про ентропію, що обчислює частково на емпіричній основі. В силу останньої обставини, надалі при вживанні терміна ентропія найчастіше буде матися на увазі напівемпірична ентропія.
Обчислення ентропії на практиці можна здійснювати в процесі послідовного аналізу станів інформаційного джерела, що безпосередньо треба з формул (1.5) і (1.6). Як видно з наведених формул, величина ентропії складається з величин ентропії в станах, у яких послідовно перебуває джерело інформації. Таким чином, задача оптимального моделювання послідовної інформаційної вибірки зводиться до задачі створення оптимальної моделі породження символів у шкірному конкретному стані, що є істотним спрощенням. Як буде показаний нижче, подібне спрощення припустиме й відносно механізму генерації коду, тобто воно фактично припустимо відносно методу кодування в цілому.
1.2.2 Дешифровані коди
Найпростіший варіант кодування вибірки інформаційного джерела - установлення відповідності між конкретними символами алфавіту й кодами, що мають цілу довжину в одиницях подання інформації. Природно зажадати, щоб код, отриманий у результаті такого кодування, був дешифрованим, тобто по будь-якій комбінації кодів символів можна було б відновити закодоване повідомлення. Необхідна умова дешифруємості було запропоновано й доведене Макмілланом. Формулювання виглядає в такий спосіб: якщо система кодів із цілими довжинами {li}Ni=1 дешифровані, те виконується нерівність
|
(1.7) |
де m - підстава системи подання інформації.
Виконання нерівності (1.7) спричиняє виконання більше важливої нерівності:
|
(1.8) |
Для доказу досить скористатися опуклістю функції logm (x). Таким чином, ефективність дешифрованого посимвольного кодування обмежена величиною ентропії імовірнісного розподілу появи символів на виході інформаційного джерела.
Більше складний й у той же час найбільше ефективний варіант кодування має на увазі одержання кодів не для окремих символів, а для цілих повідомлень. Коди декодуємих повідомлень, мабуть, також повинні задовольняти нерівності Макміллана. При цьому оцінка ефективності з розрахунку на один символ повідомлення ускладнюється необхідністю проведення усереднення по довжині повідомлення. Покажемо, що ефективність кодування вибірки інформаційного джерела зазначеним способом також обмежується величиною ентропії.
Будемо використати раніше уведені позначення. Джерело, що послідовно перебуває в станах s1, s2,..., sn, як і раніше, характеризується імовірнісними розподілами
.
Через pi1, i2,..., in позначається ймовірність появи повідомлення "i1, i2,... in", через li 1, i2,..., in - довжина коду повідомлення. Ефективність кодування повідомлень довжини n з розрахунку на один символ визначається по формулі
Коди для повідомлень довжини n повинні бути дешифрованими, тому можна скористатися нерівністю (1.8):
Права частина нерівності являє собою вираження для ентропії. Таким чином, ефективність кодування з розрахунку на один символ не може перевершувати величину ентропії повідомлення, що доводити на один символ. Використовуючи формулу (1.5), одержуємо більше зручну з обчислювальної крапки зору оцінку:
Якщо джерело, що породжує повідомлення, є стаціонарним (імовірнісний розподіл не залежить від позиції символу в повідомленні), нерівність здобуває спрощений вид:
1.2.3 Оптимальна довжина коду
Тому що код виходить для повідомлення в цілому, не можна говорити про коди для конкретних символів, що становлять повідомлення. Проте виникає необхідність визначати деякий внесок у результуючу довжину коду повідомлення, внесень кожним вхідної в нього символом. Фізичний зміст такого внеску - середнє збільшення довжини коду повідомлення, обумовлене входженням у нього даного символу. Позначимо через xi внесок, внесень символом з індексом i (у загальному випадку величина внеску являє собою речовинне число). Через xi1, i2,..., in позначимо внесок, внесень повідомленням s = i1, i2,..., in - Виходячи зі змісту поняття "внесок", для випадку стаціонарної незалежної вибірки логічно зажадати виконання наступних властивостей:
(адитивність)
,
де li1, i2,..., in - довжина реального коду повідомлення (ціле число), а M (n) - ненегативна функція, така що M (n) /n - > 0 при n - > оо
Асимптотичне поводження функції M (n) /n дозволяє зробити висновок:
|
(1.9) |
Таким чином, отримане узагальнення нерівності Макміллана на випадок внесків символів у результуючу довжину повідомлень.
Узагальнена нерівність (1.9) дозволяє обчислити точне значення величини внеску xa символу з індексом a для випадку оптимального кодування. Для обчислення точного значення необхідно вирішити задачу про мінімізацію суми
,
яка визначає середню ефективність кодування, за умови виконання нерівності (1.9). У крапці мінімуму похідна від зазначеної суми звертається в нуль:
|
(1.10) |
Підстановка рішення задачі про мінімізацію в нерівність (1.9), мабуть, повинне перетворювати його в рівність. Звідси будь-який оптимальний внесок xk легко виражається через внески інших символів:
Підставляючи вираження для xk у рівняння (1.10), одержуємо
Після узяття похідної рівняння здобуває наступний вид:
, або
Індекс k може приймати одне з N значень, тобто реально для шкірного фіксованого індексу a є N рівнянь. Просумувавши ці рівняння, одержимо
що з урахуванням виконання рівності у вираженні (1.9) рівносильне
Звідси отримаємо формулу для xa:
|
(1.11) |
Таким чином, оптимальний внесок символу, що з'являється з імовірністю p: у довжину результуючого коду становить logm p одиниць інформації в системі подання з підставою m. - анный висновок може бути використаний для обчислення оптимальної довжини коду в рамках тієї або іншої імовірнісної моделі. Одержуючи оцінку ймовірності появи чергового символу на деякому етапі кодування, можна точно визначити оптимальну довжину відповідного інформаційного опису.
1.3 Методи генерації коду
1.3.1 Префіксне кодування
Серед кодів, що задовольняють нерівності Макміллана, особливе місце займають префіксні коди. Система кодів називається префіксною, якщо жоден з кодів, що належить системі, не є качаном (префіксом) іншого коду із цієї ж системи. Очевидне достоїнство префіксного кодування полягає в тім, що одержуваний код може бути легко декодований. Завдяки властивості префікса для того, щоб визначити черговий закодований символ (повідомлення), досить проаналізувати качан відповідної чергової порції коду. При цьому довжина аналізованої порції ніколи не перевищує довжину коду чергового закодованого символу (повідомлення).
Геометрична трактування систем префіксних кодів - m-арные дерева. Властивість префікса гарантує відсутність циклів у графі, ребрам якого зіставлені різні значення інформаційної одиниці. Таким чином, граф є деревом зі ступенем розгалуження, що збігає з підставою системи подання інформації m. Слід зазначити, що нумерація ребер може бути здійснена довільним образом; значення має тільки конкретна структура дерева, а точніше - набір відстаней від кореневого вузла до листових вузлів. Ці відстані відповідають довжинам кодів префіксної системи. Крафт показав, що виконання нерівності (1.7) є гарантією існування кодового дерева зі структурою, що відповідає набору довжин , що фігурують у нерівності. Інакше кажучи, якщо система довжин задовольняє нерівності (1.7), можна побудувати систему префіксних кодів з відповідними довжинами. Дане твердження дозволяє відмовитися від розгляду систем кодів, відмінних від префіксних. Будь-яка система дешифрованих кодів задовольняє нерівності (1.7), а виходить, вона може бути без шкоди для ефективності замінена системою префіксних кодів. Нерівність (1.7) стосовно до систем префиксних кодів називають також нерівністю Крафта.
Розглянемо блокове кодування повідомлень довжини n, породжуваних деяким інформаційним джерелом. Як і раніше, позначимо через
імовірнісний розподіл появи j-ro символу повідомлення (sj - відповідний стан джерела), через pi1, i2,..., in - імовірність появи повідомлення "i1, i2,..., in". Відповідно до твердження Крафта, можна побудувати систему префіксних кодів із длинами
(Для доказу досить підставити ці довжини в нерівність Крафта й переконатися в тім, що воно виконується) Оцінимо ефективність кодування з розрахунку на один символ повідомлення:
Використовуючи альтернативне вираження для ентропії (1.5), одержуємо
Для випадку стаціонарного джерела з розподілом імовірностей
маємо:
Збільшуючи довжину повідомлення n, можна домогтися ефективності кодування як завгодно близької до ентропії джерела інформації. Таким чином, знаючи апріорі ймовірності появи різних символів на виході джерела в кожен конкретний момент часу, можна організувати кодування даного джерела, наближене до оптимального кодування на кожну наперед задану величину, за умови, що є достатній об'єм інформаційної вибірки.
1.3.2 Алгоритм Шеннона
Алгоритм побудови системи префиксних кодів з довжинами, що залежать від імовірностей по формулі , був запропонований Шенноном. Алгоритм працює в такий спосіб. Імовірності появи повідомлень p1,p2,...,pn розташовуються в порядку убування (тут N - потужність множини повідомлень). Не обмежуючи спільності, можна вважати
.
Як код повідомлення з індексом i беруться перші m-ичных розрядів числа так називаної накопиченої ймовірності. Тому що довжини кодів у такій системі не убувають зі зменшенням імовірності й імовірності появи повідомлень із індексами i+1, i+2,...,N відрізняються від імовірності появи повідомлення з індексом i принаймні на , код повідомлення з індексом i не є початком кодів повідомлень із індексами i+1, i+2,...,N. Таким чином, система кодів є префіксною. Розглянемо геометричне трактування алгоритму Шеннона. Інтервал [0,1) може бути розбитий на N підінтервалів
,
відповідним повідомленням з індексами i = 1, 2,...,N. Для ідентифікації i-го повідомлення необхідно вибрати деяке число з підінтервалу [ai, bi), представиме як можна меншою кількістю m-ічних розрядів. Для цього потрібно побудувати на інтервалі [0,1) одномірну мережу з постійним періодом, що містить крапок (місце розташування будь-якої крапки визначається li-розрядним числом), рівно одна з яких (ідентифікуюча) належить інтервалу [ai, bi). Ясно, що шукана мережа повинна мати період, що не перевищує pi, тобто . Звідки отримуємо .
Алгоритм Шеннона дозволяє генерувати коди, довжина яких відрізняється від оптимальних значень, обумовлених по формулі (1.11), менш чим на одну інформаційну одиницю. Таким чином, різниця між ефективністю кодування й ентропією (так називана надмірність) не перевищує одиниці.
1.3.3 Алгоритм Хаффмана
Алгоритм Шеннона має досить високу ефективність, однак він не є оптимальним алгоритмом побудови системи префіксних кодів. Для знаходження оптимального алгоритму необхідно при фіксованому наборі ймовірностей {p1,p2,...,pn} вирішити задачу про мінімізацію суми за умови виконання нерівності Крафта (тут li - довжина коду повідомлення з індексом i).
На практиці алгоритм Хаффмана реалізується в такий спосіб. На початковому етапі кожному повідомленню ставиться у відповідність вага, дорівнює оцінці ймовірності появи даного повідомлення. Повідомлення містяться в список, що впорядковується по убуванню ваг. Надалі елементи списку обробляються з використанням ітеративної процедури. На кожному кроці (ітерації) m останніх елементів списку поєднуються в новий елемент, що потім міститься в список замість поєднуваних елементів. Новому елементу списку ставиться у відповідність вага, дорівнює сумі ваг елементів, що заміщають. Кожна ітерація закінчується впорядковуванням отриманого нового списку, що завжди містить на один елемент менше, ніж старий список. Паралельно з роботою зазначеної процедури здійснюється послідовна побудова m-арного дерева. На кожному кроці алгоритму будь-якому елементу списку відповідає кореневий вузол m-арного дерева, що складає з вершин, що відповідають елементам, об'єднанням яких був отриманий даний елемент. При об'єднанні m елементів списку відбувається об'єднання відповідних дерев в одне нове m-арне дерево, у якому кореневий вузол відповідає новому елементу, що поміщає в список, а заміщають елементам, що, списку відповідають дочірні вузли цього кореневого вузла. Алгоритм завершує роботу, коли в списку залишається один елемент, що відповідає кореневому вузлу побудованого бінарного дерева. Для гарантії коректного завершення роботи алгоритму вихідний розмір списку повинен мати довжину, представиму у вигляді n* (m-1) +1. Якщо кількість повідомлень не відповідає цій довжині, список доповнюється до необхідного розміру за рахунок додавання в кінець фіктивних елементів, що мають нульові ваги. Побудоване в результаті описаної процедури дерево називається деревом Хаффмана. Система префіксних кодів може бути отримана шляхом присвоєння конкретних m-арних значень ребрам цього дерева.
Алгоритм Хаффмана має найбільшу ефективність серед алгоритмів побудови префіксних кодів по заданому імовірнісному розподілі1. Очевидний недолік алгоритму - більша обчислювальна складність. Алгоритм доцільно використати в тих випадках, коли імовірнісний розподіл залишається незмінним для досить великого об'єму інформаційної вибірки. Застосування алгоритму Хаффмана у випадку, коли статистичні характеристики інформаційного джерела швидко міняються, сильно утруднено необхідністю здійснення частих змін структури кодового дерева. Галлагером був запропонований ефективний спосіб зміни структури дерева Хаффмана, не потребуючий його повної перебудови. Застосування даного способу хоча й приводить до істотного спрощення хутранизма генерації коду, проте не завжди дозволяє досягти необхідної швидкості обробки інформації. Тим же недоліком володіють і практичні реалізації алгоритму Шеннона.
1.4 Основні результати і висновки
У даній главі були докладно розглянуті різні аспекти імовірнісного підходу в теорії ощадливого кодування. Викладено методи побудови імовірнісних моделей, методи генерації коду змінної довжини на основі імовірнісних розподілів, методи одержання імовірнісних оцінок. Отримано наступні важливі результати:
Сформульовано й доведена нерівність Макміллана для випадку нероздільних кодів. Обчислено величину оптимального внеску символу в результуючу довжину коду повідомлення (див. розділ 1.2.3).
Алгебраїчно доведена оптимальність алгоритму Хаффмана для системи подання інформації з довільною підставою (див. розділ 1.3.3).
Наведені результати є серйозним внеском у теорію ощадливого кодування. Ці результати можуть бути використані при розробці й аналізі нових методів одержання ефективних подань інформації різної природи.
Нажаль, серед наведених алгоритмів нема ідеального для виконання ентропійного кодування відеоінформації. Тому у наступному розділі ми запропонуємо метод, та розробимо алгоритм і програму, яка буде виконувати стиснення зображення, з метою зменшити кількість кольорів у зображенні, але зберегти його інформаційність. Цей алгоритм також не буде ідеальним, але його можна застосовувати як швидкий і зручний спосіб стиснення зображення.
2. Розробка імовірнісних методів для підвищення ефективності кодування
2.1 Квантування
Ефективність ощадливого кодування природного напівтонового зображення (наприклад, фотографічного) методами, описаними в попередньому розділі, у середньому становить декілька бітів на одне закодоване значення колірної матриці. Стосовно до синтезованих зображень (такі зображення можуть містити текст, малюнки, графічні об'єкти й т.п.) ефективність виявляється трохи вище й іноді становить менш одного біта на закодоване значення. Однак існують технології кодування, що дозволяють домогтися істотно більшого результату. Висока ефективність досягається за рахунок того, що при кодуванні стають припустимими деякі інформаційні перекручування. Щоб перекручування були як можна менш помітні, їхні характеристики вибираються з урахуванням особливостей психовизуального сприйняття зображення людиною.
Перекручування найчастіше виникають внаслідок квантування значень інформаційної вибірки. Ідея квантування полягає в заміні всіх значень із групи (інтервалу) деяким єдиним значенням. Даний прийом дозволяє зменшити кількість різних значень, що зустрічаються в матриці, що дозволяє кодувати її більш ефективно. Інформаційні перекручування, мабуть, виникають через розбіжність групуємих значень зі значенням, отриманим у процесі їхнього квантування. Повне відновлення інформації стає, таким чином, неможливим.
Розвитком зазначеного підходу є метод у якому групуються не окремі значення, а цілі вектора, складені зі значень, що перебувають на близьких позиціях у матриці. Квантоване значення в даному випадку відповідає деякій множині векторів значень. Таке рішення представляє значно більше можливостей для інформаційного опису. Воно зветься векторне квантування, а розглянутий раніше спрощений варіант називається скалярним, квантуванням.
Як неважко помітити, векторне квантування частково виконує функції контекстно-залежного моделювання: об'єднання векторів значень, що перебувають на близьких позиціях, дозволяє врахувати можливі імовірнісні взаємозв'язки між ними. Тому векторне квантування, як альтернативний метод обліку інформаційних закономірностей, є предметом для окремого розгляду, і буде залишений за рамками даної роботи. Надалі мова йтиме тільки про ті методи кодування, у яких використається скалярне квантування.
Зупинимося більш докладно на деяких деталях практичної реалізації скалярного квантування. Як ми вже відзначали вище, об'єднання значень у групи повинне вироблятися з урахуванням вимог конкретної задачі. У тих випадках, коли специфіка оброблюваної інформації не дозволяє однозначно вибрати спосіб групування значень, використається найбільш просте рішення - квантуємі значення розбиваються на рівні по довжині інтервали. Даний метод квантування називається рівномірним.
Позначимо через ? довжину інтервалу при рівномірному квантуванні {параметр квантування). Сукупність інтервалів представима у вигляді [x0+?-i, x0+?- (i + 1)). Значення x0 належить речовинному інтервалу [-?/2, ?/2) і задає базовий зсув інтервалів при квантуванні. i приймає довільні цілочисельні значення і являє собою номер інтервалу.
Номер інтервалу виступає в ролі кодуємого об'єкта. У процесі декодування по ньому відновлюється шуканий інтервал значень (деквантування). Тому що конкретні значення відновленню не підлягають, при деквантуванні вони заміняються деяким фіксованим числом. Оптимально використати як дане число математичне очікування значень інтервалу. У випадку, коли значення розподілені рівномірно, математичне очікування відповідає середині інтервалу - x0+?*i+?/2.
Квантуєма інформаційна вибірка часто представлена числами зі знаком, симетрично розподіленими щодо нуля. Маленькі по абсолютній величині значення звичайно не грають визначальної ролі - їхнє перекручування залишається практично непомітним для нашого сприйняття. У подібних ситуаціях базовий зсув інтервалу x0 має сенс вибирати рівним - ?/2. При такому виборі значення в околиці [-?/2, ?/2) будуть замінятися нулями (так називана мертва зона). З метою поліпшення схеми квантування розмір мертвої зони збільшують, залишаючи незмінними розміри інших інтервалів. Крім підвищення ефективності це дозволяє спростити процедуру квантування: якщо вибрати розмір мертвої зони рівним 2?, визначення номера інтервалу при квантуванні зведеться до ділення квантуємого значення на параметр квантування. Дане рішення використається в багатьох практичних додатках, зокрема, у стандартах кодування відеоінформації JPEG, JPEG2000, MPEG, Н.261, Н.263.
Інформаційні перекручування, що виникають у результаті скалярного квантування, звичайно помітно погіршують якість зображення, роблячи його східчастим. В ідеалі перекручування не повинні приводити до істотної зміни основного малюнка, зображення й не повинні вносити в зображення нові, що раніше не існували деталі. Із цієї причини доцільно квантувати не самі значення колірної матриці, а деякі їхні узагальнені характеристики, зміна яких не веде до кардинальної зміни рельєфу зображення. Як показує практика, найбільшою ефективністю володіють методи, у яких як об'єкт квантування виступають параметри двомірних інтерполяційних функцій, використовуваних для наближеного опису зображень.
Застосування інтерполяції саме по собі є ефективним методом одержання ощадливих подань інформації. Ефективність залежить від кількості вільних параметрів інтерполяційної функції й від того, наскільки точно ця функція наближає кодуємі дані. На практиці найбільше часто використається особливий різновид інтерполяційного методу - базисне розкладання.
2.2 Побудова інформаційного критерію
При обробці багатомірних даних у гнітючому числі випадків вирішується завдання їхнього агрегування. Як такі агрегати звичайно використаються середні величини й, зокрема, середні статечні. Серед останніх особливими властивостями володіють середнє арифметичне й середнє гармонійне. Їхнє відношення має властивості ентропії, значення якої можна інтерпретувати як міру невизначеності у виборі елементів масиву. Однак тут нас буде цікавити інший аспект зазначеного відношення, а саме - відношення як міра структурних розходжень значень компонент одномірного масиву. Оскільки розходження лежать в основі поняття інформації, те природної є спроба використання цієї міри для побудови інформаційного критерію. Для формального викладу зробимо необхідні позначення.
Нехай матриця з позитивними елементами
,
що має рядків і стовпців і нехай
.
Для кожної матриці можна визначити функцію
, (2.1)
де - транспонована матриця, елементи якої є зворотними значеннями елементів матриці .
При фіксованих значеннях елементів матриці функція (2.1) буде залежати від компонентів вектора . Бажаючи підкреслити цей факт, будемо для використати також позначення . Можна показати, що має основні властивості ентропії. Якщо рядка матриці різні за структурою значень своїх елементів, то максимальне значення (2.1) досягається на векторі , відмінному від рівномірного
.
Компоненти вектора мають цікаву властивість: дві максимальні за своїми значеннями компонента відповідають двом об'єктам (рядкам матриці ), які найбільшою мірою відрізняються друг від друга структурою значень своїх елементів (найбільш деструктивні). Це властивість вектора можна використати при розробці алгоритмів класифікації.
Можливість використання властивостей вектора для рішення завдання кластерізації даних квітів ірису на три класи - virginic, versicol й setosa з покажемо на прикладі. На рис.2.1 показаний графік значень компонент вектора для всієї вибірки. Як видно найбільші значення компонентів вектора відповідають двом елементам: [7,2 3,6 6,1 2,5] ; [4,3 3,0 1,1 0,1].
На першому кроці з використанням міри близькості
(2.2)
виявилося можливим розбити всю сукупність характеристик квітів ірису на два кластери по ступені їхньої близькості до виділених елементів по алгоритму. Отримані в результаті кластери, перший - квіти virginic й versicol, другий - квіти setosa. На другому кроці після проведення аналогічної процедури для даних першого кластера спостерігалися 9 помилок, які розподілилися між класами (квітами) як 5 до 4.
Рисунок 2.1 Графік зміни компонент вектора для всієї вибірки характеристик квітів ірису.
Загальні результати класифікації, представлені у вигляді матриці переплутування
.
Їх можна віднести до одним із кращих результатів кластерізації квітів ірису, що демонструє можливість використання інформаційних властивостей вектора для побудови алгоритмів класифікації багатомірних даних. Можна продовжити дослідження в цьому напрямку для різних вирішальних правил у процедурах класифікації, однак, залишаючи осторонь деталі, підкреслимо, що запропонований спосіб виявлення розходжень є основою для розробки ефективних алгоритмів розпізнавання.
Повернемося до основної мети нашого дослідження з формування інформаційного критерію. Розглянемо окремий випадок, коли матриця в (2.1) складається з одного вектора-стовпця . Для цього випадку представимо (2.1) у вигляді
. (2.3)
Легко перевірити, що
1. ;
2. (2.4)
3. .
На підставі цих властивостей будемо функцію (2.3) називати мірою розходжень компонент вектора або інформаційною мірою, оскільки, там, де є розходження, там є й інформація. Далі, визначимо
(2.5)
і шуканий інформаційний критерій
, (2.6)
де () і () - заелементні операції розподілу й множення відповідно.
Область визначається умовами розв'язуваного завдання. Приведемо приклади використання формули (2.6). Почнемо із простого випадку. Нехай перетворення полягає в заміні вихідного вектора вектором . Тоді область обмежень визначиться співвідношеннями , а величина - рівністю
, (2.7)
звідки треба, що максимально можлива кількість інформації втримується в тотожному перетворенні й дорівнює
, (2.8)
що й випливало очікувати.
Розглянемо більше складні й практично важливі приклади.
2.2.1 Оцінка інформативності ознак
У теорії розпізнавання образів оцінку інформативності ознаки одержують як відношення результатів розпізнавання об'єктів контрольної вибірки в повному просторі ознак до результатів розпізнавання, проведеного без обліку оцінюваної ознаки. Із цього визначення треба, що оцінка інформативності ознаки, мабуть, залежить від вирішального правила. Крім того, ця оцінка залежить від обсягу навчальної вибірки, де показано, що для одержання її достовірного значення, об'єктів у кожному класі повинне бути в десятки разів більше числа досліджуваних ознак.
Подобные документы
Основні поняття теорії інформації та їх роль у визначенні фундаментальних меж представлення інформації. Телевізійні стандарти стиснення. Кодер і декодер каналу. Стандарти стиснення двійкових та півтонових нерухомих зображень. Кодування бітових площин.
дипломная работа [8,1 M], добавлен 02.10.2014Основні теоретичні відомості алгоритмів стиснення зображень: класи зображень та їх представлення в пам'яті, алгоритми та принципи групового кодування. Огляд та аналіз сучасних програмних засобів конвертування. Тестування, опис роботи програмного засобу.
курсовая работа [2,9 M], добавлен 15.03.2014Імовірнисний підхід у теорії ощадливого кодування. Оцінка інформативності ознак та їх оптимальна градація. Застосування імовірнісних методів для підвищення ефективності ощадливого кодування відеоінформації. Ефективні алгоритми кодування інформації.
реферат [1,6 M], добавлен 29.06.2009Розробка та дослідження алгоритмів і програм кодування даних з виявленням помилок на основі циклічних CRC-кодів. Аналіз циклічних кодів. Розробка та тестування програмних модулів. Розрахунок економічних показників. Вирішення питань охорони праці.
дипломная работа [5,4 M], добавлен 22.06.2010Стиснення даних як процедура перекодування даних, яка проводиться з метою зменшення їх об'єму, розміру, обсягу. Знайомство с особливостями стиснення інформації способом кодування серій. Загальна характеристика формату ZIP, аналіз основних функцій.
презентация [1,8 M], добавлен 14.08.2013Значимість двійкової системи числення для кодування інформації. Способи кодування і декодування інформації в комп'ютері. Відповідність десятковій, двійковій, вісімковій і шістнадцятковій систем числення. Двійкове кодування інформації, алфавіт цифр.
презентация [1,4 M], добавлен 30.09.2013Історія створення мови С#. Аналіз алгоритмів кодування даних. Розробка системи в середовищі Visual Studio 2008 Express. Схема шифрування алгоритму DES. Дослідження алгоритму RC2. Приклади хешів RIPEMD-160. Програмна реалізація основних процедур системи.
дипломная работа [1,7 M], добавлен 25.10.2012Визначення кількості інформації в повідомленні, ентропії повідомлень в каналі зв’язку, ентропії двох джерел повідомлень. Продуктивність джерела повідомлень, швидкість передачі інформації та пропускна здатність каналу зв’язку. Кодування, стиснення даних.
контрольная работа [590,8 K], добавлен 07.06.2012Призначення та область застосування програм, які орієнтовані на перетворення зображень з плоского в об’ємне. Основні стадії формування тривимірного зображення. Класифікація моделей і методів візуалізації. Особливості створення карти глибин по пікселям.
курсовая работа [325,8 K], добавлен 04.06.2010Історія виникнення та сфери використання тримірної графіки. Дослідження процесу візуалізації тримірного зображення. Створення програмного забезпечення, здатного перетворювати стандартні графічні зображення до графічних зображень внутрішніх форматів Мауа.
дипломная работа [3,6 M], добавлен 23.09.2013
