NO861936L - Anordning for bestemmelse av konsistens hos en egenskap for et omraade av et bilde oppdelt i diskrete billedelementer - Google Patents

Description

Foreliggende oppfinnelse vedrører en anordning for på en lett og pålitelig måte å detektere graden av konsistens hos en egenskap for et område i et digitalisert bilde.

Ved tolkning av innholdet i digitaliserte bilder utgjør detektering av regioner et viktig skritt i analysen. Disse regioner karakteriseres typisk av at en eller flere egenskaper innenfor de samme er relativt konstante eller varierer på en forhåndsbestemt måte, dvs. er konsistente innenfor regionene. Slike egenskaper kan f.eks. være lokalt dominerende orientering, lokal spatial frekvens, graden av kurvatur eller en beskrivelse av teksturegenskaper/-parame-tere .

Detektering av regioner innebærer i prinsipp en integrasjon eller summering. Det finnes således store muligheter for at en slik karakterisering kan gjøres relativt robust, dvs.

utsagnene blir stabile og ikke beroende på tilfeldige vari-asjoner såsom støy. Et problem har hittil vært at karakterisering av varisjon innebærer differensiering, hvilket er en særlig støyfølsom operasjon. Det har derfor vært vanske-lig å skille mellom lavnivåstøy i bildet og karakteriserende egenskaper som ikke er stabile.

Foreliggende oppfinnelse skriver seg fra forskning innenfor de områder som berører datorisert billedanalyse. Litteratu-ren innenfor dette område beskriver diverse ulike algoritmer, som henfører seg til de problemer som løses ved hjelp av denne oppfinnelse. Den signalbehandling som utføres av foreliggende oppfinnelse skulle liksom disse algoritmer i prinsipp kunne utføres av en generell dator. Alle slike implementeringer har dog den ulempen at bearbeidelsen ikke er realisert i maskinvare, men krever et program av en eller annen type. Som følge av dette blir bearbeidelsestider som er aktuelle, urimelig lange for alle tilpasninger av inte-resse .

Foreliggende oppfinnelse- vedrører således et tilbud av en anordning som raskt og pålitelig tilveiebringer slik detek tering av graden av konsistens hos en egenskap i et bilde oppdelt i diskrete billedelementer.

De kjennetegnende særtrekk for oppfinnelsen fremgår av de vedføyde patenkrav.

Det har vist seg at en slik anordning ved de spesielle tilpasninger som her vedrøres, kan være tusentalls ganger ras-kere enn en generell dator.

Oppfinnelsen skal i det følgende beskrives nærmere med hensyn til en anordning for undersøkelse av et lokalt område i et bilde oppdelt i diskrete billedelement. Et fullstendig system kan enten inneholde en mengde slike enheter som ar-beider parallelt med ulike delområder av bildet, eller en eneste enhet som suksessivt skal analysere hvert delområde av bildet. Disse delområder kan delvis overlappe hverandre.

For å forenkle beskrivelsen forutsettes det her at de egenskaper som det skal legges merke til, er representert i form av todimensjonelle vektorer, en for hvert billedelement. I et mer generelt tilfelle kan dog antallet dimensjoner være større enn to. Disse vektorer representerer en egenskap, f.eks. dominerende orientering av strukturer i bildet. Vektorene kan i det to-dimesjonelle tilfellet også betraktes som kompleksverdi-signaler. Hver vektor er laget slik at dens retning beskriver den dominerende orientering-en hos en struktur i bildet, mens vektorens lengde representerer sikkerheten i angivelsen av denne retningen. Denne vektorrepresentasjon av bildet kan oppnås f.eks. gjennom transformasjon av det opprinnelige digitaliserte bildet, i hvilket hvert billedelement kan være tildelt et gråskalani-vå eller et intensitetsnivå kombinert med en fargekode, i overensstemmelse med de prinsipper som beskrives i "IEEE TRANSACTIONS ON COMMUNICATIONS", VOL. COM-31, nr 3, mars 1983, side 388-406.

