Державний комітет зв'язку та інформатизації України

Національна академія наук України

Державний науково-дослідний інститут інформаційної інфраструктури

Березька Катерина Миколаївна

УДК 621.397.3

МОДЕЛЮВАННЯ ТА СИНТЕЗ СКЛАДНИХ

ЗОБРАЖЕНЬ СИМЕТРИЧНОЇ СТРУКТУРИ

01.05.02 – математичне моделювання та обчислювальні методи

Автореферат дисертації

на здобуття наукового ступеня кандидата технічних наук

Львів-2000

Дисертацією є рукопис.

Робота виконана у Державному науково-дослідному інституті інформаційної інфраструктури Державного комітету зв'язку та інформатизації і Національної академії наук України

Науковий керівник: Член-кореспондент НАН України, доктор технічних наук, професор

Грицик Володимир Володимирович,

Державний науково-дослідний інститут інформаційної інфраструктури, директор

Офіційні опоненти: доктор технічних наук, професор

Сіроджа Ігор Борисович,

Державний аерокосмічний університет

ім. М.Є.Жуковського «ХАІ», м.Харків, завідувач кафедри

доктор технічних наук, старший науковий співробітник

Яцимірський Михайло Миколайович

Державний університет «Львівська політехніка», доцент

Провідна установа: Інститут кібернетики ім. В.М. Глушкова НАН України, відділ керуючих машин і систем

Захист відбудеться «25» квітня 2000 р. о «15» год. на засіданні спеціалізованої вченої ради Д35.813.01 в Державному науково-дослідному інституті інформаційної інфраструктури (79601, м. Львів, вул. Тролейбусна, 11).

З дисертацією можна ознайомитись у бібліотеці Державного науково-дослідного інституту інформаційної інфраструктури (79601, м. Львів, вул. Тролейбусна, 11).

Автореферат розісланий « 1 » березня 2000 р.

Вчений секретар

спеціалізованої вченої ради

доктор технічних наук Бунь Р.А.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Симетрія це фундаментальна особливість природи, яка охоплює всі форми руху і організації матерії. На протязі всієї історії людства симетрія відігравала важливу роль в мистецтві, науці та інших видах інтелектуальної діяльності. Ще в 1891 р. Є.С.Федоровим була досліджена симетрія безконечних сітчатих орнаментів, яка вичерпується 17 групами, 16 з яких були описані К.Жорданом. Подальший розвиток науки про симетрію (симетричні групи перетворень) відображений в роботах Г.Вейля, Г.М.Кокстера, В.І.Вернадського, А.В.Шубнікова та ін. В 1967 р. А.М.Заморзаєвим була запропонована теорія Р - симетрії (точніше кольорової) одне з сучасних узагальнень в галузі науки про симетрію зображень.

Але, незважаючи на значну кількість досліджень, пов’язаних з методами моделювання, опису та синтезу складних зображень, ряд питань моделювання, генерування та архівування таких зображень вивчено недостатньо. Більше того, в розповсюджених універсальних графічних редакторах (CorelDRAW, Adobe Photoshop) відсутні функції моделювання та автоматичного генерування симетричних зображень.

Тому розробка цих питань має важливе прикладне значення з огляду дослідження та вивчення технічних систем обробки і розпізнавання зображень, вивчення живих організмів та ін. Вивчення складних зображень на основі симетрії пов’язане також з поняттям краси і гармонії сприймання зображення в мистецтві.

В роботі досліджено складні зображення на основі симетрії. Вперше розглянуто як зображення вишивки, які наділені складною структурою, а також алфавітом елементів, що відповідають кольору. Адже в зображенні-вишивці відображена колективна народна мудрість, пронесена через віки, яка служить своєрідним показником культури українського народу. В цьому виді мистецтва втілені неперевершені класичні зразки геoметричного орнаменту, в якому передано багатий рослинний та тваринний світи, краса Всесвіту.

