Probabilistic algorithm for the verification of the location of fragments with consideration of relative placement in a series of images

Full Text

Исследование быстро изменяющегося информационного поля, представленного в виде серии снимков или видеопотока земной поверхности, требует выполнения ряда трудоемких задач. Одной из основных задач является определение местоположения видеокамеры относительно характерных фрагментов (объектов), расположенных на расстоянии, превышающем размер одного снимка. Вычисленное местоположение камеры позволит отследить маршрут ее перемещения до текущего характерного объекта, скорректировать существующий или задать новый маршрут движения по информационному полю. В случае правильной привязки к нескольким объектам появляется возможность предсказать появление объектов, расположенных дальше по маршруту. Быстрое изменение формы, цвета, освещенности объектов, связанное с погодными условиями, временами года, текущим расположением естественных источников света, обуславливает динамичность информационного поля и не позволяет использовать системы, требующие длительного времени обучения и предварительной обработки искомых объектов. Для решения поставленной задачи необходимо провести поиск одновременно нескольких характерных объектов, представленных в виде набора фрагментов малого размера, в серии полученных изображений с указанием их расположения относительно камеры. При известных абсолютных координатах минимум трех фрагментов (в системе глобальных координат информационного поля) можно вычислить текущее положение видеокамеры относительно любой точки исследуемого пространства. При поиске одиночного объекта широко используется корреляционный метод. Он сводится к вычислению взаимной корреляции искомого объекта и полученного изображения. При значениях, превышающих минимальный порог корреляции, сравниваемые изображения считаются идентичными [1]. Корреляционный метод обладает высоким быстродействием и позволяет найти и идентифицировать искомый фрагмент по одному кадру, однако под действием затрудняющих распознавание факторов (погодные условия, изменение освещенности, шум) вероятность правильной идентификации невелика [4]. Не менее распространенным методом поиска является использование искусственных нейронных сетей (ИНС). Данный метод основывается на извлечении существенных свойств изображений и построении на их основе сигнатур (обучение ИНС), используемых в дальнейшем для сравнения пар изображений [9]. Достаточно подробные описания построения и применения ИНС в системах цифровой обработки изображений представлены в работах [10-12]. Несмотря на широкий спектр возможностей и высокие показатели точностных характеристик, известные методы полностью не решают поставленную задачу. Идентификация объектов по одному снимку не позволяет однозначно и точно определить местоположения камеры на изменяющемся информационном поле. Для решения поставленной задачи предлагается использовать ограниченную серию снимков. Суть предлагаемого алгоритма заключается в том, что на каждом кадре в серии снимков каким-либо методом [5-7, 13] определяются предположительные координаты всех искомых фрагментов относительно верхнего левого угла первого снимка серии (рис. 1, точка О, абсолютные координаты, А). Далее вычисляются расстояния между всеми найденными фрагментами. Фрагменты, расстояния между которыми совпадают с заранее известными и абсолютные координаты которых не изменяются на протяжении наибольшего числа снимков, следующих друг за другом, считаются идентифицированными, остальные фрагменты считаются отсутствующими в текущей серии снимков. Рассмотрим расположение четырех характерных фрагментов 1, 2, 3, 4 на серии из N снимков с взаимными расстояниями между ними S12, S13, S14, S23, S24, S34 (см. рис. 1). Снимки обозначены пунктирными линиями. На снимке характерные фрагменты могут отсутствовать (снимок III), присутствовать по отдельности (снимок IV) и вместе (снимок I). Снимки в серии могут пересекаться, как снимки I, II и III, IV, и не пересекаться, как снимки II, III. Фрагменты могут присутствовать в текущей серии снимков (фрагменты 1, 2, 3) и отсутствовать (фрагмент 4). Основной алгоритм включает в себя четыре блока обработки информации (рис. 2). При вычислении элементов матрицы A абсолютных координат относительные координаты фрагмента x0 и y0 на текущем снимке суммируются с перемещением предыдущих снимков rx и ry (см. рис. 1). Т. е. вычисляются координаты каждого найденного фрагмента относительно верхнего левого угла кадра 1 в системе координат X, Y (см. рис. 1) для всей последовательности снимков j = 1, 2, …, N: Вычислив абсолютные координаты для всех выделенных характерных фрагментов в серии снимков, получаем последовательности N пар координат, из которых формируется матрица А: где i - порядковый номер искомого фрагмента; n - количество искомых фрагментов. Рис. 1. Пример расположения искомых фрагментов в серии снимков Так как возможно наличие ложно обнаруженных фрагментов, что связано с несовершенством методов поиска, то необходимо провести анализ изменения координат найденного фрагмента между текущим и предыдущим кадрами. Отсутствие изменения абсолютных координат в последовательности снимков указывает на присутствие характерного фрагмента i в одной и той же точке пространства A(xij,yij). Для определения наиболее вероятных координат фрагментов формируется множество Bi = {(Ciu,piu)}, состоящее из элементов, представляющих собой пару из координат фрагмента Ciu и ее вероятности piu, определяющей количество снимков, на которых фрагмент обнаруживался в точке Ciu, где u - порядковый номер пары. Элементы множества Bi вычисляются следующим образом: Ci1 = Ai1; pi1 = 1. Для всех j = 2, 3, …, N и u = 1, 2, …, z, где z - количество пар во множестве Bi на шаге j. Если евклидова норма где e - максимально возможное расстояние между изображениями одного и того же искомого фрагмента на разных снимках, то иначе выбирается элемент множества Bi (существующая пара), для которого минимальна, и пересчитываются его компоненты Ciu и piu: Таким образом, вероятность piu увеличивается при обнаружении фрагмента в одной и той же точке информационного поля. Для уменьшения количества вычислений из множества Bi исключаются элементы с малой вероятностью piu, а оставшиеся элементы упорядочиваются по убыванию по второму параметру piu и укладываются в строку i матрицы С: , где Упорядоченные координаты фрагментов укладываются в строку i матрицы С: где s - количество столбцов матрицы С, выбираемое вблизи значения N/10. Сильное уменьшение данного параметра ведет к увеличению вероятности не идентифицировать ни одного фрагмента, а увеличение - к возможности неправильной идентификации всех фрагментов На следующем этапе обработки (см. рис. 2) происходит вычисление расстояний между найденными объектами, которые сравниваются с известными эталонными расстояниями S (см. рис. 1). Для удобства обработки известные расстояния между фрагментами записываются в матрицу S в следующем виде: где Sil = Sli. Рис. 2. Схема подтверждения координат искомых фрагментов Для идентификации найденных фрагментов вычисляются все возможные расстояния между ними и сравниваются с известными. Если хотя бы для одной пары k, p, где i, l (i ≠ l) - номер строки, а k, p - номер столбца матрицы C, то идентификация останавливается и координатами фрагмента i считаются Cik, а фрагмента l - Clp, иначе принимается решение об отсутствии фрагментов в текущей серии снимков. Идентифицированные координаты записываются в вектор-столбец D, в котором номер строки соответствует порядковому номеру искомого фрагмента: Если искомый фрагмент отсутствует в текущей серии снимков, то вместо его координат записывается пара чисел, означающая отсутствие фрагмента. Предложенный алгоритм подтверждения местоположения протестирован в составе системы поиска [2] фрагментов в серии снимков земной поверхности, на которых присутствовали как искомые фрагменты, так и не входящие в набор тестовых изображений объекты. Расстояние между текущим и следующим снимками серии не превышало 0,3 их размеров, размеры фрагментов h и снимков H составили 64×64 и 512×512 пикселей соответственно, количество снимков в серии равно 30, количество серий - 10. Оценка вероятности правильной идентификации производилась в параметрах чувствительности Se - отношение количества правильно идентифицированных фрагментов к общему числу фрагментов, присутствующих в серии снимков, и специфичности Sp - отношение количества правильно идентифицированных фрагментов к общему числу идентифицированных фрагментов (правильных и ложных) [3]. При поиске двух характерных фрагментов быстрыми корреляционными методами независимо друг от друга, без учета расстояний между ними чувствительность и специфичность равны 0,65 и 0,17 соответственно [8]. Таким образом, при независимом поиске количество правильно идентифицированных фрагментов мало. Кроме того, с увеличением количества искомых фрагментов число одновременно правильно идентифицированных фрагментов снижается, а ложных - растет. Разработанный алгоритм, учитывающий расстояния между характерными фрагментами, позволил увеличить показатель специфичности до 0,68 при нахождении обоих искомых фрагментов на одном снимке и до 0,88 при расстоянии между фрагментами больше размера снимка. Экспериментальные исследования показали, что при увеличении количества идентифицированных фрагментов в одной серии снимков увеличивается чувствительность и специфичность при условии, что количество идентифицированных фрагментов на одном снимке не более одного. При идентификации большого количества фрагментов на одном снимке, т. е. когда расстояние между искомыми фрагментами достаточно мало, показатели чувствительности и специфичности, представленные в таблице, снижаются. Это связано с тем, что алгоритм поиска выделяет наиболее похожие на фрагменты области на каждом из снимков, и при малом расстоянии между искомыми фрагментами выше вероятность того, что расстояние между двумя ложно найденными фрагментами совпадет с известным, и происходит идентификация по одному снимку (без учета остальных кадров серии). Влияние количества искомых фрагментов на чувствительно и специфичность № п/п Количество фрагментов Расстояния между фрагментами, Sij Sij > H h < Sij < H Se Sp Se Sp 1 2 0,9 0,88 0,71 0,68 2 3 0,98 0,97 0,8 0,77 3 4 0,99 0,99 0,85 0,81 4 5 0,99 0,99 0,85 0,83 5 6 0,99 0,99 0,88 0,87 На рис. 3 представлен график зависимости времени поиска местоположения камеры от количества искомых фрагментов. Время нормировано относительно времени идентификации двух характерных фрагментов. Полученная зависимость имеет вид функции , скорость изменения которой с увеличением g уменьшается. Таким образом, увеличение количества искомых фрагментов в малой степени влияет на время поиска. Также было выяснено, что одновременное нахождение нескольких характерных фрагментов на одном снимке не влияет на время их идентификации. Рис. 3. Зависимость времени поиска от количества искомых фрагментов Результаты Применение разработанного алгоритма в системе поиска повысило показатель специфичности относительно системы, не использующей серию снимков, более чем в 2 раза, а при большом количестве идентифицированных фрагментов, расстояния между которыми больше размера снимка, показатели чувствительности и специфичности близки к 1. Предложенный алгоритм соответствует современному уровню развития науки по качеству распознавания [14, 15], в том числе показателям методов, использующих ИНС [13]. Кроме того, алгоритм подтверждения делает возможным однозначное определения местоположения видеокамеры, что повышает скорость адаптации системы анализа информационных полей к быстро изменяющимся областям поиска. Еще одним преимуществом является возможность выполнения разработанного алгоритма параллельно с получением очередной серии снимков, что уменьшает общее время местоопределения. Разработанный алгоритм может применяться в системах ориентации на местности по снимкам земной поверхности беспилотных летательных аппаратов, в системах компьютерного зрения при движении роботизированной техники.

About the authors

Ivan A Burtsev

P.A. Solovyov Rybinsk State Aviation Technical University

Postgraduate Student 53, Pushkin st., Rybinsk, Yaroslavl oblast, 152934, Russian Federation

References

Supplementary files