Kategória: Všeobecné

Zber dát

LiDAR je inovatívna metóda diaľkového merania vzdialenosti, ktorá funguje na princípe výpočtu doby šírenia impulzu laserového lúča odrazeného od objektov. LiDAR vysiela svetelné impulzy, ktoré zasiahnu zem, alebo daný objekt, a vrátia sa späť, kde sú zachytené senzormi. Meraním času návratu svetla LiDAR určí vzdialenosť bodu, v ktorom sa laserový lúč odrazil. 

LiDAR dokáže vysielať 100- až 300 000 impulzov za sekundu, pričom z každého metra štvorcového povrchu zachytí niekoľko desiatok až stoviek impulzov, v závislosti od konkrétneho nastavenia a vzdialenosti snímaného objektu. Týmto spôsobom sa vytvára tzv. mračno bodov (PointCloud) pozostávajúce, potenciálne, z miliónov bodov. Moderným využitím LiDAR-u je zber dát zo vzduchu, kde sa zariadenie umiestňuje na drony, čím sa zvyšuje efektivita a presnosť zberu dát. Na zber dát v tomto projekte boli použité drony od spoločnosti DJI, hlavne dron DJI M300 a Mavic 3 Enterprise (obr. 1). Dron DJI M300 je profesionálny dron navrhnutý pre rôzne priemyselné aplikácie a jeho parametre umožňujú, aby bol vhodným nosičom pre LiDAR.

Dron DJI M300 bol využitý ako nosič pre LiDAR značky Geosun (obr. 1). Ide o strednorozsahový, kompaktný systém s integrovaným laserovým skenerom a systémom na určovanie polohy a natočenia. Vzhľadom na pomer medzi rýchlosťou zberu a kvalitou dát boli dáta snímané z výšky 100 m nad povrchom, čím je možné zosnímať za pomerne krátky čas aj väčšie územia v postačujúcej kvalite.

Zozbierané dáta boli geolokalizované v súradnicovom systéme S-JTSK (EPSG:5514) a Baltskom výškovom systéme po vyrovnaní (Bpv), pričom súradnice sú udávané v metroch alebo metroch nad morom. Okrem lidarových dát bola súčasne vykonaná aj letecká fotogrametria, ktorá umožňuje tvorbu tzv. ortofotomozaiky. Ortofotomozaiky poskytujú fotografický záznam skúmanej oblasti vo vysokom rozlíšení (3 cm/pixel) a s polohovou presnosťou do 5 cm. Ortofotomozaika bola použitá ako podklad pre vizuálne overenie polôh jednotlivých stromov.

Klasifikácia dát

Nosným datasetom, ktorý vstupoval do automatickej identifikácie stromov, bolo lidarové mračno bodov vo formáte LAS/LAZ (nekomprimovaná a komprimovaná forma). LAS súbory sú štandardizovaným formátom pre ukladanie lidarových dát navrhnutý tak, aby zabezpečil efektívne ukladanie veľkého množstva bodových dát s presnými 3D súradnicami. LAS súbory obsahujú informácie o polohe (x, y, z), intenzite odrazu, klasifikácii bodov a ďalšie atribúty, ktoré sú nevyhnutné pre analýzu a spracovanie lidarových dát. Vďaka svojej štandardizácii a kompaktnosti sa LAS súbory často používajú v geodézii, kartografii, lesníctve, urbanistickom plánovaní a mnohých ďalších oblastiach, kde je potrebná detailná a presná 3D reprezentácia terénu a objektov.

Mračno bodov bolo potrebné najskôr spracovať do takej podoby, aby na ňom bolo možné čo najjednoduchšie identifikovať body jednotlivých stromov alebo vegetácie. Ide o proces, pri ktorom sa každému bodu v mračne bodov priradí určitá trieda, čiže hovoríme o klasifikácii.

Na klasifikáciu mračna bodov je možné použiť viacero nástrojov. V našom prípade sme sa, vzhľadom na dobré skúsenosti, rozhodli použiť softvér Lidar360 od spoločnosti GreenValley International [1]. V rámci klasifikácie mračna bodov boli jednotlivé body mračna klasifikované do nasledovných tried: neklasifikované (1), povrch (2), stredná vegetácia (4), vysoká vegetácia (5), budovy (6). Na klasifikáciu bola využitá metóda strojového učenia, ktorá po natrénovaní na reprezentatívnej trénovacej vzorke dokáže automaticky klasifikovať body ľubovoľného vstupného datasetu (obr. 2).

Trénovacia vzorka je vytvorená manuálnym klasifikovaním bodov mračna do jednotlivých tried. Na účely automatizovanej identifikácie stromov sú pre tento projekt podstatné hlavne triedy povrch a vysoká vegetácia. Avšak, pre čo najlepší výsledok klasifikácie vysokej vegetácie je vhodné zaradiť aj ostatné klasifikačné triedy. Trénovacia vzorka bola tvorená súborom viacerých menších oblastí z celého územia a zahŕňala všetky typy vegetácie, či už listnaté alebo ihličnaté, a taktiež rôzne typy budov. Na základe vytvorenej trénovacej vzorky boli následne automaticky klasifikované zvyšné body mračna. Kvalita trénovacej množiny má preto podstatný vplyv na výslednú klasifikáciu celého územia.

Segmentácia dát

Klasifikované mračno bodov bolo následne segmentované pomocou softvéru CloudCompare [2]. Segmentácia vo všeobecnosti znamená rozdelenie klasifikovaných dát na menšie celky – segmenty, ktoré spĺňajú spoločné charakteristické vlastnosti. Pri segmentácii vysokej vegetácie bolo cieľom priradiť jednotlivé body ku konkrétnemu stromu.

Na účely segmentácie stromov bol použitý plugin TreeIso v softvérovom balíku CloudCompare, ktorý automaticky rozpoznáva stromy na základe rôznych výškových a polohových kritérií (obr. 3). Celková segmentácia sa skladá z troch krokov:

1. Spájanie bodov, ktoré sú blízko seba, do segmentov a odstraňovanie šumu.
2. Spájanie susedných segmentov bodov do väčších celkov.
3. Zloženie jednotlivých segmentov do celku, ktorý tvorí jeden strom.

