Kontury

Dzisiaj trochę o konturach. Są one reprezentowane w OpenCV przez strukturę CvSeq (dokładnie taką samą, jak ta, która pojawiła się przy detekcji twarzy). Dzięki konturom możemy w prosty sposób klasyfikować zawartość obrazu. Klasyfikować możemy proste kształty, np. figury geometryczne. Rozpoznawanie twarzy itp. nie wchodzą w grę, to inna liga :) Niemniej proces ten jest przydatny w rozwiązywaniu wielu problemów. Żeby dalej nie zanudzać, poniżej kod prostej funkcji wyszukującej konturu:

CvSeq * znajdz_kontury(char* sciezka)
{
// czytamy obraz, jezeli nie istnieje, to zwracamy NULL
IplImage * obraz = cvLoadImage(sciezka, CV_LOAD_IMAGE_GRAYSCALE);
if (obraz == NULL)
return NULL;

// nasz kontur
CvSeq * kontur;
// pamiec na obliczenia
CvMemStorage * mem = cvCreateMemStorage(0);
// operacja progrowania
cvThreshold(obraz, obraz, 100, 255, CV_THRESH_BINARY_INV);
// szukanie konturow
cvFindContours(obraz, mem, &kontur);
// aproksymacja konturow
kontur = cvApproxPoly(kontur, sizeof (CvContour), mem, CV_POLY_APPROX_DP, cvContourPerimeter(kontur) * 0.035);
// sprzatanie
cvReleaseImage(&obraz);
// powinnio sie jeszcze zwolnic memstora ale na potrzeby przykladu tego nie robimy
// (poniewaz zwracamy wskaznik na sekwencje do dalszego uzycia)

return kontur;
}

Jak już wspomniałem, kontur jest strukturą CvSeq. CvMemStorage ma podobne znaczenie jak w notce o detekcji twarzy. Dalej mamy operację progowania.
PROGOWANIE

double cvThreshold(
const CvArr* src, 
CvArr* dst, 
double threshold, 
double max_value, 
int threshold_type)

Jako src i dst można bez problemu podać ten sam obraz. Trzeci parametr mówi o wartości naszego progu. Znaczenie pozostałych dwóch bardzo ładnie (z odpowiednimi przebiegami) wytłumaczono w wiki OpenCV. Do metody możemy dołączyć opcjonalnie zastosowanie algorytmu Otsu, w postaci CV_THRESH_XXX | CV_THRESH_OTSU. W naszym prostym przypadku nic on nie poprawi, ale może być pomocny w złożonych obrazach. Należy pamiętać, że wskazane są obrazy w odcieniach szarości (dla metody Otsu jest to warunek konieczny). Oprócz tej funkcji dostępna jest także inna, cvAdaptiveThreshold:

void cvAdaptiveThreshold(
const CvArr* src, 
CvArr* dst, 
double max_value, 
int adaptive_method=CV_ADAPTIVE_THRESH_MEAN_C, 
int threshold_type=CV_THRESH_BINARY, 
int block_size=3, 
double param1=5)

Pierwsze trzy parametry są identyczne jak w zwykłym cvThreshold. Po znaczenie pozostałych odsyłam ponownie do wiki OpenCV. Ten typ progowania zamiast używać stałego progu dla całego obrazu, oblicza go dynamicznie biorąc pod uwagę otoczenie analizowanego piksela. Dzięki temu wyniki mogą znacząco się poprawić, ale koszt obliczeniowy jest wyższy. Do zapoznania się z zaletami i wadami polecam tę stronę. Oprócz wymienionych metod można zastosować inne, np. detekcję krawędzi cvCanny (jednak nie jest to już progowanie!). Generalnie chcemy mieć w dalszym przetwarzaniu obraz binarny. Jeżeli podamy inny (np. pełny zakres odcieni szarości) to i tak będzie on traktowany jako obraz dwu wartościowy, ale z niekorzystnym progiem 0.
Szukanie konturów odbywa się poprzez funkcję cvFindContours:

int cvFindContours(CvArr* image, 
CvMemStorage* storage, 
CvSeq** first_contour, 
int header_size=sizeof(CvContour), 
int mode=CV_RETR_LIST, 
int method=CV_CHAIN_APPROX_SIMPLE, 
CvPoint offset=cvPoint(0, 0))

Kolejno podajemy obowiązkowo obraz na którym szukamy konturów i referencję do wskaźnika na pierwszy kontur. Na razie tyle wystarczy. Kolejną ważną operacją jest aproksymacja konturu. Uzyskujemy ją za pomocą funkcji cvApproxPoly:

