Peakerkennung in einem 2D-Array

874

Ich helfe einer Tierklinik, den Druck unter einer Hundepfote zu messen. Ich benutze Python für meine Datenanalyse und versuche jetzt nicht mehr, die Pfoten in (anatomische) Unterregionen zu unterteilen.

Ich habe aus jeder Pfote ein 2D-Array erstellt, das aus den Maximalwerten für jeden Sensor besteht, der im Laufe der Zeit von der Pfote geladen wurde. Hier ist ein Beispiel für eine Pfote, bei der ich Excel verwendet habe, um die Bereiche zu zeichnen, die ich "erkennen" möchte. Dies sind 2 mal 2 Kästchen um den Sensor mit lokalen Maxima, die zusammen die größte Summe haben.

Alt-Text

Also habe ich ein bisschen experimentiert und mich entschlossen, einfach nach den Maxima jeder Spalte und Zeile zu suchen (kann aufgrund der Form der Pfote nicht in eine Richtung schauen). Dies scheint die Position der einzelnen Zehen ziemlich gut zu "erkennen", markiert aber auch benachbarte Sensoren.

Alt-Text

Was wäre der beste Weg, um Python zu sagen, welche dieser Maxima ich möchte?

Hinweis: Die 2x2 Quadrate können sich nicht überlappen, da es sich um separate Zehen handeln muss!

Ich habe auch 2x2 als Annehmlichkeit genommen, jede fortgeschrittenere Lösung ist willkommen, aber ich bin einfach ein Wissenschaftler für menschliche Bewegung, also bin ich weder ein richtiger Programmierer noch ein Mathematiker, also halte es bitte 'einfach'.

Hier ist eine Version, die mit geladen werden kannnp.loadtxt


Ergebnisse

Also habe ich die Lösung von @ jextee ausprobiert (siehe die Ergebnisse unten). Wie Sie sehen können, funktioniert es sehr gut an den Vorderpfoten, aber weniger gut an den Hinterbeinen.

Insbesondere kann es den kleinen Gipfel, der der vierte Zeh ist, nicht erkennen. Dies hängt offensichtlich damit zusammen, dass die Schleife von oben nach unten zum niedrigsten Wert schaut, ohne zu berücksichtigen, wo sich dieser befindet.

Würde jemand wissen, wie man den Algorithmus von @ jextee optimiert, damit er möglicherweise auch den 4. Zeh findet?

Alt-Text

Da ich noch keine anderen Versuche bearbeitet habe, kann ich keine weiteren Proben liefern. Aber die Daten, die ich zuvor gegeben habe, waren die Durchschnittswerte jeder Pfote. Diese Datei ist ein Array mit den maximalen Daten von 9 Pfoten in der Reihenfolge, in der sie mit der Platte in Kontakt gekommen sind.

Dieses Bild zeigt, wie sie räumlich über die Platte verteilt waren.

Alt-Text

Aktualisieren:

Ich habe ein Blog für alle Interessierten eingerichtet und ein SkyDrive mit allen Rohmessungen eingerichtet. Also an alle, die mehr Daten anfordern: mehr Leistung für Sie!


Neues Update:

Nach der Hilfe bekam ich meine Fragen zur Pfotenerkennung und zum Sortieren der Pfoten , konnte ich endlich die Zehenerkennung für jede Pfote überprüfen! Es stellt sich heraus, dass es nur bei Pfoten funktioniert, die so groß sind wie in meinem Beispiel. Natürlich im Nachhinein ist es meine eigene Schuld, dass ich den 2x2 so willkürlich gewählt habe.

Hier ist ein schönes Beispiel dafür, wo es schief geht: Ein Nagel wird als Zeh erkannt und die 'Ferse' ist so breit, dass sie zweimal erkannt wird!

Alt-Text

Die Pfote ist zu groß, sodass bei einer Größe von 2 x 2 ohne Überlappung einige Zehen zweimal erkannt werden. Umgekehrt findet man bei kleinen Hunden oft keinen fünften Zeh, was vermutlich darauf zurückzuführen ist, dass der 2x2-Bereich zu groß ist.

Nachdem ich die aktuelle Lösung für alle meine Messungen ausprobiert habe ich kam ich zu dem erstaunlichen Schluss, dass für fast alle meine kleinen Hunde kein fünfter Zeh gefunden wurde und dass in über 50% der Auswirkungen für die großen Hunde mehr gefunden werden würde!

Also klar, ich muss es ändern. Meine eigene Vermutung war, die Größe des neighborhoodzu etwas kleiner für kleine Hunde und größer für große Hunde zu ändern . Aber generate_binary_structureich würde nicht die Größe des Arrays ändern lassen.

Daher hoffe ich, dass jemand anderes einen besseren Vorschlag zum Lokalisieren der Zehen hat, vielleicht mit der Zehenbereichsskala mit der Pfotengröße?

