Размещено на http://www.allbest.ru/

Київський національний університет будівництва і архітектури

Кафедра кібернетичної безпеки та комп'ютерної інженерії

Курсова робота

з дисципліни «Теорія інформації та кодування»

на тему: Алгоритм стиснення з втратами. Фрактальний алгоритм

Київ-2017



ВСТУП

Останнім часом зображення та ілюстрації стали використовуватися повсюдно. Проблема, пов'язана з великим обсягом для їх обробки і зберігання, з'явилася при роботі і на робочих станціях, і на персональних комп'ютерах. Розроблена велика кількість різних алгоритмів архівації графіки. фрактальний стиснення зображення перетворення

Майкл Барнслі і Алан Слоун знайшли новий метод вирішення даного завдання. У методі використовується принципово нова ідея - чи не близькість квітів в локальній області, а подібність різних за розміром областей зображення. Так за допомогою стандартних прийомів обробки зображень, таких, як виділення країв і аналіз текстурних варіацій, зображення ділиться на сегменти і кодується за допомогою деякого стискає афінного перетворення. Відновлення зображення відбувається за допомогою багаторазового застосування цього афінного перетворення.

Метою цієї роботи є побудова методу фрактального стиснення для зображень. В роботі розглядаються основні принципи методу, його обґрунтування, алгоритм його реалізації.



РОЗДІЛ 1. ЗАГАЛЬНІ ВІДОМОСТІ

1.1 Стиснення з втратами

Говорячи про коди стиснення, розрізняють поняття «стиснення без втрат» і «стиснення з втратами». Очевидно, що коли ми маємо справу з інформацією типу «номер телефону», то стиснення такого запису за рахунок втрати частини символів не веде ні до чого хорошого. Проте можна уявити цілий ряд ситуацій, коли втрата частини інформації не призводить до втрати корисності залишилася. Стиснення з втратами застосовується в основному для графіки (JPEG), звуку (MP3), відео (MPEG), тобто там, де в силу величезних розмірів файлів ступінь стиснення дуже важлива, і можна пожертвувати деталями, неістотними для сприйняття цієї інформації людиною. Особливі можливості для стиснення інформації є при компресії відео. У ряді випадків більша частина зображення передається з кадру в кадр без змін, що дозволяє будувати алгоритми стиснення на основі вибіркового відстеження тільки частини «картинки». В окремому випадку зображення людини, що говорить, що не змінює свого положення, може оновлюватися тільки в області особи або навіть тільки рота - тобто в тій частині, де відбуваються найбільш швидкі зміни від кадру до кадру.

В цілому ряді випадків стиснення графіки з втратами, забезпечуючи дуже високі ступеня компресії, практично непомітно для людини. Так, з трьох фотографій, показаних нижче, перша представлена в TIFF-форматі (формат без втрат), друга збережена в форматі JPEG c мінімальним параметром стиснення, а третя з максимальним. При цьому можна бачити, що останнє зображення займає майже на два порядки менший обсяг, ніж первая.Однако методи стиснення з втратами мають і низку недоліків.

Перший полягає в тому, що компресія з втратами застосовна не для всіх випадків аналізу графічної інформації. Наприклад, якщо в результаті стиснення зображення на обличчі зміниться форма родимки (але обличчя при цьому залишиться повністю впізнається), то ця фотографія виявиться цілком прийнятною, щоб послати її поштою знайомим, однак якщо пересилається фотознімок легких на медекспертизу для аналізу форми затемнення - це вже зовсім інша справа. Крім того, в разі машинних методів аналізу графічної інформації результати кодування з втратою (непомітні для очей) можуть бути «помітні» для машинного аналізатора.

Друга причина полягає в тому, що повторна компресія і декомпресія з втратами призводять до ефекту накопичення похибок. Якщо говорити про ступінь застосовності формату JPEG, то, очевидно, він корисний там, де важливим є великий коефіцієнт стиснення при збереженні вихідної колірної глибини. Саме це властивість зумовило широке застосування даного формату в поданні графічної інформації в Інтернеті, де швидкість відображення файлу (його розмір) має першорядне значення. Негативна властивість формату JPEG - погіршення якості зображення, що робить практично неможливим його застосування в поліграфії, де цей параметр є визначальним.

Тепер перейдемо до розгляду про стиснення інформації без втрат і розглянемо фрактальний алгоритм[7].

1.2 Алгоритм фрактального стиснення

Фрактальное стиснення зображень - алгоритм стиснення зображень c втратами, заснований на застосуванні систем ітеріруемих функцій (як правило є аффіннимі перетвореннями) до зображень. Даний алгоритм відомий тим, що в деяких випадках дозволяє отримати дуже високі коефіцієнти стиснення при прийнятному візуальному якості для реальних фотографій природних об'єктів. Через складну ситуацію з патентуванням широкого поширення алгоритм не отримав[2].

Фрактальна архівація заснована на тому, що ми представляємо зображення в більш компактній формі - за допомогою коефіцієнтів системи ітеріруемих функцій (Iterated Function System - далі по тексту як IFS). Перш, ніж розглядати сам процес архівації, розберемо, як IFS будує зображення, тобто процес декомпресії.

Якщо сказати іншими словами, IFS являє собою набір тривимірних афінних перетворень, в нашому випадку переводять одне зображення в інше. Перетворенню піддаються точки в тривимірному просторі (х_коордіната, у_коордіната, яскравість).

Найбільш наочно цей процес продемонстрував Барнслі в своїй книзі 'Fractal Image Compression'. Там введено поняття фотокопіювальних Машини, що складається з екрану, на якому зображена вихідна картинка, і системи лінз, що проектують зображення на інший екран:

