автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Агломеративная сегментация и поиск однородных объектов на растровых изображениях

МиГ™

004600443________'

Митропольский Николай Николаевич

АГЛОМЕРАТИВНАЯ СЕГМЕНТАЦИЯ И ПОИСК ОДНОРОДНЫХ ОБЪЕКТОВ НА РАСТРОВЫХ ИЗОБРАЖЕНИЯХ

05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

1 АПР 2010

Москва-2010

Работа выполнена в государственном образовательном учреждении высшего профессионального образования «Московский государственный технологический университет «СТАНКИН» на кафедре «Управление и информатика в технических системах»

Научный руководитель: доктор технических наук, профессор

Ковшов Евгений Евгеньевич

Официальные оппоненты: доктор технических наук, профессор

Андреев Юрий Сергеевич

кандидат технических наук, доцент Выжигин Александр Юрьевич

Ведущая организация: Открытое акционерное общество

«Научно-исследовательский ордена Трудового Красного Знамени кинофотоинститут» (ОАО «НИКФИ»)

Защита состоится «29» апреля 2010 г. в 12— часов на заседании диссертационного совета Д 212.147.03 при Московском государственном университете печати (127550 Москва, ул. Прянишникова, 2А).

С диссертацией можно ознакомиться в библиотеке МГУП.

Автореферат разослан «26» марта 2010 г.

Учёный секретарь диссертационного совета д. т. н., профессор ' Агеев В.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Работы в области обработки, сегментации и поиска объектов на изображениях велись и ведутся весьма интенсивно как отечественными (Андреев Ю.С., Банковский Ю.М., Богуславский A.A., Вежневец В.П., Казанов М.Д., Сергеев В.В.), так и зарубежными (Б. Рассел, Дж. Малик, М. Андретто, Юй-Ли, Юй-Цзинь Чжан, Дж. Ши, П. Виола, М. Джонс) учёными. К настоящему времени выработано множество подходов к сегментации изображения, но ни один из них не стал универсальным. В зависимости от происхождения, текстуры, качества, размера, предмета исследований и множества других параметров имеет смысл применять различные способы сегментации. Причём применимость конкретного способа для изображений определённого типа исследуется, в основном, экспериментально, и, как правило, выбранный способ сегментации обладает довольно узкой специализацией и может быть непригодным для изображений, отклоняющихся от «типичных случаев». Исходя из изложенного, актуальной задачей является разработка эффективных методов сегментации, сочетающих преимущества различных подходов и увеличивающих тем самым точность, скорость и робастность процесса сегментации.

Объект исследования. Объектом исследования диссертационной работы являются растровые полихроматические изображения (далее изображения) как

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

Предмет исследования. Предметом исследования диссертационной работы являются методы сегментации изображений и поиска объектов на них.

Целью работы является разработка комбинированного метода сегментации и применение его для поиска однородных объектов на изображениях. Базой для этого метода был выбран хорошо зарекомендовавший себя на практике метод mean-shift.

В процессе работы решались следующие научные задачи:

1. Выявление методов и исследование подходов к сегментации и поиска объектов на цветных изображениях.

2. Разработка метода, позволяющего учитывать информацию о градиенте изображения при сегментации методом mean-shift.

3. Разработка эффективного алгоритма сегментации на базе метода mean-shift и агломеративной стратегии.

4. Разработка методики, позволяющей автоматически подбирать параметры метода mean-shift для каждого этапа агломеративной сегментации.

5. Применение разработанного метода в среде прикладной информационной системы для поиска однородных объектов на изображении.

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

Методы исследований. При решении задач, поставленных в работе, были использованы методы системного анализа, статистической обработки данных, дискретной математики, кластерного анализа.

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

1. Разработан комплексный метод сегментации изображений на основе применения агломеративной стратегии и метода mean-shift.

2. Исследованы различные алгоритмы и структуры данных в рамках разработанного метода агломеративной сегментации.

3. Разработан алгоритм поиска однородных объектов на изображениях при помощи агломеративной сегментации.

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

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

консультативного центра (г. Москва). Помимо этого, определена целесообразность использования предложенных методик при создании прикладного программного обеспечения информационных систем в научно-практических разработках малого предприятия ООО «Компьютерные системы и технологии» (г. Москва).

Упомянутые выше методики внедрены в учебный процесс ГОУ ВПО МГТУ «Станкин», используются при подготовке бакалавров по направлению 220200.62 «Автоматизация и управление» и магистрантов по магистерской программе 220200.68-20 «Человеко-машинные системы управления». Материалы диссертационной работы использованы в качестве методологической основы при разработке курса лекций и практических занятий по дисциплинам «Информатика», «Программирование и основы алгоритмизации» и специальной дисциплине «Интеллектуальные системы обработки информации».

Апробация работы. Результаты работы докладывались на научно-практической конференции «Автоматизация и информационные технологии (АИТ)» (г. Москва, ГОУ ВПО МГТУ «Станкин», 2008, 2009); XI-й научной конференции МГТУ «Станкин» и «Учебно-научного центра математического моделирования МГТУ «Станкин» - ИММ РАН» по математическому моделированию и информатике (г. Москва, ГОУ ВПО МГТУ «Станкин», 2008); 4-ом международном форуме MedSoft-2008 (г.Москва, 2008), XI международной конференции «ПРОТЭК'08» (г. Москва, ГОУ ВПО МГТУ «Станкин», 2008); школе-семинаре «Задачи системного анализа, управления и обработай информации» (г. Москва, ГОУ ВПО МГУП, 2008, 2009); всероссийской студенческой научно-технической конференции «Прикладная информатика и математическое моделирование» (г. Москва, ГОУ ВПО МГУП, 2009) и конференции «Инновации в экономике» (г. Москва, ГОУ ВПО МГТУ «Станкин», 2009).

Публикации по теме диссертации. По теме диссертационной работы опубликовано И научных работ, из них 7 основных, в том числе 2 статьи в журналах, входящих в перечень ВАК РФ.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Рассматриваются существующие цветовые модели. Отдельно рассмотрено используемое в работе цветовое пространство Luv (L - яркость; и - переход от зелёного к красному; v - переход от синего к жёлтому). Евклидово расстояние в этом представлении является визуально равномерным и позволяет дать более адекватную оценку различию цветов точек. Проанализированы задачи перевода изображения из одной цветовой модели в другую.

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

Приводится обзор основных методов обработки изображений. Представлены пространственные методы, рассматривающие изображение как совокупность точек в цветовом и координатном пространствах. Также рассмотрены пространственные методы, основанные на гистограммах. Упомянуты частотные методы обработки изображения, основанные на модификации сигнала, формируемого путём применения к изображению двумерного дискретного преобразования Фурье, и методы морфологической обработки изображения, представляющие изображение в виде совокупности объектов, представленных множеством точек.

