Топологические модели в задачах информационной грануляции

Размещено на http://www.allbest.ru/

Топологические модели в задачах информационной грануляции

Бутенков С.А., к.т.н., доцент

Южный федеральный университет

Жуков А.Л., м.н.с.

НИИ прикладной механики и автоматики КБЦ РАН

Джинави А. Яссин, аспирант

Южный федеральный университет

ВВЕДЕНИЕ

В работе рассматриваются вопросы реализации основных идей принципа гранулирования многомерных данных, которые были заложены в ряде работ L. Zadeh [1-3]. Использование такого «зонтичного» подхода как теория информационной грануляции (ТИГ), которая обобщает результаты теории мягких вычислений [1], позволяет, с одной стороны, систематизировать уже имеющиеся методы, связанные с гранулированным представлением информации [2], а с другой стороны - создать новые практически полезные методы представления и анализа данных путем расширения области применения руководящего принципа мягких вычислений [3].Ключевыми терминами здесь являются перцептуальное представление и перцептуальный анализ данных, т.е. основой ТИГ является моделирование восприятий (перцепций) человека (в терминах, предложенных L. Zadeh).

В ряде наших ранних работ были предложены и практически применены некоторые частные черты весьма общего топологического подхода к математической формализации перцептуальных моделей и алгоритмов ТИГ [4-7]. Настоящая работа обобщает опубликованные ранее результаты, дает их теоретическую интерпретацию и открывает новые теоретические и практические перспективы построения новых типов систем обработки данных в условиях действия широкого спектра НЕ-факторов [8].

С практической точки зрения развиваемый подход привлекателен тем, что используемый математический аппарат реализует расширенную парадигму мягких вычислений [7], в которой используются данные, представленные в канонической форме [1]. Предложенная в наших работах алгебраическая модель канонической формы представления данных [6] применима к широчайшему набору возможных типов данных различной размерности. В результате, с помощью малого числа сравнительно простых алгоритмов, основанных на топологических отношениях между объектами [4], удается решить широчайший круг задач, возникающих в анализе изображений, ГИС, Data Mining и т.д. [5].

1. НЕОПРЕДЕЛЕННЫЕ ОБЪЕКТЫ И ОПЕРАЦИЯ РЕГУЛЯРИЗАЦИИ

В контексте ГИС, анализа изображений и т.д. часто встречаются объекты, которые имеют достаточно сложную форму, плохо описываемую средствами аналитической геометрии (образ, гештальт). Часто для них применяется описание, связанное с описанием границы, отделяющей объект интереса от фона. Однако описание границы также приводит к появлению ряда НЕ-факторов. Согласно [9] объекты с неопределенной границей можно приближенно разделить на следующие классы:

· Объекты имеющие границу, но ее форма неизвестна, либо не может быть определена путем измерений;

· Объекты, которые не имеют определенной границы, или имеют границу, установленную условно (неопределенность определения);

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

Для подобных объектов в [10] введено топологическое определение понятия неопределенного объекта (vagueregion). Пусть - множество объектов и - совокупность подмножеств , удовлетворяющая следующим аксиомам:

, , (1)

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

Отношения между этими топологическими структурами задаются в виде:

, , , . (2)

Согласно [10] назовем подмножество топологического пространства регулярно замкнутым если выполняется условие

(3)

Для объектов, не являющихся регулярно замкнутыми, в [10] введена топологическая операция регуляризации, приводящая к следующему результату в обозначениях (1-5)

. (6)

Пример выполнения операции регуляризации над различными типами подмножеств плоскости приведен на следующем рисунке.

Рис. 1 Неопределённые объекты на плоскости до и после выполнения операции регуляризации

Отметим, что для описания неопределенных объектов используются клеточные комплексы (pointsets), при этом сама операция регуляризации (6) на клеточных комплексах является плохо формализованной [10].

В ряде наших работ (например, [4,5]) был предложен иной математический аппарат, основанный идеях представления неопределенных объектов путем покрытия регулярными элементами (декартовыми произведениями подмножеств в ортогональных системах координат), также приводящий в результате к регулярному в топологическом смысле результату [6].

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

Рис. 2 Неопределённые объекты на плоскости до и после выполнения операции регуляризации покрытием

В отличие от моделей, основанных на использовании клеточных комплексов [10], в разработанной нами модели все типы объектов покрываются гранулами одной и той же размерности, которые имеют одинаковое математическое представление в виде базовых элементов Грассманна [4].

Сравнивая результаты, представленные на Рис. 1 и 2, можно отметить, что независимо от применяемой процедуры, процесс регуляризации связан с потерей исходной информации. В наших работах предложен ряд алгоритмов, позволяющих строить оптимальные покрытия гранулами для исходных дискретных представлений объектов по критерию максимального правдоподобия [11] или по критерию сохранения исходной энтропии данных [12]. Исходя из выбранного критерия, разработанные алгоритмы позволяют выбрать параметры оптимального покрытия гранулами дискретного представления объекта интереса, вплоть до покрытия гранулами размером в один элемент, при котором исходная информация сохраняется полностью.

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