· Лінзи можуть проектувати частина зображення довільної форми в будь-яке інше місце нового зображення.

· Області, в які проектується зображення, не перетинаються.

· Лінза може змінювати яскравість і зменшувати контрастність.

· Лінза може дзеркально відображати і повертати свій фрагмент зображення.

· Лінза повинна масштабувати (зменшувати) свій фрагмент зображення.

Рисунок 1.1 -- Фотокопіювальна машина



Розставляючи лінзи і змінюючи їх характеристики, ми можемо керувати одержуваних зображенням. Одна ітерація роботи Машини полягає в тому, що по вихідного зображення за допомогою проектування будується нове, після чого нове береться в якості вихідного. Стверджується, що в процесі ітерацій ми отримаємо зображення, яке перестане змінюватися. Воно буде залежати тільки від розташування і характеристик лінз, і не буде залежати від вихідної картинки. Це зображення називається 'нерухомою точкою' або аттрактором даної IFS. Відповідна теорія гарантує наявність рівно однієї нерухомої точки для кожної IFS.

Оскільки відображення лінз є стискає, кожна лінза в явному вигляді задає самоподібні області в нашому зображенні. Завдяки самоподібності ми отримуємо складну структуру зображення при будь-якому збільшенні. Таким чином, інтуїтивно зрозуміло, що система ітеріруемих функцій задає фрактал (нестрого - самоподібний математичний об'єкт).

Найбільш відомі два зображення, отриманих за допомогою IFS: 'трикутник Серпінського'(рисунок 1.2) і 'папороть Барнслі'(рисунок 1.3). 'Трикутник Серпінського' задається трьома, а 'папороть Барнслі' чотирма аффіннимі перетвореннями (або, в нашій термінології, 'лінзами'). Кожне перетворення кодується буквально ліченими байтами, в той час як зображення, побудоване з їх допомогою, може займати і кілька мегабайт.

Рисунок 1.2 -- Трикутник Серпінського



Рисунок 1.3 -- Папороть Барнслі

З вищесказаного стає зрозуміло, як працює архіватор, і чому йому потрібно так багато часу. Фактично, фрактальна компресія - це пошук самоподібних областей в зображенні і визначення для них параметрів афінних перетворень.

У гіршому випадку, коли не буде застосовуватися оптимізує алгоритм, буде потрібно перебір і порівняння всіх можливих фрагментів зображення різного розміру. Навіть для невеликих зображень при обліку дискретності ми отримаємо астрономічне число перебираються варіантів. Причому, навіть різке звуження класів перетворень, наприклад, з допомогою масштабування тільки в певну кількість разів, не дає помітного виграшу в часі. Крім того, при цьому втрачається якість зображення. Переважна більшість досліджень в області фрактальної компресії зараз спрямовані на зменшення часу архівації, необхідної для отримання якісного зображення[6].

1.3 Типова схема фрактального стиснення

З урахуванням вищесказаного, схема компресії виглядає так: зображення R розбивають на рангові області R. Далі для кожної області R знаходять область D і перетворення w такі, що виконуються наступні умови:

1) D за розмірами більше R.

2) w (R) має ту ж форму, розміри і положення, що і R.

3) Коефіцієнт перетворення повинен бути менше одиниці.

4) Значення має бути якомога менше.

Перші три умови означають, що відображення w буде стискає. А в силу четвертого умови кодуються зображення R і його образ W (R) будуть схожі один на одного. В ідеалі R = W (R). А це означає, що зображення R і буде нерухомою точкою W. Саме тут використовується подобу різних частин зображення. Як виявилося, практично всі реальні зображення містять такі схожі один на одного, з точністю до афінного перетворення, частини.

Таким чином, для компресії зображення W потрібно:

1) Розбити зображення на рангові області R (непересічні області, що покривають все зображення).

2) Для кожної рангової області R знайти область D, і відображення w, з зазначеними вище властивостями.

3) Запам'ятати коефіцієнти афінних перетворень W, положення доменних областей D, а також розбиття зображення на домени.

Відповідно, для декомпресії зображення потрібно буде:

1) Створити початкове зображення R.

2) Багаторазово застосувати до нього відображення W (об'єднання w).

3) Так як відображення W стискуюче, то в результаті, після достатньої кількості ітерацій, зображення прийде до аттрактору і перестане змінюватися. Аттрактор і є нашим вихідним зображенням. Декомпресія завершена[4].



1.4 Побудова алгоритму , афінне перетворення

Як вже стало очевидним з викладеного вище, основним завданням при компресії фрактальним алгоритмом є знаходження відповідних афінних перетворень.

Афінне перетворення (від лат. Affinis - дотичний, близький, суміжний) - відображення площини або простору в себе, при якому паралельні прямі переходять в паралельні прямі, що перетинаються в пересічні, перехресні в перехресні [5].

Афінне перетворення f:RR є перетворення виду

f(x)=M*x+v,

де M - оборотна матриця та vR.

У найзагальнішому випадку ми можемо перекладати будь-які за розміром і формою області зображення, проте в цьому випадку виходить астрономічне число перебираються варіантів різних фрагментів, яке неможливо обробити на поточний момент навіть на суперкомп'ютері.

У моєму варіанті алгоритму, викладеному далі, зроблені наступні обмеження на області:

1) Всі області є квадратами зі сторонами, паралельними сторонам зображення. Це обмеження досить жорстке. Фактично ми збираємося апроксимувати все різноманіття геометричних фігур лише квадратами.

2) При перекладі доменної області в рангову зменшення розмірів виробляється рівно в два рази. Це істотно спрощує як компресор, так і декомпресор, тому що задача масштабування невеликих областей є нетривіальною.

