0
$\begingroup$

I’m having problems implementing time-stretching using the Wave Similarity Overlap Add (WSOLA) algorithm. I got the basic OLA algorithm working first and then added wave alignment using cross-correlation but the wave alignment part doesn’t appear to be working at all and the result is identical to OLA.

I recorded the audio from my application and here are the waveforms. The first is the original sine wave, the second is the OLA version, and the last is the WSOLA version. I did a null test on the OLA and WSOLA versions and they null completely so they are producing identical results. enter image description here

I’m working off of the pseudo code from a PDF document called Time-Scale Modification Algorithms for Music Audio Signals by Jonathan Driedger. enter image description here

The full explanation is in Chapter 4. https://www.audiolabs-erlangen.de/content/05-fau/professor/00-mueller/01-students/2011_DriedgerJonathan_TSM_MasterThesis.pdf

I’ve gone over the algorithm trying to find any mistakes I may have done and I’ve tried a few tweaks to my code but nothing has worked. I’m new to DSP programming so I’m kind of at a loss on how to fix it. Any help getting this working correctly would be greatly appreciated. Thanks.

Here is my code (Java):

public class TimePitch {
    // CONSTANTS                                                        // EQUATION SYMBOLS
    private final int           windowSizeMS = 37;
    private final int           windowSizeSamples;                      // N
    private final float[]       window;                                 // w
    private final float         overlapFactor = 0.5f;                   // o
    private final int           windowOffset;                           // ηow
    private final int           offsetMax;                              // ∆max
    private final float         offsetMaxFactor = 0.5f;
    // VARIABLES
    private int                 outputBufferSize;                       // length(y)
    private int                 numberOfWindows;                        // length(γ) AND length(σ)
    private int[]               outputWindowPositions;                  // γ
    private int[]               inputWindowPositions;                   // σ

    // TIME STRETCH VALUE
    private float               timeStretch = 2.73f;                    // τ

    public TimePitch(){
        windowSizeSamples = (int)(windowSizeMS * 44.1);     // 44,100 / 1,000
        windowOffset = (int)((1-overlapFactor) * windowSizeSamples);
        offsetMax = (int)(windowSizeSamples * offsetMaxFactor);

        // Fill Hanning Window
        window = new float[windowSizeSamples];
        for (int i=0, n=window.length; i<n; i++){
            window[i] = (float)(0.5 * (1.0 - Math.cos(2.0 * Math.PI * i / n)));
        }
    }

