Обнаружение пиков в двумерном массиве

avatar
Ivo Flipse
10 сентября 2010 в 12:12
115877
22
946

Я помогаю ветеринарной клинике, измеряю давление под лапой собаки. Я использую Python для анализа данных, и теперь я застрял, пытаясь разделить лапы на (анатомические) части.

Я сделал двумерный массив каждой лапы, который состоит из максимальных значений для каждого датчика, который лапа нагружала с течением времени. Вот пример одной лапы, где я использовал Excel для рисования областей, которые хочу «обнаружить». Это прямоугольники 2 на 2 вокруг датчика с локальными максимумами, которые вместе имеют наибольшую сумму.

alt text

Итак, я попробовал немного поэкспериментировать и решил просто искать максимумы каждого столбца и строки (не могу смотреть в одном направлении из-за формы лапы). Кажется, что это довольно хорошо «определяет» расположение отдельных пальцев, но также отмечает соседние датчики.

alt text

Итак, как лучше всего сказать Python, какие из этих максимумов мне нужны?

Примечание: квадраты 2x2 не могут перекрываться, так как они должны быть отдельными пальцами!

Также я взял 2x2 для удобства, любое более продвинутое решение приветствуется, но я просто занимаюсь изучением движений человека, поэтому я не настоящий программист или математик, поэтому, пожалуйста, сохраняйте его «простым».

Вот версия , которую можно загрузить с помощью np.loadtxt


Результаты

Итак, я попробовал решение @ jextee (см. Результаты ниже). Как видите, он хорошо работает на передних лапах, но хуже работает на задних.

Точнее говоря, он не может распознать маленькую вершину четвертого пальца ноги. Очевидно, это связано с тем, что цикл смотрит сверху вниз в сторону самого низкого значения, не принимая во внимание, где оно находится.

Кто-нибудь знает, как настроить алгоритм @jextee, чтобы он мог найти и четвертый палец?

alt text

Поскольку я еще не обработал никаких других испытаний, я не могу предоставить другие образцы. Но данные, которые я привел ранее, были средними для каждой лапы. Этот файл представляет собой массив с максимальными данными 9 лап в порядке их соприкосновения с пластиной.

На этом изображении показано, как они были распределены в пространстве по пластине.

alt text

Обновление:

Я создал блог для всех, кого интересует и Я установил SkyDrive со всеми необработанными измерениями. Итак, для всех, кто запрашивает дополнительные данные: подробнее власть тебе!


Новое обновление:

Итак, после того, как я получил помощь с моими вопросами относительно обнаружения лапы и сортировки лапы, я наконец смог проверить обнаружение пальцев для каждой лапы! Оказывается, это не так хорошо работает ни с чем, кроме размеров лап, как в моем собственном примере. Конечно, оглядываясь назад, я сам виноват в том, что выбрал 2x2 так произвольно.

Вот хороший пример того, где что-то пошло не так: гвоздь распознается как палец, а «пятка» настолько широкая, что распознается дважды!

alt text

Лапа слишком велика, поэтому если взять размер 2x2 без перекрытия, некоторые пальцы будут обнаружены дважды. Наоборот, у маленьких собак часто не удается найти пятый палец, что, как я подозреваю, вызвано слишком большой площадью 2x2.

После опробования текущего решения на всех моих измерениях я пришел к ошеломляющему выводу, что почти у всех моих маленьких собак пятый палец не обнаруживается и что более чем в 50% ударов для большие собаки найдут больше!

Очевидно, мне нужно это изменить. Мое собственное предположение заключалось в изменении размера neighborhood на что-то меньшее для маленьких собак и больше для больших собак. Но generate_binary_structure не позволил мне изменить размер массива.

Таким образом, я надеюсь, что у кого-нибудь есть лучший совет по расположению пальцев ног, возможно, у него есть масштаб площади пальца в зависимости от размера лапы?

Источник
MattH
10 сентября 2010 в 12:49
0

Я так понимаю, запятые - это десятичные знаки, а не разделители значений?

Ivo Flipse
10 сентября 2010 в 12:50
0

