Программные продукты и системы

Анализ геоснимков – долгий и трудоемкий процесс. Поиск нужного объекта геологом на изображениях, охватывающих большие территории, является обычным для такого рода задач. Продуктивность действий обратно пропорциональна усталости человека, поэтому процесс занимает очень много времени и приходится идти на уступки. Например, Яндекс создал так называемую «народную карту», где пользователи могут создавать векторные объекты: дороги, здания, парковки и т.п., тем самым улучшая сервисы Яндекс.Карта и Яндекс.Навигатор.

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

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

Структура программного комплекса

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

Данная программа использует максимально простые форматы хранения данных (JSON, PNG, JPG), чтобы предоставить возможность простой интеграции с любой другой программой. Разработка написана на языке программирования С++ с использованием библиотек QT (графика, сохранение в формате JSON) и OpenCV (работа с изображениями).

Структура программного комплекса показана на рисунке 1.

Выявление областей интереса

Задачу поиска конкретных объектов на изображении можно разделить на два этапа: непосредственно выделение всех потенциальных объектов на снимке и отсеивание ненужных объектов.

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

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

Баркоды как характеристика пространственного объекта на изображении

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

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

Классический вариант формирования бар­кода для набора точечных объектов описан в работах [6–8]. В случае растрового изображения существуют адаптированные под этот формат алгоритмы [9, 10]. Каждый отдельный пиксель можно оценивать как отдельную вершину, а разницу яркости между ними – как расстояние. Но, в отличие от классического метода, здесь вместо продолжительности существования компоненты используются числа Бетти. Их принято обозначать β0, β1, β2 и т.д., и они будут содержать количество своих компонент на каждой итерации. Под итерацией понимается яркость: на одной итерации обрабатываются все пиксели с соответствующей яркостью. Данный процесс показан на рисунке 2, где каждая черная область – компонента. Для наглядности изображения на снимках под буквами в, д, ж, и, к, м инвертированы.

Компонента β0 представляет собой простейшую фигуру – точку. При появлении новой точки появляется и компонента. Если вершина появилась рядом с компонентой, то она сразу же сливается с ней. Возможны варианты, когда появление точки может спровоцировать слияние двух или даже трех крупных компонент. В таком случае остается лишь наиболее крупная, остальные исчезают, будучи поглощенными. В итоге останется только одна мега-компонента.

Компонента β1 состоит из так называемых дыр. Они строятся схожим образом, но с учетом некоторых отличий:

-  проход начинается с 255-й яркости;

-     дыры формируются только в случае, если рядом находятся три точки, образуя при этом треугольник;

-     дыры сливаются лишь тогда, когда у них образуется общее ребро;

-     если у компоненты образовалось общее ребро с одной из сторон крайних пикселей, то она исчезнет;

-     если другая компонента сольется с уже исчезнувшей, то она сама исчезнет;

-     в конце не останется ни одной дыры, так как все они соединятся друг с другом и с контуром, таким образом исчезнув.

В результате для каждой компоненты получится 256 значений, характеризующих изображение. Сами по себе эти значения уже являются сильной характеристикой, и даже такая простая величина, как отношение максимума из β1 к максимуму из β0, может быть использована для оценки схожести изображений.

Исследование показало, что компонента β1 является более сильной характеристикой. Единственная важность компоненты β0 заключается в том, что она анализирует изображение в обратном порядке относительно β1. Процесс прямого преобразования показан на рисунке 2 (б, г, е, з, й, л). Начиная с 2 (з) компоненты только поглощают оставшуюся область, не делая вклад в баркод, поэтому необходимо проводить обработку в обратном порядке, что и показано на рисунке 2 (в, д, ж, и, к, м).

Замена β0 на обратную β1 усилит характеристику, но существует еще одно возможное улучшение. Как нетрудно заметить, компоненты перестают появляться именно после поглощения фона, что, впрочем, весьма логично. Из этого следует, что изображение можно разделить на три части: яркая часть объекта, фон и темная область объекта. Обозначим начало и конец яркости фона F1 и F2. Таким образом, баркод можно будет построить, начиная с 0-й яркости и до F1, продолжить с 255-й яркости до F2 и закончить с F2 до F1.

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

Сравнение баркодов

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

Каждое число в характеристике означает количество живых дыр на каждой яркости. На графике (рис. 3 (а)) это можно представить как вертикальные отрезки.

