Grundlegende Algorithmen in der Bildverarbeitung

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

das : http://www.korbinian-riedhammer.de/misc/ip-suite.tar.bz2

was kann man den mit dem makefile machen?
wie funktioniert das ... ich habe mir sowas nochnie gearbeitet

Korbinian

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.

zafiro

make -f Makefile

= make das Makefile

bin/test-rotation sample.pgm out.pgm

= out.pgm is das bild was "raus kommt"

PS: natürlich musst du alles in die Konsole eingeben

zafiro

@Korbinian: kannst du mal bitte ein vernünftiges makefile erstellen?

Korbinian

was passt dir an diesem nich?

zafiro

der konventionen ignorierte passte einem nicht
konventionon = benennung das targets, allgemein zuviel text, kein "start"-target, ignore von CPPFLAGS

Kannst das auch alles vergessen

Korbinian

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

kgilgig

zafiro schrieb:

make -f Makefile

= make das Makefile

bin/test-rotation sample.pgm out.pgm

= out.pgm is das bild was "raus kommt"

PS: natürlich musst du alles in die Konsole eingeben

hmmm, dann kommt "error reading pgm image" . Dabei ist sample.pgm im richtigen Verzeichnis ... An was könnte das liegen

Rufus

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. mm Pixel.
Um die Performance zu steigern soll das Bild reduziert an das Control gesendet werden,
es muss doch reichen mm 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 ?

Vertexwahn

Skalierung von Rastergrafiken
http://turing.fh-landshut.de/~jamann/Skalierung von Rastergrafiken.pdf

Gregor

Vertexwahn schrieb:

Skalierung von Rastergrafiken
http://turing.fh-landshut.de/~jamann/Skalierung von Rastergrafiken.pdf

Interessant.

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.

Hallo,

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

[cpp]//******************************************************************************************
//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

  for(int i=1; i<resX-1; i++) { 
    for(int j=1; j<resY-1; j++){

      if(grid[i][j]==1) {
 doSegmentation(grid, i, j, label); //uebergabe grid an rekursion
      }
      label++;
    }
 }  [/cpp]

//******************************************************************************************
compilerfehler ist momentan folgender:
cannot convert 'int(*)[((resY-1)+1]' to 'int**' for argument '1' to 'void doSegmentation(int**,int,int,int)'

**********************************************************************

Vielen dank und viele Gruesse
marie