Да, это запятые. И @Christian, я пытаюсь вставить его в легко читаемый файл, но даже это у меня не получается :(

Ivo Flipse
10 сентября 2010 в 13:26
0

Если кому-то нужна дополнительная информация, Я открыл для него чат

Ivo Flipse
10 сентября 2010 в 15:13
0

Я просто заметил, что нижнее изображение зеркально отражено по сравнению с примером Excel. Глупая ориентация!

MattH
10 сентября 2010 в 15:37
0

@Ivo: Какова цель этого анализа? Вы говорите, что хотите определить анатомические подобласти. Это связано с ненормальным распределением нагрузки? Относительное расположение колодок?

Ivo Flipse
10 сентября 2010 в 16:01
4

Пока я делаю технико-экономическое обоснование, все идет реально. Поэтому я ищу как можно больше способов определения давления, включая субрегионы. Также мне нужно уметь различать стороны «большого пальца» и «мизинца», чтобы оценить ориентацию. Но так как этого не делали раньше, неизвестно, что мы можем найти :-)

Ivo Flipse
10 сентября 2010 в 18:32
0

@Daniyar: изображения - это просто imshow () массива (за исключением первого из Excel). @Ron: на данный момент я не обрабатывал никаких других измерений, но это одно измерение фактически имеет 9 полных контактов. Я загружу их через секунду

Ivo Flipse
10 сентября 2010 в 18:50
2

@Ron: одна из целей этого исследования - выяснить, для какого размера / веса собак подходит эта система, так что да, пока эта собака весила около 20 кг. У меня есть такие, которые значительно меньше (и больше), и я ожидаю, что не смогу сделать то же самое с настоящими маленькими.

endolith
6 октября 2011 в 02:18
0

Частичный дубликат: coderhelper.com/questions/1713335/…

Nathan
26 сентября 2018 в 20:48
0

Классный вопрос. Почему связанные данные представляют собой трехмерный массив np, а не двухмерный?

Ivo Flipse
1 октября 2018 в 11:49
2

@frank лапы измеряются во времени, отсюда 3-е измерение. Однако они не двигаются со своего места (условно говоря), поэтому меня больше всего интересует, где расположены пальцы ног в 2D. После этого 3D-аспект предоставляется бесплатно.

Dr. Manuel Kuehner
19 ноября 2018 в 20:28
1

Для меня неясно, описано ли Новое обновление в ответах ниже ?!

Jason
26 сентября 2020 в 15:31
0

Пожалуйста, проясните, решено это в достаточной степени или нет. Вы упомянули "решение jextee", где оно? Кто-то изменил его имя?

Ответы (22)

avatar
Ivan
11 сентября 2010 в 03:38
367

Я обнаружил пики с помощью фильтра локального максимума . Вот результат вашего первого набора данных из 4 лап: Peaks detection result

Я также запустил его на втором наборе данных из 9 лап, и он тоже работал.

Вот как это сделать:

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

Все, что вам нужно сделать после, это использовать scipy.ndimage.measurements.label на маске, чтобы пометить все отдельные объекты. Тогда вы сможете играть с ними по отдельности.

Обратите внимание на , что метод работает хорошо, потому что фон не зашумлен. Если бы это было так, вы бы обнаружили кучу других нежелательных пиков на заднем плане. Еще один важный фактор - размер окрестности . Вам нужно будет отрегулировать его, если размер пика изменится (он должен оставаться примерно пропорциональным).

Ryan Soklaski
22 июня 2017 в 02:12
2

Есть более простое решение, чем (eroded_background ^ local_peaks). Просто сделай (передний план и местные вершины)

Milind R
20 июля 2020 в 03:50
0

Спасибо за совет о том, как определять локальные максимумы / пики в многомерных массивах!

Othman El houfi
5 июня 2021 в 00:45
0

Действительно хорошее решение. Можете ли вы определить сложность вашего алгоритма в зависимости от размеров изображения?

Othman El houfi
10 июня 2021 в 03:08
0

@RyanSoklaski вы хоть представляете, насколько сложен этот алгоритм?

avatar
Thomio
17 апреля 2020 в 17:59
7

Просто хочу сказать вам, что есть хороший вариант найти локальный maxima в изображениях с помощью python:

from skimage.feature import peak_local_max

или для skimage 0.8.0:

from skimage.feature.peak import peak_local_max

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

avatar
8 февраля 2019 в 09:27
1

Существует несколько обширных программных продуктов, доступных в сообществе астрономов и космологов - это важная область исследований как исторически, так и в настоящее время.

Не пугайтесь, если вы не астроном - некоторые из них легко использовать вне поля зрения. Например, вы можете использовать astropy / photutils:

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

[Кажется немного грубым повторять здесь их короткий пример кода.]

