SE522437C2 - Förfarande och anordning för extraktion av information från ett målområde inom ett tvådimensionellt grafiskt objekt i en bild - Google Patents

Description

l5 20 25 30 522 437 2 Den höga upplösningen hos dessa sensorer gör det möjligt att ta bilder av objekt med tillräckligt hög noggrannhet för att kunna behandla bilderna med tillfredsställande resultat.

En bild som tagits från en handhållen anordning ger emellertid upphov till rotations- och perspektiveffekter.

För att således extrahera och tolka den önskade informa- tionen inom bilden, behövs en projicerande transforma- tion. En sådan projicerande transformation kräver åtmins- tone fyra olika punktöverensstämmelser där inga tre punkter ligger på samma linje.

Sammanfattning av uppfinningen I ljuset av ovanstående, är ett ändamål med uppfin- ningen att underlätta detektion av ett känt tvàdimensio- nellt objekt i en bild för att möjliggöra extraktion av önskad information som är lagrad i ett målområde inom objektet, även om bilden registrerats i en oförutsägbar miljö, och således vid okänd vinkel, rotation och ljus- förhållanden.

Ett annat ändamål år att åstadkomma ett universellt detektionsförfarande, vilket, med ett minimum av juste- ringar, är anpassningsbart till en mängd kända objekt. Ännu ett ändamål är att åstadkomma ett detektions- förfarande, vilket är effektivt i termer av beräknings- kraft och minnesanvändning, och vilket således är sär- skilt lämpat för handhållna bildregistreringsanordningar.

De ovannämnda ändamålen uppnås i allmänhet genom ett förfarande och en anordning enligt de bifogade självstän- diga patentkraven.

Enligt uppfinningen åstadkoms således ett förfarande för extraktion av information från ett målområde inom ett tvàdimensionellt grafiskt objekt som har ett flertal för- 10 l5 20 25 30 Lfl PJ DJ $> QR] *J 3 utbestämda särdrag med, i ett första plan, känd karakte- ristik. Förfarandet innefattar stegen: att läsa en bild i vilken nämnda objekt är placerat i ett andra plan, varvid nämnda andra plan är på förhand okänt, att i nämnda bild identifiera ett flertal kandidater till nämnda förutbestämda särdrag i nämnda andra plan, att från nämnda identifierade flertal särdrags- kandidater, beräkna en transformationsmatris för projice- rande avbildning mellan nämnda andra och första plan, att transformera nämnda målområde på nämnda objekt från nämnda andra plan till nämnda första plan, och att behandla nämnda målområde för att extrahera nämnda information.

Anordningen enligt uppfinningen är med fördel en handhållen anordning som används för detektion och tolk- ning av ett känt tvàdimensionellt objekt i form av en skylt i en enda bild, vilken registreras vid okänd vin- kel, rotation och ljusförhållanden. För att lokalisera den kända skylten i en sådan bild identifieras specifika särdrag hos skylten. Särdragsidentifikationen baseras företrädesvis på skyltens kanter. Detta möjliggör en lös- ning som är anpassningsbar till de flesta redan existe- rande skyltar, eftersom särdragen är sä generella som möjligt och gemensamma för de flesta skyltar. För att hitta linjer som är baserade på skyltens kanter, används företrädesvis en kantdetektor baserad på den Gaussiska kärnan. När alla kantpunkter identifierats, grupperas de till linjer. Den Gaussiska kärnan används med fördel också för att lokalisera kantpunkternas gradient. Hörn- punkterna på insidan av kanterna används sedan som sär- dragspunktkandidater. Dessa hörnpunkter erhålls då de linjer som löper längs kanterna skär varandra. 10 15 20 25 30 LW BJ NJ $> OJ *J 4 I en alternativ utföringsform kan, om det finns andra mycket framträdande särdrag på skylten (exempelvis punkter med en specifik gråskala, färg, intensitet eller luminescens), dessa användas istället för eller utöver kanterna, eftersom sàdana framträdande särdrag är enklare att detektera.

Så snart en specifik mängd särdragskandidater har identifierats, exekveras en algoritm baserad på den algo- ritm som är allmänt känd som RANSAC, för att verifiera att särdragen har rätt uppställning och för att beräkna en transformationsmatris. Efter att ha säkerställt att särdragen befinner sig i den korrekta geometriska upp- ställningen, kan något målområde hos objektet transfor- meras, extraheras och tolkas med exempelvis en tolk för OCR eller streckkoder.

Andra ändamål, kännetecken och fördelar med före- liggande uppfinning kommer att framgå av den följande detaljerade beskrivningen, av de bifogade osjälvständiga kraven, såväl som av ritningarna.

Kort beskrivning av ritningarna En föredragen utföringsform av föreliggande uppfin- ning kommer nu att beskrivas närmare, under hänvisning till de bifogade ritningarna.

Fig l är en schematisk vy av en bildregistrerings- anordning enligt uppfinningen, i form av en handhållen anordning.

Fig la visar såväl bildregistreringsanordningen i fig l som en datormiljö, i vilken anordningen kan an- vändas.

Fig 2 är ett blockschema, som illustrerar viktiga delar hos den i fig 1 visade bildregistreringsanord- ningen. <2 ii." : r '~. 10 15 20 25 30 522 437 5 Fig 3 är ett flödesschema som illustrerar de över- gripande steg som utförs genom förfarandet enligt upp- finningen.

Fig 4 är ett flödesschema som i närmare detalj illu- strerar ett av stegen i fig 3.

Fig 5 är ett diagram för illustration av en mask för utjämning och härledning, vilken anbringas pà en regi- strerad bild under ett steg i det i fig 3 och 4 illustre- rade förfarandet.

Fig 6-17 är foton som illustrerar behandling av en registrerad bild under olika steg av det i fig 3 och 4 illustrerade förfarandet.

Detaljerad beskrivning av en föredragen utföringsform Ãterstoden av denna specifikation har följande upp- lägg: I sektion A ges en allmän översikt av förfarandet och anordningen enligt den föredragna utföringsformen.

För att bättre förstå det material som täcks av denna specifikation, ges en introduktion till projiceran- de geometri i termer av homogen notation och beskrivs en kameraprojektionsmatris i sektion B.

Sektion C ger en förklaring av hur transformations- matrisen eller homografimatrisen kan erhållas när över- ensstämmelser i särdragspunkter har identifierats.

En förklaring av vilken sorts särdrag som bör väl- jas, och varför, àterfinns i sektion D.

Sektion E beskriver en linjedetektionsalgoritm.

Sektion F ger en beskrivning av den typ av informa- tion som kan erhållas fràn linjer.

Så snart särdragspunkterna har identifierats kan homografimatrisen beräknas, vilket görs med hjälp av en RANSAC-algoritm, såsom förklaras i sektion G. 5 lO 15 20 25 30 522 437 6 Sektion H beskriver hur den önskade informationen kan extraheras från målområdet.

Slutligen berör sektion I nägra alternativa utfö- ringsformer.

A. Allmän översikt En föredragen utföringsform kommer nu att beskrivas, där det objekt som skall kännas igen och läsas från är en skylt 100, som visas vid botten av fig 1. Det skall emel- lertid betonas att uppfinningen inte är begränsad till endast skyltar. Skylten 100 är avsedd att se ut som vil- ken skylt som helst. Màlomràdet 101, fràn vilket informa- tionen skall extraheras och tolkas, är området med siff- rorna "12345678", och indikeras i fig 1 av en streckad ram. Sàsom inses, innehåller inte skylten 100 särskilt mycket information som kan användas som särdrag.

Som med mànga andra skyltar, omges skylten 100 av en ram. Kanterna på denna ram ger upphov till linjer. Den föredragna utföringsformen baseras pà att dessa linjer används som särdrag. Emellertid kan vilken typ av särdrag som helst användas så länge som åtminstone totalt fyra särdragspunkter kan urskiljas. Om skylten innehåller nägra specifika särdrag (exempelvis punkter med en speci- fik färg), kan dessa användas istället för, eller utöver, ramen, eftersom de vanligtvis är enklare att detektera.

Fig 1 illustrerar en bildalstrande handhållen an- ordning 300, vilken implementerar anordningen enligt den föredragna utföringsformen, och med hjälp av vilken för- farandet enligt den föredragna utföringsformen kan ut- föras. Den handhàllna anordningen 300 har ett hölje 1 med ungefär samma form som en konventionell överstryknings- penna. En kortsida av höljet har ett fönster 2, genom vilket bilder registreras för olika bildbaserade funk- tioner hos den handhàllna anordningen. 10 15 20 25 30 522 457 7 I huvudsak innehåller höljet 1 en optikdel, en elektronikdel och en strömförsörjning.

Optikdelen innefattar ett antal ljuskällor 6, såsom lysdioder, ett linssystem 7 och en optisk bildsensor 8, vilken utgör gränssnitt med elektronikdelen. Lysdioderna 6 är avsedda att belysa en yta pà objektet (skylten) 100, vilken vid varje ögonblick ligger inom synhåll för fönst- ret 2. Linssystemet 7 är avsett att, så korrekt som möj- ligt, projicera en bild av ytan pà den ljuskänsliga sen- sorn 8. Den optiska sensorn 8 kan bestà av en areasensor, sàsom en CMOS-sensor eller en CCD-sensor med en inbyggd A/D-omvandlare. Sådana sensorer är kommersiellt till- gängliga. Den optiska sensorn 8 kan åstadkomma VGA-bilder ("Video Graphics Array") med en upplösning pà 640x480 och 24 bitars färgdjup. Sàledes bildar optikdelen en digital kamera.

I detta exempel är den handhàllna anordningens 300 strömförsörjning ett batteri 12, men alternativt kan den vara en nätanslutning (visas ej).

Som visas närmare i fig 2, innefattar elektronikde- len en behandlingsanordning 20 med lagringsorgan 21. Be- handlingsanordningen 20 kan implementeras genom en kom- mersiellt tillgänglig mikroprocessor, såsom en CPU ("Central Processing Unit") eller en DSP ("Digital Signal Processor"). Alternativt kan behandlingsanordningen 20 implementeras som en ASIC ("Application-Specific Inte- grated Circuit"), som diskreta analoga och digitala kom- ponenter, eller någon kombination därav.

Lagringsorganet 21 innefattar olika typer av minne, (RAM) cierade program 22 för att utföra förfarandet enligt den sàsom ett arbetsminne och ett läsminne (ROM). Asso- föredragna utföringsformen lagras i lagringsorganet 21.

Dessutom innefattar lagringsorganet 21 en uppsättning 10 15 20 25 30 LH RJ BJ J> LN \J 8 objektsärdragsdefinitioner 23 och en uppsättning inre kameraparametrar 24, vars syfte kommer att beskrivas närmare längre fram. Registrerade bilder lagras i ett omrâde 25 i lagringsorganet 21.