Осуществляется обзор наиболее популярных методов поиска объектов на изображении, приводятся метод обратной проекции (М. Дж. Свейн, Д. Баллард), нейросетевые методы (Н. Роули) метод П. Виолы и М. Джонса, а также метод Н. Дал алы и Б. Триггса. Отдельно исследуется роль сегментации в поиске объектов на изображении. Рассматриваются основные подходы к сегментации изображения. Иерархические методы, к которым относят методы, основанные на последовательном объединении (или разъединении) кластеров по принципу их близости друг к другу (М. Борсогга, Р. Ромен-Рольдан). Представлено решение задачи сегментации при помощи самоорганизующихся карт Кохонена (П. Кампаделли). Рассмотрен подход к сегментации, основанный на выделении контуров из изображения путём вычисления градиента цвета с использованием матриц Собела (Дж. Кенни, Дж. Малик), освещены методы, использующие теорию графов (Юй-Цзинь Чжан, Дж. Малик, Дж. Ши).

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

Во второй главе описывается применение фильтра Собела с целью увеличения скорости и робастности сегментации методом mean-shift за счет использования информации о градиенте изображения. Рассмотрен метод mean-shift в его классическом понимании, предложенном Фукунагой и Хостетлером в 1975 году. Отмечается, что его преимуществом является отсутствие необходимости в изначальных знаниях о количестве кластеров или о каких-либо их признаках. В рамках метода находится значение функции оценки

плотности. Единственным параметром алгоритма является размер окна h.

Выделяются недостатки метода mean-shift:

1. Невысокая скорость. Процедура вычисления вектора среднего сдвига требует больших вычислительных ресурсов.

2. Чувствительность к выбросам. В результате сегментации методом mean-shift появляются небольшие области, не несущие информации о семантической структуре изображения, но требующие затрат на обработку при интеллектуальном анализе результатов сегментации.

3. Чувствительность к размерам окна. Единственным параметром кластеризации методом mean-shift является размер окна А и его значение оказывает значительное влияние на результат.

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

Вычисление вектора среднего сдвига происходит для каждой точки независимо и в работе рассматривается методика вычисления, основанная на выполнении процедуры mean-shift параллельно для каждой точки. Это приводит к значительному увеличению скорости процедуры. Проводятся эксперименты, показывающие, что по скорости выполнения процедуры результаты «параллельного mean-shift» сходны с тем, что получаются при вычислении вектора среднего сдвига не для всех точек. Обосновывается нецелесообразность совмещения этих двух методов. Делается вывод, что в случаях, если вычислительная система обладает соответствующими возможностями, имеет смысл применять параллельный сдвиг, в противном случае для повышения быстродействия придётся пожертвовать качеством сегментации и вычислять вектор не для всех точек.

Представлен подход к сегментации изображений с ограничением по градиенту. Этот метод основан на применении процедуры mean-shift с использованием информации о градиенте как ограничивающего фактора при разрастании областей.

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

В третьей главе описывается метод сегментации, основанный на совместном использовании метода mean-shift и ашомеративной стратегии.

Решаются следующие проблемы метода mean-shift:

1. Необходимость выбирать размер окна h при настройке алгоритма на работу с конкретными данными.

2. Значительное возрастание времени работы при увеличении размера окна h.

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

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

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

Состоние 5 ' 1

Средний сдвиг 4

Состояние 4

Средний сдвиг 3

Состояние 3

Средний сдвиг 2

Состояние 2

Средний сдвиг 1

Состояние 1

Рис. 1. Агломеративная стратегия

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

Предложенный в данной работе метод состоит в ограничении всего набора точек гиперпараллелепипедом с объёмом V (рис. 2) и разбиению его на п

субпараллелепипедов с объемом:

У

п

где п - количество точек. То есть, если все точки были бы распределены по пространству равномерно, то каждая находилась бы в своём гиперпараллелепипеде с объёмом Ут. Соответственно, стороны гиперпараллелепипеда и будут определять размеры окна, то есть параметр к. Иными словами размер окна для 1-го измерения будет определяться по формуле:

где р, - коэффициент компоненты, определяется пропорционально сторонам основного гиперпараллелепипеда, <1 - размерность пространства, к -коэффициент, вводимый для того чтобы иметь возможность управлять количеством формируемых кластеров. Рекомендуемое значение к-\, приводящее к равномерному распределению пространства между кластерами.

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

В предложенном алгоритме не требуется введение специального критерия останова агломеративной кластеризации, так как в определённый момент точки перестают попадать в «окно друг к другу» и кластеры перестанут объединяться.

(2)

г

Рис. 2. Выбор размера окна

При k=l это означает, что пространство поделено между точками равномерно, меньшие значения к вызовут останов раньше. В случаях, если требуется избежать останова, необходимо увеличивать коэффициент к с каждым этапом.

Рассмотрены различные варианты алгоритмов и структур данных для хранения точек на каждом этапе сегментации. Основным требованием является обеспечение быстрого выбора всех точек, лежащих в окрестности h от точки, для которой осуществляется процедура mean-shift. Рассмотрено традиционное решение данной задачи, которым являются kd-деревья. В общем случае они демонстрируют высокую производительность. Для сокращения времени, затрачиваемого на первом этапе агломеративной сегментации, предложено использовать двумерные массивы. Это возможно, поскольку координаты х, у на первом этапе образуют плотную сетку. Показана эффективность данного метода при небольших (меньше 20 пикселей) размерах окна в пространственной области.

Рассмотрено применение алгоритмов, описанных в главе 2, на первом этапе агломеративной сегментации. Экспериментально подтверждено, что изменение алгоритма на первом этапе в этом случае не оказывает значительного влияния на результат.

Приводятся графики зависимости времени работы от размера изображения для различных вариаций алгоритмов (рис. 3).

1 - K-means

2 - Только kd-tree

3 - Разрастание

регионов

4 - N-cuts

5 - Параллельный

mean-shift

6 - Mean-shift +

Собел

50000 100000

размер изображения [пиксели]

Рис. 3. Зависимость времени работы алгоритмов от размера обрабатываемого изображения

Из графиков видно, что наилучшую производительность демонстрирует агломеративная сегментация, на первом этапе которой применяется метод mean-

shift, специализированный для обработки изображений, совместно с фильтром Собела. Метод сегментации, основанный на параллельном mean-shift, демонстрирует близкие по скорости результаты и может быть использован в тех случаях, когда первый метод не может быть применён, например, по причине того, что он не включает в результирующие сегменты границы этих сегментов. Приведён метод, использующий на первом этапе разрастание регионов, и чистый агломеративный метод, использующий только kd-деревья. Последний демонстрирует невысокую производительность по сравнению с остальными. По представленному на рис. 3 графику можно оценить его производительность в случае, если входным объектом является не изображение, а просто набор точек в Евклидовом пространстве, поскольку данный метод не опирается на какую-либо специфику изображений. Для сравнения производительности приведены два популярных метода сегментации: k-means и normalized cuts (N-cuts) (они обозначены пунктирными линиями). Как можно заметить, предложенные в данной работе методы во многом их превосходят. Данное тестирование проводилось на выборке из лесных пейзажей, характеризующихся наличием крупных одноцветных областей и однородной цветовой гаммой. При этом, агломеративный метод в среднем превосходит по производительности метод k-means в 10,5 раз и метод normalized-cuts в 3,6 раза.

