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

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ Государственный университет им. М. Е Ломоносова

Факультет вычислительной математики и кибернетики

На правах рукописи

КОВАЛЬЧУК ОЛЕГ ГЕОРГИЕВИЧ

КОНСТРУКЦИЯ СРЕДСТВ ПОДДЕРЖКИ КАРТИННО- ГРАФИЧЕСКИХ ' БАЗ ДАННЫХ В СИСТЕМЕ ИНТЕГРАЦИИ НЕОДНОРОДНЫХ БАЗ ДАННЫХ И ЗНАНИЯ

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин и систем

АВТОРЕФЕРАТ , диссертации на соискание ученой степени кандидата физико - математических наук

МОСКВА - 1991

■ - 2 -

Работа выполнена на кафедре автоматизации систем вычислительных комплексов фасультета вычислительной математики и кибернетики МГУ им. М. В. Ломоносова

Научный руководитель: доктор фиэико - математических наук, Профессор Л А. Калиниченко.

Официальные оппоненты: доктор физико-математических наук, профессор Э. 3. Любимский, кандидат физико-математических. наук С. Л. Кузнецов

Ввдуцая организация: Институт кибернетики

им. а М. Глуикова АН УССР.

Защита состоится ■45» оекоЯ? 19э/ //час. мин. Нс1 васедёши специализированного совета Д 053. 05. 38 К 4 при псковском Государственном Университете имени М. Е Ломоносова по адресу: 118699, ГСП, Москва, Ленинские Гори, .МГУ, факультет вычислительной математики и кибернетики, ауд. 685

С диссертацией можно ознакомится в библиотеке факультета ШиК МГУ.

Автореферат разослан

