Comment trier mes pattes?

Dans ma question précédente, j'ai eu une excellente réponse qui m'a aidé à détecter où une patte a heurté une plaque de pression, mais maintenant j'ai du mal à relier ces résultats à leurs pattes correspondantes:

J'ai annoté manuellement les pattes (RF = avant droit, RH = arrière droit, LF = avant gauche, LH = arrière gauche).

Comme vous pouvez le voir, il y a clairement un motif répétitif et il revient dans presque toutes les mesures. Voici un lien vers une présentation de 6 essais annotés manuellement.

Ma première pensée était d'utiliser l'heuristique pour faire le tri, comme:

• Il y a un rapport de poids d'environ 60 à 40% entre les pattes avant et arrière;
• Les pattes postérieures sont généralement plus petites en surface;
• Les pattes sont (souvent) spatialement divisées en gauche et droite.

Cependant, je suis un peu sceptique quant à mes heuristiques, car elles échoueraient sur moi dès que je rencontrerais une variation à laquelle je n'avais pas pensé. Ils ne pourront pas non plus faire face aux mesures de chiens boiteux, qui ont probablement leurs propres règles.

De plus, l'annotation suggérée par Joe est parfois foirée et ne prend pas en compte l'apparence réelle de la patte.

Sur la base des réponses que j'ai reçues à ma question sur la détection des pics dans la patte , j'espère qu'il existe des solutions plus avancées pour trier les pattes. D'autant que la répartition de la pression et sa progression sont différentes pour chaque patte distincte, presque comme une empreinte digitale. J'espère qu'il existe une méthode qui peut utiliser cela pour regrouper mes pattes, plutôt que de simplement les trier par ordre d'occurrence.

Je cherche donc une meilleure façon de trier les résultats avec leur patte correspondante.

Pour tous ceux qui sont à la hauteur du défi, j'ai mariné un dictionnaire avec tous les tableaux en tranches qui contiennent les données de pression de chaque patte (regroupées par mesure) et la tranche qui décrit leur emplacement (emplacement sur la plaque et dans le temps).

Pour clarifier: walk_sliced_data est un dictionnaire qui contient ['ser_3', 'ser_2', 'sel_1', 'sel_2', 'ser_1', 'sel_3'], qui sont les noms des mesures. Chaque mesure contient un autre dictionnaire, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] (exemple de «sel_1») qui représente les impacts extraits.

Notez également que les «faux» impacts, comme lorsque la patte est partiellement mesurée (dans l'espace ou dans le temps), peuvent être ignorés. Ils ne sont utiles que parce qu'ils peuvent aider à reconnaître un modèle, mais ne seront pas analysés.

Et pour toute personne intéressée, je tiens un blog avec toutes les mises à jour concernant le projet!

Bien! J'ai enfin réussi à faire fonctionner quelque chose de manière cohérente! Ce problème m'a attiré pendant plusieurs jours ... Des trucs amusants! Désolé pour la longueur de cette réponse, mais je dois élaborer un peu sur certaines choses ... (Bien que je puisse établir un record pour la plus longue réponse de stackoverflow non-spam jamais!)

En passant , j'utilise l'ensemble de données complet vers lequel Ivo a fourni un lien dans sa question initiale . Il s'agit d'une série de fichiers rar (un par chien) contenant chacun plusieurs exécutions d'expériences différentes stockées sous forme de tableaux ascii. Plutôt que d'essayer de copier-coller des exemples de code autonomes dans cette question, voici un référentiel mercurial bitbucket avec un code complet et autonome. Vous pouvez le cloner avec

hg clone https://[email protected]/joferkington/paw-analysis

Aperçu

Il y a essentiellement deux façons d'aborder le problème, comme vous l'avez noté dans votre question. Je vais en fait utiliser les deux de différentes manières.

1. Utilisez l'ordre (temporel et spatial) des impacts de patte pour déterminer quelle patte est laquelle.
2. Essayez d'identifier le "pawprint" uniquement en fonction de sa forme.

Fondamentalement, la première méthode fonctionne avec les pattes du chien qui suit le modèle trapézoïdal montré dans la question d'Ivo ci-dessus, mais échoue chaque fois que les pattes ne suivent pas ce modèle. Il est assez facile de détecter par programme quand cela ne fonctionne pas.

Par conséquent, nous pouvons utiliser les mesures là où cela a fonctionné pour construire un ensemble de données d'entraînement (d'environ 2000 impacts de pattes de ~ 30 chiens différents) pour reconnaître quelle patte est laquelle, et le problème se réduit à une classification supervisée (avec quelques rides supplémentaires. .. La reconnaissance d'image est un peu plus difficile qu'un problème de classification supervisée "normal").

