Détection de crête dans un réseau 2D

Solution

fichier de données: paw.txt . Code Source:

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"

Sortie sans carrés qui se chevauchent. Il semble que les mêmes zones sont sélectionnées comme dans votre exemple.

Certains commentaires

la partie délicate est de calculer les sommes de tous les carrés 2x2. J'ai supposé que tu en avais besoin, donc il pourrait y avoir des chevauchements. J'ai utilisé des tranches de découper les premières / dernières colonnes et lignes du tableau 2D original, puis les chevaucher ensemble et calculer les sommes.

Pour mieux la comprendre, de l'imagerie d'une matrice 3x3:

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

alors vous pouvez prendre ses tranches:

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

imaginez maintenant que vous les empilez l'un au-dessus de l'autre et additionnez les éléments aux mêmes positions. Ces sommes seront exactement les mêmes sur les carrés 2x2 avec le coin supérieur gauche dans le même position:

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

Quand vous avez l'sommes plus 2x2 places, vous pouvez utiliser max pour trouver le maximum, ou sort , ou sorted pour retrouver les sommets.

pour se souvenir des positions des pics, Je couple chaque valeur (la somme) avec sa position ordinale dans un tableau aplati (voir zip ). Puis je calcule la position de la ligne / colonne de nouveau quand j'imprime les résultats.

Notes

I permet aux carrés 2x2 de se chevaucher. La version éditée filtre certains d'entre eux de sorte que seuls les carrés ne se chevauchant pas apparaissent dans les résultats.

choisir des doigts (une idée)

un autre problème est comment choisir ce qui est susceptible d'être des doigts hors de tous les pics. J'ai une idée qui peut ou peut ne pas fonctionner. Je n'ai pas le temps de l'implémenter maintenant, donc juste du pseudo-code.

j'ai remarqué que si les doigts avant restent sur presque un cercle parfait, l'arrière doigt doit être à l'intérieur de ce cercle. En outre, les doigts avant sont plus ou moins également espacés. On peut essayer d'utiliser ces propriétés heuristiques pour détecter les doigts.

Pseudo code:

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

c'est une approche brutale. Si N est relativement petite, je pense que c'est faisable. Pour N=12, Il y a C_12^5 = 792 combinaisons, fois 5 façons de sélectionner un doigt arrière, donc 3960 cas à évaluer pour chaque patte.

il s'agit d'un problème d'enregistrement d'image . La stratégie générale est la suivante:

• ont un exemple connu, ou une sorte de avant sur les données.
• correspondent à vos données de l'exemple, ou adapter l'exemple à vos données.
• cela aide si vos données sont à peu près alignées en premier lieu.

voici un résumé et prêt approche , "la chose la plus stupide qui pourraient éventuellement travailler":

• commencez avec cinq coordonnées de pied à peu près à l'endroit que vous attendez.
• avec chacun, monter itérativement au sommet de la colline. i.e. étant donné la position actuelle, passer au pixel voisin maximum, si sa valeur est supérieure au pixel actuel. Arrêter lorsque votre orteil coordonnées ont cessé de bouger.

pour contrer l'orientation problème, vous pouvez avoir environ 8 paramètres initiaux pour les directions de base (Nord, Nord-est, etc). Exécutez chacun individuellement et jeter tous les résultats où deux ou plusieurs orteils se retrouvent au même pixel. Je vais y réfléchir encore, mais ce genre de chose fait encore l'objet de recherches dans le traitement d'image - il n'y a pas de bonnes réponses!

idée légèrement plus complexe: (pondérée) K-signifie regroupement. ce n'est pas si mal.

• commence par cinq coordonnées de base, mais maintenant ce sont des"centres de clusters".

puis itérer jusqu'à convergence:

• Assignez chaque pixel au cluster le plus proche (faites juste une liste pour chaque cluster).
• calculer le centre de masse de chaque groupe. Pour chaque groupe, il S'agit de: Somme (coordonnée * intensité) / somme (coordonnée)
• déplacer chaque amas au nouveau centre de masse.

cette méthode donnera certainement de bien meilleurs résultats, et vous obtenez la masse de chaque amas qui peut aider à identifier les orteils.

