Bagaimana cara mengurutkan kaki saya?

121

Dalam pertanyaan saya sebelumnya, saya mendapat jawaban luar biasa yang membantu saya mendeteksi di mana kaki menyentuh pelat tekanan, tetapi sekarang saya berjuang untuk menghubungkan hasil ini ke kaki yang sesuai:

alt teks

Saya secara manual menganotasi cakarnya (RF = kanan depan, RH = kanan belakang, LF = kiri depan, LH = kiri belakang).

Seperti yang Anda lihat, jelas ada pola yang berulang dan muncul kembali di hampir setiap pengukuran. Berikut link ke presentasi 6 percobaan yang dijelaskan secara manual.

Pikiran awal saya adalah menggunakan heuristik untuk melakukan penyortiran, seperti:

  • Ada rasio ~ 60-40% dalam menahan beban antara kaki depan dan belakang;
  • Cakar belakang umumnya lebih kecil di permukaan;
  • Cakar (sering) terbagi secara spasial di kiri dan kanan.

Namun, saya agak skeptis tentang heuristik saya, karena mereka akan gagal pada saya segera setelah saya menemukan variasi yang tidak saya pikirkan. Mereka juga tidak akan bisa mengatasi pengukuran dari anjing lumpuh, yang mungkin memiliki aturan sendiri.

Selain itu, anotasi yang disarankan oleh Joe kadang-kadang menjadi kacau dan tidak memperhitungkan seperti apa sebenarnya cakarnya.

Berdasarkan jawaban yang saya terima atas pertanyaan saya tentang deteksi puncak di kaki , saya berharap ada solusi yang lebih canggih untuk mengurutkan kaki. Terutama karena distribusi tekanan dan perkembangannya berbeda untuk setiap kaki yang terpisah, hampir seperti sidik jari. Saya harap ada metode yang dapat menggunakan ini untuk mengelompokkan kaki saya, daripada hanya mengurutkannya dalam urutan kejadian.

alt teks

Jadi saya mencari cara yang lebih baik untuk mengurutkan hasil dengan kaki yang sesuai.

Bagi siapa pun yang menghadapi tantangan, saya telah membuat acar kamus dengan semua larik yang diiris yang berisi data tekanan setiap kaki (dibundel dengan pengukuran) dan irisan yang menggambarkan lokasi mereka (lokasi di piring dan dalam waktu).

Untuk memperjelas: walk_sliced_data adalah kamus yang berisi ['ser_3', 'ser_2', 'sel_1', 'sel_2', 'ser_1', 'sel_3'], yang merupakan nama-nama pengukuran. Setiap pengukuran berisi kamus lain, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] (contoh dari 'sel_1') yang mewakili dampak yang diekstraksi.

Perhatikan juga bahwa dampak 'palsu', seperti di mana kaki diukur sebagian (dalam ruang atau waktu) dapat diabaikan. Mereka hanya berguna karena dapat membantu mengenali pola, tetapi tidak akan dianalisis.

Dan bagi siapa pun yang tertarik, saya menyimpan blog dengan semua pembaruan terkait proyek!

