Bagaimana cara menerapkan korelasi silang untuk membuktikan dua file audio serupa?

58

Saya harus melakukan korelasi silang dari dua file audio untuk membuktikan mereka serupa. Saya telah mengambil FFT dari dua file audio dan memiliki nilai spektrum daya dalam array yang terpisah.

Bagaimana saya harus melangkah lebih jauh untuk mengkorelasikan mereka dan membuktikan bahwa mereka serupa? Apakah ada cara yang lebih baik untuk melakukannya? Setiap ide dasar akan membantu saya untuk belajar dan menerapkannya.

audio fft waveform-similarity cross-correlation Lorem Ipsum
sumber
Diberikan korelasi silang dari dua vektor sinyal acak. Bagaimana Anda menerapkan kebalikan untuk mendapatkan dua vektor di MATLAB. John Muhehe

Jawaban:

56

Korelasi-silang dan konvolusi terkait erat. Singkatnya, untuk melakukan konvolusi dengan FFT, Anda

  1. zero-pad sinyal input (tambahkan nol sampai akhir sehingga setidaknya setengah dari gelombang "kosong")
  2. ambil FFT dari kedua sinyal
  3. gandakan hasilnya bersama-sama (perkalian elemen-bijaksana)
  4. lakukan FFT terbalik

conv(a, b) = ifft(fft(a_and_zeros) * fft(b_and_zeros))

Anda perlu melakukan zero-padding karena metode FFT sebenarnya adalah korelasi silang lingkaran , yang berarti sinyal membungkus ujung-ujungnya. Jadi, Anda menambahkan angka nol yang cukup untuk menghilangkan tumpang tindih, untuk mensimulasikan sinyal yang nol hingga tak terhingga.

Untuk mendapatkan korelasi silang alih - alih konvolusi, Anda perlu membalikkan salah satu sinyal sebelum melakukan FFT, atau mengambil konjugat kompleks dari salah satu sinyal setelah FFT:

  • corr(a, b) = ifft(fft(a_and_zeros) * fft(b_and_zeros[reversed]))
  • corr(a, b) = ifft(fft(a_and_zeros) * conj(fft(b_and_zeros)))

mana yang lebih mudah dengan perangkat keras / lunak Anda. Untuk autokorelasi (korelasi silang dari sinyal dengan dirinya sendiri), lebih baik melakukan konjugasi kompleks, karena Anda hanya perlu menghitung FFT satu kali.

Jika sinyal nyata, Anda dapat menggunakan FFT nyata (RFFT / IRFFT) dan menghemat separuh waktu perhitungan Anda dengan hanya menghitung setengah dari spektrum.

Anda juga dapat menghemat waktu perhitungan dengan menambahkan ukuran FFT yang lebih besar untuk dioptimalkan (seperti angka 5-halus untuk FFTPACK, angka ~ 13-halus untuk FFTW , atau kekuatan 2 untuk implementasi perangkat keras yang sederhana).

Berikut ini adalah contoh dalam korelasi FFT Python dibandingkan dengan korelasi brute-force: https://stackoverflow.com/a/1768140/125507

Ini akan memberi Anda fungsi korelasi silang, yang merupakan ukuran kesamaan vs offset. Untuk mendapatkan offset di mana gelombang "berbaris" satu sama lain, akan ada puncak dalam fungsi korelasi:

puncak dalam fungsi korelasi

Nilai x puncak adalah offset, yang bisa negatif atau positif.

Saya hanya melihat ini digunakan untuk menemukan offset antara dua gelombang. Anda bisa mendapatkan perkiraan offset yang lebih tepat (lebih baik daripada resolusi sampel Anda) dengan menggunakan interpolasi parabola / kuadrat pada puncaknya.

Untuk mendapatkan nilai kesamaan antara -1 dan 1 (nilai negatif yang menunjukkan salah satu sinyal berkurang dengan meningkatnya lainnya) Anda perlu skala amplitudo sesuai dengan panjang input, panjang FFT, implementasi FFT khusus Anda penskalaan, dll. Autokorelasi gelombang dengan dirinya sendiri akan memberi Anda nilai kecocokan maksimum yang mungkin.

Perhatikan bahwa ini hanya akan bekerja pada gelombang yang memiliki bentuk yang sama. Jika mereka telah disampel pada perangkat keras yang berbeda atau menambahkan beberapa noise, tetapi jika tidak, masih memiliki bentuk yang sama, perbandingan ini akan berfungsi, tetapi jika bentuk gelombang telah diubah oleh penyaringan atau pergeseran fasa, mereka mungkin terdengar sama, tetapi menang juga berkorelasi.

endolith
sumber
3
Padding nol harus setidaknya N = ukuran (a) + ukuran (b) -1, lebih disukai dibulatkan menjadi kekuatan 2. Untuk mendapatkan nilai antara -1 dan 1, bagi dengan norma (a) * norma (b ), yang memberikan kosinus sudut antara dua vektor dalam ruang-N untuk kelambatan yang diberikan (yaitu modulo N pergeseran geser). Pada keterlambatan ekstrem, tidak ada banyak sampel yang tumpang tindih (hanya satu di ekstrem jauh), jadi membaginya dengan norma (a) * norma (b) akan membiaskan korelasi ini terhadap 0 (yaitu menunjukkan ortogonalitas relatifnya di ruang-N) .
Eryk Sun
1
Saya pikir mungkin ada kesalahan dalam deskripsi. Tidakkah seharusnya mengalikan FFT secara bersama-sama dengan istilah memberikan FFT dari konvolusi sinyal, bukan FFT dari korelasi silang ? Seperti yang saya pahami, untuk mendapatkan FFT dari korelasi silang, perlu untuk menggunakan konjugat kompleks dari salah satu vektor FFT dalam perkalian term-by-term sebelum mengambil iFFT.
Dilip Sarwate
@DilipSarwate: Ya, Anda benar. Anda juga dapat membalikkan satu sinyal ke arah waktu, yang saya tambahkan ke jawabannya.
endolith
1
"Mengapa pembalikan waktu sulit dilakukan dalam perangkat keras?" Dalam banyak kasus, data disimpan dalam susunan sistolik dengan harapan bahwa perhitungannya bersifat lokal , yaitu , disimpan dalam sel ke- , berinteraksi hanya dengan tetangga terdekatnya . Mengirim ke sel # dan mengirim ke sel # , dan melakukan ini untuk semua meningkatkan biaya kabel, penundaan kabel (dan karenanya mengurangi laju clock maksimum yang dapat dicapai), dan juga, karena semua kabel harus saling bersilangan, menciptakan masalah routing. Ini harus dihindari jika mungkin, dan dalam hal ini, itu adalah dihindari.i x [ ± i ] x [ i ] ( N - i ) x [ N - i ] i ix[i]ix[±i]x[i](N−i)x[N−i]ii
Dilip Sarwate
1
@Leo multiplikasi elemen-bijaksana. n-by-1 array x n-by-1 array = n-by-1 array Saya menyebut ini "sampel-oleh-sampel" dalam jawabannya.
endolith
17

Korelasi adalah cara untuk mengekspresikan kesamaan dua kali (sampel audio dalam kasus Anda) dalam satu nomor. Ini adalah adaptasi kovarians yang diimplementasikan sebagai berikut:

period = 1/sampleFrequency;
covariance=0;

for (iSample = 0; iSample<nSamples; iSample++)
    covariance += (timeSeries_1(iSample)*timeSeries_2(iSample))/period;
    //Dividing by `period` might not even be necessary

Korelasi adalah versi kovarians yang dinormalisasi, yang merupakan kovarians dibagi dengan produk dari standar deviasi dari kedua seri waktu. Korelasi akan menghasilkan 0 ketika tidak ada korelasi (sama sekali tidak mirip) dan 1 untuk total korelasi (sama sekali mirip).

Anda dapat membayangkan bahwa dua sampel suara mungkin serupa tetapi tidak disinkronkan. Di situlah korelasi silang masuk. Anda menghitung korelasi antara deret waktu di mana Anda memiliki salah satu dari mereka digeser oleh satu sampel:

for (iShift=0; iShift<nSamples; iShift++)
    xcorr(iShift) = corr(timeSeries_1, timeSeries_2_shifted_one_sample);

Kemudian cari nilai maksimum dalam corrseri dan Anda selesai. (atau berhenti jika Anda telah menemukan korelasi yang cukup) Tentu saja ada sedikit lebih dari itu. Anda harus menerapkan deviasi standar dan Anda harus melakukan beberapa manajemen memori dan menerapkan hal-hal yang mengubah waktu. Jika semua sampel audio Anda memiliki panjang yang sama, Anda dapat melakukannya tanpa menormalkan kovarians dan melanjutkan dan menghitung kovarians lintas.

Hubungan yang keren dengan pertanyaan Anda sebelumnya : Analisis Fourier hanyalah adaptasi dari kovarian silang. Daripada menggeser satu seri waktu dan menghitung kovarian dengan sinyal lainnya, Anda menghitung kovarian antara satu sinyal dan sejumlah gelombang (co) sinus dengan frekuensi yang berbeda. Semuanya didasarkan pada prinsip yang sama.

Komunitas
sumber
1
Anda menyebutkan bahwa 0 tidak ada korelasi dan 1 adalah korelasi total. Saya hanya ingin mencatat bahwa -1 selesai berkorelasi negatif. Seperti pada, -1 menyiratkan bahwa sampel 1 adalah kebalikan dari sampel 2. Jika Anda memikirkannya pada grafik X, Y, itu adalah garis dengan kemiringan positif versus garis dengan kemiringan negatif. Dan saat Anda semakin mendekati 0, garis menjadi "lebih gemuk".
Kellenjb
@ selenjb, Ya, tapi saya mungkin akan mengatakannya, besarnya korelasi apa yang Anda mungkin tertarik. 1 atau -1 berarti sinyal saling mempengaruhi secara langsung.
Kortuk
14

Dalam pemrosesan sinyal, korelasi silang (xcorr dalam MATLAB) adalah operasi konvolusi dengan salah satu dari dua urutan terbalik. Karena pembalikan waktu berhubungan dengan konjugasi kompleks dalam domain frekuensi, Anda dapat menggunakan DFT untuk menghitung korelasi silang sebagai berikut:

R_xy = ifft(fft(x,N) * conj(fft(y,N)))

di mana N = ukuran (x) + ukuran (y) - 1 (lebih disukai dibulatkan menjadi kekuatan 2) adalah panjang DFT.

Penggandaan DFT setara dengan konvolusi melingkar dalam waktu. Zero padding kedua vektor dengan panjang N membuat komponen y yang bergeser secara melingkar dari tumpang tindih dengan x, yang membuat hasilnya identik dengan lilitan linear x dan waktu terbalik y.

Jeda 1 adalah pergeseran melingkar kanan y, sedangkan jeda -1 adalah pergeseran melingkar kiri. Korelasi silang hanyalah urutan produk titik untuk semua kelambatan. Berdasarkan pemesanan fft standar, ini akan berada dalam array yang dapat diakses sebagai berikut. Indeks 0 sampai ukuran (x) -1 adalah kelambatan positif. Indeks ukuran-N (y) +1 hingga N-1 adalah kelambatan negatif dalam urutan terbalik. (Dengan Python lag negatif dapat diakses dengan nyaman dengan indeks negatif seperti R_xy [-1].)

Anda dapat menganggap x-y yang empuk nol dan sebagai vektor dimensi-N. Produk titik dari x dan y untuk kelambatan tertentu adalah |x|*|y|*cos(theta). Norma-norma x dan y adalah konstan untuk pergeseran melingkar, jadi membaginya hanya menyisakan variasi kosinus dari sudut theta. Jika x dan y (untuk lag yang diberikan) ortogonal dalam N-space, korelasinya adalah 0 (yaitu theta = 90 derajat). Jika mereka co-linear, nilainya adalah 1 (berkorelasi positif) atau -1 (berkorelasi negatif, yaitu theta = 180 derajat). Ini mengarah pada korelasi silang yang dinormalisasi menjadi satu:

R_xy = ifft(fft(x,N) * conj(fft(y,N))) / (norm(x) * norm(y))

Ini dapat dibuat tidak bias dengan mengkomputasi ulang norma-norma hanya untuk bagian-bagian yang tumpang tindih, tetapi kemudian Anda juga dapat melakukan seluruh perhitungan dalam domain waktu. Anda juga akan melihat berbagai versi normalisasi. Alih-alih dinormalisasi menjadi satu, kadang-kadang korelasi silang dinormalisasi dengan M (bias), di mana M = max (ukuran (x), ukuran (y)), atau M- | m | (estimasi yang tidak bias dari lag ke-5).

Untuk signifikansi statistik maksimum mean (bias DC) harus dihapus sebelum menghitung korelasinya. Ini disebut kovarians silang (xcov di MATLAB):