Отже, актуальним є завдання розробки методу опису і моделювання та алгоритмів синтезу складних зображень, наділених симетричною структурою з метою моделювання та компактного зберігання їх в пам’яті ЕОМ. Ця задача має теоретичну та практичну цінність. Створення комп’ютерної системи (автоматичного редактора) дасть можливість здійснювати моделювання та економно зберігати великі масиви складних зображень-орнаментів, а також синтезувати нові зображення заданої симетричної структури. Розробка програмно-апаратної системи синтезу зображень вишивок дозволить відтворювати та досліджувати тонкі структури зображення на основі симетрії, красу і гармонію сприймання.

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в рамках Державної науково-технічної програми 6.02.02 з пріоритетного напрямку «Перспективні інформаційні технології і системи», затвердженої ДКНТ України (1992 р.), наступних науково-дослідних тем: «Дослідження можливостей розробки високоефективних моделей і алгоритмів обробки і класифікації одновимірних і двовимірних сигналів із складною структурою» (номер держ. реєстрації 81041804), «Дослідження і розробка ефективних методів та засобів виявлення і класифікації сигналів та прогнозування завад» (номер держ. реєстрації 76034505), «Розробка інформаційно-аналітичної системи супроводу інтеграції України в міжнародне співтовариство» (Національне агентство з питань інформатизації при Президентові України, 1998 р.).

Мета і задачі дослідження. Метою дисертації є розробка методу опису та моделювання складних симетричних зображень-орнаментів а також створення на його основі редактора зображень-орнаментів. Для досягнення поставленої мети необхідно вирішити наступні задачі:

·

· розробити мову опису структурних частин зображень-орнаментів;

· розробити алгоритми синтезу зображень-орнаментів;

· реалізувати алгоритми синтезу орнаменального зображення вишивки;

· реалізувати алгоритми редагування зображень вишивок.

Наукова новизна одержаних результатів.

·

·

·

· Запропоновано алгоритми синтезу федорівських груп перетворень зображень на основі осьових симетрій.

· Розроблено математичні моделі перетворень зображень для федорівських груп на площині та смузі в матричному вигляді, які лягли в основу синтезу алгоритмів генерування зображень-орнаментів.

· Отримано аналітичні вирази для коефіцієнтів стиснення (архівування) зображень-орнаментів, побудованих на основі запропонованого методу.

Практичне значення отриманих результатів. Практична цінність отриманих результатів полягає у тому, що: розроблені алгоритми опису, синтезу та архівування зображень-орнаментів дають можливість моделювати та автоматично генерувати складні симетричні зображення та ефективно зберігати складові зображення-орнаменту.

Запропоновані алгоритми реалізовані в наступних системах:

1)

1)

Особистий внесок здобувача. Усі теоретичні дослідження, розробка алгоритмічного і програмного забезпечення, основна частина практичних розробок виконані автором самостійно. В друкованих працях, опублікованих у співавторстві, автору належить метод опису складних зображень, алгебра мови опису та дослідження її властивостей [2, 3], алгоритми генерування груп перетворень зображень [5, 8, 10], участь в постановці задач, розробленні та програмуванні редакторів орнаментів і вишивок [12].

Апробація результатів дисертації. Результати дисертаційної роботи доповідалися на 4-ій українській конференції «Автоматика 97» (Черкаси, 1997), конференціях “Застосування обчислювальної техніки, математичного моделювання та математичних методів у наукових дослідженнях” (Львів, 1997, 1999), міжнародній науковій конференції «Сучасні проблеми математики» (Чернівці, 1998), міжнародній науковій конференції «Розробка та застосування математичних методів у науково-технічних дослідженнях» (Львів, 1998).

Структура і обсяг дисертації. Дисертаційна робота складається з вступу, чотирьох розділів, висновків. Вона викладена на 209 сторінках і включає 127 сторінок основного тексту, перелік використаних джерел із 112 найменувань на 8 сторінках, 8 додатків на 64 сторінках, ілюструється 9 рисунками та однією таблицею.

Публікації. За результатами виконаних досліджень опубліковано 12 робіт, із яких 7 статей у фахових наукових виданнях, 5 матеріали і тези конференцій, із них 6 одноосібні публікації.

ЗМІСТ ДИСЕРТАЦІЇ

