Source(compressed from original so that I could post it)
Template(I require the template to support alpha masking)
The source image with generated regions and the match location of the template
I'll start with the results.
When I perform a standard template match on the source/template pair it takes 475 ms. From there I tried multi-region template matching in parallel using Parallel.Foreach. The best result I got was with a dimension of 4x4 which brought the time down to 184 ms. I was happy with that until I observed the individual region processing times. When not performed in parallel they continually drop albeit on a curve. Even if I take the case of 4x4, which took 184 ms on average, and look at the individual region times, which are 56 ms on average, shouldn't the 4x4 multi region have taken less time? Assuming that all the threads executed concurrently, 184 ms seems high(I know what you're thinking :-) The individual region times DO spike when performed in parallel, but in serial they are usually within 5% of eachother).
Here is the code I wrote for the test. I apologize for the length:
public static class TemplateMatchTest
{
public class RegionJob
{
public Point ImageLocation;
public Image<Bgr, byte> SourceRegion;
public Image<Bgra, byte> Template;
public List<Rectangle> Results;
public double averageMatchTime;
}
public static void PerformanceTest()
{
Image<Bgra, Byte> template = Emgu.CV.CvInvoke.Imread("Template.png", Emgu.CV.CvEnum.ImreadModes.Unchanged).ToImage<Bgra, byte>();
Image<Bgr, Byte> source = Emgu.CV.CvInvoke.Imread("Source.png", Emgu.CV.CvEnum.ImreadModes.Unchanged).ToImage<Bgr, byte>();
int sampleSize = 30;
List<double> parallelAverages = new List<double>();
double cumulative = 0;
// -- Calculate the average time to find the template using parallel processing over image sections
for (int j = 1; j <= 10; j++)
{
cumulative = 0;
for (int i = 0; i < sampleSize; i++)
{
DateTime matchStart = DateTime.Now;
List<Rectangle> results = ParallelTemplateMatchBySection(source, template, 4000, j, 1.2f);
double elapsed = DateTime.Now.Subtract(matchStart).TotalMilliseconds;
cumulative += elapsed;
}
double parallelMatchAverage = cumulative / sampleSize;
parallelAverages.Add(parallelMatchAverage);
}
// -- Calculate the average time to find the template using standard template matching
cumulative = 0;
for(int i = 0; i < sampleSize; i++)
{
DateTime matchStart = DateTime.Now;
List<Rectangle> results = FindImageInImage(source, template, 4000);
double elapsed = DateTime.Now.Subtract(matchStart).TotalMilliseconds;
cumulative += elapsed;
}
double serialAverage = cumulative / sampleSize;
// -- Calculate the average time per region when calculated in serial
List<double> serialRegionAverages = new List<double>();
for (int j = 1; j <= 10; j++)
{
cumulative = 0;
List<RegionJob> serialRegions = CalculateRegionProcessingTime(source, template, 4000, j, 1.2f, sampleSize);
foreach(RegionJob serialRegion in serialRegions)
{
cumulative += serialRegion.averageMatchTime;
}
double serialRegionAverage = cumulative / serialRegions.Count;
serialRegionAverages.Add(serialRegionAverage);
}
Console.WriteLine("===================================================================================================================");
Console.WriteLine("Average times to perform standard template matching over " + sampleSize.ToString() + " samples:");
Console.WriteLine(serialAverage.ToString("F2"));
Console.WriteLine("===================================================================================================================");
Console.WriteLine("Average times to perform template matching by region over " + sampleSize.ToString() + " samples:");
for(int i = 0; i < parallelAverages.Count; i++)
{
double curAverage = parallelAverages[i];
Console.WriteLine("Dimension : " + (i + 1).ToString() + "X" + (i + 1).ToString() + " | Average: " + curAverage.ToString("F2"));
}
Console.WriteLine("===================================================================================================================");
Console.WriteLine("Average individual region times calculated in serial over " + sampleSize.ToString() + " samples:");
for (int i = 0; i < serialRegionAverages.Count; i++)
{
double curRegionAverage = serialRegionAverages[i];
Console.WriteLine("Dimension : " + (i + 1).ToString() + "X" + (i + 1).ToString() + " | Region Average: " + curRegionAverage.ToString("F2"));
}
Console.WriteLine("===================================================================================================================");
}
public static List<RegionJob> CalculateRegionProcessingTime(Image<Bgr, byte> Source, Image<Bgra, byte> Template, int Threshold, int Dimension, float OverlapCoef, int SampleSize)
{
List<RegionJob> resultRegions = GenerateRegions(Source, Template, Dimension, OverlapCoef);
for(int i = 0; i < resultRegions.Count; i++)
{
RegionJob curRegion = resultRegions[i];
double cumulative = 0;
for(int j = 0; j < SampleSize; j++)
{
DateTime matchStart = DateTime.Now;
curRegion.Results = FindImageInImage(curRegion.SourceRegion, curRegion.Template, Threshold);
double elapsed = DateTime.Now.Subtract(matchStart).TotalMilliseconds;
cumulative += elapsed;
}
curRegion.averageMatchTime = cumulative / SampleSize;
}
return resultRegions;
}
public static List<Rectangle> ParallelTemplateMatchBySection(Image<Bgr, byte> Source, Image<Bgra, byte> Template, int Threshold, int Dimension, float OverlapCoef)
{
List<Rectangle> results = new List<Rectangle>();
List<RegionJob> regions = GenerateRegions(Source, Template, Dimension, OverlapCoef);
Parallel.ForEach(regions, curRegion =>
{
curRegion.Results = FindImageInImage(curRegion.SourceRegion, curRegion.Template, Threshold);
});
foreach(RegionJob curRegion in regions)
{
foreach (Rectangle curRectangle in curRegion.Results)
{
results.Add(new Rectangle(curRectangle.X + curRegion.ImageLocation.X,
curRectangle.Y + curRegion.ImageLocation.Y,
curRegion.Template.Width,
curRegion.Template.Height));
}
}
return results;
}
public static List<Rectangle> FindImageInImage(Image<Bgr, Byte> Source, Image<Bgra, Byte> Template, int Threshold)
{
List<Rectangle> foundLocations = new List<Rectangle>();
// -- Generate the mask based on the template's alpha channel
Image<Bgr, Byte> mask = new Image<Bgr, Byte>(Template.Width, Template.Height);
for (int y = 0; y < Template.Height; y++)
{
for (int x = 0; x < Template.Width; x++)
{
if (Template.Data[y, x, 3] <= 128)
{
mask.Data[y, x, 0] = 0;
mask.Data[y, x, 1] = 0;
mask.Data[y, x, 2] = 0;
}
else
{
mask.Data[y, x, 0] = 255;
mask.Data[y, x, 1] = 255;
mask.Data[y, x, 2] = 255;
}
}
}
// -- Perform the template matching
Image<Gray, float> result = new Image<Gray, float>(Source.Width, Source.Height);
Image<Bgr, Byte> templateConverted = Template.Convert<Bgr, byte>();
Emgu.CV.CvInvoke.MatchTemplate(Source, templateConverted, result, TemplateMatchingType.Sqdiff, mask);
float[,] data = (float[,])result.Mat.GetData();
// -- Locate matches based on threshold
int width = Source.Width - Template.Width + 1;
int height = Source.Height - Template.Height + 1;
int templateWidth = Template.Width;
int templateHeight = Template.Height;
for (int x = 0; x < width; x++)
{
for (int y = 0; y < height; y++)
{
float curValue = data[y, x];
if (curValue <= Threshold)
{
Rectangle foundPoint = new Rectangle(x, y, templateWidth, templateHeight);
foundLocations.Add(foundPoint);
}
}
}
// -- Filter overlapping results
int curCheckIndex = 0;
while (curCheckIndex < foundLocations.Count - 1)
{
Rectangle curCheckRect = foundLocations[curCheckIndex];
for (var i = foundLocations.Count - 1; i > curCheckIndex; i--)
{
Rectangle curEndRect = foundLocations[i];
if (curCheckRect.IntersectsWith(curEndRect))
{
foundLocations.Remove(curEndRect);
}
}
curCheckIndex++;
}
return foundLocations;
}
public static List<RegionJob> GenerateRegions(Image<Bgr, Byte> Source, Image<Bgra, Byte> Template, int Dimension, float OverlapCoef)
{
List<RegionJob> regions = new List<RegionJob>();
float regionWidth = Source.Width / Dimension;
float regionHeight = Source.Height / Dimension;
float overlapX = Template.Width * OverlapCoef;
float overlapY = Template.Height * OverlapCoef;
for(int x = 0; x < Dimension; x++)
{
for(int y = 0; y < Dimension; y++)
{
float curX, curY, curWidth, curHeight;
if(x == 0)
{
curX = 0;
curWidth = regionWidth + overlapX / 2;
}
else if(x == Dimension - 1)
{
curX = (x * regionWidth) - overlapX / 2;
curWidth = Source.Width - curX;
}
else
{
curX = (x * regionWidth) - overlapX / 2;
curWidth = regionWidth + overlapX;
}
if (y == 0)
{
curY = 0;
curHeight = regionHeight + overlapY / 2;
}
else if(y == Dimension - 1)
{
curY = (y * regionHeight) - overlapY / 2;
curHeight = Source.Height - curY;
}
else
{
curY = (y * regionHeight) - overlapY / 2;
curHeight = regionHeight + overlapY;
}
Rectangle curRect = new Rectangle((int)curX, (int)curY, (int)curWidth, (int)curHeight);
RegionJob newRegion = new RegionJob();
newRegion.Template = Template.Clone();
Source.ROI = curRect;
newRegion.SourceRegion = Source.Copy();
newRegion.ImageLocation = new Point((int)curX, (int)curY);
regions.Add(newRegion);
Source.ROI = Rectangle.Empty;
}
}
return regions;
}
}
My goal is to reduce the generalized multi-region template matching function to perform near real-time on HD graphics. I need the matching to consider color so I can't desaturate it. I also require alpha masking in the template which rules out Cuda based template matching(As far as I know..)
I'm hoping the community has some tips on some approaches I can use to improve performance. Am I doing multithreading badly? I tried using individual threads that I created myself but the results were very similar to those above. Is the Open.CV library sharing resources for Emgu.CV.CVInvoke.MatchTemplate that is slowing down parallel processing? I read that the library should scale well in parallel.
My system specs:
Thanks for checking out this post. Sorry again for the length!