Математическая морфология

Форма (синий цвет) и ее морфологическое расширение (зеленый цвет) и эрозия (желтый цвет) под действием ромбовидного структурирующего элемента.

Математическая морфология ( ММ ) — теория и техника анализа и обработки геометрических структур, основанная на теории множеств , теории решеток , топологии и случайных функциях . ММ чаще всего применяется к цифровым изображениям , но ее также можно применять к графикам , поверхностным сеткам , твердым телам и многим другим пространственным структурам.

Топологические и геометрические понятия непрерывного пространства, такие как размер, форма , выпуклость , связность и геодезическое расстояние , были введены ММ как в непрерывных, так и в дискретных пространствах . ММ также является основой морфологической обработки изображений , которая состоит из набора операторов, преобразующих изображения в соответствии с приведенными выше характеристиками.

Основными морфологическими операторами являются эрозия , расширение , открытие и закрытие .

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

История

Математическая морфология была разработана в 1964 году в результате совместной работы Жоржа Матерона и Жана Серра в Парижской горной школе , Франция . Мэтерон руководил докторской диссертацией Серры, посвященной количественному определению характеристик минералов по тонким поперечным сечениям , и эта работа привела к новому практическому подходу, а также к теоретическим достижениям в области интегральной геометрии и топологии .

В 1968 году Центр математической морфологии был основан Парижской горной школой в Фонтенбло , Франция, под руководством Матерона и Серры.

В течение оставшейся части 1960-х и большей части 1970-х годов ММ имела дело в основном с двоичными изображениями , рассматриваемыми как множества , и создала большое количество бинарных операторов и методов: преобразование «наезд или промах» , расширение , эрозия , открытие , закрытие , гранулометрия. , истончение , скелетонизация , предельная эрозия , условная биссектриса и другие. Также был разработан случайный подход, основанный на новых моделях изображений. Большая часть работ того периода была разработана в Фонтенбло.

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

В 1980-х и 1990-х годах ММ получил более широкое признание, поскольку исследовательские центры в нескольких странах начали применять и исследовать этот метод. ММ начала применяться для решения большого количества задач и приложений обработки изображений, особенно в области нелинейной фильтрации зашумленных изображений.

В 1986 году Серра еще больше обобщил ММ, на этот раз до теоретической основы, основанной на полных решетках . Это обобщение придало теории гибкость, позволив применить ее к гораздо большему числу структур, включая цветные изображения, видео, графики , сетки и т. д. В то же время Матерон и Серра также сформулировали теорию морфологической фильтрации , основанную на новый решетчатый каркас.

В 1990-е и 2000-е годы также наблюдались дальнейшие теоретические достижения, включая концепции связей и выравниваний .

В 1993 году в Барселоне , Испания , состоялся первый Международный симпозиум по математической морфологии (ISMM) . С тех пор ISMM проводятся каждые 2–3 года: Фонтенбло , Франция (1994 г.); Атланта , США (1996 г.); Амстердам , Нидерланды (1998 год); Пало-Альто , Калифорния , США (2000 г.); Сидней , Австралия (2002 г.); Париж , Франция (2005 г.); Рио-де-Жанейро , Бразилия (2007 г.); Гронинген , Нидерланды (2009 г.); Интра ( Вербания ), Италия (2011 г.); Уппсала , Швеция (2013 г.); Рейкьявик , Исландия (2015 г.); и Фонтенбло , Франция (2017 г.).

Рекомендации

• «Введение» Пьера Сойля в (Serra et al. (Eds.) 1994), стр. 1-4.
• «Приложение A: «Центр математической морфологии», обзор» Жана Серры, в (Serra et al. (Eds.) 1994), стр. 369-374.
• «Предисловие» в (Ronse et al. (Eds.) 2005).

Бинарная морфология

В бинарной морфологии изображение рассматривается как подмножество евклидова пространства или целочисленной сетки для некоторого измерения d . ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle \mathbb {Z} ^{d}}$

Структурирующий элемент

Основная идея бинарной морфологии состоит в том, чтобы исследовать изображение с простой заранее определенной формой и сделать выводы о том, насколько эта форма соответствует или не соответствует формам изображения. Этот простой «зонд» называется структурирующим элементом и сам по себе является бинарным изображением (т. е. подмножеством пространства или сетки).

