(2019)Еремеев, Андрианов, Титов

Формат документа: pdf
Размер документа: 1.01 Мб





Прямая ссылка будет доступна
примерно через: 45 сек.



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

Алгоритм соf_s_gby пространст_gguo объектов разномасштабных карт на осно_... Еремеев С.В., Андрианов Д.Е., Титов В.С.
Компьютерная оптика, 2019, том 43, №6 1021
Алгоритм соf_s_gby пространственных объектов
разномасштабных карт на осно_ топологического анализа данных
С.В. Еремеев 1, Д.Е. Андрианов 1, В.С. Титов 2 1 Владимирский государст_gguc уни_jkbl_l
имени Александра Григорьевича и Николая Григорьевича Столетовых, Владимир, Россия;
2 ФГБОУ ВО «Юго-Западный государст_gguc университет», Курск, Россия
Аннотация
В статье рассматривается проблема автоматического соf_s_gby пространст_gguo
объектов на разномасштабных картах одной и той же местности. Для решения постаe_g-
ной задачи предлагается использоZlv методы топологического анализа данных. Исходны-
ми данными алгоритма яeyxlky пространст_ggu_ объекты, которые могут быть получены
с карт разных масштабов
и под_j`_gu искажениям. Персистентная гомология позhey_l
идентифицировать общую структуру таких объектов в b^_ топологических особенностей.
Осноgufb топологическими особенностями в исследоZgbb яeyxlky компоненты сyagh-
сти и пустоты объектов. В работе приh^blky математическое описание метода персистент-
ной гомологии для предстаe_gby пространст_gguo объектов. Приh^blky определение
баркода для пространст_gguo данных, который содержит описание объекта
в b^_ тополо-
гических признаков. Разработан алгоритм сраg_gby баркодов пространст_gguo данных,
который позволяет найти общую структуру объектов. Алгоритм базируется на анализе дан-
ных из баркода. В_^zg показатель схожести объектов по топологическим признакам. Пока-
заны результаты исследоZgbc работы алгоритма. Про_^zggu_ эксперименты подтвердили
ukhdh_ качестh предложенного алгоритма. Процент схожести при сопостаe_gbb природ-
ных
объектов с учётом масштаба и деформации получился в пределах от 85 до 92, а для му-
ниципальных при наличии растяжений и искажений частей объектов – от 74 до 87. Отраже-
ны преимущестZ предложенного подхода с аналогами при соf_s_gbb объектов, которые
под_j`_gu значительной деформации при масштабироZgbb, а также при искажениях.
Ключеu_ слоZ: персистентная гомология, баркод пространст_ggh]h
объекта, сопо-
стаe_gb_ объектов, анализ топологических особенностей, разномасштабные карты.
Цитирование: Еремеев, С.В. Алгоритм соf_s_gby пространст_gguo объектов разно-
масштабных карт на основе топологического анализа данных / С.В. Еремеев,
Д.Е. Андрианов, В.С. Титов // Компьютерная оптика. – 2019. – Т. 43, № 6. – С. 1021-1029. –
DOI: 10.18287/2412-6179-2019-43-6-1021-1029.
В_^_gb_
Сопостаe_gb_ пространст_gguo объектов на
дmo картах одной и той же местности яey_lky акту-
альной задачей [1
– 4]. Она имеет множестh различ-
ных приложений, среди которых обноe_gb_ карт
местности, сопостаe_gb_ разномасштабных карт,
поиск объектов на карте, u[hjdZ похожих объектов
по определённым признакам [5
– 7]. Карты могут хра-
нить разнородную информацию, предстаe_ggmx в
растроhf или _dlhjghf b^_. Объём простран-
ст_gghc информации одного и того же участка тер-
ритории с каждым годом у_ebqbается. Данные мо-
гут быть получены за определённый промежуток
j_f_gb и сняты с разных углов и разных масштабов.
Накопление такого рода пространст_gguo данных
e_qzl
несоот_lklие между картами и требует ав-
томатизации. Можно u^_eblv следующие подходы
для решения данной задачи. Много разработок ис-
пользуют корреляционные методы, осноZggu_ на
uqbke_gbb коэффициента корреляции между срав-
ниZ_fufb изображениями [8]. Также сущестm_l
целый ряд алгоритмов и подходов, которые приме-
няют геометрические признаки для сраg_gby схожих
объектов [9]. Вычисляются такие характеристики, как
центр
масс, площадь и периметр uimdehc оболочки, а также их отношения и т.д. Данные методы целесооб-
разно использоZlv, когда объекты идентичны друг
другу, и эти характеристики сохраняются при аффин-
ных преобразоZgbyo. Что касается картографических
объектов, которые расположены на разных масштабах
или изменяются h j_f_gb, то они могут иметь дру-
гую,
но похожую со сраgb\Z_fuf объектом форму.
Чтобы учитыZlv подобные сhcklа, в настоящее
j_fy актиgh применяются методы непрерыgh]h
предстаe_gby бинарных изображений в b^_ границ,
скелета и циркуляров [10,
11], т.е. бинарное изобра-
жение предстаey_l собой объединение непрерыguo
фигур. Отдельную группу состаeyxl методы,
напраe_ggu_ на изe_q_gb_ эскизных характеристик
объекта [12]. Важные исследоZgby _^mlky при ана-
лизе скелета контурных деформаций объекта [13].
Перспективные ноu_ научные исследоZgby направ-
лены на анализ неорганизоZgguo данных и создание
персистентного скелета [14].
После генерализации пространст_ggu_ объекты
упрощаются, происходит
их деформация, исходные
данные на карте могут быть слабо сyaZgu друг с
другом, а на другом масштабе предстаeylv единый
объект. Все это затрудняет применение стандартных
алгоритмов для сопостаe_gby объектов на разных