(encore une fois, vous avez spécifié le nombre de grappes à l'avance. Avec clustering vous devez spécifier la densité d'une manière ou d'une autre: soit choisir le nombre de clusters, approprié dans ce cas, ou choisir un rayon de cluster et voir combien vous finissez avec. Un exemple de ce dernier est poste moyen .)

Désolé pour le manque de détails de mise en œuvre ou d'autres détails. Je coderais bien, mais j'ai une date limite. Si rien d'autre n'a fonctionné la semaine prochaine, prévenez-moi et je tenterai ma chance.

Ce problème a été étudié en profondeur par les physiciens. Il y a une bonne implémentation dans ROOT . Regardez les classes TSpectrum (en particulier TSpectrum2 pour votre cas) et la documentation qui s'y rapporte.

, les Références:

1. M. Morhac et al.: Fond d'élimination méthodes pour multidimensionnelle coïncidence gamma-ray spectres. Les Instruments nucléaires et Méthodes de Recherche en Physique 401 (1997) 113-132.
2. M. Morhac et al.: Efficace à une et deux dimensions de l'Or déconvolution et de son application à la gamma-ray spectres de décomposition. Nucléaire, Méthodes et Instruments de Recherche en Physique 401 (1997) 385-408.
3. M. Morhac et al.: Identification des pics dans multidimensionnelle coïncidence gamma-ray spectres. Nucléaire, Méthodes et Instruments de Recherche en Physique A 443(2000), 108-125.

...et pour ceux qui n'ont pas accès à un abonnement à NIM:

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

Voici une idée: vous calculez le laplacien (discret) de l'image. Je m'attendrais à ce qu'il soit (négatif et) grand à maxima, d'une manière qui est plus dramatique que dans les images originales. Ainsi, maxima pourrait être plus facile à trouver.

Voici une autre idée: si vous connaissez la taille typique des spots de haute pression, vous pouvez d'abord lisser votre image en la convertissant avec un gaussien de la même taille. Cela peut vous donner des images simples à traiter.

juste quelques idées qui me viennent à l'esprit:

• prendre le gradient (dérivé) du scan, voir si cela élimine les faux appels
• prendre le maximum des maxima locaux

vous pourriez aussi jeter un oeil à OpenCV , il a une API Python assez décente et pourrait avoir quelques fonctions que vous trouverez utiles.

en utilisant l'homologie persistante pour analyser votre ensemble de données, j'obtiens le résultat suivant (Cliquez pour agrandir):

il s'agit de la version 2D de la méthode de détection de crête décrite dans cette réponse . La figure ci-dessus montre simplement les classes d'homologie persistante à 0 dimension triées par persistance.

j'ai fait haut de gamme du jeu de données d'origine par un facteur de 2 en utilisant scipy.misc.imresize (). Cependant, notez que j'ai considéré les quatre pattes comme un ensemble de données; le diviser en quatre rendrait le problème plus facile.

Methodology. L'idée derrière ceci très simple: considérer le graphique de fonction de la fonction qui attribue chaque pixel son niveau. Il ressemble à ceci:

maintenant considérer un niveau d'eau à la hauteur 255 que de façon continue descentes aux niveaux inférieurs. Au local maxima Îles pop up (naissance). À saddle points, deux îles fusionnent; nous considérons que l'Île inférieure est fusionnée à l'Île supérieure (death). Le diagramme de la persistance (des classes d'homologie dimensionnelle 0-ème, nos Îles) représente les valeurs de la mort - sur-la-naissance de toutes les îles:

Le persistance d'une île est alors la différence entre la naissance et niveau de la mort; distance verticale d'un point par rapport à la diagonale principale grise. La figure qualifie les îles de persistance Décroissante.

la toute première image montre les lieux de naissance des Îles. Cette méthode donne non seulement les maxima locaux, mais quantifie aussi leur "signification" par la persistance mentionnée ci-dessus. On filtrerait alors toutes les îles avec une persistance trop faible. Cependant, dans votre exemple chaque île (c.-à-d. chaque maximum local) est un pic que vous regardez pour.

code Python peut être trouvé ici .