Ivo Flipse
quelle
Ich gehe davon aus, dass die Kommas eher Dezimalstellen als Werttrennzeichen sind.
MattH
Ja, sie sind Kommas. Und @Christian, ich versuche es in eine leicht lesbare Datei zu stecken, aber selbst das schlägt bei mir fehl :(
Ivo Flipse
3
Während ich eine Machbarkeitsstudie mache, geht wirklich alles. Daher suche ich nach möglichst vielen Möglichkeiten, um den Druck zu definieren, einschließlich Unterregionen. Außerdem muss ich in der Lage sein, zwischen der Seite des großen Zehs und der Seite des kleinen Zehs zu unterscheiden, um die Ausrichtung abschätzen zu können. Aber da dies noch nie zuvor gemacht wurde, ist nicht abzusehen, was wir finden könnten :-)
Ivo Flipse
2
@ Ron: Eines der Ziele dieser Studie ist es zu sehen, für welche Größe / welches Gewicht von Hunden das System geeignet ist, also ja, während dieser Hund ungefähr 20 kg wiegt. Ich habe einige, die erheblich kleiner (und größer) sind, und erwarte, dass ich nicht das Gleiche für die wirklich kleinen tun kann.
Ivo Flipse
2
@frank die Pfoten werden über die Zeit gemessen, daher die 3. Dimension. Sie bewegen sich jedoch nicht von ihrem Platz (relativ gesehen), daher interessiert mich vor allem, wo sich die Zehen in 2D befinden. Der 3D-Aspekt ist danach kostenlos
Ivo Flipse

Antworten:

331

Ich habe die Peaks mit einem lokalen Maximalfilter erkannt . Hier ist das Ergebnis Ihres ersten Datensatzes mit 4 Pfoten: Ergebnis der Spitzenerkennung

Ich habe es auch auf dem zweiten Datensatz von 9 Pfoten ausgeführt und es hat auch funktioniert .

So geht's:

import numpy as np
from scipy.ndimage.filters import maximum_filter
from scipy.ndimage.morphology import generate_binary_structure, binary_erosion
import matplotlib.pyplot as pp

#for some reason I had to reshape. Numpy ignored the shape header.
paws_data = np.loadtxt("paws.txt").reshape(4,11,14)

#getting a list of images
paws = [p.squeeze() for p in np.vsplit(paws_data,4)]


def detect_peaks(image):
    """
    Takes an image and detect the peaks usingthe local maximum filter.
    Returns a boolean mask of the peaks (i.e. 1 when
    the pixel's value is the neighborhood maximum, 0 otherwise)
    """

    # define an 8-connected neighborhood
    neighborhood = generate_binary_structure(2,2)

    #apply the local maximum filter; all pixel of maximal value 
    #in their neighborhood are set to 1
    local_max = maximum_filter(image, footprint=neighborhood)==image
    #local_max is a mask that contains the peaks we are 
    #looking for, but also the background.
    #In order to isolate the peaks we must remove the background from the mask.

    #we create the mask of the background
    background = (image==0)

    #a little technicality: we must erode the background in order to 
    #successfully subtract it form local_max, otherwise a line will 
    #appear along the background border (artifact of the local maximum filter)
    eroded_background = binary_erosion(background, structure=neighborhood, border_value=1)

    #we obtain the final mask, containing only peaks, 
    #by removing the background from the local_max mask (xor operation)
    detected_peaks = local_max ^ eroded_background

    return detected_peaks


#applying the detection and plotting results
for i, paw in enumerate(paws):
    detected_peaks = detect_peaks(paw)
    pp.subplot(4,2,(2*i+1))
    pp.imshow(paw)
    pp.subplot(4,2,(2*i+2) )
    pp.imshow(detected_peaks)

pp.show()

Alles, was Sie danach tun müssen, ist die Verwendung scipy.ndimage.measurements.labelder Maske, um alle unterschiedlichen Objekte zu beschriften. Dann können Sie individuell mit ihnen spielen.

Beachten Sie, dass die Methode gut funktioniert, da der Hintergrund nicht verrauscht ist. Wenn dies der Fall wäre, würden Sie eine Reihe anderer unerwünschter Spitzen im Hintergrund erkennen. Ein weiterer wichtiger Faktor ist die Größe der Nachbarschaft . Sie müssen es anpassen, wenn sich die Peakgröße ändert (die sollte ungefähr proportional bleiben).

Ivan
quelle
1
Es gibt eine einfachere Lösung als (eroded_background ^ local_peaks). Tun Sie es einfach (Vordergrund & lokale Gipfel)
Ryan Soklaski
53

Lösung

Datendatei : paw.txt . Quellcode:

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"

Ausgabe ohne überlappende Quadrate. Es scheint, dass die gleichen Bereiche wie in Ihrem Beispiel ausgewählt sind.

Einige Kommentare

Der schwierige Teil besteht darin, die Summen aller 2x2 Quadrate zu berechnen. Ich nahm an, dass Sie alle brauchen, daher kann es zu Überschneidungen kommen. Ich habe Slices verwendet, um die ersten / letzten Spalten und Zeilen aus dem ursprünglichen 2D-Array auszuschneiden, sie dann alle miteinander zu überlappen und Summen zu berechnen.