Проведено сравнение производительности агломерагавного метода с методом normalized-cuts и традиционным mean-shift в задачах сегментации гистологических снимков крови (рис. 4) и сегментации снимков языка пациента (рис. 5). В табл. 1 приведено среднее значение, отражающее, во сколько раз больше времени необходимо этим алгоритмам для решения указанных задач по сравнению с агломеративным mean-shift.

70000

1

60000 50000 f 40000

2

1 - N-cuts

2 - Традиционный

mean-shift 3 - Агломеративный

й 30000 о.

mean-shift

со

20000

10000

3

о

о

50000 100000 150000 размер изображения [пиксели]

Рис. 4. Зависимость времени работы различных методов сегментации от размера изображения при сегментации гистологических снимков крови

250000

200000

150000

2L

100000

50000

0 50000 100000

размер изображения (пиксели]

1 - Традиционный

mean-shift

2 - N-cuts

3 - Ашомеративный

mean-shift

150000

Рнс. 5. Зависимость времени работы различных методов сегментации от размера изображения при сегментации снимков языка человека

Таблица 1. Отношение времени, затрачиваемого другими алгоритмами сегментации, ко времени, затрачиваемому агломеративным mean-shift

Наименование алгоритма Сегментация гистологических снимков кровн Сегментация снимков языка человека Сегментация снимков лесных пейзажей

Normalized cuts 17 8,1 3,6

Традиционный mean-shift 9,8 84 82

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

В четвёртой главе описывается применение разработанного подхода к сегментации для поиска однородных объектов на растровых полихроматических изображениях.

Предложена модель обработки результатов сегментации (рис. 6). Каждый

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

Рассматривается поиск однородных объектов на изображении, как частный случай обработки результатов сегментации. При этом предполагается, что объекты являются одноцветными, то есть не имеют резких и значительных изменений в цвете (такими объектами могут являться: малооблачное небо, лес, поле, дорога, море, язык пациента, окрашенные клетки и ткани при гистологических исследованиях) и имеют чётко выделенную границу. Таким образом, поиск состоит в бинарной классификации каждого сегмента - является ли он искомым объектом или нет. Для реализации бинарной классификации используется метод сопоставления с образцом. На рис. 7 представлена функциональная схема такого метода. На первом этапе происходит сегментация изображения. Кроме того, на вход системы поступает образец, с которым осуществляется сравнение всех полученных на этапе сегментации областей.

Изображение

-П

Mean-shift

кластеры Mean-shift

кластеры

кластеры Mean-shift

Рис. б. Многомасштабная сегментация методом mean-shift

Поскольку сегменты характеризуются как цветом, так и формой, сравнение производится и по цвету, и по форме. Далее, по результатам сравнения происходит фильтрация сегментов, в итоге, отбираются сегменты, соответствующие образцу. Для сравнения по цвету используются цветовые гистограммы, а для сравнения по форме используется метод shape contexts (Д. Малик, С. Белонж).

Большое количество мелких сегментов

Среднее количество средних сегментов

Небольшое количество крупных сегментов

О Б Р А Б О Т К А

Изображение

Сегментация (mean shift)

"Л

Образец

Сегменты

Л-""''

¿>

Сравнение по цвету (гистограммы)

Т

Сравнение по форме (shape context)

а

Найденные совпадения

Фильтрация (порог)

Рис. 7. Функциональная схема системы поиска однородных объектов по образцу

Рассмотрен способ повышения эффективности разработанного алгоритма поиска за счёт использования эвристики, основанной на сопоставлении цвета точки сходимости mean-shift и цветовой гистограммы искомого объекта. Также рассмотрена методика совместного использования метода Виолы-Джонса и предложенного в данной работе метода поиска однородных областей.

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

Образец

П

пЛк ®

•

Исходное изображение

Результат

Рис. 8. Поиск шлемовидных эритроцитов

Программная реализация прикладной информационной системы включает в себя четыре основных модуля:

1. Модуль сегментации изображений, в котором реализованы рассмотренные в работе методы сегментации, включая mean-shift.

2. Модуль mean-shift-кластеризации, реализующий кластеризацию многомерных данных в Евклидовом пространстве.

3. Модуль агломеративной сегментации, использующий функциональность первых двух для реализации комплексного метода сегментации изображений.

4. Модуль поиска объектов на изображении по заданному шаблону.

Разработанные алгоритмы реализованы на платформе Java с

использованием языка программирования Scala. Для повышения эффективности процедуры сегментации при использовании параллельных вычислений, применена технология Nvidia CUDA.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ

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

К результатам выполненных исследований в рамках диссертационной работы можно отнести следующее:

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

2. Проведён обзор существующих методов сегментации изображений и поиска объектов на них.

3. Разработан комплексный подход к сегментации изображений, основанный на совместном применении метода mean-shift и фильтра Собела.

4. Разработана методика выбора размеров окна, позволяющая автоматизировать подбор параметров кластеризации данных методом mean-shift.

5. Разработан агломеративный подход на основе метода mean-shift, значительно увеличивающий производительность и расширяющий возможности этого метода

6. Исследованы различные вариации алгоритмов и структур данных,

применяемых в рамках агломерагивной mean-shift-сегментации.

7. Разработан программный метод поиска однородных объектов на изображении, основанный на использовании агломеративной mean-shift-сешентации.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ КАНДИДАТСКОЙ ДИССЕРТАЦИИ

В изданиях, рекомендованных ВАК РФ:

1. Митропольский, Н. Н. Сегментация и идентификация контуров объектов на цифровых изображениях / Н. Н. Митропольский, Е. Е Ковшов. // Известия высших учебных заведений. Проблемы полиграфии и издательского дела. - 2008. - №5. - С. 19-28.

2. Митропольский, Н. Н. Агломеративная стратегия при сегментации растровых изображений методом среднего сдвига в прикладной компьютерной системе / Н. Н. Митропольский, Е. Е. Ковшов, Н. Н. Хуэ, Н. Ч. Минь // Системы управления и информационные технологии, 2009 -№3 - С. 80-83.

В других изданиях:

3. Митропольский, Н. Н. Автоматизация анализа гистологических изображений при исследовании влияния факторов окружающей среды на здоровье человека / Н. Н. Митропольский., Е. Е. Ковшов // Производство. Технология. Экология. - М.: «Янус-К», 2008 - С. 125-128.

