Machine perceptie beeldinformatieverwerking tentamen + uitwerkingen



Dovnload 102.1 Kb.
Datum22.08.2016
Grootte102.1 Kb.

machine perceptie
beeldinformatieverwerking

tentamen
+ uitwerkingen

13 december 2000


Als rode draad in dit tentamen bekijken we de noodzakelijke technieken om van een gescande pagina drukwerk zoals:

een versie te maken waarin de tekstregels volkomen horizontaal lopen. Hiermee wordt de verdere verwerking noodzakelijk om de tekst daadwerkelijk te ‘lezen’ (d.w.z. om te zetten van pixels in ASCI codes) aanzienlijk vereenvoudigd.



  • De opgaven zijn los van elkaar te maken! Ook de verschillende onderdelen van de opgaven zijn niet altijd van elkaar afhankelijk. Als onderdeel (a) dus niet lukt kijk dan wel verder naar (b) enz.

  • Bondige antwoorden graag, een goed antwoord kan verpest worden door er foutieve ‘blabla’ bij te zetten.

  • Voorzie elk blad van je naam, collegekaartnummer en e-mail.

  • De deelopgaven met een * gemerkt vergen meer inzicht/werk/tijd dan de andere opgaven. We raden je dan ook aan om pas aan deze opgaven te beginnen nadat je de andere opgaven hebt bekeken (en hopelijk beantwoord).

  • Veel succes!


No

Punten

Omschrijving

1

2

Verwijderen van ruis met behulp van een percentiel filter

2

3

Analyse van de locale beeldstructuur om het midden van de tekstregels te detecteren.

3

3

De Hough transformatie om de rotatiehoek van de gescande pagina te vinden.

4

2

Een geometrische transformatie om het beeld ‘recht te zetten’.
Het bovengeschetste probleem van het ‘rechtleggen’ van het gescande document kent een aantal deelproblemen die in de afzonderlijke opgaven aan bod komen. In onderstaande tabel is tevens het aantal punten gegeven dat maximaal voor een opgave gehaald kan worden.

1.Ruis filter


Het systeem dat gescande pagina’s tekst moet kunnen omzetten in ASCI codes moet ook kunnen werken met slechte kwaliteit scans. Daarom wordt besloten om eerst een ruisfilter toe te passen om de ruis zoveel mogelijk te ‘verwijderen’ om te vermijden dat de verdere verwerking daar teveel hinder van ondervindt.

Het percentiel filter is een locale (neighbourhood) operator gebaseerd op een statistische analyse van de beelddata. Binnen een omgeving van het pixel met coordinaten (x,y) bestaande uit M pixels labelen we de M grijswaarden met v1,...,vM. Het percentiel filter sorteert deze M pixel waarden, met als resultaat de gesorteerde lijst van pixelwaarden:

en kiest de k-de waarde als het resultaat. Dit ‘recept’ wordt voor elk pixel herhaald.



  1. Geef een pseudocode algorithme voor het percentiel filter waarin de locale omgeving een K bij K vierkante omgeving is (met K oneven) gecentreerd rond (x,y). Hierbij mag u een functie sort gebruiken dat een 1D vector waarden sorteerd naar oplopende waarde. Bordereffecten mag u buiten beschouwing laten. De k-waarde moet een parameter van de functie zijn.

for j=1:M % ..

for i=1:N % loop over alle pixels in beeld


list = []; % maak lege lijst

for jnbh=-S:S % ..

for inbh=-S:S % loop over alle pixels in KxK omgeving

list = [list, im(i+inbh, j+jnbh) ]; % voeg pixelwaarde aan lijst toe

end

end


list = sort(list); % sorteer lijst

r(i,j) = list(k); % resultaat is k-de waarde

% in gesorteerde lijst

end


end

Met een beetje moeite is bovenstaande pseudocode in matlab te implementeren. Onderstaand de werkende matlab code. Enkel voor informatie. Op tentamen wordt geen matlab programmering gevraagd. N.B. deze functie is erg traag…

function r = percentilefilter( im, K, k )

% Percentile filter using a square K size neighborhood


[N,M] = size(im); % size of the image N:vertical, M:horizontal

S = round( (K-1)/2 ); % neighborhood of size 2S+1 square

r = im; % set output to input (not really needed)
iindex = inline('min(max(1,i),N)','i','N'); % deal with border (macro)

jindex = inline('min(max(1,j),M)','j','M'); % deal with border (macro)

