Algorytm do rysowania konturu lub obrysu wokół dowolnego przezroczystego obrazu alfa

Question

Nie jestem pewien, czy istnieje jakaś nazwa tego algorytmu, który obecnie rozwijam - "rosnący algorytm sąsiedztwa" brzmi jak odpowiednia nazwa. Więc o co mi chodzi?

Chciałbym narysować obrys wokół przezroczystego obrazu alfa, aby go zarysować. Rozmiar skoku powinien być definiowany przez użytkownika.

Mam tablicę, która jest wypełniona zerami i jedynymi, rozważ każdy element tablicy jako komórkę jak w Game of Life. Element z 0 jest pusty (przezroczysty piksel), element z 1 jest komórką pierwszej generacji (nieprzezroczysty piksel), liczba pokoleń jest określona przez rozmiar otaczającego obrysu.

Ten przykład przedstawia prostokąt otoczony wartości alpha:

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 1 0 0 0 
0 0 0 1 1 1 1 0 0 0 
0 0 0 1 1 1 1 0 0 0 
0 0 0 1 1 1 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 

to chciałbym dać ci rozwijać nową generację otaczając każdą 0 generacji Moore sąsiada. Jest to druga generacja (skok z 1px) - w ten sposób tablica wygląda po wzroście w następujący sposób:

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 2 2 2 2 2 2 0 0 
0 0 2 1 1 1 1 2 0 0 
0 0 2 1 1 1 1 2 0 0 
0 0 2 1 1 1 1 2 0 0 
0 0 2 1 1 1 1 2 0 0 
0 0 2 2 2 2 2 2 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 

3. i 4. generacji (skok z 3PX):

4 4 4 4 4 4 4 4 4 4 
4 3 3 3 3 3 3 3 3 4 
4 3 2 2 2 2 2 2 3 4 
4 3 2 1 1 1 1 2 3 4 
4 3 2 1 1 1 1 2 3 4 
4 3 2 1 1 1 1 2 3 4 
4 3 2 1 1 1 1 2 3 4 
4 3 2 2 2 2 2 2 3 4 
4 3 3 3 3 3 3 3 3 4 
4 4 4 4 4 4 4 4 4 4 

tej pory tak dobrze. Ja osiągnięcie tego prostego zadania przez poniższym fragmencie kodu:

for (int gen = 1; gen <= 4; gen++) 
{ 
    for (int x = 1; x < arrayWidth - 1; x++) 
    { 
     for (int y = 1; y < arrayHeight - 1; y++) 
     { 
      // See if this cell is in the current generation. 
      if (_generation[x + arrayWidth * y] == gen) 
      { 
       // Generate next generation. 
       for (int i = x - 1; i <= x + 1; i++) 
       { 
        for (int j = y - 1; j <= y + 1; j++) 
        { 
         if (_generation[i + arrayWidth * j] == 0 || _generation[i + arrayWidth * j] > gen) 
         { 
          _generation[i + arrayWidth * j] = gen + 1; 
         } 
        } 
       } 
      } 
     } 
    } 
} 

Takie podejście sprawdza się doskonale w przypadku prostych kształtów, takich jak na przykład prostokąta. Ale jak mogę to zrobić dla elipsy? Jak tylko mamy rodzaj wzoru schodów w komórkach, Dostaję wyniki niechlujny:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 1 1 1 0 0 0 0 0 
0 0 0 0 1 1 1 1 1 1 0 0 0 0 
0 0 0 1 1 1 1 1 1 1 1 0 0 0 
0 0 1 1 1 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 1 1 1 0 0 
0 0 0 1 1 1 1 1 1 1 1 0 0 0 
0 0 0 0 1 1 1 1 1 1 0 0 0 0 
0 0 0 0 0 1 1 1 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 2 2 2 2 2 2 0 0 0 0 
0 0 0 2 2 1 1 1 1 2 2 0 0 0 
0 0 2 2 1 1 1 1 1 1 2 2 0 0 
0 2 2 1 1 1 1 1 1 1 1 2 2 0 
0 2 1 1 1 1 1 1 1 1 1 1 2 0 
0 2 1 1 1 1 1 1 1 1 1 1 2 0 
0 2 1 1 1 1 1 1 1 1 1 1 2 0 
0 2 1 1 1 1 1 1 1 1 1 1 2 0 
0 2 1 1 1 1 1 1 1 1 1 1 2 0 
0 2 2 1 1 1 1 1 1 1 1 2 0 0 
0 0 2 2 1 1 1 1 1 1 2 2 0 0 
0 0 0 2 2 1 1 1 1 2 2 0 0 0 
0 0 0 0 2 2 2 2 2 2 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 

