The idea here is that composing these transformations gives the same result, albeit with a smaller number of arithmetic operations per pixel. This is because we blur three pixels in the horizontal case, and then utilize that work in the vertical blur phase.

What are the criteria that define a "separable" filter? I imagine it would be related to the inherent dimensionality of the filter (perhaps being rank 1 in linear algebra terms) - is there an intuitive way to understand why these filters can be done in two independent passes (i.e what properties make it so)?

@probreather101, I see some research around use of Singular Value Decomposition in understanding how separable filters operate. Maybe this would help: https://bartwronski.com/2020/02/03/separate-your-filters-svd-and-low-rank-approximation-of-image-filters/

So the motivation for turning a one-pass 2D filter into a two-pass 1D filter was the naive conception that it would reduce the number of operations? Was that not a premature optimization given it's not the most straightforward description of the image processing algorithm?

It seems that going from O(n^2) from O(2n) is far from premature, especially if your goal is to write high performance image processing libraries.

Lets say you wanted to While this may be a theoretical example, use a 3d blur to produce a picture. For example your camera takes multiple pictures and wants to blur them together. Would it be feasible to convert this algorithm into a 3n time instead of N cubed?

Given the specifics of how this blur works, I think we can actually do this in O(height * width) time (i.e. not dependent on filter size) by just using the difference between the new pixel and the old pixel every time we slide our 1xf or fx1 window over. So we can actually get this to a constant function of the filter size.