Jak mogę znaleźć punkty końcowe szkieletu obrazu binarnego w OpenCV?

Question

mam szkielet w pikselach binarnych, takich jak to:

Chcę znaleźć współrzędne punktów końcowych tego szkieletu (w tym przypadku istnieją cztery), przy użyciu Open CV if odpowiedni.

Wydajność jest ważna, ponieważ analizuję kilka z nich w czasie rzeczywistym z kanału wideo i muszę wykonywać wiele innych czynności jednocześnie.

(Uwaga, przeprosiny, że zrzut ekranu powyżej ma rozmiaru artefaktów, ale jest to 8-połączone szkielet pracuję z.)

Answer 1

Biorąc tagów swoich pytań i odpowiedzi w swoim profilu, jadę zakładając, że chcesz implementację C++. Kiedy szkieletujesz obiekt, obiekt powinien mieć grubość 1 piksela. Dlatego jedną rzeczą, którą mogę zasugerować, jest znalezienie pikseli niezerowych na obrazie, a następnie przeszukanie w 8-podłączonym sąsiedztwie otaczającym ten piksel i zliczenie pikseli niezerowych. Jeśli liczba wynosi tylko 2, oznacza to, że jest kandydatem na szkieletowy punkt końcowy. Zauważ, że zamierzam też zignorować granicę, abyśmy nie wyszli poza granice. Jeśli liczba wynosi 1, jest to hałaśliwy, izolowany piksel, więc powinniśmy go zignorować. Jeśli jest to 3 lub więcej, oznacza to, że badasz część szkieletu w jednym punkcie szkieletu lub jesteś w punkcie, w którym wiele linii jest połączonych ze sobą, więc nie powinien to być również punkt końcowy.

Szczerze nie mogę wymyślić żadnego algorytmu innego niż sprawdzanie wszystkich szkieletu pikseli dla tych kryteriów .... więc złożoność będzie O(mn), gdzie m i n są wiersze i kolumny obrazu. Dla każdego piksela na obrazie, 8-piksele sprawdzanie sąsiedztwa zajmuje stały czas i będzie to takie samo dla wszystkich szkieletowych pikseli, które sprawdzasz. Jednak z pewnością będzie to podliniowe, ponieważ większość twoich pikseli będzie miała 0 na obrazie, więc sprawdzanie sąsiedztwa o wielkości 8 pikseli nie będzie dokonywane przez większość czasu.

Jako taka, jest to coś, co chciałbym spróbować, przy założeniu, że obraz jest przechowywany w cv::Mat struktury zwane im, przy czym jeden kanał (skala szarości) obraz, a jest typu uchar. Zamierzam również zapisać współrzędne punktów, w których szkieletowe punkty końcowe są typu std::vector. Za każdym razem, gdy wykryjemy punkt szkieletu, dodamy dwie liczby całkowite do wektora naraz - wiersz i kolumnę, w której wykrywamy końcowy punkt szkieletu.

// Declare variable to count neighbourhood pixels 
int count; 

// To store a pixel intensity 
uchar pix; 

// To store the ending co-ordinates 
std::vector<int> coords; 

// For each pixel in our image... 
for (int i = 1; i < im.rows-1; i++) { 
    for (int j = 1; j < im.cols-1; j++) { 

     // See what the pixel is at this location 
     pix = im.at<uchar>(i,j); 

     // If not a skeleton point, skip 
     if (pix == 0) 
      continue; 

     // Reset counter 
     count = 0;  

     // For each pixel in the neighbourhood 
     // centered at this skeleton location... 
     for (int y = -1; y <= 1; y++) { 
      for (int x = -1; x <= 1; x++) { 

       // Get the pixel in the neighbourhood 
       pix = im.at<uchar>(i+y,j+x); 

       // Count if non-zero 
       if (pix != 0) 
        count++; 
      } 
     } 

     // If count is exactly 2, add co-ordinates to vector 
     if (count == 2) { 
      coords.push_back(i); 
      coords.push_back(j); 
     } 
    } 
} 