Výsledkom je kompletná segmentácia vysokej vegetácie. Tieto segmenty sa následne uložia do jednotlivých LAS súborov a použijú sa na následné spracovanie pre určenie polohy jednotlivých stromov. Veľkým nedostatkom tohto nástroja je, že pracuje len v sériovom režime, čiže dokáže využiť len jedno CPU jadro, čo značne limituje jeho použitie v HPC prostredí.

Ako alternatívnu metódu na segmentovanie sme skúmali aj využitie ortofotomozaiky daných oblastí. Pomocou metód strojového učenia sme sa pokúsili identifikovať jednotlivé koruny stromov na snímkach a na základe takto určených geolokalizačných súradníc identifikovať príslušné segmenty v LAS súbore. Na detekciu korún stromov z ortofotomozaiky bol použitý model YOLOv5 [3] s predtrénovanými váhami z databázy COCO128 [4]. Tréningové dáta pozostávali z 230 snímok, ktoré boli manuálne anotované pomocou nástroja LabelImg [5]. Trénovacia jednotka pozostávala z 300 epoch, snímky boli rozdelené do sád po 16 vzoriek a ich veľkosť bola nastavená na 1000×1000 pixelov, čo sa ukázalo ako vhodný kompromis medzi výpočtovou náročnosťou a počtom stromov na daný výsek. Nedostatočná kvalita tohto prístupu bola obzvlášť markantná pre oblasti s hustou vegetáciou (zalesnených oblastí), ako je znázornené na obrázku 4. Domnievame sa, že to bolo spôsobené nedostatočnou robustnosťou zvolenej trénovacej sady, ktorá nedokázala dostatočne pokryť rôznorodosť obrazových dát (obzvlášť pre rôzne vegetatívne obdobia). Z týchto dôvodov sme segmentáciu z fotografický dát ďalej nerozvíjali a sústredili sme sa už iba na segmentáciu v mračne bodov.

Aby sme naplno využili možnosti superpočítača Devana, nasadili sme v jeho prostredí knižnicu lidR [6]. Táto knižnica, napísaná v jazyku R, je špecializovaný nástroj určený na spracovanie a analýzu lidarových dát, poskytuje rozsiahly súbor funkcií a nástrojov pre čítanie, manipuláciu, vizualizáciu a analýzu LAS súborov. S knižnicou lidR je možné efektívne vykonávať úlohy ako filtrovanie, klasifikácia, segmentácia a extrakcia objektov priamo z mračien bodov. Knižnica tiež umožňuje interpoláciu povrchov, vytváranie digitálnych modelov terénu (DTM) a digitálnych modelov povrchu (DSM) a výpočet rôznych metrických parametrov vegetácie a štruktúry krajiny. Vďaka svojej flexibilite a výkonnosti je lidR populárnym nástrojom v oblasti geoinformatiky a je zároveň vhodným nástrojom pre prácu v HPC prostredí, keďže väčšina funkcií a algoritmov je plne paralelizovaná v rámci jedného výpočtového uzla, čo umožňuje naplno využívať dostupný hardvér. V prípade spracovania veľkých datasetov, keď výkon alebo kapacita jedného výpočtového uzla už nie je postačujúca, môže byť rozdelenie datasetu na menšie časti, a ich nezávislé spracovanie, cesta k využitiu viacerých výpočtových HPC uzlov súčasne.

V knižnici lidR je dostupná funkcia locate_trees(), ktorá dokáže pomerne spoľahlivo identifikovať polohu stromov. Na základe zvolených parametrov a algoritmu funkcia analyzuje mračno bodov a identifikuje polohu stromov. V našom prípade bol použitý algoritmus lmf pre lokalizáciu založenú na maximálnej výške [7]. Algoritmus je plne paralelizovaný, takže dokáže efektívne spracovať relatívne veľké zvolené oblasti v krátkom čase.

Takto určené polohy stromov sa dajú následne použiť v algoritme silva2016 na segmentáciu vo funkcii segment_trees() [8]. Táto funkcia segmentuje príslušné nájdené stromy do osobitných LAS súborov (obr. 5), podobne ako plugin modul TreeIso v programe CloudCompare. Následne sa takto segmentované stromy v LAS súboroch použijú na ďalšie spracovanie, konkrétne na určenie polohy jednotlivých stromov, napríklad pomocou klastrovacieho algoritmu DBSCAN [9].

Detekcia kmeňov stromov pomocou klastrovacieho algoritmu DBSCAN

Na určenie polohy a výšky stromov v jednotlivých LAS súboroch získaných segmentáciou sme použili rôzne prístupy. Výška jednotlivých stromov bola získaná na základe z-ových súradníc pre jednotlivé LAS súbory ako rozdiel minimálnej a maximálnej súradnice mračien bodov. Keďže jednotlivé výseky z mračna bodov obsahovali v niektorých prípadoch aj viac ako jeden strom, bolo potrebné identifikovať počet kmeňov stromov v rámci týchto výsekov.

Kmene stromov boli identifikované na základe klastrovacieho algoritmu DBSCAN, pracujúceho s nasledovnými nastaveniami: maximálna vzdialenosť dvoch bodov v rámci jedného klastra (= 1 meter) a minimálny počet bodov v jednom klastri (= 10). Poloha každého identifikovaného kmeňa bola následne získaná na základe x-ových a y-ových súradníc geometrických stredov (centroidov) klastrov. Identifikácia klastrov pomocou DBSCAN algoritmu je ilustrovaná na obrázku 6.

Zistenie výšky stromov pomocou interpolácie povrchov

Ako alternatívnu metódu na určenie výšok stromov sme použili tzv. Canopy Height Model (CHM). CHM je digitálny model, ktorý predstavuje výšku stromovej obálky nad terénom. Tento model sa používa na výpočet výšky stromov v lese alebo inom vegetačnom poraste. CHM sa vytvára odčítaním digitálneho modelu terénu (DTM) od digitálneho modelu povrchu (DSM). Výsledkom je mračno bodov alebo raster, ktorý zobrazuje výšku stromov nad povrchom terénu (obr. 7).

Ak teda poznáme súradnice polohy stromu, pomocou tohto modelu môžeme jednoducho zistiť príslušnú výšku objektu (stromu) v danom bode. Výpočet tohto modelu je možné jednoducho uskutočniť použitím knižnice lidR pomocou funkcií grid_terrain(), ktorá vytvára DTM, a grid_canopy(), ktorá počíta DSM.

