Odvětvové informační středisko a Zeměměřická knihovna VÚGTK 250 66 Zdiby 98, tel. +420 284 890 375, fax: +420 284 890 056

[Detecçăo e reconstruçăo automática de junçőes de rodovia em imagens digitais de cenas rurais]

Marco Aurélio Oliveira da Silva, Aluir Porfírio dal Poz. - In: Bol. Cięnc. Geod. - ISSN 1413-4853. - Roč.9, č.2 (2003), s.263-281 : 11 obr. - Res. angl. - Lit.19.

Přeložila M. Kulatá (zkráceno)
Zdiby : VÚGTK, 2004. - 6 s.

Klíčová slova: GIS, mobilní, terén

Abstrakt:

Hlavním cílem této práce je automatická komplementace výsledků vytvořených poloautomatickými metodami extrakce silnic zaměřená na detekci a rekonstrukci křižovatek ve venkovských oblastech. Vyvinutá metoda založená na čtyřech modelech nejčastějších typů křižovatek venkovských scén, byla experimentálně zhodnocena použitím tří leteckých snímků středního rozlišení a shledána jako účinný prostředek pro komplementaci silniční sítě.

1. Úvod

Většina metod zabývajících se extrakcí silnic je založena na poloautomatických strategiích, které vyžadují zásah operátora. Ten je schopen zařadit informace do kontextu a využít apriorní znalosti. Může také dohlížet na proces extrakce od začátku až po opravu možných nedostatků.

Zřídka se v metodologii extrakce silnic objevuje detekce a automatická rekonstrukce křižovatek, především z důvodu enormní variability případů výskytu křižovatek. Navíc je těžké uplatnit zde apriorní znalosti. Specializovaná literatura se více zabývá metodami extrakce úseků silnic, které spojují oblasti křižovatek. Zde je možné použít dobře definované apriorní znalosti a tyto metody mají uspokojivé výsledky. Toto upřednostňování metod extrakce úseků silnic spojujících oblasti křižovatek jde na úkor toho, že celková rekonstrukce topologie silniční sítě závisí v podstatě na detekci a rekonstrukci křižovatek.

(Některé metody extrakce jak křižovatek, tak také i úseků mezi nimi i metody automatické a poloautomatické jsou zde krátce zmíněny a popsány).

Článek představuje metodu pro detekci a automatickou rekonstrukci křižovatek na digitálních snímcích venkovských scén. Metoda vyžaduje, aby úseky silnice spojující oblasti křižovatek byly předem vyňaty poloautomatickými metodami. Při těchto metodách operátor iniciuje proces pomocí několika zárodečných bodů, koriguje případné nedostatky v průběhu i po procesu extrakce a následně rekonstruuje křižovatky. Cílem této práce je redukce potřeby zásahu operátora, a tím zvýšení automatizace celého procesu. Metoda se zakládá na dvou postupných etapách. V první fázi jsou potenciální oblasti křižovatek silnic detekovány pomocí kritérií blízkosti a radiometrické homogenity. Kritérium blízkosti zjistí uskupení bodů patřící úsekům silnic, jejichž vzájemná vzdálenost nepřekračuje určitou horní hranici. Kritérium radiometrické homogenity ověří, zda oblast ohraničená body vybranými prvním kritériem je radiometricky kompaktní s vozovkou. Ve druhé fázi jsou používány čtyři modely křižovatek, které reprezentují typické formy výskytu křižovatek na snímcích venkovských scén. Tyto modely pak umožňují rekonstrukci křižovatek detekovaných v předchozí fázi. Proces rekonstrukce spočívá ve výpočtu nejreprezentativnějšího bodu z geometrického centra oblasti křižovatky a v geometrickém spojení mezi tímto bodem a body oblasti křižovatky, zjištěné v předchozí fázi. Experimentální výsledky dokázaly, že navržená metoda je užitečným nástrojem pro automatickou komplementaci silniční sítě.

2. Metody pro rekonstrukci křižovatek na leteckých snímcích venkovských scén

Při poloatomatickém provedení extrakce silnic následuje rekonstrukce křižovatek pomocí čtyř modelů typických forem výskytu křižovatek venkovských scén zobrazených na obr. 1:

Obr. 1 - Obvyklé typy křižovatek ve venkovských oblastech

Dále je navrženo počítačové řešení problému automatické rekonstrukce křižovatek na základě výše zmíněných modelů. Metoda se zakládá na dvou etapách: identifikace oblasti výskytu křižovatek a provedení identifikace modelů křižovatek s předem detekovanými oblastmi.

2.1 Identifikace oblastí křižovatek

Metodologie pro identifikaci míst, kde se vyskytují křižovatky, spočívá na výsledcích vytvořených nějakým poloautomatickým kresličem silnic, např. kreslič spočívající na algoritmu dynamického programování (DAL POZ a AGOURIS, 2001). Kromě vlastních souřadnic bodů, které definují úseky silnice, mohou být procesy předcházejícími extrakci vytvořeny další údaje, např. místní šířka silnice spjatá s body úseků silnice, průměrná šířka pro každý úsek silnice, místní úroveň šedi spjatá s body úseků silnice, průměrná úroveň šedi pro každý úsek silnice atd… Oblasti křižovatky jsou identifikovány analýzou těchto údajů, podle kritérií blízkosti a radiometrické homogenity.

Pomocí kritéria blízkosti jsou dva úseky silnic kandidáty na to, aby se setkaly v křižovatce, jestliže nejmenší vzdálenost mezi dvěma z jejich příslušných bodů by byla menší než n-krát průměrná šířka silnic předem extrahovaných a zahrnutých do analýzy.

Kritérium blízkosti (obr. 2) je tedy dáno rovnicí:

rovnice (1),

kde:

Obr. 2 - Kritérium blízkosti

Obr. 2 představuje dvě možná uspořádání křižovatky. Skutečná situace je zpočátku neznámá a závisí na úsudku operátora v momentu zadání příslušných údajů pro algoritmus extrakce úseků silnice.

Obr. 2 (a) ukazuje, že operátor se rozhodl nakládat se silnicí "i" jako by byla pouze jedním úsekem. Tím získal dva úseky označené jako silnice i a silnice j. Kritérium blízkosti je aplikované na body K náležící silnici j a I náležící silnici i, tato poslední musí být přemodelovaná geometricky kritériem minimální vzdálenosti, tzn. bod I má být umístěn tak, aby dⁱ_j (l,k) byla nejmenší. Vzhledem k použitému algoritmu si operátor mohl myslet, že algoritmus extrakce není schopen překonat křižovatku mezi oběma silnicemi a následně silnice i by byla rozdělena operátorem na dva úseky (obr. 2 (b)).

V tomto případě, jak ukazuje obr. 2(b), kritérium blízkosti pozná oblast křižovatky složené ze tří krajních bodů úseků silnic. Z této jednoduché analýzy vyplývá, že problém identifikace oblastí křižovatky a příslušných bodů, které je tvoří, pomocí tohoto kritéria není tak jednoduchým algoritmickým úkolem. Kromě toho se mohou vyskytnout situace, ve kterých je nutná následná verifikace, pokud mají být použita jiná kritéria.

Kritérium radiometrické homogenity ověřuje platnost křižovatek dříve rozpoznaných kritériem blízkosti. Pomocí kritéria radiometrické homogenity jsou dvě osy silnic kandidáty na to, aby tvořily křižovatku, jestliže průměrná hladina šedi podél čáry, která spojuje její příslušné dva nejbližší body

je přibližně stejná jako hladina šedi silnic předem extrahovaných a zahrnutých do analýzy. Hladiny šedi jsou modelovány v předem stanovených intervalech (obvykle 1 pixel) pomocí některé metody interpolace (např. bilineární interpolace) na základě původního snímku. Kritérium radiometrické homogenity pro každý pár (i a j) úseků silnice je dán následujícím pravidlem (obr. 3)

rovnice (2)

rovnice (3) ,

kde:

Obr. 3 - Kritérium radiometrické homogenity

Obr. 3 představuje stejný příklad jako při analýze kritéria blízkosti (obr. 2). Na obr. 3 (a) zahrnuje křižovatka předem detekovaná kritériem blízkosti jeden úsek přímky S_(i,j), na který je aplikováno kritérium radiometrické homogenity. Na obr. 3 (b) zahrnuje oblast křižovatky, která má být detekovaná, tj. trojúhelník definovaný body I, J a K. Kritérium radiometrické homogenity je tu aplikováno na úsecích přímky (S_(i,j), S_(i,k) a S_(j,k)) definovaných body detekovanými prvním kritériem, což jsou body I, J a K.

Algoritmus pro identifikaci oblastí křižovatky se tedy zakládá na dvou následných výše popsaných etapách. V první etapě jsou detekovány body s potenciálem konstituovat křižovatku, pravidlo pro rozhodnutí se zakládá na kritériu blízkosti. Ve druhé etapě používá algoritmus kritérium radiometrické homogenity pro ověření a opravení možných omylů, vzniklých v první etapě.

Na obr. 4(a) je ilustrativní příklad, kde je detekován nesprávný bod křižovatky. V tomto případě jsou detekovány dvě potenciální oblasti křižovatky silnic (J₁ a J₂). Již jednoduchá vizuální kontrola obrázku 4(a) ukazuje, že postup není správný.

Obr. 4 - Determinace potenciálních oblastí křižovatky

(a) Kritérium blízkosti

(b) Kritérium radiometrické homogenity

Na obr. 4(b) je kritérium radiometrické homogenity aplikováno na úsecích přímky spojující body oblastí předtím detekované křižovatky. Protože úseky přímek p₁p₂, p₁p₃ a p₂p₃ se nacházejí na vozovce silnice, průměrné tóny šedi na těchto úsecích, dané rovnicí 3, se výrazněji neodlišují od průměrného tónu šedi úseků silnice zahrnutých do oblasti křižovatky J_l. Všechny body J_l jsou tedy potvrzené kritériem radiometrické homogenity. V oblasti křižovatky J₂, průměrné tóny šedi pro úseky přímek p₄p₆ a p₅p₆ mají být příslušně nižší než je průměrný tón šedi úseků silnic r₂, r₄ a r₆. Bod p₆ by tedy měl být odstraněn z oblasti křižovatky J₂, zůstanou jen body p₄ a p₅.

Výše popsaná metoda umožní zjistit, že v determinované oblasti existuje křižovatka a dále že lze identifikovat, které body a úseky silnice jsou v detekované křižovatce zahrnuty. Kompletní rekonstrukce detekovaných křižovatek vyžaduje identifikaci styčných bodů. Kromě toho úseky zahrnuté do

křižovatek silnic mají být spojeny s příslušnými styčnými body. Řešení tohoto problému zakládající se na modelech křižovatek je představeno v následující části.

2.2 Rekonstrukce silniční sítě s použitím modelů křižovatek silnic

Algoritmus rekonstrukce křižovatky závisí na formě, jakou se úseky silnic stýkají v příslušných oblastech křižovatky. Detekované oblasti křižovatky jsou klasifikované podle možných modelů (obr. 5). Možnosti pro každý model závisí na tom, jak jsou silnice v oblasti křižovatky extrahovány, což svým způsobem závisí na úsudku operátora, když vybírá zárodečné body. Například křižovatka "T" může být tvořena dvěma nebo třemi úseky silnic.

MODELY KŘIŽOVATEK

Obr. 5 - Klasifikace oblastí křižovatky

Křižovatky typu "T" a "Y" mají stejné charakteristiky, co se týká výskytu a zahrnutých bodů - tzn., zda se jedná o body střední (prázdné kolečko na obr. 5) nebo krajní (černá kolečka na obr. 5) úseků silnice. Rozlišení spočívá v ověření úhlů mezi úseky silnic zahrnutými do příslušné oblasti křižovatky. Čtyři možnosti křižovatky typu "X" jsou kompatibilní s různými možnostmi inicializace předcházejícího procesu extrakce úseků silnic. Pro typ "L" je pouze jedna možnost.

Úhel mezi dvěma úseky silnice, klíčový prvek pro identifikaci různých typů křižovatek, je definován jako úhel mezi vektory směru úseků silnice v zahrnutých bodech křižovatky. Každý vektor směru úseku silnice je definován pomocí bodu oblasti křižovatky, která je považována za její nejbližší sousední. Např. v případě krajních bodů se vektory směru získají pomocí dvou prvních nebo dvou posledních bodů úseků silnice. Pokud jsou V_i = (c₁ c₂) a V_j = (c´₁ c´₂) dva vektory směru odpovídající silnicím i a j, definované ve dvou bodech klasifikovaných jako body oblasti křižovatky, pak úhel mezi uvažovanými osami je dán rovnicí:

rovnice (4),

Styčný bod mezi osami silnic i a j je dán průsečíkem mezi přímkami definovanými body patřícími do křižovatky a jejich příslušnými nejbližšími sousedními body.

Jestliže a_i x - y + b_i = 0 a a_j x - y + b_j = 0,
jsou příslušné rovnice přímky vztahující se k silnicím i a j, pak průsečík (J_(i,j)) mezi oběma silnicemi je dán rovnicí:

rovnice (5)

Styčné body pro možnosti modelů T (J_T) a Y (J_Y) se získají podle obr. 6:

Obr. 6 - Určení styčného bodu pro modely T a Y 

V případě, kdy  J_T = J_(i+j,k) a J_Y = J_(i+j,k), znamená to, že "i + j" je sloučení silnic i a j. Je tedy velmi důležité vědět a priori, který model se nejlépe hodí pro určenou oblast předem detekované křižovatky.

Např. J_T = J_(i+j,k) informuje, že nejdříve mají být sloučeny úseky silnic i a j a potom má být vypočítán styčný bod jako průsečík (rov. 5) výsledku sloučení ("i+j") a úseku silnice k.

Obr. 7 ukazuje, jak se získají styčné body pro různé možnosti modelů X (J_X) a L (J_L).

Obr. 7 - Určení styčného bodu pro modely X a L

V případě, že J_X = J_(i+j,k), J_X = J_(i,j+k) a J_X = J_(i+j,k+l) , znamená to, že "i+j", "j+k" a "k+l" představují postupné sloučení silnic i a j, j a k, a k a l.

Např. J_X = J_(i+j,k+l) ukazuje, že styčný bod je určen průsečíkem (rovnice 5) mezi "i+j" a "k+l". V případě, že J_X = J_(i,j) znamená to, že styčný bod je určen přímo průsečíkem úseků silnic i a j.

Ilustrativní příklad (stejný jako při detekci oblasti obr. 4) je na obr. 8. Předem detekované oblasti křižovatky jsou na obr. 8(a). Obr. 8(b) ukazuje, že obě oblasti křižovatek byly rekonstruovány pomocí modelů křižovatek "X" a "L", na základě pravidel J_(r1+r2,r3) a J_(r4,r5).

Obr. 8 - Ilustrativní příklad rekonstrukce silniční sítě

(a) Oblasti detekované křižovatky;
(b) Rozšíření os silnic na determinované styčné body.

3. VÝSLEDKY

Vyvinutá metoda byla provedena v jazyku Borland C++ Builder 4.0 pro prostředí PC-Windows. Pro zhodnocení metody byly provedeny experimenty poloautomatickou metodou extrakce silnic navrženou v DAL POZ a SILVA (2002 a, b). Tři letecké snímky použité pro experimenty mají střední rozlišení (pixely mezi 0,7m a 2,0m) a silnice na těchto snímcích mají průměrnou délku mezi 3 a 6 pixely. Snímky byly získány na home page systému Badger (BADGER, 2000).

První experiment byl realizován se skutečným snímkem (obr. 9 (a)). Snímek je tvořen třemi hlavními silnicemi, které byly patřičně extrahovány. Dvě křižovatky typu "T" byly detekovány a rekonstruovány pomocí algoritmu rekonstrukce silniční sítě (obr. 9(b), detailněji obr. 9(c)). Na obr. 9(c) ukazují oba horní podobrázky zvětšené příslušné oblasti křižovatek a odpovídající spodní podobrázky příslušné křižovatky detekované a rekonstruované. Styčné body rekonstruovaných křižovatek se nacházejí na velmi přesných pozicích, číselná komparace mezi pozicemi styčných bodů určených použitím příslušného algoritmu a odpovídajících pozic určených vizuálně ukazují, že rozdíly jsou v řádu 1 pixelu.

Obr. 9 - Výsledky získané se skutečným snímkem
(a) metodou extrakce;
(b) rekonstrukcí silniční sítě;
(c) zvětšením plochy křižovatky.

I ve druhém experimentu se skutečným snímkem je metoda úspěšná. Je ověřeno, že křižovatka typu "X" byla správně detekována a rekonstruována pomocí zmíněného algoritmu. Styčný bod rekonstruované křižovatky je situován naprosto přesně. Stejně jako u předchozího experimentu, vzdálenost mezi styčnými body rekonstruovanými počítačem a manuálně, je kompatibilní s úrovní pixelu. Také silniční síť je z topologického hlediska rekonstruována správně.

Také ve třetím experimentu se skutečným snímkem složeným z 10 silnic, které tvoří různé typy křižovatek, jsou i přes přítomnost geometrických nepravidelností a překážek výsledky získané metodou extrakce uspokojivé. Je patrná existence 9 křižovatek všech čtyř typů. Ukazuje se dobrá kvalita výsledků, dostatečně kompatibilní s těmi, které by byly získány manuálně. Je to potvrzeno také numericky, při srovnání styčných bodů rekonstruovaných počítačem a vizuálně, je získán průměrný rozdíl kolem 1 pixelu.

4. Závěr a budoucí perspektivy

Tato práce představila automatickou metodologii pro detekci a rekonstrukci křižovatek na digitálních snímcích venkovských scén. Hlavním cílem této metodologie je automatická komplementace výsledků vytvořených poloautomatickými metodami extrakce silnic, které obvykle umožňují přesnou a důvěryhodnou extrakci prvků silnice, které spojují oblasti křižovatek. To znamená, že navrženému algoritmu zbývá úkol detekovat a rekonstruovat automaticky křižovatky silnic. Operátorovi zůstane pouze zodpovědnost za umístění zárodečných bodů oblastí křižovatky.

Vyvinutá metoda byla experimentálně zhodnocena použitím tří leteckých snímků středního rozlišení. Jak topologie rekonstruovaných křižovatek, tak i reprezentativní bod křižovatek silnic se ukázaly jako dostatečně slučitelné s tím, co by se získalo vizuálně. Experimentální výsledky tedy dokázaly, že navržená metoda je účinným prostředkem pro komplementaci silniční sítě.

V budoucnu je možné rozšířit tuto metodologii na práci se snímky s komplexnějším obsahem, zahrnujícími např. předměstské scény s výskytem komplexnějších forem křižovatek, jako jsou např. viadukty a přístupy pomocí postranních ramen.