CvSeq* cvApproxPoly(
const void* src_seq, 
int header_size, 
CvMemStorage* storage, 
int method, 
double parameter, 
int parameter2=0)

Co do parametrów to zasadniczo najważniejsze jest to, że jako pierwszy podajemy nasz kontur, kolejne 3 tak jak w przykładowym kodzie, możliwości manewru właściwie brak :) Dociekliwym polecam OpenCV wiki. Warty omówienia jest jeszcze parameter. Jako wartość przekazuję tutaj wynik makra cvContourPerimeter pomnożony przez stałą. cvContourPerimeter zwrwaca długość całego konturu. To tyle z podstaw szukania konturów. Przejdźmy do kolejnego przykładu:

void wyswietl_kontury(char * sciezka)
{
// czytamy obraz, jezeli nie istnieje, to zwracamy NULL
IplImage * obraz = cvLoadImage(sciezka, CV_LOAD_IMAGE_COLOR);
if (obraz == NULL)
return;

// przystowowywanie obrazu
IplImage * do_analizy = cvCreateImage(cvSize(obraz->width, obraz->height), 8, 1);
cvCvtColor(obraz, do_analizy, CV_BGR2GRAY);

// nasz kontur
CvSeq * kontur;
// pamiec na obliczenia
CvMemStorage * mem = cvCreateMemStorage(0);
// operacja progrowania
cvThreshold(do_analizy, do_analizy, 100, 255, CV_THRESH_BINARY_INV);
// szukanie konturow
cvFindContours(do_analizy, mem, &kontur, sizeof (CvContour), CV_RETR_TREE);

for (; kontur != NULL; kontur = kontur->h_next)
{
// aproksymacja konturu
CvSeq* temp_kontur = cvApproxPoly(kontur, sizeof (CvContour), mem, CV_POLY_APPROX_DP, cvContourPerimeter(kontur) * 0.035);
// zaznaczanie konturow na obrazie
cvDrawContours(obraz, temp_kontur, cvScalar(255.0, 0.0, 0.0, 0.0), cvScalar(0.0, 255.0, 0.0, 0.0), 100, 2, CV_AA, cvPoint(0, 0));
}
cvNamedWindow("kontury", CV_WINDOW_AUTOSIZE);
cvShowImage("kontury", obraz);

while (1)
{
int l = cvWaitKey(100);
if (l == 'k')
break;

}
}

Jest on podobny do poprzedniej funkcji. Jedna ze zmian to inny przykład wywołania cvFindContours: CV_RETR_TREE (drzewo) zamiast domyślnego CV_RETR_LIST (listy). Zanim przejdę do dalszego omawiania spójrzmy na obraz, który będziemy dalej analizować

Jak można zauważyć, są na nim dwa rodzaje figur, nazwijmy je głównymi (czarne na białym tle) i wewnętrznymi (tutaj: białe na czarnym tle). Teraz spójrzmy na poniższy schemat

Dzięki opcji drzewa możemy zobaczyć które dokładnie kontury zawierają się wewnątrz innych. Lista pozwala nam za to na łatwiejsze iterowanie po wszystkich konturach, nie zważając na ich wzajemne relacje. h_next to wskaźnik na następny kontur w tej samej płaszczyźnie, a v_next na kontur znajdujący się wewnątrz aktualnie wskazywanego konturu. Stąd taka a nie inna konstrukcja pętli

for (; kontur != NULL; kontur = kontur->h_next)
{
... inny kod...
}

Dzięki niej i wybraniu CV_RETR_TREE przechodzimy tylko po konturach "głównych". Nową funkcją jest cvDrawContours:

void cvDrawContours(
CvArr *img, 
CvSeq* contour, 
CvScalar external_color, 
CvScalar hole_color, 
int max_level, 
int thickness=1, 
int line_type=8)

pierwsze dwa parametry to obraz na którym rysujemy i kontur który zaznaczamy. Dalej mamy dwa kolory, odpowiednio dla aktualnego konturu i dla konturów wewnątrz niego. max_level to poziom do którego mamy zaznaczać wewnętrzne kontury. 0 oznacza brak zaznaczania, 1 zaznaczanie wewnętrznych konturów, 2 zaznaczanie kolejnych poziomów zagłębienia (wewnętrzne dla wewnętrznych) itd. Kolejne parametry są podobne do tych z cvLine (patrz wpis z lutego). W przykładzie wyswietl_kontury(char * sciezka) użyłem poziomu 100 i uzyskano następujący obraz

ustalenie poziomu na 0 spowoduje, że wynik będzie następujący:

