SE513058C2

SE513058C2 - Method for matching two images of body specific patterns, each image with several pixels and partially overlapping contents, degree of correspondence between images is determined for different displacement positions

Info

Publication number: SE513058C2
Application number: SE9704925A
Authority: SE
Inventors: Christer Faahraeus; Ola Hugosson; Petter Ericson
Original assignee: Precise Biometrics Ab
Priority date: 1997-12-30
Filing date: 1997-12-30
Publication date: 2000-06-26
Also published as: SE9704925D0; SE9704925L

Abstract

Method determines several numbers for each of several displacement positions, with each number formed with the aid of pixel values from both images (1a and 1b). The numbers are used to retrieve overlap assessment values for two displacement positions simultaneously. These overlap assessment values are subsequently used to determine the degree of correspondence between the contents of the images.

Description

15 20 25 30 513 058 2 Säkerheten i systemet ökar naturligtvis ju mer data som undersöks, men à andra sidan ökar också tiden för identifieringen. Det finns därför ett stort behov av ett sätt att snabbt och effektivt matcha fingeravtryck med varandra. 15 20 25 30 513 058 2 The security of the system naturally increases the more data that is examined, but on the other hand, the time for identification also increases. There is therefore a great need for a way to quickly and efficiently match fingerprints with each other.

På senare tid har man även börjat använda andra kroppsspecifika mönster, såsom hand- och fotavtryck, och irismönster, för identifiering av personer. Vid dessa tillämpningar finns det givetvis samma behov av att snabbt matcha bilder med varandra.Recently, other body-specific patterns, such as hand and footprints, and iris patterns, have also begun to be used to identify people. In these applications, there is of course the same need to quickly match images with each other.

Ett tänkbart sätt att matcha två bilder av kropps- specifika mönster är att undersöka alla möjliga överlapp- ningspositioner mellan bilderna och att för varje över- lappningsposition undersöka samtliga par av överlappande bildpunkter, bestämma en poäng för varje par av överlap- pande bildpunkter, varvid poängen beror på hur väl bild- punkternas värden överensstämmer med varandra, och att sedan bestämma vilken av överlappningspositionerna som ger den bästa överensstämmelsen på basis av summan av poängerna för de överlappande bildpunkterna i varje posi- tion. Detta är emellertid ett alltför långsamt förfarande för den ovan angivna tillämpningen.A possible way of matching two images of body-specific patterns is to examine all possible overlapping positions between the images and to examine for each overlapping position all pairs of overlapping pixels, determining one point for each pair of overlapping pixels, the score depends on how well the values of the pixels correspond to each other, and to then determine which of the overlapping positions gives the best agreement on the basis of the sum of the points for the overlapping pixels in each position. However, this is too slow a procedure for the above application.

Sammanfattning av uppfinningen Mot bakgrund av ovanstående är ett ändamål med före- liggande uppfinning således att anvisa ett nytt sätt för automatisk matchning mellan två bilder av kroppsspecifika mönster, vilket sätt möjliggör snabbare matchning av bilderna med en given processor än ovan beskrivna sätt.Summary of the invention In view of the above, an object of the present invention is thus to provide a new method for automatic matching between two images of body-specific patterns, which method enables faster matching of the images with a given processor than the methods described above.

Ett ytterligare ändamål är att åstadkomma en anord- ning för genomförande av sättet. Ändamålen uppnås med ett sätt enligt patentkravet 1 och en anordning enligt patentkravet 17 och enligt pa- tentkravet 18. Föredragna utföringsformer anges i under- kraven. 10 15 20 25 30 35 513 058 3 Uppfinningen bygger liksom tidigare på att graden av överensstämmelse mellan två bilder av kroppsspecifika mönster, vilka var och en består av ett flertal bild- punkter och har delvis överlappande innehåll, bestäms för olika förskjutningspositioner som representerar olika överlappningar mellan bilderna. Jämförelsen av innehållet i bilderna utförs emellertid på ett effektivare sätt.A further object is to provide a device for carrying out the method. The objects are achieved with a method according to claim 1 and a device according to claim 17 and according to patent claim 18. Preferred embodiments are stated in the subclaims. The invention is based, as before, on the degree of correspondence between two images of body-specific patterns, each of which consists of a plurality of pixels and has partially overlapping contents, being determined for different displacement positions representing different overlaps. between the images. However, the comparison of the contents of the images is performed more efficiently.

Mera specifikt bestäms ett flertal tal för var och en av ett flertal förskjutningspositioner, vilka tal vart och ett bildas med hjälp av bildpunktsvärden från båda bil- derna. Talen används för att samtidigt få fram i förväg definierade överlappningsbedömningsvärden för minst två förskjutningspositioner. Dessa överlappningsbedömnings- värden används sedan vid bestämningen av graden av över- ensstämmelse mellan innehållet i bilderna.More specifically, a plurality of numbers are determined for each of a plurality of offset positions, which numbers are each formed by means of pixel values from both images. The numbers are used to simultaneously obtain predefined overlap assessment values for at least two offset positions. These overlap assessment values are then used in determining the degree of agreement between the contents of the images.

Med detta sätt kan de olika förskjutningsposition- erna undersökas med en viss grad av parallellitet, vilket gör det möjligt att undersöka bilderna snabbare än om alla förskjutningspositionerna undersöks sekventiellt.In this way, the different displacement positions can be examined with a certain degree of parallelism, which makes it possible to examine the images faster than if all the displacement positions are examined sequentially.

Denna parallellitet uppnås med hjälp av talen, som an- vänds för att samtidigt undersöka minst två förskjut- ningspositioner. Eftersom talen är baserade på innehållet i respektive bild kan man på förhand räkna ut överlapp- ningsbedömningsvärden för de fall då bildpunktsvärdena som bildar talen överlappar varandra helt eller delvis.This parallelism is achieved with the help of the numbers, which are used to simultaneously examine at least two displacement positions. Since the numbers are based on the content of each image, it is possible to calculate overlap assessment values in advance for the cases where the pixel values that form the numbers completely or partially overlap.

