Dopasowywanie szablonów niezmiennie w skali i rotacji

12

Szukam metody do niezmiennego dopasowywania szablonów w skali i rotacji. Próbowałem już niektóre, ale nie działały tak dobrze dla moich przykładów lub na zawsze do wykonania. Wykrywanie funkcji SIFT i SURF nie powiodło się całkowicie. Próbowałem także zaimplementować funkcję Log-Polar Template Matching, ale nigdy nie skończyłem (nie wiedziałem dokładnie, jak to zrobić).

W tych artykułach (pierwszy jest w języku niemieckim)

http://cvpr.uni-muenster.de/teaching/ss08/seminarSS08/downloads/Wentker-Vortrag.pdf

http://www.jprr.org/index.php/jprr/article/viewFile/355/148

Czytam o tej metodzie. Mapowanie współrzędnych biegunowych zadziałało, ale nie wiem, czy to prawda. Obrazy wyglądają tak.

source_log_polar.png http://www.shareimages.com/images/pics/0/0/3/62394-pZSfl5WenZysnpyVnKg-source_log_polar.png

template_log_polar.png

I po dopasowaniu tych 2 obrazów za pomocą funkcji dopasowania szablonu OpenCV uzyskałem ten wynik

match_log_polar.png

Teraz nie wiem jak iść dalej.

Moje szablony są zawsze prostymi symbolami przy tworzeniu planów i samych planów. Symbole mogą różnić się rozmiarem i orientacją.

Na przykład mój prosty plan:

wprowadź opis zdjęcia tutaj

I mój szablon

wprowadź opis zdjęcia tutaj

W tym przykładzie jest tylko jeden szablon, ale w planach powinien on znaleźć wszystkie wystąpienia, nawet te o rozmiarach i / lub orientacjach.

Czy ktoś ma podejście, jak mogę to rozwiązać?

Edytować:

Dodatek do podejścia Andreya. Algorytm przechwytywania odległości dla profilu promieniowego. (Korzystanie z EmguCV)

private float[] getRadialProfile( Image<Gray, byte> image, Point center, int resolution )
 {

 var roi = image.ROI;

 if ( !roi.Contains( center ) )
  {
   return null;
  }

 var steps = resolution;
 var degreeSteps = 360 / (double)resolution;
 var data = image.Data;
 var peak = 0.0f;
 var bottom = double.MaxValue;
 var bottomIndex = 0;
 var width = roi.Width;
 var height = roi.Height;
 var minX = roi.X;
 var minY = roi.Y;

 float[] distances = new float[resolution];
 for ( var i = 0; i < steps; i++ )
  {
   var degree = i * degreeSteps;
   var radial = degree * Math.PI / 180.0;
   var dy = Math.Sin( radial );
   var dx = Math.Cos( radial );

   var x = (double)center.X;
   var y = (double)center.Y;

   while ( true )
    {
    x += dx;
    y += dy;
    if ( x >= minX + width || y >= minY + height || x <= minX || y <= minY )
     {
      x = -1;
      y = -1;
      break;
     }
    var pixel = data[(int)y, (int)x, 0];
    if ( pixel == 0 )
     {
      break;
     }
    }

    float distance = 0.0f;
    if ( x != -1 && y != -1 )
    {
      distance = (float)Math.Sqrt( Math.Pow( (center.X - x), 2 ) + Math.Pow( (center.Y - y), 2 ) );
    }

    distances[i] = distance;
    if ( distance > peak )
    {
      peak = distance;
    }
    if ( distance < bottom )
    {
      bottom = distance;
      bottomIndex = i;
    }
   }

    // Scale invariance. Divide by peak
   for ( var i = 0; i < distances.Length; i++ )
   {
     distances[i] /= peak;
   }

    // rotation invariance, shift to lowest value
   for ( var i = 0; i < bottomIndex; i++ )
   {
     distances.ShiftLeft(); // Just rotates the array nothing special
   }

   return distances;
}
Arndt Bieberstein
źródło
witamy w dsp.SE. Postaramy się Ci pomóc, ale podanie dokładniejszych informacji byłoby miło. Co rozumiesz przez SIFT i SURF „całkowicie zawiodło”? Co wykryli / dopasowali? Poza tym osobiście nie wiem o dopasowaniu szablonów Log-Polar, ale jeśli próbowałeś, gdzie dokładnie był problem?
penelopa,
Wykrywania funkcji SIFT i SURF nie znaleziono żadnych funkcji w obrazie szablonu. Wygląda na to, że szablon ma zbyt mało informacji (tylko ten mały łuk i linia). Do dopasowania Log-Polar znalazłem artykuł, w którym jest opisany, ale nie dokładną matematykę. Przeszukam go i dodam.
Arndt Bieberstein,
Hej, niewiele osób tutaj rozumie niemiecki, myślę: D Ale, dla wszystkiego innego: możesz edytować swój post, aby dodać nowe informacje we właściwym miejscu, zamiast w komentarzach. I nadal nie powiedziałeś, z czym dokładnie miałeś problemy.
penelopa,
3
Autor „niemieckiego artykułu” ma artykuł w języku angielskim - www-cs.engr.ccny.cuny.edu/~wolberg/pub/icip00.pdf (dzięki google)
SergV

