I am trying to implement a algorithm for rolling shutter distortion removal based on curve interpolation, that I have seen in an paper (https://ieeexplore.ieee.org/document/6311354). This algorithm includes calculating a new x- and y-coordinate for each pixel in the source-image. Now I have to resample the created irregular grid of pixels to a regular grid, but I do not know how to do that. I only know how Target-to-Source Mapping works. But I can't use that beacuse I can't simply invert the process, that creates the irregular grid of pixels, since every pixel is computed individually.
3 Answers
Presumably, transforming the source image pixels yields a dense (twisted) grid in the target. This should allow you to use a bilinear interpolation scheme in the grid cells.
Draw regularly spaced horizontals in the target and find the intersections with the grid. You can interpolate the pixels along the edges crossed. Now along the horizontals you have irregularly spaced points, and you can interpolate between them to get regularly spaced pixels.
To speed-up the intersection process, you can use a scanline approach (sorting the grid edges on Y).
I tried different solutions and it appears, that scipy.interpolate.griddata (https://docs.scipy.org/doc/scipy/reference/generated/scipy.interpolate.griddata.html) is the best solution in terms of runtime
Near_rgrid under
find-nearest-value-in-numpy-array
snaps any cloud of points to their nearest neighbors on a regular grid,
in a page of code.
scipy RegularGridInterpolator also does linear, bilinear ... interpolation.
Scipy griddata uses KDTree. While this will work, it doesn't use the regularity of the grid at all — methods that do are simpler and faster. (Building a KDTree for 25 million points in 2d takes ~ 30 seconds on my old iMac, then queries take micro or milliseconds, scipy 1.7.1 .)
Your choice of method will of course depend on how many scattered data points and how many query points (the regular grid) you have — how big are your images ?
Related