Интеллектуальный анализ изображений с помощью нечетких отношений на инкапсулирующих гранулах

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

Интеллектуальный анализ изображений с помощью нечетких отношений на инкапсулирующих гранулах

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

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

Введение

Изображения являются наиболее сложным типом данных с точки зрения интеллектуального анализа, но, в то же время, очень важным практически и сосредотачивающим усилия большого числа исследователей [Bezdek et al., 1992], [Baltsavias et al., 1999]. Причиной является то, что оцифрованное изображение в его исходном представлении (массив пикселов) представляет собой плохо структурированную информацию [Бутенков и др., 2004]. В процессе анализа изображения структурированность исходных данных обычно повышается за счет их геометрической интерпретации, а затем снова снижается при получении лингвистического описания изображения. На всех этапах этого процесса присутствуют различные виды НЕ-факторов [Нариньяни, 2004]. Многие исследователи приходят к необходимости использования нечетких методов интеллектуального анализа [Walker, 1998], [Bloch, 1999]. Тем не менее, большинство работ в этой области основано на “механическом” переносе методов классического анализа изображений в область нечетких методов и использовании классических парадигм обработки и анализа [Дуда и др., 1976] в нечеткой интерпретации [Tizhoosh, 1997], [Tizhoosh, 1999].

В ряде наших работ [Бутенков и др., 2003], [Бутенков и др., 2004], [Butenkov, 2004], [Бутенков и др., 2005] развивается альтернативный подход к представлению и анализу изображений, основанный на принципах теории информационной грануляции Л. Задэ [Zadeh, 1997]. В настоящей работе эти результаты распространяются на стадию анализа изображений. В статье вводятся перцептуальные отношения нечеткого взаимного положения и нечеткого взаимного расстояния между гранулами. В отличие от результатов, полученных в [Matsakis et al., 2001] и др., предложенные методы не требуют вычисления криволинейных интегралов, что значительно повышает их вычислительную эффективность.

1. Основы теории информационной грануляции

Информационной гранулой называется подмножество универсума , на котором определено отношение сходства, неразличимости и т.п. [Zadeh, 1999]. Множество гранул, которое содержит все объекты универсума, называется гранулированием универсума. Подмножество называется составной (не элементарной) гранулой если оно представляет собой объединение атомарных гранул [Zadeh, 1997].

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

Важное элементарное свойство декартовых гранул связано с их -срезами. Если , и , и - это -срезы , и соответственно, то .

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

Тогда декартова гранула определяемая как

грануляция информация изображение интеллектуальный

, (1)

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

Рис. 1. Гранула , ее проекции и инкапсулирующая гранула .

С понятием инкапсулирующей гранулы тесно связано фундаментальное понятие аппроксимирующего графа отношения. Согласно [Zadeh, 1999], граф на плоском множестве задается как

, (2)

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

2. Отношения сходства и иерархическая кластеризация

В предыдущих работах были разработаны новые типы отношений на декартовых гранулах [Бутенков и др., 2004], [Butenkov, 2004], позволяющие строить процедуры обработки гранулированной информации, в том числе и изображений. Наиболее часто встречается задача кластеризации данных (в различных постановках), которая в [Batyrshin et al., 2004] представлена как преобразование данного взвешенного нечеткого отношения сходства в нечеткое отношение эквивалентности. При этом определяется иерархия нечетких отношений эквивалентности и, как результат, иерархия разбиений множества объектов на классы эквивалентности. Основной целью введения иерархии является сохранения классов сходства.

Пусть задано множество пространственных гранул универсума и -нечеткое отношение(сходства), т.е. удовлетворяет на условиям

· симметричности ;

· рефлексивности .

Отношения сходства, удовлетворяющие условию -транзитивности , называются взвешенными нечеткими отношениями эквивалентности.

Отношению сходства двойственно отношение различия , удовлетворяющее на условиям

· симметричности ;

· антирефлексивности .

Отношение различия, удовлетворяющее свойству -транзитивности в кластерном анализе называется ультраметрикой [Bloch, 1999].

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

Теперь мы можем ввести схему двухэтапной иерархической кластеризации на пространственных гранулах в виде:

, (3),

где - оператор коррекции нечеткого отношения сходства [Bloch, 1999], удовлетворяющий условию . Оператор определяет процедуру -транзитивного замыкания взвешенных отношений сходства. Выражение (2) описывает метод иерархической пространственной кластеризации, использованный в данной работе и развивающий идеологию работы [Batyrshin et al., 2004].