Odpowiedzi:

6

Myślę, że możesz rozwiązać problem w znacznie łatwiejszy sposób. Biorąc pod uwagę, że masz do czynienia z planami, nie powinieneś martwić się łącznością brzegową, hałasem i wieloma innymi rzeczami, do których zbudowano SIFT i SURF. Twój szablon jest pustym kształtem o określonych kształtach krawędzi.

Zatem moim zaleceniem jest:

  • Przejdź się po obwodzie i znajdź profil odległości krawędzi wokół środka szablonu. To jest profil promieniowy szablonu. Podziel przez największą odległość, aby zachować niezmienność skali. Obróć wektor, aby najmniejsza odległość była pierwsza, aby była niezmienna. (Jeśli szablon nie ma dominującej odległości, możesz zmienić krok 2 później)

wprowadź opis zdjęcia tutaj

  • Znajdź obiekty BLOB na obrazie. Oblicz profil promieniowy opisany w części (1) i porównaj dwa wektory za pomocą znormalizowanej korelacji. Jeśli szablon nie ma dominującej odległości, korelacja staje się znormalizowaną korelacją krzyżową i wyborem maksimum). Ci, którzy przekroczą jakiś próg, są uznawani za mecze.

Oto trochę kodu Matlab, od którego możesz zacząć - napisałem część, która znajduje profil odległości dla określonego obiektu blob i obliczyłem go dla szablonu:

function Doors
    im = imread('http://i.stack.imgur.com/Tf8EV.png');
    im = im(:,:,1);
    template = imread('http://i.stack.imgur.com/PlP4i.png');
    template = template(:,:,1);

    blobs = regionprops(template>0,'Area','Image');
    largestBlob = GetLargestBlob(blobs);
    [prof,edgeImage] = GetBlobRadialProfile(largestBlob);

    figure;
    subplot(1,2,1);plot(prof); title('Radial profile')
    subplot(1,2,2);imshow(edgeImage); title('Template');

end

function [prof,edgeImage] = GetBlobRadialProfile(blob)
    paddedImage = padarray( blob.Image,[8 8]);
    erodedImage = imerode(paddedImage,strel('disk',1));
    edgeImage = xor(erodedImage,paddedImage);

    c = regionprops(paddedImage,'Centroid');
    cx  = c.Centroid(1);
    cy  = c.Centroid(2);

    [y,x] = find(edgeImage);
    rad = (x(:)-cx).^2 + (y(:)-cy).^2;
    [~,minIndex] = min(rad);
    contour = bwtraceboundary(edgeImage, [y(minIndex), x(minIndex)],'N');
    prof = (contour(:,2)-cx).^2 + (contour(:,1)-cy).^2;
    prof = prof./max(prof);
end

function largestBlob = GetLargestBlob(blobs)    
    area = [blobs.Area];
    [~,index] = max(area);
    largestBlob = blobs(index);
end
Andrey Rubshtein
źródło
Myślę, że to nie działa z niezamkniętymi kształtami? A może po prostu pomijam te „dziury” w kształcie.
Arndt Bieberstein,
@ArndtBieberstein, tak, działa tylko dla zamkniętych kształtów. Wydaje mi się, że powinna istnieć jakaś metoda jego rozszerzenia.
Andrey Rubshtein,
Ponieważ OpenCV nie zawiera funkcji bwtraceboundary, napisałem własną i po prostu „pominąłem” dziury i wypełniłem zerami. Oto mały przykład, jak teraz wyglądają wyniki. 5 wykresów dla każdego szablonu. Czerwona kropka to punkty początkowe. Przykładowy wykres
Arndt Bieberstein,
@ArndtBieberstein, bardzo miło! Może po zakończeniu możesz podzielić się z nami wynikami.
Andrey Rubshtein, 12.12.12
Jasne, Kodeks nie jest tak fajny ani wydajny, ale działa. Załączę to poniżej mojego pytania. Jest napisany w C # (używam EmguCV)
Arndt Bieberstein,
3

Oto podstawowa koncepcja tego, co wiem, co można zrobić, na podstawie przemówienia profesora Anuraga Mittala z IIT Madras.