Effektiviteten ökar givetvis ju flera bildpunkter som ingår i varje tal eftersom detta ökar parallelliteten. Överlappningsbedömningsvärdena är alltså definierade i förväg. Härmed avses att om en bildpunkt i den ena bilden har ett första givet värde och motsvarande över- lappande bildpunkt i den andra bilden har ett andra givet värde erhålles alltid ett visst i förväg bestämt över- lappningsvärde. Motsvarande gäller när överlappningsbe- dömningsvärdena avser flera överlappande bildpunkter. De olika överlappningsbedömningsvärden som erhålls för olika 10 15 20 25 30 35 513 Û58 4 kombinationer av bildpunktsvärden kan bestämmas fritt. De kan definieras med hjälp av en eller flera formler eller tabeller eller på något annat lämpligt sätt.Of course, the efficiency increases the more pixels that are included in each number because this increases the parallelism. The overlap assessment values are thus defined in advance. This means that if a pixel in one image has a first given value and the corresponding overlapping pixel in the second image has a second given value, a certain predetermined overlap value is always obtained. The same applies when the overlap assessment values refer to several overlapping pixels. The different overlap assessment values obtained for different combinations of pixel values can be determined freely. They can be defined using one or more formulas or tables or in any other suitable way.

Det skall i sammanhanget påpekas att bilderna natur- ligtvis inte förskjuts fysiskt i förhållande till var- andra vid genomförande av sättet, utan att jämförelsen mellan bilderna sker för tänkta förskjutningar.In this context, it should be pointed out that the images are of course not physically displaced in relation to each other when implementing the method, but that the comparison between the images takes place for imagined displacements.

I ett föredraget utförande innefattar sättet vidare stegen att summera överlappningsbedömningsvärdena för var och en av nämnda förskjutningspositioner, och att använda de sålunda erhållna summorna för bestämning av vilken av förskjutningspositionerna som ger den bästa möjliga överensstämmelsen mellan innehållet i bilderna. De över- lappningsbedömningsvärden som summeras för en viss för- skjutningsposition återspeglar företrädesvis överens- stämmelsen mellan samtliga överlappande bildpunkter för den förskjutningspositionen.In a preferred embodiment, the method further comprises the steps of summing the overlap assessment values for each of said displacement positions, and of using the sums thus obtained for determining which of the displacement positions gives the best possible correspondence between the contents of the images. The overlap assessment values summed for a given offset position preferably reflect the correspondence between all overlapping pixels for that offset position.

För att ytterligare öka hastigheten för matchningen, summeras överlappningsbedömningsvärdena lämpligen paral- lellt för ett flertal förskjutningspositioner. Summe- ringen blir speciellt fördelaktig om den görs parallellt för de överlappningsbedömningsvärden som hämtas samtidigt med hjälp av ett tal.To further increase the speed of the matching, the overlap assessment values are suitably summed in parallel for a plurality of displacement positions. The summation is especially advantageous if it is done in parallel for the overlap assessment values that are retrieved simultaneously with the help of a number.

Varje överlappningsbedömningsvärde kan avse en eller flera överlappande bildpunkter. I det senare fallet upp- nås en ökning av matchningshastigheten genom att man inte behöver addera bedömningsvärden för varje överlappande bildpunkt för en viss förskjutningsposition utan redan adderade överlappningsbedömningsvärden för tvà eller flera överlappande bildpunkter kan hämtas direkt.Each overlap assessment value can refer to one or more overlapping pixels. In the latter case, an increase in the matching speed is achieved by not having to add assessment values for each overlapping pixel for a certain offset position, but already added overlap assessment values for two or more overlapping pixels can be retrieved directly.

Det flertal förskjutningspositioner för vilka tal bestäms kan lämpligen utgöra grovförskjutningspositioner, och nämnda minst två förskjutningspositioner för vilka överlappningsbedömningsvärden hämtas kan lämpligen inne- fatta minst en finförskjutningsposition, som represente- 10 15 20 25 30 35 513 058 5 rar en mindre förskjutning från en grovförskjutnings- position än förskjutningen mellan två grovförskjutnings- positioner. Det andra hämtade överlappningsbedömnings- värdet kan avse den aktuella grovförskjutningspositionen eller en annan finförskjutningsposition.The plurality of displacement positions for which numbers are determined may suitably be coarse displacement positions, and said at least two displacement positions for which overlap assessment values are retrieved may suitably comprise at least one fine displacement position, which represents a minor displacement from a coarse displacement. position than the displacement between two coarse displacement positions. The second obtained overlap assessment value may refer to the current coarse displacement position or another fine displacement position.

I det enklaste utförandet av sättet är bildernas innehåll förskjutna i förhållande till varandra i enbart en riktning. Sättet kan emellertid även utnyttjas när bilderna är förskjutna i två olika, företrädesvis vinkel- räta, riktningar i förhållande till varandra. För att man i detta fall skall få fram den position i vilken överens- stämmelsen mellan bildernas innehåll är maximal, låter man lämpligen grovförskjutningspositionerna representera olika överlappningar mellan bilderna i den första rikt- ningen, exempelvis i horisontell led, och upprepas sättet för olika överlappningar mellan bilderna i den andra riktningen, exempelvis i vertikal led.In the simplest embodiment of the method, the contents of the images are shifted relative to each other in only one direction. However, the method can also be used when the images are shifted in two different, preferably perpendicular, directions relative to each other. In order to obtain in this case the position in which the correspondence between the contents of the images is maximum, the coarse displacement positions are suitably allowed to represent different overlaps between the images in the first direction, for example in the horizontal direction, and the method for different overlaps between the images in the other direction, for example in the vertical direction.

Grovförskjutningpositionerna, som alltså utgör en delmängd av de undersökta förskjutningspositionerna, bestäms företrädesvis genom att bilderna delas in i ett flertal grovsegment som består av N x M bildpunkter där N och M är större än ett, varvid förskjutningen mellan två angränsande grovförskjutningspositioner utgörs av ett grovsegment. Grovsegmenten kan alltså åstadkommas genom att bilderna delas in i kolumner eller rader, som var och en har ett flertal bildpunkters bredd resp höjd.The coarse displacement positions, which thus constitute a subset of the examined displacement positions, are preferably determined by dividing the images into a plurality of coarse segments consisting of N x M pixels where N and M are greater than one, the displacement between two adjacent coarse displacement positions being a coarse segment. The coarse segments can thus be achieved by dividing the images into columns or rows, each of which has a width and height of several pixels.

Bilderna kan vara representerade på olika sätt. De kan vara analoga, men är företrädesvis digitala eftersom de då blir enklare att behandla med hjälp av en dator.The images can be represented in different ways. They can be analog, but are preferably digital because they then become easier to process with the help of a computer.

Bildpunktsvärdena kan representeras med olika upplösning.The pixel values can be represented with different resolutions.

Sättet är dock företrädesvis avsett för bilder som rep- resenteras som bitmappar.However, the method is preferably intended for images that are represented as bitmaps.