4. Ковшов, Е.Е. Сегментация цифровых изображений языка человека при автоматизированной диагностике / Е. Е. Ковшов, Н. Н. Митропольский // 4й международный форум MedSoft-2008. Медицинские информационные технологии. -М. 2008. - С. 62-64.

5. Митропольский, Н. Н. Автоматизация процедуры сегментации растровых полихроматических изображений на основе алгоритмов Mean-shift и Собела / Н. Н. Митропольский // Задачи системного анализа, управления и обработки информации: Межвузовский сборник научных трудов. -М.:МГУП, 2008. - Вып. 2. - С. 95-102.

6. Митропольский, Н. Н. Применение k-мерных деревьев в системах интеллектуального анализа данных при кластеризации методом среднего сдвига (mean-shift) / Н. Н. Митропольский // Инновации в экономике -2009: материалы научной конференции молодых учёных и студентов. - М: ГОУ ВПО МГТУ «Станкин», 2009 - С. 94-96.

7. Митропольский, Н. Н. Агломеративная стратегия при кластеризации данных методом среднего сдвига. / Н. Н. Митропольский //Прикладная информатика и математическое моделирование: Межвузовский сборник научных трудов. - М.:МГУП, 2009. - С. 105-110.

Введение.

Глава 1. Обзор задач и методов цифровой обработки изображений.

1.1. Компьютерное зрение и прикладные задачи.

1.2. Основные методы обработки изображений.

1.3. Поиск и распознавание объектов на растровых изображениях.

1.4. Сегментация изображений.

1.5. Постановка задачи исследовательской работы.

Глава 2. Комплексное применение метода mean-shift и фильтра Собела

2.1. Метод mean-shift.

2.2. Построение карты градиента на основе фильтра Собела.

2.3. Сегментация изображений с ограничением по градиенту.

2.4. Сегментация изображений с применением алгоритма разрастания регионов «по пути наименьшего сопротивления».

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

2.6. Оценка вычислительной сложности разработанных алгоритмов сегментации.

2.7. Выводы по главе 2.

Глава 3. Агломеративная сегментация методом mean-shift.

3.1. Общие принципы агломеративной стратегии.

3.2. Автоматический выбор размера окна. Вес точки.

3.3. Вариации структур данных и алгоритмов на различных этапах агломеративной сегментации.

3.4. Выводы по главе 3.

Глава 4. Поиск однородных объектов.

4.1. Многоуровневое выделение сегментов.

4.2. Сопоставление с образцом.

4.3. Вычислительный эксперимент и сочетание с другими алгоритмами

4.4. Программная реализация.

4.5. Выводы по главе 4.

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

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

Работы в области обработки, сегментации и поиска объектов на изображениях велись и ведутся весьма интенсивно как отечественными (Андреев Ю.С., Баяковский Ю.М., Богуславский А.А., Вежневец В.П., Казанов М.Д., Сергеев В.В.), так и зарубежными (Б. Рассел, Дж. Малик, М. Андретто, Юй-Ли, Юй-Цзинь Чжан, Дж. Ши, П. Виола, М. Джонс) учёными. К настоящему времени выработано множество подходов к сегментации изображения, но ни один из них не стал универсальным. В зависимости от происхождения, текстуры, качества, размера, предмета исследований и множества других параметров имеет смысл применять различные способы сегментации. Причём применимость конкретного способа для изображений определённого типа исследуется, в основном, экспериментально, и, как правило, выбранный способ сегментации обладает довольно узкой специализацией и может быть непригодным для изображений, отклоняющихся от «типичных случаев». Исходя из изложенного, актуальной задачей является разработка эффективных методов сегментации, сочетающих преимущества различных подходов и увеличивающих тем самым точность, скорость и робастность процесса сегментации.

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

Предмет исследования. Предметом исследования диссертационной работы являются методы сегментации изображений и поиска объектов на них.

Целью работы является разработка комбинированного метода сегментации и применение его для поиска однородных объектов на изображениях. Базой для этого метода был выбран хорошо зарекомендовавший себя на практике метод mean-shift.

В процессе работы решались следующие научные задачи:

1. Выявление методов и исследование подходов к сегментации и поиска объектов на цветных изображениях.

2. Разработка метода, позволяющего учитывать информацию о градиенте изображения при сегментации методом mean-shift.

3. Разработка эффективного алгоритма сегментации на базе метода mean-shift и агломеративной стратегии.

4. Разработка методики, позволяющей автоматически подбирать параметры метода mean-shift для каждого этапа агломеративной сегментации.

5. Применение разработанного метода в среде прикладной информационной системы для поиска однородных объектов на изображении.

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

Методы исследований. При решении задач, поставленных в работе, были использованы методы системного анализа, статистической обработки данных, дискретной математики, кластерного анализа.

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

1. Разработан комплексный метод сегментации изображений на основе применения агломеративной стратегии и метода mean-shift.

2. Исследованы различные алгоритмы и структуры данных в рамках разработанного метода агломеративной сегментации.

3. Разработан алгоритм поиска однородных объектов на изображениях при помощи агломеративной сегментации.

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

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

Упомянутые выше методики внедрены в учебный процесс ГОУ ВПО МГТУ «Станкин», используются при подготовке бакалавров по направлению 220200.62 «Автоматизация и управление» и магистрантов по магистерской программе 220200.68-20 «Человеко-машинные системы управления». Материалы диссертационной работы использованы в качестве методологической основы при разработке курса лекций и практических занятий по дисциплинам «Информатика», «Программирование и основы алгоритмизации» и специальной дисциплине «Интеллектуальные системы обработки информации».

Апробация работы. Результаты работы докладывались на научно-практической конференции «Автоматизация и информационные технологии (АИТ)» (г.Москва, ГОУ ВПО МГТУ «Станкин», 2008, 2009); XI-й научной конференции МГТУ «Станкин» и «Учебно-научного центра математического моделирования МГТУ «Станкин» - ИММ РАН» по математическому моделированию и информатике (г.Москва, ГОУ ВПО МГТУ «Станкин», 2008); 4-ом международном форуме MedSoft-2008 (г.Москва, 2008), XI международной конференции «ПРОТЭК'08» (г.Москва, ГОУ ВПО МГТУ «Станкин», 2008); школе-семинаре «Задачи системного анализа, управления и обработки информации» (г.Москва, ГОУ ВПО МГУП, 2008, 2009); всероссийской студенческой научно-технической конференции «Прикладная информатика и математическое моделирование» (г.Москва, ГОУ ВПО МГУП, 2009) и конференции «Инновации в экономике» (г.Москва, ГОУ ВПО МГТУ «Станкин», 2009).

Публикации по теме диссертации. По теме диссертационной работы опубликовано 11 научных работ, в том числе 2 статьи в журналах, входящих в перечень ВАК РФ.

Структура и объем диссертации. Диссертационная работа изложена на

137 страницах машинописного текста и состоит из введения, четырёх глав и заключения.

Основное содержание работы

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

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

