Wykrywanie pików w tablicy 2D

Rozwiązanie

Plik danych: paw.txt . Kod źródłowy:

from scipy import *
from operator import itemgetter

n = 5  # how many fingers are we looking for

d = loadtxt("paw.txt")
width, height = d.shape

# Create an array where every element is a sum of 2x2 squares.

fourSums = d[:-1,:-1] + d[1:,:-1] + d[1:,1:] + d[:-1,1:]

# Find positions of the fingers.

# Pair each sum with its position number (from 0 to width*height-1),

pairs = zip(arange(width*height), fourSums.flatten())

# Sort by descending sum value, filter overlapping squares

def drop_overlapping(pairs):
    no_overlaps = []
    def does_not_overlap(p1, p2):
        i1, i2 = p1[0], p2[0]
        r1, col1 = i1 / (width-1), i1 % (width-1)
        r2, col2 = i2 / (width-1), i2 % (width-1)
        return (max(abs(r1-r2),abs(col1-col2)) >= 2)
    for p in pairs:
        if all(map(lambda prev: does_not_overlap(p,prev), no_overlaps)):
            no_overlaps.append(p)
    return no_overlaps

pairs2 = drop_overlapping(sorted(pairs, key=itemgetter(1), reverse=True))

# Take the first n with the heighest values

positions = pairs2[:n]

# Print results

print d, "\n"

for i, val in positions:
    row = i / (width-1)
    column = i % (width-1)
    print "sum = %f @ %d,%d (%d)" % (val, row, column, i)
    print d[row:row+2,column:column+2], "\n"

Wyjście bez nakładania się kwadratów. Wygląda na to, że wybrano te same obszary, co w twoim przykładzie.

Kilka komentarzy

Najtrudniejsze jest obliczenie Sum wszystkich kwadratów 2x2. Założyłem, że potrzebujesz ich wszystkich, więc mogą się na siebie nakładać. Użyłem plasterków, aby wyciąć pierwsze / Ostatnie kolumny i wiersze z oryginalnej tablicy 2D, a następnie nakładać je wszystkie razem i obliczanie Sum.

Aby lepiej zrozumieć, zobrazowanie tablicy 3x3:

>>> a = arange(9).reshape(3,3) ; a
array([[0, 1, 2],
       [3, 4, 5],
       [6, 7, 8]])

Wtedy możesz wziąć jego plasterki:

>>> a[:-1,:-1]
array([[0, 1],
       [3, 4]])
>>> a[1:,:-1]
array([[3, 4],
       [6, 7]])
>>> a[:-1,1:]
array([[1, 2],
       [4, 5]])
>>> a[1:,1:]
array([[4, 5],
       [7, 8]])

Wyobraź sobie, że układasz je jeden nad drugim i sumujesz elementy w tych samych pozycjach. Te sumy będą dokładnie tymi samymi sumami dla kwadratów 2x2 z lewym górnym rogiem w tej samej pozycji:

>>> sums = a[:-1,:-1] + a[1:,:-1] + a[:-1,1:] + a[1:,1:]; sums
array([[ 8, 12],
       [20, 24]])

Gdy masz sumy powyżej 2x2 kwadratów, możesz użyć max, aby znaleźć maksimum, lub sort, lub sorted, aby znaleźć szczyty.

To zapamiętaj pozycje pików i para każdej wartości (sumy) z jej pozycją porządkową w spłaszczonej tablicy (patrz zip). Następnie obliczam pozycję wiersza / kolumny ponownie, gdy drukuje wyniki.

Uwagi

Pozwoliłem na nakładanie się kwadratów 2x2. Edytowana wersja filtruje niektóre z nich tak, że w wynikach pojawiają się tylko nie nakładające się kwadraty.

Choosing fingers (an idea)

Kolejnym problemem jest to, jak wybrać to, co może być fingers z wszystkich szczyty. Mam pomysł, który może się udać. Nie mam teraz czasu na implementację, więc po prostu pseudo-kod.