Um es besser zu verstehen, stellen Sie sich ein 3x3-Array vor:

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

Dann können Sie seine Scheiben nehmen:

>>> 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]])

Stellen Sie sich nun vor, Sie stapeln sie übereinander und summieren Elemente an denselben Positionen. Diese Summen sind genau die gleichen Summen über den 2x2 Quadraten, wobei sich die obere linke Ecke an derselben Position befindet:

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

Wenn Sie die Summen über 2x2 Quadrate haben, können maxSie das Maximum oder sortoder sorteddie Spitzen ermitteln.

Um mich an die Positionen der Peaks zu erinnern, kopple ich jeden Wert (die Summe) mit seiner Ordnungsposition in einem abgeflachten Array (siehe zip). Dann berechne ich die Zeilen- / Spaltenposition erneut, wenn ich die Ergebnisse drucke.

Anmerkungen

Ich habe zugelassen, dass sich die 2x2-Quadrate überlappen. Die bearbeitete Version filtert einige davon heraus, sodass in den Ergebnissen nur nicht überlappende Quadrate angezeigt werden.

Finger wählen (eine Idee)

Ein weiteres Problem ist die Auswahl der Finger aus allen Spitzen. Ich habe eine Idee, die funktionieren kann oder nicht. Ich habe momentan keine Zeit, es zu implementieren, also nur Pseudocode.

Mir ist aufgefallen, dass sich der hintere Finger innerhalb dieses Kreises befinden sollte, wenn die vorderen Finger auf einem fast perfekten Kreis bleiben. Auch die Vorderfinger sind mehr oder weniger gleichmäßig beabstandet. Wir können versuchen, diese heuristischen Eigenschaften zu verwenden, um die Finger zu erkennen.

Pseudocode:

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

Dies ist ein Brute-Force-Ansatz. Wenn N relativ klein ist, denke ich, dass es machbar ist. Für N = 12 gibt es C_12 ^ 5 = 792 Kombinationen, mal 5 Möglichkeiten, einen hinteren Finger auszuwählen, also 3960 Fälle, die für jede Pfote ausgewertet werden müssen.

Sastanin
quelle
Er muss die Pfoten anhand Ihrer Ergebnisliste manuell herausfiltern. Wenn Sie die vier obersten Ergebnisse auswählen, hat er die vier Möglichkeiten, ein 2x2-Quadrat mit dem Maximalwert 6,8 zu konstruieren
Johannes Charra
Die 2x2-Felder können sich nicht überlappen, da ich, wenn ich Statistiken erstellen möchte, nicht dieselbe Region verwenden möchte, sondern Regionen vergleichen möchte :-)
Ivo Flipse
Ich habe die Antwort bearbeitet. Jetzt gibt es keine überlappenden Quadrate in den Ergebnissen.
Sastanin
1
Ich habe es ausprobiert und es scheint für die Vorderpfoten zu funktionieren, aber weniger für die Hinterpfoten. Ich denke, wir müssen etwas ausprobieren, das weiß, wo wir suchen müssen
Ivo Flipse
1
Ich erklärte meine Idee, wie Finger im Pseudocode erkannt werden können. Wenn es Ihnen gefällt, kann ich versuchen, es morgen Abend umzusetzen.
Sastanin
34

Dies ist ein Problem bei der Bildregistrierung . Die allgemeine Strategie lautet:

  • Haben Sie ein bekanntes Beispiel oder eine Art Prior auf den Daten.
  • Passen Sie Ihre Daten an das Beispiel an oder passen Sie das Beispiel an Ihre Daten an.
  • Es ist hilfreich, wenn Ihre Daten in erster Linie grob ausgerichtet sind.

Hier ist ein grober und vorgefertigter Ansatz , "das Dümmste, was möglicherweise funktionieren könnte":

  • Beginnen Sie mit fünf Zehenkoordinaten ungefähr an der Stelle, die Sie erwarten.
  • Klettern Sie mit jedem iterativ auf die Spitze des Hügels. dh bei gegebener aktueller Position zum maximal benachbarten Pixel bewegen, wenn sein Wert größer als das aktuelle Pixel ist. Stoppen Sie, wenn sich Ihre Zehenkoordinaten nicht mehr bewegen.

Um dem Orientierungsproblem entgegenzuwirken, können Sie ungefähr 8 Grundeinstellungen für die Grundeinstellungen (Nord, Nordost usw.) vornehmen. Führen Sie jedes einzeln aus und werfen Sie alle Ergebnisse weg, bei denen zwei oder mehr Zehen am selben Pixel landen. Ich werde noch etwas darüber nachdenken, aber so etwas wird in der Bildverarbeitung noch erforscht - es gibt keine richtigen Antworten!

Etwas komplexere Idee: (gewichtet) K-bedeutet Clustering. Ist doch nicht so schlimm.

  • Beginnen Sie mit fünf Zehenkoordinaten, aber jetzt sind dies "Cluster-Zentren".

