# SW-Bild: Rechteck um die hellsten Punkte



## madboy (19. Okt 2007)

Guten Abend liebe Forenbewohner,

ich hätte gern einen rechteckigen Bereich um helle Punkte gezogen. Aber der Reihe nach:

*Was ich habe:*
- Ein Grauwert-Bild im Arbeitsspeicher (Grauwerte in einem eindimensionalen Array um genau zu sein, aber das spielt eigentlich keine Rolle)

*Was ich gern hätte:*
- die Koordinaten eines (kleinstmöglichen) Rechteckes, das mehr als 50% aller Helligkeitswerte einschließt. Beispiel (0 sei schwarz, 255 weiß):

```
0 10  250 0 0
0 250 50  0 0
0 150 250 0 0
```
Die Summe aller Werte ist hier 960 und das gesuchte Rechteck von Zeile 2, Spalte 2 bis Zeile 3, Spalte 3, was eine Summe der Werte von 700 hätte (was wiederum mehr als 50% ist ;-) )

*Was ich mir überlegt hab:*
- "brute force"-Ansatz: 1. Summe aller Grauwerte ausrechnen. 2. links oben anfangen und so lange ein imaginäres Rechteck vergrößern, bis 50% aller Grauwerte drin sind. Dann ein Punkt nach rechts und wieder vergrößern. ... Am Schluß schauen, welches Rechteck die kleinste Fläche hat.
Vorteil: das minimale Rechteck wird sicher gefunden.
Nachteil: könnte recht langsam werden ;-)


- irgendwie den "Schwerpunkt" des Bildes suchen (zum Beispiel für jeden Pixel eine imaginäre Fläche der Größe seines Grauwertes annehmen und dann nach den Regeln zum Zusammenfassen von Schwerpunkten verrechnen) und von da aus dann das Rechteck so lange wachsen lassen, bis 50% der Grauwerte drin sind.
Vorteil: schneller als "brute force"
Nachteil: evtl. wird das minimale Rechteck nicht gefunden (wenn ich mich nicht täusche)


- ? Jetzt hörts leider schon auf... Mir fällt nix mehr ein


Für Ideen, Begriffe um ne Suchmaschine damit zu füttern oder sogar fertige Algorithmen wäre ich sehr dankbar.

In der Hoffnung, mich verständlich ausgedrückt zu haben,
madboy


----------



## Marco13 (19. Okt 2007)

Wenn ich das richtig verstanden haben, wäre das gesuchte Rechteck bei deinem Beispiel doch das Rechteck, das nur aus der Spalte
250
50
250
besteht?

Wie auch immer. Irgendwie "fühlt sich das nach dynamischem Programmieren" an.... Man müßte über einen guten (oder sogar "den besten") Ansatz wohl eine Weile nachdenken (und dafür hab ich leider gerade keine Zeit) aber ein Problem, das gewisse Ähnlichkeiten zu deinem hat, wurde hier schonmal behandlet... vielleicht enthält der Thread ja zumindest ein bißchen Inspiration (nicht der Trash, den ich damals gepostet hatte  , aber vielleicht die "Gewinner", die auf der letzen Seite verlinkt sind) 
http://www.java-forum.org/de/topic51555_such-algorithmus-beschleunigen.html


----------



## madboy (19. Okt 2007)

Marco13 hat gesagt.:
			
		

> Wenn ich das richtig verstanden haben, wäre das gesuchte Rechteck bei deinem Beispiel doch das Rechteck, das nur aus der Spalte
> 250
> 50
> 250
> besteht?


Wie peinlich  
Hast natürlich recht.

Danke für den Link, werd mir das mal anschauen. Scheint wirklich ne Ähnlichkeit da zu sein  :wink:


----------