Talen är såsom nämnts baserade på innehållet i de båda bilderna. I en föredragen utföringsform används talen som adresser till minnesplatser, som lagrar över- 10 15 20 25 30 35 515 058 6 lappningsbedömningsvärdena. I detta fall är dessa lämp- ligen definierade genom att de helt enkelt är uträknade eller bestämda i förväg.As mentioned, the numbers are based on the content of the two pictures. In a preferred embodiment, the numbers are used as addresses of memory locations, which store the overlap assessment values. In this case, these are suitably defined in that they are simply calculated or determined in advance.

Adresserna används företrädesvis för att adressera en uppslagstabell som, för varje adress, innehåller nämnda i förväg uträknade överlappningsbedömningsvärden för minst två förskjutningspositioner. Den ordning i vilken bildpunktsvärdena används i adressen saknar be- tydelse så länge samma ordning används för alla adresser och så länge lagringen av överlappningsbedömningsvärdena i uppslagstabellen görs på ett förutbestämt sätt i för- hållande till denna ordning.The addresses are preferably used to address a look-up table which, for each address, contains said pre-calculated overlap assessment values for at least two offset positions. The order in which the pixel values are used in the address is irrelevant as long as the same order is used for all addresses and as long as the storage of the overlap assessment values in the look-up table is done in a predetermined manner in relation to this order.

Sättet enligt uppfinningen kan implementeras helt i hårdvara. I detta fall kan talen exempelvis bilda insig- naler till en grindmatris som har utformats på så sätt att man för varje given uppsättning insignaler får fram motsvarande överlappningsbedömningsvärden som utsignaler.The method according to the invention can be implemented entirely in hardware. In this case, the numbers can, for example, form input signals to a gate matrix which has been designed in such a way that for each given set of input signals the corresponding overlap assessment values are obtained as output signals.

I detta fall är alltså överlappningsbedömningsvärdena definierade genom grindmatrisens utformning. Detta sätt kan vara fördelaktigt för större bilder.In this case, the overlap assessment values are thus defined by the design of the gate matrix. This method can be beneficial for larger images.

I ett föredraget utförande genomförs emellertid sättet i mjukvara med hjälp av en processor som arbetar med en förutbestämd ordlängd. Uppslagstabellen innefattar då ett flertal adresserbara rader, som var och en har den förutbestämda ordlängden och som lagrar de i förväg ut- räknade överlappningsbedömningsvärdena. Genom anpassning av tabellbredden till processorns ordlängd erhålles bästa möjliga utnyttjande av processorns kapacitet. Exempelvis kan man på ett effektivt sätt summera olika rader i tabellen.In a preferred embodiment, however, the method is performed in software by means of a processor operating at a predetermined word length. The look-up table then comprises a plurality of addressable rows, each of which has the predetermined word length and which stores the pre-calculated overlap assessment values. By adjusting the table width to the processor's word length, the best possible utilization of the processor's capacity is obtained. For example, you can effectively sum up different rows in the table.

De olika parametrarna för sättet, dvs grovförskjut- ningspositionerna, antalet för varje adress lagrade överlappningsbedömningsvärden, antalet tabeller osv be- stäms lämpligen utifrån den använda processorn och dennas cache-minne för uppnàende av högsta möjliga snabbhet. 10 15 20 25 30 35 513 058 7 Företrädesvis väljs parametrarna på så sätt att båda bilderna och samtliga de i förväg uträknade överlapp- ningsbedömningsvärdena ryms i cache-minnet.The various parameters of the method, ie the coarse offset positions, the number of overlap assessment values stored for each address, the number of tables, etc. are suitably determined on the basis of the processor used and its cache memory in order to achieve the highest possible speed. 10 15 20 25 30 35 513 058 7 Preferably, the parameters are selected in such a way that both images and all the pre-calculated overlap assessment values are stored in the cache.

I ett föredraget utförande bildas varje tal av ett första finsegment, som innefattar minst två angränsande bildpunktsvärden från den första bilden, och av ett andra finsegment, som överlappar det första finsegmentet och som innefattar lika många angränsande bildpunktsvärden som det första finsegmentet från den andra bilden, samt av ett tredje finsegment, som innefattar lika många an- gränsande bildpunktsvärden som det första finsegmentet från den andra bilden och som överlappar det första fin- segmentet i en intilliggande förskjutningsposition för vilken bestämningen av ett flertal tal utförs, dvs en intilliggande grovförskjutningsposition. På detta sätt kommer talet att inkludera alla bildpunktsvärden som kan överlappa varandra i en grovförskjutningsposition och i alla finförskjutningspositioner mellan denna grovför- skjutningsposition och följande grovförskjutningsposi- tion, samt i denna följande grovförskjutningsposition.In a preferred embodiment, each number is formed by a first fine segment comprising at least two contiguous pixel values from the first image, and by a second fine segment overlapping the first fine segment and comprising as many contiguous pixel values as the first fine segment from the second image. and of a third fine segment, which comprises as many contiguous pixel values as the first fine segment from the second image and which overlaps the first fine segment in an adjacent offset position for which the determination of a plurality of numbers is performed, i.e. an adjacent coarse offset position. In this way, the number will include all pixel values that can overlap in a coarse offset position and in all fine offset positions between this coarse offset position and the following coarse offset position, as well as in this following coarse offset position.

Härigenom kan man alltså med talet hämta i förväg ut- räknade överlappningsbedömningsvärden för samtliga dessa förskjutningspositioner.In this way, the number can be used to retrieve pre-calculated overlap assessment values for all these displacement positions.

För att spara minnesutrymme så att all erforderlig information kan lagras i en processors cache-minne och därigenom vara snabbt åtkomlig, delas med fördel varje adress upp i en första och en andra deladress, varvid den första deladressen, som består av bildpunktsvärdena från det första och det andra finsegmentet, används för att samtidigt hämta överlappningsbedömningsvärden i en första tabell för överlappande bildpunkter som tillhör det första och det andra finsegmentet, och varvid den andra deladressen, som består av bildpunktsvärdena från det första och det tredje finsegmentet används för att sam- tidigt hämta överlappningsbedömningsvärden i en andra m m! 10 15 20 25 30 513 058 8 tabell för överlappande bildpunkter som tillhör det första och det tredje finsegmentet.In order to save memory space so that all the required information can be stored in a processor's cache memory and thereby be quickly accessible, each address is advantageously divided into a first and a second subaddress, the first subaddress, which consists of the pixel values from the first and the second fine segment, is used to simultaneously retrieve overlap assessment values in a first table for overlapping pixels belonging to the first and the second fine segment, and wherein the second subaddress, which consists of the pixel values from the first and the third fine segment, is used to retrieve simultaneously overlap assessment values in a second mm! 10 15 20 25 30 513 058 8 table for overlapping pixels belonging to the first and the third fine segment.

