Метод підвищення часової ефективності при фрактальному стисненні зображень
У роботі P.Indyk і R.Motwani представлений метод вирішення задачі наближеного пошуку найближчого елементу, заснований на просторово чутливому хешуванні (метод LSH - locality sensitive hashing). Автори LSH пропонують використовувати просторове хешування для організації пошуку в додатках баз даних...
Saved in:
| Date: | 2010 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2010
|
| Series: | Моделювання та інформаційні технології |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/21796 |
| 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: | Метод підвищення часової ефективності при фрактальному стисненні зображень / І.В. Хіміченко // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2010. — Вип. 55. — С. 87-92. — Бібліогр.: 7 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-21796 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-217962025-02-09T23:00:02Z Метод підвищення часової ефективності при фрактальному стисненні зображень Хіміченко, І.В. У роботі P.Indyk і R.Motwani представлений метод вирішення задачі наближеного пошуку найближчого елементу, заснований на просторово чутливому хешуванні (метод LSH - locality sensitive hashing). Автори LSH пропонують використовувати просторове хешування для організації пошуку в додатках баз даних, розпізнаванні образів, пошуку в архівах документів. Пропонується також модифікувати метод просторово чутливого хешування для організації пошуку найближчого сусіднього елементу при фрактальному стисненні зображень. 2010 Article Метод підвищення часової ефективності при фрактальному стисненні зображень / І.В. Хіміченко // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2010. — Вип. 55. — С. 87-92. — Бібліогр.: 7 назв. — укр. XXXX-0068 https://nasplib.isofts.kiev.ua/handle/123456789/21796 004.81 uk Моделювання та інформаційні технології application/pdf Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
У роботі P.Indyk і R.Motwani представлений метод вирішення задачі
наближеного пошуку найближчого елементу, заснований на просторово
чутливому хешуванні (метод LSH - locality sensitive hashing). Автори LSH
пропонують використовувати просторове хешування для організації пошуку в
додатках баз даних, розпізнаванні образів, пошуку в архівах документів.
Пропонується також модифікувати метод просторово чутливого хешування для
організації пошуку найближчого сусіднього елементу при фрактальному
стисненні зображень. |
| format |
Article |
| author |
Хіміченко, І.В. |
| spellingShingle |
Хіміченко, І.В. Метод підвищення часової ефективності при фрактальному стисненні зображень Моделювання та інформаційні технології |
| author_facet |
Хіміченко, І.В. |
| author_sort |
Хіміченко, І.В. |
| title |
Метод підвищення часової ефективності при фрактальному стисненні зображень |
| title_short |
Метод підвищення часової ефективності при фрактальному стисненні зображень |
| title_full |
Метод підвищення часової ефективності при фрактальному стисненні зображень |
| title_fullStr |
Метод підвищення часової ефективності при фрактальному стисненні зображень |
| title_full_unstemmed |
Метод підвищення часової ефективності при фрактальному стисненні зображень |
| title_sort |
метод підвищення часової ефективності при фрактальному стисненні зображень |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| publishDate |
2010 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/21796 |
| citation_txt |
Метод підвищення часової ефективності при фрактальному стисненні зображень / І.В. Хіміченко // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2010. — Вип. 55. — С. 87-92. — Бібліогр.: 7 назв. — укр. |
| series |
Моделювання та інформаційні технології |
| work_keys_str_mv |
AT hímíčenkoív metodpídviŝennâčasovoíefektivnostíprifraktalʹnomustisnennízobraženʹ |
| first_indexed |
2025-12-01T14:28:53Z |
| last_indexed |
2025-12-01T14:28:53Z |
| _version_ |
1850316510736678912 |
| fulltext |
87 © І.В. Хіміченко
проектирования профилей, адаптивных угрозам за подклассами
автоматизированных систем АС-1, АС-2, АС-3, разрабатываемая методика
впервые будет предусматривать повышенное противодействие профилем
угрозам нарушения не только конфиденциальности К, целостности Ц и
доступности Д информации (подклассы К, Ц, Д), а также одновременно и
угроз К, Ц, Д за подклассами КЦ, КД, ЦД, КЦД.
Рис 2. Программный модуль для оценки профиля противодействия угрозам на основе
динамического программирования с использованием принципа оптимума Беллмана
1. Гурин Л.С., Дымарский Я.С., Меркулов А.Д. Задачи и методы оптимального
распределения ресурсов. - М.: Сов. радио, 1968. - 464 с.
Поступила 22.02.2010р.
УДК 004.81
І.В. Хіміченко, аспірант МННЦІТтаС, Київ
МЕТОД ПІДВИЩЕННЯ ЧАСОВОЇ ЕФЕКТИВНОСТІ ПРИ
ФРАКТАЛЬНОМУ СТИСНЕННІ ЗОБРАЖЕНЬ
У роботі P.Indyk і R.Motwani представлений метод вирішення задачі
наближеного пошуку найближчого елементу, заснований на просторово
чутливому хешуванні (метод LSH - locality sensitive hashing). Автори LSH
пропонують використовувати просторове хешування для організації пошуку в
додатках баз даних, розпізнаванні образів, пошуку в архівах документів.
88
Пропонується також модифікувати метод просторово чутливого хешування для
організації пошуку найближчого сусіднього елементу при фрактальному
стисненні зображень.
Мета
Метою статті є розгляд методу підвищення часової ефективності
фрактального стиснення зображень на основі використання просторово-
чутливого хешування.
Проблема
Однією з основних проблем при фрактальному стисненні зображень є
розробка ефективного за часом методу зіставлення доменно-рангових
областей.
Шляхи вирішення
На основі аналізу існуючих методів прискорення фрактального
стиснення зображень зробити висновок про те, що найбільш перспективним і
відповідним для подальшого поліпшення буде метод Саупа, який зведе
задачу фрактального стиснення до задачі пошуку найближчого сусіднього
елементу в багатовимірному метричному просторі за допомогою просторово-
чутливого хешування.
Ідея
Для множини точок S , що містить проекції доменних блоків
( )k kD Dφ⊥ = та рангових блоків ( )m mR Rφ⊥ = на \nℜ ℑ , з мірою відстані (у
нашому випадку Евкліда), сімейство LSH функцій визначене таким чином:
Множина хеш-функцій { }:H h S U= → називається 1 2 1 2( , , , )r r p p -
чутливими для ( , )d ⋅ ⋅ , якщо для будь-якої проекції рангового і доменного
блоку ,m kR D S⊥ ⊥ ∈ на \nℜ ℑ виконується
якщо 1( , )k mD B R r⊥ ⊥∈ , то 1Pr ( ) ( )H m kh R h D p⊥ ⊥⎡ ⎤= ≥⎣ ⎦ ,
якщо 2( , )k mD B R r⊥ ⊥∉ , то 2Pr ( ) ( )H m kh R h D p⊥ ⊥⎡ ⎤= ≤⎣ ⎦ .
де ( , )B x r - гіперсфера радіусом r в сенсі міри відстані ( , )d ⋅ ⋅ з центром
в точці x , а Pr ( ) ( )H m kh R h D⊥ ⊥⎡ ⎤=⎣ ⎦ - вірогідність того, що хеш-функція
утворює колізію для даних проекцій рангового і доменного блоку mR⊥ та kD⊥ .
Застосування просторово-чутливого хешування для вирішення
задачі фрактального стиснення зображень
Для того, щоб просторово-чутлива функція хешування була корисною з
погляду її застосування до фрактального стиснення зображень, вона повинна
задовольняти нерівностям 1 2p p> та 1 2r r< .
У спеціальній літературі прийнято позначати задачу наближеного
пошуку сусіднього елементу як ( ),c NNτ − задачу, при цьому 1r τ= та
89
2r c τ= ⋅ . Покажемо, як просторово-чутливі функції можуть бути використані
для вирішення ( ),c NNτ − задачі при фрактальному стисненні: для даного
сімейства H хеш-функцій, що володіють параметрами 1 2 1 2( , , , )r r p p ,
збільшимо розрив між «високою» вірогідністю 1p і «низькою» вірогідністю
2p шляхом з'єднання декількох функцій. Зокрема, для параметра K ,
значення якого буде встановлено нижче, визначимо сімейство функцій
{ }: Kg S UΨ = → таким чином, що ( )1( ) ( ),..., ( )k k K kg D h D h D⊥ ⊥ ⊥= , де ih H∈ .
Для цілого числа L виберемо L функцій 1,..., Lg g з Ψ , незалежно і
рівномірно, випадковим чином. Під час кроку передобчислень, збережемо
кожну проекцію доменного блоку kD S⊥ ∈ в наборі ( )j kg D⊥ для кожного
1, 2,...,j L= . Оскільки загальна кількість таких множин може бути великою,
залишимо тільки непорожні набори шляхом повернення до класичного
хешування. Для того, щоб обробити ранговий блок mR , проводимо пошук
серед всіх множин 1( ),..., ( )m L mg R g R⊥ ⊥ . Оскільки можливо (хоча і
маловірогідно) що спільна кількість доменів, збережених в цих множинах, є
великою, то пошук домена припиняється після знаходження 3L елементів
(включаючи дублікати). Нехай 1 ,..., tD D⊥ ⊥ - знайдені елементи. Для кожного
домена 1,...,tD повертаємо відповідь «ТАК» (тобто даний домен є
потенційним кандидатом побудови перетворення в ранговий блок mR ),
якщо ( )1,..., 2,t mD B R r⊥∈ , інакше повертаємо відповідь «НІ». Параметри K та
L вибираються так, щоб гарантувати, що наступні дві властивості
виконуються із заданою вірогідністю:
Якщо існує ( )*
1,k mD B R r∈ , то *( ) ( )j k j mg D g R⊥= для деякого 1,...,j L=
Загальна кількість колізій mR⊥ з точками з 2( , )kS B D r⊥− менша, ніж 3L
(параметр визначений емпіричним шляхом) тобто:
( ) ( )1
2
1
( , ) ( ) 3
L
k j j k
j
S B D r g g D L⊥ − ⊥
=
− ∩ <∑ .
Якщо виконуються обидві властивості, то алгоритм є коректним. Звідси
випливає, що якщо встановити 2log(1/ )K p= , і L nρ= , де
1
2
ln(1/ )
ln(1/ )
p
p
ρ = , (1)
то властивості (1) і (2) виконуються з постійною вірогідністю. Таким
чином, отримуємо наступну теорему, яка стосується залежності ефективності
90
вирішення ( ),c NNτ − задачі при фрактальному стисненні зображень від
параметрів LSH:
Передбачимо, що існує ( )1 2, , ,c p pτ τ⋅ - чутливе сімейство функцій
хешування H для міри відстані ( , )d ⋅ ⋅ . Тоді існує алгоритм для вирішення
( ),c NNτ − задачі для міри ( , )d ⋅ ⋅ , який використовує ( )1
d dO dn n ρ++ пам'яті, з
часом обробки одного запиту, визначеним ( )dO nρ обчислень відстані і
2( log(1/ ) )ddO n p nρ ⋅ обчислень хеш-функцій з H , де ρ визначений як (1).
Адаптація просторово-чутливих хеш-функцій до фрактального
стиснення зображень на основі p-стійких розподілів
Стійкі розподіли визначаються як границі нормалізованих сум
незалежних рівномірно розподілених випадкових змінних (нижче дано
альтернативне визначення). Найбільш відомий приклад стійкого розподілу -
це нормальний (гаусовий) розподіл. Проте, клас таких розподілів є значно
ширшим. Розподіл μ над ℜ називається p -стійким, якщо існує 0p ≥ таке,
що для будь-яких d , дійсних чисел 1,..., dv v та змінних 1,..., dX X з
розподілом μ , випадкова змінна i ii
v X∑ має такий же розподіл, як і змінна
( )1/ pp
ii
v X∑ де X - випадкова змінна з розподілом μ .
Відомо, що стійкі розподіли існують для будь-якого (0,2]p∈ . Зокрема,
гаусовий (нормальний) розподіл Gμ , визначений як функція щільності
вірогідності
2 / 21( )
2
xg x e
π
−= ,
є 2-стійким.
Зауважимо, що з практичної точки зору, не дивлячись на недолік
закритих форм функцій розподілу щільності, відомо, що можна створити p -
стійку випадкову змінну з двох незалежних випадкових змінних, рівномірно
розподілених на інтервалі [0,1] .
Використовуючи p -стійкі розподіли, побудуємо сімейство хеш-функцій
H , адаптоване до фрактального стиснення зображень. Інтуїтивно, сімейство
хеш-функцій має бути просторово-чутливим, тобто якщо два вектори ,m kR D⊥ ⊥
близькі один до одного (значення m k p
R D⊥ ⊥− відносно невелике), то вони
повинні з великою вірогідністю викликати колізію (мати одне і те ж значення
хеш-функції) і, якщо вони розташовані далеко один від одного, то
вірогідність колізії має бути мала. Нехай a - вектор розмірності d , елементи
91
якого вибираються незалежно з p -стійкого розподілу. Скалярний добуток
, ma R⊥ проектує кожен вектор на множину дійсних чисел. З p -стійкості
випливає, що для двох векторів ,m kR D⊥ ⊥ відстань між їх проекціями
, ,m ka R a D⊥ ⊥− розподілено як m k p
R D X⊥ ⊥− , де X - це випадкова змінна,
що вибрана з p -стійкого розподілу. Якщо «розділити» множину дійсних
чисел на підмножини рівного розміру r та визначити значення хеш-функції
для вектора залежно від того, на яку підмножину він проектується, то
інтуїтивно ясно, що така хеш-функція буде просторово чутлива в описаному
вище сенсі.
Формально, кожна хеш-функція , ( ) : d
a bh v Nℜ → відображує вектор v
розмірності d (проекція рангового mR⊥ або доменного блоку kD⊥ ) на
множину цілих чисел. Кожна хеш-функція в сімействі однозначно
визначається вибором випадкового вектора a , визначеного вище, і дійсного
числа b , вибраного випадковим чином з діапазону [0, ]r . Для даних ,a b
визначимо хеш-функцію ,a bh таким чином:
,
,
( )a b
a v b
h v
r
⎡ + ⎤
= ⎢ ⎥
⎣ ⎦
(2)
Тепер обчислимо вірогідність колізії хеш-функції, вибраної випадково
згідно описаним вище міркуванням, для двох векторів ,m kR D⊥ ⊥ . Нехай ( )pf t
позначає щільність вірогідності абсолютного значення p -стійкого розподілу.
Для двох векторів ,m kR D⊥ ⊥ Нехай m k p
c R D⊥ ⊥= − . Для випадково вибраного
вектора a , елементи якого узяті з p -стійкого розподілу, , ,m ka R a D⊥ ⊥−
розподілене як cX , де X - випадкова змінна, вибрана з p -стійкого
розподілу. Оскільки b вибране випадково з діапазону [0, ]r , легко побачити,
що
, , ,
0
1( ) Pr ( ) ( ) 1
r
a b a b m a b k p
t tp c h R h D f dt
c c r
⊥ ⊥ ⎛ ⎞⎛ ⎞⎡ ⎤= = = −⎜ ⎟⎜ ⎟⎣ ⎦ ⎝ ⎠⎝ ⎠∫
Для фіксованого параметра r вірогідність колізії монотонно
зменшується із зростанням з m k p
c R D⊥ ⊥= − . Згідно визначення, що було
дане на початку параграфа, сімейство хеш-функцій , ( )a bh v є 1 2 1 2( , , , )r r p p -
чутливим для 1 (1)p p= та 2 ( )p p c= при 2 1/r r c= .
92
Параметр r не був чітко визначений, оскільки він залежить від значень
c та p . Для кожного даного c задача полягає у виборі такого кінцевого
значення r , яке робить ρ якомога меншим.
Висновок
У даній статті розглянуті аспекти застосування просторово-чутливого
хешування при фрактальному стисненні зображень. Описані достоїнства
даного методу, його природна пристосованість для вирішення задач, що
виникають при фрактальному стисненні. Стаття може бути використана для
наведення оцінок вимог алгоритму до пам'яті і вірогідності негативної
відповіді на запит для кожної рангової області.
Результати проведеної роботи говорять про доцільність застосування
просторово-чутливого хешування при вирішенні задач фрактального
стиснення зображень.
1. Indyk P.. Motwani R. Approximate nearest neighbor: towards removing the curse of
dimensionality. Proceedings of the Symposium on Theory of Computing, 1998.
2. Indyk P. Stable distributions, pseudorandom generators, embeddings and data stream
computation. Proceedings of the Symposium on Foundations of Computer Science, 2000.
3. Saupe D., Hamzaoui R. A guided tour of the fractal image compression literature, in: New
Directions for Fractal Modeling in Computer Graphics, J. Hart (ed.), ACM SIGGRAPH'94
Course Notes 13, 1994.
4. 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.
5. Darrell Т., Indyk P., Shakhnarovich G. (eds.), Locality-sensitive hashing using stable
distributions, Nearest Neighbor Methods in Learning and Vision: Theory and Practice, MIT
Press, 2006.
6. Boss R.D., Jacobs E.W. Archetype classification in an iterated transformation image
compression algorithm, in: Fractal Image Compression Theory and Applications, Y. Fisher
(ed.), Springer-Verlag, New York, 1994.
7. Arya S., Mount D.M., Netanyahu N.S., Silvernam R., Wu A. An optimal algorithm for
approximate nearest neighbor searching, Proc. 5th Annual ACM-SIAM Symposium on
Discrete Algorithms (1994) 573-582.
Поступила 25.02.2010р.
|