Источник: Graphicon
Алгоритм уточнения предварительной сегментации изображений с нечеткими, слабоконтрастными границами двумерных объектов
Авторы: Е.В. Заугольнова, Д.В. Юрин
Аннотация
Предложен, основанный на вычислении разрезов графа, алгоритм уточнения границ сегментов, получаемых в результате алгоритмов сегментации поиском водоразделов.
Ключевые слова: сегментация, детектор краев, уточнение границ, минимальный разрез графа, поиск водоразделов.
1. ВВЕДЕНИЕ
Задача сегментации изображений относится к фундаментальным, старейшим и наиболее сложным проблемам компьютерного зрения [1]. Разнообразие применяемых подходов и тематически ориентированных задач делают затруднительным сколько-нибудь полный обзор работ по этой тематике. Тем не менее, не смотря на активные исследования в течение нескольких десятков лет, эта проблема далека от приемлемого решения. В последние годы наметился существенный прогресс в области интерактивной сегментации [2-4]. Основная идея в этих работах состоит в следующем: пользователь выделяет на изображении несколько областей, которые должны принадлежать разным сегментам (образцы или затравки сегментов), затем компьютер производит сегментацию всего изображения с учетом введенных пользователем указаний. Если результат не удовлетворяет пользователя, то обычно предусматривается возможность дорисовать дополнительные затравки, и, с их учетом, уточнить сегментацию. В качестве алгоритма сегментации по образцам в работах [2-3] используются алгоритмы на основе поиска минимального разреза графа/максимального потока [5] и α-expansion [6-8]. Получаемая таким образом сегментация обеспечивает точное определение границ объектов и не приводит к излишней детальности (over-segmentation). Недостатком этих алгоритмов является необходимость взаимодействия с человеком, что исключает их использование в полностью автоматических системах, таких, например, как системы зрения роботов, пакетная обработка медицинских и аэрокосмических изображений.
В качестве полностью автоматических методов сегментации следует упомянуть алгоритмы, основанные на поиске водоразделов (watershed) [9-11]. Они основаны на построении промежуточного серого изображения, яркость которого тем выше, чем более отчетливая граница обнаружена в этой точке на исходном изображении, после чего это изображение трактуется как рельеф местности и выполняется его заливка. Эти алгоритмы обычно дают излишне детальную сегментацию и на последующем этапе выполняется слияние похожих по характеристикам соседствующих сегментов [13- 15]. За исключением некоторых специфических подходов [12], где сегментация методом водоразделов выполняется с крайне высокой детальностью, и все проблемы переносятся на этап слияния, обычно предпринимаются меры, чтобы размер выделяемых сегментов был не слишком мал. Часто это требование оказывается автоматически выполненным из- за выбора достаточно большой рамки [9,10] для построения рельефного изображения, что необходимо при обработке изображений с нечеткими, слабоконтрастными границами [9]. Это часто приводит к неточности определения границ объектов, сопоставимой с размером рамки. Заметим здесь, что такая неточность определения границ сегментов нежелательна как сама по себе, так и с точки зрения последующего применения алгоритмов укрупнения сегментации или классификации сегментов по вектору признаков, так как ошибочно отнесенные к сегменту пиксели искажают статистические характеристики, вычисляемые по сегменту.
В настоящей работе предлагается автоматический алгоритм сегментации, комбинирующий подходы метода водоразделов и разрезов графа. Алгоритм [9] дает начальную сегментацию с неточными границами, но обеспечивает начальную разметку для алгоритма на графах, который обеспечивает высокую точность границ.
2. СПОСОБ УТОЧНЕНИЯ ГРАНИЦ
2.1 Основные этапы алгоритма
Исходными данными для алгоритма являются изображение и результат его сегментации с неточно обнаруженными границами как на рис.1. Такая начальная сегментация получалась алгоритмом [9] и представляется в виде отдельного изображения, пиксели которого имеют значения от 1 до N (число полученных сегментов), каждому сегменту соответствует свое число.
Предлагаемый метод уточнения границ состоит из трех этапов:
Алгоритм 1:
I. Выделение областей изображения подлежащих уточнению (раздел 2.2).
II. Первичное уточнение сегментов изображения в выделенных областях (раздел 2.3).
III. Постобработка оставшихся неразмеченными пикселей изображения (раздел 2.4).
2.2 Выделение областей изображения подлежащих уточнению
границ сегментов от искомых границ объектов зависит от извилистости этих границ. Как правило, она не превышает 1/4-1/2 диаметра D рамки, использованной в [9]. Исключение составляют случаи, когда граница объектов содержит выступы и впадины шириной менее размера рамки и значительной глубины. Признаком такой ситуации является соприкосновение уточненной границы с не подлежавшим уточнению на этом этапе остовом сегмента, этот случай будет рассмотрен в заключительной части раздела 2.3. Таким образом, истинную границу между объектами надо искать в коридоре шириной +/-D/2 около границ сегментов, найденных [9]. Кроме того, на этапе уточнения границ следует избегать создания новых сегментов, поэтому в ходе разметки коридоров следует обеспечивать сохранение связности сегментов. Для выделения этих коридоров предлагается использовать алгоритм Зонга-Суня [16].
Основная идея алгоритма Зонга- Суня заключается в том, что на каждом шаге, пробегая по изображения рамкой 3x3, проверяется принадлежность каждого пикселя к границе заданной связной области. Если условия проверки выполняются, то пиксель удаляется из области. Вне зависимости от количества выполненных шагов область останется связной, в предельном случае она выродится в линию толщиной в один пиксель.
Учитывая контекст задачи, возможно использование данного алгоритма для разметки коридоров сразу между всеми сегментами изображения. Осуществляется это следующим образом: при каждом текущем положении рамки условия на принадлежность границе будут проверяться для сегмента, меткой которого помечен пиксель в ее центре (за исключением тех случаев, когда центральный пиксель уже принадлежит какому-либо коридору). На рис.2б изображен результат работы алгоритма при D=12, на рис.2а – после первого шага алгоритма, примененного к рис.1б.
2.3 Первичное уточнение сегментов
Для уточнения границ сегментов предлагается алгоритм, отчасти схожий с α-expansion [6,7]. Однако граф строится планарный, сеточный, а не как в [6,7] и задача не формулируется как минимизация энергии. Такой выбор обусловлен тем, что в рамках задачи минимизации энергии сложно добиться сохранения односвязности сегмента, установка же завышенного веса члена, сохраняющего разрывы (discontinuity preserving), приведет одновременно к плохо контролируемому спрямлению границ сегментов.
Алгоритм 2:
Для каждого сегмента из начальной сегментации (см., например, рис.1б):
1. По имеющейся начальной сегментации находятся все его соседние сегменты.
2. Строится граф таким образом, что его минимальный разрез соответствует границе между двумя областями. Первая область обязана содержать затравку рассматриваемого сегмента, а вторая затравки соседних сегментов (рис. 3а).
3. Ищется минимальный разрез в построенном графе и в зависимости от результата метятся пиксели коридоров.
4. Постобработка результатов.
В построении графа учитываются только пиксели, принадлежащие по начальной разметке (рис.1б) либо рассматриваемому сегменту, либо его соседям, найденным на первом шаге, в том числе и пиксели коридоров (рис.3а).
Ниже описан способ построения графа. Кроме истока S и стока T в него также добавляются вершины соответствующие пикселям, участвующим в построение графа. Каждая вершина соединяется ребрами с соседними, если таковые существуют, как показано на рис.3б. Вес ребра wij между соседними вершинами i и j моделировался в виде функции зависящей от разности яркости Iαi , Iαj цветовых компонент α пикселей i и j , соответствующих этим вершинам и расстоянию между ними dij , которое для графа рис.3 равно либо 1 либо корень из 2 :
Функциональный вид зависимости от расстояния выбирался в соответствии с [8], выбор зависимость от яркости эвристический и конечно требует дальнейших исследований. Нормировка на дисперсию обеспечивает инвариантность результатов относительно линейных преобразований гистограммы яркости изображения и независимость эмпирических коэффициентов μ и β от разрядности цветовых компонент.
Области, оставшиеся от сегментов после этапа утончения сегментов 2.2 не подлежат разметке, что обеспечивается соединением соответствующих вершин графа со стоком или истоком сети ребрами весом
так, что через все максимум 8 ребер, соединяющие вершину графа с соседями не может быть пропущен поток больше w0 .
Минимальный разрез в построенном графе предлагается искать, используя алгоритм поиска максимального потока описанный в [5]. Область пикселей в результате работы данного алгоритма отнесенная к истоку помечаются той же меткой, что и текущий сегмент, остальные остаются неизменными.
В результате выполнения Алгоритма 2 большая часть пикселей принадлежащих коридорам отнесется к какому- нибудь сегменту, но также останутся и неразмеченные (рис. 4).
Постобработка результатов предполагает обработку случая, описанного вначале раздела 2.2. Речь идет о том, когда складывается такая ситуация, что в результате первичного уточнения сегмент увеличивается на столько, что начинает граничить с гарантированной областью другого сегмента. Подобная ситуация говорит о том, что коридоры были выделены не достаточно глубоко и часть сегмента одного номера попала в гарантированную область сегмента другого номера. Для этой проблемы предлагается: локализовать проблемную область и уже в ней заново проделать процедуру выделения коридоров и первичное уточнение сегментов и так до тех пор, пока найденная граница не будет касаться затравки сегмента.
2.4 Постобработка неразмеченных пикселей изображения
После выполнения предыдущего этапа некоторые области изображения остаются неразмеченными (рис.4). Причиной является то, что при найденном значении максимального потока могут существовать несколько минимальных разрезов, имеющих в точности одинаковый вес. Поэтому разметка соответствующих областей осуществляется следующим образом. С помощью алгоритма Бразенхэма [18]неразмеченные пиксели объединяются в связные области. Каждая из них присоединяется к одному из своих соседних сегментов, выбираемому следующим образом. Выделяется коридор вокруг текущей неразмеченной области P такой ширины, чтобы его площадь была наиболее близка к сумме k площадей этой области. Пиксели P присоединяется к тому соседнему сегменту, средняя яркость пересечения которого с выделенным коридором наиболее близка к средней яркости области P.Результат работы этого алгоритма представлен на рис. 5б. Значение k выбиралось равным 4.
3. ЗАКЛЮЧЕНИЕ
В статье предлагается алгоритм уточнения границ основанный на поиске минимального разреза графа. На рис. 6 показан результат работы предложенного алгоритма на фрагменте космического снимка со спутника серии NOAA. Тестирование алгоритма показало, что точность обнаружения границ сегментов значительно и стабильно улучшается.
4. БЛАГОДАРНОСТИ
Работа выполнена при финансовой поддержке РФФИ, грант 06-01-00789.
5.БИБЛИОГРАФИЯ
[1] William K. Pratt. Digital Image Processing. // Wiley- Interscience; 3 edition
[2] Yuri Boykov and Marie-Pierre Jolly. Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D images. //In International Conference on Computer Vision, (ICCV) 2001, -Vol.1, -P.105-112. http://www.csd.uwo.ca/faculty/yuri/Papers/iccv01.pdf .
[3] Carsten Rother, Vladimir Kolmogorov and Andrew Blake. GrabCut - Interactive Foreground Extraction using Iterated Graph Cuts. //In ACM Transactions on Graphics (SIGGRAPH), August 2004, -Vol.23, -No.3, -P. 309 – 314. http://research.microsoft.com/vision/cambridge/segmentation/Pap ers/paper_siggraph04.pdf
[4] Vladimir Vezhnevets, Vadim Konouchine. "GrowCut" - Interactive Multi-Label N-D Image Segmentation By Cellular Automata. // In Conference Proceedings. 14-th International Conference on Computer Graphics and Vision GraphiCon'2005 - P. 150-156. June 20 - 24, 2005 Novosibirsk Akademgorodok, Russia. http://www.graphicon.ru/proceedings2005/papers/VezhntvetsKon ushin.pdf
[5] Yuri Boykov and Vladimir Kolmogorov. An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision. //In IEEE Transactions (PAMI), Vol. 26, -No. 9, -P. 1124-1137, Sept. 2004. http://www.cs.cornell.edu/Peo ple/vnk/papers/BK-PAMI04.pdf
[6] Yuri Boykov, Olga Veksler, Ramin Zabih. Fast Approximate Energy Minimization via Graph Cuts. //In IEEE Transactions on PAMI, 2001. -V. 23, -No.11, -P.1222-1239. http://www.csd.uwo.ca/faculty/yuri/Papers/pami01.pdf
[7] Vladimir Kolmogorov, Ramin Zabih. What Energy Function can be Minimized via Graph Cuts? // In IEEE Transactions on PAMI, February 2004. -V. 26, -No.2, -P. 147-159. http://www.cs.cornell.edu/People/vnk/papers/KZ-PAMIgraph_ cuts.pdf
[8] Yuri Boykov and Vladimir Kolmogorov. Computing Geodesics and Minimal Surfaces via Graph Cuts. //In International Conference on Computer Vision, (ICCV), vol. I, pp. 26-33, 2003. http://www.csd.uwo.ca/faculty/yuri/Papers/iccv03.pdf .
[9] Mintchenkov M.V., Yurin D.V., Helvas A.V. Unsupervised Algorithm for Images Segmentation on the Base of the Rayleigh 2D Objects Boundaries Detector. // In Conference Proceedings. 12-th International Conference on Computer Graphics GraphiCon'2002 -P. 243-250. Nizhny Novgorod, September 16- 21, 2002. http://www.graphicon.ru/2002/pdf/Mintchenkov_Re.pdf.
[10] Deng Y., Manjunath B.S., Shin H. Color Image Segmentation // IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR '99 — 1999 — V.2. — P.446–451. http://vision.ece.ucsb.edu/publications/99CVPRSeg.pdf
[11] Jing, F., Li, M., Zhang, H.J., Zhang, B. Unsupervised Image Segmentation Using Local Homogeneity Analysis. // Proc. IEEE International Symposium on Circuits and Systems, 2003. http://citeseer.ist.psu.edu/jing03unsupervised.html .
[12] Nikolaev D.P., Nikolayev P.P. Linear color segmentation and its implementation. //Computer Vision and Image Understanding, 2004, V. 94, pp. 115-139. http://www.ddt.ru/chaddt/Lace/pub.html
[13] S. Makrogiannis, G. Economou, and S. Fotopoulos. A graph theory approach for automatic segmentation of color images. //In International Workshop on Very Low Bit-rate Video, pages 162-- 166, 2001. http://citeseer.ist.psu.edu/makrogiannis01graph.html .
[14] Koepfler G., Lopez C.,Morel J.M. A Multiscale Algorithm for Image Segmentation by Variational Method // SIAM Journal on Numerical Analysis. — 1994 — V.31 — N 1. — P. 282–299. http://citeseer.ist.psu.edu/koepfler94multiscale.html .
[15] Nepomnyaschy P.V., Yurin D.V. Creation of hierarchical detail tree of image segmentation via solving minimum cut problem. // In Conference Proceedings. 13-th International Conference on Computer Graphics and Vision GraphiCon'2003 - P. 213-220. Moscow, September 5-10, 2003. http://www.graphicon.ru/2003/Proceedings/Technical_ru/paper87 2.pdf .
[16] T. Y. Zhang, C. Y. Suen. A fast parallel algorithm for thinning digital patterns // Commun. ACM, vol. 27, no. 3, pp. 236--239, 1984.
[17] Olga Veksler. Image Segmentation by Nested Cuts // IEEE Computer Vision and Pattern Recognition, June 2000 (CVPR'00), p.339-344. http://www.csd.uwo.ca/faculty/olga/Papers/cvpr00.pdf.
Об авторах:
Заугольнова Екатерина Викторовна – студентка факультета вычислительной математики и кибернетики Московского Государственного Университета им. М.В. Ломоносова E-mail: zaugolnovaev@mail.ru
Юрин Дмитрий Владимирович – кандидат физ.-мат. наук, ФГУП НПП ОПТЭКС, главный специалист. Телефон: +7-(916)-387-7367, +7-(495)-535-4887 E-mail: yurin_d@inbox.ru