Porovnanie výsledkov

Pre porovnanie dosiahnutých výsledkov vyššie popísanými prístupmi sme sa zameriavali na oblasť Petržalky v Bratislave, kde už boli vykonané manuálne merania polôh a výšok stromov. Z celej oblasti (približne 3500×3500 m) sme vybrali reprezentatívnu menšiu oblasť o rozmeroch 300×300 m (obr. 2). Získali sme tak výsledky pre plugin modul TreeIso v programe CloudCompare (CC), pričom sme pracovali na PC v prostredí Windows, a výsledky pre algoritmy vo funkciách locate_trees() a segment_trees() pomocou knižnice lidR  v HPC prostredí superpočítača Devana. Polohy stromov sme následne kvalitatívne a kvantitatívne vyhodnotili pomocou algoritmu Munkres (Hungarian Algorithm) [10] na optimálne párovanie. Algoritmus Munkres, tiež známy ako Maďarský algoritmus, je efektívny algoritmus na nájdenie optimálneho párovania v bipartitných grafoch. Jeho použitie pri párovaní stromov s manuálne určenými polohami stromov znamená nájdenie najlepšej zhody medzi identifikovanými stromami z lidarových dát a ich známymi polohami. Následne pri určení vhodnej hranice vzdialenosti v metroch (napríklad 5 m) potom vieme kvalitatívne zistiť počet presne určených polôh stromov. Výsledky sú spracované pomocou histogramov a percentuálne určujú správne polohy stromov v závislosti od zvolenej hranice presnosti (obr. 8). Zistili sme, že obe metódy dosahujú pri hranici vzdialenosti 5 metrov takmer rovnaký výsledok, približne 70% správne určených polôh stromov. Metóda použitá v programe CloudCompare vykazuje lepšie výsledky, resp. vyššie percento pri nižších prahových hodnotách, čo odzrkadľujú aj príslušné histogramy (obr. 8). Pri porovnaní oboch metód navzájom dosahujeme až približne 85% zhody pri prahovej hodnote do 5 metrov, čo poukazuje na kvalitatívnu vyrovnanosť oboch použitých prístupov. Kvalitu dosiahnutých výsledkov ovplyvňuje hlavne presnosť klasifikácie vegetácie v bodových mračnách, pretože prítomnosť rôznych artefaktov, ktoré sú nesprávne klasifikované ako vegetácia, skresľuje finálne výsledky. Algoritmy na segmentáciu stromov nedokážu vplyv týchto artefaktov eliminovať.

Analýza paralelnej efektivity algoritmu locate_trees() v knižnici lidR

Na zistenie efektivity paralelizácie hľadania vrcholov stromov v knižnici lidR, pomocou funkcie locate_trees(), sme daný algoritmus aplikovali na rovnaké študované územie s rôznym počtom CPU jadier – 1, 2, 4 až po 64 (maximum HPC uzla). Aby sme zistili, či je daný algoritmus citlivý aj na veľkosť problému, otestovali sme ho na troch územiach s rôznou veľkosťou – 300×300, 1000×1000 a 3500×3500 metrov. Dosiahnuté časy sú zobrazené v Tabuľke 1 a škálovateľnosť algoritmu je znázornená na obrázku 9. Výsledky ukazujú, že škálovateľnosť algoritmu nie je ideálna. Pri použití približne 20 jadier CPU klesá efektivita algoritmu na približne 50%, pri použití 64 jadier CPU je efektivita algoritmu už len na úrovni 15-20%. Efektivitu algoritmu ovplyvňuje aj veľkosť problému – čím väčšie územie, tým menšia efektivita, aj keď tento efekt nie je až tak výrazný. Na záver môžeme konštatovať, že na efektívne využitie daného algoritmu je vhodné použiť 16-32 CPU jadier a vhodným rozdelením daného skúmaného územia na menšie časti dosiahnuť maximálne efektívne využitie dostupného hardvéru. Použitie viac ako 32 CPU jadier síce už nie je efektívne, ale umožňuje ďalšie urýchlenie výpočtu.

Záverečné zhodnotenie

Zistili sme, že pre dosiahnutie dobrých výsledkov je extrémne dôležité správne nastavenie parametrov použitých algoritmov, keďže počet a kvalita výsledných polôh stromov sú od nich veľmi závislé. Na získanie čo najpresnejších výsledkov je vhodné vybrať reprezentatívnu časť skúmanej oblasti, manuálne zistiť polohy stromov a následne nastaviť parametre príslušných algoritmov. Takto optimalizované nastavenia môžu následne byť použité na analýzu celej skúmané oblasti.

Kvalitu výsledkov ovplyvňuje taktiež množstvo iných faktorov, ako napríklad ročné obdobie, ktoré má vplyv na hustotu vegetácie, alebo hustota stromov v danej oblasti a druhová variabilita vegetácie. Kvalitu výsledkov ovplyvňuje aj kvalita klasifikácie vegetácie v mračne bodov, pretože prítomnosť rôznych artefaktov, ako sú časti budov, cesty, dopravné prostriedky a iné objekty, môže následne negatívne skresliť výsledky, keďže použité algoritmy na segmentáciu stromov nedokážu tieto artefakty vždy spoľahlivo odfiltrovať.

Z hľadiska efektivity výpočtov môžeme konštatovať, že použitie HPC prostredia poskytuje zaujímavú možnosť násobného urýchlenia vyhodnocovacieho procesu. Na ilustráciu môžeme uviesť, že spracovanie, napríklad, celej skúmanej oblasti Petržalky (3500×3500 m) trvalo na jednom výpočtovom uzle HPC systému Devana približne 820 sekúnd, pri využití všetkých (t.j. 64) CPU jadier. Spracovanie danej oblasti v programe CloudCompare na výkonnom PC,  pri použití jedného CPU jadra, trvalo približne 6200 sekúnd, čo je asi 8-krát pomalšie.

Plná verzia článku SK

Autori
Marián Gall – Národné superpočítačové centrum
Michal Malček – Národné superpočítačové centrum
Dávid Murín – SKYMOVE s. r. o.
Robert Straka – SKYMOVE s. r. o.

Zdroje:

[1] https://www.greenvalleyintl.com/LiDAR360/

[2] https://github.com/CloudCompare/CloudCompare/releases/tag/v2.13.1

[3] https://github.com/ultralytics/yolov5