Den anordning som den foreliggende oppfinnelse løser de ovenfor angitte problemer med, kan kort karakteriseres som en kombinasjon av tre hovedenheter. En enhet vurderer vektorsummen av vektorene innenfor det betraktede området. En annen enhet vurderer summen av nevnte vektorers størrelser. En tredje enhet normerer til slutt det første utsagn med hensyn til det andre.

Oppfinnelsen kommer nå til å bli beskrevet nedenfor under henvisning til de vedføyde tegninger, hvor

fig. 1 illustrerer den aktuelle problemsituasjonen,

fig. 2 viser et blokkskjema av anordningen ifølge foreliggende oppfinnelse,

fig. 3 viser et mer detaljert blokkskjema av enheten for vektorsummen på fig. 2,

fig. 4 viser et mer detaljert blokkskjema av enheten for summering av vektorstørrelsen på fig. 2,

fig. 5 viser en mer detaljert illustrasjon av normeringsenheten på fig. 2,

fig. 6 viser et blokkskjema av enheten for vektorsummering i en alternativ utførelsesform av anordningen ifølge fig. 2,

fig. 7 viser et blokkskjema av enheten for summering av vektorstørrelser i den alternative utførelsesform av anordningen ifølge fig. 2,

fig. 8 viser et blokkskjema av normeringsenheten i den alternative utførelsesformen av anordningen ifølge fig. 2,

fig. 9-14 viser videreutviklinger av ovenfor nevnte utfø-relsesformer, og

fig. 15 - 16 viser deler av alternative, analoge utførel-sesformer av foreliggende oppfinnelse. Fig. 1 illusterer den aktuelle problemsituasjonen. Et område 1 med en konstant eller konsistent egenskap, f.eks. rep-resenterende en viss orientering hos strukturer innenfor området, erkarakterisertav vektorer med samme retning. Et område 2 med uregelbundet varierende eller ikke-konstante egenskaper innebærer at de krakteriserende vektorene har en orientering som varierer mer eller mindre tilfeldig. Problemsituasjonen er den at det erønskelig på en rask og pålitelig måte å kunne skille områder av type 1 fra områder av type 2. Det er således ønskelig å kunne vurdere graden av konsistens (i dette tilfellet konstans) hos egenskapen innenfor et område. Fig. 2 viser et blokkskjema av en anordning i overensstemmelse med foreliggende oppfinnelse. Figuren viser et område 3 av karakteriserende vektorer, svarende til et delområde eller vindu av et ifølge ovenstående transformert bilde oppdelt i diskrete billedelement, innenfor hvilket en må-ling skal gjennomføres. Dette område kan typisk inneholde 11 x 11 todimensjonelle vektorer. Selvfølgelig er også andre størrelser på området, f.eks. 15 x 15 vektorer muli-ge. Området bør dog inneholde minst 3x3 vektorer for å oppnå et meningsfylt resultat. Verdiene av vektorkomponen-tene innenfor dette område avføles av to ulike måleenheter 4 og 5. Utgangsresultatene fra disse to måleenheten sammen-lignes siden i en normeringsenhet 6, hvorved utgangssignal-et fra enheten 4 normeres med hensyn til utsignalet fra enheten 5. Denne normeringsenhet avgir et signal 7, hvis

størrelse karakteriserer graden av konstans hos egenskapen innenfor det aktuelle området og hvis fase karakteriserer middelverdien av vektorretningene innenfor området.

En første utførelsesform av anordningen ifølge fig. 2 kommer nå til å bli beskrevet under henvisning til fig. 3-5.

