IMAGE SEGMENTATION USING CLUSTERIZATION

Full Text

Введение В настоящее время большое внимание уделяется внедрению информационных технологий во все отрасли деятельности современного человека. Помимо ставших привычными баз данных, позволяющих хранить и обрабатывать большие потоки информации различных типов, на многих предприятиях внедряются системы телевизионной регистрации движущихся объектов. Они достаточно эффективно позволяют отслеживать наличие людей в кадре, автомобилей, деталей на конвейере и другие. Такие системы позволяют осуществлять мониторинг охраняемых зон, предупреждать оператора станка в случае обнаружения дефекта детали. Несмотря на кажущуюся простоту подобные системы работают по сложным алгоритмам, состоящим из нескольких этапов. Если говорить о наиболее сложных из них, то следует обратить внимание на алгоритмы сегментации входной информации. Их основной задачей является выделение на входящем изображении участки, которые представляют ценность для исследования, либо проведения операций над ними. Принимая во внимание популярность подобных систем следует отметить, что исследование, оптимизация и улучшений работы алгоритмов, решающих подобные задачи, является достаточно актуальным вопросом в настоящее время. Рассматривая существующие методы сегментации изображений можно обратить внимание на то, что некоторые из них являются более популярными, а другие нет. В настоящее время наиболее часто используется сегментация методами Otsu, Adaptive Treshold, ISODATA [1]. Данные методы получили широкое распространение на счет своей универсальности, а также простоты своей реализации на ЭВМ. Наиболее простым из исследуемых является метод кластеризации Otsu. Метод Otsu Данный метод использует автоматический выбор порога бинаризации, основанного на гистограммах, что позволяет алгоритму адаптироваться под конкретное изображение. В целом работа алгоритма состоит из двух шагов. Шаг 1. Автоматический расчёт порога кластеризации с использованием нормированной гистограммы яркостей изображения производится по формуле [2]: , (1) где - общее число пикселей на изображении; - число пикселей с уровнем яркости Шаг 2. Процедура кластеризации изображения с использованием рассчитанного порога. Диапазон яркостей пикселей исходного изображения делятся на два класса t (целое значение от 0 до L, где - максимальное значение яркости). Также учитывается, что каждому классу соответствует [3]: ω0 ω0(t) = ; ω1(t) = 1 - ω0(t); (2) μ0(t) = ; μ1(t) = , где ω0(t) и ω1(t) - относительные частоты появления значений каждого из классов 0 и 1, разделенных порогом i; μ0(t) и μ1(t) - средние уровни для каждого из указанных двух классов, разделенных порогом. Использование данного метода оправдано в случаях, когда изображение состоит из объекта и фона. При таких условиях порог определяется максимально точно, что позволяет выделить объект с минимальной погрешностью (см. рис. 1). а) б) Рис. 1. Результат сегментации методом Otsu: а) до обработки; б) после обработки изображения Несмотря на достоинства и простоту сегментации методом Otsu, его слабой стороной является кластеризация участков на изображениях, имеющих сложную структуру. Например, неконтрастный фон, наличие затемненных участков. Этих недостатков можно было бы избежать, если рассчитывать порог для методаOtsu не один раз для всего изображения, а для определенного участка: кластера, либо пикселя [4]. Метод Adaptive Threshold Одним из алгоритмов, которые используют такой подход является AdaptiveТhreshold. Чтобы был понятен принцип работы алгоритма, требуется описать его математически. Известно, что является исходным изображением, которое требуется кластеризовать; представляет собой расчетную величину градиента для исходного изображения рассчитываемая по формуле . (3) Этот метод отличается от предыдущего тем, что использует расчет адаптивного порога для каждого пикселя изображения. Это позволяет представить кластеризацию в следующем виде: (4) В данном случае и представляют собой поверхности в двумерном пространстве 2D, которые имеют пересечение в точке . Исходя из данного выражения следует полагать, что пересечение плоскостей будет происходить в тех точках, где находится целевая область на изображении. Это можно трактовать следующим образом: если является правильной пороговой поверхностью, то значение (где является хаусдорфовой мерой для c, а - число граничных точек объекта), будет максимальным. Это позволяет преобразовать функцию T к функциональному пространству по й формуле (5) где - первая производная от и . Полученная функция является достаточно сложной, ее можно значительно упростить. В этом случае изначальная функция примет вид [5]: (6) где - параметр регуляризации. Дальнейшая минимизация выражения (5) сводится к решению уравнения Пуассона: (7) где α = 1/2λ. Поскольку касается c; то может быть записан как F(x(T),y(T)) по правилу цепи: (8) - измененная функция Т [2]. Таким образом, согласно [6] (9) Это выражение позволяет определить пороговое значение кластеризации для каждого пиксела изображения, что делает его универсальным и позволяет применять его в достаточно широком спектре задач. Рис. 2. Исходное изображение с большим числом мелких деталей Чтобы произвести оценку работы алгоритма были выбраны два тестовых изображения. На первом изображении расположено большое количество небольших областей, которые являются целевыми (см. рис. 2). Универсальность метода AdaptiveТhreshold позволяет получить приемлемые результаты даже в случае большого числа небольших областей (см. рис. 3). Рис. 3. Результаты кластеризации первого тестового изображения После обработки на первом изображении видны границы даже мелких деталей, но присутствует и множество ненужных артефактов, которые образовались из-за наличия шероховатости поверхностей. Эти погрешности имеют незамкнутые контуры, что позволяет впоследствии убрать их с изображения [7]. Во втором тестовом изображении имеется контрастный фон, но при этом имеется большое количество тонких и коротких граней, что заметно усложняет процесс обнаружения (рис. 4). Рис. 4. Исходное изображение для кластеризации областей с гранями объекта После обработки этого изображения были получены следующие результаты (см. рис. 5). Результирующие области были выделены корректно. Исключение составляют лишь небольшие области за границами детали, которые появились в результате зашумления контуров исходного объекта. Рис. 5. Результат кластеризации второго тестового изображения Последнее изображение наиболее подходит для выделения контуров. Деталь контрастна на фоне, что делает контур наиболее четким (см. рис. 6). Рис. 6. Изображение для кластеризации с минимальным наличием шума и дефектов объекта В результате обработки этого изображения были выделены грани деталей, а также небольшие дефекты на ее поверхности (см. рис. 7). Такие результаты были достигнуты за счет отсутствия дефектов исходного изображения. Рис. 7. Результат кластеризации изображения, содержащего минимум дефектов и шумов Из полученных результатов можно сделать вывод о том, что данный алгоритм является чувствительным к наличию шума на исходном изображении, поэтому предварительно нужно выполнять корректирующие действия, например, медианную фильтрацию, что существенно снизит число нежелательных артефактов. Еще одной негативной стороной по сравнению с методом Otsu является большой объем вычислений порогов яркостей, благодаря чему достигается неплохой результат сегментации, но увеличивается вычислительная сложность. Метод ISODATA Оба рассмотренных алгоритма были разработаны сравнительно давно. В настоящее время широко распространен алгоритм ISODATA, который позволяет наиболее точно кластеризовать интересующую область на изображении. Данный алгоритм позволяет автоматически настраивать число кластеров во время итеративного процесса путем слияния схожих по заданной мере кластеров и расщепления кластеров с большим внутренним среднеквадратичным отклонением. Алгоритм ISODATA настраивается следующими параметрами: - желаемое число кластеров; - максимально допустимое число итераций; - максимальное число пар объединяемых кластеров; - пороговое значение для минимального числа элементов в кластере (используется для удаления малых кластеров); - пороговое значение для среднеквадратичного отклонения (используется для операции расщепления); - пороговое значение для межклассового расстояния (используется для операции слияния). Алгоритм состоит из следующих шагов [8]. Шаг 1. Произвольный выбор (необязательно K) начальных центров кластеров из исходной выборки , i = 1; 2 ... N. Шаг 2. Определение каждого из N элементов выборки в ближайший кластер , если [9] Шаг 3. Удаление кластеров с числом элементов меньше : если для некоторого выполнено , то кластер удаляется, уменьшается на единицу. Шаг 4. Обновляются центры кластеров: (10) Шаг 5. Рассчитываются средние расстояния от каждого элемента кластера до соответствующего центра кластера: (11) Шаг 6. Вычисляется общее среднее расстояние от элементов до центра соответствующего кластера: (12) Шаг 7. Если (кластеров мало), то переходим к шагу 8. Если (кластеров много), то переходим к шагу 11, иначе - к шагу 12. Шаг 8. Первый шаг расщепления. Находится вектор стандартного отклонения [10]: (13) Шаг 9. Находится максимальное из . Шаг 10. Расщепление кластера. Шаг 11. Слияние кластеров по принципу Min расстояния между их центрами. Шаг 12. Остановка в случае превышения Max числа итераций. Рассматривая данный алгоритм можно обратить внимание, что сложность его наиболее высокая по сравнению с предыдущими. Несмотря на это он позволяет добиться наилучших результатов (см. рис. 8). Рис. 8. Результат кластеризации с использованием алгоритма ISODATA В данном тесте алгоритмом были сегментированы интересующие области в виде темных областей с точными границами, что делает их пригодными для последующей обработки. Заключение Подводя итог, можно сделать вывод о том, что при выборе одного из рассмотренных алгоритмов следует обратить внимание на вычислительную сложность и скорость его работы. Если в работе телевизионной системы требуется лишь определить наличие интересующей области на кадрах видеоряда, то исходное изображение следует кластеризовывать методом Otsu. В случае же необходимости более детального выделения каждой области, например, для распознавания образов, требуется применение двух других алгоритмов, которые позволяют получить более точные границы каждого из объектов.

About the authors

Alexey Sergeevich Loshkarev

Povolzhskiy State University of Telecommunications and Informatics

Email: lozhkarev-as@mail.ru

References

Supplementary files