935 votes

Détection de crête dans un tableau 2D

Je suis à aider la clinique vétérinaire de mesure de la pression en vertu de l'un des chiens de la patte. J'utilise Python pour mon analyse de données et maintenant je suis coincé en essayant de diviser les pattes dans les (anatomique) sous-régions.

J'ai fait un tableau 2D de chaque patte, qui se compose d'un maximum de valeurs pour chaque capteur qui a été chargé par la patte au fil du temps. Voici un exemple d'une patte, où j'ai utilisé Excel pour tracer les domaines que je veux "détecter". Ce sont 2 par 2 cases autour du capteur avec des maxima locaux, qui, ensemble, ont la plus grande somme.

alt text

J'ai donc essayé quelques tests et tout simplement décider de chercher le maximum de chaque colonne et de la ligne (ne peut pas regarder dans une seule direction à cause de la forme de la patte). Cela semble détecter l'emplacement de la séparer les orteils assez bien, mais il marque également les voisins de capteurs.

alt text

Alors quelle serait la meilleure façon de dire à Python qui de ces maximums sont ceux que je veux?

Remarque: La 2x2 places peuvent se chevauchent pas, car ils doivent être séparés des orteils!

Aussi j'ai pris 2x2 comme une commodité, pas plus avancé solution est la bienvenue, mais je suis simplement un homme mouvement scientifique, donc je ne suis ni un vrai programmeur ou un mathématicien, de sorte s'il vous plaît garder "simple".

Voici une version qui peut être chargé avec des np.loadtxt


Résultats

J'ai donc essayé @jextee de la solution (voir les résultats ci-dessous). Comme vous pouvez le voir, il fonctionne très sur les pattes de devant, mais ça marche moins bien pour les pattes de derrière.

Plus précisément, il ne peut pas reconnaître le petit pic qui est le quatrième orteil. C'est évidemment inhérente au fait que la boucle regarde de haut en bas vers la valeur la plus basse, sans prendre en compte, lorsque cela est.

Quelqu'un sait comment modifier @jextee de l'algorithme, de sorte qu'il pourrait être en mesure de trouver le 4ème orteil trop?

alt text

Puisque je n'ai pas traité d'autres essais encore, je ne peux pas fournir tous les autres échantillons. Mais les données que j'ai donné avant étaient les moyennes de chaque patte. Ce fichier est un tableau avec le maximum de données de 9 pattes dans l'ordre qu'ils entrent en contact avec la plaque.

Cette image montre comment ils sont spatialement répartis sur la plaque.

alt text

Mise à jour:

J'ai mis en place un blog pour toute personne intéressée et j'ai mis un SkyDrive avec toutes les mesures brutes. Donc de toute personne qui demande plus de données: plus de puissance pour vous!


Nouvelle mise à jour:

Ainsi, après l'aide que j'ai eu avec mes questions au sujet de la patte de la détection et de la patte de tri, j'ai finalement été en mesure de vérifier l'orteil de détection pour chaque patte! S'avère, elle ne fonctionne pas si bien dans quoi que ce soit mais les pattes de taille moyenne comme celle de mon propre exemple. Bien sûr, avec le recul, c'est de ma faute pour le choix de la 2x2 de façon arbitraire.

Voici un bel exemple de l'endroit où ça se passe mal: un clou qui est reconnue comme étant un orteil et le talon d'' est tellement large, il est reconnu deux fois!

alt text

La patte est trop grand, afin de prendre une taille 2x2 ne se chevauchent pas, les causes de certains pieds pour être détecté deux fois. À l'inverse, dans les petits chiens, il ne parvient pas à trouver un 5ème orteil, ce qui je pense est causé par la 2x2 domaine étant trop grand.

Après avoir essayer la solution actuelle sur toutes mes mesures je suis venu à la stupéfiante conclusion que, pour presque tous mes petits chiens, il n'a pas trouver un 5ème orteil et que dans plus de 50% de l'impact pour les chiens de grande taille, il trouverait plus!

Donc clairement, j'ai besoin de la changer. Ma part, je crois, était le changement de la taille de l' neighborhood de quelque chose de plus petit pour les petits chiens et les grands pour les grands chiens. Mais generate_binary_structure ne me laisse pas changer la taille de la matrice.

Donc, je suis en espérant que quelqu'un d'autre a une meilleure suggestion pour localiser les orteils, peut-être d'avoir la zone des orteils à l'échelle avec la patte de la taille?

363voto

Ivan Points 4558

J'ai détecté les sommets à l'aide d'un maximum local de filtre. Voici le résultat sur votre premier jeu de données de 4 pattes: Peaks detection result

J'ai aussi couru le deuxième ensemble de données de 9 pattes et il a travaillé en tant que bien.

Voici comment faire:

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

Tout ce que vous devez faire est d'utiliser scipy.ndimage.mesures.l'étiquette sur le masque à l'étiquette de tous les objets distincts. Ensuite, vous serez en mesure de jouer avec eux individuellement.

Notez que la méthode fonctionne bien parce que le fond n'est pas bruyant. Si c'était le cas, vous permettrait de détecter un tas d'autres indésirables sommets en arrière-plan. Un autre facteur important est la taille du voisinage. Vous aurez besoin de l'ajuster si la taille maximale de changements (le devrait rester à peu près proportionnelle).