Fig. 3 viser mer i detalj enheten 4 for vektorsummering på fig. 2. Det forutsettes her at de ulike vektorer som fore-kommer innenfor en omgivelse omkring "målepunktet", er representert av komponentenes størrelse og fase. Ved digital representasjon kan f.eks. størrelsen representeres av et tall mellom 0 og 255, dvs. en bitgruppe (byte). På samme måte kan også fasevinkelen representeres av en bitgruppe. Herigjennom kommer hvert billedelement til å få tildelt to bitgrupper i et minne, hvilke representerer den vektor som tilhører billedpunktet. Dersom annen digital oppløsning øn-skes, er selvfølgelig andre tildelinger av minner tenkbare. Informasjonene kan også være representert i analog form, f.eks. som en spenning eller strøm. Det forutsettes også at en hensiktsmessig mekanisme, f.eks. som en adressegenerator, fra minnet stiller de aktuelle vektorverdier til disposisjon for en omgivelse omkring målepunktet. Anordninger for å tilveiebringe dette representerer dog velkjent teknikk og utgjør ikke gjenstanden for denne søknad. Fasever-dien 8 for en vektor føres til en oppslagstabell 9 for cosinus og en oppslagstabell 10 for sinus. De derved oppnådde verdier går til hver sin multiplikator 11 respektive 12. Som ytterligere inngangssignal til hver sin multiplikator foreligger vektorstørrelsen 13. Utgangssignalene fra multiplikatorene går til hver sin adderer 14 respektive 15, hvilke er tilkoblet for å arbeide som summatorer. Som ut-gangssignal fra hver sin summator oppnåes verdier som representerer realdelen respektive imaginærdelen, eller alternativt uttrykt x- respektive y-komponenten av summen av vektorene innenfor ovenfor angitte omgivelse.

De således oppnådde vektorkomponentsignaler føres til en omformer fra rektangulært til polart format, hvorved resul-tatet antar formen størrelse 16 og vinkel 17. Fig. 4 viser mer i detalj oppbyggingen av enheten for summering av vektorstørrelsen innenfor den betraktede omgivelsen. Det tidligere nevnte størrelsessignal 13 føres til en adderer som er tilbakekoblet for å tjene som summator. Ut-gangssignalet 18 fra denne kommer til å representere summen av alle vektorstørrelser innenfor den betraktede omgivelsen . Fig. 5 viser mer i detalj normeringsenheten 6 på fig. 2. Enheten består i sin grunnleggende form av en divisjonsen-het, i hvilken vektorsummens størrelse 16 divideres med summen 18 av størrelsene av de enkelte vektorene. Dette gir en normalisert utgangsstørrelse 19. Sammen med den tidligere oppnådde fasevinkelen 17 gir dette en beskrivelse av hvordan de konstante egenskapene er innenfor det betraktede område omkring målepunktet respektive den veiete middelverdien av vektorenes retningen innenfor området.

Ovenfor er det beskrevet hvordan et mål på graden av en konstans hos en egenskap i et området omkring et målepunkt, noe som tilsvarer et billedelement i det opprinnelige bilde, oppnåes med en utførelsesform av anordningen ifølge den foreliggende oppfinnelse. På tilsvarende måte kan også øv-rige billedelementer i bildet undersøkes med hensyn til graden av konstans hos nevnte egenskap i omgivelsene omkring disse billedelementer. Dette kan enten skje ved at en anordning suksessivt søker å forflytte bildet av"vinduet" til omgivelser som tilhører nye billedelement, eller ved at flere anordninger parallelt avsøker omgivelser omkring ulike billedelement.

Ved den ovenfor beskrevne utførelsesform representeres vektorene i et polart format. Alternativt kan de betraktede vektorer være representert av komponenter i rektangulært format, der den ene komponenten tilsvarer realdelen og den andre komponenten tilsvarer imaginærdelen av et kompleksverdi-signal, eller alternativt uttrykt x- respektive y-komponenten ev et vektorverdi-signal. Det forutsettes også for denne implementering at en hensiktsmessig makanisme, f.eks. en adressegenerator, fra et minne stiller de aktuelle vektorverdier til disposisjon for en omgivelse omkring målepunktet. Blokkskjemaet på fig. 2 er også i dette tilfellet hensiktsmessig for anordningen.

Den alternative utførelsesformen for oppfinnelsen kommer nå til å bli beskrevet mer i detalj under henvisning til fig. 6-8. Fig. 6 viser oppbyggingen av den nå anvendte enheten 4 for vektorsummering. Vektorenes realdel eller x-komponent 20 og imaginærdel eller y-komponent 21 går til hver sin adderer 22 respektive 23 koblet som summatorer. Disse gir som utsignal summen av realdeler 24 og imaginærdeler 25 av vektorer innenfor den betraktede omgivelsen. Fig. 7 viser oppbyggingen av enheten for summering av vek-torstørrelser innenfor den betraktede omgivelsen. Realdelen eller x-komponenten 26 og imaginærdelen eller y-komponenten 27 føres til hver sin multiplikator 28 respektive 29 koblet som kvadrerere. Utsignalene fra disse går via en adderer 30 og via en enhet 32, som genererer kvadratroten fra disse komponenter, og inn til en adderer koblet som summator 31. Denne kommer til å anvende summen 33 av vektorenes størrel-ser.

