Обработка и распознавание изображений в системах превентивной безопасности: Учебное пособие. Muthukrishnan R, Radha M. — Алгоритмы выделения контуров для сегментации изображений Список использованной литературы

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

Робертс для контрастирования и выделения перепадов предложил следующую простую нелинейную операцию двумерного дискретного дифференцирования:

.(17.4.10)

Другая операция пространственного дифференцирования, требующая меньшего объема вычислений, определяется формулой

Можно легко показать, что

Отмечая тот из четырех элементов изображения, расположенных около обнаруженной точки, который имеет наибольшее значение яркости, можно получить информацию о приблизительной ориентации перепада. Рис. 17.4.8 иллюстрирует работу операторов Робертса.

Рис. 17.4.8. Примеры выделения перепадов с помощью детекторов Робертса.

Собел предложил использовать для контрастирования нелинейный оператор с окном из элементов. На рис. 17.4.9 показаны использованные им обозначения элементов окна. Для контрастирования перепадов вычисляется величина

, (17.4.13а)

Величины - яркости элементов окна, показанного на рис. 17.4.9. Результаты обнаружения перепадов с помощью оператора Собела приведены на рис. 17.4.10.

Другой нелинейный оператор с таким же окном из элементов для контрастирования перепадов предложен Киршем .

Рис. 17.4.9. Обозначение элементов для операторов выделения перепадов c окном размером .

Этот оператор определяется следующим выражением:

, (17.4.14а)

, (17.4.14б)

Индексы у слагаемых подсчитываются по модулю 8. По существу оператор Кирша дает максимальное значение курсового градиента в некоторой точке изображения без учета значения . Примеры обнаружения перепадов с помощью оператора Кирша приведены на рис. 17.4.11.

Уоллис предложил нелинейный метод обнаружения перепадов, основанный на гомоморфной обработке изображения. Согласно этому методу, точка находится на перепаде, если величина логарифма от яркости в этой точке превосходит среднее значение логарифмов яркостей четырех ближайших соседних элементов на некоторое фиксированное значение. Элемент контрастированного изображения определяется как

или, что эквивалентно,

. (17.4.15б)

Сравнение с верхним и нижним пороговыми значениями эквивалентно сравнению дроби в скобках выражения (17.4.156) с видоизмененным порогом. Поэтому не требуется точно вычислять значения логарифмов. Основное преимущество логарифмического детектора перепадов кроме простоты вычислений состоит в том, что он не чувствителен к мультипликативным изменениям уровня яркости. Рис. 17.4.12 иллюстрирует работу логарифмического детектора перепадов.

Рис. 17.4.10. Примеры выделения перепадов с помощью оператора Собела.

Рис. 17.4.11. Примеры выделения перепадов с помощью оператора Кирша.

Логарифмический метод контрастирования, определяемый выражением (17.4.15), можно рассматривать как линейное контрастирование с помощью оператора Лапласа (17.4.5а) изображения, уровни элементов которого равны логарифмам яркостей. Другие методы контрастирования также можно легко представить в виде последовательности нелинейных поэлементных операций с дальнейшим линейным контрастированием перепадов и пороговым ограничением.

Рис. 17.4.12. Примеры выделения перепадов с помощью логарифмического оператора Лапласа.

Нелинейный метод повышения контраста и выделения перепадов, основанный на вычислении произведения набора некоторых величин, разработал Розенфельд . В этом методе используется оператор построчного одномерного усреднения. Текущее среднее

где и - целое, вычисляется для каждого элемента изображения. Эта операция выполняется для вплоть до некоторого желаемого верхнего предела. Затем для каждого элемента изображения вычисляется произведение

Понятно, что сомножители, соответствующие усреднению более высокого порядка, указывают довольно широкие пределы локализации перепада и производят некоторое подавление шумов, тогда как сомножители усреднения более низкого порядка локализуют перепад точнее, но при этом маски значительно чувствительнее к шуму. Вместе с тем можно предположить, что произведение средних разного порядка должно обеспечивать надежное обнаружение и локализацию истинных перепадов. Обоснование этого предположения, приводимое Розенфельдом, заключается в следующем.

