Про використання модифікованого дельта-алгоритму для обробки та кодування зображень
The paper considers the ideas of using a modified delta algorithm for calculating the differences between adjacent values for image coding as an algorithm for predicting pixel values and for image processing as an algorithm for obtaining image contours. Several modifications and variants of the impl...
Збережено в:
| Дата: | 2023 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Теми: | |
| Онлайн доступ: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/263 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
| Завантажити файл: |  |
Репозитарії
Physico-mathematical modeling and informational technologies| _version_ | 1867479632091021312 |
|---|---|
| author | Luts, Vasyl Luts, Yaroslav |
| author_facet | Luts, Vasyl Luts, Yaroslav |
| author_institution_txt_mv | [
{
"author": "Vasyl Luts",
"institution": "аспірант інституту кібернетики НАН України, пр. Глушкова,40, 03185, Київ"
},
{
"author": "Yaroslav Luts",
"institution": "аспірант інституту кібернетики НАН України, пр. Глушкова,40, 03185, Київ"
}
] |
| author_sort | Luts, Vasyl |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:32:19Z |
| description | The paper considers the ideas of using a modified delta algorithm for calculating the differences between adjacent values for image coding as an algorithm for predicting pixel values and for image processing as an algorithm for obtaining image contours. Several modifications and variants of the implementation of these ideas are proposed, which require further research and comparisons in order to determine the most optimal or adaptively optimal for certain conditions, primarily for the use of the delta algorithm when encoding images, since the basic, initial version has an increased dependence and sensitivity to accumulation of errors. Using the block version of the delta algorithm has less error accumulation, but requires more data to be stored. Also considered is a version of the delta algorithm, where the differences are calculated relative to the first value in the block, instead of the sequential difference calculation algorithm. Instead of using only vertical or horizontal differences, their simultaneous and coordinated application is proposed. |
| first_indexed | 2026-06-09T01:09:21Z |
| format | Article |
| fulltext |
148
doi.org/10.15407/fmmit2023.36.148
Про використання модифікованого дельта-алгоритму для
обробки та кодування зображень
Василь Луц1, Ярослав Луц2
1 аспірант інституту кібернетики НАН України, пр. Глушкова,40, 03185, Київ, e-mail: lv1@ukr,net
2 аспірант інституту кібернетики НАН України, пр. Глушкова,40, 03185, Київ,, e-mail: rorr-t@ukr.net
У роботі розглянуто декілька варіантів модифікації дельта-алгоритму обчислення різниць
між сусідніми значеннями для кодування зображень в якості алгоритму передбачення
значень пікселів та для обробки зображень в якості алгоритму отримання контурів
зображення. Запропоновано декілька модифікацій та варіантів реалізації даних ідей, які
потребують подальших досліджень та порівнянь з метою визначення найбільш оптимальних
чи адаптивно оптимальних для певних умов, в першу чергу для використання дельта-
алгоритму при кодуванні зображень, оскільки базова, початкова версія має підвищену
залежність та чутливість до накопичення похибок. Використання блочного варіанту
дельта-алгоритму має менше накопичення похибок, але потребує збереження більшої
кількості даних. Також розглянута версія дельта-алгоритму, де обчислюються різниці
відносно першого значення в блоці, замість алгоритму послідовного обчислення різниць.
Замість використання лише вертикальних або горизонтальних різниць запропоновано
одночасне та узгоджене їх застосування.
Ключові слова: дельта-алгоритм, алгоритм передбачення значень пікселів,
контури, LCEVC.
Вступ. Використання дельта-алгоритму, який полягає в обчисленні різниць між
сусідніми значеннями, з метою зменшення надлишковості даних, є добре і давно
відомим методом. Але використання дельта-алгоритму в якості алгоритму
передбачення значень пікселів перед етапом блочного кодування та стиснення
зображень не було досліджено. Аналогічно, застосувати дельта-алгоритм до
зображення з метою обчислення контурів також пропонується вперше.
Незважаючи на досить просту ідею, при реалізації виникають додаткові питання
та декілька різних варіантів і модифікацій, деякі з них розглянуто нижче. Кодек
LCEVC [1] використовує новий підхід – кодує зменшене зображення та різниці
між початковим зображенням та зменшеним. При цьому зменшене зображення
кодується і декодується за допомогою існуючих відомих кодеків, тобто даний
кодек є надбудовою над кодеками, що зроблено з метою уніфікації та сумісності з
кодеками попереднього покоління. Але різниці кодуються окремо, спрощено, з
меншими обчислювальними витратами (на підставі чого кодек і назвали кодеком
низької складності). Даний підхід паралельно, незалежно було запропоновано в
[2], але не з позиції адаптованого масштабування та сумісності з іншими
кодеками, а в якості універсального алгоритму передбачення значень пікселів
УДК 004.627, 004.932
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 148-152
149
(оскільки значення пікселя зменшеного зображення є середнім значенням блоку
пікселів більшого зображення, і може використовуватись як передбачення для
кожного з пікселів блоку), в якості спрощеної альтернативи множині відомих
специфічних алгоритмів передбачення. Відповідно, зараз в якості альтернативи
універсальному алгоритму передбачення значень пікселів на основі середнього
значення блоку пікселів пропонується використовувати дельта-алгоритм, тобто
передбаченням для значення кожного пікселя блоку виступає значення сусіднього
пікселя (в базовій версії), або значення першого пікселя блоку (в модифікованій
версії дельта-алгоритму). При цьому буде спостерігатись накопичення похибок, за
умови подальшого застосування блочних перетворень та відкидання частини
інформації (шляхом квантування коефіцієнтів перетворення та заокруглення),
оскільки кожна наступна ітерація дельта-алгоритму буде базуватись на значенні
попереднього пікселя, який обчислений з похибкою. Для зменшення цього ефекту
й запропонована модифікація, де віднімається значення першого пікселя блоку.
При цьому спостерігається збільшення абсолютних значень різниць та зменшення
коефіцієнта стиснення. Наскільки доцільно в такому випадку застосовувати цей
підхід, порівняно з відомим алгоритмом використання середнього значення блоку
пікселів в якості передбачення? Перевага застосування дельта-алгоритму полягає
в зменшенні кількості початкових даних – замість зменшеного зображення можна
взяти значення одного пікселя оригінального зображення. Але при цьому буде
значне накопичення похибок. Використання в якості початкових даних значення
першого пікселя блоку значно збільшує об’єм збережених даних, але зменшує
накопичення похибок. Відповідно, потрібно знайти компроміс, оптимальний
проміжний варіант між цими двома варіантами. Наприклад, в ієрархічному
використанні дельта-алгоритму (тобто застосуванні дельта-алгоритму другого
рівня до зменшеного зображення), або використанні одного значення не для
блоку, а для певної області зображення. Ще одна перевага дельта-алгоритму –
низька обчислювальна складність, що важливо в рамках концепції спрощеного
швидкодіючого кодека [3].
1. Застосування дельта-алгоритму для кодування зображень
Розглянемо більш детально особливості застосування дельта-алгоритму в якості
універсального алгоритму передбачення значень пікселів для кодування
зображень. Застосування дельта-алгоритму до сигналів є однозначним – адже
обчислюються різниці між сусідніми значеннями. Але у випадку зображення (2D
масиву даних) виникає питання – використовувати вертикальні різниці (по
стовпцям), чи горизонтальні (по рядкам), адже кожен варіант має недолік – гірше
передає зміни протилежного напрямку. У [4] було запропоновано обчислювати
різниці за кривою Гільберта (див. рис. 1), з метою нівелювати цей недолік. Іншим
варіантом є використання одночасно вертикальних та горизонтальних різниць у
шахматному порядку, тобто як по стовпцям, так і по рядкам (що еквівалентно
використанню двох менших зображень – одне з яких створено вертикальними
різницями, інше - горизонтальними). Потрібні подальші дослідження і тестування,
щоб визначити який варіант більш оптимальний.
Василь Луц, Ярослав Луц
Про використання модифікованого дельта-алгоритму для обробки та кодування зображень.
150
Модифікації дельта-алгоритму, як було описано вище, обчислюють різниці
між значенням зафіксованого пікселя та пікселями блоку чи області (множині
блоків). В останньому варіанті використовується значення фіксованого пікселя
для обчислення першого пікселя в блоці, а значення першого пікселя
використовується для обчислення значень всього блоку.
Рис. 1. Схема обходу пікселів зображення за кривою Гільберта
В результаті використання дельта-алгоритму спостерігаємо наступне
зменшення абсолютних значень пікселів (рис.2). Для відображення в якості
зображення різниці були взяті по модулю. Також була використана інверсія
значень, для кращого візуального сприйняття.
Рис. 2. Результат дельта-алгоритму (зліва) і віднімання середнього (справа)
Були обчислені різниці для блоку розміру 16х16, щоб краще проілюструвати
відмінності між двома алгоритмами. На блоках розміру 4х4 похибки помітно
менші, а на блоках 2х2 – ще менші. Запропонований алгоритм передбачення
значень пікселів з використанням модифікацій дельта-алгоритму може бути
інтегрованим з відомим алгоритмом універсального передбачення на основі
середнього значення блоку, тобто застосовуватись адаптивно, для тих блоків та
областей зображення, де є більш ефективним.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 148-152
151
2. Застосування дельта-алгоритму для виділення контурів зображень
Дельта-алгоритм був запропонований в якості інструменту отримання контурів в
роботі [5]. Він дає кращі результати для зображень з високою та середньою
кореляцією між пікселями, ніж для зображень з низькою кореляцією. З іншого
боку, аналогічні особливості властиві і іншим методам виявлення контурів
(наприклад, методу Канні).
Як було зазначено вище, вертикальні та горизонтальні різниці недостатньо
чітко передають зміни у протилежному напрямку, що нівелюється сумарним
використанням вертикальних та горизонтальних різниць (див. рис. 3 і 4).
Рис. 3. Вертикальні та горизонтальні різниці
Рис.4. Сумарні різниці
Зауважимо, що використання суми різниць також має недоліки, збільшуючи
фонові значення. В якості альтернативи розглядаються дві наступні модифікації:
напівсума вертикальних та горизонтальних різниць, та шахматний розподіл. В
якості додаткових інструментів обробки зображення можна використати
зменшення яскравості та обнуління значень пікселей менше порогових.
Перспективними напрямками досліджень є побудова ієрархії контурів за
критеріями масштабу, зв’язності та яскравості. Розподіл, множина контурів за
цими критеріями може дати більше інформації, ніж прості монохромні контури
одного масштабу.
Підкреслимо, що отримані дельта-алгоритмом контури є кольоровими, що
можна оцінювати як недолік так і як перевагу для більш детальних досліджень.
Василь Луц, Ярослав Луц
Про використання модифікованого дельта-алгоритму для обробки та кодування зображень.
152
Нескладно отримати монохромні контури для оцінки в першому наближенні,
маючи кольорові.
Висновки. У роботі розглянуто використання модифікацій дельта-алгоритму
обчислення різниць для кодування зображень в якості алгоритму передбачення
значень пікселів та для обробки зображень в якості алгоритму отримання контурів
зображення. Запропоновано декілька модифікацій та варіантів реалізації, які
потребують подальших досліджень та порівнянь з метою визначення найбільш
оптимальних чи адаптивно оптимальних для певних умов, в першу чергу для
використання дельта-алгоритму при кодуванні зображень, оскільки базова версія
має підвищену залежність та чутливість до накопичення похибок. Використання
блочного варіанту дельта-алгоритму має менше накопичення похибок, але
потребує збереження більшої кількості даних. Також розглянута версія дельта-
алгоритму, де обчислюються різниці відносно першого значення в блоці, замість
алгоритму послідовного обчислення різниць. Замість використання лише
вертикальних або горизонтальних різниць запропоновано їх застосування в
шахматному порядку або за кривою Гільберта.
Література
[1] https://www.lcevc.org/
[2] Я.В.Луц, Система захисту зображень для радіо мереж загального використання: Дипломний
проект на здобуття степені бакалавра. Київ: НТУУ «КПІ», 2019 р., 66 с.
https://ela.kpi.ua/bitstream/123456789/28670/1/Luts_bakalavr.pdf
[3] Я.В. Луц, В.К. Луц, Про розробку швидкодіючого спрощеного кодека зображень. Кібернетика
та комп’ютерні технології: Зб. наук. пр. 2021. № 1. С. 61-66.
[4] В.К. Луц, Комплексні підходи та моделі для кодування та обробки зображень. Міжн. наук.-
пр. конф. «Інформаційні технології та комп’ютерне моделювання», 15 – 16 грудня 2022 р.,
Ів.-Франківськ. С. 60-63.
[5] Я.В. Луц, Новий метод отримання контурів зображень. Міжн. наук.-пр. конф. «Інформаційні
технології та комп’ютерне моделювання», 15 – 16 грудня 2022 р., Ів.-Франківськ. С.57-60.
To use a modified delta algorithm for image processing and coding
Vasyl Luts, Yaroslav Luts
The paper considers the ideas of using a modified delta algorithm for calculating the differences
between adjacent values for image coding as an algorithm for predicting pixel values and for image
processing as an algorithm for obtaining image contours. Several modifications and variants of the
implementation of these ideas are proposed, which require further research and comparisons in
order to determine the most optimal or adaptively optimal for certain conditions, primarily for the
use of the delta algorithm when encoding images, since the basic, initial version has an increased
dependence and sensitivity to accumulation of errors. Using the block version of the delta algorithm
has less error accumulation, but requires more data to be stored. Also considered is a version of the
delta algorithm, where the differences are calculated relative to the first value in the block, instead
of the sequential difference calculation algorithm. Instead of using only vertical or horizontal
differences, their simultaneous and coordinated application is proposed.
Отримано 30.03.23
https://www.lcevc.org/
https://ela.kpi.ua/bitstream/123456789/28670/1/Luts_bakalavr.pdf
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-263 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:09:21Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/ff/bca0468c38adbfb32ab99d28ce8bf8ff.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-2632025-02-21T17:32:19Z To use a modified delta algorithm for image processing and coding Про використання модифікованого дельта-алгоритму для обробки та кодування зображень Luts, Vasyl Luts, Yaroslav дельта-алгоритм, алгоритм передбачення значень пікселів, контури, LCEVC. The paper considers the ideas of using a modified delta algorithm for calculating the differences between adjacent values for image coding as an algorithm for predicting pixel values and for image processing as an algorithm for obtaining image contours. Several modifications and variants of the implementation of these ideas are proposed, which require further research and comparisons in order to determine the most optimal or adaptively optimal for certain conditions, primarily for the use of the delta algorithm when encoding images, since the basic, initial version has an increased dependence and sensitivity to accumulation of errors. Using the block version of the delta algorithm has less error accumulation, but requires more data to be stored. Also considered is a version of the delta algorithm, where the differences are calculated relative to the first value in the block, instead of the sequential difference calculation algorithm. Instead of using only vertical or horizontal differences, their simultaneous and coordinated application is proposed. У роботі розглянуто декілька варіантів модифікації дельта-алгоритму обчислення різниць між сусідніми значеннями для кодування зображень в якості алгоритму передбачення значень пікселів та для обробки зображень в якості алгоритму отримання контурів зображення. Запропоновано декілька модифікацій та варіантів реалізації даних ідей, які потребують подальших досліджень та порівнянь з метою визначення найбільш оптимальних чи адаптивно оптимальних для певних умов, в першу чергу для використання дельта-алгоритму при кодуванні зображень, оскільки базова, початкова версія має підвищену залежність та чутливість до накопичення похибок. Використання блочного варіанту дельта-алгоритму має менше накопичення похибок, але потребує збереження більшої кількості даних. Також розглянута версія дельта-алгоритму, де обчислюються різниці відносно першого значення в блоці, замість алгоритму послідовного обчислення різниць. Замість використання лише вертикальних або горизонтальних різниць запропоновано одночасне та узгоджене їх застосування. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-12 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/263 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 148-152 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 148-152 2617-5258 1816-1545 10.15407/fmmit2023.36 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/263/237 Авторське право (c) 2023 Василь Луц, Ярослав Луц |
| spellingShingle | дельта-алгоритм алгоритм передбачення значень пікселів контури LCEVC. Luts, Vasyl Luts, Yaroslav Про використання модифікованого дельта-алгоритму для обробки та кодування зображень |
| title | Про використання модифікованого дельта-алгоритму для обробки та кодування зображень |
| title_alt | To use a modified delta algorithm for image processing and coding |
| title_full | Про використання модифікованого дельта-алгоритму для обробки та кодування зображень |
| title_fullStr | Про використання модифікованого дельта-алгоритму для обробки та кодування зображень |
| title_full_unstemmed | Про використання модифікованого дельта-алгоритму для обробки та кодування зображень |
| title_short | Про використання модифікованого дельта-алгоритму для обробки та кодування зображень |
| title_sort | про використання модифікованого дельта-алгоритму для обробки та кодування зображень |
| topic | дельта-алгоритм алгоритм передбачення значень пікселів контури LCEVC. |
| topic_facet | дельта-алгоритм алгоритм передбачення значень пікселів контури LCEVC. |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/263 |
| work_keys_str_mv | AT lutsvasyl touseamodifieddeltaalgorithmforimageprocessingandcoding AT lutsyaroslav touseamodifieddeltaalgorithmforimageprocessingandcoding AT lutsvasyl provikoristannâmodifíkovanogodelʹtaalgoritmudlâobrobkitakoduvannâzobraženʹ AT lutsyaroslav provikoristannâmodifíkovanogodelʹtaalgoritmudlâobrobkitakoduvannâzobraženʹ |