3) Всі доменні блоки - квадрати і мають фіксований розмір. Зображення рівномірної сіткою розбивається на набір доменних блоків.

4) Доменні області беруться 'через точку' і по Х, і по Y, що відразу зменшує перебір в 4 рази.

5) При перекладі доменної області в рангову поворот куба можливий тільки на 00, 900, 1800 або 2700. Також допускається дзеркальне відображення. Загальна кількість можливих перетворень (вважаючи пусте) - 8.

6) Масштабування (стиснення) по вертикалі (яскравості) здійснюється в фіксоване число раз - в 0,75

Рисунок 1.4 -- Розбиття квадрату на доменні блоки

Ці обмеження дозволяють:

1) Побудувати алгоритм, для якого потрібно порівняно мале число операцій навіть на досить великих зображеннях.

2) Дуже компактно представити дані для запису в файл. Нам потрібно на кожне афінне перетворення в IFS:

· два числа для того, щоб задати зсув доменного блоку. Якщо ми обмежимо вхідні зображення розміром 512х512, то досить буде по 8 біт на кожне число.

· три біта для того, щоб задати перетворення симетрії при перекладі доменного блоку в рангові.

· 7-9 біт для того, щоб задати зсув по яскравості при перекладі.

Інформацію про розмір блоків можна зберігати в заголовку файлу. Таким чином, ми витратили менше 4 байт на одне Афінний перетворення. Залежно від того, який розмір блоку, можна вирахувати, скільки блоків буде в зображенні. Таким чином, ми можемо отримати оцінку ступеня компресії.

Наприклад, для файлу в градаціях сірого 256 кольорів 512х512 пікселів при розмірі блоку 8 пікселів афінних перетворень буде 4096 (512 / 8x512 / 8). На кожне потрібно 3.5 байта. Отже, якщо вихідний файл займав 262144 (512х512) байт (без урахування заголовка), то файл з коефіцієнтами буде займати 14336 байт. Коефіцієнт архівації - 18 разів. При цьому ми не враховуємо, що файл з коефіцієнтами теж може мати надмірністю і архівувати методом архівації без втрат, наприклад LZW[6].

1.5 Аналіз роботи

Метою даної роботи є вивчення поведінки фрактального алгоритму стиснення з втратами. В вищесказаному розділі побудови алгоритму мною були зроблені та викладені у цьому розділі обмеження на області в алгоритмі. Проаналізувавши їх , зараз я наведу негативні сторони запропонованих мною обмежень.

1) Оскільки всі області є квадратами, неможливо скористатися подобою об'єктів, по формі далеких від квадратів (які зустрічаються в реальних зображеннях досить часто.)

2) Аналогічно ми не зможемо скористатися подобою об'єктів в зображенні, коефіцієнт подібності між якими сильно відрізняється від 2.

3) Алгоритм не зможе скористатися подобою об'єктів в зображенні, кут між якими не кратний 900.

Така плата за швидкість компресії і за простоту упаковки коефіцієнтів в файл.

Сам алгоритм упаковки зводиться до перебору всіх доменних блоків і підбору для кожного відповідного йому рангового блоку.

А зараз я хотів би порівняти фрактальний алгоритм з найбільш розповсюдженим алгоритмом архівації графіки - JPEG.

По-перше, зауважимо, що і той, і інший алгоритм оперують 8-бітними (в градаціях сірого) і 24-бітними кольоровими зображеннями. Обидва є алгоритмами стиснення з втратами і забезпечують близькі коефіцієнти архівації. І у фрактального алгоритму, і у JPEG існує можливість збільшити ступінь стиснення за рахунок збільшення втрат. Крім того, обидва алгоритму дуже добре распараллелівать.

Відмінності починаються, якщо ми розглянемо час, необхідне алгоритмам для архівації / розархівації. Так, фрактальний алгоритм стискає в сотні і навіть в тисячі разів довше, ніж JPEG. Розпакування зображення, навпаки, відбудеться в 5-10 разів швидше. Тому, якщо зображення буде стисло тільки один раз, а передано по мережі і Розпаковано безліч разів, то вигідніше використовувати фрактальний алгоритм.

JPEG використовує розкладання зображення по косинусоидальной функцій, тому втрати в ньому (навіть при заданих мінімальних втратах) проявляються в хвилях і ореолах на кордоні різких переходів квітів. Саме за цей ефект його не люблять використовувати при стисненні зображень, які готують для якісного друку: там цей ефект може стати дуже помітний. Фрактальний алгоритм позбавлений цього недоліку. Більш того, при друку зображення кожного разу доводиться виконувати операцію масштабування, оскільки растр друкувального пристрою не збігається з растром зображення. При перетворенні також може виникнути декілька неприємних ефектів, з якими можна боротися або масштабуючи зображення програмно, або забезпечуючи пристрій друку своїм процесором, вінчестером і набором програм обробки зображень. Як можна здогадатися, при використанні фрактального алгоритму таких проблем практично не виникає.

З цього всього можна зробити висновок , що витіснення JPEG фрактальним алгоритмом в повсюдному використанні відбудеться ще не скоро (хоча б в силу низької швидкості архівації останнього), проте в області додатків мультимедіа, в комп'ютерних іграх його використання цілком виправдано.



РОЗДІЛ 2. СПЕЦІАЛЬНА ЧАСТИНА

2.1 Постановка задачі

Користувач запучкає програму , у головному вікні потрібно вибрате зображення , яке буде використано для перетворення. Після вибору зображення , користуач налаштовує необхідні параметри для стиснення. Після вибору параметрів , натискаємо кнопку запустить , і відбувається процедура стиснення , це може зайняти деякий час. Після завершення процедури , можна переглянути стиснене зображення , зберегти його або видалити.