Вот несколько примеров широко используемых элементов структурирования (обозначаются B ):

• Позволять ; B — открытый диск радиуса r с центром в начале координат. ${\displaystyle E=\mathbb {R} ^{2}}$
• Позволять ; B — квадрат 3 × 3, то есть B = {(−1, −1), (−1, 0), (−1, 1), (0, −1), (0, 0), ( 0, 1), (1, −1), (1, 0), (1, 1)}. ${\displaystyle E=\mathbb {Z} ^{2}}$
• Позволять ; B — это «крест», заданный формулой B = {(−1, 0), (0, −1), (0, 0), (0, 1), (1, 0)}. ${\displaystyle E=\mathbb {Z} ^{2}}$

Базовые операторы

Базовыми операциями являются сдвиг-инвариантные ( трансляционно-инвариантные ) операторы, тесно связанные со сложением Минковского .

Пусть E — евклидово пространство или целочисленная сетка, а A — двоичное изображение в E.

Эрозия

Разрушение темно-синего квадрата диском, в результате чего образовался голубой квадрат.

Разрушение бинарного изображения A структурирующим элементом B определяется выражением

${\displaystyle A\ominus B=\{z\in E|B_{z}\subseteq A\},}$

где B _z – сдвиг B на вектор z , т. е. , . ${\displaystyle B_{z}=\{b+z\mid b\in B\}}$ ${\displaystyle \forall z\in E}$

Когда структурирующий элемент B имеет центр (например, B — диск или квадрат), и этот центр расположен в начале координат E , то размывание A по B можно понимать как геометрическое место точек, до которых доходит центр. B , когда B движется внутри A. Например, эрозия квадрата со стороной 10 с центром в начале координат диском радиуса 2, также с центром в начале координат, представляет собой квадрат со стороной 6 с центром в начале координат.

Эрозия A за счет B также определяется выражением . ${\displaystyle A\ominus B=\bigcap _{b\in B}A_{-b}}$

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

Расширение

Расширение темно-синего квадрата диском, в результате чего получился голубой квадрат с закругленными углами.

Расширение A структурирующим элементом B определяется формулой

${\displaystyle A\oplus B=\bigcup _{b\in B}A_{b}.}$

Расширение коммутативно и также определяется выражением . ${\displaystyle A\oplus B=B\oplus A=\bigcup _{a\in A}B_{a}}$

Если B имеет центр в начале координат, как и раньше , то расширение A на B можно понимать как место расположения точек, охватываемых B , когда центр B перемещается внутрь A. В приведенном выше примере расширение квадрата со стороной 10 диском радиуса 2 представляет собой квадрат со стороной 14 с закругленными углами и центром в начале координат. Радиус закругленных углов равен 2.

Расширение также может быть получено через , где B ^s обозначает симметричный B , то есть . ${\displaystyle A\oplus B=\{z\in E\mid (B^{s})_{z}\cap A\neq \varnothing \}}$ ${\displaystyle B^{s}=\{x\in E\mid -x\in B\}}$

Пример применения: расширение – это двойная операция эрозии. Фигуры, нарисованные очень легко, при «расширении» становятся толстыми. Самый простой способ описать это — представить, что тот же факс/текст написан более толстой ручкой.

Открытие

Открытие темно-синего квадрата диском, в результате чего получается голубой квадрат с закругленными углами.

Открытие A с помощью B получается путем размывания A с помощью B с последующим расширением полученного изображения на B :

${\displaystyle A\circ B=(A\ominus B)\oplus B.}$

Открытие также задается , что означает , что это место перемещения структурирующего элемента B внутрь изображения A. В случае квадрата со стороной 10 и диска радиуса 2 в качестве структурирующего элемента проем представляет собой квадрат со стороной 10 с закругленными углами, где радиус угла равен 2. ${\displaystyle A\circ B=\bigcup _{B_{x}\subseteq A}B_{x}}$

Пример применения: предположим, что кто-то написал заметку на ненамокшей бумаге, и письмо выглядит так, как будто по всему его телу растут крошечные волосатые корни. Открытие по существу удаляет внешние крошечные «линии волос» и восстанавливает текст. Побочным эффектом является то, что это закругляет вещи. Острые края начинают исчезать.

Закрытие

