Algorytm szukania namalowanego regionu na płótnie

Question

Aktualizacja: Próbuję usunąć trochę bałaganu z tego posta i podsumować go w bardziej zwięzły sposób. Jeśli to konieczne, zobacz oryginalną zmianę.

Obecnie próbuję prześledzić serię pojedynczych kolorowych plam na płótnie bitmapowym.

np. Przykładem bitmapy Ja próbuje śladu będzie wyglądać następująco: alt text http://www.refuctored.com/polygons.bmp

Po pomyślnym śledzenie zarysy 3 bąble na zdjęcie, chciałbym mieć klasę, która odbyła kolor kropelka przywiązany do lista punktów reprezentująca kontur obiektu typu blob (nie wszystkie piksele wewnątrz obiektów typu blob).

Problem, który napotykam, to logika w przypadkach, gdy sąsiadujący piksel nie ma otaczających pikseli innych niż poprzedni piksel.

np. Górny przykład może być cienki, ale drugi nie, ponieważ piksel nie ma dokąd, ponieważ poprzednie piksele zostały już użyte.

alt text http://www.refuctored.com/error.jpg

jestem śledzenie lewej do prawej, od góry do dołu, sprzyjając ukośnych kątów ponad kątem prostym. Muszę być w stanie przerysować dokładną kopię regionu na podstawie danych, które wypakowuję, więc piksele na liście muszą być we właściwej kolejności, aby kopia działała.

Do tej pory moja próba została podziurawiona niepowodzeniem i kilka dni wyciągania moich włosów, próbując przepisać algorytmy trochę za każdym razem, aby rozwiązać problem. Do tej pory nie udało mi się. Czy ktoś inny miał podobny problem, jak mój, który ma dobry algorytm znajdowania krawędzi?

Answer 1

Jedną z prostych metod uniknięcia tych ślepych zaułków jest dwukrotne zwiększenie rozmiaru obrazu, który ma być śledzony, za pomocą algorytmu skalowania najbliższego sąsiada przed jego śledzeniem. W ten sposób nigdy nie otrzymasz pojedynczych pasków.

Alternatywą jest użycie algorytmu kwadratów marszu - ale wydaje się jeszcze jeden lub dwa przypadki, w których nie jest on: http://www.sakri.net/blog/2009/05/28/detecting-edge-pixels-with-marching-squares-algorithm/

Answer 2

Zamiast używać rekursji, użyj stosu.

Pseudo-kod:

Add initial pixel to polygon 
Add initial pixel to stack 
while(stack is not empty) { 
    pop pixel off the stack 
    foreach (neighbor n of popped pixel) { 
     if (n is close enough in color to initial pixel) { 
      Add n to polygon 
      Add n to stack 
     } 
    } 
} 

To będzie używać dużo mniej pamięci niż w tym samym roztworze przy użyciu rekursji.

Answer 3

Czy przyjrzeliście się algorytmom wykrywania blobów? Na przykład: http://opencv.willowgarage.com/wiki/cvBlobsLib, jeśli możesz zintegrować OpenCV z aplikacją. W połączeniu z progowaniem tworzenia obrazów binarnych dla każdego koloru (lub zakresu kolorów) na obrazie, można łatwo znaleźć obiekty blob, które są tego samego koloru. Powtórz dla każdego koloru na obrazie, a masz listę plamek posortowanych według kolorów.

Jeśli nie możesz bezpośrednio użyć OpenCV, być może papier, do którego odnosi się ta biblioteka ("Algorytm etykietowania komponentów w czasie liniowym z wykorzystaniem techniki śledzenia konturów", F.Chang i wsp.) Zapewniłby dobrą metodę znajdowania obiektów typu blob.

Answer 4

Po prostu wyślij swój "Obraz" do funkcji BuildPixelArray, a następnie zadzwoń do FindRegions. Następnie zmienna "kolory" będzie przechowywać listę kolorów i współrzędne pikseli w każdym elemencie listy.

Skopiowałem źródło z jednego z moich projektów, mogą występować pewne nieokreślone zmienne lub błędy składni.

