Autor Wątek: Obwody plam  (Przeczytany 4712 razy)

Offline Knopi

  • Użytkownik

# Luty 01, 2008, 01:04:56
Według mnie filtry są ostro poronionym pomysłem... Kompletnie nie mam pojęcia jak to ma przyśpieszyć. Dostajesz na wejściu tablicę NxM ... Filtrujesz(N*M) i potem co z tym robisz ? Ja się cały czas pomysłu z obwodami co prawda ma to wtedy wciąż złożoność O(N*M) ale dla dużych plam znacznie przyśpieszy... Nie wiem jak można by to zrobić w mniejszej złożoności... A jeżeli stykanie rogami wykluczamy to możemy się na tę okoliczność zabezpieczyć...
No oczywiście to nie działa dla sytuacji dziurawych plam(czarne kółko w białym kółku...) -  jeżeli takie mogą wystąpić.
« Ostatnia zmiana: Luty 01, 2008, 01:25:49 wysłana przez Knopi »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Steel_Eagle

  • Użytkownik

# Luty 01, 2008, 01:44:24
Cytuj
Mam czarną bitmapę na które znajdować się będą różne plamy koloru białego. Moim zadaniem jest stosunkowo optymalnie znaleźć obwody tych plam(obiektów) zapisanych jako punkty o współrzędnych x,y.

Z tego co rozumiem to dla każdej plamy masz podany punkt (x,y) który leży w tej plamie. Wtedy zacznij od tego punkty iść w prawo i szukać konturu. Gdy dojdziesz do brzegu zapamiętaj ten punkt (będzie punktem końcowym) i idź po konturze aż wrócisz i licz kroki. Przechodzenie po konturze możesz napisać jako funkcję macierzy przyległych pikseli.

Offline Ventor

  • Użytkownik

# Luty 01, 2008, 08:06:57
Jedyne słuszne rozwiązanie to algorytm floodfill lub polska nazawa "pożar prerii". Trzeba go trochę zmodyfikować, żeby nie kolorował plamy a każdy napotkany kolor inny niż kolor plamy oznaczał jako jej obwód.

Filtr jest wolny bo trzeba przelatywać całą bitmapę, a szukanie konturu, o którym pisał Steel_Eagle nie sprawdzi się jeżeli plamy będą miały dziury.

//Edit
http://willow.wsb.edu.pl/~pgaj/instrukcje/instr_grafika_kontury.pdf
« Ostatnia zmiana: Luty 01, 2008, 10:24:35 wysłana przez Ventor »

deX(ter)

  • Gość
# Luty 01, 2008, 09:11:42
@Ventor: Co racja, to racja.. Floodfill by się do tego nadawał. Tu jest podobny problem, nie czytałem do końca, więc nie wiem, czy rozwiązany - http://forum.4programmers.net/viewtopic.php?p=369552

Offline shyha

  • Użytkownik
    • Shyha@Flickr

# Luty 01, 2008, 10:56:45
Xion: Oczywiscie, ze trzeba przeskanowac obrazek. Ja nigdzie nie mowilem o zlozonosci. Mowilem tylko, ze jechanie po krawedzi i porownywanie sasiednich pikseli to jest partyzantka. Jesli chcesz wyznaczyc krawedz - odpalasz filtr wysokoprzepustowy i juz masz wyrysowana krawedz. Ewentualnie mozna pewnie przejechac algorytmem zwezania krawedzi (nie pamietam jak on sie nazywal). Teraz sobie mozna jechac po pikselach i liczyc geometryczne odleglosci. Nie wiem jak ze zlozonoscia, nie wiem czy to najlepszy pomysl (ale taki przyszedl mi do glowy). Nie wiem jaka jest tresc zadania (zaliczeniowego pewnie).

Co do floodfill, to jak chcecie za pomoca tego obwod policzyc? Tez z wydajnoscia tego jest roznie, no i rekurencja, glebokosc stosu, eliminacja wielokrotnych powtorzen :)

Co do otoczki wypuklej, to by pewnie byl najlepszy pomysl ale nic nie wiemy o ksztalcie tych plam i jesli one moga byc dowolnego ksztaltu to ta metoda moze spowodowac duze rozbieznosci w wynikach (tak mi sie wydaje przynajmniej).


