Thresholding recht langsam

Hallo liebes Forum,

ich habe eine Thresholding-Programm geschrieben, welches aber recht langsam ist.
Da ich noch LV Anfänger bin habe ich hier schon mein bestes gegeben, aber wenn der ein oder andere nch eine Idee hat,
wie man dieses Program schneller werden lassen kann, wäre das super.


Zum Programm:

1. Es wird ein Array eingelesen, in Form eines Bildes.
(Daran kann ich leider nichts ändern, dass sind meine Ausgangs vorgaben. Es MUSS mit einem Array gearbeitet werden.)

2. Es wird Threshold bestimmt, nach dem folgendem Algorythmus:

<blockquote>a) An initial threshold (T) is chosen, this can be done randomly or according to any other method desired.
b) The image is segmented into object and background pixels as described above, creating two sets:
<blockquote>G1 = {f(m,n):f(m,n)>T} (object pixels)
G2 = {f(m,n):f(m,n)leT} (background pixels) (note, f(m,n) is the value of the pixel located in the mth column, nth row)</blockquote>
c) The average of each set is computed.
<blockquote> m1 = average value of G1
m2 = average value of G2</blockquote>
d) A new threshold is created that is the average of m1 and m2
T’ = (m1 + m2)/2
e) Go back to step b), now using the new threshold computed in step four, keep repeating until the new threshold matches the one before it (i.e. until convergence has been reached).
(Quelle: Wikipedia)</blockquote>

Diesen Algorythmus würde ich gerne beibehalten, da er für die Bilder, die ich bearbeiten muss am besten funktioniert.

3. Es wird ausgezählt wie viele Werte unter und über dem Threshold liegen.


Das wirklich langsame an dem Programm ist der Thresholding Teil und zu dem hätte ich gerne Hilfe.
Kann man den schlanker Implementieren, sodass das ganze schneller wird?
Jemand Ideen dazu?

Vielen Dank im Vorraus!

Rebecca



  test.vi (Größe: 27,36 KB / Downloads: 214)
in LV 8.6

Anzeige

' schrieb:Das wirklich langsame an dem Programm ist der Thresholding Teil

Ja, das kann ich nachvollziehen.

Nur eins:
AutoIndex-Ausgänge an einer While-Schleife sind bezogen auf das Speichermanagement für Arrays ganz schlecht. Theoretisch wird nämlich bei jedem Schleifendurchlauf neuer Speicher alloziert und kopiert - das dauert, dauer, dauert ...

Alle deine While-Schleifen kann man durch FOR-Schleifen ersetzen: Weil die Abbruchbedingung nicht von einer Berechnung innerhalb der While-Schleife abhängt.

Ich hab die rechte While-Schleife mal ersetzt. Kuck mal, ob das noch passt.



Nachtrag:
Ich hab mal noch eine Änderung angebracht. Eine While-Schleife hab ich durch eine FOR-Schleife ersetzt - dabei hat sich automatisch das eine Array eliminiert. Bevor ich da weiter mache, möchte ich schon wissen, ob das noch geht.

Hallo,

den Anfang der (korrekten) Kritik hat IchSelbst schon gemacht. Alle While-Schleifen können durch For-Schleifen mit aktiviertem Autoindexing ersetzt werden. Das ist in LabVIEW wesentlich effektiver.

Weitere Kritikpunkte: Die Case-Struktur, die den ersten Schleifendurchlauf von den anderen unterscheidet, ist überflüssig, wenn man das Shiftregister entsprechend initialisert.

Dann hast du in der innersten Schleife 2 Case-Strukturen nebeneinander, die aber 2x dieselbe Fallunterscheidung machen. Überflüssig, kann man zusammenfassen.

Laufzeitmäßig tödlich ist natürlich, dass du da per Autoindexing 3D-Arrays erzeugst! Vollkommen überflüssig. Du musst nur geschickt addieren. Eine ganze Reihe von Operationen kannst du dir sparen.

Dein VI lässt sich eindampfen auf das hier:
   

  test3.vi (Größe: 12,26 KB / Downloads: 192)


Gruß, Jens

P.S.: Jetzt fordere ich aber, dass das LVF auch als Quelle zitiert wird.



