maandag 27 april 2009

Thesis: inhoudstafel

  • Dankwoord
  • Inhoudstafel

  1. Inleiding
    1. Voorwoord ?
    2. Probleembeschrijving: wat is de opdracht van mijn thesis
    3. Doelstellingen: wat wens ik te bereiken met mijn thesis
    4. Thesisorganisatie: wat is de structuur van mijn thesis
  2. Wallpapergroepen
    1. Introductie: wat zijn de wallpapergroepen
    2. Eigenschappen
    3. Verband met texturen: reguliere texturen
    4. Nut voor deze thesis
  3. Roosterbepaling
    1. Bestaande methodes: welke methodes bestonden reeds en korte omschrijving hiervan
    2. Methode van Y. Liu: beschrijving van deze methode
    3. Kritiek: op deze methode
    4. Aanpassingen: aangebracht aan deze methode
    5. Resultaten: vergelijking van deze methode met mijn aangepaste methode (voordelen en nadelen) en enkele grafieken/plots
  4. Wallpapergroepclassificatie
    1. Bestaande methodes: welke methodes bestonden reeds en korte omschrijving hiervan (2 methodes)
    2. Methode van Y. Liu: beschrijving van deze methode (1e van de 2 en waarom deze)
    3. Resultaten van deze methode
  5. Textuursynthese
    1. Introductie: wat is textuursynthese
    2. Pixel-based methode
      1. Introductie: korte omschrijving van de werkwijze
      2. Voorkennis toepassen: hoe kan de kennis van het rooster en de symmetrieën elk van beide methodes verbeteren
      3. Resultaten
      4. Besluit
    3. Patch-based methode
      1. Introductie: korte omschrijving van de werkwijze

      2. Voorkennis toepassen: hoe kan de kennis van het rooster en de symmetrieën elk van beide methodes verbeteren
      3. Resultaten
      4. Besluit
  6. Conclusie
    1. Algemeen besluit: over in hoeverre de bestaande textuursynthesealgoritmes kunnen verbeterd worden wetende dat men enkel (bijna) reguliere texturen heeft
    2. Toekomstig onderzoek

  • Bibliografie

maandag 20 april 2009

Graphcut Textures

Enkele resultaten van mijn graph cut algoritme:

Inputtextuur (1) (500x500)

Gesynthetiseerde textuur (1) (500x500)

Gesynthetiseerde textuur met naden (1)

Kleur geeft aan welke oppervlakte elke patch inneemt (1)


Inputtextuur (2) (500x456)

Gesynthetiseerde textuur (2) (300x300)


Inputtextuur (3) (486x500)

Gesynthetiseerde textuur (3) (400x400)


Inputtextuur (4) (500x497)

Gesynthetiseerde textuur (4) (500x500)


Inputtextuur (5) (192x192)

Gesynthetiseerde textuur (5) (200x200)


Inputtextuur (6) (192x192)

Gesynthetiseerde textuur (6) (300x300)


Inputtextuur (7) (293x217)

Gesynthetiseerde textuur (7) (300x300)


Inputtextuur (8) (192x192)

Gesynthetiseerde textuur (8) (300x300)


Inputtextuur (9) (640x640)

Gesynthetiseerde textuur (9) (300x300)

vrijdag 27 maart 2009

Planning

Mijn planning voor de komende weken ziet er als volgt uit:
  • 28/03 - 03/04: verder implementeren van het patch based textuursynthesealgoritme. Dit betekent dat het volledig werkt en dat volgens de methode die in de paper beschreven is. Aanpassingen maken om de translatievectoren en wallpaper group in rekening te brengen om op die manier de kwaliteit van de outputtextuur en de snelheid van het algoritme te verhogen. Vervolgens testen van dit algoritme op verschillende texturen.
  • 04/04 - 10/04: op reis
  • 11/04 - 19/04: laatste aanpassingen maken aan beide algoritmes. Grondig vergelijken van beide algoritmes en beslissen welk het meest veelbelovende is. Dit algoritme verder finetunen en zeer grondig testen op verschillende klassen van texturen en zo onderzoeken in hoeverre de kwaliteit van de gesynthetiseerde texturen beter is dankzij de aanpassingen en in welke mate de snelheid verhoogd is.
  • 20/04 - 31/05: thesis schrijven