x2 = x - mean(x)
y2 = y - mean(y)
phi_xy = ifft(fft(x2,N) * conj(fft(y2,N))) / (norm(x2) * norm(y2))
Eryk Sun
sumber
Apakah ini berarti ukuran akhir array seharusnya 2*size (a) + size(b) - 1atau 2*size (b) + size (a) - 1? Tetapi dalam kedua kasus kedua array empuk memiliki ukuran yang berbeda. Apa konsekuensi dari bantalan dengan terlalu banyak nol?
@RobertK Array korelasi silang harus panjang setidaknya jumlah panjang a dan b (minus satu) seperti kata eryksun dalam jawabannya. Untuk kesederhanaan, panjang seringkali dianggap dua kali panjang vektor yang lebih panjang (kadang-kadang dibulatkan ke kekuatan lebih besar berikutnya untuk menggunakan FFT yang efisien). Pilihan membantu ketika pelanggan terlambat memutuskan dia juga ingin autokorelasi dari vektor yang lebih panjang. Salah satu konsekuensi dari padding dengan nol terlalu banyak adalah perhitungan tambahan tetapi ini mungkin diperbaiki oleh implementasi FFT yang lebih efisien. 2
Dilip Sarwate
@RobertKJ: Anda bikut a, dengan satu output per shift, tumpang tindih minimum satu sampel. Itu menghasilkan size(a)lag positif dan size(b) - 1lag negatif. Dengan menggunakan transformasi invers dari produk DFT titik-N, indeks 0through size(a)-1adalah lag positif, dan indeks N-size(b)+1through N-1adalah lag negatif dalam urutan terbalik.
Eryk Sun
3

jika Anda menggunakan Matlab coba fungsi korelasi silang:

c= xcorr(x,y)

Berikut dokumentasi Matlab:

xcorrmemperkirakan urutan korelasi silang dari proses acak. Autokorelasi ditangani sebagai kasus khusus.

...

c = xcorr(x,y)mengembalikan urutan korelasi silang dalam vektor panjang 2 * N-1, di mana xdan yadalah Nvektor panjang ( N > 1). Jika xdan ybukan panjang yang sama, vektor yang lebih pendek adalah nol-empuk dengan panjang vektor yang lebih panjang.

korelasi http://www.mathworks.com/help/toolbox/signal/ref/eqn1263487323.gif

smashtastic
sumber
Tautannya tampaknya rusak.
Danijel
2

Cara cepat dan sederhana untuk membandingkan file audio. Ambil file audio, buat salinan, dalam daw, tempel berdampingan, dalam 2 saluran stereo, balikkan fase di salah satu trek stereo, sejajarkan kedua file di awal dalam mode zoom, pastikan bahwa kedua file memiliki amplitudo yang sama di awal, lalu mainkan, jika ada keheningan total, maka kedua file itu identik, jika ada perbedaan Anda akan mendengarnya dengan cukup jelas !.

pengguna31971
sumber
1

Seperti yang ditulis di sini, Anda harus menggunakan korelasi.

Ambil saja 2 faktor yang dipertimbangkan:

  1. Jika volume diskalakan secara berbeda, Anda harus menormalkan korelasi.
  2. Jika ada penskalaan waktu maka Anda dapat menggunakan Dynamic Time Warping.
David
sumber
1

Untuk sinyal non-periodik (ukuran (y) -1) harus dikurangi dari indeks R_xy untuk mendapatkan lag yang sebenarnya.

N = ukuran (x) + ukuran (y) - 1;

lags = [0, N] - (size (y) - 1);

Patrick
sumber
0

Cara termudah untuk menemukan perbedaannya, IMO, adalah dengan mengurangi dua sinyal audio dalam domain waktu. Jika mereka sama, hasilnya di setiap titik waktu akan menjadi nol. Jika mereka tidak sama, perbedaan di antara mereka akan dibiarkan setelah dikurangi dan Anda dapat mendengarkannya secara langsung. Ukuran cepat seberapa miripnya mereka akan menjadi nilai RMS dari perbedaan ini. Ini sering dilakukan dalam pencampuran dan penguasaan audio untuk mendengar perbedaan file MP3 vs WAV misalnya. (Membalik fase satu sinyal dan menambahkannya sama dengan mengurangi. Ini adalah metode yang digunakan saat ini dilakukan dalam perangkat lunak DAW.) Mereka harus benar-benar menyesuaikan waktu agar ini berfungsi. Jika tidak, Anda dapat mengembangkan algoritme untuk menyelaraskannya, seperti mendeteksi sepuluh puncak, menghitung rata-rata offset puncak, dan menggeser satu sinyal.

Mengubah ke domain frekuensi dan membandingkan spektrum kekuatan sinyal seperti yang Anda usulkan mengabaikan beberapa informasi domain waktu. Misalnya audio yang diputar terbalik akan memiliki spektrum yang sama ketika diputar ke depan. Dengan demikian, dua sinyal audio yang sangat berbeda dapat memiliki spektrum yang sama persis.

Martin Vandepas
sumber