public class ImageProcessing{ 
    private int[,] pixelArray; 
    private int imageWidth; 
    private int imageHeight; 
    List<MyColor> colors; 

    public void BuildPixelArray(ref Image myImage) 
    { 
     imageHeight = myImage.Height; 
     imageWidth = myImage.Width; 
     pixelArray = new int[imageWidth, imageHeight]; 
     Rectangle rect = new Rectangle(0, 0, myImage.Width, myImage.Height); 
     Bitmap temp = new Bitmap(myImage); 
     BitmapData bmpData = temp.LockBits(rect, ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb); 
     int remain = bmpData.Stride - bmpData.Width * 3; 
     unsafe 
     { 
      byte* ptr = (byte*)bmpData.Scan0; 
      for (int j = 15; j < bmpData.Height; j++) 
      { 
       for (int i = 0; i < bmpData.Width; i++) 
       { 
        pixelArray[i, j] = ptr[0] + ptr[1] * 256 + ptr[2] * 256 * 256; 
        ptr += 3; 
       } 
       ptr += remain; 
      } 
     } 
     temp.UnlockBits(bmpData); 
    } 

    public void FindRegions() 
    { 
     colors = new List<MyColor>(); 

     for (int i = 0; i < imageWidth; i++) 
     { 
      for (int j = 0; j < imageHeight; j++) 
      { 
       int tmpColorValue = pixelArray[i, j]; 
       MyColor tmp = new MyColor(tmpColorValue); 
       if (colors.Contains(tmp)) 
       { 
        MyColor tmpColor = (from p in colors 
             where p.colorValue == tmpColorValue 
             select p).First(); 

        tmpColor.pointList.Add(new MyPoint(i, j)); 
       } 
       else 
       { 
        tmp.pointList.Add(new MyPoint(i, j)); 
        colors.Add(tmp); 
       } 
      } 
     } 
    } 
} 

public class MyColor : IEquatable<MyColor> 
{ 
    public int colorValue { get; set; } 
    public List<MyPoint> pointList = new List<MyPoint>(); 
    public MyColor(int _colorValue) 
    { 
     colorValue = _colorValue; 
    } 
    public bool Equals(MyColor other) 
    { 
     if (this.colorValue == other.colorValue) 
     { 
      return true; 
     } 
     return false; 
    } 
} 
public class MyPoint 
{ 
    public int xCoord { get; set; } 
    public int yCoord { get; set; } 

    public MyPoint(int _xCoord, int _yCoord) 
    { 
     xCoord = _xCoord; 
     yCoord = _yCoord; 
    } 
} 

Answer 5

Jeśli otrzymujesz przepełnienie stosu, domyślam się, że nie wykluczasz już zaznaczonych pikseli.Pierwszą próbą odwiedzenia placu powinno być to, czy już tu byłeś.

Również byłem w pracy na pokrewnym problemem nie tak dawno temu, a ja przyszedłem z innego podejścia, które zużywa dużo mniej pamięci:

Kolejka:

AddPointToQueue(x, y); 
repeat 
    x, y = HeadItem; 
    AddMaybe(x - 1, y); x + 1, y; x, y - 1; x, y + 1; 
until QueueIsEmpty; 

AddMaybe(x, y): 
if Visited[x, y] return; 
Visited[x, y] = true; 
AddPointToQueue(x, y); 

Punkt ten podejście polega na tym, że kończysz swoją kolejką zasadniczo trzymając linię owiniętą wokół odwzorowanego obszaru. Ogranicza to użycie pamięci lepiej niż stos.

W razie potrzeby można go również zmodyfikować w dowolny sposób, aby uzyskać odległość do dowolnego kwadratu.

Answer 6

Spróbuj użyć AForge.net. Wybrałbym opcję Filtruj według kolorów, Próg, a następnie możesz wykonać Morfologię, aby zmniejszyć strefy czarno-białe, aby utracić kontakt między obiektami. Wtedy możesz pójść po Bloby.