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

Question

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

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

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

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

Благодарю.

Answer 1

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

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

Установите кривую в последовательности. Убедитесь, что у вас есть непрерывная взаимно-однозначная функция от [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 2

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

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

Answer 3

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

Answer 4

Шаг 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 5

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