0 0 0 3 3 3 3 3 3 3 3 0 0 0 
0 0 3 3 2 2 2 2 2 2 3 3 0 0 
0 3 3 2 2 1 1 1 1 2 2 3 3 0 
3 3 2 2 1 1 1 1 1 1 2 2 3 3 
3 2 2 1 1 1 1 1 1 1 1 2 2 3 
3 2 1 1 1 1 1 1 1 1 1 1 2 3 
3 2 1 1 1 1 1 1 1 1 1 1 2 3 
3 2 1 1 1 1 1 1 1 1 1 1 2 3 
3 2 1 1 1 1 1 1 1 1 1 1 2 3 
3 2 1 1 1 1 1 1 1 1 1 1 2 3 
3 2 2 1 1 1 1 1 1 1 1 2 2 3 
3 3 2 2 1 1 1 1 1 1 2 2 3 3 
0 3 3 2 2 1 1 1 1 2 2 3 3 0 
0 0 3 3 2 2 2 2 2 2 3 3 0 0 
0 0 0 3 3 3 3 3 3 3 3 0 0 0 

Przy stosowaniu tego algorytmu do elipsy, zarys wygląda trochę dziwnie, bo od tego problemu (po lewej: wynik algorytm , po prawej: o wynik):

problem polega na tym, że nie chcę mieć te 2 2 i 3 3 zduplikowane bloki, które występują za każdym razem mam ten "schodek" wzór:

1 0 0 0 0 0 0 1 
0 1 0 0 0 0 1 0 
0 0 1 0 0 1 0 0 
0 0 0 1 1 0 0 0 

Chcę powyższe obliczenia 2nd i 3rd Generation wyglądać następująco:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 2 2 2 2 0 0 0 0 0 
0 0 0 0 2 1 1 1 1 2 0 0 0 0 
0 0 0 2 1 1 1 1 1 1 2 0 0 0 
0 0 2 1 1 1 1 1 1 1 1 2 0 0 
0 2 1 1 1 1 1 1 1 1 1 1 2 0 
0 2 1 1 1 1 1 1 1 1 1 1 2 0 
0 2 1 1 1 1 1 1 1 1 1 1 2 0 
0 2 1 1 1 1 1 1 1 1 1 1 2 0 
0 2 1 1 1 1 1 1 1 1 1 1 2 0 
0 0 2 1 1 1 1 1 1 1 1 2 0 0 
0 0 0 2 1 1 1 1 1 1 2 0 0 0 
0 0 0 0 2 1 1 1 1 2 0 0 0 0 
0 0 0 0 0 2 2 2 2 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 3 3 3 3 0 0 0 0 0 
0 0 0 0 3 2 2 2 2 2 3 0 0 0 
0 0 0 3 2 1 1 1 1 2 3 0 0 0 
0 0 3 2 1 1 1 1 1 1 2 3 0 0 
0 3 2 1 1 1 1 1 1 1 1 2 3 0 
3 2 1 1 1 1 1 1 1 1 1 1 2 3 
3 2 1 1 1 1 1 1 1 1 1 1 2 3 
3 2 1 1 1 1 1 1 1 1 1 1 2 3 
3 2 1 1 1 1 1 1 1 1 1 1 2 3 
3 2 1 1 1 1 1 1 1 1 1 1 2 3 
0 3 2 1 1 1 1 1 1 1 1 2 3 0 
0 0 3 2 1 1 1 1 1 1 2 3 0 0 
0 0 0 3 2 1 1 1 1 2 3 0 0 0 
0 0 0 3 2 2 2 2 2 2 3 0 0 0 
0 0 0 0 3 3 3 3 3 3 0 0 0 0 

Próbowałem wielu metod, aby odfiltrować te powtarzające się bloki komórkowe, ale nie mogę znaleźć łatwy i ogólne rozwiązanie dla rozwiązywania problem.

Jakieś pomysły na to, jak uzyskać obrys/kontur jak w Photoshopie lub Paint.NET?

Dzięki!

Cheers P

Answer 1

Właściwa nazwa to dilation, sprawdź operacji morfologicznych. Powinieneś spróbować rozszerzenia z elementem koła, to da ci żądany wynik.

Oto kod Matlab, który pokazuje jak to się robi:

im = imcircle(70); 
im = padarray(im,[20,20]); 
figure;imshow(im); 
im2 = imdilate(im,strel('disk',8)); 
figure;imshow(im2);