Введение
Алгоритм обнаружения границ изображения
Детектор границ Канни — это оператор обнаружения границ, использующий многоэтапный алгоритм для выявления широкого спектра границ на изображениях. Он был разработан Джоном Ф. Канни в 1986 году. Канни также создал вычислительную теорию обнаружения границ, объясняющую принцип работы данной техники.
Гауссов фильтр
Поскольку все результаты обнаружения границ легко подвержены влиянию шума на изображении, необходимо фильтровать шум, чтобы предотвратить ложное обнаружение, вызванное им. Для сглаживания изображения к изображению применяется свёртка с ядром гауссовского фильтра. Этот шаг слегка сглаживает изображение, чтобы уменьшить влияние явного шума на детектор границ. Уравнение для ядра гауссовского фильтра размером (2k+1)×(2k+1) приведено ниже:
Пример гауссовского фильтра 5×5, используемого для создания соседнего изображения, приведен при σ = 1. (Звездочка обозначает операцию свёртки.) Важно понимать, что выбор размера гауссовского ядра влияет на производительность детектора. Чем больше размер ядра, тем ниже чувствительность детектора к шуму. Кроме того, погрешность локализации при обнаружении границы незначительно увеличивается с увеличением размера ядра гауссовского фильтра. Размер 5×5 подходит для большинства случаев, но он также может варьироваться в зависимости от конкретной ситуации.
Предельный размер градиента или снижение границы отсечения
Минимальное подавление величин градиента, или пороговое подавление снизу, является методом утонения краев. Подавление нижней границы отсечки применяется для определения местоположений с наиболее резким изменением значения интенсивности. Алгоритм для каждого пикселя в градиентном изображении следующий:
Сравните силу края текущего пикселя с силой края пикселя в положительном и отрицательном направлениях градиента. Если сила края текущего пикселя является наибольшей по сравнению с другими пикселями в маске с тем же направлением (например, пиксель, ориентированный в направлении y, будет сравниваться с пикселем выше и ниже него по вертикальной оси), значение будет сохранено. В противном случае значение будет подавлено. В некоторых реализациях алгоритм категоризирует непрерывные направления градиента в небольшой набор дискретных направлений, а затем перемещает 3x3 фильтр по результату предыдущего шага (то есть, силе края и направлениям градиента). На каждом пикселе он подавляет силу края центрального пикселя (устанавливая его значение в 0), если его величина не больше величины двух соседей в направлении градиента. Например,
если округленный угол градиента равен 0° (то есть, край ориентирован в направлении север-юг), точка будет считаться принадлежащей краю, если ее величина градиента больше величин в пикселях в восточном и западном направлениях,
если округленный угол градиента равен 90° (то есть, край ориентирован в направлении восток-запад), точка будет считаться принадлежащей краю, если ее величина градиента больше величин в пикселях в северном и южном направлениях,
если округленный угол градиента равен 135° (то есть, край ориентирован в направлении северо-восток-юго-запад), точка будет считаться принадлежащей краю, если ее величина градиента больше величин в пикселях в северо-западном и юго-восточном направлениях,
если округленный угол градиента равен 45° (то есть, край ориентирован в направлении северо-запад-юго-восток), точка будет считаться принадлежащей краю, если ее величина градиента больше величин в пикселях в северо-восточном и юго-западном направлениях. В более точных реализациях используется линейная интерполяция между двумя соседними пикселями, которые лежат по обе стороны от направления градиента. Например, если угол градиента находится между 89° и 180°, интерполяция между градиентами в северном и северо-восточном пикселях даст одно интерполированное значение, а интерполяция между южным и юго-западным пикселями даст другое (используя соглашения, описанные в последнем абзаце). Величина градиента в центральном пикселе должна быть больше обеих этих величин, чтобы он был отмечен как край. Обратите внимание, что знак направления не имеет значения, то есть север-юг эквивалентен юг-север и так далее.
Compare the edge strength of the current pixel with the edge strength of the pixel in the positive and negative gradient directions. If the edge strength of the current pixel is the largest compared to the other pixels in the mask with the same direction (e. g., a pixel that is pointing in the y direction will be compared to the pixel above and below it in the vertical axis), the value will be preserved. Otherwise, the value will be suppressed. In some implementations, the algorithm categorizes the continuous gradient directions into a small set of discrete directions, and then moves a 3x3 filter over the output of the previous step (that is, the edge strength and gradient directions). At every pixel, it suppresses the edge strength of the center pixel (by setting its value to 0) if its magnitude is not greater than the magnitude of the two neighbors in the gradient direction. For example,
if the rounded gradient angle is 0° (i. e. the edge is in the north–south direction) the point will be considered to be on the edge if its gradient magnitude is greater than the magnitudes at pixels in the east and west directions,
if the rounded gradient angle is 90° (i. e. the edge is in the east–west direction) the point will be considered to be on the edge if its gradient magnitude is greater than the magnitudes at pixels in the north and south directions,
if the rounded gradient angle is 135° (i. e. the edge is in the northeast–southwest direction) the point will be considered to be on the edge if its gradient magnitude is greater than the magnitudes at pixels in the north west and south east directions,
if the rounded gradient angle is 45° (i. e. the edge is in the northwest–southeast direction) the point will be considered to be on the edge if its gradient magnitude is greater than the magnitudes at pixels in the north east and south west directions. In more accurate implementations, linear interpolation is used between the two neighbouring pixels that straddle the gradient direction. For example, if the gradient angle is between 89° and 180°, interpolation between gradients at the north and north east pixels will give one interpolated value, and interpolation between the south and south west pixels will give the other (using the conventions of the last paragraph). The gradient magnitude at the central pixel must be greater than both of these for it to be marked as an edge. Note that the sign of the direction is irrelevant, i. e. north–south is the same as south–north and so on.
Двойной порог
После применения не максимального подавления оставшиеся пиксели границ обеспечивают более точное представление истинных границ на изображении. Однако некоторые пиксели границ остаются, вызванные шумом и вариациями цвета. Для учета этих ложных срабатываний необходимо отфильтровать пиксели границ со слабым значением градиента и сохранить пиксели границ с высоким значением градиента. Это достигается выбором верхнего и нижнего пороговых значений. Если значение градиента пикселя границы превышает верхний порог, он помечается как пиксель сильной границы. Если значение градиента пикселя границы меньше верхнего порога, но больше нижнего порога, он помечается как пиксель слабой границы. Если значение градиента пикселя границы меньше нижнего порога, он подавляется. Значения этих порогов определяются эмпирически и зависят от содержимого конкретного входного изображения.
Отслеживание краев гистерезисом
Сильные пиксели границы, безусловно, должны быть включены в окончательное изображение границы, поскольку они, как считается, соответствуют истинным границам на изображении. Однако, по поводу слабых пикселей границы могут возникнуть споры. Нам необходимо определить, соответствуют ли эти пиксели истинной границе или являются результатом шума и цветовых вариаций. Если это последнее, то слабые пиксели границы следует исключить из рассмотрения. Данный алгоритм основывается на идее, что слабые пиксели границы, принадлежащие истинной границе, (как правило) будут связаны с сильным пикселем границы, в то время как отклики на шум будут несвязными. Для отслеживания связи границы применяется анализ областей, при котором рассматривается слабый пиксель границы и его 8 связанных соседних пикселей. Если в области присутствует хотя бы один сильный пиксель границы, то данная слабая точка границы может быть идентифицирована как подлежащая сохранению. Эти слабые пиксели границы становятся сильными границами, что, в свою очередь, может привести к сохранению соседних слабых пикселей границы.
Прохождение алгоритма
В этом разделе будет показано, как изображение проходит через каждый из пяти этапов.
Улучшения
В то время как традиционное детектирование границ по Кэнни предоставляет относительно простую, но точную методологию для задачи обнаружения границ, при более высоких требованиях к точности и надежности обнаружения, традиционный алгоритм уже не справляется со сложной задачей детектирования границ. Основные недостатки традиционного алгоритма можно суммировать следующим образом: для сглаживания шума применяется гауссов фильтр, но он также сглаживает сами границы, которые рассматриваются как высокочастотные характеристики. Это увеличивает вероятность пропуска слабых границ и появления изолированных границ в результате. Для вычисления амплитуды градиента старый алгоритм обнаружения границ Кэнни использует центральную точку в небольшом окне 2x2 для вычисления среднего значения конечных разностей, представляющего амплитуду градиента. Этот метод чувствителен к шуму и может легко обнаруживать ложные границы и пропускать реальные. В традиционном алгоритме обнаружения границ Кэнни используются два фиксированных глобальных пороговых значения для отсеивания ложных границ. Однако, по мере усложнения изображения, различным локальным областям требуются существенно разные пороговые значения для точного определения реальных границ. Кроме того, глобальные пороговые значения определяются вручную, посредством экспериментов, что усложняет вычисления при обработке большого количества различных изображений. Результат традиционного детектирования не обеспечивает удовлетворительно высокой точности – для каждой границы должен быть только один отклик, в то время как наблюдается множественный. Для устранения этих недостатков в следующих разделах представлено улучшение алгоритма Кэнни.
A Gaussian filter is applied to smooth out the noise, but it will also smooth the edge, which is considered as the high frequency feature. This will increase the possibility of missing weak edges, and the appearance of isolated edges in the result. For the gradient amplitude calculation, the old Canny edge detection algorithm uses the center in a small 2×2 neighborhood window to calculate the finite difference mean value to represent the gradient amplitude. This method is sensitive to noise and can easily detect false edges and lose real edges. In the traditional Canny edge detection algorithm, there will be two fixed global threshold values to filter out the false edges. However, as the image gets complex, different local areas will need very different threshold values to accurately find the real edges. In addition, the global threshold values are determined manually through experiments in the traditional method, which leads to a complexity of calculation when a large number of different images need to be dealt with. The result of the traditional detection cannot reach a satisfactory high accuracy of a single response for each edge multi point responses will appear. In order to address these defects, an improvement to the canny edge algorithm is presented in the following paragraphs.
Улучшение расчета величины и направления градиента
Величина и направление градиента могут быть вычислены с помощью различных операторов детекции границ, и выбор оператора может влиять на качество результатов. Наиболее часто используемым является 3x3 фильтр Собеля. Однако другие фильтры могут оказаться более подходящими, например, 5x5 фильтр Собеля, который снижает уровень шума, или фильтр Шарра, обладающий лучшей радиальной симметрией. Также часто применяются фильтры Превитта (используемый Чжоу) и Робертса Кросса.
Надежный метод определения двойного порогового значения
Для решения проблем, возникающих при сложном эмпирическом определении двойного порогового значения, метод Оцу можно применить к изображению величины градиента после не максимального подавления, чтобы получить верхний порог. Нижний порог в этом случае обычно устанавливается равным 1/2 от верхнего порога. Поскольку изображение величины градиента имеет непрерывные значения и не имеет четко выраженного максимума, метод Оцу необходимо адаптировать для использования пар "значение/количество" вместо полной гистограммы.
Опорожнение края
В то время как традиционный алгоритм обнаружения границ Канни обеспечивает хороший результат, удовлетворяющий первым двум критериям, он не всегда строго соответствует требованию единственного отклика на границу. Маллат С. и Чжун разработали метод математической морфологии для утонения обнаруженных границ.
Использование кривых
В кривлеты были заменены гауссов фильтр и оценка градиента для вычисления векторного поля, направления и величина которого аппроксимируют направление и силу границ изображения, к которому затем применяются шаги 3–5 алгоритма Канни. Кривлеты раскладывают сигналы на отдельные компоненты различных масштабов, а отбрасывание компонентов более мелких масштабов может снизить уровень шума.
Дифференциальная геометрическая формулировка
Более точный подход к получению границ с субпиксельной точностью заключается в использовании метода дифференциального обнаружения границ, где требование подавления немаксимумов формулируется с использованием второй и третьей производных, вычисленных из представления в масштабно-пространственной области (Линдеберг, 1998) – подробное описание см. в статье об обнаружении границ.
Параметры
Алгоритм Канни содержит ряд настраиваемых параметров, которые могут влиять на время вычислений и эффективность алгоритма. Размер гауссовского фильтра: фильтр сглаживания, используемый на первом этапе, напрямую влияет на результаты работы алгоритма Канни. Фильтры меньшего размера вызывают меньшее размытие и позволяют обнаруживать мелкие, чёткие линии. Фильтр большего размера вызывает большее размытие, распределяя значение пикселя по большей области изображения. Большие радиусы размытия более полезны для обнаружения крупных, более плавных границ – например, границы радуги. Пороги: использование двух порогов с гистерезисом обеспечивает большую гибкость по сравнению с использованием одного порога, однако общие проблемы, связанные с пороговой обработкой, остаются актуальными. Слишком высокий порог может привести к потере важной информации. С другой стороны, слишком низкий порог будет ошибочно определять нерелевантную информацию (например, шум) как важную. Сложно подобрать универсальный порог, который хорошо работал бы для всех изображений. На данный момент не существует проверенного подхода к решению этой проблемы.
Заключение
Алгоритм Канни адаптируется к различным условиям. Его параметры позволяют настраивать его для распознавания краев с различными характеристиками в зависимости от конкретных требований реализации. В оригинальной статье Канни вывод оптимального фильтра привел к фильтру с конечным импульсным откликом, вычисление которого может быть медленным в пространственной области, если требуется значительное сглаживание (в этом случае фильтр будет иметь большую пространственную поддержку). По этой причине часто рекомендуется использовать форму фильтра Канни с бесконечным импульсным откликом, разработанную Рашидом Деришем (детектор Канни–Дериша), которая является рекурсивной и может быть вычислена за короткое, фиксированное время для любой желаемой степени сглаживания. Вторая форма подходит для реализации в реальном времени на FPGA, DSP или очень быстрых встраиваемых компьютерах. Однако в этом контексте стандартная рекурсивная реализация оператора Канни не обеспечивает хорошего приближения к радиальной симметрии и, следовательно, имеет тенденцию к выделению горизонтальных и вертикальных краев.