Autor |
Beitrag |
wulfskin
      
Beiträge: 1349
Erhaltene Danke: 1
Win XP
D5 Pers (SSL), D2005 Pro, C, C#
|
Verfasst: 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
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;
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]); } } }
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
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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 
      
Beiträge: 1349
Erhaltene Danke: 1
Win XP
D5 Pers (SSL), D2005 Pro, C, C#
|
Verfasst: Mo 26.09.11 13:19
Hallo Ben,
danke erstmal für die schnelle Antwort.
BenBE hat folgendes geschrieben : | 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.
BenBE hat folgendes geschrieben : | 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.
BenBE hat folgendes geschrieben : | 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).
BenBE hat folgendes geschrieben : | 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.
BenBE hat folgendes geschrieben : | 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.
BenBE hat folgendes geschrieben : | 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):
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;
vector<unsigned char> L; L.resize((2*n+1)*(2*m+1) - 1);
for (int p = 0; p < passes; p++) { for (int y = 0; y < src->height; y++) { int col = y * src->widthStep; for (int x = 0; x < src->width; x++) { L.clear(); int wsize_y = min(y + m, src->height - 1); for (int wy = max(y - m, 0); wy <= wsize_y; wy++) { int wcol = wy * src->widthStep; int wsize_x = min(x + n, src->width - 1); for (int wx = max(x - n, 0); wx <= wsize_x; wx++) { 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
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Mo 26.09.11 14:32
wulfskin hat folgendes geschrieben : | Hallo Ben,
danke erstmal für die schnelle Antwort. |
Kein Ding.
wulfskin hat folgendes geschrieben : | BenBE hat folgendes geschrieben : | 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
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); } } |
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.
wulfskin hat folgendes geschrieben : | BenBE hat folgendes geschrieben : | 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.
wulfskin hat folgendes geschrieben : | BenBE hat folgendes geschrieben : | 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.
wulfskin hat folgendes geschrieben : | BenBE hat folgendes geschrieben : | 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.
wulfskin hat folgendes geschrieben : | BenBE hat folgendes geschrieben : | 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.
wulfskin hat folgendes geschrieben : | BenBE hat folgendes geschrieben : | 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.
wulfskin hat folgendes geschrieben : | 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.
wulfskin hat folgendes geschrieben : | 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
wulfskin hat folgendes geschrieben : | 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):
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;
vector<unsigned char> L; L.resize((2*n+1)*(2*m+1) - 1);
for (int p = 0; p < passes; p++) { for (int y = 0; y < src->height; y++) { int col = y * src->widthStep; for (int x = 0; x < src->width; x++) { L.clear(); int wsize_y = min(y + m, src->height - 1); for (int wy = max(y - m, 0); wy <= wsize_y; wy++) { int wcol = wy * src->widthStep; int wsize_x = min(x + n, src->width - 1); for (int wx = max(x - n, 0); wx <= wsize_x; wx++) { 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 
      
Beiträge: 1349
Erhaltene Danke: 1
Win XP
D5 Pers (SSL), D2005 Pro, C, C#
|
Verfasst: 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.
BenBE hat folgendes geschrieben : | 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 
      
Beiträge: 1349
Erhaltene Danke: 1
Win XP
D5 Pers (SSL), D2005 Pro, C, C#
|
Verfasst: Mo 26.09.11 16:01
Hallo Ben,
BenBE hat folgendes geschrieben : | Dann schau Dir mal an, ob Du eine Lookup-Tabelle für die Größen hinbekommst. Sprich
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); } } | |
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
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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
|
|
|