Аннотация
![image](https://habrastorage.org/storage/habraeffect/6d/73/6d73ec09c2c7a52eb28960a5675f2b36.png)
В статье Детектор границ Канни, как я уже и писал в комментариях к ней, искажена и потеряна суть алгоритма в том месте, где происходит поиск градиента. Для этого там используется ядра Собеля, о которых Канни совсем ничего не говорил. Я написал поправку, которая позволят алгоритму выделения контуров работать быстрее. Так же эту статью можно считать продолжением записи О градиенте изображения.
В статье не рассматриваются вопросы с выбором оптимального шага дискретизации ядра смаза.
Предпосылки
- Прежде чем вычисляется градиент функции яркости изображения, часто, для получения устойчивого результата прибегают к фильтрации шумов с использованием Гауссова фильтра, то есть выполняют предварительный смаз.
- Затем с использованием разностных аппроксимаций производных находят компоненты градиента.
Пусть смаз делается с использованием ядра размера NxN точек, а разностные шаблоны для вычисления производных вдоль осей имеют размеры 1xK и Kx1. Размер картинки положим равным MxM.
Для простоты будем считать только умножения, тогда последовательность «Смаз->Градиент» потребует N^2*M^2 + 2*K*M^2=(N^2 + 2*K)*M^2 операций.
Однако, известна формула
![image](https://habrastorage.org/storage/habraeffect/44/d3/44d3aa27e63041c06d705f2222fa4322.png)
использование которой позволит нам сократить количество на порядки. О чем она говорит? — о том, что в принципе не обязательно вначале выполнять смаз а потом дифференцировать изображение. Можно продифференцировать ядро смаза f а потом уже выполнить свертку. Приступим.
Разделение ядра
Посмотрим на двумерную функцию Гаусса:
![image](https://habrastorage.org/storage/habraeffect/a5/c7/a5c7e572ee22705dea64cba39503d1b9.png)
ее производная по x записывается в виде:
![image](https://habrastorage.org/storage/habraeffect/73/30/7330024699fe0f109efa28caa50d915d.png)
Получить эту замечательную производную мы можем исполнив код MatLab'a:
- sigma = 1.4;
- x = -3*sigma:0.1:3*sigma
- y = x;
- [x,y] = meshgrid(x,y);
- Fx1 = ( -x/2/pi/sigma^2 ).*exp( -(x.^2+y.^2)/2/sigma^2 );
- figure; surf(Fx1)
* This source code was highlighted with Source Code Highlighter.
Фильтр с таким ядром иногда называют фильтром Канни, а ядро — ядром Канни, который наравне с другими операторами, аппроксимирует производную. По этому поводу делюсь замечательно иллюстрированной заметкой.
Заметим, что производная разделима по координатам, а значит мы можем реализовать строчно — столбцовый алгоритм вычисления градиента смазанного изображения:
![image](https://habrastorage.org/r/w1560/storage/habraeffect/00/aa/00aa45aaab2567c19bfc503f99cac4cc.png)
Посчитаем количество операций в случае строчно-столбцового алгоритма.
Для получения производной по y:
- Обрабатываем Гауссом изображение I по строкам окном размера 1xK1, получаем изображение I1 за K*M^2 умножений (Не забудьте нормировать ядро),
- Обрабатываем изображение I1 по строкам с ядром размера K1x1:
![image](https://habrastorage.org/r/w1560/storage/habraeffect/ff/8a/ff8a08e0ea0d8364a320fdf4350ac7c3.png)
(Не забудьте подобрать шаги дискретизации ядра так, чтобы сумма отсчетов была равна 0)
На такую операцию нам понадобится столько же — K*M^2 умножений.
Алгоритм получения производной по x аналогичен, и суммируя количество операций получим, что для вычисления компонент смазанного градиента нам потребуется 4*K1*M^2.
Эффективность
Эффективность описанной оптимизации можно количественно выразить отношением:
![image](https://habrastorage.org/r/w1560/storage/habraeffect/1c/5c/1c5cc7cfaf456a7cfc8fa7dda14f50ec.png)
Получилось что эффективность зависит только от размеров окон, но не от размера изображений.
Пусть для смаза в простом алгоритме используется ядро размера N = 5, а для вычисления производных аппроксимация первого порядка ( ядра [-1 1] и [-1 1]' ) — K= 2.
В случае оптимизированного строчно-столбцового алгоритма положим K1 = 5. Тогда λ = 20/29 = 0.68.
Эффективность λ < 1 — у нас получилось сократить количество арифметических операций при вычислении последовательности «Смаз-Градиент».