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

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.

Похожие публикации

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 40

    +1
    На чём реализовывали алгоритм?
      0
      На C#.
        +1
        Если это не секретные разработки, интересно посмотреть и опробывать исходники в действии на других картинках. Хочется код в всеобщее обозрение.
          +1
          Проблема в том, что реализация входит в состав большой программы, используются методы и классы из других файлов. Поэтому просто опубликовать файл с методом не получится, нужно это всё вычленить, убрать лишнее и т.п. Возможно, позже сделаю. Хотя метод не сложный, мне кажется, просто описания достаточно.
            +3
            Хотя бы псевдокод в топике.
              +2
              Набросал псевдокод по статье. На C++

              www.copypastecode.com/64225/
                0
                Спасибо.
                0
                Читать имеет смысл начинать с метода void SomeCode();
                Который символизирует вызов из внешнего кода.
        +1
        Отличная статья, побольше бы таких. Спасибо.

        Как уже сказали выше, было бы неплохо, если бы была возможность попробовать «вживую».
        Может быть получится сделать набор статей с реальными примерами алгоритмов при обработке изображений, лично мне эта тема очень интересна.
          +7
          Прочитал — интересно, этот материал нам на лекциях рассказывали в университете. Добавил в избранное. Я вообще предлагаю создать отдельный блог по обработке изображений, ибо количество статей на эту тему странным образом увеличивается. Вот в ближайшее время планирую публикацию поста о распознавании на изображениях специфических объектов, и поместил бы его в новый блог.
            +3
              0
              Спасибо! Однако я сам пытался создать такой блог — не получилось, было написано что хабр коллапсирует от новых блогов. Рад что это у вас получилось. Будем наполнять эксклюзивной инфой новый блог.
                +6
                Ну ещё бы у него не получилось :]
                0
                Перенёс топик в новый блог.
                  0
                  Вопрос: почему я не могу перенести свой старый пост об обработке изображений в этот блог? Там его просто нет в списке.
                    0
                    Предположение — может быть, вы забыли подключиться к новому блогу?
                      0
                      Точно, спасибо
                0
                Мы всего-навсего заменяем яркость в точке средней по какой-то окрестности — то есть банально уменьшаем разрешение. Вообще не учитываем при подсчёте среднего расстояние от точки в слагаемом, до центра (ну то есть точки, для которой считаем). Как вы думаете, что произойдёт с тонкой красной линией?
                  +1
                  Да, правильное замечание. Вместо взятия среднего арифметического для сглаживания изображений (и подавления шума) часто используется взвешенное среднее с коэффициентами Гаусса, в нём как раз учитывается расстояние. Однако среднее арифметическое тоже даёт неплохие результаты, а доказательство состоятельности и несмещенности для такой оценки есть в любом учебнике по матстатистике (в отличие от взвешенного среднего, здесь ещё нужно доказать, что его можно использовать).
                  Позволю себе не согласиться с вами относительно того, что сглаживание изображения эквивалентно уменьшению разрешения.
                  Про красную линию — во-первых, забыл сказать, что работаем с черно-белыми (полутоновыми) изображениями, во-вторых — она даст полупрозрачный красный след ширины 2r. Если использовать взвешенное среднее — даст след ширины 2r, который в центре будет ярче, к краям бледнее — поэтому обычно предпочитают взвешенное сглаживание.
                    +2
                    Для полноты информации добавил примечание про сглаживание Гаусса.
                    0
                    Это здорово, что есть упоминание о том, что мы знаем, что ищем.
                    Однако что делать, если задача — найти особенности, формфактор которых неизвестен и вообще неизвестно, присутствуют ли они на снимке? Я правильно понимаю, что метод сложноприменим в этом случае?
                      +1
                      Да, для такого случая есть другие методы, например, метод пятна. Если появится время и настроение, расскажу о нём тоже, но в ближайшее время вряд ли получится.
                        0
                        Промотивирую ка я вас на написание.
                      +1
                      Не преуменьшая ценности вашего описания, хотелось бы озвучить, что на практике подобный алгоритм реализуется двумя операциями:

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

                      2. Применяется пороговый фильтр, отсекающий пиксели с малой яркостью (фон) от пикселей с большой яркостью (объект).
                        +1
                        Спасибо за дополнение! У меня в коде именно так и получилось, само по себе в процессе рефакторинга.
                          0
                          Вы забыли о операции преобразования исходного изображения в полутоновое
                          0
                          а можно тоже самое, но на более реальных примерах… наклоненный квардратик больно идеализированная штука
                            +1
                            Да-да! Можно зебру, пожалуйста? ;)
                              0
                              Посмотрите на аэроснимки местности в ИК-диапазоне, например, на этом сайте (нашёл сейчас через Гугл). Там можно заметить множество объектов, которые в среднем светлее или темнее фона. Размеры их тоже известны, если знаем, что ищем — поскольку высота съёмки тоже известна, и можно вычислить, сколько метров в одном пикселе. Метод применим для поиска всех таких объектов. Да, ещё, правда, нужно, чтобы объекты не стояли слишком близко друг к другу, иначе не удастся найти зону интереса для отдельного объекта.

                              Например, можно искать дома или ёжиков
                                0
                                Сколько пикселей в метре можно вычислить зная разрешение изображения, а высота съемки как правило неизвестна, более того, любая инфа о устройстве дистанционного зондирования Земли — для служебного пользования. На этих снимках данным методом сложно что-то найти. И вообще согласно нашему законодательству эти снимки относятся к секретным, слишком уж высоко разрешение, если это территория РФ.
                                  0
                                  Возможно, высота и неизвестна. Практически с этими устройствами и снимками не работал, просто в тех источниках, которые читал, было написано, что для съёмки самолёт пролетает на заданной высоте — далее через угол и высоту вычисляем размеры основания пирамиды, которую видит камера, ну и физические ширину/высоту изображения делим на число пикселей по ширине/высоте. Возможно, реально делают совсем по-другому, не знаю.
                                    0
                                    Да, все верно. Простите мой столь резкий комментарий, был приступ ночной паранойи.
                              0
                              Вспоминается курс Computer Vision, который я год назад прослушал. Отличная статья, походу, понятнее чем нам тогда объясняли.
                                –1
                                Добавить на картинку градиент — и описанный метод уже не прокатит. Думал, что будет что-то интереснее, чем blur+treshold ((
                                  0
                                  Такие методы в чистом виде редко используются. Почти всегда существует некоторая предварительная обработка изображения, определяемая решаемой задачей. В том числе существуют методы борьбы с градиентом. Так что статья не бесполезная. Это база.
                                  0
                                  А по какому принципу подбирается радиус сглаживания? Можно ли его подобрать автоматически? Что сделает алгоритм, если шум заметно больше разницы яркостей? Не загладятся ли у квадрата при этом углы? Если да — как их потом восстановить (если заранее неизвестно, что это квадрат)?
                                    0
                                    Радиус сглаживания зависит от качества изображения, которое определяется соотношением сигнал/шум. Подбирается эмпирически. Здравый смысл подсказывает, что за 50 лет должны были появиться какие-то работы по поводу автоматического выбора радиуса, но специально не искал и случайно не встречал.
                                    При возрастании шума на квадрате появляются «дырки», а на фоне — «пятна». В предельном случае будет равномерная пятнистая каша по всей зоне интереса. По поводу восстановления искаженной шумом проекции кое-какие мысли есть, но по-моему, это неверный путь — в тяжелых случаях нужны другие, более надежные методы.
                                    0
                                    Во-первых, эта статья страшно напомнила мне мою: habrahabr.ru/blogs/algorithm/112079/ :) Похожие картинки, похожая структура поста :)

                                    Во-вторых, алгоритм из моей статьи можно совместить с описанным вами, чтобы находить оптимальный порог.
                                      0
                                      Действительно, очень похоже. Спасибо за ссылку на статью.
                                        0
                                        Про второе, я бы сказал, описанные два метода — два разных способа находить порог, в зависимости от имеющейся информации. Не уверен, что их можно скомбинировать во что-то полезное, хотя подумать стоит.

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

                                      Самое читаемое