Способ и устройство для обработки сигнала и машиночитаемый носитель информации

Изобретения относятся к области обработки сигналов и могут быть использованы для определения взаимной корреляции между двумя сигналами. Техническим результатом является уменьшение шумов. Способ, реализуемый с использованием компьютера, включает: разделение первого сигнала на более короткие сегменты длиной М; осуществление взаимной корреляции сегментов первого сигнала со вторым сигналом с получением в результате множества частичных взаимных корреляционных функций; получение комбинированной взаимной корреляционной функции путем комбинирования частичных взаимных корреляционных функций; применение способа обнаружения выбросов или удаления выбросов для нахождения или удаления сегментов с искажениями или дефектами, который включает сравнение отдельных частичных взаимных корреляционных функций с комбинированной частичной взаимной корреляционной функцией с целью проверки согласия частичной взаимной корреляции с указанной комбинированной взаимной корреляционной функцией; повторное комбинирование указанных частичных взаимных корреляционных функций с исключением тех, которые на основании указанной проверки согласия были найдены содержащими искажения или дефекты, с получением в результате окончательной взаимной корреляционной функции. 3 н. и 12 з.п. ф-лы, 7 ил.

 

Область техники, к которой относится изобретение

Настоящее изобретение относится к способу и устройству для определения взаимной корреляции между первым и вторым сигналом.

Уровень техники

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

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

Взаимная корреляционная функция двух одномерных, дискретных во времени, вещественных сигналов определяется выражением

$$с(\Delta t)=(a*b)\left(\Delta t\right)={\displaystyle \sum _{t\in T}^{}a\left(t+\Delta t\right)b\left(t\right)}\left(1\right)$$

где Т - множество отсчетов, на котором как a(t+Δt), так и b(t) не равны нулю.

Взаимная корреляционная функция для каждого смещения Δt служит мерой сходства между первым сигналом и вторым сигналом, сдвинутым на соответствующую величину. При наличии статистической корреляции между двумя сигналами взаимная корреляционная функция при соответствующих смещениях принимает повышенные значения. Это иллюстрируется на фиг.1, где в левой части показаны отсчеты сигналов а и b, сдвинутых на одну единицу масштаба, имеющих, очевидно, значительную степень корреляции. В данном примере соответствующие отсчеты даже идентичны, если исключить шумовые компоненты. Взаимная корреляционная функция с указанных сигналов, показанная в правой части, отражает данный факт посредством того, что имеет максимум при смещении Δt=1.

Более строго, если случайные процессы, порождающие отсчеты а и b, являются совместно эргодическими и имеют равное нулю математическое ожидание, то функция c(Δt) является мерой ковариации указанных процессов, сдвинутых один относительно другого на Δt.

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

Например, в области телекоммуникаций взаимная корреляция используется для обнаружения образцовых (шаблонных) сигналов известной формы в зашумленном принятом сигнале (так называемые согласованные фильтры (matched filters), см., например, G. Turin. An introduction to matched filters. Information Theory, IRE Transactions on, 6 (3): 311-329, 1960). Еще одним применением является определение временного сдвига между моментами приема сигналов, используемое, например, для измерения расстояний или скоростей (см., например, патентную заявку США 2010/0027602 A1).

В области обработки изображений двумерные взаимные корреляционные функции используются для нахождения соответствия образцу; примерами служат нахождение в изображении фигур заданной формы или определение сдвига между некоторой группой пикселей в двух изображениях (см., например, BruneIIi. Template matching techniques in computer vision. 2008).

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

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

$$с\left(\Delta t\right)={\displaystyle \sum _{t_1}\dots }{\displaystyle \sum _{t_N}{a}^{*}\left(t+\Delta t\right)b\left(t\right)},t,\Delta t\in Z^N\left(2\right)$$

Частным случаем взаимной корреляционной функции является автокорреляционная функция, в которой сигнал коррелируют сам с собой (а≡b). Автокорреляционная функция, например, дает возможность обнаруживать в сигнале периодически повторяющиеся фрагменты.

Еще одной формой взаимной корреляционной функции, широко используемой в обработке изображений, является нормированная взаимная корреляционная функция по формуле 3.

