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

Работа добавлена:



Если Вы нашли нужный Вам реферат или просто понравилась коллекция рефератов напишите о Нас в любой соц сети с помощью кнопок ниже





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

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

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

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

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

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

Студента ІI курсу

Групи КСМ-22с

Спеціальності

«Комп’ютерна інженерія»

Кравченко Д.Л.

КерівникКучанський О.Ю.

Національна шкала___________________

Кількість балів_______ОцінкаESTC____

Член комісії_________________________

                                                                           (підпис) (прізвище та ініціали)

Київ-2017

ЗМІСТ

  • ЗМІСТ
  • ВСТУП
  • РОЗДІЛ 1. ЗАГАЛЬНІ ВІДОМОСТІ
  • 1.2 Алгоритм фрактального стиснення
  • Всі області є квадратами зі сторонами, паралельними сторонам зображення. Це обмеження досить жорстке. Фактично ми збираємося апроксимувати все різноманіття геометричних фігур лише квадратами.
  • При перекладі доменної області в рангову зменшення розмірів виробляється рівно в два рази. Це істотно спрощує як компресор, так і декомпресор, тому що задача масштабування невеликих областей є нетривіальною.
  • Всі доменні блоки - квадрати і мають фіксований розмір. Зображення рівномірної сіткою розбивається на набір доменних блоків.
  • РОЗДІЛ 2. СПЕЦІАЛЬНА ЧАСТИНА
  • 2.1 Постановка задачі
  • 2.2 Вхідні та вихідні дані
  • 2.3 Опис алгоритму
  • ВИСНОВКИ
  • СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ
  • ДОДАТОК

      

ВСТУП

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

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

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

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

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

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

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

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

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

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

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

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

Фрактальна архівація заснована на тому, що ми представляємо зображення в більш компактній формі - за допомогою коефіцієнтів системи ітеріруемих функцій (IteratedFunctionSystem - далі по тексту як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.1 Головне вікно програми

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

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

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

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

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

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

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

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

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

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

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

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

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

ВИСНОВКИ

Для виконання курсовоїроботи використовувався фрактальний алгоритм стиснення.За вхідні дані для моєї програми підходять зображення у форматі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

ДОДАТОК

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

   raiseException.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.

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


Похожие рефераты, которые будут Вам интерестны.

1. Універсальний алгоритм стиснення даних без втрат Лемпеля-Зіва-Велча LZW

2. Алгоритм жазу жолдарымен құрылымымен таныстыру. Алгоритм құруға үйрету

3. Алгоритм Прямого поиска. Алгоритм Бойера-Мура

4. IDEA (англ. International Data Encryption Algorithm, международный алгоритм шифрования данных) — симметричный блочный алгоритм шифрования данных

5. Алгоритм AES

6. Алгоритм Сугено

7. Алгоритм Прима

8. Алгоритм Мамдани

9. Алгоритм самообучения

10. Алгоритм кодировки RSA