SE520682C2 - Rekonstruering av ett virtuellt raster - Google Patents

Description

lO l5 520 682 2 Det är således ett allmänt problem att på ett beräk- ningseffektivt och störningsokänsligt vis identifiera objekten inför avkodningen av kodningsmönstret.

Ovanstående problem och tidigare föreslagna lös- ningar kommer i det följande att belysas i anslutning till ett speciellt kodningsmönster, vilket beskrivs i detalj i ovanstående patentpublikation WO 01/26032. Kod- ningsmönstret består av ett raster och markeringar, som är belägna vid varje rasterpunkt. Markeringarna är före- trädesvis huvudsakligen runda och är förskjutna i för- hållande till rasterpunkterna i endera av fyra ortogonala riktningar. Rastret är virtuellt och är sålunda osynligt för såväl ögat som sensorer.

Ett kodningsmönster av den här typen kan exempelvis användas för att koda absoluta positioner på ett under- lag. Därmed möjliggörs digital registrering av informa- tion som skrivs och/eller ritas för hand med en digital penna på underlaget. Under pennans förflyttning registre- ras löpande bilder av kodningsmönstret lokalt vid pennans spets. En delmängd av objekten i var och en av bilderna avkodas till en position. De avkodade positionerna utgör tillsammans en digital beskrivning av pennans förflytt- ning över underlaget.

I patentpublikationen WO Ol/26034 beskrivs en itera- tiv teknik för rekonstruering av det virtuella rastret i en digital bild av ovanstående kodningsmönster. Vid varje iteration verkställs stegen att identifiera två angräns- ande objekt, att med kännedom om det ena objektets pla- cering relativt sin rasterpunkt och på basis av ett upp- mätt avstånd mellan objekten bestämma det andra objektets rasterpunkt, samt att med utgångspunkt i den sålunda bestämda rasterpunkten söka efter ett nytt objekt inom ett sökområde som definieras med kännedom om rastrets nominella huvudriktningar. När alla objekt har behandlats har man stegat sig objekt för objekt genom bilden och identifierat tillhörande rasterpunkter, och därigenom rekonstruerat det virtuella rastret. l5 520 682 3 Denna teknik är snabb men förhållandevis känslig för störningar, eftersom den är baserad på lokala beslut kring enskilda objekt och bedömning av dessas lägen rela- tivt tillhörande rasterpunkter.

En alternativ teknik beskrivs i WO Ol/75783. Här an- vänds Fourieranalys för extrahering av riktningsvektorer från en punktmängd, vilken avspeglar objektens placering i den digitala bilden. Först bestäms punktmängdens över- gripande huvudvektorer, vilka sedan används vid korrige- ring av punktmängden med avseende på vridning och skalfel i bildplanet. Därefter beräknas ytterligare huvudvektorer i olika delar av den korrigerade punktmängden, för extra- hering av mått på perspektiveffekter och fasförskjutning.

Sedan slutkorrigeras punktmängden pà basis av dessa mått, varpå det virtuella rastret ges av den resulterande punktmängdens övergripande huvudvektorer. Tekniken är förhållandevis okänslig för störningar, men kan i vissa sammanhang vara oönskat beräkningsintensiv.

Sammanfattning av uppfinningen Föreliggande uppfinning har således som ändamål att anvisa en teknik som övervinner ovanstående problem, och närmare bestämt att anvisa en teknik som möjliggör robust och/eller beräkningseffektiv identifiering av ett vir- tuellt raster i en digital bild av ett kodningsmönster.

Dessa och andra ändamål, som kommer att framgå av följande beskrivning, uppnås helt eller delvis genom ett förfarande, ett datorprogram, ett lagringsmedium och en anordning för positionsbestämning enligt efterföljande patentkrav l, 19, 20 respektive 21. Föredragna utförings- former definieras i de underordnade patentkraven.

Tack vare att uppsättningar av objekten i den digi- tala bilden matchas mot en cellenhet, som motsvarar ett återkommande, känt grundelement hos rastret, begränsas inverkan av störningar i form av fiktiva objekt, eftersom huvuddelen av dessa inte är placerade i överensstämmelse med cellenheten och därför filtreras bort vid matchning- en. Om något enstaka objekt vid matchningen felaktigt lO 520 682 4 identifieras som godkänt, så påverkas matchningen av kringliggande objekt endast i begränsad omfattning.

Matchningen kan dessutom verkställas på beräkningseffek- tivt vis.

Ur beräkningshänseende kan det vara fördelaktigt låta objekten i bilden representeras av en punktmängd. Varje att, under såväl matchningen som rekonstrueringen, objekt kan således representeras av en punkt vars posi- tion kan motsvara en tyngdpunkt för objektet, en maximalt eller minimalt luminansvärde hos objektet, etc.

Ovannämnda cellenhet kan representeras av en polygon vars via sidlinjer förbundna hörn är associerade med vardera ett objekt. En sådan polygon motsvarar således rastrets grundelement med avseende på antalet sidlinjer och antalet associerade markeringar. Däremot kan cell- enhetens utsträckning och form avvika från grundelement- ets dito, för att tillgodose för geometrisk distorsion i den digitala bilden.

Enligt ett utförande verkställs matchningen som en regelrätt jämförelse mellan uppsättningar av objekt i den digitala bilden och ett antal, med hänsyn till avbild- ningsförhållandena, möjliga cellenheter av olika ut- sträckning och form. Alternativt korrigeras först bilden, åtminstone med avseende på vridning i bildplanet, varpå matchningen verkställs genom jämförelse av uppsättningar- na med en cellenhet som är identisk med grundelementet.

