СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ ВЫДЕЛЕНИЯ НА ЦИФРОВЫХ ИЗОБРАЖЕНИЯХ ОБЪЕКТОВ ЭЛЛИПСОИДНОЙ ФОРМЫ

Круглов А.В.¹, Гиззатуллина А.Р., Тюленева К.В., Югфельд И.Д.²

¹Аспирант,

²студент,

Уральский федеральный университет

СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ ВЫДЕЛЕНИЯ НА ЦИФРОВЫХ ИЗОБРАЖЕНИЯХ ОБЪЕКТОВ ЭЛЛИПСОИДНОЙ ФОРМЫ

Аннотация

В статье исследуется задача выделения на изображениях объектов эллиптической формы применительно к задаче автоматического обнаружения торцов бревен. Рассмотрены программные реализации четырех алгоритмов: метод Виолы-Джонса, выделение сегментов кривых (ELSD), анализ кривизны изофот и метод Хафа для эллиптических объектов (IRHT). По результатам анализа алгоритм ELSD выбран для дальнейшего применения в заданной проблематике.

Ключевые слова: обработка изображений, выделение объектов.

Kruglov A.V.¹, Gizzatullina A.R., Tuleneva K.V., Ugfeld I.D.²

¹Postgraduate student,

²student,

Ural federal university

COMPARATIVE ANALYSIS OF THE ALGORITHMS FOR ISOLATION OF ELLIPTIC OBJECTS IN DIGITAL IMAGES

Abstract

The problem of elliptical objects extracting in the images with respect to the task of automatic detection of the log butt ends is considered in the article. The review of the four algorithms is given: Viola-Jones method, the curve segments selection (ELSD), analysis of the isophotes curvature and convex edges and Hough method for elliptic objects (IRHT). The research results in choosing the ELSD algorithm for further applying in the given issue.

Keywords: image processing, object detection.

Введение

В настоящее время задача распознавания объектов на изображениях находит все большее применение в различных сферах человеческой жизни. При внедрении технологий машинного зрения в процессы оперативного контроля и учета на предприятии к алгоритмам интеллектуальной обработки изображений предъявляются повышенные требования по их эффективности и надежности. Исследуемая задача выделения на изображении торцов бревен в штабеле на первом этапе обработки изображения сводится к выделению круглых объектов. В данной работе приведен анализ эффективности работы четырех алгоритмов, выбранных в результате анализа литературных источников [1-7]. Выбранные методы представляют наиболее современные техники выделения объектов на цифровых изображениях.

Метод Виола-Джонса

Программная реализации алгоритма Виолы-Джонса [2] была написана с помощью библиотеки OpenCV. На первом этапе входное изображение переводится в градиент серого. Дальше используются признаки Хаара для поиска нужных объектов. Все признаки проходят через классификатор, который возвращает результат «истина» или «ложь». После происходит исключение лишних окон за счет использования каскада признаков. В заключении обводится предполагаемый круглый объект и выводится на выходную форму (рис. 1а, 2а).

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

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

Алгоритм ELSD (детектор сегментов эллипсов и линий)

Алгоритм [6] реализован с помощью библиотеки OpenCV. Первым действием программа переводит входное цветное изображение в черно-белое. В дальнейшем метод выделяет кандидатов в отрезки и эллипсы, которые имеют примерно гладкий контур, с помощью сбора рекурсивно соединенных точек с одинаковой ориентацией градиента. После все собранные пикселы используются для оценки правдивости отрезка и эллипса.

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

Некоторые круги не полностью замкнуты, что в дальнейшем может быть исправлено программно. Точность метода в ходе тестов составила от 84 до 98% (рис. 1б, 2б). В дальнейшем программа будет усовершенствована за счет увеличении стойкости к шуму, очистки с изображения лишних объектов, например, ненужных линий и дополнения не замкнутых окружностей.

Метод Хафа

Алгоритм предназначен для поиска объектов, принадлежащих определённому классу фигур, с использованием процедуры голосования. Процедура голосования применяется к пространству параметров, из которого и получаются объекты определённого класса фигур по локальному максимуму в так называемом накопительном пространстве (accumulator space), которое строится при вычислении трансформации Хафа [4].

Суть метода: на изображении методом голосования определяются центры предполагаемых окружностей. Далее по найденным центрам и заданному радиусу строятся окружности. На вход поступает изображение, предположительные минимальный и максимальный радиусы.

Большим недостатком данного метода является ложное детектирование окружностей (рис. 1в, 2в). При этом процент правильного выделения объектов составляет порядка 90%, так как выделение не всегда соответствует контуру объекта.

Алгоритм кривизны изофот

Изофотами называются кривые, соединяющие пиксели с одинаковой интенсивностью [5]. Кривизна изофоты, величина обратная радиусу r соприкасающейся к кривой окружности, вычисляется по следующей формуле:

,

