Программирование, 2019, № 6, стр. 3-12

1. ВВЕДЕНИЕ

Задача дешифрирования аэрокосмических снимков состоит в поиске объектов интереса на фотографиях большого размера, определении положения и класса обнаруженных объектов. Задача эта является актуальной для многих приложений [1–4]. Важную роль в классификации объектов играет анализ их формы. В частности это относится к поиску и определению типа самолетов, наблюдаемых на аэрокосмических снимках (рис. 1). Количество типов самолетов достаточно велико, до сотни наименований, их вид на изображениях изменяется в очень широких пределах в зависимости от окружающего фона и освещенности, но опытный оператор-дешифровщик весьма уверенно может находить и классифицировать найденные объекты по их форме. Однако при таком “ручном” дешифрировании требуются неприемлемо большие человеческие ресурсы для обработки огромных объемов видеоинформации, производимой современными системами наблюдения. Для того чтобы справиться с нарастающим потоком данных аэрокосмической съемки необходимо автоматизировать труд оператора-дешифровщика.

Рис. 1.

Примеры изображений самолетов на аэрокосмических снимках.

Дешифрирование включает решение двух основных задач: поиск объектов определенного вида на аэрокосмических снимках большого размера (задача детектирования) и определения класса найденных объектов (задача классификации). При решении задачи детектирования и классификации самолетов на изображениях столь большого размера традиционные методы поиска объектов заданной формы [5–7] оказываются неэффективными. Новые возможности для исследования и разработки методов решения данных задач открывает применение машинного обучения, в частности, с использованием нейронных сетей [8–10]. Для машинного обучения требуется подготовка соответствующей обучающей информации. Эта информация имеет достаточно большой объем и подготовка ее, как правило, требует значительных трудозатрат.

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

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

2. ЗАДАЧА СЕГМЕНТАЦИИ ИЗОБРАЖЕНИЙ САМОЛЕТОВ

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

Рис. 2.

Фрагменты исходных аэрокосмических снимков (верхний ряд) и размеченные изображения объектов (нижний ряд).

Известные подходы к выполнению сегментации аэрокосмических снимков имеют разный уровень автоматизации процесса разметки, и различаются по качеству сегментации и требуемым трудозатратам. Для решения задачи сегментации могут быть использованы универсальные методы интерактивной сегментации объектов, в частности, ставший классическим алгоритм GrabCut [11, 12]. На рис. 3 приведены примеры применения этого метода с использованием программного обеспечения [13] для нескольких фрагментов аэрокосмических снимков. Примеры показывают низкое качество получаемых сегментов. Таким образом, использование алгоритма GrabCut не позволяет рассчитывать на полностью автоматическое сегментирование. При этом объем остающейся ручной работы асессора по ручной доводке результата представляется таким же как при работе с исходными изображениями. Кроме того, работа алгоритма GrabCut требует существенных ресурсов времени. Затраты на обработку каждого из примера на рис. 3 составили 1–2 минуты.

Рис. 3.

Сегментация аэрокосмических снимков алгоритмом GrabCut (верхний ряд – исходные изображения самолетов, нижний ряд – результаты сегментации).

Для решения задач ручной сегментации существуют специализированные редакторы, обеспечивающие работу с различными изображениями. Примером является универсальная система [14]. Редактор содержит набор инструментов, позволяющих отметить непосредственно на изображении пикселы, относящиеся к объекту интереса (рис. 4). Для этого используются как растровые инструменты (перо, кисть, заливка), так и инструменты векторной графики (полилинии, многоугольники).

Рис. 4.

Ручная разметка границы объекта с помощью графического редактора.

Этот набор инструментов в целом дает возможность построить точную сегментацию, однако на практике он обеспечивает приемлемую точность лишь для контрастных изображений. Если граница объекта хорошо видна, асессор легко может ее разметить. Но на аэрокосмических снимках весьма часто контрастной является лишь часть границы объекта. При этом другая часть объекта скрывается в тени либо сливается с окружающим фоном (рис. 5). В этом случае точность ручной сегментации оказывается низкой, поскольку визуально положение границы определяется с большими ошибками, обусловленными как низкой контрастностью, так и малыми размерами объектов при невысоком разрешении снимков. Поэтому разметка изображений с помощью графических инструментов оказывается весьма неэффективной, приводит к ошибкам и неприемлемо большим затратам труда и времени. Значительные вариации контрастности изображений, в том числе на одном и том же снимке, не позволяют использовать для решения задачи метод активных контуров [2]. Таким образом, разработка методов разметки, обеспечивающих приемлемую точность, а также высокую скорость этого процесса является актуальной задачей.