Dann iterieren bis zur Konvergenz:

  • Weisen Sie jedes Pixel dem nächstgelegenen Cluster zu (erstellen Sie einfach eine Liste für jeden Cluster).
  • Berechnen Sie den Schwerpunkt jedes Clusters. Für jeden Cluster ist dies: Summe (Koordinate * Intensitätswert) / Summe (Koordinate)
  • Verschieben Sie jeden Cluster in den neuen Schwerpunkt.

Diese Methode liefert mit ziemlicher Sicherheit viel bessere Ergebnisse, und Sie erhalten die Masse jedes Clusters, die bei der Identifizierung der Zehen hilfreich sein kann.

(Auch hier haben Sie die Anzahl der Cluster im Voraus angegeben. Beim Clustering müssen Sie die Dichte auf die eine oder andere Weise angeben: Wählen Sie entweder die Anzahl der in diesem Fall geeigneten Cluster aus oder wählen Sie einen Clusterradius und sehen Sie, wie viele Sie beenden Ein Beispiel für Letzteres ist die Mittelwertverschiebung .)

Entschuldigung für das Fehlen von Implementierungsdetails oder anderen Besonderheiten. Ich würde das verschlüsseln, aber ich habe eine Frist. Wenn bis nächste Woche nichts anderes funktioniert hat, lass es mich wissen und ich werde es versuchen.

CakeMaster
quelle
1
Das Problem ist, dass die Pfoten ihre Ausrichtung ändern und ich zunächst keine Kalibrierung / Grundlinie für eine korrekte Pfote habe. Außerdem befürchte ich, dass viele der Bilderkennungsalgorithmen etwas außerhalb meiner Liga liegen.
Ivo Flipse
Der "grobe und fertige" Ansatz ist ziemlich einfach - vielleicht habe ich die Idee nicht gut verstanden. Ich werde zur Veranschaulichung einen Pseudocode eingeben.
CakeMaster
Ich habe das Gefühl, Ihr Vorschlag wird dazu beitragen, die Erkennung der Hinterpfoten zu verbessern. Ich weiß nur nicht, wie
Ivo Flipse
Ich habe eine andere Idee hinzugefügt. Übrigens, wenn Sie eine Menge guter Daten haben, wäre es cool, sie irgendwo online zu stellen. Es könnte für Leute nützlich sein, die Bildverarbeitung / maschinelles Lernen studieren, und Sie könnten etwas mehr Code daraus ziehen ...
CakeMaster
1
Ich habe nur darüber nachgedacht, meine Datenverarbeitung in einem einfachen Wordpress-Blog aufzuschreiben, um für andere von Nutzen zu sein, und ich muss sie trotzdem aufschreiben. Ich mag alle Ihre Vorschläge, aber ich fürchte, ich muss auf jemanden ohne Frist warten ;-)
Ivo Flipse
18

Bei Verwendung einer persistenten Homologie zur Analyse Ihres Datensatzes erhalte ich das folgende Ergebnis (zum Vergrößern anklicken):

Ergebnis

Dies ist die 2D-Version der in dieser SO-Antwort beschriebenen Peakerkennungsmethode . Die obige Abbildung zeigt einfach 0-dimensionale persistente Homologieklassen, sortiert nach Persistenz.

Ich habe den Originaldatensatz mit scipy.misc.imresize () um den Faktor 2 hochskaliert. Beachten Sie jedoch, dass ich die vier Pfoten als einen Datensatz betrachtet habe. Eine Aufteilung in vier Teile würde das Problem erleichtern.

Methodik. Die Idee dahinter ist ganz einfach: Betrachten Sie den Funktionsgraphen der Funktion, die jedem Pixel seinen Pegel zuweist. Es sieht aus wie das:

3D-Funktionsgraph

Betrachten Sie nun einen Wasserstand in Höhe 255, der kontinuierlich auf niedrigere Niveaus abfällt. Bei lokalen Maxima tauchen Inseln auf (Geburt). An Sattelpunkten verschmelzen zwei Inseln; Wir betrachten die untere Insel als mit der höheren Insel verschmolzen (Tod). Das sogenannte Persistenzdiagramm (der 0-dimensionalen Homologieklassen, unserer Inseln) zeigt die Todesfälle über den Geburtswerten aller Inseln:

Persistenzdiagramm

Die Beharrlichkeit einer Insel ist dann der Unterschied zwischen dem Geburts- und dem Todesniveau; der vertikale Abstand eines Punktes zur grauen Hauptdiagonale. Die Abbildung kennzeichnet die Inseln durch Verringern der Persistenz.

Das allererste Bild zeigt die Geburtsorte der Inseln. Diese Methode gibt nicht nur die lokalen Maxima an, sondern quantifiziert auch ihre "Bedeutung" durch die oben erwähnte Persistenz. Man würde dann alle Inseln mit einer zu geringen Persistenz herausfiltern. In Ihrem Beispiel ist jedoch jede Insel (dh jedes lokale Maximum) ein Gipfel, nach dem Sie suchen.

Python-Code finden Sie hier .

S. Huber
quelle
16