$$\overline{c}\left(\Delta t\right)={\displaystyle \sum _{t\in T}\frac{\left(a\left(t+\Delta t\right)-\overline{\alpha }\left(\Delta t\right)\right)\left(b\left(t\right)-\overline{b}\left(\Delta t\right)\right)}{{\sigma }_a\left(\Delta t\right){\sigma }_b\left(\Delta t\right)}}\left(3\right)$$

Здесь $$\overline{x}$$ и σ_х обозначают математическое ожидание и среднее квадратическое отклонение сигнала x в области наложения сигнала а и сигнала b, смещенного на Δt. Нормированная взаимная корреляционная функция эквивалентна коэффициенту корреляции между соответственно сдвинутыми сигналами. Ее преимущество в том, что она дает возможность достоверно сопоставлять сигналы на разных масштабах.

Находит применение и ранговая корреляция, в которой вместо реальных значений входных сигналов используются их ранги в ранжированной последовательности. Данный способ повышает робастность (устойчивость) по отношению к изолированным выбросам, что сравнимо с преимуществами использования медианы перед обычным усреднением. Широко используются два способа нахождения ранговой корреляции: вычисление коэффициента Спирмена ρ и коэффициента Кендалла т (см., например, G.Kendall and J.D.Gibbons. Rank correlation methods. 1990).

Раскрытие изобретения

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

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

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

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

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

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

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

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

Данные варианты представляют собой конкретные способы выполнения проверки согласия для отдельных взаимных корреляционных функций.

В соответствии с одним из вариантов осуществления указанный способ обнаружения или удаления выбросов включает одно из следующего: метод RANSAC; метод наименьшей медианы квадратов; М-оценку.

Данные варианты представляют собой примеры способа обнаружения выбросов.

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

Данный способ является конкретным предпочтительным вариантом использования метода RANSAC.

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

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

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

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

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

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

Таким образом сигналы могут быть подготовлены для взаимной корреляции.

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

Таким образом может быть снижено влияние шума.

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

Таким образом может быть осуществлено устройство, реализующее вариант осуществления настоящего изобретения.

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

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

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

Краткое описание чертежей

Фиг.1 схематично изображает взаимную корреляцию двух сигналов.

Фиг.2 схематично изображает локальное искажение и его влияние на взаимную корреляцию.

Фиг.3 схематично изображает использование метода RANSAC для аппроксимации.

Фиг.4 схематично изображает частичные взаимные корреляционные функции для видеофрагментов, показанных в качестве примера на фиг.5.

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

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

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

Осуществление изобретения

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

PCCF (partial cross-correlation function) - частичная взаимная корреляционная функция;

RANSAC (Random Sample Consensus) - метод построения и оценки модели с использованием случайной выборки;

М-оценки (M-Estimators) - широкий класс оценок, определяемых как минимумы сумм функций от данных;

LMedS (Least Median of Squares) - метод оценки модели по наименьшей медиане квадратов.

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

RANSAC представляет собой итерационный метод робастной аппроксимации множества измерений или точек данных некоторой моделью (Fischler and R.C.Bolles. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24 (6): 381-395, 1981). Фундаментальным отличием данного способа от, например, аппроксимации методом наименьших квадратов является использование не всех точек данных, а лишь количества, минимально необходимого для построения модели. Указанные точки выбираются случайным образом. На этом этапе небольшие погрешности в данных измерения устраняются не так эффективно. Однако основной целью здесь является обнаружение и исключение точек данных, содержащих значительные ошибки (так называемых выбросов). Эта цель достигается проверкой согласия всех измерений с первоначально построенной моделью. Точки, согласующиеся с моделью, называются неискаженными (inliers); точки, не согласующиеся с моделью, считаются выбросами. Указанные операции повторяются с другой группой случайно выбранных точек, и весь процесс повторяется столько раз, сколько необходимо для гарантированного выбора по меньшей мере одной группы точек, не содержащей выбросов. В итоге за окончательную принимают модель с наивысшим согласием, т.е. с наименьшим количеством выбросов, и окончательную аппроксимацию выполняют методом наименьших квадратов только по неискаженным точкам данной модели.

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

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

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

Это особенно характерно для способа выделения выбросов. Хотя далее варианты осуществления описываются, в основном, на примере RANSAC, концепция, лежащая в основе изобретения, может с равным успехом осуществляться с использованием любого другого способа исключения выбросов, например, М-оценок или метода LMedS.

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