Рис. 5.

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

3. МЕТОД РАЗМЕТКИ НА ОСНОВЕ ВЕКТОРНЫХ ШАБЛОНОВ

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

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

Первый этап – подготовка базы эталонов – осуществляется на основе высококачественных изображений объектов, полученных либо по фотографиям с высоким разрешением, либо из описаний в технической документации. На рис. 6а приведены примеры таких изображений нескольких самолетов (B-52, C-20, F-22, P-3), полученные из технической документации, находящейся в свободном доступе в интернете. На основе таких описаний могут быть получены силуэты объектов в виде растровых бинарных изображений высокого разрешения (рис. 6б). Такое изображение должно в максимальной степени отражать все существенные особенности формы объекта. В данном примере растровые изображения силуэтов самолетов имеют размеры 600 × 700 пикселей. При этом не требуется их растеризация в едином масштабе, каждая модель представляется в том масштабе, который позволяет воспроизвести все существенные элементы формы. Построение растровых силуэтных моделей по чертежам осуществляется в графическом редакторе и не составляет большого труда.

Рис. 6.

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

Далее на основе полученного растрового описания силуэта объекта создается контурная модель формы в виде многоугольника (рис. 6в). Контурное описание маркируется указателем типа объекта и помещается в базу эталонов.

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

− визуальный анализ исходного аэрокосмического снимка. Асессор находит на снимке объекты интереса и далее использует предлагаемые инструменты для разметки этих объектов (размечает рамкой для детектирования);

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

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

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

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

4. ПОСТРОЕНИЕ КОНТУРНЫХ ЭТАЛОННЫХ МОДЕЛЕЙ САМОЛЕТОВ

Описанная выше процедура оперирует с эталонными контурными описаниями объектов, которые должны быть получены и собраны в базе эталонов. Для построения контурной модели предлагается использовать алгоритм, идея которого описана в работе [15]. Входом алгоритма является растровое бинарное изображение, выходом – описание контура границы объекта в виде многоугольника. Пример на рис. 7 иллюстрирует идею, лежащую в основе алгоритма. Для наглядности визуализации растровое изображение объекта из рис. 7 (самолет F-22) представлено в более низком разрешении, не 600 × 700, а 60 × 70 пикселей (рис. 7а).

Рис. 7.

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

Построение контурной модели включает поиск и прослеживание границ растровой фигуры, и построение так называемого разделяющего многоугольника минимального периметра. Выбор многоугольника в качестве основной модели для аппроксимации границ цифрового изображения мотивируется тем, что такое описание имеет простую структуру и при этом обеспечивает необходимую точность аппроксимации границы бинарного образа. Задача состоит в том, чтобы на основании исходного бинарного растрового изображения (рис. 7a) построить аппроксимирующий многоугольник (рис. 7г). Многоугольник должен удовлетворять двум требованиям. Во-первых, он должен аппроксимировать цифровой прообраз с высокой точностью, а во-вторых, он должен быть простым, т.е. не должен иметь самопересечений. Предлагаемый метод обеспечивает выполнение этих требований.

Метод основан на следующих принципах:

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

– на решетке Z  ² вводится треугольная структура соседства. Граф соседства представляет собой триангуляцию, образованную путем разделения квадратных ячеек целочисленной решетки диагоналями. Множество всех треугольных ячеек с разноцветными вершинами образует кольцевую полосу, называемую граничным коридором (рис. 7в);

– среди всех замкнутых контуров, лежащих внутри граничного коридора, выбирается линия минимальной длины. Эта линия имеет форму простого многоугольника. Выпуклые вершины многоугольника – это черные пиксели, вогнутые – белые. Многоугольник разделяет черные и белые пиксели граничного коридора. Он называется разделяющим многоугольником минимального периметра (рис. 6г).

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