Алгоритм соf_s_gby пространст_gguo объектов разномасштабных карт на осно_... Еремеев С.В., Андрианов Д.Е., Титов В.С.
1022 Компьютерная оптика, 2019, том 43, №6
масштабах. Однако один и тот же объект при генера-
лизации сохраняет сhx структуру и глобальные то-
пологические признаки. Таким образом, естест_ggh
использоZlv топологические сhcklа объектов, ко-
торые инZjbZglgu к подобным деформациям и ис-
кажениям [15,
16].
Также очень часто для сопостаe_gby разнород-
ных карт применяют ключеu_ точки [17], например,
точку на центральном перекрестке. Для такого сопо-
стаe_gby карт требуется минимум д_ точки. Однако
чаще k_]h эти ключеu_ точки необходимо проста-
blv jmqgmx. Кроме того, могут быть большие по-
грешности при сопостаe_gbb объектов.
Таким образом, в статье рассматриZ_lky
задача
сопостаe_gby пространст_gguo объектов с дефор-
мациями на разных масштабах. Для её решения за
осноm предлагается aylv методы персистентной
гомологии, которые учитыZxl топологические сhc-
стZ набора точек [18
– 21].
1. Предстаe_gb_ пространственных объектов
на осно_ метода персистентной гомологии
Персистентная гомология относится к методам
топологического анализа данных [22,
23]. Она широ-
ко начинает использоZlvky в разных областях: обра-
ботка изображений, сигналов, анализ ДНК, кластер-
ный анализ, анализ текста [24
– 26]. Суть метода за-
ключается в том, чтобы uy\blv такие структуры,
которые будут устойчиh сохраняться при топологи-
ческих деформациях и искажениях.
В качест_ исходных данных для топологического
анализа будем рассматриZlv контур бинарного изоб-
ражения. Далее на осно_ алгоритма SUSAN (Smallest
Univalue Segment Assimilation Nucleus) из исходного
контура формируется набор характерных точек, кото-
рые описыZxl особенности этого
контура. Исполь-
зуя найденные точки, анализируем контур и сохраня-
ем только точки с указанным шагом. В результате
получим разреженное множестh точек.
Определение 1. Разреженное множестh точек
V
= {v1, v2, ..., vn} – это множестh характерных точек
исходного контура, расположенных друг от друга с
заданным шагом, где n – это количестh точек.
Строительными блоками для топологического
анализа яeyxlky симплексы.
Определение 2. k-мерным симплексом  будем
назыZlv uimdemx оболочку из k
+ 1 аффинно-
незаbkbfuo точек, т.е.
 = a0, a1, ..., ak.
В работе используются симплексы следующих
размерностей: 0, 1 и 2. Причём при k
= 0 симплекс
яey_lky точкой, при k = 1 – отрезком, а при k = 2 –
треугольником (рис. 1).
Пример разреженного множестZ точек, получен-
ного из бинарного изображения (рис. 2а), показан на
рис. 2б.
Определение 3. Симплициальный комплекс K
предстаey_l собой конечное множестh симплексов
при услоbb, что граница каждого симплекса принад-
лежит K и для дmo любых симплексов справедлиh: 
1  2 =  или  1  2 имеют общую грань
(
1, 2  K).
Пример симплициального комплекса можно b-
деть на рис. 2г, который dexqZ_l множестh сим-
плексов в b^_ точек, отрезков и треугольников.

Рис. 1. Симплексы в b^_ точки, отрезка и треугольника
Определение 4. k-мерной цепью будем назыZlv
подмножестh k-мерных симплексов в симплициаль-
ном комплексе K.
Например, на рис. 2б 0-мерные цепи предстаeyxl
собой произhevgh_ подмножестh точек из множестZ
V. Общее количестh подмножеств из этих точек раgh
2
n. По аналогии, одномерные цепи – это подмножества
из отрезков, а дmf_jgu_ – из треугольников.
Определение 5. Группой цепей C
k яey_lky мно-
жестh k-мерных цепей симплициального комплекса K.
Определение 6. k-мерный цикл – это замкнутая
последоZl_evghklv из цепей размерности k.
Например, на рис. 2д сформироZgu циклы, кото-
рые образоZgu замкнутой последоZl_evghklvx от-
резков.
Определение 7. Группа циклов Z
k – это множестh
циклов размерности k симплициального комплекса K.
Определение 8. k-мерная граница – это замкнутая
последоZl_evghklv из k-мерных цепей hdjm] сим-
плексов размерности k
+ 1.
Например, границей для дmf_jgh]h симплекса
(треугольника) будут три одномерных симплекса (три
отрезка).
Определение 9. Группа границ B
k – это множе-
стh k-мерных границ симплициального комплекса K,
при этом
B
k  Ck.
Определение 10. k-я гомологическая группа пред-
стаey_l собой фактор-группу H
k = Zk /Bk и состоит из
гомологических классов.
В работе используются фактор-группы H
0 и H 1,
для которых гомологическими классами яeyxlky
компоненты сyaghklb и пустоты соот_lklенно.
Пустоты на плоскости обычно назыZxl дырами,
которые ограничены отрезками.
Чтобы определить количестh компонент сyagh-
сти и количестh дыр, применяются числа Бетти 
0 и

1, которые описыZxl топологические особенности
симплициального комплекса и uqbkeyxlky как ранг
фактор-группы: 
k = rank (H k). В то же j_fy:
rank (H k) = rank (Zk) – rank (Bk). Ранг группы соот_l-
стm_l мощности минимального подмножестZ по-
рождающих её элементов.
Например, пусть симплициальный комплекс со-
стоит из трёх точек и трёх отрезков, соединяющих
эти точки, т.е.:
 123121323 , K= v ,v ,v v,v ,v,v ,v,v ,

