[Alg] Algoritme om een matrix te genereren *

[Jurgle]

Beste,

Bij websites waar je accounts aan kan maken zie je vaak dat er daarbij een plaatje getoond wordt met 'random' tekst/cijfers en of je die over wil tikken in het textfield eronder. Nu wil ik ook zo'n ding maken en dat is mij al aardig gelukt. Het probleem zit hem in het eventuele blurren van een gegenereerd plaatje.

Het blurren lukt, ik heb een implementatie van de welbekende gaussian blur gemaakt. Waar ik geen wiskundig algoritme voor kan verzinnen en moeilijk te vinden is op google is de radius van de blur. Ik gebruik hier nu matrixen voor van breedte:hoogte = oneven:oneven, maar wel gelijk aan elkaar. Voorbeelden van twee matrixen (voorgedefinieerd in de PHP code) staan hieronder.

In plaats van 2 voorgedefinieerde matrixen wil ik graag dat ik de radius kan definieren en dat er een matrix uitkomt. Mijn vraag aan de community: Hoe doe ik dit?

De 9x9 matrix die ik op google heb kunnen vinden met daaronder een verzonnen matrix:

code:

      $res = array();
      if($x == 9)
      {
         $res[] = array(0,  0,  1,  1,  1,  1,  1,  0,  0);
         $res[] = array(0,  1,  2,  3,  3,  3,  2,  1,  0);
         $res[] = array(1,  2,  3,  6,  7,  6,  3,  2,  1);
         $res[] = array(1,  3,  6,  9, 11,  9,  6,  3,  1);
         $res[] = array(1,  3,  7, 11, 12, 11,  7,  3,  1);
         $res[] = array(1,  3,  6,  9, 11,  9,  6,  3,  1);
         $res[] = array(1,  2,  3,  6,  7,  6,  3,  2,  1);
         $res[] = array(0,  1,  2,  3,  3,  3,  2,  1,  0);
         $res[] = array(0,  0,  1,  1,  1,  1,  1,  0,  0);
      }
      else
      {
         $res[] = array(1,  1,  1);
         $res[] = array(1,  2,  1);
         $res[] = array(1,  1,  1);
      }

[gorgi_19]

Geef even een suggestie voor een goede titel via

[BasieP]

met alleen een radius kom je er niet denk ik, je heb ook een maximale diepte nodig (bijv uit je voorbeeld '12', en '2')

verder denk ik dat er verschillende soorten zijn, de voorbeelden hierboven zijn soort van 'rondjes', maar je kan ze natuurlijk ook heel anders maken (motion blurs bijv.)

wanneer je voor een rondje gaat zal je denk ik moeten kijken naar sin/tan/cos functies.

Dan is er nog de vraag, wil je dat de diepte van je blur een sinus vorm heeft? dus zoiets:

0, 1, 1, 2, 3, 4, 6, 8, 9, 10, 10, 11, 10, 10, 9, 8, 6, 4, 3, 2, 1, 1, 0

of met het een lineare blur zijn? dus zoiets:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

ik denk dat de keuze voor linear, of sinusvormig hardcoded kunnen worden, aangezien je zoiets maar 1x veranderd. de diepte zou ik wel aanpasbaar maken, met een goed alogoritme moet het ook neit zo moeilijk zijn om aan te passen.

qua functie zou je dus iets van makeBlurMatrix(size, depth); kunnen maken, die een array terug geeft ofzo.

[ Voor 55% gewijzigd door BasieP op 06-05-2005 14:26 ]

[Jurgle]

De diepte is inderdaad ook een belangrijke en neem ik er zeker in mee.

Bij deze blur gaat het om de rondjes, dat had ik moeten vermelden in de startpost. Ik ben me ervan bewust dat het met een andere matrix heel makkelijk tot een motion blur te vervormen is.

Over het verloop van de diepte van de blur: er schijnt naast een sinus of lineair verloop ook een 'gaussian' verloop de zijn. Die zoek ik.


Een oplossing die ik had bedacht, maar erg langzaam is:
- Je maakt een image van x bij x pixels
- For straal = x / 2 to 0 : teken een cirkel in het midden van de image met een kleurverloop van zwart naar wit.
- Lees de kleur van de image uit en zet de waarde van de grayscale in de matrix.

Het nadeel hiervan is dus dat het langzaam is, bijkomend is dat dit niet de gaussian blur is, maar een lineare. *zucht*

[ Voor 3% gewijzigd door Jurgle op 06-05-2005 14:47 ]

[BasieP]

edit: Even een groote lap hardop denken van mij

het concept van jouw methode is goed, alleen kan het ook zonder plaatje. (wat het een stuk sneller maakt)
je kan dmv sinus functies (sin, cos, tan) ook posities op een circel berekenen

stel, je wilt een matrix van 9 groot, met een maximale diepte van 11.
dan maak je een iteratie (lus) die 4x (9/2) het berekenen van alle punten in de matrix doet die op een afstand van i (iteratie waarde) liggen vanaf het middelpunt.

zo krijg je dus:

