Практична реалізація алгоритму фрактального стиснення зображень, що є ефективним за часом
Наведений опис програмної реалізації алгоритму фрактального стиснення
 зображень за допомогою просторово-чутливого хешування. Дані комплексні критерії якості алгоритмів стиснення і відновлення растрових зображень; проведено
 практичне порівняння з іншими сучасними алгоритмами стиснен...
Saved in:
| Published in: | Моделювання та інформаційні технології |
|---|---|
| Date: | 2009 |
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2009
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/29649 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Практична реалізація алгоритму фрактального стиснення зображень, що є ефективним за часом / І.В. Хімченко // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 53. — Бібліогр.: 7 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860240831538003968 |
|---|---|
| author | Хіміченко, І.В. |
| author_facet | Хіміченко, І.В. |
| citation_txt | Практична реалізація алгоритму фрактального стиснення зображень, що є ефективним за часом / І.В. Хімченко // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 53. — Бібліогр.: 7 назв. — укр. |
| collection | DSpace DC |
| container_title | Моделювання та інформаційні технології |
| description | Наведений опис програмної реалізації алгоритму фрактального стиснення
зображень за допомогою просторово-чутливого хешування. Дані комплексні критерії якості алгоритмів стиснення і відновлення растрових зображень; проведено
практичне порівняння з іншими сучасними алгоритмами стиснення зображень на
основі комплексного критерію якості.
|
| first_indexed | 2025-12-07T18:29:39Z |
| format | Article |
| fulltext |
УДК 537.8
І. В. Хіміченко, аспірант Міжнародного науково-навчального центру
інформаційних технологій та систем НАН України і МОН України
ПРАКТИЧНА РЕАЛІЗАЦІЯ АЛГОРИТМУ ФРАКТАЛЬНОГО
СТИСНЕННЯ ЗОБРАЖЕНЬ, ЩО Є ЕФЕКТИВНИМ ЗА ЧАСОМ
Наведений опис програмної реалізації алгоритму фрактального стиснення
зображень за допомогою просторово-чутливого хешування. Дані комплексні критерії
якості алгоритмів стиснення і відновлення растрових зображень; проведено
практичне порівняння з іншими сучасними алгоритмами стиснення зображень на
основі комплексного критерію якості.
Вступ. Результати теоретичного аналізу часової ефективності
фрактального стиснення дозволяють говорити про доцільність застосування
методу для вирішення задач фрактального стиснення зображень.
Мета. Метою статті є практична реалізація алгоритму фрактального
стиснення статичних растрових зображень, що є ефективним за часом на
основі його порівнянь з іншими сучасними алгоритмами стиснення
зображень.
Ідея. Програмна реалізація алгоритму фрактального стиснення
складається з двох основних етапів: на етапі попередніх обчислень для всіх
векторів, що представляють доменні блоки, обчислюється їх ортонормована
проекція ( )k kD D на ортодоповнення . Визначення оператора ( )
було дано в розділі 2.1. Далі, для отриманих точок \n
kD R
обчислюються і зберігаються значення хеш-функцій ( )i kg D за формулою
(3.3.1).
Етап попередніх обчислень
На етапі попередніх обчислень для кожного доменного блоку jD з
доменного пулу 1... dnD обчислюється значення оператора ( )kD , після чого
обчислюються і зберігаються L значень просторово-чутливих хеш-функцій
від вектора ( )kD .
Алгоритм А: етап попередніх обчислень.
ВХІД: Доменний пул 1... dnD , кількість хеш-таблиц L .
ВИХІД: Хеш-таблиці iT , 1,...,i L .
ДЛЯ КОЖНОГО 1,...,i L
Ініціалізувати хеш-таблицю iT шляхом генерації випадкової хеш-функції
( )ig
ДЛЯ КОЖНОГО 1,...,i L
ДЛЯ КОЖНОГО 1,..., dj n
Зберегти точку jD , в наборі ( )i jg D хеш-таблиці iT .
Результатом етапу попередніх обчислень є заповнення L -множин,
кожна з яких містить обчислені значення просторово-чутливої хеш-функції
для доменних блоків з доменного пулу. Надалі ця інформація
використовується для швидкого зіставлення рангових і доменних блоків.
Завдяки властивостям просторово-чутливих хеш-функцій, значення хеш-
функції для схожих рангового і доменного блоку з великою вірогідністю
збігатимуться. А використання L різних хеш-функцій додатково збільшують
цю вірогідність.
Реалізація проектуючого оператора
Розглянемо реалізацію проектуючого оператора ( ) . Нагадаємо, що в
розділі 2.1 оператор ( ) визначений таким чином: передбачимо, що
ранговий блок mR має унікальне розкладання m m mR OR PR , де P -
ортогональний проекційний оператор, який проектує n в підпростір з
базисом, що складається з фіксованих базисних блоків 1 2, ,..., nB B B , а
оператор O I P проектує свій операнд на ортодоповнення . Тоді для
1( ,..., ) \n
nZ z z визначимо оператор:
( ) OZZ
OZ
.
Математичний сенс даного оператора полягає в наступному: спочатку
ранговий блок mR розглядається як вектор в лінійному векторному просторі
n з базисом, що складається з одиничних взаємно ортогональних векторів.
Для 16 початковий базис задається матрицею:
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1
E
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Оператор ( )mR проектує вектор mR в підпростір , що має базис E ,
що складається з векторів, ортогональних до всіх фіксованих базисних блоків
1 2, ,..., nB B B і потім нормалізує результат. У FracLSH використовується
тільки один фіксований базисний блок (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)1 . Тому в
якості базиса 'E було вибрано наступну множину векторів:
'
-1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 3 0 0 0 0 0 0 0 0 0 0 0 0
1 1
- -
- - -
- -
E
1 1 4 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 5 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 6 0 0 0 0 0 0 0 0 0
- -
- - - - -
- - - - - -
-1 1 1 1 1 1 1 7 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 8 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 9 0 0 0 0 0
- - - - - -
- - - - - - - -
- - - - - - - - - 0
1 1 1 1 1 1 1 1 1 1 10 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 11 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 12
- - - - - - - - - -
- - - - - - - - - - -
- - - - - - - - - - - - 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 13 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 14 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 15
- - - - - - - - - - - - -
- - - - - - - - - - - - - -
- - - - - - - - - - - - - - -
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Для зручності базис 'E наведений в своєму ненормалізованому варіанті.
Нормалізація 'E виконується автоматично під час ініціалізації програмного
забезпечення алгоритму.
Таким чином, оператор O I P проектує свій операнд на лінійний
векторний простір, заданий векторами ' '
0 14...E E . Для обчислення ( )mR нам
досить перейти від представлення вектора mR в базисі E , до представлення
mR в базисі 'E , відкинути останню координату вектора, що представляє
проекцію mR на фіксований базисний блок, і нормувати результат.
Як відомо з курсу лінійної алгебри, матриця переходу від базису E до
'E має вигляд TA E . Нижче наведений псевдокод алгоритму, що виконує
обчислення оператора ( )mR .
Алгоритм B: Обчислення проектуючого оператора.
void convert_range_basis()
BYTE *pSrcVec, double *pDstVec, size_t size;
{
size_t i,j;
for (i=0; i<size; і++)
{
pDstVec[i]=0;
for(j=0; j<size;j++)
{
if (TransitionMatrix[i][j]==0)
break;
pDstVec[i]+=
(double)pSrcVec[j]* TransitionMatrix[i][j]; }
}
pDstVec[size-l]= 0.;
normalize_vector(pDstVec, pDstVec, size-1);
}
Тут pSrcVec – початковий ранговий блок mR , pDstVec - його
нормалізована проекція ( )mR , TransitionMatrix - матриця переходу від
базису E до 'E , а функція normalize_vector() виконує нормалізацію вхідного
вектора.
Обчислення оператора ( )kD для заданого доменного блоку kD
виконується аналогічним чином. Тепер у нас є всі необхідні інструменти для
обчислення проектуючого оператора і створення допоміжної структури
даних хеш-таблиць, і можна приступати до пошуку доменно-рангових
відповідностей.
Етап пошуку доменно-рангових відповідностей
На етапі пошуку доменно-рангових відповідностей для даного рангового
блоку обчислюється ортонормована проекція ( )m mR R на ортодоповнення
. Обчислюється значення хеш-функцій ( )i mg R , і проводиться лінійний
пошук в таблицях хеш-функцій доменних блоків, обчислених раніше.
Алгоритм С: пошук доменно-рангових співвідношень.
ВХІД: Ранговий блок mR , M (максимальне число доменних блоків-
кандидатів, які повинен повернути алгоритм).
ВИХІД: M (або менше) доменних блоків-кандидатів.
ДЛЯ КОЖНОГО 1,...,i L
{точки, знайдені в множині ( )i mg R хеш-таблиці iT }
Повернути M найближчих сусідніх елементів з множини
(знаходяться лінійним пошуком серед всіх кандидатів).
Завдяки властивостям просторово-чутливих хеш-функцій, при збігу
хеш-значень для рангового і доменного вектора, існує дуже висока
вірогідність того, що дані вектори лежать близько один до одного в заданому
(у нашому випадку в Евклідовому) метричному просторі. Для M знайдених
доменних блоків-кандидатів проводиться обчислення помилки ,l mE D R ,
1,...,l M за формулою (1.3.3) і вибирається найбільш відповідний блок.
Таким чином, ми уникаємо необхідності вирішувати задачу для кожної пари
доменно-рангових блоків, а відбираємо лише декілька кандидатів, які з
великою вірогідністю дадуть вирішення, близьке до оптимального. Цим і
досягається істотне підвищення часової ефективності пропонованого
алгоритму.
Оцінка часової ефективності алгоритму
Оцінка часової ефективності фрактального стиснення з використанням
просторово-чутливого хешування ґрунтується на існуючих оцінках
алгоритму пошуку найближчого сусіднього елементу в багатовимірному
метричному просторі. Час обробки одного запиту на пошук відповідного
доменного блоку для даного рангового блоку визначається кількістю
операцій обчислення функції відстані ,m kR D між проекціями рангового і
доменного блоків, і кількістю операцій обчислення хеш-функції ( )i kg D .
Загальна кількість запитів дорівнює кількості рангових блоків. Відомо, що
при відповідному виборі параметрів алгоритму LSH для одного запиту
кількість операцій обчислення функції відстані визначається як ( )dO n , а
кількість операцій обчислення хеш-функції, відповідно, як
21/( log )d p dO n n , де
dn – загальна кількість доменних блоків, 1
2
ln(1/ )
ln(1/ )
p
p
для 1 2 1 2( , , , )r r p p –
чутливої хеш-функції, 1p визначена як вірогідність того, що відстань між
двома точками в заданому метричному просторі не більша за 1r за умови, що
хеш-функція дає колізію, 2p – це вірогідність того, що відстань між двома
точками більша за 2r за умови, що колізії не відбувається. Алгоритм LSH
для побудови проміжних структур даних вимагає 1( )d dO dn n слів пам’яті,
де d – це розмірність ортонормованої проекції jD доменного блоку на
ортодоповнення .
Таким чином, досягається сублінійний час обробки одного рангового
блоку, що є великим кроком вперед в порівнянні з класичними алгоритмами
фрактального стиснення.
Висновок. У даній статті розглянута програмна реалізація алгоритму
фрактального стиснення зображень за допомогою просторово-чутливого
хешування. Результати показують, що на основі запропонованого методу
можлива побудова високоефективного алгоритму фрактального стиснення
зображень, який працює в декілька сотень разів швидше за оригінальний
алгоритм Джеквіна, і, за певних умов, перевершує існуючі алгоритми
фрактального стиснення по співвідношенню час роботи/якість» вихідного
зображення.
1. Monro D.M., Dudbridge F. Fractal approximation of image blocks, in: Proceedings of
ICASSP-1992 IEEE International Conference on Acoustics, Speech and Signal
Processing, Vol. 3, pp. 485-488, 1992.
2. Motwani R., Naor A., Panigrahy R. Lower bounds on Locality Sensitive Hashing.
Proceedings of the Symposium on Foundations of Computer Science, 2005.
3. Friedman J.H., Bentley J.L., Finkel R.A. An algorithm for finding best matches in
logarithmic expected time, ACM Trans. Math. Software 3,3 (1977) 209-226.
4. Frigaard C., Gade J., Hemmingsen Т., Sand Т., Image compression based on fractal
theory, Institute for Electronic Systems, Aalborg University, Denmark, 1994.
5. Forte В., Vrscay E.R. Solving the inverse problem for function/image approximations
using iterated function systems, 1. Theoretical basis, Fractals 2,3 (1994) 325-334.
6. Хіміченко І.В. Підхід до фрактального стиснення зображень з використанням
просторово-чутливого хешування як метода підвищення часової ефективності при
фрактальному стисненні / САИТ, XI международная научно-техническая
конференция УНК ИПСА НТУУ «КПИ», 2009
7. Хіміченко І.В. Роль пошуку найближчого сусіднього елементу при фрактальному
стисненні зображень / ИАИ, IX международная научная конференция, НТУУ
«КПИ», 2009
|
| id | nasplib_isofts_kiev_ua-123456789-29649 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0068 |
| language | Ukrainian |
| last_indexed | 2025-12-07T18:29:39Z |
| publishDate | 2009 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Хіміченко, І.В. 2011-12-25T16:43:13Z 2011-12-25T16:43:13Z 2009 Практична реалізація алгоритму фрактального стиснення зображень, що є ефективним за часом / І.В. Хімченко // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 53. — Бібліогр.: 7 назв. — укр. XXXX-0068 https://nasplib.isofts.kiev.ua/handle/123456789/29649 537.8 Наведений опис програмної реалізації алгоритму фрактального стиснення
 зображень за допомогою просторово-чутливого хешування. Дані комплексні критерії якості алгоритмів стиснення і відновлення растрових зображень; проведено
 практичне порівняння з іншими сучасними алгоритмами стиснення зображень на
 основі комплексного критерію якості. uk Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Моделювання та інформаційні технології Практична реалізація алгоритму фрактального стиснення зображень, що є ефективним за часом Article published earlier |
| spellingShingle | Практична реалізація алгоритму фрактального стиснення зображень, що є ефективним за часом Хіміченко, І.В. |
| title | Практична реалізація алгоритму фрактального стиснення зображень, що є ефективним за часом |
| title_full | Практична реалізація алгоритму фрактального стиснення зображень, що є ефективним за часом |
| title_fullStr | Практична реалізація алгоритму фрактального стиснення зображень, що є ефективним за часом |
| title_full_unstemmed | Практична реалізація алгоритму фрактального стиснення зображень, що є ефективним за часом |
| title_short | Практична реалізація алгоритму фрактального стиснення зображень, що є ефективним за часом |
| title_sort | практична реалізація алгоритму фрактального стиснення зображень, що є ефективним за часом |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/29649 |
| work_keys_str_mv | AT hímíčenkoív praktičnarealízacíâalgoritmufraktalʹnogostisnennâzobraženʹŝoêefektivnimzačasom |