Enhancement: subpixel processing

[jankovicsandras]

Hi David,

Many thanks for your great image morphing application!

I created this Python command line program based on your work:

https://github.com/jankovicsandras/autoimagemorph

The main difference (beside no GUI) is that autoimagemorph selects the points automatically, using cv2.goodFeaturesToTrack() .

I noticed some image artifacts (bright pixels probably at Delaunay triangle edges) and found a simple method to remove them: upscale the image (for example 4x width and height), do the processing, downscale it to original size again. I call this subpixel processing in autoimagemorph , and the obvious downside is much more time and memory required (approx. 16x slower using -subpixel 4) . Still, it might be a good idea to provide this function optionally for better quality, as it's very easy to implement.

Keep up the good work! :)

[ddowd97]

Hey! Thanks for stopping by and for your kind words. I looked at your repo / source code and it looks cool! I never thought someone would want to build off my amateur project so I very much appreciate what you've done (and thank you for the credit).

When I initially created this image morpher as a university project, we were forbidden to use modules such as OpenCV (cv2) since it would have trivialized the matrix math involved. To this day, I still don't import that module for the same reason - however, goodFeaturesToTrack() sounds like a fun sub-import that wouldn't go against the spirit of my repository (since it just adds points). When I have the time, I'll try to fit that feature into my GUI too. Thanks!

As for the artifacting: those are hot pixels, if I'm not mistaken. The fix I'm currently using is a very simple median filter that removes a great deal of the hot pixels and has virtually no impact on runtime; however, I like your fix (not sure why I never thought of it, honestly) and will strongly consider replacing mine with it if I can ever figure out how to improve the performance of interpolatePoints(). I noticed you have a similar goal in your README - seriously, that interpolation function is going to be the death of me.

As a final note, I noticed you mention RGBA support as a ToDo in your repo. This is easily done by checking the shape of the image array (e.g. if leftImageARR.shape[2] == 4, then there are 4 layers, RGBA) and then modifying this section of your code (and any section thereafter that works with the morpher layers):

morphers = [
            Morpher(leftImageARR[:, :, 0], triangleTuple[0], rightImageARR[:, :, 0], triangleTuple[1]),
            Morpher(leftImageARR[:, :, 1], triangleTuple[0], rightImageARR[:, :, 1], triangleTuple[1]),
            Morpher(leftImageARR[:, :, 2], triangleTuple[0], rightImageARR[:, :, 2], triangleTuple[1]),
            Morpher(leftImageARR[:, :, 3], triangleTuple[0], rightImageARR[:, :, 3], triangleTuple[1])
            ]

Thanks so much again for your interest, it means a lot!

[jankovicsandras]

Thanks for your fast reply! There are many interesting ideas to discuss here. I try to break them down by topic, but please respond if it's too much for a single Issue. We can open separate Issues or discuss things in other channels (email). Sorry for the wall of text, I hope it won't be TLDR. :)

• OpenCV (cv2)

It's a good goal to have as few dependencies as possible. I understand also the motivations of the university.
goodFeaturesToTrack() is not that essential, I used cv2 because of experimenting and it can do the same image I/O as the imageio module.

It's easy to replace goodFeaturesToTrack() with another feature point selection function, for example a quick idea in pseudocode: featurepoint = select_closest_to_cell_center( select_pixels_with_biggest_RGBdiff_with_neighbors() )
I will probably experiment with this, but noticed earlier that Python processing is slow compared to the underlying OpenCV functions (C/C++).

My big question was actually not finding feature points on images, but finding matching feature points on 2 images, the mapping which comes naturally when the user selects the points manually.
I experimented with 2d sorting, but couldn't find a good canned answer on stackoverflow, and I'm not that good with Python or math. But I think even 2d sorting (ensuring that the pairs of automatic feature points have minimum distance) does not guarantee there will be no overlapping triangles, which look bad.

That's why autoimagemorph.py uses this grid based method: it ensures that each grid cell has only one feature point, which matches with the same grid cell's feature point on the other image. The feature point selection function in a grid cell might not be that critical, I think the algorithm above or something similar should result similar quality as goodFeaturesToTrack().

Summarized: cv2 is not that critical and can be replaced.

• median filter vs. subpixel processing