i=0     midden van je matrix, word maximale diepte = 11
i=1     bereken binnenste circel 11 - 11 / 9 / 2 * i diep (dus 8.55 = 8)
i=2     bereken tweede circel    11 - 11 / 9 / 2 * i diep (dus 6.11 = 6)
i=3     bereken derde circel     11 - 11 / 9 / 2 * i diep (dus 3.66 = 4)
i=4     bereken vierde circel    11 - 11 / 9 / 2 * i diep (dus 1.22 = 1)

zoals je ziet klopt de berekening van diepte niet, want dit is een lineare

en dan komt het probleem met deze methode (die ik me nu pas realiseer)
doordat je afrondingsfouten heb, zul je een aantal velden overslaan!

zeker wanneer je een groote matrix heb, zal door afrondingsfouten velden die diagonaal tov het midden staan wel eens overgeslagen kunnen worden..

ditzelfde zou ook tot gevolg hebben dat je harde randen ziet, ipv een mooie gradient.


derhalve zou ik dus gaan voor een andere methode, namelijk:
je tekent in een willekeurige fotoeditor een redelijk grote gradient stip (dus gewoon witte achtergrond, en in grijstinten een 'bal' die in het midden zwart is)

deze lees je mbv php in, en laat daar een 2d iteratie op los.
ipv dat je de diepte uitrekent, haal je hem dus per veld uit het plaatje

[ Voor 7% gewijzigd door BasieP op 06-05-2005 15:47 ]

[Soultaker]

Een 'Gaussian blur' is gewoon een filter waarbij de invloed van de samples normaal verdeeld is. (een 'Guassian distribution' is gewoon een 'normale verdeling').

Een normale verdeling heeft een gemiddelde en een variantie (per definitie gelijk aan het kwadraat van de standaarddeviatie, sigma). Omdat je de intensiteit van het plaatje hetzelfde wil houden, wil je een gemiddelde van 1 gebruiken. Om een 2D filter te maken kun je dan de volgende formule voor een 2D normale verdeling gebruiken:

Waarbij x en y dus coordinaten ten opzichte van het middelpunt zijn. Als je dus een 5x5 matrix hebt, dan zet je op de bovenste rij bijvoorbeeld de waarden van G(-2,-2) tot en met G(+2,-2), daaronder (G-2,-1) tot en met G(+2,-1), enzovoorts.

In de formule is sigma dus de standaarddeviatie, een maat van hoe sterk het filter is dat je maakt (hoe groter sigma, hoe meer blur-effect). Hoe groot de matrix die je maakt moet zijn hangt dus ook af van die standaarddeviatie: als je meer blur hebt op een bepaalde pixel, worden er meer pixels uit de omgeving bij betrokken. Wat je meestal doet is ofwel een grens kiezen op basis van de waarden in de matrix (bijvoorbeeld: als er geen getal kleiner dan 0.1 op de rand zit, stop ik, anders voeg ik nog een rand toe), ofwel een grootte afhankelijk van de standaarddeviatie (bijvoorbeeld: 3*sigma).

Lijkt me dat dit allemaal gewoon te implementeren is in PHP:
• kies een standaarddeviatie (sterkte van het filter)
• kies (bijvoorbeeld) de grootte N van je NxN matrix als 3*sigma, afgerond op een oneven getal
• vul de elementen van de matrix in aan de hand van de gegeven formule.

Merk op dat je de constante term 1/(2*pi*sigma²) mee kunt nemen in de elementen, of later toe kunt passen (je telt dan eerst de waarden van de samples op, en deelt het gebeuren dan door 2*pi*sigma²). Het voordeel daarvan is dat in je matrix dan alleen maar gehele getallen, wat sneller en nauwkeuriger rekent (tot een zekere grens). Verder is het waarschijnlijk zinnig (omdat je niet een oneindig grote matrix hebt), om alleen de relatieve waarden in de matrix te stoppen, en vervolgens de som van de waarden in de matrix te berekenen en daar door te delen. Die som is namelijk kleiner dan 2*pi*sigma², dus als je daar door zou delen zou je wat intensiteit verliezen.

edit:
BasieP: die methode van jouw is helemaal niet handig. Je moet het precies andersom doen, namelijk voor elk element in de matrix kijken welke waarde die krijgt. Als je dus een lineaire afstand tot het middelpunt wil hebben, gebruik je een functie F(x,y) = sqrt(x² + y²). In de matrix krijg je dan de waarden m_ij = F(j-x,i-y) (waarbij x,y het middelpunt is, dus bijvoorbeeld 3,3 voor een 5x5 matrix).

[ Voor 12% gewijzigd door Soultaker op 06-05-2005 15:55 ]

[Sjaaky]

Op wikipedia onder Gaussian function staat f(x) = a * e ^ -(x-b)^2/c^2
Dat is dus een 1-dimensionale functie. a, b en c zijn reele waarden die je kan 'instellen'. a is een soort van amplitude, b is het centrum, c is een soort van radius. Om dit 2 dimensionaal te maken gebruik je de functie 2 maal eenmaal voor de x-richting en eenmaal voor de y-richting. De 2 resultaten hiervan vermenigvuldig je met elkaar voor het definitieve antwoord.
_{ok, rijkelijk laat....}

[ Voor 6% gewijzigd door Sjaaky op 06-05-2005 16:02 ]

[Jurgle]

Hier kan ik wel wat mee, bedankt!