Рис. 17.4.13. Примеры обычного порогового ограничения и ограничения с подавлением доминирующими соседями для случая оператора Собела: а - обычное пороговое ограничение; б - увеличенный участок изображения а, содержащий ствол пушки; г - этот же участок при коэффициенте подавления, равном 1,5; г - этот же участок при коэффициенте подавления, равном 1,2.

Величина проявляет тенденцию обнаруживать и точно локализовать основные перепады и при этом подавлять шум. Это можно объяснить тем, что произведение велико лишь тогда, когда велики все сомножители, а по мере удаления от точки перепада сначала уменьшаются сомножители с малыми индексами, а затем и с большими.

Кроме того, Розенфельд предложил нелинейную процедуру порогового ограничения для выделения больших отчетливых перепадов, находящихся в окружении более мелких. Эта процедура, которую в дальнейшем будем называть «подавлением доминирующими соседями», выполняется сканированием поля контрастированных перепадов окном малых размеров. Значение в центре окна подавляется (приравнивается нулю) всякий раз, когда оно не оказывается наибольшим из всех отсчетов в этом окне. Затем выполняется обычное пороговое ограничение. Другой вариант такой обработки состоит в том, что подавление разрешается лишь в случае, если в окне имеются элементы, значения которых намного превышают значения . Алгоритм подавления доминирующими соседями с последующим пороговым ограничением оказывается довольно эффективным при обнаружении перепадов, если его объединить с методом контрастирования, обеспечивающим некоторое сглаживание шума. На рис. 17.4.13 приведены примеры, иллюстрирующие работу алгоритма подавления доминирующими соседями с последующим пороговым ограничением.

Для дискретных изображений вычисление частных производных сводится к вычислению перепада яркости соседних пикселей различ ными способами, т. е. фактически к пространственной фильтрации. Например, фильтр Робертса, использующий для определения гра диента яркости минимальное число пикселей, можно представить как f 11(x, y) 2| , где b – весовой коэффициент; L – преобразование оператором Лапла са, причем в данном случае необходимо учитывать знак яркости пик селя после преобразования. В результате яркость пикселей, лежа щих в начале перехода от менее яркой области к более яркой, умень шится, так как результат преобразования Лапласа для этих пиксе лей будет больше нуля. Яркость пикселей, лежащих в конце этого перехода, соответственно, увеличится, так как для них результат преобразования Лапласа будет меньше нуля. В итоге резкость данно го перехода возрастет, что и продемонстрировано на рис. 6.7 для b = 1. Изменяя значение b и выбирая разные маски для оператора Лапласа из (6.3), можно регулировать степень подчеркивания контура. Второй подход можно представить как f 11(x, y) 2 cf 1(x, y) 3 (c 3 1)G , (6.4) где с – весовой коэффициент; G – результат воздействия размываю щего линейного пространственного фильтра, например гауссиана (6.2). Напомним, что в результате применения размывающих филь тров области с постоянной яркостью остаются без изменений, а яр кость пикселей остальных областей на результирующем изображе нии всегда меньше яркости соответствующих пикселей на исходном изображении. Тогда в результате обработки изображения по (6.4) области постоянной яркости сохраняют значения исходного изобра жения, а яркость остальных пикселей увеличится на величину раз мывания с учетом весового коэффициента. 72 7. СЕГМЕНТАЦИЯ ИЗОБРАЖЕНИЙ 7.1. Сегментация бинарных изображений Под сегментацией изображения обычно понимается процесс его раз биения на составные части, имеющие содержательный смысл. Количе ство известных алгоритмов сегментации исчисляется десятками, одна ко большинство из них можно свести к выявлению сходства между от дельными точками изображения с целью нахождения в некотором смыс ле однородных областей. В результате сегментации каждой точке изоб ражения должен быть поставлен в соответствие номер сегмента, к кото рому эта точка отнесена, причем заранее число сегментов неизвестно. Основная сложность проблемы сегментации заключается именно в вы боре и формализации понятия однородности. Сегментация изображения на ряд однородных областей выполня ется согласно правилу связности отдельных элементов и мере одно родности, определяющей сходство связанных элементов друг с дру гом. В качестве элементов могут выступать как отдельные точки, так и их совокупности, объединенные по принципу близости каких либо свойств. В последнем случае сегментация сложного изображе ния превращается в иерархический процесс. Если в качестве харак теристики однородности выбрана яркость, то для дискретного изоб ражения в однородную область группируются связанные пиксели, имеющие одинаковую или близкую яркость. В последнем случае ре зультат сегментации будет определяться выбором уровня порога бли зости. Для бинарных изображений условие близости по яркости три виально и решение о принадлежности пикселя сегменту принимает ся на основе анализа связности. Понятие «связность» пикселей задает формальное правило, опре деляющее, какие пиксели считать соседними. Наиболее часто для каждого пикселя в качестве связанных рассматривается или область из четырех пикселей, примыкающих к нему по строке и столбцу, или область из восьми ближайших пикселей, включающая в себя и диа гональные пиксели из окрестности 3 ´ 3, хотя иногда используются 73 и более сложные определения связно сти . Формально множество пик селей P, образующих сегмент, назы вается восьмисвязным, если между любыми двумя его элементами a и b существует последовательность эле ментов {ek Î P}k = 0,…,K такая, что Рис. 7.1. Определение e0 = a; eK = b и при любом k, 0