2.2 Вхідні та вихідні дані

Вхідними даними моєї програми є зображення з розмірами не більші ніж 512х512.

Вихідними даними є зображення , стиснене фрактальним алгоритмом.

Результат роботи виводить стинену картинку та розмір в бітах.

2.3 Опис алгоритму

Дана програма використовує алгоритм фрактального стиснення. Зараз я опишу свою програму та для прикладу зроблю перетворення з декількома картинками.

Для початку зробимо запуск програми і побачимо головне вікно (Рисунок 2.1).

Нижче показано скільки часу залишилося до закінчення перетворення зображення (Рисунок 2.3).



Рисунок 2.1 Головне вікно програми

Далі ми вибираємо фото для стиснення (Рисунок 2.2).

Рисунок 2.2 Вибір фото для стиснення



Рисунок 2.3 Кількість часу , який залишився до кінця стиснення

Після того , як ми діждемося кінця стиснення , ми можемо переглянути результат (Рисунок 2.4).

Рисунок 2.4 Результат стисненого зображення



Після цього ми можемо переглянути розмір у байтах(Рисунок 2.5).

Рисунок 2.5 Розмір у байтах

Також ми можемо зберегти отримане після стиснення алгоритмом зображення у IFS форматі(Рисунок 2.6).

Рисунок 2.6 Збереження зображення у IFS форматі



Ще один приклад з стисненням зображення (Рисунок 2.7).

Рисунок 2.7 Приклад з стисненням іншого зображення

Рисунок 2.8 Результат стисненого зображення



unit FractalCompression;

interface

uses

Windows, Messages, SysUtils, Graphics, Classes;

type

// Описание одного региона в выходном файле составляет всего-навсего 6 байт

// Таким образом размер файла = Кол-во регионов * 6

TIfsRec = packed record

DomCoordX, DomCoordY: Word; // Координаты левого верхнего угла домена

Betta, FormNum: Byte; // Различие в яркости, Номер преобразования

end;

TRegionRec = packed record

MeanColor: Integer; // Усредненная цветояркость

Ifs: TIfsRec; // Параметры, вычисляемые при компрессии

end;

TDomainRec = packed record

MeanColor: Integer; // Усредненная цветояркость

end;

// Заголовок файла (8 байт)

TIfsHeader = packed record

FileExt: array[1..3] of Char;

RegSize: Byte; // Размер региона

XRegions, YRegions: Word; // Кол-во регионов по Х и У

end;

// Типы афинных преобразований

TTransformType = (ttRot0, ttRot90, ttRot180, ttRot270, ttSimmX, ttSimmY, ttSimmDiag1, ttSimmDiag2);

TProgressProc = procedure(Percent: Integer; TimeRemain: Cardinal) of Object;

TFractal = class(TComponent)

private

SourImage: PByteArray; // Пиксели изображения после преобразования в серый

DomainImage: PByteArray;// Массив пикселей доменного изображения

SourWidth: Integer; // Ширина изображения

SourHeight: Integer; // Высота изображения

FRegionSize: Integer; // Размер региона

FDomainOffset: Integer; // Смещение доменов

Regions: array of array of TRegionRec; // Информация о регионах

Domains: array of array of TDomainRec; // Информация о доменах

FGamma: Real;

FMaxImageSize: Integer; // Максимально допустимый размер изображения

FStop: Boolean;

FIfsIsLoad: Boolean; // Проверяет, была ли выполнена компрессия (загружены ли IFS-данные)

FBaseRegionSize: Integer; // Размер региона при сжатии

{Очищает данные}

procedure ClearData;

{Генерирует исключительную ситуация с сообщением Msg}

procedure Error(Msg: string; Args: array of const);

{Создает массив ссылок Regions на регионы }

procedure CreateRegions;

{По исходному изображению SourImage создает доменное изображение}

procedure CreateDomainImage;

{Создает массив 2-мерный Domains, в который заносится усредненная цветояркость

для каждого домена}

procedure CreateDomains;

{Определяет усредненную яркость для участка Image с началом в т. (X, Y)}

function GetMeanBrigth(Image: PByteArray; X, Y, Width: Integer): Byte;

function XRegions: Integer; // Число регионов по Х

function YRegions: Integer; // Число регионов по У

function XDomains: Integer; // Число доменов по Х

function YDomains: Integer; // Число доменов по У

function DomainImageWidth: Integer; // Ширина доменного изображени

procedure SetGamma(const Value: Real);

procedure SetMaxImageSize(const Value: Integer);

procedure SetRegionSize(const Value: Integer);

procedure SetDomainOffset(const Value: Integer);

{Трансформирует заданный регион в соотв. с TransformType. Пиксели в

заданном регионе должны идти друг за другом}

procedure TransformRegion(Sour, Dest: PByteArray; TransformType: TTransformType);

{Возвращает разницу (метрическое расстояние) между регионом и доменом}

function GetDifference(Region: PByteArray; DomCoordX, DomCoordY, Betta: Integer): Integer;

{Копирует указанный регион из массива AllImage в массив Dest.

Width - ширина массива AllImage}

procedure CopyRegion(AllImage, Dest: PByteArray; X, Y, Width: Integer);

function GetPixel(X, Y: Integer): Byte;

public

constructor Create(AOwner: TComponent); override;

destructor Destroy; override;

{Выполняет собственно само сжатие. При UseAllTransform будут выполнены

все афинные преобразования: поворот и симметрая. В противном случае

будет выполнен только поворот}

procedure Compress(UseAllTransform: Boolean = True; BackProc: TProgressProc = nil);

{Принудительно прерывает процесс фрактального сжатия}

procedure Stop;