Zauważyłem, że jeśli przednie palce pozostają na prawie idealnym okręgu, palec tylny powinien być wewnątrz tego okręgu. Również przednie palce są mniej lub bardziej równomiernie rozmieszczone. Możemy spróbować użyć tych właściwości heurystycznych, aby wykryć palce.

Pseudo kod:

select the top N finger candidates (not too many, 10 or 12)
consider all possible combinations of 5 out of N (use itertools.combinations)
for each combination of 5 fingers:
    for each finger out of 5:
        fit the best circle to the remaining 4
        => position of the center, radius
        check if the selected finger is inside of the circle
        check if the remaining four are evenly spread
        (for example, consider angles from the center of the circle)
        assign some cost (penalty) to this selection of 4 peaks + a rear finger
        (consider, probably weighted:
             circle fitting error,
             if the rear finger is inside,
             variance in the spreading of the front fingers,
             total intensity of 5 peaks)
choose a combination of 4 peaks + a rear peak with the lowest penalty

To podejście brutalne. Jeśli N jest stosunkowo małe, to myślę, że jest wykonalne. Dla N=12 istnieje C_12^5 = 792 kombinacje, razy 5 sposobów wyboru palca tylnego, więc 3960 przypadków do oceny dla każdej łapy.

To jest problem z rejestracją obrazu . Ogólna strategia to:

• mają znany przykład, lub jakiś rodzaj przed na danych.
• Dopasuj swoje dane do przykładu lub dopasuj przykład do swoich danych.
• pomaga, jeśli Twoje dane są w przybliżeniu wyrównane w pierwszej kolejności.

Oto szorstkie i gotowe podejście, "najgłupsza rzecz, która mogłaby zadziałać": {]}

• zacznij od pięciu współrzędnych palców w mniej więcej miejscu spodziewasz się.
• z każdym z nich, iteracyjnie wspiąć się na szczyt wzgórza. tj. biorąc pod uwagę bieżącą pozycję, przesuń do maksymalnego sąsiedniego piksela, jeśli jego wartość jest większa niż bieżący piksel. Zatrzymaj się, gdy twoje współrzędne palców przestaną się poruszać.

Aby przeciwdziałać problemowi z orientacją, możesz mieć 8 lub więcej ustawień początkowych dla podstawowych kierunków (północ, północny wschód, itp.). Uruchom każdy z nich indywidualnie i odrzuć wszelkie wyniki, w których dwa lub więcej palców kończy się w tym samym pikselu. Ja pomyśl o tym trochę więcej, ale tego rodzaju rzeczy są nadal badane w przetwarzaniu obrazów - nie ma właściwych odpowiedzi!

Nieco bardziej złożony pomysł: (ważony) K-oznacza klastrowanie.Nie jest tak źle.

• zacznij od pięciu współrzędnych palców, ale teraz są to "centra klastrów".

Następnie iteracja do zbieżności:

• Przypisz każdy piksel do najbliższego klastra (po prostu zrób listę dla każdego klastra).
• Oblicz środek masy każdego klastra. Dla każdego klastra jest to: Sum (coordinate * intensity value) / Sum(coordinate)
• Przenieś każdą gromadę do nowego środka masy.

Ta metoda prawie na pewno da znacznie lepsze wyniki, a otrzymasz masę każdego klastra, która może pomóc w identyfikacji palców.

(ponownie podałeś liczbę klastrów z przodu. Z klastrowania trzeba określić gęstość w ten czy inny sposób: albo wybrać liczbę klastrów, odpowiednie w tym case, lub wybierz promień klastra i zobacz, ile kończy się z. Przykładem tego ostatniego jest mean-shift .)

Przepraszamy za brak szczegółów implementacji lub innych szczegółów. Zakodowałbym to, ale mam termin. Jeśli nic innego nie działa do przyszłego tygodnia daj mi znać, a dam mu szansę.

