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

Question

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

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

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

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

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

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

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

---

Результаты

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

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

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

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

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

Обновление:

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

---

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

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

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

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

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

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

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

Answer 1

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

Я также запустил его на втором наборе данных из 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 на маске, чтобы пометить все отдельные объекты. Тогда вы сможете играть с ними по отдельности.

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

Answer 2

Решение

Файл данных: 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"

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

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

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

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

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

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

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

Примечания

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

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

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

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

Псевдокод:

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 случаев нужно оценить для каждой лапы.

Answer 3

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

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

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

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

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

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

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

Затем итерация до сходимости:

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

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

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

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

Answer 4

Эта проблема была подробно изучена физиками.В ROOT есть хорошая реализация.Посмотрите на TSpectrum классы (особенно TSpectrum2 для вашего случая) и документацию к ним.и др.: Методы устранения фона для многомерного совпадения гамма-спектров.Ядерные приборы и методы в физических исследованиях A 401 (1997) 113-132.

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

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

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

Answer 5

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

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

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

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

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

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

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

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

Answer 6

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

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

Answer 7

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

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

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

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

Answer 8

Просто пара идей с моей головы:

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

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

Answer 9

спасибо за необработанные данные. Я нахожусь в поезде, и это так далеко, как я получил (моя остановка подходит). Я помассировал ваш 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>

Answer 10

Решение физика:
Определите 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.
Это должно повторяться до тех пор, пока маркеры не сойдутся с лапами. Бета контролирует сканирование для оптимизации компромисса, поэтому его также следует оптимизировать экспериментально; оно также может постоянно увеличиваться со временем моделирования (имитация отжига).