Tweede resultaten textuursynthese

Nu ik de pixel based methode geïmplementeerd had en de eerste resultaten er waren, was het tijd om te beginnen aan de patch based methode die beschreven staat in Graphcut Textures: Image and Video Synthesis Using Graph Cuts van Kwatra uit 2003. Deze methode is complexer dan de vorige methode en het heeft dan ook wat langer geduurd om deze te implementeren. De huidige code is wel nog niet volledig zoals beschreven staat in de paper, maar ik was er wel mee in staat te eerste resultaten te genereren. Hetgeen het momenteel doet is tegels uitknippen uit de inputtextuur en deze in de outputtextuur aan elkaar plakken volgens een bepaalde translatie-as. Enkele resultaten zijn hieronder te zien. Voor fig.1, een bijna perfect reguliere textuur, geeft dit zeer goede resultaten. De vijf andere figuren geven het resultaat van enkele near-regular textures. Deze resultaten zijn alvast hoopgevend. Hier en daar is evenwel nog een naad te zien, maar dit ga ik zeer binnenkort verhelpen. De rekentijd is telkens ongeveer 20 seconden, dus heel wat sneller dan de pixel based methode.

Figuur 1

Figuur 2

Figuur 3

Figuur 4

Figuur 5

Figuur 6

maandag 23 maart 2009

Eerste resultaten textuursynthese

Nu het roosterbepalingsalgoritme relatief robuust was en ik een primitief wallpapergroepclassificatiealgoritme had, werd het tijd om te beginnen aan de textuursynthese. Met de informatie die ik uit de eerste twee fases kon halen, was ik in staat bestaande synthesealgoritmes te verbeteren en/of efficiënter te maken.

Het eerste textuursynthesealgoritme is een pixel-based synthesealgoritme van Wei & Levoy. Dit is een zeer eenvoudig, maar ingenieus algoritme dat een nieuwe textuur zal synthetiseren volgens een vooropgestelde grootte, pixel per pixel. Het concept wordt vrij duidelijk uitgelegd aan de hand van de volgende figuur.

Figuur 1: pixel based texture synthesis

Figuur (a) toont de inputtextuur. Daarop zijn verschillende neighbourhoods afgebeeld met een vooraf bepaalde grootte (in dit geval een 5x5 window). Op figuur (b) staat de outputtextuur. Deze wordt geïnitialiseerd zodat er random pixels staan op de randen rechts en onderaan (in feite zorgt men ervoor dat de histogram sterk lijkt op de histogram van de inputtextuur). Voor elke pixel die men wil synthetiseren, gaat men de neighbourhood van de outputtextuur vergelijken met elke mogelijk neighbourhood van de inputtextuur en neemt men diegene die er het sterkst op gelijk (bv. via de SSD). De bijhorende pixel kopieert men dan naar de outputtextuur. Figuur (c) toont de outputtextuur als ongeveer de helft van de pixels reeds gesynthetiseerd is. Figuur (d) toont de volledig gesynthetiseerde textuur.

De resultaten van een dergelijk algoritme zijn in een aantal gevallen aanvaardbaar, maar in de meeste gevallen absoluut niet. Het algoritme scoort vooral goed bij irreguliere texturen. Vanaf het moment er enige regelmaat aanwezig is, faalt het algoritme deze regelmaat te reproduceren in zijn gesynthetiseerde texturen. Enkele resultaten zijn hier te vinden. Het is dus mijn bedoeling dit algoritme zodanig aan te passen dat deze regelmaat wel degelijk terug te vinden is in de outputtextuur.