{Выполняет распаковку изображения. IterCount - кол-во итераций распаковки,

RegSize - размер региона с распакованном изображении. Если эта величина

такая же, как RegionSize при сжатии, то размер изображение будет как при сжатии.

При уменьшении RegSize распакованное изображение уменьшается и наоборот}

procedure Decompress(IterCount: Integer = 15; RegSize: Integer = 0);

{Строит изображение по доменам. Можно использовать сразу после сжатия для того,

чтобы проверить качество сжатия. Изображение, построенное по доменам,

похоже на восстановленное изображение, только имеет большую контрастность}

procedure BuildImageWithDomains;

{Проверяет, была ли выполнена компрессия (загружены ли IFS-данные, необходимые

для декомпрессии). Если IfsIsLoad=True, то можно смело делать декомпрессию}

property IfsIsLoad: Boolean read FIfsIsLoad;

{Ширина изображения (исходного, построенного по доменам, или распакованного)}

property ImageWidth: Integer read SourWidth;

{Высота изображения (исходного, построенного по доменам, или распакованного)}

property ImageHeight: Integer read SourHeight;

{Возвращает значение яркости для указанного пикселя}

property Pixel[X, Y: Integer]: Byte read GetPixel;

{Загружает полноцветное изображение TBitMap для дальнейшей компрессии}

procedure LoadImage(Image: TBitmap);

{Рисует изображение на переданном TBitmap. При Regions = True рисуется исходное

изображение, иначе рисуется доменное изображение (оно такое же, только

в 4 раза меньше по площади)}

procedure DrawImage(Image: TBitmap; Regions: Boolean = True);

{Сохраняет результат сжатия в двоичный файл}

procedure SaveToFile(FileName: string);

{Выполняет загрузку данных из двоичного файла}

procedure LoadFromFile(FileName: string);

{Определяет, какой размер будет у IFS-файла после компрессии}

function GetIFSFileSize(): Cardinal;

published

{Устанавливает размер региона}

property RegionSize: Integer read FRegionSize write SetRegionSize;

{Величина смещения домена. По умолчанию = 1 (это число соответствует

доменному изображению, которое в 4 раза меньше исходного)}

property DomainOffset: Integer read FDomainOffset write SetDomainOffset;

{Цветовой коэффициент Гамма}

property Gamma: Real read FGamma write SetGamma;

{Максимальный размер изображения}

property MaxImageSize: Integer read FMaxImageSize write SetMaxImageSize;

end;

procedure Register;

implementation

procedure Register;

begin

RegisterComponents('Samples', [TFractal]);

end;

{ TFractal }

procedure TFractal.ClearData;

begin

if Assigned(SourImage) then FreeMem(SourImage);

if Assigned(DomainImage) then FreeMem(DomainImage);

SourImage := nil;

DomainImage := nil;

SourWidth := 0;

SourHeight := 0;

Regions := nil;

Domains := nil;

end;

procedure TFractal.Compress(UseAllTransform: Boolean = True; BackProc: TProgressProc = nil);

var

RegX, RegY, DomX, DomY, Error, BestError, Betta, TransNum, TransCount: Integer;

Region, BaseRegion: PByteArray;

DCoordX, DCoordY, BestFormNum, BestDomX, BestDomY, BestBetta: Integer;

Percent: Real;

Tc, OneRegTime, AllRegTime: Cardinal;

label

LExit;

begin

FStop := False;

FIfsIsLoad := False;

FBaseRegionSize := RegionSize;

if UseAllTransform then TransCount := 8 else TransCount := 4;

if SourImage = nil then

raise Exception.Create('Изображение для фрактального сжатия еще не загружено!');

CreateRegions;

CreateDomains;

GetMem(BaseRegion, RegionSize * RegionSize);

GetMem(Region, RegionSize * RegionSize);

OneRegTime := 0;

AllRegTime := 0;

Tc := GetTickCount;

// Перебираем регионы

for RegY := 0 to YRegions - 1 do

for RegX := 0 to XRegions - 1 do

begin

if RegY * XRegions + RegX > 10 then Tc := GetTickCount;

Percent := (RegY * XRegions + RegX) / (YRegions * XRegions) * 100;

BestError := $7FFFFFFF;

BestFormNum := -1;

BestDomX := -1;

BestDomY := -1;

BestBetta := 0;

CopyRegion(SourImage, BaseRegion, RegX * RegionSize, RegY * RegionSize, SourWidth);

// Перебираем домены

for DomY := 0 to YDomains - 1 do

for DomX := 0 to XDomains - 1 do

begin

// Определяем разницу в яркости. Она всегда одна для любых трансформаций.

Betta := Regions[RegX, RegY].MeanColor - Domains[DomX, DomY].MeanColor;

DCoordX := DomX * DomainOffset;

DCoordY := DomY * DomainOffset;

// Проходим цикл по трансформациям

for TransNum := 0 to TransCount - 1 do

begin

// Выполняем афинное преобразование

TransformRegion(BaseRegion, Region, TTransformType(TransNum));

// Определяем величину разницы между изображениями

Error := GetDifference(Region, DCoordX, DCoordY, Betta);

// Запоминаем во временные переменные лучшие показатели

if Error < BestError then

begin

BestError := Error;

BestFormNum := TransNum;

BestDomX := DCoordX;

BestDomY := DCoordY;

BestBetta := Betta;

end;

if FStop then goto LExit; // Мгновенная реакция на команду выхода Stop

end; // Цикл по трансформациям

end; // Цикл по доменам

// Для каждого домена определяем его координаты и усредненную яркость

for Y := 0 to YDomains - 1 do

for X := 0 to XDomains - 1 do