I detta fall lagrar den första och den andra tabellen företrädesvis, för varje adress, ett överlapp- ningsbedömningsvärde för var och en av nämnda minst två förskjutningspositioner, varvid summan av de två över- lappningsbedömningsvärden för en första förskjutnings- position som hämtas med en adress första och andra del- adress utgör ett överlappningsbedömningsvärde för samt- liga överlappande bildpunkter för det första, det andra och det tredje finsegmentet för nämnda första förskjut- ningsposition. Överlappningsbedömningsvärdena lagras företrädesvis i samma ordning med avseende på förskjut- ningspositionerna för varje adress, så att de enkelt kan adderas.In this case, the first and second tables preferably store, for each address, an overlap assessment value for each of said at least two displacement positions, the sum of the two overlap assessment values for a first displacement position being retrieved with an address first and second sub-address constitutes an overlap assessment value for all overlapping pixels for the first, second and third fine segments for said first offset position. The overlap assessment values are preferably stored in the same order with respect to the offset positions of each address, so that they can be easily added.

För att ytterligare öka matchningshastigheten be- stäms graden av överensstämmelse mellan bilderna först med en första upplösning hos bilderna för val av ett flertal förskjutningspositioner därefter med en andra, högre upplösning hos bilderna för de valda förskjutnings- positionerna och angränsande förskjutningspositioner. På detta sätt kan man sortera bort hela områden i bilden som är ointressanta att undersöka vidare.To further increase the matching speed, the degree of agreement between the images is first determined with a first resolution of the images for selecting a plurality of offset positions then with a second, higher resolution of the images for the selected offset positions and adjacent offset positions. In this way, you can sort out entire areas in the image that are uninteresting to investigate further.

En uppfinningsenlig anordning har närmare bestämt en processorenhet som är anordnad att genomföra ett sätt enligt något av kraven 1-16. Processorenheten kan vara kopplad till en enhet för registrering av bilder och kan behandla bilderna i realtid. Anordningen uppvisar samma fördelar som det ovan beskrivna sättet, nämligen att den möjliggör en snabbare matchning av bilderna.More specifically, a device according to the invention has a processor unit which is arranged to carry out a method according to any one of claims 1-16. The processor unit can be connected to an image registration unit and can process the images in real time. The device has the same advantages as the method described above, namely that it enables a faster matching of the images.

I en föredragen utföringsform realiseras uppfinn- ingen i form av ett datorprogram som lagras på ett min- nesmedium som är avläsningsbart med hjälp av en dator. 10 15 20 25 30 513 058 9 Sättet enligt uppfinningen kan användas för att undersöka samtliga möjliga förskjutningspositioner eller endast en utvald del av dessa.In a preferred embodiment, the invention is realized in the form of a computer program which is stored on a memory medium which can be read by means of a computer. The method according to the invention can be used to examine all possible displacement positions or only a selected part of them.

Uppfinningen är tillämpbar vid alla typer av match- ning av bilder. Uppfinningen är i synnerhet tillämpbar när man har ett krav på hög matchningshastighet.The invention is applicable to all types of image matching. The invention is particularly applicable when there is a requirement for a high matching speed.

Kort beskrivning av ritningarna Ett exempel på hur uppfinningen kan realiseras be- skrivs i det följande under hänvisning till bifogade schematiska ritningar.Brief description of the drawings An example of how the invention may be realized is described in the following with reference to the accompanying schematic drawings.

Pig 1 visar en bild som består av ett flertal bild- punkter, med ett grovsegment och ett finsegment marke- rade.Pig 1 shows an image consisting of several pixels, with a coarse segment and a fine segment marked.

Pig 2 visar en tänkt överlappning mellan två bilder.Pig 2 shows an imaginary overlap between two images.

Pig 3 visar hur en adress bildas med hjälp av bild- punktsvärden från ett flertal överlappande bildpunkter i två bilder.Pig 3 shows how an address is formed using pixel values from a plurality of overlapping pixels in two images.

Pig 4 visar hur överlappningsbedömningsvärden för ett flertal olika förskjutningspositioner lagras och hämtas samtidigt.Fig. 4 shows how overlap assessment values for a plurality of different displacement positions are stored and retrieved simultaneously.

Pig 5 visar hur överlappningsbedömningsvärdena be- räknas för olika förskjutningspositioner.Fig. 5 shows how the overlap assessment values are calculated for different displacement positions.

Pig 6 visar hur överlappningsbedömningsvärden lagras och hämtas i fallet med användning av deladresser.Fig. 6 shows how overlap assessment values are stored and retrieved in the case using subaddresses.

Pig 7 olika förskjutningspositioner adderas samtidigt. visar hur överlappningsvärden för ett flertal Beskrivning av en föredragen utföringsform I det följande beskrivs ett för närvarande före- draget utförande av ett sätt för matchning av två bilder av kroppsspecifika mönster, varvid bilderna har delvis överlappande innehåll. Syftet med sättet är att finna den överlappningsposition som ger bästa möjliga överensstäm- melse mellan bildernas innehåll och att bedöma graden av överensstämmelse i denna position. Pör att bestämma vad 10 15 20 25 30 35 513 058 10 som utgör bästa möjliga överenstämmelse används ett på förhand bestämt bedömningskriterium.Pig 7 different displacement positions are added simultaneously. shows how overlap values for a plurality Description of a preferred embodiment The following is a presently preferred embodiment of a method for matching two images of body-specific patterns, the images having partially overlapping content. The purpose of the method is to find the overlapping position that gives the best possible match between the content of the images and to assess the degree of concordance in this position. In order to determine what constitutes the best possible conformity, a predetermined assessment criterion is used.

I detta exempel genomförs sättet i mjukvara med hjälp av en 32-bitars processor med en klockfrekvens av 100 Mhz och med ett 16 kB cache-minne, i vilket bilderna som skall matchas lagras. Ett exempel på en processor av denna typ är StrongARM från Digital. Processorn arbetar under styrning av ett program som läses in i processorns programminne.In this example, the method is implemented in software using a 32-bit processor with a clock frequency of 100 Mhz and with a 16 kB cache memory, in which the images to be matched are stored. An example of a processor of this type is StrongARM from Digital. The processor operates under the control of a program that is loaded into the processor's program memory.

Hur bilderna tas upp och matas in i processorns cache-minne ligger utanför ramen för föreliggande uppfin- ning och beskrivs därför inte närmare. Ett sätt att är dock att använda samma teknik som i kända passersystem, nämligen att registrera bilderna med en ljuskänslig, två- dimensionell sensor och lagra dem i något minne, från vilket processorn kan läsa in bilderna till sitt cache- minne.How the images are captured and fed into the processor's cache is outside the scope of the present invention and is therefore not described in more detail. One way, however, is to use the same technology as in known access control systems, namely to register the images with a light-sensitive, two-dimensional sensor and store them in some memory, from which the processor can load the images into its cache.