3. Топологические отношения между двумерными объектами

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

Наиболее распространенным подходом является использование топологических отношений [Egenhofer, 1996], а также основанных на них систем нечетких предикатов [Zimmerman et al., 1993]. Эта группа методов дает, скорее, логическое описание, чем количественное, хотя для некоторых предикатов введены числовые меры [Winter, 1999].

Дополнительной к ним является группа методов, основанных на использовании проекций некоторых величин на плоскости на двумерные объекты, наиболее развитым из которых является метод -гистограмм [Sjahputera et al., 2000]. В настоящей работе предложен метод построения отношений взаимного положения гранул с использованием мер на инкапсулирующих декартовых гранулах (1) и отношениях (2). Подобные методы имеют линейную вычислительную сложность благодаря использованию геометрического подхода [Бутенков, 2003], [Бутенков и др., 2003]. В наших работах используется геометрическая информация на декартовых гранулах, в отличие от работ, посвященных использованию статистических методов на декартовых гранулах [Baldwin et al., 1997].

Для введенных в [Бутенков и др., 2003] гранулированных представлений изображения определим меру единичной параметризованной гранулы на декартовой плоскости в духе примитивных элементов Грассманна:

. (4)

Тогда инкапсулирующую гранулу (1) для двух произвольных непересекающихся декартовых гранул можно задать как:

, (5)

где параметры инкапсулирующей гранулы определяются как

, ,

,

.

Перцептуальный подход основывается на известной парадигме [Zimmerman et al., 1993], cогласно которой, меры сходства между объектами должны строиться на основе выделения тех же особенностей, которые выделяет зрительная система человека [Бутенков и др., 2004].

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

a. b.

Рис. 2 Определение отношений положения объекта относительно начала координат (a) и относительно ссылочного объекта (b).

Введем псевдометрику на гранулах и (2), исходя из метрических аксиом раздела 3, учитывающих конечные размеры гранул: и . Тогда можно записать для взаимного положения гранул и с учетом (1) и (2):

(6)

где параметры, отмеченные знаком +, относятся к - инкапсулирующей грануле (5), а - функция интенсификации, представляющая собой непрерывный аналог нечеткого оператора из (2) [Бутенков и др., 2005]. Выражение (4) определяет нечеткое отношение .

Используя введенные ранее меры на гранулах [Бутенков и др., 2003], введем нечеткий аналог косинуса угла между пространственными гранулами в виде:

, (7)

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

Следующий рисунок визуализирует отношения (6) (a и b) и (7) (c) для случая единичных гранул (пикселов). В этом случае они приобретают свойства, близкие к свойствам евклидовой метрики.

a. b. c.

Рис. 4 Наглядное изображение графиков отношений между единичными гранулами.

Введенные отношения (6) и (7) позволяют решать широкий круг задач анализа гранулированных изображений, подобно тому, как евклидово расстояние и угол между векторами позволяют строить аналитическую геометрию.

4. Применение отношений положения на декартовых гранулах

Предложенные методы анализа были использованы в базовом программном обеспечении анализа изображений. В его основу положены методы оптимального гранулирования изображений [Бутенков и др., 2005], образующие новую парадигму обработки изображений.

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

Рис. 5 Выделенные на изображении объекты анализа A,B,C.

Результатом анализа изображения являются лингвистические оценки взаимного расстояния и положения объектов сложной формы.

5. Перспективы развития метода

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

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

Литература

1. [Аль-Доуяни и др., 2005] Аль-Доуяни С.Х.С., Бутенков С.А. Синергетический подход к задаче генерализации при обучении нечетких нейронных сетей для обработки изображений. // Искусственный интеллект, №4, 2005, с. 319-324.

2. [Бутенков, 2003] Бутенков С.А. Формализация неопределенности в многомерных данных. // Сб. трудов Международной конференции „Интеллектуальные системы” (IEEE AIS'03), Москва, Физматлит, 2003, с. 104-113.

3. [Бутенков и др., 2003] Бутенков С.А., Каркищенко А.Н., Кривша В.В. Перцептуальный подход к анализу гранулированных изображений в интеллектуальных системах. // Искусственный интеллект, №3, 2003, с. 209-218.

4. [Бутенков и др., 2004] Бутенков С.А., Кривша В.В. Регуляризация представления и обработки плохо структурированных изображений методами гранулированных вычислений. // Сб. трудов Международной конференции IEEE AIS'04, Москва, Физматлит, 2004, т.2, с. 104-113.