DOPASOWYWANIE DO WZORCA
Po tym wszystkim czas na najważniejsze czyli dopasowywanie konturów do wzorców. Proces ten polega na określeniu podobieństwa dwóch konturów i zdecydowaniu który z wzorcowych konturów jest najbardziej "podobny" do analizowanego konturu. Na początek warto dodać, dlaczego aproksymowaliśmy kontury. Otóż, kontury mają różną wielkość i kształty, ponadto są to wartości dyskretne. Spójrzmy na przykład zaznaczenia konturów bez aproksymacji

dla porównania jeszcze raz wersja z aproksymacją

Jak można zauważyć, kontury bez aproksymacji mają na krawędziach "schody". Algorytmy badające podobieństwo opierają się m.in. na długościach krawędzi i kątami między nimi. Poszarpanie krawędzi może wpływać niekorzystnie na wyniki. Warto jeszcze dodać, że należy starannie dobrać parametr aproksymacji. Za mały powoduje wspomniane przed chwilą problemy, z kolei za duży zbytnie uproszczenie konturów

Wracając do tematu dopasowywania :) Za nasze wzorce ustalimy sobie kwadrat

i gwiazdę pięcioramienną

poniżej kod klasyfikujący figury

void okresl_kontury1(char * sciezka, CvSeq * kontur1, CvSeq * kontur2, CvScalar kolor1 = cvScalar(0.0, 255.0, 255.0, 0.0), CvScalar kolor2 = cvScalar(255.0, 0.0, 255.0, 0.0))
{
// czytamy obraz, jezeli nie istnieje, to zwracamy NULL
IplImage * obraz = cvLoadImage(sciezka, CV_LOAD_IMAGE_COLOR);
if (obraz == NULL)
return;

// przystowowywanie obrazu
IplImage * do_analizy = cvCreateImage(cvSize(obraz->width, obraz->height), 8, 1);
cvCvtColor(obraz, do_analizy, CV_BGR2GRAY);

// nasz kontur
CvSeq * kontur;
// pamiec na obliczenia
CvMemStorage * mem = cvCreateMemStorage(0);
// operacja progrowania
cvThreshold(do_analizy, do_analizy, 100, 255, CV_THRESH_BINARY_INV);
// szukanie konturow
cvFindContours(do_analizy, mem, &kontur);

for (; kontur != NULL; kontur = kontur->h_next)
{
CvSeq* temp_kontur = cvApproxPoly(kontur, sizeof (CvContour), mem, CV_POLY_APPROX_DP, cvContourPerimeter(kontur) * 0.035);

// badanie podobieństwa konturow
double match1 = cvMatchShapes(temp_kontur, kontur1, CV_CONTOURS_MATCH_I1);
double match2 = cvMatchShapes(temp_kontur, kontur2, CV_CONTOURS_MATCH_I1);
// im mniejsza wartosc, tym bardziej kontury sa do siebie podobne
if (match1 < match2)
cvDrawContours(obraz, temp_kontur, kolor1, kolor1, 0, 2, CV_AA);
else
cvDrawContours(obraz, temp_kontur, kolor2, kolor2, 0, 2, CV_AA);
}

cvNamedWindow("kontury", CV_WINDOW_AUTOSIZE);
cvShowImage("kontury", obraz);

while (1)
{
int l = cvWaitKey(100);
if (l == 'k')
break;

}
cvDestroyWindow("kontury");
cvReleaseImage(&do_analizy);
cvReleaseImage(&obraz);
cvReleaseMemStorage(&mem);
}

w tym przykładzie mamy jedną nową funkcję - cvMatchShapes

double cvMatchShapes(
const void* object1, 
const void* object2, 
int method, 
double parameter=0)

jako object1 i objet2 przekazujemy porównywane kontury. Jako method możemy podać CV_CONTOURS_MATCH_IX gdzie X to 1,2 lub 3. Dla nas najważniejsze jest, że wyniku działania funkcji, niezależnie od metody, dostajemy liczbę zmiennoprzecinkową. Im jest ona mniejsza tym kontury są bardziej do siebie podobne. Spójrzmy na wynik wywołania funkcji dla naszych przykładowych wzorców Kolorem żółtym zaznaczono bardziej podobne do gwiazdy, różowym do kwadratu. Jak widać, jest prawie idealnie :) prostokąt w lewym górnym rogu przydzielilibyśmy raczej do kwadratu, ale komputer zadecydował inaczej. No nic, próbujemy dalej :)

