uzluga.ru
добавить свой файл
1

ТОПОЛОГИЧЕСКИЕ МОДЕЛИ В ЗАДАЧАХ ИНФОРМАЦИОННОЙ ГРАНУЛЯЦИИ



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

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

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

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

Литература

  1. 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.

  2. 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.

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

  4. 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.

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

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

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

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

  9. Câmara 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.

  10. 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.

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

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

  13. 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.

  14. 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.

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