Enligt ett alternativt, föredraget utförande skapas först en datastruktur som anger objektens grannförhållan- den. Vid matchningen används sedan datastrukturen för att bland objekten identifiera nämnda uppsättningar. Således används ett grannkriterium för att selektera de uppsätt- ningar av objekt som överhuvudtaget får matchas mot cell- enheten, vilket effektiviserar matchningen. Tack vare den förberedande selekteringen kan det också vara möjligt att applicera ett mindre strikt matchningskriterium, såsom att uppsättningen och cellenheten endast behöver ha samma antal objekt, vilket kan minska risken för att korrekta vszo 682 objekt missas vid matchningen, i synnerhet vid det inled- ningsvis beskrivna kodningsmönstret vars markeringar är förskjutna relativt sina korsningspunkter. Ovannämnda grannkriterium kan vara att objekten i en uppsättning skall bilda en cyklisk struktur av grannar och att denna cykliska struktur skall motsvara cellenheten, àtminstone med avseende på antalet därmed associerade objekt. Säle- des kan matchningssteget reduceras till att identifiera cykliska strukturer med ett givet antal objekt, vilket enkelt kan åstadkommas genom en sekvens av uppslag i datastrukturen.

För att ytterligare öka tåligheten mot störningar kan matchningen föregås av en eliminering av alla objekt som inte är ömsesidiga grannar, dvs matchningen verk- ställs endast för de objekt som enligt något kriterium har varandra som mest sannolika granne.

Tåligheten mot störningar kan ökas ytterligare genom att det virtuella rastret rekonstrueras på basis av en objektdelmängd, vilken innehåller godkända objekt som bildar ett sammanhängande område motsvarande flera intill varandra liggande cellenheter. Lämpligen bildas det sam- manhängande området att åtminstone omfatta de godkända objekt som parvis förbinds av en sidlinje som är gemensam för två cellenheter.

Rekonstrueringen av det virtuella rastret kan ske genom att de godkända objekten, åtminstone de i ovan- nämnda objektdelmängd, tillordnas var sin rasterposition i ett rasterkoordinatsystem pä det avbildade underlaget, och att det virtuella rastret rekonstrueras genom att objektens placering i den digitala bilden kopplas till deras tillordnade rasterposition på underlaget.

Enligt ett exempel beräknas rastrets rasterlinjer genom regressionsanpassning av de godkända objektens placering längs givna riktningar, vilka riktningar kan extraheras utgående frän ovannämnda rasterpositioner.

Enligt ett annat exempel beräknas en homogen trans- formationsmatris utgående från kopplingen mellan de god- lO lS 520 682 6 kända objektens lägen och de motsvarande på underlaget befintliga korsningspunkternas lägen.

Enligt ett utförande för behandling av en sekvens av digitala bilder, korrigeras först en aktuell digital bild för vridning i bildplanet via en första transformations- matris, varefter ovannämnda homogena transformations- matris beräknas utgående från den vridningskorrigerade bilden. dateras den första transformationsmatrisen på basis av Inför behandling av en ny aktuell bild, så upp- den senast beräknade homogena tranformationsmatrisen.

Detta utförande är beräkningseffektivt i det att den första transformationsmatrisen inte behöver beräknas utgående från objekten i varje aktuell bild.

Kortfattad beskrivning av ritningarna Uppfinningen beskrivs nedan i exemplifierande syfte med hänvisning till bifogade ritningar, vilka schematiskt åskådliggör för närvarande föredragna utföringsformer.

Fig l är en schematisk vy av en uppsättning om 4 X 4 markeringar i ett kodningsmönster.

Fig 2 är en schematisk vy av en handhållen apparat som kan användas för att detektera kodningsmönstret i fig 1.

Fig 3 återger schematiskt en digital bild av ett kodningsmönster av det slag som visas i fig l.

Fig 4 återger en fig 3 motsvarande punktmängd efter kompensation för vridning och skalfel i bildplanet och efter identifiering av grannförhållanden punkterna emellan.

Fig 5 illustrerar en lokal omgivning av en punkt och tillhörande sökområden för identifiering av grannpunkter.

Pig 6 visar en datastruktur för registrering av grannförhållanden i den digitala bilden.

Fig 7 återger en fig 4 motsvarande punktmängd efter extrahering av punkter med ömsesidiga grannförhållanden, vilka visas som streck i fig 7. 1520 682 7 Fig 8 återger en fig 7 motsvarande punktmångd efter extrahering av punkter ingående i cykliska strukturer av givet format.

Fig 9 är ett flödesschema som visar övergripande steg som utförs vid identifiering av den delmängd som slutligen skall användas vid rekonstrueringen av punkter- nas lägen relativt ett virtuellt raster.

Fig 10 illustrerar, utgående från punktmängden i fig 8, ett första delsteg vid rekonstrueringen enligt en första utföringsform.

Fig 11 illustrerar slutresultatet av rekonstrue- ringen enligt den första utföringsformen.

Fig 12 illustrerar, utgående från punktmängden i fig 8, en referenspunktmängd som används vid rekonstrue- ringen enligt en andra utföringsform.

Fig 13 illustrerar slutresultatet av rekonstrue- ringen enligt den andra utföringsformen.