55voto

sastanin Points 16061

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 la plus délicate est de calculer la somme de tous les carrés de 2 x 2. Je suppose que vous avez besoin de tous d'entre eux, alors il pourrait y avoir un certain chevauchement. J'ai utilisé des tranches de couper le premier/dernier les colonnes et les lignes de l'original tableau 2D, puis de chevauchement et de calcul de ces montants.

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

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

Maintenant, imaginez que vous empilez-les les unes sur les autres et la somme des éléments à la même position. Ces sommes seront exactement les mêmes sommes sur la 2x2 places avec le coin en haut à gauche dans la même position:

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

Lorsque vous avez le sommes plus 2x2 places, vous pouvez utiliser max pour trouver le maximum, ou sortou sorted pour trouver les pics.

Pour rappeler les positions des pics j'chaque couple de valeur (de la somme) avec sa position ordinale dans une stagnation de la matrice (voir zip). Puis-je calculer la ligne/colonne de la position encore quand j'ai imprimer les résultats.

Notes

- Je le droit de la 2x2 places à se chevaucher. Version modifiée d'un filtre certains d'entre eux tels que seuls les non-cumul des carrés apparaissent dans les résultats.

Le choix de doigts (une idée)

Un autre problème est de savoir comment choisir ce qui est susceptible d'être les doigts de tous les sommets. J'ai une idée qui peut ou peut ne pas fonctionner. Je n'ai pas de temps pour la mettre en œuvre dès maintenant, il suffit donc de pseudo-code.

J'ai remarqué que si le front de doigts sur presque un cercle parfait, l'arrière doigt doit être à l'intérieur de ce cercle. Aussi, le front, les doigts sont plus ou moins espacés de façon égale. On peut essayer d'utiliser ces propriétés heuristiques pour détecter les doigts.

Le 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 force brute approche. 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 arrière doigt, alors 3960 cas à évaluer pour chaque patte.

35voto

CakeMaster Points 507

C'est un problème d'enregistrement de l'image. La stratégie générale est:

  • Avoir un exemple connu, ou une sorte de préalable sur les données.
  • Ajuster vos données à l'exemple, ou adapter l'exemple à vos données.
  • Il aide si vos données sont à peu près alignés dans la première place.

Voici une rude approche, "la chose la plus stupide qui pourraient éventuellement travailler":

  • Commencer avec cinq orteils coordonnées à peu près dans le lieu que vous attendez.
  • Avec chacun, de façon itérative, de monter au sommet de la colline. c'est à dire, compte tenu de la position, de se déplacer à un maximum de voisins du pixel, si sa valeur est supérieure à pixel actuel. Arrêter lorsque votre orteil coordonnées ont cessé de bouger.

Pour contrer le problème d'orientation, vous pourriez avoir 8 ou si les réglages initiaux de la base directions (nord, Nord-Est, etc). Exécuter individuellement et jetez tous les résultats au cas où deux ou plusieurs orteils retrouver à la même pixel. Je vais réfléchir à ce un peu plus, mais ce genre de chose est toujours en cours d'étude dans le traitement de l'image - il n'y a pas de bonnes réponses!

Légèrement plus complexe idée: (pondéré a) K-means. Ce n'est pas que mauvais.

  • Commencer avec cinq orteils coordonnées, mais maintenant ce sont des "cluster centres".

Puis itération jusqu'à convergence:

  • Attribuer à chaque pixel de l'amas le plus proche (il suffit de faire une liste pour chaque cluster).
  • Calculer le centre de masse de chaque cluster. Pour chaque cluster, c'est: Somme(coordonnées * valeur d'intensité)/Somme(coordonner)
  • Le déplacement de chaque cluster pour le nouveau centre de masse.

Cette méthode sera presque certainement vous donner de bien meilleurs résultats, et vous obtenez la masse de chaque cluster, qui peuvent aider à identifier les orteils.

(Encore une fois, vous avez spécifié le nombre de clusters à l'avant. Avec le regroupement, 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 cluster de rayon et de voir combien vous vous retrouvez avec. Un exemple de ce dernier est mean-shift.)

Désolé pour le manque de détails de mise en œuvre ou d'autres détails. Je voudrais le code de cette place, mais j'ai une date limite. Si rien d'autre n'a fonctionné la semaine prochaine laissez-moi savoir et je vais vous donner un coup de feu.

18voto

dmckee Points 50318

Ce problème a été étudié en profondeur par les physiciens. Il y a une bonne mise en œuvre de RACINE. Regardez les TSpectrum classes (surtout TSpectrum2 pour votre cas) et de la documentation pour eux.

Références:

  1. M. Morhac et al.: Arrière-plan de l'élimination méthodes pour multidimensionnelle coïncidence gamma-ray spectres. Nucléaire, Méthodes et Instruments 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.: L'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 à une souscription de NIM:

12voto

ChrisC Points 1026

Juste un couple des idées sur le dessus de ma tête:

  • prendre le gradient (dérivé) de l'analyse, de voir si cela élimine les faux appels
  • prendre le maximum des maxima locaux

Vous pouvez également jeter un oeil à OpenCV, il a un assez décent, l'API Python et peut avoir certaines fonctions que vous trouvez utiles.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X