Для получения граничного коридора используются алгоритмы трассировки границы бинарного изображения [15]. Один из вариантов такой трассировки, называемый симплекс-прослеживанием, представлен на примере (рис. 8). Для бинарного изображения (рис. 8а) рассматривается целочисленная решетка, в которой узлы являются центрами пикселей. В симплекс-прослеживании применяется регулярная треугольная решетка, образованная тремя семействами линий: вертикалями, горизонталями и диагоналями (рис. 8б). Трассировка бинарного объекта осуществляется последовательным перебором граничных треугольных граней этой триангуляции (рис. 8в). Граничными считаются грани, в которых есть разноцветные вершины – пиксели разных цветов. Перебор граней начинается с треугольника, инцидентного первой паре разноцветных точек, встретившейся при последовательном просмотре решетки по горизонталям. На рис. 8б эта пара точек обозначена (A, B). Дальнейший последовательный перебор граней в процессе трассировки можно интерпретировать как перекатывание прямоугольного треугольника (плоского симплекса) вдоль границы объекта. Последовательность пикселей, которые заметает катящийся треугольник, называется следом трассировки. Объединение всех граничных треугольников образует полосу, называемую граничным коридором.

Рис. 8.

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

Задача построения разделяющего многоугольника минимального периметра, как кратчайшего кольцевого маршрута внутри граничного коридора, сводится к хорошо известной задаче построения кратчайшего геодезического пути в многоугольнике [16]. Для этого граничный коридор разрезается ребром и превращается в многоугольник (рис. 8г), у которого сторона (A, B) дублируется и образуется совпадающая с (A, B) сторона (A', B'). В этом многоугольнике необходимо найти кратчайший путь из вершины B в вершину B'. Поскольку полученный многоугольник образован из треугольников, для решения данной задачи можно использовать эффективный алгоритм построения геодезического пути в триангулированном многоугольнике [17]. С учетом полученного при симплекс-прослеживании следа проще всего получить решение методом “вытягивания нити” [15].

Алгоритм построения контурной модели в виде разделяющего многоугольника минимального периметра, включая прослеживание и аппроксимацию границы, имеет вычислительную сложность O(n), где n – количество пикселей в бинарной картинке. В табл. 1 приведены данные, иллюстрирующие размеры получаемого векторного описания контуров границы для изображений самолетов, представленных на рис. 3.

5. ПОДГОНКА КОНТУРНЫХ МОДЕЛЕЙ

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

− наложение контурной модели поверх растрового изображения аэрокосмического снимка либо его выделенного фрагмента;

− сдвиг, поворот и масштабирование контурной модели в ручном режиме с адекватной визуализацией;

− растеризация выбранного оператором положения векторного шаблона на растровом фрагменте аэрокосмического снимка.

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

Рис. 9.

Подгонка векторного шаблона a) объект на аэрокосмическом снимке, б) эталонное векторное представление контура самолета многоугольником, в) совмещение контура с объектом в результате сдвига, поворота и сжатия, г) растеризация найденного положения контура.

6. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ

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

− модуль подготовки эталонных изображений;

− модуль подгонки эталонов к тестовым изображениям.

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

Ниже представлен перечень основных возможностей графического инструмента асессора:

− загрузка списка всех доступных типов авиационной техники,

− навигация по списку типов авиационной техники с целью выбора нужного контурного эталона,

− загрузка аэрокосмических изображений, подлежащих разметке,

− работа по разметке каждого отдельного снимка (подгонка эталона),

− сохранение размеченных изображений в виде фрагментов исходных аэрокосмических снимков и бинарных масок с выделенными объектами.

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

Оценка качества и эффективности предложенного подхода выполнялась в ходе вычислительного эксперимента по разметке массива аэрокосмических изображений. В эксперименте было размечено 2909 изображений, представляющих собой фрагменты больших снимков. Фрагменты выделены асессором на основе визуального детектирования. В каждом фрагменте содержится один самолет. Для сравнения скорости работы асессора проводилось измерение времени, затрачиваемого оператором при использовании двух вариантов сегментации: на основе подгонки с помощью векторных шаблонов (метод “подгонка”) и на основе ручной обводки границ объектов путем последовательного ввода границы “точка за точкой” (метод “оконтуривание”). Измеренные затраты времени приведены в табл. 2.

Как видно из табл. 2, затраты времени асессора при работе методом подгонки составили в 4 раза меньше, чем при ручном выделении границ каждого объекта.

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

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

7. ЗАКЛЮЧЕНИЕ

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