5. [Бутенков, 2005] Бутенков С.А. Вычисления со словами в задачах интеллектуальной обработки многомерной информации. // Сб. трудов III Международного семинара “Интегрированные модели и мягкие вычисления в искусственном интеллекте”, Коломна, 2005 г., с. 133-139.

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

7. [Дуда и др., 1976] Дуда Р., Харт П. Распознавание образов и анализ сцен. - М.:Мир, 1976.

8. [Нариньяни, 2004] Нариньяни А.С. НЕ-факторы 2004. // Сб. трудов Девятой Национальной конференции по искусственному интеллекту КИИ-2004, Москва, Физматлит, 2004, т.1, с. 420-432.

9. [Baldwin et al., 1997] Baldwin J., Martin T., and Shanahan L. Fuzzy logic methods in vision recognition. // Fuzzy Logic: Applications and Future Directions Workshop, London, UK, 300-316, 1997.

10. [Baltsavias et al., 1999] Baltsavias E., Hahn M. Integration of Image Analysis and GIS. // Fritch D. (Editor) ISPS Comission IV Symposium “GIS - between Vision and Applications”, Stutgart, Germany, 1999, pp. 669-676.

11. [Batyrshin et al., 2004] Batyrshin I., Rudas Т., Klimova A. On general scheme of invariant clustering procedures based on fuzzy similarity relation. // Proc. of Int. Conference on Fuzzy Sets and Soft Computing in Economics and Finance (FSSCEF 2004, June 17-20, 2004, St. Petersburg, Russia), vol. I. - pp.122-129.

12. [Bezdek et al., 1992] Bezdek J.C., Pal S.K. (editors) Fuzzy Models for Pattern Recognition. IEEE Press, 1992

13. [Bloch, 1999] Bloch I. On fuzzy distances and their use in image processing under imprecision // Pattern recognition, 32:1873-1895, 1999.

14. [Butenkov, 2004] Butenkov S. Granular Computing in Image Processing and Understanding. // Proc. IASTED International Conf. On AI and Applications “AIA 2004”, Innsbruk, Austria, February 10-14, 2004.

15. [Egenhofer, 1996] Egenhofer M., A formal definition of binary topological relationships. // Proc. of the Third International Conference on the Foundation of Data Organization and Algorithms, Paris, 1989.

16. [Matsakis et al., 2001] Matsakis P., Laurent W. “A New Way to Represent the Relative Position between Aerial Objects”// IEEE Trans. On ”Pattern Analysis and Machine Intelligence”, 2001, vol. 21, №7, pp. 634-643.

17. [Tizhoosh, 1997] Tizhoosh H.R. On a Systematic Introduction into Fuzzy Image Processing. // Proc. AFN'97 Annual Meeting, Magdeburg, Germany, pp. 39-45.

18. [Tizhoosh, 1999] Tizhoosh H.R. “Fuzzy Image Processing”, Springer, 1997, ISBN: 3-540-63137-2.

19. [Walker, 1998] Walker E. Perspectives on Fuzzy Systems in Computer Vision. // Proc. of the Annual Conference of the North American Fuzzy Information Processing Society [NAFIPS '98], August, 1998, pp. 296-300.

20. [Winter, 1999] Winter S. Location-based similarity measures of regions. // Fritch D. (Editor) ISPS Comission IV Symposium “GIS - between Vision and Applications”, Stutgart, Germany, 1999, pp. 669-676.

21. [Zadeh, 1979] Zadeh L. Fuzzy sets and Information Granularity. // In “Advances in Fuzzy Set Theory and Applications”, M. Gupta, R. Ragade, and R. Yager, Eds. Amsterdam, The Netherlands: North-Holland, 1979, pp. 3-18.

22. [Zadeh, 1997] Zadeh L. Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic. // Fuzzy Sets Syst., vol. 90, pp. 111-127, 1997.

23. [Zadeh, 1999] Zadeh L. From Computing with Numbers to Computing with Words -- From Manipulation of Measurements to Manipulation of Perceptions. // IEEE Trans. // Circuits and Systems - Fundamental Theory and Applications, vol. 45, №1, 1999, pp. 105-119.

24. [Zimmerman et al., 1993] Zimmerman K., Freksa C. Qualitative Spatial Reasoning Using Orientation, Distance, and Path Knowledge. // Proc. of Workshop on Spatial Reasoning of the Int. Join Conference on Artificial Intelligence (IJCAI-93). Chambery, France, 1993.

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