Jeśli chcesz wyświetlić współrzędne kiedy skończysz, wystarczy sprawdzić każdą parę elementów w tym wektorze:

for (int i = 0; i < coords.size()/2; i++) 
    cout << "(" << coords.at(2*i) << "," coords.at(2*i+1) << ")\n"; 

---

Aby być kompletne, oto implementacja Pythona także. Używam niektórych funkcji numpy, aby ułatwić to sobie. Zakładając, że twój obraz jest przechowywany w img, który jest również obrazem w skali szarości, i importuje bibliotekę OpenCV i numpy (tj.import cv2, import numpy as np), jest to odpowiednik kod:

# Find row and column locations that are non-zero 
(rows,cols) = np.nonzero(img) 

# Initialize empty list of co-ordinates 
skel_coords = [] 

# For each non-zero pixel... 
for (r,c) in zip(rows,cols): 

    # Extract an 8-connected neighbourhood 
    (col_neigh,row_neigh) = np.meshgrid(np.array([c-1,c,c+1]), np.array([r-1,r,r+1])) 

    # Cast to int to index into image 
    col_neigh = col_neigh.astype('int') 
    row_neigh = row_neigh.astype('int') 

    # Convert into a single 1D array and check for non-zero locations 
    pix_neighbourhood = img[row_neigh,col_neigh].ravel() != 0 

    # If the number of non-zero locations equals 2, add this to 
    # our list of co-ordinates 
    if np.sum(pix_neighbourhood) == 2: 
     skel_coords.append((r,c)) 

Aby wyświetlić współrzędne punktów końcowych, można zrobić:

print "".join(["(" + str(r) + "," + str(c) + ")\n" for (r,c) in skel_coords]) 

---

Minor uwaga: Ten kod jest niesprawdzony. Nie mam zainstalowanego C++ OpenCV na tym komputerze, więc mam nadzieję, że to, co napisałem, zadziała. Jeśli się nie skompiluje, z pewnością możesz przetłumaczyć to, co zrobiłem, na właściwą składnię. Powodzenia!

Answer 2

Trochę za późno, ale to może być przydatne dla ludzi!

Istnieje sposób robienia tego samego, co sugeruje @rayryeng, ale z wbudowanymi funkcjami openCV! To sprawia, że ​​jest znacznie mniejszy i prawdopodobnie szybszy (zwłaszcza w Pythonie, jeśli używasz go, tak jak ja!) To jest to samo rozwiązanie, co this one.

Zasadniczo to, co próbujemy znaleźć, to piksele, które są niezerowe, z jednym niezerowym sąsiadem. W tym celu używamy wbudowanej funkcji filter2D openCV, aby przekonwertować obraz szkieletu za pomocą niestandardowego jądra, które tworzymy. Właśnie dowiedziałem się o splotach i jądrach, a this page jest naprawdę pomocny w wyjaśnieniu, co te słowa znaczą.

A więc, jakie jądro będzie działać? Jak o

[[1, 1,1], 
[1,10,1], 
[1, 1,1]]? 

Następnie, po zastosowaniu tego jądra, każdy piksel o wartości 11 jest jednym, który chcemy!

Oto co mogę użyć:

def skeleton_endpoints(skel): 
    # make out input nice, possibly necessary 
    skel = skel.copy() 
    skel[skel!=0] = 1 
    skel = np.uint8(skel) 

    # apply the convolution 
    kernel = np.uint8([[1, 1, 1], 
         [1, 10, 1], 
         [1, 1, 1]]) 
    src_depth = -1 
    filtered = cv2.filter2D(skel,src_depth,kernel) 

    # now look through to find the value of 11 
    # this returns a mask of the endpoints, but if you just want the coordinates, you could simply return np.where(filtered==11) 
    out = np.zeros_like(skel) 
    out[np.where(filtered==11)] = 1 
    return out 

Nadzieja to pomaga!