CODEWITHSUNDEEP
pythonimage-processingscipymathematical-morphology
MarcinBurz
MarcinBurz

Reputation: 347

How to perform morphology erosion using FFT Convolution

I try to calculate morphology erosion using FFT Convolution. I know erosion is dual operation to dilation. The first problem is I cannot use 0 as background as usualy I do. So I biased my values. Lets 0.1 value denotes background and 1.0 denotes foreground. Inverting background to foreground and perform FFT convolution with structure element (using scipy.signal.fftconvolve) I obtained result which I cannot interpret further. I know I should threshold the solution somehow and inverse again. How to do?

My 2D signal A:

1 1 0 1 1
1 1 1 1 1
0 1 1 1 0
1 1 1 1 1
1 1 0 1 1

Stucture element B:

0 1 0
1 1 1
0 1 0

Erode(A,B):

0 0 0 0 0
0 1 0 1 0
0 0 1 0 0
0 1 0 1 0
0 0 0 0 0

Using FFT Convolution, inv(A):

0.1 0.1 1.0 0.1 0.1
0.1 0.1 0.1 0.1 0.1
1.0 0.1 0.1 0.1 1.0
0.1 0.1 0.1 0.1 0.1
0.1 0.1 1.0 0.1 0.1

and B:

0.1 1.0 0.1
1.0 1.0 1.0
0.1 1.0 0.1

The result as below:

0.31 1.32 1.32 1.32 0.31
1.32 0.72 1.44 0.72 1.32
1.32 1.44 0.54 1.44 1.32
1.32 0.72 1.44 0.72 1.32
0.31 1.32 1.32 1.32 0.31

What next? normalize/threshold then inverse?

Best regards

Upvotes: 1

Views: 1603

Answers (2)

DrSandwich
DrSandwich

Reputation: 159

After performing the convolution by multiplying in frequency-space and inverse-transforming back into real space, you must then threshold the result above a certain value. According to the white paper Dilation and Erosion of Gray Images with Spherical Masks by J. Kukal, D. Majerova, A. Prochazka, that threshold is >0.5 for dilation, and for erosion it's >m-0.5 where m the structure element's volume (the number of 1s in B, 5 in this case).

In brief: This code will give you the expected result.

from scipy.signal import fftconvolve
import numpy as np
def erode(A,B):
    thresh = np.count_nonzero(B)-0.5
    return fftconvolve(A,B,'same') > thresh

This will work in any dimension and reproduce exactly the results of scipy.ndimage.binary_erosion - at least, I've tested it in 2D and 3D.

As for the other answer posted here that disputes the expected result of an erosion: it depends on the boundary condition. Both scipy.ndimage.binary_erosion and the custom erode(A,B) function written here assume that erosion may occur from all edges of the input A - i.e. A is padded out with 0s before the erosion. If you don't like this boundary condition - if you think, for example, that it should be treated as a reflected boundary condition - then you should consider padding the array yourself using e.g. np.pad(A,np.shape(B)[0],'reflect'). Then you'd need to un-pad the result afterwards.

I was light on details here because I wrote a more comprehensive answer on using frequency-space convolution to perform both erosion and dilation over at another question you asked, but I thought it was worthwhile to have a conclusive answer posted here for anyone seeking it.

Upvotes: 1

FiReTiTi
FiReTiTi

Reputation: 5888

My answer arrives really late, but I still give it.

  • The Erode(A,B) is wrong. This should be the answer:

1 0 0 0 1

0 1 0 1 0

0 0 1 0 0

0 1 0 1 0

1 0 0 0 1

  • Erosion/dilation are rank operations and more particularly min/max operations, but definitely not convolutions. Thus, you cannot perform them using FFT.

Upvotes: 1

Related Questions