Dieses Problem wurde von Physikern eingehend untersucht. Es gibt eine gute Implementierung in ROOT . Schauen Sie sich die TSpectrum- Klassen an (insbesondere TSpectrum2 für Ihren Fall) und die Dokumentation dazu an.

Verweise:

  1. M. Morhac et al.: Hintergrundeliminierungsmethoden für mehrdimensionale Koinzidenz-Gammastrahlenspektren. Nukleare Instrumente und Methoden in der Physikforschung A 401 (1997) 113-132.
  2. M. Morhac et al.: Effiziente ein- und zweidimensionale Goldentfaltung und ihre Anwendung auf die Zersetzung von Gammastrahlenspektren. Nukleare Instrumente und Methoden in der Physikforschung A 401 (1997) 385-408.
  3. M. Morhac et al.: Identifizierung von Peaks in mehrdimensionalen Gammastrahlenspektren. Nukleare Instrumente und Methoden in der Forschungsphysik A 443 (2000), 108-125.

... und für diejenigen, die keinen Zugang zu einem NIM-Abonnement haben:

dmckee --- Ex-Moderator Kätzchen
quelle
Für einen Blick auf den Artikel scheint es die gleiche Datenverarbeitung zu beschreiben wie das, was ich hier versuche, aber ich befürchte, dass es meine Programmierkenntnisse weit übertroffen hat :(
Ivo Flipse
@Ivo: Ich habe nie versucht, es selbst zu implementieren. Ich benutze nur ROOT. Trotzdem gibt es Python-Bindungen, aber beachten Sie, dass ROOT ein ziemlich schweres Paket ist.
dmckee --- Ex-Moderator Kätzchen
@ Ivo Flipse: Ich stimme dmckee zu. Sie haben viele vielversprechende Hinweise in anderen Antworten. Wenn sie alle versagen und Sie Lust haben, etwas Zeit zu investieren, können Sie sich mit ROOT befassen und es wird (wahrscheinlich) das tun, was Sie brauchen. Ich habe noch nie jemanden gekannt, der versucht hat, ROOT über die Python-Bindungen zu lernen (anstatt über natürliches C ++), also wünsche ich Ihnen viel Glück.
Physikmichael
13

Hier ist eine Idee: Sie berechnen den (diskreten) Laplace-Wert des Bildes. Ich würde erwarten, dass es bei Maxima (negativ und) groß ist, auf eine Weise, die dramatischer ist als in den Originalbildern. Somit könnten Maxima leichter zu finden sein.

Hier ist eine andere Idee: Wenn Sie die typische Größe der Hochdruckpunkte kennen, können Sie Ihr Bild zuerst glätten, indem Sie es mit einem Gaußschen derselben Größe falten. Dadurch können Sie möglicherweise einfachere Bilder verarbeiten.

Eric O Lebigot
quelle
11

Nur ein paar Ideen aus meinem Kopf:

  • Nehmen Sie den Gradienten (Ableitung) des Scans und prüfen Sie, ob dadurch die falschen Anrufe beseitigt werden
  • nimm das Maximum der lokalen Maxima

Vielleicht möchten Sie auch einen Blick auf OpenCV werfen , es hat eine ziemlich anständige Python-API und einige Funktionen, die Sie nützlich finden würden.

ChrisC
quelle
Mit Steigung meinst du, ich sollte die Steilheit der Hänge berechnen, sobald diese einen bestimmten Wert überschreitet, von dem ich weiß, dass es einen "Peak" gibt? Ich habe es versucht, aber einige der Zehen haben nur sehr niedrige Spitzen (1,2 N / cm) im Vergleich zu einigen anderen (8 N / cm). Wie soll ich mit Peaks mit einem sehr geringen Gradienten umgehen?
Ivo Flipse
2
Was in der Vergangenheit für mich funktioniert hat, wenn ich den Gradienten nicht direkt verwenden konnte, war das Betrachten des Gradienten und der Maxima, z. B. wenn der Gradient ein lokales Extrema ist und ich mich in einem lokalen Maxima befinde, dann bin ich an einem Punkt von Interesse.
ChrisC
11

Ich bin mir sicher, dass Sie jetzt genug haben, um fortzufahren, aber ich kann nicht anders, als die Verwendung der k-means-Clustering-Methode vorzuschlagen. k-means ist ein unbeaufsichtigter Clustering-Algorithmus, mit dem Sie Daten (in einer beliebigen Anzahl von Dimensionen - ich mache dies zufällig in 3D) in k Cluster mit unterschiedlichen Grenzen anordnen können. Es ist schön hier, weil Sie genau wissen, wie viele Zehen diese Eckzähne haben (sollten).

Außerdem ist es in Scipy implementiert, was wirklich nett ist ( http://docs.scipy.org/doc/scipy/reference/cluster.vq.html) ).

Hier ist ein Beispiel dafür, wie 3D-Cluster räumlich aufgelöst werden können: Geben Sie hier die Bildbeschreibung ein

Was Sie tun möchten, ist etwas anders (2D und enthält Druckwerte), aber ich denke immer noch, dass Sie es versuchen könnten.

Astromax
quelle
10

danke für die rohdaten. Ich bin im Zug und das ist so weit wie ich gekommen bin (meine Haltestelle kommt). Ich habe Ihre txt-Datei mit regulären Ausdrücken massiert und sie zur Visualisierung in eine HTML-Seite mit etwas Javascript eingefügt. Ich teile es hier, weil einige, wie ich, es leichter hacken können als Python.

Ich denke, ein guter Ansatz wird skalierungs- und rotationsinvariant sein, und mein nächster Schritt wird darin bestehen, Gemische von Gaußschen zu untersuchen. (Jedes Pfotenpolster ist das Zentrum eines Gaußschen).

    <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>

Alt-Text

Ron
quelle
1
Ich denke, dies ist ein Proof of Concept, dass die empfohlenen Gaußschen Techniken funktionieren könnten, wenn nur jemand es mit Python beweisen könnte ;-)
Ivo Flipse
8

Physikerlösung:
Definieren Sie 5 Pfotenmarker, die durch ihre Positionen identifiziert werden, X_iund initiieren Sie sie mit zufälligen Positionen. Definieren Sie eine Energiefunktion, indem Sie eine Auszeichnung für die Position von Markern in Pfotenpositionen mit einer Bestrafung für die Überlappung von Markern kombinieren. sagen wir:

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

( S(X_i)ist die mittlere Kraft in 2x2 Quadrat um X_i,alfa ist ein Parameter, der experimentell erreicht werden soll)

Jetzt ist es Zeit, etwas Metropolis-Hastings-Magie zu üben:
1. Wählen Sie einen zufälligen Marker und verschieben Sie ihn um ein Pixel in zufällige Richtung.
2. Berechnen Sie dE, die Energiedifferenz, die diese Bewegung verursacht hat.
3. Erhalten Sie eine einheitliche Zufallszahl von 0-1 und nennen Sie sie r.
4. Wenn dE<0oder exp(-beta*dE)>r, akzeptieren Sie den Zug und gehen Sie zu 1; Wenn nicht, machen Sie die Bewegung rückgängig und gehen Sie zu 1.
Dies sollte wiederholt werden, bis die Markierungen zu Pfoten konvergieren. Beta steuert das Scannen, um den Kompromiss zu optimieren. Daher sollte es auch experimentell optimiert werden. Sie kann auch mit der Zeit der Simulation ständig erhöht werden (simuliertes Tempern).

mbq
quelle
Möchten Sie zeigen, wie dies bei meinem Beispiel funktionieren würde? Da ich mich wirklich nicht mit Mathematik auf hohem Niveau beschäftige, fällt es mir bereits schwer, die von Ihnen vorgeschlagene Formel
Ivo Flipse
1
Dies ist High-School-Mathematik, wahrscheinlich ist meine Notation nur verschleiert. Ich habe vor, es zu überprüfen, also bleibt dran.
mbq
4
Ich bin Teilchenphysiker. Lange Zeit hieß das Software-Tool in unserer Disziplin PAW und hatte eine Entität, die sich auf Diagramme bezog, die als "Marker" bezeichnet wurden. Sie können sich vorstellen, wie verwirrend ich diese Antwort beim ersten Mal fand ...
dmckee --- Ex-Moderator Kätzchen
6

Hier ist ein anderer Ansatz, den ich verwendet habe, als ich etwas Ähnliches für ein großes Teleskop gemacht habe:

1) Suchen Sie nach dem höchsten Pixel. Sobald Sie das haben, suchen Sie danach nach der besten Anpassung für 2x2 (möglicherweise Maximierung der 2x2-Summe) oder führen Sie eine 2D-Gauß-Anpassung innerhalb des Unterbereichs von beispielsweise 4x4 durch, der auf dem höchsten Pixel zentriert ist.