    public float[] processBuffer(final float bufferIn[]){
        // IF no time stretch THEN return original input
        if (timeStretch == 1) return bufferIn;

        outputBufferSize = (int)(bufferIn.length * timeStretch);
        final float[] bufferOut = new float[outputBufferSize];

        numberOfWindows = outputBufferSize / windowOffset;
        outputWindowPositions = new int[numberOfWindows];
        inputWindowPositions = new int[numberOfWindows];

        // COMPUTE array of output window positions (γ)
        outputWindowPositions[0] = 0;
        for (int i=1, n=numberOfWindows; i<n; i++){
            outputWindowPositions[i] = outputWindowPositions[i-1] + windowOffset;
        }
        // COMPUTE array of input window positions (σ)
        for (int i=0, n=numberOfWindows; i<n; i++){
            inputWindowPositions[i] = (int)(outputWindowPositions[i] / timeStretch);
        }

        //************************************************
        // (OLA) Overlap and Add
        //************************************************
//        for (int i=0, n=numberOfWindows; i<n; i++) {
//            // windowed audio segment from input
//            final float[] windowedInput = new float[windowSizeSamples];
//            for (int j=0, m=windowSizeSamples; j<m; j++) {
//                final int index = inputWindowPositions[i] + j;
//                if (index < bufferIn.length) windowedInput[j] = bufferIn[index] * window[j];
//            }
//            // output
//            for (int j=0, m=windowSizeSamples; j<m; j++) {
//                final int index = outputWindowPositions[i] + j;
//                if (index < bufferOut.length) bufferOut[index] = bufferOut[index] + windowedInput[j];
//            }
//        }
        //************************************************
        // (WSOLA) Cross-Correlation AND Overlap and Add
        //************************************************
        final double[] frameAdj = new double[numberOfWindows];
        final double[] frameNext = new double[numberOfWindows + offsetMax * 2];
        final int[] offsets = new int[numberOfWindows];
        Arrays.fill(offsets, 0);
        for (int i=1, n=numberOfWindows; i<n; i++) {
            // OVERLAP AND ADD
            // windowed audio segment from input
            final float[] windowedInput = new float[windowSizeSamples];
            for (int j=0, m=windowSizeSamples; j<m; j++) {
                final int index = inputWindowPositions[i-1] + offsets[i-1] + j;
                if (0 < index && index < bufferIn.length) windowedInput[j] = bufferIn[index] * window[j];
            }
            // output
            for (int j=0, m=windowSizeSamples; j<m; j++) {
                final int index = outputWindowPositions[i-1] + j;
                if (0 < index && index < bufferOut.length) bufferOut[index] = bufferOut[index] + windowedInput[j];
            }

            // FIND NEXT OFFSET
            // clear input frames
            Arrays.fill(frameAdj, 0);
            Arrays.fill(frameNext, 0);
            // fill adjacent frame for cross-correlation
            for (int j=0, m=windowSizeSamples; j<m; j++) {
                final int index = inputWindowPositions[i-1] + offsets[i-1] + windowOffset + j;
                if (0 < index && index < frameAdj.length) frameAdj[j] = inputWindowPositions[index];
            }
            // fill next frame for cross-correlation
            for (int j=0, m=windowSizeSamples + offsetMax * 2; j<m; j++) {
                final int index = inputWindowPositions[i] - offsetMax + j;
                if (0 < index && index < inputWindowPositions.length) frameNext[j] = inputWindowPositions[index];
            }
            offsets[i] = (int) xcorrMax(frameAdj, frameNext, offsetMax);
        }
        //************************************************

        return bufferOut;
    }


    // CROSS-CORRELATION
    // maximum from cross-correlation
    private double xcorrMax(double[] a, double[] b, int maxlag){
        final double[] xcorr = xcorr(a, b, maxlag);
        double max = 0;
        for (int i=0, n=xcorr.length; i<n; i++){
            max = (xcorr[i] > max) ? xcorr[i] : max;
        }
        return max;
    }
    // cross-correlation
    private double[] xcorr(double[] a, double[] b, int maxlag) {
        final double[] y = new double[2*maxlag+1];
        Arrays.fill(y, 0);

        for(int lag = b.length-1, idx = maxlag-b.length+1; lag > -a.length; lag--, idx++) {
            if(idx < 0) continue;
            if(idx >= y.length) break;

            // where do the two signals overlap?
            int start = 0;
            // we can't start past the left end of b
            if(lag < 0) start = -lag;

            int end = a.length-1;
            // we can't go past the right end of b
            if(end > b.length-lag-1) end = b.length-lag-1;

            for(int n = start; n <= end; n++) {
                y[idx] += a[n]*b[lag+n];
            }
        }

        return(y);
    }
}
$\endgroup$
0
$\begingroup$

Your cross correlation is quantized instead of interpolated or filtered. This can result in quantization jitter of the lag values, causing modulation of the sequence of OLA windows.

Try upsampling your data to a much higher sample rate to reduce the correlation lag quantization noise.

$\endgroup$
  • $\begingroup$ Would quantization jitter produce the same result as no correlation? Both the OLA and WSOLA outputs are identical so it seems like I made a mistake somewhere in the WSOLA and the correlation isn't doing anything at all. I will implement upsampling as that sounds like a very good idea to help the overall quality, but it seems like my mistake is bigger than that. Thanks! $\endgroup$ – Tekkerue Sep 15 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.