0

i just take two scree shots of my desktop with little changes and compare two images programmatically using win32 api. my image extension was jpg and both the image height & width was :- height:-768 width:- 1366. i use stopwatch class just to see how much time is taken my routine to get the diff image and save it to desktop. i found it is taking 47 Milliseconds. is there any way out to minimize the time taken by the routine. here is my routine code. please have a look at my routine and inspect how could i reduce the time taken by this routine. thanks

 private void button1_Click(object sender, EventArgs e) { Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); Bitmap firstImg = new Bitmap(@"C:\Users\TRIDIP\Desktop\pic1.jpg"); Bitmap secondImg = new Bitmap(@"C:\Users\TRIDIP\Desktop\pic2.jpg"); Rectangle bounds = GetBoundingBoxForChanges(firstImg, secondImg); if (bounds == Rectangle.Empty) { return; } Bitmap diff = new Bitmap(bounds.Width, bounds.Height); Graphics g = Graphics.FromImage(diff); g.DrawImage(secondImg, 0, 0, bounds, GraphicsUnit.Pixel); g.Dispose(); stopwatch.Stop(); string strmm = string.Format("Time elapsed {0} {1} {2} {3}", stopwatch.Elapsed.Hours.ToString(), stopwatch.Elapsed.Minutes.ToString(), stopwatch.Elapsed.Seconds.ToString(), stopwatch.Elapsed.Milliseconds.ToString()); MessageBox.Show(strmm); } private Rectangle GetBoundingBoxForChanges(Bitmap _prevBitmap, Bitmap _newBitmap) { // The search algorithm starts by looking // for the top and left bounds. The search // starts in the upper-left corner and scans // left to right and then top to bottom. It uses // an adaptive approach on the pixels it // searches. Another pass is looks for the // lower and right bounds. The search starts // in the lower-right corner and scans right // to left and then bottom to top. Again, an // adaptive approach on the search area is used. // // Note: The GetPixel member of the Bitmap class // is too slow for this purpose. This is a good // case of using unsafe code to access pointers // to increase the speed. // // Validate the images are the same shape and type. // if (_prevBitmap.Width != _newBitmap.Width || _prevBitmap.Height != _newBitmap.Height || _prevBitmap.PixelFormat != _newBitmap.PixelFormat) { // Not the same shape...can't do the search. // return Rectangle.Empty; } // Init the search parameters. // int width = _newBitmap.Width; int height = _newBitmap.Height; int left = width; int right = 0; int top = height; int bottom = 0; BitmapData bmNewData = null; BitmapData bmPrevData = null; try { // Lock the bits into memory. // bmNewData = _newBitmap.LockBits(new Rectangle(0, 0, _newBitmap.Width, _newBitmap.Height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb); bmPrevData = _prevBitmap.LockBits(new Rectangle(0, 0, _prevBitmap.Width, _prevBitmap.Height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb); // The images are ARGB (4 bytes) // int numBytesPerPixel = 4; // Get the number of integers (4 bytes) in each row // of the image. // int strideNew = bmNewData.Stride / numBytesPerPixel; int stridePrev = bmPrevData.Stride / numBytesPerPixel; // Get a pointer to the first pixel. // // Note: Another speed up implemented is that I don't // need the ARGB elements. I am only trying to detect // change. So this algorithm reads the 4 bytes as an // integer and compares the two numbers. // System.IntPtr scanNew0 = bmNewData.Scan0; System.IntPtr scanPrev0 = bmPrevData.Scan0; // Enter the unsafe code. // unsafe { // Cast the safe pointers into unsafe pointers. // int* pNew = (int*)(void*)scanNew0; int* pPrev = (int*)(void*)scanPrev0; // First Pass - Find the left and top bounds // of the minimum bounding rectangle. Adapt the // number of pixels scanned from left to right so // we only scan up to the current bound. We also // initialize the bottom & right. This helps optimize // the second pass. // // For all rows of pixels (top to bottom) // for (int y = 0; y < _newBitmap.Height; ++y) { // For pixels up to the current bound (left to right) // for (int x = 0; x < left; ++x) { // Use pointer arithmetic to index the // next pixel in this row. // if ((pNew + x)[0] != (pPrev + x)[0]) { // Found a change. // if (x < left) { left = x; } if (x > right) { right = x; } if (y < top) { top = y; } if (y > bottom) { bottom = y; } } } // Move the pointers to the next row. // pNew += strideNew; pPrev += stridePrev; } // If we did not find any changed pixels // then no need to do a second pass. // if (left != width) { // Second Pass - The first pass found at // least one different pixel and has set // the left & top bounds. In addition, the // right & bottom bounds have been initialized. // Adapt the number of pixels scanned from right // to left so we only scan up to the current bound. // In addition, there is no need to scan past // the top bound. // // Set the pointers to the first element of the // bottom row. // pNew = (int*)(void*)scanNew0; pPrev = (int*)(void*)scanPrev0; pNew += (_newBitmap.Height - 1) * strideNew; pPrev += (_prevBitmap.Height - 1) * stridePrev; // For each row (bottom to top) // for (int y = _newBitmap.Height - 1; y > top; y--) { // For each column (right to left) // for (int x = _newBitmap.Width - 1; x > right; x--) { // Use pointer arithmetic to index the // next pixel in this row. // if ((pNew + x)[0] != (pPrev + x)[0]) { // Found a change. // if (x > right) { right = x; } if (y > bottom) { bottom = y; } } } // Move up one row. // pNew -= strideNew; pPrev -= stridePrev; } } } } catch (Exception ex) { int xxx = 0; } finally { // Unlock the bits of the image. // if (bmNewData != null) { _newBitmap.UnlockBits(bmNewData); } if (bmPrevData != null) { _prevBitmap.UnlockBits(bmPrevData); } } // Validate we found a bounding box. If not // return an empty rectangle. // int diffImgWidth = right - left + 1; int diffImgHeight = bottom - top + 1; if (diffImgHeight < 0 || diffImgWidth < 0) { // Nothing changed return Rectangle.Empty; } // Return the bounding box. // return new Rectangle(left, top, diffImgWidth, diffImgHeight); }
Improve this question
3
  • 1
    I would start by breaking the code down into chunks and profiling each chunk. There may be one block of code that is taking up a large portion of that time. Also, see how much time you're spending reading from the disk. If you have no choice but to read from the disk, this will be a major limiting factor. Commented Dec 12, 2012 at 19:10
  • FYI some other interesting approaches: stackoverflow.com/questions/843972/… Commented Dec 12, 2012 at 19:11
  • @Thomas As Jason Williams mentions, time 1000 passes through this code and then take the average. If you do not do that the you will notice great fluctuations between timings. Commented Dec 12, 2012 at 23:11

3 Answers 3

Reset to default
1

First, I'd suggest timing hundreds/thousands of pases through the code to determine the average speed - a single pass is never a good way of timing code. Also, you are loading two large images from disk, which could easily take longer than the entire diff operation, so you might like to eliminate the loading process from your timing test (as there's nothing you can do to optimise that code anyway).

