Содержание к диссертации
Введение
Глава 1. Обзор задач и методов цифровой обработки изображений 17
1.1. Компьютерное зрение и прикладные задачи 17
1.2. Основные методы обработки изображений 21
1.3. Поиск и распознавание объектов на растровых изображениях 33
1.4. Сегментация изображений 40
1.5. Постановка задачи исследовательской работы 47
Глава 2. Комплексное применение метода mean-shift и фильтра Собела 49
2.1. Метод mean-shift 49
2.2. Построение карты градиента на основе фильтра Собела 63
2.3. Сегментация изображений с ограничением по градиенту 65
2.4. Сегментация изображений с применением алгоритма разрастания регионов «по пути наименьшего сопротивления» 70
2.5. Вычислительный эксперимент и интерпретация результатов 72
2.6. Оценка вычислительной сложности разработанных алгоритмов сегментации 79
2.7. Выводы по главе 2 83
Глава 3. Агломеративная сегментация методом mean-shift 84
3.1. Общие принципы агломеративной стратегии 84
3.2. Автоматический выбор размера окна. Вес точки 85
3.3. Вариации структур данных и алгоритмов на различных этапах агломеративной сегментации 90
3.4. Выводы по главе 3 103
Глава 4. Поиск однородных объектов 104
4.1. Многоуровневое выделение сегментов 104
4.2. Сопоставление с образцом 107
4.3. Вычислительный эксперимент и сочетание с другими алгоритмами 112
4.4. Программная реализация 116
4.5. Выводы по главе 4 118
Основные выводы и результаты 119
Литература 121
Приложение
- Поиск и распознавание объектов на растровых изображениях
- Сегментация изображений с ограничением по градиенту
- Вариации структур данных и алгоритмов на различных этапах агломеративной сегментации
- Вычислительный эксперимент и сочетание с другими алгоритмами
Введение к работе
Актуальность работы. В настоящее время развитие вычислительной техники и средств интеллектуальной обработки данных позволяет автоматизировать многие сферы человеческой деятельности, тем самым увеличить производительность труда, уменьшить количество ошибок, освободить людей от однообразной работы. В последние десятилетия компьютеры начали оказывать существенную помощь и в задачах, связанных с распознаванием образов, интеллектуальным анализом данных и, в частности, обработкой изображений. Анализ изображений является актуальным для таких областей как сжатие данных, распознавание документов, создание баз данных изображений, контроль качества, медицинская диагностика и многих других.
Большинство изображений, получаемых с фотоаппаратуры и сканеров, являются растровыми изображениями, то есть представляют собой прямоугольную сетку из цветных точек. Человеческий мозг, анализируя получаемые глазом изображения, не представляет его в виде матрицы из точек, вместо этого он объединяет эти точки в однородные области и в дальнейшем оперирует полученными объектами. Этот процесс называется сегментацией и у человека происходит на подсознательном уровне. При решении задачи компьютерного анализа изображения и распознавания образов он должен быть реализован программно. Сегментация выполняется на первых этапах анализа изображения, и качество её выполнения оказывает ключевое влияние на скорость, точность, а иногда и возможность дальнейшего анализа.
Работы в области обработки, сегментации и поиска объектов на изображениях велись и ведутся весьма интенсивно как отечественными (Андреев Ю.С., Баяковский Ю.М., Богуславский А.А., Вежневец В.П., Казанов М.Д., Сергеев В.В.), так и зарубежными (Б. Рассел, Дж. Малик, М. Андретто, Юй-Ли, Юй-Цзинь Чжан, Дж. Ши, П. Виола, М. Джонс) учёными. К настоящему времени выработано множество подходов к сегментации изображения, но ни один из них не стал универсальным. В зависимости от происхождения, текстуры, качества, размера, предмета исследований и множества других параметров имеет смысл применять различные способы сегментации. Причём применимость конкретного способа для изображений определённого типа исследуется, в основном, экспериментально, и, как правило, выбранный способ сегментации обладает довольно узкой специализацией и может быть непригодным для изображений, отклоняющихся от «типичных случаев». Исходя из изложенного, актуальной задачей является разработка эффективных методов сегментации, сочетающих преимущества различных подходов и увеличивающих тем самым точность, скорость и робастность процесса сегментации.
Объект исследования. Объектом исследования диссертационной работы являются растровые полихроматические изображения (далее изображения) как визуальные представления совокупности объектов реального мира.
Предмет исследования. Предметом исследования диссертационной работы являются методы сегментации изображений и поиска объектов на них.
Целью работы является разработка комбинированного метода сегментации и применение его для поиска однородных объектов на изображениях. Базой для этого метода был выбран хорошо зарекомендовавший себя на практике метод mean-shift.
В процессе работы решались следующие научные задачи:
-
Выявление методов и исследование подходов к сегментации и поиска объектов на цветных изображениях.
-
Разработка метода, позволяющего учитывать информацию о градиенте изображения при сегментации методом mean-shift.
-
Разработка эффективного алгоритма сегментации на базе метода mean-shift и агломеративной стратегии.
-
Разработка методики, позволяющей автоматически подбирать параметры метода mean-shift для каждого этапа агломеративной сегментации.
-
Применение разработанного метода в среде прикладной информационной системы для поиска однородных объектов на изображении.
-
Проведение вычислительного эксперимента с полученными в работе алгоритмами и их вариациями.
Методы исследований. При решении задач, поставленных в работе, были использованы методы системного анализа, статистической обработки данных, дискретной математики, кластерного анализа.
Научная новизна. Научная новизна диссертационной работы заключается в следующих положениях:
-
Разработан комплексный метод сегментации изображений на основе применения агломеративной стратегии и метода mean-shift.
-
Исследованы различные алгоритмы и структуры данных в рамках разработанного метода агломеративной сегментации.
-
Разработан алгоритм поиска однородных объектов на изображениях при помощи агломеративной сегментации.
Практическая ценность диссертационной работы заключается в эффективном применении созданного метода для сегментации изображений, поиска однородных объектов, а также индексации содержимого изображений и извлечении знаний из изображений. Кроме того, программная реализация описываемых в работе алгоритмов является законченным продуктом и готова к использованию в различных системах интеллектуального анализа данных и системах компьютерного зрения.
Реализация результатов работы. Практические результаты диссертационной работы нашли своё применение в информационных системах клинико-диагностических и лабораторных отделений медицинского консультативного центра (г. Москва). Помимо этого, определена целесообразность использования предложенных методик при создании прикладного программного обеспечения информационных систем в научно-практических разработках малого предприятия ООО «Компьютерные системы и технологии» (г. Москва).
Упомянутые выше методики внедрены в учебный процесс ГОУ ВПО МГТУ «Станкин», используются при подготовке бакалавров по направлению 220200.62 «Автоматизация и управление» и магистрантов по магистерской программе 220200.68-20 «Человеко-машинные системы управления». Материалы диссертационной работы использованы в качестве методологической основы при разработке курса лекций и практических занятий по дисциплинам «Информатика», «Программирование и основы алгоритмизации» и специальной дисциплине «Интеллектуальные системы обработки информации».
Апробация работы. Результаты работы докладывались на научно-практической конференции «Автоматизация и информационные технологии (АИТ)» (г. Москва, ГОУ ВПО МГТУ «Станкин», 2008, 2009); XI-й научной конференции МГТУ «Станкин» и «Учебно-научного центра математического моделирования МГТУ «Станкин» - ИММ РАН» по математическому моделированию и информатике (г. Москва, ГОУ ВПО МГТУ «Станкин», 2008); 4-ом международном форуме MedSoft-2008 (г. Москва, 2008), XI международной конференции «ПРОТЭК'08» (г. Москва, ГОУ ВПО МГТУ «Станкин», 2008); школе-семинаре «Задачи системного анализа, управления и обработки информации» (г. Москва, ГОУ ВПО МГУП, 2008, 2009); всероссийской студенческой научно-технической конференции «Прикладная информатика и математическое моделирование» (г. Москва, ГОУ ВПО МГУП, 2009) и конференции «Инновации в экономике» (г. Москва, ГОУ ВПО МГТУ «Станкин», 2009).
Публикации по теме диссертации. По теме диссертационной работы опубликовано 11 научных работ, из них 7 основных, в том числе 2 статьи в журналах, входящих в перечень ВАК РФ.
Структура и объем диссертации. Диссертационная работа изложена на 137 страницах машинописного текста и состоит из введения, четырёх глав и заключения.
Поиск и распознавание объектов на растровых изображениях
Одной из важнейших задач интеллектуальной обработки изображений является поиск объектов на них. При этом целью может являться поиск лиц на фотографии, например для подсчёта количества человек или устранения дефектов; или поиск людей в видеопотоке, получаемого с системы слежения. Также эта задача актуальна при поиске изображений в базе данных и во многих других областях. В этом разделе представлены некоторые способы решения этой задачи.
Одним из самых простых способов поиска объектов на изображении является метод, основанный на сопоставлении гистограмм и называемый методом обратной проекции. Для искомого объекта строится цветовая гистограмма М и для исходного изображения строится цветовая гистограмма / и метод пытается дать ответ на вопрос: «где на исходном изображении расположены цвета, соответствующие искомому объекту?». Для этого строится дополнительная гистограмма R, у-й элемент которой вычисляется по формуле: Затем гистограмма R проецируется обратно на исходное изображение. После этого вычисляется свёртка по маске, которая, например, в случае, когда ориентация объекта не известна, может быть кругом. Точка с максимальным значением на результирующем изображении будет являться положением искомого объекта [82].
Данный метод имеет достаточно низкую вычислительную сложность и используется в системах реального времени, тем не менее, он обладает невысокой точностью и часто находит искомый объект там, где его нет.
Одним из распространённых подходов к поиску объектов на изображении является подход, основанный на использовании нейронных сетей и изложенный в [47], в частности, применяемый для поиска лиц на изображении.
Предложенный метод состоит из двух этапов: на первом этапе к изображению применяется нейросетевой фильтр, на втором этапе на основе результатов первого устанавливается положение искомого объекта и разрешаются перекрывающиеся области.
Нейросетевой фильтр (рис. 5) получает на вход блок пикселей размером 20x20 и выдаёт значение от 1 до -1, оценивая присутствие или отсутствие в данном блоке лица (искомого объекта). Для поиска объектов на всем изображении фильтр применяется ко всем областям данного изображения. Для поиска объектов в любом масштабе происходит уменьшение размера исходного изображения и для каждого уменьшенного изображения фильтр применяется заново.
Для обучения фильтра требуется большая обучающая выборка, состоящая как из изображений лиц, так и из изображений не-лиц. При этом используются изображения разного размера, ориентации, положения и интенсивности. Поскольку множество не-лиц является очень разнообразным, невозможно создать полноценную выборку этого множества. Для решения этой проблемы используется приём, заключающийся в подаче на вход уже обученной нейронной сети изображения, на котором нет лиц, с последующим включением всех найденных на данном изображении псевдо-лиц в обучающую выборку как пример не-лиц.
Описанный нейросетевой метод показывает довольно неплохие результаты при наличии большой обучающий выборки. Тем не менее, поиск объектов занимает довольно продолжительное время. Кроме этого, результирующая область представляет собой квадрат или другую фигуру заранее заданной формы, что не всегда удобно.
Наиболее популярным методом поиска объектов на изображении в настоящее время является метод, предложенный Полом Виолой и Майклом Джонсом в их статье «Rapid Object Detection using a Boosted Cascade of Simple Features» [63] в 2002-м году. Метод позволяет искать по определённым признакам заданную область на изображении. Метод позволяет искать разного рода объекты, но в основном используется для поиска человеческих лиц.
Метод использует так называемые Хааровские признаки. Пример данных признаков изображен на рис. 6, в данном случае используются прямоугольные признаки и представлены они вписанными в прямоугольник области поиска. Сумма точек, лежащих внутри белых прямоугольников вычитается из суммы, лежащих внутри серых прямоугольников. В зависимости от количества составляющих прямоугольников можно выделить двудольные (А,В), трёхдольные (С) и четырёхдольные прямоугольные признаки (D). Если взять базовое окно детектора размером 24x24, то из него извлекается свыше 180 тысяч признаков, что является избыточным. Кроме того, прямое вычисление всех признаков является довольно ресурсоёмкой задачей.
Сегментация изображений с ограничением по градиенту
Многие проблемы сегментации методом mean-shift можно решить при помощи использования информации, полученной из градиентного рельефа. В простейшем случае можно расформировывать области, границы которых не подкреплены градиентом [14]. Иными словами, на основе результатов, полученных фильтром Собела, происходит фильтрация контуров, полученных mean-shift-сегментатором: Для каждого контура осуществляется последовательный обход всех точек. Для каждой из этих точек по карте градиентов выбирается соответствующее значение градиента, и, если это значение превосходит некий заранее установленный порог level, то счётчик «подтверждённых» пикселей увеличивается на единицу. Затем высчитывается отношение количества этих точек к количеству точек во всем контуре и, если это отношение превышает заданное (threshold), то контур считается прошедшим фильтрацию, а если не превышает, то не прошедшим и исключается из рассмотрения.
Общая схема работы такого подхода представлена на рис. 30. Таким способом можно уменьшить число рассматриваемых контуров и облегчить работу классифицирующего устройства.
Хотя подобный подход и устраняет «лишние» контуры и в целом увеличивает точность сегментации за счёт использования дополнительной информации, он обладает рядом недостатков. Во-первых, нет никакой гарантии, что не будет отброшен контур или часть контура области интереса, так как в некоторых случаях даже ярко выраженные объекты не имеют достаточного подтверждения своих границ градиентом; и, во-вторых, данный метод крайне чувствителен к ошибкам сегментации, когда область интереса разбивается на несколько сегментов: вероятность того, что границы подобных сегментов будут успешно «подтверждены», весьма невысока, а значит, высоки шансы отбросить и всю область.
Эта проблема может быть решена путём использования модуля градиента, как ограничивающего фактора при разрастании регионов. В этом случае при разрастании регионов условием включения точки в область является не только схожесть цветов, но и также отсутствие высокого значения градиента в этой точке; какая либо фильтрация контуров отсутствует. На рис. 32 представлен результат применения такого алгоритма к изображению на рис. 31. Из представленных рисунков видно, что небольшие области в точках, характеризующихся большими значениями модуля градиента, практически отсутствуют. Кроме этого можно заметить, что некоторые границы на рис. 32 выделены менее жирно, чем другие. Это связано с особенностью выделения границ. Принцип выделения границ сегментов на представленных рисунках заключается в окрашивании белым цветом пикселей, которые имеют «соседей» не из своей области, это приводит к тому, что границы в большинстве случаев дублируются. Тем не менее, на рис. 32 это наблюдается не всегда - некоторые границы кажутся выделенными слабее, это объясняется тем, что некоторые точки не были включены ни в одну область, так как значение градиента в них превышало установленный порог. То есть использование описанного подхода приводит к тому, что сегментация становится «неполной» - не каждый пиксель отнесён к какой-либо области. Тривиальное решение о выделении данных пикселей в новые области по координатному принципу не решает проблему, так как данные области не обладают семантической однородностью и не могут рассматриваться как полноценные области при дальнейшем анализе. Впрочем, во многих случаях «неполная» сегментация изображения является вполне приемлемой.
Вариации структур данных и алгоритмов на различных этапах агломеративной сегментации
При практической реализации процедуры mean-shift актуальным является вопрос выбора структуры данных для хранения точек на каждом этапе кластеризации. Основным требованием является обеспечение быстрого выбора всех точек, лежащих в окрестности h от точки, для которой осуществляется процедура mean-shift. Время выполнения данной операции оказывает ключевое влияние на продолжительность процедуры mean-shift, а значит, и на общее время работы предлагаемого алгоритма. Традиционным решением данной задачи являются kd-деревья, и в общем случае подобные структуры данных демонстрируют высокую производительность [16] и именно они выбраны в качестве основного решения при реализации описываемого подхода.
На рис. 54 представлена гистограмма времени затрачиваемого на каждом этапе агломеративной сегментации. Из гистограммы чётко видно, что время, затрачиваемое на первом этапе, значительно превышает время, затрачиваемое на всех остальных (даже вместе взятых). Этот факт объясняется тем, что на первом этапе количество обрабатываемых точек крайне велико. Как известно, время работы метода mean-shift зависит от размера окна h, мы можем уменьшить значение этого окна с помощью введения особого значения поправочного коэффициента к. На рис. 55 представлена гистограмма для случая, если взять на первом этапе коэффициент :=0.2 при остальных значениях 0,5 и более. Как можно заметить из графика время, затрачиваемое на первом этапе, значительно уменьшилось, но при этом возросло время работы второго этапа (фактически, можно считать, что основная часть нагрузки была переведена на него). Но поскольку общее количество точек на втором этапе значительно меньше количества точек на первом, суммарное время работы алгоритма уменьшается (для данного примера суммарное время уменьшилось вдвое).
Можно пойти дальше и отказаться от данного ad-hoc метода и изменять коэффициент к линейно, что позволит распределить вычислительную нагрузку между этапами более равномерно. На рис. 56 представлена гистограмма времени выполнения этапов для случая, когда нагрузка распределяется равномерно. При этом можно добиться ещё более значительного уменьшения общего времени работы.
Но более значительный эффект даёт использование структуры хранения точек, основанной на двумерных массивах, возможное ввиду того, что координаты х, у на первом этапе образуют плотную сетку. Становится возможным поиск точек по пространственной области за единичное время, но поиск в цветовой области требует перебора, то есть времени линейно зависящего от площади окна в пространственной области. Несмотря на это, при небольших значениях окна в пространственной области, как показали эксперименты, данный метод весьма эффективен. На рис. 57 представлена гистограмма для этого случая: заметно уменьшение времени, затрачиваемого на первом этапе по сравнению с рис. 56.
На рис. 58 представлена зависимость суммарного времени работы алгоритма от размера изображения для случая, когда на первом этапе используется kd-дерево, и для случая, когда используется двумерный массив. Из графиков видно, что использование массивов увеличивает скорость работы алгоритма.
Иначе говоря, можно отметить, что на первом этапе мы выполняем сегментацию изображений со всей соответствующей спецификой, а остальные этапы — кластеризация данных в многомерном евклидовом пространстве.
Это означает, что на первом этапе мы также можем использовать алгоритмы, описанные в главе 2.
На рис. 59 представлена гистограмма длительности каждого этапа при использовании вариации mean-shift, специализированной для изображений. Как можно заметить время работы первого этапа снова значительно превышает время работы остальных этапов, но общее время значительно сокращено (в частности, в данном примере время сегментации сокращено с 2 минут до 6 секунд). Ещё лучших результатов можно достичь, используя параллельный mean-shift (рис. 60).
Причиной роста производительности является то, что удаётся относительно дёшево (с точки зрения вычислительной сложности) получить небольшое количество кластеров на первом этапе. На рис. 61 представлены графики, показывающие выходное количество кластеров, получаемое на каждом этапе агломеративной сегментации, при использовании только kd-деревьев и при использовании параллельного mean-shift, специализированного для изображений, на первом этапе. Графики наглядно демонстрируют, насколько меньше кластеров получается на первом этапе в случае использования специализированного метода. На последующих этапах количество кластеров выравнивается, что позволяет сделать вывод, что изменение алгоритма на первом этапе не оказывает значительного влияния на результат.
Вычислительный эксперимент и сочетание с другими алгоритмами
В итоге, к достоинствам циклического метода можно отнести высокую скорость, интуитивно понятный результат, так как порядок следования точек сохраняется, и простоту программной реализации. К недостаткам можно отнести необходимость упорядочивать точки и трудности при работе с внутренними областями. Тем не менее, циклический метод на основе контекстов форм выбран как основной способ сопоставления форм в разрабатываемой системе поиска объектов на изображении.
Примером практического применения может служить поиск шлемовидных эритроцитов при гистологическом исследовании крови. При помощи поиска однородных объектов можно посчитать их количество относительно количества эритроцитов правильной формы (Рис. 74).
На рис. 75 представлена экспериментально полученная зависимость времени, затрачиваемого на поиск объекта на изображении описываемым в данной главе методом, от размера изображения. Также на графике представлено время, затрачиваемое на сегментацию без поиска. Из данного графика видно, что в среднем время поиска составляет около 40% от времени сегментации. Это время можно уменьшить, если использовать эвристический метод, основанный на обратных проекциях. Как известно ( 1.3.1. ), метод обратных проекций позволяет по заданной гистограмме исходного объекта получить вероятность принадлежности каждой точки изображения исходному объекту. Таким образом, можно проводить сравнение только тех областей, полученных в результате сегментации, вероятность принадлежности которых искомому объекту выше определённого порога. Нахождение общей вероятности представляет собой вычислительно сложную задачу, так как время вычисления линейно зависит от размера области, а требуется эвристика, вычисление которой не потребует увеличения времени работы всего алгоритма. Более простой подход заключается в использовании точки сходимости процедуры mean-shift, которая является «характерной» точкой для всего сегмента. Зная значение цвета данной точки, по цветовой гистограмме исходного объекта можно получить значение, характеризующее вероятность того, что данный сегмент принадлежит этому объекту, и не рассматривать сегменты, для которых это значение ниже определённого порога. Возможность совершить ошибку второго рода есть в случае, когда данный сегмент не велик и значительно отличается по цвету от остальных. Но так как предполагается, что искомый объект имеет однородный цвет, то данный случай не рассматривается. В других случаях, если данный сегмент является частью искомого объекта, но по тем или иным причинам был отброшен данной эвристикой, то в ходе агломеративной сегментации он будет включён в более крупный сегмент, для которого цвет точки сходимости будет ближе к цвету искомого объекта.
На рис. 76 изображён график зависимости времени поиска от размера изображения в сравнении со временем сегментации, при использовании описанной выше эвристики. В данном случае время поиска составляет около 10% от времени сегментации.
Несмотря на то, что разработанный метод поиска однородных объектов в определённом смысле противопоставляется методам, основанным на использовании скользящего окна (Виола-Джонс, Далала-Триггс), они могут работать совместно: например, метод Виолы-Джонса, может использоваться для локализации лица человека на изображении, а описанный в данной работе метод поиска обеспечить нахождение языка на нем (рис 77). То есть на первом этапе обученный каскад осуществляет поиск лица, что занимает относительное небольшое время, затем в найденной прямоугольной области производится сегментация, в процессе которой отбирается сегмент, соответствующий языку. Агломеративная сегментация является самой вычислительно сложной операцией, поэтому уменьшение размера сегментируемого изображения приводит к значительному уменьшению общего времени поиска, кроме того, так как отбрасываются области, в которых искомый объект заведомо не может находиться, удаётся избежать большого количества ошибок первого рода (например, пальцы могут быть ошибочно приняты за язык). Численные результаты обработки изображения, представленного на рис 77 приведены в таблице 2.
Разумеется, использование подобной методики рационально только в том случае, если искомый объект не занимает значительную область на изображении, а также имеется готовый каскад для метода Виолы-Джонса или возможность его обучить.
Разработанные алгоритмы реализованы на платформе Java с использованием языка программирования Scala и представляют собой прикладную информационной систему, архитектура которой представлена на рис. 78. Разработанная система включает в себя четыре основных модуля: 1. Модуль сегментации изображений, в котором реализованы рассмотренные в работе методы сегментации, включая mean-shift. 2. Модуль mean-shift-кластеризации, реализующий кластеризацию многомерных данных в евклидовом пространстве. 3. Модуль агломеративной сегментации, использующий функциональность первых двух для реализации комплексного метода сегментации изображений. 4. Модуль поиска объектов на изображении по заданному шаблону.
