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

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

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

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

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

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

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

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

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

1. Нормальные условия или условия перпендикуляров (англ. normal conditions) — условия, призванные распознать и категоризовать найденную границу.
2. Тангенциальные условия или условия касательных (англ. 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» Архивная копия от 29 апреля 2006 на Wayback Machine
• M.D. Heath, S. Sarkar, T. Sanocki, K.W. Bowyer «A robust visual method for assessing the relative performance of edge-detection algorithms» Архивная копия от 5 марта 2016 на Wayback Machine
• Pattern Analysis and Machine Intelligence, IEEE Transactions on Архивная копия от 18 января 2012 на Wayback Machine
• Lee Iverson Архивная копия от 14 декабря 2009 на Wayback Machine
• Steven W. Zucker Архивная копия от 25 января 2012 на Wayback Machine

Литература

• 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