Kirsch compass masks are yet another type of derivative mask which are used for edge detection. This operator is also known as direction mask. In this operator we take one mask and rotate it in all the eight compass directions to get edges of the eight directions.

We are going to use OpenCV function filter2D to apply Kirsch operator to images. It can be found under Imgproc package. Its syntax is given below −

Filter2D(src, dst, depth , kernel, anchor, delta, BORDER_DEFAULT);

The function arguments are described below −

Sr.No.	Argument
1	It is source image.
2	It is destination image.
3	It is the depth of dst. A negative value (such as -1) indicates that the depth is the same as the source.
4	It is the kernel to be scanned through the image.
5	It is the position of the anchor relative to its kernel. The location Point (-1, -1) indicates the center by default.
6	It is a value to be added to each pixel during the convolution. By default it is 0.
7	BORDER_DEFAULT We let this value by default.

Apart from the filter2D() method, there are other methods provided by the Imgproc class. They are described briefly −

Sr.No.	Method & Description
1	cvtColor(Mat src, Mat dst, int code, int dstCn) It converts an image from one color space to another.
2	dilate(Mat src, Mat dst, Mat kernel) It dilates an image by using a specific structuring element.
3	equalizeHist(Mat src, Mat dst) It equalizes the histogram of a grayscale image.
4	filter2D(Mat src, Mat dst, int depth, Mat kernel, Point anchor, double delta) It convolves an image with the kernel.
5	GaussianBlur(Mat src, Mat dst, Size ksize, double sigmaX) It blurs an image using a Gaussian filter.
6	integral(Mat src, Mat sum) It calculates the integral of an image.

Example

The following example demonstrates the use of Imgproc class to apply Kirsch operator to an image of Grayscale.

Import org.opencv.core.Core; import org.opencv.core.CvType; import org.opencv.core.Mat; import org.opencv.highgui.Highgui; import org.opencv.imgproc.Imgproc; public class convolution { public static void main(String args) { try { int kernelSize = 9; System.loadLibrary(Core.NATIVE_LIBRARY_NAME); Mat source = Highgui.imread("grayscale.jpg", Highgui.CV_LOAD_IMAGE_GRAYSCALE); Mat destination = new Mat(source.rows(),source.cols(),source.type()); Mat kernel = new Mat(kernelSize,kernelSize, CvType.CV_32F) { { put(0,0,-3); put(0,1,-3); put(0,2,-3); put(1,0-3); put(1,1,0); put(1,2,-3); put(2,0,5); put(2,1,5); put(2,2,5); } }; Imgproc.filter2D(source, destination, -1, kernel); Highgui.imwrite("output.jpg", destination); } catch (Exception e) { System.out.println("Error: " + e.getMessage()); } } }

УДК: 004.932.72Ч ГРНТИ: 28.23.15 DOI: 10.15643/jscientia.2016.6.195

ОПТИМАЛЬНЫЕ АЛГОРИТМЫ ВЫДЕЛЕНИЯ КОНТУРОВ ИЗОБРАЖЕНИЯ В СИСТЕМЕТЕХНИЧЕСКОГО ЗРЕНИЯ

Е. Е. Пелевин*, С. В. Балясный

