Autor Beitrag
wulfskin
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1349
Erhaltene Danke: 1

Win XP
D5 Pers (SSL), D2005 Pro, C, C#
BeitragVerfasst: So 25.09.11 10:56 
Hallo,

zur Filterung eines Bildes habe ich einen einfachen Fraktil-Filter erstellt. Ein Fraktil-Filter durchsucht alle Pixel eines Bilder und stellt sicher, dass innerhalb eines Fensters (2*n+1)*(2*m+1) der Pixel in der Mitte weniger hell ist als percentile Prozent aller Pixel im Fenster.

Die Implementierung sieht wie folgt aus (siehe Anhang):
  • In zwei Schleifen jeden Pixel in x und y durchgehen (Funktion: cvhFractileFilter).
  • Für jeden dieser Pixel in zwei Schleifen alle Pixel im Fenster (2*n+1)*(2*m+1) in eine geordnete Liste überführen (Funktion: cvhFractileFilterHelper).
  • Aus der Liste den Eintrag herausnehmen, für den die o.g. Bedienungung erfüllt ist.
Insgesamt besteht der Algorithmus also aus 4 Schleifen zur Durchsuchung der Pixel und des Fensters plus der Handhabung der Liste. Für letzteres habe ich eine priority_queue in C++ genommen.

Je nach Bild- und Fenstergröße benötigt der Algorithmus sehr lange. Deshalb habe ich an eine Optimierung nachgedacht, aber bis auf eine mögliche Optimierung in Assembler und mgl. der Liste ist mir nichts eingefallen. Ich bin leider nicht sehr erfahren, wenn es um Optimierungen geht.

Habt ihr Vorschläge, wie ich diesen Algorithmus optimieren kann? Platform für die Implementierung war C++ mit OpenCV.

Herzlichen Dank
Hans-Peter

ausblenden volle Höhe C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
unsigned char cvhFractileFilterHelper(IplImage *src, const int k, const int l, const int n, const int m, 
  const int percentile)
{
  priority_queue<unsigned char> L;

  // evaluate neighboor field
  for (int y = max(l - m, 0); y <= min(l + m, src->height - 1); y++)
  {
    for (int x = max(k - n, 0); x <= min(k + n, src->width - 1); x++)
    {
      if ((x != k) || (l != y))
      {
        L.push((unsigned char) src->imageData[y * src->widthStep + x]);
      }
    }
  }

  // return pixel within the desired percentile
  int res = 0;
  int max = floor(((100 - percentile) * L.size() / 100.0) + 0.5);
  for (int i = 1; i < max; i++)
  {
    res = L.top();
    L.pop();
  }
  return res;
}

void cvhFractileFilter(IplImage *src, IplImage *dst, const int n, const int m, 
  const int percentile)
{
  if ((!cvhCheckGrayscale(src)) || (!cvhCheckIfSameProperties(src, dst)) ||
    (n < 1) || (m < 1) || (percentile < 0) || (percentile > 100))
    return;

  for (int y = 0; y < src->height; y++)
  {
    for (int x = 0; x < src->width; x++)
    {
      dst->imageData[x + y * dst->widthStep] =
        (char) cvhFractileFilterHelper(src, x, y, n, m, percentile);
    }
  }
}

_________________
Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: So 25.09.11 12:51 
Was mir an Optimierungen erstmal auffällt, sind folgende Dinge:
- Divisionen immer aus einer Schleife rauslassen, das bringt schon mal einiges. Also einmal berechnen, wieviele Du da rausgreifen musst und dann nur einmalig die Division berechnen.
- Deiner Helper-Funktion in die andere Methode einfügen, weil Du dann die Berechnung aus dem ersten Punkt noch weiter nach außen bringen kannst im Schleifenkonstrukt.

- Warum erstellst Du keine auf char, statt unsigned char typisierte Priority Queue?
- Wo wir grad dabei sind: Das Push/Pop einer PQ ist auch noch mal O(n*log(n)), sprich derzeit hast Du O(n^5*log(n))

Wobei die eigentliche Frage ja das Auslesen der Pixel hier ist. Wie sieht die Klasse/Interface hinter den Bildklassen aus?

