Фрактальне стиснення зображень в градаціях сірого
Gespeichert in:
| Veröffentlicht in: | Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України |
|---|---|
| Datum: | 2009 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2009
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/29613 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Фрактальне стиснення зображень в градаціях сірого / І.В. Хімченко // Збірник наукових праць Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 50. — С. 116-123. — Бібліогр.: 10 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859519512809832448 |
|---|---|
| author | Хіміченко, І.В. |
| author_facet | Хіміченко, І.В. |
| citation_txt | Фрактальне стиснення зображень в градаціях сірого / І.В. Хімченко // Збірник наукових праць Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 50. — С. 116-123. — Бібліогр.: 10 назв. — укр. |
| collection | DSpace DC |
| container_title | Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України |
| first_indexed | 2025-11-25T20:51:34Z |
| format | Article |
| fulltext |
очевидна необходимость поддержки в вычислительной среде специальной
онтологической базы знаний, включающей рубрикаторы, классификаторы,
каталоги структур образной информации. В связи с этим далее мы детальнее
рассмотрим модель Хокинса.
1. Головко В.А. Нейроинтеллект: Теория и применения. //Организация и обучение
нейронных сетей с прямыми и обратными связями - Брест:БПИ, 1999
2. Головко В.А. Нейроинтеллект: Теория и применения. //Самоорганизация,
отказоустойчивость и применение нейронных сетей - Брест:БПИ, 1999
3. Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика, 1992
4. Лурье И.К., Косиков А.Г. Теория и практика цифровой обработки изображений //
М.: Научный мир, 2003.
5. Sciascio E.Di., Mongiello. DrawSearch: A tool for interactive content-based image
retrieval over the net. Proc. SPIE, vol. 3656, 1999.
6. Muller H., Muller S., Marcand-Maillet, and Squire D. McG. Strategies for positive and
negative relevance feedback in image retrieval. In Proc. Int. Conf. Pattern Recognition,
Barcelona, Spain, 2000.
7. Porkaew S., Mehrotra S., Ortega M. and Chakrabarti K. Similarity search using multiple
examples in MARS. In Visual Information and Information Systems. New York: Springer-
Verlag, 1999
8. http://tineye.com - поисковый сервис для поиска похожих изображений.
9. Блейксли С., Хокинс Д. Об интеллекте. Москва: Изд. дом «Вильямс» - 2007- 240 с.
10. Гаврилова Т.А. Онтологический подход к управлению знаниями при разработке
корпоративных информационных систем. // Новости искусственного интеллекта, N2,
2003. - с.24-30.
11. Siтоп Н. А. Тпе sсienсе оf Ше аrtificial. 2d еd. Саmbridge, МА: МГГ Press, 1996.
Поступила 11.02.2009р.
УДК 004.81
І.В. Хіміченко, аспірант МННЦІТтаС, Київ
ФРАКТАЛЬНЕ СТИСНЕННЯ ЗОБРАЖЕНЬ В ГРАДАЦІЯХ СІРОГО
Вступ
Об 'єктом дослідження є обчислювальні (комп'ютерні) алгоритми
фрактального стиснення зображень в аспекті їх часової ефективності при
обмеженнях градацій сірого.
Предмет дослідження - оптимальність алгоритмів стиснення статичних
растрових зображень з використанням фрактальної графіки.
Мета дослідження - побудова методу фрактального стиснення для
растрових статичних зображень з використанням класичного алгоритму
фрактального стиснення статичних зображень.
Очікувані результати - асимптотичні оцінки часової ефективності
116 © І.В. Хіміченко
http://tineye.com
розробленого алгоритму фрактального стиснення зображень в градаціях
сірого.
Зображення, таке як відома фрактальна папороть, може бути відтворене
за допомогою відносно простої системи ітеруючих функцій, оскільки цей
вигляд володіє властивістю глобальної самоподібності. Це означає, що ціле
зображення складається із зменшених копій його самого або його частин.
Збільшуючи таке зображення можна спостерігати один і той самий ступінь
деталізації незалежно від якості зображення. Крім того, зображення такого
типу - це двійкове зображення, тобто кожен його піксель може бути
представлений одиницею або нулем. Реальні зображення не володіють
властивістю глобальної самоподібності. Крім того, реальні зображення не є
двійковими, кожен піксель належить діапазону значень (у градаціях сірого)
або вектору значень (у кольорі). Для того, щоб представити таке зображення
як атрактор ітераційної системи, то, очевидно, нам необхідний спосіб
побудувати таку систему функцій в автоматичному режимі.
У даній статті розглядається побудова і реалізація таких систем, які
можуть бути використані у фрактальному кодуванні довільних зображень в
градаціях сірого.
Метричний простір для зображень в градаціях сірого
Зображення в градаціях сірого можна розглядати як дійсну функцію
/(х, у ) , визначену на одиничному квадраті 12 = 1x1. Тобто
/ : 12 ^ {1,2,..., п ^ } с й
де п - це число градацій сірого.
Рис. 1.2.1. Графік зображення як дійсна функція.
В якості вихідного зображення використано Lena.jpg
Можна ввести метрику d(•, •) на цій функції, наприклад, наступним
чином:
117
( 2 Y'2
d(f1, f2 ) = I j I f (x, y) - f2 (x, y)|2dxdy (1)
V/2 )
Визначимо простір F дійсних функцій інтегрованих з квадратом на / 2
з введеною метрикою. Тоді простір F - повний, і в ньому виконується
теорема про стискуючі відображення.
Зображення, що розглядаються в даній дисертації, - це цифрові
зображення, тобто n x m матриця значень \ f t j ], i = 1,2,..., n, j = 1,2,..., m , де
f і j = f (x j, y j ) . Таким чином, це матриця фіксованих значень функції f (x, y ) ,
узятих в точках (x t, y i ) . В цьому випадку говорять про середньоквадратичну
метрику (від rms - root mean square):
n m 2
dm (A1, f2 ) = [ £ £ | A1( x , yj ) - f2 ( x , yj )| ] 1 / 2
i=1 j=1
Системи ітеруючих кусково-визначених функцій
У фрактальному стисненні зображень використовуються IFS
спеціального вигляду, а саме системи ітеруючих кусково-визначених функцій
(partitioned iterated function system - PIFS). PIFS складається з повного
метричного простору X , набору підобластей Dk с X , к = 1,2,...,n та набору
стискуючих відображень wІ : Dk ^ X , i = 1,2,...,n .
Рис. 1.2.2. Система ітеруючих кусково-визначених функцій
Афінні перетворення зображень в градаціях сірого
Нехай VІ (х, у) - це афінне перетворення, що переводить в себе
одиничний квадрат: 12 ^ 1 2 , або, іншими словами
м> І (х, у) = 4 ^ у | + ЬІ
Для деякої матриці Лі розміром 2 х 2 і вектора Ьі, розміром 2 х 1.
118
Нехай Dk с 12 - деяка підобласть одиничного квадрата 12 і нехай Rm -
область значень перетворення w,, що діє на множині Dk так, що
w, (Dk) = Rm. Тепер можна визначити відображення wj: F ^ F , що діє на
зображення f (x, y) у вигляді
Wi ( f ) ( x , y) = 5,. • f (w-1(x, y)) + ot (2)
за умови, що w, оборотне та (x, y) є Rm . Константа s, розширює або звужує
діапазон значень функції f або, для зображень в градаціях сірого, управляє
контрастністю. Аналогічно, константа збільшує або зменшує значення
градацій сірого, або управляє яскравістю.
Перетворення Wi називається просторовою складовою перетворення
w,.
Перетворення (2) - це базове афінне перетворення зображень в градаціях
сірого, яке найчастіше використовується для фрактального стиснення.
Стискуючі відображення зображень в градаціях сірого
Для того, щоб відображення W, : F ^ F було стисненням, необхідно
виконання умови
d(W,.(f1), W,.(f2)) < s• d(f„ f2)
для деякого s, 0 < s < 1, де d(•, •) - це метрика, що задана виразом (1).
Використовуючи формулу заміни змінної в кратному інтегралі, отримаємо
d2 (w, ( f ) , w, ( f 2 ) ) = J |w, ( f ) ( x , y) - w, ( f 2 ) ( x , y)f dxdy =
w, ( D,)
= |s,|2 • |det A\ • J | fi(x,y) - f2(x ,y) | 2 dxdy <|s,,|2 • |detAt\ • d2(fx, f2) де At -
D,
матриця перетворення wt, det Af - визначник A, та s, - коефіцієнт
стиснення. Щоб перетворення було стисненням, достатньо виконання умови
|s,| ^ |de tA, | < 1 (3)
Зокрема, коефіцієнт стиснення має бути за модулем більше одиниці:
|s,| > 1. Тоді просторова складова w, буде стисненням з коефіцієнтом
стиснення, достатньо маленьким для того, щоб виконувався вираз (3).
Теорема про стискуючі відображення для зображень в градаціях сірого
Розіб'ємо одиничний квадрат 12 на множину рангових блоків, які
утворюють покриття I2 :
12 =^Rm ,
119
R n R = 0
Нехай Wi - PIFS вигляду w, • Dk ^ Rm
Для деякої множини доменних блоків (доменів - domains) Dk Œ 12
(блоки Dk можуть перекриватися і можуть не повністю перекривати 12 ).
Для кожного Wi визначимо відповідне стиснення w{ на просторі
зображень F :
~ - і
wi(f)(X У) = s, • f(w ( X У)) + o,
вибираючи s, так, щоб w{ було стисненням. Тепер визначимо
W : F ^ F наступним чином
W (f )( x, y) = wt (f )( x, y) для ( x, y ) є Rm
Внаслідок того, що рангові блоки Rm покривають 12, W визначене для
всіх ( x, y) з 12 і, значить, W (f ) є зображенням. Оскільки кожне
відображення w{ є стисненням, то W є стисненням на F. Тому, згідно
теоремі про стискуючі відображення, W має єдину нерухому точку fw є F ,
що задовольняє
W (fw ) = fw
Ітераційно, застосовуючи W до будь-якого початкового зображення f 0 ,
отримаємо нерухому точку fw :
Won(fo) ^ fw при n ^ œ ,
де Won ( f o ) - це W (W (...W ( f o ) ) ) ( n -разів)
Рис. 1.2.3. Декілька ітерацій процесу декодування зображення Lena.jpg
Теорема про стискуючі зображення є базовою для всіх існуючих методів
фрактального кодування. Для зображення в градаціях сірого / намагаємося
знайти стискуюче відображення Ж , таке, щоб зображення , що є
нерухомою точкою відображення Ж , було близьким до / . Тоді Ж містить
120
всю необхідну інформацію, необхідну для отримання fw. Якщо для
зберігання W потрібно менше місця, ніж для збереження зображення f , то
це означає, що ми досягли стиснення зображення.
Теорема колажа для зображень в градаціях сірого
Як у випадку з IFS та двійковими зображеннями, теорема колажа існує і
для PIFS та зображень в градаціях сірого. Нехай задане зображення в
градаціях сірого f . Передбачимо, що ми можемо знайти стискуюче
відображення W , таке що d(f,W(f)) < s .
Тоді
s
d ( f, fw ) < — (4)
1 - s
де s - це коефіцієнт стиснення відображення W , а fw - його нерухома точка.
Це означає, що ми можемо почати з будь-якого зображення g і ітеративно
застосовувати перетворення W до зображення g, щоб отримати
зображення, близьке до f .
W°" ( g ) ^ fw « f
Тоді як теорема про стискуючі відображення забезпечує саму
можливість фрактального кодування, теорема колажа дає практичний спосіб
його реалізації. Замість того щоб думати про нескінченну кількість ітерацій,
вживаних до даного зображення, нам потрібно тільки знайти таке
відображення W однократне застосування якого, тобто зображення W ( f ) ,
буде близьким до бажаного зображення f . Відмітимо, що W має бути
стисненням з коефіцієнтом стиснення s багато меншим одиниці, інакше
умова, що міститься в правій частці нерівності (4) втрачає сенс.
Теорема колажа підводить нас на один крок ближче до процесу
фрактального кодування зображень. Маючи дане зображення в градаціях
сірого f , ми намагаємося знайти стиснення W таке, що W( f ) , тобто fw
буде близьким до f . Декодування полягає в ітеруванні W будь-якого
початкового зображення g для отримання fw .
Представлення зображень кінцевим об'ємом даних
Комп'ютерне зображення в його цифровому уявленні є набором значень
інтенсивностей світлового потоку, розподілених за кінцевою площею, що має
зазвичай прямокутну форму.
У випадку монохромних зображень інтенсивність випромінюваної
світлової енергії з одиниці поверхні в точці з координатами
зображення можна представити деяким числом B(Ç, rf). Одиничний елемент
зображення, що характеризується певним значенням rf), називається
121
пікселем, а величина z = f (£,ц) - яскравістю.
Статистична і візуальна надмірність зображень
Потік даних про зображення має істотну кількість зайвої інформації, яка
може бути усунена практично без помітних для ока спотворень.
Існує два типи надмірності:
• Статистична надмірність, пов'язана з кореляцією і передбаченістю
даних. Ця надмірність може бути усунена без втрати інформації, початкові
дані при цьому можуть бути повністю відновлені.
• Візуальна (суб'єктивна) надмірність, яку можна усунути з
частковою втратою даних, мало відтворних зображень, що впливають на
якість; це - інформація, яку можна вилучити із зображення, не порушуючи
візуально сприйману якість зображень.
Статистична надмірність зображень
Нехай є дискретизоване M х N пікселів і квантоване з точністю K біт на
піксель монохромне зображення. Отже, для зберігання цього зображення
необхідно M х N х K біт інформації.
Якщо передбачити, що квантовані значення яскравості не рівноімовірні,
то зменшення інформації можливе шляхом зміни кількості біт інформації для
кодування пікселів: вірогідніші кодуються словами з меншою кількістю біт,
менш вірогідніші - з великою. Цей метод називається кодуванням словами
змінної довжини або ентропійним кодуванням.
Нехай квантований рівень яскравості z має вірогідність P(z) і йому
привласнюється слово - код довжини L(z) біт. Тоді середня довжина коди
для всього зображення складе L = £ L( z) • P( z) біт на піксель. Нижня
Ь
границя для L визначається інформаційною теоремою і називається
ентропією випадкової величини:
H(f) = - £ P ( ^ • ісе2 P(z) < L (4)
z
Таким чином, ентропія - це міра кількості інформації, яку несе
випадкова величина рівня яскравості z.
H(z) > 0 , оскільки P(z) є [0,1]. З формули (6) маємо, що чим більш
нерівномірний розподіл P( z), тим менша ентропія і тим ефективнішим може
бути ентропійне кодування.
Найбільш відомі методи ефективного кодування символів засновані на
122
знанні частоти кожного символу присутнього в повідомленні. Знаючи ці
частоти, можна побудувати таблицю кодів, що має наступні властивості:
• різні коди можуть мати різну кількість біт;
• коди символів, що зустрічаються найбільше, мають більше біт, ніж
коди символів з меншою частотою;
• хоча коди мають різну бітову довжину, вони можуть бути
відновлені єдиним чином.
Цими властивостями характеризується відомий алгоритм Хаффмана.
Візуальна надмірність зображень
Усунення візуальної надмірності зображень є основним резервом
скорочення інформації, що передається. Для оптимізації процесу кодування з
точки зору забезпечення передачі найменшого об'єму інформації необхідно, з
одного боку, не передавати надлишкову інформацію, а, з іншого, - не
допустити надмірної втрати якості зображення.
До цих пір не існує простої та адекватної моделі візуального сприйняття
зображень, придатної для оптимізації їх кодування.
1. ФедерЕ. Фракталы. M.: Мир, 1991.
2. Божокин С.В., Паршин Д.А. Фракталы и мультифракталы. - Ижевск: НИЦ
«Регулярная и хаотическая динамика», 2001.
3. Шредер М. Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая.
- Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.
4. Kenneth Falconer. Fractal geometry. Mathematical foundations and applications. -
JOHN WILEY & SONS: Chichester, New York, Brisbane, Toronto, Singapore, 1990.
5. Бондаренко В.А., Дольников В.Л. Фрактальное сжатие изображений по Барнсли-
Слоану. Автоматика и телемеханика. 1994. №5. С. 12-20.
6. Ваганова Н. А., Фрактальное сжатие динамических изображений. Инфор-
мационные технологии, Новосибирск 1999.
7. Васильев К.К., Наместников СМ. Анализ методов сжатия изображений при
разных критериях качества восстановленного изображения. Труды IX международной
научно-технической конференции «Радиолокация, навигация, связь», Воронеж, 2003,
с. 10б0-10б7.
S. Ватолин Д.С, Фрактальное сжатие изображений, Computerworld Шб, 199б.
9. Ватолин Д.С, Использование ДКП для ускорения фрактального сжатия
изображений. Программирование, Номер 3, 1999, стр. 51-57.
10. Ватолин Д.С. Алгоритмы сжатия изображений II ISBN 5-S9407-041-4 М.: Диалог-
МГУ, 1999.
Поступила 16.02.2009р.
123
|
| id | nasplib_isofts_kiev_ua-123456789-29613 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0067 |
| language | Ukrainian |
| last_indexed | 2025-11-25T20:51:34Z |
| publishDate | 2009 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Хіміченко, І.В. 2011-12-19T15:04:12Z 2011-12-19T15:04:12Z 2009 Фрактальне стиснення зображень в градаціях сірого / І.В. Хімченко // Збірник наукових праць Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. — К.: ІПМЕ ім. Г.Є. Пухова НАН України, 2009. — Вип. 50. — С. 116-123. — Бібліогр.: 10 назв. — укр. XXXX-0067 https://nasplib.isofts.kiev.ua/handle/123456789/29613 004.81 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/29613 |
| work_keys_str_mv | AT hímíčenkoív fraktalʹnestisnennâzobraženʹvgradacíâhsírogo |