Region Growing und Rekursive Aufrufe

[blender]

Hallo,

ich möchte gerne ein Programm schreiben, dass mit der Region Growing Methode Regionen erkennt.
Die erkannten Regionen dienen dazu, ein Bild zu Vektorisieren.
Ich bin mir dessen bewusst, dass Farbverläufe dann als eine Region erkannt werden.

Wenn ich den unten angegebenen Code ausführe, kommt nach einiger Wartezeit eine Warnmeldung: Stack Überlauf. (Die Stelle ist im Quellcode markiert.)

Dort habe ich einen Rekursiven Aufruf, was wahrscheinlich auch zu dem Fehler geführt hat.
Allerdings hätte ich bei einem Rekursiven Aufruf einen Fehler eher hier Erwartet:

Delphi-Quellcode:

c  := image.Canvas.Pixels[x,y];
c1 := image.canvas.pixels[x+1,y];
c2 := image.Canvas.Pixels[x-1,y];
c3 := image.canvas.pixels[x,y-1];
c4 := image.canvas.pixels[x,y+1];

da die Variablen ja auch noch beim nächsten mal die gleiche Adresse haben.

Delphi-Quellcode:

//...

type
  TXYValues = class
  Values: array of array of byte;
  LeftX, LeftY: Integer;
   private
    procedure RegionGrowing(x,y,i: integer; var image: TImage);
   public
    constructor Create(LengthX, LengthY: Integer);
    function NoRegionLeft: boolean;
    function IsAenlich(maxunterschied:Integer; var c1,c2:tcolor):boolean;
    procedure StartRegionGrowing(image: TImage; i: integer);
  end;

//...

procedure TXYValues.RegionGrowing(x,y,i: integer; var image: TImage);
var c, c1, c2, c3, c4: TColor;
begin
c  := image.Canvas.Pixels[x,y];
c1 := image.canvas.pixels[x+1,y];
c2 := image.Canvas.Pixels[x-1,y];
c3 := image.canvas.pixels[x,y-1];
c4 := image.canvas.pixels[x,y+1];

try //Nur um die Fehlermeldungen zu unterdrücken. Werde ich später ausbessern.
if (values[x+1,y]=0) then
if (IsAenlich(50, c, c1)) then
 begin
 values[x+1,y] := i;
 RegionGrowing(x+1,y,i,image);
 end;
except
end;

try
if (values[x-1,y]=0) then //in dieser Zeile ist der Stack Überlauf
if (IsAenlich(50, c, c2)) then
 begin
 values[x-1,y] := i;
 RegionGrowing(x-1,y,i,image);
 end;
except
end;

try
if (values[x,y-1]=0) then
if (IsAenlich(50, c, c3)) then
 begin
 values[x,y-1] := i;
 RegionGrowing(x,y-1,i,image);
 end;
except
end;

try
if (values[x,y+1]=0) then
if (IsAenlich(50, c, c4)) then
 begin
 values[x,y+1] := i;
 RegionGrowing(x,y+1,i,image);
 end;
except
end;

end;

procedure TXYValues.StartRegionGrowing(image: TImage; i: integer);
begin
RegionGrowing(leftx,lefty,i,image);
end;

function TXYValues.IsAenlich(maxunterschied:Integer; var c1,c2:tcolor):boolean;
var r1,g1,b1,
    r2,g2,b2: byte;
    crgb1,crgb2: Integer;
begin
  c1 := colortorgb(c1);
  c2 := colortorgb(c2);

  r1 := getrvalue(c1); // ROT
  g1 := getgvalue(c1); // GRÜN
  b1 := getbvalue(c1); // BLAU
  r2 := getrvalue(c2); // ROT
  g2 := getgvalue(c2); // GRÜN
  b2 := getbvalue(c2); // BLAU

  if r1+g1+b1 < r2+g2+b2 then
  begin
  crgb1 := r1+g1+b1;
  crgb2 := r2+g2+b2;
  end
  else
  begin
  crgb2 := r1+g1+b1;
  crgb1 := r2+g2+b2;
  end;

result := crgb1 >= crgb2 - maxunterschied;