Алгоритм соf_s_gby пространст_gguo объектов разномасштабных карт на осно_... Еремеев С.В., Андрианов Д.Е., Титов В.С.
Компьютерная оптика, 2019, том 43, №6 1023
где v iV (i = 1, 2, 3).
Для k = 1 получим:
1) множестh одномерных цепей в b^_ отрезков
 

11213231213
12 23 13 23
12 13 23 ,,, , ,
,,
+; C K = v ,v v ,v v ,v v ,v v ,v
v,v + v ,v v,v + v ,v
v,v v,v v ,v


2) множестh циклов, образоZgguo отрезками
  111223 3Z K = , v ,v + v ,v + v ,v ;
3) пустое множестh границ
1BK= .
При этом rank
(Hk) = 1, т.е. количестh дыр раgh
1. Если же рассматриZlv треугольник как дmf_jguc
симплекс, то количестh дыр раgh 0. В обоих случа-
ях количестh компонент сyaghklb раgh 1.
Например, на рис. 2
г присутстm_l 5 компонент
сyaghklb и 0 дыр, а на рис. 2
д – 1 компонента сya-
ности и 4 дыры.
Определение 11. Фильтрация
K0  K1  K2  ...  Kn –
это eh`_ggZy последоZl_evghklv симплициальных
комплексов.
Определение 12. Персистентная гомология
i, j
kH –
это множество
k-х гомологических классов для филь-
трации
K0  K1  K2  ...  Kn, причём создание класса
происходит в симплициальном комплексе
Ki и его су-
ществоZgb_ продолжается до
Kj (i, j  0, 1, 2, ..., n; i < j).
Процесс формирования симплициальных ком-
плексов в заbkbfhklb от радиуса u]ey^bl следую-
щим образом (рис. 2
б-ж). Вокруг каждой точки из
разреженного множестZ
V строится круг радиуса r.
Начальным расстоянием
r яey_lky минимальное рас-
стояние между точками, максимальное – наибольшее
расстояние. Если круги дmo различных точек пересе-
каются, то эти точки соединяются отрезком. Если же
пересекаются круги трёх точек, то они образуют тре-
угольник. При у_ebq_gbb радиуса количестh сим-
плексов и топологических свойств изменяется: число
симплексов увеличиZ_lky, образуются ноu_ компо-
ненты сyaghklb
и дыры. Дыра существует до тех пор,
пока k_ образующие её точки не будут соединены
друг с другом. При у_ebq_gbb расстояния
r число
компонент сyaghklb станет раgh единице, так как k_
имеющиеся компоненты объединяются в одну
(рис. 2
ж). Симплициальный комплекс, построенный
по такому принципу, назыZxl комплексом Чеха [27].
Определение 13.
k-баркодом для фильтрации
симплициальных комплексов множестZ точек
V бу-
дем назыZlv множестh пар b^Z:
    barcode kiiV= d,l ,  1,2 ... i= , ,
где
di – координата создания топологической особен-
ности,
di принимает одно из hafh`guo значений
радиуса
r; li – длина сущестhания топологической
особенности. Например, на рис. 2
з можно b^_lv 1 – баркод,
показыZxsbc информацию о сущестhания каж-
дой дыры.
Топологические особенности, длина которых не
преurZ_l некоторого значения
, будем считать
шумом, искажающим предстаe_gb_ о расположении
объектов. Такие особенности не подлежат рассмотре-
нию. В статье используется значение
, раgh_ 1/3 от
средней длины k_o отрезков баркода. Стойкие осо-
бенности прояeyxlky на длинных отрезках баркода,
длина которых больше
, и яeyxlky основой для
дальнейшего анализа (рис. 2
и).
а) б)
в)
г)
д)
е)
ж)

з)
и)
Рис. 2. Исходное бинарное изображение (а); разреженное
пространстh точек (б); процесс построения
симплициальных комплексов при различных значениях r
(0;11;15;19;27;80) (б,
в, г, д, е, ж); баркод с шумом (з);
баркод без шума (и)

Алгоритм соf_s_gby пространст_gguo объектов разномасштабных карт на осно_... Еремеев С.В., Андрианов Д.Е., Титов В.С.
1024 Компьютерная оптика, 2019, том 43, №6
2. Алгоритм сраg_gby баркодов
пространственных объектов
Исходными данными для сопостаe_gby объектов
яeyxlky два множестZ точек контуров:
X = {x1, x2, ..., xn} и Y = {y1, y2, ..., ym}.
По каждому набору точек строятся баркоды. Рас-
смотрим баркоды
barcode ( ) {( )} ii
1XX X =d,l ( 1, 2, ..., ) X i= w и
barcode ( ) {( )} jj
1
YY Y= d,l (1,2,...,) Y j= w
для анализа дыр. Алгоритм работает аналогично для
анализа компонентов сyaghklb. По сути мы получа-
ем дZ множестZ топологических признаков, кото-
рые содержат данные по каждой дыре. Причём коли-
честh дыр
wX и wY может быть различным. Требуется
на осно_ информации из баркодов определить сте-
пень схожести топологических признаков дmo объ-
ектов. Длинные отрезки баркода соот_lklуют
устойчиuf характеристикам и играют ключеmx
роль при идентификации объектов. Если длины от-
резков баркода меньше некоторого заданного порога,
т.е.
,<ε j
i
X
Y ll (i 1, 2, ..., wX; j1, 2, ..., wY), то они яey-
ются шумом и не dexqZxlky в анализ.
Элементы баркодов barcode
1(X ) и barcode 1(Y ) отсор-
тируем по значениям iXl и jYl в порядке убывания, т.е.
1 ii+ X X ll (i 1, 2, ..., wX –1) и 1 j j+
YY ll (j 1, 2, ..., wY –1).
Найдём наибольший отрезок среди k_o отрезков
дmo баркодов:
1 max max ( ) 1 X Y =l,l . Если 1 max Xl< , то
1 (max/ ) ii
XX Xl=l l (i = 2, 3, ..., wX). Если же 1 max Yl< , то
1 (max/ ) jj
Y
YYl=l l  (j = 2, 3, ..., wY).
После чего uqbkebf сумму:
1
w
X
i
X X
i= S= l  , 1 w
Y
j Y
Y
j=S= l  .
Исходя из общей суммы, определим _k каждого
отрезка в баркодах barcode
1(X ) и barcode 1(Y ):
1 {...} 2w
X p= p ,p , ,p , где iX i X
l
p=
S  1,2 ... X i= , ,w
и
1{...} 2w
Y t= t ,t , ,t , где
jY
j
Yl
t=
S  1,2 ... Y j= , ,w .
Для того чтобы определить похожесть дmo
баркодов, uqbkebf отношение
iXl и jYl, которые
имеют одинакоu_ индексы:
12 min(,){... } XYww z= z ,z , ,z ,
где
/,если,
=
/,иначе,ii i iX YXY
i
ii
YX ll l z
ll


 1, 2, ..., min ( , ) XY i= w w .
