Вас вітає Інтернет конференція!
Вітаємо на нашому сайті
ПОРІВНЯЛЬНИЙ АНАЛІЗ АЛГОРИТМІВ СТИСНЕННЯ ЗОБРАЖЕНЬ НА ОСНОВІ КУСКОВО-ЛІНІЙНОЇ АПРОКСИМАЦІЇ ТА РІЗНИХ СТРАТЕГІЙ ОБХОДУ МАТРИЦІ
07.12.2023 23:53
[1. Інформаційні системи і технології]
Автор: Сточанський Мар’ян Андрійович, студент, Національний університет «Львівська політехніка»
ORCID: 0009-0002-6739-836X
Вступ. Одним зі способів стиснення зображення є стиснення на основі кусково-лінійної апроксимації. Серед алгоритмів кусково-лінійної апроксимації розглядаються алгоритми Рамера-Дугласа-Пакера, Реуманна-Віткама, Вісвалінгама-Уайатта.
Стиснення, засноване на методі кусково-лінійної апроксимації, представляє спрощений підхід до стиснення зображень. Цей метод виявляє значну гнучкість, пропонуючи широкий спектр існуючих алгоритмів кусково-лінійної апроксимації [1-2]. Кусково-лінійна апроксимація дозволяє спростити функцію до набору лінійних фрагментів, що різко зменшує обсяг даних. Цей підхід базується на використанні простих лінійних функцій, що спрощує процес відтворення зображення з апроксимованих даних.
Рис. 1. Приклад кусково-лінійної апроксимації
Аналіз алгоритмів. Суть апроксимації полягає у стисненні певної функції. Для цього зображення потрібно перетворити у відповідну функцію, яка стане об'єктом апроксимації. У випадку стиснення зображень використовується формула відносної яскравості. Для кожного рядка, стовпця чи іншого вибраного елемента зображення формується відповідна функція, що відображає відносну яскравість кожного пікселя. Формула визначення яскравості кожного пікселя у моделі RGB визначається наступним чином (1):
де R – значення червоного каналу кольору, G – значення зеленого каналу кольору, B – значення синього каналу кольору.
Алгоритм Рамера-Дугласа-Пакера використовує стратегію "розділяй і володарюй". Далі алгоритм обчислює відстань від кожної точки до відрізка по перпендикуляру та обирає найдальшу вершину, яка залишається в результаті. Далі по цій точці відбувається розбиття на 2 криві, і алгоритм рекурсивно продовжується.
Алгоритм Реуманна-Віткама базується на створенні смуги, що пролягає через останні дві підтверджені значущі точки [3]. Ширина цієї смуги завжди відповідає точності наближення. Суть алгоритму полягає в тому, щоб вилучати всі точки, які не належать до цієї смуги, до тих пір, поки не буде знайдено першу точку за її межами. Ця точка стає наступною значущою точкою . Цей процес триває, доки алгоритм не дійде до кінця кривої.
Алгоритм Вісвалінгама-Уайатта створює трикутники, з'єднуючи три сусідні точки і обчислює їх площу на кожній ітерації. Потім з усіх сформованих трикутників обирається той, що має найменшу площу, і видаляється вершина, пов'язана з цим трикутником. Після цього відбувається процес створення нових трикутників і вибору трикутника з найменшою площею повторюється.
Для порівняння алгоритмів потрібно обирати такі метрики, які мають найбільше значення для кінцевого користувача. Серед таких метрик є час виконання, час кодування та декодування зображення, відношення розміру вхідних та вихідних даних зображення та середньоквадратичну похибку (MSE). MSE є поширеним показником при оцінці ефективності регресійної моделі [4]. Цей показник обчислюється за формулою (2):
де N та M – висотою та шириною зображення відповідно, I – матриця оригінального зображення, С – відтворена матриця стиснутого зображення.
Результати досліджень. Для порівняння стиснення потрібно використовувати вхідне зображення, над яким буде проводитись операція стиснення. У якості тестового зображення для таких порівнянь зазвичай використовують стандартне зображення "Lenna". Стандартний розмір цього зображення складає 512 на 512 пікселів.
Основна мета алгоритмів кусково-лінійної апроксимації полягає у виявленні ключових точок, кількість яких залежить від рівня точності наближення. Це значення повинне бути позитивним. Чим вище його значення, тим менше ключових точок в апроксимації, і, навпаки, при зменшенні цього значення, збільшується кількість точок, що вважаються значущими. На рис. 2 та 3 зображено результат стиснення з точністю наближення 2 та 32 для алгоритму Рамера-Дугласа-Пакера.
Рис. 2. Результати стиснення за алгоритмом Рамера-Дугласа-Пакера з точністю наближення 2 (а) та 32 (б)
Як можна побачити, при меншому значенні точності наближення середньоквадратична похибка, яка вказує на якість апроксимації набагато менша. Так, для точності наближення 2 це значення рівне близько 1.67%, а для точності 32 це значення рівне 7.8%. Також візуально помітно на рис. 2 (б) стиснене зображення значно спотворене, порівняно з зображенням, стисненим з точністю наближення 32.
Для порівняння алгоритмів кусково-лінійної апроксимації та стратегій обходу матриць візьмемо тестове зображення з розширенням 512x512 пікселів та точність наближення 2. Результат виконання програми зображено на рис. 3.
Рис. 3. Результат порівняння конфігурацій при точності наближення рівному 2
На даному рисунку результати порівняння відсортовано за ступенем стиснення. Результати порівняння показують, що використання різних алгоритмів при однаковій точності наближення веде до значної різниці у ступені стиснення через різний спосіб використання цього значення алгоритмами. Отже, порівняння цих алгоритми за таких умов не є об'єктивним і не дозволяє зробити висновки про їх ефективність.
Для виконання об’єктивного порівняння потрібно підібрати таку точність наближення, щоб ступінь стиснення для всіх алгоритмів був однаковий. Так для Рамера-Дугласа-Пакера було обрано точність наближення 2, для Реуманна-Віткама – 5, а для Вісвалінгама-Уайатта – 11. Результати зображено на рис. 4.
Рис. 4. Результат порівняння конфігурацій при степені стиснення 3
Як видно з рисунку 3, найкращий час апроксимації демонструє алгоритм Реуманна-Віткама, який приблизно в 6-7 разів швидше ніж Рамера-Дугласа-Пакера та в 20 разів швидше ніж Вісвалінгама-Уайатта. Алгоритм Вісвалінгама-Уайатта є найповільнішим, проте для нього MSE є найнижчим. Це вказує на те, що ефективність апроксимації вища та зображення менше спотворюється.
Висновки. Кожен алгоритм стиснення демонструє різні результати при однаковому значенні точності наближення, що робить порівняння неефективним. Порівнюючи алгоритми з однаковим ступенем стиснення, найшвидшим є алгоритм Реуманна-Віткама. При цьому алгоритм Вісвалінгама-Уайатта демонструє найкращу якість стиснення, хоча і є найповільнішим.
Література
1. R. Melnyk, P. Viazovskyy, “Image compression using piecewise-linear approximation”, Computer science and information technologies; 20-24 November, 2012 Lviv, Ukraine.
2. Melnyk R. A. Image compression based on the Visvalingam-Whyatt algorithm / R. A. Melnyk, Y. L. Shokur // Litteris et Artibus : proceedings of the 6th International 68 youth science forum, November 24-26, 2016, Lviv, Ukraine / Lviv Polytechnic National University. - Lviv : Lviv Polytechnic Publishing House, 2016. - P. 63-66. Bibliography: 11 titles.
3. Melnyk R. A. Image compression by Ramer–Douglas–Peucker approximation algorithm / R.A. Melnyk, P.V. Viazovskyy // Тези доповідей Пʼятої міжнародної науково-практичної конференції «Методи та засоби кодування, захисту й ущільнення інформації», м. Вінниця, 19-21 квітня 2016 р. – Вінниця : ВНТУ, 2016 – С. 111-113.
4. Prasad N. G. N., Rao J. N. K. The Estimation of the Mean Squared Error of Small-Area Estimators. Journal of the American Statistical Association. 1990. Vol. 85, no. 409. P. 163–171. URL: https://doi.org/10.1080/01621459.1990.10475320 (дата звернення: 10.06.2023).
_________________________________________________________________________
Науковий керівник: Мельник Роман Андрійович, доктор технічних наук, професор, Національний університет «Львівська політехніка»
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter
Інші наукові праці даної секції
-
СКЛАДОВІ СЕГМЕНТУ ІТ-ПОСЛУГ І ЙОГО ПЕРСПЕКТИВИ В КОНТЕКСТІ ІКТ-РИНКУ УКРАЇНИ
29.11.2023 11:05 -
ЗАСТОСУВАННЯ ЦИФРОВИХ ТЕХНОЛОГІЙ У ПРОЄКТОМУ НАВЧАННІ МАЙБУТНІХ ОСВІТЯН
28.11.2023 23:11 -
ВИЯВЛЕННЯ ДЕФЕКТІВ НА МАТЕРІАЛАХ З ДОПОМОГОЮ НЕЙРОННИХ МЕРЕЖ
27.11.2023 21:08 -
ШАБЛОНИ ВИДОБУВАННЯ ДАНИХ В ЗАДАЧАХ ЕЛЕКТРОННОЇ КОМЕРЦІЇ
27.11.2023 19:23 -
ОСОБЛИВОСТІ ФРЕЙМВОРКІВ САМОНАЛАШТУВАННЯ СИСТЕМ
27.11.2023 18:35
Конференції
Конференції 2024
Конференції 2023
Конференції 2022
Конференції 2021