Рассматриваются существующие цветовые модели. Отдельно рассмотрено используемое в работе цветовое пространство Luv (L - яркость; и - переход от зелёного к красному; v - переход от синего к жёлтому).

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

Приводится обзор основных методов обработки изображений. Представлены пространственные методы, рассматривающие изображение как совокупность точек в цветовом и координатном пространствах. Также рассмотрены пространственные методы, основанные на гистограммах. Упомянуты частотные методы обработки изображения, основанные на модификации сигнала, формируемого путём применения к изображению двумерного дискретного преобразования Фурье, и методы морфологической обработки изображения, представляющие изображение в виде совокупности объектов, представленных множеством точек.

Осуществляется обзор наиболее популярных методов поиска объектов на изображении, приводятся метод обратной проекции (М. Дж. Свейн, Д. Баллард), нейросетевые методы (Н. Роули) метод П. Виолы и М. Джонса, а также метод Н. Далалы и Б. Триггса. Отдельно исследуется роль сегментации в поиске объектов на изображении. Рассматриваются основные подходы к сегментации изображения. Иерархические методы, к которым относят методы, основанные на последовательном объединении (или разъединении) кластеров по принципу их близости друг к другу (М. Борсотти, Р. Ромен-Рольдан). Представлено решение задачи сегментации при помощи самоорганизующихся карт Кохонена (П. Кампаделли). Рассмотрен подход к сегментации, основанный на выделении контуров из изображения путём вычисления градиента цвета с использованием матриц Собела (Дж. Кенни, Дж. Малик), освещены методы, использующие теорию графов (Юй-Цзинь Чжан, Дж. Малик, Дж. Ши).

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

Во второй главе описывается применение фильтра Собела с целью увеличения скорости и робастности сегментации методом mean-shift за счет использования информации о градиенте изображения. Рассмотрен метод mean-shift в его классическом понимании, предложенном Фукунагой и Хостетлером в 1975 году. Отмечается, что его преимуществом является отсутствие необходимости в изначальных знаниях о количестве кластеров или о каких-либо их признаках. В рамках метода находится значение функции оценки плотности. Единственным параметром алгоритма является размер окна h.

Выделяются недостатки метода mean-shift:

1. Невысокая скорость. Процедура вычисления вектора среднего сдвига требует больших вычислительных ресурсов.

2. Чувствительность к выбросам. В результате сегментации методом mean-shift появляются небольшие области, не несущие информации о семантической структуре изображения, но требующие затрат на обработку при интеллектуальном анализе результатов сегментации.

3. Чувствительность к размерам окна. Единственным параметром кластеризации методом mean-shift является размер окна h и его значение оказывает значительное влияние на результат.

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

Вычисление вектора среднего сдвига происходит для каждой точки независимо и в работе рассматривается методика вычисления, основанная на выполнении процедуры mean-shift параллельно для каждой точки. Это приводит к значительному увеличению скорости процедуры. Проводятся эксперименты, показывающие, что по скорости выполнения процедуры результаты «параллельного mean-shift» сходны с тем, что получаются при вычислении вектора среднего сдвига не для всех точек. Обосновывается нецелесообразность совмещения этих двух методов. Делается вывод, что в случаях, если вычислительная система обладает соответствующими возможностями, имеет смысл применять параллельный сдвиг, в противном случае для повышения быстродействия придётся пожертвовать качеством сегментации и вычислять вектор не для всех точек.

Представлен подход к сегментации изображений с ограничением по градиенту. Этот метод основан на применении процедуры mean-shift с использованием информации о градиенте как ограничивающего фактора при разрастании областей.

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

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

В третьей главе описывается метод сегментации, основанный на совместном использовании метода mean-shift и агломеративной стратегии.

Решаются следующие проблемы метода mean-shift:

1. Необходимость выбирать размер окна h при настройке алгоритма на работу с конкретными данными.

2. Значительное возрастание времени работы при увеличении размера окна h.

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

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

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

Рассмотрены различные варианты алгоритмов и структур данных для хранения точек на каждом этапе сегментации. Основным требованием является обеспечение быстрого выбора всех точек лежащих в окрестности h от точки, для которой осуществляется процедура mean-shift. Рассмотрено традиционное решение данной задачи, которым являются kd-деревья. В общем случае они демонстрируют высокую производительность. Для сокращения времени, затрачиваемого на первом этапе агломеративной сегментации, предложено использовать двумерные массивы. Это возможно, поскольку координаты х, у на первом этапе образуют плотную сетку. Показана эффективность данного метода при небольших (меньше 20 пикселей) размерах окна в пространственной области.

Рассмотрено применение алгоритмов, описанных в главе 2, на первом этапе агломеративной сегментации. Экспериментально подтверждено, что изменение алгоритма на первом этапе в этом случае не оказывает значительного влияния на результат.

Приводятся исследования зависимости времени работы от размера изображения для различных вариаций алгоритмов. Показано, что наилучшую производительность демонстрирует агломеративная сегментация, на первом этапе которой применяется метод mean-shift, специализированный для обработки изображений, совместно с фильтром Собела. Метод сегментации, основанный на параллельном mean-shift, демонстрирует близкие по скорости результаты и может быть использован в тех случаях, когда первый метод не может быть применён, например, по причине того, что он не включает в результирующие сегменты границы этих сегментов. Приведён метод, использующий на первом этапе разрастание регионов, и чистый агломеративный метод, использующий только kd-деревья. Последний демонстрирует невысокую производительность по сравнению с остальными. Для сравнения производительности приведены два популярных метода сегментации: k-means и normalized cuts (N-cuts). Показано, что предложенные в данной работе методы во многом их превосходят.

Проведено сравнение производительности агломеративного метода с методом normalized-cuts и традиционным mean-shift в задачах сегментации гистологических снимков крови и сегментации снимков языка пациента. На основании полученных данных в диссертационной работе делается вывод об эффективности применения разработанного метода для решения этих задач. Кроме этого, разноплановый характер приведённых задач позволяет утверждать, что разработанный метод является универсальным и может быть использован для решения широкого спектра задач, связанных с сегментацией изображений.

В четвёртой главе описывается применение разработанного подхода к сегментации для поиска однородных объектов на растровых полихроматических изображениях.

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

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

Поскольку сегменты характеризуются как цветом, так и формой, сравнение производится и по цвету, и по форме. Далее, по результатам сравнения происходит фильтрация сегментов, в итоге, отбираются сегменты, соответствующие образцу. Для сравнения по цвету используются цветовые гистограммы, а для сравнения по форме используется метод shape contexts (Д. Малик, С. Белонж).

Рассмотрен способ повышения эффективности разработанного алгоритма поиска за счёт использования эвристики, основанной на сопоставлении цвета точки сходимости mean-shift и цветовой гистограммы искомого объекта. Также рассмотрена методика совместного использования метода Виолы-Джонса и предложенного в данной работе метода поиска однородных областей.

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