end;

constructor TXYValues.Create(LengthX, LengthY: Integer);
var x, y: integer;
begin
inherited create;

SetLength(Values,lengthx,lengthy);

for x := 0 to High(values) do
 begin
 for y := 0 to High(values[x]) do
  begin
  Values[x][y] := 0;
  end;
 end;

end;

function TXYValues.NoRegionLeft: boolean;
var x,y: Integer;
begin

result := true;

for x := 1 to High(Values) do
 begin
 if result then
 for y := 1 to High(Values[x]) do
  begin
  if result then
  if Values[x][y] < 1 then
   begin
   result := false;
   Leftx := x;
   lefty := y;
   end;

  end;

 end;
end;

//...

procedure TForm1.ButtonClick(Sender: TObject);
var x, i: Integer;
    Regions: TXYValues;
begin
i := 0;
Regions := TXYValues.Create(image1.Width, image1.Height);

while not Regions.NoRegionLeft do
 begin

 inc(i);
 Regions.StartRegionGrowing(image1,i);

 end;

//Restliche Behandlung

Regions.Free;

end;

[Uwe Raabe]

Ohne das jetzt weiter zu anylysieren, aber solltest du nicht ab und an mal überprüfen, ob deine Koordinaten (x, y) überhaupt noch im gültigen Bereich liegen?

[blender]

Stimmt, danke. Werde ich ausbessern.
Falls vielleicht jemand eine Idee hat, wie man das anders Realisieren könnte wäre das auch nicht schlecht.

[blender]

Es kommt immer noch der Fehler Stack überlauf.

Neuer Code:

Delphi-Quellcode:

procedure TXYValues.RegionGrowing(x,y,i: integer; var image: TImage);
var c, c1, c2, c3, c4: TColor;
begin
c  := image.Canvas.Pixels[x,y];
c1 := image.canvas.pixels[x+1,y];
c2 := image.Canvas.Pixels[x-1,y];
c3 := image.canvas.pixels[x,y-1];
c4 := image.canvas.pixels[x,y+1];

if form1.progressbar1.position = form1.progressbar1.max then
form1.progressbar1.position := 0;
form1.progressbar1.Position := form1.progressbar1.Position+1;

if (High(values) > x) then //muss man hier zwei if Anweisungen plazieren?
 if (high(values[x]) > y) then // die zweite Abfrage soll logischerweise nur erfolgen,
 begin // wenn die erste Bedingung erfüllt ist.

 try
 if (values[x+1,y]=0) then
  if (IsAenlich(50, c, c1)) then
   begin
   values[x+1,y] := i;
   RegionGrowing(x+1,y,i,image);
   end;
 except
 end;

 try
 if (values[x-1,y]=0) then
  if (IsAenlich(50, c, c2)) then
   begin
   values[x-1,y] := i;
   RegionGrowing(x-1,y,i,image);
   end;
 except
 end;

 try
 if (values[x,y-1]=0) then
  if (IsAenlich(50, c, c3)) then
   begin
   values[x,y-1] := i;
   RegionGrowing(x,y-1,i,image);
   end;
 except
 end;

 try
  if (values[x,y+1]=0) then
   if (IsAenlich(50, c, c4)) then
    begin
    values[x,y+1] := i;
     RegionGrowing(x,y+1,i,image);
    end;
  except
  end;

 end;

end;

procedure TXYValues.StartRegionGrowing(image: TImage; i: integer);
begin
form1.progressbar1.min := 0;
form1.progressbar1.position := 0;
form1.progressbar1.max := 100;
RegionGrowing(leftx,lefty,i,image);
end;

[blender]

Ich habe eben noch einmal die Variablen durchgeguckt:
x = undefinierter Bezeichner
y = undefinierter Bezeichner
i = undefinierter Bezeichner
image = undefinierter Bezeichner
values = undefinierter Bezeichner
leftx = undefinierter Bezeichner
lefty = undefinierter Bezeichner

Also alle Variablen meines TXYValues.
Die Restlichen Variablen sind noch da.

