Szkieletyzacja - wydobycie szkieletu obiektu na zbinaryzowanym obrazie. Poniżej przedstawiam trzy metody, od najprostrzej do najbardziej skutecznej.

Szkieletyzacja przez maskę

Potrzebna maska:

 x   0   x 
 x   1   x 
 1   1   1 


1 oznacza czarny piksel, 0 oznacza biały piksel, to co stoi na miejscu x jest nieistotne.
W celu poprawnego działania algorytmu należy obramować oryginalny obraz ramką o grubości 1 px złożoną z białych pikseli.

Przebieg algorytmu:

  • Każdy czarny piksel (wartość 1) oryginalnego obrazka przyrównujemy do maski oraz jej obrotów o 90, 180 i 270 stopni.
  • Jeśli otoczenie piksela spełni którąś z masek, do kopii wstawiana jest wartość 0 (biały), jeśli zaś otoczenie piksela nie spełni żadnej z masek, wstawiamy do kopii wartość 1 (czarny)
  • Zastępujemy oryginał kopią.
  • Czynność powtarzamy tak długo, jak długo w obrazie zachodzą zmiany.

Szkieletyzacja algorytmem KMM

Potrzebne maski:

  • czwórki = {3, 6, 7, 12, 14, 15, 24, 28, 30, 48, 56, 60, 96, 112, 120, 129, 131, 135, 192, 193, 195, 224, 225, 240}
  • wycięcia = {3, 5, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28, 29, 30, 31, 48, 52, 53, 54, 55, 56, 60, 61, 62, 63, 65, 67, 69, 71, 77, 79, 80, 81, 83, 84, 85, 86, 87, 88, 89, 91, 92, 93, 94, 95, 97, 99, 101, 103, 109, 111, 112, 113, 115, 116, 117, 118, 119, 120, 121, 123, 124, 125, 126, 127, 131, 133, 135, 141, 143, 149, 151, 157, 159, 181, 183, 189, 191, 192, 193, 195, 197, 199, 205, 207, 208, 209, 211, 212, 213, 214, 215, 216, 217, 219, 220, 221, 222, 223, 224, 225, 227, 229, 231, 237, 239, 240, 241, 243, 244, 245, 246, 247, 248, 249, 251, 252, 253, 254, 255}
  • sprawdzarka = {{128, 64, 32}, {1, 0, 16}, {2, 4, 8}}

Maskę sprawdzarka zakłada się na zasadzie sumy wartości. Na początku analizy waga piksela środkowego maski wynosi 0. Jeżeli danej komórce maski odpowiada piksel o wartości 1, 2, 3 lub 4, to do wagi piksela środkowego dodaje się wagę analizowanej komórki (nie jest ona wymnażana razy wartość piksela). W celu poprawnego działania algorytmu należy obramować oryginalny obraz ramką o grubości 1 px złożoną z białych pikseli.

Przebieg algorytmu:

  • Wszystkie czarne piksele oznaczamy jako 1, zaś białe jako 0.
  • Piksele 1, które posiadają sąsiadów o oznaczeniu 0 po bokach, u góry lub u dołu, oznaczamy jako 2.
  • Pozostałe piksele 1, które posiadają sąsiadów o oznaczeniu 0 na rogach, oznaczamy jako 3.
  • Dla pikseli oznaczonych jako 2 za pomocą maski sprawdzarka obliczamy ich wagę. Jeśli waga znajduje się na liście czwórki oznaczenie piksela zamieniamy z 2 na 4.
  • Dla wszystkich pikseli oznaczonych jako 4 wyliczamy wagę za pomocą maski sprawdzarka. Jeśli waga znajduje się na liście wycięcia, zamieniamy piksel na 0, zaś w przeciwnym razie zamieniamy go na 1.
  • Dla wszystkich pikseli oznaczonych jako 2 wyliczamy wagę za pomocą maski sprawdzarka. Jeśli waga znajduje się na liście wycięcia, zamieniamy piksel na 0, zaś w przeciwnym razie zamieniamy go na 1.
  • Dla wszystkich pikseli oznaczonych jako 3 wyliczamy wagę za pomocą maski sprawdzarka. Jeśli waga znajduje się na liście wycięcia, zamieniamy piksel na 0, zaś w przeciwnym razie zamieniamy go na 1.
  • Procedurę powtarzamy dopóki w jej trakcie na obrazie zachodzą zmiany.

