ПОРІВНЯЛЬНИЙ АНАЛІЗ АЛГОРИТМІВ СТИСНЕННЯ ЗОБРАЖЕНЬ НА ОСНОВІ КУСКОВО-ЛІНІЙНОЇ АПРОКСИМАЦІЇ ТА РІЗНИХ СТРАТЕГІЙ ОБХОДУ МАТРИЦІ - Scientific conference

Congratulation from Internet Conference!

Hello

Рік заснування видання - 2011

ПОРІВНЯЛЬНИЙ АНАЛІЗ АЛГОРИТМІВ СТИСНЕННЯ ЗОБРАЖЕНЬ НА ОСНОВІ КУСКОВО-ЛІНІЙНОЇ АПРОКСИМАЦІЇ ТА РІЗНИХ СТРАТЕГІЙ ОБХОДУ МАТРИЦІ

07.12.2023 23:53

[1. Information systems and technologies]

Author: Сточанський Мар’ян Андрійович, студент, Національний університет «Львівська політехніка»



Вступ. Одним зі способів стиснення зображення є стиснення на основі кусково-лінійної апроксимації. Серед алгоритмів кусково-лінійної апроксимації розглядаються алгоритми Рамера-Дугласа-Пакера, Реуманна-Віткама, Вісвалінгама-Уайатта.

Стиснення, засноване на методі кусково-лінійної апроксимації, представляє спрощений підхід до стиснення зображень. Цей метод виявляє значну гнучкість, пропонуючи широкий спектр існуючих алгоритмів кусково-лінійної апроксимації [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 Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
допомога Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter
Сonferences

Conference 2024

Conference 2023

Conference 2022

Conference 2021



Міжнародна інтернет-конференція з економіки, інформаційних систем і технологій, психології та педагогіки

Наукова спільнота - інтернет конференції

:: LEX-LINE :: Юридична лінія

Інформаційне суспільство: технологічні, економічні та технічні аспекти становлення