Een eerste aanpassing aan het algoritme, is een aanpassing die o.a. terug te vinden is in de doctoraatsthesis Sample-Based Texture Synthesis door M. Sabha. Daarin wordt vermeld dat het random initialiseren van de pixels in de outputtextuur geen goed idee is in het geval de inputtextuur een zekere regelmaat vertoont. De nieuwe gesynthetiseerde pixels zullen meestal heel lokaal de inputtextuur benaderen, maar de globale regelmaat niet weergeven. Een grotere neighbourhood nemen helpt in sommige gevallen, maar ook niet altijd. Een beter idee is dan het nemen van een stuk van de inputtextuur (waarvan de dimensies die van de tegelgrootte benaderen, of een veelvoud ervan zijn) en dit stuk te plakken in de linkerbovenhoek van de outputtextuur. De nieuwe gesynthetiseerde pixels zullen nu in de meeste gevallen zowel de lokale structuur van de inputtextuur benaderen, maar ook de globale structuur. Een belangrijke vereiste is wel dat de neighbourhoodgrootte zo moet gekozen zijn dat ze ongeveer de dimensies van de tegelgrootte benadert. Hoe kleiner de dimensies, hoe kleiner de kans dat de globale structuur te zien zal zijn in de outputtextuur.

Figuur 2: textuursynthese met een random geïnitialiseerde output en een waarvan een stuk van de input gekopieerd werd

Een volgende stap is het bepalen van de neighbourhoodgrootte. Het is heel logisch deze even groot te nemen als die van de tegelgrootte. In de meeste gevallen geeft dit correcte resultaten. In sommige gevallen echter niet. Het is namelijk zo dat bv. een 5x5 window in feite slechts ongeveer 3x5 groot is en dus niet de volledige structuur van een tegel omvat. De neighbourhoodgrootte verdubbelen of toch zeker de hoogte verdubbelen biedt een oplossing.

Een laatste aanpassing is om de efficiëntie van het algoritme te verbeteren en in kleine mate ook de kwaliteit van de outputtextuur te verhogen. Als men, zoals in het huidige geval, weet waar men t.o.v. een bepaalde referentiepositie in de inputtextuur pixels aan het synthetiseren is in de outputtextuur, en men daarenboven ook weet wat de tegelgrootte is, kan men de zoekruimte waarbinnen men op zoek gaat naar een gelijkaardige neighbourhood verkleinen. Deze methode wordt verduidelijkt op fig. 3 en 4. Rond elke pixel die in aanmerking komt in de inputtextuur wordt een window gebruikt, in dit geval een 9x9 window, zodat kleine roosterafwijkingen kunnen opgevangen worden.

Figuur 3: de allereerste pixel die moet gesynthetiseerd worden

Figuur 4: de gele vierkanten duiden de pixels aan die in aanmerking komen om op de plaats van de nieuwe pixel te komen

Een aanpassing die zeker ook nog van pas komt, maar die ik nog niet geïmplementeerd heb, is om niet enkel op de roosterpunten (en directe omgeving daarvan) te gaan zoeken naar overeenkomstige pixels, maar ook de symmetrieën van de wallpapergroepen in rekening breng. Dit is in principe niet zo'n grote aanpassing, maar het zal de resultaten slechts weinig beïnvloeden.

Enkele resultaten van het algoritme in huidige toestand zijn hieronder weergegeven.

Figuur 5: inputtextuur (192x192)

Figuur 6: outputtextuur (100x100)

Figuur 7: inputtextuur (247x250)

Figuur 8: outputtextuur (100x100)

Figuur 9: inputtextuur (355x267)

Figuur 10: outputtextuur (140x120)