Szkieletyzacja algorytmem K3M

Potrzebne maski:

  • Jest to tablica kolejnych masek, w opisie algorytmu kolejne wiersze tablicy będą oznaczane od A0 do A5.
    private static final int [][] A = {
    {3, 6, 7, 12, 14, 15, 24, 28, 30, 31, 48, 56, 60, 62, 63, 96, 112, 120, 124, 126, 127, 129, 131, 135,143, 159, 191, 192, 193, 195, 199, 207, 223, 224, 225, 227, 231, 239, 240, 241, 243, 247, 248, 249, 251, 252, 253, 254},
    {7, 14, 28, 56, 112, 131, 193, 224},
    {7, 14, 15, 28, 30, 56, 60, 112, 120, 131, 135, 193, 195, 224, 225, 240},
    {7, 14, 15, 28, 30, 31, 56, 60, 62, 112, 120, 124, 131, 135, 143, 193, 195, 199, 224, 225, 227, 240, 241, 248},
    {7, 14, 15, 28, 30, 31, 56, 60, 62, 63, 112, 120, 124, 126, 131, 135, 143, 159, 193, 195, 199, 207, 224, 225, 227, 231, 240, 241, 243, 248, 249, 252},
    {7, 14, 15, 28, 30, 31, 56, 60, 62, 63, 112, 120, 124, 126, 131, 135, 143, 159, 191, 193, 195, 199, 207, 224, 225, 227, 231, 239, 240, 241, 243, 248, 249, 251, 252, 254}
    };
  • Maska jest używana na końcu do likwidacji nadmiarowych sąsiadów.
    private static final int [] A1pix = {3, 6, 7, 12, 14, 15, 24, 28, 30, 31, 48, 56, 60, 62, 63, 96, 112, 120, 124, 126, 127, 129, 131, 135, 143, 159, 191, 192, 193, 195, 199, 207, 223, 224, 225, 227, 231, 239, 240, 241, 243, 247, 248, 249, 251, 252, 253, 254};
  • Maska jest używana do wyliczania wagi piksela w celu porównywania jej z wagami z tablic A oraz A1pix. Wagę wylicza się sumując wartości maski dla czarnych lub czerwonych sąsiadów piksela.
    private static int [][] maska = {{128, 64, 32}, {1, 0, 16}, {2, 4, 8}};

Przebieg algorytmu:

  • Wszystkie czarne piksele, które spełniają maskę A0 są oznaczane jako graniczne (na przykład na czerwono).
  • Wszystkie piksele graniczne, których waga jest w tablicy A1 są usuwane.
  • Wszystkie piksele graniczne, których waga jest w tablicy A2 są usuwane.
  • Wszystkie piksele graniczne, których waga jest w tablicy A3 są usuwane.
  • Wszystkie piksele graniczne, których waga jest w tablicy A4 są usuwane.
  • Wszystkie piksele graniczne, których waga jest w tablicy A5 są usuwane.
  • Pozostałe piksele graniczne są z powrotem zamieniane na czarne.
  • Jeśli podczas powyższych faz na obrazie zaszły zmiany - następuje powrót do fazy szukania granic.
  • W przeciwnym razie obraz przeszukiwany jest ostatni raz, tym razem usuwane są czarne piksele, których waga pasuje do maski A1pix.

Przykład porównania metod

U góry znajdują się obrazy oryginalne, dalej ścienione przez maskę, pod nimi ścienione KMM, a na dole ścienione K3M.

Currently unrated
  • Share