1. Модуль сегментации изображений, в котором реализованы рассмотренные в работе методы сегментации, включая mean-shift.

2. Модуль mean-shift-кластеризации, реализующий кластеризацию многомерных данных в евклидовом пространстве.

3. Модуль агломеративной сегментации, использующий функциональность первых двух для реализации комплексного метода сегментации изображений. <

4. Модуль поиска объектов на изображении по заданному шаблону.

Разработанные алгоритмы реализованы на платформе Java с использованием языка программирования Scala. Для повышения эффективности процедуры сегментации при использовании параллельных вычислений, применена технология Nvidia CUDA.

Публикации по теме кандидатской диссертации

В изданиях, рекомендованных ВАК Министерства образования и науки РФ: 1. Митропольский, Н. Н. Сегментация и идентификация контуров объектов на цифровых изображениях / Н. Н. Митропольский, Е. Е Ковшов. // Известия высших учебных заведений. Проблемы полиграфии и издательского дела. - 2008. - №5. - С. 19-28.

2. Митропольский, Н. Н. Агломеративная стратегия при сегментации растровых изображений методом среднего сдвига в прикладной компьютерной системе / Н. Н. Митропольский, Е. Е. Ковшов, Н. Н. Хуэ, Н. Ч. Минь // Системы управления и информационные технологии, 2009 -№3-С. 80-83.

В других изданиях:

3. Митропольский, Н. Н. Автоматизация процедуры сегментации цифровых фотографий языка человека в компьютерной диагностической системе / Н. Н. Митропольский // Материалы студенческой научно-практической конференции «Автоматизация и информационные технологии (АИТ-2008)» Первый тур, Сборник тезисов докладов. - М.:МГТУ «Станкин», 2008 - С. 46-48.

4. Митропольский, Н. Н. Сегментация фотографий языка пациента в автоматизированной компьютерной диагностической системе / Н. Н. Митропольский // Материалы студенческой научно-практической конференции «Автоматизация и информационные технологии (АИТ-2008)» Второй тур, Сборник тезисов докладов. - М.:МГТУ «Станкин», 2008-С. 113-119. Г,

5. Митропольский, Н. Н. Задача поиска языка человека на входном изображении в компьютерной диагностической системе / Н. Н. Митропольский // Материалы XI-й научной конференции МГТУ «Станкин» и «Учебно-научного центра математического моделирования МГТУ «Станкин» - ИММ РАН» по математическому моделированию и ионформатике - 2008. - С. 100-102.

6. Митропольский, Н. Н. Автоматизация анализа гистологических изображений при исследовании влияния факторов окружающей среды на здоровье человека / Н. Н. Митропольский., Е. Е. Ковшов // Производство. Технология. Экология. - М.: «Янус-К», 2008 - С. 125-128.

7. Ковшов, Е.Е. Сегментация цифровых изображений языка человека при автоматизированной диагностике / Е. Е. Ковшов, Н. Н. Митропольский //

4й международный форум MedSoft-2008. Медицинские информационные технологии. - М. 2008. - С. 62-64.

8. Митропольский, Н. Н. Автоматизация процедуры сегментации растровых полихроматических изображений на основе алгоритмов Mean-shift и Собела / Н. Н. Митропольский // Задачи системного анализа, управления и обработки информации: Межвузовский сборник научных трудов. -М.:МГУП, 2008. - Вып. 2. - С. 95-102.

9. Митропольский, Н. Н. Повышение эффективности кластеризации данных в Евклидовом пространстве методом среднего сдвига / Н. Н. Митропольский // Материалы студенческой научно-практической конференции «Автоматизация и информационные технологии (АИТ-2009)» Первый тур. Сборник тезисов докладов. — М.:МГТУ «Станкин», 2009-С. 79-83.

10. Митропольский, Н. Н. Применение k-мерных деревьев в системах интеллектуального анализа данных при кластеризации методом среднего сдвига (mean-shift) / Н. Н. Митропольский // Инновации в экономике -2009: материалы научной конференции молодых учёных и студентов. — М: ГОУ ВПО МГТУ «Станкин», 2009 - С. 94-96. •

11. Митропольский, Н. Н. Агломеративная стратегия при кластеризации данных методом среднего сдвига. / Н. Н. Митропольский //Прикладная информатика и математическое моделирование: Межвузовский сборник научных трудов. - М.:МГУП, 2009. - С. 105-110.

Основные выводы и результаты

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

К результатам выполненных исследований в рамках диссертационной работы можно отнести следующее:

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

2. Проведён обзор существующих методов сегментации изображений и поиска объектов на них.

3. Разработан комплексный подход к сегментации изображений, основанный на совместном применении метода mean-shift и фильтра Собела.

4. Разработана методика выбора размеров окна, позволяющая автоматизировать подбор параметров кластеризации данных методом mean-shift.

5. Разработан агломеративный подход на основе метода mean-shift, значительно увеличивающий производительность и расширяющий возможности этого метода.

6. Исследованы различные вариации алгоритмов и структур данных, применяемых в рамках агломеративной mean-shift-сегментации.

7. Разработан программный метод поиска однородных объектов на изображении, основанный на использовании агломеративной meanshift-сегментации.

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

1. Кристофидес Н., Теория графов. Алгоритмический подход/Кристофидес Н. — М.: Мир, 1978 —с. 432.

2. JL Шапиро Докомпьютерное зрение/JI. Шапиро, Дж. Стокман; Пер. с англ — М.: БИНОМ. Лаборатория знаний, 2006 — с. 752.

3. Гонсалес Р. ,Цифровая обработка изображений/Р. Гонсалес, Р. Вудс; пер. с англ. под ред. П. А. Чочиа — М.: Техносфера, 2006 — с. 1072.

4. Zhang, Yu-Jin, Advances in Image and Video Segmentation/ IRM Press — 2006.

5. Castleman K.R., Digital Image Processing/ Englewood Cliffs, New Jersey:

6. Prentice Hall — 1996 — pp. 351.

7. R.O. Duda and P.E. Hart, Pattern Classification and Scene Analysis. IEEE Trans.

8. Signal ProcessingWiley — 1973 — pp. 914.

9. Rosenfeld А., Как A. C, Digital Picture Processing, 2nd edition/ Academic Press,1.c.Orlando, FL, USA — 1982.

10. Scott D.W., Multivariate Density Estimation./ Wiley — 1992.

11. Казанов М.Д., Сегментация изображений страниц цветных печатныхдокументов// Материалы международной конференции студентов и аспирантов по фундаментальным наукам Ломоносов-2004 , 2004.

12. Ковшов Е.Е., Сегментация цифровых изображений языка человека при автоматизированной диагностике./Е.Е. Ковшов, Н.Н. Митропольский // 4й международный форум MedSoft-2008. Медицинские информационные технологии. М. , 2008 — с. 62-64.

13. Митропольский Н.Н., Автоматизация процедуры сегментации цифровых фотографий языка человека в компьютерной диагностической системе//