a) один из исходных сигналов разделяют на более короткие сегменты длиной М;

b) вычисляют взаимную корреляцию каждого из сегментов и второго сигнала, в результате чего получают частичные взаимные корреляционные функции (PCCF); и

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

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

На первом шаге один из исходных сигналов (первый сигнал) разделяют на более короткие сегменты длиной М (короче длины L исходных данных).

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

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

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

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

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

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

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

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

а) сведения видеоданных к одномерному временному ряду, отражающему характерные изменения сцены во времени. Для формирования такого временного ряда может использоваться, например, объем потока (битрейт) видеоданных, формируемых кодером, как описано, например, в заявке на европейский патент №09175917.5.

b) применение способа корреляции в соответствии с одним из вариантов осуществления настоящего изобретения для определения временного смещения между двумя последовательностями видеоданных.

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

Далее несколько более подробно описываются еще некоторые варианты осуществления изобретения.

В качестве одного из вариантов осуществления можно рассмотреть идею, лежащую в основе описываемого способа взаимной корреляции, которая состоит в разделении одного из исходных сигналов на более короткие сегменты длиной М (которая меньше длины L исходного сигнала), и взаимной корреляции каждого из сегментов со вторым сигналом. Получаемые таким образом частичные взаимные корреляционные функции (PCCF) затем комбинируются, отделяя искаженные сегменты от неискаженных способом, подобным методу RANSAC. Аппроксимируемая модель в терминах метода RANSAC представляет собой смещение, то есть единственную скалярную величину. Точками данных являются частичные взаимные корреляционные функции, которые для определения возможных предположительных смещений комбинируются, т.е. суммируются. Действительно, сумма всех PCCF c_i дает взаимную корреляционную функцию исходных сигналов:

$$\begin{array}{l}{\displaystyle \sum _t{c}_i\left(\Delta t\right)={\displaystyle \sum _i{\displaystyle \sum _{t\in T}a\left(t+\Delta t\right)b_i\left(t\right)}}}\\ ={\displaystyle \sum _{t\in T}a\left(t+\Delta t\right){\displaystyle \sum _i{b}_i\left(t\right)}}\\ ={\displaystyle \sum _{t\in T}a\left(t+\Delta t\right)b\left(t\right)}\\ =c\left(\Delta t\right)\end{array}$$

Исключение из суммирования PCCF, являющихся выбросами, дает возможность устранить их влияние на результирующую взаимную корреляционную функцию.

Количество PCCF, комбинируемых на каждом шаге RANSAC, является предметом компромиссного выбора. Для получения в результирующей взаимной корреляционной функции максимально четко выраженного максимума в принципе желательно использовать наибольшее из возможных количество PCCF. Однако увеличение данного количества также увеличивает и вероятность включения в расчет PCCF, являющихся выбросами. Решение зависит от ожидаемого распределения всплесков ошибок и индивидуально для каждой конкретной задачи.

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

Нижеприведенный способ описывает предлагаемый в соответствии с одним из вариантов осуществления способ взаимной корреляции двух входных сигналов a(t) и b(t).

1. Разделить сигнал b(t) на сегменты bi(t) длиной М.

2. Вычислить PCCF ci(Δt)=(а*bi)(Δt).

3. [повторять шаги 3а/b/с до нахождения группы PCCF, не содержащей выбросов]

a) случайной выборкой сформировать группу PCCF и вычислить их сумму;

b) определить по указанной сумме предположительные смещения;

c) для каждого предположительного смещения определить в группе количество PCCF, не являющихся выбросами.

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

5. При необходимости пересчитать смещение по комбинации (сумме) PCCF, не являющихся выбросами.

Конкретный способ выполнения шага 3с является предметом выбора, осуществляемого специалистом в соответствии с конкретными обстоятельствами. Например, для определения количества выбросов и количества точек, согласующихся с моделью, может выполняться проверка того, что смещения частичных взаимных корреляционных функций отстоят от величины смещения комбинированной взаимной корреляционной функции не более, чем на заданное пороговое значение. В качестве порогового значения может использоваться, например, среднеквадратическое отклонение выборки величин смещений частичных" взаимных корреляционных функций, но возможны и другие варианты выбора порогового значения. Шаг 3 может повторяться целиком до тех пор, пока не будет отобрана группа PCCF, не содержащая выбросов, то есть группа, в которой все PCCF согласуются с моделью.

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