I fig 1 visas schematiskt en digital bild l som består av ett flertal bildpunkter 2 av vilka några är schematiskt indikerade som rutor. Denna bild skall matchas mot en likadan bild med delvis samma innehåll.Fig. 1 schematically shows a digital image 1 which consists of a plurality of pixels 2, some of which are schematically indicated as squares. This image must be matched against a similar image with partly the same content.

Bilden är 55 bildpunkter bred och 76 bildpunkter hög. Den lagras som en bitmapp, varvid varje bildpunkt alltså har värdet ett eller noll. I detta exempel rep- resenterar värdet ett en svart punkt och värdet noll en vit punkt.The image is 55 pixels wide and 76 pixels high. It is stored as a bitmap, each pixel thus having the value one or zero. In this example, the value a represents a black dot and the value zero a white dot.

För genomförande av sättet delas varje bild in i elva grovsegment 3 i form av vertikala band, vilka var och en är fem bildpunkter breda och 76 bildpunkter höga.To carry out the method, each image is divided into eleven coarse segments 3 in the form of vertical bands, each of which is five pixels wide and 76 pixels high.

Varje grovsegment delas in i finsegment 4 som vart och ett består av en horisontell rad av fem angränsande bild- punkter.Each coarse segment is divided into fine segment 4, each of which consists of a horizontal row of five adjacent pixels.

Grovsegmenten 3 används för att definiera ett fler- tal grovförskjutningspositioner. I fig 2 visas en första grovförskjutningsposition, i vilken två bilder la och lb 10 15 20 25 30 513 058 ll är så förskjutna i förhållande till varandra att ett grovsegment 3, som markeras med snedstreckade linjer, från respektive bild överlappar varandra. I en andra grovförskjutningsposition kommer två grovsegment från respektive bild överlappa varandra osv. upp till en elfte grovförskjutningsposition i vilken samtliga grovsegment överlappar varandra. Skillnaden mellan två angränsande grovförskjutningspositioner är således ett grovsegment.The coarse segments 3 are used to define a plurality of coarse displacement positions. Fig. 2 shows a first coarse displacement position, in which two images 1a and 1b are so displaced relative to each other that a coarse segment 3, which is marked with oblique lines, overlaps each other from the respective image. In a second coarse offset position, two coarse segments from each image will overlap, and so on. up to an eleventh coarse displacement position in which all coarse segments overlap. The difference between two adjacent coarse displacement positions is thus a coarse segment.

I varje grovsegment definieras fyra finförskjut- ningspositioner. Dessa representerar en förskjutning i förhållande till en grovförskjutningsposition med en, två, tre resp fyra bildpunktskolumner.In each coarse segment, four fine displacement positions are defined. These represent a displacement in relation to a coarse displacement position with one, two, three and four pixel columns, respectively.

Grovförskjutnings- och finförskjutningspositionerna representerar förskjutningar mellan bilderna i en första riktning, nämligen i horisontell led. Om bilderna även kan vara förskjutna i förhållande till varandra i ver- tikal led definieras ett antal vertikalförskjutningsposi- tioner, varvid varje vertikalförskjutningsposition rep- resenterar en förskjutning med en bildpunktsrad i ver- tikal led. I fig 3 visas i den vänstra delen av figuren en vertikalförskjutningsposition för en första bild la och en andra bild lb, som är visad med streckade linjer i överlappningsläget.The coarse offset and fine offset positions represent offsets between the images in a first direction, namely in the horizontal direction. If the images can also be displaced in relation to each other in the vertical direction, a number of vertical displacement positions are defined, each vertical displacement position representing an displacement with a row of pixels in the vertical direction. Fig. 3 shows in the left part of the figure a vertical displacement position for a first image 1a and a second image 1b, which is shown in broken lines in the overlapping position.

Finsegmenten 4 används för att bestämma ett antal lO-bitars deladresser som i sin tur används för att hämta på förhand uträknade överlappningsbedömningsvärden, som vart och ett ger ett mått på graden av överensstämmelse mellan en eller flera överlappande bildpunkter för en viss förskjutningsposition. En första deladress bildas genom att de fem minst signifikanta bitarna till adressen hämtas från ett första finsegment 4a i den första bilden la och de fem mest signifikanta bitarna hämtas från mot- svarande överlappande finsegment 4b i den andra bilden lb. Den första deladressen representerar alltså värdet 10 15 20 25 30 35 513 058 12 för överlappande bildpunkter, som man vill jämföra för att kontrollera graden av överensstämmelse av innehållet.The fine segments 4 are used to determine a number of 10-bit sub-addresses which in turn are used to retrieve pre-calculated overlap judgment values, each of which provides a measure of the degree of agreement between one or more overlapping pixels for a particular offset position. A first subaddress is formed by retrieving the five least significant bits of the address from a first fine segment 4a in the first image 1a and the five most significant bits being retrieved from corresponding overlapping fine segments 4b in the second image 1b. The first subaddress thus represents the value of overlapping pixels, which one wants to compare to check the degree of conformity of the content.

I fig 3 visas ett exempel på hur det första finseg- mentet 4a om fem bitar ”lOOl0” hämtas från den ena bilden la och det andra finsegmentet 4b om fem bitar ”Oll0O” hämtas från den andra bilden lb och sätts samman till adressen ”Oll00lOOl0”.Fig. 3 shows an example of how the first fine segment 4a of five bits "100l0" is retrieved from one image 1a and the second fine segment 4b of five bits "Oll0O" is retrieved from the second image 1b and assembled to the address "Oll0010010 ”.

De första deladresserna används för att adressera två tabeller med vardera 1024 rader (antalet möjliga olika adresser). Tabellerna visas schematiskt som Tabell l och Tabell 2 i fig 4. I tabellerna, som liksom bilderna lagras i processorns cache-minne, finns på förhand uträk- nade överlappningsbedömningsvärden (nedan kallade poäng), vilket schematiskt visas i fig 4 genom en förstoring av en rad i vardera tabellen.The first subaddresses are used to address two tables with 1024 rows each (the number of possible different addresses). The tables are shown schematically as Table 1 and Table 2 in Fig. 4. In the tables, which like the images are stored in the processor's cache, there are pre-calculated overlap assessment values (hereinafter referred to as points), which is schematically shown in Fig. 4 by an enlargement of a row in each table.

