Московський державний університет імені Ломоносова
Механіко-математичний факультет
Курсова робота
на тему В«Алгоритми стиснення данихВ»
Студент 3го курсу І. Межиров
Науковий керівник А. Шень
Москва 2004
Зміст
Введення .................................................. ........................................... 1
Основний алгоритм порівняння пари букв ............................................. 3
Швидкий відмова для пари різних букв ............................................. ...... 5
Отримання монохромних зображень ............................................ 7
9
Введення
У цієї роботі описується спосіб поліпшення стиснення файлів формату DjVu.
Файл формату DjVu зберігає в стислому вигляді одно або кілька растрових зображень, при цьому, чим більше ці зображення схожі на друкований текст, тим краще стиснення. На відміну від стиснення алгоритмом JPEG, при стисненні в DjVu краю букв не розмиваються. p> Цей формат був придуманий і розвивався у фірмі AT & T між 1995 і 1999 роками. У 2000 всі права були продані фірмі LizardTech. У тому ж році LizardTech опублікувала частину коду під ліцензією GPL. На основі цього коду група розробників, яка працювала над цим проектом в AT & T, створила свій незалежний варіант (теж під ліцензією GPL), який називається DjVuLibre [1]. У безкоштовно доступних програмах є можливості розархівування і перегляду DjVu-файлів, але тільки демонстраційне стиск. На жаль, ці програми не працюють під Windows (хіба що через cygwin - перенесення середовища Unix в Windows). Програми з повними можливостями продаються фірмою LizardTech; з її сайту [4] можна також безкоштовно скачати програму для перегляду DjVu під Windows.
У DjVu-файлі зберігається окремо фон, передній план і монохромна маска, що визначає, які пікселі зображення належать фону, а які - переднього плану. Фон і передній план кодуються алгоритмом IW44, який, як і JPEG, кілька розмиває зображення. Автори стверджують, що IW44 досягає зменшення розмірів файлу в два рази в порівнянні з JPEG при тому ж рівні спотворень.
Чорно-біла маска кодується алгоритмом JB2. Цей алгоритм досягає стиснення в 4-6 разів кращого, ніж TIFF-G4 (CCITT/MMR Group 4). Як і у випадку з багатьма іншими алгоритмами (МРЗ, наприклад), алгоритм декодувальнику визначений жорстко, проте в алгоритмі кодувальника можливі зміни, що покращують стиск.
Частина DjVu-файлу, стисла за алгоритмом JB2, являє собою заархівовану послідовність команд. Ці команди можуть мати вигляд "Поставити таке-то зображення в таку-то крапку", а можуть мати вигляд "Поставити одна з раніше зустрічалися зображень в таку-то крапку". Так як у першому випадку команда містить ціле зображення, нехай і заархівувати, а в другому випадку - всього лише номер, то ясно, що чим більше елементарних зображень однакові, тим краще буде стиск.
Зображення, надходить на вхід кодувальника, розділяється на літери виділенням чорних компонент зв'язності. Алгоритм розрахований на те, що елементарними зображеннями будуть якраз букви, і дійсно, після такого розбиття зазвичай залишаються окремі літери, хоча і шматки в 2-3 букви теж часто зустрічаються.
У відсканованому документі, швидше за все, не буде жодної пари однакових зображень літер, хоча буде дуже багато букв, невідмітних для людини. Якщо навчитися розбивати букви на класи неотличимой, то можна замінити всі літери в класі на одну. Людина не помітить змін у зображенні, а розмір файлу сильно зменшиться.
При допомогою алгоритмів, розроблених автором, розмір файлу зменшується на 55 В± 5% (Для сторінок, які містять лише текст; малюнки і діаграми зменшують цей показник, оскільки займають багато місця і не стискаються). Єдина некомерційна програма для ЛВ2-стиснення, cjb2 з DjVuLibre, досягає зменшення розміру тільки на 30 В± 5%.
Тепер опишемо загальну схему алгоритму класифікації букв. Припустимо, що є алгоритм для порівняння пари букв (сам алгоритм буде описаний далі). По парі букв він видає один із трьох відповідей - В«такВ», В«ніВ» або В«може бутиВ». Відповідь В«такВ» означає, що букви, на думку алгоритму, еквівалентні; відповідь В«ніВ» означає, що алгоритм вважає літери різними, відповідь В«може бутиВ» означає, що алгоритм не впевнений, але краще вважати їх різними уникнення помилок.
Можливість В«НіВ» існує тільки для прискорення. Якщо алгоритм замість В«ніВ» буде завжди говорити В«може бутиВ», то результат не зміниться, але швидкість впаде (в програмі швидкість падає в 4,5 рази).
Будемо вважати, що алгоритм не помиляється, кол...