Domains[X, Y].MeanColor := GetMeanBrigth(DomainImage, X * DomainOffset,

Y * DomainOffset, DomainImageWidth);

end;

procedure TFractal.CreateRegions;

var

X, Y: Integer;

begin

Regions := nil;

SetLength(Regions, XRegions, YRegions);

// Для каждого региона определяем его координаты и усредненную яркость

for Y := 0 to YRegions - 1 do

for X := 0 to XRegions - 1 do

Regions[X, Y].MeanColor := GetMeanBrigth(SourImage, X * RegionSize, Y * RegionSize, SourWidth);

end;

destructor TFractal.Destroy;

begin

ClearData();

inherited;

end;

procedure TFractal.DrawImage(Image: TBitmap; Regions: Boolean = True);

var

X, Y, Pixel: Integer;

Handle: HDC;

begin

if SourWidth * SourHeight < 1 then

Error('Ошибка отрисовки изображения!', []);

Image.Width := SourWidth;

Image.Height := SourHeight;

Handle := Image.Canvas.Handle;

for Y := 0 to SourHeight - 1 do

begin

for X := 0 to SourWidth - 1 do

begin

Pixel := SourImage[Y * SourWidth + X];

Pixel := (Pixel shl 16) + (Pixel shl 8) + Pixel;

SetPixel(Handle, X, Y, Pixel);

end;

end;

if not Regions then

for Y := 0 to SourHeight div 2 - 1 do

begin

for X := 0 to SourWidth div 2 - 1 do

begin

Pixel := DomainImage[Y * DomainImageWidth + X];

Pixel := (Pixel shl 16) + (Pixel shl 8) + Pixel;

SetPixel(Handle, X, Y, Pixel);

end;

end;

end;

procedure TFractal.Error(Msg: string; Args: array of const);

begin

raise Exception.CreateFmt(Msg, Args);

end;

function TFractal.GetMeanBrigth(Image: PByteArray; X, Y, Width: Integer): Byte;

var

I, J, Bufer: Integer;

begin

Bufer := 0;

for I := Y to Y + RegionSize - 1 do

for J := X to X + RegionSize - 1 do

Inc(Bufer, Image[I * Width + J]);

Result := Trunc(Bufer / (RegionSize * RegionSize));

end;

procedure TFractal.LoadImage(Image: TBitmap);

var

X, Y: Integer;

PixColor: TColor;

red, green, blue, mask: integer;

begin

ClearData; // Удаляем массивы

SourWidth := (Image.Width div RegionSize) * RegionSize;

SourHeight := (Image.Height div RegionSize) * RegionSize;

if (SourWidth > MaxImageSize) or (SourWidth < 16) or

(SourHeight > MaxImageSize) or (SourHeight < 16)

then Error('Недопустимые размеры изображения %d x %d', [Image.Width, Image.Height]);

// ======= Заполняем массив SourImage (для регионов) ===========

// Выделяем память под изображение

GetMem(SourImage, SourWidth * SourHeight);

// Делаем пиксели серыми и сохраняем их в строковом массиве SourImage

mask := $000000FF;

for Y := 0 to SourHeight - 1 do

for X := 0 to SourWidth - 1 do

begin

PixColor := Image.Canvas.Pixels[X, Y]; // Определяем цвет пикселя

red := (PixColor shr 16) and mask;

green := (PixColor shr 8) and mask;

blue := PixColor and mask;

SourImage[Y * SourWidth + X] := Byte((red + green + blue) div 3);

end;

// Теперь все пиксели стали серыми.

// ======= Заполняем массив DomenImage (для доменов) ===========

// Вообще-то домены в 2 раза больше регионов, однако из-за этого их сложно сравнивать.

// А вот если мы доменное изображение уменьшим в 4 раза (по площади), то

// размер 1 домена станет равным размеру 1 региона, что гораздо лучше

// и экономнее.

CreateDomainImage;

FIfsIsLoad := False;

end;

procedure TFractal.SetDomainOffset(const Value: Integer);

begin

if (Value < 1) or (Value > 32) then

Error('Задана недопустимая величина смещения домена %d', [Value]);

FDomainOffset := Value;

end;

procedure TFractal.SetGamma(const Value: Real);

begin

if (Value < 0.1) or (Value > 1) then

Error('Параметр GAMMA имеет недопустимое значение %d', [Value]);

FGamma := Value;

end;

procedure TFractal.SetMaxImageSize(const Value: Integer);

begin

FMaxImageSize := Value;

end;

procedure TFractal.SetRegionSize(const Value: Integer);

begin

if (Value < 2) or (Value > 64) then

Error('Задано недопустимое значение региона %d', [Value]);

FRegionSize := Value;

end;

function TFractal.XDomains: Integer;

begin

Result := SourWidth div (2 * DomainOffset) - 1;

if Result <= 1 then

Error('Недопустимое количество доменов по Х %d', [Result]);

end;

function TFractal.YDomains: Integer;

begin

Result := SourHeight div (2 * DomainOffset) - 1;

if Result <= 1 then

Error('Недопустимое количество доменов по Y %d', [Result]);

end;

function TFractal.XRegions: Integer;

begin

Result := SourWidth div RegionSize;

end;

function TFractal.YRegions: Integer;

begin

Result := SourHeight div RegionSize;

end;

procedure TFractal.TransformRegion(Sour, Dest: PByteArray; TransformType: TTransformType);

var

I, J: Integer;

begin

case TransformType of

ttRot0: // Поворот на 0 градусов

begin

for I := 0 to RegionSize - 1 do

for J := 0 to RegionSize - 1 do

Dest[I * RegionSize + J] := Sour[I * RegionSize + J];

end;

ttRot90: // Поворот на 90 градусов