Problem ten został dogłębnie zbadany przez fizyków. Jest dobra implementacja w ROOT. Spójrz na klasy TSpectrum (szczególnie TSpectrum2 dla Twojego przypadku) i dokumentację dla nich.

Bibliografia:

[[11]}M. Morhac et al.: Metody eliminacji tła dla wielowymiarowych zbiegów widma promieniowania gamma. Nuclear Instruments and Methods in Physics Research A 401 (1997) 113-132. [[11]}M. Morhac et al.: Wydajny- i dekonwolucja dwuwymiarowego złota i jego zastosowanie do rozkładu widma promieniowania gamma. Nuclear Instruments and Methods in Physics Research A 401 (1997) 385-408. [[11]}M. Morhac et al.: Identyfikacja pików w wielowymiarowych zbieżnych widmach gamma-ray. Nuclear Instruments and Methods in Research Physics A 443 (2000), 108-125.

...i dla tych, którzy nie mają dostępu do abonamentu na NIM:

• spektrum.doc
• SpectrumDec.ps.gz
• SpectrumSrc.ps.gz
• SpectrumBck.ps.gz

Oto pomysł: obliczasz (dyskretną) Laplacian obrazu. Spodziewałbym się, że będzie (negatywna i) duża w maxima, w sposób bardziej dramatyczny niż na oryginalnych obrazach. Tak więc, maxima może być łatwiejsze do znalezienia.

Oto inny pomysł: jeśli znasz typowy rozmiar miejsc wysokociśnieniowych, możesz najpierw wygładzić swój obraz, łącząc go z Gaussem o tej samej wielkości. Może to ułatwić przetwarzanie obrazów.

Tylko kilka pomysłów z czubka mojej głowy:

• Weź gradient (pochodną) skanowania, sprawdź, czy eliminuje to fałszywe wywołania
• Weź maksimum lokalnej maksymy

Możesz też rzucić okiem na OpenCV , ma całkiem przyzwoite API Pythona i może mieć kilka przydatnych funkcji.

Używając trwałej homologii do analizy zestawu danych otrzymuję następujący wynik (Kliknij, aby powiększyć):

To jest 2D-Wersja metody wykrywania pików opisanej w tym więc odpowiedz . Powyższy rysunek pokazuje po prostu 0-wymiarowe klasy trwałej homologii posortowane według trwałości.

Zrobiłem zwiększenie oryginalnego zbioru danych o współczynnik 2 za pomocą scipy.misc.imresize(). Jednak zauważ, że uważałem cztery łapy za jeden zestaw danych; dzieląc go na cztery ułatwiłoby to problem.

Metodologia. Idea stojąca za tym dość prosta: rozważmy wykres funkcji funkcji, która przypisuje każdemu pikselowi swój poziom. Wygląda tak:

Rozważmy teraz poziom wody na wysokości 255, który stale schodzi do niższych poziomów. Na lokalnych wyspach maxima pojawiają się (narodziny). W punktach siodłowych łączą się dwie wyspy; uznajemy, że dolna wyspa jest połączona z wyższą wyspą (śmierć). Tzw. trwałość diagram (z 0-wymiarowych klas homologii, nasze Wyspy) Przedstawia wartości śmierci nad urodzeniami wszystkich wysp:

trwałość wyspy jest wtedy różnicą między poziomem narodzin i śmierci; pionową odległością kropki od szarej głównej przekątnej. Na rysunku zaznaczono Wyspy zmniejszając trwałość.

Pierwsze zdjęcie pokazuje miejsca narodzin na wyspach. Metoda ta daje nie tylko lokalne maksima, ale także kwantyfikuje ich "znaczenie" przez wyżej wspomnianą wytrwałość. Można by wtedy odfiltrować wszystkie wyspy ze zbyt niską trwałością. Jednak w twoim przykładzie każda wyspa (tj. każde lokalne maksimum) jest szczytem, którego szukasz.