merci pour les données brutes. Je suis dans le train et c'est aussi loin que je suis arrivé (mon arrêt approche). J'ai massé votre fichier txt avec regexps et je l'ai inséré dans une page html avec du javascript pour la visualisation. Je partage ici parce que certains, comme moi, pourrait trouver plus facilement piratable que python.

je pense qu'une bonne approche sera invariante échelle et rotation, et ma prochaine étape sera d'étudier des mélanges de gaussiens. (chaque patte pad être le centre d'une gaussienne).

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

je suis sûr que vous en avez assez pour continuer, mais je ne peux pas m'empêcher de suggérer l'utilisation de la méthode de regroupement k-means. k-means est un algorithme de clustering non supervisé qui va vous prendre des données (dans n'importe quel nombre de dimensions - j'arrive à le faire en 3D) et l'organiser en K clusters avec des frontières distinctes. C'est bien ici parce que vous savez exactement combien d'orteils de ces canidés (dû).

en outre, il est mis en œuvre en Scipy qui est vraiment agréable ( http://docs.scipy.org/doc/scipy/reference/cluster.vq.html ).

voici un exemple de ce qu'il peut faire pour résoudre spatialement clusters 3D:

ce que vous voulez faire est un peu différent (2D et inclut des valeurs de pression), mais je pense toujours que vous pourriez donner une chance.

solution du physicien:

Définissez 5 marqueurs paw identifiés par leurs positions X_i et introduisez-les dans des positions aléatoires. Définissez une fonction d'énergie combinant une récompense pour la localisation des marqueurs dans les positions des pattes avec une punition pour le chevauchement des marqueurs; disons:

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

( S(X_i) est la force moyenne en 2x2 carré autour de X_i , alfa est un paramètre à atteindre expérimentalement)

Maintenant temps de faire un peu de Metropolis-Hastings magique:

1. Sélectionnez le repère aléatoire et déplacez-le d'un pixel dans la direction aléatoire.

2. Calculer dE, la différence d'énergie que ce mouvement a causé.

3. Obtenez un numéro aléatoire uniforme de 0-1 et appelez-le R.

4. Si dE<0 ou exp(-beta*dE)>r , accepter le déménagement et passer à 1; sinon, annuler le déménagement et passer à 1.

Cela devrait être répété jusqu'à ce que les marqueurs convergent vers les pattes. Beta contrôle le balayage jusqu'à l'optimisation du compromis, de sorte qu'il doit aussi être optimisé expérimentalement; il peut également être constamment augmenté avec le temps de simulation (recuit simulé).

est une autre approche que j'ai utilisée pour faire quelque chose de similaire pour un grand télescope:

1) rechercher le pixel le plus élevé. Une fois que vous avez cela, cherchez autour de cela pour le meilleur ajustement pour 2x2 (peut-être maximisant la somme 2x2), ou faites un ajustement gaussien 2d à l'intérieur de la sous-région de dire 4x4 centré sur le pixel le plus élevé.

définissez ensuite ces 2x2 pixels que vous avez trouvés à zéro (ou peut-être 3x3) autour du centre de la crête

retourner à 1) et répéter jusqu'à ce que le pic le plus élevé tombe en dessous d'un seuil de bruit, ou vous avez tous les orteils dont vous avez besoin

il est probablement intéressant d'essayer avec les réseaux neuronaux si vous êtes en mesure de créer des données de formation... mais cela nécessite de nombreux échantillons annotés à la main.

une ébauche...

vous voudriez probablement utiliser un algorithme de composants connectés pour isoler chaque région de patte. wiki a une description décente de ceci (avec un certain code) ici: http://en.wikipedia.org/wiki/Connected_Component_Labeling

vous devrez prendre une décision sur l'utilisation de la connectivité 4 ou 8. personnellement, pour la plupart des problèmes, je préfère la 6-connexité. de toute façon, une fois que vous avez séparé chaque "la patte imprimer" en tant que Région connectée, il devrait être assez facile d'itérer à travers la région et de trouver les maxima. une fois que vous avez trouvé les maxima, vous pouvez itérativement agrandir la région jusqu'à ce que vous atteigniez un seuil prédéterminé afin de l'identifier comme un "orteil"donné.