- Statt einer PQ könntest Du auch ein Array nehmen, welches für jeden Pixel-Wert die Anzahl speichert. in einem weiteren Schritt kann dieses Array durch einen Zähler ersetzt werden, den Du nur erhöhst, wenn der Pixel dunkler ist, als der aktuell untersuchte Pixel. Der Filter liefert dann eine 1 im Fenster, wenn der Zähler kleiner als die Fraktil-Variable ist (Ggf. Bedingungen etwas verdrehen). Damit wären wir dann bereits bei O(n^4) und hätten eine Queue durch eine einzige Variable ersetzt.

Das wäre erstmal, was mir sofort dazu einfällt, wobei Du damit schon mal um Längen schneller werden dürftest.

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
wulfskin Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1349
Erhaltene Danke: 1

Win XP
D5 Pers (SSL), D2005 Pro, C, C#
BeitragVerfasst: Mo 26.09.11 13:19 
Hallo Ben,

danke erstmal für die schnelle Antwort.

user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Divisionen immer aus einer Schleife rauslassen, das bringt schon mal einiges.
Die einzige Division in Zeile 20 muss innerhalb der Schleife (der Hauptfunktion) bleiben, da die Fenstergröße nicht konstant ist (wegen Rändern). Die Multiplikationen zur Berechnung des Spaltenoffsets habe ich nun aus den Schleifen herausgenommen.

user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Deiner Helper-Funktion in die andere Methode einfügen, weil Du dann die Berechnung aus dem ersten Punkt noch weiter nach außen bringen kannst im Schleifenkonstrukt.
Erledigt, aber die Begründung verstehe ich nicht.

user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Warum erstellst Du keine auf char, statt unsigned char typisierte Priority Queue?
Zur Sortierung der Helligkeiten benötige ich den vorzeichenunbehafteten Wert (255 = weiß, 0 = schwarz).

user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Wo wir grad dabei sind: Das Push/Pop einer PQ ist auch noch mal O(n*log(n)), sprich derzeit hast Du O(n^5*log(n))
Ich würde sogar sagen O(n^2*m^2*log(m)*m/2) wegen des Zugriffs auf das Listenelement in der Unterfunktion (n = Länge einer Bildseite, m = Länge des Betrachtungsfensters). Ich habe jetzt die Priority-Queue durch einen Vector ersetzt um eine konstante Zugriffszeit zu bekommen. Außerdem ist der Vector aufgrund der Array-Basis imho performanter, da die Kapazität konstant ist und somit kein verschieben von Speicher nötig ist.

user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Wobei die eigentliche Frage ja das Auslesen der Pixel hier ist. Wie sieht die Klasse/Interface hinter den Bildklassen aus?
Zur Vereinfachung nehmen wir ein Graustufenbild. Die Pixel sind zeilenweise fortlaufend angeordnet. Also pro Pixel ein Char mit der Helligkeitsinformation, macht insgesamt (Breite * Hoehe) Chars. Ich könnte natürlich (vgl. mit Scanline) eine komplette Zeile auslesen und durch diese dann iterieren, aber ich sehe darin keinen Vorteil.

user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Statt einer PQ könntest Du auch ein Array nehmen, welches für jeden Pixel-Wert die Anzahl speichert. in einem weiteren Schritt kann dieses Array durch einen Zähler ersetzt werden, den Du nur erhöhst, wenn der Pixel dunkler ist, als der aktuell untersuchte Pixel. (..)
Gute Idee. Wobei dann die Information über die Helligkeit fehlt und diese wird ja letztendlich verwendet um den Pixel in der Mitte des Fensters zuzweisen.

Insgesamt habe ich nun also eine Performance von O(n^5*log(n)) (für m=n). Ist es schneller die Elemente direkt beim Einfügen zu sortieren? Sonstige Ideen?