Kod Pythona można znaleźć tutaj .

Dzięki za surowe dane. Jestem w pociągu i to jest tak daleko, jak dostałem (mój przystanek zbliża się). Masowałem Twój plik txt z wyrażeniami regularnymi i umieściłem go na stronie html z javascript do wizualizacji. Dzielę się nim tutaj, ponieważ niektórzy, jak ja, mogą znaleźć go łatwiejsze do zhakowania niż python.

Myślę, że dobrym podejściem będzie niezmiennik skali i rotacji, a moim następnym krokiem będzie zbadanie mieszanin gaussów. (każda łapka stanowiąca środek gaussian).

    <html>
<head>
    <script type="text/javascript" src="http://vis.stanford.edu/protovis/protovis-r3.2.js"></script> 
    <script type="text/javascript">
    var heatmap = [[[0,0,0,0,0,0,0,4,4,0,0,0,0],
[0,0,0,0,0,7,14,22,18,7,0,0,0],
[0,0,0,0,11,40,65,43,18,7,0,0,0],
[0,0,0,0,14,61,72,32,7,4,11,14,4],
[0,7,14,11,7,22,25,11,4,14,65,72,14],
[4,29,79,54,14,7,4,11,18,29,79,83,18],
[0,18,54,32,18,43,36,29,61,76,25,18,4],
[0,4,7,7,25,90,79,36,79,90,22,0,0],
[0,0,0,0,11,47,40,14,29,36,7,0,0],
[0,0,0,0,4,7,7,4,4,4,0,0,0]
],[
[0,0,0,4,4,0,0,0,0,0,0,0,0],
[0,0,11,18,18,7,0,0,0,0,0,0,0],
[0,4,29,47,29,7,0,4,4,0,0,0,0],
[0,0,11,29,29,7,7,22,25,7,0,0,0],
[0,0,0,4,4,4,14,61,83,22,0,0,0],
[4,7,4,4,4,4,14,32,25,7,0,0,0],
[4,11,7,14,25,25,47,79,32,4,0,0,0],
[0,4,4,22,58,40,29,86,36,4,0,0,0],
[0,0,0,7,18,14,7,18,7,0,0,0,0],
[0,0,0,0,4,4,0,0,0,0,0,0,0],
],[
[0,0,0,4,11,11,7,4,0,0,0,0,0],
[0,0,0,4,22,36,32,22,11,4,0,0,0],
[4,11,7,4,11,29,54,50,22,4,0,0,0],
[11,58,43,11,4,11,25,22,11,11,18,7,0],
[11,50,43,18,11,4,4,7,18,61,86,29,4],
[0,11,18,54,58,25,32,50,32,47,54,14,0],
[0,0,14,72,76,40,86,101,32,11,7,4,0],
[0,0,4,22,22,18,47,65,18,0,0,0,0],
[0,0,0,0,4,4,7,11,4,0,0,0,0],
],[
[0,0,0,0,4,4,4,0,0,0,0,0,0],
[0,0,0,4,14,14,18,7,0,0,0,0,0],
[0,0,0,4,14,40,54,22,4,0,0,0,0],
[0,7,11,4,11,32,36,11,0,0,0,0,0],
[4,29,36,11,4,7,7,4,4,0,0,0,0],
[4,25,32,18,7,4,4,4,14,7,0,0,0],
[0,7,36,58,29,14,22,14,18,11,0,0,0],
[0,11,50,68,32,40,61,18,4,4,0,0,0],
[0,4,11,18,18,43,32,7,0,0,0,0,0],
[0,0,0,0,4,7,4,0,0,0,0,0,0],
],[
[0,0,0,0,0,0,4,7,4,0,0,0,0],
[0,0,0,0,4,18,25,32,25,7,0,0,0],
[0,0,0,4,18,65,68,29,11,0,0,0,0],
[0,4,4,4,18,65,54,18,4,7,14,11,0],
[4,22,36,14,4,14,11,7,7,29,79,47,7],
[7,54,76,36,18,14,11,36,40,32,72,36,4],
[4,11,18,18,61,79,36,54,97,40,14,7,0],
[0,0,0,11,58,101,40,47,108,50,7,0,0],
[0,0,0,4,11,25,7,11,22,11,0,0,0],
[0,0,0,0,0,4,0,0,0,0,0,0,0],
],[
[0,0,4,7,4,0,0,0,0,0,0,0,0],
[0,0,11,22,14,4,0,4,0,0,0,0,0],
[0,0,7,18,14,4,4,14,18,4,0,0,0],
[0,4,0,4,4,0,4,32,54,18,0,0,0],
[4,11,7,4,7,7,18,29,22,4,0,0,0],
[7,18,7,22,40,25,50,76,25,4,0,0,0],
[0,4,4,22,61,32,25,54,18,0,0,0,0],
[0,0,0,4,11,7,4,11,4,0,0,0,0],
],[
[0,0,0,0,7,14,11,4,0,0,0,0,0],
[0,0,0,4,18,43,50,32,14,4,0,0,0],
[0,4,11,4,7,29,61,65,43,11,0,0,0],
[4,18,54,25,7,11,32,40,25,7,11,4,0],
[4,36,86,40,11,7,7,7,7,25,58,25,4],
[0,7,18,25,65,40,18,25,22,22,47,18,0],
[0,0,4,32,79,47,43,86,54,11,7,4,0],
[0,0,0,14,32,14,25,61,40,7,0,0,0],
[0,0,0,0,4,4,4,11,7,0,0,0,0],
],[
[0,0,0,0,4,7,11,4,0,0,0,0,0],
[0,4,4,0,4,11,18,11,0,0,0,0,0],
[4,11,11,4,0,4,4,4,0,0,0,0,0],
[4,18,14,7,4,0,0,4,7,7,0,0,0],
[0,7,18,29,14,11,11,7,18,18,4,0,0],
[0,11,43,50,29,43,40,11,4,4,0,0,0],
[0,4,18,25,22,54,40,7,0,0,0,0,0],
[0,0,4,4,4,11,7,0,0,0,0,0,0],
],[
[0,0,0,0,0,7,7,7,7,0,0,0,0],
[0,0,0,0,7,32,32,18,4,0,0,0,0],
[0,0,0,0,11,54,40,14,4,4,22,11,0],
[0,7,14,11,4,14,11,4,4,25,94,50,7],
[4,25,65,43,11,7,4,7,22,25,54,36,7],
[0,7,25,22,29,58,32,25,72,61,14,7,0],
[0,0,4,4,40,115,68,29,83,72,11,0,0],
[0,0,0,0,11,29,18,7,18,14,4,0,0],
[0,0,0,0,0,4,0,0,0,0,0,0,0],
]
];
</script>
</head>
<body>
    <script type="text/javascript+protovis">    
    for (var a=0; a < heatmap.length; a++) {
    var w = heatmap[a][0].length,
    h = heatmap[a].length;
var vis = new pv.Panel()
    .width(w * 6)
    .height(h * 6)
    .strokeStyle("#aaa")
    .lineWidth(4)
    .antialias(true);
vis.add(pv.Image)
    .imageWidth(w)
    .imageHeight(h)
    .image(pv.Scale.linear()
        .domain(0, 99, 100)
        .range("#000", "#fff", '#ff0a0a')
        .by(function(i, j) heatmap[a][j][i]));
vis.render();
}
</script>
  </body>
