CODEWITHSUNDEEP
c#imagealgorithmimage-processingbitmap
Ozzah
Ozzah

Reputation: 10701

Fast sub-image comparison in C#

I'm working on a photographic mosaic algorithm. There are 4 steps involved:

  1. Determine segment regions
  2. Determine cost of each candidate image at each segment region
  3. Determine best assignment of each candidate image to each segment region
  4. Render photographic mosaic.

The whole process is relatively straightforward, however Step 2 involves comparing n images with m segments, with n >> m. This is by far the most time intensive step.

Here is the process I go through for each segment-candidate pair:

  1. Determine if the candidate image is compatible with the segment dimensions. If not, the assignment is assumed to be forbidden.
  2. Using an intermediate sub-picture Bitmap created with Graphics.DrawImage(Image, Rectangle, Rectangle, GraphicsUnit), I convert the bitmap data into red, green, and blue int[,] matrices for the segment of the original image. I use the LockBits() method instead of the GetPixel() method as it is vastly faster. To reduce computation time, these matrices are only about 3x3 or 5x5 rather than the full dimensions of the original segment.
  3. I do the same process with the candidate image, creating red, green, and blue 3x3 or 5x5 int[,] matrices.
  4. Starting with cost = 0, I add the magnitude of the difference of the red, green, and blue values of the source and candidate image segments to the cost. The sum of these absolute differences is the assignment cost.

In reality, I check each candidate image with all 16 RotateFlipType transformations, so there are 16*n*m comparisons needed, where n = the number of segments and m = the number of placement regions.

I'm wondering whether I can perhaps do an FFT of each image and rather than comparing each pixel, I compare the low frequency components only, as the high frequency components will not substantially affect the output. On the other hand a lot of the overhead such as getting the sub-images and converting them to matrices are still there, and my gut tells me a spectral comparison will be slower than basic comparison of 25 int values.

Upvotes: 0

Views: 902

Answers (1)

Spektre
Spektre

Reputation: 51845

At first I would do a huge speed up by

  1. create info for each image like:

    average color, r/g/b histograms I think 8 or 16 points per channel will suffice. You can add any other info (darkest/brightest color,...) but it should be rotation/flip invariant

  2. index sort the images by average color

    limit the R,G,B to few bits only like 4 ... and create single integer number from it like

    col=R+(G<<4)+(B<<8);

    and finally index sort used images by this number

  3. comparison

    so binary search the index sorted images (if you create table of indexes per each reduced color then this will be also reduced to O(1)) and find only images with close or equal average color as your segment.

    Then find closest matches to histogram from these and then apply all you have only on those images...

    The histogram comparison can be done by correlation coefficient or by any distance,or statistical deviation ...

    As for the FFT part of your question I think it is more or less already answered by comments. Yes you can use it but I think it is an overkill for this. The overhead is huge but you can rescale images to low resolution and use FFT on that or just compare low res images only instead

[Notes]

Also using HSV instead of RGB could improve visual similarity

Upvotes: 2

Related Questions