Ivo Flipse
sumber
1
Ya, pendekatan yang saya gunakan tidak cukup berhasil. Hanya untuk menguraikan, pendekatan yang saya gunakan adalah dengan hanya memesan dampak, dan menganggap bahwa kaki pertama yang disentuh sama dengan kaki ke-5 untuk disentuh, dan seterusnya. (mis. pesan dampak dan gunakan modulo 4). Masalahnya adalah terkadang kaki belakang menyentuh bantalan sensor setelah kaki pertama mendarat. Dalam hal ini, kaki pertama yang menabrak sama dengan kaki keempat atau ketiga yang menabrak. Semoga ini masuk akal.
Joe Kington
1
Apakah saya akan menafsirkan gambar dengan benar karena salah satu jari kaki belakang memberikan tekanan yang jauh lebih sedikit daripada yang lain? Juga tampak bahwa jari kaki selalu mengarah ke 'dalam' yaitu ke arah pusat massa anjing. Bisakah Anda memasukkan itu sebagai heuristik?
Thomas Langston
1
Saya akui keterampilan pemrosesan gambar saya yang terbatas agak berkarat, tetapi apakah mudah untuk mengambil gradien paling curam dari bantalan tengah besar di setiap kaki? Tampaknya sudut paling tidak curam akan sangat membantu (contoh gambar tangan untuk kaki yang diposting: imgur.com/y2wBC imgur.com/yVqVU imgur.com/yehOc imgur.com/q0tcD )
pengguna470379
Bisakah Anda menjelaskan dengan baik bagaimana data di walk_sliced_dataterstruktur? Saya melihat kamus kamus array 3D. Jika saya memperbaiki dimensi ketiga dan memplot dua yang pertama sebagai gambar, saya rasa saya melihat cakar.
Steve Tjoa
@ Thomas, ya setiap kaki dimuat dengan jelas dengan cara yang berbeda. Saya tahu apa yang saya ingin program itu lakukan, tetapi saya tidak tahu bagaimana memprogramnya ... @Steve, saya menambahkan klarifikasi di bagian bawah :-)
Ivo Flipse

Jawaban:

123

Baik! Saya akhirnya berhasil mendapatkan sesuatu yang bekerja secara konsisten! Masalah ini menarik saya selama beberapa hari ... Hal-hal menyenangkan! Maaf untuk panjangnya jawaban ini, tetapi saya perlu menjelaskan sedikit tentang beberapa hal ... (Meskipun saya dapat membuat rekor untuk jawaban stackoverflow non-spam terpanjang yang pernah ada!)

Sebagai catatan tambahan, saya menggunakan kumpulan data lengkap yang ditautkan oleh Ivo dalam pertanyaan aslinya . Ini adalah serangkaian file rar (satu per anjing) yang masing-masing berisi beberapa percobaan berbeda yang disimpan sebagai array ascii. Daripada mencoba menyalin-tempel contoh kode yang berdiri sendiri ke dalam pertanyaan ini, berikut adalah repositori mercurial bitbucket dengan kode lengkap yang berdiri sendiri. Anda dapat mengkloningnya dengan

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


Gambaran

Pada dasarnya ada dua cara untuk mendekati masalah, seperti yang Anda catat dalam pertanyaan Anda. Saya sebenarnya akan menggunakan keduanya dengan cara yang berbeda.

  1. Gunakan urutan (temporal dan spasial) tumbukan kaki untuk menentukan kaki yang mana.
  2. Cobalah untuk mengidentifikasi "jejak kaki" hanya berdasarkan bentuknya.

Pada dasarnya, metode pertama bekerja dengan cakar anjing mengikuti pola seperti trapesium yang ditunjukkan pada pertanyaan Ivo di atas, tetapi gagal jika cakarnya tidak mengikuti pola tersebut. Ini cukup mudah untuk dideteksi secara terprogram ketika itu tidak berfungsi.

Oleh karena itu, kita dapat menggunakan pengukuran di mana ia bekerja untuk membangun set data pelatihan (dari ~ 2000 dampak kaki dari ~ 30 anjing yang berbeda) untuk mengenali kaki mana, dan masalahnya berkurang ke klasifikasi yang diawasi (Dengan beberapa kerutan tambahan. .. Pengenalan gambar sedikit lebih sulit daripada masalah klasifikasi terbimbing "normal").


Analisis Pola

Untuk menguraikan metode pertama, ketika seekor anjing berjalan (tidak berlari!) Secara normal (yang mungkin tidak dilakukan oleh beberapa anjing ini), kami memperkirakan cakar akan menabrak dalam urutan: Kiri Depan, Kanan Belakang, Kanan Depan, Kiri Belakang , Kiri Depan, dll. Polanya dapat dimulai dengan kaki kanan depan atau kiri depan.

