Взаємна кореляція

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Наочне порівняння згортки, взаємної кореляції та автокореляції. Для операцій, що включають функцію f, і виходячи з припущення, що висота f становить 1,0, значення результату в 5 різних точках показано затіненою областю під кожною точкою. Також, вертикальна симетрія f є причиною того, що та в цьому прикладі ідентичні.

В обробці сигналів взаємна кореляція (англ. cross-correlation) — це міра подібності двох рядів як функція зміщення одного відносно іншого. Вона також відома як ковзний скалярний добуток (англ. sliding dot product) та ковзний внутрішній добуток (англ. sliding inner-product). Її зазвичай використовують для пошуку в довгому сигналі коротшої відомої ознаки. Вона має застосування в розпізнаванні образів, аналізі одиничних частинок[en], електронній томографії[en], усереднюванні, криптоаналізі та нейрофізіології . Взаємна кореляція за своєю природою подібна до згортки двох функцій. В автокореляції, яка є взаємною кореляцією сигналу з самим собою, завжди буде пік на нульовій затримці, і його розмір буде енергією сигналу.

У теорії ймовірностей та статистиці термін взаємні кореляції стосується кореляцій між елементами двох випадкових векторів та , тоді як кореляції випадкового вектора є кореляціями між елементами самого , що утворюють кореляційну матрицю . Якщо як , так і є скалярними випадковими величинами, які багаторазово реалізуються в часовому ряді, то кореляції різних часових примірників відомі як автокореляції (англ. autocorrelations) , а взаємні кореляції із у часі є часовими взаємними кореляціями (англ. temporal cross-correlations). У теорії ймовірностей та статистиці визначення кореляції завжди включає такий стандартувальний коефіцієнт, щоби кореляції мали значення від −1 до +1.

Якщо та  — дві незалежні випадкові величини з функціями густини ймовірності та відповідно, то густина ймовірності різниці формально задається взаємною кореляцією (у сенсі обробки сигналів) , проте цю термінологію в теорії ймовірностей та статистиці не використовують. На противагу цьому, згортка (еквівалентна взаємній кореляції та ) дає функцію густини ймовірності суми .

Взаємна кореляція детермінованих сигналів[ред. | ред. код]

Для безперервних функцій та взаємну кореляцію визначають як[1][2][3]

 

 

 

 

( 1 )

що рівнозначне

де позначує комплексне спряжене , а  — зміщення, відоме також як запізнювання (англ. lag; ознака в з трапляється в на ).

Якщо та обидві є безперервними періодичними функціями з періодом , то інтегрування з до замінюється інтегруванням за будь-яким інтервалом довжини :

 

 

 

 

( 2 )

що рівнозначне

Аналогічно, для дискретних функцій взаємну кореляцію визначають як[4][5]

 

 

 

 

( 3 )

що рівнозначне

.

Для скінченних дискретних функцій (циклічну, англ. circular) взаємну кореляцію визначають як[6]

 

 

 

 

( 4 )

що рівнозначне

.

Для скінченних дискретних функцій , ядрову взаємну кореляцію (англ. kernel cross-correlation) визначають як[7]

 

 

 

 

( 5 )

де  — вектор ядрових функцій , а  — афінне перетворення.

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

Пояснення[ред. | ред. код]