Fig 14 är ett flödesschema som visar övergripande steg som kan utföras vid rekonstrueringen enligt den andra utföringsformen.

Fig 15 är en fig 7 motsvarande vy av en alternativ punktmàngd efter extrahering av punkter med ömsesidiga grannförhållanden.

Beskrivning av föredragna utföringsformer Nedanstående beskrivning är inriktad på positions- bestämning utifrån digitala bilder av ett positionskod- ningsmönster. Positionskodningsmönstret kan vara av godtyckligt slag, exempelvis något av de inledningsvis utpekade mönstren. I det följande exemplifieras dock upp- finningen i anslutning till det mönster som beskrivs i sökandens patentpublikationer WO 01/16691, WO 01/26032 Och WO Ol/26033. med hänvisning till fig 1.

Detta mönster beskrivs nedan i korthet Positionskodningsmönstret omfattar ett raster 10 som är uppbyggt av ett antal rasterlinjer 11. Rastret 10 är virtuellt i så måtto att det varken syns för det mänsk- liga ögat eller kan detekteras direkt av en anordning som lO 520 682 8 skall bestämma positioner på ytan. Rastret 10 kan ses som sida vid sida utlagda, inbördes i detta fall kvadrater. uppbyggt av en mångfald, identiska grundelement, Posi- tionskodningsmönstret omfattar också ett flertal marke- ringar 12, som var och en, beroende på sin placering, representerar ett av fyra värden ”1” till ”4”. Marke- ringens 12 värde beror på var den är placerad i för- hållande till sin nominella position 13. Den nominella positionen 13, som också kan betecknas som en raster- punkt, representeras av skärningspunkten mellan raster- linjerna 11.

I exemplet i fig 1 finns fyra möjliga placeringar, en på var och en av rasterlinjerna som utgår från den nominella positionen 13. Förskjutningen från den nomi- nella positionen 13 är lika stor för alla värden. Varje markering 12 är med sin tyngdpunkt förskjuten i förhåll- ande till sin nominella position 13, dvs ingen markering är belägen i den nominella positionen. Det finns vidare en enda markering 12 per nominell position 13.

Förskjutningen är företrädesvis 1/6 av rasterlinje- avståndet, eftersom det då blir relativt enkelt att av- göra vilken nominell position som en viss markering till- hör. Förskjutningen bör vara minst omkring 1/8 av raster- linjeavståndet, eftersom det annars kan bli det svårt att bestämma en förskjutning, dvs kraven på upplösning blir stora. Å andra sidan bör förskjutningen vara mindre än omkring 1/4 av rasterlinjeavståndet för att tillhörighet till nominell position skall kunna bestämmas.

Varje markering 12 utgöres i detta exempel av en mer eller mindre cirkulär prick med en radie som är omkring lika stor som förskjutningen eller något mindre. Radien kan vara mellan 25% till 120% av förskjutningen. Om radien blir mycket större än förskjutningen kan det bli svårt att bestämma rasterlinjerna. Om radien blir för liten behövs större upplösning för att registrera marke- ringarna. Markeringarna behöver dock inte vara cirkulära eller runda, utan kan ha vilken som helst lämplig form, lO 520 682 9 sàsom kvadratisk, triangulär, elliptisk, fylld, ofylld etc.

Ovan beskrivna mönster kan utformas att koda ett mycket stort antal absoluta positioner. Exempelvis kan mönstret vara sådant att 6 X 6 angränsande markeringar tillsammans kodar ett underlag, i form av en x-koordinat och en y-koordinat. Om en delmängd av mönstret är appli- cerad på ett underlag kan man åstadkomma en elektronisk representation av det som skrivs eller ritas pà under- laget med en penna genom att man löpande bestämmer pennans position pà produkten genom avläsning av den lokala kombinationen av markeringar. Denna avläsning kan ske genom optisk detektion.

I fig 2 visas en handhållen apparat 20, nedan kal- lad penna, som används för optisk detektion av positions- kodningsmönstret i fig 1. I det följande beskrivs kort pennans huvudkomponenter enligt ett utförande. För en mer fullständig beskrivning hänvisas till ovannämnda patent- publikationer WO Ol/16691, WO Ol/26032 och WO Ol/26033.

Pennan 20 uppvisar ett pennformigt hölje 21 som i sin ena kortände avgränsar en öppning 22. Kortänden är avsedd att ligga an mot eller hållas pä litet avstånd från den yta pà vilken positionsbestämningen skall ske.

En eller flera infraröda lysdioder 23 är inrättade vid öppningen 22 för belysning av det ytomràde som skall avbildas, och en IR-känslig areasensor 24, CCD- eller CMOS-sensor, exempelvis en är inrättad att registrera en tvädimensionell bild av ytomràdet.

Areasensorn 24 är kopplad till en databehandlare 25 som är anordnad att bestämma en position pä basis av den av sensorn 24 registrerade bilden. Databehandlaren 25 kan innehålla ett processororgan 25a som är programmerat att bearbeta bilder fràn sensorn 24, eller från ett sensorn 24 tillordnat minne, för positionsbestämning pà basis av dessa bilder.