Jika ini selalu terjadi, kita cukup mengurutkan dampak dengan waktu kontak awal dan menggunakan modulo 4 untuk mengelompokkannya dengan kaki.

Urutan Dampak Normal

Namun, meskipun semuanya "normal", ini tidak berhasil. Ini karena pola bentuknya yang seperti trapesium. Cakar belakang secara spasial berada di belakang cakar depan sebelumnya.

Oleh karena itu, tumbukan kaki belakang setelah benturan kaki depan sering kali jatuh dari pelat sensor, dan tidak terekam. Demikian pula, benturan kaki terakhir sering kali bukan pukulan kaki berikutnya dalam urutan, karena benturan kaki sebelum terjadi dari pelat sensor dan tidak direkam.

Hind Paw yang terlewat

Meskipun demikian, kita dapat menggunakan bentuk pola tumbukan kaki untuk menentukan kapan hal ini terjadi, dan apakah kita telah memulai dengan kaki depan kiri atau kanan. (Saya sebenarnya mengabaikan masalah dengan dampak terakhir di sini. Namun, tidak terlalu sulit untuk menambahkannya.)

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

Terlepas dari semua ini, sering kali tidak berfungsi dengan benar. Banyak anjing dalam kumpulan data lengkap tampak berlari, dan dampak cakar tidak mengikuti urutan temporal yang sama seperti saat anjing berjalan. (Atau mungkin anjing itu hanya memiliki masalah pinggul yang parah ...)

Urutan Dampak Abnormal

Untungnya, kami masih dapat mendeteksi secara programatik apakah dampak kaki mengikuti pola spasial yang kami harapkan atau tidak:

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

Oleh karena itu, meskipun klasifikasi spasial sederhana tidak berfungsi sepanjang waktu, kami dapat menentukan kapan klasifikasi tersebut berfungsi dengan keyakinan yang wajar.

Set Data Pelatihan

Dari klasifikasi berbasis pola yang berfungsi dengan benar, kita dapat membuat kumpulan data pelatihan yang sangat besar dari kaki yang diklasifikasikan dengan benar (~ 2400 dampak kaki dari 32 anjing yang berbeda!).

Sekarang kita dapat mulai melihat seperti apa bentuk kaki kiri depan "rata-rata", dll.

Untuk melakukan ini, kita memerlukan semacam "metrik kaki" yang memiliki dimensi yang sama untuk anjing mana pun. (Dalam kumpulan data lengkap, ada anjing yang sangat besar dan sangat kecil!) Cetakan kaki dari elkhound Irlandia akan jauh lebih lebar dan jauh "lebih berat" daripada cetakan kaki dari pudel mainan. Kita perlu mengubah skala setiap cetakan kaki sehingga a) mereka memiliki jumlah piksel yang sama, dan b) nilai tekanan distandarisasi. Untuk melakukan ini, saya mencontoh ulang setiap cetakan kaki ke kisi 20x20 dan menskalakan ulang nilai tekanan berdasarkan nilai tekanan maksimum, mininum, dan rata-rata untuk dampak kaki.

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

Setelah semua ini, akhirnya kita bisa melihat seperti apa kaki kiri depan, belakang kanan, dll. Perhatikan bahwa ini dirata-ratakan pada> 30 anjing dengan ukuran yang sangat berbeda, dan kami tampaknya mendapatkan hasil yang konsisten!

Cakar Rata-rata

Namun, sebelum kita melakukan analisis apa pun tentang ini, kita perlu mengurangi mean (kaki rata-rata untuk semua kaki semua anjing).

Kaki Berarti

Sekarang kita dapat menganalisis perbedaan dari mean, yang sedikit lebih mudah dikenali:

Cakar Diferensial

Pengenalan Kaki Berbasis Gambar