Zoals reeds te zien op deze figuren, is het duidelijk dat de resultaten voor reguliere texturen zo goed als perfect zijn. Voor near-regular textures zijn de resultaten nogal wisselvallig. Fig.8 toont goede resultaten voor de synthese van fig.7. Fig.6 toont de iets minder geslaagde synthese van fig.5. Hoe minder regulier de texturen, hoe minder de kwaliteit van het resultaat. Het blijkt dat deze methode voor een groot deel texturen wel acceptabele resultaten geeft, maar voor het andere deel soms eerder ruis produceert dan iets anders. De conclusie is dat deze methode te kort schiet als men een zo algemeen mogelijke methode wenst. Ook qua tijd is deze methode niet aan te raden. Ik heb welliswaar geen optimalisaties doorgevoerd (buiten een klein stuk van de code dat ik in C geïmplementeerd heb), maar bv. voor fig.8 mocht ik rond de 15 minuten wachten.

Nu ik reeds geëxperimenteerd heb met de patch based methode van Kwatra, is het duidelijk dat deze methode meer perspectieven biedt. De lokale en globale structuur wordt daarbij eenvoudig in de output gebracht en de snelheid zal veel hoger liggen dan die van de pixel based methode.

dinsdag 17 februari 2009

Roosterbepaling

Ondertussen is er (alweer) wat tijd verstreken, maar ik heb zeker niet stilgezeten, integendeel, ik heb van mijn beperkte aantal examens kunnen profiteren om heel wat aan mijn thesis te werken. Een van mijn belangrijkste progressies is het afwerken van de code om het rooster in een textuur te bepalen. Ik had reeds werkende code hiervoor, maar deze werkte maar op een beperkt aantal texturen. De code die ik nu heb is zeer robuust en werkt op een zeer brede waaier van texturen. Hieronder volgt een beschrijving van de werkwijze die ik hanteer. De belangrijkste aanpassingen zijn gebaseerd op de ondervinding dat een goede preprocessing van de textuur zeer belangrijk is.

De eerste stap, een preprocessing stap, is gebaseerd op het feit dat de lokale intensiteit van een textuur niet overal even groot is. Bij een zo goed als perfecte textuur is dit geen probleem, maar bij een foto van een near-regular texture kan dit wel voor problemen zorgen. Dit kan bv. veroorzaakt zijn door een flash die niet volledig uniform is of door zonlicht. Een oplossing hiervoor is om de intensiteitswaarden van een textuur te delen door de intensiteitswaarden van een circular average filter toegepast op de oorspronkelijke textuur, gevolgd door een normalisatie. Dit wordt hieronder gedemonstreerd.

Textuur: vóór

Circular average filter toegepast op de textuur

Textuur: na deling en normalisatie

Vervolgens worden er enkele kleine aanpassingen gedaan, zoals een constrastverhoging, een inversie van de intensiteitswaarden indien de gemiddelde intensiteitswaarde hoger is dan 0.5 (dit geeft meer uitgesproken pieken bij de autocorrelatie) en nogmaals een circular average filter (ditmaal met een zeer kleine straal) om hoogfrequente ruis te elimineren. Het resultaat is hieronder weergegeven.

Textuur na contrastverhoging, inversie en smoothing

In de volgende preprocessingstap gaan we op zoek naar een gepaste threshold zodat we de textuur kunnen omzetten naar een zwart-wit textuur. Het is namelijk gebleken dat de pieken in de autocorrelatiefunctie hierdoor meer uitgesproken zijn. Een mogelijke thresholdwaarde kan men berekenen door de brightness aan te passen bij een maximaal contrast en de intensiteit te zoeken waarbij relatief het minste aantal pixels veranderen. Dit wordt gedemonstreerd in onderstaande figuur.

Animatie die aangeeft waar een mogelijk optimale threshold ligt

