Как рассчитать «разницу» между двумя последовательностями точек?

Question

У меня есть две последовательности длиной n и m.Каждый из них представляет собой последовательность точек вида (x, y) и представляет кривые на изображении.Мне нужно выяснить, насколько различны (или похожи) эти последовательности, учитывая тот факт, что

1. одна последовательность, вероятно, длиннее другой (т. Е. Одна может быть вдвое меньше, чем другая,но если они прослеживают приблизительно одну и ту же кривую, они совпадают)

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

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

Спасибо.

Answer 1

Вы имеете в виду, что вы пытаетесь сопоставить кривые, которые были переведены в координаты x, y? Одним из методов обработки изображений является использование цепных кодов [ Я ищу достойную ссылку, но все, что я могу найти прямо сейчас, это this ], чтобы кодировать каждую последовательность и затем сравнивать эти цепные коды. Вы можете взять сумму разностей (по модулю 8), и если результат равен 0, кривые идентичны. Поскольку последовательности имеют разную длину и не обязательно начинаются в одном и том же относительном месте, вам придется сдвигать одну последовательность и делать это снова и снова, но вам нужно создать код цепи только один раз. Единственный способ определить, является ли одна из последовательностей перевернутой, состоит в том, чтобы попробовать как прямую, так и обратную одну из последовательностей. Если кривые не совсем одинаковы, сумма будет больше нуля, но непросто сказать, насколько кривые отличаются от суммы.

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

Answer 2

Метод в этом направлении может работать:

Для обеих последовательностей:

Установите кривую в последовательности. Убедитесь, что у вас есть непрерывная взаимно-однозначная функция от [0,1] до точек на этой кривой. То есть для каждого (действительного) числа от 0 до 1 эта функция возвращает принадлежащую ей точку на кривой. Отслеживая функцию для всех чисел от 0 до 1, вы получаете всю кривую.

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

Теперь, после того как мы получили такую ​​функцию F (double) для первой последовательности и G (double) для второй последовательности, мы можем вычислить подобие следующим образом:

double epsilon = 0.01;
double curveDistanceSquared = 0.0;
for(double d=0.0;d<1.0;d=d+epsilon)
{
   Point pointOnCurve1 = F(d);    
   Point pointOnCurve2 = G(d); 
   //alternatively, use G(1.0-d) to check whether the second sequence is reversed       
   double distanceOfPoints = pointOnCurve1.EuclideanDistance(pointOnCurve2);
   curveDistanceSquared = curveDistanceSquared + distanceOfPoints * distanceOfPoints;
}
similarity = 1.0/ curveDistanceSquared;

Возможные улучшения:

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

-При расчете расстояния рассмотрите возможность перепараметризации функции G таким образом, чтобы расстояние было минимальным. (Это означает, что у вас есть возрастающая функция R, такая, что R (0) = 0 и R (1) = 1, но который в целом является общим. При расчете расстояния вы используете

   Point pointOnCurve1 = F(d);    
   Point pointOnCurve2 = G(R(d)); 

Впоследствии вы пытаетесь выбрать R таким образом, чтобы расстояние было минимальным. (чтобы увидеть, что происходит, обратите внимание, что G (R (d)) также отслеживает кривую)).

Answer 3

Шаг 1: канонизируйте ориентацию.Например, предположим, что все кривые начинаются в конечной точке с наименьшим лексикографическим порядком.

def inCanonicalOrientation(path):
    return path if path[0]<path[-1] else reversed(path)

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

def resample(path, numPoints)
    pathLength = pathLength(path)  #write this function

    segments = generateSegments(path)
    currentSegment = next(segments)
    segmentsSoFar = [currentSegment]

    for i in range(numPoints):
        samplePosition = i/(numPoints-1)*pathLength
        while samplePosition > pathLength(segmentsSoFar)+currentSegment.length:
            currentSegment = next(segments)
            segmentsSoFar.insert(currentSegment)
        difference = samplePosition - pathLength(segmentsSoFar)
        howFar = difference/currentSegment.length
        yield Point((1-howFar)*currentSegment.start + (howFar)*currentSegment.end)

Это можно изменить с линейной передискретизации на что-то лучшее.

def error(pathA, pathB):
    pathA = inCanonicalOrientation(pathA)
    pathB = inCanonicalOrientation(pathB)

    higherResolution = max([len(pathA), len(pathB)])
    resampledA = resample(pathA, higherResolution)
    resampledB = resample(pathA, higherResolution)

    error = sum(
        abs(pointInA-pointInB)
        for pointInA,pointInB in zip(pathA,pathB)
    )
    averageError = error / len(pathAorB)
    normalizedError = error / Z(AorB)
    return normalizedError

Где Z - что-то вроде«диаметр» вашего пути, возможно максимальное евклидово расстояние между любыми двумя точками на пути.

Answer 4

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

Answer 5

Я бы использовал процедуру подбора кривой, но также бросил бы в постоянном члене, т.е. 0 = B0 + B1 * X + B2 * Y + B3 * X * Y + B4 * X ^ 2и т. д. Это позволит уловить поступательную дисперсию, а затем вы можете выполнить статистическое сравнение оценочных коэффициентов кривых, образованных двумя наборами точек, в качестве способа их классификации.Я предполагаю, что вам придется выполнять бивариантную интерполяцию, если данные образуют произвольные кривые в плоскости xy.