Sum (binary) pixels within a fixed-size region centered at *each and every* pixel

user_17054107 0
Viewed 74

Given an HxW binary image (represented as a numpy 2d array) and D (integer), I would like to output another HxW 2d array in which each (i, j) index stores the number of 1 pixels in the binary image which are at most D rows or columns (basically, up to D pixels away in the L1 sense) from (i, j).

I can of course achieve this by convolving the binary image with a DxD all-ones square, but that seems rather slow using scipy.signal.convolve2d, for example. Also, my D can be rather large (e.g. 256 for an image of size 2600x1900). Any other suggestions?

computer-vision signal-processing image-processing numpy python
1 Answers

A DxD square is a separable filter kernel -- convolving an image with a DxD square of 1s is the same as convolving each row with a row of D 1s, and then convolving each column of the result with a column of D 1s. That reduces the problem from O(H * W * D * D) to O(H * W * D).

But a 1d convolution with a row or column of D 1s can be implemented as a (single stage) cascaded integrator-comb filter. That reduces the problem complexity from O(H * W * D) to O(H * W).

Computationally, this is similar to what @Cris Luengo suggests in comments, but it can be implemented in place without extra memory.

user_54835260
Related