14. Материалы студенческой научно-практической конференции «Автоматизация и информационные технологии(АИТ-2008)» Первый тур, Сборник тезисов докладов. М.:МГТУ «Станкин» , 2008 — с. 46-48

15. Митропольский Н.Н., Агломеративная стратегия при кластеризации данных методом среднего сдвига// Прикладная информатика и математическое моделирование: Межвузовский сборник научных трудов. М.:МГУП , 2009 — с. 105-110.

16. Митропольский Н.Н., Автоматизация анализа гистологических изображений при исследовании влияния факторов окружающей среды наздоровье человека./Митропольский Н.Н., Ковшов Е.Е. // Производство. Технология. Экология. М.: «Янус-К» , 2008 — с. 125-128.

17. Митропольский Н.Н., Сегментация и идентификация контуров объектов на цифровых изображениях/Н.Н. Митропольский ,Е.Е. Ковшов // Известия высших учебных заведений. Проблемы полиграфии и издательского дела. -М.: МГУП , 2008 — с. 19-28.

18. D. Comanicu, P. Meer, Mean shift: A robust approach toward feature space analysis.// IEEE Trans. Pattern Anal. Machine Intell., 2002 — c. 603-619

19. QCAV. 1999. Quality control by artificial vision. Proc. 5th Int. Conf. QualityControl by Artificial Vision (18-21 May 1999), Trois-Rivieres, Canada.

20. Behiels, G., Maes, F., Vandermeulen, D., et al., Evaluation of image features and search strategies for segmentation of bone structures in radiographs using active shape models. // Medical Image Analysis — 2002 — vol. 6(1).

21. Borsotti, M., Campadelli, P., Schettini, R., Quantitative evaluation of color image segmentation results. Pattern Recognition Letters, — 1998.

22. Brunner D., Soille P., Iterative area filtering of multichannel images // Image and Vision Computing — 2007— vol.28 — pp. 1352-1364.

23. Bryant, D., Bouldin, D., Evaluation of edge operators using relative and absolute grading. // In Proceedings of the IEEE Conference on Pattern Recognition Image Processing — 1979.

24. Buf, J. M. H., Campbell, T. G., A quantitative comparison of edge-preserving smoothing techniques. // Signal Processing — 1990 — vol. 21 — pp. 289-301.

25. Campadelli P., Medici D. Schettini R., Color image segmentation using Hopfield networks//Image and Vision Computing— 1997— vol.15— pp. 161-166.

26. Canny, J., A Computational Approach To Edge Detection, // IEEE Trans. Pattern Analysis and Machine Intelligence — 1982 — vol. 8 — pp. 679-714.

27. Chabrier, S., Rosenberger, C., Laurent, H., Emile, В., March'e, P., Evaluating the segmentation result of a gray-level image. // In Proceedings of the International Conference European Signal Processing Conference .

28. Cheng Y., Mean Shift, Mode Seeking, and Clustering, // IEEE Trans. Pattern Analysis and Machine Intelligence — 1995 — vol. 17 — pp. 790-799.

29. Choi E. Hall P., Data Sharpening as a Prelude to Density Estimation, // Biometrika— 1999— vol.86 — pp. 941-947.

30. Chu C.K., Glad I.K., Godtliebsen F., Maron J.S., Edge-Preserving Smoothers for Image Processing, // J. Am. Statistical Assoc. — 1998 — vol. 93 — pp. 526541.

31. Comaniciu D., Meer P., Distribution Free Decomposition of Multivariate Data, // Pattern Analysis and Applications— 1999— vol.2— pp. 22-30.

32. Comaniciu, D., An Algorithm for Data-Driven Bandwidth Selection // IEEE Trans. Pattern Analysis Machine Intell. — 2003 — vol. 25 — pp. 281-288.

33. Comaniciu, D. Meer, P., Mean Shift Analysis and Applications // IEEE Int. Conf. Computer Vision (ICCV'99), Kerkyra, Greece.

34. Correia, P., Pereira, F., Classification of video segmentation application scenarios. // IEEE Transactions on Circuits and Systems for Video Technology — 2004 — vol. 14(5)— pp. 735-741.

35. D. Blei, A. Ng, and M. Jordan, Latent dirichlet allocation // Journal of Machine Learning Research — 2003 — vol. 3 — pp. 993-1022.

36. Demigny, D., Kaml'e, T. A discrete expression of Canny's criteria for step edge detector performances evaluation. // IEEE Transactions on Pattern Analysis and Machine Intelligence — vol. 19(11)— pp. 1199-1211.

37. Fleck, M., D. Forsyth, and C. Pregler., Finding naked people in images. // Proc. European Conf. Comput. Vision. Springer-Verlag, New York, — 1996.

38. Foley, James D. et al, Computer Graphics Principles and Practice, 2nd edition //1. Addison-Wesley — 1990.

39. Freund Y, Robert E. S., A decision-theoretic generalization of on-line learning and an application to boosting // — August 1997 — vol. 55(1) — pp. 119-139.

40. Fukunaga K., Hostetler L.D., The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition, // IEEE Trans. Information Theory — 1975 — vol. 21 — pp. 32-40.

41. Fukunaga K., Introduction to Statistical Pattern Recognition, second ed // Academic Press — 1990 .

42. Gibson, J.J., The Perception of the Visual World. Boston: Houghton Mifflin. — 1950.

43. Glasby, C. A., and G. W. Horgan., Image Analysis for the BiologicalSciences. John Wiley & Sons, Chichester, England.

44. H. Rowley, S. Baluja, and T. Kanade., Neural network-based face detection // In IEEE Patt. Anal. Mach. Intell. — 1998.

45. Hwang J.N. Lay S.R., Lippman A., Nonparametric Multivariate Density Estimation: A Comparative Study, // IEEE Trans. Signal Processing — 1994 — vol.42 — pp. 2795-2810.

46. J Sivic, В Russell, AA Efros, A Zisserman, WT Freeman, Discovering objects and their location in images // In IEEE international conference on computer vision. — 2005 — pp. 8.

47. Kirbas, C., Quek, F. К. H., Vessel extraction techniques and algorithms: A survey. // In Proceedings of the 3rd Bioinformatics and Bioengineering Symposium — 2003 .

48. Kitchen, L., Rosenfeld, A., Scene analysis using region-based constraint filtering //Pattern recognition.— 1984.

49. Kopydlowski, D. , 100% inspection of crossbars using machine vision.Publication MS83-210, Society of Manufacturing Engineers, Dearborn, MI. 1983.

50. Levkowitz, Haim, Color Theory and Modeling for Computer Graphics, Visualization,and Multimedia Applications, // Kluwer Academic — 1997.

51. Liu L. Sclaroff S., Deformable Shape Detection and Description via Model-Based Region Grouping, // Proc. 1999 IEEE Conf. Computer Vision and Pattern Recognition, — 1999.