The median filter helps removing hot pixels, and it's fast. But it blurs the output somewhat. The subpixel processing results are sharp, but the process takes proportionally longer. The -subpixel 4 option, which removes most hot pixels takes 16x as much time. That's a lot slooooowwer.

I think it's best to have both alternatives, they can be used in combination.

• Hot pixels

Are these hot pixels coming from rasterization? Are they related to getPoints() trueArray, coordArray, mask? I'm sorry, I don't understand the math, but thought that all color planes (R G B) use the same triangle grid. But if that's true, how is it possible, that the hot pixels are bright green, rose or blue? I thought the same coordinates should result the same artifact on all color planes, so black hot pixels (or maybe white or transparent), but not colorful ones? Is there some automatic added noise in a function (RectBivariateSpline interpolation maybe) ?

• Performance

As I understand, this is an iteration on all pixels in interpolatePoints():
for x, y, z in zip(targetPoints, leftSourcePoints, rightSourcePoints): # TODO: ~ 53% of runtime

Is it possible to "outsource" this iteration to a C/C++ engine, like cv2, scipy, numpy (I'm sorry I'm a Python noob, not familiar with these.) ? I guess this would be a huge performance boost.

autoimagemorph.py doesn't use the multiprocessing.Pool, I should put this back.

• RGBA

Thanks, I'll try that!

[ddowd97]

Hello again! Your writeup went above and beyond (especially with that image), so thanks for the good read. I apologize my responses can't be as nice looking - I have written both of these shortly before leaving for work.

• Regarding goodFeaturesToTrack()

Admittedly, I'm not super knowledgeable on automatic and reliable point correspondence placement.. but this is mostly because I haven't really looked into it yet. Your described pseudocode
featurepoint = select_closest_to_cell_center( select_pixels_with_biggest_RGBdiff_with_neighbors() ) is likely one of the best approaches without turning to machine learning or a specific library (e.g. one that only finds face correspondences). Relating to these, I am only aware of the dlib library, which was used to generate the following points in an image from this website:

• Median Filter vs. Image DSR (Subpixel Processing)

While I completely understood the difference between the two, I really liked how thorough you were with the image explanation (which only makes me want to implement your solution more). You have probably noticed that I am currently implementing median_filter 2 at the moment, as I found the blurring in 3+ to be a bit too extreme. It's also interesting that goodFeaturesToTrack()'s processing can affected by the resizing, but it makes sense: note that if you apply goodFeaturesToTrack() before scaling an image up (and then scaling the points up along with it), you would effectively avoid the shown behavior where different feature points are determined.

• Hot Pixels

It's a difficult issue to analyze. At this point in time, it's clear that they appear most prominently in smaller images (and thus why image DSR is a good solution). Through debugging, I have gone so far as to identify which of the hundreds of thousands of pixels were hot (in each layer) before the morph completed, but I couldn't do much with the information. For me, the issue is compounded by the fact that the image layers are created in separate process threads (for performance), which makes debugging this sort of thing more difficult. You are correct that each image slice uses the same triangle grid (and that, presumably, any artifacts should be white); further, I should hope that the issue is not RectBivariateSpline() since this was by far the fastest 2D interpolation method I could find..

TL;DR: I don't have a clear answer for what is specifically causing the hot pixels at this time. :(

• Performance

I have attempted to outsource to libraries such as numba, but they are very, very particular with what they are able to work with (mostly just numpy operations and basic linear algebra, which is unfortunately not the bottleneck here). The snippet you have highlighted (interpolatePoints(): for x, y, z in zip(targetPoints, leftSourcePoints, rightSourcePoints)) isn't compatible with this sort of thing, since this is where the program uses RectBivariateSpline(). It might be possible to do this with the getPoints() function though! I tried a little while ago, but it deserves a second attempt at some point.

Gotta run to work now!

[ddowd97]

Apologies for the long delay (I was working under an intensive .NET training program), but I've finally resolved this issue with my latest release to this repository. In short, my algorithm for interpolating images was completely correct but the lack of documentation for RectBivariateSpline()'s kx and ky parameters was causing unnecessary artifacts to appear in the blends.

    

Before                                                                           After

Since this has now been fixed and hot pixels no longer appear (from what I can tell), I'm finally closing this issue. Thanks!

(I should also note that I've added your goodFeaturesToTrack() suggestion to my To Do list.)

[jankovicsandras]

Great work! Thank you. :) 👍