Fractal Image Compression

Опис

За допомогою цієї програми ви можете:

Стискати зображення з цим фрактальним методом
Декомпресувати попередньо стиснуті зображення в іншому форматі

Скористайтеся бібліотеками платформи, у яких містяться такі можливості:

Багатомовна
Налаштований багатореставрний масштаб
Параметр темного режиму
Сповіщення про нову версію

Прос:

Якщо програму правильно запрограмовано, вона працює незалежно від роздільної здатності зображення.
Це відмінний метод стискання
Дозволяє вам вчитися

Збори:

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

Опис коду

Це реалізація цьогоалгоритм fractal image compression(англ.), опублікованій в IEEE під час навчання в коледжі.

Програма використовує додаткову бібліотеку триангуляції Delauny, яка також використовується уПеремотування програмName

Алгоритм високого рівня:

Стиснення:
- Fractal стиснення фокусується на збереженні взаємозв' язків між ділянками зображення, а не на фактичних значеннях пікселів, особливо між трикутниками у цьому випадку.
- Зображення поділено на трикутну сітку, що складається з декількох трикутників, утворюючи триангульований домен.
- Зображення поділяється на новий набір триангуляцій з більшими трикутниками, що позначаються для кодової книги.
- Триангуляції є динамічними, алгоритм дроблення і об' єднання застосовуються на основі розбіжності у пікселях трикутника.
- Після того, як буде визначено триангуляцію кодової книги, буде обрано найбільш репрезентовані 2^n трикутники для створення кодової книги. Значення n істотно впливатиме на час стискання з незначним впливом на коефіцієнт стискання і на якість, яку буде досягнуто.
- Для кожного доменного трикутника, оптимальне відображення з трикутником з кодової книги на основі мінімального значення квадратної помилки (MSE)
- Оптимальне відображення між трикутниками можна знайти за допомогою комбінацій:
  - Пересилки вершин (6 можливостей)
  - Визначення зсуву для середнього значення
  - Пошук коефіцієнта масштабування між 0 і 1, який буде застосовано до відхилення від середнього значення. Цей коефіцієнт масштабу має зберігатися між 0 і 1, щоб запобігти розбіжності під час ітеративного процесу стискання.
  Крім того, ці параметри слід оцінювати за допомогою обмеженої кількості бітів, щоб переконатися, що і час стискання, і співвідношення є поміркованими і у відповідності з бажаною якістю.
Збережена інформація у стиснутому файлі для кожного каналу:
- Інформація для відтворення двох триангуляцій:
  - Трикутники, що розділяються на кожну ітерацію
  - Вершини, які було вилучено у результаті об' єднання (після завершення ітерацій дроблення)
- Вибір 2^n трикутників коду
- Оптимальна карта кожного доменного трикутника:
  - Який трикутник кодової книги він використовує для карти (n бітів)
  - Оптимальна перестановка (6 комбінацій, 3 біти)
  - Зміщення (записи вказують на те, що відступ ефективно представлено з 6 бітами)
  - Масштаб (записи вказують на те, що масштаб ефективно представлено з 6 бітами)
Декомпресування (для кожного каналу):
- З'являються трикутники двох триангуляцій.
- Трикутники кодової книги.
- Цей процес повторюється до завершення зв' язку:
  - Приписування всіх трикутників домену до їх оптимальних кореспонденцій з трикутниками кодової книги

Отримавши ступінь магістра в штучному інтелекті, я передбачаю, як вивести найбільш важливі трикутники для книги коду, застосовуючи K-медоїди.

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

Обробка зображень поділено на канали, типово RGB.

Вона використовує багатопроцесорні процеси, з однією ниткою, присвяченою кожному каналу.

З версією v1. 1 було додано інструмент для читання, сумісний з стандартом ImageIO.

Отже, ви можете відкрити стиснуте зображення (. dfc) за допомогою програми просто:

BufferedImage image = ImageIO.read("image.dfc");

Версії

Fractal image compression v1, 0 & copyright; (2022- 24)

Програма реалізує алгоритм fractal image compression описаний у газеті IEEE з моїх університетських днів. Цей алгоритм засновано на триангуляції Делауней і програмуванні блоків.

Я співпрацював з однокурсником університету, щоб розробити першу версію цього алгоритму під час інтернування останнього курсу Телеко Телебачення (план 64 Барселони).

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

Я пам'ятаю, що ми розробляли досить непогану тріанґуляцію Делауни і успішно впроваджували підхід розділення та об' єднання. Це означало обчислювати найбільш репрезентуючі трикутники і знаходити оптимальні карти під час процесу кодування. Але, незважаючи на три місяці інтенсивного розвитку, ми так і не закінчили програму.

Зараз, 25 років потому, я презентую вам нову реалізацію алгоритму, повністю розроблений і завершений за два тижні.

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