В зависимости от задачи отдельные PCCF и их комбинации не обязательно имеют единственный выраженный максимум. Могут наблюдаться несколько локальных максимумов сопоставимой величины, дающие более одного предположительного смещения. Это явление показано на фиг.4, где изображены частичные взаимные корреляции для двух видеосигналов a(t) и b(t), показанных на фиг.5. В левой части фиг.5 показаны входные сигналы a и b, в правой части показаны два одновременно снятых кадра, взятых из последовательностей видеоданных, по которым были сформированы сигналы a(t) и b(t). Из данных кадров очевидно, что указанные последовательности видеоданных сняты с разных углов. Деление сигнала b на сегменты, используемое в данном способе, показано на фиг.5 вертикальными пунктирными линиями, проведенными с интервалом в 100 кадров.

Явление существования более одного предположительного смещения (ср. фиг.4) выражено сильнее, когда комбинируется лишь небольшое количество PCCF,. или когда PCCF вычисляются лишь по небольшому числу отсчетов.

Для нахождения предположительных смещений в комбинации произвольно выбранных PCCF на первом шаге может выполняться шумоподавление. В соответствии с одним из вариантов осуществления для этого можно использовать морфологическое замыкание или многократное вычисление выпуклой оболочки результирующей взаимной корреляционной функции с целью сохранения только значимых максимумов указанной функции. Для соответствующих предположительных смещений затем проверяется, сколько отдельных PCCF согласуется с каждым из них. Данная операция может рассматриваться как «проверка согласия» в том смысле, что в ней проверяется, находится ли данное предположительное смещение в согласии с отдельными смещениями отдельных PCCF. Для выполнения такой проверки согласия во внимание могут быть приняты следующие параметры:

- абсолютное или относительное значение PCCF при проверяемом смещении;

- кривизна PCCF при проверяемом смещении;

- выраженное в количестве отсчетов расстояние от проверяемого смещения до ближайшего значимого локального максимума PCCF;

а также любое сочетание этих и, возможно, других критериев.

Абсолютное (или относительное) значение отдельной PCCF при данном предположительном смещении может сравниваться со значением предположительной комбинированной взаимной корреляционной функции. Если их разность больше (заранее заданного) порогового значения, то отдельная PCCF может считаться не находящейся в согласии с комбинированной PCCF (т.е., с предположительным значением комбинированной взаимной корреляционной функции). Данная PCCF, следовательно, может быть признана «выбросом».

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

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

В описании нижеследующего варианта осуществления шаги способа иллюстрируются более конкретным примером.

В рассматриваемом далее примере конкретного использования решается задача синхронизации двух видеофрагментов с использованием одномерных временных рядов, построенных по кадрам указанных видеофрагментов. Указанный временной ряд может представлять собой, например, просто объем потока данных (битрейт) как функцию времени (как, например, описано в заявке на европейский патент №09175917.5 «Method and apparatus to synchronize video data»), либо любую другую функцию времени, зависящую от одной переменной. В данном случае для нахождения временного смещения между двумя различными временными рядами, соответствующими двум разным видеофрагментам, а тем самым и между самими видеофрагментами, можно использовать взаимную корреляцию.

Одним из способов нахождения временного смещения между двумя последовательностями видеоданных является преобразование видеоданных в одномерный временной ряд, отражающий характерные изменения сцены во времени. Для формирования такого временного ряда может использоваться, как уже упоминалось, способ, описанный в заявке на европейский патент №09175917.5 «Method and apparatus to synchronize video data». Использованные видеофрагменты сняты неподвижными камерами и отображают одну и ту же сцену с человеком, совершающим некоторые действия перед неподвижным фоном. Полученные вышеуказанным способом одномерные сигналы можно считать квазистационарными и нормировать их на глобальное математическое ожидание и среднеквадратическое отклонение. Польза этого аналогична применению нормированной взаимной корреляционной функции по формуле (3).