Неполный и слегка предвзятый список методов / пакетов / ссылок, которые могут представлять интерес, приведен ниже - добавьте больше в комментариях, и я буду обновлять этот ответ по мере необходимости. Конечно, есть компромисс между точностью и вычислительными ресурсами. [Честно говоря, их слишком много, чтобы давать примеры кода в одном ответе вроде этого, поэтому я не уверен, будет ли этот ответ летать или нет.]

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

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

Задача поиска источников ASKAP / EMU: https://arxiv.org/abs/1509.03931

Вы также можете искать задачи извлечения источников Planck и / или WMAP.

...

avatar
S. Huber
23 мая 2018 в 17:59
24

Используя постоянную гомологию для анализа набора данных, я получаю следующий результат (щелкните, чтобы увеличить):

Result

Это двухмерная версия метода обнаружения пиков, описанного в этом ответе SO. На приведенном выше рисунке просто показаны 0-мерные устойчивые классы гомологии, отсортированные по постоянству.

Я увеличил масштаб исходного набора данных в 2 раза с помощью scipy.misc.imresize (). Однако обратите внимание, что я действительно рассматривал четыре лапы как один набор данных; разделив его на четыре части, проблема будет проще.

Методология. Идея, лежащая в основе этого, довольно проста: рассмотрим функциональный график функции, которая назначает каждому пикселю его уровень. Это выглядит так:

3D function graph

Теперь рассмотрим уровень воды на высоте 255, который непрерывно опускается на более низкие уровни. В локальных максимумах всплывают острова (рождение). В седловых точках сливаются два острова; мы считаем, что нижний остров сливается с верхним островом (смерть). Так называемая диаграмма устойчивости (классов гомологии 0-го измерения, наши острова) изображает смерть выше значений рождения всех островов:

Persistence diagram

настойчивость острова - это тогда разница между уровнем рождения и смерти; расстояние от точки до серой главной диагонали по вертикали. На рисунке островки помечаются уменьшением стойкости.

На самой первой картинке показаны места зарождения островов. Этот метод не только дает локальные максимумы, но также количественно оценивает их «значимость» по вышеупомянутой стойкости. Затем можно было бы отфильтровать все острова со слишком низкой стойкостью. Однако в вашем примере каждый остров (т.е. каждый локальный максимум) - это пик, который вы ищете.

Код Python можно найти здесь.

avatar
13 августа 2013 в 21:02
12

Я уверен, что у вас уже достаточно, но я не могу не предложить использовать метод кластеризации k-средних. k-means - это неконтролируемый алгоритм кластеризации, который берет данные (в любом количестве измерений - я делаю это в 3D) и объединяет их в k кластеров с четкими границами. Здесь приятно, потому что вы точно знаете, сколько пальцев у этих клыков (должно быть).

Кроме того, он реализован в Scipy, что очень приятно (http://docs.scipy.org/doc/scipy/reference/cluster.vq.html).

Вот пример того, что он может сделать для пространственного разрешения 3D-кластеров: enter image description here

То, что вы хотите сделать, немного отличается (2D и включает значения давления), но я все же думаю, что вы могли бы попробовать.

avatar
Ron
11 сентября 2010 в 01:07
10

спасибо за необработанные данные. Я в поезде, и это все, что у меня есть (приближается моя остановка). Я обработал ваш txt-файл регулярными выражениями и поместил его на html-страницу с некоторым javascript для визуализации. Я делюсь им здесь, потому что некоторым, вроде меня, его легче взломать, чем python.

Я думаю, что хороший подход будет инвариантным к масштабу и вращению, и следующим моим шагом будет исследование смесей гауссиан. (каждая подушечка лапы является центром гауссиана).

    <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

Ivo Flipse
11 сентября 2010 в 09:27
1

Я считаю, что это доказательство концепции того, что рекомендуемые гауссовские методы могут работать, если бы только кто-то мог доказать это с помощью Python ;-)

avatar
dmckee --- ex-moderator kitten
10 сентября 2010 в 22:49
18

Эта проблема достаточно глубоко изучена физиками. Хорошая реализация есть в ROOT. Посмотрите на классы TSpectrum (особенно TSpectrum2 для вашего случая) и документацию к ним.

