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

Offline ciano

  • Użytkownik
    • Serwis naprawy telewizorów LCD

# Styczeń 31, 2008, 21:29:27
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.

Offline Mr. Spam

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

cyberion

  • Gość
# Styczeń 31, 2008, 21:33:33
I co? Liczysz na kod? ;]. Sprecyzuj, czego oczekujesz od forumowiczów ;].

A tak ode mnie - w czym to masz napisać?

Offline Złośliwiec

  • Użytkownik
    • Dark Cult

# Styczeń 31, 2008, 21:41:00
Jeśli plama jest punktem, to jej obwód jest równy zero :). Natomiast jeśli jest trochę większa, to masz wierzchołki - wystarczy zsumować długość łączących je odcinków i masz obwód.

A jeśli coś źle zrozumiałem, to dlatego, że pytanie zostało zadane w dość dziwny sposób :).

Offline Knopi

  • Użytkownik

# Styczeń 31, 2008, 23:29:01
A może program ma przeszukać bitmapę i znaleźć białe plamy, które składają się z pewnych punktów(x,y) oraz obliczyć ich obwód ?

cyberion

  • Gość
# Styczeń 31, 2008, 23:35:36
Ja na Twoim miejscu miałbym następujący plan działania:

ustalasz wielkość plamki ( masz jej współrzędne x,y ) i odpowiednio do wielkości bitmapy dostosowujesz promień plamki ( załóżmy że będzie to koło ). Jeżeli w Twoim programie po wciśnięciu jakiegoś klawisza ilość tych plamek ma się zwiększać/zmniejszać to wtedy regulujesz już tylko promieniem, bo współrzędne mogą być ( co wcale nie oznacza, że muszą ) losowane.
To co napisałem to taka moja wizja tego jak mógłbyś to racjonalnie zastosować w swoim programie.

Offline skoti

  • Użytkownik

# Styczeń 31, 2008, 23:42:04
wpisujesz współrzędne białych punktów i liczysz z nich otoczkę wypukłą, wtedy tylko sumujesz odległości między punktami na obwodzie działać będzie dla najbardziej wymyślnych plamek :)

Offline Khaine

  • Użytkownik

# Styczeń 31, 2008, 23:49:33
ja mysle, ze chodzi o dowolne plamy. Wtedy zrobilbym to iteracyjnie. Jedziemy po calej bitmapie i sprawdzamy kolor. Jesli jest rowny 0xFFFFFF (czy jaka tam jest jego interpretacja jako bialego) to sprawdz czy pixel wyzej jest kolor 0x000000 (a w zasadzie brak koloru :P). Jesli tak, to znaczy, ze jestes na 'gorze' placka i ten pixel nalezy do obwodu. Analogicznie z lewa, prawa strona i dolem. Jesli sprawdzamy od lewej do prawej to: jesli napotkasz bialy pixel, a poprzedni byl czarny to masz pixel z obwodu. Jesli natomiast aktualny jest bialy a nastepny czarny to tez masz pixel z obwodu. Dla kazdego pixela warto sprawdzic wszystkich sasiadow w ten sposob.

Offline Xion

  • Redaktor
    • xion.log

# Luty 01, 2008, 00:02:18
Za bardzo optymalnie to się chyba nie da, ale można tak jak, proponuje Khaine. Czyli szukamy pierwszego białego piksela, a następnie rekurencyjnie przeglądamy sąsiadujące do niego, aż napotkamy na granicę czarny-biały. Oczywiście każdy przeglądnięty piksel należy odpowiednio oznaczyć, żeby przypadkiem nie rozpatrywać jednej "plamy" dwa razy.

Offline Knopi

  • Użytkownik

# Luty 01, 2008, 00:11:13
Chyba bardziej optymalnie to jest jechać po obwodzie - czyli wzdłuż granicy czarny-biały. Dla małych plam to to jest rybka ale dla dużych różnica jest wymierna.... plama 1000x1000 to nie przejrzenie 1000000 tylko 4000 pikseli. Tylko warunkiem jest to, żeby w plamie nie było dziur...

No i czy masz jakieś konkretne limity pamięci wyznaczone ?

Offline shyha

  • Użytkownik
    • Shyha@Flickr

# Luty 01, 2008, 00:27:36
Czy wyście poszaleli? Ta metoda Khaine'a to jakaś partyzantka :) Jeśli to jest czarno-białe to pół problemu, filtr wysokiej częstotliwości i jazda :) jeśli coś tam jeszcze jest to wyznaczyć jakoś obszary zainteresowania, filtr i jazda.
Pozatym to śmierdzi programem na zaliczenie...

Offline Knopi

  • Użytkownik

# Luty 01, 2008, 00:32:59
Przede wszystkim chciałbym dostać treść zadania a nie dywagować co to jest.... Limity czasu i pamięci, dostępne biblioteki, specyfikacje wejścia itp.

Offline Khaine

  • Użytkownik

# Luty 01, 2008, 00:41:18
ja to takiego brute force zasadzilem, czyli to co mi pierwsze do glowy przyszlo :D Rzecz jasna to trzeba ostro zoptymalizowac, zeby nazwac dobrym algorytmem. Mozna tez zastosowac filtry. Jesli mamy uzywac tylko 2 kolorow to sprawe bardzo ulatwia.

Jechanie po obwodzie nie jest do konca dobre. A co jesli te placki sie stykaja krawedziami pixeli (clipping)? Wtedy jest szansa, ze algorytm zacznie jechac po obwodzie innego placka :P Przedstawiona przeze mnie metoda tez tak powinna zadzialac :D

Offline Knopi

  • Użytkownik

# Luty 01, 2008, 00:43:59
No jeżeli się stykają krawędziami pikseli to to oznacza że to jest jedna plama, co nie ?

Offline Liosan

  • Redaktor

# Luty 01, 2008, 00:53:14
zamiatanie? drzewa przedziałowe? Pole da się w ten sposób policzyć chyba w O(n log n) od ilosci pikseli, a obwód pewnie podobnie tylko trzeba będzie trzymać więcej danych w drzewie.

W ogóle to "moim zadaniem jest" jest co najmniej podejrzane... sposób sformułowania posta prawie sugeruje, że to jest Twoje zadanie (np. na zaliczenie) a nie nasze :P

EDIT: Shyha: czy mógłbyś rozwinąć pomysł?

EDIT2: to O(nlogn) jest dla wersji z dziurami, jeśli nie ma dziur to raczej da szybciej... O(łączny obwód * log(ilość plam))? strzelam, mało istotne :P

Jeśli chodzi o szukanie dziur w plamach, to nasuwają mi się na myśl metody probabilistyczne - atakowanie paradoksem dnia urodzin da w miarę poprawny wynik :)

Liosan
« Ostatnia zmiana: Luty 01, 2008, 00:57:41 wysłana przez Liosan »

Offline Xion

  • Redaktor
    • xion.log

# Luty 01, 2008, 00:54:35
Mogą się stykać rogami, a jeśli się przyjmie sąsiedztwo tylko w pionie i poziomie, to wtedy będą to dwie plamy.

shyha: Ale filtr tak czy siak wymaga przejechania po całym obrazku i wykonania podobnej ilości obliczeń, a i wynikową bitmapę pewnie trzeba będzie przejrzeć, żeby uzyskać dane w odpowiednim formacie. Swoją drogą warto by te pożądane struktury danych znać i generalnie mieć jakieś bliższe informacje o problemie, bo póki co to dywagujemy sobie tylko.