Som visas i fig la kan den handhàllna anordningen 300 vara ansluten till en dator 200 via en överförings- länk 301. Datorn 200 kan vara en vanlig persondator med kretsar och program, vilka möjliggör kommunikation med den handhàllna anordningen 300 genom ett kommunikations- gränssnitt 210. I detta syfte kan elektronikdelen också innefatta en sändtagare 26 för överföring av information till/fràn datorn 200. Sändtagaren 26 är företrädesvis anpassad för korthàllsradiokommunikation i enlighet med exempelvis Bluetooth-standarden pá 2,4 GHz-ISM-bandet ("Industrial, Scientific and Medical"). Sändtagaren kan emellertid, alternativt, vara anpassad för infraröd kommunikation (såsom IrDA - "Infrared Data Association", som indikeras av streckade linjer vid 26') eller trad- baserad seriell kommunikation (såsom RS232, vilken indi- keras av streckade linjer vid 26"), eller i stort sett vilken som helst tillgänglig standard för korthàllskom- munikation mellan en handhållen anordning och en dator.

Elektronikdelen innefattar vidare knappar 27, med hjälp av vilka användaren kan styra den handhàllna anord- ningen 300 och specifikt skifta mellan dess olika funk- tionalitetsmoder.

Valbart kan den handhàllna anordningen 300 innefatta en bildskärm 28, såsom en flytande-kristall-bildskärm (LCD).

I samband med föreliggande uppfinning är, såsom visas i fig 3, den handhàllna anordningens 300 allmänt viktiga funktion, att identifiera ett känt tvàdimensio- nellt objekt 100 i en bild, vilken registreras av den 10 15 20 25 30 9 handhàllna anordningen 300 vid en okänd vinkel, rotation och belysning (steg 31-33 i fig 3). Så snart det två- dimensionella objektet har identifierats i den regist- rerade bilden, bestäms en transformationsmatris (steg 34 i fig 3) i syfte att genom projektion transformera (steg 35 i fig 3) målområdet 101 inom den registrerade bilden av det tvådimensionella objektet 100 till ett plan som är lämpligt för vidare behandling av informationen inom mål- området.

Màlomràdet 101 kan helt enkelt transformeras till ett förutbestämt första plan, vilket kan vara normal- planet hos den handhàllna anordningens 300 optiska in- axel, så att det verkar som att bilden registrerades rakt framför den handhàllna anordningens 300 fönster 2, sna- rare än vid en okänd vinkel och rotation.

Det första planet innefattar ett antal särdrag, vilka kan användas för transformationen. Dessa särdrag kan erhållas direkt från det fysiska objektet 100, för att avbildas genom direkta mätningar vid själva objektet.

Ett annat sätt att erhålla sådan information är att ta en bild av objektet och att mäta själva bilden.

Slutligen behandlas det transformerade målområdet genom exempelvis optisk teckenigenkänning (OCR) eller streckkodstolkning, för att extrahera den eftersökta informationen (steg 36 och 37 i fig 3). I detta syfte innehåller den föredragna utföringsformen åtminstone en av en OCR-modul 29 och en streckkodsmodul 29'. Med fördel kan sådana moduler 29 eller 29' implementeras som pro- gramkod 22, vilken lagras i lagringsorganet 21 samt exe- kveras av behandlingsanordningen 20.

Den extraherade informationen kan användas på många olika sätt, antingen internt i den handhàllna anordningen 10 15 20 25 30 522 437 10 300, eller externt i datorn 200, efter att ha överförts över överföringslänken 301.

Icke begränsande exempel på användningsfall inne- fattar en nattvakt som kontrollerar var och när under hans nattskift som han befann sig vid olika platser, genom infàngst av bilder av i allmänhet identiska skyltar 100 som innehåller olika information, när han går runt det skyddade området, ett affärsbiträde som använder den handhàllna anordningen 300 i inventeringssyften, spàrning av gods i industriomràden, eller för registrering av registreringsnummer för bilar och andra fordon.

Den handhållna anordningen 300 kan med fördel åstad- komma andra bildbaserade tjänster, såsom skannerfunktio- nalitet och musfunktionalitet.

Skannerfunktionaliteten används för registrering av text. Användaren för inenheten 300 över den text som han vill registrera. Den optiska sensorn 8 registrerar bilder med partiellt överlappande innehåll. Bilderna sätts samman av behandlingsanordningen 20. Varje tecken i den sammansatta bilden lokaliseras och med hjälp av exempel- vis mjukvaran för neurala nätverk i behandlingsanord- ningen 20 bestäms dess motsvarande ASCII-tecken. Den text som på detta sätt konverteras till teckenkodat format kan lagras, i form av en textsträng, i den handhållna anord- ningen 300 eller överföras över länken 301 till datorn 200. Skannerfunktionaliteten beskrivs närmare i sökandens publikation nr WO98/20446, vilken häri införlivas genom denna hänvisning.

Musfunktionaliteten kan användas för att styra en markör på datorns 200 bildskärm 201. När den handhållna anordningen 300 förflyttas över en yttre basyta, regist- rerar den optiska sensorn 8 ett flertal partiellt över- lappande bilder. Behandlingsanordningen 20 bestämmer 10 15 20 25 30 522 437 ll positionssignaler för datorns 200 markör baserat på de registrerade bildernas relativa positioner, vilka bestäms med hjälp av bildernas innehåll. Musfunktionaliteten beskrivs närmare i sökandens publikation nr WO99/60469, vilken härmed införlivas genom denna hänvisning.

Ytterligare bildbaserade tjänster kan åstadkommas av den handhàllna anordningen 300, exempelvis traditionell bild- eller videokamerafunktionalitet, ritverktyg, över- sättning av skannad text, adressbok, kalender eller e~post/fax/SMS ("Short Messages Services") via en mobil- telefon, såsom en GSM-telefon ("Global System for Mobile Communications", vilket inte visas i fig 1).

B. Projicerande geometri Detta kapitel introducerar de huvudsakliga geomet- riska idéer och beteckningar som är nödvändiga för för- ståelse av det material som täcks i återstoden av denna specifikation.

Introduktion Vid euklidisk geometri, kan koordinatparet (LJO i den euklidiska rymden R2 representera en punkt i real- planet. Det är således vanligt att identifiera ett plan med R2. Om man betraktar R2 som en vektorrymd, kan koordinater identifieras som vektorer. Denna sektion kommer att introducera homogen representation för punkter och linjer i ett plan. Den homogena representationen åstadkommer en konsekvent beteckning för projicerande avbildningar av punkter och linjer. Denna beteckning kommer att användas för att förklara avbildningar mellan olika representationer av plan.

Homogena koordinater En linje i ett plan representeras av ekvationen ax+by+c==0, där olika val på a, b och c ger upphov till olika linjer. Vektorrepresentationen av denna linje är "' íf-šš lâcïi (j: åífšš lšíllíišffië -Éší-i. ÉWI íïx-'íß 10 15 20 25 12 l=(mb4flT. Å andra sidan representerar även ekvationen (hÛx+(MÛy+kc=O samma linje för en konstant k, skild från noll. Således är överensstämmelsen mellan linjer och vektorer inte identisk, eftersom tvà vektorer som är relaterade genom en övergripande skalning anses vara lika. En ekvivalensklass med vektorer under detta ekviva- lensförhállande är känd som homogena vektorer. Uppsätt- ningen ekvivalensklasser för vektorer i R3 -{0ßÅDT bildar den projicerande rymden P2. Beteckningen -(OQJDT betyder att vektorn (OQÅDT är utesluten.

En punkt som representeras av vektorn x=(x¿0T ligger pà linjen l=(mb¿jT om och endast om ax+by+c==0. Denna ekvation kan skrivas som en skalärprodukt av tvá vekto- rer, (x¿@UQLhcf~=0. Här är punkten representerad som en tre-vektor (LyJ), genom addition av en sista koordinat pà l till 2-vektorn. Med användning av samma terminologi som ovan, noterar vi att (knk%kjQLhcf'=0, vilket betyder att vektorn kQLyJ) representerar samma punkt som Qnyl) för alla konstanter k som är skilda från noll. Således kan vektoruppsättningen kU¿%DT betraktas som den homogena representationen av punkten (x¿ÛT i R2. En godtycklig homogen vektor som representerar en punkt har formen T x=(x1,x2,x3) . xl xz T ' 2 Denna vektor representerar punkten ( x, x) 1 R , 3 3 om x3#O.

En punkt som representeras som en homogen vektor är således också en del av den projicerande rymden P2. Ett specialfall av en punkt x=(xUxpxQT i P2 är när x3=O.

Detta representerar inte en finit punkt R2. I P2 är dessa (F. C931 t flm: lO 15 20 25 522 457 13 punkter kända som idealpunkter, eller oändlighetspunkter.

Uppsättningen av samtliga idealpunkter representeras av x=(xvxP0fÄ Denna uppsättning ligger pá en enda linje som är känd som oändlighetslinjen och betecknas av vektorn La=(QOJY . Genom beräkningar kan man verifiera att ljx = (o,o,1)(x1,x2 ,o)f = o .

Homografier eller projicerade avbildningar När punkter avbildas frán ett plan till ett annat är det slutgiltiga målet att hitta en enda funktion som avbildar varje punkt från det första planet unikt till en punkt i det andra planet.

En projektivitet är en inverterbar avbildning h fràn P2 -+ P2 sàdan att xl, xz och x3 ligger pà samma linje om och endast om hßq), hßq) och hßg) gör det (se Hartley, R. och Zissermann, A., "Multiple View Geometry in computer vision", Cambridge University Press, 2000). En projekti- vitet kallas också för en kolineärisering, en projektiv transformering eller en homografi.

Denna avbildning kan också skrivas som Mk)=Lfig där x, MX) e P2 och H'är en icke-singulär 3x3-matris. H kallas en homografimatris. Från och med nu kommer vi att beteckna x'=h(x), vilket ger: eller enbart x'=Hx. 10 15 20 25 522 437 14 Eftersom både x' och x är homogena representationer av punkter, kan H förändras genom multiplicering av en godtycklig konstant skild fràn noll utan att homografi- transformationen ändras. Detta betyder att H endast be- stäms upp till en skala. En matris som denna kallas en homogen matris. Följaktligen har H endast åtta frihets- grader, och skalan kan väljas så att en av dess bestånds- delar (exempelvis hg) kan antas vara 1. Om emellertid koordinatsystemets origo av H avbildas till en punkt vid oändligheten, kan det bevisas att h9=0 och skalning av H sä att h9=0 kan därför leda till instabila resultat. Ett annat sätt att välja en representation för en homografi- matris är att kräva att beloppet ßfl=1.

Kameraprojektionsmatris En kamera är en avbildning fràn den tredimensionella världen till den tvàdimensionella bilden. Denna avbild- ning kan beskrivas som: x P11 P12 P13 P14 y = P21 P22 P23 P24 Z P31 P32 Paz P34 ~N'~<:>< eller kortare, x==PX. X är den homogena representationen av punkten i den tredimensionella koordinatramen. x är motsvarande homogena representation av punkten i den två- dimensionella koordinatramen. P är den homogena 3x4 kame- raprojektionsmatrisen. För en fullständig härledning av P (se Hartley, R., and Zissermann, A., "Multiple View Geo- 10 20 25 522 457 15 metry in computer vision", Cambridge University Press, 2000, sid 139-144), där kameraprojektionsmatrisen för den grundläggande hàlkameran härleds. P kan faktoriseras som: P=1 I detta fall är K den 3x3-kalibreringsmatris, som innehåller kamerans inre parametrar. R är en 3x3-rota- tionsmatris och t är 3xl translateringsvektorn. Denna faktorisering kommer att användas nedan.

Pà plan Antag att vi endast är intresserade av att avbilda punkter fràn den världskoordinatram som ligger i samma plan n. Eftersom vi är fria att välja vàr världskoordi- natram som vi önskar, kan vi exempelvis definiera n:Z==O.

Detta reducerar ekvationen ovan. Om vi betecknar kolum- nerna i kameraprojektionsmatrisen med p,, får vi: x y :bl P2 P3 P4 1 .X :bn P2 Pa Y' 1 Avbildningen mellan punkterna x”=(ÅQYJ)T pà n, och deras motsvarande punkter pà bilden x', är en vanlig plan homografi x'=Hx,,, där H=[p1 pz p,].

Ytterligare begränsningar Om vi har en kalibrerad kamera, kommer kalibrerings- matrisen K att vara känd och vi kan erhålla ytterligare information. Eftersom P=1 \ 1131:; 20:12 üjä ífäië-§.f;f';«<: 10 15 20 25 30 522 437 16 och kalibreringsmatrisen K är icke inverterbar, kan vi erhålla: K_1P=R[I i "t]=K_liP1 P2 p: P4i=K_l[h1 hz P3 hai- De två första kolumnerna i rotationsmatrisen R är ekvivalenta med de tvà första kolumnerna hos K"Uï. Om man betecknar dessa tvà kolumner med r, och rz, får vi: [fl rzi=K4|ïhl hzi' Eftersom rotationsmatrisen är ortogonal, bör Q och 13 vara ortogonala och av samma längd. Som vi emellertid har nämnt förut, är H endast bestämd upp till skala, vilket betyder att Q och Q inte kommer att vara norma- liserade, utan att de fortfarande skall vara av samma längd.

Slutsats: Med en kalibrerad kamera erhàller vi tvà ytterligare begränsningar pà H: där [fl rzizK-lihx hz] ~ C. Lösning för homografimatrisen H Det första som skall beaktas när man löser ekvatio- nen för homografimatrisen H, är hur många motsvarande punkter x' éè x som behövs. Som nämndes i sektion B, har H àtta frihetsgrader. Eftersom vi arbetar i 2D har varje punkt begränsningar i två riktningar, och således har varje punktöverensstämmelse tvà frihetsgrader. Detta betyder att en nedre gräns av fyra överensstämmande punkter i de två olika koordinatramarna behövs för att ~ » 5:22: far? -§=:=»;~ "*;';=f;':r 522 437 17 beräkna homografimatrisen H. Denna sektion kommer att visa olika sätt att lösa ekvationen för H.

Algoritmen för direkt linjär transformering (DLT) För varje punktöverensstämmelse har vi ekvationen 5 x'i=Hx,. . Notera att eftersom vi arbetar med homogena vektorer kan x',. och Hxi skilja sig upp till skala.

Ekvationen kan också uttryckas som en vektorkryssprodukt x',.> skalfaktorn kommer att avlägsnas. Om vi betecknar den 10 jzte raden i H med hfT, så kan Hxl. uttryckas som: h1Tx.

I Hx- = hzïx.

I I h3TX.

I Om man använder samma terminologi som i sektion B, kan kryssprodukten ovan uttryckas som: 3T 2T y: h Xi _W'i h Xi x',.xHx,. = w',.h1Tx,. -xßhaïxi = 0 . 2T lr x'ih Xí-yßh X,- 15 Eftersom hfTxi=xirhj för j=1..3, kan vi arrangera om ekvationen och erhålla: OT - w',. xf y', xf h* x',.> - ' xT x'.x.T OT h3 I l I I Vi stàr nu inför tre linjära ekvationer med åtta obekanta element (de nio elementen i H minus ett pà grund få? Lffnåé ïf}:".âï_=_1i ÉPÉ iä'-C-'f:ï';Ii§Äfi.?2 íšïšíïnšwšrfi-'JZ 10 15 20 25 522 437 18 av skalfaktorn). Eftersom emellertid den tredje raden är linjärt beroende av de övriga två raderna, tillhandahål- ler endast tvà av ekvationerna användbar information.

Därför ger varje punktöverensstämmelse oss två ekvatio- ner. Om vi använder fyra punktöverensstämmelser kommer vi att få àtta ekvationer med àtta okända element. Detta system kan nu lösas med hjälp av gaussisk eliminering.

Ett annat sätt att lösa systemet kan vara med hjälp av SVD, sàsom beskrivs nedan.

Singulärvärdesfaktorisering (SVD) I det verkliga livet fär vi vanligtvis inte punk- ternas positioner att vara exakta, pà grund av brus i bilden. Lösningen till H kommer således att vara inexakt.

För att få ett H som är mer noggrant, kan vi använda fler än fyra punktöverensstämmelser och sedan lösa ett över- bestämt system. Om à andra sidan punkterna är exakta, kommer systemet att ge upphov till ekvationer som är linjärt beroende av varandra, varvid vi återigen kommer att ha àtta ekvationer som är linjärt oberoende.

Om vi har n tal för punktöverensstämmelse, kan vi beteckna ekvationsuppsättningen med Ah==0, där A är 2nx9 matris, och Ett sätt att lösa detta system är genom minimering av den euklidiska normalen "Ah" istället, under begräns- ningen "ML=k, där k är en konstant skild från noll. Denna sista begränsning är pà grund av att H är homogen. Mini- 10 15 20 25 30 522 457 19 mering av normalen "Ah" är samma som optimering av pro- blemet: nfinAh.

Hflfl En lösning pà detta problem kan erhållas genom SVD.

En detaljerad beskrivning av SVD ges i Golub, G. H., och Van Loan, C. F., "Matrix Computations", 3:e upplagan, The John Hopkins University Press, Baltimore, MD, 1996.

Med hjälp av SVD kan matrisen A faktoriseras till: A==USVT, där den sista kolumnen med V ger lösningen pà h.

Restriktioner pà de överensstämmande punkterna Om tre punkter, av de fyra punktöverensstämmelserna, är kolinjära, kommer de att ge upphov till ett under- bestämt system (se Hartley, R., och Zissermann, A., "Multiple View Geometry in computer vision", Cambridge University Press, 2000, sid 74), och lösningen från SVD kommer att degenerera. Vi kommer därmed att vara begrän- sade när vi väljer vara särdragspunkter, sà att vi inte väljer kolinjära punkter.

D. Särdragsrestriktioner En viktig fråga är hur man ska hitta särdrag i objekt. Eftersom resultaten företrädesvis antas vara applicerbara pà redan existerande skyltar, är det önsk- värt att hitta särdrag vilka ofta används och som är enkla att detektera på en bild. Ett bra särdrag skall uppfylla sà många som möjligt av följande kriterier.

Vara enkelt att detektera; Vara enkelt att särskilja; Vara placerat i en användbar uppställning.

I denna sektion hittas nàgra olika typer av särdrag som kan användas för beräkning av homografimatrisen H. 10 15 20 25 30 522 437 20 Särdragen skall på något vis vara associerade med punk- ter, eftersom punktöverensstämmelserna används för att beräkna H1 Program för att finna särdrag, där användaren bara kan ändra några få konstanter, implementeras enligt föreliggande uppfinning och lagras i området 23 för defi- nition av objektssärdrag i lagringsorganet 21, för att anpassa särdragssökaren för specifika objekt.

Ett mycket vanligt särdrag i de flesta skyltar är olika kombinationer av linjer. De flesta skyltar omges av en kant, vilken ger upphov till en linje. Många skyltar har också ramar kring dem, vilket ger upphov till dubbla linjer som är parallella. Oavsett vilken typ av särdrag som hittas, är det viktigt att samla så mycket informa- tion som möjligt från varje enskilt särdrag. Eftersom linjer är ofta använda särdrag, kommer en beskrivning av hur olika typer av linjer kan hittas att ges i sektion E.

Antal särdrag Eftersom bilderna år av 2D-plan och har fångats av en handhållen kamera 300, är scen- och bildplanen rela- terade genom en planprojektiv transformation. I sektion C kom vi fram till att åtminstone fyra punktöverensstäm- melser behövs för beräkning av H. Om fyra punkter i scenplanet och de fyra motsvarande punkterna på bilden hittas, så kan H beräknas. Problemet är att vi inte vet om vi har de korrekta motsvarande punkterna. Därför måste en verifieringsprocedur för att kontrollera huruvida H är korrekt utföras. För att göra detta kan H verifieras med ännu fler punktöverensstämmelser. Om kameran är kalibre- rad, kan en verifiering av H med kamerans inre parametrar såsom förklaras vid slutet av sektion B. 24 utföras, Restriktioner på linjer I 2D har linjer tvà frihetsgrader och på samma sätt som med punkter kan fyra linjer - där inga tre linjer 10 15 20 25 30 5222 437 21 sammanfaller - användas för beräkning av homografimatri- sen. Emellertid màste beräkningen modifieras litet, eftersom linjer transformeras som P=I¥4l, till skillnad mot punkter som transformeras som x%=Hk, för samma homo- grafimatris H (se Hartley, R., och Zissermann, A., "Multiple View Geometry in computer vision", Cambridge University Press, 2000, sid 15).

Det är till och med möjligt att blanda särdrags- punkter och -linjer när man beräknar homografimatrisen.

Det finns emellertid ytterligare nägra begränsningar när man gör detta, eftersom punkter och linjer är beroende av varandra. Såsom bevisats i sektion C, har fyra punkter, och pà samma sätt fyra linjer, åtta frihetsgrader. Tre linjer och en punkt är geometriskt ekvivalent med fyra punkter, eftersom tre icke sammanfallande linjer definie- rar en triangel, och triangelns hörnpunkter unikt defi- nierar tre punkter. Pà samma sätt är tre icke kolinjära punkter och en linje ekvivalent med fyra linjer, vilka har åtta frihetsgrader. Två punkter och tvà linjer kan emellertid inte användas för beräkning av homografimatri- sen. Anledningen är att totalt fem linjer och fem punkter kan bestämmas unikt utifràn tvà punkter och tvá linjer.

Problemet är emellertid att fyra av fem linjer är sam- manfallande och att fyra av de fem punkterna är kolin- jära. Dessa två system degenererar sàledes och kan inte användas för beräkning av homografimatrisen.

Välj hörnpunkter I den föredragna utföringsformen används inte lin- jernas ekvation i samband med beräkning av homografi- matrisen. Istället beräknas linjernas skärningspunkter, och sàledes används endast dessa punkter i beräkningarna.

En av anledningarna att göra detta är pà grund av propor- tionerna mellan koordinaterna (a, b och c) hos linjerna. lO 15 20 25 30 5212 437 22 I en bild med VGA-upplösning, kommer värdena pà en norma- liserad linjes koordinater att vara 0ShL b|s1, mån o s |c{ s «/64o2 + 4802 = soo _ Detta betyder att c-koordinaten inte står i propor- tion till a- och b-koordinaterna. Effekten av detta blir att en liten variation hos linjens gradient (dvs a- och b-koordinaterna) kan resultera i en stor variation av komponenten c. Detta gör det svàrt att verifiera linje- överensstämmelser.

Problemet med dessa proportionerliga koordinater försvinner inte när linjernas skärningspunkter används istället för linjernas parameter, det flyttas bara. Detta är bara ett sätt att normalisera parametrar, sä att de enkelt kan jämföras med varandra vid verifieringsproce- duren.

E. Linjedetektion Med hänvisning till fig 4 och 5 kommer nu detaljer om hur man bestämmer kandidater till särdragspunkter (dvs steg 33 i fig 3). Steg 41 och 42 i fig 4 beskrivs i denna sektion, medan steg 43 kommer att beskrivas i nästa sektion.

Kanter definieras som punkter där bildens gradienter är stora i termer av gràskala, färg, intensitet eller luminescens. Sá snart alla kantpunkter i en bild har er- hållits, kan de analyseras för att avgöra hur många av dem som ligger pä en rak linje. Dessa punkter kan sedan användas som grund för en linje.

Extraktion av kantpunkter Det finns flera olika sätt att extrahera punkter fràn bilden. De flesta baseras pä tröskling, omràdestill- 10 15 20 25 522 437 23 växt, omràdesuppdelning och sammanslagning ("region growing, region splitting and merging") (se Gonzalez, R.

C., och Woods, R. E., “Digital Image Processing", Addison Wesley, Reading, MA, 1993, sid 414). I praktiken är det vanligt att köra en mask genom bilden. Definitionen av en kant är skärningspunkten mellan tvà olika homogena regio- ner. Således är maskerna vanligtvis baserade på beräkning av en lokal derivata. Digitala bilder absorberar vanligt- vis en obestämd mängd brus, som ett resultat av sampling.

Därför är en utjämningsmask också att föredra före den deriverande masken, i syfte att reducera bruset. En ut- jämningsmask, som ger mycket trevliga resultat, är den gaussiska kärnan Ga: G@(x)=---:- där G är standardavvikelsen (eller kärnans bredd) och X är avståndet från den punkt som är under utredning.

Istället för att först köra en utjämningsmask över bilden och sedan derivera den, är det fördelaktigt att bara ta bildens faltning med derivatan hos den gaussiska kärnan: íGa'(x)=__x_ 1 Öx 02 \/2n'o'2 e-xz/Zaz Fig 5 visar åGJx) för a=1.2 .

Eftersom bilder är 2D, används filtret i bàde x- och y-riktningarna. För att särskilja kantpunkterna n, väljs de filtrerade punkterna f(n), dvs resultatet av bildens faltning med derivatan av den gaussiska kärnan, där g; ,. lO 15 20 25 522 437 24 f("-1) f(fl)> f(fl+1), thres där thres är en vald tröskel.

I fig 7 är samtliga de kantpunkter som detekterats fràn en ursprungsbild 102 (fig 6) markerade med ett "+"- tecken, vilket indikeras av hänvisningsbeteckningen 103.

En gaussisk kärna med 0fl=L2 och thres=5 har använts här.

Extraktion av linjeinformation Sá snart alla punkter har erhållits, är det möjligt att hitta ekvationen för den linje som de kan utgöra en del av. Gradienten hos en punkt i bilden är en vektor som pekar i den riktning, i vilken bildintensiteten vid den aktuella punkten minskar mest. Denna vektor är i samma riktning som normalen till den möjliga linjen. Därför mäste samtliga kantpunkters gradient hittas. För att extrahera X-koefficienten hos kantpunkten, anbringas derivatan av den gaussiska kärnan i 2D, Û X 2 z 2 :G x, :__ _e-(x +y )/2o' I öx °( JO 2fla4 på bilden kring kantpunkterna. I denna mask är (my) avståndet från kantpunkten. _ _ n _ -3a Vanligtvis anvands ett omrade pà -3a där G är standardavvikelsen.

Pá samma sätt kan y-koefficienten extraheras. Sàsom nämnts ovan har linjens normal samma riktning som gra- dienten. Således har a- och b-koefficienterna för linjen erhàllits. Den sista koordinaten c kan enkelt beräknas, eftersom ax+by+c==0. Företrädesvis kommer linjens ekva- 10 15 20 25 522 457 25 tion att vara normaliserad, sà att linjens normal kommer att ha längden 1: __ (a,b,c)T JM +b2) ' Detta betyder att c-koordinaten kommer att ha samma l värde som avståndet fràn linjen till origo.

Klustring av kantpunkter till linjer För att ta reda pà om kantpunkter utgör del av en linje, mäste begränsningar pà punkterna tillämpas. Det finns tvà huvudsakliga begränsningar: - Punkterna skall ha samma gradient.

- Den föreslagna linjen skall löpa genom punkterna.

Eftersom bilden kommer att vara oskarp, behöver dessa begränsningar endast uppfyllas inom gränsen för en viss tröskel. Tröskeln kommer naturligtvis att bero pà under vilka omständigheter bilden togs, bildens upplös- ning samt objektet på bilden. Eftersom samtliga data för punkterna är kända är det enda som behöver göras att gruppera punkterna tillsammans och anpassa linjer till dem (steg 42 i fig 4). Följande algoritm används enligt den föredragna utföringsformen: För ett visst antal slingor, Steg 1: Välj slumpvist en punkt p=(x¿%DT, med linjedata l=(mb¿ÛT; Steg 2: Hitta, med hjälp av pnï-l övriga punkter pn=(rvyMDT, med linjedata ln=(aMbMcnYfl vilka ligger på samma linje; Steg 3: Se, med hjälp av (aMbn)(mbf'>(L-%nm2), om dessa punkter har samma gradient som p; 3 - 22-1; *IÉ 1 Pa-*Jçi CÉÉ 2 š5..~:=ÉÉ_“-_'¿fï I* l iii) f: i *'-'=»*"<=:zi;'=ïf.' 'F Û ITT ~ 13 -- il:- ï-íš-í _ ”fi” lO 15 20 25 30 522 437 26 Steg 4: Anpassa, med hjälp av SVD, en ny linje l=(mb¿flT utifrån alla de punkter som uppfyller villkoren i steg 2 och steg 3, pn Upprepa steg 2-3; Steg 5: Upprepa steg 2-4 tvà gånger; Steg 6: Om det finns åtminstone en viss mängd punk- ter som uppfyller dessa villkor, definiera dessa punkter till att utgöra en linje; Slut. Repetera med àterstàende punkter.

Denna algoritm väljer slumpvist en punkt. Ekvationen för den linje, som denna punkt kan utgöra en del av, är redan känd. Nu hittar algoritmen alla andra punkter som har samma gradient och ligger pà samma linje som den första punkten. Bàda dessa kontroller mäste utföras inom ett visst tröskelvärde. I steg 2 kontrollerar algoritmen om punkten ligger närmare linjen än avståndet thresl. I steg 3 kontrollerar algoritmen om de tvà punkternas gra- dienter är samma. Om de är det, skall produkten av gra- dienterna vara 1. Återigen är det, pä grund av onoggrann- het, tillräckligt om produkten är större än Üf4hnß2).

Eftersom kantpunkterna inte är exakt placerade, och eftersom gradienterna inte kommer att ha det exakta värdet, beräknas i steg 4 en ny linje. Denna linje be- räknas, med hjälp av SVD, pä följande sätt, utifrån samt- liga de punkter, som uppfyller villkoren i steg 2 och steg 3. Punkterna skall också uppfylla villkoret (x¿¿D@Lb¿ÛT=4l Således kan en nx3-matris bestående av dessa punkter sättas samman, och i likhet med sektion C optimeras med hjälp av SVD nfinAl, IMS för att erhålla bättre noggrannhet upprepas steg 2 och steg 3. För att ytterligare öka noggrannheten inträffar 10 15 20 25 30 522 437 27 ännu en rekursion. Såsom inses av fackmannen, kommer vär- dena pà tröskeltalen att behöva bestämmas beroende på en verklig tillämpning.

Fig 8 visar de linjer 104 som hittades, samt kant- punkterna 103 som användes i exemplet ovan.

Om de använda kantpunkterna utelämnas, är det enk- lare att se hur bra approximeringen av de skattade lin- jerna är, se fig 9.

F. Från linjerna utvunnen information För att beräkna homografimatrisen H behövs fyra mot- svarande punkter fràn de tvâ koordinatramarna. Eftersom mànga linjer är tillgängliga, kan ytterligare information åstadkommas.

Krysspunkter Hörn utgör vanliga särdrag pá skyltar. Det finns emellertid vanligtvis mänga hörn pà en skylt, vilka inte är intressanta, om det exempelvis finns text pà skylten, kommer bokstäverna att ge upphov till en massa hörn som är ointressanta. När nu de linjer som utgörs av kanter har erhållits, kan kanternas hörnpunkter enkelt beräknas (steg 43 i fig 4) genom att ta kryssprodukten för tvà linjer: xc=li> Vektorn XC kommer att vara den homogena represen- tanten för den punkt i vilken linjerna L och lj skär var- andra. Om den tredje koordinaten pà xc=0, så är xc oänd- lighetspunkten, och linjerna L och lj är parallella.

Dessa krysspunkter, kombinerat med informationen från linjerna, kommer att åstadkomma ännu mer informa- tion. En verifikation av huruvida linjerna verkligen har kantpunkter vid krysspunkterna, eller huruvida skärnings- punkten ligger i linjernas förlängning, kan utföras. 10 15 20 25 30 522 437 28 Denna information kan sedan jämföras med de särdrags- punkter som söks, eftersom information rörande huruvida de skall ha kantpunkter vid krysspunkterna är känd. På detta sätt kan krysspunkter som är ointressanta elimi- neras. Punkter som är ointressanta kan ha olika ursprung.

En möjlighet är att de utgör krysspunkter som skall vara där, men som i detta specifika fall inte används. En annan möjlighet är att de alstras av linjer, vilka inte skall finnas, men vilka ändå har uppstått pà grund av störande element i bilden.

I fig 10 har alla krysspunkter markerats med ett "+"-tecken, såsom syns vid 105. Ramens verkliga hörn är markerade med ett "*"-tecken, såsom syns vid 106.

Parallella linjer Ett annat vanligt särdrag på skyltar är ramar, vilka ger upphov till parallella linjer. Om endast linjer som har sitt ursprung i ramar är intressanta, kan alla linjer som inte har en parallell motsvarighet, dvs en linje med en näraliggande normal i motsatt riktning, kasseras.

Eftersom linjen är transformerad, kan parallella linjer i 3D-värden tyckas vara icke-parallella pà 2D-bildscenen.

Emellertid kommer linjer som ligger nära varandra fort- farande att vara parallella, inom en viss felmarginal.

Resultatet av en algoritm som hittar parallella linjer 107, 107' visas i fig ll.

När samtliga uppsättningar parallella linjer har hittats, är det möjligt att lista ut vilka linjer som är kandidater till att vara en linje som svarar mot en rams inre kant. Om kryssprodukterna för samtliga dessa linjer beräknas, erhålles en uppsättning punkter som är möjliga kandidater till inre hörnpunkter i en ram, såsom marke- rats med "*"-tecken vid 108 i fig 12.

ZílíIÃi» <3? -víïfš fZê .Z r ïšïšïš? 10 15 20 25 30 522 437 29 Fortlöpande kantpunkter Av en tillfällighet, är det möjligt att linjedetek- tionsalgoritmen alstrar en linje som faktiskt bestär av en massa smä kanter som ligger pä en rak linje. Exempel- vis kan kanter pà bokstäver som skrivits pä en rak linje ge upphov till en sådan linje. Om endast linjer som be- står av fortlöpande kantpunkter är intressanta, är det önskvärt att eliminera dessa andra linjer. Ett sätt att göra detta är att ta medelpunkten för samtliga kant- punkter pà linjen. Från denna punkt extrapoleras ytter- ligare nägra punkter längs linjen. Nu kontrolleras skill- naden i intensitet pà båda sidor av linjen vid de valda punkterna. Om intensitetsskillnaderna vid punkterna inte överskrider ett visst tröskelvärde, är linjen inte upp- byggd av fortlöpande kantpunkter.

Med denna algoritm kommer inte bara linjer som här- rör fràn icke fortlöpande kantpunkter att elimineras, utan algoritmen kommer också att eliminera tunna linjer pä bilden. Detta är en positiv effekt, om endast kant- linjer som härrör fràn tjocka ramar skall användas som särdrag. I fig 13 har samma algoritmer som användes tidi- gare anbringats pà bilden 102 som visas i fig 6. Den enda skillnaden i algoritmerna är att ingen kontroll har ut- förts beträffande huruvida linjerna består av fortlöpande kantpunkter längs kanter.

Fig 14 visar en förstoring av resultatet från algo- ritmen, med kontroller av fortlöpande kantpunkter an- bringat på linjen 109 vid den nedre delen av talen "12345678". Algoritmen gav ett negativt resultat, i termer av huruvida det var fortlöpande kantmönster eller inte. Fig 15 är en förstoring av samma algoritm, an- bringad pà linjen 110 vid den nedre delen av ramen. Här iii-lv íïïå íëïà iii-z 23:“=2>znt"ÅI“¿>šJäêšáš»låílíšlääíšlíïëfi-â .Sšiï -Iïš «.;“~.-=':-:=:¿:J>k<: 212352 (Lä '_35 íl<šE'*«ï.f.í;':<: lO 15 20 25 30 522 437 30 gav algoritmen ett positivt resultat, genom att kant- punkterna är fortlöpande.

G. Beräkning av homografimatrisen H Så snart särdragskandidaterna pà bilden har erhål- lits, måste de matchas mot särdrag från den ursprungliga skylten, vilka har kända koordinater. Om fyra särdrags- kandidater har hittats, kan deras koordinater matchas med motsvarande koordinater för särdragspunkter hos objektet, vilka lagrats i området 23 i lagringsorganet 21, och homografimatrisen H kan beräknas. Eftersom sannolikt fler kandidater till de intressanta särdragen än de avsedda kommer att hittas, måste en verifieringsprocedur utföras.

Denna procedur måste verifiera att de valda överensstäm- melserna för särdragspunkter har utförts med korrekt matchning. Om det således finns många kandidater för möj- liga särdragspunkter, bör homografimatrisen beräknas flera gånger och verifieras varje gång, för att kontrol- lera huruvida det är den riktiga punktöverensstämmelsen eller inte.

Med fördel optimeras denna matchningsprocedur med hjälp av Fischler och Bolles RANSAC-algoritm (se Fischler, M. A., och Bolles, R. C., "Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography", Comm.

Assoc. Comp. Mach., 24(6):38l-395, 1981).

RANSAC RANSAC (The RANdom Sample and Consensus algorithm) är en skattningsalgoritm, som har förmåga att arbeta med mycket stora uppsättningar av möjliga överensstämmelser.

Det bästa sättet att bestämma homografimatrisen H är att beräkna H för samtliga möjliga kombinationer, verifiera varje lösning och sedan använda den överensstämmelse som har det bästa verifieringsresultatet. Verifieringsproce- 10 15 20 25 30 522 437 31 durer kan, såsom beskrivs nedan, göras på olika sätt.

Eftersom beräkning av H för varje möjlig kombination är mycket tidsödande, är detta inte en särskilt bra ansats när algoritmen skall utföras i realtid. RANSAC-algoritmen är också en algoritm för hypotes och verifiering, men den arbetar på ett annat sätt. Istället för att systematiskt arbeta sig igenom de möjliga särdragspunkterna, väljer den slumpvis sina överensstämmelsepunkter och beräknar sedan homografimatrisen samt utför verifieringarna.

RANSAC skall upprepa denna procedur ett visst antal gånger och sedan bestämma sig för att använda den upp- sättning av överensstämmelser som har det bästa verifie- ringsresultatet.

Fördelarna med RANSAC-proceduren är att den är mer robust när det finns många möjliga särdragspunkter, och att den testar överensstämmelser i slumpvis ordning. Om punktöverensstämmelserna testas i systematisk ordning, och algoritmen råkar starta med en punkt som är felaktig, mäste samtliga överensstämmelser som denna punkt kan ge upphov till verifieras av algoritmen. Detta händer inte med RANSAC, eftersom en punkt endast kommer att matchas med en enda möjlig punktöverensstämmelse, och nya sär- dragspunkter därefter kommer att väljas för matchning med varandra. RANSAC~matchningsproceduren utförs endast ett specificerat antal gånger, och den bästa lösningen väljs.

Eftersom punkterna väljs slumpvis, har ibland rätt matchning, eller åtminstone en som är nära den rätta, valts, och dessa punkt överensstämmelser kan användas för beräkning av H.

Verifieringsprocedurer När homografimatrisen har beräknats, måste det veri- fieras att korrekta punktöverensstämmelser har använts.

Detta kan göras på några olika sätt. 10 15 20 25 30 522 457 32 Ett femte särdrag Det vanligaste sättet att verifiera H'är att använda ytterligare särdragspunkter. I detta fall mäste ännu fler än de fyra särdragspunkterna från de ursprungliga objek- ten vara kända. De återstående punkterna från det ur- sprungliga objektet kan transformeras till bildens ko- ordinatsystem. Därefter kan en verifieringsprocedur ut- föras, för att kontrollera huruvida punkterna har hittats på bilden. Ju fler ytterligare särdrag som hittas, desto större är sannolikheten att den korrekta uppsättningen punktöverensstämmelser har valts.

Kamerans inre parametrar Om kameran är kalibrerad, är det möjligt att veri- fiera den förmodade homografimatrisen med kamerans inre parametrar 24, vilka lagrats i lagringsorganet 21 (se diskussionen i föregående sektioner). Detta inför ytter- ligare begränsningar på de valda särdragspunkterna. Om punkterna representerar en rektangels hörn, kommer de första och andra raderna, q och rz att ge upphov till samma värde, om punkterna är korrekt matchade upp till ett rotationsfel för rektangeln på 180 grader. Detta är uppenbart eftersom om en rektangel roteras 180 grader kommer den att ge upphov till exakt samma rektangel. På samma sätt kan en kvadrat roteras 90, 180 eller 270 grader, och ändå ge upphov till exakt samma kvadrat. I alla dessa fall kommer Q och rz fortfarande att vara ortogonala. Även om denna verifieringsprocedur kan ha ett rota- tionsfel, om hörn på en rektangel används som särdrags- punkter, är den fortfarande mycket användbar, eftersom rektanglar är vanliga särdrag. Rotationsfelet kan enkelt kontrolleras senare. lf rv- . *VV 10 15 20 25 30 Verifieringsfel Beroende på hur särdragspunkterna väljs, kan det fortfarande inträffa fel när särdragspunkterna verifie- ras. Såsom nämnts ovan, är homografimatrisen en homogen matris, och endast bestämd upp till en skala. Om objektet har punkter som är vid exakt samma uppställning som sär- drags- och verifieringspunkterna, förutom att de är rote- rade och/eller upp till skala, kommer verifieringsproce- duren att ge upphov till exakt samma värden som om den korrekta punktöverensstämmelsen hade hittats. Därför är det viktigt att välja särdragspunkter som är så distinkta som möjligt.

Restriktioner pà RANSAC RANSAC är endast baserat på slumpmässighet. Om ännu mer information finns tillgänglig, bör denna uppenbar- ligen användas för att optimera RANSAC-algoritmen. Några restriktioner som kan läggas till är följande.

Stopp om lösningen hittats Istället för att upprepa beräkningarna i proceduren ett specifikt antal gånger, är det möjligt att stoppa om verifieringen indikerar att en lösning som är bra har hittats. För att bestämma om en lösning är bra eller inte kan ett villkor göras, som om åtminstone en viss mängd särdragspunkter i verifieringsproceduren har hittats, så mäste detta vara den korrekta homografimatrisen. Om kame- rans inre parametrar används som verifieringsprocedur, kan ett stopp göras om rl och r, är mycket nära att ha samma längd och vara ortogonala.

Särdragspunkter på samma linje Begränsningen att endast en sådan uppsättning sär- dragspunkter skall användas, där inga tre punkter tillåts ligga på samma linje, kan inkluderas i RANSAC-algoritmen.

Efter att fyra punkter slumpvis valts är det möjligt att 10 15 20 25 30 522 457 34 kontrollera om tre av dem ligger pà samma linje, innan man fortsätter med beräkning av homografimatrisen. Kombi- nerat med de följande tvâ restriktionerna är denna kon- troll mycket tidseffektiv.

Konvext hölje Det konvexa höljet för en godtycklig uppsättning S punkter är den minsta konvexa polygon IQ för vilken varje punkt i S ligger antingen på gränsen av P; eller i dess inre. Tvä av de vanligaste algoritmerna som används för beräkning av det konvexa höljet är Graham's avsökning och Jarvis's marsch. Båda dessa algoritmer använder en teknik som kallas "roterande svepning" (se Cormen, T. H., Leiserson, C. E., och Rivest, R. L., "Introduction to Algorithms", The Massachusetts Institute of Technology, 1990, sid 898). När man beräknar det konvexa höljet, kommer dessa algoritmer också att åstadkomma hörnens ordning, säsom de framträder pà höljet, i motsols ord- ning. Graham's avsökning arbetar i Obflgn)-tid, till skillnad från Jarvis's marsch som arbetar i 00%)-tid, där n är antalet punkter och h är antalet hörn.

Eftersom projicerande avbildningar är linjebevaran- de, mäste de också bevara det konvexa höljet. I en upp- sättning med fyra punkter, där inga tre punkter ligger pà samma linje, kommer det konvexa höljet att bestå av an- tingen tre eller fyra av punkterna. Detta betyder att i tvä uppsättningar med motsvarande punkter, kommer båda deras konvexa höljen att bestà av antingen tre eller fyra punkter. En kontroll av detta kan, efter att de tvâ upp- sättningarna pá fyra punkter har valts, inkluderas i RANSAC-algoritmen.

Qi' / ~. 10 15 20 25 30 522 457 35 Systematisk sökning Principen bakom RANSAC är att slumpvist välja fyra punkter, matcha dem med fyra förmodat överensstämmande punkter, vilka också valts slumpmässigt, samt sedan för- kasta dessa punkter och välja nya. Det är möjligt att modifiera denna algoritm och inkludera några systematiska operationer. Så snart de två uppsättningarna med fyra punkter har valts, kan samtliga möjliga kombinationer av matchning mellan dessa punkter testas. Detta betyder att det finns 4h=24 olika kombinationer att testa. Om rest- riktionerna ovan har inkluderats, kan detta antal reduce- ras kraftigt. Först kan man säkerställa att inga tre punkter av de fyra punkterna i varje uppsättning ligger på samma linje. Sedan kan man kontrollera om båda upp- sättningarna har samma mängd punkter i det konvexa höl- jet. Om så är fallet, kommer också ordningen av punkterna på höljet att erhållas, och nu kan alltså punkterna endast matchas med varandra på antingen tre eller fyra olika sätt, beroende på hur många punkter höljet består av.

Således, av 24 möjliga kombinationer, har O, 3 eller 4 förmodade punktöverensstämmelser nåtts. Naturligtvis är beräkning av det konvexa höljet och säkerställande av att inga tre punkter ligger på samma linje tidsödande, men det är obetydligt jämfört med att beräkna homografi- matrisen 24 gånger.

H. Extraktion av målområde Så snart homografimatrisen är känd, kan vilket om- råde som helst från bilden extraheras, så att det kommer att verka som om bilden var tagen från ett ställe som ligger rakt framför den. För att göra denna extraktion kommer alla punkterna inom det intressanta området att transformeras till bildplanet enligt den valda lösningen. fa:- -~ f: lå :Z-š <3 : Éšlïgåíilffiïfhš :sï-Q-Lííäké: Zíï “(29 - -å .='.“i<§<: 10 15 20 25 30 522 437 36 Eftersom bilden är en diskret koordinatram, består den av bildpunkter med heltalsvärden. De transformerade punk- terna kommer emellertid förmodligen inte att vara heltal.

Därför måste en bilinjär interpolation (se exempelvis Heckbert, P. S., "Graphics Gems IV", Academic Press, Inc., 1994) göras för att erhålla intensiteten fràn bil- den. Den transformerade bilden kan àterskapas fràn an- tingen gràskaleintensiteten, eller kan samtliga tre intensitetsnivàer erhållas fràn den ursprungliga bilden i färg.

Fig 16 visar bildens 102 i fig 6 màlomràde 101, som hittats av algoritmerna ovan.

I fig 17 har målområdet 101' transformerats så att exempelvis OCR- eller streckkodstolkning kan följa (steg 36 och 37 i fig 3). I detta exempel valdes en upplösning pà 128 bildpunkter i x-riktningen.

I. Alternativa utföringsformer Uppfinningen har beskrivits ovan under hänvisning till en föredragen utföringsform. Emellertid är andra utföringsformer än den som beskrivits ovan lika möjliga inom uppfinningens skyddsomfàng, sàsom detta definieras enligt de bifogade patentkraven. Specifikt observeras att uppfinningen kan utföras i andra portabla anordningar än den som beskrivs ovan, exempelvis mobiltelefoner, por- tabla digitala assistenter (PDA), handdatorer, kalendrar, kommunikationsanordningar, etc.

Vidare är det möjligt att, inom uppfinningens skyddsomfàng, utföra några av stegen enligt uppfinnings- förfarandet i den externa datorn 200, snarare än i den handhàllna anordningen 300. Exempelvis är det möjligt att överföra det transformerade målområdet 101 som en digital bild (JPEG, GIF, TIFF, BMP, EPS, etC) Över länken 301 till datorn 200, vilken sedan kommer att utföra själva lO 15 522 457 37 behandlingen av det transformerade málomràdet 101, för att extrahera den önskade informationen (OCR-text, streckkod, etc).

Naturligtvis kan datorn 200, pà konventionellt sätt, vara ansluten till ett lokalt nätverk, eller ett globalt nätverk, sàsom Internet, vilket gör det möjligt för den extraherade informationen att vidarebefordras till ytter- ligare applikationer utanför den handhàllna anordningen 300 och datorn 200. Alternativt kan den extraherade in- formationen kommuniceras genom en mobiltelefon, vilken är funktionellt ansluten till den handhàllna anordningen 300 genom IrDA, Bluetooth eller kabel (visas ej på ritningar- na). "“('"~í?$ï*

Claims (26)

10 15 20 25 30 522 457 38 PATENTKRAV

1. Förfarande för extraktion av information från ett màlområde (101) inom ett tvådimensionellt grafiskt objekt (100) som har ett flertal förutbestämda särdrag (23) med, i ett första plan, känd karakteristik, k ä n n e t e c k n a t av stegen: att läsa en bild (102) i vilken nämnda objekt (100) är placerat i ett andra plan, varvid nämnda andra plan är pà förhand okänt, att i nämnda bild identifiera ett flertal kandidater (108) till nämnda förutbestämda särdrag (23) i nämnda andra plan, att från nämnda identifierade flertal särdrags- kandidater, beräkna en transformationsmatris (H) för projicerande avbildning mellan nämnda andra och första plan, att transformera nämnda objekts målområde (101) från nämnda andra plan till nämnda första plan, och att behandla nämnda målområde för att extrahera nämnda information.

2. Förfarande enligt krav 1, varvid nämnda flertal förutbestämda särdrag (23) läses fràn ett minne (21) innan nämnda flertal särdragskandidater (108) identifie- ras.

3. Förfarande enligt krav 1 eller 2, varvid nämnda flertal förutbestämda särdrag (23) inkluderar åtminstone fyra särdrag.

4. Förfarande enligt krav 3, varvid nämnda åtmins- tone fyra förutbestämda särdrag är fyra punkter, fyra linjer, tre punkter och en linje, eller en punkt och tre linjer. 10 15 20 25 30 522 437 39

5. Förfarande enligt krav 3, varvid nämnda àtmins- tone fyra förutbestämda särdrag är fyra punkter, varvid nämnda flertal särdragskandidater (108) identifieras genom: att lokalisera kantpunkter (103) som punkter i nämnda bild (102), vilka har stora gradienter, att klustra nämnda kantpunkter till linjer (104), och A att bestämma nämnda flertal särdragskandidater som skärningspunkter (105, 106, 108) mellan tvà godtyckliga av nämnda linjer.

6. Förfarande enligt krav 5, varvid nämnda skär- ningspunkter (105, 106, 108) är vid fyra hörnpunkter pà en ram i nämnda tvàdimensionella grafiska objekt.

7. Förfarande enligt något av föregående krav, varvid nämnda transformationsmatris (H) beräknas genom: att bland nämnda identifierade flertal särdrags- kandidater slumpvis välja sä många särdragskandidater som i nämnda flertal särdragskandidater (23), att beräkna en hypotetisk transformationsmatris för nämnda slumpvist valda kandidater och nämnda flertal förutbestämda särdrag, att verifiera den hypotetiska transformations- matrisen, att repetera stegen ovan ett flertal gånger, och som nämnda informationsmatris (H) välja den speci- fika hypotetiska transformationsmatris med bäst resultat från verifieringssteget.

8. Förfarande enligt krav 6 eller 7, varvid den hypotetiska transformationsmatrisen verifieras med hjälp av åtminstone ett ytterligare förutbestämt särdrag.

9. Förfarande enligt något av krav 6-8, varvid nämnda flertal förutbestämda särdrag (23) innefattar íï (I: fi." '_l'flï' lll 1,2 S355 ÉÉÉÉ iè'-."-'~.'::=flí{rl¿>. Zíï' 321 (f-“š »fifšíšêß . iï 10 15 20 25 30 522 437 40 åtminstone fyra punkter och varvid nämnda steg att slump- vis välja är begränsat till en uppsättning av fyra sär- dragskandidater, vilken inte innefattar tre på en linje liggande punkter.

10. Förfarande enligt krav 9, varvid nämnda steg att slumpvis välja begränsas ytterligare genom beräkning av det komplexa höljet för nämnda särdragskandidater.

11. Förfarande enligt något av föregående krav, varvid nämnda flertal förutbestämda särdrag (23) inne- fattar åtminstone en punkt som har ett värde för grå- skala, färg, intensitet eller luminescens, vilket är tydligt skilt från omgivande punkter i nämnda tvàdimen- sionella grafiska objekt (100).

12. Förfarande enligt något av föregående krav, varvid nämnda tvàdimensionella grafiska objekt (100) är en skylt.

13. Förfarande enligt något av föregående krav, varvid nämnda behandlingssteg innefattar optisk tecken- igenkänning (OCR) av nämnda målområde (101).

14. Förfarande enligt något av föregående krav, varvid nämnda behandlingssteg innefattar streckkods- tolkning av nämnda målområde (101).

15. Förfarande enligt något av föregående krav, varvid nämnda behandlingssteg innefattar överföring av nämnda målområde (101) till en extern dator (200).

16. Förfarande enligt något av föregående krav, varvid nämnda första plan är nämnda lästa bilds (102) bildplan.

17. Förfarande enligt något av krav 1-15, varvid nämnda första plan är en tidigare läst bilds bildplan.

18. Förfarande enligt krav 1-17, varvid nämnda flertal förutbestämda särdrag (23) erhålls genom direkt mätning vid nämnda tidigare lästa bild. 10 15 20 25 30 522 4s7ö 41

19. Datorprogramprodukt, vilken är direkt laddnings- bar till ett internminne (21) i en behandlingsanordning (20), varvid datorprogramprodukten innefattar programkod (22) för att när den exekveras av nämnda behandlings- anordning utföra stegen enligt nàgot av krav 1-18.

20. Datorprogramprodukt enligt krav 19, innefattad pà ett datorläsbart medium (21).

21. Handhàllen bildalstringsanordning (300), vilken har lagringsorgan (21) och en behandlingsanordning (20), varvid lagringsorganet innehåller programkod (22) för att när den exekveras av nämnda behandlingsanordning utföra stegen enligt nàgot av krav 1-18.

22. Anordning för extraktion av information fràn ett màlomràde (101) inom ett tvàdimensionellt grafiskt objekt (100), vilket har ett flertal förutbestämda särdrag (23) med, i ett första plan, känd karakteristik, varvid anord- ningen innefattar en bildsensor (8), en behandlingsan- ordning (20) och lagringsorgan (21), k ä n n e t e c k n a d av ett första område (25) i nämnda lagringsorgan (21), varvid nämnda första område är anpassat för lagring av en bild (102) som registrerats av nämnda bildsensor (8), i vilken nämnda objekt (100) befinner sig i ett andra plan, varvid nämnda andra plan är pà förhand okänt, och ett andra område (23) i nämnda lagringsorgan (21), varvid nämnda andra omrâde är anpassat för lagring av nämnda flertal förutbestämda särdrag, varvid: nämnda behandlingsanordning (20) är anordnad att läsa nämnda bild (102) från nämnda första omràde (25), att läsa nämnda flertal förutbestämda särdrag från nämnda andra omrâde (23), att i nämnda bild identifiera ett flertal kandidater till nämnda särdrag i nämnda andra plan, att från nämnda identifierade särdragskandidater .--.f'«--v ,v ,-.,-, ~ »vy y ,_... _ f~»--'-_ - ;-¿ '-. f~«-,»~. .<'~.-^-: f. - «-;= q-x ,..., _, .,~, ._ >_,_»,1~~. f- a; .f-.fï , ,_ ._ Law-_: ~ ut! .få Izæf. 1.;- gvïu: ger: -Åchß 12min; ïcuitffifli SJ; av; :šz--vir-nflfz 2=.m-¿ 'f-J v..- aqffliwàízi. 10 15 20 522 437 42 beräkna en transformationsmatris (H) för projicerande avbildning mellan nämnda andra och första plan, att transformera nämnda màlomràde (101) i nämnda objekt fràn nämnda andra plan till nämnda första plan, och att efter transformationen extrahera nämnda information fràn nämnda màlomràde.

23. Anordning enligt krav 22, vidare innefattande en modul (29) för optisk teckenigenkänning (OCR), vilken är anpassad att extrahera nämnda information från nämnda målområde (101).

24. Anordning enligt krav 22, vidare innefattande en modul (29') för streckkodstolkning, vilken är anpassad att extrahera nämnda information från nämnda målområde (101).

25. ¿ Anordning enligt nàgot av krav 22-24 i form av en handhållen anordning (300).

26. Anordning enligt något av krav 22-24, varvid nämnda anordning innefattar en handhållen anordning (300) och en dator (200). ;-;1=^<;;;:=.-k=; :Elf íï