Chodzi o wykrywanie obiektów na podstawie kształtu, ale oczywiście można je również rozszerzyć gdzie indziej.

  1. Oblicz krawędzie za pomocą detektora krawędzi Berkeley.
  2. Połącz uzyskane krawędzie. „Globalne wykrywanie granic obiektów”.
  3. Dopasowywanie kształtów za pomocą odległości fazowania lub odległości Houstoffa.

Jego praca na ten temat jest dostępna na: Wieloetapowe wykrywanie obiektów odkształcalnych na podstawie konturu.

Z drugiej strony myślę, że SIFT powinien działać, ponieważ algorytmy wykrywania narożników działałyby na funkcji szablonu, którą masz tam.

Uwaga: SIFT nie jest niezmiennie całkowicie rotacyjny. Nie jest w stanie poradzić sobie z obrotami> 60 stopni lub więcej. Tworzenie wielu szablonów to dobry pomysł.

Podobnie jak w przypadku logarytmicznych transfromów Fouriera-Mellina: powodują utratę informacji z powodu sposobu próbkowania transformat.

Naresh
źródło
Ta metoda brzmi naprawdę obiecująco! Nie mogę otworzyć twojego linku, ale przejrzałem twoje podejście. Nie wiedziałem, że SIFT, że SIFT nie jest całkowicie rotacyjny! Bardzo dobra odpowiedź! +1
Arndt Bieberstein
1
Prawie nie znalazłem nic na temat odległości fazowania i jej działania, dla tych, którzy również szukają tego, wypróbuj ten link.
Arndt Bieberstein,
@Naresh SIFT nie jest niezmienny dla dużych obrotów poza płaszczyzną. Nie w tej samej płaszczyźnie.
a-Jays,
1

Nie zastanawiałem się nad tym, ale jestem pewien, że solidne rozwiązanie można bez problemu zastosować przy użyciu klasycznych deskryptorów Fouriera (FD). Myślę, że twój problem może być bardzo dobrym kandydatem do tego. Nie sądzę, że musisz wykonywać wykrywanie krawędzi, ponieważ masz czarne rysunki. Po prostu rozpocznij skanowanie rastrowe, aż trafisz na jakiekolwiek piksele, a następnie wykonaj następujące czynności:

Po prostu traktuj obwód pokoju tak, jakby był to sygnał 1D, gdzie amplituda sygnału to normalna odległość od środka ciężkości obiektu, próbkowana z pewną stałą szybkością. Więc zrób prosty model FD dla drzwi. Następnie zeskanuj parametr każdego pokoju za pomocą swego rodzaju wypukłego filtra w poszukiwaniu wznoszącego się zbocza, piku i spadku, który ustawia okno start / stop „sygnału” do przechwycenia. Wykonaj FFT lub podobny algorytm FD na tym przechwyconym „sygnale” i porównaj z szablonem FD. Być może krok porównywania szablonów może być prostą korelacją z progiem wyzwalającym dopasowanie. Ponieważ tylko twoje drzwi mają okrągłe krawędzie, co powinno być dość łatwym problemem dopasowania FD.

Pomyśl o tym, jak przy użyciu FD do pobierania obrazów lub muzyki z bazy danych. Wiele białych ksiąg na ten temat.

Jest to dobry samouczek na temat korzystania z FD do przybliżania kształtów: wątpię, czy będziesz go potrzebować, ale możesz też najpierw przekształcić swoje obrazy w układ współrzędnych biegunowych, aby poradzić sobie z obrotami, jak zaproponowano w tym artykule: Pobieranie obrazów na podstawie kształtu za pomocą ogólny deskryptor Fouriera

zobaczyć, jak FD parametryzują wykrywanie obwodu jabłka? Ten sam pomysł jak twoje drzwi.

BTW, jestem prawie pewien, że odwzorowanie całego schematu na współrzędne biegunowe nie pomoże w niezmienności rotacyjnej - trzeba by to zrobić w odniesieniu do środka ciężkości każdych drzwi, od czego dokładnie zaczyna się twój problem. Właśnie dlatego myślę, że chcesz po prostu uchwycić kandydatów na drzwi i być może odwzorować ich na współrzędne biegunowe, aby pasowały do ​​szablonu drzwi FD, tak jak to zrobiono w powyższym dokumencie.

daj mi znać, jak to będzie, jeśli spróbujesz tego podejścia.

Ariel Bentolila
źródło
0

Być może znajdziesz ten kod Matlaba, który napisałem, przydatny: Fractal Mosaics

Implementuje artykuł „Solidna rejestracja obrazu za pomocą transformacji log-polar” ( pdf ) w aplikacji artystycznej, która wymagała większej niezawodności niż tradycyjne metody, które znalazłem.

użytkownik2348114
źródło