Segmentation of geospatial rasters: analysis of the temporal characteristics of the AREAONAREAOVERLAYER algorithm
This paper investigates the performance of the AreaOnAreaOverlayer algorithm used for segmenting geospatial rasters based on elevation features within the FME environment. The main focus is on analyzing the algorithm’s temporal characteristics when processing large volumes of data, particularly in v...
Збережено в:
| Дата: | 2025 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
PROBLEMS IN PROGRAMMING
2025
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/840 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| _version_ | 1859502943361826816 |
|---|---|
| author | Tsaryniuk, O.V. Glybovets, A.M. |
| author_facet | Tsaryniuk, O.V. Glybovets, A.M. |
| author_sort | Tsaryniuk, O.V. |
| baseUrl_str | https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| collection | OJS |
| datestamp_date | 2025-11-03T10:06:23Z |
| description | This paper investigates the performance of the AreaOnAreaOverlayer algorithm used for segmenting geospatial rasters based on elevation features within the FME environment. The main focus is on analyzing the algorithm’s temporal characteristics when processing large volumes of data, particularly in vegetation cover classification tasks. The study describes the experimental setup, typical input data, and the impact of polygon geometric parameters on execution time. The results provide insight into the algorithm’s application limits and reveal dependencies between the structure of input data and computational complexity.Prombles in programming 2025; 2: 87-97 |
| first_indexed | 2025-09-17T09:25:14Z |
| format | Article |
| fulltext |
Аналітика даних
87
© O.В. Царинюк, A.М. Глибовець, 2025
ISSN 1727-4907. Проблеми програмування. 2025. №2
УДК 004.62, 004.67 https://doi.org/10.15407/pp2025.02.087
О.В. Царинюк, А.М. Глибовець
СЕГМЕНТАЦІЯ ГЕОПРОСТОРОВИХ РАСТРІВ:
АНАЛІЗ ЧАСОВИХ ХАРАКТЕРИСТИК АЛГОРИТМУ
AREAONAREAOVERLAYER
У статті досліджується продуктивність алгоритму AreaOnAreaOverlayer, що використовується для сег-
ментації геопросторових растрів за ознаками висоти в середовищі FME. Основну увагу приділено ана-
лізу часових характеристик алгоритму під час обробки великих обсягів даних, зокрема, в задачах кла-
сифікації рослинного покриву. Описано експериментальне середовище, типові вхідні дані та вплив ге-
ометричних параметрів полігонів на час виконання операції. Отримані результати дають змогу оцінити
межі застосування алгоритму та виявити залежності між структурою вхідних даних і обчислювальною
складністю.
Ключові слова: просторовий аналіз, сегментація растрів, геоінформаційні системи, часові характерис-
тики, продуктивність алгоритму
O.V. Tsaryniuk, A.M. Hlybovets
SEGMENTATION OF GEOSPATIAL RASTERS: ANALYSIS
OF THE TEMPORAL CHARACTERISTICS OF THE
AREAONAREAOVERLAYER ALGORITHM
This paper investigates the performance of the AreaOnAreaOverlayer algorithm used for segmenting
geospatial rasters based on elevation features within the FME environment. The main focus is on analyzing the
algorithm’s temporal characteristics when processing large volumes of data, particularly in vegetation cover
classification tasks. The study describes the experimental setup, typical input data, and the impact of polygon
geometric parameters on execution time. The results provide insight into the algorithm’s application limits and
reveal dependencies between the structure of input data and computational complexity.
Keywords: spatial analysis, raster segmentation, geographic information systems, temporal characteristics,
algorithm performance
.
Вступ
В останні десятиліття геопросторові
дані все більше інтегруються у різні сфери
людської діяльності. Якщо раніше геоін-
формаційні системи знаходили застосу-
вання лише в окремих галузях, на кшталт
логістики чи військової справи, то зараз
складно знайти галузь, яка не використо-
вує карти чи геопросторові дані. Перед
виробництвом геопросторових даних пос-
тають виклики, коли потрібно створювати
більш точні геодані, у стисліші терміни та
за меншу собівартість.
Основним джерелом геопросторових
даних є засоби дистанційного зондування
Землі (ДЗЗ). До цих засобів належать су-
путникові знімки, аерофотозйомка, лідарна
зйомка, радіолокаційна зйомка та інші.
Кожен із цих засобів має свої обмеження
до застосування та специфіку обробки
отриманих даних. Наприклад, супутнико-
вий знімок несе в собі спектральні харак-
теристики об’єктів, але на ньому відсутня
інформація про висотну складову, а на 3D-
моделі радіолокаційної зйомки відсутня
інформація про типи об’єктів, розташовані
на цій моделі. Лідарна зйомка дозволяє
отримати інформацію про земну поверхню
у тривимірному просторі, включно із ти-
пами об’єктів. Але вона має певні обме-
ження, зокрема, через необхідність вико-
ристання літальних апаратів із відносно
вузькою смугою охоплення (до 2 км за
проліт) та значний обсяг вихідних даних,
який коливається в межах 100–10 000
МБ/км².
Аналітика даних
88
Огляд літератури
Стрімкий розвиток технологій машин-
ного навчання уможливив вдосконалення
існуючих технологій отримання геоданих.
У дешифруванні супутникових знімків
широко застосовуються згорткові моделі,
U-Net [1], ResNet [2], що дозволило значно
заощадити ресурси на ручній векторизації
супутникових зображень. Математичні
моделі, описані у працях Liu, et al [3,4]
дозволили створювати висотні моделі міс-
цевості (DHM) з глобальним покриттям
завдяки поєднанню відкритих даних ліда-
рної зйомки та супутникових знімків висо-
кої роздільної здатності.
Сегментація зображень є однією з най-
складніших задач обробки зображень. На
сьогодні існує багато підходів і методів
сегментації, зокрема, методи сегментації
описані в роботах Hofmann & Tiede [5] та
Mueller & Corcoran [6]. Більшість дослі-
джень у сфері сегментації рослинності зо-
середжені на визначенні індивідуальних
крон дерев. Цей напрям відіграє ключову
роль у детальному вивченні лісових екоси-
стем, що підтверджується роботами Douss,
et al [7], Li, et al [8], Lindberg, et al [9], а
також Jakubowski, et al [10]. Завдяки цим
дослідженням було значно поглиблено
наше розуміння характеристик окремих
дерев, структури лісів та розподілу біо-
маси.
На відміну від детального аналізу ок-
ремих крон дерев, наше дослідження
спрямоване на розробку методів узагаль-
неної сегментації, що дозволяють виділяти
великі масиви рослинності з подібними
(або майже однаковими) висотними харак-
теристиками. Такі підходи є ефективними
для сегментації рослинного покриву на
великих територіях, наприклад, на рівні
цілих країн. Це особливо важливо для ана-
лізу рослинності, необхідного для регіона-
льних і національних екологічних оцінок,
планування землекористування та реаліза-
ції масштабних природоохоронних -
заходів.
Попередня робота
У попередній частині дослідження
Tsaryniuk, et al [11] було розроблено три
різні підходи до сегментації геопросторо-
вих растрів: методом згорткових фільтрів,
методом рандомних точок та методом гек-
сагонів. Кожен із методів використовує
різні підходи до сегментації та має свої
особливості.
Метод згорткових фільтрів має пере-
вагу у вигляді можливості обробляти ве-
ликі растри цілісно, без розділення на час-
тини. Проте його використання ускладню-
ється у випадках, коли потрібно працюва-
ти з окремими тайлами: на стиках виника-
ють відмінності в даних, що унеможлив-
лює подальше об’єднання результатів в
єдиний набір. Крім того, перетворення
растрового зображення у векторну форму є
складним під час обробки великих об’ємів
даних, а також цей метод схильний до
створення полігонів малої площі, які пот-
ребують додаткової фільтрації або уза-
гальнення.
Метод рандомних точок дозволяє па-
ралельно обробляти окремі полігони, на
яких генеруються точки, що сприяє під-
вищенню продуктивності. Водночас він
вимагає наявності додаткового векторного
шару, який підлягає сегментації, тоді як
інші методи працюють безпосередньо з
растровими даними. У деяких випадках
полігони, які використовуються для гене-
рації точок, можуть бути надто великими,
що ускладнює та уповільнює процес -
обробки.
Метод гексагонів також забезпечує
можливість паралельної обробки як на рів-
ні растрових даних, так і на рівні векторної
сітки гексагонів. Він не потребує додатко-
вих векторних шарів, на противагу методу
рандомних точок. Водночас точність ре-
зультатів методу гексагонів дещо нижча
порівняно з методом згорткових фільтрів.
Оцінка точності цих методів показала,
що всі три методи мають достатньо висо-
кий показник точності. Для подальшої ро-
боти було обрано метод гексагонів як най-
перспективніший в плані обробки великих
масивів даних, оскільки цей метод має ни-
зку переваг у порівнянні з іншими метода-
ми: відносно невисока складність обчис-
лень, можливість обробки даних частина-
ми та подальше комбінування частин в
єдиний набір даних.
Аналітика даних
89
Оскільки нашою основною задачею є
побудова алгоритму, що зможе працювати
з великими даними, в цій роботі ми зосе-
редилися на визначенні характеристик да-
них, що впливають на час обробки та ре-
сурси, необхідні для успішного завершен-
ня роботи алгоритму.
Опис методу сегментації
гексагонами
У нашій роботі ми вирішуємо задачу
поєднання геопросторових даних за типа-
ми об’єктів з висотною складовою у вели-
ких масштабах. Одним із прикладів засто-
сування є сегментація рослинного покри-
ву. Для реалізації запропонованого методу
сегментації геопросторових растрів було
обрано програмне середовище FME
(Feature Manipulation Engine) [12].
FME — це програмна платформа, роз-
роблена компанією Safe Software, призна-
чена для інтеграції, трансформації та кон-
вертації просторових і непросторових да-
них між різними форматами та структура-
ми. FME підтримує сотні форматів ГІС,
CAD, баз даних, растрових зображень, 3D-
моделей, а також різноманітні хмарні сер-
віси. Особливістю FME є можливість
створення робочих процесів (workflow) без
необхідності програмування, завдяки ви-
користанню трансформерів — спеціалізо-
ваних інструментів для обробки даних.
Трансформер в FME — це окремий
функціональний блок, який виконує певну
операцію над даними у процесі трансфор-
мації. Наприклад, трансформери можуть
змінювати геометрію, фільтрувати об'єкти,
змінювати атрибути, об'єднувати дані,
аналізувати просторові зв'язки тощо. Ко-
жен трансформер має свою спеціалізацію
та набір параметрів для налаштування.
Кастомний трансформер (Custom
Transformer) — це користувацький набір з
одного або кількох трансформерів, згрупо-
ваних в єдиний логічний блок. Він дозво-
ляє створювати повторно використовувані
компоненти з власними вхідними та вихі-
дними портами, які можуть бути інтегро-
вані в інші робочі процеси FME. Кастомні
трансформери часто використовуються
для спрощення складних робочих проце-
сів, підвищення читабельності схем або
стандартизації окремих частин трансфор-
мації.
Наш метод сегментації гексагонами
(Рис. 1) передбачає створення послідовної
сітки шестикутників із заданою стороною
SIDE_LENGTH, поєднання цієї сітки з ма-
трицею DHM (Digital Height Model) та век-
торним шаром рослинного покриву. Для
генерації гексагонів було використано кас-
томний трансформер HexagonSampler (Рис.
2), розроблений та опублікований Gauthier
[13]. Він створює сітку шестикутників по
заданій рамці (у нашому випадку в ролі
рамки виступає описуючий прямокутник
вхідного набору рослинності). Створення
сітки шестикутників складається з наступ-
них етапів:
• ExpressionEvaluator та
ExpressionEvaluator_2 обчислюють атрибу-
ти _hoffset та _voffset на базі заданого ко-
ристувачем параметра довжини сторони
шестикутника — SIDE_LENGTH:
ℎ𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 = 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆_𝐿𝐿𝑆𝑆𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿 ∗ 3
𝑣𝑣𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 = cos(30°)𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆_𝐿𝐿𝑆𝑆𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿 ∗ 2
• 2DgridAccumulator генерує сітку
точок з інтервалом _hoffset та _voffset;
• Offsetter, підключений паралельною
гілкою, створює копію сітки точок і змі-
щує її відносно першої сітки на _ℎ𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜
2 та
_𝑣𝑣𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜
2 ;
• 2DArcReplacer перетворює точки на
кола з радіусом SIDE_LENG;
Аналітика даних
90
Рис. 1. Реалізація сегментації векторного набору рослинності за висотною характеристикою
методом гексагонів у середовищі FME
Рис. 2. Загальний вигляд кастомного модуля HexagonSampler
• ArcStroker генералізує коло до шес-
тикутника за заданим числом інтерпольо-
ваних граней, яке дорівнює 6.
Результатом роботи HexagonSampler є
послідовна нерозривна сітка правильних
шестикутників з фіксованою довжиною
ребра. AttributeKeeper видаляє непотрібні
атрибути, створені HexagonSampler, а
Counter створює унікальний id шестикут-
ників, який надалі буде використаний для
обробки великих масивів даних окремими
частинами. AreaOnAreaOverlayer накладає
полігони на полігони, перетинаючи гео-
метрію та спільні атрибути. У нашій мо-
делі він приймає на вхід два набори полі-
гонів: вхідний вектор рослинності та сітку
шестикутників. Tester відсіює непотрібні
об’єкти, залишаючи лише частини гекса-
гонів, які перетнулися з набором рослин-
ності. Counter_2 створює унікальні id в
атрибуті _veget_id, які будуть використані
для перенесення значень з растра. Модуль
Raster rounding
(RasterExpressionEvaluator_2,
RasterCellValueRounder,
RasterExpressionEvaluator_3) виконує
округлення значень пікселів вхідного рас-
тра до 3. Оскільки у задачі прописування
висот рослинності 3 метри є допустимою
похибкою, ця операція допомагає прибра-
ти зайвий «шум» у значеннях. Clipper на-
різає вхідний растр по сегментованим по-
лігонам векторної рослинності. На цьому
етапі відбувається передача значень
_veget_id до растрів.
RasterStatisticsCalculator обчислює міні-
мальне\максимальне\середнє значення
пікселів кожного фрагменту растра.
Аналітика даних
91
FeatureJoiner відповідає за перенесення
мінімального\максимального\середнього
значення пікселів із растра до сегменто-
ваних полігонів рослинності. Dissolver
об’єднує сегменти рослинності з однако-
вими значеннями висоти, а
AttributeRenamer_5 перейменовує атрибу-
ти перед записом даних у вихідний файл.
Результатом роботи алгоритму
hexagon_segmentation.fmw є векторний
шар рослинності, представлений сегмен-
тами з різною висотою (Рис. 3).
Рис. 3. Фрагмент векторного шару рослинного покриву. До сегментації – ліворуч,
сегментований методом гексагонів з довжиною сторони гексагону 20 метрів
та кроком висоти 3 метри – праворуч
Аналіз складності алгоритму
AreaonAreaOverlayer
Важливо зазначити, що FME є комер-
ційним програмним забезпеченням із за-
критим кодом. Внутрішня реалізація алго-
ритмів, зокрема, методів оптимізації та
індексування, залишається недоступною
для користувача.
Через це обмеження ми не можемо
безпосередньо проаналізувати алгоритміч-
ну складність, переглянувши вихідний код
чи документацію, тому було ухвалено рі-
шення дослідити поведінку алгоритму
експериментальним шляхом. Зокрема, ми
дослідили вплив характеристик вхідних
даних (кількість полігонів, їхня форма та
кількість вершин) на час виконання алго-
ритму та використання оперативної
пам’яті.
Були створені контрольовані тестові
набори даних із чітко визначеними харак-
теристиками — кількістю полігонів, кіль-
кістю перетинів та складністю геометрії
(кількістю вершин). Це дозволило нам ем-
пірично оцінити залежність часу обробки
та витрат ресурсів від параметрів вхідних
даних.
У дослідженні ми також детально про-
аналізували роботу трансформера
AreaOnAreaOverlayer, який відіграє клю-
чову роль у процесі сегментації.
AreaOnAreaOverlayer виконує просторовий
аналіз та створює нові об’єкти на перети-
нах вхідних полігонів. Немає інформації,
які саме методи оптимізації використову-
ються у FME, але припускаємо, що там
може бути застосоване просторове індек-
сування, наприклад, R-дерева. Аналіз часу
виконання алгоритму AreaOnAreaOverlayer
дозволяє наблизитись до розуміння його
ефективності та окреслити межі продукти-
вності методу гексагонів для сегментації
великих масивів геопросторових даних.
Особлива увага приділялася аналізу
часу виконання, враховуючи потенційне
просторове індексування та геометричні
операції. Для цього було створено тестові
набори полігональних даних з різними
Аналітика даних
92
характеристиками та зроблено вимірюван-
ня продуктивності алгоритму на наборах
даних розміром від 20 000 до 10 000 000
полігонів. Тестові набори даних генерува-
лись із відомими кількостями полігонів,
перетинами полігонів, вершинами поліго-
нів. Було експериментально виміряно час
роботи алгоритму AreaOnAreaOverlayer та
кількість ресурсів (оперативної пам’яті),
необхідних для обробки конкретного дата-
сету.
Для перевірки гіпотези, що загальна
кількість вершин полігонів має вплив на
час роботи алгоритму, ми створили 2 типи
наборів тестових даних: ‘round’ і ‘squere’.
Перший тип (round) – це сферичні поліго-
ни, які утворені з кола з кутом інтерполяції
вершин 22,5гр. та зміщенням по осях X та
Y (Рис. 4а). Другий тип (squere) – це полі-
гони у формі квадратів, які зміщені один
від одного на 1\4 довжини сторони квадра-
та по осях X та Y (Рис. 4б).
Рис. 4. Тестові набори для оцінки складності алгоритму AreaOnAreaOverlayer:
а) round_data, б) squere_data, в) v2_squere_data, г) v3_squere_data
Заміри часу та ресурсів проведені на
12 наборах кожного типу даних з загаль-
ною кількістю полігонів від 20 000 до
10 000 000. Результати замірів наведені у
Таблицях 1, 2, 3, 4:
Таблиця 1
Результати замірів часу роботи та обсягу оперативної пам’яті на тестових даних (round_data)
Features_Count Memory_KB time_fin
20 000 252 872 2.8
100 000 911 008 13.1
1 000 000 8 323 876 151.6
2 000 000 17 502 468 316.2
3 000 000 26 613 348 541.2
4 000 000 30 941 884 804.8
5 000 000 41 899 008 1 131.4
6 000 000 46 550 676 1 547.4
7 000 000 61 031 896 2 090.4
8 000 000 65 557 424 2 691.9
9 000 000 70 041 100 3 256.1
10 000 000 74 203 936 4 191.9
Аналітика даних
93
Таблиця 2
Результати замірів часу роботи та обсягу оперативної пам’яті на тестових даних (squere_data)
Features_Count Memory_KB time_fin
20 000 334 408 3.6
100 000 1 277 492 16.5
1 000 000 12 935 884 205.8
2 000 000 22 070 072 500.4
3 000 000 32 607 576 861.8
4 000 000 47 216 188 1 373.4
5 000 000 51 416 280 2 011.2
6 000 000 71 398 116 2 861.8
7 000 000 74 950 820 3 747.1
8 000 000 104 255 576 6 227.3
9 000 000 104 426 492 9 888.2
10 000 000 104 196 532 10 370.2
Таблиця 3
Результати замірів часу роботи та обсягу оперативної пам’яті на тестових даних
(v2_squere_data)
Features_Count Memory_KB time_fin
20 000 272 340 3.1
100 000 967 692 15.6
1 000 000 9 790 160 190.6
2 000 000 21 019 932 398.3
3 000 000 31 670 228 677.2
4 000 000 35 156 372 1 008.9
5 000 000 48 899 756 1 523.6
6 000 000 53 473 136 2 065
7 000 000 72 671 100 2 782.3
8 000 000 76 267 516 3 762.8
9 000 000 79 681 916 5 350.1
10 000 000 82 591 852 6 639.2
Таблиця 4
Результати замірів часу роботи та обсягу оперативної пам’яті на тестових даних
(v3_squere_data)
Features_Count Memory_KB time_fin
20 000 269 380 2.2
100 000 964 524 13.1
1 000 000 7 535 360 166.5
2 000 000 16 001 076 376.4
Аналітика даних
94
3 000 000 23 667 180 644.8
4 000 000 34 240 536 838
5 000 000 37 579 208 1 057.7
6 000 000 51 428 532 1 565.8
7 000 000 54 452 632 2 199.7
8 000 000 58 342 284 2 874.3
9 000 000 77 111 808 3 633.3
10 000 000 80 141 216 3 421.1
Після отримання результатів було ви-
явлено, що перший тип даних (квадрати)
обробляється суттєво довше, та потребує
більше оперативної пам’яті ніж другий
тип, хоча має меншу загальну кількість
вершин. Ми висунули припущення, що
причиною такої роботи алгоритму була
кількість взаємних перетинів полігонів.
Якщо вважати a,b,c,d…рядами поліго-
нів у тестовому наборі, а 1,2,3,4,5… їхнім
порядковим номером у напрямку зміщен-
ня, то, наприклад, у першому наборі полі-
гонів round_data (Рис. 4а), об’єкт b5 має
перетин лише з двома сусідніми об’єктами
свого ряду b4 та b6. А полігон b5 з набору
squere_data (Рис. 4б), має шість перетинів:
b3,b4,b6,b7,a5,c5.
Для підтвердження гіпотези, що кіль-
кість перетинів суттєво впливає на час ро-
боти та необхідну кількість ресурсів, ми
ухвалили рішення створити ще 2 типи на-
борів: squere_v2 та squere_v3. У squere_v2
кількість взаємних перетинів була змен-
шена з 6 до 4, а у squere_v3 до двох.
У ході експерименту було виявлено,
що кількість пар об’єктів, які перетина-
ються, мають значно більший вплив на час
роботи, ніж кількість вершин у цих
об’єктах. На графіках (Рис. 5) зображено
відношення швидкості обробки даних до
кількості об’єктів та кількості вершин. З
цих графіків можна зробити висновок, що
швидкість роботи алгоритму
AreaOnAreaOverlayer більше залежить від
кількості взаємних перетинів полігонів,
ніж від кількості вершин у цих полігонах.
Також швидкість обробки даних за одини-
цю часу суттєво зменшується зі збільшен-
ням обсягу даних. Тому для подальшої
адаптації архітектури методу сегментації
для обробки великих масивів даних потрі-
бно враховувати ці фактори.
Рис. 5. Графіки відношення швидкості обробки даних до кількості об’єктів
та кількості вершин
Аналітика даних
95
Під час обробки даних FME читає і
оперує даними в оперативній пам’яті (ОП).
Це дозволяє ефективно обробляти дані, але
водночас створює потребу у достатньому
обсязі ОП для обробки наявного масиву
даних. Наскільки впливає обсяг доступної
ОП на час обробки видно на прикладі тес-
тових наборів прямокутників «squere»
(Рис. 6). У разі встановлених 128Гб опера-
тивної пам’яті на ПК, FME процес стає
помітно повільнішим досягнувши 80%
об’єму наявної ОП. Досягнувши ліміту по
ОП, FME починає використовувати диско-
вий кеш (якщо він доступний в операцій-
ній системі). Додаткові процеси оптиміза-
ції використаної пам’яті, зайвий час запи-
су\читання даних із диска пояснюють сут-
тєве збільшення часу роботи алгоритму.
Для оцінки часової складності роботи
алгоритму AreaOnAreaOverlayer ми розра-
хували значення кутового коефіцієнта k за
отриманими графіками (Рис. 6, 7, 8).
Рис. 6. Графіки часу виконання алгоритму AreaOnAreaOverlayer на наборі squere_data
Рис. 7. Графіки часу виконання алгоритму AreaOnAreaOverlayer на наборі round_data
Аналітика даних
96
Рис. 8. Графіки часу виконання алгоритму AreaOnAreaOverlayer на наборі squere_data_v2
Розрахуємо коефіцієнт нахилу K з рів-
няння прямої (1) у логарифмічній системі
координат:
Y′ = 𝐾𝐾𝐾𝐾′ + 𝐵𝐵 (1),
X′ = log10(X),
Y′ = log10(Y).
Візьмемо з графіків дві координати з
1-го та 4-го набору: X1=20 000, X2=2 000
000, а значення Y1 та Y2 визначимо відпо-
відно до часу роботи кожного типу наборів
даних.
Формула для обчислення коефіцієнта
нахилу:
𝐾𝐾 = 𝐾𝐾2 − 𝐾𝐾1
𝑌𝑌2 − 𝑌𝑌1
Розраховані значення для різних набо-
рів даних: round_data: K=1.0264,
square_data: K=1.0715, square_data_v2:
K=1.0544, square_data_v3: K=1.1166.
Середній кутовий коефіцієнт у лога-
рифмічній шкалі за всіма наборами даних
становить 1.06. Це означає, що алгоритм
має майже лінійну складність.
Висновки
У цьому дослідженні було проведено
аналіз алгоритму AreaOnAreaOverlayer у
середовищі FME з метою оцінки часу ви-
конання та впливу різних характеристик
вхідних векторних полігонів на час оброб-
ки та використання ресурсів. Отримані
результати вказують на те, що найбільший
вплив на швидкість виконання алгоритму
має кількість взаємних перетинів поліго-
нів, а не їхня загальна складність (кількість
вершин). Це випливає з порівняння отри-
маних даних за наборами round_data та
square_data: набір round_data обробляється
помітно швидше та потребує суттєво мен-
ше оперативної пам’яті внаслідок меншої
кількості взаємних перетинів полігонів у
наборі.
Іншим важливим фактором є об’єм до-
ступної оперативної пам’яті, оскільки FME
обробляє дані в оперативній пам’яті, що
забезпечує швидке виконання алгоритму.
Але досягнувши 80% заповнення доступ-
ної оперативної пам’яті, швидкість оброб-
ки суттєво знижується через використання
дискового кешування.
Отримані результати є ключовими для
подальшої розробки архітектури автомати-
зованого пайп-лайну по сегментації гео-
просторових растрів. Попри майже лінійну
складність алгоритму, немає потреби у
розділенні вхідного набору на частини.
Однак варто враховувати об’єм доступної
оперативної пам’яті, оскільки під час об-
робки великих масивів даних, ресурсів
може не вистачити для успішного резуль-
тату. У подальшій роботі ми плануємо до-
слідити залежність розміру вхідних даних
від обсягу оперативної пам’яті, необхідної
для роботи алгоритму, та розробити мо-
Аналітика даних
97
дуль, який буде відповідати за розподілен-
ня обчислень.
References
1. Ronneberger, O., Fischer, P., & Brox, T.
(2015). U-Net: Convolutional Networks for
Biomedical Image Segmentation.
http://arxiv.org/abs/1505.04597.
2. He, K., Zhang, X., Ren, S., & Sun, J. (2015).
Deep Residual Learning for Image
Recognition. http://arxiv.org/abs/1512.03385
3. S. Liu, et al, The overlooked contribution of
trees outside forests to tree cover and woody
biomass across Europe. Science Advances
9(37), 2023, doi: 10.1126/sciadv.adh4097.
4. Liu S, Brandt M, Nord-Larsen T, Chave J,
Reiner F, Lang N, Tong X, Ciais P, Igel C,
Pascual A, Guerra-Hernandez J, Li S,
Mugabowindekwe M, Saatchi S, Yue Y,
Chen Z, Fensholt R. The overlooked
contribution of trees outside forests to tree
cover and woody biomass across Europe. Sci
Adv. 2023 Sep 15;9(37):eadh4097. doi:
10.1126/sciadv.adh4097. Epub 2023 Sep 15.
PMID: 37713489; PMCID: PMC10881069.
5. P. Hofmann, D. Tiede,Image segmentation
based on hexagonal sampling grids, South‐
Eastern European Journal of Earth
Observation and Geomatics 3, 2014 pp. 173-
177.
6. J.N. Mueller, J.N. Corcoran, A Random Point
Initialization Approach to Image
Segmentation with Variational Level-sets.
2021, http://arxiv.org/abs/2112.12355.
7. R. Douss, I.R Farah, Extraction of individual
trees based on Canopy Height Model to
monitor the state of the forest. Trees, Forests
and People 8, 2022, doi:
10.1016/j.tfp.2022.100257
8. W. Li, Z. Niu, S. Gao, N. Huang, H. Chen,
Correlating the horizontal and vertical
distribution of LiDAR point clouds with
components of biomass in a Picea crassifolia
forest. Forests 5(8), 2014, pp. 1910–1930.
doi: 10.3390/f5081910.
9. E. Lindberg, J. Holmgren, H. Olsson,
Classification of tree species classes in a
hemi-boreal forest from multispectral
airborne laser scanning data using a mini
raster cell method. International Journal of
Applied Earth Observation and
Geoinformation 100, 2021, doi:
10.1016/j.jag.2021.102334.
10. M.K. Jakubowski, W. Li, Q. Guo, M. Kelly,
Delineating individual trees from lidar data:
A comparison of vector- and raster-based
segmentation approaches. Remote Sensing
5(9), 2013, pp. 4163–4186. doi:
10.3390/rs5094163.
11. Tsaryniuk, O., Hlybovets, A., & Oletsky, O.
(2023). Automated Pipelines for Large-Scale
Height-Based Vegetation Segmentation.
12. Safe Software, FME: Feature Manipulation
Engine[cited 04.05.2025]:
https://www.safe.com/fme.
13. FME Hub, HexagonSampler, [cited
04.05.2025]:
https://hub.safe.com/publishers/larry/transfor
mers/hexagonsampler.
Одержано: 06.05.2025
Внутрішня рецензія отримана: 14.05.2025
Зовнішня рецензія отримана: 15.05.2025
Про авторів:
Царинюк Олександр Васильович,
PhD Комп'ютерні науки, аспірант.
https://orcid.org/0000-0003-1394-2040
Глибовець Андрій Миколайович,
доктор технічних наук, професор,
декан.
https://orcid.org/0000-0003-4282-481X
Місце роботи авторів:
Національний університет
«Києво-Могилянська академія»
https://www.ukma.edu.ua/
|
| id | pp_isofts_kiev_ua-article-840 |
| institution | Problems in programming |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-11-04T02:10:27Z |
| publishDate | 2025 |
| publisher | PROBLEMS IN PROGRAMMING |
| record_format | ojs |
| resource_txt_mv | ppisoftskievua/d8/1438617fda90e09667d8c4b276f33bd8.pdf |
| spelling | pp_isofts_kiev_ua-article-8402025-11-03T10:06:23Z Segmentation of geospatial rasters: analysis of the temporal characteristics of the AREAONAREAOVERLAYER algorithm Сегментація геопросторових растрів: аналіз часових характеристик алгоритму AREAONAREAOVERLAYER Tsaryniuk, O.V. Glybovets, A.M. spatial analysis; raster segmentation; geographic information systems; temporal characteristics; algorithm performance UDC 004.62, 004.67 просторовий аналіз; сегментація растрів; геоінформаційні системи; часові характеристики; продуктивність алгоритму УДК 004.62, 004.67 This paper investigates the performance of the AreaOnAreaOverlayer algorithm used for segmenting geospatial rasters based on elevation features within the FME environment. The main focus is on analyzing the algorithm’s temporal characteristics when processing large volumes of data, particularly in vegetation cover classification tasks. The study describes the experimental setup, typical input data, and the impact of polygon geometric parameters on execution time. The results provide insight into the algorithm’s application limits and reveal dependencies between the structure of input data and computational complexity.Prombles in programming 2025; 2: 87-97 У статті досліджується продуктивність алгоритму AreaOnAreaOverlayer, що використовується для сег ментації геопросторових растрів за ознаками висоти в середовищі FME. Основну увагу приділено ана лізу часових характеристик алгоритму під час обробки великих обсягів даних, зокрема, в задачах кла сифікації рослинного покриву. Описано експериментальне середовище, типові вхідні дані та вплив ге ометричних параметрів полігонів на час виконання операції. Отримані результати дають змогу оцінити межі застосування алгоритму та виявити залежності між структурою вхідних даних і обчислювальною складністю.Prombles in programming 2025; 2: 87-97 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-09-07 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/840 10.15407/pp2025.02.087 PROBLEMS IN PROGRAMMING; No 2 (2025); 87-97 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2 (2025); 87-97 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2 (2025); 87-97 1727-4907 10.15407/pp2025.02 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/840/891 Copyright (c) 2025 PROBLEMS IN PROGRAMMING |
| spellingShingle | spatial analysis raster segmentation geographic information systems temporal characteristics algorithm performance UDC 004.62 004.67 Tsaryniuk, O.V. Glybovets, A.M. Segmentation of geospatial rasters: analysis of the temporal characteristics of the AREAONAREAOVERLAYER algorithm |
| title | Segmentation of geospatial rasters: analysis of the temporal characteristics of the AREAONAREAOVERLAYER algorithm |
| title_alt | Сегментація геопросторових растрів: аналіз часових характеристик алгоритму AREAONAREAOVERLAYER |
| title_full | Segmentation of geospatial rasters: analysis of the temporal characteristics of the AREAONAREAOVERLAYER algorithm |
| title_fullStr | Segmentation of geospatial rasters: analysis of the temporal characteristics of the AREAONAREAOVERLAYER algorithm |
| title_full_unstemmed | Segmentation of geospatial rasters: analysis of the temporal characteristics of the AREAONAREAOVERLAYER algorithm |
| title_short | Segmentation of geospatial rasters: analysis of the temporal characteristics of the AREAONAREAOVERLAYER algorithm |
| title_sort | segmentation of geospatial rasters: analysis of the temporal characteristics of the areaonareaoverlayer algorithm |
| topic | spatial analysis raster segmentation geographic information systems temporal characteristics algorithm performance UDC 004.62 004.67 |
| topic_facet | spatial analysis raster segmentation geographic information systems temporal characteristics algorithm performance UDC 004.62 004.67 просторовий аналіз сегментація растрів геоінформаційні системи часові характеристики продуктивність алгоритму УДК 004.62 004.67 |
| url | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/840 |
| work_keys_str_mv | AT tsaryniukov segmentationofgeospatialrastersanalysisofthetemporalcharacteristicsoftheareaonareaoverlayeralgorithm AT glybovetsam segmentationofgeospatialrastersanalysisofthetemporalcharacteristicsoftheareaonareaoverlayeralgorithm AT tsaryniukov segmentacíâgeoprostorovihrastrívanalízčasovihharakteristikalgoritmuareaonareaoverlayer AT glybovetsam segmentacíâgeoprostorovihrastrívanalízčasovihharakteristikalgoritmuareaonareaoverlayer |