Processororganet 25a kan omfatta en mikroprocessor, såsom en CPU ("Central Processing Unit"), en DSP ("Digi- lO l5 520 682 tal Signal Processor“) eller någon annan programmerbar logisk anordning, sàsom en FPGA. Processororganet 25a kan alternativt, eller dessutom, omfatta en hàrdvarukrets, såsom en ASIC ("Application-Specific Integrated Circuit") och/eller diskreta analoga och digitala komponenter.

Minnesorganet 25b omfattar företrädesvis olika typer (RAM), (ROM/FLASH) Pà känt vis kan arbetsminnet säsom arbetsminne läsminne (FLASH). lagra data under det att denna bearbetas medelst pro- av minne, och skrivminne cessororganet 25a, kan läsminnet lagra den programkod som exekveras av processororganet 25a i arbetsminnet, och kan skrivminnet lagra resultatet av bearbetningen, säsom positionskoordinater.

Pennan 20 har också en pennspets 26 som avsätter markeringsvätska pä underlaget. Därmed kan användaren skriva fysiskt pä underlaget samtidigt som det skrivna registreras digitalt via optisk detektion av positions- kodningsmönstret. Markeringsvätskan är lämpligen trans- parent för infrarött ljus, medan positionskodningsmönst- (fig l) ljus. Därmed undviks att markeringsvätskan stör detek- rets markeringar 12 är absorberande för infrarött tionen av mönstret.

När pennan 20 förs över ett positionskodat underlag registrerar således areasensorn 24 en följd av digitala gràskalebilder som överförs till databehandlaren 25 för positionsbestämning. 12 (fig 1) I bilderna framträder markeringarna som mörka objekt mot en ljus bakgrund. Van- ligen täcker varje objekt flera bildelement.

För att kunna avkoda en bild mäste databehandlaren rekonstruera det virtuella rastret och fastställa ett givet antal objekts placeringar relativt detta.

Inför rekonstrueringen av det virtuella rastret verkställer databehandlaren först en s k segmenterings- process för att isolera objekten fràn bakgrunden i grå- skalebilden och därigenom reducera mängden data att be- handla i efterföljande steg. Detta kan ske genom en för fackmannen välkänd trösklingsoperation, vilken resulterar l5 520 682 ll i en binär bild. För att ytterligare reducera mängden data kan databehandlaren extrahera en punktmängd från den binära bilden, t ex genom beräkning av tyngdpunkten för respektive objekt. Slutresultatet av segmenteringspro- cessen kan således vara en binär bild (bitmap), där varje objekt identifieras av ett bildelement (pixel), eller någon annan datastruktur som innehåller en lägesbeståm- ning för varje objekt med pixel- eller subpixelupplös- ning.

Segmenteringsprocessen kommer i allmänhet också att identifiera fiktiva objekt, dvs objekt utan motsvarighet i den avbildade delmängden av positionskodningsmönstret, exempelvis som följd av brus, belysningsvariationer, eller artefakter (smuts, ojämnheter, etc) hos det posi- tionskodade underlaget. Sådana fiktiva objekt kan störa avkodningsprocessen.

Fig 3 visar schematiskt en digital bild av ovan beskrivna kodningsmönster. I fig 3 indikeras objekt med ringar och motsvarande punktmängd med kryss. Det vir- tuella rastret 10 är också inritat för att underlätta förståelsen. Uppenbarligen är den digitala bilden regist- rerad med vridning och kraftig snedställning av sensorn relativt det positionskodade underlaget. Det må under- strykas att fig 3 är ett schematiskt exempel, och att antalet n objekt i det praktiska fallet kan vara betyd- ligt större. Även om varje position kodas av 36 (6 x 6) objekt så omfattar varje digital bild i allmänhet fler objekt, 100-200.

Efter segmenteringen underkastas den binära bilden typiskt n = en korrigeringsprocess, vilken resulterar i en punktmängd väsentligen utan vridning i bildplanet. Detta kan àstad- kommas via Fourieranalys av punktmängden, såsom beskrivs i detalj i ovannämnda patentpublikation WO Ol/75783.

Fourieranalysen resulterar i övergripande huvudvektorer för punktmängden, dvs övergripande riktningar och avstånd i den binära bilden. Därefter beräknas en linjär trans- formationsmatris som överför huvudvektorerna till resul- 520 682 12 tatvektorer vars riktning och längd väsentligen motsvarar (fig l), vektorer med längdförhållande lzl. Punktmängden korrige- originalrastret i detta fall inbördes ortogonala ras därefter för vridning och skalfel genom att transfor- mationsmatrisen opereras på den ursprungliga punktmängd~ en. I fig 4 visas resultatet av korrigeringsprocessen för punktmängden i fig 3. Av tydlighetsskäl visas även det virtuella rastret 10, som ju ännu inte är rekonstruerat.

Det framgår att en icke-linjär komponent, dvs perspektiv- förvrängning, kvarstår hos den korrigerade punktmängden.

Härefter verkställer databehandlaren en sökprocess, vilken syftar till att identifiera punkternas grannför- hàllanden. punktmängden, Närmare bestämt eftersöks, för varje punkt i en grannpunkt i givna sökriktningar.

Sökprocessen illustreras närmare i fig 5, utgående frän två resultatvektorer vl, v2 enligt ovan. I sökpro- cessen används fyra, utgående från dessa resultatvektor- er vl, v2 definierade, sökvektorer: vl, vz, v3=-vl och v4=-V2. Varje sökvektor är sin tur tillordnad ett sök- omràde I-IV, vars utsträckning är satt med kännedom om kodningsmönstrets uppbyggnad. Sökområdena är lämpligen tillräckligt stora för att säkerställa detektion av en punkt tillhörande en angränsande rasterkorsning, men tillräckligt små för att undvika detektion av punkter (jfr fig l). I det aktuella kodningsmönstret är varje markering förskjuten tillhörande andra rasterkorsningar 1/6 av rasterlinjeavståndet, varför det minsta avståndet mellan markeringarna är 2/3 rasterlinjeavstånd (marke- ringar som är förskjutna i riktning mot varandra).

Perspektiveffekter i bilden kan reducera detta avstånd, varför sökområdenas radie i föreliggande exempel har satts till ca 1/2 rasterlinjeavstånd.

Utgående från en punkt A i fig 5 identifieras en grannpunkt D i sökomràdet I, två potentiella grannpunkter B och C i sökomràdet II, och inga grannpunkter i sök- områdena III-IV. lO l5 520 682 13 Om flera potentiella grannpunkter identifieras per sökområde, väljs den grannpunkt som är belägen närmast sökområdets centrum, dvs sökvektorns spets. Denna urvals- process kan även ta hänsyn till ytstorleken på de mot punkterna svarande objekten, t ex i förhållande till objektens kända nominella storlek. Därmed kan man redu- cera inverkan av brus, vilket som regel resulterar i objekt med liten ytstorlek.

Under sökprocessen skapar databehandlaren en tabell, lista eller annan datastruktur innehållande en grannpunkt i respektive sökriktning, för varje punkt i punktmängden, såsom indikeras i fig 6. Denna tabell definierar ett ske- lett av grannförhållanden för användning vid rekonstrue- ringen av det virtuella rastret.

I fig 4 återger pilarna de grannförhållanden som bestämts för punktmängden i fig 3.

Ovannämnda skelett förfinas dock ytterligare i två kontrollsteg innan databehandlaren verkställer rekonst- rueringen av rastret.

I det första kontrollsteget extraheras endast de punkter som är ömsesidiga grannar, såsom indikeras med dubbelriktade pilar i fig 4. Motsvarande skelett visas i fig 7, i vilken enkelstreck indikerar ömsesidiga grann- förhållanden.

I det andra kontrollsteget, som schematiskt visas i fig 9, matchas först skelettet i fig 7 mot cykliska (steg 901). strukturer av känt format De cykliska struk- turerna kan ses som cellenheter, vilka motsvarar det ursprungliga rastrets grundelement. I exemplet är grund- elementen kvadrater och cellelementen godtyckliga poly- goner med fyra hörn med vardera en punkt. De cykliska strukturerna kan identifieras utgående från datastruk- turen i fig 6, genom att databehandlaren för en aktuell punkt kontrollerar om det finns en första granne i den första sökriktningen vl, om den första grannen har en andra granne i den andra sökriktningen vz, om den andra grannen har en tredje granne i den tredje sökriktningen lO l5 520 682 ïïffi 14 v3, om den tredje grannen har en fjärde granne i den fjärde sökriktningen V4, och om den fjärde grannen är identisk med den aktuella punkten. I så fall extraheras dessa punkter och identifieras som ingående i en cell- enhet. I fig 8 visas de cellenheter som identifierats utgående från fig 7.

Härefter klassificeras länkarna mellan punkterna.

Om länken ingår som en sidlinje i två cellenheter, klassificeras länken som stark (steg 902), annars som svag (steg 903).

Klassificeringen används sedan för identifiera ett sammanhängande område av skelettet att använda vid re- konstrueringen. Detta sker genom att databehandlaren (steg 904) ingående punkterna och identifierar alla starka punkter, väljer en startpunkt bland de i cellenheterna dvs punkter som kan nås från startpunkten via starka länkar (steg 905). Därefter identifierar databehandlaren dvs punkter som kan nås från de star- (steg 906). alla svaga punkter, ka punkterna via en och endast en svag länk Databehandlaren bildar en första komponent eller delmängd av de identifierade starka och svaga punkterna (steg 907), och upprepar sedan ovanstående sökning för andra startpunkter (steg 908). Dessa startpunkter kan lämpligen väljas bland de punkter som ännu inte ingår i någon kom- ponent, eller åtminstone bland de punkter som ännu inte klassats som starka. I det sistnämnda fallet kan således svaga punkter ingå i flera komponenter. När alla möjliga startpunkter testats, utväljs den komponent som inne- håller flest punkter, alternativt flest starka punkter (steg 909).

I fig 8 visas resultatet av det andra kontrollsteget för de från skelettet i fig 7 extraherade punkterna, ut- gående från startpunkten S. Starka och svaga länkar visas med dubbelstreck respektive enkelstreck, och starka och svaga punkter visas med fyllda respektive ofyllda cirk- lar. l0 l5 520 682 I fig 8 visas också att de starka och svaga punkter- na, åtminstone i den utvalda komponenten, åsätts var sin rasterposition i ett rasterkoordinatsystem som kan, men inte behöver, vara centrerat i startpunkten S. Varje rasterposition ges i exemplet av två rasterkoordinater i form av heltal. Dessa rasterpositioner används för att koppla punkterna i komponenten till det ursprungliga kodningsmönstrets rasterkorsningar, såsom kommer att beskrivas närmare nedan.

Ovanstående klassificering av länkarna syftar till att minimera uppkomsten av fel när en komponent bildas av flera lokalt identifierade cellenheter. I fig 15 visas ett exempel på ett skelett av ömsesidiga grannförhållan- den mellan punkter/objekt i en bild. Även om varje cell- enhet verkar korrekt identifierad i sin lokala omgivning, så innehåller cellenheterna som helhet ett geometriskt fel. starka länkar, Om komponenten byggs upp på grundval av endast så minimeras denna typ av geometriska fel eftersom de starka länkarna ingår i två cellenheter och därmed är bestämda med större säkerhet än de svaga länk- arna.

Eftersom den efterföljande rekonstrueringen för- bättras med antalet punkter som ingår i den utvalda kom- ponenten, så kan man dock tillåta svaga länkar att ge bidrag till komponenten med en ytterligare punkt, såsom beskrevs i ovanstående exempel. Även om det inte framgår av exemplet i fig 8, kan det vara lämpligt att reducera inverkan av de svaga punkterna relativt de starka punkt- erna, t ex genom att de svaga punkterna ges en raster- position som är bestämd i endast en dimension, och när- mare bestämt så, att en svag punkt tillordnas den raster- koordinat som är gemensam för den svaga punkten och den starka punkt som länkar den svaga punkten till den aktu- ella komponenten.

Härefter skall det virtuella rastret rekonstrueras utifrån den utvalda komponenten i fig 8. lO 520 682 7f¿*¥ïå~?f¥ï l6 Enligt en första utföringsform verkställer databe- handlaren en regressionsanpassning av grupper av punkter till räta linjer som approximerar rasterlinjer, sàsom indikeras i fig lO. Närmare bestämt grupperas punkterna efter sina rasterpositioner. Utgående fràn fig 8 så har det bildats vertikala grupper med punkter vars raster- positioner i en första dimension ges av -1, O, 1, 2 respektive 3, samt horisontella grupper med punkter vars rasterpositioner i en andra dimension ges av -1, 0, 1, 2, 3 respektive 4. Riktningen pä varje enskild linje kan ha låg precision, pà grund av det làga antalet punkter per linje, speciellt vid den utvalda komponentens periferi.

Därför verkställer databehandlaren en kompletterande regressionsanpassning, i vilken lutningskoefficienten för de vertikala respektive horisontella linjerna anpassas till en linjär funktion i horisontell respektive verti- kal led. Perspektiveffekter gör nämligen att inbördes parallella linjer riktas mot en gemensam perspektivpunkt.

Detta visas exempelvis i ovannämnda patentpublikation WO Ol/75783, vilken införlivas häri genom denna hänvis- ning.

Efter den andra regressionsanpassningen kan nya rasterlinjer beräknas, vilka utgör en väsentligen korrekt rekonstruering av det virtuella rastret 10, säsom visas i fig ll.

Databehandlaren kan alternativt verkställa den komp- letterande regressionsanpassningen genom att anpassa de inbördes avständen mellan angränsande vertikala respek- tive horisontella linjer till en linjär funktion längs en horisontell respektive vertikal riktningsvektor. Även i detta fall möjliggörs en rekonstruering av de raster- linjer som bildar det virtuella rastret.

Med kännedom om det virtuella rastret kan databe- handlaren sedan avkoda punkterna i den utvalda komponent- en och pà basis därav beräkna sensoranordningens position pä det positionskodade underlaget. För detaljer kring avkodningen hänvisas till ovannämnda patentpublikationer 520 682 17 WO 01/16691, WO 01/26032 och WO Ol/26033, Vilka inför- livas häri genom denna hänvisning.

Enligt en andra utföringsform verkställer databe- handlaren rekonstrueringen genom beräkning av en homogen transformationsmatris. I detta fall jämförs varje punkt i den utvalda komponenten, såsom visas i fig 8, med mot- svarande rasterkorsning i ett idealt raster, såsom visas i fig 12. Härvid används rasterpositionerna för att iden- tifiera punkter och motsvarande rasterkorsningar, såsom också indikeras i fig 8 och 12. Därmed kan ett ekvations- system ställas upp innehällande tolv obekanta parametrar (hos transformationsmatrisen) och ekvationer som till antalet är dubbelt sä många som punkterna i den utvalda komponenten, på liknande vis som beskrivs i ”Digital Image Processing” av R.F. Gonzalez och R.E. Woods, 1992, pp 67-68. liga punkter härrör från ett och samma geometriska plan Addison-Wesley, Med kännedom om att samt- (dvs underlaget) kan antalet obekanta parametrar reduce- ras till ätta.

Det finns en mängd olika kända numeriska metoder för lösning av dylika överbestämda ekvationssystem. Det för närvarande föredragna utförandet är baserat pä en minsta- kvadrat-anpassning.

Det kan te sig oväntat att en korrekt homogen trans- formationsmatris kan beräknas genom koppling av punkterna i fig 8 till rasterkorsningarna i fig 12, (jfr fig 1) eftersom punkt- erna genom sina förskjutningar inte exakt motsvarar rasterkorsningarna. Den beräknade transforma- tionsmatrisen representerar dock någon form av medelvärde över ett stort antal punkter, varför förskjutningarna matematiskt väsentligen tar ut varandra.

När den homogena transformationsmatrisen har beräk- nats opereras den på den utvalda komponentens punkter, vilka då överförs till sina korrekta placeringar i för- hållande till ett rekonstruerat raster vars rasterkors- ningar ges av rasterpositionerna, såsom indikeras i fig 13. lO 520 682 18 I det följande beskrivs i anslutning till fig 14 övergripande förfarandesteg som utförs av databehandlaren vid behandling av en sekvens av gràskalebilder.

Först inläses en aktuell gràskalebild (steg 141), vilken via en segmenteringsprocess bildar en aktuell binär bild (steg 142). Sedan extraheras lämpligen en aktuell punktmängd från den aktuella binära bilden.

Därefter beräknas en linjär transformationsmatris LTM, t ex via Fourieranalys av den aktuella punktmängden (steg 143). Den linjära transformationsmatrisen används sedan för att korrigera den aktuella punktmängden för (steg 144). samt de första och andra kont- vridning och ev skalfel Härefter verkställs sökprocessen (steg 145), (steg 146-147), rollstegen vilka resulterar i en utvald komponent, dvs en utvald delmängd punkter. Slutligen be- räknar databehandlaren en homogen transformationsmatris HTM på basis av den utvalda komponentens punkter (steg 148), varpå den homogena tranformationsmatrisen opereras pà komponentens punkter för att skapa ett rekonstruerat raster med tillhörande punkter (steg 149), vilka sedan (steg 150).

Vid digitalisering av handskrift bör denna för kor- avkodas rekt àtergivning registreras med en samplingstakt av ca 50-100 Hz. Vid denna samplingstakt sker dock förhållande- vis smà förändringar i vridning och snedställning av pennan mellan påföljande bilder. Detta kan utnyttjas för att minimera beräkningsarbetet med att ta fram en ny linjär transformationsmatris LTM för en efterföljande gràskalebild. I stället för att verkställa en förhåll- andevis tids- och beräkningskrävande analys, t ex via Fouriertransformering, kopieras de linjära parametrarna frän den homogena transformationsmatrisen HTM in i den linjära transformationsmatrisen LTM (steg l43'), varpå den sålunda uppdaterade transformationsmatrisen används under korrigeringsprocessen (steg 144). Därmed kan pro- cessorkraft frigöras i databehandlaren för andra beräk- ningar, t ex avkodning. l5 520 682 19 Ovanstående förfarande kan realiseras av programkod som exekveras i den digitala pennans processororgan, eller i en till pennan kopplad, extern behandlingsenhet.

Programkoden kan tillhandahållas på ett lagringsmedium, t ex i form av en diskett, en CD~ROM, eller propagerande signaler via ett datornätverk. Alternativt kan förfaran- det realiseras av en hårdvarukrets och/eller diskreta analoga/digitala komponenter, eventuellt i kombination med exekvering av programkod enligt ovan.

Det mä påpekas att det sökta patentskyddets omfatt- ning ej begränsas av ovan beskrivna utföringsexempel.

Uppfinningen kan varieras och ändras på ett flertal sätt inom ramen för de bifogade patentkraven.

Exempelvis år den uppfinningsenliga tekniken appli~ cerbar även för kodningsmönster baserade på andra grund- element, såsom hexagoner, rektanglar, trianglar etc, eller andra markeringar, såsom streck, trianglar, tvä- dimensionella streckkoder etc, placerade med eller utan förskjutning relativt korsningspunkterna hos ett vir- tuellt rastermönster.

Vidare mà påpekas att ovanstående korrigerings- process inte är knuten till användning av Fouriertrans- former, utan kan verkställas med någon annan för syftet vedertagen metod, såsom Hough-transformer, Walsh-trans- former etc. För övrigt är det inte ens nödvändigt att verkställa någon korrigering, utan sökprocessen kan verk- ställas på basis av de övergripande huvudvektorerna i stället för resultatvektorerna. En inledande korrigering kan dock underlätta implementeringen av den efterföljande sökprocessen, eftersom samma sökomràden kan användas för alla punkter och alla bilder.

Enligt ett ytterligare alternativ utan korrigerings- process verkställs den andra kontrollprocessen som en regelrätt geometrisk matchning av punktmängden mot en uppsättning olika möjliga cellenheter. Databehandlaren kan exempelvis vara anordnad att, på basis av ett aktu- ellt beräknat perspektiv, hämta möjliga cellenheter från lO 520 682 ett bibliotek i sitt minnesorgan. Exempelvis kan en kvadratsumma av avvikelserna mellan punkter och mot- svarande hörn hos respektive cellenhet användas som matchningskriterium, varvid kvadratsumman bör under- stiga ett gränsvärde för att överensstämmelse skall anses föreligga.

Enligt ett annat tänkbart alternativ sker en inledande korrigeringsprocess, varefter en regelrätt geometrisk matchning verkställs av punktmängden mot kodningsmönstrets kända grundelement. Även här kan en kvadratsumma av avvikelserna mellan punkter och hörn- positioner användas som matchningskriterium.

Claims (21)

lO l5 20 25 30 35 520 682 21 PATENTKRAV

1. Förfarande vid rekonstruering av ett virtuellt raster utgående från objekt i en digital bild, varvid objekten åtminstone delvis återger markeringar (12) på (12) (13) tillhörande det virtuella rastret ett underlag och varvid varje markering är asso- för raster- (10), av stegen att matcha uppsättningar cierad med en respektive korsningspunkt (ll) k ä n n e t e c} linjer av objekten mot en cellenhet, vilken motsvarar ett åter- kommande, känt grundelement hos nämnda raster, att när en uppsättning överensstämmer med cellenheten identifiera de i uppsättningen ingående objekten som godkända, och att rekonstruera det virtuella rastret på basis av de god- kända objektens inbördes placering.

2. Förfarande enligt krav 1, varvid objekten i bilden representeras av en punktmängd.

3. Förfarande enligt krav 1 eller 2, varvid cell- enheten är associerad med ett givet antal objekt.

4. Förfarande enligt krav l, 2 eller 3, varvid cellenheten är en polygon vars via sidlinjer förbundna hörn är associerade med vardera ett objekt.

5. Förfarande enligt något av föregående krav, om- fattande stegen att bilda en objektdelmängd innehållande godkända objekt som bildar ett sammanhängande område motsvarande flera intill varandra liggande cellenheter, och att rekonstruera det virtuella rastret på basis av objektdelmängden.

6. Förfarande enligt krav 5, varvid det samman- hängande området bildas att åtminstone omfatta de god- kända objekt som parvis förbinds av en sidlinje som är gemensam för två cellenheter.

7. Förfarande enligt krav 5 eller 6, varvid objekt- delmängden bildas att innehålla det största möjliga antalet godkända objekt. 10 l5 20 25 30 35 520 682 22

8. Förfarande enligt något av föregående krav, om- fattande det inledande steget att skapa en datastruktur över objektens grannförhållanden, varvid matchningssteget omfattar att med användning av datastrukturen identifiera nämnda uppsättningar.

9. Förfarande enligt något av föregående krav, ytterligare omfattande stegen att i den digitala bilden bestämma huvudvektorer som återger dess övergripande rasterlinjeriktningar och rasterlinjeavstånd, att på basis av huvudvektorerna identifiera objektens grannför- hàllanden genom att för varje objekt identifiera ett annat objekt som granne i respektive rasterlinjeriktning, och att därefter verkställa matchningssteget utgående från objektens grannförhållanden.

10. Förfarande enligt krav 8 eller 9, varvid de i en uppsättning ingående objekten identifieras som godkända om de som grannar bildar en cyklisk strukturer som mot- svarar cellenheten, åtminstone med avseende på antalet därmed associerade objekt.

11. ll. Förfarande enligt något av föregående krav, om- fattande steget att tillordna de godkända objekten var sin rasterposition i ett rasterkoordinatsystem på det av- bildade underlaget, varvid det virtuella rastret rekonst- rueras på basis av objektens placering i den digitala bilden och deras tillordnade rasterposition på under- laget.

12. Förfarande enligt något av föregående krav, varvid steget att rekonstruera det virtuella rastret omfattar att beräkna rasterlinjerna genom regressions- anpassning av de godkända objektens placering längs givna riktningar.

13. Förfarande enligt krav 5 och 12, varvid rikt- ningarna ges av rasterpositioner, företrädesvis av heltalskoordinater i ett rasterkoordinatsystem, vilka rasterpositioner àsätts de godkända objekten i samband med steget att bilda objektdelmängden. lO 15 20 25 30 35 520 682 23

14. Förfarande enligt något av kraven 1-11, varvid steget att rekonstruera det virtuella rastret omfattar att beräkna en homogen transformationsmatris utgående från lägesförhållandena mellan de godkända objekten och de motsvarande på underlaget befintliga korsningspunkt- erna, vars inbördes placering är definierade av grund- elementet.

15. Förfarande enligt krav 5 och 14, varvid läges- förhållandena ges av rasterpositioner, företrädesvis av heltalskoordinater i ett rasterkoordinatsystem, vilka rasterpositioner åsätts de godkända objekten i samband med steget att bilda objektdelmängden.

16. Förfarande enligt krav 15, för behandling av en sekvens av digitala bilder, omfattande det inledande steget att via en första transformationsmatris korrigera en aktuell digital bild för vridning i dess plan, att beräkna den homogena transformationsmatrisen utgående från den sålunda vridningskorrigerade bilden, och att uppdatera den första transformationsmatrisen inför be- handling av en nästföljande digital bild.

17. Förfarande enligt krav 16, varvid steget att uppdatera den första transformationsmatrisen omfattar att extrahera relevanta linjära parametrar från den homogena transformationsmatrisen.

18. Förfarande enligt något av föregående krav, var- vid matchningssteget verkställs endast för de objekt som är ömsesidiga grannar.

19. Datorprogram, vilket innefattar programkod som när den exekveras i en dator bringar datorn att genomföra ett förfarande enligt något av kraven 1-18.

20. Lagringsmedium vilket är avläsbart medelst en dator och på vilket är lagrat ett datorprogram som när det exekveras i en dator bringar datorn att genomföra ett förfarande enligt något av kraven 1-18.

21. Anordning för positionsavkodning, omfattande (25) position på basis av information som bestämts från en en signalbehandlare som är anordnad att beräkna en 10 15 520 682 24 (24) område av ett positionskodningsmönster, vilket omfattar (12) respektive korsningspunkt medelst en sensor genererad digital bild av ett del- markeringar som var och en är associerad med en (13) (ll) tillhörande ett virtuellt raster (10), varvid signal- (25) beräkningen rekonstruera det virtuella rastret för rasterlinjer behandlaren vidare är anordnad att inför positions~ (10) gående från objekt i den digitala bilden, vilka objekt ut- åtminstone delvis återger nämnda markeringar, k äz1r1e - t e c k n a d (25) att matcha uppsättningar av objekten mot en cellenhet, av att signalbehandlaren är anordnad vilken motsvarar ett återkommande, känt grundelement hos nämnda raster (10), att när en uppsättning överensstämmer med cellenheten identifiera de i uppsättningen ingående objekten som godkända, och att rekonstruera det virtuella (10) placering. rastret på basis av de godkända objektens inbördes