Інформаційні технології пошуку та зберігання даних про графічні об’єкти на основі їх семантики
Методи визначення повноти та достатності словника графічних елементів, семантичної значущості та суперечності елементів опису різних об’єктів. Організація пошук даних про графічні об’єкти, з використанням алгоритму фільтрації їх семантичних описів.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | автореферат |
| Язык | украинский |
| Дата добавления | 28.08.2015 |
| Размер файла | 121,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Національний університет "Львівська політехніка"
УДК 004.424.6
05.13.06 - інформаційні технології
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата технічних наук
інформаційні технології пошуку та зберігання даних про графічні об'єкти на основі їх семантики
Чаплагін Микола Петрович
Львів - 2008
Дисертацією є рукопис
Робота виконана у Національному університеті "Львівська політехніка" Міністерства освіти і науки України
Науковий керівник - доктор технічних наук, доцент Медиковський Микола Олександрович, Національний університет "Львівська політехніка" Міністерства освіти і науки України, професор кафедри автоматизованих систем управління
Офіційні опоненти:
- доктор технічних наук, професор Воробель Роман Антонович, Фізико-механічний інститут ім. Г.В. Карпенка Національної академії наук України, завідувач відділу обчислювальних методів і систем перетворення інформації
- кандидат технічних наук, доцент Шеховцов Анатолій Вікторович, Херсонський національний технічний університет Міністерства освіти і науки України, професор кафедри інформаційних технологій
Захист відбудеться "4" липня 2008 р. о 16:00 годині на засіданні спеціалізованої вченої ради Д 35.052.14 при Національному університеті "Львівська політехніка" за адресою: 79013, м. Львів, вул. С.Бандери, 12.
З дисертацією можна ознайомитися у науково-технічній бібліотеці Національного університету "Львівська політехніка" (79013, м. Львів, вул. Професорська,1)
Автореферат розісланий "03" червня 2008 р.
Вчений секретар спеціалізованої вченої ради, кандидат технічних наук, доцент А.Є. Батюк
Анотації
Чаплагін М.П. Інформаційні технології пошуку та зберігання даних про графічні об'єкти на основі їх семантики. Рукопис. Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю -05.13.06 - інформаційні технології, Національний університет "Львівська політехніка", 2008.
Дисертація присвячена питанням організації пошуку даних про графічні об'єкти у сховищі даних на основі їх семантики для потреб оператора АСУ та розробки методів зберігання таких даних. У дисертації сформульовано основні підходи до вирішення проблеми зменшення потоків даних у системі управління потоками даних, та організації пошуку графічних об'єктів їх заміною даними про графічні об'єкти. Розроблено метод подання даних про графічні об'єкти, метод визначення повноти та достатності словника графічних елементів, метод визначення семантичної значущості та семантичної суперечності елементів опису графічних об'єктів. Сформовано словник графічних елементів, серед яких визначено лінію, криву, коло, "майже" коло, трикутник, "майже" трикутник, чотирикутник, "майже" чотирикутник, багатокутник, "майже" багатокутник. Такий словник дозволяє організувати швидкий та ефективний пошук даних про графічні об'єкти, з використанням розробленого алгоритму фільтрації семантичних описів графічних об'єктів. Розроблений метод подання даних про графічні об'єкти дозволяє зменшити розмір файлів, що передаються між блоками системи для подальшої обробки, до 10 разів. Ефективність першого семантичного фільтра наближається до 90%, в той же час другий семантичний фільтр визнаний неефективним. Використання в алгоритмі пошуку тільки першого та третього семантичних фільтрів дозволило зменшити час пошуку в два рази, без втрати результату.
Ключові слова: інформаційна технологія, автоматизована система управління, пошук графічних об'єктів, семантична значущість.
Chaplahin M.P. Information technologies of search and storage of data about graphic objects based on their semantic. -Manuscript.
The dissertation for the nomination to a Philosophy Doctor scientific degree (Engineering) in specialty 05.13.06 - the information technologies, National University "Lvivska politechnika", Lviv, 2008
Dissertation theme is data about graphic objects storage methods development and semantic based search of data about graphic objects organization for automated system operator needs. In dissertation formulated basics decisions of data flow decrease issue in data flow control system, and graphic objects search organization using they replacement by data about graphic objects (DGO). Also in dissertation developed DGO representation method, determination of semantic graphic object dictionary entirety and sufficiency method, determination semantic value and semantic divisiveness of graphic object description elements method. Graphic elements dictionary developed, with selecting elements: line, curve, circle, fuzzy circle, triangle, fuzzy triangle, quadrangle, fuzzy quadrangle, polygon, fuzzy polygon. This dictionary allows quick and effective search for DGO organization, using developed graphic objects semantic definition filtration algorithm. Developed DGO representation method allows decrease file size that used in transition within system communication lines, about 10 times. First semantic filter efficiency is up to 90%, but second semantic filter efficiency found insufficient. Experiments prove, that using only first and third semantic filters in search procedures decreases search time 2 times without affecting final search result.
Keywords: information technology, automatic management system, graphic objects search, semantic value.
Чаплагин Н.П. Информационные технологии поиска и хранения данных про графические объекты на основе их семантики. Рукопись.
Диссертация для получения научной степени кандидата технических наук по специальности 05.13.06 - информационные технологии, Национальный университет "Львовская политехника". 2008
В диссертации рассматриваются вопросы разработки методов хранения данных про графические объекты в хранилище данных для потребностей оператора АСУ потоками данных. В диссертации сформулированы основные подходы к решению проблемы уменьшения потоков данных в системах управления потоками данных, и организации поиска графических объектов используя их замену данными про графические объекты. Разработан метод представления данных про графические объекты, метод определения полноты и достаточности словаря графических элементов, метод определения семантической значимость и семантической противоречивости элементов описания графических объектов. Сформировано словарь графических элементов, среди которых выделены линия, кривая, круг, "почти" круг, треугольник, "почти" треугольник, четырёхугольник, "почти" четырёхугольник, многоугольник, "почти" многоугольник. Такой словарь даёт возможность определить семантическую значимость каждого элемента описания графического объекта, а также семантическую значимость описания графического объекта в целом. Такое представление данных про графический объект также позволяет организовать его повторное использование без проведения дополнительных вычислений, поскольку его можно сохранить в файловой системе хранилища данных в файле в формате XML. Хранение файлов семантических данных про графический объект позволяет организовать быстрый и эффективный поиск данных про графические объекты, с использованием разработанного алгоритма семантической фильтрации описей графических объектов. Процесс поиска представляет собой последовательное сравнение семантического описания запроса-образца с каждым семантическим описанием в хранилище. Поскольку для каждого графического объекта можно выделить три уровня детализации, то процесс сравнения также разделён на три этапа в зависимости от параметров сравнения объектов. Первый фильтр определяет совпадение подмножеств элементов образца и анализируемого описания. Второй семантический фильтр сравнивает семантическую значимость каждого набора элементов из описания. И третий семантический фильтр сравнивает семантическую значимость элементов соответствующих типов. В каждом следующем этапе принимают участие только те описания, которые прошли предыдущий фильтр. Разработанный метод представления данных про графические объекты даёт возможность уменьшить размер файлов, которые передаются между блоками системы для дальнейшей обработки почты в 10 раз. Эффективность первого семантического фильтра приближается к 90%, в то же время второй семантический фильтр признан неэффективным. Использование в алгоритме поиска только первого и третьего семантических фильтров позволило уменьшить время поиска в два раза без ухудшения результата.
Ключевые слова: информационная технология, автоматизированная система управления, поиск графических объектов, семантическая значимость.
Загальна характеристика роботи
Актуальність теми. Розвиток і запровадження інформаційних технологій стримується значними затратами часу, та інших ресурсів систем для розміщення, пошуку і відображення даних. Той факт, що людина-оператор більшу частину інформації отримує через зоровий апарат, зумовлює переважне використання графічних об'єктів у інтерфейсі машина-людина. Для прийняття рішень оператору потрібні лише ті графічні об'єкти, які забезпечують розв'язання поставленої задачі, що вимагає організувати пошук потрібних графічних об'єктів серед всієї множини у сховищі даних. Порівняння заданого фрагменту з отриманим результатом пошуку проводять на стороні користувача з використанням графічного подання даних, що зумовлює додаткові затрати часу. Особливі ускладнення виникають при опрацюванні даних про графічні об'єкти, оскільки кожне зображення можна охарактеризувати за різними критеріями. Крім того, постійне зростання обсягів інформації, при незмінних параметрах інстальованої автоматизованої системи управління потоками даних, зумовлює зниження її ефективності.
Вирішення задачі зменшення потоків даних про графічні об'єкти здійснювалося, в основному, шляхом розроблення форматів кодування та компресії [М. Барнслі], особливо ефективні з яких використовують методи статистичного ущільнення (компресії без втрат) [А. Жакуін] та врахування психовізуальних і психофізичних властивостей сприйняття мультимедійної інформації людиною [С. Смейл, Д.С. Ватолін] Проте, за реалізацією, це скоріше екстенсивний, ніж інтенсивний шлях вирішення проблеми зменшення потоків даних між окремими вузлами системи.
Значний внесок у вирішення проблем оброблення графічних зображень зробили цілий ряд зарубіжних та вітчизняних вчених Б.К. П. Хорн, А. П'ю, А.Г. Івахненко, Є.П. Путятін, В.Г. Кожем'яко, В.В. Лукін, С.А. Башкіров, Г. Фреге, та інші, в роботах яких визначені критерії оброблення та подальшого пошуку даних різного характеру і окреслені способи оцінювання якості пошуку. Розроблені ними принципи, методи і засоби семантичного опису та аналізу графічного об'єкту передбачають участь оператора на етапі попереднього оброблення, тому реалізація їх вимагає додаткових досліджень умов застосування в автоматизованих системах для підвищення ефективності роботи.
Аналіз відомих результатів показує, що суттєвого спрощення розв'язання окремих задач зберігання та пошуку даних, в тому числі про графічні об'єкти, можна досягти шляхом їх структуризації в сховищах з використанням для цього особливим чином створеного семантичного опису. Такі методи практично не застосовуються для організації пошуку даних через недостатність системних досліджень способів опису та технологій застосування.
Тому перспективним шляхом вирішення вказаної задачі є застосування методів інтелектуалізації систем зберігання та пошуку графічних даних з використанням логіко-математичного опису їхньої семантики, що забезпечує удосконалення методів зберігання, зменшення обсягів передавання даних, і, тим самим, підвищення ефективності автоматизованих систем.
У зв'язку з цим, розроблення інформаційної технології пошуку та зберігання даних про графічні об'єкти з використанням їх семантики і вдосконалення методів та алгоритмів інтелектуалізації АСУ опрацювання даних є актуальною науковою задачею.
Зв'язок роботи з науковими програмами планами і темами. Дисертаційна робота безпосередньо пов'язана з планами науково-дослідних робіт Національного університету "Львівська політехніка". Окремі етапи виконано в межах держбюджетної науково-дослідної роботи кафедри автоматизованих систем управління "Нейромережні технології класифікації лексико-семантичної інформації для систем дистанційної освіти (СДО)" 2007-2008 рр. № державної реєстрації 0107U001115. Участь автора полягає у розробленні алгоритму реалізації семантичного опису вмісту графічних об'єктів та способу його зберігання у файловій системі, методу та алгоритму оцінювання семантичної значущості вмісту зображень, методу пошуку графічних об'єктів на основі їх семантики.
Метою роботи є розроблення інформаційної технології зберігання та пошуку графічних об'єктів у сховищах даних із застосуванням методів і алгоритмів інтелектуалізації автоматизованої системи опрацювання даних на основі семантики графічних об'єктів.
Для досягнення поставленої мети вирішено такі задачі:
- проведено класифікацію відомих способів організації пошуку графічних об'єктів за їх алгоритмами;
- досліджено способи пошуку (фільтрації) графічних об'єктів з використанням семантичного аналізу вмісту об'єкта;
- обґрунтовано ефективне застосування засобів математичної логіки і формальних граматик для визначення семантичної значущості графічних примітивів;
- розроблено засоби визначення ознак семантичної значущості вмісту графічних об'єктів;
- розроблено метод оцінювання ефективності процесу зберігання та пошуку даних про графічні об'єкти;
- розроблено структуру інтелектуалізованої автоматизованої системи зберігання та пошуку графічних даних, в якій реалізовано семантичний пошук вмісту графічних об'єктів.
Об'єктом дослідження є процеси зберігання та пошуку даних про графічні об'єкти в сховищах.
Предметом дослідження є методи та алгоритми зберігання та пошуку даних у сховищі на основі семантичного аналізу вмісту графічного об'єкта.
Методи дослідження. Використано методи математичної логіки для розроблення алгоритмів пошуку даних про графічні об'єкти, методи формальних граматик для визначення правил зберігання і пошуку графічних об'єктів та методи комп'ютерного моделювання для дослідження ефективності нових інформаційних технологій пошуку даних про графічні об'єкти з використанням семантичного аналізу їхнього вмісту.
Наукова новизна отриманих результатів
В роботі отримано такі нові наукові результати:
- розроблено спосіб пошуку графічних об'єктів на підставі оцінювання семантичної значущості та несуперечності їх елементів для побудови автоматизованих систем опрацювання графічних даних;
- удосконалено метод побудови семантичного словника для опису вмісту графічних об'єктів з використанням множини графічних примітивів, що дає можливість визначити величини семантичної значущості окремих фрагментів;
- визначено характеристики семантичних властивостей фрагментів графічних об'єктів через параметри їх взаємного розташування, що дозволяє оцінити семантичне значення вмісту графічного об'єкта;
- розроблено метод аналізу процесу зберігання та пошуку даних про графічні об'єкти із врахуванням їх семантичних параметрів і функціональних залежностей між параметрами сховища, що дає можливість оцінити ефективність пошуку.
Практичне значення одержаних результатів. Розроблена інформаційна технологія інтелектуалізації АСУ пошуком графічних об'єктів на основі їх семантичного аналізу забезпечує можливість реалізувати програмні засоби семантичного аналізу та пошуку, а алгоритми семантичного контролю окремих фрагментів графічних об'єктів та об'єктів у цілому дозволяють виявляти найбільш семантично значимі для розв'язування даної задачі графічні об'єкти і підвищити ефективність пошуку, зменшити час доставки і їх графічної візуалізації.
Застосування такої інформаційної технології дозволяє вдосконалити процеси картографування, прив'язку об'єктів до місцевості (GPS), наприклад, в містобудуванні, верифікацію зображень та їх захист. Наукові результати та елементи програмного забезпечення використано при розробленні Управлінням земельних ресурсів м. Львова інформаційно-аналітичної системи моніторингу змін у Державному земельному кадастрі.
Отримані результати використовуються у навчальному процесі кафедри АСУ Національного університету "Львівська політехніка" та землевпорядного факультету Львівського державного аграрного університету. Зокрема, це стосується: аналізу та класифікації методів пошуку графічних даних та даних про графічні об'єкти, способу зберігання даних про графічні об'єкти доповнених їх семантичним описом, методу семантичної фільтрації об'єктів з використанням їх семантичної значущості, системного аналізу методів пошуку даних про графічні об'єкти та обґрунтування способів їх застосування для рішення задач картографування, алгоритму розроблення опису картографічних матеріалів з використанням їх простих складових, що зведені у словник семантичного опису картографічного матеріалу.
Особистий внесок здобувача. Основні наукові результати теоретичних і практичних досліджень, викладені в дисертації, одержані автором особисто. У друкованих працях, опублікованих у співавторстві, дисертанту належать: формулювання задач, розроблення методів досліджень [4,7,8], розроблення методу створення семантичного словника [6], розроблення методу семантичного оцінювання вмісту графічного об'єкта [5,7], розроблення методу пошуку даних про графічні об'єкти з використанням аналізу їхньої семантичної значущості [5,7], комп'ютерне моделювання [7,8], а також оцінювання ефективності результатів досліджень [8].
Апробація результатів. Основні результати досліджень були представлені і всебічно обговорені на таких науково-технічних конференціях:
1. Науково-методична конференція "Сучасні проблеми телекомунікацій і підготовка фахівців в галузі телекомунікацій - 2005", Львів, 2005.
2. Міжнародна науково-технічна конференція "Комп'ютерні науки та інформаційні технології" (CSIT-2006), Львів, 2006.
3. IX International Conference CADSM "The expirience of designinng and Application of CAD Systems in Microelectronics", Львів-Поляна, 2007.
4. Науково-практична конференція "Сучасні проблеми телекомунікацій і підготовка фахівців в галузі телекомунікацій - 2007", Львів, 2007.
5. XXVI Науково-технічна конференція "Моделювання", ІПМЕ, Київ, 2007.
Публікації. Результати дисертаційної роботи опубліковано в 13 наукових працях, у тому числі 8 статей у фахових виданнях згідно з переліком ВАК України та у 5 збірниках праць науково-технічних конференцій.
Структура і обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, списку використаних джерел (115 найменувань) та додатків.
Загальний обсяг роботи 170 сторінок, з яких 143 сторінки основного тексту.
Основний зміст роботи
У вступі обґрунтовано актуальність розроблення інформаційних технологій зберігання та пошуку графічних даних. Сформульовано мету і задачі досліджень, наукову новизну і практичне значення отриманих результатів. Подано відомості про особистий внесок автора, апробацію результатів роботи та публікації.
У першому розділі проведено дослідження стану задачі підвищення ефективності систем обробки даних про графічні об'єкти. Показано її нетривіальність, високу затратність розробки рішень та реалізації, можливість, в більшості випадків, оцінити роботу відомих систем лише посередньо, за результатами експлуатації готових програмних засобів.
Здійснено класифікацію відомих технологій роботи з графічними даними залежно від поставленої мети. Показано, що задача є важливою, оскільки графічні дані займають не тільки значну частину серед даних, якими оперує система, але займають і значні об'єми пам'яті системи, а тому використовують значні ресурси під час оброблення.
Оскільки процес опрацювання і аналізу графічного об'єкта вимагає гнучкості у підходах і оцінках, застосовуються переважно менш формалізовані методи. З цієї точки зору перспективними методами пошуку є методи індексації графічних об'єктів словами природної мови, як найменш формалізовані. Ці методи дозволяють врахувати вміст зображення, оскільки кожному графічному об'єкту присвоюється певне ключове слово чи словосполучення. В подальшому пошук відбувається серед присвоєних словесних індексів. Проте, основна перевага методу природного індексу є і його основним недоліком, оскільки індекси формуються на основі суб'єктивного досвіду оцінювача, і тому недостатньо достовірні, повні і ефективні.
Аналіз літературних джерел із вказаної проблематики показує перспективність застосування методів на основі побудови сигнатур для організації пошуку графічних об'єктів. Проте вони описують лише одну з характеристик зображення - колір, текстуру та інші. Оскільки текстура багатьох видів графічних зображень, та їх кольорове наповнення дуже подібні (наприклад, на аерофото), тому для організації ефективного пошуку вимагається побудова сигнатур за цілим рядом ознак, і їх комбінація, що вимагає аналізувати декілька рівнів вмісту зображення, тобто його семантику.
Тому дослідження та розв'язання задачі розроблення інформаційної технології зберігання та пошуку графічних об'єктів з використанням їх семантики та вдосконалення методів і алгоритмів інтелектуалізації АСУ зберігання та пошуку графічних даних є актуальними.
У другому розділі розроблено теоретичні основи опрацювання та аналізу графічних об'єктів з використанням апробованого логіко-математичного апарату семантичного аналізу, а також описана побудова основ інформаційної технології організації, зберігання та пошуку графічних об'єктів за вмістом, що використовує пошук відповідного семантичного опису заданого фрагменту (опис семантики) в масиві описів графічних об'єктів, якими доповнено формат зберігання графічного об'єкта.
Встановлено, що основою семантичного аналізу вмісту графічного об'єкту є такі фактори: наявність системи інтерпретації та правил її використання; гомоморфізм між правилами використання системи інтерпретації та подання графічних об'єктів; семантична несуперечність системи опису графічних об'єктів.
Складовими частинами системи інтерпретації є: семантичний словник системи графічних об'єктів ; семантичне середовище ; система правил використання середовища.
Семантичний словник є структурованою множиною атрибутів, примітивів та елементів, які використовуються для опису графічних об'єктів, в якій нижній рівень структуризації - призначення ключових елементів у словнику, а верхній - виродження семантичного словника в набір фрагментів графічних об'єктів.
Для більш детальної структуризації словник розбито на підмножини, які об'єднують набори атрибутів, або примітивів з близькими значеннями семантичної значущості. Такі підмножини незалежні від конкретної інтерпретації набору елементів . Тоді структура словника має вигляд:
,
де, відповідно, множини: - ключових елементів , - контекстно обумовлюючих елементів , - семантичної значущості елементів, m - число елементів.
Оскільки словник вміщає лише термінологічну базу елементів опису об'єкта даного формату, то число елементів в інтерпретації складається з числа елементів одного рядка і підсумовується з числом елементів інтерпретаційного розширення для елемента :
,
де - функція перерахунку числа елементів інтерпретаційного опису та - елементів опису, яка має інтерпретацію .
Якщо діапазон семантичної значущості елемента в множині задати інтервалом числових величин
,
то структура семантичного словника матиме вигляд:
,
де "" - сума за модулем два.
Для подальшого аналізу важливою є структура опису, яка оперує наборами елементів (сукупністю семантично визначених атрибутів, або примітивів)
, де .
З розробленого для аналізу вмісту об'єктів словника із структурою , сформовано ієрархічні залежності між наборами елементів залежно від їх семантичних значущостей. Тобто, визначено контрольні набори для розв'язування задач аналізу вмісту графічного об'єкту.
Визначено умови семантичної несуперечності та семантичної повноти фрагмента будь-якого графічного об'єкта, оскільки ці дві характеристики є основою формування наборів елементів для структур та , де кожне є набором елементів, який використовується в графічному об'єкті.
В процесі аналізу для будь-якого об'єкту з необхідно знайти величини значень семантичної значущості кожного елемента, тобто визначити для всіх елементів об'єкта . Для цього розбиваємо всі набори елементів на підмножини у відповідності з прийнятою в структурою та знаходимо для кожного набору його семантичну значущість:
,
де - семантична значущість елемента в контексті набору елементів .
Величиною семантичної суперечності є різниця між значенням функції і значенням функції у відповідній позиції графічного об'єкту:
.
Якщо , то семантична суперечність у відповідному місці графічного об'єкту відсутня. Тоді середня величина семантичної суперечності по всьому графічному об'єкту визначається з виразу:
, для .
Розроблений опис семантичної інтерпретації із використанням формальних граматик є підставою для розроблення нового підходу при реалізації методів семантичного аналізу графічних об'єктів з метою розв'язання задач пошуку графічної інформації за вмістом.
У третьому розділі розроблено і досліджено метод семантичного аналізу вмісту графічних об'єктів.
Розроблено структуру семантичної моделі об'єкту з виділенням на ньому графічних примітивів, присвоєння їм символьних позначень і використання їх як умовний алфавіт, з подальшою побудовою моделі семантичного опису зображення та його фрагменту (рис.1).
Для виміру смислового навантаження даних, тобто їх об'єму на семантичному рівні, використано тезаурусну міру, яка пов'язує семантичні властивості інформації із здатністю користувача сприймати отриману інформацію. В дисертаційній роботі тезаурус складається з графічних примітивів.
Виділено основні типи графічних примітивів зображення, та створено на їх основі модель зображення, яка є гнучкою, не залежить від масштабування та позиціонування зображення, кольору виконання примітиву (якщо не задано особливі умови). Обґрунтовано використання типових середовищ з існуючих програмних продуктів оброблення графічних примітивів: line, curve, circle, fuzzy circle, triangle, fuzzy triangle, quadrangle, fuzzy quadrangle, polygon, fuzzy polygon. З метою більш детального семантичного опису графічних об'єктів графічні примітиви за ознакою неперервності їх контурів поділено на два типи. Тим самим розроблено основу для створення семантичного словника з даної предметної області і побудови інтелектуальної системи пошуку графічних об'єктів на основі семантичного аналізу.
Виділивши графічні примітиви, як елементи (elements), кожному з них, залежно від форми (shape), присвоєно значення (value), і, отже, отримано їх семантичний опис:
Семантична значущість, визначена за алгоритмом, схема якого наведена на рис. 2, зберігається у tags <Value></Value>.
Словник може бути розширений введенням атрибутів елементів: колір наповнення, колір лінії. Для зменшення навантаження на СУБД сховища даних семантичний опис доцільно зберігати як файл у файловій системі. Причому існують готові методи і алгоритми структуризації даних всередині файла для більшої зручності і швидкості використання, наприклад, засоби XML. Його застосування дозволяє записувати дані у файл у структурованому вигляді, орієнтованому на конкретну предметну область і тип задач. Крім того, у сучасних програмних системах вбудовано засоби автоматизації роботи з структурами XML, що дозволяє зменшити час розроблення програмного забезпечення і пришвидшує його роботу. Таким чином, у АСУ потоками даних семантичний опис графічного об'єкта зберігається як файл у форматі XML, опис кожного об'єкту зберігається в окремому файлі.
Розроблений метод семантичного аналізу графічного об'єкту, що полягає у визначенні семантичної значущості елементів опису графічного об'єкта (рис. 2), забезпечує можливість реалізації розробленого підходу до синтезу та імплементації структури елементів АСУ зберігання та пошуку графічних об'єктів.
Рис.2. Схема алгоритму визначення семантичної значущості графічних примітивів
У четвертому розділі проведено дослідження елементів інтелектуалізації АСУ зберігання та пошуку графічних даних на основі їх семантики. графічний семантичний словник алгоритм
Розроблено структуру сховища даних, в якому: графічні об'єкти зберігаються як файли; семантичний опис зберігається як файл у форматі XML; опис кожного об'єкту зберігається в окремому файлі; в базі даних зберігається додаткова інформація про ці об'єкти, така як час надходження об'єкту у сховище, оригінальна назва, шлях до об'єкта у сховищі.
Структура таблиці MySQL: ім'я графічного файлу у сховищі; шлях до графічного файлу у сховищі; ім'я оригінального файлу; час запису об'єкта у сховище; ознака існування семантичного опису для графічного об'єкта; ім'я файлу опису; шлях до файлу семантичного опису у сховищі, чим забезпечено швидку і достовірну ідентифікацію графічного об'єкта за описом.
Схема алгоритму оброблення нових надходжень графічних об'єктів у сховище подано на рис.3.
Рис.3. Схема алгоритму оброблення нових надходжень
Процес пошуку даних про графічні об'єкти відбувається у блоці аналізу семантичного запиту (рис. 4).
Рис.4. Блок аналізу семантичного запиту
Семантична значущість елементів визначається за таким алгоритмом.
Для множини примітивів графічного об'єкта , де у - кількість графічних примітивів графічного об'єкта, в якому присутні примітиви з словника P = , тоді , де k - кількість типів примітивів, що присутні в графічному об'єкті.
Ранг примітиву R визначається числом подібних типів примітивів об'єкта:
,
де m - число примітивів типу у об'єкті. Тоді, попередня семантична значущість х кожного графічного примітиву:
. (1)
Множину графічних примітивів об'єкта розбиваємо на набори елементів за ознакою відстані між елементами. Виконуємо перерангування об'єктів всередині наборів графічних елементів:
,
де к - номер набору елементів, - ранг і-го типу графічного примітиву в k-ому наборі елементів, - кількість типів примітивів у наборі елементів, - кількість примітивів у наборі.
Тоді семантична значущість кожного елемента набору буде:
. (2)
У випадку, якщо у наборі елементів є лише один тип графічних примітивів, або якщо порядок рангування не змінився, тобто:
, (3)
то семантична значущість не змінюється.
У випадку, якщо порядок порушено, то семантична значущість елемента коректується, і визначається як середнє арифметичне між відповідними семантичними значеннями:
, (4)
де - величина корекції семантичної значущості в залежності від кількості графічних примітивів у графічному об'єкті.
У випадку, коли кількість графічних примітивів у графічному об'єкті незначна, семантична значущість кожного окремого примітиву зростає:
(5)
Семантична значущість набору елементів визначається як сума семантичних значущостей, тобто
, (6)
де у - число графічних примітивів в об'єкті.
Трирівнева деталізація даних про графічний об'єкт (об'єкт, набір елементів, елемент) зумовлює необхідність розробити і дослідити ефективний інструментарій для побудови їх пошуку. Процес пошуку є процесом виділення, або фільтрації, об'єктів, що відповідають запиту, від інших. Аналіз семантичних описів графічних об'єктів показує, що таких фільтрів повинно бути три. Тому пошук об'єктів за їх семантичною значущістю слід реалізувати за допомогою трьох семантичних фільтрів, що забезпечить зменшення потоків даних в системі.
Перший, найбільш загальний фільтр, який мусить відкинути найбільше число зайвих графічних об'єктів, це вмістовий фільтр. В ньому перевіряється наявність всіх графічних примітивів першого порядку запиту у графічному об'єкті за формулою:
(7)
де - запит, - об'єкт, що аналізується, - число типів графічних примітивів, - кількість графічних примітивів i-го типу у запиті,
- число графічних примітивів i-го типу у описі графічного об'єкта, що перевіряється.
Другий семантичний фільтр призначений для визначення семантичної суперечності між наборами елементів. Різниця між найменш суперечним набором елементів досліджуваного об'єкта і запиту дає суперечність між наборами:
, (8)
де , h - кількість наборів елементів об'єкта; , де g - кількість наборів елементів запиту.
В результаті, семантична суперечність між запитом та об'єктом, що аналізується, визначається як:
, (9)
де n - число наборів.
Третій семантичний фільтр призначений для визначення семантичної суперечності між окремими елементами однакових типів. Мінімальні суперечності для елементів однакових типів:
, (10)
де та - семантичні значущості елементів відповідних типів запиту та об'єкта що аналізується.
Семантична суперечність графічного об'єкта і зразка визначається як:
. (11)
На кожному етапі в семантичному аналізі беруть участь об'єкти, семантична суперечність між якими не перевищує встановленої межі.
Оцінювання ефективності розроблених методів та алгоритмів.
З метою підвищення ефективності пошуку змінено формат зберігання файлу на:
Це забезпечило зменшення на 30% необхідних ресурсів фізичної пам'яті.
Ефективність семантичної фільтрації визначається кількістю відібраних файлів потрібного вмісту. Найбільш ефективним виявився перший фільтр (рис. 5) (незалежно від величини допуску), на ньому відкидається найбільша кількість файлів. Другим за ефективністю виявися третій семантичний фільтр. В той же час, другий семантичний фільтр виявився не лише малоефективним, а в загальному неефективним. Його ефективність зростає зі зменшенням величини допуску, проте не перевищує 22%, а в загальному для файлів різного вмісту тримається нижче відмітки 5% (рис. 6).
Рис.5. Ефективність семантичних фільтрів. Поріг подібності 20%
Рис.6. Ефективність семантичних фільтрів. Поріг подібності 5%
На основі аналізу ефективності семантичних фільтрів удосконалено метод семантичного пошуку шляхом виключення другого фільтра з процесу пошуку. При цьому, для 80 проведених експериментів, час пошуку зменшився на 36,7% при однакових вихідних умовах(рис. 7).
Рис. 7. Залежність часу пошуку від ефективності фільтрів
Розроблена інформаційна технологія зберігання і пошуку з використанням семантичного оцінювання вмісту графічного об'єкту є ефективним засобом пошуку в сховищах графічних об'єктів, для визначення подібності яких необхідно враховувати афінні перетворення.
Висновки по роботі
В дисертаційній роботі розв'язана актуальна наукова задача розроблення інформаційної технології зберігання та пошуку даних про графічні об'єкти з використанням їх семантики та вдосконалення методів і алгоритмів інтелектуалізації АСУ опрацювання даних про графічні об'єкти. При цьому отримано такі наукові та практичні результати:
1) На основі аналізу відомих технологій зберігання та пошуку даних про графічні об'єкти обгрунтовано актуальність застосування логіко-математичного опису їх семантики, що дає можливість зменшити обсяги передавання даних і підвищити ефективність автоматизованих пошукових систем.
2) Побудовано семантичний словник на основі формальних граматик, який включає головні ознаки графічних об'єктів, їхні атрибути та ієрархію і використовується для визначення семантичної значущості елементів об'єктів.
3) Розроблено семантичну модель графічного об'єкта з використанням графічних примітивів, що забезпечило можливість визначити найближчий об'єкт з наявних у сховищі даних із заданою подібністю.
4) Досліджено метод розроблення автоматичного аналізатора вмісту графічного об'єкта з використанням поняття про семантичну повноту та подальшим визначенням семантичної значущості об'єктів, що забезпечило нечутливість пошуку до афінних перетворень елементів.
5) Розроблено метод оцінювання ефективності процесів зберігання та пошуку даних про графічні об'єкти на основі семантичної та функціональної залежності між параметрами сховища даних та графічних об'єктів, що покращило параметри семантичного опису об'єктів і способи фільтрації даних.
6) Удосконалено структуру системи пошуку даних на основі розробленої інформаційної технології з визначенням характеристик семантичних властивостей об'єктів які заносяться у сховище, що забезпечило суттєве зменшення обсягів аналізованих даних про графічні об'єкти (не менше ніж на порядок) та покращення якості пошуку через невразливість до афінних перетворень.
Список опублікованих праць за темою дисертації
1. Чаплагін М.П. Методи представлення даних в блочних проектах / М.П. Чаплагін // Моделювання та інформаційні технології: зб. наук. пр. ІПМЕ НАН України. - 2004. - Вип.27. - С.161-165.
2. Чаплагін М.П. Застосування методів вейвлет-перетворення для представлення і обробки мультимедійних даних в блочних проектах / М.П. Чаплагін // Зб. наук. пр. ІПМЕ НАН України. - 2005. - Вип.28. - С.118-124.
3. Чаплагін М.П. Класифікація методів і алгоритмів подання мультимедійних даних в блочних проектах / М.П. Чаплагін // Моделювання та інформаційні технології: Зб. наук. пр. ІПМЕ НАН України. - 2005. - Вип.29. - С.169-176.
4. Нога А.Ю. Представлення нечітких понять в гібридній експертній системі / А.Ю. Нога, М.П. Чаплагін // Зб. наук. пр. ІПМЕ НАН України. - 2005 - Вип.30. - С.126-132.
5. Медиковський М.О. Застосування семантичного підходу до аналізу графічних об'єктів / М.О. Медиковський, М.П. Чаплагін // Вісник Нац. ун-ту "Львівська політехніка": Комп'ютерні науки та інформаційні технології - 2006. - № 565. - С.150-155.
6. Медиковський М.О. Метод розроблення словника для побудови семантичного опису графічного об'єкта / М.О. Медиковський, М.П. Чаплагін // Вісник НУ "Львівська політехніка": Комп'ютерні науки та інформаційні технології - 2007 - № 598 - С.149-153.
7. Тимченко О.В. Оцінювання вмісту графічного об'єкту на основі його семантики та її використання для організації пошуку графічних об'єктів в АСУ потоками даних / О.В. Тимченко, М.П. Чаплагін // Зб. наук. пр. ІПМЕ НАН України. - 2007 - Вип.39. - С.12-16.
8. Медиковський М.О. Визначення ефективності методу семантичного пошуку графічних об'єктів / М.О. Медиковський, О.В. Тимченко, М.П. Чаплагін // Зб. наук. пр. ІПМЕ НАН України. - 2007 - Вип.41. - С.84-98.
9. Web-сайт як блочний проект: матеріали науково-методичної конференції ["Сучасні проблеми телекомунікацій і підготовка фахівців в галузі телекомункацій - 2005"], (Львів, 17-20 жовт. 2005 р.) / Львівське обл. наук.-тех. тов. радіотехніки, радіоелектроніки і зв'язку, Львівська дирекція ВАТ "Укртелеком", Національний університет "Львівська Політехніка". - Львів: Національний університет "Львівська політехніка", 2005. - С.7-8.
10. Semantic approach usage for graphic object analysis : proceedings of the international conference on computer science and information technologies Computer Science & Information Technologies ["computer science and engineering 2006"], (Lviv, 11-13 Jctober 2006) / Lviv Politechnik National University. - Lviv: Lviv Politechnik National University. - 2006. P. 128-129.
11. Semantic dictionary development method for building graphic object's semantic description : proceedings of the international conference on computer science and information technologies Computer Science & Information Technologies ["The Experience of Designing and Application of CAD Systems in Microelectronics"], (Lviv-Polyana, 20-24 February 2007) / Lviv Politechnik National University. - Lviv: Lviv Politechnik National University, 2007. - P. 541.
12. Організація пошуку відомостей про графічні об'єкти в АСУ потоками даних на основі оцінювання семантики їх вмісту: матеріали науково-практичної конференції ["Сучасні проблеми телекомунікацій - 2007"], (Львів, 18-20 жовтня 2007 р.) / Львівське обл. наук.-тех. тов. радіотехніки, радіоелектроніки і зв'язку, Львівська дирекція ВАТ "Укртелеком", Національний університет "Львівська Політехніка". - Львів: Національний університет "Львівська політехніка", 2007 р. - С.36-39.
13. Розроблення семантичних фільтрів для організації пошуку графічних об'єктів в автоматизованих системах управління потоками даних: матеріали XXVI Науково-практичної конференції ["Моделювання"], (Київ, 12-13 січня 2007 р.) / ІПМЕ ім. Г.Є.Пухова. - К.: ІПМЕ ім. Г.Є.Пухова 2007. - С.75-76.
Размещено на Allbest.ru
Подобные документы
Проблема інформаційної обробки геологічних даних. Методи побудови розрізу з відомих елементів залягання. Підготовка даних для аналізу. Ієрархія об'єктів, що беруть участь в побудовах. Розрахунок витрат на розробку та впровадження проектного рішення.
магистерская работа [4,2 M], добавлен 17.12.2014Характеристика сучасних баз даних. Вивчення складу та призначення різноманітних елементів меню. Сутність об’єктів баз даних та елементів середовища керування СУБД MS Access. Основні засоби опрацювання об’єктів, принцип запуску середовища СУБД MS Access.
лабораторная работа [443,3 K], добавлен 13.03.2011Архітектура Web-баз даних. Загальні відомості про мову SQL. Створення таблиць баз даних. Використання бібліотеки для пошуку інформації. Аутентифікація за допомогою РНР й MySQL. Зберігання паролів в окремому файлі на сервері, використання бази даних.
курсовая работа [913,8 K], добавлен 12.01.2010Опис вхідних та вихідних повідомлень, процедури перетворення даних. Розробка інфологічної моделі, інформаційні об’єкти та їх характеристика. Автоматизація даталогічного проектування. Опис структур таблиць бази даних на фізичному рівні, реалізація запитів.
курсовая работа [2,5 M], добавлен 02.01.2014Бізнес процеси й елементи даних. Специфікація елементів даних. Діаграма класів проектування. Створення та використання об'єктів бази даних. Таблиці, обмеження цілісності, тригери, типові вибірки, представлення, індекси. Типові оператори модифікації даних.
курсовая работа [255,3 K], добавлен 01.06.2019Схема алгоритму програми. Алгоритм процедури введення даних, виведення результатів сортування, побудови дерева, перестановки елементів, "вирішення сімейного конфлікту". Приклад для масиву з 20 елементів. Користувацьке вікно та побудова піраміди.
курсовая работа [3,0 M], добавлен 21.02.2011Розробка VHDL-програми та синтез елементів пристрою для реалізації підстановки в S-блоках алгоритму DES. Основна функція шифрування (функція Фейстеля). Генерування ключів ki. Проведення симуляції роботи даних програм в середовищі САПР Aldec Riviera 2004.
курсовая работа [176,9 K], добавлен 21.01.2013Нові методи та спеціалізовані обчислювальні пристрої зменшення обсягів даних тріангуляційного опису об’єктів комп’ютерної томографії. Розвиток методу розбиття тріангуляційних сіток на окремі елементи. VHDL-модель спеціалізованого апаратного прискорювача.
автореферат [135,2 K], добавлен 13.04.2009Індексація веб-ресурсів, проблема індексації динамічних веб-сторінок, мультимедійних та графічних елементів. "Прихований Інтернет" та вдосконалення методів пошуку, на основі лінгвістичних технологій. Технічні складнощі Web та класифікація його ресурсів.
реферат [22,2 K], добавлен 10.08.2011Організована структура, призначена для зберігання інформації. Системи управління базами даних. Зберігання та пошук інформації про можливості використання ресурсів психологічних тестів мережі Internet. Створення об'єктів бази даних та запити до них.
курсовая работа [3,1 M], добавлен 21.10.2012