[4] https://www.kaggle.com/ultralytics/coco128

[5] https://github.com/heartexlabs/labelImg

[6] Roussel J., Auty D. (2024). Airborne LiDAR Data Manipulation and Visualization for Forestry Applications.

[7] Popescu, Sorin & Wynne, Randolph. (2004). Seeing the Trees in the Forest: Using Lidar and Multispectral Data Fusion with Local Filtering and Variable Window Size for Estimating Tree Height. Photogrammetric Engineering and Remote Sensing. 70. 589-604. 10.14358/PERS.70.5.589.

[8] Silva C. A., Hudak A. T., Vierling L. A., Loudermilk E. L., Brien J. J., Hiers J. K., Khosravipour A. (2016). Imputation of Individual Longleaf Pine (Pinus palustris Mill.) Tree Attributes from Field and LiDAR Data. Canadian Journal of Remote Sensing, 42(5). 

[9] Ester M., Kriegel H. P., Sander J., Xu X.. KDD-96 Proceedings (1996) pp. 226–231

[10] Kuhn H. W., “The Hungarian Method for the assignment problem”, Naval Research Logistics Quarterly, 2: 83–97, 1955

V súčasnosti, väčšina najmodernejších segmentačných modelov hlbokého učenia poskytuje výstup iba v rastrovej forme. Avšak GIS často potrebujú dáta vo vektorovej forme. Jednou z metód, ktorá dokáže generovať dáta vo vektorovej forme, je Frame Field learning. Táto metóda generuje okrem segmentačnej masky aj frame field pole, ktoré obsahuje štrukturálne informácie o objektoch, ktoré sa následne využívajú v procese vektorizácie.

Modely Frame Field learningu sú trénované metódou “s učiteľom” (z angl. “supervised learning”), ktorá potrebuje veľké množstvo anotovaných dát. Na získanie takéhoto množstva kvalitných dát je potrebná manuálna ľudská práca, ktorá však môže byť zdĺhavá a nákladná. Jednou z metód, ktorá môže znížiť závislosť od anotovaných dát, je “učenie s čiastočným učiteľom”, resp. “čiastočne riadené učenie“ (z angl. “semi-supervised learning”). Tento prístup učenia využíva nielen anotované dáta, ale aj množinu neanotovaných dát.

Cieľom tejto spolupráce medzi Národným kompetenčným centrom pre HPC a Geodeticca Vision s.r.o. bolo identifikovať, implementovať a vyhodnotiť vhodnú metódu učenia s čiastočným učiteľom pre Frame Field learning.

Metódy

Frame Field learning

Hlavnou myšlienkou Frame Field learning [1] metódy je pomôcť vektorizačnému algoritmu vyriešiť nejednoznačné prípady pri vektorizácii, ktoré sú spôsobené diskrétnou pravdepodobnostnou segmentačnou mapou (výstup zo segmentačného modelu), a to pridaním tzv. frame fields poľa (viď. Obrázok 1) ako ďalšieho výstupu z neurónovej siete, reprezentujúceho geometrické charakteristiky budov.

Frame field pole

Frame field je vektorové pole rádu 4, čo znamená, že každému bodu v rovine priradí 4 smerové vektory. Protiľahlé vektory majú rovnakú hodnotu, ale s opačným znamienkom, takže každému bodu v rovine je priradený vektor {u, −u, v, −v}. Tieto vektory postačujú na definovanie tvaru budov, ktoré sú z veľkej časti pravidelného tvaru s pravouhlými rohmi.

Frame Field learning

Proces metódy Frame Field learning môžeme zosumarizovať nasledovne:

1. Vstupom do neurónovej siete je RGB obraz o veľkosti 3 x V x Š.
2. Na generovanie mapy príznakov (z angl. “feature map”) je možné využiť rôzne segmentačné architektúry, napr. U-Net.
3. Učenie je supervizované (patrí medzi metódy učenia s učiteľom), pričom pre učenie segmentačných masiek sa využívajú označené rastrované polygóny pre interiér a hranice budov. Ako stratová funkcia sa využíva lineárna kombinácia funkcií cross-entropy a Dice loss.
4. Pre učenie samotného Frame Field poľa sa využívajú vektory polygónov označených budov, kde konzistentnosť a presnosť Frame Field poľa zabezpečujú tri stratové funkcie:
   1. L_align stratová funkcia riadi správne natočenie Frame Field poľa na smery dotyčnice vektoru polygónu.
   1. L_align90 stratová funkcia zabraňuje, aby sa Frame Field pole degradovalo na priamkové pole.
   1. L_smooth zabezpečuje hladký priebeh Frame Field poľa.
5. Pre zachovanie konzistentnosti medzi segmentačnou pravdepodobnostnou mapu a Frame Field výstupom sú definované regularizačné stratové funkcie, ktoré zarovnávajú Frame Field pole s gradientmi segmentačnej mapy.

Vektorizácia

Proces vektorizácie transformuje výstup z natrénovanej neurónovej siete do topologicky čistých vektorov pomocou algoritmu Active Skeleton Model (ASM). Princíp algoritmu spočíva v iteratívnom posúvaní vrcholov skeletového grafu do ich ideálnej pozície. Skeletový graf je vygenerovaný pomocou morfologickej operácie “thinning” z gradientu segmentačnej mapy. Iteratívny posun je riadený gradientovou optimalizačnou metódou, ktorej cieľom je minimalizovať energetickú funkciu, ktorá má nasledujúce zložky:

1. E_{probability –} riadi prispôsobenie skeletového grafu kontúram pravdepodobnostnej mapy budovy na konkrétnu hodnotu pravdepodobnosti (napr. 0.5)
2. E_{frame field align} – riadi zarovnanie každej hrany skeletového grafu na Frame Field pole.
3. E_length – zaisťuje homogénnu distribúciu vrcholov skeletového grafu.

UniMatch metóda čiastočne riadeného učenia

UniMatch [2], pokročilá metóda učenia s čiastočným učiteľom z kategórie regulátorov konzistentnosti, stavia na základných princípoch vytvorených metódou FixMatch [3], ktorá je základnou metódou v tejto kategórií algoritmov. Funguje na princípe pseudo-označovania (z angl. “pseudo-labeling“) v kombinácií s reguláciou konzistentnosti.