В местах, где индекс uoh^bl за пределы одного
из значений
wX или wY, примем, что
min( , ) 1 min( , ) 2 max( , ) ... 0 XY XY XYww ww ww zz z  . Далее умножим значения множестZ
z на соот_l-
стmxsb_ значения максимального по мощности
множестZ
p или t и сложим эти произведения, чтобы
uqbkeblv показатель схожести
Q:
1
1 ,если,
,иначе. X
Yw
ii X Y
i
w
ii
i
zp w w
Q=
zt











(1)
Имея данные показатели для k_o объектов, полу-
чаем hafh`ghklv u^_eblv максимально похожий
по топологии объект и принять его за идентичный.
ИсследоZgby показали, что баркод по дырам
несёт большую часть процента схожести по сравне-
нию с компонентами сyaghklb. Это можно ujZablv
так:
HolePart – доля баркода по дырам, а 1 – HolePart – по компонентам сyaghklb. В статье экс-
периментально принято, что
HolePart = 75, т.е. баркод
по дырам даёт deZ^ 75 процентов, а баркод по ком-
понентам связности – 25. Показатель схожести
Q по
дырам умножается на 0,75, а по компонентам сyagh-
сти – на 0,25. Таким образом, полностью схожие объ-
екты дадут в сумме 100 процентов.
3. Результаты исследований
ИсследоZgb_ проводилось сначала для сопоставле-
ния природных объектов на разных масштабах, а затем
для муниципальных с учетом деформации и искажений.
В качест_ аналога в работе рассмотрено метриче-
ское
сопоставление объектов. В этом методе рассчи-
тыZxlky д_ матрицы расстояний
|| || X
ijr (i, j = 1, 2, ..., n)
и
|| ||Y
ijr (i, j = 1, 2, ..., m) между k_fb точками мно-
жеств
X ={ x1, x2, ..., xn} и Y ={ y1, y2, ..., ym}. Будем счи-
тать, что
n  m. Для количест_gghc оценки uqbkey-
ется параметр X Y
ij ij ij =r r  . Далее для каждой точки
xi  X определяется hafh`gZy сопряжённая ей точка,
исходя из ujZ`_gby:
i = min{ 1i, 2i, ..., ni}. Считает-
ся, что две точки сопряжённые, если
i не превышает
порога
. Далее подсчитыZ_lky количестh сопря-
жённых точек и оцениZ_lky процент схожести отно-
сительно общего числа точек.
3.1. Сопоставление природных объектов
при их масштабироZgbb и деформации
Рассмотрим в качест_ исходных данных два снимка
разных масштабов одного и того же остроZ (рис. 3).
Как b^gh из рисунков, они обладают одной и той же
структурой, но имеют различия по наличию деталей.
а) б)
Рис. 3. Исходные снимки остроZ, сделанные под разным
углом и на разных масштабах: 1:30000 (а), 1:10000 (б)

Алгоритм соf_s_gby пространст_gguo объектов разномасштабных карт на осно_... Еремеев С.В., Андрианов Д.Е., Титов В.С.
Компьютерная оптика, 2019, том 43, №6 1025
При_^zf два изображения к бинарному b^m на
основе метода Отсу после предZjbl_evgh]h сглажи-
Zgby исходных изображений с параметром размытия
по Гауссу, раghfm 3 (рис. 4
а, б). Кроме того, для би-
нарного изображения (рис. 4
б) uihegbf сглажиZ-
ние контура со значением 10 пикселей (рис. 4
в).
Далее каждое бинарное изображение предстаbf в
b^_ разреженного пространстZ точек и построим
баркоды.
На рис. 5 показаны 1 – баркоды объектов.
Те топологические особенности, которые не несут
ключеhc информации, будем считать шумом. Барко-
ды без шума имеют более похожую общую структуру
и, соот_lklенно, схожесть объектов между собой.
Численные характеристики для сравнения объек-
тов
по их баркодам без шума при_^_gu в табл. 1, а в
табл. 2 – при метрическом сопостаe_gbb.
Табл. 1. Численные характеристики топологической
схожести природных объектов на разных масштабах
ОстроZ
б в
а 63,35 24,55 87,90 63,30 22,02 85,32
б 67,14 24,75 91,89
Для каждой пары объектов указана схожесть по
дырам, компонентам сyaghklb и итогоZy.
Табл. 2. Численные характеристики при метрическом
сопостаe_gbb природных объектов на разных масштабах
ОстроZ
б в
а 89 67
б
72
3.2. Сопоставление муниципальных объектов
при их деформации
Сопостаe_gb_ объектов в муниципальных ГИС
осложняется u^_e_gb_f контуров в сyab с наличием
перекрыZxsboky объектов на карте. Над исходным
зданием (рис. 6
а) uihegbf деформацию за счёт _jlb-
кального сжатия на 20 % и горизонтального растяжения
также на 20 % (рис. 6 б). Чтобы получить изображение
на рис. 6
в, сделаем искажения jmqgmx в отдельных
углоuo частях бинарного изображения на рис. 6
б. Да-
лее проводим аналогичные исследоZgby, как в подпа-
раграфе 3.1, результаты которых показаны на рис. 7,
8.
Численные характеристики схожести, uqbke_g-
ные по ujZ`_gbx (1) и при метрическом соf_s_-
нии точек, предстаe_gu в табл. 3 и 4.
а) б) в)
Рис. 4. Бинарные изображения остроZ с разных масштабов (а, б); деформация бинарного изображения (в)

