Авторы: Потапов Н.Н., Тупиков П.А.

Источник: Потапов Н.Н. Методы выделения контуров на изображениях / Н.Н. Потапов, П.А. Тупиков // 8-я международная конференция Распозначание образов и анализ изображений: новые информационные технологии, 2007. — С. 105–108.

Аннотация

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

Введение

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

Постановка задачи

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

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

Из данных, полученных от радиолокационных средств, формируется измеренная карта размером X_m×Y_m точек. Эталонная карта размером X₀×Y₀ точек загружается при подготовке полетного задания.

Корреляционная обработка при использовании алгоритмов выделения контуров состоит из нескольких последовательных этапов:

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

На рисунке 1 показана эталонная карта местности, а на рисунке 2 — результат операции выделения контуров.

Рисунок 1 — Эталонная карта

Рисунок 2 — Контуры, выделенные на эталонной карте

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

Методы выделения контуров

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

Пример отслеживающего метода — метод жука — приведен на рисунке 3. Жук начинает движение с белой области по направлению к черной, Как только он попадает на черный элемент, он поворачивает налево и переходит к следующему элементу. Если этот элемент белый, то жук поворачивается направо, иначе — налево. Процедура повторяется до тех пор, пока жук не вернется в исходную точку. Координаты точек перехода с черного на белое и с белого на черное и описывают границу объекта.

На рисунке 3 показана схема работы такого алгоритма.

Рисунок 3 — Метод жука

Метод, основанный на последовательном сканировании изображения (рисунок 4), заключается в поиске таких пар точек, для которых разность интенсивностей с соседними точками (вдоль направления сканирования) больше некоторого порога Δ/2, а разность интенсивностей со всеми точками между искомыми не превышает этот порог.

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

Рисунок 4 — Метод последовательного сканирования

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

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

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

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

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

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

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

Сравнение методов выделения контуров

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

Для проведения анализа выбиралась степень разреженности измеренной карты и производилась серия из N_E экспериментов. В каждом эксперименте создавалась эталонная карта. На эталонной карте выбиралась точка совмещения и создавалась измеренная карта с заданной степенью разрежения. Затем методами последовательного сканирования изображений производилось выделение контуров и корреляционно-экстремальная обработка согласно той модификации алгоритма выделения контуров, которая предполагает точечное сравнение контуров. Эксперимент считается успешным, если полученные координаты точки совмещения карт совпадают с заданными. Обозначив количество успешных экспериментов N_ES, определим надежность вычислений по исследуемому алгоритму как вероятность успешного эксперимента P=N_ES/N_E. Также проводились исследования зависимости надежности вычислений от ширины Δ уровня квантования контуров. Исследования производились при следующих значениях параметров: X₀=256, Y₀=100, X_m=50, Y_m=3, N_E=100.

Анализ

По результатам анализа можно сделать следующие выводы:

• надежность вычислений в разных сериях экспериментов не достигает 100%;
• надежность вычислений понижается при увеличении ширины Δ уровня квантования контуров;
• с увеличением разрежения измеренной карты вдоль направления, перпендикулярного направлению движения надежность незначительно возрастает;
• с увеличением разрежения измеренной карты вдоль направления движения надежность падает.

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

Список использованной литературы

1. Андреев Г.А., Потапов А.А. Алгоритмы обработки навигационной пространственно-временной информации (часть 1) // Зарубежная радиоэлектроника. — 1989. — № 3. — C. 3–18.
2. Андреев Г.А., Потапов А.А. Алгоритмы обработки навигационной пространственно-временной информации (часть 2) // Зарубежная радиоэлектроника. — 1989. — № 4. — C. 3–21.
3. Белоглазов И.Н., Тарасенко В.П. Корреляционно-экстремальные системы. — М.: Сов. радио, 1974. — C. 392. 4. Бочкарев А.М. Корреляционно-экстремальные системы навигации // Зарубежная радиоэлектроника. — 1981. — № 9. — C. 28–53.
5. Буймов А.Г. Корреляционно-экстремальная обработка изображений. — Томск: Изд-во ТГУ, 1987. — C. 134.
6. Корреляционно-экстремальные системы управления: Сборник статей / Под ред. В.П. Тарасенко. — Томск: Изд-во Томск. ун-та, 1981. — C. 160.
7. Красовский А.А., Белоглазов И.Н., Чигин Г.П. Теория корреляционно-экстремальных навигационных систем.  — М.: Наука, 1979. — C. 448.