Der var matematik i, da Carlie gennemsøgte overvågningsvideooptagelser, for at finde morderen. Jeg hørte det som “Point pattern matching” og line detection/edge detection. Der var “gait analysis”, hvor man identificerer folk på måden, de går på. Så var der separation af skygger på deb grumme video.
Point pattern matching
Jeg har fundet en “tutorial” om det overordnede problem: Man har nogle punkter, et punktmønster, givet ved deres koordinater (x1,…,xd), som kan repræsentere sted, farve, hastighed,…. Lad os sige, vi har 100 af dem på èt billede. Og vi har 100 punkter, et andet punktmønster, på et andet billede – på en anden overvågningsvideoer for eksempel. Er de så “det samme”, altså omrids af samme person, samme bil,…
Det kan de godt være, uden at se ens ud. Man kan se dem fra en anden vinkel, der kan være ændret lys, …
Det beskrives matematisk ved nogle tilladte afbildninger (funktioner) tænk f.eks. på rotationer. Spørgsmålet lyder nu: Findes der en tilladt afbildning, der bringer det ene punktmønster over i det andet.
Og ydermere: Findes der en algoritme, der afgør det? Og afgør det hurtigt.
Lad os holde os til translationer (parallelforskydning) og rotationer. Og at vores punkter har to koordinater, i.e., det foregår i planen. Vi har to punktmønster, A og B. Opgaven er at flytte A saa tæt på B som muligt, og så dernæst afgøre, om det er tæt nok til, at vi vil sige A og B er billeder af det samme.
Eksempel: Hvis der er tre punkter p,q,r i A og tre punkter s,t,u i B, så gælder det om at skubbe trekanten givet ved a,b,c over i trekanten s,t,u. Og det er ikke klart, om a skal ligge tættest på s eller t eller u.
Det er et enormt område, der er anvendelser mange steder, og algoritmerne tilpasses det område, de skal bruges på. I astronomi kunne man måske interessere sig for at finde stjernekonstellationer. De består af et lille antal punkter, så en optimal algoritme til det kan være helt anderledes end den, der bruges til store punktmængder.
Med et lille antal punkter kan man sommetider bruge en “brute force” algoritme, som gennemsøger alle flytninger af A og ser, hvilken der giver kortest afstand til B. Afstand til B findes ved (d(p,s)+d(q,t)+d(r,u)) hvor d(p,q) er afstanden fra det flyttede punkt p til q
og så d(p,t)+d(q,u)+d(r,s)
og endelig d(p,u)+d(q,s)+d(r,t)
Den mindste af disse er afstanden – vi har så taget hensyn til, at vi ikke ved, hvilke hjørner i A, der skal svare til hvilke i B. Kender man ikke “omløbsretningen ” for A og B er der flere muligheder, man skal undersøge.
Skyggeseparation.
Her er en temmelig langhåret artikel om, hvordan man finder det, der er gemt i skyggen på et billede. Der er fysik i: Lys polariserer, og det skal udnyttes. I denne artikel kan de ikke behandle gamle billeder. Man optager billeder med information om polarisering (ved at optage på flere bølgelængder, tror jeg nok), og så kan man bagefter finde det, der er i skyggerne.
Andre tilgange (shadow segmentation hedder det, hvis I vil søge) går ud på, at spketret – fordeleingen af rød, grøn, blå i skyggen er anderledes end i noget, der er belyst. På den måde kan man automatisk opdage, når noget er i skyggen, og forøge intensiteten der – til Videokonferencer for eksempel.
Man har også mere geometriske metoder, hvor man bruger, at skyggers facon er givet ved andre objekter. Og så leder man efter figurer, der kunne være fremkommet som skygger.