The task of object recognition on digital images becomes more relevant in connection with the development of intelligent robotic systems. The initial stage of any recognition techniques is the preliminary selection of objects. A method for selecting objects with high accuracy and low computational complexity is proposed. МЕТОД ФРАКТАЛЬНОЙ СЕЛЕКЦИИ ОБЪЕКТОВ НА АЭРОКОСМИЧЕСКИХ ИЗОБРАЖЕНИЯХ Андрусенко А.С., Шабаков Е.И.

Методы распознавания объектов, полученных с помощью различных оптико-электронных систем, развиваются с 70-х годов XX века – с того времени, когда появились первые цифровые изображения, пригодные для анализа с помощью компьютеров – например, ставшая классикой книга Дуды, Харта и Строка (1973) [1]. Последние 10 лет задачи распознавания находят все новые прикладные области применения. Достаточно широко известны и широко применяются автоматические системы распознавания автомобильных номеров [2], лиц [3], автоматический анализ сцен в целях безопасности, системы технического зрения в робототехнике [4].

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

Любое изображение земной поверхности содержит два класса объектов: естественные (природные) и искусственные (антропогенные). Для моделирования природных объектов используется фрактальная геометрия, которая была введена Б. Мандельбротом в классических работах [5, 6] в период 1977-82 гг.

По нотации Мандельброта [7], термин “фрактал” происходит от латинского fractus, означающего изломанный, дроблёный. Фракталом называется математическое множество, обладающее свойством самоподобия (объект, в точности или приближенно совпадающий с частью себя самого, то есть имеет ту же форму, что и одна или более частей), для которого существует метрика Хаусдорфа Безиковича и она строго больше евклидовой метрики. Если взять евклидову плоскость, то она будет «гладкой» в любом направлении, а движущаяся точка может менять координаты X и Y, но никогда не “приподнимется” над плоскостью или “опустится” ниже (координата Z постоянна). В этом случае метрика Хаусдорфа строго равна эвклидовой. Если же поверхность фрактальна, то плоскость становится изломанной, и движущаяся точка, вопервых, пройдет больший путь, во-вторых, будет немного менять свою координату Z с точки зрения наблюдателя, находящегося вне такой плоскости. При этом движущаяся точка остается на плоскости. Для такой фрактальной плоскости метрика Хаусдорфа строго больше евклидовой. Чем больше метрика Хаусдорфа, тем более изломана поверхность.

Фундаментальными характеристиками фракталов, позволяющими моделировать природные объекты, являются:  Зависимость их метрических свойств (длина, ширина, площадь) от масштаба измерения, которая выражается параметром, называемым фрактальная размерность D (коэффициент, описывающий фрактальные структуры или множества на основе количественной оценки иx сложности). Рис. 1. Треугольная призма и регрессирующий участок D.  Самоподобие – способность увеличенного фрагмента объекта выглядеть идентично исходному объекту.

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

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

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

Метод призм разработан Кларком в 1986 году для вычисления D топографических поверхностей. По цифровому изображению перемещается скользящее окно «window size». Определяются значения яркости для угловых и центральных пикселов. Затем вычисляются площади четырех пространственных треугольников, сформированных соответствующими отсчетами яркости. Каждый такой треугольник является верхней поверхностью призмы, построенной от основания (яркость 0) до соответствующих значений яркости (рис. 1).

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

D 

Log (Sфр ) .

Log (S ) Для корректного вычисления D методом призм требуется правильный выбор размера окна. При слишком малом размере окна результат будет выглядеть слишком “гладким”, маленькое окно будет “скользить” по склонам “волн яркости”, выдавая минимальные значения D. При слишком большом размере окна, метод пропускает перепады яркости и его результат становится случайным. Правильный размер окна должен соответствовать размеру элемента самоподобия изображения. Это, например, размер транспортного средства, расстояние между волнами на морской поверхности, средний размер склона горного массива, средний размер «завитка» облака и т.д. Точное суммирование поверхностей всех элементарных призм в окне дает более точные результаты и позволяет уменьшить влияние размера окна на релевантность метода [9].     Рис. 2. Выделение различных типов объектов методом фрактальной селекции.

Основой для клеточного метода (box-counting) является приближенная формула для вычисления фрактальной размерности [10]:

 LogN( )  log c  Dlog  ,       где ε – размер скользящего окна; N(ε) –количество окон, перекрывающих изображение; с – константа.

Геометрически фрактальная размерность D представляет собой угол наклона графика зависимости log N(ε) от log ε. Для вычисления D необходимо произвести несколько измерений с разными размерами окна ε. При использовании двух размеров окон получаем систему линейных уравнений, из которой можно получить значение D: LogN(1)  log c  D log 1;  LogN( 2 )  log c  D log  2.    При большем выборе размеров окон точность вычисления повышается. При этом целесообразно применить метод наименьших квадратов.

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

Фрактальные методы рассчитывают для каждой точки изображения значение фрактальной размерности – базового параметра фрактальной геометрии. Установив пороговое значение фрактальной размерности, можно определить, относится ли данная точка изображения к природному или антропогенному объекту. Исследования, проведенные в [11], определяют порог фрактальной размерности для снимков, полученных с космических оптико-электронных снимков в диапазоне 2,5 – 2,7.

Для фрактала метрические свойства (длина, ширина, площадь) пропорциональны масштабу. При этом, например, для длины L, будет выполняться равенство [12]:

L( )   (1D).     где δ – масштаб; D – фрактальная размерность; k – коэффициент пропорциональности.

Это означает, что при последовательном увеличении изображения линейные размеры фрактала также увеличиваются за счет появления новых, ранее не видных, мелких деталей. Классический пример – береговая линия, которая при приближении открывает все новые изгибы, приводящие к увеличению ее известной общей протяженности [13].

Фрактальная размерность D характеризует степень фрактальности связей элементов множества и определяется [12]:

 D  E 1 H.     где Е – число независимых измерений; Н – параметр самоподобия (0 < Н < 1).

Фрактальная размерность есть вещественное число и, применительно к «прямой», лежит в диапазоне 1 < D < 2, к «плоскости» - лежит в диапазоне 2 < D < 3.   Объект обладает самоподобием, если любой его произвольный фрагмент, будучи увеличен до размеров исходного объекта, становится подобен (в строгом смысле идентичен) этому объекту [12]. Например, если взять ветку цветной капусты и последовательно отделять от нее все более мелкие побеги, то при одинаковом увеличении i-го элемента в поле кадра все итерации будут малоразличимы между собой (подобны).

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

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

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

Как правило, фотограмметрические параметры изображения известны, поэтому приведение линейных размеров объекта к предполагаемому изображению объекта на снимке не вызывают трудностей [14].

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

Анализ процесса перемещения скользящего окна, размер которого соответствует размеру объекта, по фрактальному бинарному изображению показывает, что по мере «наползания» скользящего окна на изображение объекта вычисленное Ct будет увеличиваться и достигнет максимума, когда объект полностью попадет в окно (см. график 4 на рис. 3). При дальнейшем движении окна Ct начнет уменьшаться.

Для дальнейших расчетов целесообразно ввести понятие фрактальной плотности DNfr в апертуре [Lt x Lt]: Рис. 3. Графики фрактальной селекции.   DN fr  i, j0

LtLt  B(i, j) , 

 Cmax  DN fr  1.  G0.9  DN fr  0.9.  

   При значении фрактальной плотности для заданной цели ≥ 1 в точке бинарного изображения i,j фиксируется центр области изображения [Lt x Lt], в котором может находиться объект. Максимальный критерий поиска объекта:

Критерий Gmax учитывает наличие в окне фрактального бинарного шума и фрагментов других антропогенных объектов. Отметим, что критерий Gmax является слишком строгим для практического применения. В самом деле, существует множество факторов, которые могут привести к уменьшению числа пикселов реального фрактального бинарного изображения объекта относительно эталонного. Это может привести к пропуску объекта. Поэтому возможно применение более мягких критериев, например:   Выбор критерия поиска объекта требует дальнейшего экспериментального изучения. Очевидно, что при любом критерии обнаружения объекта всегда возможна ситуация, когда на изображении будет присутствовать антропогенный объект, Ci которого больше, чем Cj объекта, что приведет к ошибке типа «ложное обнаружение».

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

В общем случае объект на снимке имеет произвольную ориентацию. Скользящее окно, размер которого точно соответствует размеру объекта, будет давать ошибки типа «пропуск объекта» из-за того, что произвольно ориентированный объект никогда не попадет полностью в окно. Это проблема решается за счет увеличения размера скользящего окна до максимальной длины объекта Lt. В пределах окна [Lt x Lt] объект может располагаться произвольным образом – всегда найдется несколько положений окна, в которых объект полностью попадает в окно (рис. 4).

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

На рис. 4 приведен пример идеального прохождения скользящего окна по изображению протяженной цели (окно перемещается слева направо, сверху вниз). В положении 1 окно впервые полностью включает изображение цели. Поэтому область изображения с центром [i1, j1] и размером [Lt, Lt] следует зафиксировать как область возможного нахождения объекта для дальнейшего распознавания. Однако, размер этой области избыточен – что особенно существенно для протяженных объектов. Поэтому необходимо разработать способ уменьшения области возможного нахождения цели. Это будет сделано на следующем этапе фрактальной сегментации.

В положении 2 на рис. 4 скользящее окно еще содержит полное изображение объекта, но на следующем шаге объект начнет исчезать из окна. При этом очевидно, что между положениями 1 и 2 существует множество других положений окна, которые можно интерпретировать как области возможного нахождения объекта. Кроме этого, положения 3 и 4 задают целую область 6, в которой располагаются все возможные центры положения объекта. Поэтому на следующем этапе сегментации необходимо также определить точное местоположение центра объекта из всех возможных.

Границы области возможного нахождения объекта определяются кругом, радиус которого составляет половину максимального размера объекта Lt/2. Центр круга совпадает с центром объекта и центром области выделения.

На рисунке 5 представлен пример реального сюжета, в котором протяженный объект (судно) располагается в окружении других искусственных объектов, у которых Ct может быть как больше, так и меньше эталонной. Кроме этого, на фрактальном бинарном изображении часто присутствуют паразитные засветки. Поэтому позиции 1 – 4 скользящей апертуры смещаются относительно идеальных (см. рис. 4), так как в окне появляются дополнительные яркие пикселы, которые заставляют максимальный критерий Gmax срабатывать раньше. 54 1 Рис. 4. Идеальное расположение объекта в скользящем окне [Lt x Lt]: 1-4 – крайние положения окна, при которых выполняется максимальный критерий поиска объекта; 5 – минимальное окно, соответствующее размерам и ориентации объекта; 6 – область расположения возможных центров объекта. 2 3

Lt/2 4 Рис. 5. Произвольное расположение объекта в окне [Lt x Lt]: 1-4 – крайние положения скользящего окна, при которых выполняется максимальный критерий поиска объекта; 6 – область расположения возможных центров объекта.

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

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

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

Так как для практического использования рекомендуется использовать критерий поиска объекта G, необходимо дополнительно увеличить радиус области возможного расположения объекта на пропорциональную величину – 10%:

Rt =1,1 * Lt / 2   Изображение объекта в любом случае будет находиться внутри этого круга. При дальнейшем использовании в произвольном алгоритме распознавания, выделенные области возможного расположения объекта применяются в качестве пространственных фильтров, которые следует совместить с исходным цифровым изображением. В результате получим набор участков исходного снимка с изображениями объекта.

Для апробации метода был проведен эксперимент. Обработке подвергались аэрокосмические снимки размером 1024х1024, с масштабом 30 – 300 м. Линейное разрешение на местности составило от 0,3, до 1,5 м.

Анализ данных позволяет сделать вывод о высокой надежности метода – доля критических ошибок типа «пропуск объекта» составляет не более 7%, причем их большая часть относится к самому сложному сюжету – плотная компоновка разнотипных объектов. Для простых объектов доля правильно выделенных объектов приближается к 99%.

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

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

На рис. 6 показаны результаты применения метода для различных ландшафтов, результаты представлены в табл. 2. Анализ данных позволяет сделать вывод высокой надежности метода – доля критических ошибок типа «пропуск объекта» составляет не более 8%, причем их большая часть ожидаемо относится к антропогенному ландшафту, фрактальные бинарные изображения которого продуцируют наибольшее количество помех.  Таблица 1. Результаты выделения объектов методом фрактальной селекции для различных сюжетов.

Количе- Ошибка Доля ошибок Ошибка Доля ошибок Тип объекта ство объ- «пропуск «пропуск «ложное «ложное ектов объекта» объекта» обнаружение» обнаружение» Одиночные объекты Групповые однотипные объекты Групповые разнотипные объекты Плотная компоновка, однотипные объекты Плотная компоновка, разнотипные объекты 24 576 591 1003 868 0 6 5 24 59 0% 1% 1% 3% 7% 2 32 99 125 191 8% 6% 17% 12% 22% г Рис. 6. Выделение объектов методом фрактальной селекции: а – природный ландшафт, объект – здания; б – антропогенный ландшафт, объект - автомобили; в – смешанный ландшафт, объект – автомобили; г – однородный ландшафт, объект – судно. Тип объекта Таблица 2. Результаты выделения объектов методом фрактальной селекции

для различных ландшафтов.

Кооблъиечкетсотвво «оОпбшръоеикпбтукасак» До«олпбяръооекпштуиасбк»ок Оошбинбакрауж«леноижен»ое оДбон«лаляроуожжшнеионбеиоек» Природный ландшафт Антропогенный ландшафт Смешанный ландшафт Однородный ландшафт 40 227 209 38 2 19 11 1 5% 8% 5% 3% 2 82 41 2 5% 36% 20% 6% При исследовании результатов применения метода для различных условий освещенности была выявлена проблема снижения точности метода для объектов с низким углом стояния Солнца. Наличие большой насыщенной тени у объекта приводит к смещению геометрического центра области возможного расположения объекта, и, как следствие, ухудшение условий для работы алгоритмов распознавания. Применение менее строгого критерия поиска цели G0,8 устраняет данную проблему.

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

Исследования показали, что размер скользящего окна надо выбирать компромиссно, применительно к конкретным условиям съемки и конкретным параметрам съемочной аппаратуры с учетом вероятности пропуска объекта и вероятности ложного обнаружения. Метод фрактальной селекции применим к любым типам цифровых изображений и демонстрирует надежные результаты в обнаружении антропогенных объектов. Доля ошибок типа «пропуск объекта» составляет не более 8,5% в зависимости от ландшафта и условий наблюдения. Метод обладает низкой вычислительной сложностью, что позволяет реализовать автоматический поиск объектов в режиме поступления данных.

ЛИТЕРАТУРА

Richard O. Duda, Peter E. Hart, David G. Stork, Pattern Classification and Scene Analysis, New York, John Wiley and Sons, 1973.

Friedrich, Markus; Jehlicka, Prokop; Schlaich, Johannes (2008). "Automatic number plate recognition for the observance of travel behavior". 8th International Conference on Survey Methods in Transport: Harmonisation and Data Comparability, May 2008, Annecy, France.

Brunelli, R. & T. Poggio (1993), Face Recognition: Features versus Templates, IEEE Transactions on PAMI, 15(10):1042-1052.

B. Horn. Robot vision. MIT Press, Cambridge, Mass. 1986. 509 pp.

Mandelbrot В. B. The Fractals Geometry of Nature. San Francisco: W. H. Freeman, 1982. 625 p. Pentland, А. Р. Fractal-based description of natural scenes//IEEE Trans, on Pattern Analysis and Machine Intelligence. 1984. V. PAMI-6(6). P. 661—674.

Mandelbrot В. В. Fractals: Form, Chance and Dimension. San Francisco: Freeman, 1977. 470 p. Sun W. Fractal analysis of remotely sensed images: A review of methods and applications / W. Sun, G. Xu, P.Gong, S. Liang // International Journal of Remote Sensing, V.27, No 22, 20 November 2006, P.4963 – 4990.

Sun, W. Fractal analysis of remotely sensed images: A review of methods and applications / W. Sun, G. Xu, P.Gong, S. Liang // International Journal of Remote Sensing, V.27, No 22, 20 November 2006, P.4963 – 4990.