бинарный декартовый гранула данные

2. ТОПОЛОГИЧЕСКИЕ ОТНОШЕНИЯ МЕЖДУ НЕОПРЕДЕЛЕННЫМИ ОБЪЕКТАМИ

В работах по ГИС были предложены формальные определения бинарных топологических отношений между объектами [13]. В частности, S. Winter предложил методы построения отношений между двумерными неопределенными объектами, основанные на оценке пересечения объектов.

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

Нами предложена более общая система отношений, основанная на использовании понятия инкапсулирующей гранулы по 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].

3. ПРИМЕНЕНИЕ БИНАРНЫХ ОТНОШЕНИЙ НА ДЕКАРТОВЫХ ГРАНУЛАХ

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

Для этого используются предложенные в [5,6] модели декартовых гранул в цветовом пространстве. Следующий рисунок изображает образцы камуфляжной окраски и соответствующие цветовые гистограммы в пространстве HSV.

a) b)

Рис. 7. Цветовые гистограммы изображений вариантов камуфляжной раскраски для разных стран

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

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

ЗАКЛЮЧЕНИЕ

Предложенный в работе подход к формализации регулярного представления данных в условиях действия НЕ-факторов является эффективной с практической точки зрения формализацией идеи метода информационной грануляции, позволяющем формализовать понятие образа, гештальта и т.д., часто используемое как в теории L. Zadeh, так и в сходных подходах, в которых распознавание гештальта служит методом решения плохо формализованных задач [15]. Подобные задачи часто встречаются в технической и медицинской диагностике, распознавании в сложных условиях и т.п.

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

Литература

Zadeh L.A. From Сomputing with Numbers to Computing with Words - From Manipulation of Measurements to Manipulation of Perceptions// IEEE Transactions on Circuits and Systems. - 1999. - Vol.45. - P.105-119.

Zadeh L. A. Toward a Theory of Fuzzy Information Granulation and Its Centrality in Human Reasoning and Fuzzy Logic. Fuzzy Sets and Systems. - 1997. Vol.90. - P.111-127.

Zadeh L. A. Toward a Generalized Theory of Uncertainty//Information Sciences - Informatics and Computer Science. -2005. - Vol.172. - P.1-40.

Butenkov S. Granular Computing in Image Processing and Understanding// AIA 2004, Innsbruck, Austria. In Proceedings of the IASTED Conference In Artificial Intelligence and Applications. - 2004. - P.811-816.

Бутенков С.А., Жуков А.Л. Гранулирование геометрических данных в задачах автоматизированного проектирования// Известия вузов: ТТИ ЮФУ. Технические науки. - 2008. - № 12. - С.138-146.

Бутенков С.А. Алгебраические модели в задачах интеллектуального анализа многомерных данных// Математическая теория систем 2009 (МТС-2009). Сборник научных трудов международной научно-технической конференции (Москва, 26-30 января 2009). - С.93-101.

Бутенков С.А. Развитие парадигмы интеллектуального анализа многомерной информации применительно к теории информационной грануляции// Интегрированные модели и мягкие вычисления в искусственном интеллекте. Труды IV-ой Международной научно-практической конференции (Коломна, 28-30 мая 2007 г.). - М.: Физматлит, 2007. - С.188-194.

Нечеткие гибридные системы. Теория и практика// Под ред. Н.Г. Ярушкиной. - М.: Физматлит, 2007.

Camara G., Egenhofer M., Fonseca F., Monteiro A.M.V. What's in an Image// International Conference COSIT '01 - Santa Barbara - CA, 2001. In: Montello, D. R., (Ed.), Spatial Information Theory - A Theoretical Basis for GIS. - P.14-28.

Erwig M., Schneider M. Vague Regions// 5th International Symposium on Advances in Spatial Databases (SSD). Lecture Notes in Computer Science, №1262. - Berlin: Springer, 19777. - P.298-320.

Бутенков С.А., Бутенков Д.С., Кривша В.В. Гранулированные вычисления в системах интеллектуального анализа пространственных данных// Интеллектуальный анализ информации. Труды V Международной конференции (Киев, 2005 г.). - 2005. - С.108-117.

Бутенков С.А. Энтропийный подход к оценке качества гранулирования многомерных данных// Труды 11-ой национальной конференции по искусственному интеллекту с международным участием (Дубна, 28 сентября 3 октября 2008 г.). - М.: URSS, 2008. - С.331-340.

Egenhofer M. A Formal Definition of Binary Topological Relationships// Third International Conference on the Foundation of Data Organization and Algorithms, Paris. - 1989. - P.115-132.

Winter S. Location-based Similarity Measures of Regions// In: Fritch D. (Editor) ISPS Commission IV Symposium “GIS - between Vision and Applications”, Stuttgart, Germany. - 1999. - P.669-676.

Мазуров В.Д. Распознавание образов как средство автоматического выбора процедуры в вычислительных методах// Журнал вычислительной математики и математической физики. - 1970. - Т.10. - №6.

Размещено на Allbest.ur