Оператор Айверсона

Оператор Айверсона, в дисциплине компьютерного зрения — оператор обнаружения границ в изображениях. Был разработан Ли Айверсоном[1] и Стивеном Цукером[2]. Описание метода было впервые опубликовано в журнале IEEE Transactions on Pattern Analysis and Machine Intelligence[3] в октябре 1995 года.

Данный метод был призван улучшить действие существующих линейных операторов для распознавания границ путём добавления логических проверок на существование границы. Это позволило уменьшить число ошибочно распознанных линий без потери чувствительности.

Преимущества алгоритма

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

Кроме того, оператор Айверсона позволяет четко разделять между собой 3 вида границ:

Края (англ. step-edges).
Светлые линии (англ. positive contrast lines).
Темные линии (англ. negative contrast lines).

Основы алгоритма

В основе данного алгоритма лежит семейство так называемых логических/линейных операторов (англ. logical/linear operators), которые объединяют в себе теорию линейных операторов и алгебру логики. Условия проверки содержащиеся в данных операторах делятся на 2 различных класса:

Нормальные условия или условия перпендикуляров (англ. normal conditions) — условия, призванные распознать и категоризовать найденную границу.
Тангенциальные условия или условия касательных (англ. tangential conditions) — условия, гарантирующие непрерывность найденной границы.

Общий вид двумерного логического/линейного оператора таков:

\mathbf {\Psi } (x,y)=T(x)\times N_{i}(y)

Где $(x,y)$ определено как локальная ортонормированная система координат. Данный оператор $\Psi$ является декартовым произведением двух одномерных логических/линейных операторов. Оператор $T$ (тангенциальный оператор) выполняет проверку на непрерывность рассматриваемой границы, а оператор $N_{i}$ (нормальный оператор) выполняет проверку на существование границы, где индекс $i\in \{P,N,E\}$ задает тип рассматриваемой границы:

$P$ — для светлых линий
$N$ — для темных линий
$E$ — для краев светлых или темных областей

Оператор $T$ является идентичным для всех трех типов границ.

Нормальные операторы

Нормальный оператор для светлых линий $N_{P}$ имеет следующий вид:

N_{P}=n_{l}^{\prime }\wedge n_{r}^{\prime }\wedge n_{l}^{(3)}\wedge n_{r}^{(3)}

Для темных линий выражения в операторе принимают абсолютно противоположные значения:

N_{N}=-n_{l}^{\prime }\wedge -n_{r}^{\prime }\wedge -n_{l}^{(3)}\wedge -n_{r}^{(3)}

Нормальный оператор для краев имеет вид:

N_{E}=n_{c}^{\prime }\wedge n_{l}^{\prime \prime }\wedge n_{r}^{\prime \prime }\wedge n_{l}^{(4)}\wedge n_{r}^{(4)}

Тангенциальные операторы

Тангенциальный оператор $T$ , проверяющий непрерывность границы имеет вид:

T=t^{-}\wedge t^{+}

Линейные составляющие

Линейными составляющими вышеописанных логических/линейных нормальных операторов являются выражения вида $n_{i}^{k}$ использующие производные Гауссианы, где $k$ указывает порядок соответствующей производной, а $i\in \{l,r,c\}$ указывает на производную слева, производную справа или производную в данной точке.

Линейные составляющие для $N_{P}$ и $N_{N}$ принимают следующие значения:

n_{l}^{\prime }=G_{\sigma }^{\prime }(x+\varepsilon )/2\varepsilon

n_{r}^{\prime }=-G_{\sigma }^{\prime }(x-\varepsilon )/2\varepsilon

n_{l}^{(3)}=-G_{\sigma }^{(3)}(x+\varepsilon )/2\varepsilon

n_{r}^{(3)}=G_{\sigma }^{(3)}(x-\varepsilon )/2\varepsilon

Линейные составляющие для $N_{E}$ :

n_{c}^{\prime }=G_{\sigma }^{\prime }(x)

n_{l}^{\prime \prime }=G_{\sigma }^{\prime \prime }(x+\varepsilon )

n_{r}^{\prime \prime }=-G_{\sigma }^{\prime \prime }(x-\varepsilon )

n_{l}^{(4)}=G_{\sigma }^{(4)}(x+\varepsilon )

n_{r}^{(4)}=-G_{\sigma }^{(4)}(x-\varepsilon )

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

См. также

Примечания

Ссылки

Литература

L. A. Iverson, S. W. Zucker «Logical/Linear Operators for Image Curves», IEEE Trans. on PAMI, October 1995
M.D. Heath, S. Sarkar, T. Sanocki, K.W. Bowyer «A robust visual method for assessing the relative performance of edge-detection algorithms», IEEE Trans. on PAMI, December 1997

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Lee Iverson

[2] Steven W. Zucker

[3] L. A. Iverson, S. W. Zucker «Logical/Linear Operators for Image Curves», IEEE Trans. on PAMI, October 1995