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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

Ссылки

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

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

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

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

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

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

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

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

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

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

Эрозия

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

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

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

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

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

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

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

Расширение

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

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

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

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

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

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

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

Открытие

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

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

$A\circ B=(A\ominus B)\oplus B.$

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

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

Закрытие

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

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

$A\bullet B=(A\oplus B)\ominus B.$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$f\circ b=(f\ominus b)\oplus b,$

$f\bullet b=(f\oplus b)\ominus b.$

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

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

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

где $B\subseteq E$.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эрозия – это любой оператор $\varepsilon \colon L\rightarrow L$ которая распределяется по нижней грани и сохраняет вселенную. Т.е.:

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

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

$X\leq \varepsilon (Y)\Leftrightarrow \delta (X)\leq Y$

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

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

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

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

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

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

$\gamma =\delta \varepsilon ,$

$\phi =\varepsilon \delta .$

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

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

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

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

См. также

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

Ссылки

• Анализ изображений и математическая морфология , Жан Серра, 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