Fig. 8 viser enheten 6 på fig. 2 for sammenligning av de to typene av vektorsummer for den aktuelle representasjon. De tidligere oppnådde summene av realdeler 24 og imaginærdeler 25 føres til hver sin normeringsenhet 34 respektive 35. Der divideres de samme med den tidligere oppnådde vektorstør-relsesummen 33. De derved oppnådde utsignalene 36 og 37 ut-gjør i rektangulære komponenter denønskede beskrivelse av hvordan den konstante egenskap er innenfor den observerte regionen samt den veiete gjennomsnittsverdien av vektorens retninger.

Nedenfor beskrives der noen videreutviklinger av oppfinnelsen under henvisning til fig. 9 - 14.

I mer generelle tilfeller kan det være ønsket at den ovenfor bekrevne målingen skjer med en viss veiing av de vektorverdier som finnes innenfor den betraktede omgivelse. Dette vises på fig. 9 i sammenheng med enheten 4 på fig. 2. For dette formål kan de innkommende verdiene 13 i en multiplikator 39 multipliseres med vektkoeffisientene lagret i et minne 38 før summeringen utføres. Disse koeffisienter kan være av kompleksverdi. Kompleksverdi-koeffisienter har den fordelen at de dels gir opphavet til en ren skalering og dels en vridning av vektorene før summeringen. Dette gir større fleksibilitet når det gjelder typer av egenskaper som kan detekteres. Den ekstra vridningsmuligheten gjør det nemlig mulig å detektere området i hvilket vektorene er innbyrdes vridd på en forhåndsbestemt måte.

Samme type av funksjon vises på fig. 10 i sammenheng med enheten 5 på fig. 2. For dette formål kan de innkommende verdier 13 i en multiplikator 40 multipliseres med vektkoeffisientene lagret i et minne 41 før summeringen utfø-res. I visse tilfeller kan minnene 38 og 41 utgjøre samme enhet.

Det innses at den tidligere beskrevne målingen utgjør et spesialtilfelle av veiingen med vektkoeffisinentene likt

med 1. Dette svarer til det tilfelle da man ønsker å detektere hvorvidt vektorene innenfor måleområdet er parallelle. Ønsker man derimot å detektere hvorvidt vektorene "roterer" på en forhåndsbestemt måte innenfor område, kommer koeffi-sientene til å være komplekse, idet vridningen av hver vektor i den forhåndsbestemte "målemasken" med hensyn til f. eks. x-akselen skyldes kompleksverdi-koeffisientenes verdi.

I det generelle tilfelle da den betraktede egenskapen representeres av en n-dimensjonal vektor, der n>2, utgjøres kompleksverdi-veiefaktorene i stedet av n x n matriser, hvilke kan vri og skalere vektorene i et n-dimensjonelt vektorrorn.

I dette mer generelle tilfelle suppleres anordningen også med et ytterligere element. Således suppleres f.eks. anordningen ifølge fig. 6 med ytterligere summatorer 22, 23 inn-til antallet summatorer svarer til antallet dimensjoner n. På lignende måte suppleres anordningen ifølge fig. 7 med ytterligere kvadrerere.

Normeringen kan i noen tilfeller bli støyfølsom, f.eks. når informasjonen består av signaler med liten størrelse. Det er da hensiktsmessig at normeringen gjøres i relasjon til et visst basenivå i form av et tilleggssignal 43 som i en adderer 42 adderes til summasjonssignalet 18 for vektor-størrelsene, slik det vises på fig. 11. Også her innses det at den tidligere beskrevne målingen utgjør et spesialtilfelle, nemlig det tilfelle der basisnivået eller referansesignalet er lik 0.

