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

Материал из Техническое зрение
Перейти к: навигация, поиск

Содержание

Морфологический дескриптор

Введем понятие $\textit{морфологического дескриптора}$ $$ \mathbf{d}(A,\mathbf{E})=\langle n,d(A,E_{1}),{\ldots},d(A,E_{n}) \rangle, $$ где $\mathbf{E}=\langle E_{1},{\ldots},E_{n} \rangle$ - базис морфологического разложения; $n=\rm{dim}(\mathbf{E})$ - размерность базиса $\textbf{E}$, называемая также $\textit{размерностью дескриптора}$; $d(A,E_{i})$ - $\textit{дескриптор элемента}$ разложения $E_{i}$. $\textit{Объемом дескриптора}$ назовем $\nu (\mathbf{d})$ - количество памяти (бит), необходимое для хранения данного дескриптора $\textbf{d}$. Как правило, объем дескриптора пропорционален размерности базиса.

Пусть дан некоторый полный базис разложения $\textbf{X}$ размерности $n$. Тогда для любого образа $A\in \Omega $ его дескриптор $\textbf{d}(A,\textbf{X})$ будем называть $\textit{базовым полным дескриптором}$. Любой $\textit{подбазис}$ $\textbf{Y}=\langle Y_{1},{\ldots},Y_{m} \rangle: \textbf{Y}\subseteq \textbf{X}$, $\dim(\bf{Y})\le \dim(\bf{X})$ соответственно определяет $\textit{субдескриптор}$ $\textbf{d}(A,\textbf{Y})$. Определим $\textit{критерий качества сегментации}$ в виде функционала

$$ \textrm{Ф}(A,\mathbf{Y}) = J(A, \mathrm{Pr}(A,\mathbf{Y})) + \alpha \nu (\mathbf{d}(A,\mathbf{Y})) \to \min(\mathbf{Y}:\textbf{Y}\subseteq \textbf{X}), $$

где $J$ - $\textit{функционал качества проекции}$; $\alpha $ - настроечный параметр, определяющий компромисс между требованиями минимизации объема дескриптора $\nu (\mathbf{d}(A,\mathbf{Y}))$ и искажений $J$, вносимых в $\textit{сегментированное изображение}$ Pr($A,\mathbf{Y}$) по сравнению с исходным образом $A$. $\textit{Процедура оптимальной сегментации}$ $S$ определяет

$$ \mathbf{Y}=S(A,\mathbf{X}): \textbf{Y}\subseteq \textbf{X}, \quad \textrm{Ф}(A,\bf{Y})\to \min(\bf{Y}). $$

При этом процедура сегментации $S$ может быть представлена в виде $\textit{матрицы перехода к новому базису}$ $\mathbf{S}(A)$ размерности $m\times n$:

$$ \mathbf{Y }= \textbf{S}(A) \times \textbf{X}, $$

где $n$ и $m$ - размерности базиса $\textbf{X}$ и подбазиса $\textbf{Y}$ соответственно.

Сегментация без потери информации

В работе $[66]$ предложена схема конструирования неискажающих морфологических операторов сегментации $\textit{без потери информации}$ на основе эквивалентных преобразований базисов путем $\textit{исключения}$ примитивов с нулевыми коэффициентами разложения и $\textit{группировки}$ примитивов с одинаковыми коэффициентами разложения.

Для описанных эквивалентных преобразований матрица перехода $\mathbf{S}(A)$ состоит из нулей и единиц. С формальной точки зрения, последовательно применяя эквивалентные преобразования, можно исключить все элементы разложения с нулевыми коэффициентами, сгруппировать все примитивы с одинаковыми весами и, таким образом, построить $\textit{неискажающий проектор}$ с минимальным объемом (минимальной размерностью) дескриптора. Однако не все элементы с одинаковыми весами допустимо и целесообразно объединять. В каждой конкретной морфологии существуют свои ограничения на допустимое объединение образующих. Эти ограничения можно описать как предикат $\textit{правил перехода}$ $p(\mathbf{X}\to \mathbf{Y})=p(\mathbf{S})$, значения которого не зависят от сегментируемого образа $A$ и определяются априори, исходя из семантики данного конкретного разложения. Рассмотрим несколько примеров.

Пример 1

Разложения по системам ортогональных функций (Фурье, вейвлет). Здесь условием допустимого объединения образующих является то, что получаемые образующие нового базиса также должны быть ортогональны. Поскольку $\mathbf{S}(A)$ состоит из $0$ и $1$, соответствующее правило перехода гласит, что в каждом столбце матрицы перехода может быть только одна единица.$\quad\diamondsuit $

Пример 2