Setzen Sie dann die gefundenen 2x2 Pixel um die Spitzenmitte auf Null (oder vielleicht 3x3)

Gehen Sie zurück zu 1) und wiederholen Sie den Vorgang, bis der höchste Peak eine Geräuschschwelle unterschreitet oder Sie alle Zehen haben, die Sie benötigen

Paulus
quelle
Möchten Sie ein Codebeispiel freigeben, das dies tut? Ich kann verfolgen, was Sie versuchen, habe aber keine Ahnung, wie ich es selbst codieren soll
Ivo Flipse
Ich komme eigentlich aus der Arbeit mit Matlab, also ja, das würde schon helfen. Aber wenn Sie wirklich fremde Funktionen verwenden, kann es für mich schwierig sein, sie mit Python zu replizieren
Ivo Flipse
6

Es lohnt sich wahrscheinlich, es mit neuronalen Netzen zu versuchen, wenn Sie in der Lage sind, einige Trainingsdaten zu erstellen. Dafür sind jedoch viele von Hand kommentierte Beispiele erforderlich.

Antirez
quelle
Wenn sich die Mühe lohnt, würde es mir nichts ausmachen, eine große Stichprobe von Hand zu kommentieren. Mein Problem wäre: Wie implementiere ich das, da ich nichts über das Programmieren neuronaler Netze weiß
Ivo Flipse
6