De ovenstående videreutviklinger av oppfinnelsen gjelder for vektorer i polart format. De kan også implementeres for rektangulært format, slik det er vist på fig. 12 - 14. Vektkoeffisientminnene 44 og 47 avgir her tilsvarende vekt-koeffisienter eller matriser, med hvilken hjelp signalene 20, 21 respektive 26, 27 veies i multiplikatorer 45, 46 respektive 48, 49. På analog måte som ovenfor kan også basisnivået 51 i en adderer 50 adderes til signalet 33.

Den tidligere beskrevne implementeringer henfører seg fram-for alt til digital teknikk, hvorved billedelementenes vektorer er representert i digital form. De angitte funksjoner kan dog med fordel utføres også i analog teknikk. De strukturer som blir spesielle for denne implementasjonsform, er gjengitt på fig. 15 og 16.

Ifølge fig. 15 summerer den første summeringsenheten 4 alle realdeler 20 og imaginærdeler 21 av vektorene multiplisert med respektive vektfaktorer implementert av motstandsnett 52, 53 eller multipliserende D/A-omformere styrt av digita-le styresignaler 54, 55, hvoretter signalene føres videre til summatorer 56, 57. Multiplikasjonen kan ses som en av-speiling av Ohms lov. Fordelen med multipliserende D/A-omformere er at den resulterende resistansverdi som svarer til multiplikasjonfaktoren, er innstillbar gjennom et digi-talt styresignal.

Ifølge fig. 16 summerer den andre summeringsenhet 5 alle komponenter av størrelsessignalet 13 av vektorene multiplisert med vektfaktorer implementert av motstandsnett 60 eller multipliserende D/A-omformere styrt av styresignaler 61, hvoretter signalene føres videre til en summator 62, f.eks. en tilbakekoblet operasjonsforsterker.

Ved utførelsesformen ifølge fig. 15 og 16 forutsettes det at signalene er tilgjengelige dels som real- og imaginærdel, dels som størrelse. Dette gir en særdeles enkel oppbygning av anordningen. Under de samme forutsetninger kan også enhetene ifølge fig. 4 og 6 kombineres. Det innses således at det kan være ønskelig å lagre billedsignalene dels i rektangulær form, dels i polar form, eller i tillegg til den rektangulære formen i det minste å lagre vektorstørrel-sene. Det ekstra behov for minne dette gir opphav til, kom-penseres av anordningens forenklede oppbygning. Dette gjelder i særdeleshet om hele eller store deler i bildet skal undersøkes i et trinn i flere parallelt arbeidende anordninger .

Som det framgår av den ovenstående beskrivelse, kan anordningen ifølge foreliggende oppfinnelse varieres på flere måter. Bare et fåtall eksempler på tilgjengelige muligheter er blitt beskrevet her. Oppfinnelsens ramme bør således ikke betraktes som begrenset til disse eksempler, men bør i stedet omfatte det som er beskrevet i de vedføyde patent-krav.

Claims (15)

1. Anordning for bestemmelse av graden av konsistens hos en egenskap for et område av et bilde oppdelt i diskretet billedelementer, hvorved denne egenskap representeres av vektorverdi-signaler, et for hvert billedelement, med vek-torretningen beskrivende egenskapens type og vektorstørrel-sen beskrivende sikkerheten i egenskapsutsagnet, karakterisert ved en første enhet (4) for veiet summering av vektorene innenfor området etter forhåndsbestemte vridninger av disse, en andre enhet (5) for veiet summering av størrelsene av vektorene innenfor området, og en normeringsenhet (6) for normering av utsignalene fra den første summeringsenheten (4) med hensyn til summen av utsignalene fra den andre summeringsenheten (5) og et refe-ransesignal (43, 51, p).

2. Anordning som angitt i krav 1, karakterisert ved at den første enheten (4) omformer vektorenes fasesignal (8) til cosinus- og sinuskomponenter, som er tilført på den ene inngangen til hver sin multiplikator (11, 12), på hvis andre inngang størrelsessignalet (13) av tilsvarende vektor ligger, og at resulterende produkter er tilført en inngang til hver sin adderer (14, 15), som begge er tilbakekoblet for å tjene som summatorer, hvoretter det oppnådde vektorverdi-signalet er tilført en enhet som utfø-rer en omforming fra rektangulære til polare koordinator (16, 17) (fig.3).