Modifizierter Code (im Vergleich zum vorheringen Code habe ich noch eine fünften übergeordnete Schleife eingefügt, mit der die Anzahl der Versuche (passes) angegeben werden kann) - diese dient nur zu Testzwecken und kann ignoriert werden):
ausblenden volle Höhe C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
void cvhFractileFilter(IplImage *src, IplImage *dst, const int n, const int m, 
  const int percentile, const int passes)
{
  if ((!cvhCheckGrayscale(src)) || (!cvhCheckIfSameProperties(src, dst)) ||
    (n < 1) || (m < 1) || (percentile < 0) || (percentile > 100) || (passes < 1))
    return;

  // array with neighboor pixels
  vector<unsigned char> L;
  L.resize((2*n+1)*(2*m+1) - 1);

  for (int p = 0; p < passes; p++)
  {
    // cykle through all columns
    for (int y = 0; y < src->height; y++)
    {
      // calculate column pixel offset
      int col = y * src->widthStep;
      // cykle through all rows
      for (int x = 0; x < src->width; x++)
      {
        // evaluate window
        // empty array
        L.clear();
        // cykle through all window rows
        int wsize_y = min(y + m, src->height - 1);
        for (int wy = max(y - m, 0); wy <= wsize_y; wy++)
        {
          // calculate window column pixel offset
          int wcol = wy * src->widthStep;
          // cykle through all window columns
          int wsize_x = min(x + n, src->width - 1);
          for (int wx = max(x - n, 0); wx <= wsize_x; wx++)
          {
            // check whether window pixel differs from center pixel
            if ((wx != x) || (wy != y))
            {
              L.push_back(src->imageData[wcol + wx]);
            }
          }
        }
        sort(L.begin(), L.end());
        int i = min((int) ((100 - percentile) * L.size() / 100.0), (int) L.size() - 1);
        dst->imageData[col + x] = (char) L[i];
      }
    }
  }
}

Herzlichen Dank
Hans-Peter

_________________
Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Mo 26.09.11 14:32 
user profile iconwulfskin hat folgendes geschrieben Zum zitierten Posting springen:
Hallo Ben,

danke erstmal für die schnelle Antwort.

Kein Ding.

user profile iconwulfskin hat folgendes geschrieben Zum zitierten Posting springen:
user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Divisionen immer aus einer Schleife rauslassen, das bringt schon mal einiges.
Die einzige Division in Zeile 20 muss innerhalb der Schleife (der Hauptfunktion) bleiben, da die Fenstergröße nicht konstant ist (wegen Rändern). Die Multiplikationen zur Berechnung des Spaltenoffsets habe ich nun aus den Schleifen herausgenommen.

Dann schau Dir mal an, ob Du eine Lookup-Tabelle für die Größen hinbekommst. Sprich

ausblenden C#-Quelltext
1:
2:
3:
4:
5:
for(int i = 1; i <= w; i++) {
    for(int j = 1; j <= h; j++) {
        p[j, i] = (int)(((100-percentile)*(i*j-1))/100.0); //Index für Zugriff
    }
}


Zusätzlich die Größe n und m vor den beiden Schleifen so anpassen (mit min und max), dass in der Schleifeninitialisierung der Aufruf entfallen kann.

user profile iconwulfskin hat folgendes geschrieben Zum zitierten Posting springen:
user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Deiner Helper-Funktion in die andere Methode einfügen, weil Du dann die Berechnung aus dem ersten Punkt noch weiter nach außen bringen kannst im Schleifenkonstrukt.
Erledigt, aber die Begründung verstehe ich nicht.

Grob gesagt bildet jede Funktion einen Sichtbarkeitsbereich, innerhalb dessen man seine Anweisungen ausführt. Hat man nun eine Berechnung, die sehr oft ausgeführt werden muss (besagte Funktion), darin aber eine Anweisung, deren Wert sich praktisch nie ändert, so wird diese "Konstante" dennoch immer neu berechnet. Löst man nun diese innere Funktion auf, so kann man diese Berechnung außerhalb dieser Schleife bereits erledigen und bekommt damit den Gewinn, dass die Konstante halt auch nur einmal ausgerechnet wird.

user profile iconwulfskin hat folgendes geschrieben Zum zitierten Posting springen:
user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Warum erstellst Du keine auf char, statt unsigned char typisierte Priority Queue?
Zur Sortierung der Helligkeiten benötige ich den vorzeichenunbehafteten Wert (255 = weiß, 0 = schwarz).

