QImage Segmentierung

[micha]

Hi,

ich suche nach einer Möglichkeit zur Segmentierung eines 2-dimensionalen QImage-Bildes (540x150), das in Regionen mit eindeutigen Farben aufgeteilt ist (insgesamt 89 Regionen mit genau so vielen Farben).
Ziel der Segmentierung ist es, bei einer Suche nach einer bestimmten Farbe in dem Bild die Region die diese Farbe enthält, aufgeteilt in Rechtecke zu erhalten ( Rechtecke deshalb, da ich anschließend die Region per bitBlt auf ein QPaintDevice übertragen muss, was nur über QRect möglich ist ).
Die Region, die eine bestimmte Farbe enthält, ist zusammenhängend, es kann also nicht vorkommen, das eine Farbe über das ganze Bild verteilt ist.
Zusätzlich ist es wahrscheinlich, dass das QImge-Objekt zur Laufzeit seine Größe verändert, was zu folgenden Fragen führt:

1) Indiziere ich die kompletten Regionen bei jedem QResizeEvent oder soll ich jedesmal das komplette Bild nach der Region durschsuchen, wenn eine bestimmte Farbe abgefragt wird ( was im Endeffekt häufiger vorkommen wird, als die Größenveränderung des Bildes ).
Eine weiter Möglichkeit wäre auch ein Mittelweg, indem ich das Bild während eines QResizeEvents in Quadrate einteile und jede Farbe einem Quadrat zuteile, was das später Suchen der Farbe auf dieses Quadrat beschränken würde.

2) Gibt es einen schnellere Algorithmus um den ersten Pixel einer Farbe in dem Bild zu finden, als das Bild einfach von einer Seite beginnend danach zu durchsuchen ( wahrscheinlich schon, allerdings müsste da zuvor auch mindestens ein kompletter Bilddurchlauf zur Indizierung stattfinden, oder ? ).

3) Wenn ich jetzt einen Pixel der gesuchten Farbe habe, über welchen Algorithmus bestimme ich dann die konvexe Hülle, der dieser Pixel angehört ?

4) Und schließlich, wenn ich dann alle Punkte habe, wie teile ich die dann in Rechtecke auf ?

Mir würden schon ein paar Fachbegriffe, mit denen ich Google füttern kann helfen. Ich hab bis jetzt nur Seiten gefunden, die sich mit viel komplexeren Problemen beschäftigen ( 3-dimensionale Bilder, Unterscheidung zwischen Hintergrund und eigentlichen Elementen, Elemente bestehend aus unterschiedlichen Farbzusammenseztungen, was bei mir ja alles nicht gegeben ist ).
Ansätze wären natürlich auch nicht schlecht ,)

Gruß micha

[anda_skoa]

Hi micha!

Sind die Regionen so gestaltet, dass sich die umschreibende Rechtecke nicht überschneiden, oder ist das nicht sicher gewährleistet?

Beim Segmentieren würde ihc zuerst mal alle Regionen bestimmen und einen Index aufbauen, der für einen Farbwert, die x/y Koordinaten eines Punktes dieser Region enthält.
Vielleicht der Schwerpunkt der Region, wenn dieser in der Region liegt.

Wenn bei einem Resize bekannt ist, wo der neue Bereich ist, müßte man nur den neuen Teil checken und eventuell mit den Bereichen am Rand zum alten Bild verbinden.
Das hängt aber von der Vergrößerung ab.
Einfacher ist sicher, eine neue Indizierung zu machen.

Alles geht leichter, wenn die Bedingung erfüllt ist, dass sich die umschreibenden Rechtecke nicht überlappen.

So einen Fall hatte ich mal in einer Übung auf der Uni :)

Ciao,
_

[micha]

So einen Fall hatte ich mal in einer Übung auf der Uni :)

Na, ich mach das vorerst noch zum Glück nur als Hobby ;)


Sind die Regionen so gestaltet, dass sich die umschreibende Rechtecke nicht überschneiden, oder ist das nicht sicher gewährleistet?

Das ist nicht gewährleistet. Sorry, hab mich oben falsch ausgedrückt, ich suche natürlich nicht nach der konvexen Hülle, sondern nach den exakten Rechtecken, die diese Farbe beinhaltet. Ist vielleicht besser anhand eines Beispiels ;) :

http://www.aichler.net/test.png

Das QImage ist eine Maske für ein QPixmap, indem bei einem Event ein bestimmter Bereich, definiert durch die entsprechende Farbe in der Maske, durch ein anderes QPixmap ersetzt werden muss ( per bitBlt );

Ich hab jetzt erst mal beim Grundproblem, den Rechtecken, angefangen.
Das mit den Punkten suchen und die dann in Rechtecke aufteilen, hab ich ad acta gelegt. Statt dessen hab ich mir gedacht, ich suche zuerst den linken oberen Pixel der Farbe, indem ich das Bild von links oben nach rechts unten scanne, und bestimme dann zuerst die horizontale Breite.
Jede weitere Linie in dem Bild, die die gleiche x Koordinate hat und die gleiche Breite, wird dem Rechteck zugeordnet.
Wenn nicht, wird ein neues Rechteck erstellt.
Hier mal die Implementation:



const QRectArray search (QImage *img, const QRgb& rgb)
{
QPtrStack <QRect> stack;
QRect *cr = 0x0;
int width = img->width ();
int height = img->height ();
int items = 0;

for (int my=0; my < height; my++)
{
for (int mx=0; mx < width; mx++)
{
if (compare (img->pixel (mx,my), rgb))
{
/* top left edge of the color has been found */

for (int x=mx; x < width; x++)
{
/*search for the color´s horizontal end*/

if ( ! compare (img->pixel (x, my), rgb))
{
/*end has been found, color width is x-mx */

if ( ! cr || (mx != cr->x () && (x-mx) != cr->width ()))
{
cr = new QRect (mx, my, (x-mx), 1);
Q_CHECK_PTR (cr);
stack.push (cr);
items++;
}
else
/*enlarge rectangle by one line*/
cr->setHeight (cr->height () + 1);

/*break both x loops*/
x = mx = width;
}
}
}
} /* x */
} /* y */

QRectArray a(items--);

while (items >= 0)
a.insert (items--, stack.pop ());

return (a);
}


Die Funktion compare () ist lediglich dazu da, den Farbvergleich um einen definierten Fehlerbereich zu entschärfen.

Ist das eher ein bescheidener Ansatz ?

Gruß micha