Hierna wordt, zoals in een vorige post reeds vermeld, de autocorrelatie berekend en worden hiervan de pieken gezocht in een 8x8 window. In tegenstelling tot de vorige versie, waarbij de afstand tot de dichtstbijzijnde grotere piek als maat voor een lokale piek werd gebruikt, gebruiken we nu simpelweg de correlatiewaarde als maat wat betere resultaten geeft. We nemen initieel de 7 punten in de autocorrelatiefiguur met de hoogste waarde (1 punt is het middelpunt van de autocorrelatiefiguur, de andere 6 punten liggen ongeveer rond dit middelpunt). Voor elk van deze punten (behalve het middelpunt) wordt gecontroleerd of er in het verlengde van dit punt t.o.v. het middelpunt geen andere punten liggen met een hogere SSDn (sum of squared differences, normalized: een betere maat dan de correlatiemaat, maar rekenintensiever), want dit wijst erop dat de textuur een bijna-regulariteit vertoont, maar er dus geen is.

Autocorrelatiefiguur met het middelpunt in het rood en de 6 punten met hoogste correlatiewaarde in het geel

Textuur waarbij het algoritme oorspronkelijk een verkeerd rooster berekende

Autocorrelatie en de 7 punten met hoogste correlatiewaarde (de twee middelste gele punten zijn fout)

Autocorrelatie met gecorrigeerde punten

Vervolgens worden op deze 7 punten de GHT (general hough transform) toegepast. Indien dit geen resultaat geeft, wordt er iteratief telkens een extra punt genomen tot de GHT wel een resultaat geeft. Zo zijn er voor de eerste textuur 10 punten nodig.

De autocorrelatiefiguur met de 10 punten met hoogste correlatiewaarde die nodig zijn om 2 vectoren te vinden met de GHT

De textuur met het gevonden rooster

Dit algoritme slaagt erin het rooster te vinden van zowat alle testtexturen (ongeveer 200). Een nodige voorwaarde om het rooster te vinden is dat de textuur niet transparant mag zijn, bv. een hek vertoont verschillende gaten waardoor men de achtergrond kan zien. Bij deze texturen slaagt mijn algoritme er meestal nog wel in het rooster te vinden, maar niet altijd. Enkele voorbeelden.

Textuur van een hek waarbij het rooster correct bepaald wordt

Textuur van een hek waarbij het rooster niet correct bepaald wordt

Andere nodige voorwaarden zijn het feit dat de textuur een relatief groot deel van de afbeelding moet bedekken (minstens ongeveer 70%), de textuur niet te onregelmatig mag zijn en er minstens vier tegels aanwezig moeten zijn.

De rekentijd nodig voor het berekenen van het rooster is ongeveer 15 seconden voor een 500x500 afbeelding en na een optimalisatie van de genormaliseerde kruiscorrelatiemethode (normxcorr2) nog 9 seconden.

donderdag 18 december 2008

Wallpaper group classificatie (2)

De voorbije twee weken heb ik voornamelijk besteed aan het finetunen van het classificatiealgoritme beschreven in mijn vorige blogpost, en niet, zoals vermeld in die post, met het implementeren van een alternatief algoritme. Dat algoritme bleek te complex om op korte tijd (2 weken tot de thesispresentatie) te implementeren. En omdat het eerste algoritme nog geen acceptabele resultaten gaven, besloot ik dat algoritme verder te tunen.

Enkele van de aanpassingen zijn de volgende:
- detectie van glide reflection
- fixen van een bug in de code om een textuur te spiegelen over een bepaalde as
- beter selecteren van naburige roosterpunten in de correlatiefunctie en de mediaantegel registreren op deze roosterpunten
- fixen van enkele bugs in het classificatiegedeelte van de code

Al deze aanpassingen zorgden voor een verbetering van de resultaten. Om de tabel uit vorige post als vergelijking te gebruiken: de eerste 3 regels zijn mijn oude resultaten, de laatste 3 de resultaten van het algoritme in huidige vorm.

Tabel 1: trimmed normalized residual error van verschillende symmetrieën voor verschillende texturen en de uitkomst van het classificatiealgoritme

Nog een laatste opmerking is dat near-regular textures nu ook een stuk beter worden ondersteund, maar nog steeds geen bevredigende resultaten geven. Er is dus nog heel wat werk aan de winkel.