а)
б) в)
г) д) е)
Рис. 5. Баркоды объектов с шумом (а, в, д); без шума (б, г, е) для бинарных изображений из рис. 4
а)
б) в)
Рис. 6. Бинарные изображения муниципальных объектов: исходный объект (а); здание с растяжением (б);
здание с растяжением и искажениями (в)

Алгоритм соf_s_gby пространст_gguo объектов разномасштабных карт на осно_... Еремеев С.В., Андрианов Д.Е., Титов В.С.
1026 Компьютерная оптика, 2019, том 43, №6
а) б) в)
Рис. 7. Разреженное пространстh точек муниципальных объектов
а) б) в)
г) д) е)
Рис. 8. Баркоды муниципальных объектов с учётом деформации и искажений с шумом (а, в, д;); без шума (б, г, е)
Табл. 3. Численные характеристики топологической
схожести муниципальных объектов при деформациях
и искажениях
Муниципальные объекты
б в
а 50,17 23,87 74,04 63,25 24,35 87,60
б 60,33 24,50 84,83
Табл. 4. Численные характеристики при метрическом
соf_s_gbb муниципальных объектов с учётом
деформации и искажений
Муниципальные объекты
б в
а 73 54
б
75
Анализ результатов показыZ_l близкое соf_s_-
ние баркодов при незначительных удалениях деталей
после деформации. Даже при сильном масштабироZ-
нии структура объекта сохраняется. Т.е. глобальные
характеристики исходного объекта соiZ^Zxl с гло-
бальными характеристиками объекта после генерали-
зации или масштабироZgby, несмотря на то что де-
тальная информация на одном из объектов карты от
-
сутстm_l. При анализе муниципальных объектов так-
же были uy\e_gu общие топологические особенно-
сти между объектами после деформации и искажений.
При сраg_gbb с метрическим сопоставлением пред-
ложенный подход показал преимущестZ при анализе
объектов, которые под_j`_gu значительной дефор-
мации при масштабироZgbb, а также при искажениях.
Для исследоZgby при сопостаe_gbb разных про-
странст_gguo
объектов были aylu бинарные изоб-
ражения остроZ (рис. 4
б) и муниципального объекта
(рис. 6
а). В результате работы алгоритма схожесть объектов составила 56,23
%, dexqZy схожесть по
дырам (32,68 % из 75 % hafh`guo) и схожесть по
компонентам сyaghklb (23,55 % из 25 % допусти-
мых). Анализ показыZ_l, что осноgh_ различие до-
стигается за счёт несоот_lklия баркодов по дырам,
в то j_fy как по компонентам сyaghklb баркоды
имеют достаточно близкое значение.
Заключение
В статье рассмотрена задача сопостаe_gby объек-
тов на разнородных картах. Осноm алгоритма со-
стаey_l анализ формы объектов, которые под_j]Z-
ются масштабироZgbx, генерализации,
деформаци-
ям и искажениям, однако общая структура объекта
сохраняется. К таким деформациям инZjbZglgu ме-
тоды персистентной гомологии. Для сопостаe_gby
объектов из разных карт анализируются их баркоды.
При_^_gu результаты исследоZgbc сопостаe_gby
пространст_gguo объектов для природных и муни-
ципальных карт. Про_^zggu_ эксперименты показа-
ли, что основное ebygb_ на схожесть объектов при
их соf_s_gbb
оказыZxl топологические особенно-
сти в b^_ дыр. Чем больше у исходных объектов
устойчиuo дыр, тем больше будет качестh при их
соf_s_gbb. Разработанный подход может быть ис-
пользоZg, например, для решения задачи аlhfZlb-
ческого заполнения атрибутиguo данных карты од-
ного масштаба на осно_ данных карты другого мас-
штаба. Это позhebl осущестblv
более быструю
интеграцию пространст_gguo и семантических дан-
ных многомасштабных карт.
Благодарности
ИсследоZgb_ uiheg_gh при финансовой под-
держке РФФИ и администрации Владимирской обла-
сти в рамках научного проекта № 17-47-330387.