52. Luo, Y., Zhang, Y. J., Gao, Y. Y., et al., Extracting meaningful region for content-based retrieval of image and video. // SPIE, — 2001.

53. M. Andreetto, L. Zelnik-Manor and P. Perona, Unsupervised Learning of Categorical Segments in Image Collections // Computer Vision and Pattern Recognition Workshops, 2008. CVPRW '08. IEEE Computer Society Conference — 2008 — pp. 1-8.

54. Ma W.Y. Manjunath B.S., Edge flow: A Framework of Boundary Detection and Image Segmentation, // IEEE Trans. Image Processing — 2000 — vol. 9 — pp. 1375-1388.

55. McCane, В., On the evaluation of image segmentation algorithms. // In Proceedings of Digital Image Computing: Techniques and Applications, Massey University, Albany Campus, Auckland, New Zealand — 1997.

56. Munoz, X., Freixenet, J., Cufi, X., et al., Strategies for image segmentation combining region and boundary information. // Pattern Recognition Letters — 2002 — vol. 23 — pp. 375-392.

57. N. Dalai, B. Triggs, Histograms of Oriented Gradients for Human Detection // Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition — 2005 — pp. 886 — 893.

58. Ohta Y., Kanade Т., Sakai Т., Color Information for Region Segmentation, // Computer Graphics and Image Processing — 1980 — vol. 13 — pp. 222-241

59. Olabarriaga, S. D., Smeulders, A.W. M., Interaction in the segmentation of medical images: A survey. // Medical Image Analysis — 2001 — vol. 5(2) — pp. 127-142.

60. P. Viola, M. Jones, Rapid Object Detection using a Boosted Cascade of Simple Features .

61. Park, Marron J., Comparison of Data-Driven Bandwidth Selectors, // J. Am.

62. Statistical Assoc.— 1990— vol.85— pp. 66-72.

63. Peli, Т., Malah, D., A study of edge detection algorithms. // Computer Graphics and Image Processing— 1982— vol.20— pp. 1-21.

64. Perona P.,Malik J., Scale-Space and Edge Detection Using Anisotropic Diffusion, // IEEE Trans. Pattern Analysis and Machine Intelligence — 1990 — vol. 12 — pp. 629-639.

65. Pham, D., Xu, C., Prince, J., Current methods in medical image segmentation. // Annual Review of Biomedical Engineering— 2000— vol.2— pp. 315-337.

66. Prati, A., Mikic, I., Trivedi, M. M., et al., Detecting moving shadows: Algorithms and evaluation. // IEEE PAMI — 2003 — vol. 25(7) — pp. 918-923.

67. Ridder D., Kittler J., Lemmers O., Duin R., The Adaptive Subspace Map for Texture Segmentation,. // Proc. 2000 Int'lel Conf. Pattern Recognition — Sept. 2000 — vol. — pp. 216-220.

68. Riseman, E. M., Arbib, M. A., Computational techniques in the visual segmentation of static scenes. // CGIP — 1977 — vol. 6 — pp. 221-276.

69. Roberts, S.J., Parametric and Non-Parametric Unsupervised Cluster Analysis, // Pattern Recognition — 1997 — vol. 30 — pp. 261-272.

70. Roman-Roldan, R., Gomez-Lopera, J.F., Atae-allah, C., Martinez-Aroza, J., \& Luque Escamilla, P.L., A measure of quality for evaluating methods of segmentation and edge detection. // Pattern Recognition, — 2001.

71. Roman-Roldan, R., Gomez-Lopera, J.F., Atae-allah, C., Martinez-Aroza, J., Luque-Escamilla, P.L., A measure of quality for evaluating methods of segmentation and edge detection // Pattern Recognition — 2001 — vol. 34 — pp. 969-980.

72. Russell, B.C. Freeman, W.T. Efros,A.A. Sivic, J. Zisserman, A., Using

73. Multiple Segmentations to Discover Objects and their Extent in Image Collections // Computer Vision and Pattern Recognition, 2006 IEEE Computer Society Conference on — 2006— pp. 1605- 1614.

74. S. Belongie, J. Malik, J. Puzicha, Shape matching and object recognition using shape contexts // Technical Report UCB//CSD-00-1128 UC Berkeley, — 2002 — pp. 509-521.

75. S. Belongie, J. Malik, J. Puzicha,, Shape Context: A New Descriptor for Shape Matching and Object Recognition // Advances in Neural Information Processing Systems 13: Proc. 2000 Conf — 2001 — pp. 831-837.

76. Sahoo, P.K., Soltani, S., Wong, A.K.C., Chen, Y.C., A survey of thresholding techniques. // Graphical Model and Image Processing (CVGIP) — 1988 — vol. 41 — pp. 233-260.

77. Sheather S., Jones M., A Reliable Data-Based BandwidthSelection Method for Kernel Density Estimation, // J. Royal StatisticsSoc. В — 1991 — vol. 53 — pp. 683-690.

78. Shi, J., Malik, J., Normalized cuts and image segmentation. // IEEE Trans. Pattern Analysis and Machine Intelligence — 2000 — vol. 22(8) — pp. 888-905

79. Silverman B. W., Density Estimation for Statistics and Data Analysis // Chapman and Hall— 1986.

80. Swain, M.J. Ballard, D.H., Indexing via color histograms // Computer Vision, 1990. Proceedings — Dec 1990 — pp. 390-393.

81. T. Cour, F. Benezit, J. Shi, Spectral Segmentation with Multiscale Graph Decomposition // Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) — 2005 — vol. 2 — pp. 1124-1131.

82. T. Hofmann, Probabilistic latent semantic indexing // In SIGIR — 1999.

83. T. Hofmann, Unsupervised learning by probabilistic latent semantic analysis // Machine Learning — 2001 — vol. 43 — pp. 177-196.

84. Tabb M. Ahuja N., Multiscale Image Segmentation by Integrated Edge and

85. Region Detection, // ШЕЕ Trans. Image Processing — 1997 — vol. 6 — pp. 642-655.

86. Touzani A. Postaire J.G., Clustering by Mode Boundary Detection, // Pattern Recognition Letters— 1989— vol.9— pp. 1-12.

87. Tremeau A., Borel N., A region growing and merging algorithm to color segmentation//Pattern recognition. — 1997.

88. Wand M.P. Jones M., Kernel Smoothing. // Chapman and Hall — 1995.

89. Wilson, D.L., Baddeley, A.J., Owens, R.A., A new metric for gray-scale image comparison. // International Journal Computer Vision — 1997 — vol. 24 — pp. 5-17.

90. Zamperoni, P., Starovoitov, V., On measures of dissimilarity between arbitrary gray-scale images. // International Journal of Shape Modeling. — 1996 .

91. Zhang, Y.J. A, survey on evaluation methods for image segmentation. // International Conference Computer Vision and Pattern Recognition (CVPR). — 1996.