Najciemniejsze miejsce obrazka

A co mi tam, męczę się już długo to już umieszczę...

No więc zastanawiam się nad algorytmem, który pozwoliłby wybrać z obrazka jak najciemniejszy obszar o zadanej wielkości. Funkcja zwracałaby tylko pozycję górnego lewego rógu obszaru. I to wszystko na TBitmap. Jakieś propozycje?

Podziel obrazek na prostokąty i oblicz średnią 'jasność' każdego z nich (średnia składowych kolorów każdego pixela i średnie tych średnich :-)). Po tym sortujesz uzyskaną listę jasności kwadratów i masz ich jasności:)

Podziel obrazek na prostokąty i oblicz średnią 'jasność' każdego z nich (średnia składowych kolorów każdego pixela i średnie tych średnich :-)). Po tym sortujesz uzyskaną listę jasności kwadratów i masz ich jasności:)

A jezeli nie sa rownomiernie rozmieszczone najciemniejsze prostokaty? Np. chcesz miec prostokat o rozmiarach 10x10. Jezeli podzielisz wedlug boku 10x10 to moze sie okazac, ze nie znajdziesz najciemniejszego, bo moze on sie zaczynac w od piksela (5, 5), czyli na obszarze 4 twoich prostokatow.

Jest wyjście, ale baaardzo prostackie: lecisz po wszystkich pikselach i ustalasz średnią jasności, nastepnie lecisz po pixelach i zapamietujesz te poniżej średniej, później grupujesz ich pozycje (czyli ustalasz czy są zgrupowane w pobliżu siebie) [imo, to jest trudne (znajdź dobrą pętle), ale może sobie poradzisz], gdy już masz położenie obiektów wybierasz te najciemniejsze i najbliższe podanemu rozmiarowi i gotowe. Proste, co? hmm... ni-hu-hu... ale powodzenia [cya]

Rozwiązanie toporne to właśnie te prostokąty, i lecenie całą pętlą począwszy od 1,1 do np. 10,1 a potem od 1,2 itd. - ale - jaka jest złożoność, każdy widzi ;) [długość oczekiwanego prostokąta * wysokośc prostokąta * (długość bitmapy-długośc prostokąta) * (wysokość bitmapy - wysokość prostokąta) = o czymś zapomniałem? :]

Sposobu jeden post wyżej trochę nie qmam ;) - co więcej - nie chce mi się mysleć ;) [nie chce mi się mysleć nad czymkolwiek, gdzie trzbea liczyć coś średniego - rzadko mi się udawało]

Możnaby jednak wyznaczyć przez przelecenie przez wsie piksele najjaśniejszych i powrzucać je na stos po czym wrzucając kolejne piksele jako miejsca, na których nie można postawić prostokąta, a stawiac go w innym miejscu...
dobra - pogmatwałem - sposób post wyżej jest lepszy ;)

Zakrecone to dopiero ja podam...

1. Dzielisz obraz na 4 prostakaty.
2. Wyznaczasz srednia wazona jasnosc kazdego z prostakatow. Wazenie polega na tym, ze im piksel blizej srodka podzialu, tym wieksza wage uzyskuje.
3. Wyznaczamy srodek nowego prostokata (ktorego wymiary sa o polowe mniejsze niz wymiary obrazka) tak, ze bierzemy srednie ktore wyliczylismy i proporcjonalnie, im wieksza wartosc sredniej, tym blizej odpowiedniego rogu ekranu laduje nasz nowy srodek.
4. Powtarzamy punkty 1-3 dla naszego nowego obrazka (ten wyznaczony prostokat) do momentu, az uzyskamy taki obrazek, ze juz kolejne zmniejszanie wymiarow spowoduje, ze nie bedzie mozna zmiescic w nim prostakata o poszukiwanej wielkosci
5. Jezeli poszukiwany obszar jest proporcjonalny do rozmiaru oryginalnej bitmapy to w efekcie otrzymamy wlasnie ten nasz poszukiwany najciemniejszy prostokat. Jezeli nie, to juz ten niewielki prostokat trzeba bedzie przeszukac metoda brute force, czyli maksymalnie (n-1)*(m-1) mozliwych kwadratow (m, n - wymiary poszukiwanego prostokata).

Mam nadzieje, ze cos z tego zrozumieliscie. To jest cos na styl HINT, metody kompresji przy uzyciu interpolacji (chociaz mocno przyblizone).

Strona Olimpiady Informatycznej, Niebieskie książeczki, chyba IX wydanie, zadanie Działki.

Wystarczy trochę zmodyfikować i będzie co trzeba...