Kreis und Linie mit zufälliger Anordung in einer Bitmap finden // diverse Filter

gramboler

ChaosAngel schrieb:

PS: Wenn irgendwas schon durchgelaufen ist zeig mal die Ergebnisse, wäre cool !

-> ist versprochen!!!!

Bis es soweit ist, werde ich euch aber noch ein paar mal fragen müssen

das 1. Ergebnis kann ich schon liefern:

http://img85.imageshack.us/my.php?image=schwarzweiss5dc.jpg

ich habe die Graustufenkonvertierung nach dem NTSC-Standard benutzt:
Luminanz = 0.176·P.rot + 0.81·P.grün + 0.011·P.blau

Ich bin mit der Kamera näher and das Teil herangefahren. Außerdem istist das gezeigte Bild eine eine JPEG Datei und keine Bitmap. Ich bearbeite aber die Bitmap. da ist die Qualität noch viel besser.

Jester

Bashar schrieb:

Die Hough-Transformation für Kreise hat den Nachteil, dass sie nur Kreise mit einem bestimmten Radius findet. Wenn du nur knapp daneben liegst, bilden sich die Peaks nicht mehr besonders deutlich heraus; bei größerer Abweichung klappts gar nicht.

Ja, aber er sagte, der Radius sei bekannt. Außerdem kann man die Trafo natürlich auch mit variablem Radius durchführen. Ist halt etwas mehr Rechenaufwand. Aber um den Kreis zu finden würde ich eher ein matched-Filter verwenden.

gramboler

ok, ....entweder ich finde keinen passenden Median Filter oder ich bin zu blöd ihn zu verstehen.

Ich zeige euch einmal was ich gemacht habe um mein Graustufenbild zu erzeugen. Vielleicht habe ich auch da schon etwas falsch verstanden, aber es funktioniert:

//---- Schwarz- / Weisbild daraus machen ------------------------------------

				for (int i=0; i< 240/*bmih.biHeight*/; i++)
				{
					for (int j=0; j< 320/*bmih.biWidth*/; j++)
					{
						luminanz = picture[j][i].rgbBlue * 0.299 + picture[j][i].rgbRed  * 0.587 + picture[j][i].rgbGreen * 0.114;

						picture[j][i].rgbBlue     = luminanz;
						picture[j][i].rgbRed      = luminanz;
						picture[j][i].rgbGreen    = luminanz;
						picture[j][i].rgbReserved = 0;	
					}
				}

dies erzeugt mir ein wunderbares s/w-Bild. Vielleicht sollte ich noch erklären, dass in picture [j][i].rgbBlue/Red/Green die jeweiligen Farbwerte für jedes einzelne Pixel stehen. Da ich nun ein Graustufenbild habe sind nun alle drei Werte gleich.

Wer verrät mir nun, wie ich dazu einen Median Filter schreibe?
Oder was sollte ich anders machen?
Ich weiss gerade wirklich nicht weiter.

ChaosAngel

Hab leider grad garkeine Zeit, muss zur Uni, mach mal nur kurz Copy und Paste ausm \1:

Ersetzt den Wert eines Pixel mit dem Median der Werte der Pixel in
der n×n-Nachbarschaft.
-----

Shit Formel lässt sich net kopieren ....
Hier mal die Ränge auf dem Bild was hier steht für 3x3
3 8 5
2 4 9
1 7 6

So, muss nu los, vielleicht hilft wiki ...
Bye

Edit:
Sorry, hab grad Gülle geschrieben !
Du nimmst imho einfach alle Pixel in deiner n x n Umgebung sortierst die Werte der Grösse nach und nimmst das mittlere Element. Lässt sich natürlich optimieren.

Desweiteren solltest du für das Filtern vielleicht mit nem 8bit Bild rechnen und net mit 3 mal den selben Wert berechnen für das 24bit Bild.

gramboler

ok,.........wie ich sehe bist du in der Uni angekommen. Bin übrigends schon seit 7.15 in meiner FH. Wie der Opa schon gesagt hat:

Zitat meines Großvaters schrieb:

"Du musst den Feierabend in der Früh suchen,...mein Sohn"

Aber nun zurück zu meinem Problem:

ChaosAngel schrieb:

Desweiteren solltest du für das Filtern vielleicht mit nem 8bit Bild rechnen und net mit 3 mal den selben Wert berechnen für das 24bit Bild.

Ich weiss nicht ob dass geht, wenn ich am Ende meines Progarmes wieder eine Bitmap haben muss. Oder gibt es eine 8 bit Bitmap?

ChaosAngel schrieb:

Du nimmst imho einfach alle Pixel in deiner n x n Umgebung sortierst die Werte der Grösse nach und nimmst das mittlere Element. Lässt sich natürlich optimieren.

Ich nehme an, dass ich diese Matrix um mein Pixel legen muss. Mein Pixel ersetze ich dann durch mein durch das mittlere Element.

gramboler

Jetzt habe ich ein komplett weises Bild. Meiner Meinung habe ich aber genau das gemacht (einmal abgesehen von dem 8 bit Bitmap) was ChaosAngel geschrieben hat.

ich habe mir eine Matrize, 3x3, um das aktuell zu bearbeitende Pixel gelegt und diese dann mit einem Bubblesort sortiert. Den mittleren Wert habe ich dann in das Pixel geschrieben.

for (int y=0; y< 240/*bmih.biHeight*/; y++)
				{
					for (int x=0; x< 320/*bmih.biWidth*/; x++)
					{
						filterfeldX[x][y] =   picture[x][y].rgbRed;  // hier habe ich nur Rot genommen, da blau und grün = rot sind
					}
				}

				for (int y=0; y< 240/*bmih.biHeight*/; y++)
				{
					for (int x=0; x< 320/*bmih.biWidth*/; x++)
					{
						f = 0;
						for (int my=y-1; my<y+1; my++)
						{
							for (int mx=x-1; mx<x+1; mx++)
							{
															feld[f]= filterfeldX[mx][my];
								f++;
							}
						}					

						int temp;
						for (int i=0; i<8; i++)
						{
							for (int j=0; j < 8-i; j++)
							{
								if ( feld[j] > feld[j+1])
								{
									temp = feld[j];
									feld[j] = feld[j+1];
									feld[j+1] = temp;
								}
							}
						}
						mittelWert = feld[5];

						picture[x][y].rgbBlue  = mittelWert; 
						picture[x][y].rgbRed   = mittelWert;
						picture[x][y].rgbGreen = mittelWert;
					}
				}

das Resultat ist ein komplett weises Bild.

Ich hoffe mit dem mittleren Wert wurde nicht der durchschnitt aller Pixel gemeint.

Interessatnt ist, dass wenn ich schreibe mittelWert = feld[0]; dann bekomme ich ein Graustufenbild. Habe ich so einen Min- Filter geschrieben?
Ab dem feld[4] ist das Bild dann komplett weis.
Der Bubbelsort müsste aber richtig funktionieren.

Mortal2006

1. Ich glaube du greifst auf bereiche zu die nicht zum Bild gehören...
weil du wenn du z.B. in der ersten Spalte bist auf das -1 element zugreifst ... du solltest also schreiben:

for (int y=1; y< 240-1/*bmih.biHeight*/; y++)
                {
                    for (int x=1; x< 320-1/*bmih.biWidth*/; x++)
                    {

Das -i macht doch irgendwie alles kaputt ? Wenn das stärkste element ganz vorne ist, sollte es so doch nie bis ganz nach hinten kommen ?

for (int i=0; i<8; i++)
                        {
                            for (int j=0; j < 8-i; j++)

Naja ich weiß nicht genau was ein min oder max filter macht, aber könnte es nicht besser sein das ganze in eine "neue" bitmap zu schreiben?

Kann mich bei den Sachen auch irren .. bin nicht so der pro

Maxi

du musst das auf jeden fall in eine neue bitmap schreiben...

stell dir vor:

du machst in der linken oberen 'Ecke mal so ein medianfilter drauf, dann hat die linke obere Ecke ja die Farbe des Medians der n*n Pixel drum herum (bzw. nur n/2 weil es ja die ecke ist). Wenn du jetzt einen Pixel weiter nach rechts gehst und wieder median machst, dann wird ja schon die neue Farbe der linken oberen Ecke verwendet und der median des ixels daneben stimmt gar nicht mehr. Deshalb: aus der einen bm lesen, und in die neue bm schreiben, zum schluss die alte durch die neue erstezten oder auch behalten, wie dus brauchst

ChaosAngel

Also, ich denke
1. Das du in eine neue Bitmap schreiben musst.
2. Ich meine mit BitMap (auch mein 8Bit PerPixel bezog sich darauf) nicht ein *.bmp Bild sondern einfach ein 2D Array. In deinem Beispiel heisst es glaube ich filterFeld, das ist genau das was ich meinte !
Am ende aller FilterOperationen schreibst du halt alles wieder in dein 24bit BMP zurück indem alle Farben halt den gleichen Wert haben.

So, zum Filtern legst du dir erstmal 2 filterFelder an.
In einem stehen deine Input Daten und im zweiten sollen deine OutPut Daten dann stehen.
Dein Feld sieht schon ganz ok aus. Ich nehme an, hoffe das du C++ schreibst.
Dann nimm gefälligst einen std::vector statt dem "Feld", und benutze die sort Methode, n eigenes Bubblesort möcht ich hier bitte nicht sehen, dafür gibt es std libs.
So, dann füllst du dein Feld wie bisher mit den 9 Werten und sortierst es. Der Median soll tatsächlich NICHT das arithmetische Mittel sein sondern wirklich der Pixel in der Mitte. Hast du also richtig erkannt.
Diesen Wert schreibst du nun aber nicht sofort zurück ins OriginalBild, sondern in dein 2tes filterFeld.

Wenn du damit fertig bist kannst du von mir aus aus dem OutPut FilterFeld wieder deine bmp machen.

Soweit ich das richtig erkannt habe hast du das alles auch so gemacht !(ohne Umweg über 2tes filterFeld, aber bei mehreren FIlterOperationen ist es vielleicht besser so ...)
Das einzige Woran es also liegen kann wäre dein Bubblesort. Also entweder nimmst du dir schnell ne std methode dafür oder du musst das Ding debuggen und richtig machen. Wird letztendlich aber ungünstig sein da Bubble ja auch noch verdammt langsam ist.

PPS: Du greifst in deiner Schleife wo du dein Feld füllst über die Array Grenzen hinaus. Hier musst du also manuell abfangen das y mindestens 1 und höchstens 239 oder so.. ist.
Es gibt mehrere Methoden Randpixel zu behandeln. Am besten wird hier sein einfach den Rand zu nehmen, also wenn y=-1 ist dann die Stelle 0 zu nehmen...

Na denn man Tau ...

PPPPS:

mittelWert = feld[0]; dann bekomme ich ein Graustufenbild. Habe ich so einen Min- Filter geschrieben?

Wenn ich mich net völlig irre ergibt feld[0] den min Filter und feld[8] den max Filter... Das Graustufenbild hast du aber schon vorher !!!
Du sagtest das alle Werte (rot, grün, blau) gleich seien in deinem Bitmap (du hast also schon ein Graustufenbild erzeugt).

Der Min/Max/Median Filter dient nur zur Noise Reduktions, also das hässliche kleine schwarze und Weisse Punkte auf dem Bild verschwinden die da auch garnicht hingehören (so kannst du halt einfach ein bisschen die Auflösung der Kamera kompensieren)

gramboler

Mortal2006 schrieb:

Das -i macht doch irgendwie alles kaputt ? Wenn das stärkste element ganz vorne ist, sollte es so doch nie bis ganz nach hinten kommen ?
for (int i=0; i<8; i++)
                        {
                            for (int j=0; j < 8-i; j++)

-> nein das ist der Bubbelsort, und der funktioniert auch.

ich habe meinen Code ändern müssen, damit ich kein weises Bild mehr bekomme.

Die Lösung war ganz einfach. Ich habe mir nicht alle Pixel der Median Matrix angeschaut, sonder nur ein Teil. Somit hat auch mein Bubbelsort nicht funktioniert.

...
for (int my=y-1; my<y+2; my++)  //hier steht nicht mehr y+1 bzw. x+1. 
{
 for (int mx=x-1; mx<x+2; mx++)
 {
    ...

mit dieser kleinen Änderung geht es.

@ChaosAngel
Ich habe nicht gewusst, dass es eine Methode zum sortieren gibt, mir war nur der qsort bekannt.
Da ich den Bubbelsort schneller geschrieben habe, als mich durch zahlreiche Internetseiten und die MSDN Library durchzuarbeiten, nur um so etwas zu finden, habe ich es so gemacht. Ich werde mir aber auf jedenfall die std::vector anschauen.

So dann bin ich jetzt einmal gespannt, was für Probleme der Sobel Filter noch mit sich bringt

DANKE an alle die mir bis dahin geholfen haben!!!! Das war wirklich SPITZE, ohne euch hätte ich es vielleicht oder nicht in der Zeit nicht geschafft.

ChaosAngel

Bilder !!!
@Sobel
Input -> VertFilter -> Output
Output -> HorizFilter -> FinalOut

Als Input natürlich das Bild nehmen was du durch die anderen Filter bereits erhalten hast.

@std::sort
Ja, genau wegen diesem Fehler in deinem sort lgo sollte halt der Erste Blick immer erst in die Bibliotheken sein. Man spart SEHR viel Zeit damit die stl zu benutzen anstatt nen sort algo, ne verkettete Liste, nen dynamisches Array, ne Map, nen Stack etc... zu implementieren. Ausserdem weiss man das diese algo's und strukturen Fehlerfrei sind(naja, meißtens jedenfalls, einige MS implementierungen der STL sind echt buggy, aber das sollte bei deinem Gebrauch nicht auffallen und tut hier auch nichts zur Sache).

gramboler

Also der Sobel Filter hat mich nicht wirklich überzeugt.

hier ist das Ergebnis:

http://img164.imageshack.us/my.php?image=mitsobel9yg.jpg

Ich habe den Median Filter hinter den Sobel geschrieben. Das hat noch zu den besten Ergebnissen geführt.

Wen es interessiert wie es geht:

for (int y=0; y<240/*bmih.biHeight*/; y++)
				{
					for (int x=0; x<320/*bmih.biWidth*/; x++)
					{	
						input[x][y] = output[x][y];
					}
				}

				for (int y=0; y<240/*bmih.biHeight*/; y++)
				{
					for (int x=0; x<320/*bmih.biWidth*/; x++)
					{
						output[x][y] = abs(   (-1 * input[x-1][y+1]) + (1 * input[x+1][y+1])
										    + (-2 * input[x-1][y]  ) + (2 * input[x+1][y]  )
											+ (-1 * input[x-1][y-1]) + (1 * input[x+1][y-1]));
					}
				}

				// Kanten in Y-Richtung
				for (int y=0; y< 240/*bmih.biHeight*/; y++)
				{
					for (int x=0; x< 320/*bmih.biWidth*/; x++)
					{	
						input[x][y] = output[x][y];
					}
				}

				for (int y=0; y< 240/*bmih.biHeight*/; y++)
				{
					for (int x=0; x< 320/*bmih.biWidth*/; x++)
					{
						output[x][y] = abs(  (-1 * input[x-1][y+1]) + (1 * input[x-1][y-1])
											+(-2 * input[x]  [y+1]) + (2 * input[x]  [y-1])
											+(-1 * input[x+1][y+1]) + (1 * input[x+1][y-1]));
					}
				}

Jester

Ehm, das was Du da gemacht hast ist kein wirklicher Sobel. Also die einzelnen Teile schon, aber du sollst nicht beide zusammen auf das Bild anwenden.

Erst Sobel-X, dann wieder auf das Originalbild(!) den Sobel-Y. Das gesambild erhältst Du nun, indem Du an jeder Stelle sqrt(Sobel-X^2 + Sobel-Y^2) hinschreibst.

gramboler

Ob ich das Ergebnis für meine Anwendung gebrauchen kann muss ich noch herausfinden. Aber hier ist das Resultat des nun hoffentlich richtigen Sobel Filters.

http://img161.imageshack.us/my.php?image=mitsobel1lb.jpg

die Linien um das Teil herum sind meine Finger.

und hier das vielleicht interessantere,.... der Code:

//---- Sobel Filter ---------------------------------------------------------

				//      -1   0   1                       -1  -2  -1
				//      -2   0   2   x Filtermatrix       0   0   0   y Filtermatrix
				//	    -1   0   1                        1   2   1

				for (int y=0; y<240/*bmih.biHeight*/; y++)
				{
					for (int x=0; x<320/*bmih.biWidth*/; x++)
					{	
						sobelX[x][y] = output[x][y];
						sobelY[x][y] = output[x][y];
					}
				}

				// Kanten in X-Richtung
				for (int y=0; y<240/*bmih.biHeight*/; y++)
				{
					for (int x=0; x<320/*bmih.biWidth*/; x++)
					{
						sobelX[x][y] = abs(   (-1 * input[x-1][y+1]) + (1 * input[x+1][y+1])
										    + (-2 * input[x-1][y]  ) + (2 * input[x+1][y]  )
											+ (-1 * input[x-1][y-1]) + (1 * input[x+1][y-1]));
					}
				}

				// Kanten in Y-Richtung

				for (int y=0; y< 240/*bmih.biHeight*/; y++)
				{
					for (int x=0; x< 320/*bmih.biWidth*/; x++)
					{
						sobelY[x][y] = abs(  (-1 * input[x-1][y+1]) + (1 * input[x-1][y-1])
											+(-2 * input[x]  [y+1]) + (2 * input[x]  [y-1])
											+(-1 * input[x+1][y+1]) + (1 * input[x+1][y-1]));
					}
				}

				for (int y=0; y< 240/*bmih.biHeight*/; y++)
				{
					for (int x=0; x< 320/*bmih.biWidth*/; x++)
					{	
						output[x][y] = sqrt(sobelX[x][y] * sobelX[x][y] + sobelY[x][y] * sobelY[x][y]);
					}
				}

				//------------------------------------------------------------------------------

ChaosAngel

Na das sieht doch schon eher nach Sobel aus. Sorry, das mit dem falschen Sobel war mein Fehler, hatte es falsch beschrieben.

for (int y=0; y<240/*bmih.biHeight*/; y++)
                {
                    for (int x=0; x<320/*bmih.biWidth*/; x++)
                    {    
                        sobelX[x][y] = output[x][y];
                        sobelY[x][y] = output[x][y];
                    }
                }

Dafür könntest auch mal n memcpy nehmen, und das ganze hin und her midde Speicher kannste gut über Pointer vereinfachen und ne Menge Performance rausholen, aber das tut ja erstmal noch nichts zur Sache.

Ob du das Bild gebrauchen kannst, nunja, ich muss gestehen das ich momentan nichts mehr auf dem Bild erkenne. Ich denke du musst einfach ein bisschen mit den Filtern experimentieren welches Anti-Noise Filter am besten dein Bild bereinigt und beim Sobeln vielleicht den Kernel vergrössern, oder sogar den Filter mehrmals drüber jagen um die Kanten noch stärker hervor zu heben ...

Du musst am Ende eine gute Mischung zwischen den Filtern finden so das die unwichtigen Linien herausfliegen und nur deine Kugel übrig bleibt. Ich denke darauf ein paar mal den Sobel angewendet sollte dir dann schon richtig scharfe linien geben die du dann testen kannst.

Mortal2006

Also ich würde das mit dem Sobel lassen ... das bringt zwar nachher bei der Linienerkennung nen bischen geschwindigkeit aber sonst wäre mir für deine Aufgabe kein weiterer vorteil bekannt (was natürlich nichts heißt) ...

Ich würde das Bild Binarisieren, oder wie man das nennt, und dann die linien mit so einer Art LaPlace Filter erkennen. Nur das der Laplace Filter eventl. werte außerhalb von 0-255 liefert ... deswegen würde ich sowas machen...

abs(input[x-1][y]-input[x][y])

Das ganze dann so wie beim Sobelfilter aus X und Y Richtung und man sollte die linien schön erkennen können

Jester

ChaosAngel schrieb:

Dafür könntest auch mal n memcpy nehmen, und das ganze hin und her midde Speicher kannste gut über Pointer vereinfachen und ne Menge Performance rausholen, aber das tut ja erstmal noch nichts zur Sache.

Ne ganze Menge Performance dürfte sich auch rausholen lassen, indem man den Sobel-Filter zerlegt:

(-1 0 1)   (1)           
(-2 0 2) = (2) ** (1 0 -1)
(-1 0 1)   (1)

** bezeichnet die Faltung. Also erst Kanten suchen und dann Mit Binomial-TP glätten. Der für waagrechte Kanten geht analog. Müßte man mal probieren, ob's was bringt. Bei größeren Matrizen ist der Vorteil größer.

Weißt Du eigentlich schon, wie's danach weitergehen soll? Außer "Linien suchen"? Falls nein, schau doch nochmal nach, ob Du nicht eine der bereits vorgeschlagenen Ideen ausprobieren möchtest.

gramboler

[quote="Jester]
Weißt Du eigentlich schon, wie's danach weitergehen soll? Außer "Linien suchen"? Falls nein, schau doch nochmal nach, ob Du nicht eine der bereits vorgeschlagenen Ideen ausprobieren möchtest.

-> Wie was weitergehen soll??? Und welche vorgeschlagene Ideen???
Meinst du damit irgendwelche Filter? Oder generell, wie ich die Koodinaten der Linien herausbekomme?
Bis zum Sobelfilter habe ich bis ketzt schließlich alles schon gemacht.

Was vielleicht noch interessant wäre, ist die Hough Transformation zur Erkennung von Kreisen.

@ChaosAngel

Ich glaube es ist besser, wenn man den Median Filter anch dem Sobel anwendet

Jester

gramboler schrieb:

-> Wie was weitergehen soll??? Und welche vorgeschlagene Ideen???
Meinst du damit irgendwelche Filter? Oder generell, wie ich die Koodinaten der Linien herausbekomme?
Bis zum Sobelfilter habe ich bis ketzt schließlich alles schon gemacht.

Und, wie funktionierte die Kantenerkennung mit Hough? War das Ergebnis des matched-Filters zu was zu gebrauchen?

Der Median-Filter ist hier übrigens vermutlich nicht so geeignet. Ein Gauß-Tiefpaß wäre vermutlich besser geeignet um das Rauschen zu unterdrücken. Ein Binomialtiefpaß könnte hinteressant sein.

gramboler

Die Hough Transformation habe ich ncht nicht durchgeführt. Ich werde aber darüber berichten, sobald ich das gemacht habe.
Ich muss mich gerade ein wenig um mein Studium kümmern, dass ich durch die rumprogrammierei ein wenig vernachlässigt habe.

Mein momentaner Stand ist:

- Bild über Webcam einlesen
- Videostream in einem Fenster ablaufen lassen
- ein Schwarz/Weis Bild daraus machen
- Sobel Filter darüber laufen lassen
- Median Filter
- Bild als Datei abspeichern

Geplant ist noch:

- Line zu erkennen
- Das Teil mit einem Anderen vergleichen und herausfinden ob es das richtige ist (darum die Linien- und Kreiserkennung, dient zur identifikation des Teils)
- ...ich weis nicht wie weit die Studienarbeit noch erweitert wird