ein grober Umriss ...

Sie möchten wahrscheinlich einen Algorithmus für verbundene Komponenten verwenden, um jede Pfotenregion zu isolieren. Wiki hat eine anständige Beschreibung davon (mit etwas Code) hier: http://en.wikipedia.org/wiki/Connected_Component_Labeling

Sie müssen sich entscheiden, ob Sie 4 oder 8 Verbindungen verwenden möchten. persönlich bevorzuge ich für die meisten probleme 6-vernetzung. Sobald Sie jeden "Pfotenabdruck" als verbundene Region getrennt haben, sollte es einfach genug sein, durch die Region zu iterieren und die Maxima zu finden. Sobald Sie die Maxima gefunden haben, können Sie die Region iterativ vergrößern, bis Sie einen vorgegebenen Schwellenwert erreichen, um ihn als einen bestimmten "Zeh" zu identifizieren.

Ein subtiles Problem hierbei ist, dass Sie Rotationen, Schrägstellungen und Übersetzungen berücksichtigen müssen, sobald Sie anfangen, mithilfe von Computer-Vision-Techniken etwas als rechte / linke / vordere / hintere Pfote zu identifizieren und einzelne Zehen zu betrachten. Dies wird durch die Analyse sogenannter "Momente" erreicht. Bei Vision-Anwendungen sind einige verschiedene Momente zu berücksichtigen:

zentrale Momente: Translationsinvariante normalisierte Momente: Skalierung und Translationsinvariante Hu-Momente: Translations-, Skalierungs- und Rotationsinvariante

Weitere Informationen zu Momenten finden Sie, indem Sie im Wiki nach "Bildmomenten" suchen.

Joshua
quelle
4

Es scheint, dass Sie mit dem Jetxee-Algorithmus ein bisschen schummeln können. Er findet die ersten drei Zehen in Ordnung, und Sie sollten erraten können, wo die vierten darauf basieren.

Geoff
quelle
4

Interessantes Problem. Die Lösung, die ich versuchen würde, ist die folgende.

  1. Wenden Sie ein Tiefpassfilter an, z. B. eine Faltung mit einer 2D-Gauß-Maske. Dies gibt Ihnen eine Reihe von (wahrscheinlich, aber nicht unbedingt Gleitkomma) Werten.

  2. Führen Sie eine nicht maximale 2D-Unterdrückung mit dem bekannten ungefähren Radius jedes Pfotenpolsters (oder Zehs) durch.

Dies sollte Ihnen die maximalen Positionen geben, ohne dass mehrere Kandidaten nahe beieinander liegen. Zur Verdeutlichung sollte der Radius der Maske in Schritt 1 auch dem in Schritt 2 verwendeten Radius ähnlich sein. Dieser Radius kann wählbar sein oder der Tierarzt kann ihn vorher explizit messen (er variiert je nach Alter / Rasse / usw.).

Einige der vorgeschlagenen Lösungen (mittlere Verschiebung, neuronale Netze usw.) funktionieren wahrscheinlich bis zu einem gewissen Grad, sind jedoch zu kompliziert und wahrscheinlich nicht ideal.

Bob Mottram
quelle
Ich habe keine Erfahrung mit Faltungsmatrizen und Gaußschen Filtern. Möchten Sie also zeigen, wie es in meinem Beispiel funktionieren würde?
Ivo Flipse
3

Nun, hier ist ein einfacher und nicht besonders effizienter Code, aber für diese Größe eines Datensatzes ist er in Ordnung.

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]

Ich mache einfach ein Array mit der Position oben links und der Summe jedes 2x2-Quadrats und sortiere es nach der Summe. Ich nehme dann das 2x2-Quadrat mit der höchsten Summe aus dem Wettbewerb und setze es in diebest Array und entferne alle anderen 2x2-Quadrate, die einen Teil dieses gerade entfernten 2x2-Quadrats verwendet haben.

Es scheint gut zu funktionieren, außer mit der letzten Pfote (die mit der kleinsten Summe ganz rechts in Ihrem ersten Bild). Es stellt sich heraus, dass es zwei andere geeignete 2x2-Quadrate mit einer größeren Summe gibt (und sie haben die gleiche Summe zu gegenseitig). Einer von ihnen wählt immer noch ein Quadrat aus Ihrem 2x2-Quadrat aus, der andere befindet sich links. Glücklicherweise wählen wir zum Glück mehr von dem, was Sie möchten, aber dies erfordert möglicherweise einige andere Ideen, um die ganze Zeit das zu bekommen, was Sie tatsächlich wollen.

Justin Peel
quelle
Ich gehe davon aus, dass Ihre Ergebnisse mit denen in der Antwort von @ Jextee übereinstimmen. Zumindest scheint es so, als würde ich es testen.
Ivo Flipse
3

Ich möchte euch nur sagen, dass es eine gute Möglichkeit gibt, lokale maximaBilder in Bildern mit Python zu finden:

from skimage.feature import peak_local_max