Пытьевские "формы". В качестве базиса исходного полного разложения может использоваться $\textit{тривиальное пиксельное разбиение}$ $$ f(x,y)= \sum_{ij}a_{ij}\phi (i,j,x,y), $$ где $\phi (i,j,x,y)=\{1:x=i,\;y=j;~0:x\ne i,\;y\ne j\}$ - $\textit{индикаторная функция пиксела}$; $\langle x,y \rangle$ - положение пиксела; $a_{ij }=f(i,j)$ - значение цифрового изображения в точке $\langle i,j \rangle$. Соответствующее формальное правило перехода для ортогональных разложений определено выше и предписывает, что в каждом столбце матрицы перехода должна быть ровно одна единица. Однако помимо формальных ограничений в данной задаче важны и семантические, а именно, получающиеся в результате слияния пикселов области должны быть $\textit{связными}$. С учетом этого две связные области должны считаться $\textit{разными}$ $\textit{примитивами}$, даже если на данном изображении они заполнены пикселами одинаковой интенсивности. В качестве обоснования такого подхода можно рассмотреть значение соответствующего объема дескриптора, описывающего связные области. Наиболее экономным способом описания бинарных областей является описание в виде $\textit{контуров}$ (списков контурных точек). Объем контурного дескриптора пропорционален не площади области, а ее периметру. Общий периметр двух областей меньше суммы их периметров на длину общей границы. Таким образом, целесообразно объединять все смежные области равной интенсивности в одну связную область. Если же две области равной интенсивности не имеют общей границы, то при их объединении суммарный периметр не уменьшится, следовательно, такое объединение нецелесообразно. Таким образом, оказывается, что интуитивно введенное Пытьевым понятие $\textit{"формы' как множества связных областей равной яркости}$ есть на самом деле регулярное решение задачи оптимальной морфологической сегментации без потерь (рис. 10).$\quad\diamondsuit $

Пример 3

Бинарная ММ Серра. В качестве исходного базиса полного разложения рассмотрим множество структурирующих элементов одинаковой формы $B(x,y,r)$ всех возможных положений $\langle x,y \rangle\in {R}^{2}$ и размеров $r\in [0,+\infty )$. Рассмотрим задачу построения неискажающего дескриптора минимального объема $\mathbf{Y}_{B}$ на базе исходного полного разложения $\mathbf{X}_{B}$. С формальной точки зрения все элементы разложения с ненулевыми коэффициентами можно было бы объединить в единый примитив, поскольку значения этих коэффициентов одинаковы и равны единице. Однако, как и в примере $2$, не все объединения дают выигрыш в объеме дескриптора. В данном случае выигрыш появляется, когда $\textit{большие примитивы разложения поглощают меньшие, которые целиком в них входят}$. В самом деле, объем дескриптора (записи типа $\langle x,y,r \rangle$) будет одинаков для элемента $B(x,y,r)$ любого масштаба. В тоже время, любой элемент $B(x,y,R)$ может быть представлен в виде

$$ B(x,y,R)=\cup _{\langle i,j,r\rangle}\{B(i,j,r): B(i,j,r)\subseteq B(x,y,R), r\le R\}, $$

и поскольку монотонные проекторы сохраняют включение, проекция любого образа $A$ на множество образующих $\{B(i,j,r): B(i,j,r)\subseteq B(x,y,R)$, $r\le R\}$ всегда равна Pr$(A,B(x,y,R))$, если Pr$(A,B(x,y,R))\ne \emptyset$. Формальное правило перехода в данном случае имеет следующий вид: единицы в матрице перехода $\mathbf{S}(A)$ могут стоять на пересечении строки, соответствующей $B(x,y,R)$, и столбца, соответствующего $B(i,j,r)$, если $B(i,j,r)\subseteq B(x,y,R)$, $r\le R$. В частности, для дисковых структурирующих элементов $D(x,y,r)$ решение задачи оптимальной сегментации на базе ММ Серра также автоматически порождает описанную выше процедуру $\textit{скелетизации}$, или $\textit{построения морфологического остова}$ двумерных бинарных образов (рис. 10).$\quad\diamondsuit $

6-3-10.jpg

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

Сегментация с потерей информации

Предложена также схема конструирования оптимальных морфологических операторов сегментации $\textit{с потерей информации}$. Доказана проективность получаемых операторов сегментации для двух основных классов операторов морфологической сегментации: $\textit{проекторов минимального расстояния}$ (минимальной нормы отклонения) и $\textit{монотонных проекторов}$ (в более общем виде эти утверждения приводятся ниже для общего случая критериальных проективных операторов).

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

Заметим, что основным ограничением рассмотренных в данном разделе методов и подходов является то, что рассматриваемый в рамках проективной морфологии разложений класс $\textit{структурных моделей с однородными связями}$ позволяет задавать лишь состав входящих в модель элементов и связь между образующими и образом в целом, но не учитывает связи образующих элементов между собой. Это ограничение является принципиальным, так как модели более общего вида, описываемые произвольными гиперграфами, не могут быть однозначно охарактеризованы регулярными массивами или векторами признаков. Для работы с такими моделями необходимо использовать обобщенный морфологический формализм, рассматриваемый в следующем разделе.

Личные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты