One neat trick that can improve most image processing algorithms is rescaling the source to several powers of 2 fraction of the original image and iteratively going through the images from small to large. For example, I would use 1/16, 1/8, 1/4, and 1/2 of the original size. This is faster because there are less pixels to iterate through in the small image and a small neighborhood in the small image is equal to a larger neighborhood in the original image. Each later iteration would only need to search through a neighborhood big enough to refine what had been lost through the last downsizing.
However, when this approach is used on the Khan algorithm, it actually produced worse results. Below is the result of the regular 5-iteration process:
Here is the result of 5 iterations with pyramids. Obviously worse.
But it's even worse when compared to a regular 3-iteration process:
Hm, that's puzzling... My first thought was that maybe downsizing is causing the target pixel to be mixed with the neighbors, thus making it more similar and higher weighted than it should be, but upon further investigation, that doesn't seem to be the main cause. Below is the upscaled result of an iteration on 1/16 of the image:
Can you see the edges where each (gigantic 16x16) weight meets another? The problem was that the ghost was so "thin" that downsizing it either made it non-existent, or made the surrounding "good" areas be considered ghosts. The next iteration would recover the good pixels where they were incorrectly considered ghosts. But for the ghost pixels that were incorrectly considered good, the combined result of those 2 iterations (1 small and 1 regular) is practically the equivalent of 1 regualr iteration.
I'm currently trying to implement a joint bilateral upscaling, which takes into consideration both the radiance and spatial proximity. Hopefully this will make the result of the small iterations less erroneous, but I'm still not sure how it would fair if the ghost was pixel-thin. Maybe if I can quickly go through an interation of Khan if the pixel is too different than its neighbors...