Применение методов спектральной кластеризации для обработки изображений



Дата04.07.2013
Размер29.2 Kb.
ТипДокументы
Н.К. ШАПОВАЛОВ

Научный руководитель – Е.В. ЧЕПИН, к.т.н., снс, доцент

Московский инженерно-физический институт (государственный университет)
ПРИМЕНЕНИЕ МЕТОДОВ СПЕКТРАЛЬНОЙ КЛАСТЕРИЗАЦИИ ДЛЯ ОБРАБОТКИ ИЗОБРАЖЕНИЙ
В статье рассматриваются методы спектральной кластеризации применительно к анализу изображений. Приводятся наиболее типичные способы решения задач, лежащих в основе этих методов. Указываются перспективные направления развития данного направления.
Кластеризация изображений является одним из наиболее перспективных направлений компьютерной науки. Она составляет неотъемлемую часть предобработки изображений, которая является важнейшим этапом при решении задач разработки систем машинного зрения.

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

В этой статье рассмотрим методы спектральной кластеризации как имеющие хорошую математическую основу и перспективные с точки зрения практики.

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

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

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

На третьем этапе производится рекурсивное разбиение полученных сегментов.

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

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

Одним из наиболее фундаментальных методов спектральной кластеризации является метод нормированных разрезов [1]. Этот метод, разработанный Ши и Маликом в 2000 году, является основой многих современных методов спектральной кластеризации.


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

Как показывают результаты работы спектральной кластеризации с применением метода Ланцоша, для получения приемлемых сегментов требуется очень большое число итераций. Поэтому в данный момент на базе IPPLabMSCo реализуется метод решения обобщенной задачи собственных значений, получивший название APL. Этот метод был разработан в 2007 году в Неапольском Университете [3].

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

Проблема спектральной кластеризации является очень важной как для теории, так и для приложений. Она затрагивает такие направления науки и техники, как вычислительная линейная алгебра, параллельные вычисления и машинное зрение.
Список литературы
1. J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888-905, 2000.

2. Парлетт Б. Симметричная проблема собственных значений. Численные методы: Пер. с англ. — М.: Мир, 1983. 384 с.

3. M. Aiello, F. Andreozzi, E. Catanzariti, F. Isgro, M. Santoro, "Fast convergence for spectral clustering," iciap, pp.641-646, 14th International Conference on Image Analysis and Processing (ICIAP 2007), 2007.

Похожие:

Применение методов спектральной кластеризации для обработки изображений iconАнализ и применение итеративных методов восстановления изображений в оптико-цифровых системах
Гаусса и Пуассона, характерных для регистрации изображений цифровыми матричными фотоприемниками. Выполнены численные эксперименты...
Применение методов спектральной кластеризации для обработки изображений iconГистограммные методы обработки изображений Фильтрация изображений в пространственной области
Восстановление изображений методом свертки и обратного проецирования в компьютерной томографии
Применение методов спектральной кластеризации для обработки изображений iconО сжатии изображений на основе биномиальных чисел
Традиционные методы кодирования в некоторой степени решают поставленную задачу [1]. Однако для получения большего эффекта необходимо...
Применение методов спектральной кластеризации для обработки изображений iconРабочая учебная программа По дисциплине: Обработка изображений По направлению
Цель дисциплины – изучение современных алгоритмов интеллектуального анализа и обработки изображений
Применение методов спектральной кластеризации для обработки изображений iconТопологические алгоритмы обработки цифровых изображений
Целью преподавания дисциплины является ознакомление слушателей с основными методами исследования топологических свойств цифровых...
Применение методов спектральной кластеризации для обработки изображений iconМетодика сравнительного анализа родственных эконометрических моделей
Приведены математические основы методов согласования ранжировок и классификаций, включая соответствующие теоремы с доказательствами....
Применение методов спектральной кластеризации для обработки изображений iconОбработка и передача изображений Применение многомасштабных моделей в задачах восстановления изображений
Когда искажение изображения обусловлено исключительно наличием аддитивного шума (1) записывается следующим образом: g[x,y]=f[x,y]+e[x,y]...
Применение методов спектральной кластеризации для обработки изображений iconКонтрольная работа по дисциплине «Цифровая обработка речи и изображений» на тему «Контурная фильтрация изображений»
Следовательно, для повышения качества изображения можно применять широкий круг методов; пригодность каждого из них зависит от целей...
Применение методов спектральной кластеризации для обработки изображений iconМатематическая морфология и обработка
За последующее время математическая морфология достигла состояния серьезного инструмента обработки изображений с основным применением...
Применение методов спектральной кластеризации для обработки изображений iconНейрокомпьютеры и их применение
Эффек-тивность использования нейрокомпьютеров для обработки радио и гидролокационной информации, причем как на уровне первичной,...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org