Oops, mein Fehler. Bin von Delphi ausgegangen, wo Byte=Char=unsigned ist.

user profile iconwulfskin hat folgendes geschrieben Zum zitierten Posting springen:
user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Wo wir grad dabei sind: Das Push/Pop einer PQ ist auch noch mal O(n*log(n)), sprich derzeit hast Du O(n^5*log(n))
Ich würde sogar sagen O(n^2*m^2*log(m)*m/2) wegen des Zugriffs auf das Listenelement in der Unterfunktion (n = Länge einer Bildseite, m = Länge des Betrachtungsfensters). Ich habe jetzt die Priority-Queue durch einen Vector ersetzt um eine konstante Zugriffszeit zu bekommen. Außerdem ist der Vector aufgrund der Array-Basis imho performanter, da die Kapazität konstant ist und somit kein verschieben von Speicher nötig ist.

Jup. Durch den einheitlichen Sichtbarkeitsbereich entfällt sogar zusätzlich noch Arbeit des Memory-Managers wegen Out-of-Scope-Finalisierung des Objektes.

user profile iconwulfskin hat folgendes geschrieben Zum zitierten Posting springen:
user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Wobei die eigentliche Frage ja das Auslesen der Pixel hier ist. Wie sieht die Klasse/Interface hinter den Bildklassen aus?
Zur Vereinfachung nehmen wir ein Graustufenbild. Die Pixel sind zeilenweise fortlaufend angeordnet. Also pro Pixel ein Char mit der Helligkeitsinformation, macht insgesamt (Breite * Hoehe) Chars. Ich könnte natürlich (vgl. mit Scanline) eine komplette Zeile auslesen und durch diese dann iterieren, aber ich sehe darin keinen Vorteil.

Also im Grunde ein blankes Array ohne zusätzliche Magie beim Zugriff? Ne, dann passt das so bereits.

Frag nur, weil Konstrukte wie TCanvas.Pixels[x,y] sind relativ lahm, da die immer noch haufenweise andere Sachen Machen. Wenn Du aber schon direkten Zugriff auf den Speicherbereich hast, dann ist das wirklich auch nur der Griff in den Speicher.

user profile iconwulfskin hat folgendes geschrieben Zum zitierten Posting springen:
user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Statt einer PQ könntest Du auch ein Array nehmen, welches für jeden Pixel-Wert die Anzahl speichert. in einem weiteren Schritt kann dieses Array durch einen Zähler ersetzt werden, den Du nur erhöhst, wenn der Pixel dunkler ist, als der aktuell untersuchte Pixel. (..)
Gute Idee. Wobei dann die Information über die Helligkeit fehlt und diese wird ja letztendlich verwendet um den Pixel in der Mitte des Fensters zuzweisen.

Bin jetzt von einem binären Filter ausgegangen, der einfach nur S/W ausgibt im Ergebnis-Bild, ob die Bedingung erfüllt ist. Wenn natürlich die eigentliche Percentile-Information benötigt wird, kann man auf diese n*log(n) schleicht verzichten.

user profile iconwulfskin hat folgendes geschrieben Zum zitierten Posting springen:
Insgesamt habe ich nun also eine Performance von O(n^5*log(n)) (für m=n). Ist es schneller die Elemente direkt beim Einfügen zu sortieren?

Es gibt nen Beweis, dass das Sortieren durch Vergleich mindestens n*log(n) benötigt, egal wann der Vergleich gemacht wird. Das Sortieren beim Einfügen hat aber sogar den Nachteil, dass du den Overhead der Sortier-Routine nicht nur einmal, sondern mehrfach hast.

user profile iconwulfskin hat folgendes geschrieben Zum zitierten Posting springen:
Sonstige Ideen?

Ich hab von jemandem gehört, der das die Tage mal in nen Textur-Shader gegossen hat. Wenn derjenige sich bitte kurz mit Code melden könnte ;-)