Analyse de modèle

Pour élaborer sur la première méthode, lorsqu'un chien marche (ne court pas!) Normalement (ce que certains de ces chiens peuvent ne pas être), nous nous attendons à ce que les pattes aient un impact dans l'ordre suivant: avant gauche, arrière droit, avant droit, arrière gauche , Avant gauche, etc. Le motif peut commencer par la patte avant gauche ou avant droite.

Si c'était toujours le cas, on pourrait simplement trier les impacts par temps de contact initial et utiliser un modulo 4 pour les regrouper par patte.

Cependant, même lorsque tout est "normal", cela ne fonctionne pas. Cela est dû à la forme trapézoïdale du motif. Une patte arrière tombe spatialement derrière la patte avant précédente.

Par conséquent, l'impact de la patte arrière après l'impact initial de la patte avant tombe souvent de la plaque du capteur et n'est pas enregistré. De même, le dernier impact de patte n'est souvent pas la patte suivante dans la séquence, car l'impact de la patte avant qu'il ne se produise sur la plaque du capteur et n'a pas été enregistré.

Néanmoins, nous pouvons utiliser la forme du motif d'impact de la patte pour déterminer quand cela s'est produit et si nous avons commencé avec une patte avant gauche ou droite. (J'ignore en fait les problèmes avec le dernier impact ici. Ce n'est pas trop difficile de l'ajouter, cependant.)

def group_paws(data_slices, time):   
    # Sort slices by initial contact time
    data_slices.sort(key=lambda s: s[-1].start)

    # Get the centroid for each paw impact...
    paw_coords = []
    for x,y,z in data_slices:
        paw_coords.append([(item.stop + item.start) / 2.0 for item in (x,y)])
    paw_coords = np.array(paw_coords)

    # Make a vector between each sucessive impact...
    dx, dy = np.diff(paw_coords, axis=0).T

    #-- Group paws -------------------------------------------
    paw_code = {0:'LF', 1:'RH', 2:'RF', 3:'LH'}
    paw_number = np.arange(len(paw_coords))

    # Did we miss the hind paw impact after the first 
    # front paw impact? If so, first dx will be positive...
    if dx[0] > 0: 
        paw_number[1:] += 1

    # Are we starting with the left or right front paw...
    # We assume we're starting with the left, and check dy[0].
    # If dy[0] > 0 (i.e. the next paw impacts to the left), then
    # it's actually the right front paw, instead of the left.
    if dy[0] > 0: # Right front paw impact...
        paw_number += 2

    # Now we can determine the paw with a simple modulo 4..
    paw_codes = paw_number % 4
    paw_labels = [paw_code[code] for code in paw_codes]

    return paw_labels

Malgré tout cela, cela ne fonctionne souvent pas correctement. De nombreux chiens de l'ensemble de données complet semblent courir, et les impacts de pattes ne suivent pas le même ordre temporel que lorsque le chien marche. (Ou peut-être que le chien a juste de graves problèmes de hanche ...)

Heureusement, nous pouvons toujours détecter par programme si les impacts des pattes suivent ou non notre schéma spatial attendu:

def paw_pattern_problems(paw_labels, dx, dy):
    """Check whether or not the label sequence "paw_labels" conforms to our
    expected spatial pattern of paw impacts. "paw_labels" should be a sequence
    of the strings: "LH", "RH", "LF", "RF" corresponding to the different paws"""
    # Check for problems... (This could be written a _lot_ more cleanly...)
    problems = False
    last = paw_labels[0]
    for paw, dy, dx in zip(paw_labels[1:], dy, dx):
        # Going from a left paw to a right, dy should be negative
        if last.startswith('L') and paw.startswith('R') and (dy > 0):
            problems = True
            break
        # Going from a right paw to a left, dy should be positive
        if last.startswith('R') and paw.startswith('L') and (dy < 0):
            problems = True
            break
        # Going from a front paw to a hind paw, dx should be negative
        if last.endswith('F') and paw.endswith('H') and (dx > 0):
            problems = True
            break
        # Going from a hind paw to a front paw, dx should be positive
        if last.endswith('H') and paw.endswith('F') and (dx < 0):
            problems = True
            break
        last = paw
    return problems

Par conséquent, même si la classification spatiale simple ne fonctionne pas tout le temps, nous pouvons déterminer quand elle fonctionne avec une confiance raisonnable.

Ensemble de données de formation

À partir des classifications basées sur des modèles où cela a fonctionné correctement, nous pouvons créer un très grand ensemble de données d'entraînement de pattes correctement classées (~ 2400 impacts de pattes de 32 chiens différents!).

Nous pouvons maintenant commencer à regarder à quoi ressemble une patte avant gauche "moyenne", etc.

Pour ce faire, nous avons besoin d'une sorte de "métrique de patte" qui est la même dimensionnalité pour n'importe quel chien. (Dans l'ensemble de données complet, il y a à la fois des chiens très grands et très petits!) Une empreinte de patte d'un élan irlandais sera à la fois beaucoup plus large et beaucoup plus "lourde" qu'une empreinte de patte d'un caniche jouet. Nous devons redimensionner chaque empreinte de patte pour que a) elles aient le même nombre de pixels, et b) les valeurs de pression soient standardisées. Pour ce faire, j'ai rééchantillonné chaque empreinte de patte sur une grille 20x20 et mis à l'échelle les valeurs de pression en fonction de la valeur de pression maximale, minimale et moyenne pour l'impact de la patte.