begin

for I := 0 to RegionSize - 1 do

for J := 0 to RegionSize - 1 do

Dest[(RegionSize - 1 - J) * RegionSize + I] := Sour[I * RegionSize + J];

end;

ttRot180: // Поворот на 180 градусов

begin

for I := 0 to RegionSize - 1 do

for J := 0 to RegionSize - 1 do

Dest[(RegionSize - 1 - I) * RegionSize + (RegionSize - 1 - J)] := Sour[I * RegionSize + J];

end;

ttRot270: // Поворот на 270 градусов

begin

for I := 0 to RegionSize - 1 do

for J := 0 to RegionSize - 1 do

Dest[J * RegionSize + (RegionSize - 1 - I)] := Sour[I * RegionSize + J];

end;

ttSimmX: // Симметрия относительно Х

begin

for I := 0 to RegionSize - 1 do

for J := 0 to RegionSize - 1 do

Dest[(RegionSize - 1 - I) * RegionSize + J] := Sour[I * RegionSize + J];

end;

ttSimmY: // Симметрия относительно У

begin

for I := 0 to RegionSize - 1 do

for J := 0 to RegionSize - 1 do

Dest[I * RegionSize + (RegionSize - 1 - J)] := Sour[I * RegionSize + J];

end;

ttSimmDiag1: // Симметрия от. главной диагонали

begin

for I := 0 to RegionSize - 1 do

for J := 0 to RegionSize - 1 do

Dest[J * RegionSize + I] := Sour[I * RegionSize + J];

end;

ttSimmDiag2: // Симметрия от. второстепенной диагонали

begin

for I := 0 to RegionSize - 1 do

for J := 0 to RegionSize - 1 do

Dest[(RegionSize - 1 - J) * RegionSize + (RegionSize - 1 - I)] := Sour[I * RegionSize + J];

end;

end;

end;

function TFractal.DomainImageWidth: Integer;

begin

Result := SourWidth div 2;

end;

procedure TFractal.LoadFromFile(FileName: string);

var

X, Y: Integer;

Header: TIfsHeader;

begin

if not FileExists(FileName) then

Error('Файл "%s" не существует', [FileName]);

with TMemoryStream.Create do

begin

LoadFromFile(FileName);

Seek(0, soFromBeginning);

Read(Header, SizeOf(TIfsHeader));

if Header.FileExt <> 'IFS' then

begin

Free;

Error('Файл "%s" имеет недопустимый формат!', [FileName]);

end;

SourWidth := Header.XRegions * Header.RegSize;

SourHeight := Header.YRegions * Header.RegSize;

RegionSize := Header.RegSize;

Regions := nil;

SetLength(Regions, XRegions, YRegions);

for Y := 0 to YRegions - 1 do

for X := 0 to XRegions - 1 do

Read(Regions[X, Y].Ifs, SizeOf(TIfsRec));

Free;

end;

// Нужен для масштабирования при декомпрессии

FBaseRegionSize := RegionSize;

FIfsIsLoad := True;

end;

procedure TFractal.SaveToFile(FileName: string);

var

X, Y: Integer;

Header: TIfsHeader;

begin

if Regions = nil then

Error('Сжатие изображения не выполнено!', []);

if FileExists(FileName) and not DeleteFile(FileName) then

Error('Невозможно удалить файл %s. Возможно он используется другим приложением' +

'или доступен только для чтения.', [FileName]);

Header.FileExt := 'IFS';

Header.RegSize := RegionSize;

Header.XRegions := XRegions;

Header.YRegions := YRegions;

with TMemoryStream.Create() do

begin

// Сохраняем заголовочную информацию

Write(Header, SizeOf(TIfsHeader));

for Y := 0 to YRegions - 1 do

for X := 0 to XRegions - 1 do

Write(Regions[X, Y].Ifs, SizeOf(TIfsRec));

try

SaveToFile(FileName);

except

Free;

Error('Произошла ошибка при сохранении в файл "%s"', [FileName]);

end;

Free;

end;

end;

procedure TFractal.Decompress(IterCount: Integer = 15; RegSize: Integer = 0);

var

I, J, X, Y, Pixel, Iter: Integer;

Domain1, Domain2: PByteArray;

Scale: Real;

begin

// Массив Region должен быть уже заполненным.

if not FIfsIsLoad then

Error('Данные, необходимые для декомпрессии, не загружены!', []);

Scale := 1;

if RegSize >= 2 then

begin

SourWidth := XRegions * RegSize;

SourHeight := YRegions * RegSize;

Scale := FBaseRegionSize / RegSize;

RegionSize := RegSize;

end;

// Создаем серое изображение.

if Assigned(SourImage) then FreeMem(SourImage);

GetMem(SourImage, SourWidth * SourHeight);

// Делаем пиксели серыми и сохраняем их в строковом массиве SourImage

for I := 0 to SourHeight * SourWidth - 1 do SourImage[I] := 127;

for Iter := 1 to IterCount do

begin

// Создаем доменное изображение

CreateDomainImage;

// Доменное и регионное изображения создали

// Проходим по всем регионам

for J := 0 to YRegions - 1 do

for I := 0 to XRegions - 1 do

begin

// Запоминаем соответствующий домен, чтобы над ним можно было выполнить преобразования

GetMem(Domain1, RegionSize * RegionSize);

GetMem(Domain2, RegionSize * RegionSize);

CopyRegion(DomainImage, Domain1,

Trunc(Regions[I, J].Ifs.DomCoordX / Scale),

Trunc(Regions[I, J].Ifs.DomCoordY / Scale), DomainImageWidth);

// Выполняем заданное преобразование