У вступі обгрунтовано актуальність проведеної роботи, показано її зв`язок із науковими програмами, сформульовано мету, поставлено основні задачі дослідження, визначено наукову новизну та практичну цінність отриманих результатів.

У першому розділі показано фундаментальну роль симетрії в різних сферах життєдіяльності людини, проведено класифікацію української народної вишивки та зроблено аналіз існуючих методів аналізу та синтезу складних зображень.

В вузькому розумінні симетрія це дзеркальне відображення відносно площини в просторі (прямої на площині), в широкому розумінні властивість геометричної фігури, що характеризує деяку правильність її форми. Показано, що це фундаментальне поняття зустрічається в багатьох областях науки, мистецтва, а саме в математиці, фізиці, біології, хімії, техніці, кристалографії, архітектурі, образотворчому мистецтві, музиці, танцях, ювелірних роботах, вишивці, літературі, в типографському орнаменті та ін.

Проаналізовано українські народні вишивки з точки зору симетричної структури згідно умовного етнографічного районування території. Виділено локальні відмінності між специфічними техніками виконання, типовими орнаментальними мотивами і композиціями, поширеною колірною гамою і спільні характерні риси для вишивки кожного регіону (симетрична композиційна структура). Зроблено поділ мотивів на такі види: геометричні; рослинні; рослинно-геометричні; зооморфні. Проведено аналіз структурної композиції вишивальних орнаментів. Згідно неї орнамент поділено на підорнаменти, рапорти і мінімальні рисунки. Підорнамент це узор, що складається з ритмічно впорядкованих однакових елементів (побудований на одній групі перетворення). Підорнаменти в свою чергу діляться на рапорти. Рапортом називається мінімальна по площі область, якою можна покрити підорнамент використовуючи лише переноси. Рапорт в свою чергу ділиться ще на менші складові мінімальний рисунок (мотив, ). Мінімальний рисунок це найменша частина рапорту, з допомогою якої, проводячи перетворення симетрії, будується рапорт. Орнамент, зображений на рис. 1 складається з двох підорнаментів (позначення І і ІІ). Рапорт І-го підорнаменту 1 (обведено вузькою штриховою лінією), мінімальний рисунок (обведено широкою штриховою лінією) 2; рапорт ІІ-го підорнаменту 3, мінімальний рисунок 4.

Проаналізовано відомі методи представлення зображень, серед яких: прямі (матричні) найбільш прості, але зв’язані з великими затратами на обробку відеоданих; опис зображення за допомогою коефіцієнтів ортогонального перетворення перетворення Фур’є, Адамара (неефективно проводяться локальні операції над зображеннями); пірамідально-рекурсивні представлення зображення описується впорядкованою послідовністю декількох зображень різного розрізнення (виникають технічні труднощі при аналізі складних зображень); синтаксичні (структурні) методи представлення, які базуються на описі зображень складених об’єктів у вигляді ієрархічної структури.

Показано, що найбільш прийнятним для опису складних симетричних зображень є структурний метод, який дозволяє описувати зображення шляхом виділення мінімального рисунку та його перетворення за допомогою симетричних груп.

У другому розділі запропоновано метод опису та моделювання складних симетричних зображень, який полягає у виділенні із зображення-орнаменту структурних складових (мінімального рисунку, рапорту, підорнаменту) та їх математичного опису.

В роботі розглянуто зображення-вишивку, як об’єкт, надiлений структурою (рис.1,2). Позначивши повороти мотиву, зображеного на рис.2, у вигляді нескінченних множин: А={повороти проти годинникової стрiлки на , k=0,1,2,...}, В={повороти проти годинникової стрiлки на , k=0,1,2,...}, С={повороти проти годинникової стрiлки на , k=0,1,2,...}, D={повороти проти годинникової стрiлки на , k=0,1,2,...}, Г={A,B,C,D} і через a, b, c, І (оскільки І одиничний елемент групи поворотів мотиву) будь-який елемент з відповідних множин, то таблиця множення для групи поворотів Г має вигляд (табл. 1). Операція суперпозиції поворотів не виводить за межі множини Г. Мотив належить до циклічної групи Cn.

Таблиця 1

Таблиця множення групи поворотів Г

Множники | I | a | b | c

I | I | a | b | c

a

b

c | a

b

c | b

c

I | c

I

a | I

a

b

Використовуючи груповий підхід до зображення отримано формалізований запис орнаменту, який має наступний вигляд: z() орнаментне зображення на площині, де z є Z = { p1, p2, pm, pg, cm, pmm, pmg, pgg, cmm, p4, p4m, p4g}; j() орнаментне зображення на полосі, де j є J = { p1, p2, pm, pg, cm, pmm, pmg, pm, pmm} (позначення прийняті згідно з міжнародною системою позначень плоских кристалографічних груп).

Для опису мінімального рисунку () вишивки запропоновано наступну мову опису.

1. Кожен непохідний елемент помічено в двох різних точках головній г і хвостовій х (рис.3,а). Причому непохідні елементи дотикаються і накладаються тільки в головних чи хвостових точках.

2. Введено бінарні операції конкатенації (з'єднання):

- операція a + b (рис.3,б головна точка "a" дотикається до хвостової точки "b");

- операція a b (рис.3,в головна точка "a" співпадає з хвостовою точкою "b");

- операція a b (рис.3,г хвостова точка "a" дотикається до хвостової точки "b");

- операція a b (рис.3,д хвостова точка "a" співпадає з хвостовою точкою "b");

- операція a - b (рис.3,е головна точка "a" дотикається до головної точки "b");

- операція a b (рис.3,є головна точка "a" співпадає з головною точкою "b");

- операція a b (рис.3,ж головна точка "a" дотикається до головної точки "b" і хвостова точка "a" дотикається до хвостової точки "b".

3. Введено наступну унарну операцію:

визначається як переміна головної і хвостової точок.

4. Введено непохідні елементи:

а) a, b, c, d (рис. 4,а), причому a=b=c=d=1. Якщо а ланцюжок символів, то аn ланцюжок, що складається з n раз побудованого ланцюжка а.

б) "порожні" непохідні елементи pa, pb, pc, pd (рис. 4,б);

в) "несуттєві" непохідні елементи na, nb, nc, nd (рис. 4,в).

Граматика, що породжує речення в цій мові, є безконтекстною граматикою, для якої VN = {S, SF},

VT = {a} {+, , -, , , , , (, )},

a це будь-який непохідний елемент з вище названих,

P : S a, S (S & S), S (S), S SF, SF (SF & SF), SF (SF), & +, & , & -, & , & , & , & .

Як семантичну інформацію про непохідні елементи розглянуто множину ознак, яка потрібна для опису виділеного непохідного елементу. Семантична інформація про підобраз (допоміжний символ граматик) оцінюється по семантичній інформації непохідних елементів, що його складають.

Представлено семантичними функціями бінарні операції конкатенації (табл.2). Вираз ДОТ означає "дотикатися до", НАКЛ - "накладатися на".

Таблиця 2

Представлення бінарних операцій семантичними функціями

Ts (B) | Правило підстановки | Семантична функція

D1D  | B D1D    | х(B)=х(D1)

г(B)= г(D )

г(D1) ДОТ х(D )

D1  D  | B D1  D    | х(B)=х(D1)

г(B)= г(D )

г(D1) НАКЛ х(D )

D1  D  | B D1  D    | х(B)=х(D1)

г(B)= г(D )

х(D1) ДОТ х(D )

D1  D  | B D1  D    | х(B)=х(D1)

г(B)= г(D )

х(D1) НАКЛ х(D )

D1 D  | D1 D    | х(B)=х(D1)

г(B)= г(D )

г(D1) ДОТ г(D )  

D1  D  | B D1  D    | х(B)=х(D1)

г(B)= г(D )

г(D1) НАКЛ г(D )

1  D  | B D1  D  | х(B)=х(D1)

г(B)= г(D )

г(D1) ДОТ г(D ) 

х(D1) ДОТ х(D ).

Визначено алгебру, яка складається з деякої непустої множини непохідних елементів множина Е і послідовності визначених на Е операцій F={~, +, , -, , , , }.

Для даної алгебри виконуються наступні закони.

1.

(U1 U2)=( U2 U1);

(U1 U2)=(U2 U1); (U1 - U2) =(U2 - U1);

(U1 U2)=(U2 U1); (U1 U2)=(U2 U1).

2. Асоціативності для операцій +,

((U1 + U2) + U3) = (U1 + (U2 + U3));

((U1 U2) U3) = (U1 (U2 U3)).

3. Інверсії ( ( U)) = U.

4. Для операції справджуються наступні рівності:

((U1 + U2)) = ((U2) + (U 1)); ( (U1 U2)) = ( (U2) (U 1));

((U1 U2)) = ((U2) (U 1)); ( (U1 U2)) = ((U2) - (U 1));

((U1 U2)) = ((U2) (U 1)); ( (U1 - U2)) = ((U2) (U 1));

((U1 U2)) = ((U2) (U 1)).

Запропоновано рекурсивні алгоритми побудови та моделювання зображень-орнаментів для 7-и груп на полосі (J = { p1, p2, pm, pg, cm, pmm, pmg, pm, pmm}) і 12-и на площині (Z = { p1, p2, pm, pg, cm, pmm, pmg, pgg, cmm, p4, p4m, p4g}). За допомогою них структура зображень задається шляхом використання елементарного зображення (рапорту) і закону переходу на наступний рівень. Для груп перетворень на площині закон переходу на наступний рівень це переноси в напрямку X та Y, на смузі перенос в напрямку X. Елементарні зображення для площини мають вигляд:

;

;

;

;

;

;

;

;

;

;

;

,

де мінімальний рисунок, R, R1, R2 відображення, P, Q ковзні відображення, X , Y переноси, T, S повороти на 180 та 90.

Елементарні зображення для смуги мають вигляд:

;

;

;

;

;

;

.

Оскільки операція відображення відносно осі є основним видом симетрії, а всі інші (поворот, паралельний перенос, ковзне відображення) одержуються на її основі, то проаналізовано процес синтезу груп перетворень (підорнаментів) через відображення і отримано наступні результати. Нехай R1, R2, R3 відображення в гіпотенузі і катетах прямокутного рівнобедреного трикутника (рис. 5). Тоді множина груп Z представляється таким чином:

p4m R1, R2, R3;

p4g R2, R1 R3;

p4 R1 R3, R2 R3;

cmm R1, R3 R1 R3, R2 R3;

pgg R2 R1 R3 , R1 R3 R2;

cm R1, R2 R1 R3;

pg R2 R1 R3, R1 R2 R1 R3 R1;

pmg R1 R2 R1 R2 R 3, R1 R3 R1 R3;

p2 R2 R3, R1 R3 R1 R3, R1 R2 R3 R1;

pmm R2, R3, R1 R2 R1, R1 R3 R1;

pm R2, R1 R3 R1, R3 R1 R2 R1;

p1 R2 R1 R3 R1, R3 R1 R2 R1.

Аналогічно проаналізовано множину груп J.

Нехай R1, R2, R3 відображення в сторонах прямокутника (рис.6). Множина груп J має наступне представлення:

p1 R1 R3;

pg R1 R3 R2;

p1m R1, R3;

p2 R1 R2 , R3 R2;

pmg R1 R2 , R3;

pm R1 R3, R2;

pmm R1 , R2 , R3.

У третьому розділі розроблено підхід до синтезу груп перетворень через породжувальні перетворення, запропоновано алгоритми синтезу мінімального рисунку в різних базисах, спроектовано узагальнений алгоритм синтезу орнаментів.

На основі підходу до синтезу груп перетворень через породжувальні перетворення одержано наступні матриці перетворень для груп множини J, наведені в табл. 3 (x, y сторони прямокутників, що утворюють прямокутно-решітчату сітку).

Аналогічним чином отримано матриці перетворень для груп множини Z.

Таблиця 3

Групи смуги

Назва | Породжуючі перетворення в матричному вигляді

групи | I | II | III

p1

pg

p1m

p2

pmg

pm

pmm

Показано, що внаслідок мінімізації числа операцій над непохідними елементами синтез мінімального рисунку може відбуватися в наступних базисах: K={~, , }, L={~, , }, M={~, }. Більше того, K={~, , }, L={~, , } є повними базисами, а M={~, } є мінімальним базисом. В результаті доведено наступну теорему:

Теорема. Будь-яке зображення можна представити з допомогою множини непохідних елементів та набору операцій M={~, }. Більше того ці операції є незалежні.

Узагальнений алгоритм синтезу орнаментів складається з наступних етапів.

1.

Синтез мінімального рисунку відбувається в одному випадку на основі його алгебраїчної формули опису в іншому шляхом використання бази типових для даної орнаментальної області мінімальних рисунків. При цьому можливі два способи формування мінімального рисунку: детермінований та стохастичний. Використання детермінованого способу синтезу вимагає повного формалізованого опису мінімального рисунку. Стохастичний спосіб дозволяє шляхом використання генератора випадкових чисел із різними законами розподілу дискретних випадкових величин (Бернуллі, Пуассона, геометричного розподілу тощо) вибирати із відповідних множин (множини непохідних елементів, множина кольорів, множини довжин непохідних елементів, множини операцій над непохідними елементами) необхідний елемент з довжиною та кольором. При виборі унарної операції проходить автоматичне її виконання над сформованим ланцюжком елементів. В противному разі (бінарні операції) відбувається вибір другого ланцюжка елементів.

2. Формування груп перетворень зображень.

Формування груп перетворень здійснюється трьома способами:

a)

б) на основі осьових симетрій;

в) рекурсивним способом (як підгрупи груп переносів).

Утворення орнаменту із підорнаментів відбувається шляхом послідовного заповнення площини групами перетворень зображень, причому послідовність заповнення немає принципового значення і відбувається за рішенням людини-орнаментиста.

Приклад синтезу мінімального рисунку і групи перетворень наведено на рис.7-9. На рис. 7 мінімальний рисунок розкладено на непохідні елементи і показана конкатенація між ними. Рис. 8 демонструє мінімальний рисунок згенерований по формулі:

(c2 (~d3) + (~nd3) +(~d2) (~b7) + c4 +) ((~b5) c5) ((~b2) + (~a) + (~нa2) (~c4) + nd2 + d).

На рис. 9 представлено орнамент, що складається з одного підорнаменту і реалізований він по формулі :

p1m /5/: (c2 (~d3) + (~nd3) +(~d2) (~b7) + c4 +) ((~b5) c5) ((~b2) + (~a) + (~нa2) (~c4) + nd2 + d), де 5 число ітерацій (кількість рапортів, що присутні в орнаменті).

Дано оцінку величини коефіцієнтів стиснення симетричних зображень для різних варіантів (в .bmp та .txt (у вигляді формули опису) форматах) зберігання в пам’яті ЕОМ складових орнаменту. Нехай об’єм пам’яті для збереження мінімального рисунку в .bmp форматі, а об’єм пам’яті для збереження мінімального рисунку в .txt форматі. Тоді коефіцієнт стиснення мінімального рисунку рівний = .

Коефіцієнт стиснення для рапорту рівний

,

де кількість мінімальних рисунків в рапорті.

Коефіцієнт стиснення для підорнаменту рівний

,

де - кількість ітерацій (кількість рапортів).

Коефіцієнт стиснення для орнаменту рівний .

Спроектовано інформаційну модель побудови орнаменту, яка передбачає використання довідників мінімальних рисунків (необхідних для вибору варіантів формування підорнаментів орнаментистом). Розроблено інфологічну та даталогічну моделі бази даних забезпечують зручну підтримку довідників орнаментистом.

Завдяки використанню запропонованих алгоритмів синтезу орнаментів, досягнуто скорочення часу синтезу та суттєве зменшення об’єму памяті для їх зберігання.

У четвертому розділі описано розроблені редактор орнаментів та редактор вишивок, а також наведено результати синтезу і архівування складних орнаментальних зображень.

Редактор орнаментів дозволяє синтезувати складні зображення-орнаменти на основі аналітичних формул мінімального рисунку, підорнаменту та орнаменту. Разом з тим, розроблена програмна система дає можливість здійснювати архівування зображень шляхом виділення мінімального рисунку (формули в форматі *.txt або зображення в форматі *.bmp) та груп перетворень над ним, що здійснюється автоматизованим шляхом з участю людини-орнаментиста. Для наведеного на рис. 10 орнаменту об’єм пам’яті в форматі *.txt (об’єм формули) становить 671 байт, а об’єм пам’яті в форматі *.bmp рівний 315 Кб. Формула орнаменту має наступний вигляд (орнамент побудований в базисі операцій {~,}):

p4m (3; 4)/9/: nd(8,0) b(4,10) a(3,10) (~b(3,10)) (~a(2,10)) b(2,10) (~d(3,10)) b(4,10) c(8,10) (~nc(2,0)) (~a(5,10)) (~d(2,10)) a(2,10) (~c(2,10)) (~d(2,10)): 81, 81.

В останній формулі p4m позначення групи; (3, 4) координати першого елемента групи в площині з накладеною сіткою; 9 кількість рапортів групи; nd(8,0) b(4,10) ... формула мінімального рисунку показаного на рис. 11, де перше число в дужках код довжини непохідного елементу, друге код кольору; 81, 81 розмір сітки в пікселах по горизонталі і вертикалі, відповідно.

Залежність об’ємів пам’яті в форматах *.bmp від *.txt для мінімальних рисунків та підорнаментів приведені на рис 12,а і 12,б відповідно.

Спроектований програмно-апаратний комплекс створення та редагування вишивок дозволяє синтезувати самостійно різні вишивки для швейних машин фірми «BROTHER» моделей «PE-100» і «Super Galaxi». В склад комплексу входить пакет прикладних програм (редактор вишивок) та пристрій вводу-виводу інформації (програматор) для репрограмуючого картріджу. Редактор вишивок виконує наступнi функцiї: створення картинки для проектованої вишивки в форматі *.bmp; створення необхідних контурів для автоматичного заповнення областей стібками; автоматичне заповнення областей і обшивка контурів стібками із встановленими параметрами; редагування результатів автоматичного заповнення; ручне накладання стібків; створення шарів вишивки. Програматор призначений для виконання наступних функції: читання та запис даних із картріджу; визначення серійного номеру картріджу; стирання даних із картріджу; шифрування та дешифрування даних; здійснення захисту даних.

Отже, розроблені редактори орнаментів, вишивок та програматор дозволяють, відповідно, синтезувати орнаменти, перетворювати їх в масив стібків та програмувати для автоматичного вишивання на тканині.

У додатках наведено приклади зображень українських народних вишивок на смузі та площині, елементарні рисунки орнаментів та їх формули побудови, синтезовані орнаменти з відповідними математичними описами, роздрук програм редактора орнаментів, відповідна інструкція користувача та матеріали впровадження.

ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ ТА ВИСНОВКИ

1.

1.

1.

1.

1.

1.

1.

1.

1.

СПИСОК ОСНОВНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

1.

АНОТАЦІЯ

Березька К.М. Моделювання та синтез складних зображень симетричної структури. Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02математичне моделювання та обчислювальні методи. Державний науково-дослідний інститут інформаційної інфраструктури, Львів, 2000.

Дисертація присвячена опису, моделюванню та синтезу складних симетричних зображень. Розроблено метод опису та моделювання складних зображень, який базується на запропонованій мові опису структурних частин зображень-орнаментів та розроблених алгоритмах синтезу та моделювання груп перетворень.

Досліджено властивості операцій наведеної мови опису. Запропоновано алгоритми синтезу та моделювання груп перетворень зображень на основі осьових симетрій. Отримано аналітичні вирази для коефіцієнтів стиснення зображень, побудованих на основі структурного методу.

На основі розроблених алгоритмів спроектовано та впроваджено редактори орнаментів та вишивок, наведено результати генерування та архівації орнаментів.

Ключові слова: складне симетричне зображення, зображення-орнамент, симетрія, математичне моделювання, синтез, мова опису, архівація.

Березская Е.Н. Моделирование и синтез сложных изображений симметричной структуры. Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 математическое моделирование и вычислительные методы.Государственный научно-исследовательский институт информационной инфраструктуры, Львов, 2000.

Диссертация посвящена описанию, моделированию и синтезу сложных симметричных изображений.

Целью диссертационного исследования является разработка метода описания и моделирования сложных симметричных изображений и создание на его основе редактора орнаментов. Для достижения даной цели были решены следующие задачи:

·

· розработан язык описания структурных частей изображений-орнаментов;

· розроботаны алгоритмы синтеза сложных изображений, со симметричной структурой;

·

В работе показана фундаментальная роль симметрии в разных сферах жизнедеятельности человека (в науке, технике, искусстве, быту), раскрыта ее геометрическая сущность, предложено классификацию украинской народной вышивки и сделан анализ существующих методов описания и синтеза сложных изображений. Обосновано использования структурных методов описания сложных изображений.

В диссертации доказано, что преобразования над изображениями вышивки (вышивка - объект, наделенный структурой) образуют 12 групп преобразований на плоскости и 7 групп преобразований на полосе, которые относятся к соотвествующим федоровским группам.

Предложен метод описания и моделирования сложных симметричных изображений, который базируется на разработанном языке описания минимальных рисунков и алгоритмах синтеза подорнаментов (на основе синтеза групп преобразований). В основу построения языка описания сложных изображений положена бесконтекстная грамматика, построенная путем выделения непроизводных элементов и использования соответствующих правил их соединения. Исследованы свойства алгебры языка описания изображений.

Предложен рекурсивный подход к описанию групп преобразований, на основе которого формализованы раппорты групп.

Разработаны алгоритмы синтеза групп преобразований на плоскости и полосе путем использования композиции порождающих преобразований (смещение, поворот, скользящее и зеркальное отражения).

Получены алгоритмы синтеза минимальных рисунков в разных базисах операций. Показано, что вследствие минимизации числа операций над непроизводными элементами синтез минимальных рисунков можно производить в полном и минимальном базисах, в результате чего доказана теорема о минимальном базисе. Разработана информационная модель построения орнаментов, которая предусматривает использование справочников минимальных рисунков.

Предложен обобщенный алгоритм синтеза орнаментальных изображений, который состоит из следующих этапов: формирование минимального рисунка и формирование групп преобразований. Синтез минимального рисунка происходит в одном случае на основе его алгебраической формулы описания, в другом путем использования базы данных типовых для данной орнаментной области минимальных рисунков. При этом возможны два способа формирования минимальных рисунков: детерминированный и стохастический. Использование детерминированного способа синтеза требует полного формализованного описания минимального рисунка, стохастический способ формирует его по законам распределения дискретных случайных величин. Синтез групп преобразований происходит тремя способами: через порождающие преобразования, на основе осевых симметрий, и рекурсивным способом.

Дана оценка коэффициентов сжимания симметричных изображений для разных вариантов (в .bmp и .txt форматах) сохранения в памяти ЭВМ составляющих орнамента.

На основе разработаного метода программно реализован редактор орнаментов, который дает возможность, используя аналитические формулы минимальных рисунков, подорнаментов и орнаментов, синтезировать сложные орнаментные изображения. Вместе с тем созданная программная система дает возможность проводить архивацию изображений путем выделения минимального рисунка и групп преобразований над ним.

Спроектированный программно-аппаратный комплекс создания и редактирования вышивок дает возможность самостоятельно синтезировать различные вышивки для швейных машин фирмы «BROTHER» моделей «PE-100» и «Super Galaxi». В состав комплекса входит пакет прикладных программ (редактор вышивок) и устройство ввода-вывода информации (программатор) для репрограммируемого картриджа.

Таким образом, разработанные редакторы орнаментов, вышивок и программатор дают возможность, соответственно, синтезировать орнаменты, преобразовывать их в массив стежков и программировать для автоматического вышивания на ткани.

Ключевые слова: сложное симметричное изображение, изображение-орнамент, симметрия, математическое моделирование, синтез, язык описания, архивация.

Berezka K.M. Modelling and synthesis of complex pictures of symmetrical structure. - Manuscript.

Dissertation for the candidate degree of technical sciences in speciality 01.05.02 - mathematical modeling and numerical methods. - The State Scientific and Research Institute of Information Infrastructure, Lviv, 2000.

The dissertation is dedicated to the description, modeling and synthesis of complex symmetrical pictures. Developed method of depicting and modeling of complex pictures is based on the suggested language for depicting of structural parts of ornamental pictures and created algorithms of synthesis and modeling the transformation groups.

The properties of algebra of the given language are investigated. Algorithms of synthesis and modeling of transformation groups of pictures on the basis of axial symmetry are suggested. Analitical expressions for coefficients of compressing pictures built on the basis of structural method were obtained. Editors of ornaments and embroideries are projected and introduced on the basis of developed algorithms.

The results of generating and archivation of ornaments are given.

Key words: complex symmetrical pictures, ornamental picture, symmetry, mathematical modeling, synthesis, the language of description, archivation.

Підп. до друку 28.02.2000. Формат 29.7421/4

Папір офсетний. Друк офсетний. Гарнітура Times.

Тираж 100 прим. Зам. №67.

Віддруковано в СМП «ТАЙП»

46004, м.Тернопіль, вул. Чернівецька, 44б.

Тел.: 22-61-61