Сравнение методов нахождения ключевых точек на контуре изображений аэрофотосъемки



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

Ключевые слова: искусственный интеллект, компьютерное зрение, детектор контуров, ключевые точки

Одним из приоритетных направлений исследования в области искусственного интеллекта можно назвать компьютерное зрение [1, 2, 3, 4, 5, 6]. Исследование методов компьютерного зрения является актуальным, поскольку для эффективного выполнения задач роботами и другими автоматическими системами необходимо получать информацию об их окружении [3, 4]. Одним из факторов влияния на проблему искусственного интеллекта можно назвать разработку алгоритмов выделения контуров на изображении и их дальнейший анализ [7, 8, 9, 10]. Важная задача анализа контуров является их сопоставление [11] с целью нахождения объектов на изображении, а также сравнения изображений, например, для целей навигации беспилотных летательных аппаратов [2, 7, 9]. Одним из методов сравнения контуров является их сопоставление по ключевым точкам [12]. Существует ряд различных методов нахождения ключевых точек на плоскостных кривых, некоторые из которых будут рассмотрены в данной статье, а также будет произведен их сравнительный анализ.

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

Алгоритм нахождения ключевых точек.

Шаг 1. Выполняется предобработка изображения, цель которой подавить шумы и удалить незначащую информацию (мелкие делатели, например, движущиеся по дороге автомобили).

Шаг 2. Выполняется выделение контуров методом, предложенным в [9, 13].

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

Шаг 4. Клиниям контура, которые теперь описаны в виде цепочек декартовых координат, применяется один из трех методов нахождения ключевых точек:

− Экстремумы расстояний точек кривой от ее центроида;

− Резкие перепады кривизны кривой;

− Аппроксимация кривой ломаной линией на основе метода наименьших квадратов.

Более подробно данные алгоритмы будут описаны в главе «Подходы к нахождению ключевых точек».

Обоснование выбора метода предобработки изображений.

В качестве метода предобработки рассмотрены три варианта:

− Размытие фильтром Гаусса.

− Медианная фильтрация.

− Сигма-фильтрация.

Размытие фильтром Гаусса состоит в свертке изображения с ядром фильтра, которое вычисляется по формуле:

(1)

где x, y координаты точки в ядре фильтре (маске), – среднеквадратичное отклонение [4, 5]. Недостатком данной предобработки является тот факт, что мелкие детали из изображения не удаляются, они просто превращаются в пятна (рис. 1).

Рис. 1. Эффект применения фильтра Гаусса

В отличии от размытия изображения Гаусс фильтром, медианная фильтрация не дает эффект расфокусировки, хотя в некоторых случаях слегка размывает границы. Кроме того, медианная фильтрация способна удалять из изображения мелкие незначимые детали, а также шум «соль и перец» и импульсные шумы (рис. 2).

Математически медианную фильтрацию можно выразить формулой:

(2)

где – оператор, выделяющий медиану сигнала, — функция яркости пикселя изображения [5]

Рис. 2. Эффект применения медианной фильтрации

Рис. 3. Эффект применения сигма-фильтрации

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

Сигма фильтрация выполняется следующим образом: сначала строиться гистограмма распределения яркости пикселей в скользящем окне. По ней находиться наиболее вероятное значение (как точка максимума гистограммы). Далее, по формуле вычисляется среднеквадратичное отклонение:

(3)

где N — количество столбцов в гистограмме, – яркость пикселя, соответствующая столбцу k – гистограммы, M — наиболее вероятное значение яркости [4, 5].

Если яркость рассматриваемого пикселя попадает в диапазон:

(4)

где k — некая эмпирическая константа, обычно принимающая значения от 1 до 3, то данный пиксель остается без изменения, иначе его яркость устанавливается в M [5, 6].

Эффект от применения сигма фильтрации праведен на рис. 3.

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

Подходы кнахождению ключевых точек.

В данной статье будут рассмотрены перечисленные в главе «Алгоритм нахождения ключевых точек» способы выделения ключевых точек.

Экстремумы расстояний точек кривой от ее центроида. Вкачестве центроида используется центр масс кривой, координаты которого можно вычислить по следующим формулам:

(5)

(6)

где – координата x точки кривой, — координата y точки кривой, n — количество точек кривой.

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

(7)

где и координаты точки [5].

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

Угол между векторами определятся по формуле:

(8)

где — скалярное произведение векторов и [5].

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

Построение прямой методом наименьших квадратов сводится к решению системы линейных уравнений:

(9)