EDIT: Wenn du schon verhinderst, dass 3D-Arrays erstellt werden, bringt das schon einen riesigen Geschwindigkeitsgewinn:
   

Ich hab mal ein Beispiel gemacht, um Zeiten zu messen. Es geht um den Algorithmus "counting spots > focal size". Einmal mit doppelter FOR-Schleife wegen des 2DArr. Einmal mit den polymorphen Elementen "größer gleich", "Bool to U8", "U8 to I32", "Summe I32", und einmal in C.

Fazit:
Die manuelle Programmierung mit den 2 For-Schleifen ist schneller als die polymorphe, die ja eigentlich die LV-spezifische Programmierung ist. (Von der C-Lösung reden wir lieber nicht. Die ist zwar schnell getippt ...). Es ist aber zu beachten, dass die Verzweigung des 2DArr unbedingt vor der Sequenz geschehen muss. Alleine die Verzweigung kostet viel Zeit (Speicher allozieren und kopieren).

Die polymorphe Lösung hat den gewichtigen Nachteil, dass Arrays alloziert werden müssen - ganz schlecht, wie wir wissen.

Was auf jeden Fall beachtet werden muss: Warum muss der Vergleichswert DBL sein, wenn es U8 auch tut? Ebenso die Wandlung nach I64.

Hallo!

@IchSelbst: "Was auf jeden Fall beachtet werden muss: Warum muss der Vergleichswert DBL sein, wenn es U8 auch tut? Ebenso die Wandlung nach I64. "

Die Wandlung nach I64 erfolgt um den Zahlenbereich zu vergrößern, da der durch U8/I8 vorgegebene Zahlenbereich zu klein ist um die hier entstehenden Summen zu händeln.
Mit U8 hatte ich ursprünglich angefangen, und bekam dann sehr kuriose Werte raus, die mich überhaupt auf diese Umwandlung brachten.
Für den Vergleichswert sollte es I64 oder I32 auch tun, sodass man hier nicht zusäztlich wandeln muss.
Bei meiner Version hat LV da rumgesponnen, als ich das mit I64 ausprobiert habe; KA warum.


@ Jens G
Nachdem ich dein Programm jetzt ausführlich auseinandergepuhlt habe und begeistert festgestellt habe: Es Funktioniert!
Ein Dickes Kompliment: Sehr schön, sehr elegant gelöst!
Ich hätte das so nicht gekonnt und wäre vorallem auf diese hübschen Summationen gar nicht erst gekommen.

Vielen, vielen lieben Dank!

Ich werd' das LVF auch brav als Quelle in das Programm hinenschreiben. ;-)

Beste Grüße, Rebecca

Das 2D-Array läßt sich auf 1D umformen. Man braucht dann keine verschachtelten For-Schleifen mehr. Das bringt für die Geschwindigkeit wahrscheinlich nicht viel, aber mir gefällt es so einfach besser .
Es ist aber absolut tödlich für die Geschwindigkeit, wenn bei geschätzten 10^7 Bildpunkten in der innersten Schleife 10^7 mal von Integer nach DBL konvertiert wird! Die Integerwerte sind vermutlich groß genug, daß ein Rundung auf ganze Zahlen keinen Fehler verursacht. Habs mal gemacht.
Zwei Realzahlen auf Gleichheit zu testen, wie in diesm VI, funktioniert sowieso in der Regel nicht. Deshalb wundert es mich sehr, daß das Programm so wie es war überhaupt jemals beendet wird.
Habe mal alles auf Integer-Berechnung umgestellt, ich hoffe, es ist jetzt noch um einige Zehnerpotenzen schneller
(Testen kann ich es nicht, daß ich das ADDON nicht habe)

   

  test3WA.vi (Größe: 17,77 KB / Downloads: 182)


Edit: Ich hatte mich auf das VI von Jens in #3 bezogen. Jetzt sehe ich, daß IchSelbst bereits die Realzahlen aus der Welt geschafft hat und so diese Konvertierungen auch vermeidet. Habe das VI (nicht die Graphik) geändert und den Simulator von IchSelbst angeschlossen. Zeitverbrauch des VIs mit dem Simulator 5000*5000 Pixel: 1.7 sec