Топологические модели в задачах информационной грануляции
Скачать 121.26 Kb.
|
ТОПОЛОГИЧЕСКИЕ МОДЕЛИ В ЗАДАЧАХ ИНФОРМАЦИОННОЙ ГРАНУЛЯЦИИБутенков С.А., к.т.н., доцент Южный федеральный университет e-mail: saab@tsure.ru Жуков А.Л., м.н.с. НИИ прикладной механики и автоматики КБЦ РАН e-mail: lamark-21@yandex.ru Джинави А. Яссин, аспирант Южный федеральный университет e-mail: ginawiyassin@yahoo.com 1. ВВЕДЕНИЕ В работе рассматриваются вопросы реализации основных идей принципа гранулирования многомерных данных, которые были заложены в ряде работ L. Zadeh [1-3]. Использование такого «зонтичного» подхода как теория информационной грануляции (ТИГ), которая обобщает результаты теории мягких вычислений [1], позволяет, с одной стороны, систематизировать уже имеющиеся методы, связанные с гранулированным представлением информации [2], а сдругой стороны – создать новые практически полезные методы представления и анализа данных путем расширения области применения руководящего принципа мягких вычислений [3]. Ключевыми терминами здесь являются перцептуальное представление и перцептуальный анализ данных, т.е. основой ТИГ является моделирование восприятий (перцепций) человека (в терминах, предложенных L. Zadeh). В ряде наших ранних работ были предложены и практически применены некоторые частные черты весьма общего топологического подхода к математической формализации перцептуальных моделей и алгоритмов ТИГ [4-7]. Настоящая работа обобщает опубликованные ранее результаты, дает их теоретическую интерпретацию и открывает новые теоретические и практические перспективы построения новых типов систем обработки данных в условиях действия широкого спектра НЕ-факторов [8]. С практической точки зрения развиваемый подход привлекателен тем, что используемый математический аппарат реализует расширенную парадигму мягкиих вычислений [7], в которой используются данные, представленные в канонической форме [1]. Предложенная в наших работах алгебраическая модель канонической формы представления данных [6] применима к широчайшему набору возможных типов данных различной размерности. В результате, с помощью малого числа сравнительно простых алгоритмов, основанных на топологических отношениях между объектами [4], удается решить широчайший круг задач, возникающих в анализе изображений, ГИС, Data Mining и т.д. [5]. 2. НЕОПРЕДЕЛЕННЫЕ ОБЪЕКТЫ И ОПЕРАЦИЯ РЕГУЛЯРИЗАЦИИ В контексте ГИС, анализа изображений и т.д. часто встречаются объекты, которые имеют достаточно сложную форму, плохо описываемую средствами аналитической геометрии (образ, гештальт). Часто для них применяется описание, связанное с описанием границы, отделяющей объект интереса от фона. Однако описание границы также приводит к появлению ряда НЕ-факторов. Согласно [9] объекты с неопределенной границей можно приближенно разделить на следующие классы:
Для подобных объектов в [10] введено топологическое определение понятия неопределенного объекта (vague region). Пусть  – множество объектов и  – совокупность подмножеств , удовлетворяющая следующим аксиомам: ,  ,  (1)Пара  называется топологическим пространством, множества  называются открытыми множествами данного пространства, а элементы  называются точками топологического пространства. Пусть  – подмножество топологического пространства. Тогда внутренностью , обозначаемой как  называется объединение всех открытых множеств, содержащихся в . Замыканием , обозначающимся как , называется пересечение всех замкнутых множеств, которые содержат . Внешностью , обозначаемой как  , называется объединение всех открытых множеств, не содержащих . Границей , обозначаемой как , называется пересечение замыкания и замыкания дополнения , так что  . Отношения между этими топологическими структурами задаются в виде:  ,  ,  ,  . (2)Согласно [10] назовем подмножество топологического пространства регулярно замкнутым если выполняется условие (3)Для объектов, не являющихся регулярно замкнутыми, в [10] введена топологическая операция регуляризации, приводящая к следующему результату в обозначениях (1-5)  . (6)Пример выполнения операции регуляризации над различными типами подмножеств плоскости приведен на следующем рисунке.  Рис. 1 Неопределённые объекты на плоскости до и после выполнения операции регуляризации Отметим, что для описания неопределенных объектов используются клеточные комплексы (point sets), при этом сама операция регуляризации (6) на клеточных комплексах является плохо формализованной [10]. В ряде наших работ (например, [4,5]) был предложен иной математический аппарат, основанный идеях представления неопределенных объектов путем покрытия регулярными элементами (декартовыми произведениями подмножеств в ортогональных системах координат), также приводящий в результате к регулярному в топологическом смысле результату [6]. Следующий рисунок иллюстрирует результат покрытия дискретного представления неопределенных объектов (подмножеств плоскости, имеющих различную размерность) регулярными элементами (декартовыми гранулами по L. Zadeh).  Рис. 2 Неопределённые объекты на плоскости до и после выполнения операции регуляризации покрытием В отличие от моделей, основанных на использовании клеточных комплексов [10], в разработанной нами модели все типы объектов покрываются гранулами одной и той же размерности, которые имеют одинаковое математическое представление в виде базовых элементов Грассманна [4]. Сравнивая результаты, представленные на Рис. 1 и 2, можно отметить, что независимо от применяемой процедуры, процесс регуляризации связан с потерей исходной информации. В наших работах предложен ряд алгоритмов, позволяющих строить оптимальные покрытия гранулами для исходных дискретных представлений объектов по критерию максимального правдоподобия [11] или по критерию сохранения исходной энтропии данных [12]. Исходя из выбранного критерия, разработанные алгоритмы позволяют выбрать параметры оптимального покрытия гранулами дискретного представления объекта интереса, вплоть до покрытия гранулами размером в один элемент, при котором исходная информация сохраняется полностью. С прикладной точки зрения, однако, такие модели гранул (неопределенных объектов) являются в значительной степени информационно избыточными. В соответствии с [10], для хранения данных о двумерном клеточном комплексе, связанном с декартовой гранулой, необходимо использовать в базе данных структуру, которая сохраняет координаты вершин комплекса, а также его сторон и данные о внутренности комплекса. В пространстве  объем хранимых данных будет оцениваться снизу как  . Очевидно, что для практических целей модели гранул в пространстве высокой размерности на основе клеточных комплексов мало пригодны. В то же время, для используемых нами покрытий прямоугольниками объем данных растет только как  [12].3. ТОПОЛОГИЧЕСКИЕ ОТНОШЕНИЯ МЕЖДУ НЕОПРЕДЕЛЕННЫМИ ОБЪЕКТАМИ В работах по ГИС были предложены формальные определения бинарных топологических отношений между объектами [13]. В частности, S. Winter предложил методы построения отношений между двумерными неопределенными объектами, основанные на оценке пересечения объектов [14]. К недостаткам этого метода построения отношений можно отнести то, что они не применимы для случая непересекающихся объектов. Затем, в указанных работах (и последующих тоже) эти отношения формировались, изучались и использовались для объектов, представляющих подмножества плоскости, что вполне естественно для ГИС. Нами предложена более общая система отношений, основанная на использовании понятия инкапсулирующей гранулы по L. Zadeh [2]. Рассмотрим основные определения, связанные с этим понятием. Информационной гранулой называется подмножество универсума  , на котором определено отношение сходства, неразличимости и т.п. [1]. Множество гранул, которое содержит все объекты универсума, называется гранулированием универсума. Подмножество  называется составной (не элементарной) гранулой если оно представляет собой объединение атомарных гранул [3].Определив на плоскости проекции произвольной гранулы  , обозначаемые как  и  , зададим инкапсулирующую декартову гранулу для произвольного как  . Гранула  является точной верхней гранью конечного множества всех гранул, содержащих . Мереологическое определение информационной гранулы широко обсуждалось в работах Л. Заде [1,2]. Введем ряд определений для общих процедур грануляции. Пусть  – гранулы в  соответственно, тогда гранула  – это декартова гранула. Для простоты мы будем предполагать, что  (рис. 3), что соответствует определению математической модели изображения [2]. Рис. 3. Декартова гранула для произвольных подмножеств Важность понятия декартовой гранулы происходит в большой степени от ее роли в процессе, называемом инкапсуляцией информации. Рассмотрим гранулу , для которой  и  обозначают проекции на и  областей и соответственно. Таким образом,  ,  Тогда декартова гранула определяемая как (7)инкапсулирует исходную произвольную гранулу в том смысле, что является точной верхней гранью декартовых гранул, которые содержат (рис. 4). Таким образом, может использоваться как верхняя аппроксимация для [1]. В более общей постановке мы можем построить цилиндрическое расширение [2]. Более конкретно цилиндрическое расширение  гранулы в направлении  является цилиндрическим нечетким множеством, таким что  , где  – луч, то есть прямая, проходящая через точку  в направлении ,  , где  и  – углы, определяющие . С помощью такого построения инкапсулирует .С понятием инкапсулирующей гранулы тесно связано фундаментальное понятие аппроксимирующего графика отношения. Согласно [2], график на плоском множестве задается как  , где операция ”+” означает дизъюнкцию в широком смысле слова [2]. Отметим, что в настоящей работе речь идет о декартовых координатах в отличие от лингвистических переменных. Рис. 4. Гранула G, ее проекции и инкапсулирующая гранула G+ В соответствии с определениями (1-6), при построении бинарного отношения между покрывающими гранулами  и  также можно охарактеризовать множествами внутренней области  , границей  и внешней областью  . (8)Поскольку в наших работах внутренность и границы покрывающих гранул отдельно не рассматриваются, то матрица, характеризующая топологические отношения между гранулами примет вид:  , (9)где  ,  – регулярные замыкания гранул и –  .Две произвольные гранулы и можно инкапсулировать одной общей гранулой , являющейся точной верхней гранью (рис. 3). Тогда внешнюю область  гранулы G можно описать с помощью инкапсулирующей гранулы по формуле: . (10)Следовательно, матрица, описывающая топологические отношения между гранулами с учетом формул (9) и(10) примет вид:  (11)или  . (12)Тогда по аналогии с работой [14] два объекта и можно описать, в общем случае, следующими четырьмя базовыми множествами:  ,  ,  ,  .Представление базовых множеств в виде эйлеровых диаграмм будет следующим:  Рис. 5. Базовые множества для построения топологических отношений на гранулах G1 и G2 В отличии от [14], информацию о бинарном отношении на гранулах и несут все четыре меры (11)-(12). После нормировки для получения описания взаимного положения объектов возможны 24=16 возможных комбинаций, ряд из которых не могут быть реализованы. После анализа всех возможных вариантов получим взаимосвязь топологических характеристик положения в следующем виде: Рис. 6. Бинарные топологические отношения на объектах Важнейшей особенностью предложенного подхода является его «антиасимптотичность», которая заключается в том, что регулярные представления в виде гранул и алгоритмы их обработки корректны при уменьшении размеров гранул до 1, т.е. могут выполняться для отдельных пикселей [4]. 4. ПРИМЕНЕНИЕ БИНАРНЫХ ОТНОШЕНИЙ НА ДЕКАРТОВЫХ ГРАНУЛАХ В качестве примера использования введенного аппарата для решения практической задачи выделения на цветном изображении камуфлированных объектов. Идея метода заключается в том, чтобы искать на цветном изображении не контуры, элементы изображения камуфлированного объекта, а участки, чьи цветовые гистограммы соответствуют известным образцам камуфляжной формы. Для этого используются предложенные в [5,6] модели декартовых гранул в цветовом пространстве. Следующий рисунок изображает образцы камуфляжной окраски и соответствующие цветовые гистограммы в пространстве HSV.       a) b) Рис. 7. Цветовые гистограммы изображений вариантов камуфляжной раскраски для разных стран Нами разработаны алгоритмы, основанные на расширенной парадигме мягких вычислений [7], которые в соответствии с идеями настоящей работы, выделяют оптимальные покрытия цветовых гистограмм и с помощью введенных отношений позволяют находить гранулы, принадлежащие изображениям камуфлированных объектов. Отметим, что для этих целей использовались те же алгоритмы, что и для распознавания изображений [4], выделения камуфлированных объектов на черно-белых изображениях и т.д. 5. ЗАКЛЮЧЕНИЕ Предложенный в работе подход к формализации регулярного представления данных в условиях действия НЕ-факторов является эффективной с практической точки зрения формализацией идеи метода информационной грануляции, позволяющем формализовать понятие образа, гештальта и т.д., часто используемое как в теории L. Zadeh, так и в сходных подходах, в которых распознавание гештальта служит методом решения плохо формализованных задач [15]. Подобные задачи часто встречаются в технической и медицинской диагностике, распознавании в сложных условиях и т.п. Полученные в работах нашей научной школы основные теоретические и практические результаты могут служить основой для построения эффективных систем анализа данных высокой размерности (например, цветных изображений и т.п.), а также предоставляют средства компенсации и учета НЕ-факторов (в результате применения регуляризации данных). Литература
|
Добавить документ в свой блог или на сайт
Похожие:
 | План работы конференции 24 апреля 2014: Пленарное заседание «Актуальные... Направления: экономическая безопасность; автоматизированные системы управления технологическими процессами; системный подход к обеспечению... |  | Моделирование коррозионных процессов для информационной системы поддержки... Ведущая организация – фгоу впо кемеровский государственный сельскохозяйственный институт |