I detta exempel är poängsättningen den följande. Två överlappande vita bildpunkter ger en poäng, två överlap- pande svarta bildpunkter ger två poäng, medan en vit och en svart överlappande bildpunkt ger noll poäng.In this example, the scoring is as follows. Two overlapping white pixels give one point, two overlapping black pixels give two points, while a white and a black overlapping pixel give zero points.

I fig 5 visas de poänger som lagras i tabellerna i fig 4 på raden med adressen ”Oll00lOOl0” och hur dessa beräknas. Poäng O lagras i Tabell 2 och Poäng 1-4 i Tabell l. För varje överlappande bildpunkt erhålles en poäng i enlighet med ovan angivna poängsättning. Poängen för alla överlappande bildpunkter summeras för åstadkom- mande av den totala poäng eller det överlappningsbedöm- ningsvärde som skall lagras i tabellen på raden med den aktuella adressen.Fig. 5 shows the points stored in the tables in Fig. 4 on the row with the address "Oll00lOOl0" and how these are calculated. Points 0 are stored in Table 2 and Points 1-4 in Table 1. For each overlapping pixel, one point is obtained in accordance with the above scoring. The score for all overlapping pixels is summed to achieve the total score or the overlap assessment value to be stored in the table on the row with the current address.

I Tabell 2 i fig 4 finns för varje adress lagrat den poäng (Poäng O) som erhålles när de båda finsegmenten överlappar varandra helt, dvs den överlappning som er- hàlles i grovförskjutningspositionen. Denna poäng är en summa av poängen för fem överlappande bildpunkter och är lagrad i en byte. I Tabell 1 finns för varje adress lag- som erhålles när de båda fin- rat de poänger (Poäng I-4) n l \ ÄB 10 15 20 25 30 35 513 05-8 13 segmenten förskjuts delvis i förhållande till varandra, dvs motsvarande olika finförskjutningspositioner. Dessa poänger lagras i var sin byte i ett 32-bitars ord och kan således hämtas samtidigt med en läsning eller ett tabell- uppslag under en klockcykel. Poäng 1 avser den poäng som erhålles när finsegmenten förskjuts ett steg i förhål- lande till varandra, så att bara fyra överlappande bild- punkter erhålles. Poäng 2 avser den poäng som erhålles när finsegmenten förskjuts två steg i förhållande till varandra, så att bara tre överlappande bildpunkter er- hålles osv. Förskjutningarna återspeglar den överlappning som erhålles i finförskjutningspositionerna mellan den aktuella grovförskjutningspositionen och följande grov- förskjutningsposition.In Table 2 in Fig. 4, for each address is stored the score (Score 0) obtained when the two fine segments completely overlap each other, ie the overlap obtained in the coarse displacement position. This score is a sum of the points for five overlapping pixels and is stored in one byte. In Table 1, for each address there is a law obtained when the two fines the points (Points I-4) nl \ ÄB 10 15 20 25 30 35 513 05-8 13 fine displacement positions. These points are stored in their respective bytes in a 32-bit word and can thus be retrieved at the same time as a reading or a table spread during a clock cycle. Score 1 refers to the score obtained when the fine segments are shifted one step in relation to each other, so that only four overlapping pixels are obtained. Score 2 refers to the score obtained when the fine segments are shifted two steps relative to each other, so that only three overlapping pixels are obtained, and so on. The offsets reflect the overlap obtained in the fine offset positions between the current coarse offset position and the following coarse offset position.

Såsom framgår av ovanstående avser de överlappnings- bedömningsvärden som hämtas med den första deladressen bara överlappningar mellan bildpunkterna i det första och det andra finsegmentet för de undersökta förskjutnings- positionerna. Överlappningarna som sker i dessa förskjut- ningspositioner mellan bildpunkterna i det första finseg- mentet och andra bildpunkter än de i det andra finsegmen- tet fångas inte upp med hjälp av ovan beskrivna förfa- rande.As can be seen from the above, the overlap assessment values obtained with the first subaddress refer only to overlaps between the pixels in the first and the second fine segment of the examined displacement positions. The overlaps that occur in these offset positions between the pixels in the first fine segment and pixels other than those in the second fine segment are not captured using the procedure described above.

För att kunna undersöka även dessa överlappningar bildas utöver den första deladressen även en andra del- adress. Denna andra deladress består av de fem bild- punktsvärdena i det första finsegmentet 4a och dessutom fem bildpunktsvärden för ett tredje finsegment 4c som gränsar till det andra finsegmentet i den andra bilden lb och som överlappar det första finsegmentet i den följande grovförskjutningspositionen.In order to be able to investigate these overlaps, a second sub-address is also formed in addition to the first sub-address. This second subaddress consists of the five pixel values in the first fine segment 4a and in addition five pixel values for a third fine segment 4c which adjoins the second fine segment in the second image 1b and which overlap the first fine segment in the following coarse displacement position.

I fig 6 visas ett exempel på hur den andra del- adressen bildas. Bildpunktsvärdena ”lO0l0” från det första finsegmentet 4a i den första bilden la utgör de fem mest signifikanta bitarna i den andra deladressen, “linan 10 15 20 25 30 35 513 058 14 medan bildpunktsvärdena ”l0lOl” från det tredje finseg- mentet 4c i den andra bilden lb utgör de fem minst sig- nifikanta bitarna i den andra deladressen.Fig. 6 shows an example of how the second sub-address is formed. The pixel values "101010" from the first fine segment 4a in the first image 1a constitute the five most significant bits in the second subaddress, the line 10 15 20 25 30 35 513 058 14 while the pixel values "10101" from the third fine segment 4c in the the second image 1b constitutes the five least significant bits in the second subaddress.

Poängen eller överlappningsbedömningsvärdena för de bildpunkter i det första och det tredje finsegmentet som överlappar varandra i olika förskjutningspositioner, lagras i en tredje tabell, som i fig 7 betecknas Tabell 3. Poängen räknas givetvis ut pà samma sätt som i fallet med Tabell l, men poängen lagras i ”omvänd ordning”. I den första byten på en tabellrad i Tabell 3 lagras näm- ligen Poäng 4, som avser en överlappande bildpunkt mellan det första och det tredje finsegmentet. I den andra byten lagras Poäng 3, som avser två överlappande bildpunkter mellan det första och det tredje finsegmentet osv.The points or overlap assessment values for the pixels in the first and third fine segments that overlap each other in different displacement positions are stored in a third table, which in Fig. 7 is called Table 3. The points are of course calculated in the same way as in the case of Table 1, but the points stored in "reverse order". In the first change on a table row in Table 3, namely Point 4 is stored, which refers to an overlapping pixel between the first and the third fine segment. In the second change, Point 3 is stored, which refers to two overlapping pixels between the first and the third fine segment, and so on.