You've started on the right track by looking for top/left and then bottom/right. But perhaps you could do a little bit better. You need to look for early-outs and unnecessary work. For example, why is the first loop tracking top/left/bottom/right? Before you hit the first diff, there is no point in checking if you need to update bottom. Once you find top, there is no point checking if you need to update it. So think about splitting your loops up so that you update less state in the loop (but without increasing the number of pixels you consider)

Then you have to start reducing the overhead-per-pixel and taking advantage of your knowledge of the processor/bus/memory architecture - e.g. if you have a 64-bit processor, reading 32 bits at a time is very likely to be slower than reading 64 bits at a time - so use longs (Int64) to compare pairs of pixels per iteration rather than only one. This will make better use of the processor's register width and halve the number of iterations of your loop (halve the number of adds to your x value, and the number of branches to go around the loop again). (Note: You will have to be careful of images with odd Width, and if you find a pair of pixels that are different, you will need to check each pixel within the pair to determine exactly where the diffs lie). You may get further gains using wider data types depending on your processor/bus architecture.

Next, you can see if cache coherence helps. In your second (bottom/right) loop you are iterating in reverse through the X values. Depending on your processor architecture this could be much slower than iterating through them forwards - so you may get a better time on average by searching forwards through each scanline.

(Note: The above might not be "the optimal way" to do this, and there are likely to be hardware acceleration tricks that will make the processor faster, but hopefully it'll give you some ideas about how being lazy can help you to go much faster)

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

thanks for ur suggestion. from ur explanation it seems u r very much experience developer but i am not. this is first time i am working with image processing routine. can u please refactor or modify my code to gain better performance but the output would be same. thanks
I think you'll learn a lot more and have more fun if you do it for yourself. What I've suggested above are only small tweaks to the code you already have.
0

It's not really an answer for the question, but maybe this will help.

First of all i think you spend most of the time on the Drawing of the image on the screen and not comparing the images. Try to measure the time without the draw which usually is a heavy operation.

Second, it will be a good idea to run the method once (or twice) before the time measure because the first time you run a code it might take a little bit longer to run, even better is to run it 1000 times and divide the total time by 1000 to get an average estimation.

and last but not least, maybe you can skip few pixels and check every second pixel and still it will give you good results ?

Improve this answer

Comments

0

In such code x > right inside loop can be removed (we have same check in loop "x")

for (int x = _newBitmap.Width - 1; x > right; x--) // Found a change. // if (x > right) { right = x; }

But try to refactor code before optimization.

Improve this answer

2 Comments

if i comment the above line if (x > right) { right = x; } then how much time will be reduce.
You should comment only "if". The body "right = x" can be left, but after this "x" loop will terminate. Performance will increase a little.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.