Základný princíp metódy FixMatch spočíva v generovaní pseudo-označení (anotácií) pre neanotované dáta, pomocou predikcií neurónovej siete. To znamená, že pre slabo perturbovaný neanotovaný vstup x^w sa vygeneruje predikcia p^w, ktorá slúži ako pseudo-označenie pre predikciu silne perturbovaného vstupu x^s. Následne sa vypočíta hodnota chybovej funkcie, napr. cross-entropy(p^w,  p^s), pričom do úvahy sa berú iba tie oblasti z p^w, ktoré majú hodnotu pravdepodobnosti väčšiu ako daný prah, napr. >0.95. 

Rozšírenie metódy UniMatch oproti metóde FixMatch spočíva v dvoch princípoch:

1. UniPerb (Unified Perturbations for Images and Features) – aplikácia perturbácie na úrovni príznakov (z angl. “feature perturbation“). V praxi to znamená, že na výstup (teda príznak – feature) z encoder vrstvy neurónovej siete sa aplikuje dropout funkcia, ktorá náhodne vynuluje niektoré príznaky. Takto upravený výstup z encoder vrstvy následne vstupuje do decoder časti siete, ktorá vygeneruje p^fp.
2. DusPerb (Dual-Stream Perturbations) – namiesto jednej silnej perturbácie sa využívajú dve silné perturbácie x^s1 a x^s2.

V konečnom dôsledku máme tri stratové funkcie – cross-entropy(p^w,  p^fp), cross-entropy(p^w,  p^s1), cross-entropy(p^w,  p^s2). Tie sa nakoniec lineárne kombinujú so supervizovanou stratovou funkciou.

Táto metóda v súčasnosti patrí medzi state-of-the-art metódy učenia s čiastočným učiteľom. Hlavnou výhodou tejto metódy je jej jednoduchosť pri implementácií a nevýhodou je jej citlivosť na výber vhodnej slabej a silnej perturbácie.

Integrácia UniMatch metódy do Frame Field učenia

Implementácia UniMatch do Frame Field learning frameworku

Aby sme mohli implementovať UniMatch metódu do Frame Field leagning štruktúry, potrebovali sme najprv definovať slabú a silnú perturbáciu v kontexte leteckých snímok. Ako slabé perturbácie sme zvolili základné priestorové transformácie obrazu, vrátane rotácie, zrkadlenia a vertikálneho/horizontálneho prevrátenia. Všetky tieto transformácie sú oprávnené pre letecké snímky.

V prípade silných perturbácií sme použili fotometrické transformácie. Tie zahŕňajú úpravy odtieňa, farby, či jasu obrazu. Poskytujú výraznejšie zmeny snímok než s použitím priestorových transformácií. 

Dôležitým krokom bola implementácia perturbácie na úrovni príznakov (feature perturbation).   Túto perturbáciu sme implementovali ako dropout mechanizmus vo vrstve medzi encoder a decoder časťami architektúry U-Net. Tento mechanizmus zahodí (nastaví na nulu) náhodne vybrané hodnoty príznakov (výstup z encoder vrstvy). Takto upravené hodnoty výstupu z encoder časti siete vstupujú ďalej do decoder časti U-Net architektúry.

V prípade dual-stream perturbácií sme prispôsobili Frame Field framework tak, aby využíval dve silné perturbácie. Predikcia pre slabú perturbáciu sa použila ako pseudo-označenie pre dve silné perturbácie (preto označenie dual-stream). Dve silné perturbácie prispievajú k celkovej robustnosti a efektívnosti modelu.

Prostredníctvom týchto úprav bola UniMatch metóda úspešne integrovaná do Frame Field learning algoritmu, čím sa zvýšila jeho schopnosť efektívne spracúvať a učiť sa z anotovaných a hlavne neanotovaných dát.

Experimenty
Dáta
Anotované dáta

Anotované dáta použité v štúdii pochádzajú z troch rôznych zdrojov, detaily sú uvedené v Tabuľke 1.

Neanotované dáta

Neanotované dáta (verejne dostupné vysoko kvalitné letecké snímky) pochádzajú z Geodetického a kartografického ústavu (GKÚ) [6]. Pri výbere sme sa zamerali na oblasť s rozlohou 7 000 km², čím bola zaistená diverzita rôznych povrchov krajín a mestských prostredí.

Spracovanie dát: Patching

Anotované aj neanotované snímky boli spracované pomocou metódy “patching”,ktorá obraz rozdeľuje na malé časti veľkosti 320x320px. Táto veľkosť bola špecificky vybraná tak, aby vyhovovala požiadavkám pre vstup zvolenej neurónovej siete. Takýmto spôsobom vzniklo z anotovaných dát približne 55 000 malých častí a z neanotovaných dát okolo 244 000 častí.

Trénovanie
Architektúra modelu

Použitý model sme navrhli s pomocou U-Net architektúry s EfficientNet-B4 základom. Táto kombinácia poskytuje  dobrú rovnováhu presnosti a efektívnosti, čo je veľmi dôležité pri práci s komplexnými segmentačnými úlohami. EfficientNet-B4 ako základ neurónovej siete bol vybraný pre optimálnu rovnováhu medzi spotrebou pamäte a výkonom. V metóde Frame Field learning sa U-Net architektúra ukázala byť vysoko efektívna, o čom svedčia výsledky použitia tejto siete v rôznych štúdiách.

Trénovací proces

Na trénovanie sme použili AdamW optimalizátor, ktorý kombinuje výhody Adam optimalizácie s regularizačnou metódou “weight decay”, čím pomáha modelu lepšie generalizovať. Aby sme sa vyhli pretrénovaniu modelu, použili sme L2 regularizáciu a taktiež bola použitá metóda ReduceLROnPlateau na optimalizáciu parametra rýchlosti učenia. Táto metóda upravuje parameter rýchlosti učenia na základe validačnej straty.

Úpravy potrebné pre implementáciu učenia s čiastočným učiteľom

Kľúčovým aspektom nášho trénovania bolo nastavenia podielu anotovaných a neanotovaných obrázkov. Experimentovali sme s pomermi od 1:1 do 1:5 (počet anotovaných : počet neanotovaných). Takýmto spôsobom sme zisťovali, ako rôzne množstvá neanotovaných dát ovplyvňujú trénovací proces. Identifikovali sme optimálny pomer pre trénovanie nášho modelu tak, aby bolo zachované efektívne učenie s využitím metódy učenia s čiastočným učiteľom.