Однако под баркодом подразумевают имен­но горизонтальные отрезки, поэтому необходимо преобразовать вертикальные отрезки в горизонтальные (рис. 3 (б)). Для этого достаточно просто «срезать» каждый слой на каждой вертикальной отметке и поместить отдельные отрезки на отдельные уровни (рис. 3 (в)).

Само же сравнение можно делать по-разному. Фиксированный размер характеристики (256 чисел) идеально подошел бы для нейросетевого классификатора, хотя можно пойти дальше и извлечь признаки уже из баркода с помощью методов датамайнинга.

Сравнение баркодов сводится к сравнению отрезков компонент друг с другом. Прежде всего стоит уделить внимание предобработке отрезков баркода. Сначала необходимо отсеять «мусор» в виде мелких отрезков, чья длина слишком мала, чтобы сделать вклад в итоговую характеристику. Пример отсеивания показан на рисунке 4.

Также следует учитывать такой факт, как яркость изображения. Снимки делаются в разное время и при разной освещенности, поэтому даже в один снимок может попасть местность из двух разных промежутков времени (рис. 5 (а, б)). Так что, при сравнении отрезков можно использовать относительную продолжительность их существования. Ее суть заключается в том, что берется начало появления дыры, которая стала существовать раньше всех, и вычитается из всех дыр. Таким образом, баркоды у светлого объекта (рис. 6 (а)) и темного (рис. 6 (б)) будут одинаковыми (рис. 6 (в)) после нормализации, а возможная погрешность уйдет вместе с порогом шума.

Рассмотрим пример сравнения двух баркодов (рис. 7). Для оценки их схожести сначала следует рассчитать общую сумму всех отрезков (в данном случае она равна 25). Это необходимо для определения вклада каждого отрезка. Затем нужно отсортировать отрезки в каждом баркоде по убыванию, чтобы можно было приступить к сравнению. Первыми срав-ниваются отрезки AB и CD. Их суммарный вклад будет равен 72 % (18/25).

Следующий шаг – расчет отношения пересечения отрезков. Для этого необходимо взять их общую зону пересечения, которая будет равна длине отрезка M1M2, где M1 = max(A, C), а M2 = min(B, D). Получившийся отрезок необходимо разделить на наибольшую из длин сравниваемых отрезков, то есть max(AB, CD). На рисунке 7 длина отрезка M1M2 равна 7, CD длиннее AB, максимальная длина равна 10.

Зная длины, можно определить процент схожести отрезков: (длина M1M2)/max(AB, CD) = 0,7. Данный результат умножается на вклад этих отрезков, то есть на 72 %: 0,7×0,72 = = 0,504. Алгоритм применяется для каждой пары отрезков.

Результатом схожести двух баркодов будет сумма всех оценок схожестей. В рассматриваемом случае она равна 71 %: 0,504 + 0,21 = = 0,714.

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

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

Поиск объектов на геоснимках

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

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