</html>

Jestem pewien, że masz już dość, ale nie mogę pomóc, ale sugeruję użycie metody k-means clustering. k-means to nienadzorowany algorytm klastrowania, który pobierze dane (w dowolnej liczbie wymiarów-zdarza mi się to zrobić w 3D) i ułoży je w klastry k o wyraźnych granicach. Miło tu, bo wiesz dokładnie, ile palców powinny mieć te kły.

DODATKOWO jest zaimplementowany w Scipy co jest naprawdę fajne ( http://docs.scipy.org/doc/scipy/reference/cluster.vq.html).

Oto przykład, co może zrobić, aby przestrzennie rozwiązać klastry 3D:

To, co chcesz zrobić, jest trochę inne (2D i zawiera wartości ciśnienia), ale nadal myślę, że możesz spróbować.

Rozwiązanie Fizyka:
Zdefiniuj 5 znaczników paw identyfikowanych przez ich pozycje X_i i init je przypadkowymi pozycjami. Zdefiniuj jakąś funkcję energetyczną łączącą pewną nagrodę za położenie markerów w pozycjach łapy z pewną karą za nakładanie się markerów; powiedzmy:

E(X_i;S)=-Sum_i(S(X_i))+alfa*Sum_ij (|X_i-Xj|<=2*sqrt(2)?1:0)

(S(X_i) jest średnią siłą w kwadracie 2x2 wokół X_i, alfa jest parametrem, który ma być osiągany eksperymentalnie)

Teraz czas na magię Metropolis-Hastings:
1. Wybierz losowy znacznik i przesuń go o jeden piksel w losowym kierunku.
2. Oblicz dE, różnicę energii spowodowaną tym ruchem.
3. Uzyskaj jednolitą liczbę losową od 0-1 i nazwij ją r.
4. Jeśli dE<0 lub exp(-beta*dE)>r, Zaakceptuj ruch i przejdź do 1; jeśli nie, Cofnij ruch i przejdź do 1.
Należy to powtarzać, aż markery zbiegną się w łapy. Beta kontroluje skanowanie w celu optymalizacji tradeoff, więc powinien być również zoptymalizowany eksperymentalnie; może być również stale zwiększany z czasem symulacji (symulowane wyżarzanie).

Oto kolejne podejście, które zastosowałem robiąc coś podobnego dla dużego Teleskopu:

1) wyszukaj najwyższy piksel. Gdy już to masz, Szukaj wokół tego dla najlepszego dopasowania do 2x2 (może maksymalizacji sumy 2x2), lub zrobić dopasowanie Gaussa 2D wewnątrz podregionu powiedzmy 4x4 wyśrodkowany na najwyższym pikselu.