Med hjälp av den första och den andra deladressen kan man på detta sätt hämta överlappningsvärden för fyra finförskjutningspositioner. Genom att summera'överlapp- ningsvärdena för den första och den andra deladressen får man fram ett överlappningsvärde för varje förskjutnings- position. Vart och ett av dessa överlappningsvärden avser fem överlappande bildpunkter för den aktuella förskjut- ningspositionen.With the help of the first and the second subaddress, it is possible in this way to retrieve overlap values for four fine displacement positions. By summing the overlap values for the first and the second subaddress, an overlap value is obtained for each offset position. Each of these overlap values refers to five overlapping pixels for the current offset position.

I fig 7 visas Tabell l och Tabell 3, en första och en andra deladress som används för att adressera dessa tabeller och överlappningsbedömningsvärdena på varsin rad i tabellen.Fig. 7 shows Table 1 and Table 3, a first and a second subaddress used to address these tables and the overlap assessment values on each row in the table.

I det följande beskrivs hur matchningen mellan bil- derna utförs. Först väljs en första grovförskjutnings- position. För denna position väljs ett första par av överlappande finsegment. Antag att det första finseg- mentet i den första bilden har bildpunktsvärdena ”lO010” och att det andra finsegmentet i den andra bilden har bildpunktsvärdena ”OllOO”, såsom i exemplet i fig 3.The following describes how the matching between the images is performed. First, a first coarse displacement position is selected. For this position, a first pair of overlapping fine segments is selected. Assume that the first fine segment in the first image has the pixel values “1010” and that the second fine segment in the second image has the pixel values “OllOO”, as in the example in Fig. 3.

Dessa värden används för att bilda den första binära deladressen ”OllO0lO0lO”. Antag vidare att ett tredje 10 15 20 25 30 35 513 058 15 finsegment som gränsar till det andra finsegmentet i den andra bilden har värdena "lO10l”. Dessa värden används för att tillsammans med bildpunktsvärdena för det första finsegmentet bilda den andra deladressen ”lO0lOlOl0l”.These values are used to form the first binary subaddress "OllO0lO0lO". Assume further that a third fine segment adjacent to the second fine segment in the second image has the values "10101", these values are used together with the pixel values of the first fine segment to form the second subaddress "101010101010" .

Den första deladressen används för att adressera både den första och den andra tabellen. Från den första tabellen fås i det givna exemplet poängerna 4, 3, O och 1 lagrade i ett ord och från den andra tabellen erhålles poängen 1.The first subaddress is used to address both the first and second tables. From the first table in the given example the points 4, 3, 0 and 1 are obtained stored in one word and from the second table the point 1 is obtained.

Den andra deladressen används för att adressera den tredje tabellen, från vilken poängerna 2, 0, 3, 3 fås i det givna exemplet. Poängerna summeras parallellt, varvid 4 erhålles.The second subaddress is used to address the third table, from which scores 2, 0, 3, 3 are obtained in the given example. The points are summed in parallel, whereby 4 are obtained.

När dessa första överlappande finsegment har jäm- totalpoängerna 6, 3, 3, förts med varandra, fortsätter matchningen med två nya överlappande finsegment, tills en fullständig jämförelse mellan det eller de överlappande grovsegmenten har ut- förts.When these first overlapping fine segments have the total points 6, 3, 3, added together, the matching continues with two new overlapping fine segments, until a complete comparison between the overlapping coarse segment or segments has been performed.

Varje gång ett ord erhålles med de fyra summerade poängerna för två deladresser adderas ordet till tidigare erhållna ord. Poängen för fyra olika förskjutningsposi- tioner adderas alltså parallellt genom en enda addition.Each time a word is obtained with the four summed points for two subaddresses, the word is added to previously obtained words. The points for four different offset positions are thus added in parallel by a single addition.

Eftersom poängen är låga kan ett stort antal additioner genomföras innan det uppkommer någon överföringssiffra (carry) och innan någon undanlagring på annan plats så- ledes behöver göras. Poängen från den andra tabellen adderas på motsvarande sätt. I fig 8 visas schematiskt hur poängen för fyra förskjutningspositioner adderas parallellt, varvid ordet A representerar det ord som erhålles med en första adress, bestående av en första och en andra deladress, och ordet B representerar det ord som erhålles med en andra adress, bestående av en första och en andra deladress, och ordet C den erhållna summan.Since the points are low, a large number of additions can be made before any carry figure (carry) arises and before any storage elsewhere needs to be done. The points from the second table are added accordingly. Fig. 8 shows schematically how the score for four offset positions is added in parallel, the word A representing the word obtained with a first address, consisting of a first and a second subaddress, and the word B representing the word obtained with a second address, consisting of a first and a second subaddress, and the word C the sum obtained.

När samtliga överlappande finsegment har undersökts för den första grovförskjutningspositionen, upprepas förfarandet för den andra och följande grovförskjutnings- 10 15 20 25 30 513 058 16 positioner tills samtliga grovförskjutningspositioner undersökts.Once all the overlapping fine segments have been examined for the first coarse displacement position, the procedure for the second and subsequent coarse displacement positions is repeated until all the coarse displacement positions have been examined.

Om bilderna även kan vara förskjutna i vertikal led i förhållande till varandra, upprepas sättet för varje vertikalposition, varvid bilderna alltså först förskjuts en rad i förhållande till varandra i vertikal led och därefter samtliga grovförskjutnings~ och finförskjut- ningspositioner undersöks, varefter bilderna förskjuts till nästa vertikalförskjutningsposition och undersöks och så vidare tills samtliga vertikalförskjutningsposi- tioner har avsökts.If the images can also be displaced in vertical direction relative to each other, the method for each vertical position is repeated, whereby the images are first displaced one row relative to each other in vertical direction and then all coarse displacement and fine displacement positions are examined, after which the images are displaced to the next vertical displacement position and examined and so on until all vertical displacement positions have been scanned.

När samtliga förskjutningspositioner har undersökts har man erhållit en poängsumma för varje position. Med det bedömningskriterium som används i detta exempel rep- resenterar då den största poängsumman den förskjutnings- position som ger den bästa överlappningen mellan inne- hållet i bilderna. Om en första bild jämförs med flera andra bilder anger den poängen den andra bild som bäst överensstämmer med den första bilden.When all displacement positions have been examined, a score has been obtained for each position. With the assessment criterion used in this example, the largest score then represents the offset position that gives the best overlap between the content in the images. If a first image is compared to several other images, that score indicates the second image that best matches the first image.

