Liczenie klastrów obrazka czarno-białego.

Witam! Mam następujący problem programistyczno-algorytmiczny. Otóż do wykonania mam funkcję, która dla danego obrazka czarno-białego (przyjmujemy więc tablicę bitową; 1-kolor czarny, 0-kolor biały) wyliczy mi ilość klastrów poszczególnej wielkości. Klaster definiujemy jako ilość znajdujących się obok siebie pixeli (jedynek dla naszej tablicy).
Na poniższym obrazku zaprezentuję o co chodzi.

Nasza funkcja powinna wypisać:
Klastrow rozmiaru 1: 1
Klastrow rozmiaru 2: 2
Klastrow rozmiaru 4: 2
Klastrow rozmiaru 7: 1

Największy problem w tym, aby używać w tej funkcji operacji bitowych i działań na bardziej zaawansowanych strukturach w celu zoptymalizowania działania funkcji dla dużych tablic.

Jako argument funkcji mamy wskaźnik na tablicę zero-jedynkową oraz rozmiar wymiary tablicy m,n.

Może ktoś spotkał się już z podobnym problemem i pomoże.

No ale konkretnie z czym masz problem? Mamy ci wymyślić cały algorytm i implementację (wtedy powinieneś przesunąć obszar swoich zainteresowań w kierunku działu 'praca') czy sprawiają ci kłopot szczegóły?
Jeśli chodzi o

Największy problem w tym, aby używać w tej funkcji operacji bitowych i działań na bardziej zaawansowanych strukturach w celu zoptymalizowania działania funkcji dla dużych tablic.
to w czym problem? Skoro piksele to pojedyncze bity to do ich porównywania możesz użyć xor'a (daje 0 dla równych i 1 jeden dla nierównych), ew. and jeśli chcesz sprawdzić czy dwa dane piksele mają wartość 1/true ;)

Czy ja piszę, żeby mi ktoś pisał od początku? Piszę, że może ktoś już takie coś zrobił - to ewentualnie mógłby się podzielić kodem albo metodą (algorytmem)?

Algorytm może być taki:
przeszukujesz tablicę wiersz po wierszu, jak natrafisz na jedynkę, to uruchamiasz algorytm rekurencyjny, który sprawdza wszystkie sąsiadujące pola dopóki będą tam jedynki, no i oczywiście je zlicza. Po zliczeniu powinien też przestawić jedynkę na 0. Jak już zliczy, to szukasz dalej jedynek linia po linii od miejsca w którym skończyłeś. Na koniec jeszcze trzeba by wypisać wyniki, to ważne jest...

drobna watpliwosc:
"Największy problem w tym, aby używać w tej funkcji operacji bitowych" - skoro dostajesz na wejsciu 'prostokatna' tablice bajtow, kazdy z nich to zero albo jeden, to jak tu wcisnac bitowe.. musialbys to najpierw sobie 'upchnac'

chodnik - rekurencja moze byc calkiem ciezko, poniewaz musisz zapewnic aby podwywolania przypadkiem nie wieszly na swoje obszary i nie zliczyly tego samego pola n-krotnie, chyba ze sie wpadnie np. na pomysl wytyczenia 'stron swiata' i odpalaniu podwywolania z nakazem iscia tylko w dana strone. innym sposobem moze byc np. lekko zmodyfikowany algorytm dijkstry, ten z numerowaniem wezlow na trasie - tutaj chodzilo by sie po czarnym jak sie tylko na jakis by trafilo. Acz - jego najprostsza implementacja wymagalaby drugiej, identycznej tablicy do trzymania numerku dla danego pixela. Poza tym sa tez fajne algorytmu np. wyznaczania kontury figury. odpalasz go na obrazku i dostajesz w efekcie liste punktow (tu: pikseli) opisujacych kontur figury. Potem sobie ich pozycje inteligentnie poodejmowac i pododawac i voil'a, mamy powierzchnie. Tutaj haczyk i trudnosc, poza algorytmem konturu, tkwi w slowie 'inteligentnie' :)

Postąpiłbym tak jak proponuje Chodnik, lecz...
Rekurencyjne rozwiązanie bywa tu czasem okropnie nie efektywne.
Popatrz za iteracyjnym FLOODFILL, wystarczy dodać licznik, a liczniki zliczać w tablicy.

floodfill - wlasnie to nazwalem zmodyfikowanym algorytmem dijkstry ze wzgledu na liczniki :)

Nie wiem czy to coś pomoże, ale rzeczywiście wyżej wspomniany algorytm FloodFill działa tu. Nie jest to na bitach ale przerobić zawsze idzie a tablice wyników nożna zoptymalizować, dziś mam leniwy dzień ale jak interesuje cię ta opcja to daj znak, przerobimy na bity i zoptymalizujemy.

#include<conio.h>
#include<stdio.h>

// Rozmiar tablicy
#define SZ_TAB 20
#define WY_TAB 10

// Czarne i biale w tablicy - przykladowe
char tab[WY_TAB][SZ_TAB]=
{{0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1},
 {0,1,0,0,0,1,0,0,0,1,1,0,0,0,1,0,1,0,0},
 {0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,1},
 {0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1},
 {0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,1},
 {0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0,0,0},
 {0,0,1,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0},
 {1,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0},
 {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}};

// Tutaj znajda sie wyniki -  szczyt nieoptymalizacji.. ;)
unsigned int wynik[SZ_TAB*WY_TAB];

