Файл для печти в MS Word   (  task_w.zip  - с картинками  )
                                                 (  task_wo.zip - без картинок ) 
 

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

Смысл операций морфологии

Мы будем рассматривать морфологию двоичных изображений. Двоичное изображение представляется в виде упорядоченного набора (упорядоченного множества) черно-былых точек (пикселей), или 0 и 1. Под областью (region) изображения обычно понимается некоторое подмножество 1-чек изображения. Каждая операция двоичной морфологии является некоторым преобразованием этого множества. В качестве исходных данных принимаются двоичное изображение B и некоторый структурный элемент S. Результатом операции также является двоичное изображение.

Структурный элемент суть тоже некоторое двоичное изображение (геометрическая форма – shape). Он может быть произвольного размера и произвольной структуры. Чаше всего используются симметричные элементы, как прямоугольник фиксированного размере (BOX(l,w)), или круг некоторого диаметра (DISK (d)). В каждом элементе выделяется особая точка, называемая начальной (origin). Она может быть расположена в любом месте элемента, хотя в симметричных это обычно центральный пиксель.

В начале результирующая поверхность заполняется 0, образуя полностью черное изображение. Затем осуществляется зондирование (probing) или сканирование исходного изображения пиксель за пикселем структурным элементом. Для зондирования каждого пикселя на изображение “накладывается” структурный элемент так, чтобы совместились зондируемая и начальные точки. Затем проверяется некоторое условие на соответствие пикселей структурного элемента и точек изображения “под ним”. Если условие выполняется – то на результирующем изображении в соответствующем месте ставится 1 (в некоторых случаях будет добавляться не один единичный пиксель, а все единички из структурного элемента).

По рассмотренной выше схеме выполняются базисные (basic) операции. Такими операциями являются расширение (dilation) и сужение (erosion). Производные операции – это некоторая комбинация базисных, выполняемых последовательно. Основными из них являются открытие (opening) и закрытие (closing).
 

Базовые операции

Def: Перенос (translation) множества пикселей X на вектор t определяется как

Перенос t может быть определен как упорядоченная пара чисел , где - движение вдоль оси х, а - движение вдоль оси y.

Def: Расширение двоичного изображения B на структурный элемент S записывается в виде  и определяется как:

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

Def: Сужение двоичного изображения B на структурный элемент S записывается как и определяется как:

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

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

Операция закрытия “закрывает” небольшие внутренние “дырки” в изображении, и убирает углубления (bays) по краям области. 

Def: Открытие двоичного B на структурный элемент S записывается как и определяется как:

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

Над парой двоичных изображений также могут применяться обычные теоретико-множественные логические операции как AND, OR, NOT, MINUS.
 
 

Скелетонизация

Для распознавания объектов часто необходимо изучить его форму. Ее удобно представлять в виде некоторого “скелета” (по другому – медианы, или срединной оси формы). Выяснилось, что скомбинировав несколько операций математической морфологии можно получить производную, позволяющую выделять из объекта его “скелет”, и она, соответственно, получила название “скелетонизации”. 

n-м элементом скелета S изображения X по структурному элементу Q называется

где N- max(n: X-nQ != /0), 

!= - не равно

/0 – пустое множество

/ - теоретико-множественно вычитание

( X*nQ, где *- знак операции, обозначает последовательное применение операции к изображению n раз) 

Тогда частичным скелетом S(k) изображения X по структурному элементу Q назовем объединение 

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

Если k равно 0, то , и реконструкция называется точной. Если , то мы получаем частичную реконструкцию, т.е. открытие (сглаживание) X на kQ. Варьируя k мы можем получать различные степени сглаживания исходного изображения X.

На рисунке:

(a) - Сужения

(b) - Открытия расширения 

(с) – n-ые элементы скелета

(d) – расширенные элементы скелета 

(e) – частичные объединения элементов скелета 

(f) – частичные расширения

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

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

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

Условное расширение

Def: Условное расширение двоичного изображения С на структурный элемент S по исходному двоичному изображению B определяется как:

Условное расширение применяется тогда, когда после сужения изображения необходимо его расширить только теми пикселями, которые входили в первоначальное изображе
 

                                                          Задание

Цель задания:

        Решить некоторую задачу (выделение скелета - скелетонизацию) средствами математической морфологии. Таким образом, задание можно подразбить на два:
       Задание №1 Реализовать базовые операции математической морфологии (расширение, сужение, открытие, закрытие) (5 баллов)
       Задание №2 Реализовать операцию скелетонизации, и расширение его по тому же структурному элементу до исходного изображения. (+ 5 баллов)

         Удобство интерфейса и красота вывода данных учитываются. 

Интерфейс:

     Интерфейс программы должен допускать ввод изображения и применение к нему последовательности операций. На экране должно быть два изображения - исходное и полученное. Если исходное изображение не вводится, то исходным для операции cтановится ранее полученное изображение. Должна быть возможность ввода  произвольного структурного элемента.  По умолчанию структурный элемент - квадрат
    3*3, заполненный единичками с начальной точкой в центре квадрата.
 

Оформление задания:

            См. предыдущие задание и faq.