4-06 In security.

Charlie analyserede en tegning, som havde en skjult besked. Matematikken bag var, ifølge Charlie, morfologisk “billedrensning” (morphological image cleaning). Han lavede en CART analyse (Classification and Regression Tree) af et beslutningstræ for at se, om det var sandsynligt, at det var Don, der ledte morderen på sporet. Det blev også brugt til at forbinde to af personerne – McGurn og Gibbs.

Og så var der et flot billede på Charlies nyudkomne bog. Det var et icosidodekaeder:

(den havde spidser stikkende ud fra alle sideflader – på engelsk kaldes det en “stellated icosidodecahedron”) Her er den:

Det er den, der blev brugt i serien, og den er lavet på en 3D printer, siger de hos MathWorld, og de ved det, for det er dem, der har lavet den….
CART-analyse

Classification And Regression Trees, CART, er en del af branchen datamining. Det er en bestemt algoritme, lavet af Breiman, Friedman, Olshen og Stone i 1986.Bogen fås på Amazon. Eksemplet hos Breiman et. al. er, om man kan forudse forløbet for hjertepatienter udfra de tal, man måler. Kan man for nye patienter forudsige noget udfra, hvad man ved, om de patienter, man allerede har set.
Her er et træ vedr. hjertepatienter:

CART er en metode til bygning af et beslutningsstøttetræ. Strukturen i et træ er, at man har en stribe spørgsmål/tests med to mulige udfald (ja/nej). Man starter altid samme sted – et indgangsspørgsmål. Ja leder en til nye spørgsmål, mens nej leder til nogen andre. Med de data man har, løber man ned gennem træet (træer står på hovedet i den slags analyser…) og følger forgreningerne. Man ender yderst i et blad, hvor man i eksemplet her kan aflæse, om der er stor, eller lille risiko for, at patienten dør. I mere avancerede modeller kan man også knytte en sandsynlighed til svarene – hvor sandsynligt er udfaldet ja, og hvor sandsynligt er nej. Det gør, at man kan regne baglæns: Hvis udfaldet er, at patienten døde, hvad er så de sandsynlige årsager – hvor ville man have kunnet forudse det? (Det må være det, Charlie vil – forudse, om Dons handlinger var årsag).

Man har metoder, som udfra en stor datamængde laver den slags træer, så man kan lære af de data, man allerede har, når der kommer en ny patient/et nyt firma udsteder aktier etc.

Et lidt mere indviklet træ fra Pouls Svante Eriksens kursus om netop CART for Produkt og Design psykologuddannelsen i Aalborg

Her er et par beslutningsstøttetræer fra Miljøstyrelsen. (Noget med pesticider i overfladevand)

Steganografi, Morfologisk billedrensning,

Vi har haft steganografi tidligere på bloggen, hvor hemmelige beskeder blev skjult i “unødvendige” bits i et billede. Denne gang var det en håndtegning, som gemte på en besked, og Charlie bruge en “billedrensnings” algoritme til at finde det, der var længere streger – thin features . Den type algoritme, han påstod at bruge, (Morphological Image Cleaning, MIC) fjerner “støj” fra et billede og bevarer skarpere elementer som f.eks. kanter. Om det virker, når man har lavet en tegning, der inkluderer den hemmelige besked, tvivler jeg på. En tegning er ikke støj.

Morfologi er studiet af struktur og facon. Det bruges meget generelt og mange forskellige steder, f.eks. om en proces, der udfra “rodede” problemer laver struktur, så man kan stille mere kvantitative spørgsmål og derefter forhåbentlig får disse stillet som “opgaver”, der kan angribes med matematik. Dette beskrives på Swedish Morphological Society, hvor man gennemgår forskellige eksempler. Et “rodet” spørgsmål kunne være “Hvad gør vi ved økonomisk kriminalitet?” (Eller bandekriminalitet, kunne man måske tilføje i disse dage).
Man skal have klargjort, hvilke problemer, der er, (skatteunddragelse, bestikkelse, bedrageri, konkurrenceforvridning, hvidvaskning…), metoder (regnskabssnyd, falske produkter (IT-factory), diverse finansielle fiksfakserier…), hvem går det ud over, motiver… Og hvad har man af midler? Der vil være sammenhænge – nogen midler virker mod noget; nogen ting kan ikke foregå samtidig etc. Man skal finde en konsistent strategi uden indre modstrid.
I analysen fastlægger man, hvilke variable, der indgår, hvilke værdier, disse kan have – det kan godt være “ja/nej”, der er muligheden, og hvilke der kan optræde samtidig.
En senere analyse kan gå på kausalitet – hvad kan forårsage hvad og med hvilke sandsynligheder.

At strukturere sådanne rodede problemer kaldes morfologi. Det går tilbage til F.Zwicky, som var ansat på CalTech. Han påstod selv, at han brugte metoden til mange af sine opdagelser i astronomi/astrofysik.

MIC-algoritmen – ( R.A. Peters, A new algorithm for image Noise Reduction Using mathematical Morphology, IEEE transactions on Image processing, 1995) er en kombination af flere billedbehandlingsalgoritmer.

Først finder man en “udglattet” version af billedet: Hver pixel forventes at ligne sine naboer. Man definerer først, hvad naboerne er f.eks.
De ialt fire pixels, der ligger lige oven for, neden for, til venstre eller til højre for
De 8 pixels, der foruden de fire fra før, er dem skråt op til højre, skråt ned til højre og tilsvarende til venstre
Eller mere indviklede nabolag – det kaldes “strukturerende elementer” og bestemmer, hvor udglattet, billedet bliver.

I en udglatning skifter man farve på en pixel efter en funktion af naboernes farve.

Det oprindelige billede kalder vi B, den udglattede version U. Differensen imellem de to (man kan trække pixelværdier fra hinanden) B-U indeholder nu dels støj og dels “kanterne” – en kantpixel ligner jo netop ikke sine naboer.

MIC algoritmen leder efter kanterne i B-U. Og tilføjer til sidst disse kanter til U. Den bruger information fra det oprindelige billede og fra “udglatningen” – f.eks. noget om forskellen på, om man glatter ud ved at lade en pixel have samme farve som sin lyseste nabo eller sin mørkeste nabo (så vidt jeg har forstået- det hedder open-close og close-open, hvis nogen vil vide mere).

I seneste nummer af Plus Magazine beskrives en anden type billedrensning/gendannelse, hvor man bruger partielle differentialligninger – varmeledningsligningen – til at ændre pixels i forhold til deres naboer: Restoring Profanity – om restaurering af nogle østrigske fresker.