user profile iconwulfskin hat folgendes geschrieben Zum zitierten Posting springen:
Modifizierter Code (im Vergleich zum vorheringen Code habe ich noch eine fünften übergeordnete Schleife eingefügt, mit der die Anzahl der Versuche (passes) angegeben werden kann) - diese dient nur zu Testzwecken und kann ignoriert werden):
ausblenden volle Höhe C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
void cvhFractileFilter(IplImage *src, IplImage *dst, const int n, const int m, 
  const int percentile, const int passes)
{
  if ((!cvhCheckGrayscale(src)) || (!cvhCheckIfSameProperties(src, dst)) ||
    (n < 1) || (m < 1) || (percentile < 0) || (percentile > 100) || (passes < 1))
    return;

  // array with neighboor pixels
  vector<unsigned char> L;
  L.resize((2*n+1)*(2*m+1) - 1);

  for (int p = 0; p < passes; p++)
  {
    // cykle through all columns
    for (int y = 0; y < src->height; y++)
    {
      // calculate column pixel offset
      int col = y * src->widthStep;
      // cykle through all rows
      for (int x = 0; x < src->width; x++)
      {
        // evaluate window
        // empty array
        L.clear();
        // cykle through all window rows
        int wsize_y = min(y + m, src->height - 1);
        for (int wy = max(y - m, 0); wy <= wsize_y; wy++)
        {
          // calculate window column pixel offset
          int wcol = wy * src->widthStep;
          // cykle through all window columns
          int wsize_x = min(x + n, src->width - 1);
          for (int wx = max(x - n, 0); wx <= wsize_x; wx++)
          {
            // check whether window pixel differs from center pixel
            if ((wx != x) || (wy != y))
            {
              L.push_back(src->imageData[wcol + wx]);
            }
          }
        }
        sort(L.begin(), L.end());
        int i = min((int) ((100 - percentile) * L.size() / 100.0), (int) L.size() - 1);
        dst->imageData[col + x] = (char) L[i];

      }
    }
  }
}

Herzlichen Dank
Hans-Peter

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Für diesen Beitrag haben gedankt: wulfskin
wulfskin Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1349
Erhaltene Danke: 1

Win XP
D5 Pers (SSL), D2005 Pro, C, C#
BeitragVerfasst: Mo 26.09.11 14:53 
Hallo Ben,

nochmals danke. Ich habe alles soweit verstanden. Ich schau mir jetzt noch die Verbesserung mit der Lookup-Tabelle an und prüfe, inwieweit sich die Laufzeit dadurch noch verkürzen lässt.

user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Also im Grunde ein blankes Array ohne zusätzliche Magie beim Zugriff?
Genau, man greift direkt auf den Bildspeicher zu.

Viele Grüße
Hans-Peter

_________________
Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.
wulfskin Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1349
Erhaltene Danke: 1

Win XP
D5 Pers (SSL), D2005 Pro, C, C#
BeitragVerfasst: Mo 26.09.11 16:01 
Hallo Ben,

user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
Dann schau Dir mal an, ob Du eine Lookup-Tabelle für die Größen hinbekommst. Sprich

ausblenden C#-Quelltext
1:
2:
3:
4:
5:
for(int i = 1; i <= w; i++) {
    for(int j = 1; j <= h; j++) {
        p[j, i] = (int)(((100-percentile)*(i*j-1))/100.0); //Index für Zugriff
    }
}

ich habe jetzt die Lösung mit der Lookup-Tabelle erstellt und tatsächlich nochmal etwas Zeit gewonnen. Allerdings verstehe ich den Grund dafür nicht wirklich. Ich meine, die Division muss ja immer noch zum Befüllen der Tabelle gerechnet werden. Warum ist das an anderer Stelle schneller?

Viele Grüße
Hans-Peter

_________________
Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Mo 26.09.11 16:41 
Divisionen sind teuer. Im Vergleich zu nem Speicheruugriff oder sogar Cache Hit etwa Faktor 100 bis 5000 bei modernen CPUs daher zählt nur deren Anzahl. Und da bei dir W*H>>N*M ist das insgesamt schneller.

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Für diesen Beitrag haben gedankt: wulfskin