Алгоритм соf_s_gby пространст_gguo объектов разномасштабных карт на осно_... Еремеев С.В., Андрианов Д.Е., Титов В.С.
Компьютерная оптика, 2019, том 43, №6 1027
Литература
1. Wallgrün, J. Qualitative matching of spatial information /
J.O. Wallgrün, D. Wolter, K. Richter // GIS: Proceedings of
the ACM International Symposium on Advances in Geo-
graphic Information Systems. – 2010. – P. 300-309.
2. Mustière, S. Matching networks with different levels of
detail / S. Mustière, T. Devogele // GeoInformatica. – 2008.
– Vol. 12, Issue 4. – P. 435-453.
3. Biedl, T. Planar matchings for weighted straight skeletons /
T. Biedl, S. Huber, P. Palfrader // International Journal of
Computational Geometry and Applications. – 2016.
Vol. 26, Issues 3-4. – P. 211-229.
4. Ефимов, А.И. Алгоритм поэтапного уточнения проек-
тиgh]h преобразоZgby для соf_s_gby изображений /
А.И. Ефимов, А.И. Ноbdh\ // Компьютерная оптика. –
2016. – Т. 40, № 2. – С. 258-265. – DOI: 10.18287/2412-
6179-2016-40-2-258-265.
5. Zhao, L. Shape matching algorithm based on shape con-
texts / L. Zhao, Q. Peng, B. Huang // IET Computer Vision.
– 2015. – Vol. 9, Issue 5. – P. 681-690.
6. Eremeev, S.V. Comparison of urban areas based on data-
base of topological relationships in geoinformational sys-
tems / S.V. Eremeev, D.E. Andrianov, V.A. Komkov // Pat-
tern Recognition and Image Analysis. – 2015. – Vol. 25,
No 2. – P. 314-320.
7. Eremeev, S. An approach to establishing the correspond-
ence of spatial objects on heterogeneous maps based on
methods of computational topology / S. Eremeev,
K. Kuptsov, S. Romanov. – In: Analysis of images, social
networks and texts (AIST 2017) / ed. by W. van der Aalst
[et al.]. – Cham: Springer, 2018. – P. 172-182.
8. Zhang, T. Multi-task correlation particle filter for robust
object tracking / T. Zhang, C. Xu, M. Yang // IEEE Confer-
ence on Computer Vision and Pattern Recognition. – 2017.
Vol. 1(2). – P. 4819-4827.
9. Садыков, С.С. Алгоритм построения uimdehc оболочки
бинарного изображения и формирование его безразмерных
признаков / С.С. Садыков // Алгоритмы, методы и системы
обработки данных. – 2015. – № 2(31). – С. 77-85.
10. Ломов, Н.А. Площадь дискового покрытия – дескрип-
тор формы изображения / Н.А. Ломов, Л.М
. Местецкий
// Компьютерная оптика. – 2016. – Т. 40, № 4. – С. 516-
525. – DOI: 10.18287/2412-6179-2016-40-4-516-525.
11. Ломов, Н.А. Классификация дmf_jguo фигур с ис-
пользоZgb_f скелетно-геодезических гистограмм тол-
щин-расстояний / Н.А. Ломов, С.В. Сидякин, Ю.В. Ви-
зильтер // Компьютерная оптика. – 2017. – Т. 41, № 2. –
С. 227-236. – DOI: 10.18287/2412-6179-2017-41-2-227-236.
12. Eitz, M. Sketch-based shape retrieval / M. Eitz, R. Richter,
T. Boubekeur, K. Hildebrand, M. Alexa // ACM Transac-
tions on Graphics. – 2012. – Vol. 31, Issue 4. – 31.
13. Bai, X. Path similarity skeleton graph matching / X. Bai,
L.J. Latecki // IEEE Transactions on Pattern Analysis and Ma-
chine Intelligence. – 2008. – Vol. 30, Issue 7. – P. 1282-1292.
14. Kališnik, S. A higher-dimensional homologically persis-
tent skeleton / S. Kališnik, V. Kurlin, D. Lesnik // Advanc-es in Applied Mathematics. – 2019. – Vol. 102. – P. 113-
142.
15. Carlsson, G.
Persistence barcodes for shapes / G. Carlsson,
A. Zomorodian, A. Collins, L. Guibas // Proceedings of the
2004 Eurographics, ACM SIGGRAPH Symposium on Ge-
ometry Processing. – 2004. – P. 124-135.
16. Skraba, P. Persistence-based segmentation of deformable
shapes / P. Skraba, M. Ovsjanikov, F. Chazal, L. Guibas //
2010 IEEE Computer Society Conference on Computer Vi-
sion and Pattern Recognition – Workshops. – 2010. – P. 45-
52.
17. Förstner, W. Detecting interpretable and accurate scale-
invariant keypoints / W. Förstner, T. Dickscheid, F. Schind-
ler // IEEE 12
th International Conference on Computer Vi-
sion. – 2009. – P. 2256-2263.
18. Su, Y. Contour guided hierarchical model for shape match-
ing / Y. Su, Y. Liu, B. Cuan, N. Zheng // IEEE International
Conference on Computer Vision (ICCV). – 2015. –
P. 1609-1617.
19. Ahmed, M. Local persistent homology based distance be-
tween maps / M. Ahmed, B. Fasy, C. Wenk // Proceedings
of the 22nd ACM SIGSPATIAL International Conference
on Advances in Geographic Information Systems. – 2014. –
P. 43-52.
20. Bendich, P. Homology and robustness of level and in-
terlevel sets / P. Bendich, H. Edelsbrunner, D. Morozov,
A. Patel // Homology, Homotopy and Applications. – 2013.
Vol. 15. – P. 51-72.
21. Collins, A. A barcode shape descriptor for curve point cloud
data / A. Collins, A. Zomorodian, G. Carlsson, L. Guibas //
Computers and Graphics. – 2004. – Vol. 28. – P. 881-894.
22. Carlsson, E. An algebraic topological method for feature
identification / E. Carlsson, G. Carlsson, V. de Silva, S. For-
tune // International Journal of Computational Geometry
and Applications. – 2006. Vol. 16(4). – P. 291-314.
23. Carlsson, G. Topological pattern recognition for point cloud
data / G. Carlsson // Acta Numerica. – 2014. – Vol. 23. –
P. 289-368.
24. Lum, P.Y. Extractng insights from the shape of complex
data using topology / P.Y. Lum, G. Singh, A. Lehman,
T. Ishkanov, M. Vejdemo-Johansson, M. Alagappan,
J. Carlsson, G. Carlsson // Scientific Reports. – 2013. –
Vol. 3. – P. 12-36.
25. Макаренко, Н.Г. РаспознаZgb_ текстур на цифроuo
изображениях методами uqbkebl_evghc топологии /
Н.Г. Макаренко, Ф.А. Уртьев, И.
С. КнязеZ,
Д.Б. МалкоZ, И.Т. Пак, Л.М. КаримоZ // Соj_f_ggu_
проблемы дистанционного зондироZgby Земли из кос-
моса. – 2015. – Т. 12, № 1. – С. 131-144.
26. Zhu, X. Persistent homology: An introduction and a new
text representation for natural language processing / X. Zhu
// Proceedings of the Twenty-Third International Joint Con-
ference on Artificial Intelligence. – 2013. – P. 1953-1959.
27. Edelsbrunner, H. Computational topology: An introduc-
tion / H. Edelsbrunner. – American Mathematical Society,
2009.


