Дискретні фрактальні ступінчасті мультивейвлети і мультивейвлет-пакети – нова мультивейвлет-технологія для оброблення та кодування зображень
The construction method and algorithms of twodimension discrete fractal step multiwavelets and multiwavelet packets, discrete multiwavelet-transforms with multiwavelet packets of given sizes for different levels of the schedule without performing convolution and sample thinning operations, unlike th...
Saved in:
| Date: | 2023 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Subjects: | |
| Online Access: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/275 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Physico-mathematical modeling and informational technologies |
| Download file: |  |
Institution
Physico-mathematical modeling and informational technologies| _version_ | 1867479643499528192 |
|---|---|
| author | Hnativ, Lev |
| author_facet | Hnativ, Lev |
| author_institution_txt_mv | [
{
"author": "Lev Hnativ",
"institution": "к. т. н., пров. н. с., інститут кібернетики НАН України, пр. Глушкова, 40"
}
] |
| author_sort | Hnativ, Lev |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:32:19Z |
| description | The construction method and algorithms of twodimension discrete fractal step multiwavelets and multiwavelet packets, discrete multiwavelet-transforms with multiwavelet packets of given sizes for different levels of the schedule without performing convolution and sample thinning operations, unlike the classical method, have been developed. Algorithms of 2D fast multiwavelet transforms (FMWT) with multiwavelet packets of given sizes for various levels of the low computational complexity decomposition have been developed. The method and algorithms of image coding based on 2D FMWT as a new multiwavelet technology are proposed. A method of image coding based on a three-level 2D FMWT is proposed, which, compared to the well-known classic Malla algorithm, has 78.8 times less multiplicative complexity and requires 22.5 times less additions. |
| first_indexed | 2026-06-09T01:09:32Z |
| format | Article |
| fulltext |
53
doi.org/10.15407/fmmit2023.36.053
Дискретні фрактальні ступінчасті мультивейвлети
і мультивейвлет-пакети – нова мультивейвлет-технологія
для оброблення та кодування зображень
Лев Гнатів
к. т. н., пров. н. с., інститут кібернетики НАН України, пр. Глушкова, 40, e-mail: levhnativ@gmail.com
Розроблено метод побудови і алгоритми двовимірних (2D) дискретних фрактальних
ступінчастих мультивейвлетів і мультивейвлет-пакетів, дискретних мультивейвлет-
перетворень з мультивейвлет-пакетами заданих розмірів для різних рівнів розкладу без
виконання операцій згортки і прорідження вибірки на відміну від класичного методу.
Розроблено алгоритми 2D швидких мультивейвлет-перетворень (ШМВП) з
мультивейвлет-пакетами заданих розмірів для різних рівнів розкладу низької
обчислювальної складності. Запропоновано методи і алгоритми оброблення та кодування
зображень на основі 2D ШМВП як нова мультивейвлет-технологія. Запропоновано метод
кодування зображень на основі трьохрівневого 2D ШМВП, який порівняно з відомим
класичним алгоритмом Малла має в 78,8 раз меншу мультиплікативну складність і
потребує у 22,5 рази менше додавань.
Ключові слова: фрактальні ступінчасті мультивейвлети; вейвлет-пакети;
мультивейвлет-пакети; мультивейвлет-перетворення; дискретне мульти-
вейвлет-перетворення; швидкі алгоритми; швидке мультивейвлет-
перетворення; мультиплікативна складність; мультивейвлет-технологія.
Вступ. В [1] були визначені мультивейвлети і мультивейвлет-пакети та
побудовані ортогональні і біортогональні мультивейвлети. Показано, що
мультивейвлети при кодуванні зображень кращі за відомі скалярні вейвлети.
Вейвлет-пакети дозволяють краще ніж вейвлети представляти зміст
високочастотних сигналів, і тим самим покращують результати стиснення для
зображень з великою кількістю текстури, хоча й збільшують обчислювальну
складність. У [2,3] описано новий клас фрактальних ступінчастих
мультивейвлетів і мультивейвлет-пакетів і на їх основі розроблено метод і
алгоритм швидкого мультивейвлет-перетворення низької обчислювальної
складності, яка порівняно з відомим класичним алгоритмом Малла [4] за
мультиплікативною складністю менша в 70 раз, а за адитивною складністю - в 20
раз, що представляє нову мультивейвлет-технологію для оброблення сигналів і
зображень.
1. Дискретне мультивейвлет-перетворення
Для функції f t , яка представлена послідовністю чисел, дискретне мульти-
вейвлет-перетворення (ДМВП) визначається парою ДМВП перетворень [3]
УДК 519.6, 004.932
Лев Гнатів
Дискретні фрактальні ступінчасті мультивейвлети і мультивейвлет-пакети …
54
1
0 0
1
0 0 0,
01
1
, ,
N
j i
t
W j i f t t j j
N
, (1)
1 1
, 1
01
1
, , 1, 1k
i
N
k
j i
t
W j i f t t i N
N
, (2)
де 1N - число мультивейвлет-функцій рангу k, які представляють мультивейвлет-
пакет розміру 1 1N N , 1 2 , 2pN p ,
,
k
j i t - i-та функція фрактального
ступінчастого мультивейвлета рангу k [2], 0,1,... 2k p для j-го рівня розкладу,
0,1,2,...j m ;
0 0,j i t – масштабна функція Хаара 0 0j та 0 0i , 0,0 1t .
При цьому додавання проводиться для значень t, i та j. Для функцій
1, 0,2 ,n n
f x x m
p
.
2.1.2. Швидке мультивейвлет-перетворення
В [3] запропоновано швидке мультивейвлет-перетворення (ШМВП), яке
представляє собою ефективний метод реалізації обчислення ДМВП, який
використовує взаємозв’язок між коефіцієнтами ДМВП сусідніх рівнів розкладу.
Коефіцієнти наближення 01,W j i і коефіцієнти деталей 1,kW j i
рівня
1j можуть бути обчислені через коефіцієнти наближення 0,W j i рівня j.
Теорема [3]
001, ,i
n
W j i n W j n , 10,1,... 1n N , (3)
1, ,k
i
k
i
n
W j i n W j n
, 11,... 1i N , 0,1,... 2k p . (4)
Вирази (3), (4) представляють алгоритм швидкого мультивейвлет-
перетворення, який може бути обчислений з допомогою тільки операцій
скалярного добутку без операцій згортки (еквівалентно фільтрації) і
проріджуваної виборки з фактором 2, що потребує відомий алгоритм Малла
швидкого вейвлет-перетворення (ШВП) [4,5]. У роботі [2] запропоновано
рекурентний матричний метод побудови мультивейвлет-пакета розміру 1 1N N ,
на основі якого, отримано факторизоване представлення матриці мультивейвлет-
пакета як добуток 2 12log 1N матриць. Це дозволяє будувати швидкий
алгоритм (ША) обчислення ДМВП. Розроблено ША обчислення ДМВП з
мультивейлет-пакетом розміру 1 1N N , який потребує операцій множення
1 13 /2 4NM N і додавання
1 117 /4 6NA N для функцій з лінійними змінами
та
1 119 /4 6NA N – з нелінійними змінами, тобто має лінійну обчислювальну
складність.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип.36 , 53-57
55
Запропонований в [2] алгоритм ШМВП порівняно з відомим класичним
алгоритмом Малла [4] для фільтрів з 8-ми ненульовими коефіцієнтами має в 512
log2 N/73 раз менше мультиплікативну складність, що для N=2
10
становить 70 раз
і потребує в 1024 log2 N/511 раз менше додавань, що становить 20 раз.
3.2. Двовимірне дискретне мультивейвлет-перетворення
Визначимо ДМВП функції ,f x y розмірів M N наступним чином:
0
1 1
0
0 0
1
, , , ,
M N
j
x y
W j m n f x y x y
MN
, (5)
1 1
, , , 1
0 0
1
, , , , , , , , 1, 1
i
M N
i i
i j m n
x y
W j m n f x y x y i H V D i N
MN
(6)
Як в одновимірному випадку, 0j - початковий рівень розкладу, і коефіцієнти
0, ,W j m n
визначають наближення функції ,f x y при рівні
0
j . Коефіцієнти
, ,
i
iW j m n
визначають горизонтальні, вертикальні і діагональні деталі для рівнів
0
j j . Звичайно вважаємо
0
j =1 і вибираємо числа N і M так, щоб вони були
степенем двійки. 2JN M
, 2J , , 0,1,2,...2 1jm n
. При цьому,
0,1, 2, ...J r , /r j p ,
1
2 , 2
p
N p .
Вхідна функція ,f x y може бути відновлена за заданими коефіцієнтами W і
i
iW
в (5) і (6) з допомогою оберненого ДМВП:
00 , ,
1
, , , ,j m n
m n
f x y W j m n x y
MN
1 1
, , ,
, , 1 1
1
, , ,
i
N r
i
i j m n
i H V D i j m n
W j m n x y
MN
. -57 (7)
Як і одновимірне ДМВП, двовимірне ДМВП може бути реалізовано із
допомогою тільки операцій скалярного добутку без операцій згортки
(еквівалентно фільтрації) і проріджуваної виборки з фактором 2, що потребує
відомий класичний метод Малла двовимірного швидкого вейвлет-перетворення
[4,5]. Оскільки використовувані масштабна і мультивейвлет-функції є
роздільними, то спочатку обчислюється одновимірне ШМВП по рядкам від
функції ( , )f x y , а потім обчислюється одновимірне ШМВП по стовпцям від
отриманого результату. Зауважимо, що як у випадку свого одновимірного
аналога для отримання коефіцієнтів наближення і деталей для рівня розкладу
1j двовимірне ШМВП оперує з коефіцієнтами наближення рівня розкладу j .
У двовимірному випадку, однак, ми маємо діло з трьома наборами коефіцієнтів
деталей – горизонтальним, вертикальним і діагональним.
Однорівневий блок мультивейвлет-пакетів може застосовуватись
повторно (для чого коефіцієнти наближення на виході цього блока
Лев Гнатів
Дискретні фрактальні ступінчасті мультивейвлети і мультивейвлет-пакети …
56
мультивейвлетів потрібно подати на вхід такого ж наступного блоку
мультивейвлетів), результатом чого буде p -рівневе перетворення
1, 2, ...,j j j j p . Як і в одновимірному випадку, зображення ( , )f x y
використовується в якості коефіцієнтів ( , , )W j m n
на вході. Множенням n
стовпців зображення на послідовності ( )n і ( )k n , 1,2,3k , ми отримаємо
чотири частини зображення із зменшенням вчетверо роздільної здатності по
вертикалі. Високочастотні або детальні частини характеризують високочастотні
у вертикальному напрямі складові зображення. Низькочастотна частина або
наближення містить інформацію про низькі у вертикальному напрямі частоти.
До чотирьох частин зображення далі застосовується аналогічна процедура по m
рядкам. Це дає на виході шістнадцять зображень (16 частин вихідного
зображення), які можуть бути представлені чотирма групами зображень, по
одному, по три і по шість зображень в групі: W
,
1 2 3
, ,H H HW W W
,
1 2 3
, ,V V VW W W
,
1,2 1,3 2 ,1 2 ,3 3,1 3,2
, , , , ,VH VH VH VH VH VHW W W W W W
і
1 2 3
, ,D D DW W W
.
На рис. 1. показані зображення, які представляють собою результат
скалярного добутку зображення ( , )f x y і двовимірної масштабуючої функції і
мультивейвлет-функцій для одного рівня розкладу.
Рис.1. Двовимірне ШМВП для одного рівня розкладу.
В роботі запропоновано мультивейвлет-метод кодування зображень на
основі трьохрівневого двовимірного ШМВП з мультивейвлет-пакетом розміру
8х8. Як показано в [5], при збільшенні числа рівнів розкладу більше трьох, мало
змінюється число коефіцієнтів, що обнуляються. Запропонований метод
кодування зображень на основі трьохрівневого 8-точкового двовимірного
ШМВП порівняно з відомим класичним алгоритмом Малла [4] ШВП для
фільтрів з 8-ми ненульовими коефіцієнтами має в 7,88 log2 N раз меншу
мультиплікативну складність, що для N=2
10
становить 78,8 раз і потребує в
2,25log2 N раз менше додавань, що у 22,5 рази менше для функцій з лінійними
змінами.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип.36 , 53-57
57
Висновки. Розроблено метод побудови і алгоритми двовимірних (2D)
дискретних фрактальних ступінчастих мультивейвлетів і мультивейвлет-пакетів,
2D дискретних мультивейвлет-перетворень з мультивейвлет-пакетами заданих
розмірів для різних рівнів розкладу без виконання операцій згортки і
прорідження вибірки на відміну від класичного методу Малла. Розроблено
алгоритми 2D швидких мультивейвлет-перетворень на основі швидких
алгоритмів обчислення дискретних мультивейвлет-перетворень з мультивейвлет-
пакетами заданих розмірів лінійної обчислювальної складності для різних рівнів
розкладу низької обчислювальної складності для більш точнішого і більш
швидкого аналізу та кодування зображень. Запропоновано метод і алгоритми
кодування зображень на основі 2D ШМВП як нова мультивейвлет-технологія для
кодування зображень, яка на основі трьохрівневого 8-точкового 2D ШМВП,
порівняно з класичним алгоритмом Малла 2D ШВП для фільтрів з 8-ми
ненульовими коефіцієнтами має в 78,8 раз меншу мультиплікативну складність і
у 22,5 рази меншу адитивну складність.
Література
[1] Martin M.B., Bell A.E. New image compression techniques using multiwavelets and multiwavelet
packets. IEEE Trans Image Process. 2001, vol.10, №4. Р. 500-510.
[2] Гнатів Л.О. Фрактальні ступінчасті мультивейвлети – нова вейвлет-технологія для
оброблення сигналів та кодування зображень. Тези доп. Міжнар. наук. конф. “Сучасна
інформатика: проблеми, досягнення та …”, Україна, Київ, 13-15 грудня 2017. С. 195-197.
[3] Гнатів Л.О. Ортонормовані базиси фрактальних ступінчастих мультивейвлетів – нова
мультивейвлет-технологія для оброблення сигналів і зображень. Фізико-математичне
моделювання та інформаційні технології. 2021. № 32. С. 91-95.
https://doi.org/10.15407/fmmit2021.32.091.
[4] Малла C. Вейвлеты в обработке сигналов. Москва: Мир. 2005. 671 с.
[5] Гонсалес Д., Вудс Р. Цифровая обработка изображений. Москва: Техносфера. 2005. 1072 с.
Discrete fractal step multiwavelets and multiwavelet packets – a
new multiwavelet technology for image processing and coding
Lev Hnativ
The construction method and algorithms of twodimension discrete fractal step multiwavelets and
multiwavelet packets, discrete multiwavelet-transforms with multiwavelet packets of given sizes for
different levels of the schedule without performing convolution and sample thinning operations,
unlike the classical method, have been developed. Algorithms of 2D fast multiwavelet transforms
(FMWT) with multiwavelet packets of given sizes for various levels of the low computational
complexity decomposition have been developed. The method and algorithms of image coding
based on 2D FMWT as a new multiwavelet technology are proposed. A method of image coding
based on a three-level 2D FMWT is proposed, which, compared to the well-known classic Malla
algorithm, has 78.8 times less multiplicative complexity and requires 22.5 times less additions.
Отримано 15.03.23
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-275 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:09:32Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/8c/25898c4ba83eec075b6449a985be4b8c.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-2752025-02-21T17:32:19Z Discrete fractal step multiwavelets and multiwavelet packets – a new multiwavelet technology for image processing and coding Дискретні фрактальні ступінчасті мультивейвлети і мультивейвлет-пакети – нова мультивейвлет-технологія для оброблення та кодування зображень Hnativ, Lev фрактальні ступінчасті мультивейвлети; вейвлет-пакети; мультивейвлет-пакети; мультивейвлет-перетворення; дискретне мульти-вейвлет-перетворення; швидкі алгоритми; швидке мультивейвлет-перетворення; мультиплікативна складність; мультивейвлет-технологія The construction method and algorithms of twodimension discrete fractal step multiwavelets and multiwavelet packets, discrete multiwavelet-transforms with multiwavelet packets of given sizes for different levels of the schedule without performing convolution and sample thinning operations, unlike the classical method, have been developed. Algorithms of 2D fast multiwavelet transforms (FMWT) with multiwavelet packets of given sizes for various levels of the low computational complexity decomposition have been developed. The method and algorithms of image coding based on 2D FMWT as a new multiwavelet technology are proposed. A method of image coding based on a three-level 2D FMWT is proposed, which, compared to the well-known classic Malla algorithm, has 78.8 times less multiplicative complexity and requires 22.5 times less additions. Розроблено метод побудови і алгоритми двовимірних (2D) дискретних фрактальних ступінчастих мультивейвлетів і мультивейвлет-пакетів, дискретних мультивейвлет-перетворень з мультивейвлет-пакетами заданих розмірів для різних рівнів розкладу без виконання операцій згортки і прорідження вибірки на відміну від класичного методу. Розроблено алгоритми 2D швидких мультивейвлет-перетворень (ШМВП) з мультивейвлет-пакетами заданих розмірів для різних рівнів розкладу низької обчислювальної складності. Запропоновано метод і алгоритми кодування зображень на основі 2D ШМВП як нова мультивейвлет-технологія. Запропоновано метод кодування зображень на основі трьохрівневого 2D ШМВП, який порівняно з відомим класичним алгоритмом Малла має в 78,8 раз меншу мультиплікативну складність і потребує у 22,5 рази менше додавань. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-13 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/275 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 53-57 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 53-57 2617-5258 1816-1545 10.15407/fmmit2023.36 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/275/232 Авторське право (c) 2023 Лев Гнатів (Автор) |
| spellingShingle | фрактальні ступінчасті мультивейвлети вейвлет-пакети мультивейвлет-пакети мультивейвлет-перетворення дискретне мульти-вейвлет-перетворення швидкі алгоритми швидке мультивейвлет-перетворення мультиплікативна складність мультивейвлет-технологія Hnativ, Lev Дискретні фрактальні ступінчасті мультивейвлети і мультивейвлет-пакети – нова мультивейвлет-технологія для оброблення та кодування зображень |
| title | Дискретні фрактальні ступінчасті мультивейвлети і мультивейвлет-пакети – нова мультивейвлет-технологія для оброблення та кодування зображень |
| title_alt | Discrete fractal step multiwavelets and multiwavelet packets – a new multiwavelet technology for image processing and coding |
| title_full | Дискретні фрактальні ступінчасті мультивейвлети і мультивейвлет-пакети – нова мультивейвлет-технологія для оброблення та кодування зображень |
| title_fullStr | Дискретні фрактальні ступінчасті мультивейвлети і мультивейвлет-пакети – нова мультивейвлет-технологія для оброблення та кодування зображень |
| title_full_unstemmed | Дискретні фрактальні ступінчасті мультивейвлети і мультивейвлет-пакети – нова мультивейвлет-технологія для оброблення та кодування зображень |
| title_short | Дискретні фрактальні ступінчасті мультивейвлети і мультивейвлет-пакети – нова мультивейвлет-технологія для оброблення та кодування зображень |
| title_sort | дискретні фрактальні ступінчасті мультивейвлети і мультивейвлет-пакети – нова мультивейвлет-технологія для оброблення та кодування зображень |
| topic | фрактальні ступінчасті мультивейвлети вейвлет-пакети мультивейвлет-пакети мультивейвлет-перетворення дискретне мульти-вейвлет-перетворення швидкі алгоритми швидке мультивейвлет-перетворення мультиплікативна складність мультивейвлет-технологія |
| topic_facet | фрактальні ступінчасті мультивейвлети вейвлет-пакети мультивейвлет-пакети мультивейвлет-перетворення дискретне мульти-вейвлет-перетворення швидкі алгоритми швидке мультивейвлет-перетворення мультиплікативна складність мультивейвлет-технологія |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/275 |
| work_keys_str_mv | AT hnativlev discretefractalstepmultiwaveletsandmultiwaveletpacketsanewmultiwavelettechnologyforimageprocessingandcoding AT hnativlev diskretnífraktalʹnístupínčastímulʹtivejvletiímulʹtivejvletpaketinovamulʹtivejvlettehnologíâdlâobroblennâtakoduvannâzobraženʹ |