Ссылки:

  1. М.Морхак и др.: Методы устранения фона для многомерных совпадений гамма-спектров. Ядерные приборы и методы в физических исследованиях A 401 (1997) 113-132.
  2. М.Морхак и др.: Эффективная одно- и двумерная деконволюция золота и ее применение для разложения спектров гамма-излучения. Ядерные приборы и методы в физических исследованиях A 401 (1997) 385-408.
  3. М.Морхак и др.: Идентификация пиков в многомерных совпадениях гамма-спектров. Ядерные приборы и методы в физике исследований A 443 (2000), 108-125.

... и для тех, у кого нет доступа к подписке на NIM:

Ivo Flipse
10 сентября 2010 в 23:59
0

Беглый взгляд на статью, похоже, описывает ту же обработку данных, что и я, но я боюсь, что она значительно превзошла мои навыки программирования :(

dmckee --- ex-moderator kitten
11 сентября 2010 в 00:13
0

@Ivo: Я никогда не пробовал реализовать это сам. Я просто использую ROOT. Тем не менее существуют привязки python, но имейте в виду, что ROOT - довольно тяжелый пакет.

physicsmichael
11 сентября 2010 в 22:55
0

@Ivo Flipse: Я согласен с dmckee. В других ответах у вас много многообещающих потенциальных клиентов. Если все они терпят неудачу, и вы чувствуете, что хотите потратить некоторое время, вы можете покопаться в ROOT, и он (вероятно) сделает то, что вам нужно. Я никогда не знал никого, кто пытался бы изучить ROOT через привязки python (а не естественный C ++), поэтому желаю вам удачи.

avatar
Bob Mottram
10 сентября 2010 в 22:39
4

Интересная задача. Я бы попробовал следующее решение.

  1. Примените фильтр нижних частот, например свертку с двухмерной гауссовой маской. Это даст вам набор значений (возможно, но не обязательно с плавающей запятой).

  2. Выполните двухмерное немаксимальное подавление, используя известный приблизительный радиус каждой подушечки лапы (или пальца).

Это должно дать вам максимальные позиции без наличия нескольких кандидатов, находящихся близко друг к другу. Чтобы уточнить, радиус маски на шаге 1 также должен быть аналогичен радиусу, используемому на шаге 2. Этот радиус можно выбрать, или ветеринар может явно измерить его заранее (он будет зависеть от возраста / породы / и т. Д.).

Некоторые из предложенных решений (средний сдвиг, нейронные сети и т. Д.), Вероятно, будут работать до некоторой степени, но они слишком сложны и, вероятно, не идеальны.

Ivo Flipse
10 сентября 2010 в 22:58
0

У меня нет опыта работы с матрицами свертки и гауссовскими фильтрами, не могли бы вы показать, как это будет работать на моем примере?

avatar
mbq
10 сентября 2010 в 19:24
8

Решение физика:
Определите 5 маркеров лапы, идентифицируемых их положениями X_i, и начните их со случайными положениями. Определите некоторую энергетическую функцию, сочетающую некоторую награду за расположение маркеров в положениях лап с некоторым наказанием за перекрытие маркеров; скажем:

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

(S(X_i) - средняя сила в квадрате 2x2 вокруг X_i, alfa - параметр, который будет измерен экспериментально)

А теперь пора применить магию Метрополиса и Гастингса:
1. Выберите случайный маркер и переместите его на один пиксель в случайном направлении.
2. Вычислите dE, разность энергий, вызванных этим движением.
3. Получите равномерное случайное число от 0 до 1 и назовите его r.
. 4. Если dE<0 или exp(-beta*dE)>r, примите перемещение и перейдите к 1; в противном случае отмените перемещение и перейдите к 1.
Так повторять до тех пор, пока маркеры не сойдутся в лапы. Бета-версия управляет сканированием для оптимизации компромисса, поэтому его также следует оптимизировать экспериментально; его также можно постоянно увеличивать со временем моделирования (имитация отжига).

Ivo Flipse
10 сентября 2010 в 19:43
0

Хотите показать, как это будет работать на моем примере? Поскольку я действительно не увлекаюсь математикой высокого уровня, мне уже трудно разгадать предложенную вами формулу :(

mbq
10 сентября 2010 в 20:08
1

Это математика средней школы, вероятно, мои обозначения просто запутаны. У меня есть план проверить это, так что следите за обновлениями.

dmckee --- ex-moderator kitten
11 сентября 2010 в 00:43
4

Я физик элементарных частиц. Долгое время популярный программный инструмент в нашей дисциплине назывался PAW, и у него была сущность, связанная с графиками, называемая «маркером». Вы можете себе представить, насколько запутанным я нашел этот ответ первые пару раз ...

avatar
Aidan Brumsickle
10 сентября 2010 в 19:19
5

Возможно, вы можете использовать что-то вроде Gaussian Mixture Models. Вот пакет Python для выполнения GMM (только что поискал в Google) http://www.ar.media.kyoto-u.ac.jp/members/david/softwares/em/

avatar
joshua
10 сентября 2010 в 19:05
6

приблизительный набросок ...

вы, вероятно, захотите использовать алгоритм связанных компонентов для изоляции каждой области лапы. в вики есть достойное описание этого (с некоторым кодом) здесь: http://en.wikipedia.org/wiki/Connected_Component_Labeling

вам нужно будет решить, использовать ли 4 или 8 подключений. лично для большинства задач я предпочитаю 6-связность. в любом случае, как только вы выделили каждый «отпечаток лапы» как связанную область, будет достаточно легко перебирать область и находить максимумы. как только вы найдете максимумы, вы можете итеративно увеличивать область, пока не достигнете заранее определенного порога, чтобы идентифицировать ее как заданный «палец».

одна тонкая проблема заключается в том, что как только вы начнете использовать методы компьютерного зрения, чтобы идентифицировать что-то как правая / левая / передняя / задняя лапа, и вы начнете смотреть на отдельные пальцы ног, вы должны начать делать повороты, перекосы и перемещения. в учетную запись. это достигается посредством анализа так называемых «моментов». В приложениях машинного зрения следует учитывать несколько различных моментов:

центральные моменты: инвариант переноса нормализованные моменты: инвариант масштабирования и трансляции hu моменты: перенос, масштаб и инвариант вращения

дополнительную информацию о моментах можно найти, выполнив поиск «моменты изображения» в вики.

avatar
antirez
10 сентября 2010 в 18:33
6

Вероятно, стоит попробовать нейронные сети, если вы можете создать некоторые обучающие данные ... но для этого нужно много образцов, аннотированных вручную.

Ivo Flipse
10 сентября 2010 в 18:52
1

Если это того стоит, я бы не прочь аннотировать большой образец вручную. Моя проблема была бы в следующем: как мне это реализовать, поскольку я ничего не знаю о программировании нейронных сетей.

avatar
Paulus
10 сентября 2010 в 18:21
6

Вот еще один подход, который я использовал, когда делал что-то подобное для большого телескопа:

1) Найдите самый высокий пиксель. Как только у вас это получится, поищите вокруг него наиболее подходящее для 2x2 (возможно, максимизируя сумму 2x2) или выполните 2d-гауссовское соответствие внутри подобласти, скажем, 4x4 с центром на самом высоком пикселе.

Затем установите эти 2x2 пикселя, которые вы нашли, равными нулю (или, может быть, 3x3) вокруг центра пика

вернитесь к 1) и повторяйте до тех пор, пока самый высокий пик не упадет ниже шумового порога, или у вас будет все необходимое

