Problem mit SUSAN Implementierung

Question

Wiedereinmal habe ich ein Problem beim Implementieren eines Algorithmus. Der SUSAN Algorithmus berechnet die Anzahl der Pixel um das mittlere Pixel die innerhalb einer gewissen Abweichung liegen, und soll eigentlich schneller als der Canny Algorithmus sein.

Es werden jeweils 36 Pixel um das mittlere betrachtet. Bei mir ist dieser Algorithmus allerdings langsamer, als Canny, weswegen ich vermute es liegt an den if-Anweisungen.

        private static void ApplyUSAN(int t)
        {
            int widthTemp = width - 3;
            int heightTemp = height - 3;
            int tempP = 0;
            byte tempPixNValue;

            for (int x = 3; x < widthTemp; ++x)
            {
                for (int y = 3; y < heightTemp; ++y)
                {
                    tempP = image[x, y];

                    tempPixNValue = 0;
//wiederholt die untenstehende if-Anweisung, mit allen x und y werten innerhalb einer ca. runden 37 Pixel fassenden Maske mit Radius r=3,5 Pixel (also ohne das Zentrum 3)

             if (Math.Abs(image[x + 3, y + 1] -tempP) <= t)
                 {
                        tempPixNValue += 1;
                 }

                    USANImage[x, y] = tempPixNValue;

                }
            }
        }

Hat vielleicht jemand eine Idee, wie man die if-Anweisung, die die Abweichung überprüft, optimieren könnte?

Answer 1

... weswegen ich vermute es liegt an den if-Anweisungen.

Hallo,

welchen if-Verzweigungen? In Deinem code sehe ich nur eine, die auch nur eine Zuweisung vornimmt. Der nachfolgende Methodenaufruf - USANImage[x, y] = tempPixNValue; - liegt ja außerhalb des if-blocks und wird somit von Deinem code immer ausgeführt...

Infos zum Algorithmus:

http://users.fmrib.ox.ac.uk/~steve/susan/susan/susan.html

c-code:

http://users.fmrib.ox.ac.uk/~steve/susan/

Viele Grüße,

  Thorsten

Answer 2

Insgesammt sind es 37 if-Anweisungen, die ich, wegen der schlechten Lesbarkeit, hier ausgespart habe.

Diese fragen alle Pixel um die Mitte ab.

Answer 3

Insgesammt sind es 37 if-Anweisungen, die ich, wegen der schlechten Lesbarkeit, hier ausgespart habe.

Wenn Du wissen willst, wie Du einen bestimmten Code verbessern kannst, bringt es nicht, diesen Code "auszusparen". Daher poste diesen bitte oder stell ihn als Textdatei, alternativ als kleines, lauffähiges Projekt online zur Verfügung.

---

Gruß, Stefan
Microsoft MVP - Visual Developer ASP/ASP.NET
http://www.asp-solutions.de/ - Consulting, Development
http://www.aspnetzone.de/ - ASP.NET Zone, die ASP.NET Community

Answer 4

Also gut, tut mir leid, ich hätte ihn gleich ganz posten sollen.

private static void ApplyUSAN(int t)
        {
            int widthTemp = width - 3;
            int heightTemp = height - 3;
            int tempP = 0;
            byte tempPixNValue;

            for (int x = 3; x < widthTemp; ++x)
            {
                for (int y = 3; y < heightTemp; ++y)
                {
                    tempP = image[x, y];

                    tempPixNValue = 0;

                    if (Math.Abs(image[x - 3, y - 1] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x - 3, y] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x - 3, y + 1] - tempP) <= t)
                        tempPixNValue += 1;

                    if (Math.Abs(image[x - 2, y - 2] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x - 2, y - 1] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x - 2, y] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x - 2, y + 1] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x - 2, y + 2] - tempP) <= t)
                        tempPixNValue += 1;

                    if (Math.Abs(image[x - 1, y - 3] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x - 1, y - 2] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x - 1, y - 1] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x - 1, y] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x - 1, y + 1] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x - 1, y + 2] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x - 1, y + 3] - tempP) <= t)
                        tempPixNValue += 1;

                    if (Math.Abs(image[x, y - 3] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x, y - 2] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x, y - 1] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x, y] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x, y + 1] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x, y + 2] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x, y + 3] - tempP) <= t)
                        tempPixNValue += 1;

                    if (Math.Abs(image[x + 1, y - 3] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x + 1, y - 2] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x + 1, y - 1] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x + 1, y] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x + 1, y + 1] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x + 1, y + 2] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x + 1, y + 3] - tempP) <= t)
                        tempPixNValue += 1;

                    if (Math.Abs(image[x + 2, y - 2] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x + 2, y - 1] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x + 2, y] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x + 2, y + 1] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x + 2, y + 2] - tempP) <= t)
                        tempPixNValue += 1;

                    if (Math.Abs(image[x + 3, y - 1] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x + 3, y] - tempP) <= t)
                        tempPixNValue += 1;
                    if (Math.Abs(image[x + 3, y + 1] - tempP) <= t)
                        tempPixNValue += 1;

                    USANImage[x, y] = tempPixNValue;
                    }
            }
        }

