Мы продолжаем публиковать лекции Натальи Васильевой, старшего научного сотрудника HP Labs и руководителя HP Labs Russia. Наталья Сергеевна читала курс, посвящённый анализу изображений, в петербургском Computer Science Center, который создан по совместной инициативе Школы анализа данных Яндекса, JetBrains и CS-клуба.
Всего в программе девять лекций. Первая и вторая уже были опубликованы. В предыдущем рассказе речь шла об основах пространственной и частотной обработки изображений. Третья лекция посвящена основным операциям морфологической обработки изображений. Под катом — слайды, план лекции и её дословная расшифровка.
Основные операции математической морфологии:
Производные морфологические операции:
Всего в программе девять лекций. Первая и вторая уже были опубликованы. В предыдущем рассказе речь шла об основах пространственной и частотной обработки изображений. Третья лекция посвящена основным операциям морфологической обработки изображений. Под катом — слайды, план лекции и её дословная расшифровка.
- Математическая морфология
- Базовые операции теории множеств
- Отражение и перенос
- Структурный элемент
Основные операции математической морфологии:
- dilation
- dilation: примеры
- примерные расширения
- эрозия
- эрозия: примеры
- применение расширения и эрозии
- пример
Производные морфологические операции:
- Opening
- closing
- свойства
- Hit-or-Miss Transform
- выделение границ
- заполнение областей
- выделение связных компонент
- построение выпуклой оболочки
- утончение
- утолщение
- построение остова
- усечение
- заключение
Полная текстовая расшифровка лекции
Методы такой математической морфологии в контексте обработки изображений были предложены в 1964 году французами Жан-Пьером Серром и Жоржем Матероном. Жан Серр собственно писал кандидатскую диссертацию на эту тему. Вскоре после защиты его диссертации в Париже был открыт целый центр математической морфологии, и на изучение этих методов было потрачено значительно большее количество времени, целый такой раздел.
В основе этих методов лежит теория множеств. Предполагается, что любой объект на изображении можно представить тоже в виде множества, либо множества в двумерном пространстве, либо множества в трёхмерном пространстве.
Мы будем сегодня обсуждать методы применительно только к двумерному пространству, так называемую бинарную морфологию. Но это всё достаточно интуитивно расширяется на трёхмерный случай. Как же представляется изображение в случае бинарном?
Опять же бинарный — это значит, у нас есть только чёрные, только белые пиксели. И тогда фиксируем цвет фона. Предположим, фон у нас белый, то тогда объект задаётся набором координат точек, принадлежащим этому объекту, ну и, соответственно, принадлежность множеству. То есть набор пар х, у, которые принадлежат объекту, формируют множество.
Ещё как в школе (я не знаю кто где начал изучать теорию множеств) рисуют множество, чтобы пояснить, что такое объединение пересечений и так далее. Тут самое интуитивное понятие — это как раз те же самые картинки и есть. В трёхмерном случае у нас добавляется ещё одна координата, это значение яркости. А так в остальном всё то же самое. Базовую теорию операции множеств, я надеюсь, все знают и помнят.
Если у нас есть два множества a и b, мы их можем объединить. Это будет множество точек, которые входят либо в a, либо в b. Мы можем их пересечь пересечением — будет множество точек, которые входят и туда, и сюда. Мы можем построить дополнение к множеству, это будет множество точек, которое не принадлежит множеству a. И можем вычесть одно множество из другого, соответственно это будет множество точек, принадлежащее первому и не принадлежащих второму.
В математической морфологии есть ещё две операции, которые может не столь базовые, но тоже столь понятные. Это центральное отражение множества, здесь под множеством понимаем множество пар х, у. Если у нас есть набор этих пар х, у, тогда центральным отражением будет множество, отражённое относительно начала координат или какого-то другого как бы заданного начала координат.
Параллельный перенос, соответственно, сдвинутое множество на какое-то заданное число z. Если у нас здесь было начало координат, начальное множество а было здесь, потом мы его подвинули куда-то. Но z — это соответственно тоже вектор, то есть мы сдвигаем по х и по у.
Тут отображено центральное отражение, соответственно, если оно было изначально где-то здесь, его можно отразить наверх.
Эти операции используются очень широко при определении базовых операций морфологии математической. Вообще в математической морфологии все операции задаются двумя множествами. Одно множество из себя представляет само изображение, с которым мы хотим что-то сделать, а второе множество — это так называемый структурный элемент, ещё его иногда называют структурообразующий или примитив (structure elements или просто primitive).
Это обычно множество, то есть оно вида такого же, как картинка. Предполагается в бинарной морфологии, что у него тоже есть только белые и чёрные точки. Оно обычно существенно меньшей формы, чем изображение, то есть чаще всего размер там 3, 5, 15 пикселей — не больше.
Вот это некое подобие маски, которое мы обсуждали, когда говорили про пространственные линии фильтрации изображения.
Соответственно вот примеры. Наверно, два наиболее распространённых структурных элемента в виде такого листа и куба. Когда происходит морфологическая обработка, то опять же, как и в случае линейной пространственной фильтрации, у нас вот этот структурный элемент скользит по картинке, и мы смотрим на значения, на изображения, которые оказались под этим структурным элементом. Ну и в зависимости от того, выполняются ли те или иные условия, в результирующем изображении ставится нолик или единичка.
То есть у нас есть на входе наше изображение исходное и структурный элемент, на выходе изначально у нас вся картинка залита чёрным, и мы принимаем решение о том, выставлять какой-либо пиксель в белый цвет или нет — в зависимости от условий, от значений этого структурного элемента и того куска изображения, которое находится под структурным элементом.
Две базовые операции математической морфологии, на которых строится абсолютно всё, — это так называемые delation, erosion. По-русски delation обзывают и дилатацией, и расширением, и наращиванием, кто во что горазд. По сути это, на самом деле, расширение какое-то, такое распухание объекта, которое было изначально на изображении.
Erosion — сужение, это такое похудение объекта, которое было на изображении. И сейчас мы посмотрим, как всё это происходит.
Две ещё не менее важные операции, которые используются, — это размыкание и замыкание (opening/closing), которые строятся как суперпозиция из первых двух базовых. И собственно, что они делают, это тоже мы с вами проговорим.
Эти четыре операции, которые используются наиболее активно. Дальше мы ещё будем рассматривать прочие производные операции, которые в принципе, наверно, тоже используются, но в достаточно ограниченном наборе задач.
Давайте перейдём к рассмотрению этих самых задач. Что есть расширение. Представьте себе, что у вас есть изначальный объект, это вот этот синенький квадратик внутри, и структурный элемент у нас здесь представлен в виде вот этого диска. Для структурного элемента должен обязательно быть задан так называемый начальный элемент, и чаще всего структурный элемент у нас бывает симметричный, и начальный элемент совпадает с его центром.
Основное применение расширения — это когда у нас есть какие-то жидкие объекты и нам нужно построить мосты между кусками и, вообще говоря, одной и той же компоненты связности. Довольно часто применяется при распознавании текста, то есть если у нас шрифт какой-нибудь такой, когда есть явные промежутки в буквах, чтобы эти буквы были распознаваемы. То есть чтобы контур, по крайней мере, был соответственный, то применяют в частности расширение. В чём, наверно, основной минус всех морфологических методов? В том, что нужно каждый раз очень чётко подбирать маску по размеру и по форме, потому что в частности вот это вот очень сильно зависит от размера шрифта, и в том случае, если у нас здесь разрыв, скажем, в три пикселя, он свяжет это дело, если больше, то не свяжет. Либо надо применять несколько последовательных операций расширения, и смотреть, что получается, то есть такая техника.
Операция «эрозия» в некотором смысле обратна расширению. Не в математическом смысле обратна. Эрозией или размыванием ещё называют следующий результат. Здесь у нас опять синенький квадрат, это наше исходное множество. Диск — это структурный элемент и результатом эрозии является такое множество, что если мы помещаем, ну то есть, так что мы передвигаем структурный элемент по нашему исходному множеству и берём только те точки, которые покрываются и изображением, и структурным элементом. То есть, если у нас вдруг структурный элемент начинает вылезать за пределы картинки, то все точки структурного элемента должны помещаться в исходный объект. Здесь центр не играет такой большой роли.
Здесь, соответственно, примеры эрозии. Тот же самый объект, который у нас был с расширением, структурный элемент точно такой же, но здесь исходный объект помечен пунктиром, а результат эрозии закрашен в серый цвет. Тут тоже исходный объект и результатом эрозии будет линия.
Ещё один пример эрозии — эрозия с последующим расширением. Здесь сначала была картинка из крупных квадратиков и мелких точек. Сначала была применена эрозия со структурным элементом, размер которого превышает размер мелких квадратиков, но меньше, чем крупные. И мы видим, что у нас в итоге остались только крупные в виде очень похудевшем. А дальше можно применить расширение, чтобы их нарастить.
На самом деле, такое последовательное применение эрозии и расширения образует две наиболее часто использующие производные операции. Одна из них — размыкание, открытие (opening). Вторая — замыкание (closing). Отличаются они только порядком операции. Размыкание — когда мы сначала производим эрозию, потом — расширение. Замыкание — наоборот.
Собственно, разница в эффектах следующая: в первом случае, когда мы применяем эрозию, у нас сглаживаются контуры объекта как бы изнутри, то есть мы углы объекта округляем. А в том случае, если мы применяем замыкание, тогда у нас тоже сглаживаются углы объекта, но как бы снаружи. То есть получается, что у нас реакцию размыкания можно представить так, как будто бы вы обкатываете шариком контуры объекта, они становятся гладкие. Замыкание — это когда наоборот мы делаем соответственно расширение, а потом — делаем эрозию.
Основные свойства у них следующие. Если мы берём исходный элемент а, структурный элемент b, то результат размыкания всегда будет лежать внутри исходного объекта. А здесь наоборот. Исходный объект будет содержать в себе замыкание. Если у нас есть два множество c и d, c является подмножеством d, то при выборе одного и того же структурного элемента, что результат размыкания, что результат замыкания тоже будет, ну то есть отношение вложенности сохранится. Свойства 2 и 3 у них одинаковые. Ну и повторное применение одной и той же операции (размыкание, размыкание) будет эквивалентно одному размыканию, то же самое с замыканием.
Ещё несколько примеров. Здесь исходное множество а, в качестве множества b и структурного элемента тут снова диск. Пунктиром обозначены контуры исходного объекта. Delation будет выглядеть следующим образом. Если у нас размер структурного элемента больше, чем наша перемычка здесь между этими объектами, то они поделятся на две составляющие. Дальше, если мы после этого поверх этого результата проведём операцию расширения, то результат будет выглядеть следующим образом. Исходный чуть прорастёт, но, тем не менее, перемычка здесь не восстановится. Здесь к исходному множеству сначала применяем операцию расширения, потом операцию эрозии. Здесь у нас перемычка сохраняется, углы тоже сглаживаются и заполняются ещё какие-то такие выпуклости.
Комбинируя все эти операции, можно выполнять различные задачи. Одна из таких классических так называемая Hit-or-Miss Transform, и по-русски её обзывают преобразование «Успех и удача». Когда у вас есть изображение, вы точно знаете, что на этом изображении должен быть объект определённой формы, знаете его размер и хотите найти его координаты. Используется составной структурный элемент. Один для выделения объекта, второй — для выделения фона. То есть мы пытаемся с помощью первого структурного объекта обрисовать объект, который мы ищем, а с помощью второго, как будет выглядеть фон вокруг него. Вот здесь пример. Обозначается он звездочкой в кружочке.
Объясню на рисунке. Допустим, у нас есть исходное множество а, которое состоит из объединения трёх подмножеств x, y, z, которые не связаны друг с другом, и мы хотим найти расположение, где расположен объект х, то есть мы знаем его размер, мы знаем его форму. Тогда в качестве первого структурного элемента мы выбираем сам х, а в качестве второго структурного элемента мы выбираем разницу между небольшой окрестностью вокруг х и самим х, то есть то, как будет выглядеть фон вокруг этого элемента.
Дальше происходит следующее. Мы вычисляем дополнение к исходному множеству а, которое изображено вот здесь вот. Дальше производим эрозию по а с помощью первой маски х. Понятно, что у нас сам х — это тот объект, который был меньше его, удалится полностью, останется только кусочек объекта того кусочка у, который был больше, чем исходная маска. Потом делаем то же самое, только применяем операцию эрозии к дополнению исходного множества, используя маску окрестности, то есть небольшая окрестность минус сам х. У нас получится вот здесь вот такая загогулина и точка.
Теперь, если мы дальше построим пересечение этих двух результатов, то мы получим центр нашего элемента х, который искали. Если несколько таких объектов, то нужно соответственно несколько масок.
Ещё одним морфологическим применением операций является заполнение области. У нас есть контур, и вы хотите залить всё, что внутри. Всё это тоже можно сделать с помощью морфологических операций. Здесь их потребуется сразу несколько. Необходимое условие для этого простейшего алгоритма — знание хотя бы одной точки внутри того элемента, который вы хотите заполнить.
Собственно, тогда операция будет происходить следующим образом. Берём некий структурный элемент, к примеру, вот такой, у нас наше исходное множество, его дополнение, мы изначально строим, соответственно, х0 — это у нас какая-то точка внутри элемента.
То есть вот, на самом деле, этот пиксель. Это точка внутри объекта, который мы хотим залить. Мы строим расширение этой точки с помощью нашего структурного элемента.
Строим и пересекаем с дополнением k каждый раз, на каждом шаге и до тех пор это проделываем, пока у нас xk не перестанет отличаться от xk-1.
Получается залитый объект. В этом случае контур должен быть не тоньше чем половина структурного элемента? Помимо этого, можно решать тоже важную задачу про выделение связных компонент (выделение компонент связности), тоже с помощью последовательного применения морфологических операций. Если кто помнит, на первой лекции я рассказывала про двухпроходный алгоритм выделение связных компонент. На мой взгляд, он более удачен, чем тот, который можно делать с помощью морфологии. Но тем не менее, чтобы были в курсе.
На самом деле, когда обсуждают морфологические операции, есть определённый набор задач, которые, не то чтобы принято, но известно, что можно решить с помощью морфологических штук.
Если мы хотим выделить связный компонент, минус опять в том, что нам нужно снова знать какую-то точку, которая принадлежит связной компоненте. То есть, к примеру у нас есть такая компонента у и есть точка п изначально, которая, мы точно знаем, принадлежит этой компоненте. То мы берём некий структурный элемент. Опять у нас х0 — это самая точка, как в случае с заполнением всё то же самое, только пересекаем мы не с дополнением к исходному множеству, а с самим исходным множеством. В остальном алгоритм точно такой же.
Мы последовательно строим расширение начальной точки и пересекаем результат с исходным множеством. Наивная заливка, да.
Следующая задача, которую можно решать с помощью морфологических операций, построение выпуклой оболочки объекта. К примеру, у нас есть объект такого вида, и мы хотим построить выпуклую оболочку его. Некий многоугольник минимальной площади, описывающий наш объект. Тогда тут нам уже понадобится целых 4 структурных элемента, которые выглядят таким образом. Эти крестики означают, что нам не важно, какое значение будет здесь, нам важно, что здесь вот единичка, вот здесь вот нолик. Здесь нас не особо интересует. Но центр у нас в центре. Вот здесь у нас, к примеру, не важно что тут у нас, обязательно единичка.
Тут суть в том, что они должны быть разные. Можно попробовать, давайте проговорим, что происходит здесь, потом подумаем, почему квадрат не сработает. Квадрат без центра нам говорит о том, что мы обязаны иметь вот здесь вот единички. Результат, соответственно, этого Hit-or-Miss с масками вот такого вида или с единичками обязательными, будет разным. Если мы прогоняем, требуя наличия только одной из граней, или если мы требуем наличия всех.
Я думаю, если выбрать другой набор этих самых структурных элементов, если туда возможно добавить еще диагонали, то тогда мы сможем построить меньшей площади фигуру. Соответственно, что здесь происходит: мы для каждого из этих структурных элементов выполняем этот самый Hit-or-Miss и объединяем его с исходной фигурой.
Следующая вещь, которую можно сделать, построить так называемое утончение объекта. То есть что-то вроде остова, но остовом не являющееся. Я не хочу, чтобы вы запомнили операции, которые можно сделать. Я хочу, чтобы вы из этой лекции запомнили, как выглядят 4 основные операции, это соответственно расширение, эрозия, размыкание, замыкание, и понимали, как они работают. И плюс к этому знали ещё, что можно сделать в принципе с помощью морфологических операций — что можно сделать заливку, можно построить оболочку, можно выделить связные компоненты, и можно сделать то, что я сейчас перечисляю.
В принципе, если немного подумать, то можно понять, как с помощью этого конструктора можно получить вот это вот. То есть цель моя просто сказать, донести до вас то, что можно это сделать с помощью этих операций.
Соответственно, здесь для разных операций количество структурных элементов, которые вам нужно, меняется. То есть здесь их нужно 8 для построения того самого утончения, такого вида, строятся они соответственно следующим образом. Нам нужно взять исходный элемент, построить для каждого из этих b опять Hit-or-Miss и вычесть из того, что было.
Тут показаны последовательно, здесь выполнение с первым с b1, потом с b2, с b3, с b4, с b5, b6, b7, b8. Мы их поменяем до тех пор, пока не будет схождения. Когда у нас фигура перестаёт меняться, мы её вычитаем. Тем самым получаем такую тонкую штуку.
В некотором роде можно делать обратную операцию утолщения, когда у нас есть исходный объект, и мы хотим его нарастить слегка.
На самом деле, утолщение редко применяется. И даже если нужно сделать что-то подобное, чаще всего берут, строят сначала дополнение к объекту, потом утончение полученного дополнения, которое и будет, собственно говоря, утолщением фона. То есть берут сначала дополнение к объекту, берут фон и строят утончение фона. Потом обратно — берут дополнение к получившемуся уточнению, и оно является утолщением. Это оказывается дешевле, чем строить утолщение в том виде, как здесь описано.
Одна из таких достаточно важных понятий при распознавании объектов, это так называемый остов, остов фигуры. Это множество точек, которые равноудалены хотя бы от двух сторон. Можно аналогию привести: если мы одновременно абсолютно со всех сторон подожжём нашу фигуру, то там, где огонь встретится, это и будет как раз остов. Или более математическое описание. Если мы попытаемся вписывать последовательно окружности в нашу фигуру таким образом, чтобы окружность касалась хотя бы двух граничных точек, то множество центров этих окружностей образуют остов.
Здесь вот первичный остов и те точки, которые у нас до контура не дошли, сюда вписывается вот ещё несколько окружностей и получается конечный остов, который выглядит таким образом. Построить его можно тоже с помощью морфологических операций.
Строятся частичные остовы следующим образом. Мы берём множество а и к нему k раз применяем, b — это структурный элемент, совершенно точно, вычитаем b. И вычитаем еще результат этой разности с открытием к b. Можно еще строить так называемое усечение — попытка удалять ненужные концы, ненужные края. Если у нас есть, к примеру, символ, и у нас есть некие мусорные концы, то можно построить усечение фигуры таким образом, чтобы удалить эти ненужные края. Тоже с помощью соответственно различных операций и с различными структурными элементами. Тут их, соответственно, 8 структурных элементов такой формы, то есть b1, b2, b3, b4, ну здесь показано b1, b2 — это то же самое, повернутое на 90 градусов, b3 — на 180, b4 — на 270. И b5, b6, b7, b8 то же самое, только диагональное. Элемент h — это единичный куб.
Соответственно, мы сначала пытаемся обрезать исходную фигуру так, чтобы остались крайние точки, а потом мы её обратно строим в попытке построить всё, но не построить вот эти вот лишние кусочки. Вот, собственно, всё, что я хотела рассказать. Прошу прощения, что лекция была сумбурной.
То, что я хочу, чтобы вы вынесли из этой лекции — это то, что такие операции бывают, чтобы у вас от зубов отскакивало понимание делатации, эрозии, closing, opening. И чтобы вы имели представление о том, что можно сделать с изображениями с помощью комбинаций этих самых штук. Морфологические операции бывают достаточно полезными, когда хочется либо оставить на изображении какие-то определенные формы объектов или удалить их оттуда. То есть на практике я никогда не использовала ни построение остова таким образом, ни построение выпуклых оболочек, а операции открытия и закрытия помогают иногда.
В основе этих методов лежит теория множеств. Предполагается, что любой объект на изображении можно представить тоже в виде множества, либо множества в двумерном пространстве, либо множества в трёхмерном пространстве.
Мы будем сегодня обсуждать методы применительно только к двумерному пространству, так называемую бинарную морфологию. Но это всё достаточно интуитивно расширяется на трёхмерный случай. Как же представляется изображение в случае бинарном?
Опять же бинарный — это значит, у нас есть только чёрные, только белые пиксели. И тогда фиксируем цвет фона. Предположим, фон у нас белый, то тогда объект задаётся набором координат точек, принадлежащим этому объекту, ну и, соответственно, принадлежность множеству. То есть набор пар х, у, которые принадлежат объекту, формируют множество.
Ещё как в школе (я не знаю кто где начал изучать теорию множеств) рисуют множество, чтобы пояснить, что такое объединение пересечений и так далее. Тут самое интуитивное понятие — это как раз те же самые картинки и есть. В трёхмерном случае у нас добавляется ещё одна координата, это значение яркости. А так в остальном всё то же самое. Базовую теорию операции множеств, я надеюсь, все знают и помнят.
Если у нас есть два множества a и b, мы их можем объединить. Это будет множество точек, которые входят либо в a, либо в b. Мы можем их пересечь пересечением — будет множество точек, которые входят и туда, и сюда. Мы можем построить дополнение к множеству, это будет множество точек, которое не принадлежит множеству a. И можем вычесть одно множество из другого, соответственно это будет множество точек, принадлежащее первому и не принадлежащих второму.
В математической морфологии есть ещё две операции, которые может не столь базовые, но тоже столь понятные. Это центральное отражение множества, здесь под множеством понимаем множество пар х, у. Если у нас есть набор этих пар х, у, тогда центральным отражением будет множество, отражённое относительно начала координат или какого-то другого как бы заданного начала координат.
Параллельный перенос, соответственно, сдвинутое множество на какое-то заданное число z. Если у нас здесь было начало координат, начальное множество а было здесь, потом мы его подвинули куда-то. Но z — это соответственно тоже вектор, то есть мы сдвигаем по х и по у.
Тут отображено центральное отражение, соответственно, если оно было изначально где-то здесь, его можно отразить наверх.
Эти операции используются очень широко при определении базовых операций морфологии математической. Вообще в математической морфологии все операции задаются двумя множествами. Одно множество из себя представляет само изображение, с которым мы хотим что-то сделать, а второе множество — это так называемый структурный элемент, ещё его иногда называют структурообразующий или примитив (structure elements или просто primitive).
Это обычно множество, то есть оно вида такого же, как картинка. Предполагается в бинарной морфологии, что у него тоже есть только белые и чёрные точки. Оно обычно существенно меньшей формы, чем изображение, то есть чаще всего размер там 3, 5, 15 пикселей — не больше.
Вот это некое подобие маски, которое мы обсуждали, когда говорили про пространственные линии фильтрации изображения.
Соответственно вот примеры. Наверно, два наиболее распространённых структурных элемента в виде такого листа и куба. Когда происходит морфологическая обработка, то опять же, как и в случае линейной пространственной фильтрации, у нас вот этот структурный элемент скользит по картинке, и мы смотрим на значения, на изображения, которые оказались под этим структурным элементом. Ну и в зависимости от того, выполняются ли те или иные условия, в результирующем изображении ставится нолик или единичка.
То есть у нас есть на входе наше изображение исходное и структурный элемент, на выходе изначально у нас вся картинка залита чёрным, и мы принимаем решение о том, выставлять какой-либо пиксель в белый цвет или нет — в зависимости от условий, от значений этого структурного элемента и того куска изображения, которое находится под структурным элементом.
Две базовые операции математической морфологии, на которых строится абсолютно всё, — это так называемые delation, erosion. По-русски delation обзывают и дилатацией, и расширением, и наращиванием, кто во что горазд. По сути это, на самом деле, расширение какое-то, такое распухание объекта, которое было изначально на изображении.
Erosion — сужение, это такое похудение объекта, которое было на изображении. И сейчас мы посмотрим, как всё это происходит.
Две ещё не менее важные операции, которые используются, — это размыкание и замыкание (opening/closing), которые строятся как суперпозиция из первых двух базовых. И собственно, что они делают, это тоже мы с вами проговорим.
Эти четыре операции, которые используются наиболее активно. Дальше мы ещё будем рассматривать прочие производные операции, которые в принципе, наверно, тоже используются, но в достаточно ограниченном наборе задач.
Давайте перейдём к рассмотрению этих самых задач. Что есть расширение. Представьте себе, что у вас есть изначальный объект, это вот этот синенький квадратик внутри, и структурный элемент у нас здесь представлен в виде вот этого диска. Для структурного элемента должен обязательно быть задан так называемый начальный элемент, и чаще всего структурный элемент у нас бывает симметричный, и начальный элемент совпадает с его центром.
Основное применение расширения — это когда у нас есть какие-то жидкие объекты и нам нужно построить мосты между кусками и, вообще говоря, одной и той же компоненты связности. Довольно часто применяется при распознавании текста, то есть если у нас шрифт какой-нибудь такой, когда есть явные промежутки в буквах, чтобы эти буквы были распознаваемы. То есть чтобы контур, по крайней мере, был соответственный, то применяют в частности расширение. В чём, наверно, основной минус всех морфологических методов? В том, что нужно каждый раз очень чётко подбирать маску по размеру и по форме, потому что в частности вот это вот очень сильно зависит от размера шрифта, и в том случае, если у нас здесь разрыв, скажем, в три пикселя, он свяжет это дело, если больше, то не свяжет. Либо надо применять несколько последовательных операций расширения, и смотреть, что получается, то есть такая техника.
Операция «эрозия» в некотором смысле обратна расширению. Не в математическом смысле обратна. Эрозией или размыванием ещё называют следующий результат. Здесь у нас опять синенький квадрат, это наше исходное множество. Диск — это структурный элемент и результатом эрозии является такое множество, что если мы помещаем, ну то есть, так что мы передвигаем структурный элемент по нашему исходному множеству и берём только те точки, которые покрываются и изображением, и структурным элементом. То есть, если у нас вдруг структурный элемент начинает вылезать за пределы картинки, то все точки структурного элемента должны помещаться в исходный объект. Здесь центр не играет такой большой роли.
Здесь, соответственно, примеры эрозии. Тот же самый объект, который у нас был с расширением, структурный элемент точно такой же, но здесь исходный объект помечен пунктиром, а результат эрозии закрашен в серый цвет. Тут тоже исходный объект и результатом эрозии будет линия.
Ещё один пример эрозии — эрозия с последующим расширением. Здесь сначала была картинка из крупных квадратиков и мелких точек. Сначала была применена эрозия со структурным элементом, размер которого превышает размер мелких квадратиков, но меньше, чем крупные. И мы видим, что у нас в итоге остались только крупные в виде очень похудевшем. А дальше можно применить расширение, чтобы их нарастить.
На самом деле, такое последовательное применение эрозии и расширения образует две наиболее часто использующие производные операции. Одна из них — размыкание, открытие (opening). Вторая — замыкание (closing). Отличаются они только порядком операции. Размыкание — когда мы сначала производим эрозию, потом — расширение. Замыкание — наоборот.
Собственно, разница в эффектах следующая: в первом случае, когда мы применяем эрозию, у нас сглаживаются контуры объекта как бы изнутри, то есть мы углы объекта округляем. А в том случае, если мы применяем замыкание, тогда у нас тоже сглаживаются углы объекта, но как бы снаружи. То есть получается, что у нас реакцию размыкания можно представить так, как будто бы вы обкатываете шариком контуры объекта, они становятся гладкие. Замыкание — это когда наоборот мы делаем соответственно расширение, а потом — делаем эрозию.
Основные свойства у них следующие. Если мы берём исходный элемент а, структурный элемент b, то результат размыкания всегда будет лежать внутри исходного объекта. А здесь наоборот. Исходный объект будет содержать в себе замыкание. Если у нас есть два множество c и d, c является подмножеством d, то при выборе одного и того же структурного элемента, что результат размыкания, что результат замыкания тоже будет, ну то есть отношение вложенности сохранится. Свойства 2 и 3 у них одинаковые. Ну и повторное применение одной и той же операции (размыкание, размыкание) будет эквивалентно одному размыканию, то же самое с замыканием.
Ещё несколько примеров. Здесь исходное множество а, в качестве множества b и структурного элемента тут снова диск. Пунктиром обозначены контуры исходного объекта. Delation будет выглядеть следующим образом. Если у нас размер структурного элемента больше, чем наша перемычка здесь между этими объектами, то они поделятся на две составляющие. Дальше, если мы после этого поверх этого результата проведём операцию расширения, то результат будет выглядеть следующим образом. Исходный чуть прорастёт, но, тем не менее, перемычка здесь не восстановится. Здесь к исходному множеству сначала применяем операцию расширения, потом операцию эрозии. Здесь у нас перемычка сохраняется, углы тоже сглаживаются и заполняются ещё какие-то такие выпуклости.
Комбинируя все эти операции, можно выполнять различные задачи. Одна из таких классических так называемая Hit-or-Miss Transform, и по-русски её обзывают преобразование «Успех и удача». Когда у вас есть изображение, вы точно знаете, что на этом изображении должен быть объект определённой формы, знаете его размер и хотите найти его координаты. Используется составной структурный элемент. Один для выделения объекта, второй — для выделения фона. То есть мы пытаемся с помощью первого структурного объекта обрисовать объект, который мы ищем, а с помощью второго, как будет выглядеть фон вокруг него. Вот здесь пример. Обозначается он звездочкой в кружочке.
Объясню на рисунке. Допустим, у нас есть исходное множество а, которое состоит из объединения трёх подмножеств x, y, z, которые не связаны друг с другом, и мы хотим найти расположение, где расположен объект х, то есть мы знаем его размер, мы знаем его форму. Тогда в качестве первого структурного элемента мы выбираем сам х, а в качестве второго структурного элемента мы выбираем разницу между небольшой окрестностью вокруг х и самим х, то есть то, как будет выглядеть фон вокруг этого элемента.
Дальше происходит следующее. Мы вычисляем дополнение к исходному множеству а, которое изображено вот здесь вот. Дальше производим эрозию по а с помощью первой маски х. Понятно, что у нас сам х — это тот объект, который был меньше его, удалится полностью, останется только кусочек объекта того кусочка у, который был больше, чем исходная маска. Потом делаем то же самое, только применяем операцию эрозии к дополнению исходного множества, используя маску окрестности, то есть небольшая окрестность минус сам х. У нас получится вот здесь вот такая загогулина и точка.
Теперь, если мы дальше построим пересечение этих двух результатов, то мы получим центр нашего элемента х, который искали. Если несколько таких объектов, то нужно соответственно несколько масок.
Ещё одним морфологическим применением операций является заполнение области. У нас есть контур, и вы хотите залить всё, что внутри. Всё это тоже можно сделать с помощью морфологических операций. Здесь их потребуется сразу несколько. Необходимое условие для этого простейшего алгоритма — знание хотя бы одной точки внутри того элемента, который вы хотите заполнить.
Собственно, тогда операция будет происходить следующим образом. Берём некий структурный элемент, к примеру, вот такой, у нас наше исходное множество, его дополнение, мы изначально строим, соответственно, х0 — это у нас какая-то точка внутри элемента.
То есть вот, на самом деле, этот пиксель. Это точка внутри объекта, который мы хотим залить. Мы строим расширение этой точки с помощью нашего структурного элемента.
Строим и пересекаем с дополнением k каждый раз, на каждом шаге и до тех пор это проделываем, пока у нас xk не перестанет отличаться от xk-1.
Получается залитый объект. В этом случае контур должен быть не тоньше чем половина структурного элемента? Помимо этого, можно решать тоже важную задачу про выделение связных компонент (выделение компонент связности), тоже с помощью последовательного применения морфологических операций. Если кто помнит, на первой лекции я рассказывала про двухпроходный алгоритм выделение связных компонент. На мой взгляд, он более удачен, чем тот, который можно делать с помощью морфологии. Но тем не менее, чтобы были в курсе.
На самом деле, когда обсуждают морфологические операции, есть определённый набор задач, которые, не то чтобы принято, но известно, что можно решить с помощью морфологических штук.
Если мы хотим выделить связный компонент, минус опять в том, что нам нужно снова знать какую-то точку, которая принадлежит связной компоненте. То есть, к примеру у нас есть такая компонента у и есть точка п изначально, которая, мы точно знаем, принадлежит этой компоненте. То мы берём некий структурный элемент. Опять у нас х0 — это самая точка, как в случае с заполнением всё то же самое, только пересекаем мы не с дополнением к исходному множеству, а с самим исходным множеством. В остальном алгоритм точно такой же.
Мы последовательно строим расширение начальной точки и пересекаем результат с исходным множеством. Наивная заливка, да.
Следующая задача, которую можно решать с помощью морфологических операций, построение выпуклой оболочки объекта. К примеру, у нас есть объект такого вида, и мы хотим построить выпуклую оболочку его. Некий многоугольник минимальной площади, описывающий наш объект. Тогда тут нам уже понадобится целых 4 структурных элемента, которые выглядят таким образом. Эти крестики означают, что нам не важно, какое значение будет здесь, нам важно, что здесь вот единичка, вот здесь вот нолик. Здесь нас не особо интересует. Но центр у нас в центре. Вот здесь у нас, к примеру, не важно что тут у нас, обязательно единичка.
Тут суть в том, что они должны быть разные. Можно попробовать, давайте проговорим, что происходит здесь, потом подумаем, почему квадрат не сработает. Квадрат без центра нам говорит о том, что мы обязаны иметь вот здесь вот единички. Результат, соответственно, этого Hit-or-Miss с масками вот такого вида или с единичками обязательными, будет разным. Если мы прогоняем, требуя наличия только одной из граней, или если мы требуем наличия всех.
Я думаю, если выбрать другой набор этих самых структурных элементов, если туда возможно добавить еще диагонали, то тогда мы сможем построить меньшей площади фигуру. Соответственно, что здесь происходит: мы для каждого из этих структурных элементов выполняем этот самый Hit-or-Miss и объединяем его с исходной фигурой.
Следующая вещь, которую можно сделать, построить так называемое утончение объекта. То есть что-то вроде остова, но остовом не являющееся. Я не хочу, чтобы вы запомнили операции, которые можно сделать. Я хочу, чтобы вы из этой лекции запомнили, как выглядят 4 основные операции, это соответственно расширение, эрозия, размыкание, замыкание, и понимали, как они работают. И плюс к этому знали ещё, что можно сделать в принципе с помощью морфологических операций — что можно сделать заливку, можно построить оболочку, можно выделить связные компоненты, и можно сделать то, что я сейчас перечисляю.
В принципе, если немного подумать, то можно понять, как с помощью этого конструктора можно получить вот это вот. То есть цель моя просто сказать, донести до вас то, что можно это сделать с помощью этих операций.
Соответственно, здесь для разных операций количество структурных элементов, которые вам нужно, меняется. То есть здесь их нужно 8 для построения того самого утончения, такого вида, строятся они соответственно следующим образом. Нам нужно взять исходный элемент, построить для каждого из этих b опять Hit-or-Miss и вычесть из того, что было.
Тут показаны последовательно, здесь выполнение с первым с b1, потом с b2, с b3, с b4, с b5, b6, b7, b8. Мы их поменяем до тех пор, пока не будет схождения. Когда у нас фигура перестаёт меняться, мы её вычитаем. Тем самым получаем такую тонкую штуку.
В некотором роде можно делать обратную операцию утолщения, когда у нас есть исходный объект, и мы хотим его нарастить слегка.
На самом деле, утолщение редко применяется. И даже если нужно сделать что-то подобное, чаще всего берут, строят сначала дополнение к объекту, потом утончение полученного дополнения, которое и будет, собственно говоря, утолщением фона. То есть берут сначала дополнение к объекту, берут фон и строят утончение фона. Потом обратно — берут дополнение к получившемуся уточнению, и оно является утолщением. Это оказывается дешевле, чем строить утолщение в том виде, как здесь описано.
Одна из таких достаточно важных понятий при распознавании объектов, это так называемый остов, остов фигуры. Это множество точек, которые равноудалены хотя бы от двух сторон. Можно аналогию привести: если мы одновременно абсолютно со всех сторон подожжём нашу фигуру, то там, где огонь встретится, это и будет как раз остов. Или более математическое описание. Если мы попытаемся вписывать последовательно окружности в нашу фигуру таким образом, чтобы окружность касалась хотя бы двух граничных точек, то множество центров этих окружностей образуют остов.
Здесь вот первичный остов и те точки, которые у нас до контура не дошли, сюда вписывается вот ещё несколько окружностей и получается конечный остов, который выглядит таким образом. Построить его можно тоже с помощью морфологических операций.
Строятся частичные остовы следующим образом. Мы берём множество а и к нему k раз применяем, b — это структурный элемент, совершенно точно, вычитаем b. И вычитаем еще результат этой разности с открытием к b. Можно еще строить так называемое усечение — попытка удалять ненужные концы, ненужные края. Если у нас есть, к примеру, символ, и у нас есть некие мусорные концы, то можно построить усечение фигуры таким образом, чтобы удалить эти ненужные края. Тоже с помощью соответственно различных операций и с различными структурными элементами. Тут их, соответственно, 8 структурных элементов такой формы, то есть b1, b2, b3, b4, ну здесь показано b1, b2 — это то же самое, повернутое на 90 градусов, b3 — на 180, b4 — на 270. И b5, b6, b7, b8 то же самое, только диагональное. Элемент h — это единичный куб.
Соответственно, мы сначала пытаемся обрезать исходную фигуру так, чтобы остались крайние точки, а потом мы её обратно строим в попытке построить всё, но не построить вот эти вот лишние кусочки. Вот, собственно, всё, что я хотела рассказать. Прошу прощения, что лекция была сумбурной.
То, что я хочу, чтобы вы вынесли из этой лекции — это то, что такие операции бывают, чтобы у вас от зубов отскакивало понимание делатации, эрозии, closing, opening. И чтобы вы имели представление о том, что можно сделать с изображениями с помощью комбинаций этих самых штук. Морфологические операции бывают достаточно полезными, когда хочется либо оставить на изображении какие-то определенные формы объектов или удалить их оттуда. То есть на практике я никогда не использовала ни построение остова таким образом, ни построение выпуклых оболочек, а операции открытия и закрытия помогают иногда.