Vyhodnotenie modelu

Na vyhodnotenie nášho modelu na extrakciu budov sme zvolili metriky, ktoré precízne merajú ako presne sa predikcie zhodujú so skutočnými štruktúrami.

Intersection over Union (IoU)

Kľúčovou metrikou, ktorú sme využívali je metrika s názvom Intersection over Union (IoU). Počíta zhodu medzi predikciami modelu a skutočným tvarom budov. Hodnota skóre IoU blízka 1 znamená, že naše predikcie sú podobné skutočným budovám. Táto metrika je nevyhnutná na posúdenie geometrickej presnosti pre segmentované oblasti, pretože odráža presnosť vytýčenia hraníc budov. Okrem toho, vyhodnotením pomeru správne predikovanej oblasti ku kombinovanej oblasti (zjednotenie oblasti predikcie a skutočnej oblasti), nám IoU poskytuje jasnú mieru efektivity modelu v zachytávaní skutočného kontextu a tvaru budov v komplexnej mestskej krajine.

Precision, Recall (senzitivita) a F1 skóre

Metrika nazývaná precision vyjadruje podiel správne identifikovaných budov zo všetkých identifikovaných budov. Senzitivita (angl. “recall“) ilustruje schopnosť modelu zachytiť všetky skutočné budovy. Vysoká hodnota tejto metriky poukazuje na citlivosť modelu pri detekcii budov. F1 skóre kombinuje precision a senzitivitu do jednej metriky, poskytujúc vyvážený obraz výkonu modelu.

Complexity Aware IoU (cIoU)

Ďalšou použitou metrikou bola Complexity Aware IoU (cIoU) [7]. Táto metrika rieši nedostatky IoU tým, že vyvažuje presnosť segmentácie a komplexnosť tvarov polygónov. Zatiaľ čo IoU môže viesť model k vytváraniu veľmi komplexných polygónov, cIoU zaručuje, že komplexnosť polygónov (počet ich vrcholov) je zachovaná realistická, čím odráža skutočný tvar budov, ktoré sú obvykle málo komplexné.

N Ratio Metrika

Metrika N ratio je doplnkovým komponentom v našej vyhodnocovacej stratégii. Porovnáva počet vrcholov v našich predpovedaných tvaroch s tými v skutočných budovách [7]. Tým nám metrika pomáha porozumieť, ako presne náš model replikuje detailnú štruktúru budov.

Max Tangent Angle Error (MTAE)

Na zaistenie čistej geometrie pri extrakcii budov, je dôležité presné meranie pravidelnosti kontúr. Chyba maximálneho uhla dotyčníc (resp. Max Tangent Angle Error (MTAE)) [1] je metrika navrhnutá presne pre tieto potreby, a je doplnením Intersection over Union (IoU) metriky. Špecificky cieli na nedostatok IoU metriky, ktorým je to, že segmentácia s okrúhlymi rohmi môže dosiahnuť vyššie skóre než segmentácia s presnejšími (ostrejšími) rohmi. Vyhodnocovaním zhody okrajov budov cez porovnávanie uhlov dotyčníc vo vybraných bodoch predikovaných a skutočných kontúr, MTAE efektívne penalizuje nepresnosti v orientácii okrajov. Toto zameranie na presnosť okrajov je dôležité pre produkovanie čistých vektorových reprezentácií budov, zdôrazňujúc dôležitosť presného vymedzenia hraníc v segmentačných úlohách.

Vyhodnotenie

Natrénované modely boli testované na veľkej dátovej množne leteckých snímok v plnej veľkosti (namiesto malých častí, pomocou ktorých bola sieť trénovaná). Takéto testovanie poskytuje presnejšie zobrazenie reálnych použití takýchto modelov. Na extrakciu budov zo snímok v plnej veľkosti sme použili techniku posuvného okna, čím boli vytvorené predikcie po jednotlivých segmentoch obrázku. Na okraje prekrývajúcich sa segmentov bola použitá pokročilá priemerovacia technika, dôležitá pre minimalizáciu nežiadúcich efektov a zachovanie konzistentnosti v rámci predikčnej mapy. Výstupná predikčná mapa v plnej veľkosti bola následne vektorizovaná do presných vektorových polygónov s použitím algoritmu Active Skeleton Model (ASM).

Výsledky

Výsledky z experimentov, odrážajúce výkon segmentačného modelu natrénovaného s rôznymi nastaveniami, odhalili zaujímavé zistenia (viď. Tabuľka 2). Vyhodnotili sme výkon základného modelu (len supervizovaný prístup) a výkon modelov trénovaných metódami učenia s čiastočným učiteľom s použitím rôznych podielov anotovaných a neanotovaných dát (1:1, 1:3, a 1:5).

1. IoU: hodnota IoU metriky bola pre základný model na hodnote 80.50%. S prínosom neanotovaných dát do trénovacieho procesu pozorujeme stabilný nárast, dosahujúc až 85.77%, s použitím pomeru 1:5 anotovaných k neanotovaným obrázkom.
2. Precision, senzitivita a F1 skóre: Hodnota metriky precision sa zlepšila z hodnoty 85.75% pre základný model na hodnotu 90.04% pre model s použitým podielom 1:5. Podobne senzitivita sa zľahka zvýšila z hodnoty 94.27% na 94.76%. F1 skóre taktiež narástlo z hodnoty 89.81% na 92.34%. Tieto zlepšenia naznačujú, že zakomponovaním metódy s čiastočným učiteľom sa model stal presnejším a spoľahlivejším v predikciách.
3. N Ratio a cIoU: Výsledky ukazujúznateľnýpokles v hodnote metriky N Ratio z hodnoty 2.33 pre základný model, na hodnotu 1.65 pre model s 1:5 podielom (anotované : neanotované), čo indikuje, že učenie s čiastočným učiteľom produkuje jednoduchšie, ale presnejšie vektorové tvary, ktoré viac pripomínajú skutočné štruktúry budov. Toto zjednodušenie tvarov pravdepodobne prispieva k zvýšenej použiteľnosti výstupu v praktických GIS aplikáciách. Súbežne, hodnoty metriky (cIoU) sa signifikantne zlepšili z hodnoty 48.89% pre základný model, na hodnotu 64.75% pre model s 1:5 podielom. Preto sa zdá, že učenie s čiastočným učiteľom nezlepšuje len zhodu predikovaných stôp budov a skutočných stôp budov, ale tiež generuje jednoduchšie vektorové tvary, ktoré sú bližšie reálnym geometrickým tvarom budov.
4. Priemerná MTAE: Redukcia metriky MTAE z 18.60° na 17.45° pri použití učenia s čiastočným učiteľom predstavuje zlepšenie v geometrickej presnosti predikcií modelu. To naznačuje, že táto metóda učenia je lepšia pri zachytávaní architektonických prvkov budov s presnejšie definovanými uhlami, čo prispieva k produkcii topologicky jednoduchších a čistejších vektorových polygónov.