Цього разу за допомогою бібліотеки " Триангуляція " Делауней запрограмована спеціалістами.

Очевидно, що коли ви не мусите робити цеглу самостійно, то чим швидше ви можете будувати стіни...

Відео- демонстрація

Fractal image compression v1. 1 & copyright; (2026)

Нова можливість у версії v1. 1 - додавання програми для читання зображень з фракталом у програмі, сумісній з ImageIO.

Отже, ви можете прочитати стиснуте зображення (. dfc) з програмою у такий спосіб:

BufferedImage image = ImageIO.read("image.dfc");

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

Але результат зовсім не поганий.

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

⇩05/2026 - ⇩12/2026 . після відновлення еволюції цієї програми, я пропоную зробити тести з справжніми зображеннями, і я спробую зробити це з "4000 x 3000" пікселів.

Я стикаюся з багатьма проблемами:

Процес триває цілу вічність у поділених ітераціях (за рахунок широких триангуляцій до 400 000 трикутників, і що перевірку стану було повторено для всіх трикутників у кожній ітерації)
Пам'ять вичерпується після обмеження 23 ГБ, яке я мав на своїй системі.
- Результат ітерацій дроблення і об' єднання зберігається у булівському списку (близько 16 ітерій x 2 типів триангуляції x 3 каналі x 400 000 елементів!!!!). Загалом це приблизно 40 000 000 елементів, які все ще прийнятні)
- Крім того, вибір книги більшості представлених трикутників (встановлених до 256) було виконано за допомогою K- ммедоїдів (понад 400 000 елементів) (Я думаю, що пам' ять, використана цим алгоритмом, була O'n^2). Тепер вона виходить з- під контролю...)
- І, для більшої кількості ІНРІ, ці обчислення були паралельні до трьох каналів (rgb)!
Після того, як ці проблеми будуть розв'язані, мені вдається стиснути зображення (4000 x 3000), але я бачу, що для завершення роботи потрібно 6-8 годин.

І я пропоную їх вирішити:

Для вшанування дроблень. Вирішення:
- Я збільшую мінімальний розмір трикутників, які слід розділити, покроково пропорційно до кількості пікселів у зображенні. Результат полягає у зменшенні кількості трикутників у трикулях. У зображенні (4000 x 3000) кількість трикутників ділиться на більше ніж 4 (ми перейшли від 400 000 трикутників до близько 100 000 трикутників).
- Крім того, я створюю Створення з трикутниками, які не відповідають критерію дроблення (відносно розбіжності значень їх пікселів), щоб не повторювати їх у кожній ітерації. Тепер стрибайте!
У системі закінчується пам' ять. Вирішення:
- Результат дроблень і об' єднання збережено у булівських списках. Вирішення:
  - Як прогрес поділу ітерацій, кількість трикутників, які розділюються радикально, пам'ять зберігається шляхом збереження індексів трикутників, які розділюються на Сет.
- Пам' ять K- медоїдів (здебільшого O' n^2). Вирішення:
  - Як ми поділили кількість трикутників на 4... пам'ять, потрібна для цього алгоритму, це зменшення трикутників включає ділення пам'яті, що використовується коефіцієнтом близько 16 разів.
  - Три кондитерських конструкцій (по одному для кожного каналу). Вирішення:
    - Ми поєднуємо обчислення триангуляцій і вибір найбільш репрезентуючих трикутників для книги коду (з K-медоїдами).
  - Ми поділили пам'ять, необхідну для "Кмедоїдів 48"!
Процес обробки зображень " справжнього " триває вічно ( стискання прикладу зображення займає від 6 до 8 годин) з 3 нитками, по одному для кожного з каналів. Вирішення:
- Зробіть налаштування кількості гілок. (Налаштувавши її до 23 ниток (у моїй системі 24 ядра), час обробки буде зменшено до трьох з половиною годин).
Ефекти розв' язку:
- Результат поділу на 4 трикутників, очевидно, призводить до значної втрати якості стиснутого зображення, але з такою великою роздільною здатністю, це не настільки важливо.
- Якщо поділити кількість трикутників на 4, це також призводить до поділу розміру стисненого файла, який, як гадають, також і порядку 4.

Я також намагаюся зменшити розмір стиснутого файла, реорганізуючи дані, які слід зберігати.

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

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

Я думаю, він не марнується, якщо ви допитливі. на цьому сайті я розповідаю про ключові точки, на які я покладався.

Хоча, можливо, варто було б шукати загального компресора без втрат, наприклад, "застібку" або "7z," а потім застосувати його до глобальності стиснутого файла... можливо, наступного разу.

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

За допомогою цієї маленької програми на парі файлів з початковим кодуванням (одне з 143x143 та інше з 4000x3000), можна зменшити розмір стиснутого файла на 4%.