Algorithmus für hellstes Pixel (~echtzeit?!)

R

Requiem

Grünschnabel
Hallo an alle!

Ich hab ein recht komplexes problem, auch wenn die frage an sich wohl einfach ist :/ :
für ein projekt muss ich in einem bild möglichst schnell das hellste pixel finden (wenn es mehrere gibt sollte das erste mit maximalwerten reichen).
Das bild kommt letztendlich von einer usb-webcam und hat zwar farbinformationen, dürfte aber wegen filtern an der kamera nur noch aus schwarz/grau und ein paar hellen flecken bestehen. Das bild hat eine auflösung von mindestens 800x600 und maximal 1600x1200. Da das hellste pixel nach möglichkeit in echtzeit in jedem frame (also 25x in der sekunde) gefunden werden soll, brauche ich dafür jetzt einen möglichst effektiven algorithmus.... ich erwarte/hoffe garnicht auf komplette ausarbeitungen,ich brauche lediglich ansätze wie das am schnellsten ginge, da die methode
Code:
for pixel in frame; do
   if [[ value > $max ]]; then max=pixel(x,y); fi
done
nicht sonderlich effizient ist ;) auf die programmiersprache kommts deshalb auch nicht an, pseudocode reicht vollkommen!
Bin für alle vorschläge dankbar :)

MFG
Requiem
 
Hi,
Jenachdem wie genau du das ganze brauchst kannst du folgendes machen:
Leg ein Raste über das bild.

count x_pixel
cont y_pixel

for pixel in y_pixel do
for pixel in x_pixel do
if [[ value > $max ]]; then
max=pixel(x,y);
x_max=x;
y_max=y;
fi
done
done


und such in der umgebung des hellsten pixels des Rastes
range=10 #belibieger wert.
y__range_pixel = y_max - range to y_max +range;
x__range_pixel = x_max - range to x_max +range:

for pixel in y__range_pixel do
for pixel in x__range_pixel do
if [[ value > $max ]]; then
max=pixel(x,y);
fi
done
done


Du kannst hal unter umständen nicht den hellsten punkt finden, das muss dir bewusst sein, aber einen hellen Punkt findest du auf jeden fall (lokales maximum). Besonders bei einem großen helligkeits gradienten kann das auftreten.
Ich hoffe, dass dir mein vorschlag weiterhilft.
Gruß, Georg
 
wandle das bild von rgb nach hsv um dann hast du die helligkeit jedes pixels im v-wert - umwandeln am besten mit ImageMagick.
Ich habs mal in C implementiert - müßte aber suchen.


alternativ: mit matlab sollts in ebenfalls in echtzeit gehen
 
Zuletzt bearbeitet:
...

Du kannst hal unter umständen nicht den hellsten punkt finden, das muss dir bewusst sein, aber einen hellen Punkt findest du auf jeden fall (lokales maximum). Besonders bei einem großen helligkeits gradienten kann das auftreten.
Ich hoffe, dass dir mein vorschlag weiterhilft.
Gruß, Georg

Wenn man schon vom Ideal ausgeht, lok. Optimum = glob. Optimum, dann gibt es elegantere Methoden als das Abgrasen des gesamten Bereiches, um diese zu ermitteln. Einfach und schnell zu realisieren wären Tangentenmethoden (zum Beispiel von Newton).

Gruss, Xanti
 
Hi!

Erstmal vielen dank für die vielen antworten, mit der emailbenachrichtigung hat leider irgendwie nicht geklappt :/

Das umwandeln in hsv hab ich mir auch schon überlegt, aber ich denke die umwanldung braucht zu lange und die rastermethode halte ich für wenig effektiv, könnte auch unter umständen zu viele ressourcen verbrauchen... Deshalb klingt das mit den tangenten sehr interessant (vor allem da es sich idr wirklich um ein globales maximum handeln sollte). Wo/unter welchen suchbegriffen kann ich denn mehr dazu finden?

Nochmal vielen dank!
Requiem

edit: wenn damit das newton-verfahren gemeint ist hab ich grad null ahnung wie ich das darauf anwenden soll oO
 
Zuletzt bearbeitet:
Mal sehen, ob ich das alles noch aus meinen Erinnerungen zusammenkriege (wenns fehlerhaft ist, nicht meckern) ;)

Da die Funktion (sagen wir f) konvex ist, gilt offensichtlich:

Code:
x ist minimal, falls f'(x) = 0

Du musst also die Nullstelle von f' berechnen, z. B. mit dem Newtonverfahren:

Code:
solange |f'(x_n)| > toleranz 
{
1. Gradient an der Stelle x_n approximieren (damit hast Du die Suchrichtung)
2. Schnittstelle des Gradienten mit der X-Achse berechnen -> x_n+1
}

Da Deine Funktion auf einer (zweidimensionalen) Ebene definiert ist, musst Du zur Aproximation der Ableitung 3 Stützstellen nutzen (x_n + x-Richtung + y-Richtung).

Gruss, Xanti
 
Hi,
das hier dürfte dir weiterhelfen.
http://de.wikipedia.org/wiki/Newton_Iteration

Das Problem bei der ganzen sahe ist , dass du nicht zwingend das globale Maximum erreichst, da die Verteilung der Helligkeit nicht stetig differenzierbar ist.
Wenn es dir darauf ankommt unter allen Umständen denn hellsten Punkt zu erwischen sind diese Verfaheren nicht geeignet.

Gruß, Georg
 
oi :think: Ich...denke ich muss mich da ziemlich reinknien um das anwenden zu können.... :hilfe2: ^^ naja, vlt wirds ja....

nochmal eine frage zum verständnis: prinzipiell ist das ganze dann doch sogar 3dimensional, oder? also x/y für die position und z für steigung/helligkeit?

Zumindest hab ich jetzt was worüber ich mir die nächsten tage den kopf zerbrechen kann ^^

Regards
Requiem
 
...
nochmal eine frage zum verständnis: prinzipiell ist das ganze dann doch sogar 3dimensional, oder? also x/y für die position und z für steigung/helligkeit?

Die Funktion und damit das Problem ist zweidimensional, die Darstellung mit x-y-z dreidimensional.
 
Zuletzt bearbeitet:

Ähnliche Themen

evilWM vs Ratpoison vs Ion

Deutsche Installationsanleitung für Slackware 9.0 (und auch 9.1)

Zurück
Oben