Pull to refresh

Сегментация изображений методом квантилей

Reading time 5 min
Views 11K
image Сегментацией называется присвоение пикселям изображения меток так, что области, обладающие сходными в определённом смысле свойствами, имеют одинаковые метки. Также сегментацией порой называют поиск проекции объекта на изображении. Данный топик расскажет о простом, но эффективном методе поиска проекции объекта, называемом методом квантилей. Указана область применимости метода и приведены некоторые модификации, повышающие эффективность.

Некоторые понятия и предположения


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

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

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

Исходные данные и постановка задачи


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

Необходимо пометить пиксели, принадлежащие проекции объекта.

В качестве примера возьмём вот такое изображение:
image

Оно имеет размер 140х140 пикселей. На нём изображён квадрат размером 80х80 пикселей, расположенный в центре и повёрнутый на 15 градусов. Средняя яркость фона — 80, средняя яркость объекта — 120. Гауссов шум имеет стандартное отклонение 20.

Оригинальный метод квантилей


Метод квантилей был впервые описан в работе [1]. Метод в его исходном виде предполагает, что яркость любого пикселя объекта на изображении выше, чем яркость любого пикселя фона. Из этого предположения вытекает простой метод сегментации. Упорядочим все пиксели изображения по убыванию яркости. Из нашего предположения следует, что пиксели, принадлежащие проекции объекта, расположатся в начале упорядоченной последовательности. Поэтому мы можем пометить первые S пикселей меткой «Объект» — они и будут принадлежать искомой проекции.

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


Стоит обсудить ещё один небольшой вопрос. На реальных изображениях, как наше, вряд ли удастся подобрать такое пороговое значение яркости, чтобы большую порога яркость имели ровно S пикселей изображения. Часто при одном пороге яркости (t) мы отсекаем A<S пикселей, а при пороге (t-1) — B>S пикселей. «Упорядочить», как предложено выше, одинаковые по яркости пиксели мы не можем, мы должны или брать все пиксели яркости (t), или не брать. Самым простым способ решить — посмотреть, что меньше: (S-A) или (B-S). Смотрим, какое число — A или B — ближе к тому, что нужно получить, и берём соответствующий порог. Именно такой метод применялся при получении изображений, представленных в топике.

«Улучшенный» метод квантилей


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

Математическая статистика говорит нам, что в нашем случае гауссова шума оценка среднего значения яркости в точке, выполненная путём вычисления среднего арифметического яркости по окрестности, будет состоятельной и несмещённой оценкой. Иными словами, мы не знаем истинную среднюю яркость для каждого пикселя изображения, но мы можем взять некоторую окрестность этого пикселя B(z,r), где z — координаты пикселя, r — радиус окрестности:
Квадратная окрестность B(z,r)

и вычислить среднее арифметическое яркости по этой окрестности:
Среднее арифметическое по окрестности

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

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

Для нашего изображения мы получим вот такой результат (сегментация с r=1):
Улучшенный метод квантилей, r=1

Результат заметно улучшился. Увеличим радиус для вычисления среднего арифметического до r=2:
Улучшенный метод квантилей, r=2

При радиусе 2 посторонних «пятнышек» совсем не осталось! Можно, однако, заметить, что с увеличением радиуса искажается граница объекта. Это связано с тем, что оценка истинного среднего по среднему арифметическому верна лишь тогда, когда окрестность B(z,r) лежит или целиком на объекте, или целиком на фоне, то есть когда в неё попадают случайные величины с одним и тем же оцениваемым средним значением. На границе в окрестность попадают пиксели и фона, и объекта, что, естественно, искажает оценку.

Модификация алгоритма


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

Ниже представлены результаты, полученные после выполнения выбора наибольшей связной компоненты на изображениях с результатом сегментации оригинальным методом и «улучшенным» методом с r=1 (при r=2 и так остаётся всего одна связная компонента):

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

Заключение


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

Источники


[1] Doyle W. Operations useful for similarity invariant pattern recognition. // Journal ACM. 1962. Vol. 9, № 2. С. 259-267.
Tags:
Hubs:
+67
Comments 40
Comments Comments 40

Articles