Databases
StackOverflow2013
Postsdbo
POC# Bitmap Cross Correlation Algorithm Performance Issues
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POC# Bitmap Cross Correlation Algorithm Performance Issues
    text
    copied!<p>This is my first question on stack overflow, so far I found all the answers to my problems in no time. Thanks a lot! Usually I am mostly into PLC programming, my knowledge of the PC world is rather limited and this is my first time ever using C#.</p> <p>So, I happened to try to cross correlate two pixel areas in two bitmaps, according to the paper here: <a href="http://users.ox.ac.uk/~atdgroup/publications/Rankov,%20V.,%20Proceedings%20of%20Spie,%20Vol.%205701,2005.pdf" rel="nofollow">http://users.ox.ac.uk/~atdgroup/publications/Rankov,%20V.,%20Proceedings%20of%20Spie,%20Vol.%205701,2005.pdf</a></p> <p>[EDIT] The goal is to find the exact location of the match in order to perform stitching of the two images. I also took out some of the commented code to make the overview better (I will open another question for the moving average part). [/EDIT]</p> <p>My problems are the proper implementation of a moving average and general performance tweaks, where I hope you guys can help me out.</p> <p>The bitmaps have a fixed overlap in all directions which I know (10%), so I can keep the search areas (called composite area in source code below) rather small, but not small enough as it seems. I also assume that they have the same size and pixel format. The performance of my algorithm does not satisfy me, though. I have a feeling (mostly because I lack "deep" knowledge and experience), that there is lots of room for improvement.</p> <p>I figured out the main performance "eaters" as the following (see source code below):</p> <ul> <li>Calculation of pixel values in separate method (mostly introduced for readability, quickly discarded)</li> <li>four nested for loops</li> </ul> <p>Here are some time measurements of release (Core Duo 2.4GHz, 4GB) for two 950px * 950px, 24RGB bitmaps. Search Area (composite image area) was 70px * 800px, sample area 8px * 400px.</p> <ul> <li>separate average function: 5519ms</li> <li>average function inlined: 5350ms (only?)</li> <li>[EDIT] changes suggested by Yaur: 700ms![/EDIT]</li> </ul> <p>In general, using smaller sample and search areas (4x40 and 30x100) gives pretty fast times, ranging from a few ms to a few hundret ms. Unfortunately, in order to be safe to find matches I have to use big areas. Before going into subsampling etc., I would like to be sure that my current algorithm is not completely out of the world. </p> <p>Are there any tweaks / tricks or general improvements you can think of? Every hint would be gladly appreciated.</p> <p>[EDIT] The correlation method (improved drastically):</p> <pre class="lang-cs prettyprint-override"><code>private unsafe void CrossCorrelate(ref float CCCoefficient, ref Point SampleMatchLocation) { float res = 0; float tmpRes = 0; // get bit data of sample area BitmapData bmdSample = m_bmpSampleRaw.LockBits(m_rectSampleArea, ImageLockMode.ReadOnly, m_bmpSampleRaw.PixelFormat); byte* pSample = (byte*)(void*)bmdSample.Scan0; // calculate sample average and coefficient 1 (stays same for all iterations) int SampleAvg = GetAverage(bmdSample, 0, bmdSample.Width, 0, bmdSample.Height); float CN1 = GetCN1(bmdSample, SampleAvg); int CompAvg = 0; BitmapData bmdComp = null; Rectangle compRect; int SearchHeightLimit = m_rectSearchArea.Height - m_rectSampleArea.Height; int SearchWidthLimit = m_rectSearchArea.Width - m_rectSampleArea.Width; int SearchLocX = m_rectSearchArea.X; int SearchLocY = m_rectSearchArea.Y; int SampleHeight = m_rectSampleArea.Height; int SampleWidth = m_rectSampleArea.Width; int a = 0; // used to calculate power of 2 without using Math.Pow // iterate through search area, // in case of equal sizes make sure it iterates at least once if (SearchHeightLimit == 0) SearchHeightLimit++; if (SearchWidthLimit == 0) SearchWidthLimit++; for (int i = 0; i &lt; SearchHeightLimit; i++) { for (int j = 0; j &lt; SearchWidthLimit; j++) { int CN0Sum = 0; int CN2Sum = 0; // create composite pixel data at current search location compRect = new Rectangle(SearchLocX + j, SearchLocY + i, SampleWidth, SampleHeight); bmdComp = m_bmpCompositeRaw.LockBits(compRect, ImageLockMode.ReadOnly, m_bmpCompositeRaw.PixelFormat); byte* pComp = (byte*)(void*)bmdComp.Scan0; // get average pixel value of sample area CompAvg = GetAverage(bmdComp, 0, bmdComp.Width, 0, bmdComp.Height); for (int y = 0; y &lt; SampleHeight; y++) { for (int x = 0; x &lt; SampleWidth; x++) { int Sidx = (y * bmdSample.Stride) + x * m_iPixelSize; CN0Sum += (pSample[Sidx] + pSample[Sidx + 1] + pSample[Sidx + 2] - SampleAvg) * (pComp[Sidx] + pComp[Sidx + 1] + pComp[Sidx + 2] - CompAvg); a = pComp[Sidx] + pComp[Sidx + 1] + pComp[Sidx + 2] - CompAvg; CN2Sum += (a * a); } } // release pixeldata of current search area (commented out when using moving average) m_bmpCompositeRaw.UnlockBits(bmdComp); float CN2 = (float)Math.Sqrt(CN2Sum); float CN0 = (float)CN0Sum; tmpRes = CN0 / (CN1 * CN2); if (tmpRes &gt; res) { res = tmpRes; SampleMatchLocation.X = m_rectSearchArea.X + j; SampleMatchLocation.Y = m_rectSearchArea.Y + i; } // exit early if perfect match found if (res == 1) { m_bmpSampleRaw.UnlockBits(bmdSample); CCCoefficient = res; return; } } } m_bmpSampleRaw.UnlockBits(bmdSample); CCCoefficient = res; } </code></pre> <p>[/EDIT] The correlation method (original):</p> <pre class="lang-cs prettyprint-override"><code>float res = 0; float tmpRes = 0; // get bit data of sample area BitmapData bmdSample = m_bmpSampleRaw.LockBits(m_rectSampleArea, ImageLockMode.ReadOnly, m_bmpSampleRaw.PixelFormat); // calculate sample average and coefficient 1 (stays same for all iterations) int SampleAvg = GetAverage(bmdSample, 0, bmdSample.Width, 0, bmdSample.Height); float CN1 = GetCN1(bmdSample, SampleAvg); int CompAvg = 0; BitmapData bmdComp = null; Rectangle compRect; unsafe { // iterate through search area (I know it skips if areas have same size) for (int i = 0; i &lt; (m_rectSearchArea.Height - m_rectSampleArea.Height); i++) { for (int j = 0; j &lt; (m_rectSearchArea.Width - m_rectSampleArea.Width); j++) { int CN0Sum = 0; int CN2Sum = 0; // create composite pixel data at current search location compRect = new Rectangle(m_rectSearchArea.X + j, m_rectSearchArea.Y + i, m_rectSampleArea.Width, m_rectSampleArea.Height); bmdComp = m_bmpCompositeRaw.LockBits(compRect, ImageLockMode.ReadOnly, m_bmpCompositeRaw.PixelFormat); CompAvg = GetAverage(bmdComp, 0, bmdComp.Width, 0, bmdComp.Height); // the actual correlation loops byte* pSample = (byte*)(void*)bmdSample.Scan0; byte* pComp = (byte*)(void*)bmdComp.Scan0; for (int y = 0; y &lt; bmdSample.Height; y++) { for (int x = 0; x &lt; bmdSample.Width; x++) { int Sidx = (y * bmdSample.Stride) + x * m_iPixelSize; // same stride assumed //CN0Sum += (GetPixelValue(pSample, Sidx) - SampleAvg) * (GetPixelValue(pComp, Sidx) - CompAvg); CN0Sum += (pSample[Sidx] + pSample[Sidx + 1] + pSample[Sidx + 2] - SampleAvg) * (pComp[Sidx] + pComp[Sidx + 1] + pComp[Sidx + 2] - CompAvg); //CN2Sum += (long)Math.Pow((GetPixelValue(pComp, Sidx) - CompAvg), 2); CN2Sum += (int)Math.Pow((pComp[Sidx] + pComp[Sidx + 1] + pComp[Sidx + 2] - CompAvg), 2); } } // release pixeldata of current search area m_bmpCompositeRaw.UnlockBits(bmdComp); tmpRes = (float)CN0Sum / (CN1 * (float)Math.Sqrt(CN2Sum)); if (tmpRes &gt; res) { res = tmpRes; SampleMatchLocation.X = m_rectSearchArea.X + j; SampleMatchLocation.Y = m_rectSearchArea.Y + i; } // exit early if perfect match found if (res == 1) { m_bmpSampleRaw.UnlockBits(bmdSample); CCCoefficient = res; return; } } } } // unsafe m_bmpSampleRaw.UnlockBits(bmdSample); CCCoefficient = res; </code></pre> <p>The method used to calculate the average of a specified area:</p> <pre class="lang-cs prettyprint-override"><code>private int GetAverage(BitmapData bmpData, int X1, int X2, int Y1, int Y2) { int total = 0; if (X2 == 0 || X2 == X1) X2++; if (Y2 == 0 || Y2 == Y1) Y2++; unsafe { byte* p = (byte*)(void*)bmpData.Scan0; for (int y = Y1; y &lt; Y2; y++) { for (int x = X1; x &lt;X2; x++) { int idx = (y * bmpData.Stride) + x * m_iPixelSize; //total += GetPixelValue(p, idx); total += p[idx] + p[idx + 1] + p[idx + 2]; } } } return total / ((X2 - X1) * (Y2 - Y1)); } </code></pre> <p>Small function to calculate pixel averages, discarded this one quickly:</p> <pre class="lang-cs prettyprint-override"><code>private unsafe Int32 GetPixelValue(byte* pPixel, int idx) { // add up all color values and return return pPixel[idx] + pPixel[idx + 1] + pPixel[idx + 2]; } </code></pre> <p>The function used to calculate the never changing part of the equation</p> <pre class="lang-cs prettyprint-override"><code>private float GetCN1(BitmapData bmpData, long avg) { double Sum = 0; unsafe { byte* p = (byte*)(void*)bmpData.Scan0; for (int y = 0; y &lt; bmpData.Height; y++) { for (int x = 0; x &lt; bmpData.Width; x++) { int idx = (y * bmpData.Stride) + x * m_iPixelSize; Sum += Math.Pow(p[idx] + p[idx + 1] + p[idx + 2] - avg, 2); } } } return (float)Math.Sqrt(Sum); } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload