Kartdatabasehåndtering - Map database management

Kart database management systemer er programmer designet for å effektivt lagre og hente romlig informasjon. De er mye brukt i lokalisering og navigering, spesielt i bilapplikasjoner. Videre spiller de en stadig viktigere rolle i de nye områdene med stedsbaserte tjenester , aktive sikkerhetsfunksjoner og avanserte førerassistansesystemer . Felles for disse funksjonene er kravet til en innebygd kartdatabase som inneholder informasjon som beskriver veinettet.

Når den er utformet godt, muliggjør en kartdatabase rask indeksering og oppslag av en stor mengde geografiske data.

Innholdet i en kartdatabase

Figur 1: Funksjoner og deres respektive attributter i en kartdatabase

Kart lagres som grafer eller todimensjonale matriser av objekter med attributter for plassering og kategori, der noen vanlige kategorier inkluderer parker, veier, byer og lignende.

En kartdatabase representerer et veinett sammen med tilhørende funksjoner. Kartleverandører kan velge forskjellige modeller av et veinett som grunnlag for å formulere en database. Vanligvis inneholder en slik modell grunnleggende elementer (noder, lenker og områder) i veinettet og egenskapene til disse elementene (posisjonskoordinater, form, adresser, veiklasse, hastighetsområde, etc.). De grunnleggende elementene blir referert til som funksjoner og egenskapene som attributter. Annen informasjon knyttet til veinettet er også inkludert, inkludert severdigheter, bygningsformer og politiske grenser. Dette vises skjematisk i det tilstøtende bildet. Geographic Data Files (GDF) er en standardisert beskrivelse av en slik modell.

Hver node i et kartgraf representerer en punktplassering av jordens overflate og er representert av et par lengdegrad (lon) og breddegrad (lat) koordinater. Hver lenke representerer en veistrekning mellom to noder, og er representert av et linjesegment (tilsvarende en rett veiseksjon) eller en kurve som har en form som generelt er beskrevet av mellomliggende punkter (kalt formpunkter) langs lenken. Imidlertid kan kurver også være representert av en kombinasjon av centroid (punkt eller node), med en radius og polære koordinater for å definere grensene for kurven. Formpunkter er representert av lon-lat-koordinater som noder, men formpunkter tjener ikke formålet med å koble sammen lenker, det samme gjør noder. Områder er todimensjonale former som representerer ting som parker, byer, blokker og er definert av grensene. Disse dannes vanligvis av en lukket polygon , som er former som indikerer at et objekt over et kart må ha en nær grense, noe som betyr at den første polygonen skal være den samme som en siste polygon. (For eksempel, for å plotte et kvadratisk objekt på et kart, er polygonene 1,2,3,4,1.)

Et annet poeng for validering på data er poenget i polygon , som hjelper til med å finne punkter som ligger utenfor en polygon. F.eks. For en bestemt lon-lat-koordinater i en by, hvis punktet krysser polygonet i et oddetall, så er det inne i polygonet og et gyldig punkt; ellers er den utenfor polygonet og ugyldig.

Utvekslingsformat

Kartleverandører samler vanligvis inn, aggregerer og leverer data i et veldefinert og dokumentert filformat som er spesielt ment for informasjonsutveksling, f.eks. Navteq bruker Standard Interchange Format (SIF) og GDF , mens Tele Atlas bruker en proprietær form for GDF. Det er vanligvis i vanlig tekstform ( ASCII ) som består av felt som lett kan tolkes og tolkes av de forskjellige partene som skal håndtere det. Det bærbare formatet gjør det enkelt å utføre tillegg, slettinger og modifikasjoner av enkle tekstredigeringsprogrammer.

Et lite antall posttyper brukes til å representere de forskjellige typene data. Hver posttype består av en sekvens av felt, som enten har fast lengde eller avgrenses av et tegnsettingstegn, for eksempel et komma. For eksempel kan en lenkeenhet representeres av en registrering av skjemaet:

der type1 definerer dette som en koblingsposttype og etikett fungerer som en identifikator for å skille denne lenken fra alle andre. Den z1 og Z2 felt bestemme den vertikale atskillelse av denne koblingen fra andre deler av de tilsvarende noder node1 og node2 . Dermed kan en overgang til en lenke for eksempel bli representert som ikke koblet til den lenken. Andre posttyper brukes til å representere adresseinformasjon, formpunkter for en lenke, byer og stater, interessepunkter (POI) osv.

Utvekslingsformatet for en kartdatabase er ikke organisert godt for bruk av en navigasjonsenhet under kjøretid. Postene er i en vilkårlig rekkefølge og er derfor vanskelige å søke og data, som gatenavn og koordinatverdier, gjentas fra post til post. Følgelig omorganiseres databaseinnholdet til en binær form som er mer egnet for driftstid.

Kjøretidsformat

Kjøretidsformater er vanligvis proprietære, og forhindrer interoperasjon av kart mellom forskjellige navigasjonssystemer. Imidlertid er et nytt initiativ kalt Navigation Data Standard (NDS) en bransjegruppe av bilprodusenter, leverandører av navigasjonssystemer og kartdataleverandører som har som mål å standardisere dataformatet som brukes i bilnavigasjonssystemer. De involverte selskapene inkluderer TomTom , BMW , Volkswagen , Daimler , Renault , ADIT, Alpine Electronics , Navigon , Bosch , DENSO , Mitsubishi , Harman Becker, Panasonic , PTV, Continental AG , Navteq og Zenrin .

Databasen omorganiseres av en navigasjonsleverandør gjennom en kompileringsprosess som inneholder minst følgende fem trinn:

1. Se etter nettverkskonsistens. Forsikre deg for eksempel om at alle nodepar som skal kobles sammen med en lenke har en slik kobling og omvendt har alle nodepar som ikke skal kobles til ikke har en koblingslenke.
2. Tilordne identifikatorer (ID-er) til alle enheter på en systematisk måte.
3. Bruk flere sett med indekser på enheter for å gjøre det lettere å søke i databasen på forventede måter.
4. Erstatt flere forekomster av dataelementer (gatenavn, koordinater, etc.) med indekser i tabeller som inneholder en enkelt kopi av hvert slikt element.
5. Bruk andre komprimeringsteknikker for å redusere den totale størrelsen på databasen.

Konsistenskontrollen i trinn 1 er vanligvis en veldig interaktiv og iterativ prosess som kan ta uker å fullføre. I løpet av denne tiden må avvik oppdages, undersøkes og løses.

I trinn 2 blir IDer generelt tildelt sekvensielt når enheter av hver type oppstår. Eventuelle endringer i inngangsdatabasen fra en versjon til en annen vil påvirke tildelingen av ID-er til alle enheter. Følgelig er det liten forventning om kontinuitet i oppgaven mellom versjoner.

I trinn 3 lar hver anvendte indeks raskt søke i databasen på en bestemt måte. Ett indeks sett brukt på lenker kan sorteres etter den alfabetiske rekkefølgen på gatenavnene på lenkene. Et annet indeks sett brukt på lenker kan sorteres etter nodene de er koblet til for å lette ruteplanlegging. Nok et indeks sett brukt på noder kan sorteres i henhold til rekkefølgen på utseendet langs en vei. I noen av disse tilfellene kan et binært søk utføres i stedet for et uttømmende søk, og i noen tilfeller kan en søkeprosess erstattes med en enkel tabelloppslag.

Inkrementell oppdatering

For de fleste navigasjonsfunksjoner er det viktig å ha en oppdatert kartdatabase i kjøretøyet, og for noen funksjoner er det viktig, spesielt de som er relatert til aktiv sikkerhet. En vanlig strategi er å overføre oppdateringsinformasjon til kjøretøyet når den blir tilgjengelig via en trådløs kanal. Den trådløse kanalen kan være toveis, for eksempel Wi-Fi og mobiltelefon, kringkasting , for eksempel satellittradio, FM-underoperatør eller ATSC- datakasting, eller en kombinasjon av begge. I alle fall ville det være upraktisk eller ekstremt ineffektivt å overføre hele den nye databasen for å erstatte en eksisterende versjon, siden det sannsynligvis vil være flere gigabyte i størrelse.

I stedet er det ønskelig å overføre akkurat den informasjonen knyttet til endringer som er gjort i den eksisterende databasen. En stor vanskelighetsgrad er at enhver endring som gjøres i innholdet i en kartdatabase, generelt fører til endringer i alle tildelte enhets-IDer og alle tildelte indekser under kompileringsprosessen. Disse nye IDene og indeksene gjennomsyrer hele den sammensatte databasen, slik at enhver samling av trinn vil trolig utgjøre det meste av databasen. For å overvinne denne vanskeligheten, har tre tilnærminger blitt tatt, som kort er 1) ombord kompilator 2) oversikt butikk 3) geografiske fliser.

Kompilator om bord

I dette tilfellet overføres grunnleggende endringer i utvekslingsformatet til databasen til kjøretøyet. Slike endringer er representert i transaksjonsform bestående av tillegg , sletting og erstatning . Disse endringene brukes på den eksisterende innebygde databasen i utvekslingsformat. Utvekslingsformatet for den innebygde databasen kan enten lagres separat eller genereres etter behov ved å "dekompilere" kjøretidsformatet. Den samlede databasen blir deretter samlet, som innebærer tildeling av ID og bruk av indekser.

Denne samlingen ombord vil trolig være beregningsintensiv og kreve betydelig minne. Imidlertid trenger det ikke å være interaktivt og iterativt, det samme gjør off-board-kompilering, siden konsistenskontroller og oppløsning allerede har blitt gjort. Videre kan ombordkompilering gjøres i bakgrunnen, slik at beregningstiden ikke er kritisk.

Utseende butikk

I dette tilfellet blir grunnleggende endringer også overført til kjøretøyet, men blir plassert på et eget minneplass som kalles en butikk . Endringene er også representert i transaksjonsform, men kan vises i hvilket som helst praktisk format, som ikke nødvendigvis er hverken utveksling eller kjøretid. Under drift av navigasjonsenheten blir det søkt i butikken som ser bort fra hver gang du får tilgang til hoveddatabasen. Eventuelle transaksjoner (endringer) som gjelder dataene du får tilgang til, blir deretter brukt.

Nødvendigheten av å undersøke utkikklageret og bruke endringer for hver databasetilgang kompliserer selvfølgelig navigasjonsalgoritmene og forlenger beregningstiden. Dette unngår imidlertid behovet for en innebygd kompilator.

Geografiske fliser

I denne tilnærmingen er kartdatabasen delt inn i relativt små rektangulære regioner (fliser) som tessellerer kartet. Flisstørrelsen er i størrelsesorden 1 km på siden. Disse flisene er samlet separat, slik at alle ID-er og indekser er betinget av den spesifikke flisen de gjelder for. Brikkene som har endret seg på grunn av grunnleggende enhet eller attributtendringer i databasen, overføres til kjøretøyet, der de erstatter den tilsvarende eksisterende flisen.

Utskifting av fliser er betydelig enklere enn kompilering ombord eller å bruke en butikk som ser bort fra deg. Det kan imidlertid ikke være effektivt for overføring. En lokal endring av enheter og attributter, uavhengig av omfang, krever overføring av hele flisen som inneholder. Videre er det kanteffekter der en endring i en enhet innenfor en flis påvirker enhetene i nærliggende fliser. Det er ganske mulig at et lite antall enhetsendringer vil kreve overføring av nesten alle fliser, og derved beseire formålet med trinnvise oppdateringer. Disse problemene kan løses ved å velge flisestørrelse og hyppigheten for oppdatering.

Legge ved hjelpedata

Ulike navigasjonsfunksjoner, som involverer aktiv sikkerhet, førerassistanse og stedsbaserte tjenester, krever data som ikke anses å være en del av en kartdatabase, og som sannsynligvis leveres av en annen leverandør enn kartleverandøren. Slike data må krysshenvises til enhetene og attributtene til hoveddatabasen. Siden hjelpedataene ikke nødvendigvis er samlet med hoveddatabasen, er det imidlertid behov for andre midler for å etablere kryssreferanser, som refereres til som vedlegg av hjelpedataene. To vanlige tilnærminger er funksjonsspesifikke referansetabeller og generisk referanse.

Funksjonsspesifikke referansetabeller

Funksjonsspesifikke referansetabeller gir et middel for å feste funksjonsspesifikke data til en kartdatabase produsert av enhver deltakende leverandør. En slik tabell er produsert i fellesskap for å støtte en bestemt funksjon eller klasse av funksjoner som involverer stedsbasert service, aktiv sikkerhet eller avansert førerassistanse. Den vil vanligvis bestå av en liste over kartelementer av en bestemt type (f.eks. Lenker, kryss, interessante steder, etc.) sammen med identifiserende attributter (f.eks. Gatenavn, lengdegrad / breddegradskoordinater, etc.). I tillegg tildeles hver oppføring i tabellen en unik identifikator. Settet med oppføringer i en tabell velges generelt, gjennom enighet av alle interesserte parter. Som en praktisk sak vil resultatet representere en liten delmengde av elementene av den gitte typen som er tilgjengelige i kartdatabasene, og vil bestå av de som er viktigere for applikasjonsområdet. Etter at en tabell er formulert, er det oppgaven til hver deltakende leverandør å bestemme og kryssreferanse elementene i kartdatabasen som tilsvarer tabelloppføringene.

Figur 2: TMC-steder i Metro Detroit

Et mye brukt eksempel er TMC-standarden for plasseringskodetabeller for referanse til trafikkdata. TMC, som står for Traffic Message Channel , er en del av Radio Data System (RDS), som er implementert som en sub-carrier-modulasjon av et kommersielt FM-kringkastingssignal. TMC-tabellene gir primært referanser til punktsteder langs hovedveier som tilsvarer kryss med andre veier. En tabelloppføring identifiserer et punktsted ved hjelp av både kontekstuell informasjon (som region, vei og veidel, skjæringsnavn) og omtrentlige lengdegrad / breddekoordinater.

