Grundlegende Algorithmen in der Bildverarbeitung

MrBurns

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.

0 1 0   0 0 0   1 1 1
0 1 0 * 1 1 1 = 1 1 1
0 1 0   0 0 0   1 1 1

oder 

0 1 0   0 0 0   1 2 1
0 2 0 * 1 2 1 = 2 4 2
0 1 0   0 0 0   1 2 1

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.

Korbinian

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.

MrBurns

Kannst du den Code mal posten.

ok mann, ich formoliere es dann anders.

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.

danke nochmal .

Adil

Korbinian

MrBurns schrieb:

Kannst du den Code mal posten.

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.

Souza

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.

vielen Dank im voraus

Korbinian

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?

Souza

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

gruß

Sunday

Korbinian schrieb:

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.

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%

Korbinian

Hast du mal die Filterimplentierungen da? Mich würde die Testumgebung interessieren

Testumgebung war ein Computer.

Sunday

Korbinian schrieb:

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.

Sunday schrieb:

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.

schrieb:

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.

Korbinian

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

Sunday

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).

b7f7

bei grössen daten ist es besser den median in dieser Art zu rechnen
damit commt man in logN zum Ziel

template <typename T>
struct divider
{
  divider(const T&o):val(o){}
  bool operator()(const T&o) {return o<val;}
  T val;
};

template <typename T,typename RandItr>
RandItr median(RandItr begin, RandItr end)[cpp]
{
  while(begin!=end)
  {
    divider<T> Pred((*(begin) + *(end-1))/2 );
    RandItr pos=std::partition(begin,end,Pred);
    size_t distB=std::distance(begin,pos);
    size_t distE=std::distance(pos,end);
    if(distB==0)            return begin;
    else if(distB<distE)    begin=pos;
    else                    end=pos;

  }
  return begin;
}

das hat sicher noch paar macken aber dafür is mir grad zu früh

Wie führt man das unter linux aus?

g++ dateiname.cpp -o dateiname
./dateiname

funktioniert nicht,

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

Korbinian

@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