Ivo Flipse
10 сентября 2010 в 19:16
0

Не хотите поделиться примером кода, который делает это? Я могу следить за тем, что вы пытаетесь сделать, но понятия не имею, как это кодировать сам

Ivo Flipse
10 сентября 2010 в 20:55
0

На самом деле я работаю с Matlab, так что да, это уже поможет. Но если вы используете действительно сторонние функции, мне может быть сложно воспроизвести это с помощью Python.

avatar
Rick Hull
10 сентября 2010 в 17:56
1

Я не уверен, что это отвечает на вопрос, но похоже, что вы можете просто найти n самых высоких пиков, у которых нет соседей.

Вот суть. Обратите внимание, что это на Ruby, но идея должна быть ясной.

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
Ivo Flipse
10 сентября 2010 в 18:58
0

Я собираюсь попробовать и посмотреть, смогу ли я преобразовать его в код Python :-)

agf
14 апреля 2012 в 00:41
0

Пожалуйста, включите код в сам пост, вместо ссылки на суть, если он имеет разумную длину.

Ben Crowell
2 июня 2021 в 19:34
0

Я не думаю, что в целом это будет хорошо. Он не справится с шумом. Также нет гарантии, что из 4 точек, которые он обнаружит, некоторые не будут лежать в одной подушечке пальца.

avatar
geoff
10 сентября 2010 в 17:45
4

Кажется, можно немного схитрить, используя алгоритм jetxee. Он считает, что первые три пальца в порядке, и вы должны догадаться, откуда взялся четвертый.

avatar
CakeMaster
10 сентября 2010 в 14:54
35

