Rotation von Bildern
2.1 Octave Implementierung
2.2 c++ Implementierung
Preprocessing von Bildern
3.1 Einfache Filter
3.2 Implementierung einfacher Filter in Octave
3.3 Implementierung einfacher Filter in c++
3.4 Effektive Implementierung eines 3x3 Gaussfilters
In diesem Artikel möchte ich einige grundlegende Verfahren vorstellen, die in der Bildverarbeitung regen Einsatz finden. Ich werde jedes Verfahren zunächst beschreiben, dann anhand eines Octave Skriptes veranschaulichen, und schließlich (fragmentweise) in c++ implementieren. Diese Implementierungen sind i.d.R. nicht die schnellsten, da ich auf Anschaulichkeit Wert gelegt habe.
Warum benutze ich Octave, um die Algorithmen zu veranschaulichen, obwohl der Leser vermutlich nur an der c++ Variante interessiert ist? Zum einen, weil Octave Programmtext deutlich übersichtlicher und damit leichter nachzuvollziehen ist. Meines Erachtens wichtiger ist aber, daß es gerade in der Bildverarbeitung praktisch ist, mit diesem Tool vertraut zu sein, da man oft ein Verfahren erst einmal ausprobieren möchte, bevor man es implementiert. Würde man sofort anfangen, die Idee in c++ zu implementieren, so hat man erst einmal einen größeren Zeitaufwand, dann das größere Risiko, einen Fehler darin zu haben, und letztendlich verfängt man sich leicht in Startschwierigkeiten wie "`wie lese ich ein Bild ein"'. Alles das wird durch die abstraktere Implementierung in Octave verhindert.
Neben den trivialen Implementierungen werde ich auch eine Effektive am Beispiel eines Filters zeigen, die nicht nur wegen den Programmiertricks so gut ist, sondern weil mathematische Umstände zu unserem Vorteil genutzt werden. Ich zeige das, um den Leser auch für die Theorie hinter den Verfahren zu interessieren. Oft entstehen neue schnelle Lösungen, weil die Probleme von einer anderen Seite betrachtet werden.
2 Rotation von Bildern
Oftmals sind die Bilder nicht in der Position, in der man sie gerne hätte. Das liegt zum einen daran, dass die Kamera oder der Detektor nicht korrekt angebracht sind, oder ganz einfach das Objekt nicht in der richtigen Lage ist, wie z.B. schiefe Fotos oder schiefe Zeilen in der Schrifterkennung. Rotationen im zweidimensionalen Raum lassen sich mathematisch recht einfach darstellen: Sei p ein zu rotierender und q der rotierte Punkt, so besteht folgender Zusammenhang mit der Rotationsmatrix R resultierend aus dem Rotationswinkel omega:
§R = \left( \begin{array}{cc} \cos\omega & -\sin\omega \\ \sin\omega & \cos\omega \end{array} \right)§ §q = Rp§
Möchte man nun eine Rotation eines ganzen Bildes durchführen, so berechnet man für jeden Punkt aus dem Urbild die Koordinaten im rotierten Bild. Bei der Implementierung ist auf ungültige Koordinaten zu achten: Das kann zum einen ein Nichtbeachten von nicht erreichbaren Koordinaten sein, zum anderen eine Expansion des Bildes (bei Winkeln ungleich 90, 180 und 270 Grad). Der Einfachheit halber werde ich hier Ersteres zeigen. Punkte im Bild, denen kein Punkt aus dem Urbild zugewiesen wird, bleiben z.B. schwarz. Nimmt man nun die "Vorwärtsabbildung" so kann es sein, dass manche Pixel aufgrund von Rundungsfehlern nicht rotiert werden. Dem kann man entgegenkommen, indem man nicht von Urbild nach Bild rechnet sondern umgekehrt, und optional beim Zugriff interpoliert (z.B. bilinear). Damit wird jedem Pixel im Bild ein (interpoliertes) Pixel aus dem Urbild zugeordnet, was umgekehrt aufgrund der Diskretisierung nicht der Fall ist.
for i=1:dim
for j=1:dim
x = round(i*cos(w)-j*sin(w));
y = round(i*sin(w)+j*cos(w));
if (x > 0 && x <= dim && y > 0 && y <= dim)
Bild(i,j) = Urbild(x,y);
endif
endfor
endfor
for i=1:dim
for j=1:dim
x = round(i*cos(w)-j*sin(w));
y = round(i*sin(w)+j*cos(w));
if (x > 0 && x <= dim && y > 0 && y <= dim)
Bild(i,j) = Urbild(x,y);
endif
endfor
endfor
for i=1:dim
for j=1:dim
x = round(i*cos(w)-j*sin(w));
y = round(i*sin(w)+j*cos(w));
if (x > 0 && x <= dim && y > 0 && y <= dim)
Bild(i,j) = Urbild(x,y);
endif
endfor
endfor
template <typename T>
void rotate(T* din, T* dout, unsigned sx, unsigned sy, double w)
{
for (unsigned i = 0; i < sy; ++i)
{
for (unsigned j = 0; j < sx; ++j)
{
signed rx = (signed)((double)j*cos(w) - (double)i*sin(w));
signed ry = (signed)((double)j*sin(w) + (double)i*cos(w));
if (rx < 0 || ry < 0 || rx >= sx || ry >= sy)
continue;
dout[i*sx + j] = din[ry*sx + rx];
}
}
return;
}
C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
template <typename T>
void rotate(T* din, T* dout, unsigned sx, unsigned sy, double w)
{
for (unsigned i = 0; i < sy; ++i)
{
for (unsigned j = 0; j < sx; ++j)
{
signed rx = (signed)((double)j*cos(w) - (double)i*sin(w));
signed ry = (signed)((double)j*sin(w) + (double)i*cos(w));
if (rx < 0 || ry < 0 || rx >= sx || ry >= sy)
continue;
dout[i*sx + j] = din[ry*sx + rx];
}
}
return;
}
C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
template <typename T>
void rotate(T* din, T* dout, unsigned sx, unsigned sy, double w)
{
for (unsigned i = 0; i < sy; ++i)
{
for (unsigned j = 0; j < sx; ++j)
{
signed rx = (signed)((double)j*cos(w) - (double)i*sin(w));
signed ry = (signed)((double)j*sin(w) + (double)i*cos(w));
if (rx < 0 || ry < 0 || rx >= sx || ry >= sy)
continue;
dout[i*sx + j] = din[ry*sx + rx];
}
}
return;
}
3 Preprocessing von Bildern
Normalerweise werden Bilder vor ihrer Verarbeitung erst vorbereitet, um bessere Eingangsbedingungen für die eigentlichen Algorithmen zu haben. Unter einem Filter verstehe ich eine Operation, die ein Bild verändert. Ich möchte hier zuerst einfache Filter vorstellen, die auf einer Faltung zweier Bilder beruhen, und dann erweiterte Filter, die teils aus mathematischen Ideen resultieren, und nichts mit Faltung zu tun haben.
3.1 Einfache Filter
Bei einfachen Filtern wird das Urbild mit einem Filterkernel gefaltet. Mathematisch ist die Faltung zweier Bilder im Diskreten für die Bildfunktionen f und g so beschrieben:
§(f * g)(n) = \sum_k{f(k)g(n-k)}§
Da allerdings der Filterkernel normalerweise eine Dimension von 3x3 oder 5x5 hat, keinenfalls aber die Größe des Urbilds, wird das Urbild abschnittweise mit dem Kernel gefaltet. Praktisch gesehen ist das eine Multiplikation der jeweils überlappenden Matrixelemente (was sich im c++ Code gut sehen lässt). Kernelgrößen sind im Allgemeinen ungerade, damit beim Programmieren immer die Mitte des Kernelfensters eindeutig ist.
Bei der hier gezeigten c++ Implementierung wird der Rand (also die Pixel, für die die Filtermaske nicht vollständig gefüllt ist) nicht gefiltert. Ein besseres Verfahren ist z.B. die fehlenden Werte mit 0 anzunehmen. Die Implementierung ist desweiteren nicht gerade die Effektivste: Für jedes Pixel wird das Kernelfenster neu aufgestellt. Ist die Kernelgröße im vornherein bekannt, so kann man effektivere Implementierungen schreiben, indem man sich Pointerarithmetik zu Hilfe nimmt. Als Beispiel eines effektiv implementierten Filters zeige ich eine elegante Version des 3x3 Gauß Filter, der sich neben der Pointerarithmetik noch folgende Eigenschaft zunutze macht: Die zweifache Anwendung des 2x2 Mittelwertfilters entspricht der einfachen Anwendung eines 3x3 Gaussfilters.
Verknüpfung von Kernel- und Bildelementen beim 3x3 Mittelwertfilter
Beispiele für einfache Filter
Mittelwert: Der Mittelwertfilter wird in verschiedenen Kernelgrößen verwendet und bildet jeweils den Mittelwert über die Umgebung. Kernelgrößen zwischen 2 und 5 sind gebräuchlich.
§M = \frac{1}{4}\left( \begin{array}{cc} 1 & 1 \\ 1 & 1 \end{array} \right)§
Gaußfilter: Der Gaussfilter wird in Kernelgrößen ab 3 verwendet, die Elemente sind entsprechend der Gaußverteilung erstellt. Er erzielt eine bessere Glättung des Bildes als ein Mittelwertfilter, da die Pixel von außen nach innen immer mehr an Einfluss erhalten.
§G = \frac{1}{16} \left( \begin{array}{ccc} 1 & 2 & 1 \\ 2 & 4 & 2 \\ 1 & 2 & 1 \end{array} \right)§
Kantenerkennung, finite Differenz: Der einfache Kantenerkennungsfilter beruht auf der Idee der finiten Differenzen. Betrachtet man das Bild als zweidimensionale diskrete Funktion, so kann man mit Hilfe des Differenzenquotienten die Steigung für x und y Richtung an jedem Punkt berechnen. Auf diese Weise erhält man kleine Werte, wenn sich der Farb-/Grauwert kaum ändert, und große Werte, wenn von einem Pixel zum nächsten ein starker An-/Abstieg ist. Die beiden gezeigten Kernel sind die sog. forward difference Kernel für x und y Richtung.
§B_x = \left( \begin{array}{cc} -1 & 1 \end{array} \right); B_y = \left( \begin{array}{c} -1 \\ 1 \end{array} \right)§
Vereinfacht gesagt beruht die Kantenerkennung durch finite Differenzen auf den Unterschieden von einem zum nächsten Pixel in jede Bildrichtung: Ändert sich der Farbwert stark, so ist die Differenz groß und eine Kante liegt vor. Ändert er sich aber kaum, so wird ein homogenes Gebiet vorliegen.
Sobelfilter: Der Sobelfilter funktioniert ähnlich wie der einfache Kantenerkennungsfilter, nur dass er die Nachbarschaft mit in Betracht zieht:
§S_x = \left( \begin{array}{ccc} -1 & 0 & 1 \\ -2 & 0 & 2 \\ -1 & 0 & 1 \end{array} \right); S_y = \left( \begin{array}{ccc} -1 & -2 & -1 \\ 0 & 0 & 0 \\ 1 & 2 & 1 \end{array} \right)§
void filter(double *din, double *dout, unsigned sx, unsigned sy, double *kernel, unsigned kdim)
{
for (unsigned y = (kdim/2); y < sy - (kdim/2); ++y)
for (unsigned x = (kdim/2); x < sx - (kdim/2); ++x)
{
dout[y*sx+x] = 0.;
for (unsigned i = 0; i < kdim; ++i)
for (unsigned j = 0; j < kdim; ++j)
dout[y*sx+x] += (kernel[i*kdim+j] * din[(y+j-kdim/2)*sx + x+i-kdim/2];
}
}
C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11
void filter(double *din, double *dout, unsigned sx, unsigned sy, double *kernel, unsigned kdim)
{
for (unsigned y = (kdim/2); y < sy - (kdim/2); ++y)
for (unsigned x = (kdim/2); x < sx - (kdim/2); ++x)
{
dout[y*sx+x] = 0.;
for (unsigned i = 0; i < kdim; ++i)
for (unsigned j = 0; j < kdim; ++j)
dout[y*sx+x] += (kernel[i*kdim+j] * din[(y+j-kdim/2)*sx + x+i-kdim/2];
}
}
C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11
void filter(double *din, double *dout, unsigned sx, unsigned sy, double *kernel, unsigned kdim)
{
for (unsigned y = (kdim/2); y < sy - (kdim/2); ++y)
for (unsigned x = (kdim/2); x < sx - (kdim/2); ++x)
{
dout[y*sx+x] = 0.;
for (unsigned i = 0; i < kdim; ++i)
for (unsigned j = 0; j < kdim; ++j)
dout[y*sx+x] += (kernel[i*kdim+j] * din[(y+j-kdim/2)*sx + x+i-kdim/2];
}
}
3.4 Effektive Implementierung eines 3x3 Gaussfilters
Wie eingangs erwähnt beruht diese Implementierung auf der Äquivalenz der zweifachen 2x2 Mittelwertfilterung zur 3x3 Gaussfilterung (wer's nicht glaubt nehme ein Blatt Papier, und rechne es nach :-). Daraus ergeben sich zwei Vorteile: Zum einen ist das Fenster auf 2x2 geschrumpft, zum anderen sind die Gewichte für die Felder jetzt immer 0.25 statt vorher zwischen 0.0625 und 0.25, was die Berechnung erleichtert: man kann im voraus alle Werte mal 0.25 nehmen, so muss man beim Durchlaufen nur noch zusammenzählen. Es werden somit 4 Pointer für das Kernelfenster und einer für das Outputfeld benutzt. Jetzt ist nur Vorsicht geboten: Wendet man den gleichen Filter zwei mal an, so stimmt das Ergebnis nicht. Das Outputfenster muss einmal an (0,0) und einmal an (1,1) liegen.
Nimmt man alles das zusammen, so erhält man folgende Implementierung:
void gaussian3filter(double *img, double *buf, unsigned sx, unsigned sy)
{
// this is a 3x3 gaussian filter realized by 2 2x2 mean value filters double *pass1 = buf;
double *pass2 = img+sx+1;
// first pass ptrs double *p1_1 = img;
double *p1_2 = img+1;
double *p1_3 = img+sx;
double *p1_4 = img+sx+1;
// second pass ptrs double *p2_1 = buf;
double *p2_2 = buf+1;
double *p2_3 = buf+sx;
double *p2_4 = buf+sx+1;
// perform 2 line of 1st pass for (unsigned i = 0; i < sx-1; ++i)
*pass1++ = .25*((*p1_1++) + (*p1_2++) + (*p1_3++) + (*p1_4++));
// skip last field
++pass1; ++p1_1; ++p1_2; ++p1_3; ++p1_4;
// 1 line more to go for (unsigned i = 0; i < sx-1; ++i)
*pass1++ = .25*((*p1_1++) + (*p1_2++) + (*p1_3++) + (*p1_4++));
++pass1; ++p1_1; ++p1_2; ++p1_3; ++p1_4;
// now continue with the 1st pass, but work on 2nd in parralel for (unsigned i = 2; i < sy-1; ++i) // we start in line 3
{
for (unsigned j = 0; j < sx-1; ++j)
{
*pass1++ = .25*((*p1_1++) + (*p1_2++) + (*p1_3++) + (*p1_4++));
*pass2++ = .25*((*p2_1++) + (*p2_2++) + (*p2_3++) + (*p2_4++));
}
++pass1; ++p1_1; ++p1_2; ++p1_3; ++p1_4;
++pass2; ++p2_1; ++p2_2; ++p2_3; ++p2_4;
}
// 2 more lines for 2nd pass for (unsigned i = 0; i < sx-1; ++i)
*pass2++ = .25*((*p2_1++) + (*p2_2++) + (*p2_3++) + (*p2_4++));
// skip last field
++pass2; ++p2_1; ++p2_2; ++p2_3; ++p2_4;
// 1 line more to go for (unsigned i = 0; i < sx-1; ++i)
*pass2++ = .25*((*p2_1++) + (*p2_2++) + (*p2_3++) + (*p2_4++));
}
4 Erweiterte Filter
Natürlich gibt es noch andere Filter, die nicht auf der Faltung von Urbild mit Kernel basieren. Sie machen sich meist andere Eigenschaften von realen Bildern oder unseres Perzeptionsmechanismus zunutze. Da die Implementierungen recht einfach sind und kaum Hilfsfunktionen benötigen, verzichte ich hier auf die Octave Variante.
4.1 Thresholding
Beim Thresholding wird, wie der Name schon sagt, ein Schwellwert festgelegt, und dementsprechend pixelweise für einen bestimmten Wert entschieden. Meistens benutzt man es, um s/w Bilder zu erhalten, man kann das Verfahren allerdings auch auf mehrere Farben auslegen, z.B. bei der Farbraumumwandlung von 16bit auf 8bit bei Farb- oder Grauwertbildern. Da dieser Filter so trivial ist, werde ich keine Implementierung zeigen.
4.2 Medianfilter
Dem Namen nach ähnelt er dem Mittelwertfilter aus dem vorigen Kapitel. Das dahinter liegende Verfahren ist jedoch ein komplett anderes: Die Farb-/Grauwerte werden über eine gewisse Fenstergröße (Kernelsize) in ein Array kopiert und sortiert, und dann das Pixel auf den Wert gesetzt, der in der Mitte dieses Arrays steht. Sinn dieses Verfahrens ist z.B. in Kombination mit dem Differenzbildverfahren Inhomogenitäten festzustellen: Weicht ein Pixel zu stark von seiner Umgebung ab, so liegt vermutlich eine Unregelmäßigkeit vor (bei Gusseisenteilprüfung z.B. ein Gasbläschen).
Der Vorteil des Medianfilters gegenüber dem Mittelwertfilter ist, dass diese Methode sehr ausreißerstabil ist. Wenn sich unter der Filtermaske viele Pixel gleicher Helligkeit befinden und einzelne sehr verschiedene, so haben diese keinen Einfluss auf den resultierenden Helligkeitswert. Die empfohlene Filtergröße liegt bei 7-13, je nach Verwendung.
template<type T>
void medianFilter(T *din, T *dout, unsigned sx, unsigned sy, unsigned ks)
{
T *values = new T[ks*ks];
for (unsigned y = (ks/2); y < sy - (ks/2); ++y)
{
for (unsigned x = (ks/2); x < sx - (ks/2); ++x)
{
// Werte aufsammeln for (unsigned i = 0; i < ks; ++i)
for (unsigned j = 0; j < ks; ++j)
values[i*ks + j] = din[(y+j-ks/2)*sx + (x+i-ks/2)];
// Array sortieren
std::sort(values, values+(ks*ks));
// Aktuelles Pixel auf Median setzen
dout[y*sx + x] = (T)(*(values+(ks/2)));
}
}
delete [] values;
return;
}
4.3 Histogram Equilisation
Ziel der Histogrammnormalisierung ist eine Verbesserung des Kontrastes und die Glättung des Histogramms. Letztere dient dazu eigentlich gleiche, aber unter verschiedenen Lichtverhältnissen aufgenommene Bilder besser vergleichen zu können. Es wird zuerst ein Histogramm des Bildes erstellt und anschließend normalisiert, sodaß das gesamte Spektrum des Farbraumes (Grauraumes) ausgenutzt wird. Wichtig ist jedoch, daß das Bildformat über einen Helligkeitskanal (YCrCb, HLS, ...) verfügt. Die hier vorgestellte Implementierung arbeitet mit [0;255] Grauwertbildern.
Der Algorithmus:
Erstelle eine Tabelle mit Zuordnung Grauwert-Häufigkeit
Erstelle die laufende Summe
Normalisiere jedes Element der Summe durch Teilung durch die Gesamtsumme
Multipliziere diese Werte mit dem hoechsten Grauwert
// Container fuellen for (unsigned y = 0; y < sy; ++y)
for (unsigned x = 0; x < sx; ++x)
container[din[y*sx+x]]++;
// Graymap erstellen
std::map<unsigned char, int> graymap;
for (unsigned it = 0; it < 256; ++it)
if (container[it] < 0)
graymap[it] = container[it];
// Laufende Summe bilden unsigned char hgval = 0;
double *sum = new double [graymap.size()]
std::map<unsigned char, int>::iterator iter = graymap.begin();
sum[0] = (double)iter->second;
for (unsigned it = 1, iter++; iter != graymap.end(); ++iter, ++it)
{
sum[it] = sum[it-1] + (double)iter->second;
if (iter->first > hgval)
hgval = iter->first;
}
for (unsigned it = 0; i < graymap.size(); ++it)
sum[it] = (int)(sum[it] / sum[graymap.size()-1]) * (double)hgval);
// Bild aktualisieren, dazu Grauwerttabelle anpassen for (unsigned it = 0; iter = graymap.begin(); iter != graymap.end(); ++iter, ++it)
container[iter->first] = (int)sum[it];
// container enthaelt jetzt die Zuordnung der neuen Grauwerte for (unsigned y = 0; y < sy; ++y)
for (unsigned x = 0; x < sx; ++x)
dout[y*sx+x] = container[din[y*sx+x]];
}
// Container fuellen for (unsigned y = 0; y < sy; ++y)
for (unsigned x = 0; x < sx; ++x)
container[din[y*sx+x]]++;
// Graymap erstellen
std::map<unsigned char, int> graymap;
for (unsigned it = 0; it < 256; ++it)
if (container[it] < 0)
graymap[it] = container[it];
// Laufende Summe bilden unsigned char hgval = 0;
double *sum = new double [graymap.size()]
std::map<unsigned char, int>::iterator iter = graymap.begin();
sum[0] = (double)iter->second;
for (unsigned it = 1, iter++; iter != graymap.end(); ++iter, ++it)
{
sum[it] = sum[it-1] + (double)iter->second;
if (iter->first > hgval)
hgval = iter->first;
}
for (unsigned it = 0; i < graymap.size(); ++it)
sum[it] = (int)(sum[it] / sum[graymap.size()-1]) * (double)hgval);
// Bild aktualisieren, dazu Grauwerttabelle anpassen for (unsigned it = 0; iter = graymap.begin(); iter != graymap.end(); ++iter, ++it)
container[iter->first] = (int)sum[it];
// container enthaelt jetzt die Zuordnung der neuen Grauwerte for (unsigned y = 0; y < sy; ++y)
for (unsigned x = 0; x < sx; ++x)
dout[y*sx+x] = container[din[y*sx+x]];
}
// Container fuellen for (unsigned y = 0; y < sy; ++y)
for (unsigned x = 0; x < sx; ++x)
container[din[y*sx+x]]++;
// Graymap erstellen
std::map<unsigned char, int> graymap;
for (unsigned it = 0; it < 256; ++it)
if (container[it] < 0)
graymap[it] = container[it];
// Laufende Summe bilden unsigned char hgval = 0;
double *sum = new double [graymap.size()]
std::map<unsigned char, int>::iterator iter = graymap.begin();
sum[0] = (double)iter->second;
for (unsigned it = 1, iter++; iter != graymap.end(); ++iter, ++it)
{
sum[it] = sum[it-1] + (double)iter->second;
if (iter->first > hgval)
hgval = iter->first;
}
for (unsigned it = 0; i < graymap.size(); ++it)
sum[it] = (int)(sum[it] / sum[graymap.size()-1]) * (double)hgval);
// Bild aktualisieren, dazu Grauwerttabelle anpassen for (unsigned it = 0; iter = graymap.begin(); iter != graymap.end(); ++iter, ++it)
container[iter->first] = (int)sum[it];
// container enthaelt jetzt die Zuordnung der neuen Grauwerte for (unsigned y = 0; y < sy; ++y)
for (unsigned x = 0; x < sx; ++x)
dout[y*sx+x] = container[din[y*sx+x]];
}
Röntgendetektoren, CCD Kameras oder Fingerprintleser haben oft defekte Pixel. An dieser Stelle liefern sie im Normalfall den Mini- oder Maximalwert des Wertebereichs zurück. Bei Röntgendetektoren oder CCD Kameras kann man diese defekten Pixel leicht identifizieren, indem man z.B. ein sog. Hellbild erstellt. Bei Röntgen ist das Vollbelichtung ohne durchstrahltes Objekt, bei CCD starke Überbelichtung ("Hellbild"). Das Ergebnis ist ein weißes Bild, das an den defekten Pixeln schwarz ist. Wiederholt man das mit einem Dunkelbild, so erhält man die entsprechend "anders" defekten Pixel. Hat man die defekten Pixel erst einmal identifiziert, kann man versuchen sie gezielt zu interpolieren. Oftmals genügt ein Mittelwertfilter im betroffenen Gebiet, möchte man allerdings mehr Information wiederherstellen oder ist das defekte Gebiet größer, so bietet sich das sog. band limitaion Verfahren an.
Wem die Fouriertransformation nicht geläufig ist, dem empfehle ich sich zuerst eine gute Erklärung dazu z.B. auf www.wikipedia.org zu lesen Die Idee: Das Bild wird als zweidimensionales Signal betrachtet. Man nimmt nun an, dass es in realen Bildern keine harten Sprünge in den Farb-/Grauwerten gibt, sondern immer mehr oder weniger weiche Übergänge. Wendet man nun die Fouriertransformation auf ein gewähltes Fenster des Bildes an, so bekommt man das Frequenzspektrum dieses Fensters, welches einem angibt, welche Sinus- oder Cosinusschwingungen man mit welcher Gewichtung überlagern müsste, um das Ausgangssignal zu erhalten. Harte Sprünge würden sich in hohen Frequenzen darstellen, da diese schnell oszillieren und man nur dadurch den geforderten schnellen Farbübergang erreichen kann. Beim band limitation Verfahren werden nun einfach alle Frequenzen oberhalb eines Grenzwertes auf 0 gesetzt, also entfernd. Rekonstruiert man nun das Bildfenster aus diesem modifizierten Frequenzspektrum, so erhält man eine Version des Bildes ohne die schnellen Frequenzen. Abschließend überträgt man die als defekt markierten Pixel von dem rekonstruierten Bild ins Originalbild. Wendet man dieses Verfahren nun iterativ an, so lässt sich die Qualität der Interpolation immer weiter verbessern. Will man das Verfahren noch optimieren, so kann man den Grenzwert bei dem die Frequenzen "abgeschnitten" werden sollen bei jeder Iteration neu bestimmen.
Zu diesem Verfahren biete ich jetzt nur eine Octave Implementierung, da für die c++ Variante eine FFT Bibliothek benötigt würde und dann der Code fast analog zur Octavevariante wäre.
An den Bildern sieht man, dass die Frequenzmethode für größere Fehler nur bedingt nützlich ist. Man könnte das Ergebnis verbessern, indem man eine kleinere Fenstergröße nimmt. Im Beispiel wurde das ganze Bild genommen, was hier einer Fenstergröße von 128 entspricht. Fenstergrößen von 64 Pixel haben sich bewährt.
Ok, dann kommen hier mal ein paar Anregungen und Hinweise von mir.
Zitat:
Bei der hier gezeigten c++ Implementierung wird der Rand (also die Pixel, für die die Filtermaske nicht vollständig gefüllt ist) nicht gefiltert. Ein besseres Verfahren ist z.B. die fehlenden Werte mit 0 anzunehmen.
Ich wollte hier darauf hinweisen, dass man an das "Randproblem" durchaus mit vielen unterschiedlichen Ansätzen herangeht, die natürlich auch für jeweils unterschiedliche Einsatzgebiete geeignet sind. Letztendlich kann man mit den ganzen Ansätzen, die es so gibt, wahrscheinlich ganze Bücher füllen und wahrscheinlich gibt es diese Bücher auch tatsächlich. Zwei weitere Ansätze für das Randproblem sind zum Beispiel.
1. Man kann jeweils den Wert des nächsten Pixels im Bild für einen Bildpunkt auf dem Rand annehmen.
2. Man kann das Ende des Bildes als eine Art Spiegel ansehen und für einen Bildpunkt auf dem Rand jeweils den Wert des "Spiegelpixels" im Bild annehmen.
Jede Variante hat hier ganz unterschiedliche Auswirkungen auf die äußeren Bereiche des Ausgabebildes. Wenn man den Rand des Bildes überall auf 0 setzt, dann wird bei Anwendung eines Mittelwertfilters das Ausgabebild nach außen hin dunkler. Bei Anwendung eines Ableitungsfilters werden vielleicht ungewollt große Steigungen in den äußeren Bereichen des Ausgabebildes angezeigt.
Nächster Punkt: Der Gaussfilter.
An dieser Stelle empfehle ich interessierten Lesern des Artikels, sich ein bischen mehr mit der dahinterstehenden Mathematik zu befassen, da diese hier interessante Möglichkeiten bietet, mit denen man beispielsweise eine ganze Menge Performance herausholen kann. Bei einem 3x3-Gaussfilter wird man da zwar noch nicht so viel herausholen können, aber wenn man es plötzlich mit einem 11x11-Gaussfilter zu tun hat, ist es schon sinnvoll, zu wissen, dass man hier die 2-dimensionale Faltung in 2 eindimensionale Faltungen aufteilen kann. Während man dann in der zweidimensionalen Faltung 11*11=121 Multiplikationen pro Pixel zu berechnen hat und entsprechend viele Zahlen summieren muss, hat man in den zwei eindimensionalen Faltungen nur noch 2*11=22 Multiplikationen pro Pixel zu berechnen und kann nebenbei auch noch einiges an Speicher sparen, weil man den Algorithmus "in-place" machen kann und dazu nur einen relativ kleinen Buffer benötigt, der einer Zeile/Spalte des Bildes entspricht.
Ein weiterer Punkt ist hier die Möglichkeit der Kombination von Gaussfilter und Ableitung. Wenn man beides machen möchte, kann man sich einiges an Zeit sparen, wenn man statt 2 Faltungen, einmal mit einem Gaussfilter und einmal mit einem Ableitungsfilter, nur noch eine Faltung mit der Ableitung eines Gaussfilters durchzuführen hat.
Insgesamt lohnt es sich einfach, die dahinterstehende Mathematik halbwegs zu kennen, wenn man mit Faltungen, Fouriertransformationen usw. zu tun hat. Die Mathematik bietet einem an dieser Stelle viele Möglichkeiten und zeigt interessante Eigenschaften dieser Operationen auf.
_________________ "The problem with quotes on the Internet is that it is hard to verify their authenticity" - Abraham Lincoln
Hallo,
ich verstehe zwar nur einen Bruchteil, traue mich aber trotzdem mal zu fragen.
Zum ersten Beispiel, siehe Code:
C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
template <typename T>
void rotate(T* din, T* dout, unsigned sx, unsigned sy, double w)
{ //was ist unsigned für ein Datentyp? Muß man int nicht angeben? for (unsigned i = 0; i < sy; ++i)
{
for (unsigned j = 0; j < sx; ++i) //wird j nicht inkrementiert?
{
signed rx = (signed)((double)j*cos(w) - (double)i*sin(w));
signed ry = (signed)((double)j*sin(w) + (double)i*cos(w));
if (rx < 0 || ry < 0 || rx >= sx || ry >= sy)
continue;
dout[i*sx + j] = din[ry*sx + rx];
}
}
return;
}
C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
template <typename T>
void rotate(T* din, T* dout, unsigned sx, unsigned sy, double w)
{ //was ist unsigned für ein Datentyp? Muß man int nicht angeben? for (unsigned i = 0; i < sy; ++i)
{
for (unsigned j = 0; j < sx; ++i) //wird j nicht inkrementiert?
{
signed rx = (signed)((double)j*cos(w) - (double)i*sin(w));
signed ry = (signed)((double)j*sin(w) + (double)i*cos(w));
if (rx < 0 || ry < 0 || rx >= sx || ry >= sy)
continue;
dout[i*sx + j] = din[ry*sx + rx];
}
}
return;
}
C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
template <typename T>
void rotate(T* din, T* dout, unsigned sx, unsigned sy, double w)
{ //was ist unsigned für ein Datentyp? Muß man int nicht angeben? for (unsigned i = 0; i < sy; ++i)
{
for (unsigned j = 0; j < sx; ++i) //wird j nicht inkrementiert?
{
signed rx = (signed)((double)j*cos(w) - (double)i*sin(w));
signed ry = (signed)((double)j*sin(w) + (double)i*cos(w));
if (rx < 0 || ry < 0 || rx >= sx || ry >= sy)
continue;
dout[i*sx + j] = din[ry*sx + rx];
}
}
return;
}
grübel dann schon einmal weiter...
_________________ freshman.say("Wer nicht an Wunder glaubt ist kein Realist"); while(1)freshman.roflbsaotp();
/*roflbsaotp:=RollingOnTheFloorLaughingBlowingSnotAllOverThePlace*/
Hoppla!
Danke für Hinweis auf den Tippfehler: Natürlich muss nicht i sondern j inkrementiert werden. Im Beispielprojekt zum download sollten allerdings keine Fehler sein.
_________________ Frage an mich? korbinian at c-plusplus dot de
ich muß ein Kantenbild erzeugen, dasgehört zum thema Morphologe Operatoren!
dieses bild wird mit einer ausgewählte maske (entweder 3x3 oder 5x5 maske)
und auch nach einem auswahl der innere oder äußere kante.
ich hoffe, das jemeinden mir helfen kann.bitte es ist sehr wichtig und ich muß vor montag mit den Programme fertig sein.
Ich hab das ganze nur überflogen, aber zur Optimierung des Gaussfilters ist es wohl besser den Filter zu separieren (was Gregor sagte). Dies ist immer dann möglich wenn dies gilt.
z.B.
Man hat dann nur noch zwei 1D Filter und nicht einen 2D.
Dann führt man jeweils eine Filterung des Bildes in X und eine in Y Richtung durch.
Wenn mans noch effizienter will, kopiert man die zu Filternde Zeile/Spalte in ein Array und den zusätzlichen Rand (spiegeln...) gleich mit. Dies hat den Vorteil, dass man nicht bei der Filterung prüfen muss, ob der Filter "rausragt", man spart also die ifs. Und man hat bei der Filterung in Y Richtung weniger Cache Misses, da es sehr wahrscheinlich ist, dass eine Spalte in den Cache passt, aber nicht das ganze Bild.
für den gaussfilter auf jeden fall, für den mittelwertfilter wäre ich mir da nicht so sicher: meine implementierung durchläuft das NxM feld genau einmal mit M*N + 2M schritten, für jeden schritt 8 additionen und zwei zuweisung. die aufspaltung würde dazu führen, das feld 2 mal im ganzen zu durchlaufen, dafür nur mit einer addition, einer subtraktion und einer zuweisung. ich habs jetz nicht exakt nachgeprüft, aber für große bilder dürft meins schneller sein, auch wenn du das bild nicht spiegelst sondern über pointer gehst.
_________________ Frage an mich? korbinian at c-plusplus dot de
so lautet dann die Aufgabe:
Erstellen Sie ein Programm zur Kantenerzeugung von Binärbildern wahlweise mithilfe einer 3x3 - oder 5x5-Maske.Man kann sog. innere und äußere Kanten erzeugen.
Das Programm soll die folgenden Anforderungen erfühllen:
=>Erzeugung wahlweise einer inneren oder äußeren Kante mit wahlweise einer 3x3- oder 5x5-Maske.
=>Darstellung des Kantenbildes.
und es gibt einen Regel zur Erzeugung einer Kanten bildes:
dilatiertes Bild XOR Quellbild = ein einpixelbreites Kantenbild
bzw.
quellbild XOR erodiertes Bild = ein einpixelbreites Kantenbild
Wenn Sie eine 5x5-Maske nehmen, dann wird die Kante breiter als ein Pixel.
ich hoffe, dass ich es dies mal besser ausgedrückt habe.
ich bedanke mich vielmals, dass du auf meine Frage geantwortet hast, ist wirklich sehr nett.
ich hoffe, dass du mich dies mal helfen könntest.
ich werde dann auf deine antwort warten.
So muss mich Korrigieren, ich meinte nicht den 3x3 Mittelwert (den man durch geeignete Pointer in "linearer" zeit (MxNx(8 add, 1div, 1 zuweis) machen kann) sondern den 3x3 Gauss, und der ist oben im Artikel. Allerdings spalte ich den 3x3 Kernel in eine doppelte Anwendung eines 2x2, wodurch man besser implementie
@Adil
Erwartest du jetzt dass jemand deine Hausaufgaben macht? Das solltest du eigentlich (dir zu liebe) selber machen. Ein Tip: Im Artikel oben wird gezeigt, wie man mit einem 3x3 Filter ein Kantenbild erzeugt. Noch ein Tip: Nachdem du ein binäres bild hast vereinfacht es den Filter. Es wird dir ein Hinweis auf Dilatation und Erosion gegeben, was eigentlich nichtlineare Filter sind. Im binären allerdings kannst du das trotzdem recht schick machen, da es so aussieht:
Erosion: Wenn im Filterbereich eine 0 vorkommt, setze das aktuelle Pixel auf 0
Dilatation: Wenn im Filterbereich eine 1 vorkommt, setze das aktielle Pixel auf 1
Ersteres macht das Bild optisch kleiner (frisst was weg), letzteres gibt was dazu. Was du jetzt implementieren musst ist lediglich das abfahren des Bildes mit deiner Filtermaske und das anschliessende ver-xor-en mit dem urbild. Wie das abfahren geht, beschreibe ich oben.
_________________ Frage an mich? korbinian at c-plusplus dot de
Zuletzt bearbeitet von Korbinian am 01:14:15 12.12.2005, insgesamt 1-mal bearbeitet
servus!
Hab das Forum hier grad entdeckt und auch gleich vieles zu fragen. Und zwar muss ich für die Uni einen Mittelwertfilter programmieren. Das Problem ist, dass ich kaum mit c++ gearbeitet hab und auch sonst nicht wirklich fit bin im programmieren. Kann mir vielleicht jemand schildern, wie man in c++ ein Bild einlesen (also Pfadangabe im code) und dann den Mittelwertfilter darauf anwenden kann und dieses Bild dann in verändertem Zustand wieder ausgeben kann. Soll nämlich n Plugin für ein Grafikprogramm werden, wenns fertig ist. Soll nix fertiges sein, aber vielleicht ne Anleitung in die richtige Richtung. Allein kriege ichs nicht gebacken. Das grübeln hat kein Ende.
An der Uni solltest du das lesen aber bereits beherrschen: Wie du einen (Mittelwert)Filter in c++ realisierst ist dort nämlich haarklein beschrieben, sowohl in Theorie als auch Praxis. Das Bildeinlesen ist etwas trickreicher, wenn du dich mit PGM (portable graymap) Bildern begnügst, kannst du aus meinem Beispielprojekt die lese und schreibfunktionen dafür verwenden. Alternativ bieten sich die verschiedenen Bibliotheken an (die du über google findest): libpng, libjpg und andere. Die einzubinden ist allerdings anfangs ein gefummel, da die oft recht umständlich sind. Wenn du noch Schwierigkeiten mit c(++) hast, würde ich empfehlen, dass du das erstmal mit leichten Tutorials aus der Welt schaffst. Wenn dir nur der Überblick fehlt, kannst du mal in mein Beispielprojekt reinsehen, wie die funkionen implementiert werden, und wie sie benutzt werden (in den Tests). Wenn du das ganze als Plugin schreiben sollst musst du dich auch noch mit den Pluginkonventionen rumärgern.
Hilft das?
_________________ Frage an mich? korbinian at c-plusplus dot de
erstmal danke für die schnelle Antwort. Werde mal in deine Beispielimplementierungen schauen und versuchen da was draus mitzunehmen. Falls es noch irgendwo hakt werde ich euch wahrscheinlich weiter nerven mit sinnlosen fragen
für den gaussfilter auf jeden fall, für den mittelwertfilter wäre ich mir da nicht so sicher: meine implementierung durchläuft das NxM feld genau einmal mit M*N + 2M schritten, für jeden schritt 8 additionen und zwei zuweisung. die aufspaltung würde dazu führen, das feld 2 mal im ganzen zu durchlaufen, dafür nur mit einer addition, einer subtraktion und einer zuweisung. ich habs jetz nicht exakt nachgeprüft, aber für große bilder dürft meins schneller sein, auch wenn du das bild nicht spiegelst sondern über pointer gehst.
für farbbilder ist ein 3x3 2d-mittelwertfilter schneller als zwei separierte 1d-kernel. hab ich zumindest so in meinen tests rausgebekommen (AMD Athlon XP 2800+, 1 GiB RAM). für alle anderen filtergrössen bringt die separierung enorme geschwindigkeitsgewinne.
C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Graubild
Filter Filtergröße Bildgröße Zeit-2D (in ms) Zeit-1D (in ms) Differenz
Mean 3x3 1024x960 79,9847 63,5322 79,43%
Mean 5x5 1024x960 109,5654 64,2914 58,68%
Mean 7x7 1024x960 146,9064 65,0890 44,31%
Mean 9x9 1024x960 178,9027 62,5780 34,98%
Mean 11x11 1024x960 210,9300 66,6648 31,61%
Mean 13x13 1024x960 244,8744 68,5941 28,01%
Mean 15x15 1024x960 278,5071 69,4492 24,94%
Mean 99x99 1024x960 3086,1738 288,0406 9,33%
Farbbild
Mean 3x3 1024x960 176,6281 208,3354 117,95%
Mean 5x5 1024x960 253,9408 205,2999 80,85%
Mean 7x7 1024x960 333,9920 210,3773 62,99%
C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Graubild
Filter Filtergröße Bildgröße Zeit-2D (in ms) Zeit-1D (in ms) Differenz
Mean 3x3 1024x960 79,9847 63,5322 79,43%
Mean 5x5 1024x960 109,5654 64,2914 58,68%
Mean 7x7 1024x960 146,9064 65,0890 44,31%
Mean 9x9 1024x960 178,9027 62,5780 34,98%
Mean 11x11 1024x960 210,9300 66,6648 31,61%
Mean 13x13 1024x960 244,8744 68,5941 28,01%
Mean 15x15 1024x960 278,5071 69,4492 24,94%
Mean 99x99 1024x960 3086,1738 288,0406 9,33%
Farbbild
Mean 3x3 1024x960 176,6281 208,3354 117,95%
Mean 5x5 1024x960 253,9408 205,2999 80,85%
Mean 7x7 1024x960 333,9920 210,3773 62,99%
C/C++ Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Graubild
Filter Filtergröße Bildgröße Zeit-2D (in ms) Zeit-1D (in ms) Differenz
Mean 3x3 1024x960 79,9847 63,5322 79,43%
Mean 5x5 1024x960 109,5654 64,2914 58,68%
Mean 7x7 1024x960 146,9064 65,0890 44,31%
Mean 9x9 1024x960 178,9027 62,5780 34,98%
Mean 11x11 1024x960 210,9300 66,6648 31,61%
Mean 13x13 1024x960 244,8744 68,5941 28,01%
Mean 15x15 1024x960 278,5071 69,4492 24,94%
Mean 99x99 1024x960 3086,1738 288,0406 9,33%
Farbbild
Mean 3x3 1024x960 176,6281 208,3354 117,95%
Mean 5x5 1024x960 253,9408 205,2999 80,85%
Mean 7x7 1024x960 333,9920 210,3773 62,99%
Hast du mal die Filterimplentierungen da? Mich würde die Testumgebung interessieren
ich glaub da wäre meine chefin nicht einverstanden.
zuerst werden die ränder erweitert (zero-padding, spiegeln, was auch immer). ein LUT wird angelegt um die zielgrauwerte zu berechnen. dann wird zuerste vertikal und dann horizontal gefiltert. beim filtern selbst, spare ich mir einige unnötige berechnungen. statt immer wieder neu die werte unter der filtermaske zu berechnen, aktualisiere ich lediglich die summe der grauwerte die aktuell unter der maske liegen, d.h. wenn die maske um einen pixel verschoben wird, kommt effektiv auch nur ein "neuer" pixel dazu und ein "alter" pixel verschwindet (1 addition und 1 subtraktion pro bildpunkt). den endgrauwert frage ich dann mit hilfe dieser summe und des LUT ab.
beim filtern selbst, spare ich mir einige unnötige berechnungen. statt immer wieder neu die werte unter der filtermaske zu berechnen, aktualisiere ich lediglich die summe der grauwerte die aktuell unter der maske liegen, d.h. wenn die maske um einen pixel verschoben wird, kommt effektiv auch nur ein "neuer" pixel dazu und ein "alter" pixel verschwindet (1 addition und 1 subtraktion pro bildpunkt). den endgrauwert frage ich dann mit hilfe dieser summe und des LUT ab.
Ah, deshalb ist das so schnell. Ich hatte mich schon geärgert, weil mein Gaussfilter hier ein ganzes Stück langsamer ist. Weißt du, ob so ein Trick auch mit nem Gaussfilter geht?
Wieso ist das bei nem Farbbild langsamer? Es müsste doch alles nur drei mal so lange dauern wie bei den Graubildern.
Naja, sein Bild ist so in etwa 1MB als Grauwertbild groß. Das passt vielleicht sogar in den Cache seiner CPU. Das Farbbild ist aber dreimal größer und das heißt, dass er häufiger auf den normalen Arbeitsspeicher zurücgreifen muss. Er wird vermutlich deutlich mehr als dreimal so viele Cache misses haben. Das könnte dazu führen, dass das mehr als dreimal so lange dauert. ...nur so ne Vermutung.
stimmt, das mit dem 1 sub und add ist ein guter trick. hast du bei den gaussfiltern mal die 2x 1d gegen meine 2d gebencht? weil das ist das eigentliche was mich interessiert ;)
_________________ Frage an mich? korbinian at c-plusplus dot de
bin bisher leider noch nicht dazu gekommen das auch mit anderen filtern zu testen. aber den medianfilter kann man extrem verbessern. dort kann man ebenfalls eine aktualisierung der werte vornehmen (das gilt übrigens für alle rangordnungsfilter).
Ausserdem würde es mich interessieren, was für ein datei ich jetzt als erstes aus deinem projekt compilern soll ... da sind nämlich mehr als eine .cpp datei
@b7f7: keine schlechte idee beim median gleich beim einfügen zu sortieren, das spart sicher zeit!
@kenner: nuja was hast du denn alles runtergeladen? das von dir genannte prinzip sollte es eigentlich schon tun. bei dem beispielprojekt von mir war allerdings auch ein makefile dabei :)
_________________ Frage an mich? korbinian at c-plusplus dot de
kenner der linuxsxsteme
Unregistrierter
kenner der linuxsxsteme Unregistrierter
19:00:32 19.02.2006 Titel:
wenn du mehr über make wissen möchtest, empfehle ich dir ein make tutorial, leicht über google erhältlich (im linux forum hier gibts auch eins, glaub ich). generell kannst du mit einem schlichten 'make' alles bauen, die binaries findest du dann unter bin/ oder lib/ steht glaub ich auch in der readme drin.
_________________ Frage an mich? korbinian at c-plusplus dot de
deine konventionen sind mir neu, ein start oder main mach ich nur, wenn es sich um ein programm handelt. das ist nur eine sammlung von klassen und funktionen, jemand der das benutzt sucht gezielt einzelne sachen. genauso die cppflags, drauf geschissen, ich will _meine_ compilierregeln für das projekt, nicht die standardmaessig eingestellten (auch hier wieder: es handelt sich nicht um ein auslieferbares programm/lib, sondern um ein spielzeug zum basteln).
aber es hindert dich niemand daran hier ein makefile reinzustellen. aber vielleicht schreibst du erst den datenbankartikel fertig...
_________________ Frage an mich? korbinian at c-plusplus dot de
Hallo ich habe hier mal reingeschaut und finde den Artikel super,
auch wenn ich nicht alles gelesen habe. Diese Grundlagen sind gut und wichtig, nett zusammengestellt.
Ich selbst interessiere mich für einen Algorithmus der mir Bilder verkleinert.
Aufgabe:
Ich habe ein Bild mit n-Megapixel das in einem Control dargestellt wird z.B. m*m Pixel.
Um die Performance zu steigern soll das Bild reduziert an das Control gesendet werden,
es muss doch reichen m*m Daten zu übertragen plus den Infos die das Bildformat benötigt.
Zusätzlich wäre es schön wenn die Koordinaten wieder hochgerechnet werden könnten wenn
z.B. im Control an Position x/y geklickt wurde entspricht dies ja im Originalbild anderen
Koordinaten.
Gibt es da Algorithmen ?
Wie heißt der Fachbegriff nach dem ich suchen sollte ?
Vielleicht noch ein Zusatz zur Verkleinerung von Bildern...
Das Problem ist da, dass im Ursprungsbild Frequenzen vorhanden sein können, die im verkleinerten Bild nicht mehr realisiert werden können. In dem PDF gibt es da ein Beispiel mit solchen Gittern, die teilweise beim Verkleinern verschwinden. Eine Variante, wie man dem aus dem Weg gehen kann, ist, mit einer passenden Tiefpassfilterung vor dem Verkleinern dafür zu sorgen, dass die Grenzfrequenz im Originalbild klein genug ist.
_________________ "The problem with quotes on the Internet is that it is hard to verify their authenticity" - Abraham Lincoln
Zuletzt bearbeitet von Gregor am 19:40:41 28.04.2006, insgesamt 1-mal bearbeitet
ich habe folgendes Problem:
Ich möchte in einem 2-Dimensionales Array (momentan nur aus bestehend 0 und 1 Feldern = einem Binärbild) Seqmente finden und zusammenhängende 1er Felder mit einem gemeinsamen Label beschriften (in diesem Falle geht dann das Label von 2 bis n und wird gesetzt indem ich einfach die 1 im Feld mit dem jeweiligen Wert ueberschreibe.
Das ganze versuche ich rekursiv, habe aber bisher noch ein Problem bei der Uebergabe des Arrays (=grid[resX][resY]) an die Rekursion. (Ob der Rest so funktioniert weiss ich noch nicht, weils ichs ja noch nicht ausprobieren konnte.)
Wäre super wenn mir jemand einen Tipp geben könnte was ich falsch mache. Bin nicht so wirklich erfahren in C++ und vorallem nicht mit Rekursionen. Das macht mir diverse Gehirnverknotungen
//******************************************************************************************
//initialisierung der Array-Grössen (momentan global) int resX = 500;
int resY = 500;
...
//segmentierungsfunktion void doSegmentation(int **grid, int x, int y, int label) {
grid[x][y] = label;
//gehe ueber alle 8 nachbarn des aktuellen pixels und gehe in rekursion wenn ein Pixel mit 1 belegt ist (d.h. nicht 0 und nicht schon gelabelt)
for (int dy=-1; dy<=1; dy++) {
for (int dx=-1; dx<=1; dx++) {
//TODO: pruefe hier ob Nachbar existiert oder gleich grid[x][y] ist if(grid[x+dx][y+dy] == 1) {
doSegmentation(grid, x+dx, y+dy, label);
cout<<"in recursion"<<endl;
}
else
continue;
}
}
return;
}
......
//startpunkt der Rekursion
int label = 2;
//gehe ueber 2 dim array von 1 bis res-2
//wenn pixel ==1 gehe in rekursion
//******************************************************************************************
//initialisierung der Array-Grössen (momentan global) int resX = 500;
int resY = 500;
...
//segmentierungsfunktion void doSegmentation(int **grid, int x, int y, int label) {
grid[x][y] = label;
//gehe ueber alle 8 nachbarn des aktuellen pixels und gehe in rekursion wenn ein Pixel mit 1 belegt ist (d.h. nicht 0 und nicht schon gelabelt)
for (int dy=-1; dy<=1; dy++) {
for (int dx=-1; dx<=1; dx++) {
//TODO: pruefe hier ob Nachbar existiert oder gleich grid[x][y] ist if(grid[x+dx][y+dy] == 1) {
doSegmentation(grid, x+dx, y+dy, label);
cout<<"in recursion"<<endl;
}
else
continue;
}
}
return;
}
......
//startpunkt der Rekursion
int label = 2;
//gehe ueber 2 dim array von 1 bis res-2
//wenn pixel ==1 gehe in rekursion
//******************************************************************************************
//initialisierung der Array-Grössen (momentan global) int resX = 500;
int resY = 500;
...
//segmentierungsfunktion void doSegmentation(int **grid, int x, int y, int label) {
grid[x][y] = label;
//gehe ueber alle 8 nachbarn des aktuellen pixels und gehe in rekursion wenn ein Pixel mit 1 belegt ist (d.h. nicht 0 und nicht schon gelabelt)
for (int dy=-1; dy<=1; dy++) {
for (int dx=-1; dx<=1; dx++) {
//TODO: pruefe hier ob Nachbar existiert oder gleich grid[x][y] ist if(grid[x+dx][y+dy] == 1) {
doSegmentation(grid, x+dx, y+dy, label);
cout<<"in recursion"<<endl;
}
else
continue;
}
}
return;
}
......
//startpunkt der Rekursion
int label = 2;
//gehe ueber 2 dim array von 1 bis res-2
//wenn pixel ==1 gehe in rekursion
if(grid[i][j]==1) {
doSegmentation(grid, i, j, label); //uebergabe grid an rekursion
}
label++;
}
}
//******************************************************************************************
compilerfehler ist momentan folgender:
cannot convert 'int(*)[((resY-1)+1]' to 'int**' for argument '1' to 'void doSegmentation(int**,int,int,int)'
//******************************************************************************************
compilerfehler ist momentan folgender:
cannot convert 'int(*)[((resY-1)+1]' to 'int**' for argument '1' to 'void doSegmentation(int**,int,int,int)'
Hallo, ich suche Methoden zum Ermitteln von Greifpunkten für einen sauger!
ich möchte aus einer kste mehrere päckchen rausholen und benötige dazu einen greifpunkt!
welche möglichkeiten gibt es? ( mittelpunkt,schwerpunkt)
ich binarisiere das bild und erhalte helle wolken an den relevanten stellen und möchte nun in diese wolken greifen.
ich brauche für ein Projekt einen 3d gauss filter in c++ ....hat da vll jemand nen code? oder kann man für ein 3d objekt auch einen 2d filter verwenden?
Den in 2d findet man ja hier schon...vll kann man den auch einfach umschreiben nur meiner einer ist dazu leider nicht im stande .
vll kann man den auch einfach umschreiben nur meiner einer ist dazu leider nicht im stande
Dann fang doch einfach schonmal an damit und wenn du dann tatsächlich auf Probleme stößt fragst du im entsprechenden Forum nach. Eine Fertiglösung wirst du hier im Forum wohl kaum einfach vorgesetzt bekommen.
ich brauche für ein Projekt einen 3d gauss filter in c++ ....hat da vll jemand nen code? oder kann man für ein 3d objekt auch einen 2d filter verwenden?
Den in 2d findet man ja hier schon...vll kann man den auch einfach umschreiben nur meiner einer ist dazu leider nicht im stande .
Guck Dir mal die Vigra-Bildverarbeitungsbibliothek an. Die ist ausgesprochen gut und realisiert viele Algorithmen für den allgemeinen Fall von n-dimensionalen Bildern. Einen Gauss-Filter für dreidimensionale Bilder findest Du da auf jeden Fall.
_________________ "The problem with quotes on the Internet is that it is hard to verify their authenticity" - Abraham Lincoln
Zuletzt bearbeitet von Gregor am 13:52:38 26.06.2009, insgesamt 1-mal bearbeitet
Will einen Mittelwertfilter beliebiger Größe separieren, also erst die Zeilen und danach die Spalten durchlaufen. Das ganze ist über Borland c++ geschrieben und hab ne eigene Klasse, die mein geladenes Bild in einen Array des Typs unsigned char. Hier mal der Code:
Image* Image::MWSep(int Maske){
if (Maske % 2 == 0) { //Es sollen nur ungrade Filtergrößen zugelassen werden return 0;
}
int radius = Maske / 2;
int pixel; //Zum Hochzählen
Image* ci = new Image( width, height,format); //2 neue Images angelegt, um das jeweilige Ergebnisbild zu speichern
Image* cj = new Image( width, height,format);
//MW Filter Spalten for (int i = 0; i < chanel; i++) { // Alle Kanäle for (int j = 0; j < height ; j++) { // Alle Zeilen for (int k = 0; k < width ; k++) { // Alle Spalten if(k<radius||k>height-radius){ //Rand bekommt das Ursprungsbild
ci->Data[i][j*width+k]=Data[i][j*width+k];
}
else{
//eigendlicher Mittelwertfilter, über alle Zeilen
pixel = 0;
for(int l=k-radius; l<= k+radius; l++){ //Zeilen
pixel+= Data[i][l*width+j];
}
ci->Data[i][j*width+k]=(double) pixel /Maske + 0.5;
}
}
}
}
//MW Filter Über alle Spalten for (int i = 0; i < chanel; i++) { // Alle Kanäle for (int j = 0; j < height ; j++) { // Alle Zeilen for (int k = 0; k < width ; k++) { // Alle Spalten if(k<radius||k>width-radius){ //Randbehandlung
cj->Data[i][j*width+k]=Data[i][j*width+k];
}
else{
Image* Image::MWSep(int Maske){
if (Maske % 2 == 0) { //Es sollen nur ungrade Filtergrößen zugelassen werden return 0;
}
int radius = Maske / 2;
int pixel; //Zum Hochzählen
Image* ci = new Image( width, height,format); //2 neue Images angelegt, um das jeweilige Ergebnisbild zu speichern
Image* cj = new Image( width, height,format);
//MW Filter Spalten for (int i = 0; i < chanel; i++) { // Alle Kanäle for (int j = 0; j < height ; j++) { // Alle Zeilen for (int k = 0; k < width ; k++) { // Alle Spalten if(k<radius||k>height-radius){ //Rand bekommt das Ursprungsbild
ci->Data[i][j*width+k]=Data[i][j*width+k];
}
else{
//eigendlicher Mittelwertfilter, über alle Zeilen
pixel = 0;
for(int l=k-radius; l<= k+radius; l++){ //Zeilen
pixel+= Data[i][l*width+j];
}
ci->Data[i][j*width+k]=(double) pixel /Maske + 0.5;
}
}
}
}
//MW Filter Über alle Spalten for (int i = 0; i < chanel; i++) { // Alle Kanäle for (int j = 0; j < height ; j++) { // Alle Zeilen for (int k = 0; k < width ; k++) { // Alle Spalten if(k<radius||k>width-radius){ //Randbehandlung
cj->Data[i][j*width+k]=Data[i][j*width+k];
}
else{
Image* Image::MWSep(int Maske){
if (Maske % 2 == 0) { //Es sollen nur ungrade Filtergrößen zugelassen werden return 0;
}
int radius = Maske / 2;
int pixel; //Zum Hochzählen
Image* ci = new Image( width, height,format); //2 neue Images angelegt, um das jeweilige Ergebnisbild zu speichern
Image* cj = new Image( width, height,format);
//MW Filter Spalten for (int i = 0; i < chanel; i++) { // Alle Kanäle for (int j = 0; j < height ; j++) { // Alle Zeilen for (int k = 0; k < width ; k++) { // Alle Spalten if(k<radius||k>height-radius){ //Rand bekommt das Ursprungsbild
ci->Data[i][j*width+k]=Data[i][j*width+k];
}
else{
//eigendlicher Mittelwertfilter, über alle Zeilen
pixel = 0;
for(int l=k-radius; l<= k+radius; l++){ //Zeilen
pixel+= Data[i][l*width+j];
}
ci->Data[i][j*width+k]=(double) pixel /Maske + 0.5;
}
}
}
}
//MW Filter Über alle Spalten for (int i = 0; i < chanel; i++) { // Alle Kanäle for (int j = 0; j < height ; j++) { // Alle Zeilen for (int k = 0; k < width ; k++) { // Alle Spalten if(k<radius||k>width-radius){ //Randbehandlung
cj->Data[i][j*width+k]=Data[i][j*width+k];
}
else{
Also die Performancediskussion ... MMX und SSEx sind wie geschaffen fuer diese Operationen. Auch kann man es direkt auf seiner Grafikkarte ueber Shader realisieren.
Zum geposteten Code: Ich persoenlich finde ihn nicht schoen. Was solls ...
_________________ If it were not for laughter, there would be no Tao.
Sie können einen Beitrag nicht so schnell nach Ihrem letzten absenden, bitte warten Sie einen Augenblick.
Nächstes Thema anzeigen Vorheriges Thema anzeigen
Sie können keine Beiträge in dieses Forum schreiben. Sie können auf Beiträge in diesem Forum antworten. Sie können Ihre Beiträge in diesem Forum nicht bearbeiten. Sie können Ihre Beiträge in diesem Forum nicht löschen. Sie können an Umfragen in diesem Forum nicht mitmachen.
c++.de ist Teilnehmer des Partnerprogramms von Amazon Europe S.à.r.l. und Partner des Werbeprogramms, das zur Bereitstellung eines Mediums
für Websites konzipiert wurde, mittels dessen durch die Platzierung von Werbeanzeigen und Links zu amazon.de
Werbekostenerstattung verdient werden kann.
Die Vervielfältigung der auf den Seiten www.c-plusplus.de, www.c-plusplus.info, www.c-sar.de, www.c-plusplus.net und www.baeckmann.de
enthaltenen Informationen ohne eine schriftliche Genehmigung des Seitenbetreibers ist untersagt
(vgl. §4 Urheberrechtsgesetz). Die Nutzung und Änderung der vorgestellten Strukturen und Verfahren in
privaten und kommerziellen Softwareanwendungen ist ausdrücklich erlaubt, soweit keine Rechte Dritter verletzt werden.
Der Seitenbetreiber übernimmt keine Gewähr für die Funktion einzelner Beiträge oder Programmfragmente, insbesondere
übernimmt er keine Haftung für eventuelle aus dem Gebrauch entstehenden Folgeschäden.
Twitter
Facebook
, nur den Code würde ich noch besser vom Text abgrenzen. Auf jeden Fall toll, dass ihr euch hier die Mühe macht. 
dort kann man ebenfalls eine aktualisierung der werte vornehmen (das gilt übrigens für alle rangordnungsfilter). 
.