for j=1:M

for i=1:N

list = []; % define an empty list

for jnbh=-S:S

for inbh=-S:S

list = [list, im( iindex(i+inbh,N), jindex(j+jnbh,M) )];

end

end


list = sort(list);

r(i,j) = list(k);



end

end
Voor oneven K waarde zijn er ook een oneven aantal pixels in de locale omgeving. Keuze van de middelste waarde, d.w.z. k = (K2+1)/2 leidt tot het zogenaamde mediaan filter.




  1. 0

    0

    0

    0

    0

    10

    10

    10

    10

    10

    0

    0

    0

    0

    0

    10

    10

    10

    10

    10

    0

    0

    1

    0

    0

    10

    10

    10

    10

    10

    0

    0

    0

    0

    0

    10

    10

    10

    4

    10

    0

    0

    0

    0

    0

    10

    10

    10

    10

    10

    0

    2

    0

    0

    0

    10

    10

    10

    10

    10

    0

    0

    0

    0

    0

    10

    10

    10

    80

    10

    0

    0

    1

    0

    0

    10

    8

    10

    10

    10

    0

    0

    0

    0

    0

    10

    10

    10

    10

    10

    0

    0

    0

    0

    0

    10

    10

    10

    10

    10
    Gegeven een beeld f waarin een licht vlak grenst aan een donker vlak met een rechte edge tussen beide gebieden. Door een slechte opname bevat dit beeld ook ruis. Hiernaast een voorbeeld van zo’n ruisig beeld (fragment).

Wat is het resultaat van het mediaan filter binnen een 3x3 omgeving?

Alle waarden in de linkerhelft van het beeld worden 0 en alle waarden in de rechterhelft worden 10. Als voorbeeld: neem het punt met waarde 4 (zie figuur). De gesorteerde waardes zijn daar: 4, 10, 10, 10, 10, 10, 10, 10, 10. De 5-de (middelste) waarde is de mediaan en is gelijk aan 10. NB de 3x3 omgeving moet voor het filter in elk punt van het beeld worden bekeken.



  1. (* zie uitleg pagina 1) Kunt u een manier bedenken om de mediaan efficient te berekenen van een waardenensemble v1,…,vM dat maar in enkele waarden verschilt van een ensemble w1,...,wM. Dit speelt een grote rol in de beeldbewerking: merk op dat de ensembles van grijswaarden van de locale omgeving van het punt (x, y) maar weinig verschilt van het ensemble van grijswaardes van de locale omgeving van het punt (x+1, y).

Hier zijn meerdere efficiënte algorithmes te verzinnen. Merk op dat de KxK omgeving van punt (i,j) slechts op K plaatsen verschilt van de KxK omgeving van punt (i-1,j). Hou nu bij van welk pixel de waarden in de lijst afkomstig zijn (ook na sortering). Dan kunnen de K waarden die ‘uit de omgeving vallen’ als je gaat van pixel (i-1,j) naar (i,j) eenvoudig uit de lijst van gesorteerde waardes verwijderd worden (de lijst van de waardes uit de omgeving van (i-1,j)). De K nieuwe waarden worden dan eerst gesorteerd en dan worden de twee gesorteerde lijsten gemerged. Dit alles is significant efficienter voor grote K.

2.Locale beeldstructuur


In het beeld van de tekst gaan we nu proberen de regels te vinden; het zal voldoende zijn om voor iedere regel een beperkt aantal punten te vinden waarvan we zeker zijn dat ze op die regel liggen; die gebruiken we dan als input voor de Hough-transformatie van de volgende opgave.