Następnie ustaw te 2x2 piksele, które znalazłeś na zero (a może 3x3) wokół środka piku

Wróć do 1) i powtarzaj aż najwyższy szczyt spadnie poniżej szumu threshold, or you have all the toes you need

Prawdopodobnie warto spróbować z sieci neuronowych, jeśli jesteś w stanie stworzyć pewne dane treningowe... ale to wymaga wielu próbek adnotowanych ręcznie.

Szorstki zarys...

Prawdopodobnie chciałbyś użyć algorytmu connected components, aby wyizolować Każdy region łapy. wiki ma przyzwoity opis tego (z jakimś kodem) tutaj: http://en.wikipedia.org/wiki/Connected_Component_Labeling

Będziesz musiał podjąć decyzję, czy użyć połączenia 4 czy 8. osobiście w przypadku większości problemów wolę 6-konektowe. w każdym razie, po oddzieleniu każdego "odcisku łapy" jako połączonego regionu, powinno być wystarczająco łatwo / align = "center" bgcolor = "# e0ffe0 " / cesarz chin / / align = center / gdy już znajdziesz maksimum, możesz iteracyjnie powiększyć region, aż osiągniesz z góry określony próg, aby zidentyfikować go jako dany "palec u nogi".

Subtelnym problemem jest to, że jak tylko zaczniesz używać technik widzenia komputerowego, aby zidentyfikować coś jako prawą/lewą/przednią / tylną łapę i zaczniesz patrzeć na poszczególne palce, musisz zacząć brać pod uwagę obroty, pochylenia i tłumaczenia. odbywa się to poprzez analiza tzw. "momentów". istnieje kilka różnych momentów do rozważenia w aplikacjach vision:

Central moments: tłumaczenie niezmienne momenty znormalizowane: skalowanie i tłumaczenie niezmienne HU moments: translation, scale, and rotation invariant

Więcej informacji na temat momentów można znaleźć, przeszukując "image moments" na wiki.

Być może możesz użyć czegoś w rodzaju modeli mieszanek Gaussa. Oto pakiet Pythona do robienia GMMs (właśnie zrobiłem wyszukiwanie w Google) http://www.ar.media.kyoto-u.ac.jp/members/david/softwares/em/

Cóż, oto prosty i niezbyt wydajny kod, ale dla tego rozmiaru zbioru danych jest w porządku.

import numpy as np
grid = np.array([[0,0,0,0,0,0,0,0,0,0,0,0,0,0],
              [0,0,0,0,0,0,0,0,0.4,0.4,0.4,0,0,0],
              [0,0,0,0,0.4,1.4,1.4,1.8,0.7,0,0,0,0,0],
              [0,0,0,0,0.4,1.4,4,5.4,2.2,0.4,0,0,0,0],
              [0,0,0.7,1.1,0.4,1.1,3.2,3.6,1.1,0,0,0,0,0],
              [0,0.4,2.9,3.6,1.1,0.4,0.7,0.7,0.4,0.4,0,0,0,0],
              [0,0.4,2.5,3.2,1.8,0.7,0.4,0.4,0.4,1.4,0.7,0,0,0],
              [0,0,0.7,3.6,5.8,2.9,1.4,2.2,1.4,1.8,1.1,0,0,0],
              [0,0,1.1,5,6.8,3.2,4,6.1,1.8,0.4,0.4,0,0,0],
              [0,0,0.4,1.1,1.8,1.8,4.3,3.2,0.7,0,0,0,0,0],
              [0,0,0,0,0,0.4,0.7,0.4,0,0,0,0,0,0]])

arr = []
for i in xrange(grid.shape[0] - 1):
    for j in xrange(grid.shape[1] - 1):
        tot = grid[i][j] + grid[i+1][j] + grid[i][j+1] + grid[i+1][j+1]
        arr.append([(i,j),tot])

best = []

arr.sort(key = lambda x: x[1])

for i in xrange(5):
    best.append(arr.pop())
    badpos = set([(best[-1][0][0]+x,best[-1][0][1]+y)
                  for x in [-1,0,1] for y in [-1,0,1] if x != 0 or y != 0])
    for j in xrange(len(arr)-1,-1,-1):
        if arr[j][0] in badpos:
            arr.pop(j)


for item in best:
    print grid[item[0][0]:item[0][0]+2,item[0][1]:item[0][1]+2]

Po prostu robię tablicę z położeniem lewego górnego rogu i sumą każdego kwadratu 2x2 i sortuję ją według sumy. Następnie biorę kwadrat 2x2 z najwyższą sumą, umieszczam go w tablicy best i usuwam wszystkie pozostałe kwadraty 2x2, które używały jakiejkolwiek części tego właśnie usunąłem kwadrat 2x2.

Wygląda na to, że działa dobrze, z wyjątkiem ostatniej łapy (tej z najmniejszą sumą po prawej stronie na pierwszym zdjęciu), okazuje się, że istnieją dwa inne kwalifikujące się kwadraty 2x2 z większą sumą (i mają taką samą sumę do siebie). Jeden z nich nadal wybiera jeden kwadrat z twojego kwadratu 2x2, ale drugi jest wyłączony po lewej stronie. Na szczęście widzimy, że wybieramy Więcej z tych, które chcesz, ale może to wymagać innych pomysłów, aby uzyskać to, czego naprawdę chcesz przez cały czas.