def paw_image(paw):
    from scipy.ndimage import map_coordinates
    ny, nx = paw.shape

    # Trim off any "blank" edges around the paw...
    mask = paw > 0.01 * paw.max()
    y, x = np.mgrid[:ny, :nx]
    ymin, ymax = y[mask].min(), y[mask].max()
    xmin, xmax = x[mask].min(), x[mask].max()

    # Make a 20x20 grid to resample the paw pressure values onto
    numx, numy = 20, 20
    xi = np.linspace(xmin, xmax, numx)
    yi = np.linspace(ymin, ymax, numy)
    xi, yi = np.meshgrid(xi, yi)  

    # Resample the values onto the 20x20 grid
    coords = np.vstack([yi.flatten(), xi.flatten()])
    zi = map_coordinates(paw, coords)
    zi = zi.reshape((numy, numx))

    # Rescale the pressure values
    zi -= zi.min()
    zi /= zi.max()
    zi -= zi.mean() #<- Helps distinguish front from hind paws...
    return zi

Après tout cela, nous pouvons enfin jeter un œil à ce à quoi ressemble une patte moyenne avant gauche, arrière droite, etc. Notez que cela est en moyenne sur plus de 30 chiens de tailles très différentes, et nous semblons obtenir des résultats cohérents!

Cependant, avant de faire une analyse sur ceux-ci, nous devons soustraire la moyenne (la patte moyenne pour toutes les pattes de tous les chiens).

Nous pouvons maintenant analyser les différences par rapport à la moyenne, qui sont un peu plus faciles à reconnaître:

Reconnaissance des pattes basée sur l'image

Ok ... Nous avons enfin un ensemble de modèles contre lesquels nous pouvons commencer à essayer de faire correspondre les pattes. Chaque patte peut être traitée comme un vecteur à 400 dimensions (renvoyé par la paw_imagefonction) qui peut être comparé à ces quatre vecteurs à 400 dimensions.

Malheureusement, si nous utilisons juste un algorithme de classification supervisée "normal" (c'est-à-dire trouver lequel des 4 motifs est le plus proche d'une empreinte de patte particulière en utilisant une simple distance), cela ne fonctionne pas de manière cohérente. En fait, cela ne fait pas beaucoup mieux que le hasard aléatoire sur l'ensemble de données d'entraînement.

C'est un problème courant dans la reconnaissance d'images. En raison de la dimensionnalité élevée des données d'entrée et de la nature quelque peu «floue» des images (c'est-à-dire que les pixels adjacents ont une covariance élevée), le simple fait de regarder la différence entre une image et une image modèle ne donne pas une très bonne mesure de la similitude de leurs formes.

Pattes propres

Pour contourner cela, nous devons construire un ensemble de "pattes propres" (tout comme les "faces propres" dans la reconnaissance faciale), et décrire chaque empreinte de patte comme une combinaison de ces pattes propres. Ceci est identique à l'analyse des composants principaux et fournit essentiellement un moyen de réduire la dimensionnalité de nos données, de sorte que la distance est une bonne mesure de la forme.

Parce que nous avons plus d'images d'entraînement que de dimensions (2400 contre 400), il n'est pas nécessaire de faire une algèbre linéaire "sophistiquée" pour la vitesse. Nous pouvons travailler directement avec la matrice de covariance de l'ensemble de données d'apprentissage:

def make_eigenpaws(paw_data):
    """Creates a set of eigenpaws based on paw_data.
    paw_data is a numdata by numdimensions matrix of all of the observations."""
    average_paw = paw_data.mean(axis=0)
    paw_data -= average_paw

    # Determine the eigenvectors of the covariance matrix of the data
    cov = np.cov(paw_data.T)
    eigvals, eigvecs = np.linalg.eig(cov)

    # Sort the eigenvectors by ascending eigenvalue (largest is last)
    eig_idx = np.argsort(eigvals)
    sorted_eigvecs = eigvecs[:,eig_idx]
    sorted_eigvals = eigvals[:,eig_idx]

    # Now choose a cutoff number of eigenvectors to use 
    # (50 seems to work well, but it's arbirtrary...
    num_basis_vecs = 50
    basis_vecs = sorted_eigvecs[:,-num_basis_vecs:]

    return basis_vecs

Ce basis_vecssont les "pattes propres".

Pour les utiliser, nous dotons simplement (c.-à-d. Multiplication de matrice) chaque image de patte (comme un vecteur à 400 dimensions, plutôt qu'une image 20x20) avec les vecteurs de base. Cela nous donne un vecteur à 50 dimensions (un élément par vecteur de base) que nous pouvons utiliser pour classer l'image. Au lieu de comparer une image 20x20 à l'image 20x20 de chaque patte «modèle», nous comparons l'image transformée en 50 dimensions à chaque patte en modèle transformée en 50 dimensions. Ceci est beaucoup moins sensible aux petites variations dans la façon exacte dont chaque orteil est positionné, etc., et réduit fondamentalement la dimensionnalité du problème aux seules dimensions pertinentes.

Classification des pattes basée sur la patte propre

Maintenant, nous pouvons simplement utiliser la distance entre les vecteurs à 50 dimensions et les vecteurs "gabarit" pour chaque jambe pour classer quelle patte est laquelle:

codebook = np.load('codebook.npy') # Template vectors for each paw
average_paw = np.load('average_paw.npy')
basis_stds = np.load('basis_stds.npy') # Needed to "whiten" the dataset...
basis_vecs = np.load('basis_vecs.npy')
paw_code = {0:'LF', 1:'RH', 2:'RF', 3:'LH'}
def classify(paw):
    paw = paw.flatten()
    paw -= average_paw
    scores = paw.dot(basis_vecs) / basis_stds
    diff = codebook - scores
    diff *= diff
    diff = np.sqrt(diff.sum(axis=1))
    return paw_code[diff.argmin()]

Voici quelques-uns des résultats:

Problèmes restants

Il y a encore des problèmes, en particulier avec les chiens trop petits pour faire une empreinte de patte claire ... (Cela fonctionne mieux avec les grands chiens, car les orteils sont plus clairement séparés à la résolution du capteur.) De plus, les empreintes de pattes partielles ne sont pas reconnues avec cela. système, alors qu'ils peuvent l'être avec le système à motif trapézoïdal.

Cependant, comme l'analyse des pattes propres utilise intrinsèquement une métrique de distance, nous pouvons classer les pattes dans les deux sens et revenir au système basé sur des motifs trapézoïdaux lorsque la plus petite distance de l'analyse des pattes propres par rapport au «livre de codes» dépasse un certain seuil. Cependant, je n'ai pas encore implémenté cela.

Ouf ... C'était long! Mon chapeau est à Ivo pour avoir posé une question aussi amusante!

En utilisant les informations purement basées sur la durée, je pense que vous pourriez appliquer des techniques de modélisation cinématique; à savoir cinématique inverse . Combiné avec l'orientation, la longueur, la durée et le poids total, cela donne un certain niveau de périodicité qui, j'espère, pourrait être la première étape pour essayer de résoudre votre problème de "tri des pattes".

Toutes ces données pourraient être utilisées pour créer une liste de polygones bornés (ou tuples), que vous pourriez utiliser pour trier par taille de pas puis par paw-ness [index].

Pouvez-vous demander au technicien qui exécute le test de saisir manuellement la première patte (ou les deux premières)? Le processus pourrait être:

• Montrez à la technologie l'ordre des étapes de l'image et demandez-lui d'annoter la première patte.
• Étiquetez les autres pattes en fonction de la première patte et permettez au technicien d'apporter des corrections ou de relancer le test. Cela permet aux chiens boiteux ou à 3 pattes.