Русская Википедия:Оператор Айверсона
Оператор Айверсона, в дисциплине компьютерного зрения — оператор обнаружения границ в изображениях. Был разработан Ли Айверсоном[1] и Стивеном Цукером[2]. Описание метода было впервые опубликовано в журнале IEEE Transactions on Pattern Analysis and Machine Intelligence[3] в октябре 1995 года.
Данный метод был призван улучшить действие существующих линейных операторов для распознавания границ путём добавления логических проверок на существование границы. Это позволило уменьшить число ошибочно распознанных линий без потери чувствительности.
Преимущества алгоритма
Основным преимуществом алгоритма является значительное уменьшение количества ошибочно положительных откликов (распознавания несуществующих границ) по сравнению с ранее существующими алгоритмами.
Кроме того, оператор Айверсона позволяет четко разделять между собой 3 вида границ:
- Края (Шаблон:Lang-en).
- Светлые линии (Шаблон:Lang-en).
- Темные линии (Шаблон:Lang-en).
Основы алгоритма
В основе данного алгоритма лежит семейство так называемых логических/линейных операторов (Шаблон:Lang-en), которые объединяют в себе теорию линейных операторов и алгебру логики. Условия проверки содержащиеся в данных операторах делятся на 2 различных класса:
- Нормальные условия или условия перпендикуляров (Шаблон:Lang-en) — условия, призванные распознать и категоризовать найденную границу.
- Тангенциальные условия или условия касательных (Шаблон:Lang-en) — условия, гарантирующие непрерывность найденной границы.
Общий вид двумерного логического/линейного оператора таков:
- <math>\mathbf{\Psi}(x,y) = T(x) \times N_i(y) </math>
Где <math>(x,y)</math> определено как локальная ортонормированная система координат. Данный оператор <math>\Psi</math> является декартовым произведением двух одномерных логических/линейных операторов. Оператор <math>T</math> (тангенциальный оператор) выполняет проверку на непрерывность рассматриваемой границы, а оператор <math>N_i</math> (нормальный оператор) выполняет проверку на существование границы, где индекс <math>i\in\{P,N,E\}</math> задает тип рассматриваемой границы:
- <math>P</math> — для светлых линий
- <math>N</math> — для темных линий
- <math>E</math> — для краев светлых или темных областей
Оператор <math>T</math> является идентичным для всех трех типов границ.
Нормальные операторы
Нормальный оператор для светлых линий <math>N_P</math> имеет следующий вид:
- <math>N_P = n_l^{\prime}\wedge n_r^{\prime}\wedge n_l^{(3)}\wedge n_r^{(3)}</math>
Для темных линий выражения в операторе принимают абсолютно противоположные значения:
- <math>N_N = -n_l^{\prime}\wedge -n_r^{\prime}\wedge -n_l^{(3)}\wedge -n_r^{(3)}</math>
Нормальный оператор для краев имеет вид:
- <math>N_E = n_c^{\prime}\wedge n_l^{\prime \prime}\wedge n_r^{\prime \prime}\wedge n_l^{(4)}\wedge n_r^{(4)}</math>
Тангенциальные операторы
Тангенциальный оператор <math>T</math>, проверяющий непрерывность границы имеет вид:
- <math>T= t^- \wedge t^+</math>
Линейные составляющие
Линейными составляющими вышеописанных логических/линейных нормальных операторов являются выражения вида <math>n_i^k</math> использующие производные Гауссианы, где <math>k</math> указывает порядок соответствующей производной, а <math>i\in\{l,r,c\}</math> указывает на производную слева, производную справа или производную в данной точке.
Линейные составляющие для <math>N_P</math> и <math>N_N</math> принимают следующие значения:
- <math> n_l^{\prime} = G_{\sigma}^{\prime}(x+\varepsilon)/2\varepsilon </math>
- <math> n_r^{\prime} = -G_{\sigma}^{\prime}(x-\varepsilon)/2\varepsilon </math>
- <math> n_l^{(3)} = -G_{\sigma}^{(3)}(x+\varepsilon)/2\varepsilon </math>
- <math> n_r^{(3)} = G_{\sigma}^{(3)}(x-\varepsilon)/2\varepsilon </math>
Линейные составляющие для <math>N_E</math>:
- <math> n_c^{\prime} = G_{\sigma}^{\prime}(x) </math>
- <math> n_l^{\prime \prime} = G_{\sigma}^{\prime \prime}(x+\varepsilon) </math>
- <math> n_r^{\prime \prime} = -G_{\sigma}^{\prime \prime}(x-\varepsilon)</math>
- <math> n_l^{(4)} = G_{\sigma}^{(4)}(x+\varepsilon) </math>
- <math> n_r^{(4)} = -G_{\sigma}^{(4)}(x-\varepsilon)</math>
С помощью операции свертки линейных составляющих операторов с функцией входного сигнала с изображения, алгоритм Айверсона позволяет проверять локальные условия существования границ на определенном участке изображения.
См. также
- Оператор Кэнни
- Оператор Ротуэлла
- Оператор Собеля
- Выделение границ
- Компьютерное зрение
- Оператор Прюитта
- Перекрёстный оператор Робертса
Примечания
Ссылки
- L. A. Iverson, S. W. Zucker «Logical/Linear Operators for Image Curves» Шаблон:Wayback
- M.D. Heath, S. Sarkar, T. Sanocki, K.W. Bowyer «A robust visual method for assessing the relative performance of edge-detection algorithms» Шаблон:Wayback
- Pattern Analysis and Machine Intelligence, IEEE Transactions on Шаблон:Wayback
- Lee Iverson Шаблон:Wayback
- Steven W. Zucker Шаблон:Wayback
Литература
- 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