В левой части фиг.5 показаны полученные вышеуказанным способом два входных сигнала, а в правой части в качестве примера два синхронных кадра из соответствующих видеофрагментов. Обычная взаимная корреляционная функция данных сигналов, представленная на графике в левой части фиг.6, дает величину смещения 1 кадр. На графике в правой части фиг.6 сигналы а и b показаны наложенными друг на друга со смещением 1 кадр, определенным при обычной взаимной корреляции. Отклонение от истинного смещения (действительного взаимного смещения двух видеоизображений) вызвано эффектами на краях изображений. Из-за различия направлений, с которых камеры ведут съемку, люди, входящие в кадр и выходящие из него, порождают флуктуации, которые проявляются в одномерных сигналах с небольшой задержкой. Этим, например, вызван довольно сильный максимум около 700-го кадра в обоих сигналах а и b. При обычной взаимной корреляции прежде всего выравниваются такие доминирующие фрагменты сигналов, а менее выраженные, но при том более точно согласующиеся фрагменты остаются без внимания. Как показано на фиг.6, обычная взаимная корреляция сигналов а и b дает смещение Δtxcorr=1 кадр. Это происходит из-за наличия порожденного помехой максимума между кадрами 600 и 700, по которому сигналы вынужденно выравниваются.

Предлагаемый в соответствии с одним из вариантов осуществления способ взаимной корреляции решает указанную проблему, исключая из рассмотрения такие единичные сегменты, что показано на фиг.7. Указанный способ взаимной корреляции в соответствии с вариантом осуществления настоящего изобретения дает правильную величину смещения Δtcor= 50 кадров. При применении данного способа из анализа исключаются сегменты bi, обозначенные в правой части фиг.7 цифрами в кружках, представляющие собой фрагменты сигнала, в которых локальные максимумы являются следствием помех, например (1) входа людей в кадр справа; (2) входа людей в кадр слева; и (3) недостатка движения в сцене, не позволяющего надежно установить временные соотношения между двумя видеофрагментами. В данном варианте осуществления настоящего изобретения фрагменты (1), (2) и (3) признаны «выбросами», поскольку способом, основанным на проверке согласия, установлено, что частичные взаимные корреляционные функции, соответствующие данным искаженным фрагментам, не находятся в согласии с результирующей комбинированной PCCF. На указанном основании те PCCF, которые соответствуют указанным фрагментам, исключены, и результирующая комбинированная PCCF дает истинное смещение, равное 50 кадрам. В правой части фиг.7, где показаны сигналы а и b, сигнал b сдвинут на истинное смещение 50 кадров, определенное по показанной на левой стороне фиг.7 взаимной корреляционной функции, вычисленной с использованием проверки согласия.

При конкретном применении способа настоящего варианта осуществления изобретения в вышеописанном эксперименте, иллюстрирующем эффективность данного способа, второй сигнал был разделен на сегменты длиной М=100 кадров (шаг 1 вышеописанного способа). На шаге случайного выбора (шаг 3а) для определения возможных смещений комбинировали s=3 сегмента. Перед нахождением локальных максимумов (шаг 3b) и для проверки, выполняемой на шаге Зс, соответствующие сигналы были подвергнуты фильтрации путем вычисления замыкания при ширине структурного элемента 51 кадр. В данном случае PCCF признавалась находящейся в согласии с данным предположительным смещением (то есть не считалась выбросом), если ее ближайший локальный максимум отстоял не далее чем на 10 кадров. Однако указанное значение является предметом выбора и может быть в соответствии с конкретной задачей задано специалистом. Вопрос о том, каким образом определять, находится ли PCCF в согласии с комбинированной PCCF, может решаться различными способами.

Специалисту в данной области должно быть очевидно, что способы, элементы, модули и устройства, описанные в связи с вариантами осуществления настоящего изобретения, могут быть реализованы аппаратно, программно либо сочетанием указанных средств. В частности, понятно, что варианты осуществления настоящего изобретения и элементы модулей, описанных в связи с ними, могут быть осуществлены компьютерной программой или компьютерными программами, работающими на компьютере или выполняемыми микропроцессором. Любое устройство, реализующее изобретение, может, в частности, быть выполнено в форме элемента сети, например, роутера, сервера, работающего в сети модуля, или в форме мобильного устройства, например, мобильного телефона, смартфона, карманного персонального компьютера (Personal Digital Assistant, PDA) и т.п.

