High Performance PolynomialTransform for movies

Hi,

I have to process hundreds of movies, each of which has hundreds of frames. I need to perform an affine transform warp, followed by a 3rd order polynomial transform warp. I have the coefficients. I have tried the warps on individual randomly selected frames, and they look correct.

Each movie is a 3D matrix of shape [frames, nPixX, nPixY]. It would be very slow to apply the transform to every frame using for-loop. Do you have suggestions on how a (python) for-loop can be bypassed?

In my naive understanding of mathematics, any warp or combination of such is a linear operation onto the pixels of the original image. Thus, it should be possible to obtain such A and B that

ImgNew = A*ImgOld + B

If this is possible, I could use numpy multiplication and addition to have much faster performance than repeating this for every frame.

My movie is 256*256 pixels. I understand that the naive solution would result in a dense matrix A of size 2^32 ~ 4 Gb. While theoretically feasible, its probably not the optimal solution. However, the warping operation I have in mind is not strongly nonlinear, therefore matrix A would be very sparse. So a solution with sparse matrix transform would likely be optimal…

Hi Aleksejs,

We have an example of this in Chapter 5 of Elegant SciPy, which you can read online here.

You can also take a look at scikit-image’s warp functionality, which uses SciPy’s map_coordinates underneath the hood.

@stefanv I appreciate your reply, but it’s not sufficient for me to be able to make progress:

  • The scikit-image warp function does not accept arrays of images as input. I already use this function in my solution using for loops, but it is slow
  • The Scipy’s map_coordinates function produces a list of coordinates. I can use this to calculate the new coordinate for each pixel of the original image. However, the pixel coordinates are going to be fractional. How do I then project these coordinates onto the original pixel coordinates? I presume this solution is essentially re-implementing the warp function, except that the output would be a sparse map.
  • I have had a read of the Elegant SciPy chapter you linked, and I did not find what I was looking for. I already know how sparse matrices work in general, and I’m not interested in segmentation. I am interested in obtaining a sparse matrix representation of a Polynomial Transform given necessary parameters.

I would appreciate further clarification, if possible

Hi Aleksejs,

All the examples I linked to include both a coordinate transformation + interpolation step. You have to do the transformation in reverse, so that you map pixels in your output image to pixels in your input image. Those, as you point out, may land on non-integer positions, so you have an interpolation step that figures out their values from the nearest neighbors.

I don’t think you will easily get away from the for-loop over frames, but I also don’t think that this is what is slowing you down. If you can make a single frame transformation fast, then your for-loop won’t introduce significant overhead.

The chapter I linked to in Elegant SciPy gives an example of exactly what you want to do, so I recommend you take another look—specifically, look for the section titled “Applications of sparse matrices: image transformations”; it describes how to take a mapping and figure out what the matrix will be that applies it with, say, bilinear interpolation. Then you can warp each individual frame by performing A @ x where x are your image values.