Image alignment is the most time-consuming stage of low light image combining. By using a method similar to what has been proposed in HDR+ project page (https://www.timothybrooks.com/tech/hdr-plus/), we introduce decimation to image alignment and it brings big saving in calculation time.
This is how decimation helps: as discussed earlier, assume block size is B, search range in both horizontal and vertical S, the complexity of image alignment is proportional to B*S*S. For a 4k x 3k image and search range equal to 40 ([-40,40] with each even position), the complexity for matching each pair is 19.2G operations, which is enormous. To save MIPS, we can divide this process to two steps:
Step 1: decimate the image by 16. After decimation, it becomes much easier to align images with the cost of reduced accuracy. The complexity of step 1 now becomes B/16*S*S.
Step 2: we are not done yet. Decimating the original image by 16 means aggregating 16 pixels of the original pixel to one. Now it is time to find out exactly which one of these 16 pixels provides the best alignment so that there is no sacrifice on accuracy. But the search range is drastically reduced. We now align with original image with size B but less range with new S' = 4. S' = 4 is sufficient to find one out of 16 pixel candidates.
Breaking the original image alignment to two steps reduces MIPS quite a bit: instead of B*S*S = 19.2G, now we have B/16*S*S + B*4*4 = 1.39G, a reduction of 93% of complexity.
By our experiment, the new execution time of the whole image combining process becomes 9.7s without any help from multicore, which is a roughly 1/4 of the baseline. The sample code can be found here: https://github.com/legendzhangn/blog/tree/master/lowlight_image_combine_even_faster
No comments:
Post a Comment