Links de gehele gescande pagina, rechts een uitvergroting van een klein deel van de pagina.


  1. In het beeld van de tekst zijn relevante structuren op verschillende schalen (‘scales’) zichtbaar. Benoem op zijn minst 5 niveaus (geef ze namen die overeenkomen met de belangrijke tekstelementen voor de analyse.

    • het tekst-blok op de pagina

    • een alinea

    • een regel (hoogte) of een regelafstand

    • een woord

    • een letter

    • lijndikte (waarmee letters zijn opgebouwd)

    • schreef

NB de ‘pixel grootte’ komt weliswaar overeen met een schaal in relatie tot het document maar is op zich niet zo relevant voor de analyse. A priori wordt het aantal pixels per mm (dots per inch) zo gekozen dat de kleinste relevante schaal goed onderscheidbaar is. Is dus afhankelijk van welke schaal in bovenstaand rijtje nog belangrijk is in de toepassing.

  1. Om de tekstregels te vinden zijn we natuurlijk geïnteresseerd in de ‘regel-schaal’. Eigenlijk zijn twee groottes van belang: teksthoogte en regelafstand. Welke ga je gebruiken voor de regel-detectie (lees eerst even verder voor je deze beantwoordt)?

‘dark bars on light background’ : regelafstand

  1. Waarom is het bepalen van de locale structuur op een schaal  equivalent aan het bepalen van de locale structuur op schaal 0 in een beeld geconvolueerd met een Gauss van breedte ?

De locale structuur van een beeld is vastgelegd door de spatiële afgeleides (Taylor benadering). Afgeleide wordt bepaald door convolutie met (afgeleide van) Gauss functie. De schaal  bepaald de grootte van de details waarin je geinteresseerd bent. Omdat zowel convolutie als differentiëren lineair zijn maakt de volgorde niets uit:

Ofwel differentiëren met afgeleide op schaal  is gelijk aan eerst convolueren met Gauss van schaal  gevolgd door het nemen van afgeleide (op schaal 0).


We zoeken in het Gaussisch gesmoothde beeld dus naar ‘dark bars on light background’. We raadplegen een tabel van local structuren en vinden dat we dan moeten zoeken naar de plaatsen waar en .

  1. Wat zijn ijkcoördinaten (‘gauge coordinates’) in het algemeen en waarom zijn ze nuttig?

IJk coordinaten zijn locale coordinaten waarvan de asrichtingen bepaald worden door de data (de beeldfunctie). In elk punt van het beeld zullen de asrichtingen in het algemeen verschillend zijn. IJkcoordinaten geven een manier om de locale beeldstructuur te representeren op een coordinatenstelsel dat bij de data past. Nuttig omdat je dan een algorithme-ontwerp even kunt loskoppelen van de implementatie (in xy coordinaten).

  1. Naast het pq-ijkstelsel is het gradiënt ijkstelsel een belangrijk stelsel. Geef de definitie van dit stelsen en geef de eerste orde afgeleides in dit stelsel uitgedrukt in de fx.en fy afgeleiden.

Gradiënt ijkstelsel: orthonormale basis vectoren v en w waarbij w de (genormaliseerde) gradiënt vector is. De gradiënt vector in het xy stelsel is

waarin fx en fy de afgeleiden in de x en y richting zijn. Diezelfde gradiëntvector maar nu in het vw stelsel heeft als componenten:





  1. We hebben blijkbaar (p, q)-coördinaten nodig in het recept. Wat is dat voor een soort ijking en wanneer gebruik je die in plaats van het gradiënt ijkstelsel (the gradient-gauge)?

Het gradiënt ijkstelsel is niet bruikbaar als de gradiënt nul is (zowel fx en fy gelijk nul). In dat geval wordt de tweede orde structuur gebruikt om een ijkstelsel te definieren. De eigenvectoren van de Hessiaan matrix bepalen de p en q richtingen.

De locale structuur in die ijkcoordinaten, in de punten (a, b) waar de gradiënt nul is, wordt gegeven door:



waarbij de afspraak is dat de fpp kleiner is dan qq.



  1. fpp en fqq zijn de eigenwaarden van een belangrijke matrix die de locale structuur beschrijft. Hoe heet die matrix en welk aspect van de structuur beschrijft hij?

Hessiaan matrix, welke de tweede orde structuur vastlegd (de kwadratische vorm in de Taylor benadering).

  1. Beredeneer waarom het idee en inderdaad de punten op de regels zal vinden.

Bij een zwarte lijn op een witte achtergrond ziet de locale beeldstructuur eruit als een ‘goot’: constant in de p-richting (fpp ongeveer nul) en gekromd in de q-richting (fqq>>0).





  1. Als je dit moet implementeren, hoe bereken je dan fpp en fqq (geef het principe, geen formules) ?

Er is een formule waarmee fpp en fqq kunnen worden uitgedrukt in fx, fy, fxx, fxy en fyy. Deze afgeleides kunnen eenvoudig met Gaussische convoluties worden uitgerekend. Daarmee zijn dan fpp en fqq op ieder punt in het beeld eenvoudig berekenbaar als een ‘point operator’ met de beelden fx, fy, fxx, fxy en fyy als input beelden. Het is hierbij nog nodig om een keuze te maken voor de schaal waarop de Gaussische afgeleide wordt bepaald.

Dus NIET de coördinaten transformatie (rotatie) expliciet op ieder punt uitvoeren gegeven de Hessian matrix.



3.Hough transformatie


We gaan de punten op de regels uit opgave 2 gebruiken om de stand en positie van de regels te bepalen. Daarvoor gebruiken we de Hough-transformatie methode.

  1. Wat houdt die methode in en waarom is dit een geschikte oplossing voor dit probleem?

De HT transformeert punten in het beeld naar de parameterruimte. Zo ‘stemt’ ieder mogelijk punt op een regel (rechte lijn) voor alle parameters van de lijnen die door dit punt gaan.De parameter combinaties (d.w.z. rechte lijnen) die veel stemmen hebben verkregen komen overeen met de in een beeld zichtbare lijnen.

Het is een geschikte methode omdat



    • we hier zoeken naar lijnen die eenvoudig parameteriseerbaar zijn

    • de detectie methode beschikbaar is (we kunnen voor elk punt in het beeld aangeven of het mogelijk op een regel ligt).

    • we zijn geinteresseerd in de lijnparameters (hoek, regelafstand en plaats)



  1. We zoeken lijnen; daarvoor zijn verschillende Hough-transformaties bekend. Sommigen zijn niet geschikt om alle lijnen in een beeld even goed te vinden, een voorbeeld is de point-to-line Hough transformatie y = a x + b. Wat is het probleem, en welke Hough-transformatie heeft dat probleem niet?

De parameterisatie y = a x + b is gebaseerd op de helling (tangent) a van de lijn. De waarde van a wordt zeer groot voor (bijna) verticale lijnen. Dit maakt dat de parameterruimte van waarden (a,b) waarden moeilijk (dan wel onmogelijk) discretiseerbaar is. De point-to-sine Hough transformatie kent dit probleem niet.

De teksten in ons voorbeeld liggen altijd wel ongeveer recht; er is gegeven dat de richtingscoëfficiënt van de lijnen ligt tussen –½ en ½. We gebruiken daarom nu wel de (a,b)-parametrisatie en de Hough-transformatie die daarbij hoort.



  1. Geef de pseudocode voor de Hough-transformatie-stap van de detectie procedure. Die moet zijn te implementeren door iemand die het dictaat niet heeft gelezen. Behalve de structuur van het algoritme moet ook de juiste keuzen voor de discretisatie van de parameter-ruimte worden aangegeven, dus de intervallen waarin a en b gesampled moeten worden.

initialiseer een gediscretiseerde parameterruimte H(a,b) op nul

loop over alle punten (x,y) in beeld

if (x,y) een (waarschijnlijk) lijnpunt is

loop over a van – ½ tot ½ met stapgrootte s



b = -a x + y

H(a,b) = H(a,b) + 1

endloop

endif


endloop

De stapgrootte s is afhankelijk van de nauwkeurigheid waarmee de richting van de lijnen bepaald dient te worden. De mogelijke waarden van b worden bepaald door de beeldgrootte (maximale waarden van x en y) en door het interval van hellingshoek a.



  1. In onderstaande figuur is de transformatie uitgevoerd op een vereenvoudigde output van de regel-detectie uit vraag 2 (linker beeld). Het resultaat staat rechts. Hoe bepaal je uit de transformatie de positie en locatie van de 4 regels? En hoe bepaal je de regelafstand?

De 4 (stippel) lijnen in het beeld links zijn terug te vinden als de 4 locale maxima in de parameter ruimte rechts. Deze locale maxima hebben alle dezelfde a-waarde (zelfde helling). Het verschil in bi-waarden is NIET de regelafstand, immers de regelafstand is de LOODRECHTE afstand tussen de lijnen.



  1. Waarom lopen de lijnen in het Hough-domein allemaal zo schuin, van linksboven naar rechtsonder?

Door de keuze van de oorsprong in het beeld. Een punt (x,y) leidt tot b = -x a + y in de Hough parameterruimte. De helling van de lijnen in de parameterruimte zijn dus allemaal negatief als de x coordinaten in het beeld allemaal positief zijn (zoals gekozen).

  1. (* zie eerste pagina) Dat schuinlopen maakt detectie van de maxima in de Hough-transformatie nogal onnauwkeurig in die schuine richting. Dat komt door de keuze van de oorsprong van de (x,y)-coördinaten in het originele beeld links. Leg dat uit, en beredeneer wat het gevolg is als je de oorsprong in het midden van beeld kiest. Geeft je dat een beter gedrag van de piek-detectie?

De oorsprong in het midden van het beeld leggen heeft tot gevolg dat er in de parameterruimte lijnen komen met zowel positieve als negatieve hellingen. De ‘snijpunten’ van die lijnen in de parameterruimte (die zijn ‘uitgesmeerd’ t.g.v. discretisatie effecten) worden daarmee nauwkeuriger bepaald.

4.Geometrische transformatie


Met de Hough transformatie van de vorige opgave zijn we erin geslaagd om de hoek van de tekst regels met de x-as te meten. Nu moeten we nog het beeld zodanig geometrisch transformeren dat in het resultaatbeeld de tekstregels horizontaal komen te lopen.

Voor een rotatie over  graden is gegeven:

waarin (x’, y’) de coordinaten van het geroteerde punt zijn en (x, y) de coordinaten van het oorspronkelijke beeld.



  1. Geef een pseudocode algorithme voor het uitvoeren van de rotatie gegeven het originele beeld F (met indices 01<256 en 02<256) en gewenst resultaat beeld G, bemonsterd (gesampled) in dezelfde punten. Gebruik hierin de bilineare interpolatie.

Een geometrische transformatie is een backward algorithme, d.w.z. loop over alle pixels in het resultaatbeeld en bereken waar de pixels vandaan kwamen. Verwijzend naar de vergelijking hierboven, moeten we uitrekenen wat (x, y) is gegeven (x’,y’). Dat is inversie van de rotatie is eenvoudig: neem hoek –alpha i.p.v. alpha (netjes inverteren van de matrix geeft hetzelfde).

Het algorithme wordt daarmee:

for xa = 0 to 255 % ..

for ya = 0 to 255 % loop over alle pixels in beeld


x = xa*cos(phi) – ya*sin(phi);

y = xa*sin(phi) + ya*cos(phi);


G(xa,ya) = interpolate( F, x, y );

end


end

Pseudocode voor de de bilineaire interpolatie functie is

i = floor(x); % de links onderhoek van de vier omliggende pixels

j = floor(y); % idem

a = x - i;

b = y – j;


interpolatedvalue = (1-a)(1-b) F(i,j) +

a (1-b) F(i+1,j) +

a b F(i+1,j+1) +

(1-a) b F(i,j+1) ;

Hierbij is weer geen rekening gehouden met het ‘border probleem’,

Als illustratie is werkende matlab code voor beeldrotatie onderstaand gegeven. Hierbij is het ook mogelijk om een punt (x0,y0) waarom geroteerd moet worden aan te geven. Wederom geldt dat deze code niet echt efficient is (vanwege de traagheid van de interpreter in matlab en vanwege het feit dat check op border voor alle beeldaccess wordt gedaan i.p.v. in de loop onderscheid te maken tussen punten ‘middenin’ het beeld en punten aan de rand).

function G = imagerotation( F, phi, x0, y0 )

% very slow image rotation

phi = phi * pi / 180; % van graden naar radialen

[N,M] = size(F); % size of the image N:vertical, M:horizontal

G = F; % set output to input (not really needed)

iindex = inline('min(max(1,i),N)','i','N'); % dealing with the border

jindex = inline('min(max(1,j),M)','j','M'); % idem

for ya=1:M

for xa=1:N

x = (xa-x0)*cos(phi) - (ya-y0)*sin(phi) + x0;

y = (xa-x0)*sin(phi) + (ya-y0)*cos(phi) + y0;

i = floor(x);

j = floor(y);

a = x-i;


b = y-j;

if x<1 | x>=N | y<1 | y>=M

G(xa,ya)=0;

else


G(xa,ya) = (1-a)*(1-b)*F( iindex(i,N), jindex(j,M) ) + ...

a*(1-b)*F( iindex(i+1,N), jindex(j,M) ) + ...

a*b*F( iindex(i+1,N), jindex(j+1,M) ) + ...

(1-a)*b*F( iindex(i,N), jindex(j+1,M) );



end

end


end

Beeldinformatieverwerking: Tentamen 13-12-2000




De database wordt beschermd door het auteursrecht ©opleid.info 2017
stuur bericht

    Hoofdpagina