Hallo zusammen,
ich hab ein kleines Problem mit einer Anwendung in OpenCV bei der ich
ein Grauwertbild Pixel für Pixel bearbeiten will.
Die Pixel sollen anhand der Kriterien Position und Wert unterschieden
werden und entsprechend zu weiß(255) oder schwarz(0) geändert werden.
Das ganze habe ich in Python umgesetzt.
Hierfür habe ich eine for-Schleife verwendet:
Beispiel:
for x in range(100):
for y in range(100):
if(bedingung):
image[x,y]= 0 oder 255
Der Code funktioniert, aber braucht sehr viel Zeit.
Die Ausführung dauert einige Sekunden, selbst bei kleineren Bildern.
Gibt es eine Möglichkeit die einzelnen Pixel auf eine schnellere Weise
abzufragen und zu ändern?
Deine Schleife stellt offensichtlich den trivialen Algorithmus für dein
Problem dar. Je nach konkreten Problem kann es effizientere Algorithmen
geben.
Das ist keine Frage der Programmiersprache.
Experte schrieb:> Und was ist 'Bedingung' genau?
Da wird überprüft ob der Pixelwert größer als eine Schwelle ist und ob
er links oder rechts im Bild ist.
EdB schrieb:> Experte schrieb:>> Und was ist 'Bedingung' genau?>> Da wird überprüft ob der Pixelwert größer als eine Schwelle ist und ob> er links oder rechts im Bild ist.
Wenn grundsätzlich alle Pixel einzeln angeschaut werden müssen, führt
kein Weg an deinem Algo vorbei, die untere Schranke wäre dann bei O(n),
und das macht deine Schleife bereits. (vgl. Sortierung, da muss
mindestens jedes Element einmal betrachtet werden, darum kann es keinen
Algo besser O(n) theoretisch geben).
EdB schrieb:> for x in range(100):> for y in range(100):
Dein Example sehr minimalistisch, aber "for x in range" ist in Python
eigentlich immer falsch (okay es gibt ein paar exotische Ausnahmen),
Leider kenne ich den Type von Image nicht aber nach ich bin mir ziemlich
sicher das man über Image Iterieren kann. Alleine das Kann schon etwas
Geschwindigkeit bringen.
Die Bedingung kann natürlcih komplizierter sein. Wenn es nur das < ist
gibt es dafür explizite openCV Funktionen.
Das schaut zwar immer noch jeden Pixel an (muss es ja), macht das aber
optimiert.
Imonbln schrieb:> "for x in range" ist in Python> eigentlich immer falsch
Warum das? range(100) erzeugt halt im Speicher eine Liste mit 100
Einträgen. Müsste nicht sein, lieber xrange(), juckt bei heutigen
Maschinen aber auch keinen und im Vergleich zum Speicherplatzbedarfs des
Bildes ist das eh Kleinkram.
dodadi schrieb:> Warum das? range(100) erzeugt halt im Speicher eine Liste mit 100> Einträgen. Müsste nicht sein, lieber xrange(), juckt bei heutigen> Maschinen aber auch keinen und im Vergleich zum Speicherplatzbedarfs des> Bildes ist das eh Kleinkram.
xrange ist Python2 und seit Anfang des Jahres damit eigentlich im EOL.
Was das Iterieren angeht, der Hauptgrund warum es eigentlich immer
Falsch ist eine "for x in range" zu schrieben, ist der das man
eigentlich jedes Objekt (wo es sinnvol ist) seinen eigenen Iterator
mitbringt. meisten Will man ja das nächste Objekt haben und nicht seinen
Index kennen, was Python intern nutzen kann zum den Zugriff auf die
nächste instance zu Optimieren.
Ausserdem geben seit Python3 viele Funktionen lieber ihren Iterator
zurück als Speicher für alle Elemente zu verbrauchen z.b map.
Zeig bitte mal etwas mehr Code.
- Du kannst aus Python auch C Code aufrufen, falls in dieser Anwendung
akzeptabel. Das läuft oft deutlich schneller. Wenn du willst, kannst du
auch auf ASM Ebene dann optimieren.
Für den C-Fall noch ein paar Tipps:
- Wo kommt die Bedingung her? Wird die on-the-fly berechnet? Ggf liegt
hier auch ein Problem.
- Welche Datentypen verwendest du? Eventuell lassen sich mehrere Werte
in einem Schritt abarbeiten (8-bit Pixel in 32-bit Registern)
- Loop unrolling mal probiert? Macht ggf hässlichen Code, kann aber
schneller werden. Sprünge kosten üblicherweise viel Performance.
Für Python wurden schon genügend Optionen genannt
M. K. schrieb:> Cyblord -. schrieb:>> Das ist keine Frage der Programmiersprache.>> https://devopsworld.de/1133>> Ist es nicht?
Nein weil die absolute Laufzeit für die Betrachtung eines Algorithmus
keine Rolle spielt. Ist dir die Zeit zu lange, dann kannst du immer noch
auf einem Supercomputer oder Cluster ausführen.
Ein sehr schlechter Algo bleibt sehr schlecht, auch wenn er ein wenig
schneller in C als in Python ausgeführt ist. Erst wenn der Algo
nachweislich optimal ist, kann man sich über solche Dinge wie Maschine,
CPU oder Programmiersprache Gedanken machen.
Dirk K. schrieb:> Es kann einen Unterschied machen, wie man iteriert:for x in range(100):> for y in range(100):> vs.for y in range(100):> for x in range(100):> Ausprobieren!>> merciless
Danke, aber das habe ich bereits getestet.
Johannes O. schrieb:> - Wo kommt die Bedingung her? Wird die on-the-fly berechnet? Ggf liegt> hier auch ein Problem
Die if-Anfrage wird in der Schleife ausgewertet. Bsp. if img[x,y]>100:
img[x,y]=255
Johannes O. schrieb:> - Welche Datentypen verwendest du? Eventuell lassen sich mehrere Werte> in einem Schritt abarbeiten (8-bit Pixel in 32-bit Registern)
uint8
Dirk K. schrieb:> In python benutzt openCV numpy als image container.
Das habe ich auch bereits gefunden.
Laut anderen Beiträgen soll man mit numpy den größten Zeitgewinn
erzielen.
Allerdings verstehe ich nicht so recht wie man damit arbeitet.
Cyblord -. schrieb:> Ein sehr schlechter Algo bleibt sehr schlecht
Ja, da hast Du recht.
Aber ein sehr schlechter Algo läuft auf unterscheidlichen
Programierspachen immer noch unterschiedlich schnell.
Ein sehr schlechter Algo in einer sehr schnellen Sprache geschrieben ist
u.U. schneller als ein sehr guter Algo in Python.
Also verstehe ich Deinen Ansatz nicht, das die Sprache keine Rolle
spielt.
Aber lassen wir das nicht zum Schlagabtausch werden.
Die laufen nicht so gut zwischen uns.
Also, hast Du recht und ich Unrecht und dabei belassen wir das.
Das hält mein Ego aus ;-)
100x100 müsste selbst in Python fluppen. Da stimmt was nicht mit dem
Zugriff auf ,,image", wird wohl jedesmal neu geladen oder so. Wäre wohl
besser ein richtiges array/liste im Pythonstil zu haben, evtl. gibt da
eine Funktion die ein solches zurückliefert, welches man dann
zwischenspeichert in einer Variable....
> Der Code funktioniert, aber braucht sehr viel Zeit.> Die Ausführung dauert einige Sekunden, selbst bei kleineren Bildern.
Wie klein?
Ersetze mal image durch ein erstelltes array gleicher Größe und
vergleiche.
Und poste den code der sich hinter deiner Bedingungsfunktion verbirgt
M. K. schrieb:> Also, hast Du recht und ich Unrecht und dabei belassen wir das.> Das hält mein Ego aus ;-)
Putzig. Schlagabtausch? Das wäre so als würde ich nem Hund einen Knochen
hinwerfen und er mag ihn nicht. So ein Schlagabtausch wäre das. Und was
das mit seinem Ego macht und ich dabei Recht habe, interessiert mich
ungefähr ähnlich.
Hier der gesamte Code:
import cv2
import numpy as np
import matplotlib.pyplot as plt
img = cv2.imread('/home/pi/Desktop/Bilder2/Bild1.png',0)
for x in range(img.shape[0]):
for y in range(img.shape[1]):
if(img[x,y]>180 or y>450):
img[x,y]=255
cv2.imshow('Image',img)
cv2.waitKey(0)
cv2.destroyAllWindows()
Damit dein code schneller ( viel schneller) wird, führt kein Weg an der
Benutzung der OpenCV Routinen bzw numpy vorbei. Bedeutet für Dich: Du
musst Dich in beides einarbeiten, was nicht so schwer ist und Dir auch
bei anderen Aufgabenstellungen helfen wird.
Der Code ist langsam, weil alles durch den python Interpreter läuft. Mit
OpenCV/numpy würde das in optimierten (C-)Routinen ausgeführt. Ein
Full-HD Bild sollte mit Deiner Schwellenwertoperation auf einem
aktuellen Rechner deutlich unter 100ms berechnet werden.
Asdf schrieb:> Damit dein code schneller ( viel schneller) wird, führt kein Weg an der> Benutzung der OpenCV Routinen bzw numpy vorbei. Bedeutet für Dich: Du> musst Dich in beides einarbeiten, was nicht so schwer ist und Dir auch> bei anderen Aufgabenstellungen helfen wird.
Ok, ich habe schon eine Weile in der Richtung recherchiert aber noch
nichts funktionierendes hinbekommen.
Weiß jemand wie man numpy für meine Aufgabe anwenden würde?
Mike B. schrieb:> je nach Prozessor geht auch erstmal multithreading mittels OpenMP
WENN dein Algorithmus parallelisierbar ist. Und selbst dann ist das
immer aufwändiger als einfach die große Maschine rauszuholen, wenn das
möglich ist.
Aber an 1. Stelle steht der Algorithmus selbst. Der ist das wichtigste.
Alles andere ist nachgeordnet. Ich bin dagegen auf einen schlechten Algo
mit dem Hammer Rechenleistung einzuschlagen.
Cyblord -. schrieb:> und ich dabei Recht habe
Und das ist es ja, worum es geht, nicht wahr?
Ich würde ja auf Quarantänekoller bei Dir tippen, aber Du bist ja immer
so.
Naja, Du must ja mit Dir leben.
Asdf schrieb:> Der Code ist langsam, weil alles durch den python Interpreter läuft. Mit> OpenCV/numpy würde das in optimierten (C-)Routinen ausgeführt.
Nein das kann nicht stimmen.
Denn Cyblord sagt das das völlig unabhängig von der Sprache ist, und
Cyblord hat immer recht, sonst bekommt er Stresspickel, wirft sich auf
den Boden und brüllt bis er einen Lutscher bekommt.
:-)))
EdB schrieb:> for x in range(img.shape[0]):> for y in range(img.shape[1]):> if(img[x,y]>180 or y>450):> img[x,y]=255
Das Ganze in zwei Konstrukte auflösen (je halbe Y-Auflösung). Einmal
alle Y-Positionen größer 450 den Wert 255 zuweisen (Vorteil: kein if )
und einmal alle andere mit der Abfrage größer 180 bearbeiten (Vorteil:
nur eine Abfrage).
Imonbln schrieb:> ungefähr so> import cv2>> img = cv2.imread('/home/pi/Desktop/Bilder2/Bild1.png',0)>> img[ img > 180] = 255 # dein img[x,y] > 180 in numpy parallel> img[ 0:img.shape[0], 450:] = 255 # dein y > 450 in numpy>> img[ img <= 180] = 0 # bin nicht sicher ob du das einfach vergessen hast>> cv2.imshow('Image',img)> cv2.waitKey(0)> cv2.destroyAllWindows()
Danke erstmal für den Tipp.
Das versuch ich mal.
Cyblord -. schrieb:> Mike B. schrieb:>> je nach Prozessor geht auch erstmal multithreading mittels OpenMP>> WENN dein Algorithmus parallelisierbar ist. Und selbst dann ist das> immer aufwändiger als einfach die große Maschine rauszuholen, wenn das> möglich ist.>> Aber an 1. Stelle steht der Algorithmus selbst. Der ist das wichtigste.> Alles andere ist nachgeordnet. Ich bin dagegen auf einen schlechten Algo> mit dem Hammer Rechenleistung einzuschlagen.
Sorry aber hier gehts grad um einen Algo der 100x100 Bildpunkte
nacheinander aber unabhängig voneinander abcheckt.
Leichter parallelisierbar gehts doch kaum noch.
bei 8 nutzbaren cores teilt der scheduler die Arbeit in 8 Teile, fertig.
Und dass der angegebene Algo für die Aufgabe kaum besser geht wurde
schon gesagt.
Hängt halt nur von der Hardware ab.
Einen singlecore mit Hyperthreading würde auch nicht extra mit
multithreading belasten, aber ab 3 nutzbaren cores geht da schon was.
Imonbln schrieb:> img[ img > 180] = 255 # dein img[x,y] > 180 in numpy parallel> img[ 0:img.shape[0], 450:] = 255 # dein y > 450 in numpy
Der Code klappt super und ist schnell...
Nur eine Frage:
Ist es möglich beide Bedingungen in einem abzufragen?
z.B.:
Alle Pixel die in der linken Bildhälfte sind und über 180 sind werden zu
255.
EdB schrieb:> Ist es möglich beide Bedingungen in einem abzufragen?
Ich bin kein numpy Experte, keine Ahnung ob das geht. Da musst du ins
Handbuch gucken.
Cyblord -. schrieb:> Mike B. schrieb:>> je nach Prozessor geht auch erstmal multithreading mittels OpenMP>> WENN dein Algorithmus parallelisierbar ist. Und selbst dann ist das> immer aufwändiger als einfach die große Maschine rauszuholen, wenn das> möglich ist.>> Aber an 1. Stelle steht der Algorithmus selbst. Der ist das wichtigste.> Alles andere ist nachgeordnet. Ich bin dagegen auf einen schlechten Algo> mit dem Hammer Rechenleistung einzuschlagen.
Irgendwie widersprechen sich diese beiden Aussagen. Oben schreibst du,
man soll doch einfach einen dickeren Rechner nehmen, unten bist du
dagegen, das zu tun.
Rolf M. schrieb:> Irgendwie widersprechen sich diese beiden Aussagen. Oben schreibst du,> man soll doch einfach einen dickeren Rechner nehmen, unten bist du> dagegen, das zu tun.
Könnte man meinen. Geb ich zu. ;-)
Das mit dem dickeren Rechner war auf Geschwindigkeitsprobleme wegen der
Programmiersprache bezogen und darauf dass mehr Rechenleistung bis zu
einem gewissen Punkt einfacher zu bekommen ist als Parallelisierung.
Bezüglich eines schlechten Algo macht aber mehr Rechenleistung nur
begrenzt sinn, da hier es hier sehr schnell um extreme Größenänderungen
gehen kann.
z.B. bei einer Datenbankabfrage mit JOIN kann die Auswahl des
Optimierers bezüglich der inneren und äußeren Tabelle einen Unterschied
von 1ms bis 1 Million Jahre ausmachen.
EdB schrieb:> Ist es möglich beide Bedingungen in einem abzufragen?
Genau wie in deinem Beispiel ist es normalerweise falsch.
Wenn du OR in einer Abfrage hast, werden fast immer beide
Bedingungen geprüft (Extremfall - alle Adressen über 450 haben
Wert kleiner 180).
Wie schon jemand geschrieben hat - Adressen über 450 auf 255 setzen,
nur auf Wert über 180 abfragen.
EdB schrieb:> Der Code funktioniert, aber braucht sehr viel Zeit.
Auf welcher Hardware läuft denn Dein Code?
C64? Arduino?
> Die Ausführung dauert einige Sekunden, selbst bei kleineren Bildern.
Sogar auf 'nem RasPi hab ich auf 1000x1000 Pixel erhöhen müssen, damit
ich eine Laufzeit von 4-5 Sekunden erreicht hab. Was mach ich bloß
falsch.