void okresl_kontury2(char * sciezka, CvSeq * kontur1, CvSeq * kontur2, CvScalar kolor1 = cvScalar(0.0, 255.0, 255.0, 0.0), CvScalar kolor2 = cvScalar(255.0, 0.0, 255.0, 0.0))
{
// czytamy obraz, jezeli nie istnieje, to zwracamy NULL
IplImage * obraz = cvLoadImage(sciezka, CV_LOAD_IMAGE_COLOR);
if (obraz == NULL)
return;

// przystowowywanie obrazu
IplImage * do_analizy = cvCreateImage(cvSize(obraz->width, obraz->height), 8, 1);
cvCvtColor(obraz, do_analizy, CV_BGR2GRAY);

// nasz kontur
CvSeq * kontur;
// pamiec na obliczenia
CvMemStorage * mem = cvCreateMemStorage(0);
// operacja progrowania
cvThreshold(do_analizy, do_analizy, 100, 255, CV_THRESH_BINARY_INV);
// szukanie konturow
cvFindContours(do_analizy, mem, &kontur);

// tworzymy histogramy
int rozmiary[2] = {2,2};
CvHistogram * hist_analiz = cvCreateHist(2, rozmiary, CV_HIST_ARRAY, NULL);
CvHistogram * hist_kontur1 = cvCreateHist(2, rozmiary, CV_HIST_ARRAY, NULL);
CvHistogram * hist_kontur2 = cvCreateHist(2, rozmiary, CV_HIST_ARRAY, NULL);
// obliczamy histogramy geometryczne
cvCalcPGH(kontur1, hist_kontur1);
cvCalcPGH(kontur2, hist_kontur2);



for (; kontur != NULL; kontur = kontur->h_next)
{
CvSeq* temp_kontur = cvApproxPoly(kontur, sizeof (CvContour), mem, CV_POLY_APPROX_DP, cvContourPerimeter(kontur) * war);
cvCalcPGH(temp_kontur, hist_analiz);

cvCompareHist(hist_analiz,hist_kontur1,CV_COMP_CORREL);
// badanie podobieństwa konturow
double match1 = cvCompareHist(hist_analiz,hist_kontur1,CV_COMP_CORREL);
double match2 = cvCompareHist(hist_analiz,hist_kontur2,CV_COMP_CORREL);
// badanie korelacji, jezeli histogramy sa podobne to korelacja jest wieksza (1,0 dla identycznych i -1,0 calkowicie roznych)
if (match1 > match2)
cvDrawContours(obraz, temp_kontur, kolor1, kolor1, 0, 2, CV_AA);
else
cvDrawContours(obraz, temp_kontur, kolor2, kolor2, 0, 2, CV_AA);
}

cvNamedWindow("kontury", CV_WINDOW_AUTOSIZE);
cvShowImage("kontury", obraz);

while (1)
{
int l = cvWaitKey(100);
if (l == 'k')
break;

}
cvDestroyWindow("kontury");
cvReleaseImage(&do_analizy);
cvReleaseImage(&obraz);
cvReleaseMemStorage(&mem);
}

Z rzeczy nowych: na początek tworzymy histogramy (patrz: poprzedni wpis). Rozmiary {2,2} nie są obowiązkowe, pierwszy rozmiar nie musi być równy drugiemu. Najważniejsze, żeby histogram był dwuwymiarowy. Proponuję pozmieniać wartości i sprawdzić jak wpływa to na wyniki (ale nie na przykładzie z tego wpisu, bo jest to bardzo prosty przypadek i nic się nie zmieni), oczywiście nie licząc przypadku gdzie podamy jeden z rozmiarów jako 1, gdyż nie ma on sensu. Kontynuując, kolejną nowością jest cvCalcPGH

void cvCalcPGH(
const CvSeq* contour, 
CvHistogram* hist)

funkcja ta odpowiednio zapełnia histogram danymi. Możemy później porównać te histogramy funkcją cvCompareHist

double cvCompareHist(
const CvHistogram* hist1, 
const CvHistogram* hist2, 
int method)

odnośnie możliwych metod odsyłam do OpenCV wiki. Ja wybrałem tutaj korelację. Ważne jest to, że nie zawsze wynik interpretowany jest tak samo. Np. dla chi-kwadrat kontury identyczne są dla wartości 0.0 a najbardziej odbiegają od siebie przy 2.0. Czas na wynik Jak widać, wyniki można uznać za bardziej satysfakcjonujące :) Nie znaczy to, że poprzednia metoda jest gorsza. Należy popróbować dla danego zestawu danych i wybrać bardziej optymalną (odwieczny problem dokładność/szybkość). To by było na tyle z konturów :) Dla bardziej dociekliwych, chcących się dowiedzieć "jak to działa", polecam zainteresować się takimi rzeczami jak kody łańcuchowe (kody Freemana), momenty geometryczne, momenty Hu, a w przypadku drugiej metody pairwise geometric histograms (stąd skrót PGH).