Wydaje się, że można oszukać trochę za pomocą algorytmu jetxee. Uważa, że pierwsze trzy palce są w porządku i powinieneś być w stanie odgadnąć, gdzie opiera się czwarty.

Ciekawy problem. Rozwiązanie, którego bym spróbował, jest następujące.

1. Zastosuj filtr dolnoprzepustowy, taki jak splot z maską Gaussa 2D. To da ci kilka (prawdopodobnie, ale niekoniecznie zmiennoprzecinkowych) wartości.

2. Wykonaj niesymetryczne tłumienie 2D, używając znanego przybliżonego promienia każdej łapy (lub palca).

To powinno dać Ci maksymalne stanowiska bez wielu kandydatów, którzy są blisko siebie. Dla jasności, promień maski w kroku 1 powinien być również podobny do promienia użytego w Kroku 2. Promień ten można wybrać, lub weterynarz może wyraźnie zmierzyć go wcześniej (będzie się różnić w zależności od wieku/rasy/itp.).

Niektóre z proponowanych rozwiązań (mean shift, sieci neuronowe itd.) prawdopodobnie będą działać do pewnego stopnia, ale są zbyt skomplikowane i prawdopodobnie nie są idealne.

Chcę wam tylko powiedzieć, że jest fajna opcja, aby znaleźć lokalne maxima w obrazach z Pythonem.

from skimage.feature import peak_local_max

Lub dla skimage 0.8.0

from skimage.feature.peak import peak_local_max

Http://scikit-image.org/docs/0.8.0/api/skimage.feature.peak.html

Być może wystarczy naiwne podejście: Zbuduj listę wszystkich kwadratów 2x2 na swojej płaszczyźnie, uporządkuj je według ich sumy (w porządku malejącym).

Najpierw wybierz kwadrat o najwyższej wartości do swojej "listy łap". Następnie iteracyjnie wybierz 4 z kolejnych najlepszych kwadratów, które nie przecinają się z żadnym z wcześniej znalezionych kwadratów.

Co zrobić, jeśli postępujesz krok po kroku: najpierw zlokalizujesz globalne maksimum, przetworzysz w razie potrzeby otaczające punkty, podając ich wartość, a następnie Ustaw znaleziony region na zero i powtórz dla następnego.

Nie jestem pewien, czy to odpowiada na pytanie, ale wydaje się, że można po prostu szukać N najwyższych szczytów, które nie mają sąsiadów.

Oto sedno. zauważ, że jest w Ruby, ale pomysł powinien być jasny.

require 'pp'

NUM_PEAKS = 5
NEIGHBOR_DISTANCE = 1

data = [[1,2,3,4,5],
        [2,6,4,4,6],
        [3,6,7,4,3],
       ]

def tuples(matrix)
  tuples = []
  matrix.each_with_index { |row, ri|
    row.each_with_index { |value, ci|
      tuples << [value, ri, ci]
    }
  }
  tuples
end

def neighbor?(t1, t2, distance = 1)
  [1,2].each { |axis|
    return false if (t1[axis] - t2[axis]).abs > distance
  }
  true
end

# convert the matrix into a sorted list of tuples (value, row, col), highest peaks first
sorted = tuples(data).sort_by { |tuple| tuple.first }.reverse

# the list of peaks that don't have neighbors
non_neighboring_peaks = []

sorted.each { |candidate|
  # always take the highest peak
  if non_neighboring_peaks.empty?
    non_neighboring_peaks << candidate
    puts "took the first peak: #{candidate}"
  else
    # check that this candidate doesn't have any accepted neighbors
    is_ok = true
    non_neighboring_peaks.each { |accepted|
      if neighbor?(candidate, accepted, NEIGHBOR_DISTANCE)
        is_ok = false
        break
      end
    }
    if is_ok
      non_neighboring_peaks << candidate
      puts "took #{candidate}"
    else
      puts "denied #{candidate}"
    end
  end
}

pp non_neighboring_peaks