3. Anordning som angitt i krav 2, karakterisert ved at den første enheten (4) innledes med en multiplikator (39) for multiplikasjon av størrelsessignalet (13) med vektfaktorer hentet fra et minne (38), hvoretter signalet føres videre til multiplikatorene (11,12) (fig.9).

4. Anordning som angitt i krav 1, k a r a k t e r i -• sert ved at den første summeringsenheten (4) summerer den første respektive den andre komponenten (20, 21) av vektorene i hver sin adderer (22, 23), hvilke er tilbakekoblet for å tjene som summatorer (fig. 6).

5. Anordning som angitt i krav 4, karakterisert ved at den første enheten (4) innledes med multiplikatorer (45, 46) for multiplikasjon av den første respektive den andre komponenten (20, 21) av vektorene med vektfaktorer hentet fra et minne (44), hvoretter signalene føres videre til addererne (fig. 12).

6. Anordning som angitt i krav 1, karakterisert ved at den første summeringsenheten (4) summerer alle første respektive andre komponenter (20, 21) av vektorene multiplisert med respektive vektfaktorer (52, 53) implementert av motstandsnett eller styrte (54, 55) multipliserende D/A-omformere, hvoretter signalene føres videre til summatorer (56, 57) (fig. 15).

7. Anordning som angitt i et av de foregående krav, karakterisert ved at den andre summeringsenheten (5) fører størrelsessignalet (13) til en inngang til en adderer tilbakekoblet for å tjene som summator, fra hvis utgang normeringssignalet (18) fremskaffes (fig.

4) .

8. Anordning som angitt i krav 7, karakterisert ved at den andre enheten (5) innledes med en multiplikator (40) for multiplikasjon av størrelsessignalet (13) med vektfaktorer hentet fra et minne (41), hvoretter signalet føres videre til den som summator tilbakekoblede addereren (fig. 10).

9. Anordning som angitt i et av kravene 1-6, karakterisert ved at den andre enheten (5) summerer alle komponenter av størrelsessignalet (13) av vektorene multiplisert med vektfaktorer (60) implementert av motstandsnett eller styrte (61) multipliserende D/A-omformere, hvoretter signalene føres videre til summatorer (62) (fig. 16).

10. Anordning som angitt i et av kravene 1-6, karakterisert ved at i den andre summeringsenheten (5) er komponentene av vektorene tilført begge inngangene til hver sin multiplikator (28, 29) for kvadre-ring, hvoretter de kvadrerte signalene summeres i en adderer (30), det oppnådde signalet er tilført en enhet (32) som danner kvadratroten av addererens utsignal, og disse signaler adderes i en som summator (31) tilbakekoblet adderer (fig. 7).

11. Anordning som angitt i krav 10, karakterisert ved at den andre enheten (5) innledes med multiplikatorer (48, 49) for multiplikasjon av den første respektive andre komponenten (26, 27) av vektorene med vektfaktorer hentet fra et minne (47), hvoretter signalene føres videre til multiplikatorene (28, 29) (fig. 13).

12. Anordning som angitt i et av kravene 1-3, 7-11, karakterisert ved at normeringsenheten (6) inneholder en enhet for divisjon av størrelsessignalet (16) for vektorsummen med summasjonssignalet (18, 33, 63) for vektorstørrelsene (fig. 5).

13. Anordning som angitt i krav 12, karakterisert ved at normeringsenheten (6) inneholder en adderer (42) for addisjon av referanssignalet (43, p) til summasjonssignalet (18, 33, 63) for vektorstørrelsene (fig.

11) .

14. Anordning som angitt i et av kravene 1, 4 - 11, karakterisert ved at normeringsenheten (6) inneholder to enheter (34, 35) for divisjon av vektorsummens komponenter (24, 25; 58, 59) med summen (18, 33, 63) av vektorstørrelsene (fig. 8).

15. Anordning som angitt i krav 14, karakterisert ved at normeringsenheten (6) inneholder en adderer (50) for addisjon av referansesignalet (51, p) til summasjonssignalet (18, 33, 63) for vektorstørrelsene (fig.

14) .