// metoda FLOODFILL
int l=0;
int FloodFill (int x,int y)
{
    // sprawdzenie przekroczenia zakresu obszaru
    if (x >= 0 && x <= SZ_TAB && y >= 0 && y <= WY_TAB)
        // sprawdzenie warunku rysowania
        if (tab[y][x]==1)
        {
           // postawienie punktu
           tab[y][x]=0;
           l++;

           // wywolania rekurencyjne
           FloodFill (x,y-1);
           FloodFill (x+1,y);
           FloodFill (x,y+1);
           FloodFill (x-1,y);
           FloodFill (x-1,y-1);
           FloodFill (x-1,y+1);
           FloodFill (x+1,y-1);
           FloodFill (x+1,y+1);
        }
    return l;
}

int main(void)
{
    // Namaluje obrazek...
    for (int y=0;y<WY_TAB;y++)
    {
        for (int x=0;x<SZ_TAB;x++)
        {
            if (tab[y][x]==0) printf("-");
            if (tab[y][x]==1) printf("X");
        }
        printf("\n");
    }
    printf("\n");

    // Powylicza klastry...
    for (int y=0;y<WY_TAB;y++)
        for (int x=0;x<SZ_TAB;x++)
            if (tab[y][x]==1)
            {
                int p=FloodFill(x,y);
                wynik[p]++;
                l=0;
            }

    // Przedstawi wynik
    for (int x=0;x<SZ_TAB*WY_TAB;x++)
        if (wynik[x])
            printf("Klastrow rozmiaru %d:%d\n",x,wynik[x]);

    getch();
}

quetzalcoatl napisał(a)

drobna watpliwosc:
"Największy problem w tym, aby używać w tej funkcji operacji bitowych" - skoro dostajesz na wejsciu 'prostokatna' tablice bajtow, kazdy z nich to zero albo jeden, to jak tu wcisnac bitowe.. musialbys to najpierw sobie 'upchnac'

Na całej tablicy na raz? No może też jakoś by się udało, ale lepiej po jednym (jak pisałem xor, ew. and do porównywania) ew. jak juz grupować to raczej max w bajty ;) Przy choćby i shortach już by rozdzielczość była raczej kiepska ;) Chociaż sam nie wiem, czy jest sens się w to bawić skoro możliwe, że dobry kompilator sam to wychwyci ;)

@up -> jak c++ to nie lepiej vector<bool> (ew. bitset jak stały rozmiar tablicy) zamiast tablicy charów? Zawsze lepiej te bity upakuje ;)

Tylko kosmetyka

for (int y=1; y<WY_TAB-1; y++)
        for (int x=1; x<SZ_TAB-1; x++)
            if (..........

albo może lepiej

    if (x >= 0 && x <= SZ_TAB /***** && y >= 0 *******/ && y <= WY_TAB)
           .....
           //FloodFill (x,y-1);
           FloodFill (x+1,y);
           FloodFill (x,y+1);
           FloodFill (x-1,y);
           //FloodFill (x-1,y-1);
           FloodFill (x-1,y+1);
           //FloodFill (x+1,y-1);
           FloodFill (x+1,y+1);

Tak czy siak, rekurencyjnie nie jest dobrze, stos obrzydliwie rośnie.
Jak pamiętam iteracyjnie z kolejką jest tylko szczyptę bardziej skomplikowane.

JeanQ napisał(a)

Nie jest to na bitach ale przerobić zawsze idzie a tablice wyników nożna zoptymalizować, dziś mam leniwy dzień ale jak interesuje cię ta opcja to daj znak, przerobimy na bity i zoptymalizujemy.

Nad tym to już ja się zastanowię.

Dzięki za pomoc, jednak bardziej potrzebuję metody iteracyjnej.

albo może lepiej
    if (x >= 0 && x <= SZ_TAB /***** && y >= 0 *******/ && y <= WY_TAB)
           .....
           //FloodFill (x,y-1);
           FloodFill (x+1,y);
           FloodFill (x,y+1);
           FloodFill (x-1,y);
           //FloodFill (x-1,y-1);
           FloodFill (x-1,y+1);
           //FloodFill (x+1,y-1);
           FloodFill (x+1,y+1);

Może jednak lepiej NIE bo jak algorytm znajdzie np... taki kształt:

11000000000
01100000000
00110000100
00011000100
00001100100
00000111100

... to bedzie lipa.

Będzie lipa

Ghostek napisał(a)

quetzalcoatl napisał(a)

drobna watpliwosc:
"Największy problem w tym, aby używać w tej funkcji operacji bitowych" - skoro dostajesz na wejsciu 'prostokatna' tablice bajtow, kazdy z nich to zero albo jeden, to jak tu wcisnac bitowe.. musialbys to najpierw sobie 'upchnac'

Na całej tablicy na raz? No może też jakoś by się udało, ale lepiej po jednym (jak pisałem xor, ew. and do porównywania) ew. jak juz grupować to raczej max w bajty ;) Przy choćby i shortach już by rozdzielczość była raczej kiepska ;) Chociaż sam nie wiem, czy jest sens się w to bawić skoro możliwe, że dobry kompilator sam to wychwyci ;)

@up -> jak c++ to nie lepiej vector<bool> (ew. bitset jak stały rozmiar tablicy) zamiast tablicy charów? Zawsze lepiej te bity upakuje ;)

chodzilo mi o sprasowanie kolejnych 32 charow z wiersza do jednego uint32. and'ujac z przesuneiciem mozna w miare sensownie i szybko sprawdzic 31 pol w jednym kierunku w dwoch operacjach -- ale dowiesz sie tylko ze 'sa takie jakeis obok siebie', sprawdzenie ktore to dokladnie kosztuje wiecej. sprawdzenie skrajny -a -pierszy nastepneog jeszcze gorzej.. ale jakby to dobrze napisac to moze by cos wyszlo. z vector - moze, ale tez bym sie sklanial ku bitset