Замыкание синей фигуры (объединение двух квадратов) диском, в результате чего происходит объединение синей фигуры и голубых областей.

Замыкание А посредством В достигается расширением А посредством В с последующей эрозией полученной структуры посредством В :

${\displaystyle A\bullet B=(A\oplus B)\ominus B.}$

Замыкание также можно получить с помощью , где X ^c обозначает дополнение X относительно E (т. е. ) . Сказанное выше означает , что замыкание является дополнением локуса трансляций симметричного структурирующего элемента за пределы образа А. ${\displaystyle A\bullet B=(A^{c}\circ B^{s})^{c}}$ ${\displaystyle X^{c}=\{x\in E\mid x\notin X\}}$

Свойства основных операторов

Вот некоторые свойства основных бинарных морфологических операторов (расширение, эрозия, открытие и закрытие):

• Они инвариантны к трансляции .
• Они возрастают , то есть если , то , и и т.д. ${\displaystyle A\subseteq C}$ ${\displaystyle A\oplus B\subseteq C\oplus B}$ ${\displaystyle A\ominus B\subseteq C\ominus B}$
• Расширение коммутативно : . ${\displaystyle A\oplus B=B\oplus A}$
• Если начало координат E принадлежит структурирующему элементу B , то . ${\displaystyle A\ominus B\subseteq A\circ B\subseteq A\subseteq A\bullet B\subseteq A\oplus B}$
• Расширение ассоциативно , т. е. . Более того, эрозия удовлетворяет . ${\displaystyle (A\oplus B)\oplus C=A\oplus (B\oplus C)}$ ${\displaystyle (A\ominus B)\ominus C=A\ominus (B\oplus C)}$
• Эрозия и расширение удовлетворяют двойственности . ${\displaystyle A\oplus B=(A^{c}\ominus B^{s})^{c}}$
• Открытие и закрытие удовлетворяют двойственности . ${\displaystyle A\bullet B=(A^{c}\circ B^{s})^{c}}$
• Расширение является дистрибутивным по объединению множеств.
• Эрозия является распределительной по пересечению множеств.
• Расширение является псевдообратной эрозией, и наоборот, в следующем смысле: тогда и только тогда, когда . ${\displaystyle A\subseteq (C\ominus B)}$ ${\displaystyle (A\oplus B)\subseteq C}$
• Открытие и закрытие идемпотентны .
• Открытие является антиэкстенсивным, т.е. , тогда как закрытие является экстенсивным , т.е. ${\displaystyle A\circ B\subseteq A}$ ${\displaystyle A\subseteq A\bullet B}$

Другие операторы и инструменты

• Преобразование «попадание или промах»
• Обрезка преобразования
• Морфологический скелет
• Фильтрация по реконструкции
• Предельные эрозии и условные биссектрисы
• Гранулометрия
• Функции геодезического расстояния

Морфология оттенков серого

Водораздел градиента изображения сердца

В морфологии оттенков серого изображения — это функции , отображающие евклидово пространство или сетку E в , где — набор действительных чисел , — элемент, больший любого действительного числа, и — элемент, меньший любого действительного числа. ${\displaystyle \mathbb {R} \cup \{\infty ,-\infty \}}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \infty }$ ${\displaystyle -\infty }$

Элементы структурирования в оттенках серого также являются функциями того же формата, называемыми «функциями структурирования».

Обозначая изображение через f ( x ), функцию структурирования через b ( x ) и поддержку b через B , расширение шкалы серого f на b определяется выражением

${\displaystyle (f\oplus b)(x)=\sup _{y\in B}[f(y)+b(x-y)],}$

где «sup» обозначает супремум .

Аналогично, эрозия f на b определяется выражением

${\displaystyle (f\ominus b)(x)=\inf _{y\in B}[f(y)-b(y-x)],}$

где «inf» обозначает нижнюю границу .

Как и в бинарной морфологии, открытие и закрытие задаются соответственно формулами

${\displaystyle f\circ b=(f\ominus b)\oplus b,}$

${\displaystyle f\bullet b=(f\oplus b)\ominus b.}$

Функции плоского структурирования

В морфологических приложениях часто используются плоские элементы структурирования. Плоские функции структурирования — это функции b ( x ) в виде

${\displaystyle b(x)={\begin{cases}0,&x\in B,\\-\infty &{\text{otherwise}},\end{cases}}}$