Тульский государственный университет Россия, 300012, г. Тула, пр-т Ленина, 92 * email: [email protected]

В статье рассматривается вопрос распознавания контуров изображения в робототехнике. В качестве объектов исследования выступают четыре алгоритма идентификации контуров: Кирша, Робинсона, Канни и Marr-Hildreth. С помощью данных алгоритмов, часто применяющихся в современной робототехнике, было проведено исследование по эффективности выделения контуров изображений в системах технического зрения с принимающими на вход различными типами объектов. Результаты проведенных исследований показали, что наиболее эффективным в выделении контуров на изображении является метод Канни. В процессе работы было выявлено, что данный метод позволяет достигнуть высокой резкости, а также детализации. Вторым по эффективности выделения линейных контуров стал метод Marr-Hildreth. Исходя из результатов исследования, можно сделать вывод о том, что существуют наиболее универсальные алгоритмы, но каждый из них по-своему подходит для определенных классов изображений.

Ключевые слова: Кирш, Робинсон, Канни, Marr-Hildreth, оператор, распознавание, контур, робототехника, система технического зрения (СТЗ).

OPTIMAL ALGORITHM OF EDGE DETECTION WITHIN THE SYSTEM OF COMPUTER VISION

E. E. Pelevin*, S. V. Balyasny

Tula State University

Prospect Lenina 92, 300012, Tula, Russia

* email: [email protected]

The article touches upon the edge detection of digital images in robotics. Four algorithms of edge identification singled out by Kirsh, Robinson, Canny and Marr-Hildreth serve as the subject matter of the research. With the help of these algorithms widely used in the modern robotics, the research of efficiency of edge detection of images within the systems of computer vision which accept various input types of objects has been done. The results of the research done have shown that the method of Canny is the most effective in edge detection of images. During the work process, it has been found out that this method allows achieving both high definition and refinement. The method of Marr-Hildreth has become the second efficient method in edging of line contours. Based on the research results, the following conclusion can be drawn: there are more universal algorithms, but each of them differently fits particular classes of images.

Keywords: Kirsh, Robinson, Canny, Marr-Hildreth, operator, edge detection, contour, robotics, computer vision system.

Несомненно, в век компьютерных технологий все большее место в современной науке занимает робототехника. Это связанно с внедрением нового оборудования на заводах, автозаправочных станциях, в аэропортах и в других сферах жизнедеятельности человека. Частью этих нововведённых систем является программа с тем или иным алгоритмом распознавания контуров изображений, например, реализация выделения контуров различных деталей или механизмов. От эффективности данного алгоритма зависит и вся последующая работа роботизированной системы в целом.

В настоящее время существует большое количество различных алгоритмов выделения контуров, но лишь некоторые из них получили широкое распространение, а именно за счет своей универсальности. В этой работе будут рассмотрены наиболее популярные алгоритмы: оператор Кирша, оператор Робинсона, детектор границ Канни и метод Marr-Hildreth . Для тестирования этих методов будет использоваться тестовое изображение (рис.1).

Первым из рассматриваемых методов является оператор Кирша. Этот метод был разработан Русселом А. Киршем в 1971 году . Данный алгоритм основывается на использовании обнаруживающей матрицы (маски), которую последовательно вращают по восьми основным сторонам

Рис. 1. Исходное изображение для обнаружения контуров.

света: север, северо-запад, запад, юго-запад, юг, юго-восток, восток и северо-восток. После исследования Руссел А. Кирш вывел следующие маски для каждой стороны света :

5 5 5 -3 0 -3 -3 -3 -3J

COMPUTER SCIENCE | Juvenis scientia 2016 № 6

В данном случае величина границы определяется как максимальное значение, которое может быть найдено при помощи маски. Определенная маска помогает направлению выдать максимальную величину. Из этого можно сделать вывод, что маска ко позволяет выделять вертикальные границы, а маска к5 - диагональные. Из масок так же заметно, что последние похожи на первые четыре, но являются их зеркальным отражением по центральной оси используемой матрицы .

В ходе обработки тестового изображения, можно получить следующий результат (рис. 2).

Рис. 2. Идентификация контуров оператором Кирша.