//edit:
teraz tak sobie mysle, ze pewnie wszystkie pomysly daloby sie zmiksowac w jedno rozwiazanie :)
« Ostatnia zmiana: Luty 01, 2008, 11:03:17 wysłana przez shyha »

Offline Liosan

  • Redaktor

# Luty 01, 2008, 11:53:23
no i rekurencja, glebokosc stosu, eliminacja wielokrotnych powtorzen :)

zastępujesz rekurencję while'm, eliminacja powtórzeń to druga bitmapa.

Jedyne słuszne rozwiązanie to algorytm floodfill ...

A ja myślę, że jedyne słuszne to odpowiednia miotła. I co teraz? :) Może poczekajmy na pana ciano :)

Liosan

Offline shyha

  • Użytkownik
    • Shyha@Flickr

# Luty 01, 2008, 11:56:49
Jak w tym wypadku chcesz to podmienic wersja nierekurencyjna? Zalozmy, ze plama ma ksztalt litery X i zaczniesz wypelniac na samym srodku. Pytam z ciekawosci, bo nie widze prostego rozwiazania.

Offline orzech

  • Użytkownik
    • homepage

# Luty 01, 2008, 13:31:23
W zeszłym semestrze pisałem aplikację do wektoryzacji obrazów rastrowych (w zasadzie dwukolorowych plam). Mając bitmapę należało znaleźć krzywą (Beziera, B-Sklejaną, łamaną ...), która najlepiej opisywałaby plamę. Problem kojarzy mi się trochę z tematem tego wątku. Wykorzystałem do rozwiązania algorytm genetyczny, być może tutaj znalazłby zastosowanie.

Pozdrawiam

Offline Liosan

  • Redaktor

# Luty 01, 2008, 14:00:01
Jak w tym wypadku chcesz to podmienic wersja nierekurencyjna? Zalozmy, ze plama ma ksztalt litery X i zaczniesz wypelniac na samym srodku. Pytam z ciekawosci, bo nie widze prostego rozwiazania.

Wydaje mi się, że nie do końca się zrozumieliśmy :) Powiedziałem, że można zastąpić while'm, bo while to rekurencja a rekurencja to while :) Możesz np. połączyć interesujące pola bitmapy w listę i traktować ją jak stos - tak jak się robi DFSa bez rekurencji. Nie jest to zbytnie usprawnienie - no, chyba, że planowałeś stack overflow :)

Liosan

Offline shyha

  • Użytkownik
    • Shyha@Flickr

# Luty 01, 2008, 14:07:18
Tylko caly problem polega wlasnie na wyznaczeniu tych 'interesujacych pol' :)

Offline Knopi

  • Użytkownik

# Luty 01, 2008, 14:15:36
A ja mam wrażenie, że każdy mówi o innym wariancie tego zadania...

Offline shyha

  • Użytkownik
    • Shyha@Flickr

# Luty 01, 2008, 14:21:09
A ja mam wrażenie, że każdy mówi o innym wariancie tego zadania...
Jest tylko jeden wariant: Dowolna plama. Wyliczyc obwod.

Offline Knopi

  • Użytkownik

# Luty 01, 2008, 14:31:53
Hmm... A takie pytanie taki układ x pikseli ułożonych w linii prostej jaki ma obwód ? 0 ? Traktujemy to jak odcinek ?

Offline shyha

  • Użytkownik
    • Shyha@Flickr

# Luty 01, 2008, 15:28:13
Ja bym raczej powiedzial 2*l
To pytanie do tego, kto rzucil temat i wstydzi sie przyznac, ze to zadanie na laborke z programowania, algorytmow albo grafiki.

Offline mwojt

  • Użytkownik

# Luty 08, 2008, 18:50:23
już gdzieś na innym forum wpisywałem, że to chyba tak:

long obwod=0;
for (int x=0; x<wielkośćplanszyx; x++)
for (int y=0; y<wielkośćplanszyy; y++)
if (pixel(x,y)==czarny)
 for (int a=-1; a<1; a++)
  for (int b=-1; b<1; b++)
   if (pixel(x+a,y+b)==biały) {obwod++; pixel(x+a,y+b)=szary;}