С_^_gby об авторах
Еремеев Сергей Владимироbq, 1980 года рождения, кандидат технических наук, доцент, работает на ка-
федре информационных систем Муромского института (филиала) Владимирского государст_ggh]h уни_jkb-
тета. Область научных интересов: обработка пространст_gguo данных, геоинформационные системы, тополо-
гический анализ данных. E-mail:
sv-eremeev@yandex.ru .

Алгоритм соf_s_gby пространст_gguo объектов разномасштабных карт на осно_... Еремеев С.В., Андрианов Д.Е., Титов В.С.
1028 Компьютерная оптика, 2019, том 43, №6
Андрианов Дмитрий Евгеньеbq, 1973 года рождения, доктор технических наук, доцент, за_^mxsbc
кафедрой информационных систем Муромского института (филиала) Владимирского государст_ggh]h уни-
_jkbl_lZ. Область научных интересов: исследоZgb_ теоретических основ обработки пространст_gguo дан-
ных, разработка методов и моделей обработки и анализа данных в геоинформационных системах, топология
пространст_ggh-распределенных объектов. E-mail: AndrianovDE@inbox.ru .

Титов Виталий Семеноbq, 1943 года рождения, доктор технических наук, профессор, за_^mxsbc
кафедрой uqbkebl_evghc техники Юго-западного государст_ggh]h уни_jkbl_lZ. Область научных инте-
ресов: распознаZgb_ образов и цифроZy обработка изображений. E-mail: titov-kstu@rambler.ru .

ГРНТИ: 28.23.15.
Поступила в редакцию 14 янZjy 2019 г. Окончательный ZjbZgl – 29 июля 2019 г.


An algorithm for matching spatial objects of different-scale maps
based on topological data analysis
S.V. Eremeev 1, D.E. Andrianov 1, V.S. Titov 2 1 Vladimir State University, Vladimir, Russia, 2 Southwest State University, Kursk, Russia
Abstract
A problem of automatic comparison of spatial objects on maps with different scales for the
same locality is considered in the article. It is proposed that this problem should be solved using
methods of topological data analysis. The initial data of the algorithm are spatial objects that can
be obtained from maps with different scales and subjected to deformations and distortions. Persis-
tent homology allows us to identify the general structure of such objects in the form of topological
features. The main topological features in the study are the connectivity components and holes in
objects. The paper gives a mathematical description of the persistent homology method for repre-
senting spatial objects. A definition of a barcode for spatial data, which contains a description of
the object in the form of topological features is given. An algorithm for comparing feature bar-
codes was developed. It allows us to find the general structure of objects. The algorithm is based
on the analysis of data from the barcode. An index of objects similarity in terms of topological fea-
tures is introduced. Results of the research of the algorithm for comparing maps of natural and
municipal objects with different scales, generalization and deformation are shown. The experi-
ments confirm the high quality of the proposed algorithm. The percentage of similarity in the
comparison of natural objects, while taking into account the scale and deformation, is in the range
from 85 to 92, and for municipal objects, after stretching and distortion of their parts, was from 74
to 87. Advantages of the proposed approach over analogues for the comparison of objects with
significant deformation at different scales and after distortion are demonstrated.
Keywords : persistent homology, barcode of spatial object, comparison of objects, analysis of
topological features, multi-scale maps.
Citation : Eremeev SV, Andrianov DE, Titov VS. An algorithm for matching spatial objects of
different-scale maps based on topological data analysis. Computer Optics 2019; 43(6): 1021-1029.
DOI: 10.18287/2412-6179-2019-43-6-1021-1029.
Acknowledgements : The work was funded by the Russian Foundation for Basic Research
(RFBR) and Vladimir region authorities under the research project No. 17-47-330387.
References
[1] Wallgrün J, Wolter D, Richter K. Qualitative matching of
spatial information. GIS: Proceedings of the ACM Interna-
tional Symposium on Advances in Geographic Information
Systems 2010: 300-309.
[2] Mustière S, Devogele T. Matching networks with different
levels of detail. GeoInformatica 2008; 12(4): 435-453.
[3] Biedl T, Huber S, Palfrader P. Planar matchings for weighted
straight skeletons. International Journal of Computational
Geometry and Applications 2016; 26(3-4): 211-229.
[4] Efimov AI, Novikov AI. An algorithm for multistage pro-
jective transformation adjustment for image superimposi-
tion [In Russian]. Computer Optics 2016; 40(2): 258-265.
DOI: 10.18287/2412-6179-2016-40-2-258-265. [5] Zhao L, Peng Q, Huang B. Shape matching algorithm based
on shape contexts. IET Comp Vis 2015; 9(5): 681-690.
[6] Eremeev SV, Andrianov DE, Komkov VA. Comparison of
urban areas based on database of topological relationships
in geoinformational systems. Pattern Recognition and Im-
age Analysis 2015; 25(2): 314-320.
[7] Eremeev S, Kuptsov K, Romanov S. An approach to estab-
lishing the correspondence of spatial objects on heteroge-
neous maps based on methods of computational topology.
In Book: van der Aalst W, et al, eds. Analysis of images,
social networks and texts (AIST 2017). Cham: Springer;
2018: 172-182.
[8] Zhang T, Xu C, Yang M. Multi-task correlation particle
filter for robust object tracking. IEEE Conf Comp Vis Pat-
tern Recogn 2017; 1(2): 4819-4827.