где . ${\displaystyle B\subseteq E}$

В этом случае расширение и эрозия значительно упрощаются и определяются соответственно формулами

${\displaystyle (f\oplus b)(x)=\sup _{z\in B^{s}}f(x+z),}$

${\displaystyle (f\ominus b)(x)=\inf _{z\in B}f(x+z).}$

В ограниченном дискретном случае ( E — сетка, а B ограничена) операторы супремума и инфимума можно заменить операторами максимума и минимума . Таким образом, расширение и эрозия являются частными случаями фильтров статистики порядка , при этом расширение возвращает максимальное значение в пределах скользящего окна (симметрично поддержке функции структурирования B ), а эрозия возвращает минимальное значение в скользящем окне B .

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

Другие операторы и инструменты

• Морфологические градиенты
• Преобразование в цилиндре
• Алгоритм водораздела

Комбинируя эти операторы, можно получить алгоритмы для многих задач обработки изображений, таких как обнаружение признаков , сегментация изображения , повышение резкости изображения , фильтрация изображения и классификация . В этом направлении следует также изучить непрерывную морфологию ^[1].

Математическая морфология на полных решетках

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

Присоединения (дилатация и эрозия)

Позвольте быть полной решеткой с нижней и верхней границей, обозначенными и соответственно. Его вселенная и наименьший элемент обозначаются буквами U и соответственно. Более того, пусть – совокупность элементов из L . ${\displaystyle (L,\leq )}$ ${\displaystyle \wedge }$ ${\displaystyle \vee }$ ${\displaystyle \emptyset }$ ${\displaystyle \{X_{i}\}}$

Расширение — это любой оператор , который распределяет по супремуму и сохраняет наименьший элемент. Т.е.: ${\displaystyle \delta \colon L\rightarrow L}$

• ${\displaystyle \bigvee _{i}\delta (X_{i})=\delta \left(\bigvee _{i}X_{i}\right)}$,
• ${\displaystyle \delta (\emptyset )=\emptyset }$.

Эрозия — это любой оператор , который распределяет информацию по нижней грани и сохраняет вселенную. Т.е.: ${\displaystyle \varepsilon \colon L\rightarrow L}$

• ${\displaystyle \bigwedge _{i}\varepsilon (X_{i})=\varepsilon \left(\bigwedge _{i}X_{i}\right)}$,
• ${\displaystyle \varepsilon (U)=U}$.

Расширения и эрозии образуют связи Галуа . То есть для каждого расширения существует одна и только одна эрозия, удовлетворяющая условию ${\displaystyle \delta }$ ${\displaystyle \varepsilon }$

${\displaystyle X\leq \varepsilon (Y)\Leftrightarrow \delta (X)\leq Y}$

для всех . ${\displaystyle X,Y\in L}$

Аналогично, для каждой эрозии существует одно и только одно расширение, удовлетворяющее указанной выше связи.

Более того, если два оператора удовлетворяют связи, то должно быть расширение и эрозия. ${\displaystyle \delta }$ ${\displaystyle \varepsilon }$

Пары эрозий и расширений, удовлетворяющие вышеуказанной связи, называются «примыканиями», а эрозия называется присоединенной эрозией расширения, и наоборот.

Открытие и закрытие

Для каждого присоединения морфологическое открытие и морфологическое закрытие определяются следующим образом: ${\displaystyle (\varepsilon ,\delta )}$ ${\displaystyle \gamma \colon L\to L}$ ${\displaystyle \phi \colon L\to L}$

${\displaystyle \gamma =\delta \varepsilon ,}$

${\displaystyle \phi =\varepsilon \delta .}$

Морфологическое открытие и закрытие представляют собой частные случаи алгебраического открытия (или просто открытия) и алгебраического закрытия (или просто закрытия). Алгебраические открытия — это операторы в L , которые являются идемпотентными, возрастающими и антиэкстенсивными. Алгебраические замыкания — это операторы в L , которые являются идемпотентными, возрастающими и экстенсивными.

Частные случаи

Бинарная морфология — это частный случай морфологии решетки, где L — степенное множество E (евклидово пространство или сетка), то есть L — множество всех подмножеств E и включение множества . В этом случае нижняя грань — это пересечение , а верхняя грань — объединение . ${\displaystyle \leq }$