Dies ist nur der erste Schritt der SUSAN Implementierung, wobei das Problem ist, dass der Algorithmus jetzt bereits langsamer ist, als mein Canny-Algorithmus.

Answer 5

Hallo Simon,

den Algorithmus als solches kenne ich nicht, daher beziehe ich mich rein auf den Code.

image ist was genau? Bitmap? Großes Array? ...? Falls ja, warum liest Du nicht vor der Schleife die relevanten Pixel/Elemente aus image aus und schreibst die bspw. in ein kleineres Array, dass genau so viele Elemente enthält wie nötig (alternativ eine andere Auflistung wie bspw. List( Of <WasAuchImmer> ), wobei hier die Performance wahrscheinlich schlechter sein wird). Danach könntest Du dann einfach komplett durch das Array laufen ohne jeweils immer auf den Index abzustellen. Denn eine gesonderte Prüfung gibt es ja hier nicht, die Bedingung ist immer dieselbe, nur der Wert des Arrayelements ist ggfs. ein anderer.

Dazu könntest Du dir dann auch gleich die x-fache Verwendung von Math.Abs( ... ) sparen, indem Du die Werte gleich richtig umgeschrieben im o.g. Array ablegst und somit nur noch direkte Vergleiche durchführst.

Nur, damit ichs dann auch richtig verstehe (wie gesagt, den Algorithmus kenne ich nicht): Es soll für jeden inneren Schleifendurchlauf _immer_ jedes if( ... ) abgearbeitet werden. Letztendlich (wenn alles wahr wäre, bei jedem if( ... ) also true rauskommen würde) könnte tempPixNValue also 37 sein? Falls nicht, ergäbe sich natürlich erhebliches Verbesserungspotential.

Beachte auch, dass Du ggfs. im Debug Mode testest. In dem Fall ist die Abarbeitung erheblich langsamer als im Release Mode. Stell das ggfs. mal um und teste dann nochmal.

---

Gruß, Stefan
Microsoft MVP - Visual Developer ASP/ASP.NET
http://www.asp-solutions.de/ - Consulting, Development
http://www.aspnetzone.de/ - ASP.NET Zone, die ASP.NET Community

Answer 6

@ Stefan,

Der Algortihmus zählt tatsächlich alle Pixel, die innerhalb eines gewissen Spielraums, dem Mittleren ähnlich sind.

Diese Ähnlichkeit wird mit dem Math.Abs bestimmt, da der Wert immer positiv sein sollte. Gibt es eine Möglichkeit die zu beschleunigen, bzw. irgendwie zu umgehen?

Die Methode die Werte in ein temporäres Array umzuschreiben ist leider langsamer und vorrallem nicht gut möglich, da die Maske (alle abzufragenden Werte für ein Pixel) rund sein soll.

Gibt es eine Möglichkeit die Differenz zwischen zwei Bytes zu bestimmen und zwar ohne Umwandlung in int oder einen anderen Datentyp?

Answer 7

Hallo Simon

Zu Math.Abs kann ich mir nicht vorstellen, dass dies relevante Rechenzeit kostet,
denn dies sollte vom JITer (hoffentlich) auf ein paar wenige, simple Assembler-OPcodes umgesetzt werden können.
  (ich nehme an du misst mit dem Release-Build standalone, nicht etwa im Studio Debugger)

Derart Low-Level Operationen in C# zu optimieren wird wohl schwierig (ohne komplexe Messungen / Profiling).
Ich vermute ein guter Teil der Zeit kosten auch die vielen Array-Zugriffe, welche in C# deutlich mehr kosten als in C++.
Daher könnte man uU per C# 'unsafe' Pointers noch eine Messung machen.
Aber, bei solchen Algorithmen wird man wohl nur mit C++ oder gar native-Assembler wirklich markantes erreichen.
Der Algorithmus taugt potentiell wohl auch für Parallelisierung, bzw evtl sogar für auf einer GPU.

Answer 8

Das mit den Pointer scheint eine Möglichkeit zu sein.

Allerdings verstehe ich persönlich die MSDN Dokumentation zu Pointern nicht so ganz.

Muss das Array ein Pointer Array sein (int*[,]) oder nur die Abfrage?

Vielleicht kann mir das noch jemand näher erläutern.

Ist es, falls das Array ein Pointer Array sein muss, möglich dieses z.B. mit fixen int Werten zu belegen?

Answer 9

Simon

es wird wohl ein Pointer auf das Array (dein 'image') sein.
Lies Dok für C# 'fixed', in deinem Fall wohl auch betreffend multi-dimensional Arrays:

http://msdn.microsoft.com/en-us/library/aa664784.aspx
http://msdn.microsoft.com/en-us/library/f58wzh21.aspx

 // Annahme etwas wie: int[,] image = new int[1000,1000];
 unsafe {
  fixed (int* ptr = image) {

Ob Multi-Dimensional hier zum Performance-Nachteil wird weiss ich nicht, uU wäre da 'flat' besser.