Алгоритм соf_s_gby пространст_gguo объектов разномасштабных карт на осно_... Еремеев С.В., Андрианов Д.Е., Титов В.С.
Компьютерная оптика, 2019, том 43, №6 1029
[9] Sadykov SS. Algorithm for the construction of a convex
hull of a binary image and the formation of its dimension-
less features [In Russian]. Algorithms, Methods and Data
Processing Systems 2015; 2(31): 77-85.
[10] Lomov NA, Mestetskiy LM. Area of the disk cover as an image
shape descriptor [In Russian]. Computer Optics 2016; 40(4):
516-525. DOI: 10.18287/2412-6179-2016-40-4-516-525.
[11] Lomov NA, Sidyakin SV, Visilter YuV. Classification of two-
dimensional figures using skeleton-geodesic histograms of
thicknesses and distances. Computer Optics 2017; 41(2): 227-
236. DOI: 10.18287/2412-6179-2017-41-2-227-236.
[12] Eitz M, Richter R, Boubekeur T, Hildebrand K, Alexa M.
Sketch-based shape retrieval. ACM Transactions on
Graphics 2012; 31(4): 31.
[13] Bai X, Latecki LJ. Path similarity skeleton graph match-
ing. IEEE Transactions on Pattern Analysis and Machine
Intelligence 2008; 30(7): 1282-1292.
[14] Kališnik S, Kurlin V, Lesnik D. A higher-dimensional
homologically persistent skeleton. Advances in Applied
Mathematics 2019; 102: 113-142.
[15] Carlsson G, Zomorodian A, Collins A, Guibas L. Persis-
tence barcodes for shapes. Proc 2004 Eurographics, ACM
SIGGRAPH Symposium on Geometry Processing 2004:
124-135.
[16] Skraba P, Ovsjanikov M, Chazal F, Guibas L. Persistence-
based segmentation of deformable shapes. Proc CVPRW
2010: 45-52.
[17] Förstner W, Dickscheid T, Schindler F. Detecting inter-
pretable and accurate scale-invariant keypoints. IEEE 12
th
ICCV 2009: 2256-2263.
[18] Su Y, Liu Y, Cuan B, Zheng N. Contour guided hierarchical
model for shape matching. IEEE ICCV 2015: 1609-1617. [19] Ahmed M, Fasy B, Wenk C. Local persistent homology
based distance between maps. Proceedings of the 22nd
ACM SIGSPATIAL International Conference on Advanc-
es in Geographic Information Systems 2014: 43-52.
[20] Bendich P, Edelsbrunner H, Morozov D, Patel A. Homol-
ogy and robustness of level and interlevel sets. Homology,
Homotopy and Applications 2013; 15: 51-72.
[21] Collins A, Zomorodian A, Carlsson G, Guibas L. A bar-
code shape descriptor for curve point cloud data. Comput-
ers and Graphics 2004; 28: 881-894.
[22] Carlsson E., Carlsson G., de Silva V., and Fortune S. An
algebraic topological method for feature identification. In-
ternational Journal of Computational Geometry and Appli-
cations 2006; 16(4): 291-314.
[23] Carlsson G. Topological pattern recognition for point
cloud data. Acta Numerica 2014; 23: 289-368.
[24] Lum PY, Singh G, Lehman A, Ishkanov T, Vejdemo-
Johansson M, Alagappan M, Carlsson J, Carlsson G. Ex-
tractng insights from the shape of complex data using to-
pology. Sci Rep 2013; 3: 12-36.
[25] Makarenko ND, Yuriev FA, Knyazeva IS, Malkova DB,
Pak IT, Karimova LM. Texture recognition on digital im-
ages using computational topology methods [In Russian].
Modern problems of remote sensing the Earth from space
2015; 12(1): 131-144.
[26] Zhu X. Persistent homology: An introduction and a new
text representation for natural language processing. In:
Proceedings of the 23rd International Joint Conference on
Artificial Intelligence 2013: 1953-1959.
[27] Edelsbrunner H. Computational topology: An introduction.
American Mathematical Society; 2009.


Author’s information
Sergey Vladimirovich Eremeev (b. 1980), candidate of Technical Sciences, Associate Professor. Currently he works
at Information Systems department, Murom Institute (branch) of Vladimir State University. Research interests are spatial
data processing, geographic information systems and topological data analysis. E-mail:
sv-eremeev@yandex.ru .

Dmitry Evgenyevich Andrianov (b. 1973), doctor of Engineering, Associate Professor, Head of Information Sys-
tems department of MI VlSU. Research interests are theoretical bases of spatial data processing, development of meth-
ods and models of data processing, data analysis in geoinformation systems and topology of spatially distributed ob-
jects. E-mail:
AndrianovDE@inbox.ru .

Vitaliy Semenovich Titov (b. 1943), doctor of Engineering, professor, Head of Computer Technology department
of SWSU. Research interests are image recognition and digital image processing.
E-mail: titov-kstu@rambler.ru .

Received January 14, 2019. The final version – July 29, 2019.