[c#] Snelle matrix operaties

[Iska]

Hi allemaal,

Ik ben nu een tijdje bezig met een 'depth map' te maken mbv 2 foto's, die parallel op een paar cm van elkaar zijn genomen, ala je ogen. Om onderscheid te maken tussen verschillende objecten heb ik gekozen voor een cross-correlation. Het probleem is nu echter dat ik moet gaan werken met grote matrices (foto's) en dat gaat allemaal erg traag.

Voor de cross-correlation op een bepaald punt x,y heb je de volgende gegevens nodig (zie formule link):
1) De waarden van een matrix gekwadrateerd (inwendig product van zichzelf?) en opgeteld
2) Van alle waarden in de matrix een getal aftrekken
3) De sommatie van een matrix
4) De werkelijke correlatie uitrekenen

Bij de toepassing van 1, 2 en 3 heb ik het volgende:

code:

y = 0; x = 0;
while (x < width)
{
  while (y < height)
    {
      leftCorrArr[x, y] = leftDataArr[x, y] - leftAvr; //Getal aftrekken van waarde
      norml += leftCorrArr[x, y] * leftCorrArr[x, y]; //Waarde kwadrateren

      rightCorrArr[x, y] = rightDataArr[x, y] - rightAvr;
      normr += rightCorrArr[x, y] * rightCorrArr[x, y];

      y++;
    }

    x++;
    y = 0;
}

Voor het laatste heb ik dit

code:

normt = (int) Math.Pow(norml * normr, 0.5);

y = 0; x = 0;
u = 0; v = 0;

while (u < width)
{
  while (v < height)
  {
    while (x < width)
    {
      while (y < height)
      {
        xt = x; yt = y;
        if (x - u < 0) xt = width + (x - u); //Wanneer hij bij het begin van de matrix is aangekomen, verder vanaf de rechter kant van de afbeelding
        if (y - v < 0) yt = height + (y - v); //,,

        corrDataArr[u, v] += leftCorrArr[x, y] * rightCorrArr[xt, yt];

        y++;
      }

      x++;
      y = 0;
    }

    corrDataArr[u, v] = (int) ((255f * (float) corrDataArr[u, v]) / (float)normt); //Uiteindelijke data

    v++;
    x = 0;
  }

  u++;
  v = 0;
}

Het vervelende is dat dit gewoon vreselijk traag is! Bij een afbeelding van 100*75 duurt het hele proces toch al snel een seconde of 2, dus 1024*768 hoef ik nieteens te proberen (is trouwens op een E8400@3,6).

Nu is mijn vraag:
Is er een manier om in c(#) heel snel matrix operaties, zoals die uit het lijstje, uit te voeren? Op deze manier gaat het namelijk gewoon echt TE traag!

Alvast bedankt

[Mijzelf]

Je bent in elk geval te veel werk aan het doen. Een correspondentiepunt in het linkerbeeld kan niet echt op een andere hoogte zitten dan in het rechter beeld, dus je hoeft niet voor iedere pixel de hele hoogte van het andere plaatje te doorlopen. Een paar pixels marge zou voldoende moeten zijn. (Tenzij je je camera opstelling niet weet, maar die zou je moeten weten na 1 keer alles doorrekenen)

Verder kan een correspondentiepunt in het rechterbeeld nooit rechts van die in het linkerbeeld zitten, en vice versa, dus je kunt je breedte scan ook aardig beperken.

[Reptile209]

Zijn er geen Matlab-achtige lib's voor C#? Matlab kan dit soort bulk-operaties op matrices echt supersnel, veel sneller dan je ooit zelf zult implementeren. Of gaat het je (ook) om het leerproces en is een dergelijke shortcut dus een beetje te makkelijk?

[JanWillem32]

Dit is een heel bekend programmeer probleem bij zo ongeveer alle programmeurs die ooit met programmeren voor afbeeldingen te maken hebben gehad.
http://software.intel.com...uilt-in-cpu-acceleration/
(Zelf zou ik iets andere code gebruiken, maar het gaat om het voorbeeld.)
De manier voor programmeren voor SIMD en multi-threading is niet gemakkelijk snel aan te leren, maar is het wel helemaal waard.
Voor grafische bewerkingen heb ik zelf meer de specializatie gekozen voor GPU acceleratie d.m.v. DirectX, maar dat is ook nogal een vak apart (en verstand van het bovenstaande is daarvoor nog steeds aanbevolen).

[Nick The Heazk]

Ik zou je eigen link nog eens goed doornemen. Daarin wordt uit de doeken gedaan hoe je die normalized cross-correlation op een meer efficiënte manier kunt implementeren dan de straightforward manier (het naieve algoritme). Alle bekommernissen inzake SIMD, parallel, Matlab zijn op dit moment, imo, niet relevant. Probeer eerst eens de efficiënte versie te implementeren, die in de paper waarnaar je linkt, beschreven wordt.

Een goed alternatief bestaat eruit om eens te Googlen of er geen bibliotheken bestaan die deze functionaliteit voor jou implementeren.

[Av3ng3rtje]

Effe snel googled: http://research.microsoft.com/en-us/projects/Accelerator/

't Proberen waard

[Iska]

@Mijzelf (lol)
Hoewel het inderdaad een hoop zal schelen vind ik de aanname dat de opstelling altijd loodrecht staat niet heel praktisch. Het 2de punt dat je maakt is daarentegen wel sterk, ik ga daar zeker even naar kijken!

@Reptile209
Matlab is niet bepaald snel. Heb het vaker gebruikt maar was niet erg van ondersteboven.. Verder is dit gewoon om het me leuk leek om te doen en ik een paar uurtjes vrij had deze week . Geen bijzondere reden

@JanWillem32
Bedankt voor de link! Ik heb al redelijk wat geëxperimenteerd met OpenCL, maar ik heb het 'parallel denken' nog niet zo goed onder de knie als lineair. Daarom wilde ik eerst de code maken in single-thread om daarna misschien over te kunnen zetten naar OpenCL. Voordat ik dat ga doen wil ik echter wel goed geoptimaliseerde code hebben

@Nick The Heazk
Ik moet vaker verder dan de eerste alinea lezen . Zal maar even moeten gaan zoeken naar optimalisaties (bijv. zoals Mijzelf aangaf)..

@Av3ng3rtje
Kende ik nog niet! Kan ik het iig 2x sneller maken bij gebruik van CPU

Bedankt voor jullie reacties!

[Mijzelf]

Iska schreef op zondag 04 september 2011 @ 22:52:
Hoewel het inderdaad een hoop zal schelen vind ik de aanname dat de opstelling altijd loodrecht staat niet heel praktisch.

Loodrecht staan? Dat heeft hier weinig mee te maken. Ik neem aan dat je je twee camera's op de een of andere manier gefixeerd hebt tov elkaar. (Anders zul je zowiezo een groot probleem hebben om je diepte-informatie te kwantificeren). Deze fixatie bepaald hoe de de correspondentiepunten kunnen staan in de beide camerabeelden.

[windancer]

Twee gedachten :

• Matlab is niet langzaam mits je niet zelf dingen gaat uitprogrammeren. Je moet gaan denken in matrices en operaties op matrices.
• De standaard manier om snelle matrix operaties te doen is gebruik maken van een geoptimaliseerde LAPACK library. De bekendste hiervan is de MKL van Intel. Voor het .Net framework zijn hier managed wrappers voor. Voorbeelden hiervan zijn Math.NET en ILNumerics.net. Bij deze wrappers wordt vaak de MKL library zelf meegeleverd.