Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to remove the boundary effects arising due to zero padding in scipy/numpy fft?

I have made a python code to smoothen a given signal using the Weierstrass transform, which is basically the convolution of a normalised gaussian with a signal.

The code is as follows:


#Importing relevant libraries  
from __future__ import division  
from scipy.signal import fftconvolve   
import numpy as np 

def smooth_func(sig, x, t= 0.002):   
    N = len(x)   
    x1 = x[-1]   
    x0 = x[0]    


# defining a new array y which is symmetric around zero, to make the gaussian symmetric.  
    y = np.linspace(-(x1-x0)/2, (x1-x0)/2, N)   
    #gaussian centered around zero.  
    gaus = np.exp(-y**(2)/t)     

#using fftconvolve to speed up the convolution; gaus.sum() is the normalization constant.  
    return fftconvolve(sig, gaus/gaus.sum(), mode='same')

If I run this code for say a step function, it smoothens the corner, but at the boundary it interprets another corner and smoothens that too, as a result giving unnecessary behaviour at the boundary. I explain this with a figure shown in the link below.
Boundary effects

This problem does not arise if we directly integrate to find convolution. Hence the problem is not in Weierstrass transform, and hence the problem is in the fftconvolve function of scipy.

To understand why this problem arises we first need to understand the working of fftconvolve in scipy.
The fftconvolve function basically uses the convolution theorem to speed up the computation.
In short it says:
convolution(int1,int2)=ifft(fft(int1)*fft(int2))
If we directly apply this theorem we dont get the desired result. To get the desired result we need to take the fft on a array double the size of max(int1,int2). But this leads to the undesired boundary effects. This is because in the fft code, if size(int) is greater than the size(over which to take fft) it zero pads the input and then takes the fft. This zero padding is exactly what is responsible for the undesired boundary effects.

Can you suggest a way to remove this boundary effects?

I have tried to remove it by a simple trick. After smoothening the function I am compairing the value of the smoothened signal with the original signal near the boundaries and if they dont match I replace the value of the smoothened func with the input signal at that point.
It is as follows:


i = 0 
eps=1e-3
while abs(smooth[i]-sig[i])> eps: #compairing the signals on the left boundary
    smooth[i] = sig[i]
    i = i + 1
j = -1

while abs(smooth[j]-sig[j])> eps: # compairing on the right boundary.
    smooth[j] = sig[j]
    j = j - 1

There is a problem with this method, because of using an epsilon there are small jumps in the smoothened function, as shown below:
jumps in the smooth func

Can there be any changes made in the above method to solve this boundary problem?

like image 349
Omkar Avatar asked Apr 04 '12 06:04

Omkar


2 Answers

Best approach is probably to use mode = 'valid':

The output consists only of those elements that do not rely on the zero-padding.

Unless you can wrap your signal, or the signal being processed is an excerpt from a larger signal (in which case: process full signal then crop region of interest) you are always going to have edge effects when doing convolution. You have to choose how you want to deal with them. Using mode = valid just crops them off, which is a pretty good solution. If you know that the signal is always 'step-like' you could then extend the front and end of the processed signal as appropriate.

like image 141
fraxel Avatar answered Nov 17 '22 17:11

fraxel


What a symmetric filter kernel produces at the ends depends on what you assume the data is beyond the ends.

If you don't like the looks of the current result, which assumes zeros beyond both ends, try extending the data with another assumption, say a reflection of the data, or polynomial regression continuation. Extend the data on both ends by at least half the length of the filter kernel (except if your extension is zeros, which come for free with the existing zero-padding required for non-circular convolution). Then remove the added end exensions after filtering, and see if you like the looks of your assumption. If not, try another assumption. Or better yet, use actual data beyond the ends if you have such.

like image 37
hotpaw2 Avatar answered Nov 17 '22 17:11

hotpaw2