Сравните два массива точек

Question

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

То, что могло бы означать (1 коэффициент - идеальное совпадение, 0 или меньше - совсем не соответствует):

1. Очки 640 до 660 - Очень похожие (коэффициент ~ 0,8)
2. Пункты 670 до 690 - совершенно аналогичные (коэффициент составляет ~ 0,5- ~ 0,6)
3. Очки 720 до 780 - Скажем, очень похожи (коэффициент составляет ~ 0,5- ~ 0,6)
4. Баллы 790 к 810 - Perf (коэффициент равен 1)

Коэффициент - это только мои мысли о том, как конечный расчетный результат функции сравнения может выглядеть с данными.

Я прочитал много сообщений о SO, но, похоже, это не помогло решить мою проблему. Буду признателен за вашу помощь. Спасибо

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

Click here to see original size of image

Answer 1

Моя попытка:

Total_sum=0 
1. For each index i in the range (m,n) 
2.  sum=0 
3.  k=Array1[i]*Array2[i]; t1=magnitude(Array1[i]); t2=magnitude(Array2[i]); 
4.  k=k/(t1*t2) 
5.  sum=sum+k 
6. Total_sum=Total_sum+sum 
Coefficient=Total_sum/(m-n) 

Если все значения равны, то сумма будет возвращать 1 в каждом конкретном случае и total_sum вернется (м-н) * (1). Следовательно, когда одно и то же делится на (m-n), мы получаем значение как 1. Если графики являются точными противоположностями, мы получаем -1, а для других вариантов возвращается значение от -1 до 1.
Это не так эффективно, когда диапазон y или диапазон x огромен. Но я просто хотел дать вам представление.

Другим вариантом было бы выполнить обширную XNOR.

1. For each index i in the range (m,n) 
2.  sum=1 
3.  k=Array1[i] xnor Array2[i]; 
4.  k=k/((pow(2,number_of_bits))-1) //This will scale k down to a value between 0 and 1 
5.  sum=(sum+k)/2 

Coefficient=sum 

Полезно?

Answer 2

Вы можете определить метрику расстояния для двух векторов A и B длины N, содержащих числа в интервале [-1, 1], например. а

sum = 0 
for i in 0 to 99: 
    d = (A[i] - B[i])^2 // this is in range 0 .. 4 
sum = (sum/4)/N // now in range 0 .. 1 

Это теперь возвращает расстояние 1 для векторов, которые полностью противоположны (один все 1, другое все -1), и 0 для одинаковых векторов.

Вы можете перевести это в свой коэффициент по

coeff = 1 - sum 

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

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

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

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

procedure calc(A, B, size, d, sorted): 
    if (d > 0): 
    A' = new array[size - 1] 
    B' = new array[size - 1] 
    for i in 0 to size - 2: 
     A'[i] = (A[i + 1] - A[i])/2 // keep in range -1..1 by dividing by 2 
     B'[i] = (B[i + 1] - B[i])/2 
    return calc(A', B', size - 1, d - 1, sorted) 
    else: 
    if (sorted): 
     A = sort(A) 
     B = sort(B) 
    sum = 0 
    for i in 0 to size - 1: 
     sum = sum + (A[i] - B[i]) * (A[i] - B[i]) 
    sum = (sum/4)/size 
    return 1 - sum // return the coefficient 

procedure similarity(A, B, size): 
    sum a = 0 
    a = a + calc(A, B, size, 0, false) 
    a = a + calc(A, B, size, 0, true) 
    a = a + calc(A, B, size, 1, false) 
    a = a + calc(A, B, size, 1, true) 
    return a/4 // take average 

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

Answer 3

Я думаю, что предложение HighPerformanceMarks является стандартным способом выполнения работы.

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

• Разделить оба массива на те же предопределенные индексные интервалы.
• Рассматривайте элементы массива в каждом интервале как векторные координаты в многомерном пространстве.
• вычислить точку продукта обоих векторов.

dot продукт не будет отрицательным. если два вектора перпендикулярны в их векторном пространстве, тоточечный продукт будет 0 (на самом деле именно так «перпендикуляр» обычно определяется в более высоких измерениях), и он достигнет своего максимума для одинаковых векторов.

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

Предостережение: Это специальная эвристика, выбранная для вычислительной эффективности. я не могу рассказать вам о математических/статистических свойствах процесса и свойствах разделения. Если вам нужен тщательный анализ, однако, вы, вероятно, будете лучше соглашаться с теорией корреляции и, возможно, переслать свой вопрос на math.stackexchange.com.

Answer 4

Я также считаю, что High Performance Mark в основном дал вам ответ (кросс-корреляция). На мой взгляд, большинство других ответов дают вам только половину того, что вам нужно (т. Е. Продукт-точка плюс сравнение с некоторым порогом). Однако это не будет считать сигнал похожим на сдвинутую версию самого себя. Вы захотите вычислить этот точечный продукт N + M - 1 раз, где N, M - размеры массивов. Для каждой итерации вычислите произведение точек между массивом 1 и сдвинутой версией массива 2. Сумма, которую вы смещаете массив 2, увеличивается на одну итерацию.Вы можете представить массив 2 как окно, которое вы передаете через массив 1. Вам нужно запустить цикл с последним элементом массива 2, перекрывающим только первый элемент массива 1.

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

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