Trénovanie na HPC

HPC konfigurácia

Trénovanie bolo realizované na HPC klastri Devana vybavenom dostatočnými výpočtovými zdrojmi. HPC klaster Devana disponuje 8 GPU uzlami. Každý GPU uzol obsahuje 4 GPU karty NVIDIA A100 s kapacitou VRAM  40GB, 64 jadier CPU a 256GB kapacity RAM. Plánovanie úloh zabezpečuje systém Slurm.

PyTorch Lightning knižnica

Na paralelizáciu sme použili knižnicu PyTorch Lightning, ktoré poskytuje užívateľsky priateľské prostredie pre prácu s viacerými GPU. Táto knižnica umožňuje užívateľovi špecifikovať počet GPU, počet výpočtových uzlov, poskytuje rôzne distribuované stratégie a možnosť mixed-precision trénovania.

Slurm a PyTorch Lightning nastavenie

Pri trénovaní pomocou 1 GPU vyzerala naša Slurm konfigurácia nasledovne:
#SBATCH –partition=ngpu
#SBATCH –gres=gpu:1
#SBATCH –cpus-per-task=16
#SBATCH –mem=64000

A nastavenie PyTorch Lightning pre Trainer:

trainer = Trainer(accelerator=”gpu”, devices=1)

Takto sme alokovali jednu GPU kartu zo štyroch dostupných na danom uzle, a 16 CPU zo 64 dostupných, následkom čoho máme 16 workerov pre data loadery. Keďže učenie s čiastočným učiteľom využíva dva data loadery, (jeden pre anotované a ďalší pre neanotované dáta), alokovali sme 8 workerov pre každý z nich. Je dôležité zaručiť, aby celkový počet jadier pre data loadery nepresiahol počet dostupných jadier, pretože trénovanie môže zlyhať.

Distribuované dátovo-paralelné (DDP) trénovanie

S použitím PyTorch Lightning distribuovaného dátovo-paralelného trénovania (DDP) sme dosiahli, že každá použitá GPU bola operovaná nezávisle:

• Každá GPU spracovala časť dátovej sady.
• Všetky procesy inicializovali model nezávisle.
• Všetky procesy vykonali dopredné a spätné šírenie paralelne.
• Gradienty boli synchronizované a spriemerované medzi procesmi.
• Každý proces aktualizoval svoj optimalizátor individuálne.

S týmto prístupom vypočítame počet data loaderov nasledovne: pre učenie s čiastočným učiteľom v prostredí jedného uzla so 4 GPU kartami a dvoma typmi data loaderov, máme 8 data loaderov, pričom každý má 8 workerov – dohromady 64 workerov.

Na plné využitie jedného uzla so 4 GPU sme použili nasledovnú konfiguráciu:

#SBATCH –partition=ngpu

#SBATCH –gres=gpu:4

#SBATCH –exclusive

#SBATCH –cpus-per-task=64

#SBATCH –mem=256000

Kľúčové slovo „–exclusive“ znamená, že daný výpočtový uzol nebude súčasne poskytnutý inému používateľovi. Špecifikácie „–cpus-per-task=64“ a „–mem=256000“ sú v danom nastavení redundantné, nakoľko sa použijú všetky výpočtové zdroje daného uzla.

PyTorch Lightning Trainer, nastavíme nasledovne:

trainer = Trainer(accelerator=”gpu”, devices=4, strategy=”ddp”)

Využitie viacerých výpočtových uzlov

S použitím PyTorch Lightning knižnice je tiež možné využiť viacero výpočtových uzlov v HPC systéme. Napríklad, využitie 4 uzlov so 4 GPU kartami na každom uzle (dohromady 16 GPU) bolo konfigurované:

trainer = Trainer(accelerator=”gpu”, devices=4, strategy=”ddp”, num_nodes=4)

Analogicky, Slurm konfigurácia bola nastavená takto:

#SBATCH –nodes=4

#SBATCH –ntasks-per-node=4

#SBATCH –gres=gpu:4

Tieto nastavenia a výsledky zdôrazňujú škálovateľnosť a flexibilitu komplexného trénovacieho procesu modelov strojového učenia v HPC prostredí, najmä pre úlohy, ktoré vyžadujú významné výpočtové zdroje, ako je napríklad naša úloha využívajúca učenie s čiastočným učiteľom v geopriestorovej dátovej analýze.

Analýza škálovateľnosti trénovania

V analýze škálovateľnosti trénovania sme dôkladne preskúmali vplyv rozširovania výpočtových zdrojov na efektívnosť trénovania modelov s využitím knižnice PyTorch Lightning.
Tento prieskum zahŕňal metódy učenia s učiteľom aj čiastočným učiteľom s dôrazom na zvyšovanie počtu GPU kariet, vrátane prístupu využívajúceho 2 uzly (8 GPU).

Kľúčovým zistením z tejto analýzy je, že nárast v pomeroch urýchlenia pre učenie s učiteľom nie je priamo úmerný počtu použitých GPU kariet. Ideálne, zdvojnásobenie počtu GPU kariet by malo zdvojnásobiť urýchlenie (t.j., napr. použitie 4 GPU kariet by malo mať za následok štvornásobné urýchlenie voči jednej GPU karte). Skutočné hodnoty urýchlenia boli nižšie než ideálne hodnoty. Tento nesúlad možno pripísať tzv. overhead-u (.j. nutnému navýšeniu operácií, ako transfer dát, I/O a pod. a tým pádom aj celkovému trvaniu výpočtu) asociovanému s manažovaním viacerých GPU kariet a výpočtových uzlov, obzvlášť synchronizácii dát cez všetky GPU karty, čo má za následok pokles efektívnosti.

