Сравнение последовательностей на слегка неравномерных сетках

[ilghiz]

Добрый день,

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

Аналогично, фотографируем объект на том же транспортере один раз и второй, но из-за того, что объект уехал, а ближние куски объекта на матрице пикселей занимают больше места, имеем искажение, и оно "кривое". Хочется научиться сопоставлять такие объекты.

Итак, пусть это одномерная задача, пусть даны

точки оцифровки

$a_i, i=1, ..., N_a$ первого и
$b_j, j=1, ..., N_b$ второго объектов,

которые оцифрованы в "неизвестные" моменты времени

$y_1=0<y_2<...y_{N_a}=1$
$z_1=0<z_2<...z_{N_b}=1$,

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

Мы хотим сопоставить эти объекты и найти оптимальный набор $y$ и $z$.

ИМХО, задача как-то должна называться, и, скорей всего, ее уже миллион раз решали, то есть у нее есть и название, и решение.

Сам вижу примерно решение таким:

Пусть мы дополнительно потребуем

$$\sum_i || y_i-y_{i-1}-1/(N_a-1) ||_2^2 \to 0$$

$$\sum_j || z_j-z_{j-1}-1/(N_b-1) ||_2^2 \to 0$$

,

и заведем какую-то симметричную в нуле и хорошо спадающую функцию $f(x)$, $f(0)=1$, $f'(0)=0$, $f(x)=f(-x)$, $f(x \to \infty) \to 0$, тогда

$$\min_{y_i, i=2,\dots, N_a-1; z_j, j=1,\dots, N_b-1} ||\sum_i f(x-y_i) a_i - \sum_j f(x-z_j) b_j||_2^2 + \alpha \sum_i || y_i-y_{i-1}-1/(N_a-1) ||_2^2 + \alpha \sum_j || z_j-z_{j-1}-1/(N_b-1) ||_2^2$$

правда у меня есть сомнение о хорошей сходимости такой минимизации квазиньютоновскими методами, а по-другому такую минимизацию, ИМХО, не реально выполнить.

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

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

Спасибо!

[Anatoly]

А не пробовали посмотреть в сторону алгоритма типа Dynamic Time Warping? Там речь как раз о сравнении слегка "разъехавшихся" сигналов. Ширина этого расхождения по времени является одним параметров настройки алгоритма.

[Pavia]

ilghiz в сообщении #1400843 писал(а):

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

Да тут DTW.

ilghiz в сообщении #1400843 писал(а):

Аналогично, фотографируем объект на том же транспортере один раз и второй, но из-за того, что объект уехал, а ближние куски объекта на матрице пикселей занимают больше места, имеем искажение, и оно "кривое". Хочется научиться сопоставлять такие объекты.

Применяют устранение дисторсия и коррекцию перспективы. Так же смотрите перспективно корректное преобразования (perspective correct transform). Вообще применяют калибровку камеры и построение 3D модели.

ilghiz в сообщении #1400843 писал(а):

правда у меня есть сомнение о хорошей сходимости такой минимизации квазиньютоновскими методами

Посмотрите аппроксимацию Паде.

[ilghiz]

Спасибо большое! Да, похоже на DTW, узнал много нового.

Скажите, пожалуйста, а как Паде аппроксимация тут может помочь? Это же банально аппроксимация дробями полиномов и на улучшение сходимости квазиньютоновских методов вроде не влияет, или? Или Вы о чем-то другом и я не понял мысль, скажите, пожалуйста!