1. Способ обработки сигнала для определения взаимной корреляции между первым и вторым сигналами, реализуемый с использованием компьютера, включающий:
разделение первого сигнала на более короткие сегменты длиной М;
осуществление взаимной корреляции сегментов первого сигнала со вторым сигналом с получением в результате множества частичных взаимных корреляционных функций;
получение комбинированной взаимной корреляционной функции путем комбинирования частичных взаимных корреляционных функций;
применение способа обнаружения выбросов или удаления выбросов для нахождения или удаления сегментов с искажениями или дефектами, причем указанный способ обнаружения выбросов включает:
сравнение отдельных частичных взаимных корреляционных функций с комбинированной частичной взаимной корреляционной функцией с целью проверки согласия частичной взаимной корреляции с указанной комбинированной взаимной корреляционной функцией; причем способ обработки сигнала дополнительно включает:
повторное комбинирование указанных частичных взаимных корреляционных функций с исключением тех, которые на основании указанной проверки согласия были найдены содержащими искажения или дефекты, с получением в результате окончательной взаимной корреляционной функции со сниженным влиянием искажений и дефектов.

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

3. Способ по п.1, отличающийся тем, что дополнительно включает: выбор группы более коротких сегментов длиной М; вычисление комбинированной взаимной корреляции по частичным взаимным корреляционным функциям выбранной группы; выполнение проверки согласия с целью нахождения выбросов среди указанных частичных взаимных корреляционных функций указанной группы; повторение шагов выбора группы сегментов, вычисление комбинированной взаимной корреляции и проверку согласия отдельных частичных взаимных корреляций, соответствующих указанным сегментам, до нахождения по меньшей мере одной группы сегментов, не содержащей выбросы или имеющей наименьшее количество выбросов; вычисление окончательной комбинированной взаимной корреляционной функции по группе сегментов, не содержащей выбросы или имеющей наименьшее количество выбросов.

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

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

6. Способ по п.1, отличающийся тем, что указанный способ обнаружения или удаления выбросов включает одно из следующего: метод RANSAC; метод наименьшей медианы квадратов; М-оценку.

7. Способ по п.1, отличающийся тем, что указанный способ обнаружения выбросов представляет собой метод RANSAC, в котором аппроксимируемой моделью является максимальная величина взаимной корреляции между первым и вторым сигналами, а данными, используемыми при аппроксимации, являются соответствующие максимумы частичных взаимных корреляционных функций, значения которых после исключения искаженных частичных взаимных корреляционных функций комбинируют, получая полную взаимную корреляционную функцию.

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

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

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

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

12. Устройство для обработки сигнала для определения взаимной корреляции между первым и вторым сигналами, содержащее модуль для разделения первого сигнала на более короткие сегменты длиной М;
модуль для осуществления взаимной корреляции сегментов первого сигнала со вторым сигналом с получением в результате множества частичных взаимных корреляционных функций;
модуль для получения комбинированной взаимной корреляционной функции путем комбинирования частичных взаимных корреляционных функций;
модуль для применения способа обнаружения выбросов или удаления выбросов для нахождения или удаления сегментов с искажениями или дефектами, причем указанный способ обнаружения выбросов включает сравнение отдельных частичных взаимных корреляционных функций с комбинированной частичной взаимной корреляционной функцией с целью проверки согласия частичной взаимной корреляции с указанной комбинированной взаимной корреляционной функцией; и модуль для повторного комбинирования указанных частичных взаимных корреляционных функций с исключением тех, которые на основании указанной проверки согласия были найдены содержащими искажения или дефекты, с получением в результате окончательной взаимной корреляционной функции со сниженным влиянием искажений и дефектов.

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

14. Устройство по п.12, отличающееся тем, что дополнительно содержит модуль для выбора группы более коротких сегментов длиной М; модуль для вычисления комбинированной взаимной корреляции по частичным взаимным корреляционным функциям выбранной группы; модуль для выполнения проверки согласия с целью нахождения выбросов среди указанных частичных взаимных корреляционных функций указанной группы; модуль для повторения выбора группы сегментов, вычисления комбинированной взаимной корреляции и проверки согласия отдельных частичных взаимных корреляций, соответствующих указанным сегментам, до нахождения по меньшей мере одной группы сегментов, не содержащей выбросы или имеющей наименьшее количество выбросов; модуль для вычисления окончательной комбинированной взаимной корреляционной функции по группе сегментов, не содержащей выбросы или имеющей наименьшее количество выбросов.

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