Učenie s čiastočným učiteľom ukázalo mierne iný trend, viac približujúci sa ideálnemu (lineárnemu) nárastu urýchlenia. Zdá sa, že komplexnosť a vyššie výpočtové nároky učenia s čiastočným učiteľom zmierňujú dopad overhead nákladov a tým umožňujú efektívnejšie využívanie viacerých GPU. Napriek výzvam spojeným so synchronizáciou dát cez viacero GPU kariet a výpočtových uzlov, vyššie výpočtové nároky učenia s čiastočným učiteľom umožňujú efektívnejšie škálovanie zdrojov, t.j. urýchlenie bližšie ideálnemu scenáru.

Záver

Výskum predstavený v tejto práci úspešne demonštruje efektívnosť integrácie metódy UniMatch, ktorá patrí medzi metódy učenia s čiastočným učiteľom, do Frame Field learning metódy, pre úlohy extrakcie budov z leteckých snímok. Táto integrácia primárne adresuje notorický nedostatok anotovaných dát v aplikáciách hlbokého učenia v geografických informačných systémoch (GIS) a navyše, poskytuje škálovateľný a efektívny prístup z hľadiska úspory nákladov.

Výsledky sumarizované v tejto štúdii indikujú, že použitie učenia s čiastočným učiteľom významne zlepšuje výkon modelu vo viacerých kľúčových metrikách, vrátane  Intersection over Union (IoU), presnosti pozitívnych predikcií, senzitivity, F1 skóre, N Ratio, complexity-aware IoU (cIoU), a priemernej chyby Max Tangent Angle Error (MTAE). Obzvlášť, zlepšenia v metrikách IoU a cIoU zdôrazňujú zvýšenú presnosť modelu vo vymedzovaní stôp budov a generovaní vektorových tvarov, ktoré vierohodne reprezentujú skutočné štruktúry. Tento výsledok je dôležitý pre aplikácie urbanistického plánovania, environmentálne štúdie a manažment infraštruktúry, kde sú precízne mapovanie a popis budov kľúčové.

Prezentovaná metodika, ktorá kombinuje Frame Field learning s inovatívnym UniMatch prístupom, preukázala, že je vysoko efektívna vo využívaní kombinácie anotovaných a neanotovaných dát. Táto stratégia nielen že zlepšuje geometrickú presnosť predikcií modelu, ale tiež zaručuje generovanie jednoduchších a topologicky presnejších vektorových polygónov. Navyše, škálovateľnosť a efektívnosť trénovania na HPC systéme Devana s použitím knižnice PyTorch Lightning a distribuovanej, dátovo-paralelnej stratégie (DDP) bola kľúčová pre zvládnutie tak výpočtovo náročných úloh, akým je učenie s čiastočným učiteľom nad príslušnými dátami, v časovom rozsahu rádovo desiatok minút, až hodín.

Práca zdôrazňuje potenciál učenia s čiastočným učiteľom v zlepšovaní automatickej extrakcie budov z leteckých snímok. Implementácia UniMatch do Frame Field learning metódy predstavuje významný krok vpred, poskytujúc robustné riešenie pre výzvy spojené s nedostatkom dát a potreby vysokej presnosti geopriestorovej dátovej analýzy. Tento prístup zlepšuje efektívnosť a presnosť extrakcie budov, a taktiež otvára nové možnosti pre aplikácie metód učenia s čiastočným učiteľom v GIS a príbuzných oblastiach.

Poďakovanie

Výskum bol realizovaný s podporou Národného kompetenčného centra pre HPC, projektu EuroCC 2 a Národného Superpočítačového Centra na základe dohody o grante 101101903-EuroCC 2-DIGITALEUROHPC-JU-2022-NCC-01.

Časť výskumu bola realizovaná s využitím výpočtovej infraštruktúry obstaranej v projekte Národné kompetenčné centrum pre vysokovýkonné počítanie (kód projektu: 311070AKF2) financovaného z Európskeho fondu regionálneho rozvoja, Štrukturálnych fondov EU Informatizácia spoločnosti, operačného programu Integrovaná infraštruktúra 2014-2020.

Autori:

Patrik Sabol – Geodeticca Vision s.r.o., Floriánska 19, 044 01 Košice, Slovenská republika

 Bibiána Lajčinová – Národné Superpočítačové Centrum, Dúbravská cesta 3484/9, 84104 Bratislava-Karlová Ves, Slovenská republika

Plná verzia článku SK

Plná verzia článku EN

Literatúra:

[1] Nicolas Girard, Dmitriy Smirnov, Justin Solomon, and Yuliya Tarabalka. “Polygonal Building Extraction by Frame Field Learning”. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (June 2021), pp. 5891-5900.

[2] L. Yang, L. Qi, L. Feng, W. Zhang, and Y. Shi. “Revisiting Weak-to-Strong Consistency in Semi-Supervised Semantic Segmentation”. In: 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (June 2023), pp. 7236-7246. doi: 10.1109/CVPR52729.2023.00699.

[3] Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin D. Cubuk, Alex Kurakin, Han Zhang, and Colin Raffel. “FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence”. In: CoRR, vol. abs/2001.07685 (2020). Available: https://arxiv.org/abs/2001.07685.

[4] Emmanuel Maggiori, Yuliya Tarabalka, Guillaume Charpiat, and Pierre Alliez. “Can Semantic Labeling Methods Generalize to Any City? The Inria Aerial Image Labeling Benchmark”. In: IEEE International Geoscience and Remote Sensing Symposium (IGARSS) (2017). IEEE.

[5] Adrian Boguszewski, Dominik Batorski, Natalia Ziemba-Jankowska, Tomasz Dziedzic, and Anna Zambrzycka. “LandCover.ai: Dataset for Automatic Mapping of Buildings, Woodlands, Water and Roads from Aerial Imagery”. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops (June 2021), pp. 1102-1110.

[6] “Ortofotomozaika.” Geoportal SK. Accessed February 14, 2024. https://www.geoportal.sk/sk/zbgis/ortofotomozaika/.

[7] Stefano Zorzi, Shabab Bazrafkan, Stefan Habenschuss, and Friedrich Fraundorfer. “PolyWorld: Polygonal Building Extraction with Graph Neural Networks in Satellite Images”. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (2022), pp. 1848-1857.