Kann es sein, dass StartRegionGrowing nicht wartet bis RegionGrowing fertig ist und dann Regions vorzeitig freigegeben wird?

[Cyf]

Du kannst übrigens Bedingungen in den if-Abfragen mit

Delphi-Quellcode:

and

verknüpfen, würde das übersichtlicher machen, "ähnlich" :wink:
Sofern du keine Threads benutzt, was ich hier nicht sehe, wird nichts vorzeitig freigegeben (was überhaupt?) [Edit]achso oberer Schnipsel[/Edit], das würde auch in einer AccessViolation enden.
Ein Stacküberlauf im Zusammenhang mit Rekursionen deutet normalerweise auf eine fehlerhafte Abbruchbedingung hin.

[blender]

Ich weiß das man zwei bedingungen mit and verknüpfen kann. Ich habe ja dazu geschrieben/gefragt, ob das nötig ist, da wenn die erste Bedingung nicht erfüllt ist die zweite Funktion einen Fehler erzeugen würde.
Man überlege mal:
Wenn High(values) kleiner als x ist kann high(values[x]) nicht aufgerufen werden und würde einen Fehler erzeugen.
Hier noch mal den gesamten Quelltext.
Es ist alles Deklariert:

Delphi-Quellcode:

//uses Klausel und co.

type
  TXYValues = class
  Values: array of array of byte;
  LeftX, LeftY: Integer;
   private
    procedure RegionGrowing(x,y,i: integer; var image: TImage);
   public
    constructor Create(LengthX, LengthY: Integer);
    function NoRegionLeft: boolean;
    function IsAenlich(maxunterschied:Integer; var c1,c2:tcolor):boolean;
    procedure StartRegionGrowing(image: TImage; i: integer);
  end;

//Deklaration von TForm1 sowie Globale (oder lokale? Die verwechsle ich immer) Variablenvereinbarungen

procedure TXYValues.RegionGrowing(x,y,i: integer; var image: TImage);
var c, c1, c2, c3, c4: TColor;
begin
c  := image.Canvas.Pixels[x,y];
c1 := image.canvas.pixels[x+1,y];
c2 := image.Canvas.Pixels[x-1,y];
c3 := image.canvas.pixels[x,y-1];
c4 := image.canvas.pixels[x,y+1];

if form1.progressbar1.position = form1.progressbar1.max then
form1.progressbar1.position := 0;
form1.progressbar1.Position := form1.progressbar1.Position+1;

if (High(values) > x) then
 if (high(values[x]) > y) then
 begin

 try
 if (values[x+1,y]=0) then
  if (IsAenlich(50, c, c1)) then
   begin
   values[x+1,y] := i;
   RegionGrowing(x+1,y,i,image);
   end;
 except
 end;

 try
 if (values[x-1,y]=0) then
  if (IsAenlich(50, c, c2)) then
   begin
   values[x-1,y] := i;
   RegionGrowing(x-1,y,i,image);
   end;
 except
 end;

 try
 if (values[x,y-1]=0) then
  if (IsAenlich(50, c, c3)) then
   begin
   values[x,y-1] := i;
   RegionGrowing(x,y-1,i,image);
   end;
 except
 end;

 try
  if (values[x,y+1]=0) then
   if (IsAenlich(50, c, c4)) then
    begin
    values[x,y+1] := i;
     RegionGrowing(x,y+1,i,image);
    end;
  except
  end;

 end;

end;

procedure TXYValues.StartRegionGrowing(image: TImage; i: integer);
begin
form1.progressbar1.min := 0;
form1.progressbar1.position := 0;
form1.progressbar1.max := 100;
RegionGrowing(leftx,lefty,i,image);
end;

function TXYValues.IsAenlich(maxunterschied:Integer; var c1,c2:tcolor):boolean;
var r1,g1,b1,
    r2,g2,b2: byte;
    crgb1,crgb2: Integer;
begin
  c1 := colortorgb(c1);
  c2 := colortorgb(c2);

  r1 := getrvalue(c1); // ROT
  g1 := getgvalue(c1); // GRÜN
  b1 := getbvalue(c1); // BLAU
  r2 := getrvalue(c2); // ROT
  g2 := getgvalue(c2); // GRÜN
  b2 := getbvalue(c2); // BLAU

  if r1+g1+b1 < r2+g2+b2 then
  begin
  crgb1 := r1+g1+b1;
  crgb2 := r2+g2+b2;
  end
  else
  begin
  crgb2 := r1+g1+b1;
  crgb1 := r2+g2+b2;
  end;

result := crgb1 >= crgb2 - maxunterschied;

end;

constructor TXYValues.Create(LengthX, LengthY: Integer);
var x, y: integer;
begin
inherited create;

SetLength(Values,lengthx,lengthy);

for x := 0 to High(values) do
 begin
 for y := 0 to High(values[x]) do
  begin
  Values[x][y] := 0;
  end;
 end;

end;

function TXYValues.NoRegionLeft: boolean;
var x,y: Integer;
begin

result := true;

for x := 1 to High(Values) do
 begin
 if result then
 for y := 1 to High(Values[x]) do
  begin
  if result then
  if Values[x][y] < 1 then
   begin
   result := false;
   Leftx := x;
   lefty := y;
   end;

  end;

 end;
end;

//...

procedure TForm1.Button3Click(Sender: TObject);
var x, i: Integer;
    Regions: TXYValues;
begin
i := 0;
Regions := TXYValues.Create(image1.Width, image1.Height);

while not Regions.NoRegionLeft do
 begin

 inc(i);
 Regions.StartRegionGrowing(image1,i);

 end;

Regions.Free;

end;

[Uwe Raabe]

Du mußt nicht nur die oberen Array-Grenzen überprüfen, sondern auch die unteren (x < 0 bzw. y < 0).

Dieser Code sollte dein Problem lösen:

Delphi-Quellcode:

procedure TXYValues.RegionGrowing(x, y, i: integer; var image: TImage);  // übrigens ist das var hier überflüssig!

  procedure Check(c: TColor; x, y, i: integer; image: TImage);
  var
    c1: TColor;
  begin
    if (x >= 0) and (x < image.Width) then begin
      c1 := image.canvas.pixels[x, y];
      if (values[x, y] = 0) and IsAenlich(50, c, c1) then begin
        values[x, y] := i;
        RegionGrowing(x, y, i, image);
      end;
    end;
  end;

var
  c: TColor;
begin
  if form23.progressbar1.position = form23.progressbar1.max then
    form23.progressbar1.position := 0;  // sollte besser auf progressbar1.min gesetzt werden
  form23.progressbar1.Position := form23.progressbar1.Position+1;

  c  := image.Canvas.Pixels[x,y];
  Check(c, x + 1, y, i, image);
  Check(c, x - 1, y, i, image);
  Check(c, x, y - 1, i, image);
  Check(c, x, y + 1, i, image);
end;

Ich würde es sogar vorziehen, die procedure Check als Methode von TXYValues zu realisieren (deshalb auch die ausführliche Parameterliste).

[Cyf]

Bei Verwendung von and wird die zweite Bedingung (ohne Änderungen bei den Compiler-Schaltern) nicht mehr überprüft, wenn die erste bereits unwahr war, zumindet wenn ich mich grade richtig erinnere, da das auch von Sprache zu Sprache verschieden ist :gruebel: .

[Medium]

Das ist das Standardverhalten bei Delphi, man kann es aber in den Optionen abschalten: Projekt -> Optionen -> [Compiler] -> Syntaxoptionen -> Boolsche Ausdrücke vollständig (bei D7). In C kann man per Operator unterscheiden. Ein "&" ist ein AND mit der o.g. Option, "&&" entspricht dem Standardverhalten von Delphi. Entsprechend auch bei "|" bzw. "||" (=OR). Java kennt, wenn ich mich nicht irre, nur noch die doppelten Operanden, also nur noch den optimierten Fall in dem die Ausdrücke nicht zwangsweise vollständig ausgewertet werden. XOR gibt es übrigens nur in einfacher Ausführung "^", da dabei ohnehin immer der ganze Ausdruck ran muss.