I ett för närvarande föredraget utförande av uppfin- ningen utförs först en överlappningsbedömning på det ovan beskrivna sättet med en grövre upplösning hos bilderna än den med vilken de är lagrade. I detta exempel används en upplösning av 25 x 30 bildpunkter. Syftet med detta är att man snabbt ska välja ut relevanta förskjutningsposi- tioner för noggrannare undersökning av överensstämmelsen mellan innehållet i bilderna. Därefter upprepas sättet för bilderna i dessa och angränsande förskjutningsposi- tioner för den ursprungliga upplösningen.In a presently preferred embodiment of the invention, an overlap assessment is first performed in the manner described above with a coarser resolution of the images than the one with which they are stored. In this example, a resolution of 25 x 30 pixels is used. The purpose of this is to quickly select relevant offset positions for more thorough examination of the correspondence between the contents of the images. Then repeat the procedure for the images in these and adjacent offset positions for the original resolution.

I ovanstående exempel lagras överlappningsbedöm- ningsvärdena i tre olika tabeller. Detta har skett för att utnyttja den använda processorn på ett optimalt sätt.In the above example, the overlap assessment values are stored in three different tables. This has been done to utilize the processor used in an optimal way.

För andra processorer kan det vara lämpligt att istället lagra alla överlappningsvärdena i en tabell eller i fler 513 058 17 än tre tabeller. Fackmannen kan göra denna bedömning med utgångspunkt från beskrivningen ovan.For other processors, it may be appropriate to store all the overlap values in one table or in more than three tables instead. Those skilled in the art can make this assessment based on the description above.

Claims

n, 10 15 20 25 30 35 513 058 18 PATENT REQUIREMENTS

A method of matching two images of body-specific patterns, each image consisting of a plurality of pixels and having partially overlapping content, the degree of correspondence between the contents of the images being determined for different offset positions representing different overlaps between the images, including the steps of determining a plurality of numbers for each of a plurality of displacement positions, each of which is formed by means of pixel values from both images, - using each of the numbers to simultaneously obtain predefined overlap assessment values for at least two displacement positions, and - use the overlap assessment values when determining the degree of correspondence between the images for the different displacement positions.

The method of claim 1, further comprising the steps of summing the overlap judgment values for each of said offset positions, and using the sums thus obtained to determine which of the offset positions gives the best possible match between the contents of the images. .

A method according to claim 1 or 2, wherein the overlap assessment values are summed in parallel for a plurality of displacement positions.

A method according to any one of the preceding claims, wherein some of the overlap assessment values refer to more than one overlapping pixel.

A method according to any one of claims 1-4, wherein said plurality of displacement positions for which the numbers are determined constitute coarse displacement positions and said at least two displacement positions for which overlap assessment values are retrieved comprise at least one fine displacement ïtšííC - lï-fšv-SG 16:31 , \ s-: nlzn-pciff- (I-1 '= g:' o11p; $ ï.patïïcïllnnsxl ﬁ l; \ p2972503.Li:> <~ 10 15 20 25 30 513 058 19 position representing a smaller displacement from a coarse displacement position than the displacement between two coarse displacement positions.

The method of claim 5, wherein the coarse offset positions represent different overlaps between the images in a first direction and further comprising the step of repeating the method of different overlaps between the images in a second direction.

A method according to claim 5 or 6, wherein the coarse displacement positions are determined by dividing the images into a plurality of coarse segments consisting of N x M pixels where N and M are greater than one, the displacement between two adjacent coarse displacement positions being a coarse segment.

A method according to any one of the preceding claims, wherein the images consist of bitmaps.

A method according to any one of the preceding claims, wherein the numbers constitute addresses of memory locations which store said overlap assessment values which consist of pre-calculated values.

The method of claim 9, wherein the addresses are used to address at least one look-up table which, for each address, contains the pre-calculated overlap assessment values for at least two offset positions.

11. ll. A method according to claim 10, which method is performed by means of a processor operating with a predetermined word length and wherein said at least one look-up table comprises a plurality of addressable rows, each having the predetermined word length and storing said predetermined overlap assessment values.

A method according to claim 11, wherein the storage of the overlap assessment values is performed in such a way that all the overlap assessment values and the images to be matched are stored in a cache memory in the processor. EDC-C 6G 16: 31 \\ s-mlm-pdc ~~ 0l \ _g: 'oz: pss: 5'apatïcš ﬂ tins' ~ _lS “> 9TI \ p29? 3 * (33 .zioc 10 15 20 25 30 35 513 058 20

A method according to any preceding claim, further comprising the step of forming each number of a first fine segment comprising at least two contiguous pixel values from the first image, and of a second fine segment overlapping the first fine segment and comprising equal numbers adjacent pixel values as the first fine segment from the second image, and of a third fine segment comprising as many contiguous pixel values as the first fine segment from the second image and overlapping the first fine segment in an adjacent offset position for which the determination of a multiple speeches are performed.

The method of claim 13 in combination with claim 9, wherein each address is divided into a first and a second subaddress, the first subaddress consisting of the pixel values from the first and second fine segments being used to simultaneously retrieve overlap assessment values in a first table for overlapping pixels belonging to the first and the second fine segment, and wherein the second subaddress, which consists of the pixel values from the first and the third fine segment, is used to retrieve overlap assessment values in a second table at the same time. for overlapping pixels belonging to the first and third fine segments.

The method of claim 14, wherein the first and second tables, for each address, store an overlap assessment value for each of said at least two offset positions, and wherein the sum of the overlap assessment values for a first offset position is retrieved by an address first and second subaddresses constitute an overlap assessment values for all overlapping pixels between the first, second and third fine segments of said first offset position. 20 00 C- 3 - 30 16: 31 * As-: nlzxz - pdc- 0l \ gro1: ',> s $ “-. Pat \ c“: 1' \ _: ~ :: 1: ~: \ - ._l'-: Qf-ïp ﬁ # 372 S 03.410: m! 10 15 513 058 21

A method according to any one of the preceding claims, wherein the degree of correspondence between the images is first determined by a first resolution of the images for selecting a plurality of displacement positions, and then determined by a second, higher resolution of the images for the selected displacement positions and adjacent displacement position. - tioner.

Device for matching two images, each of which consists of a plurality of pixels and which has partly overlapping content, characterized by a processor unit which is arranged to carry out a method according to any one of claims 1-16.

Device for matching two images, each consisting of a plurality of pixels and having partially overlapping contents, which device comprises a memory medium, which can be read by means of a computer and on which year a computer program for carrying out the method according to any one of claims 1-16. Eøtï-U-üiš SC- lézïšl Näs-mir. ~ Pdc-Glïgrotpsgšäpar \ <: n \ zans \ 1997 \ p2972SOIš.cíoc