0
$\begingroup$

I have a 2D signal, and I want to compute a new signal by calculating a weighted mean of each sample's neighbours. However, I also have a 2D bitmask, the same size as the original signal, which indicates that samples in certain positions should be ignored in any average they appear in, including not being counted in the total number of points being averaged, e.g. if my kernel was a 3x3 grid with 1/9 in each entry, then a masked position next to the sample being averaged would mean the sum (of the remaining 8 elements) would be divided by 8 instead of 9. (Unfortunately my kernel is not this simple in practice)

For now, I am calculating this in amplitude space straightforwardly, i.e. for each sample, I go through each value in the kernel, check whether the corresponding cell is masked, and if not, add it to a running total, then divide by the number of unmasked cells.

My understanding is that if I was not masking out samples, this would be a convolution and I could compute the same result more efficiently by taking the FFT of the signal, the FFT of the (zero-padded) kernel, multiplying the two elementwise and then un-FFTing. Being able to do the calculation this way would be a big performance improvement, because I already have to do an FFT of the data for other reasons and so retaining it is "free."

Does anyone know if it is possible to extend the FFT method to take into account that certain samples should be ignored?

Improve this question
$\endgroup$
1
  • $\begingroup$ Just a note: the frequency = 0 output of your FFT is absolutely and positively an average, and in a sense so is each frequency bin (they're just averages that have been weighted by sinusoids). If the pixels in question are just generally useless, with invalid data in them, it may be best to replace them with the average of their nearest neighbors first (or implement some other dead-pixel replacement scheme) -- then treat the resulting image as all good, and do your follow-on processing pretending blissful ignorance that you had dead pixels to start with. $\endgroup$
    – TimWescott
    Commented Dec 14, 2022 at 23:51

1 Answer 1

Reset to default
1
$\begingroup$

That's not going to be possible; from a system-theoretic perspective, your mask makes this operation not position-independent (i.e., the system's not LTI anymore), so no global integral transform equivalence can help you here.

If your "leave out" pixel are very few (or affect only a small portion of the image), you could still fast-convolve your image using the FFT, and then in the result remove the patches affected by the mask, and calculate only these patches "slowly"; this could work out computationally advantageous because the filter size 3×3 is small compared to the image.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think I'd want to work out whether a 3x3 convolution can be profitably done using the FFT method, even if the forward FFT part is already done. $\endgroup$
    – TimWescott
    Commented Dec 14, 2022 at 23:48
  • $\begingroup$ In practice, the kernels involved are much larger than 3x3, but still smaller than the image, so the suggestion to use the FFT method and then correct piecemeal is a good one. That said, I don't know exactly what the bitmask will look like at design time, so "inverting" it to determine which positions will need correction efficiently is possibly a significant processing cost. $\endgroup$
    – redroid
    Commented Dec 15, 2022 at 1:45
  • $\begingroup$ Depending on the way your mask is stored, there can be very efficient methods of finding unaffected areas $\endgroup$
    – Marcus Müller
    Commented Dec 15, 2022 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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