Это проблема регистрации изображения. Общая стратегия:

  • Имейте известный пример или какой-то предшествующий на данных.
  • Подгоните свои данные к примеру или подгоните пример к своим данным.
  • Это помогает, если ваши данные примерно на выровнены в первую очередь.

Вот примерный и готовый подход , «самая глупая вещь, которая могла бы сработать»:

  • Начните с пяти координат пальцев ног примерно в том месте, которое вы ожидаете.
  • С каждым итеративно поднимайтесь на вершину холма. т.е. с учетом текущей позиции перейти к максимальному соседнему пикселю, если его значение больше текущего пикселя. Остановитесь, когда координаты вашего пальца ноги перестанут двигаться.

Чтобы противодействовать проблеме ориентации, вы можете иметь около 8 начальных настроек для основных направлений (север, северо-восток и т. Д.). Запускайте каждый по отдельности и отбрасывайте любые результаты, когда два или более пальца ноги попадают в один и тот же пиксель. Я подумаю об этом еще немного, но подобные вещи все еще исследуются в области обработки изображений - нет правильных ответов!

Немного более сложная идея: (взвешенная) кластеризация K-средних. Это не так уж плохо.

  • Начните с пяти координат зацепления, но теперь это «центры кластеров».

Затем повторяйте до сходимости:

  • Назначьте каждый пиксель ближайшему кластеру (просто составьте список для каждого кластера).
  • Вычислить центр масс каждого кластера. Для каждого кластера это: Sum (координата * значение интенсивности) / Sum (координата)
  • Переместите каждый кластер в новый центр масс.

Этот метод почти наверняка даст гораздо лучшие результаты, и вы получите массу каждого кластера, которая может помочь в идентификации пальцев ног.

(Опять же, вы заранее указали количество кластеров. При кластеризации вы должны так или иначе указать плотность: либо выберите количество кластеров, подходящее для этого случая, либо выберите радиус кластера и посмотрите, как многие из них вы получите. Пример последнего: средний сдвиг.)

Приносим извинения за отсутствие деталей реализации или других особенностей. Я бы написал код, но у меня есть крайний срок. Если к следующей неделе ничего не помогло, дайте мне знать, и я попробую.

Ivo Flipse
10 сентября 2010 в 15:12
1

Проблема в том, что лапы меняют свою ориентацию, и у меня нет калибровки / базовой линии правильной лапы для начала. К тому же я боюсь, что многие алгоритмы распознавания изображений немного не подходят для моей лиги.

CakeMaster
10 сентября 2010 в 16:14
0

Подход «грубо и готово» довольно прост - возможно, я не совсем понял эту идею. Я добавлю псевдокод для иллюстрации.

Ivo Flipse
10 сентября 2010 в 17:31
0

У меня есть чувство, что ваше предложение поможет исправить распознавание задних лап, я просто не знаю, как

CakeMaster
10 сентября 2010 в 19:19
0

Я добавил еще одну идею. Кстати, если у вас есть масса хороших данных, было бы здорово разместить их где-нибудь в Интернете. Это может быть полезно для людей, изучающих обработку изображений / машинное обучение, и вы можете извлечь из этого еще немного кода ...

Ivo Flipse
10 сентября 2010 в 19:22
1

Я как раз думал о том, чтобы записать свою обработку данных в простой блог Wordpress, просто чтобы быть полезным для других, и я все равно должен это записать. Мне нравятся все ваши предложения, но я боюсь, что мне придется ждать кого-то без крайнего срока ;-)

J.Hirsch
19 декабря 2019 в 00:38
0

@IvoFlipse Не бойтесь неизвестного. Сначала получите данные, код может наверстать упущенное.

avatar
Justin Peel
10 сентября 2010 в 14:46
3

Вот простой и не очень эффективный код, но для такого размера набора данных он подходит.

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]

Я просто создаю массив с положением верхнего левого угла и суммой каждого квадрата 2x2 и сортирую его по сумме. Затем я беру квадрат 2x2 с наибольшей суммой вне конкуренции, помещаю его в массив best и удаляю все остальные квадраты 2x2, которые использовали любую часть этого только что удаленного квадрата 2x2.