oder zum Überfliegen 0.8.0:

from skimage.feature.peak import peak_local_max

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

Thomio
quelle
1

Vielleicht reicht hier ein naiver Ansatz aus: Erstellen Sie eine Liste aller 2x2 Quadrate in Ihrem Flugzeug und ordnen Sie sie nach ihrer Summe (in absteigender Reihenfolge).

Wählen Sie zuerst das am höchsten bewertete Quadrat in Ihrer "Pfotenliste" aus. Wählen Sie dann iterativ 4 der nächstbesten Quadrate aus, die sich mit keinem der zuvor gefundenen Quadrate schneiden.

Johannes Charra
quelle
Ich habe tatsächlich eine Liste mit allen 2x2-Summen erstellt, aber als ich sie bestellt hatte, hatte ich keine Ahnung, wie ich sie iterativ vergleichen sollte. Mein Problem war, dass ich beim Sortieren die Koordinaten aus den Augen verlor. Vielleicht könnte ich sie in ein Wörterbuch stecken, mit den Koordinaten als Schlüssel.
Ivo Flipse
Ja, eine Art Wörterbuch wäre notwendig. Ich hätte angenommen, dass Ihre Darstellung des Rasters bereits eine Art Wörterbuch ist.
Johannes Charra
Nun, das Bild, das Sie oben sehen, ist ein numpy Array. Der Rest wird derzeit in mehrdimensionalen Listen gespeichert. Es wäre wahrscheinlich besser, damit aufzuhören, obwohl ich nicht so vertraut mit dem Durchlaufen von Wörterbüchern bin
Ivo Flipse
1

Es gibt mehrere und umfangreiche Softwarekomponenten aus der Astronomie- und Kosmologie-Community - dies ist sowohl historisch als auch aktuell ein bedeutendes Forschungsgebiet.

Seien Sie nicht beunruhigt, wenn Sie kein Astronom sind - einige sind außerhalb des Feldes einfach zu bedienen. Zum Beispiel könnten Sie Astropie / Photutils verwenden:

https://photutils.readthedocs.io/en/stable/detection.html#local-peak-detection

[Es scheint ein bisschen unhöflich, ihren kurzen Beispielcode hier zu wiederholen.]

Eine unvollständige und leicht voreingenommene Liste von Techniken / Paketen / Links, die von Interesse sein könnten, ist unten angegeben. Fügen Sie in den Kommentaren weitere hinzu, und ich werde diese Antwort nach Bedarf aktualisieren. Natürlich gibt es einen Kompromiss zwischen Genauigkeit und Rechenressourcen. [Ehrlich gesagt gibt es zu viele, um Codebeispiele in einer einzigen Antwort wie dieser anzugeben, daher bin ich mir nicht sicher, ob diese Antwort fliegen wird oder nicht.]

Source Extractor https://www.astromatic.net/software/sextractor

MultiNest https://github.com/farhanferoz/MultiNest [+ pyMultiNest]

Herausforderung bei der Suche nach ASKAP / EMU-Quellen: https://arxiv.org/abs/1509.03931

Sie können auch nach Planck- und / oder WMAP-Quellenextraktionsproblemen suchen.

...

jtlz2
quelle
0

Was ist, wenn Sie Schritt für Schritt vorgehen: Sie suchen zuerst das globale Maximum, verarbeiten bei Bedarf die umgebenden Punkte anhand ihres Werts, setzen dann den gefundenen Bereich auf Null und wiederholen ihn für den nächsten.

Cedric H.
quelle
Hmmm, diese Einstellung auf Null würde es zumindest aus weiteren Berechnungen entfernen, das wäre nützlich.
Ivo Flipse
Anstatt auf Null zu setzen, können Sie eine Gaußsche Funktion mit handverlesenen Parametern berechnen und die gefundenen Werte von den ursprünglichen Druckwerten abziehen. Wenn also der Zeh auf Ihre Sensoren drückt, können Sie durch Finden des höchsten Druckpunkts die Auswirkung dieses Zehs auf die Sensoren verringern und so die benachbarten Zellen mit hohen Druckwerten eliminieren. en.wikipedia.org/wiki/File:Gaussian_2d.png
Daniyar
Möchten Sie ein Beispiel basierend auf meinen Beispieldaten @Daniyar zeigen? Da ich mit einer solchen Datenverarbeitung wirklich nicht vertraut bin
Ivo Flipse
0

Ich bin nicht sicher, ob dies die Frage beantwortet, aber es scheint, als könnten Sie nur nach den n höchsten Gipfeln suchen, die keine Nachbarn haben.

Hier ist das Wesentliche. Beachten Sie, dass es in Ruby ist, aber die Idee sollte klar sein.

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
Rick Hull
quelle
Ich werde versuchen, einen Blick darauf zu werfen und zu sehen, ob ich es in Python-Code konvertieren kann :-)
Ivo Flipse
Bitte fügen Sie den Code in den Beitrag selbst ein, anstatt auf einen Kern zu verlinken, wenn er eine angemessene Länge hat.
agf