un problème subtil ici est que dès que vous commencez à utiliser des techniques de vision par ordinateur pour identifier quelque chose comme une patte droite/gauche/avant/arrière et vous commencez à regarder les orteils individuels, vous devez commencer à prendre rotations, dérapages et traductions en compte. ceci est accompli grâce à l'analyse de soi-disant "moments". il y a quelques moments différents à considérer dans les applications de vision:

moments centraux: invariant de traduction moments normalisés: invariant d'échelle et de traduction hu moments: traduction, échelle, et invariant de rotation

plus d'informations sur les moments peuvent être trouvées en cherchant" image moments " sur wiki.

peut-être Pouvez-vous utiliser quelque chose comme des modèles de mélange gaussien. Voici un paquet Python pour faire des GMMs (vient de faire une recherche Google) http://www.ar.media.kyoto-u.ac.jp/members/david/softwares/em/

Eh bien, voici quelques code simple et pas terriblement efficace, mais pour cette taille d'un ensemble de données, il est très bien.

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]

j'ai essentiellement juste faire un tableau avec la position de l'en haut à gauche et la somme de chaque carré 2x2 et le Trier par la somme. Je prends alors le carré 2x2 avec la somme la plus élevée hors de question, le mets dans le tableau best , et supprime tous les autres carrés 2x2 qui ont utilisé n'importe quelle partie de ce carré 2x2 vient d'être supprimé.

It semble fonctionner très bien sauf avec la dernière patte (celle avec la plus petite somme sur l'extrême droite dans votre première image), il s'avère qu'il ya deux autres 2x2 éligibles carrés avec une plus grande somme (et ils ont une somme égale à l'autre). L'un d'eux sélectionne encore un carré de votre carré 2x2, mais l'autre est à gauche. Heureusement, par chance, nous voyons à être le choix de plus de ce que vous voulez, mais cela peut demander quelques autres idées pour être utilisé pour obtenir ce que vous voulez vraiment tous temps.

il semble qu'on puisse tricher un peu en utilisant l'algorithme de jetxee. Il trouve les trois premiers orteils bien, et vous devriez être en mesure de deviner où la quatrième est basée sur cela.

problème intéressant. La solution que j'essaierais est la suivante.

1. appliquer un filtre passe-bas, comme convolution avec un masque gaussien 2D. Cela vous donnera un tas de (probablement, mais pas nécessairement à virgule flottante).

2. effectuer une suppression 2D non-maximale en utilisant le rayon approximatif connu de chaque patte (ou pied).

This devrait vous donner les positions maximales sans avoir plusieurs candidats qui sont proches. Juste pour clarifier, le rayon du masque à l'étape 1 devrait également être similaire au rayon utilisé à l'étape 2. Ce rayon peut être sélectionné, ou le vétérinaire pourrait mesurer explicitement à l'avance (il varie selon l'âge/race/etc).

certaines des solutions suggérées (déplacement moyen, réseaux neuronaux, etc.) fonctionneront probablement à un certain degré, mais sont trop compliquées et probablement pas idéal.

je veux juste vous dire qu'il y a une bonne option pour trouver des maxima locaux en images avec python.

from skimage.feature import peak_local_max

ou pour écrémage 0.8.0

from skimage.feature.peak import peak_local_max

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

peut-être une approche naïve est suffisante ici: construire une liste de tous les carrés 2x2 sur votre plan, les ordonner par leur somme (dans l'ordre décroissant).

tout d'abord, sélectionnez le carré le plus apprécié dans votre "liste des pattes". Ensuite, choisir itérativement 4 des meilleurs carrés suivants qui ne se croisent pas avec l'un des carrés précédemment trouvés.

Que faire si vous procédez étape par étape: vous localisez d'abord le maximum global, traitez si nécessaire les points environnants étant donné leur valeur, puis réglez la région trouvée à zéro, et répétez pour la prochaine.

Je ne suis pas sûr que cela réponde à la question, mais il semble que vous pouvez simplement chercher les n plus hauts sommets qui n'ont pas de voisins.

Voici l'essentiel. notez que C'est dans Ruby, mais l'idée doit être claire.

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