где i — индекс точки, n — количество точек, и — координаты каждой точки [5, 14].

Результаты экспериментов.

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

Контур был выделен методом, предложенным в работах [9, 13]. Образец контура для используемого изображения приведен на рис. 5.

Рис. 4. Исходное изображение

Рис. 5. Образец контура

Эксперименты проводились на наиболее длинной кривой контура, см. рис. 6.

Рис. 6. Часть контура для тестирования алгоритма

Рис. 7. Ключевые точки первого алгоритма

Ключевые точки, которые нашел алгоритм на основе экстремумов расстояний точек кривой от ее центроида показаны на рис. 7.

Ключевые точки, которые нашел алгоритм на основе резких перепадов кривизны кривой показаны на рис. 8. Ключевые точки, которые нашел алгоритм на основе аппроксимации кривой ломаной линией на основе метода наименьших квадратов показаны на рис. 9.

Рис. 8. Ключевые точки второго алгоритма

Рис. 9. Ключевые точки третьего алгоритма

Заключение.

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

− Метода на основе экстремумов расстояний точек кривой от ее центроида;

− Метод на основе резких перепадов кривизны кривой;

− Метод аппроксимация кривой ломаной линией на основе метода наименьших квадратов.

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

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

Литература:

1. Holk Cruse, Malte Schilling States as Emergent Properties. Статья в Интернете [Электронный ресурс]. Режим доступа: http://open-mind.net/papers/mental-states-as-emergent-properties-from-walking-to-consciousness# свободный (дата обращения 19.02.2016).
2. Стюарт Рассел, Питер Норвиг, «Искусственный интеллект. Современный подход». Издательство Вильямс, 2016. – 1408 с.: ил.
3. Визильтер Ю. В., Желтов С. Ю. Проблемы технического зрения в современных авиационных системах // Техническое зрение в системах управления мобильными объектами 2010: Труды научно-технической конференции-семинара. Вып. 4 / Под ред. Р. Р. Назирова. — М.: КДУ, 2011. — С. 11–44.
4. Д. Форсайт, Ж. Понс, Компьютерное зрение. Современный подход, Москва, 2004, 465 с.
5. Gonzalez R, Woods R, Digital image processing. Published by Pearson Education Inc, Publishing as Prentice Hall, 2002, p. 1072
6. B. K. P. Horn, Robot Vision, The Mit Press, 1989, 488 p.
7. Canny J. A Computational Approach to Edge Detection // IEEE Transaction on Pattern Analysis and Machine Intelligence. — 1986. — Vol. PAMI-8 № 6 — pp. 679–698.
8. Shuravin A. P, статья «Reviw of image Edge Detection Methods in Computer Vision Problems», «IV Всеросийская научно-техническая конференция аспирантов, магистрантов и молодых ученых с международным участием: «Молодые ученые — ускорению научно-технического прогресса в XXI-ом веке», Ижевск, 20–21 апреля 2016 года, Сборник материалов конференции, стр. 1020–1024.
9. Архипов И. О., Мурынов А. И., Юферев Д. А. Построение контуров структурных элементов графического изображения на основе метода наименьших квадратов // Вестник ИжГТУ им. М. Т. Калашникова. — 2015. — № 4(68). — С. 60–64.
10. Сакович И. О., Белов Ю. С. Обзор основных методов контурного анализа для выделения контуров движущихся объектов. Инженерный журнал: наука и инновации, 2014, вып. 12. URL: http://engjournal.ru/catalog/it/hidden/1280.html.
11. Максимов А. Н., Еланцев М. О., Архипов И. О., Широков В. А. Сопоставление характерных точек на последовательных кадрах в задачах аэронавигации по зрительным образам // Молодые ученые — ускорению научно-технического прогресса в XXI веке сборник материалов IV Всероссийской научно-технической конференции аспирантов, магистрантов и молодых ученых с международным участием. — Ижевск: ИННОВА, 2016. — С. 428–432.
12. Архипов И. О., Еланцев М. О. Методика определения координат летательного аппарата по зрительным образам // Интеллектуальные системы в производстве. — 2016. — № 4(31). — С. 4–7.
13. Архипов И. О., Еланцев М. О. Двунаправленный алгоритм обхода контурного препарата // Вестник ИжГТУ им. М. Т. Калашникова. — 2016. — № 2(70). — С. 107–109.
14. Орлов А. И. Восстановление зависимости методом наименьших квадратов на основе непараметрической модели с периодической составляющей // Научный журнал КубГАУ. — 2013. — № 91(07). — С. 1–30.