Позднее в 1977 году был разработан оператор Робинсона, который, по сути, являлся аналогом метода Кирша, но благодаря использованию коэффициентов о, 1 и 2 стал более простым в реализации. Матрицы, которые использует данный оператор, являются симметричными относительно своих центральных осей, каждая из которых заполнена нулями. Благодаря этому можно использовать лишь первые четыре матрицы, а остальные результаты получить, инвертируя первые. Оператор Робинсона будет выглядеть следующим образом:

Рис. 3. Результат работы оператора Робинсона.

Несмотря на простоту предыдущего оператора, наибольшую популярность в итоге получил детектор границ Канни. Метод впервые был описан в 1983 году ученым Джоном Канни в своей магистерской диссертации. Данный метод превосходит по эффективности своей работы многие современные, даже если и был разработан более тридцати лет назад. Его отличительной особенностью является устранение шума на контурах изображения, что, несомненно, оказывает влияние на конечный результат. Данный алгоритм заключается в выполнении следующих шагов:

Размытие исходного изображения с) с помощью метода Гаусса ^(г, с). ^(г, c)=f(r,c)*G(r,c,6);

Выполнить поиск градиента. Границы намечаются там, где градиент принимает максимальное значение;

Подавление не-максимумов. Только локальные максимумы отмечаются как границы;

Итоговые границы определяются путем подавления всех краев, не связанных с определенными границами.

Результатом работы алгоритма являются контуры на изображении. За счет своих особенностей данный метод мало восприимчив к шуму (рис. 4).

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

Как и в предыдущем случае, можно провести обработку исходных изображений (рис. 3).

Рис. 4. Результат работы метода Канни.

Последний метод обнаружения границ цифровых изображений называется Магг-ЫИге^, который был разработан в 1980 году. Он подразумевает под собой обнаружение кривых на всех участках, где наблюдается резкое изменение яркостей групп пикселей. Данный метод является простым и работает при помощи свертки исходного изо-

бражения с LoG-функцией или как быстрая аппроксимация с DoG. При работе метода нули в обратном результате обозначают контуры изображения. Для работы метода необходимо придерживаться следующих шагов алгоритма :

Размытие изображение методом Гаусса;

Применение оператора Лапласа к размытому изображению (часто первые два шага объединены в один);

Производится цикл вычислений и в полученном результате смотрят на смену знака. Если знак изменится с отрицательного на положительный и значение изменится более чем на некоторый заданный порог, то необходимо определить эту точку, как границу;

Для получения лучших результатов шаг с использованием оператора Лапласа можно выполнить через гистерезис, то есть так, как это реализовано в алгоритме Канни.

Результат работы данного алгоритма на тестовом изображении будет следующим (рис. 5).

Исходя из проведенных исследований, можно сделать вывод о том, что для распознавания механизмов и других объектов, состоящих из криволинейных контуров, в робототехнике эффективнее всего может применяться метод Канни, который позволяет добиться наибольшей резкости границ и высокой детализации. Для выделения линейных контуров объектов, например, в тех случаях, если используются системы технического зрения на конвейерных линиях, наилучшим образом подходит метод Marr-Hildreth, который выделяет даже мелкие линейные контуры на изображениях. Таким образом, в робототехнике могут использоваться все описанные алгоритмы выделений, но каждый из них наиболее эффективен на определенном классе задач, а также нацелен на получение результата определенного качества.

ЛИТЕРАТУРА

1. Аммерал Л. Принципы программирования в машинной графике / Л. Аммерал. М.: Сол Систем, 1992. 665 с.

2. Бутаков Е.А. Обработка изображений на ЭВМ: моногр. / Е.А. Бутаков, В.И. Островский, И.Л. Фадеев. М.: Радио и связь, 1987. 205 с.

3. Прэтт У. Цифровая обработка изображений / У. Прэтт. М.: Мир, 1982. Т. 2. 716 с.

4. Ту Дж. Принципы распознавания образов / Дж. Ту, Р. Гонсалес. М.: Мир, 1978. 764 с.

5. Файн В.С. Опознавание изображений / В.С. Файн. М.: Наука, 2003. 322 с

6. Яншин В. Обработка изображений на языке Си для IBM PC: Алгоритмы и программы / В. Яншин, Г. Калинин. М.: Мир, 1994. 358 с.