Oke ... Akhirnya kita memiliki serangkaian pola yang bisa kita coba untuk mencocokkan cakarnya. Setiap kaki dapat diperlakukan sebagai vektor 400 dimensi (dikembalikan oleh paw_imagefungsi) yang dapat dibandingkan dengan empat vektor 400 dimensi ini.

Sayangnya, jika kita hanya menggunakan algoritma klasifikasi terbimbing "normal" (yaitu menemukan pola mana dari 4 pola yang paling dekat dengan cetakan kaki tertentu menggunakan jarak sederhana), itu tidak bekerja secara konsisten. Faktanya, ini tidak jauh lebih baik daripada peluang acak pada set data pelatihan.

Ini adalah masalah umum dalam pengenalan gambar. Karena dimensi tinggi dari data masukan, dan sifat gambar yang agak "kabur" (yaitu piksel yang berdekatan memiliki kovarian yang tinggi), hanya melihat perbedaan gambar dari gambar template tidak memberikan ukuran yang sangat baik untuk kesamaan bentuk mereka.

Eigenpaws

Untuk menyiasati hal ini kita perlu membangun satu set "eigenpaws" (seperti "eigenfaces" dalam pengenalan wajah), dan mendeskripsikan setiap cetakan kaki sebagai kombinasi dari eigenpaws ini. Ini identik dengan analisis komponen utama, dan pada dasarnya menyediakan cara untuk mengurangi dimensi data kita, sehingga jarak adalah ukuran bentuk yang baik.

Karena kita memiliki lebih banyak gambar latihan daripada dimensi (2400 vs 400), tidak perlu menggunakan aljabar linier "mewah" untuk kecepatan. Kita dapat bekerja secara langsung dengan matriks kovarians dari kumpulan data pelatihan:

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

Ini basis_vecsadalah "eigenpaws".

Eigenpaws

Untuk menggunakan ini, kita cukup memberi titik (yaitu perkalian matriks) setiap gambar kaki (sebagai vektor 400 dimensi, bukan gambar 20x20) dengan vektor basis. Ini memberi kita vektor 50 dimensi (satu elemen per vektor basis) yang dapat kita gunakan untuk mengklasifikasikan gambar. Alih-alih membandingkan gambar 20x20 dengan gambar 20x20 dari setiap kaki "kerangka", kami membandingkan gambar 50 dimensi yang diubah dengan setiap kaki kerangka yang diubah 50 dimensi. Ini jauh kurang sensitif terhadap variasi kecil dalam bagaimana tepatnya setiap jari kaki diposisikan, dll, dan pada dasarnya mengurangi dimensi masalah hanya ke dimensi yang relevan.

Klasifikasi Kaki Berbasis Eigenpaw

Sekarang kita dapat menggunakan jarak antara vektor 50-dimensi dan vektor "template" untuk setiap kaki untuk mengklasifikasikan kaki mana yang:

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

Inilah beberapa hasilnya: alt teks alt teks alt teks

Masalah yang Tersisa

Masih ada beberapa masalah, terutama dengan anjing yang terlalu kecil untuk membuat jejak kaki yang jelas ... (Ini bekerja paling baik dengan anjing besar, karena jari-jari kaki lebih jelas dipisahkan pada resolusi sensor.) Selain itu, jejak kaki parsial tidak dikenali dengan ini sistem, sementara mereka bisa dengan sistem berbasis pola trapesium.

Namun, karena analisis eigenpaw secara inheren menggunakan metrik jarak, kita dapat mengklasifikasikan kaki dengan dua cara, dan kembali ke sistem berbasis pola trapesium ketika jarak terkecil analisis eigenpaw dari "buku kode" melebihi beberapa ambang batas. Saya belum menerapkan ini.

Fiuh ... Itu lama sekali! Topi saya turun ke Ivo karena memiliki pertanyaan yang menyenangkan!