Кажется, все работает нормально, за исключением последней лапы (той, у которой наименьшая сумма находится в дальнем правом углу на вашем первом изображении), оказывается, что есть два других подходящих квадрата 2x2 с большей суммой (и у них есть равную сумму друг другу). Один из них по-прежнему выбирает один квадрат из вашего квадрата 2x2, но другой находится слева. К счастью, по счастливой случайности мы видим, что можем выбрать больше того, что вам нужно, но это может потребовать использования некоторых других идей, чтобы постоянно получать то, что вы действительно хотите.

Ivo Flipse
10 сентября 2010 в 17:44
0

Я считаю, что ваши результаты такие же, как и в ответе @Jextee. По крайней мере, мне так кажется.

avatar
sastanin
10 сентября 2010 в 14:09
55

Решение

Файл данных: paw.txt. Исходный код:

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"

Вывод без перекрывающихся квадратов. Похоже, что выбраны те же области, что и в вашем примере.

Некоторые комментарии

Сложная часть - вычислить суммы всех квадратов 2x2. Я предполагал, что вам нужны все они, поэтому может быть некоторое совпадение. Я использовал срезы, чтобы вырезать первые / последние столбцы и строки из исходного 2D-массива, а затем наложить их все вместе и вычислить суммы.

Чтобы лучше понять это, визуализируем массив 3x3:

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

Затем вы можете взять его срезы:

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

Теперь представьте, что вы складываете их один над другим и суммируете элементы в одинаковых позициях. Эти суммы будут точно такими же суммами в квадратах 2x2 с левым верхним углом в том же положении:

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

Если у вас есть суммы по квадратам 2x2, вы можете использовать max, чтобы найти максимум, или sort, или sorted, чтобы найти пики.

Чтобы запомнить положения пиков, я связываю каждое значение (сумму) с его порядковым номером в сглаженном массиве (см. zip). Затем я снова вычисляю позицию строки / столбца при печати результатов.

Примечания

Я разрешил перекрытие квадратов 2x2. Отредактированная версия отфильтровывает некоторые из них, так что в результатах появляются только неперекрывающиеся квадраты.

Выбор пальцев (идея)

Еще одна проблема - как выбрать из всех пиков то, что может быть пальцами. У меня есть идея, которая может сработать, а может и не сработать. У меня нет времени реализовать это прямо сейчас, поэтому просто псевдокод.

Я заметил, что если передние пальцы остаются почти на идеальном круге, задний палец должен быть внутри этого круга. Кроме того, передние пальцы расположены более или менее на одинаковом расстоянии. Мы можем попытаться использовать эти эвристические свойства для обнаружения пальцев.

Псевдокод:

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

Это метод грубой силы. Если N относительно мало, я думаю, что это выполнимо. Для N = 12 существует C_12 ^ 5 = 792 комбинации, умноженное на 5 способов выбора заднего пальца, так что 3960 случаев для оценки для каждой лапы.

Johannes Charra
10 сентября 2010 в 14:22
0

Ему придется вручную отфильтровать лапы, учитывая ваш список результатов ... выбор четырех самых верхних результатов даст ему четыре возможности построить квадрат 2x2, содержащий максимальное значение 6,8.

Ivo Flipse
10 сентября 2010 в 14:26
0

Блоки 2x2 не могут перекрываться, поскольку, если я хочу вести статистику, я не хочу использовать один и тот же регион, я хочу сравнивать регионы :-)

sastanin
10 сентября 2010 в 15:58
0

Я отредактировал ответ. Теперь в результатах нет перекрывающихся квадратов.

Ivo Flipse
10 сентября 2010 в 17:22
1

Я попробовал, и вроде работает для передних лап, но меньше для задних. Думаю, нам придется попробовать что-то, что знает, где искать

sastanin
10 сентября 2010 в 22:16
0

Я понимаю, в чем проблема. Я подумаю, как распознать лучшее «созвездие» пиков, чтобы выбрать. Что вы думаете о подходе «четыре в ряд и один в сторону» или «четыре по кругу и один внутри»?

Ivo Flipse
10 сентября 2010 в 22:53
0

Как показано на моем втором изображении (вот ссылка для всех лап), все пики будут отмечены, если вы проверите максимальные значения для каждой строки и столбца, поэтому, возможно, вместо того, чтобы просто просматривать список, отсортированный сверху вниз, мы могли бы проверьте, какой из этих максимумов самый высокий, при этом не имея соседей (игнорируя все, что близко к максимуму). Возможно, даже глядя, какая сумма 2x2 является наибольшей для каждой строки и столбца.

sastanin
10 сентября 2010 в 23:23
1