Як приклад розгляньмо дві дійснозначні функції та , що відрізняються лише невідомим зміщенням уздовж осі x. Взаємною кореляцією можливо скористатися, щоби знайти, наскільки мусить бути зміщено вздовж осі x, щоби зробити її ідентичною до . Ця формула по суті соває функцію уздовж осі x, обчислюючи інтеграл від їхнього добутку в кожному положенні. Коли функції збігаються, значення є максимальним. Це тому, що коли піки (додатні області) вирівняно, вони роблять великий внесок до інтегралу. Аналогічно, коли вирівнюються западини (від'ємні області), вони також роблять додатний внесок до інтегралу, оскільки добуток двох від'ємних чисел є додатним.

Анімація, яка наочно показує, як обчислюється взаємна кореляція

З комплекснозначними функціями та взяття спряження забезпечує, що вирівняні піки (або вирівняні западини) з уявними компонентами робитимуть до інтегралу додатний внесок.

В економетрії взаємну кореляцію з запізнюванням іноді називають взаємною автокореляцією (англ. cross-autocorrelation).[8]:с. 74

Властивості[ред. | ред. код]

  • Взаємна кореляція функцій та рівнозначна згортці (позначуваній через ) функцій та . Тобто,
  • Якщо функція є ермітовою[en], то
  • Якщо як , так і є ермітовими, то .
  • .
  • Аналогічно теоремі про згортку[en], взаємна кореляція задовольняє
    де позначує перетворення Фур'є, а знову позначує комплексне спряження , оскільки . У поєднанні з алгоритмами швидкого перетворення Фур'є цю властивість часто використовують для ефективного чисельного обчислення взаємних кореляцій[9] (див. циклічну взаємну кореляцію[en]).
  • Взаємна кореляція пов'язана зі спектральною густиною (див. теорему Вінера — Хінчина[en]).
  • Взаємна кореляція згортки та з функцією це згортка взаємної кореляції та з ядром :
    .

Взаємна кореляція випадкових векторів[ред. | ред. код]

Визначення[ред. | ред. код]

Для випадкових векторів та , кожен з яких складається з випадкових елементів з відомими математичним сподіваннями та дисперсіями, матрицю взаємної кореляції та визначають через[10]:с.337

 

 

 

 

( 6 )

й вона має розміри . У записі по складових:

Випадкові вектори та не зобов'язані мати однакові розміри, й будь-який з них може бути скалярним значенням.

Приклад[ред. | ред. код]

Наприклад, якщо та  — випадкові вектори, то  — матриця , чиїм -м елементом є .

Визначення для комплексних випадкових векторів[ред. | ред. код]

Якщо та  — комплексні випадкові вектори[en], кожен з яких містить випадкові величини з відомими математичними сподіваннями та дисперсіями, то матрицю взаємної кореляції та визначають через

де позначує ермітове транспонування.

Взаємна кореляція стохастичних процесів[ред. | ред. код]

В аналізі часових рядів і статистиці взаємна кореляція пари випадкових процесів — це кореляція між значеннями цих процесів у різні моменти часу як функція від цих двох моментів часу. Нехай  — пара випадкових процесів, а  — будь-яка точка в часі ( може бути цілим числом для дискретночасового[en] процесу, або дійсним числом для процесу неперервночасового[en]). Тоді  — це значення (або реалізація[en]), реалізоване в результаті заданого перебігу процесу в момент часу .

Взаємна кореляційна функція[ред. | ред. код]

Припустімо, що цей процес у момент часу має середні значення та і дисперсії та , для будь-якого . Тоді визначенням взаємної кореляції між моментами часу та є[10]:с.392

 

 

 

 

( 7 )

де  — оператор математичного сподівання. Зауважте, що цей вираз може бути не визначеним.

Взаємна коваріаційна функція[ред. | ред. код]

Віднімання середнього значення перед множенням дає перехресну коваріацію моментів часу та :[10]:с.392

 

 

 

 

( 8 )

Зауважте, що цей вираз не є однозначно визначеним для всіх часових рядів та процесів, оскільки середнє значення або дисперсія можуть не існувати.

Визначення для стаціонарного в широкому сенсі стохастичного процесу[ред. | ред. код]

Нехай подає пару стохастичних процесів, спільно стаціонарних у широкому сенсі[en]. Тоді взаємну коваріаційну та взаємну кореляційну функції задають наступним чином.

Взаємна кореляційна функція[ред. | ред. код]

 

 

 

 

( 9 )

або, рівнозначно,

Взаємна коваріаційна функція[ред. | ред. код]

 

 

 

 

( 10 )

або, рівнозначно,

де та  — середнє значення та стандартне відхилення процесу , сталі в часі через стаціонарність; і так само для , відповідно. показує математичне сподівання. Те, що взаємні коваріація та кореляція не залежать від , — саме додаткова інформація (поза індивідуальною стаціонарністю в широкому сенсі), яку передає вимога, що спільно стаціонарні в широкому сенсі.

Взаємну кореляцію пари спільно стаціонарних у широкому сенсі стохастичних процесів можливо оцінювати усереднюванням добутку зразків, виміряних за одним процесом, і зразків, виміряних за іншим (та за його зсувами в часі). Зразки, включені до цього усереднювання, можуть бути довільною підмножиною всіх зразків у сигналі (наприклад, зразки в межах скінченного часового вікна, або підвибірка[яка?] одного з сигналів). За великої кількості зразків це усереднення збігається до істинної взаємної кореляції.

Унормовування[ред. | ред. код]

Поширеною практикою в деяких дисциплінах (наприклад, у статистиці та аналізі часових рядів) є унормовувати взаємно кореляційну функцію, щоб отримувати залежний від часу коефіцієнт кореляції Пірсона. Проте в деяких інших дисциплінах (наприклад, в інженерії) унормовування зазвичай пропускають, а терміни «взаємна кореляція» та «взаємна коваріація» використовують як взаємозамінні.

Визначення нормованої взаємної кореляції стохастичного процесу:

.

Якщо функція однозначно визначена, її значення мусять лежати в діапазоні , причому 1 вказує на ідеальну кореляцію, а −1 — на ідеальну антикореляцію[en].

Для спільно стаціонарних у широкому сенсі стохастичних процесів визначення таке:

.

Унормовування важливе як тому, що інтерпретація автокореляції як кореляції забезпечує безмасштабну міру сили статистичної залежності, так і тому, що унормовування впливає на статистичні властивості оцінюваних автокореляцій.

Властивості[ред. | ред. код]

Властивість симетрії[ред. | ред. код]

Для спільно стаціонарних у широкому сенсі стохастичних процесів взаємно кореляційна функція має таку властивість симетрії:[11]:с.173

Відповідно, для спільно СШС стохастичних процесів:

Аналіз часової затримки[ред. | ред. код]

Взаємні кореляції корисні для визначання часової затримки між двома сигналами, наприклад, для визначання часових затримок поширення акустичних сигналів системою спрямованих мікрофонів.[12][13][прояснити: ком.]  Після обчислення взаємної кореляції між двома сигналами максимум (або мінімум, якщо сигнали корельовані негативно) взаємно кореляційної функції вказує момент часу, коли сигнали узгоджені найкраще; тобто затримка часу між цими двома сигналами визначається аргументом максимуму, або arg max, взаємної кореляції, як у

Термінологія в обробці зображень[ред. | ред. код]

Центрована нормована взаємна кореляція (ЦНВК)[ред. | ред. код]

Для застосувань в обробці зображень, у яких яскравість зображення та шаблону може змінюватися залежно від умов освітлення та експозиції, зображення можуть спочатку унормовувати. Зазвичай це роблять на кожному кроці шляхом віднімання середнього значення та ділення на стандартне відхилення. Тобто, взаємна кореляція шаблону з підзображенням  — це

де  — число пікселів у та ,  — усереднення , а  — стандартне відхилення .

З погляду функціонального аналізу це можливо розглядати як добуток двох унормованих векторів. Тобто, якщо

та

то наведена вище сума дорівнює

де  — скалярний добуток, а  — норма L². З Коші — Буняковського тоді випливає, що ЦНВК (англ. zero-normalized cross-correlation, ZNCC) має діапазон .

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

Нормована кореляція — це один із методів, які використовують для зіставляння з шаблоном[en], процесу, який використовують для пошуку зразків або об'єктів у зображенні. Вона також є двовимірною версією коефіцієнту кореляції моменту добутку Пірсона.

Нормована взаємна кореляція (НВК)[ред. | ред. код]

НВК (англ. normalized cross-correlation, NCC) подібна до ЦНВК, з тією лише відмінністю, що не віднімається локальне середнє значення освітленостей:

Нелінійні системи[ред. | ред. код]

При використанні взаємної кореляції для нелінійних систем необхідно бути обережними. За певних обставин, які залежать від властивостей вхідних даних, взаємна кореляція між входом і виходом системи з нелінійною динамікою може бути повністю сліпою до певних нелінійних ефектів.[14] Ця проблема виникає через те, що деякі квадрати моментів можуть дорівнювати нулеві, й це може помилково підказувати, що між двома сигналами існує невелика «кореляція» (у сенсі статистичної залежності), хоча насправді ці два сигнали сильно пов'язані нелінійною динамікою.

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. Bracewell, R. "Pentagram Notation for Cross Correlation." The Fourier Transform and Its Applications. New York: McGraw-Hill, pp. 46 and 243, 1965. (англ.)
  2. Papoulis, A. The Fourier Integral and Its Applications. New York: McGraw-Hill, pp. 244–245 and 252—253, 1962. (англ.)
  3. Weisstein, Eric W. "Cross-Correlation." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Cross-Correlation.html [Архівовано 30 серпня 2020 у Wayback Machine.] (англ.)
  4. Rabiner, L.R.; Schafer, R.W. (1978). Digital Processing of Speech Signals. Signal Processing Series. Upper Saddle River, NJ: Prentice Hall. с. 147–148. ISBN 0132136031.  (англ.)
  5. Rabiner, Lawrence R.; Gold, Bernard (1975). Theory and Application of Digital Signal Processing. Englewood Cliffs, NJ: Prentice-Hall. с. 401. ISBN 0139141014.  (англ.)
  6. Wang, Chen (2019). Kernel learning for visual perception, Chapter 2.2.1. Doctoral thesis. Nanyang Technological University, Singapore. с. 17–18.  (англ.)
  7. Wang, Chen; Zhang, Le; Yuan, Junsong; Xie, Lihua (2018). Kernel Cross-Correlator. The Thirty-second AAAI Conference On Artificial Intelligence. Association for the Advancement of Artificial Intelligence. с. 4179–4186. Архів оригіналу за 19 грудня 2021. Процитовано 12 січня 2022.  (англ.)
  8. Campbell; Lo; MacKinlay (1996). The Econometrics of Financial Markets. NJ: Princeton University Press. ISBN 0691043019.  (англ.)
  9. Kapinchev, Konstantin; Bradu, Adrian; Barnes, Frederick; Podoleanu, Adrian (2015). GPU implementation of cross-correlation for image generation in real time. 2015 9th International Conference on Signal Processing and Communication Systems (ICSPCS). с. 1–6. ISBN 978-1-4673-8118-5. doi:10.1109/ICSPCS.2015.7391783.  (англ.)
  10. а б в Gubner, John A. (2006). Probability and Random Processes for Electrical and Computer Engineers. Cambridge University Press. ISBN 978-0-521-86470-1.  (англ.)
  11. Kun Il Park, Fundamentals of Probability and Stochastic Processes with Applications to Communications, Springer, 2018, 978-3-319-68074-3 (англ.)
  12. Rhudy, Matthew; Brian Bucci; Jeffrey Vipperman; Jeffrey Allanach; Bruce Abraham (November 2009). Microphone Array Analysis Methods Using Cross-Correlations Proceedings of 2009 ASME International Mechanical Engineering Congress, Lake Buena Vista, FL. с. 281–288. ISBN 978-0-7918-4388-8. doi:10.1115/IMECE2009-10798.  (англ.)
  13. Rhudy, Matthew (November 2009). Real Time Implementation of a Military Impulse Classifier. University of Pittsburgh, Master's Thesis. Архів оригіналу за 14 липня 2014. Процитовано 16 листопада 2021.  (англ.)
  14. Billings, S. A. (2013). Nonlinear System Identification: NARMAX Methods in the Time, Frequency, and Spatio-Temporal Domains. Wiley. ISBN 978-1-118-53556-1.  (англ.)

Література[ред. | ред. код]

  • Tahmasebi, Pejman; Hezarkhani, Ardeshir; Sahimi, Muhammad (2012). Multiple-point geostatistical modeling based on the cross-correlation functions. Computational Geosciences 16 (3): 779–797. doi:10.1007/s10596-012-9287-1.  (англ.)

Посилання[ред. | ред. код]