Joe Kington
sumber
2
Jawaban yang bagus. Saya mencoba metode eigenpaw juga, tetapi tidak sekeras Anda. Satu masalah yang saya lihat adalah pendaftaran kaki, yaitu pendaftaran wajah untuk pengenalan wajah. Apakah Anda mengalami masalah dalam menormalkan lokasi dan rotasi setiap kaki? Jika demikian, maka mungkin kaki tersebut dapat diproses sebelumnya menjadi beberapa fitur invarian rotasi-terjemahan sebelum melakukan PCA.
Steve Tjoa
2
@Steve, saya belum mencoba memutarnya meskipun saya berdiskusi dengan Joe tentang cara memperbaikinya lebih jauh. Namun, untuk menyelesaikan proyek saya untuk saat ini, saya secara manual membuat anotasi semua cakarnya sehingga saya dapat membungkusnya. Untungnya, ini juga memungkinkan kami membuat set pelatihan yang berbeda untuk membuat pengenalan lebih sensitif. Untuk memutar cakarnya, saya berencana menggunakan jari-jari kaki, tetapi seperti yang Anda baca di blog saya, itu tidak semudah pertanyaan pertama saya membuatnya terlihat seperti ...
Ivo Flipse
@Dasar ya saya beralih ke hosting situs web saya sendiri dan memindahkan semua konten Wordpress, tetapi saya tidak dapat mengedit komentar saya lagi di sini. Anda seharusnya dapat menemukannya di sini: flipserd.com/blog/ivoflipse/post/improving-the-paw-detection
Ivo Flipse
4

Menggunakan informasi yang murni berdasarkan durasi, saya pikir Anda dapat menerapkan teknik dari pemodelan kinematika; yaitu Kinematika Invers . Dikombinasikan dengan orientasi, panjang, durasi, dan berat total, ini memberikan beberapa tingkat periodisitas yang, saya harap bisa menjadi langkah pertama untuk mencoba memecahkan masalah "penyortiran kaki" Anda.

Semua data itu dapat digunakan untuk membuat daftar poligon berbatas (atau tupel), yang dapat Anda gunakan untuk mengurutkan berdasarkan ukuran langkah kemudian berdasarkan kaki [indeks].

Lam Chau
sumber
2

Dapatkah Anda meminta teknisi menjalankan pengujian secara manual untuk memasukkan kaki pertama (atau dua kaki pertama)? Prosesnya mungkin:

  • Tunjukkan teknis urutan gambar langkah dan minta mereka untuk memberi keterangan pada kaki pertama.
  • Beri label pada kaki lainnya berdasarkan kaki pertama dan izinkan teknisi untuk melakukan koreksi atau menjalankan kembali pengujian. Hal ini memungkinkan untuk anjing pincang atau berkaki 3.
Jamie Ide
sumber
Saya sebenarnya memiliki anotasi dari cakar pertama, meskipun mereka tidak sempurna. Namun, cakar pertama selalu menjadi cakar depan dan tidak akan membantu saya memisahkan cakar belakang. Lagipula, urutannya tidak sempurna seperti yang disebutkan Joe, karena itu mengharuskan kedua bagian depan menyentuh plat di awal.
Ivo Flipse
Anotasi akan berguna saat menggunakan pengenalan gambar, karena dari 24 pengukuran yang saya miliki, setidaknya 24 kaki sudah dianotasi. Jika mereka kemudian akan dikelompokkan menjadi 4 grup, dua di antaranya harus berisi jumlah yang wajar dari kedua kaki depan yang cukup untuk membuat algoritme cukup pasti dari pengelompokan.
Ivo Flipse
Kecuali saya salah membacanya, uji coba beranotasi terkait menunjukkan kaki belakang menyentuh pertama dalam 4 dari 6 uji coba.
Jamie Ide
Ah, maksudku bijak waktu. Jika Anda memutar melalui file, kaki depan harus selalu menjadi yang pertama menyentuh pelat.
Ivo Flipse