TransformRegion(Domain1, Domain2, TTransformType(Regions[I, J].Ifs.FormNum));

// Изменяем пиксели текущего региона

for Y := 0 to RegionSize - 1 do

for X := 0 to RegionSize - 1 do

begin

Pixel := Domain2[Y * RegionSize + X] + Regions[I, J].Ifs.Betta;

SourImage[(J * RegionSize + Y) * SourWidth + I * RegionSize + X] := Pixel;

end;

procedure TFractal.CreateDomainImage;

var

X, Y, PixColor: Integer;

begin

if Assigned(DomainImage) then FreeMem(DomainImage);

GetMem(DomainImage, SourWidth * SourHeight div 4);

for Y := 0 to SourHeight div 2 - 1 do

for X := 0 to SourWidth div 2 - 1 do

begin

// Определяем усредненный цвет пикселя (по цветам 4-х соседних пикселей)

PixColor :=

SourImage[Y * 2 * SourWidth + X * 2] + SourImage[Y * 2 * SourWidth + X * 2 + 1] +

SourImage[(Y * 2 + 1) * SourWidth + X * 2] + SourImage[(Y * 2 + 1) * SourWidth + X * 2 + 1];

DomainImage[Y * DomainImageWidth + X] := Trunc(PixColor / 4 * Gamma);

end;

end;

function TFractal.GetDifference(Region: PByteArray; DomCoordX,

DomCoordY, Betta: Integer): Integer;

var

X, Y, Diff: Integer;

begin

Result := 0;

for Y := 0 to RegionSize - 1 do

for X := 0 to RegionSize - 1 do

begin

Diff := Region[Y * RegionSize + X] -

DomainImage[(DomCoordY + Y) * DomainImageWidth + DomCoordX + X];

Inc(Result, Sqr(Abs(Diff - Betta)));

end;

end;

procedure TFractal.CopyRegion(AllImage, Dest: PByteArray; X, Y,

Width: Integer);

var

I, J: Integer;

begin

for I := 0 to RegionSize - 1 do

for J := 0 to RegionSize - 1 do

Dest[I * RegionSize + J] := AllImage[(Y + I) * Width + X + J];

end;

procedure TFractal.BuildImageWithDomains;

var

I, J, X, Y: Integer;

Domain1, Domain2: PByteArray;

begin

if not FIfsIsLoad then

Error('Данные, необходимые для восстановления по доменам, не загружены!', []);

for J := 0 to YRegions - 1 do

for I := 0 to XRegions - 1 do

begin

GetMem(Domain1, RegionSize * RegionSize);

GetMem(Domain2, RegionSize * RegionSize);

// Копируем домен

CopyRegion(DomainImage, Domain1, Regions[I, J].Ifs.DomCoordX,

Regions[I, J].Ifs.DomCoordY, DomainImageWidth);

// Выполняем афинное преобразование

TransformRegion(Domain1, Domain2, TTransformType(Regions[I, J].Ifs.FormNum));

// Копируем домен в регион

for Y := 0 to RegionSize - 1 do

for X := 0 to RegionSize - 1 do

SourImage[(J * RegionSize + Y) * SourWidth + I * RegionSize + X] :=

Domain2[Y * RegionSize + X] + Regions[I, J].Ifs.Betta;

FreeMem(Domain1);

FreeMem(Domain2);

end;

end;

procedure TFractal.Stop;

begin

FStop := True;

end;

function TFractal.GetPixel(X, Y: Integer): Byte;

begin

Result := SourImage[Y * SourWidth + X];

end;

function TFractal.GetIFSFileSize: Cardinal;

begin

Result := (ImageWidth div RegionSize) * (ImageHeight div RegionSize) * SizeOf(TIfsRec);

if Result > 0 then Inc(Result, SizeOf(TIfsHeader));

end;

end.



ВИСНОВКИ

Для виконання курсової роботи використовувався фрактальний алгоритм стиснення. За вхідні дані для моєї програми підходять зображення у форматі BMP з розміром не більше ніж 512х512. Створену мною програма не є ідеальним рішенням , але її можна використовувати для стиснення зображень. З обґрунтування теми моєї курсової роботи можна сказати , що витіснення найбільш популярного і більш використованого алгоритму JPEG , фрактальний алгоритм в повсюдному використанні витіснить його ще не скоро (хоча б в силу низької швидкості архівації останнього), проте в області додатків мультимедіа, в комп'ютерних іграх його використання цілком виправдано.



СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

1. ГОСТ 19.201-78. Техническое задание. требования к содержанию и оформлению [Електронний ресурс]. Режим доступу: http://infostart.ru/public/13769/

2. Алгоритм фрактального сжатия [Електронний ресурс]. - Режим доступу : https://ru.wikipedia.org/wiki/Алгоритм_фрактального_сжатия

3. Лутц, М. Треугольник Серпинского [Електронний ресурс]. - Режим доступу :, http://fractalworld.xaoc.ru/sierpinski_triangle

4. Калугин Е. Обзор алгоритмов сжатия с потерями [Електронний ресурс]. - Режим доступу : http://mf.grsu.by/UchProc/livak/en/po/theory_fractal.html

5. Аффинное преобразование [Електронний ресурс]. - Режим доступу: https://ru.wikipedia.org/wiki/Афинное_преобразование.

6. Ватолин Д.С. Алгоритмы сжатия изображений. Методическое пособие. [Електронний ресурс]. - Режим доступу : http://lib.ru/TECHBOOKS/ALGO/VATOLIN/algcomp.htm#_Toc448152512

7. А.Прохоров . Сжатие информации с потерями и без потерь [Електронний ресурс]. - Режим доступу : http://compress.ru/article.aspx?id=10581

Размещено на Allbest.ru