Використання математичного сподівання для швидкого центрування наборів зображень

There is proposed RSA algorithm modification on the based of the form of pixel threads. The used picture must be in the one byte pixel format and allows contour separation.

Збережено в:
Бібліографічні деталі
Дата:2009
Автор: Пелешко, Д.Д.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2009
Назва видання:Моделювання та інформаційні технології
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/21145
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Використання математичного сподівання для швидкого центрування наборів зображень / Д.Д. Пелешко // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2009. — Вип. 50. — С. 135-144. — Бібліогр.: 6 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-21145
record_format dspace
spelling irk-123456789-211452013-02-13T03:03:53Z Використання математичного сподівання для швидкого центрування наборів зображень Пелешко, Д.Д. There is proposed RSA algorithm modification on the based of the form of pixel threads. The used picture must be in the one byte pixel format and allows contour separation. 2009 Article Використання математичного сподівання для швидкого центрування наборів зображень / Д.Д. Пелешко // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2009. — Вип. 50. — С. 135-144. — Бібліогр.: 6 назв. — укр. XXXX-0068 http://dspace.nbuv.gov.ua/handle/123456789/21145 004.932; 681.142.2; 622.02.658.284; 621.325 uk Моделювання та інформаційні технології Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Ukrainian
description There is proposed RSA algorithm modification on the based of the form of pixel threads. The used picture must be in the one byte pixel format and allows contour separation.
format Article
author Пелешко, Д.Д.
spellingShingle Пелешко, Д.Д.
Використання математичного сподівання для швидкого центрування наборів зображень
Моделювання та інформаційні технології
author_facet Пелешко, Д.Д.
author_sort Пелешко, Д.Д.
title Використання математичного сподівання для швидкого центрування наборів зображень
title_short Використання математичного сподівання для швидкого центрування наборів зображень
title_full Використання математичного сподівання для швидкого центрування наборів зображень
title_fullStr Використання математичного сподівання для швидкого центрування наборів зображень
title_full_unstemmed Використання математичного сподівання для швидкого центрування наборів зображень
title_sort використання математичного сподівання для швидкого центрування наборів зображень
publisher Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
publishDate 2009
url http://dspace.nbuv.gov.ua/handle/123456789/21145
citation_txt Використання математичного сподівання для швидкого центрування наборів зображень / Д.Д. Пелешко // Моделювання та інформаційні технології: Зб. наук. пр. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2009. — Вип. 50. — С. 135-144. — Бібліогр.: 6 назв. — укр.
series Моделювання та інформаційні технології
work_keys_str_mv AT peleškodd vikoristannâmatematičnogospodívannâdlâšvidkogocentruvannânaborívzobraženʹ
first_indexed 2025-07-02T21:41:28Z
last_indexed 2025-07-02T21:41:28Z
_version_ 1836572987814313984
fulltext 135© Д.Д.Пелешко УДК 004.932; 681.142.2; 622.02.658.284; 621.325 Д.Д.Пелешко, к.т.н., доц. НУ “Львівська політехніка”, м.Львів ВИКОРИСТАННЯ МАТЕМАТИЧНОГО СПОДІВАННЯ ДЛЯ ШВИДКОГО ЦЕНТРУВАННЯ НАБОРІВ ЗОБРАЖЕНЬ There is proposed RSA algorithm modification on the based of the form of pixel threads. The used picture must be in the one byte pixel format and allows contour separation. Вступ На практиці зображення того самого об'єкта або ділянки місцевості, отримані в різний час або за допомогою різних датчиків, можуть значно відрізнятися один від іншого. Звідси випливає ряд важливих задач прив'язки, а також точної взаємної геометричної корекції для наступної обробки зображення [1-5]. У теорії обробки зображень задача пошуку відповідності отримала роз- повсюдження і відома як проблема «пошуку за зразком». Формально її можна розглядати як процес ототожнення еталонного зображення (фраг- мента) на першому знімку з одним з безлічі фрагментів, які лежать у деякій (такій, що задається) області (зоні пошуку) другого знімку. Алгоритми встановлення подібності в тій чи іншій мірі пов’язані одер- жанням характеристик стохастичного взаємозв'язку порівнюваних фрагмен- тів зображень [2]. Традиційно для реалізації процедури знаходження і сумі- щення зображень використовують кореляційну прив´язку цифрових зобра- жень. Метод кореляційної прив´язки зображень має такі недоліки: • взаємна кореляційна функція може мати досить розмитий максимум, що ускладнює його знаходження, оскільки не враховує просторову структуру порівнюваних зображень; • комбінаторна складність - великий перебір ситуацій [2-5]. Широке застосування кореляційно-екстремальних процедур розпізна- вання сигналів призводить до необхідності шляхів їх вдосконалення [6]. 1. Постановка задачі Формування наборів зображень може реалізовуватись різними способами: рухом камери, рухом об’єкта, тощо. При цьому величина зсуву може перевищувати наперед задану величину Δ, яка в загальному випадку є функцією декартових координат, тобто Δ = Δ (x,y) і, у більшості випадків, є основою математичних методів подальшої обробки зображень. В такому разі виникає задача центрування зображень в межах заданої величини Δ.  Як зазначено вище, базовий метод, а саме метод кореляційної прив’язки, має деякі недоліки й основним з них це є комбінаторна складність. Тому метою даної статті є розв’язання задачі прискорення центрування 136 зображення в межах заданої величини Δ. Основним завданням є розробка методу із суттєво меншою комбінаторною складністю в порівнянні із існуючими методами з метою прискорення розв’язання задачі центрування. Основним базисом для вирішення цієї задачі є методи математичної статистики. 3. Математична модель прискореного центрування Основна ідея алгоритму прискореного центрування полягає у швидкому формуванні для кожного зображення відповідних наборів “підозрілих” на подібність фреймів з подальшим їх звуженням математичною кореляцією із заданим фрагментом. Нехай існує набір з N рисунків ( ){ }2, , 1.. :P X d z z z z z N P P C + = = = , (1) де 2, ,: , 1, X d d z z zC Q z N+ → = ; (2) ( ){ }2, , , , , | 1, 1, , , .X Nd z z i jdtp i j i l j h l h+ += = = ∧ = ∈ (3) Тут через P позначається набір з N рисунків Pz, а 2, , 2,X Nd z + +⊂ - область визначення оператора Cz; d zQ Color⊂ - замкнена обмежена підмножина простору кольорів; функція Cz – представлення рисунка у вигляді перетворення з координатного простору 2, ,X d z + у колірний простір d zQ ; , Nl h +∈ – довжина та висота рисунка. Початком координат на усіх рисунках набору P є верхній лівий кут зображення. На будь-якому фіксованому зображенні набору вибираємо зображення стосовно якого будуть центруватись решта зображень набору. Нехай у випадку існування (1) таке зображення має індекс 1, тобто це - P1. Тоді через 'P позначимо набір з решти рисунків { } 2.. 'P z z N P = = . На P1 визначимо фрейм ( )2, , 2, , 1,зад 1,зад 2, , 2, , 1,зад 1,зад 2, , 2, , 1,зад 1,зад , , ,fr fr fr fr X X fr fr X X X X d d d d d d x y l h + + + + + += Δ Δ , (4) якому відповідає фрагмент зображення 1,задP . Тут 2, , 1,задfrX d x + Δ i 2, , 1,задfrX d y + Δ - зміщення початку фрейма 2, , 1,задfrX d+ відносно початку 2, , 1X d+ в напрямках x та y відповідно. Іншими характеристиками фрейма виступають його довжина 2, , 1,задfrX dl + та висота 2, , 1,задfrX Ndh + +∈ Проблема вибору початкового фрейму 2, , 1,задfrX d+ в даній статті детально не розглядатиметься. Приймаємо лише одне припущення, що, 2, , 1,задfrX d+ містить такий фрагмент зображення P1, який існує на усіх зображеннях набору 'P . Для кожного рисунку з 'P сформуємо скінченне неунікальне покриття 137 фреймів { } { }{ } { } , , 1..2, , 2, , , ,1.. 1.. 1..1.. ' ' fr frX X z z m Nd d z z m z mz N m N z Nz N χ χ =+ + = = == = χ = =χ (5) з розмірами 2, , 2, , 1,зад 1,зад i fr frX Xd dl h+ + в кількості - ,zNχ фреймів Тоді за (31) маємо { } ( ){ }{ } , 2, , 2, , , , , , ,1.. 2.. ' | ; , : 'fr frP X X z d d z z m z m z m z m z m zm N z N P P P C z m χ + + = = = = = ∀ ∈χ . ( 6) Для кожного фрагмента ,z mP порахуємо математичне сподівання значення кольору ,z mM ( ) 2, , 2 , , , , поч 2, , поч 2, , , , 2, , 2, ,2, , 2, , , , , , поч поч , ,, , , 1 ; 1.. ; 2.. X Xfr fr X Xfr fr X Xfr fr fr frX X d d z m z m d d z m z m d dd d z m z m z m z m x l y h d z m zz m i j i x j y M c m N z N l h + + + + + ++ + + + χ = = = = =∑ ∑ . ( 7) Аналогічно до (7) обчислюється середнє значення 1,задM для фрагмента 1,задP . В результаті цього кожному фрейму 2, , ,frX d z m + однозначно поставлено у відповідність характеристика – середнє значення кольорів відповідного фрагмента зображення ,z mP 2, , , ,frX d z m z mM+ → . (8) А за (5) кожному покриттю 'zχ у відповідність ставиться набір середніх значень { },' , 2..z z mM z Nχ → = . (9) Для порівняння характеристик ,z mM із 1,задM при фіксованому z використовує відносну похибку , 1,зад , , z m z m z z m M M M − Δ = ≤ δ . (10) Для зручності можна прийняти, що [ ]1, : zz N∀ ∈ δ = δ . (11) В результаті використання (9) та однозначної відповідності (8) для кожного рисунка набору 'P можна сформувати набір “підозрілих” на подібність фреймі { } , ,підоз 2, , ,підоз ,підоз , , 1.. ' ' , ' |frX z d z z z z m z m m Nχ + = χ ⊆ χ χ = Δ < δ . (12) Очевидно, що розмірність , ,підозzNχ покриття ,підоз'zχ не перевищує розмірності покриття 'zχ , ,підоз ,z zN Nχ χ≤ . (13) 138 Наступним кроком є звуження покриття ,підоз'zχ до одного фрейма, через видалення з ,підоз'zχ зайвих фреймів. З цією метою для кожного фрейма з ,підоз'zχ знаходимо значення кореляції відповідного до фрейма з ,підоз'zχ фрагмента ,z mP з фрагментом 1,задP за формулою ( ) ( )( ) ( )( ) ( )( ) ( )( ) , 1,зад , 1,зад ,1,зад, , , , , , , ,підоз2 2 1,зад ,1,зад, , , , , , , , ; 1.. ; 2.. , z m z m d d z mi j z m i j i j z d d z mi j z m i j i j i j r P P c M c M m N z N c M c M χ = − − = = = − − ∑ ∑ ∑ (14) де ( )1,зад, , d i jc - значення кольору фрагмента 1,задP . В результаті (14) для кожного ,підоз'zχ отримуємо набір значень кореляцій ( ), 1,зад ,,z m z mr P P , які є характеристиками кожного фрагмента ,z mP ( ){ } , ,підоз ,підоз , 1,зад , 1.. ' , , 2.. z z z m z m m N r P P z N χ= χ → = . (15) З усіх ( ), 1,зад ,,z m z mr P P при фіксованому z знаходимо фрагмент з максимальною абсолютною ненульовою кореляцією ( )( )max , ,підоз , , 1,зад ,1.. max , , 2.. z z m z m z mm N P r P P z N χ= = = . (16) При цьому його індекс ( )max max , ,підоз, : 1; zz m m Nχ⎡ ⎤∈ ⎣ ⎦ є індексом шуканого фрейму в покритті ,підоз'zχ . Решта фреймів з ,підоз'zχ видаляємо. Отже ,підоз'zχ завжди звужується до одного фрейму з індексом ( )max,z m { } { }max max 2, , ,підоз , ,' , 2..frX d z z m z mP z N+χ = → = . (17) Звужений ,підоз'zχ , зокрема фрейм, який він містить, дає змогу знайти зміщення для кожного зображення набору відносно фіксованого P1 ( ) ( ) 2, , 2, ,2, , 2, , , ,1,зад 1,задmax max , 1, , 1,; , 2..fr frfr frX XX Xd dd d z m z m x x y yx z y z z N + ++ + Δ = Δ −Δ Δ = Δ −Δ = , (18) де ( ) ( ), 1, , 1,,x z y zΔ Δ - відповідно горизонтальне та вертикальне зміщення z –го зображення набору 'P відносно P1. Звертаємо увагу на те, що зміщення ( ) ( ), 1, , 1,, Nx z y zΔ Δ ∈ , тобто можуть набувати як додатних так і від’ємних значень. 3.1. Результати практичних експериментів З метою практичної перевірки викладених теоретичних основ методу перевірки сформовано набори рисунків різної розмірності, в яких рисунки є результатами горизонтальних та вертикальних зсувів деякого рисунка. Надалі 139 такі набори будемо називати наборами штучно-згенерованих рисунків (НШЗР). Нехай задано набір рисунків, наведений на рис.1. Наведений набір має розмірність – N = 88 рисунків (тобто { }0 88,...,P P P= ) в градаціях сірого, розмірність кожного рисунка l = 34× h = 54 піксели. Центрування здійснювалось стосовно рисунка з індексом 0 (на наборі він не виділений червоним прямокутником). Точність центрування - δ = 0.001. Індексування рисунків в наборі розпочинається з 0, тобто { }1 88' ,...,P P P= . Звертаємо увагу на те, що розмірність набору 'P менша від розмірності набору P на один рисунок, а саме на P0. Рис.1. Зріз екранної форми - результати центрування методом математичного середнього набору штучно-згенерованих рисунків 140 На першому рисунку набору (рис.1) вибрано квадратний фрейм з координатами 2, , 1,зад 10frX d x + Δ = і 2, , 1,зад 10frX d y + Δ = пікселів, шириною 2, , 1,зад 10 frX dl + = пікселів і довжиною 2, , 1,зад 10 frX dh + = пікселів. Відповідний фрагмент виділено червоним квадратом на площині рисунка з нульовим індексом. Рис.2. Зріз екрану - результати формування множин підозрілих фреймів незвуженого покриття 'χ при центруванні методом математичного середнього набору штучно- згенерованих рисунків (рис.1) На рис.2 наведено екранну форму, на якій зображено незвужене покриття 'χ , тобто набір підозрілих фреймів для кожного рисунка набору 'P . Швидкість формування 'χ є визначальною для пропонованого алгоритму. На рис.1 в таблиці ”Зміщення” і колонці “значення” в мітці ”підозр - ” вказується кількість підозрілих фреймів для кожного рисунка. Рис. 3. Розподіл підозрілих фреймів (незвуженого набору 'χ ) в невпорядкованому наборі 'P штучно-згенерованих рисунків (рис.1) 141 На рис.3 наводиться розподіл розмірностей незвуженого покриття 'χ . Періодичність розподілу визначається невпорядкованістю набору 'P і штучним генеруванням рисунків. Результати суміщення, тобто значення ( ) ( ), 1, , 1,,x z y zΔ Δ наведені на рис.1 в таблиці ”Зміщення” і в колонці “значення”. На рис. 4 наводиться розподіл абсолютної величини ( ) ( ) 2 2 , 1, , 1,x z y zΔ + Δ зміщення. Подібно до розподілу розмірностей покриття 'χ періодичність величини ( ) ( ) 2 2 , 1, , 1,x z y zΔ + Δ визначається невпорядкованістю набору 'P і штучним генеруванням рисунків. Рис.4. Розподіл абсолютної величини зміщення в невпорядкованому наборі 'P штучно-згенерованих рисунків (рис.1) Рис.5. Часова залежність роботи алгоритму центрування набору штучно-згенерованих рисунків методом математичного середнього від розмірності набору (тренд - експонентціальний) 142 На рис.5 наведено часові результати (тобто, фактично швидкість) роботи алгоритму центрування НШЗР запропонованим методом залежно від розмірності. Дані цього графіка є середніми значеннями п'яти кращих експериментів. При цьому середньоквадратичне відхилення результатів експерименту не перевищувало 20 мс. Такий підхід зумовлений тим, що ОС MS не операційною системою реального часу і на швидкість роботи алгоритму впливає завантаженість ОС. При цьому розкид результатів може бути дуже значним. Тому довелось проводити набори експериментів для кожної розмірності. Надалі з усіх експериментів набору вибиралось такі, які не відхилялись більше ніж на величину середньоквадратичного відхилення. Величини відхилень для різних розмірностей тут є випадковими, основним критерієм при їх виборі були мале значення (не більше 20 мс) і забезпечення отримання однакового числа експериментів у кожному наборі. На основі результатів вибраних експериментів характеристикою швидкості роботи алгоритму виступало середнє значення значень часу усіх експериментів при кожній розмірності набору. Як видно з результатів експериментів, швидкість роботи алгоритму різко падає (тренд експонентний) із зростанням розмірності набору. Це обумовлено тим, що стрімко зростає кількість арифметичних обчислень. На рис. 6 наведено залежність швидкості роботи процесу центрування НШЗР від розмірів заданого фрейма 2, , 1,задfrX d+ . По осі X на рис.6. характеристикою виступає нормоване в межах від 0 до 1 значення, яке є співвідношенням площі 2, , 1,задfrX d+ до площі рисунка 0PS , тобто 2, , 01,зад / frX d PS S+ . Для спрощення представлення результатів в усіх випадках форма 2, , 1,задfrX d+ була квадратною. Експерименти проводились подібно до експериментів, результати яких відображені на рис.5. Тобто характеристикою виступало середнє значення результатів п’яти кращих експериментів при різних 2, , 01,зад / frX d PS S+ . При цьому похибка відхилення також не перевищували 20 мс. Як показали результати експериментів, найгіршим (найдовше працював алгоритм) для даного набору рисунків є співвідношення 2, , 01,зад / 0.02 frX d PS S+ = , що відповідає розмірам 2, , 2, , 1,зад 1,зад 20; 20 fr frX Xd dl h+ += = . При більших та менших розмірах заданого фрейма (в даному випадку квадратного) швидкість роботи алгоритму лише зростає. Наведені результати не відображають повної картини залежності швидкості роботи алгоритму від розмірів 2, , 1,задfrX d+ , а ілюструють лише характер цієї залежності (тренд поліномний). Очевидно, що тип і якісний вміст рисунка та вибраного фрагмента також будуть впливати на час роботи алгоритму. Основним результатом приведеної залежності є існування максимального екстремуму - найбільшого часу роботи алгоритму. Це означає, що пришвидшення роботи алгоритму є можливим через вибір 143 2, , 1,задfrX d+ . Пошук найменшого значення є достатньо складним, оскільки до розгляду треба приймати двомірний розподіл часу роботу. Двомірність розподілу повинна забезпечуватись довільними характеристиками заданого фрагмента. При цьому можуть існувати декілька екстремумів. Зважаючи на залежність цього розподілу від типу рисунків набору, одержання будь-яких кількісних характеристик існування екстремумів не розглядалось. 4. Висновки Як видно з результатів порівняння часу роботи різних алгоритмів (рис.5) при однаковій розмірності набору і однаковому заданому фреймі метод центрування на основі математичного середнього є найшвидшим з усіх відомих автору. Очевидно, що на практиці за великих розмірностей набору ефективність методу буде зростати, тобто прискорення центрування у порівнянні з наведеними на рис.6 методами буде зростати. При цьому це зростання має характер експонентний, а не пропорційний. Кількісна величина прискорення центрування може несуттєво відрізнятись залежно від характеристик наборів і заданих фреймів. Рис.6. Залежність швидкості роботи алгоритму центрування набору штучно- згенерованих рисунків методом математичного середнього від розмірів заданого фрейма (через співідношення площі фрагмента до площі рисунка, тренд - поліномний) Запропонований метод не залежить від палітри рисунків набору. Як показали результати експериментальних досліджень, його можна використовувати на кольорових зображеннях без жодних застережень. При цьому з метою зменшення обчислень значення кольору кожного піксела можна розглядати не як вектор байтів кольорів, а єдиним цілим, тобто у форматі, коли значення кожного кольору палітри є байтом у змінній цілого типу. 144 © Б.В.Дурняк, О.В.Шевченко Усі експерименти, результати яких наведені на рисунках, проводились стосовно вертикального і горизонтального центрування. Проте жодних теоретичних обмежень не існує проти центрування з поворотом. А тому можна стверджувати, що наведених метод можна використовувати стосовно центрування зображень, які зсунуті відносно будь-яких афінних перетворень. 1. Грузман И.С., Киричук В.С., Косых В.П., Перетягин Г.И., Спектор А.А. Цифровая обработка изображений в информационніх системах: Учебное пособие.- Новосибирск: Изд-во НГТУ, 2000.– 168 с. 2. А.М.Крот, Е.Б.Минервина. Быстрые алгоритмы ы программы цифровой спектральной обработки сигналов и и изображений. - Минск: «Навука і тэхніка», 1995. - 407 с. 3. А.В.Гиренко, П.А.Корчагин и др. Методы корреляционного обнаружения объектов. –Харьков: АО «Бизнес- Информ», 1996. - 111с. 4. Ярославский Л.П. Введение в цифровую обработку изображений. –М.: Сов. радио, 1979. - 312 с. 5. Путятин Е.П., Аверин С.М. Обработка изображений в робототехнике. М.: Машиностроение. 1990. - 320 с. 6. Ю.Рашкевич, Б.Демида, Д.Пелешко, Н.Кустра Центрування зображень на основі методів кореляційного аналізу // Національна академія наук України Зб. наук. пр. ІПМЕ ім. Г.Є.Пухова. - Вип. 29. Київ, 2005. - С.121-128. Поступила 19.11.2008р. УДК 683.05 Б.В.Дурняк, О.В.Шевченко АНАЛІЗ СПЕЦІАЛЬНИХ ПАРАМЕТРІВ МЕРЕЖІ ЗВ’ЯЗКУ ПРИ ВИКОРИСТАННІ ДЛЯ ЇХ МОДЕЛЮВАННЯ ТЕОРІЇ МАСОВОГО ОБСЛУГОВУВАННЯ Розглянуто можливі підходи до методів розв’язку задач, що обумовленні спеціальними вимогами. Possible approaches to methods of the decision of problems which are fixed by special requirements are considered. Виходячи з аналізу сучасних можливостей систем зв’язку, та аналізу задач, що розв’язані і впроваджені у ці системи, можна стверджувати, що однією з актуальних задач, які потрібують дослідження, є задачі підвищення якісних параметрів процесів функціонування мережі на рівні структури системи зв’язку в межах регіону, що являються розподіленими у просторі, і можуть бути неоднорідними. Особливо актуальною є ця проблема у випадку,