| Программа по формированию навыков безопасного поведения на дорогах... Цель: познакомить с этапами моделирования, компьютерными моделями, дать определение информационной модели, познакомить ч видами информационных... | | 5 3 стремление к грануляции и поисковая активность Заочная всероссийская научная конференция с международным участием «Научное творчество ХХI века» |
| Построение информационной инфраструктуры вуза с применением модели Saas аннотация Памятка локомотивной бригаде (машинисту) по предупреждению проезда запрещающих сигналов | | Программа по формированию навыков безопасного поведения на дорогах... Трехуровневая система организации бд. Модели данных. Классификация моделей данных. Семантические модели данных. Модель полуструктурированных... |
| Аналитический доклад Совету глав правительств СНГ о текущем состоянии,... В настоящее время эффективное информационное взаимодействие невозможно представить без использования информационных технологий, телекоммуникационных... | | Рабочая программа дисциплины Целью освоения дисциплины является формирование представлений об объектах, видах и задачах профессиональной деятельности бакалавра... |
| Классификация угроз. Формализация подхода к обеспечению информационной... ... | | Рабочая программа дисциплины Введение в профессию Целями освоения дисциплины «Введение в профессию» является формирование представлений об области, объектах, видах и задачах профессиональной... |
| Программа по формированию навыков безопасного поведения на дорогах... Цели: ввести классификацию структур информационных моделей; сформировать понятие табличной информационной модели; научить учащихся... | | Программа по формированию навыков безопасного поведения на дорогах... Цели: ввести классификацию структур информационных моделей; сформировать понятие табличной информационной модели; научить учащихся... |
| Дисциплины «математические методы в инженерных задачах» Кафедра математики Направление Математические методы в инженерных задачах – это прикладная математическая дисциплина, в которой изучаются, способствующая развитию... | | Программа по формированию навыков безопасного поведения на дорогах... Урок разработан с учетом использования модели «1: 1» или byod. Учебная деятельность способствует воспитанию активных граждан общества... |
| «Модели компьютерного обеспечения иос. Использование цифрового интерактивного... Постепенное оснащение школы средствами икт определо педагогические модели применения информационных и коммуникационных технологий... | | Требования к экзамену Модели и моделирование. Понятие, цель и виды моделей. Этапы создания компьютерной модели |