Эталонный объект можно загрузить либо с компьютера, либо прямо из списка найденных. Чем больше уникальных эталонов, тем выше точность сравнения. Загруженные эталоны будут использоваться для поиска айсбергов (см. http://www.swsys.ru/uploaded/image/2021-1/2021-1-dop/5.jpg).

При сравнении алгоритм возвращает коэффициент схожести, поэтому пользователю необходимо выбрать минимально необходимую схожесть объекта (см. http://www.swsys.ru/uploaded/image/2021-1/2021-1-dop/6.jpg).

Стоит напомнить, что баркоды похожи на SimHash: если объекты кардинально разные, то схожесть их баркодов будет приближена к нулю, в то время как для хоть немного схожих объектов коэффициент схожести может начинаться уже с 15–20 % (см. http://www.swsys.ru/uploaded/image/2021-1/2021-1-dop/7.jpg).

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

Заключение

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

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

Литература

1.    Визильтер Ю.В., Горбацевич В.С., Вишняков Б.В., Сидякин С.В. Поиск объектов на изображении с использованием морфлетных описаний // Компьютерная оптика. 2017. Т. 41. № 3. С. 406–411. DOI: 10.18287/2412-6179-2017-41-3-406-411.

2.    Денисова А.Ю., Мясников В.В. Обнаружение аномалий на гиперспектральных изображениях // Компьютерная оптика. 2014. Т. 38. № 2. С. 287–296.

3.    Magdeev R.G., Tashlinskii A.G. A comparative analysis of the efficiency of the stochastic gradient approach to the identification of objects in binary images. Pattern Recognition and Image Analysis, 2014, vol. 24, no. 4, pp. 535–541. DOI: 10.1134/S1054661814040130.

4.    Sadowski C., Levin G. SimHash: Hash-Based Similarity Detection. 2007. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.473.7179&rep=rep1&type=pdf (дата обращения: 03.08.2020).

5.    Xu Y., Qi L. SimHash-based similar neighbor finding for scalable and privacy-preserving service recommendation. Lecture Notes in Computer Science, 2017, vol. 10603, pp. 113–122.

6.    Carlsson G. Topological pattern recognition for point cloud data. Acta Numerica, 2014, vol. 23, pp. 289–368. DOI: 10.1017/S0962492914000051.

7.    Edelsbrunner H., Harer J. Computational Topology: An Introduction. 2009, 282 p.

8.    Еремеев С.В., Андрианов Д.Е., Титов В.С. Алгоритм совмещения пространственных объектов разномасштабных карт на основе топологического анализа // Компьютерная оптика. 2019. Т. 43. № 6. C. 1021–1029. DOI: 10.18287/2412-6179-2019-43-6-1021-1029.

9.    Макаренко Н.Г., Уртьев Ф.А., Князева И.С., Малкова Д.Б., Пак И.Т., Каримова Л.М. Распознавание текстур на цифровых изображениях методами вычислительной топологии // Современные проблемы дистанционного зондирования Земли из космоса. 2015. Т. 12. № 1. С. 131–144.

10. Еремеев С.В., Романов С.А. Алгоритм сегментации изображений на основе персистентной гомологии для решения задач поиска дефектов // Изв. Юго-Западного гос. ун-та. 2020. Т. 24. № 1. С. 144–158. DOI: 10.21869/2223-1560-2020-24-1-144-158.

References

1. Vizilter Yu.V., Gorbatsevich V.S., Vishnyakov B.V., Sidyakin S.V. Object detection in morphlet descriptions. Computer Optics, 2017, vol. 41, no. 3, pp. 406–411 (in Russ.). DOI: 10.18287/2412-6179-2017-41-3-406-411.
2. Denisova A.Yu., Myasnikov V.V. Anomaly detection for hyperspectral imaginary. Computer Optics, 2014, vol. 38, no. 2, pp. 287–296 (in Russ.).
3. Magdeev R.G., Tashlinskii A.G. A comparative analysis of the efficiency of the stochastic gradient approach to the identification of objects in binary images. Pattern Recognition and Image Analysis, 2014,
   vol. 24, no. 4, pp. 535–541. DOI: 10.1134/S1054661814040130.
4. Sadowski C., Levin G. SimHash: Hash-Based Similarity Detection. 2007. Available at: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.473.7179&rep=rep1&type=pdf (accessed August 3, 2020).
5. Xu Y., Qi L. SimHash-based similar neighbor finding for scalable and privacy-preserving service recommendation. Lecture Notes in Computer Science, 2017, vol. 10603, pp. 113–122.
6. Carlsson G. Topological pattern recognition for point cloud data. Acta Numerica, 2014, vol. 23,
   pp. 289–368. DOI: 10.1017/S0962492914000051.
7. Edelsbrunner H., Harer J. Computational Topology: An Introduction. 2009, 282 p.
8. Eremeev S.V., Andrianov D.E., Titov V.S. An algorithm for matching spatial objects of different-scale maps based on topological data analysis. Computer Optics, 2019, vol. 43, no. 6, pp. 1021–1029 (in Russ.). DOI: 10.18287/2412-6179-2019-43-6-1021-1029.
9. Makarenko N.G., Urtiev F.A., Knyazeva I.S., Malkova D.B., Pak I.T., Karimova L.M. Texture recognition in digital images by computational topology methods. Sovr. Probl. DZZ Kosm., 2015, vol. 12, no. 1,
   pp. 131–144 (in Russ.).
10. Eremeev S.V., Romanov S.A. An algorithm of image segmentation based on persistent homology for solving defects searching problems. Proceedings of the Southwest State University, 2020, vol. 24, no. 1,
    pp. 144–158 (in Russ.). DOI: 10.21869/2223-1560-2020-24-1-144-158.