Ученый секретарь специализированного совета профессор (

Н. И Трифонов

- а -

I. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Проблема обобщенного, однородного представления и интегрированного использования для решения задач разнообразных представлений данных, знаний и программ накопленных в организациях и составляющих их информационный ресурс, входит в задачу научно-исследовательского проекта СИНТЕЗ. 'Ко- . нечной целью проекта является создание методов и средств под-дерюся интероперабельных сред неоднородных информационны* ресурсов.

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

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

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

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

Картжшая' (графическая) база данных (КБД) есть совокупность хранимых данных о пространственных объектах, их свойствах и

' - А -

отношениях, представляющих интерес для исследований в заданной предметной области.

В тех областях, где изображения являются необходимым видом представления информации,, системы поддержи КЕЩ позволяют эф-.фективно решать сложные и трудоемкие прикладные задачи. Это определяется тем, что во многих случаях представление информации для человеко-машинных систем в виде изображений оказывается значительно более удобным и естественным по сравнению с символьным представлением.

Для поддержи КБД приходится создавать новые или расширять существующие модели данных и раарабзтывать эффективную реализацию рассматриваемых моделей.

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

Все это сделаю проблему реализации КБД задачей практической необходимости и важности в теории и практике систем баз данных и обуславливает ее актуальность.

Цель работы. Целью диссертационной работы является разработка практически эффективного метода поддержки КБД через абстрактный тип данных (АТД), обоснование правильности разработанного подхода: определение модели картинно-графических данных, описание картинно-графических данных языковыми средствами концептуального уровня; определение архитектуры и создание программных средств реализации КБД.

В диссертационной работе ставятся и решаются следующие задачи:

1. Исследуются и.описываются средства поддержки КБД;

'¿. Определяется подход представления картинно-графических данных посредством АТД;

3. Предлагается метод реализации АТД;

4. Разработка и реализация системы поддержки КБД.

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

- Б -

картинно-графических данных.

Научная новизна Диссертационная работа содержит следующие основные научные результаты:

- представлен подход к поддерже КБД в рамках проекта СИНТЕЗ, обеспечивающий управление долговременным хранением, поиском, вводом и представлением картинно-графических данных в их интеграции с традиционными символьными данными. Принципиальными особенностями метода является расширение обобщенной (в данном случае реляционной) модели данных средствами поддержи абстрактных типов данных и введения на этой основе доменов картинно-графического типа;

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

- разработана архитектура системы реализации абстрактных типов данных, принципиальной особенностью которой является структурное размещение реализатора-АТД по отношению к процессору базы данных на одном уровне с системой хранения традиционных данных и преобразователями моделей данных;

- предложено представление структурированных картинно-графических данных посредством формата бКБ и представлены алгоритмы пространственных операций с использованием метода доступа дерево";

- предлогено применение комбинированных средств ведения КБД и графического интерфейса с пользователем;

- предлагаемый подход является весьма общим и применимым для обобщенного представления разнообразных видов и форм специфических информационных ресурсов на основе, аппарата абстрактных типов данных при создании интероперабельных сред неоднородных информационных ресурсов в проекте СИНТЕЗ.

{фактическая ценность. Практическими результатами работы является разработка принципов поддержки АТД для системы интеграции неоднородных баз данных и знаний, архитектуры, языков и интерфейсов системы реализации АТД для картинно-графических данных, а такде программные средства, реализующие предложенный подход к разработке системы поддержки КБД

- б -

Разработанное программное обеспечение для поддержки КБД внедрено в системе интеграции неоднородных баз данных и знаний. Система поддержи КБД принята Мекведомственной комиссией и передана в Государственный фонд алгоритмов и программ в 1991 .году. Внедрение подтверждено актом.

Апробация работы. Результаты диссертационной работы докладывались на семинарах ИЛИ АН СССР "Система интеграции неоднородных баз данных и знаний" в 1987-1991гг., на семинарах кафедры АСВК факультета ВМК МГУ и лаборатории математических методов исследования почв Почвенного института ВАСХНИЛ в 19871989г., ка конференции молодых ученых в Институте математики с ВЦ АН МССР в 1887г. , на научно-практическом семинаре "Проблемы создания видеографических информационных систем", г.Киев 1990г.,- на международной конференции "Проблемы информатики", г.Самара 1991., на семинаре по проекту "Синтез", г.Бердянск 1991г..

Публикации. Ш материалам диссертации опубликовано пять печатных работ. —-

Объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложений, изложенных на 138 страницах; работа содержит 3 рисунка и 4 таблицы.

II. СОДЕРЖАНИЕ РАБОТ 1<

Во введении обоснована актуальность темы, формулируются цс;-ли к задачи исследования, дана краткая характеристика работы.

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

Работы, ориентированные. на поддержу КБД, отличаются Сольем« разнообразием. Многообразие подходов - объективная закономерность, предопределенная раъзитием систем баз данных:

- необходимость» разработки средств поддержки КБД для даль-нейыего развития систем управления базами данных (СУБД), систем обработки и анализа изображений;

- разработкой специализированных информационных систем для

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

Существенное влияние на выбор подхода к поддержке КБД имеют й сами картинно-графические данные из-за следующих особенностей:

- пространственная природа данных; . '

- многообразие способов и форм представления картинно-графических данных;

- необходимость применения увобных методов ввода и визуализации картинно-графических данных;

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

- необходимость применения специальных устройств, ввода, вывода, хранения данных.

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

При рассмотрении предложенного метода определены средства концептуального описания, функции манипулирования картинно-графическими данными. При этом также представлены возможности языка запросов к КБД.

Предложен подход к реализации рассматриваемого метода, включающий представление архитектуры системы реализации АТД, определение языковых средств и описание основных "компонентов системы и их функций.

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

Сравнительный анализ' систем поддержки КБД позволяет выявить тенденцию развития систем баз данных для манипулирования картинно-графическими данными, разработки эффективных языков запросов, организации удобных графических интерфейсов с пользова-

- в -

телем, реализации эффективных методов доступа.

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

Для СУБД были выявлены способы представления картинно-графических объектов языковыми средствами концептуального уровня систем баз данных.

• На базе доступных работ по поддержке КБД в системах баз данных, были выделены основные класры операций над картинно-графическими данными, наиболее часто применяемые в различных системах..

Представлены наиболее распространенные типы запросов к картинной базе данных и дан краткий анализ ряда языков запросов, реализующих поиск в КБД, с целью выявления особенностей языковых конструкций обеспечивающих манипулирование картинно-графическими данными.

Выделены наиболее распространенные пространственные запросы и представлено сравнение известных пространственных методов доступа. ' '

• Анализ показал,

- основными- способами представления данных об изображении являются позиционный и структурный. Для поддержи КБД в системах баз данных представляется необходимым реализация обоих способов представления,' что позволяет объединить преимущества каждого из них;

- представление картинно-графических данных посредством аппарата поддержки абстрактных типов данных обеспечивает эффективную реализацию средств поддержи КБД;

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

- проблема поиска картинно-графических данных по их пространственным характеристикам и взаимосвязям решаете? расширенными средствами языка запросов для манипулирования картинно-графическими данными;

- исследуемые пространственные методы доступа успешно решают проблему эффективного поиска картинно-графической информации' посредством создаваемых пространственных структур данных.

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

Картинный тип дачных как АТД

Далее будет представлен подход к реализации средств подг держки. КБД принятый в системе интеграции неоднородных баз данных и знаний и в проекте СИНТЕЗ.

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

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

КТД е'сть множество изображений, каждое из которых рассматривается в пространстве изображений отдельно, без пространственной взаимосвязи с другими экземплярами множества и однозначно определено своими координатами в таком пространстве.

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

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

ко кап единое,целое, но и как совокупность пространственных объектов. Элементы изображения, принимаемые в качестве объек-тоз, определяются конкретными задачами.^

Такое представление изображения называется структурированная. Оно позволяет на основе анализа изображения извлекать соответствующую информацию об объектах, осуществлять поиск объектов, чьи пространственные характеристики удовлетворяют заданным критериям.

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

Значения СКТД задаются в соответствии с выбранным способом структурного представления изображений, основанном на координатной привязке составляющих элементов. Экземплярами СКТД могут быть объекты типа точка, ломаная, область. Набор типов может быть расширен в зависимости от области применения.

С точки зрения языка, базовой конструкцией" для определения ГОД и СКТД является АТД. Атрибуту отношения со значениями, которыми являхд'ся изображения, соответствует определенные в схеме базы данных домены - АТД, интерпретирующие КТД или СКТД. В состав отношения шлет входить несколько атрибутов типа КТД или СКТД.

Значения АТД в кортежах отношения интерпретируются идентификаторами КТД (например, кмя файла изображения) или СКТД (например, пространственный индекс), которые однозначно задамг представления значений КТД или СКТД в среде хранения.

Собственно значения КТД или СКТД представлены соответственно позиционным и структурированным методом в КБД.

Применение АТД обусловлено тем, что:

- обеспечивается возможность определения на концептуальном уровне новых разновидностей типов данных КТД и СКТД;

- определяется набор операций над этими типами данных;

- обеспечивается концептуальная независимость от' способов представления, методов структурирования данных и реализации операций для различных КТД'и СКТД;

- обеспечивается реализация расширения языка запросов спе-

- 11 - .

циальными операциями над картинно-графическими данными, позволяющая осуществлять аффективный поиск к КБД;

- обеспечивается эффективная реализация средств • поддержки КБД (ввод/визуализация", хранение, обработка).

На концептуальном уровне АТД описываются средствами языка спецификации типов и процедур (ЯСТП). КТД определяется типом PICTURE. Каждый экземпляр. КТД идентифицируется своим символьным идентификатором. Значения экземпляра задаются в соответствии с выбранным способом представления КТД (например, матричным представлением).

СКТД определяется типами: STRUCT_PIC (структурированный картинно-графический тип), STRUCT_REGION (тип данных область), STRUCT„SEGMENT (тип данных ломаная) и STRUCT_POINT (тип данных точка). Следует отметить, что операции STRUCT_Р1С наследуются остальными названными выше типами.

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

Операции над абстрактными типами данных s

В рассматриваемом типе КТД определяется набор операций над его экземплярами. Операции включают в основном фунцщии обработки изображений, такие как:

- функции улучшения качества изображения;

- функции изменения пространственных характеристик экземпляров и получения новых экземпляров из нескольких;

- вычислительные операции над одним или несколькими экземплярами.

В нашем случае, мы используем КТД для визуализации изображений по алфавитно-цифровым данным и для получения структурированного представления изображений ручным способом. Также допускаем задание операций обработки изображений, которые обычно используются в области анализа и обработки изображений (например, операции ADD (сложения), SUB (вычитания), LPF (усиления резкости), ОТ (усиления контраста)).

Набор операций над СКТД подразделяется на следующие подмножества:

- операции вычисления геометрических характеристик зкземп-

ляров СКТД;

- операции вычисления значений экземпляра СКТД, полученного из заданных значений двух или более других экземпляров СКТД;

- операции многоуровнего представления экземпляров СКТД;

- логические операции проверки заданных пространственных отношений между экземплярами СКТД;

- операции прямого пространственного поиска экземпляров СКТД посредством окна поиска.

Операции вычисления геометрических характеристик значений СКТД позволяет получать значения площади, периметра СКТД типа область, длины элемента СКГД типа ломаная, угла наклона СКТД типа ломаная (отрезок), а также вычислять расстояние медцу двумя заданными элементами СКТД.

Операции вычисления значений СКТД позволяют получать новые значения СКГД из заданных двух значений СКТД в результате их пересечения, объединения, разности на плоскости изображения, а также получать значения центра расположения, границ элемента СКТД типа область.

Операции многоуровневого представления выполняют функции масштабирования значений СКТД.

Логические операции позволяют определить пространственные отношения между заданными значениями СКТД. Например, отношения "внутри", "покрывает", "медду", "к северу", "касается".

Операции прямого пространственного поиска осуществляют нахождение значений СКТД на плоскости изображения по условию поиска на плоскости.

Операции СКТД выполняются как над отдельными значениями, так и над множеством значений СКТД одного или разных типов.

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

Расширение языка запросов

Необходимое для поддержки КБД расширение языка запросов рассматривается здесь применительно к языку фильтров системы

интеграции неоднородных баз данных и знаний, основанному на многосортном исчислении предикатов. В язык фильтров введены следующие функции над атрибутами типа КТД и СКТД:

- задание в условиях требуемых пространственных отношений между компонентами СКТД на плоскости изображения;

• - поддержка взаимосвязи между значениями КТД (СКТЛ) и символьными данными;

- реализация пространственных манипуляций над КТД (СКТД) (вычисление значений новых созданиях КТД (СКТД))-,

- реализация геометрических вычислений над СКТД в процессе ответа на запрос;

- поддержка прямого пространственного поиска на плоскости изображения посредством задания произвольного окна поиска;

- поддержка многоуровневого поиска КТД и СКТД;

- обработка пространственных характеристик КТД в процессе ответа на запрос.

С целью поддержки КТД и СКТД в языке фильтров используются следующие средства:

- предикаты в термах;

- функции в выражениях;

- средства формирования вычисляемых атрибутов типа КТД или СКТД.

Предикаты в термах обеспечивают логические условия пространственного отбора СКТД в КЕД.

5ункции в выражениях позволяют вычислять геометрические характеристики СКТД и используются в составе термов условий в выражениях.

Средства формирования вычисляемых атрибутов позволяют создавать значения новых картинных атрибутов посредством задания операций над КТД (СКТД).

Общий формат языковых средств йля работы с КБД имеет следу-шее описание:

<выражение>:: - <значение) ! <функция над АТД>

<предикат>:: - <имя предиката? ( <список параметров> ) <список

параметров»:: - <параметр> ! <параметр> , ссписок

параметров> <параметр>:: - <значение> ! <имя АТД>

- 14 -

<имя АТД>:: - <идентификатор атрибутах

«значением:- <булевское значение» ! <символьное значение> I

<вещественное значение> I <целочисленное значение» I <имя предикатам:- COVERING I COVERED_BY I OVERLAPPING I DISJOINED I NORTH I SOUTH i EAST 1 WEST I NORTH_ EAST I NQRTH_WEST ! SOUTH_EAST i SOUTH_WEST ! WITHIN I OUTSIDE I NEAREST I FURTHEST I TOUCH Г BETWEEN <список описателей производных атрибутов»::- «описатель производного атрибута» I <список описателей производных атрибутов» , <описатель производного атрибута» «описатель. производного атрибута»::-<аспект» - «функция АТД> <функция АТД>:: - <иш функции АТД> ( «список параметров» ) <имя функции ATД>::-INTERSECT ! UNION I DIFFERENCE I ZOOM_IN ! ZOOM_OUT ! CENTER I BOUNDARIES I SLOPE I ADD ! SUB i MUL I LPP 1 MDN ! CNT I SLS ! AREA I PERIMETER I LENGTH ! DISTANCE «аспект»::- <имя АТД>

Функции манипулирования картинно-графическими данными в картинной базе данных Системой обеспечиваются следующие функции над КБД:

- реализация функций манипулирования картинно-графическими данными в КБД (создание, удаление, изменение объектов);

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

- реализация функций управления методом доступа "R-дерево" (создание структуры R-дерева; удаление, помещение, обновление объекта в структуре R-дерева);

- реализация функций непосредственной визуализации картинно -графических данных из КБД;

- реализация функций идентификации картинно-графических данных на плоскости (посредством мигания объектов на плоскости).

Третъя глава посвящена проблемам разработки системы реализации ATД. Определена архитектура системы, определены языки и

основные компоненты системы реализации АТД. Предложены и описаны основные функциональные характеристики системы ввода и визуализации картинно-графических данных.

Представлен реализованный в системе метод доступа И-дерево, опсаны основные его характеристики и спецификации операций. Описываются функции и интерфейсы системы реализации КЕД. В главе 3 описано таю® состояние реализации данных средств поддержки АТД для картинно-графических данных, в рамках работ по теме "Система интеграции неоднородных баз данных и знаний".

.Общая схема реализации абстрактного типа данных На рис. 1. приведена обшая схема средств реализации КБД на основе аппарата поддержки АТД.

I Диалоговый! I монитор I _ I__I

I Процессор! _ I данных ! I_I

_(__

Система хранения данных( СХЮ

I

1 Система ввода лизации КГД

и визуа-1

УИАТД

I Реализатор 1 АТД

1 Система I хранения

I кгд

Рис. 1

- 16 - ,

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

Взаимодействие системы ввода с системой хранения включает:

- передачу на исполнение функций манипулирования картинно-графическими данными (создание, помещение, удаление и др., функций реализующих управление методом доступа "R-дерево");

- получение результата выполнения функций;

- анализ результата

Взаимодействие системы визуализации с диалоговым монитором происходит, когда результирующие кортежи содержат атрибуты картинно-графического типа. Тогда для каждого атрибута картинно-графического типа осуществляется переход в режим визуализации с передачей значения идентификатора атрибута и его значения .в результирующем кортеже. По идентификатору атрибута'и идентификатору объекта система визуализации получает из системы хранения . непосредственно значения объекта и представляет его на экран. -

Взаимодействие системы визуализации с системой хранения включает также:

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

- передачу на исполнение функций реализующих непосредственную визуализацию картинно-графических данных из КБД;

- передачу на исполнение функций реализующих идентификацию картинно-графических данных на плоскости.

Поддержа АТД в процессоре данных осуществляется в следующих операциях:

- при открытии/закрытии отношений (операция OPEN/CLOSE), содержащих атрибуты АТД осуществляется инициализация/освобож-

- 17 -

дение заданного атрибута картинно-графического типа;

- операции проекции и селекции (РЕЗТЙ/РВД), при проверке условий содержащих АТД или при формировании нового атрибута АТД в результирующем отношении, содержат в качестве операндов функции над АТД.

На уровне процессора реляционной алгебры (ПРА) в представленных случаях осуществляется, выход на интерфейс с системой поддержки КЕД для обеспечения выполнения заданных функций над АТД.

Поддержка конкретной реализации КТД и СКТД реализуется ниже центрального исполнительного уровня системы (процессора реляционной алгебры).

Поддержка реализации КТД и СКТД обеспечивается универсальным интерпретатором АТД и реализатором АТД.

Универсальный интерпретатор АТД (УКАТД) является главным звеном, обеспечивающим взаимодействие процессора данных и реализатора АТД.

Основное назначение УИАТД заключается в получении директив от процессора данных и их интерпретации. Выполнение директив на уровне УИАТД включает их анализ для выявления вида АТД и передачу на исполнение конкретному реализатору АТД

Реализатор АТД (РАТД) предназначен для управления конкретными реализациями АТД (в нашем случае КТД или СКТД). Он обеспечивает поддержку следующих основных функций реализации КТД или СКТД:

- поддержка средств хранения конкретной реализации АТД;

- манипулирование значениями КТД (СКТД) (осуществление выбора пространственных характеристик объектов и выполнение Функций над КТД (СКТД) аргументами которых являются полученные пространственные характеристики).

Система ввода и визуализации картинно-графических данных

Средства поддержки ввода, представления и визуализации кар-■ тинно-графических данных предназначены для:

- ввода изображений (картинно-графических данных) средствами оптического считывающего устройства (сканкера);

- улучшения характеристик качества изображений (подавления шумов, усиления яркости, контрастности и зернистости);

- 18 -

- сжатия послесканнерных изображений;

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

- формирования структурированного представления в формате метафайлов для картинно-графических типов данных;

- визуализации картинно-графических данных.

Отличительной особенностью комплекса является то, что вводимые изображения могут рассматриватся как.в позиционном так и в структурированном представлении, что соответствует,представлению КТД и СКТД.

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

Программа управляется с помощю меню, составленных из текстов и пиктограмм и обеспечивает работу с изложенными функциями манипулирования картинно-графическими данными в КБД.

Создание КБД для СКТД заключается во вводе изображения сканирующим устройством, его предварительной обработке (для получения более качественного представления) и классификации для получения структурированных компонент изображения.-. В результате создается метафайл СКТД, соответствующий графическому стандарту 6К5 с некоторыми изменениями, учитывающими классификацию и топологию полученных пространственных представлений. Изменения структуры метафайла включают последовательное задание записи домена, после которой идут записи определенного примитива (область, ломаная, точка). Определение каждого примитива может включать запись классификатора (структурированного объекта состоящего из набора примитивов: например почвенная карта).

Для значений СКТД конкретного домена картинно-графического типа создается структура И-дерева

При вводе картинно-графической информации каждый объект, представленный форматом бКБ, должен наряду с графическими данными содержать символьную информацию (символьный идентификатор) для последующей однозначной идентификации по признаку (для установления связи с символьной информацией в кортежах отношений). Например, это - название городов, рек, регионов.

Ввод реализуется последовательно: картинно-графическая и символьная информация вводятся отдельно. Связь устанавливается по символьным идентификаторам объектов от алфавитно-цифровой базы данных к картинно-графической (заключительный этап ввода).

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

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

Создание КВД для КТД заключается во вводе изображений сканирующим устройством, их предварительной обработка. В реэуль-' тате создаются сканнерные образы в формате СШ-файла графического редактора ОЙНАЬО.

Следует отметить, что 'загрузка КБД осуществляется" системой автономно и предполагает наличие картинно-графических доменов, не заданных в схеме баз данных. Функции обновления и удаления картинно-графических данных осуществляются отдельно от традиционной базы данных.

Средства визуализации предназначены для просмотра яа экране дисплея совокупности графических объектов, хранящихся в форма-то метафайла 6КЗ. При просмотре ответа на запрос, если ре-еультирукядай кортеж отношения содержит атрибуты картинно-графического типа, то для каждого из них осуществляется переход в графический режим, в" котором визуализируется объект на плоскости. 4

Средства визуализации позволяют осуществлять визуализацию: ■ • классификатора(ов), домена(ов), объекта(ов).

Применяются следующие методы визуализации в языке~запросов:

- результат запроса представляется на пустом .экране;

- результат запроса добавляется к изображению на экране;

- результат запроса идентифицируется миганием на экране;

-so - •

- последовательная визуализация выводимых результатов запроса: сначала первое представление, затем последующие. Например, визуализация почвенных регионов, затем отдельно визуализация выращиваемых культур;

- осуществление визуализации иерархического представления графических объектов: от простого представления к более детальному представлению объекта;

- задавать окно поиска. • Указывается имя домена и задается окно поиска на экране. Результатом будут объекты которые: находятся внутри окна (COVERING), пересекают окно (OVERLAPPING), покрывают окно (COVEREDJ3Y), находятся снаружи окна (DISJOINED);

- осуществлять поиск по сходству: указывается имя домена и 'задается объект поиска на экране. Результатом будут те объекты, которые сходны с заданным.

Реализатор абстрактного типа данных.

Структурно реализатор абстрактного типа находится по отношению к реляционному процессору на одном уровне с системой хранения традиционных данных (ИД) и на одном уровне с преобразователями моделей данных системы интеграции неоднородных баз данных и-знаний.

Реализатор абстрактного типа состоит из двух частей - общей части (не зависящей от вида АТД), именуемой универсальным интерпретатором АТД, и переменной части - реализатора конкретных АТД (РАТД).

Основное назначение УИАТД заключается в получении директив от процессора данных и их интерпретации. Выполнение директив включает их анализ для выявления вида АТД и осуществления взаимодействия с реализаторами соответствующих АТД.

Реализатор АТД обеспечивает поддержку конкретного АТД.

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

Для поддержки СКТД в РАТД реализуется динамическая структура R-дерева, позволяющая осуществлять управление созданными индексными структурами, обеспечивающими эффективную организа-

цию хранения и поиска СКТД

Каждому компоненту СКТД в структуре соответствует пространственный индекс, однозначно его идентифицирующий.

Средства поддержи динамической индексной структуры R-дерева реализуют следующие операции:

- создание упакованного R-дерева по заданному списку индексных записей;

- осуществление поиска всех индексных записей, покрывающих окно поиска, пересекающих окно поиска или покрытых окном поиска, по. заданному окну поиска;

- помещение заданной индексной записи в R-дерево;

- удаление заданной индексной записи из R-дерева

Манипулирование данными структурированного картинного типа -

реализуется набором операций над СКТД. Алгоритмы этих операций базируются на существующих исследованиях в области вычислительной геометрии.

На базе этих исследований удалось установить, что эффектив-I ные алгоритмы для геометрических задач часто конструируются при помощи общих методов теории алгоритмов (рекурсия, динамическое программирование, балансировка). Однако, существует метод, который подсказан исключительно природой некоторых геометрических задач Это метод заметания. В нашем случае используется метод плоского заметания (в двух измерениях). Реализация метода заметания используется например, в операциях COVERING, C0YEREDJ3Y, OVERLAPPING, DISJOINED, TOUCH.

Манипулирование значениями картинно-графических данных, представленных в формате 6KS метафайла в Реализаторе ЛТД, заключается з выполнении следующих функций (извлечение' из GKS-представления объекта его атрибутов): получение индекса цвета ломаной, получение индекса цвета полимаркера, получение индекса цвета области, получение масштаба ломаной, получение типа маркера, получение вида заполнения области, получение типа линии, получение координат объекта

Полученные атрибуты объектов являются исходными значениями для выполнения функций над картинно-графическими данными. Большинство операций в 'качестве входных значений используют пространственные координаты объектов.

-22-

Функции системы хранения данных

Система хранения реализует функции создания, открытия, закрытия КБД, а тагане функции управления картинно-графическими объектами (например, запись объекта, чтение по индексу, удаление по индексу). Каждый объект описывается структурой, содержащей имя домена, к которому принадлежит данный объект, имя объекта- его идентификатор, адрес массива, содержащего полное описание объекта в том виде, как оно хранится в КБД (в формате бКЭ-метафайла или СШ-файла). Структура содержит также длину массива, имена классификаторов объекта (например, для объекта типа область в картографии задаются классификаторы принадлежности объекта: почва и фауна).

Средства поддержки работы с КБД включает также компоненты управления пространством изображения, редактирования изображений и представления результатов а ал роса на плоскости.

В заключении сформулированы основные результаты диссертационной работы.

В приложении приведены материалы об использовании результатов диссертации на базе примера базы данных.

' III. ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Определена семантика операций над картинными типами данных и структурированными картинными типами данных, дана их классификация и предложено их описание на языке спецификации процедур.

3. разработаны средства языка фильтров обеспечивающие манипулирование картинно-графическими данными:

- предикаты в термах;

- функции в выражениях;

- средства формирования вычисляемых атрибутов картин-

ного типа данных или структурированного картинного типа данных.

4. Разработаны и реализованы средства пользовательского интерфейса для работы с картинно-графической базой данных и осуществлена реализация пространственного метода доступа "К-дере-во" .

5. Разработана архитектура.системы реализации абстрактных типов данных.

6. Определены интерфейсы и структуры основных компонент скстемц реализации картинно-графических баз данных: системы ввода, визуализации картинно-графических данных; универсального интерпретатора абстрактных типов данных, реализатора абстрактных типов данных и системы хранения картинно-графических данных.

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

I 8. Разработаны и реализованы средства поддержки картинно-графических баз данных в рамках системы интеграции неоднородных баз данных и знаний.

9. Полученные результаты могут быть обобпзени для целого класса специфических форм данных с целью их поддержки в интероперабельных средах информационных ресурсов в рамках проекта СИНТЕЗ.

По теме диссертации опубликованы следующие работы:

1. Калиниченко Л А., Ковальчук О. Г. Средства поддержи картинных баз данных для системы интеграции неоднородных баз данных и знаний// Тез. докл. научно-практического семинара "Проблемы создания видеографических информационных систем". - Киев, - 1990, - с. 3-17.

2. Калиниченко Д А. , Ковальчук О. Г., Куропев М. Ю.- Некоторые аспекты реализация пространственных запросов к картинной базе данных в рамках системы интеграции// Тез. докл. международной конференции "Проблемы информатики". - Самара, - 1891. - с. 3-5.

3. Ковальчук 0. Г. Анализ известных подходов поддержки картинно-графических баз данных (обзор), 5 Всесоюзная конференция

- 24 -

"Системы Оаз данных и знаний". - Львов, - 1891. - 36 с.

4. Ковальчук 0. Г. функции к интерфейсы системы реализации картинно-графических типов данных. Система интеграции неоднородных баз данных и баз знаний // ГФАГ1, - 1990г., - 50 с.

Б. Калиниченко л. А. , Ковальчук О. Г. Конструкция средств поддержки картинно-графических баз данных // Препринт ИЛИ АН СССР, - 1991. - 76 с. (в печати).