где  производные первого и второго порядка от функции яркости L(x, y). Значения кривизны ограничиваются краевыми пикселями, предварительно полученными в результате применения оператора Канни. Полученный набор значений кривизны фильтруется между верхним и нижним порогом в целях исключения точек с очень низким (принадлежность к прямым линиям или окружностям с большим радиусом) и очень высоким (принадлежность к маленьким окружностям) значением кривизны (рис 1г, 2г).

Рис. 1 – Результат работы алгоритмов для 1го изображения:

а) Метод Виолы-Джонса б) Алгоритм ELSD в) Метод Хафа г) Анализ кривизны изофот

Рис. 2 – Результат работы алгоритмов для 2го изображения:

а) Метод Виолы-Джонса б) Алгоритм ELSD в) Метод Хафа г) Анализ кривизны изофот

Заключение

Описанные методы были протестированы на базе изображений штабелей круглого леса, содержащей 68 изображений. Тестирование проводилось на ПК Intel Core  i7 2,8 GHz; 8 Gb RAM. Результаты тестирования приведены в табл. 1.

Таблица 1 – Усредненные показатели эффективности для выбранных методов в процентах относительно общего числа бревен

	Метод Виолы-Джонса	Алгоритм ELDS	Метод Хафа	Алгоритм кривых изофот
Ошибки первого рода	82.5%	9%	225.85%	43%
Ошибки второго рода	41%	2%	4.2%	75%

Как видно из результатов тестирования, наилучшее соотношение ошибок первого и второго рода демонстрирует метод на основе алгоритма ELDS. При этом метод также отличается высоким быстродействием. Метод Хафа демонстрирует низкие показатели по части ошибок второго рода, однако количество ложных срабатываний метода крайне велико. Методы Виолы-Джонса и анализа кривых изофот показали низкую эффективность в рамках решаемой задачи.

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

Литература

1. L.Pan, W.-S.Chu, J.M.Saragih, F.Torre, Fast and Robust Circular Object Detection with Probabilistic Pairwise Voting (PPV) // IEEE Signal Processing Letters – 2011. - № 18(11) – С. 639–642.
2. А.А.Котов, С.А.Усилин, Д.П.Николаев, Построение устойчивых признаков для алгоритма Виолы и Джонса в задаче классификации транспортных средств // 35-я конференция молодых ученых и специалистов «Информационные технологии и системы – 2012», 2012, Петрозаводск.
3. D.K.Prasad, M.K.H.Leung, S.-Y.Cho, Edge curvature and convexity based ellipse detection method // Pattern Recognition – 2012. – № 45(9) – С. 3204–3221.
4. W.Lu, J.Tan, Detection of incomplete ellipse in images with strong noise by iterative randomized Hough transform (IRHT) // Pattern Recognition – 2008. – № 41(4) – С. 1268–1279.
5. T.Marco, D.Cazzato, M.Leo, C.Distante Randomized circle detection with isophotes curvature analysis // Pattern Recognition – 2015. – № 48(2) – С. 411-421.
6. K.Hahn, S.Jung, Y.Han, H.Hahn, A new algorithm for ellipse detection by curve segments // Pattern Recognition Letters – 2008. – № 13 – С. 1836-1841.
7. M.Fornaciari, A.Prati, R.Cucchiara, A fast and effective ellipse detector for embedded vision applications // Pattern Recognition – 2014. – № 47(11) – С. 3693-3708

References

1. L.Pan, W.-S.Chu, J.M.Saragih, F.Torre, Fast and Robust Circular Object Detection with Probabilistic Pairwise Voting (PPV) // IEEE Signal Processing Letters – 2011. - № 18(11) – С. 639–642.
2. A.A.Kotov, S.A.Ysilin, D.P.Nikolaev, Postroenie ystoichivih priznakov dlja algoritma Violi I Djonsa v zadache klassifikacii transportnih sredstv // 35-ja conferencija molodih ychenih I specialistov «Informacionie tehnologii I sistemi – 2012», 2012, Petrozavodsk.
3. D.K.Prasad, M.K.H.Leung, S.-Y.Cho, Edge curvature and convexity based ellipse detection method // Pattern Recognition – 2012. – № 45(9) – С. 3204–3221.
4. W.Lu, J.Tan, Detection of incomplete ellipse in images with strong noise by iterative randomized Hough transform (IRHT) // Pattern Recognition – 2008. – № 41(4) – С. 1268–1279.
5. T.Marco, D.Cazzato, M.Leo, C.Distante Randomized circle detection with isophotes curvature analysis // Pattern Recognition – 2015. – № 48(2) – С. 411-421.
6. K.Hahn, S.Jung, Y.Han, H.Hahn, A new algorithm for ellipse detection by curve segments // Pattern Recognition Letters – 2008. – № 13 – С. 1836-1841.
7. M.Fornaciari, A.Prati, R.Cucchiara, A fast and effective ellipse detector for embedded vision applications // Pattern Recognition – 2014. – № 47(11) – С. 3693-3708