Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Аналіз та реалізація стиснення даних за допомогою алгоритму Mjpeg
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2010
Тип роботи:
Завдання
Предмет:
Методи та засоби комп’ютерних інформаційних технологій
Група:
КН-34
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра САПР
ПОЯСНЮВАЛЬНА ЗАПИСКА
до курсової роботи з дисципліни: “Методи і засоби комп’ютерних інформаційних технологій ”
на тему: “Аналіз та реалізація стиснення даних за допомогою алгоритму Mjpeg”
Керівник: Дарнобит Юрій Романович
Завдання на курсову роботу
Проаналізувати методи стиснення даних. Розробити програмну реалізацію методу стиснення даних за допомогою алгоритму Mjpeg.
Анотація
Побережник В.В. “Аналіз та реалізація стиснення даних за допомогою алгоритму Mjpeg ”. Курсова робота – НУ “Львівська політехніка”, САПР, дисципліна: “Методи і засоби комп’ютерних інформаційних технологій”, 2010 р.
Дана курсова робота складається з 40 сторінок, містить 1 таблицю, 1 додаток. Для написання курсової роботи були використані матеріали з 5-х літературних джерел.
Метою даної роботи є створення програми стиснення даних з використанням алгоритму Mjpeg.
Зміст
Вступ......................................................................................................................…..5
1.Аналіз предметної області .........................................................………………...6
2. Кодування інформації................................................................………………...11
2.1. Способи кодування інформації.............................................…………………11
2.2. Кодування символьної (текстової) інформації......………………………….12
2.3. Кодування числової інформації....... .......... .....................................................12
2.4. Кодування графічної інформації...............................……...………………….13
2.5. Кодування звукової інформації..........................................................………...14
3. Алгоритм кодування Mjpeg.................................................................................15
3.1.Формат JPEG.......................................................……………………………….15
3.2.Режими стискання JPEG.....................................................................................15
3.3.Послідовний режим стиснення в JPEG……………………………………….15
3.4. Алгоритм Хафмана.............................................................................................16
4.Постановка задачі та опис алгоритму…….……………………………………17
4.1. Блок-схема алгоритму……………...………………………………………….19
4.2.Опис програмної реалізації…….……..…………………………......................20
4.3. Аналіз результатів…….…………………….…………………………………22
Висновки…………………………………………………........................................23
Список використаних джерел…………………………….……………………….24
Додаток……………………………………………………………………………...25
Вступ
ХХІ століття - вік інформатики й інформатизації. Технологія дає можливість передавати й зберігати все більші обсяги інформації. Це благо має й зворотній бік. Інформація стає усе більше вразливою по різних причинах:
зростаючі обсяги збережених і переданих даних;
розширення кола користувачів, що мають доступ до ресурсів ЕОМ, програмам і даним;
ускладнення режимів експлуатації обчислювальних систем.
Тому все більшу важливість здобуває проблема захисту інформації від несанкціонованого доступу (НСД) при передачі й зберіганні. Сутність цієї проблеми - постійна боротьба фахівців із захисту інформації зі своїми "опонентами".
Захист інформації - сукупність заходів, методів і засобів, що забезпечують:
виключення НСД до ресурсів ЕОМ, програмам і даним;
перевірку цілісності інформації;
виключення несанкціонованого використання програм (захист програм від копіювання).
Очевидна тенденція до переходу на цифрові методи передачі й зберігання інформації дозволяє застосовувати уніфіковані методи й алгоритми для захисту дискретної (текст, факс, телекс) і безперервної (мова) інформації.
Випробуваний метод захисту інформації від НСД – кодування (криптографія). Кодування (encryption) називають процес перетворення відкритих даних (plaintext) у зашифровані (шифртекст, ciphertext) або зашифрованих даних у відкриті за певними правилами із застосуванням ключів
1. Аналіз предметної області
Захист даних з допомогою кодування – одне з можливих рішень проблеми їхньої безпеки. Закодовані дані стають доступними тільки для того, хто знає, як їх рокодовувати, і тому викрадення закодованих даних є абсолютно безглуздим для несанкціонованих користувачів.
Коди і шифри використовувались задовго до появи ЕОМ. З теоретичного погляду не існує чіткої різниці між кодами і шифрами. Однак у сучасній практиці відмінність між ними, як правило, є достатньо чіткою. Коди оперують лінгвістичними елементами, поділяючи текст, що шифрується, на такі смислові елементи, як слова і склади. У шифрі завжди розрізняють два елементи: алгоритм і ключ.
Алгоритм дозволяє використати порівняно короткий ключ для шифрування наскільки завгодно великого тексту. Для захисту даних в ІС в основному використовуються шифри, тому далі мова піде саме про них. У цій главі будуть наведені основні корисні для практики концепції криптографічного захисту інформації, а також обговорені переваги і недоліки найбільш поширених засобів захисту.
Визначимо низку термінів, що використовуються у криптографії.
Гамування – процес накладення за певним законом гами шифру на відкриті дані.
Під гамою шифру розуміється псевдовипадкова двійкова послідовність, що виробляється за заданим алгоритмом, для зашифровування відкритих даних і розшифрування зашифрованих даних.
Зашифровуванням даних називається процес перетворення відкритих даних на зашифровані з допомогою шифру, а розшифруванням даних – процес перетворення закритих даних на відкриті з допомогою шифру.
Шифруванням називається процес зашифровування або розшифрування даних.
Дешифруванням будемо називати процес перетворення закритих даних на відкриті при невідомому ключі і, можливо, невідомому алгоритмі.
Імітозахист – захист від нав'язування неправдивих даних. Для забезпечення імітозахисту до зашифрованих даних додається імітовставка, що являє собою послідовність даних фіксованої довжини, отриману за певним правилом з відкритих даних і ключа.
Ключ – конкретний таємний стан деяких параметрів алгоритму криптографічного перетворення даних, що забезпечує вибір одного варіанту із сукупності всіляких для даного алгоритму.
Криптографічний захист – це захист даних з допомогою криптографічного перетворення, під яким розуміється перетворення даних шифруванням і (або) виробленням імітовставки.
Синхропосилка – вхідні відкриті параметри алгоритму криптографічного перетворення.
Рівняння зашифровування – співвідношення, що описує процес утворення зашифрованих даних з відкритих даних у результаті перетворень, заданих алгоритмом криптографічного перетворення.
Під шифром розуміється сукупність зворотних перетворень безлічі відкритих даних на безліч зашифрованих даних, заданих алгоритмом криптографічного перетворення.
Криптостійкістю називається характеристика шифру, визначальна його стійкість до дешифрування. Звичайно ця характеристика визначається періодом часу, необхідним для дешифрування.
Одним з найбільш розповсюджених криптографічних стандартів на шифрування даних, що застосовуються в США, є DES (Data Encryption Standard). Первісно засіб, що лежить в основі даного стандарту, був розроблений фірмою IBM для своїх цілей. Він був перевірений Агенцією Національної Безпеки США, що не виявило в ньому статистичних або математичних вад. Це означало, що дешифрування даних, захищених з допомогою DES, не могло бути виконане статистичними (наприклад, з допомогою частотного словника) або математичними ("прокручуванням" в зворотному напрямку) засобами.
Після цього засіб фірми IBM був прийнятий як федеральний стандарт. Стандарт DES використовується федеральними департаментами і агенціями для захисту всіх достатньо важливих даних у комп'ютерах (виключаючи деякі дані, засоби захисту яких визначаються спеціальними актами). Його застосовують багато недержавних інститутів, у тому числі більшість банків і служб оберту грошей. Обумовлений у стандарті алгоритм криптографічного захисту даних опублікований для того, щоб більшість користувачів могли використати перевірений і апробований алгоритм з гарною криптостійкістю. Помітимо, що, з одного боку, публікація алгоритму небажана, оскільки може призвести до спроб дешифрування закритої інформації. Але, з іншого боку, це не настільки істотно (якщо стандарт сильний) у порівнянні зі слабкими засобами захисту даних, що використовуються державними інститутами. Інакше кажучи, втрати від публікації алгоритму криптографічного захисту набагато менші, ніж втрати від застосування засобів захисту з низькою криптостійкістю. Зрозуміло, стандартний алгоритм шифрування даних має володіти такими характеристиками, щоб його опублікування не відбилося на криптостійкості.
Засіб шифрування з використанням датчика ПВЧ найбільш часто використовується у програмній реалізації системи криптографічного захисту даних. Це пояснюється тим, що з одного боку, він достатньо простий для програмування, а з іншого боку, дозволяє створювати алгоритми з дуже високою криптостійкістю. Крім того, ефективність даного засобу шифрування є достатньо високою. Системи, основані на засобі шифрування з використанням датчика ПВЧ, дозволяють зашифрувати в секунду від декількох десятків до сотень кілобайт даних (тут і надалі всі характеристики наведені для персональних комп'ютерів).
Однак простота засобу може зіграти злий жарт з розробником власного алгоритму шифрування даних. Як вже було показане вище (проблема відомого тексту) шифр, який має дуже грізний вигляд, може бути чутливим до простих впливів. Тому кожний новий алгоритм шифрування даних перед його застосуванням має підлягати всебічному математичному, статистичному і криптографічному аналізам. Тільки після усунення всіх слабких сторін алгоритму він може використовуватися для шифрування даних. У противному випадку результати можуть бути катастрофічними.
Основною перевагою засобу DES є те, що він є стандартним. Як стверджує Національне Бюро Стандартів США, алгоритм має наступні властивості:
високий рівень захисту даних проти дешифрування і можливої модифікації даних;
простота і розуміння;
високий ступінь складності, що робить його розкриття дорожче одержуваного при цьому прибутку;
засіб захисту грунтується на ключі і не залежить ні від якої "таємності" алгоритму;
економічний у реалізації та ефективний у швидкодії.
Важливою характеристикою цього алгоритму є його гнучкість при реалізації і використанні в різноманітних додатках обробки даних. Кожний блок даних шифрується незалежно від інших, що дозволяє розшифрувати окремий блок у зашифрованому повідомленні та структурі даних. Тому можна здійснювати незалежну передачу блоків даних і довільний доступ до зашифрованих даних. Ні тимчасова, ні позиційна синхронізація для операцій шифрування не потрібні.
Алгоритм виробляє зашифровані дані, в яких кожний біт є функцією від усіх бітів відкритих даних і всіх бітів ключа. Відмінність лише в одному біті даних дасть у результаті рівні ймовірності зміни для кожного біта зашифрованих даних.
Звичайно, ці властивості DES вигідно відрізняють його від засобу шифрування з використанням датчика ПВЧ, оскільки більшість алгоритмів шифрування, побудованих на основі датчиків ПВЧ, не характеризуються всіма перевагами DES. Однак і DES має низку недоліків.
Найістотнішим недоліком DES фахівці визнають розмір ключа, що вважається занадто малим. Стандарт у нинішньому вигляді не є невразливим, хоча і є дуже тяжким для розкриття (досі не були зареєстровані випадки дешифрування інформації, зашифрованою з використанням засобу DES). Для дешифрування інформації засобом підбору ключів достатньо виконати 256 операцій розшифрування (тобто всього близько 7*1016 операцій). Хоча в наш час немає апаратури, що могла б виконати в період часу, що оглядається, подібні обчислення, ніхто не гарантує, що вона не з'явиться в майбутньому. Деякі фахівці пропонують модифікацію для усунення цього недоліку: вхідний текст Р зашифровується спочатку за ключем К1, після цього за ключем К2 і, нарешті, за ключем К3. В результаті час, що вимагається для дешифрування, зростає до 2168 операцій (приблизно, до 1034 операцій).
Ще один недолік засобу DES полягає в тому, що окремі блоки, що містять однакові дані (наприклад, пропуски), матимуть однаковий вигляд у зашифрованому тексті, що з погляду криптоаналізу є невірним.
Засіб DES може бути реалізований і програмно. Залежно від швидкодії та типу процесора персонального комп'ютера програмна система, що шифрує дані з використанням засобу DES, може обробляти від декількох кілобайт до десятків кілобайт даних у секунду. У той же час необхідно відзначити, що базовий алгоритм все ж розрахований на реалізацію в електронних приладах спеціального призначення.
Алгоритм криптографічного перетворення, що був союзним стандартом і визначається ДГСТ 28147-89, вільний від недоліків стандарту DES і в той же час володіє всіма його перевагами. Крім того, у стандарт вже закладений засіб, з допомогою якого можна зафіксувати невиявлену випадкову або навмисну модифікацію зашифрованої інформації.
Однак у алгоритму є дуже істотний недолік, який полягає в тому, що його програмна реалізація дуже складна і практично позбавлена всякого сенсу із-за вкрай низької швидкодії. За оцінками авторів, за одну секунду на персональному комп'ютері можуть бути оброблені всього лише декілька десятків (максимально сотень) байт даних, а подібна продуктивність навряд чи задовольнить кого-небудь з користувачів. Хоча зараз вже розроблені апаратні засоби, що реалізують даний алгоритм криптографічного перетворення даних, які демонструють прийнятну продуктивність (біля 70 Кб/с для IBM ПC AT з тактовою частотою 12 Мгц), все ж складається враження, що розробники алгоритму цілком не піклувались про ефективність його програмної реалізації та про вартість шифрування даних.
Тепер зупинимося на засобі RSA. Він є дуже перспективним, оскільки для зашифровування інформації не вимагається передачі ключа іншим користувачам. Це вигідно відрізняє його від всіх описаних вище засобів криптографічного захисту даних. Але в наш час до цього засобу відносяться з підозрою, оскільки в ході подальшого розвитку може бути знайдений ефективний алгоритм визначення дільників цілих чисел, в результаті чого засіб шифрування стане абсолютно незахищеним. Крім того, не має чіткого доказу, що не існує іншого засобу визначення таємного ключа за відомим, окрім як визначення дільників цілих чисел.
Урешті-решт, засіб RSA має лише переваги. До числа цих переваг слід віднести дуже високу криптостійкість, досить просту програмну і апаратну реалізації. Щоправда, слід помітити, що використання цього засобу для криптографічного захисту даних нерозривно пов'язане з дуже високим рівнем розвитку техніки.
2. Кодування інформації
Код — це набір умовних позначень (або сигналів) для запису (або передачі) деяких заздалегідь певних понять.
Кодування інформації – це процес формування певного представлення інформації. У вужчому сенсі під терміном «кодування» часто розуміють перехід від однієї форми представлення інформації до іншої, зручнішою для зберігання, передачі або обробки. Зазвичай кожен образ при кодуванні уявленні окремим знаком.
Знак - це елемент кінцевої безлічі відмінних один від одного елементів.
У вужчому сенсі під терміном "кодування" часто розуміють перехід від однієї форми представлення інформації до іншої, зручнішою для зберігання, передачі або обробки.
Комп'ютер може обробляти тільки інформацію, представлену в числовій формі. Вся інша інформація (наприклад, звуки, зображення, свідчення приладів і т. д.) для обробки на комп'ютері повинна бути перетворена в числову форму. Наприклад, щоб перевести в числову форму музичний звук, можна через невеликі проміжки часу вимірювати інтенсивність звуку на певних частотах, представляючи результати кожного вимірювання в числовій формі. За допомогою програм для комп'ютера можна виконати перетворення отриманої інформації, наприклад "накласти" один на одного звуки від різних джерел.
Аналогічним чином на комп'ютері можна обробляти текстову інформацію. При введенні в комп'ютер кожна буква кодується певним числом, а при виводі на зовнішні пристрої (екран або друк) для сприйняття людиною по цих числах будуються зображення букв. Відповідність між набором букв і числами називається кодуванням символів.
Як правило, всі числа в комп'ютері представляються за допомогою нулів і одиниць (а не десяти цифр, як це звично для людей). Іншими словами, комп'ютери зазвичай працюють в двійковій системі числення, оскільки при цьому пристрої для їх обробки виходять значно простішими. Введення чисел в комп'ютер і вивід їх для читання людиною може здійснюватися в звичній десятковій формі, а всі необхідні перетворення виконують програми, що працюють на комп'ютері.
2.1. Способи кодування інформації
Одна і та ж інформація може бути представлена (закодована) в декількох формах. C появою комп'ютерів виникла необхідність кодування всіх видів інформації, з якими має справу і окрема людина, і людство в цілому. Але вирішувати задачу кодування інформації людство почало задовго до появи комп'ютерів. Грандіозні досягнення людства - писемність і арифметика - є не що інше, як система кодування мови і числової інформації. Інформація ніколи не з'являється в чистому вигляді, вона завжди якось представлена, якось закодована.
Двійкове кодування – один з поширених способів представлення інформації. У обчислювальних машинах, в роботах і верстатах з числовим програмним управлінням, як правило, вся інформація, з якою має справу пристрій, кодується у вигляді слів двійкового алфавіту.
2.2. Кодування символьної (текстовою) інформації
Основна операція, вироблювана над окремими символами тексту, - порівняння символів.
При порівнянні символів найбільш важливими аспектами є унікальність коди для кожного символу і довжина цієї коди, а сам вибір принципу кодування практично не має значення.
Для кодування текстів використовуються різні таблиці тієї, що перекодувала. Важливо, щоб при кодуванні і декодуванні одного і того ж тексту використовувалася одна і та ж таблиця.
Таблиця тієї, що перекодувала - таблиця, що містить впорядкований деяким чином перелік кодованих символів, відповідно до якої відбувається перетворення символу в його двійковий код і назад.
Найбільш популярні таблиці тієї, що перекодувала: ДКОЇ-8, ASCII, Cp1251, Unicode.
Історично склалося, що як довжина коди для кодування символів було вибрано 8 битий або 1 байт. Тому частіше всього одному символу тексту, що зберігається в комп'ютері, відповідає один байт пам'яті.
Різних комбінацій з 0 і 1 при довжині коди 8 біт може бути 28 = 256, тому за допомогою однієї таблиці тієї, що перекодувала можна закодувати не більше 256 символів. При довжині коди в 2 байти (16 бітів) можна закодувати 65536 символів.
2.3. Кодування числової інформації
Схожість в кодуванні числової і текстової інформації полягає в наступній: щоб можна було порівнювати дані цього типу, у різних чисел (як і у різних символів) повинен бути різний код. Основна відмінність числових даних від символьних полягає в тому, що над числами окрім операції порівняння проводяться різноманітні математичні операції: складання, множення, витягання кореня, обчислення логарифма і ін. Правила виконання цих операцій в математиці детально розроблені для чисел, представлених в позиційній системі числення.
Основною системою числення для уявлення чисел в комп'ютері є двійкова позиційна система числення.
Кодування текстової інформації
В даний час, велика частина користувачів, за допомогою комп'ютера обробляє текстову інформацію, яка складається з символів: букв, цифр, розділового і ін. знаків Підрахуємо, скільки всього символів і яка кількість бітів нам потрібно.
10 цифр, 12 розділових знаків, 15 знаків арифметичних дій, букви російського і латинського алфавіту, ВСЬОГО: 155 символів, що відповідає 8 біт інформації.
Одиниці вимірювання інформації.
1 байт = 8 бітів
1 Кбайт = 1024 байтам
1 Мбайт = 1024 Кбайтам
1 Гбайт = 1024 Мбайтам
1 Тбайт = 1024 Гбайтам
Суть кодування полягає в тому, що кожному символу ставлять у відповідність двійковий код від 00000000 до 11111111 або відповідний йому десятковий код від 0 до 255.
Необхідно пам'ятати, що в даний час для кодування російських букв використовують п'ять різних кодових таблиць (ЯКІ - 8, Ср1251, Ср866, Мас, ISO), причому тексти, закодовані за допомогою однієї таблиці правильно не відображатимуться в іншій
Основним відображенням кодування символів є код ASCII - American Standard Code for Information Interchange- американський стандартний код обміну інформацією, який вдає із себе таблицю 16 на 16, де символи закодовані в шістнадцядковій системі числення.
2.4. Кодування графічної інформації
Важливим етапом кодування графічного зображення є розбиття його на дискретні елементи (дискретизація).
Основними способами представлення графіки для її зберігання і обробки за допомогою комп'ютера є растрові і векторні зображення
Векторним зображенням є графічний об'єкт, що складається з елементарних геометричних фігур (найчастіше відрізань і дуг). Положення цих елементарних відрізань визначається координатами крапок і величиною радіусу. Для кожної лінії указується двійкові коди типу лінії (суцільна, пунктирна, штрихпунктирна), товщини і кольору.
Растровим зображенням є сукупність крапок (пікселів), отриманих в результаті дискретизації зображення відповідно до матричного принципу.
Матричний принцип кодування графічних зображень полягає в тому, що зображення розбивається на задану кількість рядків і стовпців. Потім кожен елемент отриманої сітки кодується за вибраним правилом.
Pixel (picture element - елемент рисунка) - мінімальна одиниця зображення, колір і яскравість якої можна задати незалежно від решти зображення.
Відповідно до матричного принципу будуються зображення, що виводяться на принтер, відображаються на екрані дисплея, отримувані за допомогою сканера.
Якість зображення буде тим вище, чим "щільніше" розташовані пікселі, тобто ніж більше роздільна здатність пристрою, і чим точніше закодований колір кожного з них.
Для чорно-білого зображення код кольору кожного пікселя задається одним бітом.
Якщо малюнок кольоровий, то для кожної крапки задається двійковий код її кольору.
Оскільки і кольори кодуються в двійковому коді, то якщо, наприклад, ви хочете використовувати 16-кольоровий малюнок, то для кодування кожного пікселя вам буде потрібно 4 бита (16=24), а якщо є можливість використовувати 16 битий (2 байти) для кодування кольору одного пікселя, то ви можете передати тоді 216 = 65536 різних квітів. Використання трьох байтів (24 бітів) для кодування кольору однієї крапки дозволяє відобразити 16777216 (або близько 17 мільйонів) різних відтінків кольору - так званий режим “дійсного кольору” (True Color). Відмітимо, що це використовувані в даний час, але далеко не граничні можливості сучасних комп'ютерів.
2.5. Кодування звукової інформації
З курсу фізики вам відомо, що звук - це коливання повітря. За своєю природою звук є безперервним сигналом. Якщо перетворити звук в електричний сигнал (наприклад, за допомогою мікрофону), ми побачимо напругу, що плавно змінюється з часом.
Для комп'ютерної обробки аналоговий сигнал потрібно якимсь чином перетворити в послідовність двійкових чисел, а для цього його необхідно дискретизувати і оцифрувати.
Можна поступити таким чином: вимірювати амплітуду сигналу через рівні проміжки часу і записувати набутих числових значень в пам'ять комп'ютера.
3. Алгоритм кодування Mjpeg
MJPEG (Motion JPEG) покадровий метод відеостиснення, основною особливістю якого являється стиснення кожного кадру відеопотоку за допомогою алгоритма стиснення зображень JPEG.
3.1.Формат JPEG
JPEG - Найпоширеніший формат, використовуваний для зберігання фотографічних зображень. Але, не дивлячись на його широке розповсюдження, внутрішні механізми стискування JPEG залишаються чимось схожий на чорну магію. JPEG є абревіатурою від «Joint Photographie Experts Group» (Об'єднаний комітет експертів з машинної обробки фотозображень). Ця організація під керівництвом міжнародних комітетів із стандартизації створила стандарт стискування зображень. Стандарт JPEG вельми складний, оскільки він описує не стільки формат файлів зображень, а визначає безліч пов'язаних з ним технологій стискування зображень. Потужність формату JPEG полягає в тому, що для фотографічних зображень він забезпечує максимальне стискування в порівнянні з будь-якими іншими загальноприйнятими форматами растрових зображень. Фотографію, для зберігання якої у вигляді файлу Windows BMP потрібно 1 Мбайт, у форматі JPEG зазвичай можна стискувати до 50 Кбайт. Хоча формат JPEG вимагає значних обчислень, його видатні можливості по стискуванню зображень зазвичай переважують недолік, зв'язаний з великими витратами часу на обробку даних.
3.2.Режими стискування JPEG
Первинний стандарт JPEG визначав чотири режими стискування: ієрархічний, прогресивний, послідовний і без втрат. Крім того, для цих режимів стандарт визначав декілька процесів кодування. Хоча між методами стискування є деяка спільність, здебільшого їх слід реалізовувати як абсолютно різні технології.
3.3Послідовний режим
Послідовний режим є простим режимом JPEG. Як ясно з його назви, послідовний режим стискування забезпечує кодування зображення зверху вниз. Послідовний режим підтримує дискретизацію даних з точністю 8 і 12 бітів. У послідовному JPEG кожен колірний компонент повністю кодується в один скан - блок стислих даних, який містить результати одного проходу по зображенню для одного або декількох компонентів. У більшості форматів всі стислі дані пікселів зберігаються в одній безперервній області файлу. У форматі JPEG кожен прохід по зображенню зберігається в окремому блоці даних, званому сканом. В рамках методу послідовного стискування стандарт JPEG визначає два альтернативні процеси кодування. Один використовує кодування Хаффмана, а в іншому застосовується арифметичне кодування.
3.4.Алгоритм Хафмана
В основі алгоритму Хафмана лежить ідея кодування бітовими групами. Спочатку проводиться частотний аналіз вхідної послідовності даних, тобто встановлюється частота входження кожного символу, що зустрічається у ній. Після цього символи сортуються по спаданню частоти входження.
Основна ідея полягає в наступному: чим частіше зустрічається символ, тим меншою кількістю біт він кодується. Результат кодування зводиться в словник, що необхідний для декодування.
Розглянемо простий приклад, що ілюструє роботу алгоритму Хафмана. Нехай задано текст, в якому літера 'А' входить 10 разів, літера 'B' - 8 раз, 'C'- 6 разів , 'D' - 5 разів, 'E' і 'F' - по 4 рази. Тоді один з можливих варіантів кодування за алгоритмом Хафмана наведений у таблиці 1.
Таблиця 1.
Символ
Частота входження
Бітовий код
A
10
00
B
8
01
C
6
100
D
5
101
E
4
110
F
4
111
4. Постановка задачі та опис алгоритму
Дана курсова робота передбачає розробити програмний продукт що повинен розв’язувати важливі питання в галузі стиснення даних: стиснення графічної інформації, текстової, відеоінформації, та будь-якої іншої інформації що представлена в електронній формі. Даний алгоритм, а саме алгоритм Mjpeg, вибраний для програмної реалізації як один з найефективніших для вирішення проблем криптографії. Стиснення інформації полягає в тому щоб перетворити її в інший вид який би займав менше електронного місця, оскільки Mjpeg являє собою по кадрове стиснення відеоінформації методом jpeg, а один із можливих алгоритмів jpeg – є алгоритм Хаффмана. Перевагами методу Хаффмана є його досить висока швидкість і так само висока якість стискання. Цей алгоритм порівняно давно відомий і є на сьогодні дуже розповсюдженим: прикладами є програма compact OC UNIX (програмна реалізація), а також стандарт кодування факсів (апаратна реалізація).
Кодування Хаффмана має мінімальну надлишковість за умови, що кожний символ кодується окремим ланцюжком в алфавіті. Таким чином не важко оцінити можливості даного методу та порівняти його з іншими алгоритмами. Наприклад: найбільш відомий – це кодування довжин серій (run length encoding, RLE). Зміст методу – заміна ланцюжків символів, що повторюються, на один цей символ та лічильник повторювання. Проблема полягає в тому, щоб декодер міг відрізнити у вихідному потоці таку кодовану серію від інших символів. Розв’язок цієї проблеми очевидний – додавати до таких ланцюжків деякі заголовки (наприклад, використовувати перший біт як ознаку кодованої серії). Метод є досить ефективним для графічних зображень у форматі “байт на піксел” (наприклад, формат PCX використовує кодування RLE).
Недоліки методу RLE є очевидними: це, передусім, низька пристосованість до багатьох розповсюджених типів файлів, наприклад, текстових: у загальному випадку реально стиснути можна лише ланцюжки проміжків на початку абзаців. Саме тому цей метод можна ефективно використовувати лише у комбінації з вторинним кодуванням.
Цей підхід реалізовано в алгоритмі кодування факсів: спочатку зображення розбивається на чорні та білі крапки, що перетворюються алгоритмом RLE на потік довжин серій, а потім ці довжини серій кодуються за методом Хаффмана зі спеціально підібраним деревом.
Найбільш цікавими є однопрохідні алгоритми, що стискають не просто файл прямого доступу, а потік – файл, що не дозволяє позиціонування та скролінгу (подібно до програмного каналу (pipe) в UNIX). Такі алгоритми мають більш широку сферу застосувань, зокрема вони зручніші для апаратної реалізації в складі інтелектуальних контролерів пристроїв. Наприклад, протокол v42bis, що застосовується в модемах – це реалізація модифікації алгоритму LZW. Алгоритм програмної реалізації можна побачити на Рис. 1.
Рис. 1. Алгоритм програмної реалізації
4.1.Блок-схема алгоритму
4.2. Опис програмної реалізації
Розглянемо ці п’ять частин програми детальніше:
1. Задання вхідного файлу. Початок відліку таймера.
На цьому етапі користувач безпосередньо взаємодіє із інтерфейсом програми, тобто він має змогу ввести ім’я вхідного файлу, а також опцію, для кодування/декодування файлу:
-e – якщо файл потрібно кодувати. Якщо файл потрібно кодувати, то додаткових опцій не потребується.
Для ведення статистики, запускаємо таймер, який буде працювати весь час роботи програми.
Відкриття файлу, зчитування вмістимого у буфер
спроба відкрити вказаний файл;
якщо спроба вдала, то виділяється пам’ять під буфер та записується у нього вмістиме файлу.
Кодування/декодування тексту
якщо вказана опція декодування файлу, то викликається функція EncodeText
здійснюється перевірка чи файл дійсно кодований lzhaf.exe
отримуємо попередню назву файлу
отримуємо довжину словника
зчитуємо словник
розкодовуємо текст
якщо файл треба розкодувати, то викликається функція CodeText
формуємо список символів із частотами
викликаємо функцію GetHC, яка закодовує кожен символ відповідним кодом Хаффмана
записуємо заголовок lzh-файлу, попереднє ім’я файлу, довжину словнику, та власне сам словнику вихідний буфер
скануємо текст, та записуємо коди символів у вихідний буфер
Запис кодованого/декодованого тексту у вихідний файл
- вихідний буфер даних записуємо у вихідний файл. Якщо відбувалось кодування, то до назви файла додаємо розширення lzh.
5. Кінець відліку таймеру
- виключаємо таймер, виводимо відповідні показники таймеру на екран
Важливо відмітити також деякі параметри та деталі даної програми, та самої мови програмування. Дана програма являє собою файл з розширенням exe, розмір якого складає 69400 байт. Важливим буде відзначити бібліотеки що підключаються в даній програмі: stdio – стандартна бібліотека вводу виводу, stdlib – бібліотека що містить в собі функції виділення пам’яті і контролю процеса виконання програми, string – бібліотека що містить функції роботи з рядками та функції роботи з пам’ятю, ctape – бібліотека що містить функції для класифікації символів.
Вданому випадку неможливо оминути таке питання, а на які мові програмування реалізація алгоритму буде найефективнішою? На мою думку найефективнішою буде мова програмування високого рівння – Сі++. Мова Сі++ є універсальною мовою програмування, на додаток до якої розроблений набір різноманітних бібліотек. Тому, чесно говорячи, він дозволяє вирішити практично будь-яку задачу програмування. Проте, у силу різних причин (не завжди технічних) для якихось типів задач він вживається частіше, а для якихось – рідше. Сі++ як спадкоємець мови Сі широко використовується в системному програмуванні. На ньому можна писати високоефективні програми, у тому числі операційні системи, драйвери і т.п. Мова Сі++ – одна з основних мов розробки трансляторів. Оскільки системне програмне забезпечення часте буває написано мовою Сі чи Сі++, той і програмний інтерфейси до підсистем ОС теж часто пишуть на Сі++. Відповідно, ті програми, навіть і прикладні, котрі взаємодіють з операційними системами, написані мовою Сі++. Розподілені системи, що функціонують на різних комп’ютерах, також розробляються мовою Сі++. Цьому сприяє те, що в широко розповсюджених компонентих моделей CORBA і COM є зручні інтерфейси мовою Сі++. Обробка складних структур даних – тексту, бізнес-інформації, Internet-сторінок і т.п. – одна з найбільш розповсюджених можливостей застосування мови. У цілому треба сказати, що мова Сі++ у даний час є однією з найбільш розповсюджених мов програмування у світі.
4.3 Аналіз результатів
1.Стиснення текстової інформації
1.exe e 1.txt 2.txt
Вхідний файл 1.txt
Вихідний файл 2.txt
Розмір вхідного файлу 10677 байт
Розмір вихідного файлу 4742 байт
Коефіцієнт стиснення 10677/47420=2.25
Вміст частини текстового файлу: 1. Аналіз предметної області
Захист даних з допомогою кодування – одне з можливих рішень проблеми їхньої безпеки. Закодовані дані стають доступними
Вміст частини закодованого файлу: µ) ЮЏ-ЋзоxooЋ.OШ/Ivm›oр mпі9e:ђ.4\Ц§UWміfЮOё…ѕ*ФоУRҐ·AMЬдM™·бЯѓ‘Хд¬ЂћньЄL8fд|ЁсWfжх‰K&›·z]LEW4АхЏ
2.Стиснення графічної інформації
1.exe e bmp.bmp bmp1.bmp
Вхідний файл bmp.bmp
Вихідний файл bmp1.bmp
Розмір вхідного файлу 787510 байт
Розмір вихідного файлу 35151 байт
Коефіцієнт стиснення 787510/35151=22.4
3.Стиснення аудіо інформації
1.exe e 12.mp3 123.mp3
Вхідний файл 12.mp3
Вихідний файл 123.mp3
Розмір вхідного файлу 3564015 байт
Розмір вихідного файлу 3497046 байт
Коефіцієнт стиснення 3564015/3497046=1.019
4.Стискання відео інформації
1.exe e video.avi video1.avi
Вхідний файл video.avi
Вихідний файл video1.avi
Розмір вхідного файлу 7429632 байт
Розмір вихідного файлу 5932704 байт
Коефіцієнт стиснення 7429632/5932704=1.25
Як видно з вище наведених результатів роботи програми найбільш ефективним виявилось стиснення графічної інформації а найменш ефективним стиснення аудіо інформації. Це свідчить про те що алгоритм Хаффмана дійсно являється ефективним алгоритмом.
Висновки
В процесі виконання даної курсової роботи було розроблено програму для стиснення інформації . Використовуючи метод кодування MJPEG.
В процесі стиснення бітові ланцюжки фіксованої довжини замінюються на бітові ланцюжки різної довжини, причому основою для визначення нової довжини бітового ланцюжка для кожного числа є частота, з якою це число зустрічається в даному блоці інформації. Найбільш числам, що часто зустрічаються, повинні відповідати коротші ланцюжки. Звідси зрозуміло, що ступінь стиснення залежить не від розміру початкового файлу, а від його структури і типу файлу. Тобто якщо узяти два файли однакового розміру, але один з них складатиметься з яких-небудь символів, що повторюються з різною частотою, а інший - міститиме теж кількість символів, але таких, що частоти входження їх у файл співпадатимуть .то в цьому випадку перший файл стискатиметься більшою мірою, чим другий. Причини цього в тому, що довжина бітового ланцюжка в другому випадку для всіх кодованих символів буде однакова і складає 8 бітний, як і в початковому файлі, тобто стиснення не відбувається.
Файли однакового розміру будуть стислі однаковою мірою тільки в тому випадку, якщо в них обох буде присутня рівна кількість символів.
При тестуванні програми було виявлено, що програма є ефективною і для стиснення текстових файлів.
До переваг програмного продукту можна віднести:
відображення процесу архівування та розархівування;
До недоліків програми належать:
низький рівень стиснення файлів, що містять gif-картинки
відносно низька швидкість архівування великих файлів.
Список використаних джерел
1.http://home.onego.ru/~chiezo/gif.htm.
2.http://www.compression.ru.
3.www.algo.4u.ru.
4.Теория кодирования / под ред. Э.Л.Блоха – М.1964.
5.Миано Дж. Форматы и алгоритмы сжатия изображений в действии. – М.: Издательство Триумф, 2003.
Додаток
Текст програми на мові С++
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
FILE *infile, *outfile;
unsigned long int textsize = 0, codesize = 0, printcount = 0;
char wterr[] = "Can't write.";
void Error(char *message)
{
printf("\n%s\n", message);
exit(EXIT_FAILURE);
}
/********** LZW компресія **********/
#define N 4096 /* буферний розмір */
#define F 60 /* lookahead буферний розмір */
#define THRESHOLD 2
#define NIL N /* лист дерева */
unsigned char
text_buf[N + F - 1];
int match_position, match_length,
lson[N + 1], rson[N + 257], dad[N + 1];
void InitTree(void) /* initialize trees */
{
int i;
for (i = N + 1; i <= N + 256; i++)
rson[i] = NIL; /* корінь */
for (i = 0; i < N; i++)
dad[i] = NIL; /* вузол */
}
void InsertNode(int r) /* вставка в дерево */
{
int i, p, cmp;
unsigned char *key;
unsigned c;
cmp = 1;
key = &text_buf[r];
p = N + 1 + key[0];
rson[r] = lson[r] = NIL;
match_length = 0;
for ( ; ; ) {
if (cmp >= 0) {
if (rson[p] != NIL)
p = rson[p];
else {
rson[p] = r;
dad[r] = p;
return;
}
} else {
if (lson[p] != NIL)
p = lson[p];
else {
lson[p] = r;
dad[r] = p;
return;
}
}
for (i = 1; i < F; i++)
if ((cmp = key[i] - text_buf[p + i]) != 0)
break;
if (i > THRESHOLD) {
if (i > match_length) {
match_position = ((r - p) & (N - 1)) - 1;
if ((match_length = i) >= F)
break;
}
if (i == match_length) {
if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
match_position = c;
}
}
}
}
dad[r] = dad[p];
lson[r] = lson[p];
rson[r] = rson[p];
dad[lson[p]] = r;
dad[rson[p]] = r;
if (rson[dad[p]] == p)
rson[dad[p]] = r;
else
lson[dad[p]] = r;
dad[p] = NIL; /* крок p */
}
void DeleteNode(int p)
{
int q;
if (dad[p] == NIL)
return; /* реєстрований */
if (rson[p] == NIL)
q = lson[p];
else
if (lson[p] == NIL)
q = rson[p];
else {
q = lson[p];
if (rson[q] != NIL) {
do {
q = rson[q];
} while (rson[q] != NIL);
rson[dad[q]] = lson[q];
dad[lson[q]] = dad[q];
lson[q] = lson[p];
dad[lson[p]] = q;
}
rson[q] = rson[p];
dad[rson[p]] = q;
}
dad[q] = dad[p];
if (rson[dad[p]] == p)
rson[dad[p]] = q;
else
lson[dad[p]] = q;
dad[p] = NIL;
}
/* Huffman coding */
#define N_CHAR (256 - THRESHOLD + F)
/* види символів (character code = 0..N_CHAR-1) */
#define T (N_CHAR * 2 - 1) /* розмір столу */
#define R (T - 1) /* місцеположення кореня */
#define MAX_FREQ 0x8000 /* обновляє дерево, коли */
/* коренева частота доходить до цього значення. */
typedef unsigned char uchar;
/* стіл для кодування і декодування верхніх 6 бітів місцеположення */
/* для кодування */
uchar p_len[64] = {
0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
};
uchar p_code[64] = {
0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
0xF8, 0xF9, 0xFA, 0xFB, 0xF...
25.03.2012 13:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора