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

Выделение дорог и водоемов на аэрофотоизображениях является важной задачей геоинформационных систем , так как объекты этих категорий наиболее стабильны и могут служить надежной привязкой к координатам местности [1], [3]. Экспериментально установлено, что при выделении дорог масштаб должен быть выбран таким образом, чтобы дорога по ширине занимала 2-3 элемента изображения. Если ширина дороги равна или менее 1 элемента, дорога становится прерывистой из-за пространственной дискретизации аэрофотоизображений, что затрудняет её обнаружение. Если ширина дороги 4 и более элеметов, эффективность её автоматического обнаружения снижается вследствие необходимости анализировать большие окрестности исследуемых точек. Однако при оптимальной ширине дороги в 2-3 элемента она обнаруживается как узкий протяженный полигон, в то время как желательный результат выделения - одна линия проходящая по центру. Пример приведен на рис 1.

Рис 1. Пример выделения дороги на аэрофотоизображении.

Здесь и в дальнейшем мы будем рассматривать один и тот же фрагмент изображения для возможности сравнения результатов. Аппроксимируем этот полигон полиномами 1-й степени

с точностью ε. Для этого необходимо минимизировать функционал

, (1)

где ,

n – число точек.

Минимизацию необходимо проводить одновременно по , i=1..n. То есть, число искомых неизвестных n+2. Графически это координаты пересечения перпендикуляров проведенных из каждой точки на пока еще неизвестную прямую . Согласно условию Эйлера [2] для достижения минимума необходимо чтобы являлись решением системы уравнений:

     , (2)

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

, (3)

При этом вычисляются по формулам:

      , (4)

где

,

.

Решениями системы (2) являются две прямые, обладающие замечательными свойствами:

- первая прямая минимизирует функционал (1) ,

- вторая прямая перпендикулярна к первой и проходит через центр масс множества точек .

Таким образом, мы можем построить автоматический рекурсивный алгоритм:

1. строим Эйлеровые полиномы по формулам (3),(4).
2. Проверяем значение функционала (1).
3. Если значение меньше заданного ε завершаем процесс вычислений, решение найдено.
4. Если значение функционала (1) больше заданного ε, второе решение уравнения (3) автоматически дает нам Эйлеровое (оптимальное, идеальное) разбиение (скалярное произведение к каждой точке > или < 0) множества на два подмножества, к каждому из которых в отдельности применяются действия первого шага.
5. И так до тех пор, пока значение функционала (1) не станет меньше ε.

Пример работы алгоритма приведен на рис.2, рис.3. На Рис.2 приведен результат работы алгоритма совместно с исходными точками. На рис.3 исходные точки удалены.

Рис. 2

 

Рис. 3

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

      , (5)

где - последняя точка аппроксимирующего полинома, найденного на предыдущем шаге.

Первый шаг делается без ограничений по формулам (3), (4). Будем минимизировать функционал (1) при ограничении (5). Для этого составим функцию Лагранжа [2].

      , (6)

Теперь, уже согласно условию Эйлера-Лагранжа [2] , для достижения минимума функционала (1) при условии (5) необходимо, чтобы λ являлись решением системы уравнений:

      , (7)

В данном случае число искомых неизвестных составляет n+3.

Здесь мы также не будем утруждать читателя простыми, но весьма объемными выкладками и приведем сразу конечный результат:

коэффициент находится из квадратичного уравнения

(8)

где находятся по формулам:

        , (9)

,

        , (10)

где , имеют тот же смысл, что и в расшифровке формулы (4).

Пример работы алгоритма минимизации функционала (1) при условии одного связанного конца (5) приведен на рис.4 и рис.5. На Рис.4 приведен результат работы алгоритма совместно с исходными точками. На рис.5 исходные точки удалены.

Рис.4

Рис. 5

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

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

Водоемы имеют три особенности , по которым человек их определяет достаточно быстро:

1 – гладкость , то есть после фильтрации для уменьшения шума и межэлементного вычитания по строке и столбцу остаточный сигнал не более 3 единиц,

2 – темность, то есть 99 % имеют яркость меньше чем средняя яркость по изображению,

3 – “плотность “. При этом “плотность “ - достаточно сложное и неопределенное понятие. Под ним мы будем понимать отношение “массы” к длине контура. Для круга это , для квадрата итд. В качестве этого параметра мы будем брать отношение числа точек связности к длине контура описывающего эту связность. Пример реализации этих 3-х особенностей приведен на Рис.6.

Рис. 6 Результат выделения водоёмов

Отдельно покажем фрагмент изображения водоема при большом увеличении на Рис. 7.

Рис. 7 Фрагмент изображения водоема при большом увеличении.

Результат визуализации после аппроксимации по приведенному выше алгоритму показан на Рис. 8.

Рис. 8 Аппроксимация по Эйлеру –Лагранжу

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

Наиболее близка наша работа к методу главных компонент разработанному Пирсоном [4] и получившего широкое применение при анализе статистических данных в самых разных областях знания. Однако, аппроксимация в методе главных компонент ищется в виде линейного многообразия , которое является линейной комбинаций главных компонент

и минимизирует расстояние каждого вектора до многообразия

.

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

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

Выводы.

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

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

Литература :

1 Грюнберг Г. Ю. Картография с основами топографии. — М.: Просвещение, 1991.

2 Смирнов В.И. Курс высшей математики, т.4, ч.1. Наука, М., 1974.

3 Салищен К.А. "Картоведение" - Москва: Издательство московского университета, 1990 - с.400 4. Pearson K., On lines and planes of closest fit to systems of points in space, Philosophical Magazine, (1901) 2, 559—572;

 

 Скачать статью (RAR -архив, 400 kb)

Автор(ы)  :  Мартынихин А.В.