Identifikatorer tilordnet oppføringer i en tabell er 16-biters heltall og har derfor et område på 65536 verdier. Dette er for få til å dekke verden, så det er formulert separate tabeller for hvert land eller region i et land. For en gitt storbyregion er bare kryss langs motorveier, hovedveier og noen større veier inkludert. Dette er illustrert i følgende figur for metroen i Detroit. Dekningen er ment for å gi trafikkrådgivende informasjon om veier med høyt bruk. Trafikkbasert ruteplanlegging krever derimot dekning av alle eller nesten alle større veier, og støttes derfor ikke tilstrekkelig av TMC-plasseringskodetabeller slik de for øyeblikket er formulert.

Generisk referanse

Generisk referanse er et forsøk på å feste data til en hvilken som helst kartdatabase ved å oppdage referanseinformasjon gjennom en form for kartmatching. De funksjonsspesifikke dataelementene er tilordnet elementer, for eksempel punkter, lenker eller områder, som sannsynligvis bare tilnærmer de tilsvarende kartelementene i en bestemt kartdatabase. Et søk i kartdatabasen gjøres for best mulig passform. For å forbedre søkeprosessen legges naboelementer strategisk til hvert enkelt element for å sikre at riktig løsning blir funnet i hvert tilfelle. For eksempel, hvis kartelementet er en lenke som forbinder to kryss, kan en eller begge tverrgatene legges til av hensyn til søket. Forhåpentligvis gjør dette en feil kamp usannsynlig. Selv om prosedyren er ganske heuristisk, skisserer en foreslått standard kalt Agora strategien for å velge naboelementer som skal legges til.

Europeisk konsortium ActMAP

Et europeisk konsortium kalt ActMAP (Actualize Map) er (med sine ord) "utvikler standardiserte mekanismer for å oppdatere eksisterende kartdatabaseinnhold og muliggjøre dynamisk tilknytning av informasjon til det digitale kartet i kjøretøyet". ActMAP-konsortiet består av ERTICO (koordinator), BMW, CRF Fiat Research Center, DaimlerChrysler, Navigon, Navteq, Tele Atlas og Siemens VDO Automotive. De er ferdig med det meste av arbeidet og publiserte en rekke rapporter, som ble sendt til ISO- komiteen TC204 WG3 for standardisering. Rapportene deres fungerer som et godt utgangspunkt og referanse for arbeidet med dette prosjektet. Et viktig spørsmål deres rapporter adresserer, er å håndtere kompleksiteten til flere kartleverandører, ved hjelp av proprietære formater, kombinert med flere dataleverandører og flere versjoner av bilkart. De løser dette ved å bruke et åpent mellomformatformat uttrykt med XML og basert på konseptene i ISO-standarden GDF 4.0. Alle modifikasjoner i leverandørens database blir først konvertert til dette mellomformatet, lagret på en server og deretter konvertert til hvert format som brukes i individuelle biler. De antar at hver bil har et "baseline" kart fra en kartleverandør, og at denne baseline definerer referanseidentifikatorer (f.eks. Kortsegment-ID) for de fleste funksjoner som skal oppdateres. For funksjoner uten referanseidentifikator i grunnlinjen, foreslår de å bruke en "generisk" referanse som oppdages heuristisk ved hjelp av kartmatching som beskrevet av en foreslått standard kalt AGORA

Et stort problem som ikke direkte behandles av ActMAP er at for hver nye versjon av leverandørens kartdatabase blir alle referanse-IDer vanligvis tildelt på nytt ved en kompileringsprosess, som ødelegger korrespondanse med ID-er fra tidligere versjoner. Dette forstyrrer alvorlig muligheten til å bruke trinnvise oppdateringer for å generere en ny versjon av en kartdatabase fra en tidligere versjon. Et annet problem som ikke løses av ActMAP er manglende evne til å referere til og karakterisere underseksjoner av veisegmenter (for eksempel kurver, bakker, manøvreringsfelt osv.) For å oppdatere dem.

Se også

• Automotive navigasjonssystem
• Korteste sti-problem , klasse av problemer og algoritmer som brukes for å oppnå en navigasjonsrute fra en kartdatabase.
• Geografisk database
• Geografisk informasjonssystem
• Global Navigation Satellite System
• Intelligent transportsystem
• Kart
• Navteq
• Interessepunkt
• Objektrelasjonell database
• Åpne Geospatial Consortium
• Robotkartlegging
• Tele Atlas
• Telematikk

Referanser