[Khaine]

#programowanie #przetwarzanieobrazu

Znacie może jakiś prosty i szybki algorytm wypełniania kolorem? Flood fill kategorycznie odpada, bo przy danym obszarze wypełnienia wypierdzieli stos zanim zdążymy mrugnąć. Musi być względnie oszczędny pamięciowo. We internetach jest trochę różnych algorytmów, ale większość właśnie podaje flood filla lub inne rekurencyjne, które po prostu nie mają prawa tutaj zadziałać. Ogółem dochodzi jeszcze jeden problem, bo ten algorytm to nie jest zwykłe wypełnianie kolorem, tylko ma docelowo służyć do segmentacji obrazu (czyli będzie kolejno wykrywał poszczególne obiekty i kolorował je na różne odcienie szarości wg. zadanego klucza). Dlatego tak de facto musi pamiętać co już załatwił, żeby zostało to wszystko posegmentowane w odpowiedni sposób i we względnie optymalny sposób (nie lubię marnować zasobów bez sensu).

Myślałem o zastosowaniu wektora, gdzie odkładalibyśmy sobie sąsiednie niepokolorowane piksele, które algorytm będzie potem po kolei sprawdzał. Eliminujemy w ten sposób rekurencję, ponadto wyczerpanie wszystkich pikseli z wektora oznacza zakończenie kolorowania danego obiektu i dodanie np +0.1 do intensywności przy napotkaniu następnego. Oprócz tego można utworzyć drugi wektor z pikselami już pokolorowanymi, żeby w trakcie fora sprawdzającego czy byliśmy w tym miejscu po prostu pomijał ten obszar (pętla w pętli, for leci sobie po pikselach do momentu napotkania choćby jednego piksela obrazu, wtedy wpada w while który wypełnia obiekt, po czym wraca do fora i szuka dalej aż się nie skończy obraz).

Nie wiem na ile to jest optymalne, ale przynajmniej stosu nie #!$%@?. Chyba, że są na to lepsze metody?

[ghostface]

@Khaine: czytałeś http://en.wikipedia.org/wiki/Flood_fill#Alternative_implementations ?

[Khaine]

@ghostface: Ten pierwszy alternatywny flood fill to jest generalnie to samo o czym pomyślałem. Czyli chyba lepszej metody nie będzie.

[jooj]

@Khaine: http://en.wikipedia.org/wiki/Connected-component_labeling

Jakiś czas temu używałem tego. Efektywniejszy od flood-filla ale w implementacji ciut trudniejszy.

[Khaine]

@jooj: Heh, na bazie przeszukiwania grafu. Pomyśleć, że na dyskretnej człowiek nie przywiązywał do tego jakiejś specjalnej wagi. Ale też podobny do tego alternatywnego flood filla.