Я объяснил свою идею, как можно обнаружить пальцы в псевдокоде. Если понравится, могу завтра вечером попробовать реализовать.

Ivo Flipse
11 сентября 2010 в 00:07
0

Если мы воспользуемся эвристикой для определения «наиболее вероятных» кандидатов на два самых высоких пальца ноги и, возможно, на основе формы заднего пальца, можно будет уменьшить количество комбинаций. Также, глядя на другие предложения с использованием фильтров Гаусса, возможно, это повысит эффективность вашего предложения.

avatar
Cedric H.
10 сентября 2010 в 13:05
0

Что делать, если вы продолжите шаг за шагом: сначала вы определите глобальный максимум, при необходимости обработаете окружающие точки с учетом их значения, затем установите для найденной области ноль и повторите для следующей.

Ivo Flipse
10 сентября 2010 в 13:10
0

Хммм, установка на ноль по крайней мере уберет его из любых дальнейших вычислений, что было бы полезно.

Daniyar
10 сентября 2010 в 17:48
0

Вместо установки нуля вы можете вычислить гауссову функцию с выбранными вручную параметрами и вычесть найденные значения из исходных показаний давления. Итак, если палец прижимает ваши датчики, то, найдя самую высокую точку нажатия, вы используете его, чтобы уменьшить влияние этого пальца на датчики, тем самым устраняя соседние ячейки с высокими значениями давления. en.wikipedia.org/wiki/File:Gaussian_2d.png

Ivo Flipse
10 сентября 2010 в 18:39
0

Хотите показать пример, основанный на моих выборочных данных @Daniyar? Поскольку я действительно не знаком с такой обработкой данных

avatar
Eric O Lebigot
10 сентября 2010 в 13:05
14

Вот идея: вы вычисляете (дискретный) лапласиан изображения. Я ожидал, что он будет (отрицательным и) большим в максимуме, более драматичным, чем на исходных изображениях. Таким образом, будет легче найти максимумы.

Вот еще одна идея: если вы знаете типичный размер пятен высокого давления, вы можете сначала сгладить изображение, свернув его с помощью гауссиана того же размера. Это может упростить обработку изображений.

avatar
Johannes Charra
10 сентября 2010 в 13:00
1

Может быть, здесь достаточно наивного подхода: составьте список всех квадратов 2x2 на вашей плоскости, отсортируйте их по сумме (в порядке убывания).

Сначала выберите квадрат с наивысшим значением в вашем «списке лап». Затем итеративно выберите 4 из следующих лучших квадратов, которые не пересекаются ни с одним из ранее найденных квадратов.

Ivo Flipse
10 сентября 2010 в 13:08
0

Я действительно составил список со всеми суммами 2x2, но когда я их заказал, я понятия не имел, как их итеративно сравнивать. Моя проблема заключалась в том, что при сортировке я потерял координаты. Возможно, я мог бы вставить их в словарь, используя координаты в качестве ключа.

Johannes Charra
10 сентября 2010 в 13:31
0

Да, нужен какой-нибудь словарь. Я бы предположил, что ваше представление сетки уже является своего рода словарем.

Ivo Flipse
10 сентября 2010 в 13:53
0

Что ж, изображение, которое вы видите выше, представляет собой массив numpy. Остальное в настоящее время хранится в многомерных списках. Возможно, лучше было бы прекратить это делать, хотя я не так хорошо знаком с итерацией по словарям.

avatar
ChrisC
10 сентября 2010 в 12:38
13

Пара идей, которые мне не приходят в голову:

  • возьмите градиент (производную) сканирования, посмотрите, устраняет ли это ложные вызовы
  • взять максимум локальных максимумов

Вы также можете взглянуть на OpenCV, у него довольно приличный Python API и, возможно, есть некоторые функции, которые вы найдете полезными.

Ivo Flipse
10 сентября 2010 в 13:37
0

Вы имеете в виду, что с градиентом я должен рассчитать крутизну склонов, как только она превысит определенное значение, я знаю, что есть «пик»? Я пробовал это, но некоторые пальцы ног имеют очень низкие пики (1,2 Н / см) по сравнению с некоторыми другими (8 Н / см). Итак, как мне обрабатывать пики с очень низким градиентом?

ChrisC
10 сентября 2010 в 14:27
2

Что сработало для меня в прошлом, если я не мог напрямую использовать градиент, так это смотреть на градиент и максимумы, например если градиент является локальным экстремумом, а я нахожусь в локальном максимуме, то я нахожусь в точке интереса.