Uniqueness estimation technique of the electronic map's fragments based on the fuzzy logic

Full Text

Введение Одной из важных задач, решаемых геостационарными космическими системами наблюдения Земли, является задача привязки изображений по электронным картам (ЭК) в процессе периодической съемки земного диска, содержащего одну и ту же часть поверхности Земли. При этом в качестве опорной координатной основы используются уникальные фрагменты (изломы береговых линий океанов, морей и крупных озер, контуры крупных островов), которые хорошо различимы на изображениях от геостационарных спутников, имеют специфичную геометрическую форму, характеризуются высокой временной устойчивостью и в большинстве ЭК выделены в отдельный слой [1, 2]. Определение параметров координатной привязки по ЭК реализуется путем последовательного выполнения следующих четырех этапов: выделение на снимке и карте уникальных фрагментов; формирование на основе уникальных фрагментов бинарных масок в виде уникальной линии карты, расширенной с одной стороны областью с единичными элементами яркости (что соответствует суше), а с другой стороны - областью с нулевыми элементами (что соответствует водной поверхности); выполнение корреляционного поиска одноименных фрагментов на снимке, которые наиболее близки к маске по геометрии и яркостному перепаду; установление на основе множества найденных опорных точек местности геометрического соответствия изображения на снимке и ЭК. Теоретическая часть Для поиска одноименных фрагментов снимок и ЭК должны отображаться в единой проекции. Векторная ЭК представляет собой множество M множеств ,, каждое из которых состоит из пар некоторым образом упорядоченных географических координат . Такие множества задают пространственные объекты и сопровождаются информацией о типе объекта (например, тип - «береговая линия») и о его характеристиках (площадь , периметр , географический регион ). Так как исходная ЭК представляет объекты всего земного шара, то выполняется преобразование (фильтрация) исходного множества объектов ЭК. Сначала осуществляется выделение тех объектов ЭК из географического региона , которые попадают в заданный локальный регион : , где - оператор выбора объекта ЭК в регионе , попадающего в заданный локальный регион . Затем осуществляется формирование нового множества объектов ЭК путем удаления из объектов (чаще всего это малоразмерные объекты), не содержащихся на изображениях диска Земли: , где - оператор удаления малоразмерных объектов, чья площадь удовлетворяет условию: , где - пороговое значение площади объекта. И, наконец, выполняется координатное преобразование элементов множества в систему координат , в которой регистрируются изображения ([x]=пиксел, [y]=пиксел):. , где - оператор координатных преобразований. Пересчет координат выполняется по формулам преобразования в нормализованную геостационарную проекцию [3]. а б б Рис. 1. Преобразование ЭК: а - объекты исходного множества ; б - объекты множества На рис. 1,а и 1, б представлены соответственно все объекты исходного множества и объекты множества , полученного в результате фильтрации объектов множества . На основе преобразованной ЭК выделяются уникальные фрагменты береговых линий. Размеры фрагментов выбираются исходя из двух условий [1]: размеры должны быть достаточно большими для их надежного сопоставления с одноименными объектами снимка; размеры нельзя неограниченно увеличивать, так как начинают негативно сказываться взаимные искажения между одноименными объектами снимка и ЭК. Экспериментально установлено, что прямоугольная область, включающая уникальный фрагмент, должна иметь размеры порядка пикселей. Под уникальностью фрагмента ЭК понимается его неповторяемость, выражающаяся в характерной изломанности. Определение уникальных фрагментов ЭК может быть выполнено как с участием оператора, так и автоматически. В первом случае оператор указывает начальную и конечную точки фрагмента, на основании которых формируется уникальный фрагмент ЭК. Автоматическое формирование уникальных фрагментов выполняется по следующему алгоритму. а б в Рис. 2. Примеры уникальных (а, б) и неуникальных (в) фрагментов ЭК 1. Для каждой точки некоторого объекта карты формируются участки путем последовательного включения других точек объекта до тех пор, пока размер сформированного участка (; ) не станет больше порога . 2. Для каждого участка по методу наименьших квадратов исходя из условия: (или ) вычисляются параметры и уравнения классической линейной регрессии (КЛР), а затем находится среднеквадратическое отклонение (СКО) невязок (или ) по отношению к КЛР, которое и является мерой уникальности. 3. Искомое множество уникальных фрагментов формируется в виде , где - пороговое значение меры уникальности. При пороге на изображении, представленном на рис. 1,б, можно выделить 63 уникальных фрагмента, расположенных по всей поверхности земного диска. На рис. 2 представлены примеры двух уникальных фрагментов (а: ; б: ) и одного неуникального фрагмента (в: ). Для каждого фрагмента формируется набор бинарных масок в виде «коридоров» с равноудаленными границами от линии карты. Для этого сначала осуществляется векторно-растровое преобразование фрагмента в плоскость регистрируемого изображения, а затем выполняется его утолщение таким образом, чтобы осевая линия «коридора» являлась линией ЭК. Элементам, находящимся по одну сторону осевой линии, включая и ее, присваивается единичная яркость, а элементам, расположенным по другую сторону - нулевая яркость, что соответствует более светлой суше и более темной водной поверхности. Такие «коридоры» позволяют учесть как топологию береговых линий, так и взаимное расположение водной и земной поверхностей. Для увеличения надежности совмещения фрагмента снимка и маски формируется набор бинарных масок с разной шириной «коридора». По результатам совмещения снимка с бинарными масками с различной шириной «коридора» в качестве окончательного принимается решение, при котором достигается максимум меры схожести (коэффициента корреляции). На рис. 3 представлены примеры формирования бинарных масок с различной шириной «коридора». а б в Рис. 3. Примеры бинарных масок с различной шириной «коридора»: 2 пикселя (а), 4 пикселя (б) и 8 пикселей (в) Как показывает анализ, применение только одной характеристики - среднеквадратического отклонения - для описания уникальности фрагмента ЭК приводит к тому, что фрагменты, имеющие одинаковые (близкие) значения меры уникальности , будут отнесены к одному классу (группе) фрагментов. Однако, вообще говоря, можно сформировать большое количество фрагментов ЭК, имеющих не только одинаковые значения меры уникальности , но и одинаковые значения длин своих ломаных , при этом существенно отличающихся друг от друга по своей форме. В связи с этим при оценке уникальности фрагментов ЭК предлагается использовать дополнительные характеристики уникальности фрагментов ЭК. Получение дополнительных характеристик уникальности фрагментов ЭК может быть реализовано с использованием уравнения нечеткой линейной регрессии (НЛР) с асимметричными параметрами треугольных функций принадлежности (ТФП) [5], что позволит благодаря учету асимметричных параметров используемых ТФП адекватно дифференцировать фрагменты ЭК, имеющие близкие значения меры уникальности . Использование ТФП с асимметричными параметрами (в отличие от случая использования ТФП с симметричными параметрами) обеспечит не только вычисление значения меры уникальности , равное значению, получаемому с помощью уравнения КЛР (рис. 4,а), но и позволит определить «коридор» уравнения НЛР посредством введения в решение задачи асимметричного треугольного нечеткого числа -типа, описываемого тройкой параметров , с функцией принадлежности вида [4] (1) где - модальное значение (ядро) треугольного нечеткого числа (ТНЧ); и - левый и правый параметры (размах) нечеткости соответственно. Носителем ТНЧ является интервал . При ТНЧ является симметричным, при - асимметричным. Уравнение НЛР в задаче оценки уникальности фрагмента ЭК может быть записано как , (2) где и - треугольные нечеткие числа, описывающие параметры, соответствующие параметрам и уравнения КЛР. Введем дополнительные обозначения для унификации формулировки задачи поиска оптимальных значений параметров уравнения НЛР вида (2). Пусть (), при этом все , так как соответствуют параметру (свободному члену уравнения КЛР). Задача поиска оптимальных значений параметров уравнения НЛР обычно решается как задача линейного программирования (ЗЛП) при равных (симметричных) значениях параметров ТФП в виде [4] (3) при ограничениях ; (4) ; (5) ; (; ; ), (6) где - значение -уровня ТНЧ (; в случае, если не оговорено иначе, целесообразно использовать ). Однако такая формулировка оптимизационной задачи обеспечивает нахождение симметричных параметров ТФП, что приводит к недостаточно адекватному определению параметров уравнения НЛР (и, как следствие, к недостаточно точному учету геометрического расположения данных); кроме того, не гарантирует получение значения среднеквадратического отклонения , близкого к значению среднеквадратического отклонения , получаемого с помощью уравнения КЛР. Для устранения данного недостатка целесообразно выполнить формулировку оптимизационной задачи, используя асимметричные параметры ТФП и, кроме того, модифицировать саму целевую функцию. Исходя из вышесказанного задача поиска оптимальных значений параметров и уравнения НЛР может быть сформулирована как задача квадратичного программирования (ЗКП) в виде [4] (7) при ограничениях ; (8) ; (9) ; (; ; ), (10) где - значение -уровня ТНЧ (); - весовые коэффициенты, характеризующие вклад первого и второго слагаемых в целевую функцию вида (7); - малое положительное число такое, что . В этом случае функция принадлежности произвольной точки данных (; ) уравнению НЛР может быть определена как [4] (11) На рис. 4,б-в приведены соответственно примеры НЛР с асимметричными и симметричными параметрами ТФП, полученных на основе одинаковых исходных наборов данных. x y пикс. Классическая линейная регрессия: ; ; а y пикс. x пикс. y пикс. Нечеткая линейная регрессия (ЗКП) с асимметричными параметрами ТФП: ; ) б x пикс. Нечеткая линейная регрессия (ЗКП) с симметричными параметрами ТФП: ; ; в Рис. 4. Примеры регрессий x пикс. y пикс. а x пикс. y пикс. б x пикс y пикс. в y пикс. x пикс г x пикс. y пикс. д x пикс. y пикс. е Рис. 5. «Коридоры» регрессий На рис. 5 показаны примеры НЛР с асимметричными параметрами ТФП, полученных на основе разных исходных наборов данных. При этом НЛР, приведенные на рис. 5,а-д, имеют одинаковые значения меры уникальности и одинаковые уравнения КЛР, но разные «коридоры» НЛР. НЛР, приведенная на рис. 5,е, имеет значение меры уникальности , несколько отличающееся от значения меры уникальности данных, приведенных на рис. 5,а-д, и несколько иное уравнение КЛР. Как видно из рисунков, зачастую «коридоры» НЛР характеризуются явно выраженной асимметрией ввиду использования асимметричных параметров ТФП. Такие «коридоры» могут иметь разную ширину (; ) своих нижней () и верхней () частей в начале () и в конце () относительно уравнения КЛР. Учет таких особенностей НЛР позволяет более точно дифференцировать уникальные фрагменты, представляющие собой кусочно-линейные объекты (наборы исходных данных). Для оценки подобия уникальных фрагментов могут быть использованы нечеткие меры подобия, рекомендуемые к использованию при обработке изображений [5], в частности, следующие нечеткие меры, показавшие наивысшее качество результатов при выполнении оценки подобия тестовых наборов данных, описываемых с помощью уравнений НЛР: ; (12) , (13) где и - значения функций принадлежности нечетких множеств и соответственно (значения функций принадлежности двух наборов исходных данных, соответствующим уравнениям НЛР); - количество точек данных. Как показывает анализ, в общем случае для обеспечения применимости нечетких мер подобия к тем или иным фрагментам (наборам исходных данных) необходимо выполнение предварительной классификации наборов исходных данных с учетом асимметрии «коридоров», что позволит исключить возможность получения неадекватных результатов упорядочения наборов исходных данных по степени близости (подобия) к некоторому эталонному фрагменту, например в случае, когда «коридоры» одних наборов данных существенно асимметричны (рис. 4,б), а «коридоры» других могут считаться близкими к симметричным (рис. 5,в), но имеют близкие значения отношений площадей своих верхних и нижних частей. В связи с наличием асимметрии «коридоров» НЛР предлагается использовать следующую методику. Для каждого анализируемого фрагмента, сравниваемого с некоторым эталонным фрагментом, определяются точки, лежащие сверху () и снизу () относительно уравнения КЛР. Для каждой группы точек вычисляются значения мер подобия и . Оценка нечеткой меры подобия анализируемого фрагмента эталонному фрагменту находится как , (14) где и вычисляются в соответствии с формулами для мер подобия (или ). Целью дальнейших исследований должен быть выбор наиболее адекватных нечетких мер подобия и выявление ограничений, накладываемых на их применимость. При выполнении сравнительного анализа нескольких фрагментов (наборов данных) с эталонным фрагментом на предмет их подобия можно рекомендовать использование нескольких нечетких мер подобия одновременно с последующим выбором того варианта упорядочения по степени подобия, который дают большинство применяемых нечетких мер подобия. Наряду с анализом нечетких мер подобия существенный интерес представляет анализ площадей и центроидов верхней и нижней частей «коридоров» НЛР анализируемых наборов данных. При этом площади могут быть легко найдены с использованием параметров и уравнения НЛР и формулы для нахождения площади треугольника, а центроиды - с применением формулы для вычисления центра тяжести одноточечных множеств [6]: . (15) Экспериментальная часть Ниже рассмотрен пример, демонстрирующий построение регрессий, полученных при решении ЗКП вида (7)-(10) с асимметричными и симметричными параметрами ТФП, и подтверждающий целесообразность использования НЛР с асимметричными параметрами ТФП для дифференциации уникальных фрагментов ЭК. Исходные данные (значения ), на основе которых строятся регрессии, приведены в табл. 1. На рис. 4,а приведен пример построения КЛР по данным табл. 1. При этом оптимальные значения параметров уравнения КЛР равны ; ; мера уникальности (СКО) . На рис. 4,б показан пример построения НЛР с асимметричными параметрами ТПФ по данным табл. 1. При построении НЛР с асимметричными параметрами ТФП использовались следующие значения весовых коэффициентов и чисел , : ; ; ; . Следует отметить, что выбор значений весовых коэффициентов не оказывает существенного влияния на результаты решения задачи ввиду использования асимметричных параметров ТФП [4]. Результаты расчетов показывают, что ядра треугольных нечетких чисел и уравнения НЛР с асимметричными параметрами ТФП совпадают с коэффициентами уравнения КЛР: и и, как следствие, совпадают вычисленные значения мер уникальности: . На рис. 4,в приведен пример построения НЛР с симметричными параметрами ТФП по данным табл. 1, демонстрирующий худшее качество этой регрессии по сравнению с КЛР и НЛР с асимметричными параметрами ТФП, так как ее мера уникальности (), определяемая через СКО, оказалась больше, чем у двух других (). НЛР, полученные при решении ЗЛП вида (3)-(6), характеризуются еще более низким качеством, поскольку значения их мер уникальности (СКО) существенно превосходят значения мер уникальности (СКО) КЛР и НЛР, полученных при решении ЗКП вида (7)-(10), на одних и тех же наборах исходных данных [7]. Таблица 1 Исходные данные и значения функций принадлежности исходных данных уравнениям НЛР 1 2 3 4 5 6 7 8 9 10 11 12 13 21 20 28 27 32 38 34 42 49 45 54 36 53 0 0 0 0,68 0,90 0,13 0,64 0,67 0,00 0,9 0,3 0,0 0,91 0 0 0,28 0,77 0,83 0,43 0,70 0,74 0,39 1,0 0,5 0,0 0,97 Таблица 2 Параметры «коридоров» НЛР Ширина «коридора» Параметры ТФП Асимметричные (AS) Симметричные (S) В начале Нижняя 1,792 1,300 Верхняя 0,808 1,300 В конце Нижняя 19,542 18,314 Верхняя 9,658 18,314 В начале Суммарная 2,600 2,600 В конце Суммарная 29,200 36,628 Таблица 3 Значения нечетких мер подобия фрагментов эталонному фрагменту Фрагмент Рис. 5 а б в г д е Нечеткая мера подобия по формуле (12) 0,009 0,117 0,099 0,00 0,115 0,277 Нечеткая мера подобия по формуле (13) 0,018 0,209 0,181 0,00 0,206 0,433 Номер в списке упорядочения по близости к эталонному фрагменту 5 2 4 6 3 1 В табл. 1 и табл. 2 приведены соответственно значения функции принадлежности вида (11), вычисленные на основе данных табл. 1, и значения ширины «коридоров» для уравнений НЛР с асимметричными (AS) и симметричными (S) параметрами ТФП. Анализ табличных данных свидетельствует о том, что НЛР с асимметричными параметрами ТФП более точно описывает данные табл. 1, чем НЛР с симметричными параметрами ТФП (так как ; и , где и - средние значения функций принадлежности и соответственно), именно благодаря использованию асимметричных параметров ТФП, позволивших ввести в рассмотрение нижний и верхний (относительно уравнения регрессии) «коридоры», имеющие разную ширину. В трехмерном пространстве НЛР с асимметричными параметрами ТФП можно представить как поверхность, высота которой равна единице вдоль прямой, определяемой уравнением регрессии (совпадающим с уравнением КЛР), и равна нулю вдоль прямых, определяемых нижней и верхней границами НЛР (рис. 4,б). Высота поверхности в промежуточных точках определяется в соответствии с уравнением для значений функции принадлежности вида (11). На рис. 5,а-д показаны примеры «коридоров» НЛР для пяти фрагментов изображений, имеющих одинаковые значения мер уникальности (СКО) и одинаковые значения длин ломаных l, которыми аппроксимируются контуры фрагмента, но существенно отличающихся друг от друга своей «изломанностью». При этом данные для построения графиков на рис. 5,г получены из графиков рис. 4,а зеркальным их отображением относительно линии регрессии, а графики рис. 5,д получены аналогично из рис. 5,г, но с учетом отклонения данных, относительно прямой, определяемой уравнением регрессии. На рис. 5,е приведен пример «коридоров» НЛР для фрагмента с характеристиками (мера уникальности () и длина ломаной ()), несколько отличающимися от соответствующих характеристик других наборов данных, по которым построены графики (рис. 4,б, рис. 5,а-д). Использование нечетких мер подобия, вычисляемых по формулам (12) и (13), для оценки подобия фрагментов, приведенных на рис. 5, а-е, эталонному фрагменту, приведенному на рис. 4,б, позволило получить одинаковые списки упорядочения рисунков и соответствующих им фрагментов и наборов данных по убыванию их меры подобия: рис. 5, е,б,д,в,а,г. Как можно заметить, фрагмент, изображенный на рис. 5,е, визуально наиболее близок к эталонному фрагменту, изображенному на рис. 4,б. Фрагменты на рис. 5,а-д визуально существенно отличаются от эталонного фрагмента на рис. 4, б, и их упорядочение на предмет подобия эталонному фрагменту производилось для демонстрации результатов применения нечетких мер подобия по формулам (12) и (13). Заключение Полученные результаты свидетельствуют о целесообразности использования нормальной линейной регрессии с асимметричными параметрами треугольной функцией принадлежности для решения задачи формирования уникальных фрагментов электронной карты, что позволяет более надежно дифференцировать фрагменты ЭК за счет учета большего количества характеристик анализируемых фрагментов изображений, наряду с уже используемой мерой уникальности , вычисляемой как СКО. Методика оценки подобия уникальных фрагментов ЭК некоторому эталонному фрагменту с использованием нечетких мер подобия обеспечивает возможность упорядочения фрагментов ЭК, имеющих сходные значения меры уникальности , по близости к эталонному фрагменту.

About the authors

Lidiya A Demidova

Riazan State Radiotechnical University

(Dr. Sci. (Techn.)), Professor 59/1, Gagarina st., Riazan, 390005

Gennady N Myatov

Samara State Technical University

(Ph.D. (Techn.)), Associate Professor 244, Molodogvardeyskaya st., Samara, 443100

References

Supplementary files