Точно так же морфология в оттенках серого - это еще один частный случай, где L - это набор функций, отображающих E в , а , и - это точечный порядок, верхняя граница и нижняя грань соответственно. То есть, если f и g являются функциями из L , то тогда и только тогда, когда ; нижняя грань определяется ; и супремум определяется выражением . ${\displaystyle \mathbb {R} \cup \{\infty ,-\infty \}}$ ${\displaystyle \leq }$ ${\displaystyle \vee }$ ${\displaystyle \wedge }$ ${\displaystyle f\leq g}$ ${\displaystyle f(x)\leq g(x),\forall x\in E}$ ${\displaystyle f\wedge g}$ ${\displaystyle (f\wedge g)(x)=f(x)\wedge g(x)}$ ${\displaystyle f\vee g}$ ${\displaystyle (f\vee g)(x)=f(x)\vee g(x)}$

См. также

• Преобразование H-максимумов

Примечания

1. Г. Сапиро, Р. Киммел, Д. Шакед, Б. Кимия и А. М. Брукштейн. Реализация морфологии непрерывного масштаба посредством эволюции кривой. Распознавание образов, 26(9):1363–1372, 1993.

Рекомендации

• Анализ изображений и математическая морфология Жана Серры, ISBN  0-12-637240-3 (1982)
• Анализ изображений и математическая морфология, Том 2: Теоретические достижения Жана Серры, ISBN 0-12-637241-1 (1988) 
• Введение в морфологическую обработку изображений Эдварда Р. Догерти, ISBN 0-8194-0845-X (1992) 
• Морфологический анализ изображений; Принципы и приложения Пьера Сойля, ISBN 3-540-65671-5 (1999 г.), 2-е издание (2003 г.) 
• Математическая морфология и ее применение к обработке сигналов , Дж. Серра и Ф. Салембье (ред.), материалы 1-го Международного семинара по математической морфологии и ее приложениям к обработке сигналов (ISMM'93), ISBN 84-7653-271-7 (1993) 
• Математическая морфология и ее приложения к обработке изображений , Дж. Серра и П. Сойль (ред.), труды 2-го международного симпозиума по математической морфологии (ISMM'94), ISBN 0-7923-3093-5 (1994). 
• Математическая морфология и ее приложения к обработке изображений и сигналов , Хенк Дж. А. Хейманс и Йос Б. Т. Рёрдинк (редакторы), материалы 4-го международного симпозиума по математической морфологии (ISMM'98), ISBN 0-7923-5133-9 (1998) 
• Математическая морфология: 40 лет спустя , Кристиан Ронс, Лоран Наджман и Этьен Десенсьер (ред.), ISBN 1-4020-3442-3 (2005) 
• Математическая морфология и ее приложения к обработке сигналов и изображений , Джеральд Дж. Ф. Банон, Джуниор Баррера, Улиссес М. Брага-Нето (ред.), материалы 8-го международного симпозиума по математической морфологии (ISMM'07), ISBN 978-85-17 -00032-4 (2007) 
• Математическая морфология: от теории к приложениям , Лоран Наджман и Хьюг Талбот (редакторы). ИСТЭ-Уайли. ISBN 978-1-84821-215-2 . (520 стр.), июнь 2010 г. 

Внешние ссылки

• Онлайн-курс Жана Серры по математической морфологии (на английском, французском и испанском языках)
• Центр математической морфологии Парижской горной школы
• История математической морфологии, Жорж Матерон и Жан Серра
• Morphology Digest, информационный бюллетень по математической морфологии, Пьер Сойль
• Лекции по обработке изображений: сборник из 18 лекций в формате pdf из Университета Вандербильта. Лекции 16–18 посвящены математической морфологии Алана Питерса.
• Математическая морфология; из лекций по компьютерному зрению Робин Оуэнс
• SMIL — простая (но эффективная) библиотека морфологических изображений (из Парижской горной школы)
• Бесплатная библиотека обработки изображений, оптимизированная SIMD
• Демонстрация Java-апплета
• ФИЛЬТРЫ: бесплатная библиотека обработки изображений с открытым исходным кодом.
• Быстрые морфологические эрозии, расширения, открытия и закрытия
• Морфологический анализ нейронов с использованием Matlab