Difference between revisions of "Example Template Matching"

From BoofCV
Jump to navigationJump to search
m
m
(11 intermediate revisions by the same user not shown)
Line 1: Line 1:
= Template Matching Example =
<center>
<center>
<gallery widths=250px heights=200px>
<gallery widths=250px heights=200px>
File:Example_template_matches.jpg | Found matches for three different templates.
File:Example_template_matches.jpg | Found matches for the cursor with and without a mask.
File:Example_template_intensity.jpg | Match intensity for a template.
File:Example_template_intensity.jpg | Match intensity for a template.
</gallery>
</gallery>
</center>
</center>


Template matching finds all the points inside an image which match a template. A template is simply a smaller image.  Typically template matching is only used in highly controlled environments and doesn't work to well in natural scenes.  A template matching algorithm works by computing a fit score for each pixel in the image and then looking for local maximums.
Template matching compares a smaller image (the template) against every possible location in a larger target image. A match is declared the fit score is a local peak and above a threshold.  Typically template matching is only used in highly controlled environments and doesn't work to well in natural scenes.  It's also extremely computationally expensive and larger images/templates are likely to take an excessive amount of time to process.  


The example below is intended to demonstrate the strengths and weaknesses of template matching.  For each template the number of matches returned needs to be specified.  If the number of matches is known then the results are good in this example, but if too many are requested the some of the results are noise.  The intensity image is shown for a match.  Notice how ambiguous the results are.
The example below is intended to demonstrate the strengths and weaknesses of template matching.  For each template the number of matches returned needs to be specified.  If the number of matches is known then the results are good in this example, but if too many are requested the some of the results are noise.  The intensity image is shown for a match.  Notice how ambiguous the results are.


Example Code:
Example Code:
* [https://github.com/lessthanoptimal/BoofCV/blob/v0.11/examples/src/boofcv/examples/ExampleTemplateMatching.java ExampleTemplateMatching.java]
* [https://github.com/lessthanoptimal/BoofCV/blob/v0.37/examples/src/main/java/boofcv/examples/features/ExampleTemplateMatching.java ExampleTemplateMatching.java]


Concepts:
Concepts:
Line 23: Line 21:
/**
/**
  * Example of how to find objects inside an image using template matching.  Template matching works
  * Example of how to find objects inside an image using template matching.  Template matching works
  * well when there is little noise in the image and the object's appearance is known and static.
  * well when there is little noise in the image and the object's appearance is known and static.  It can
* also be very slow to compute, depending on the image and template size.
  *
  *
  * @author Peter Abeles
  * @author Peter Abeles
  */
  */
public class ExampleTemplateMatching {
public class ExampleTemplateMatching {
/**
/**
* Demonstrates how to search for matches of a template inside an image
* Demonstrates how to search for matches of a template inside an image
Line 34: Line 32:
* @param image          Image being searched
* @param image          Image being searched
* @param template        Template being looked for
* @param template        Template being looked for
* @param mask            Mask which determines the weight of each template pixel in the match score
* @param expectedMatches Number of expected matches it hopes to find
* @param expectedMatches Number of expected matches it hopes to find
* @return List of match location and scores
* @return List of match location and scores
*/
*/
private static List<Match> findMatches(ImageFloat32 image, ImageFloat32 template,
private static List<Match> findMatches(GrayF32 image, GrayF32 template, GrayF32 mask,
  int expectedMatches) {
  int expectedMatches) {
// create template matcher.
// create template matcher.
TemplateMatching<ImageFloat32> matcher =
TemplateMatching<GrayF32> matcher =
FactoryTemplateMatching.createMatcher(TemplateScoreType.SUM_DIFF_SQ, ImageFloat32.class);
FactoryTemplateMatching.createMatcher(TemplateScoreType.SUM_SQUARE_ERROR, GrayF32.class);


// Find the points which match the template the best
// Find the points which match the template the best
matcher.setTemplate(template, expectedMatches);
matcher.setImage(image);
matcher.process(image);
matcher.setTemplate(template, mask,expectedMatches);
matcher.process();


return matcher.getResults().toList();
return matcher.getResults().toList();
}
}


Line 55: Line 54:
* a better match to the template.
* a better match to the template.
*/
*/
public static void showMatchIntensity(ImageFloat32 image, ImageFloat32 template) {
private static void showMatchIntensity(GrayF32 image, GrayF32 template, GrayF32 mask) {
 
// create algorithm for computing intensity image
// create algorithm for computing intensity image
TemplateMatchingIntensity<ImageFloat32> matchIntensity =
TemplateMatchingIntensity<GrayF32> matchIntensity =
FactoryTemplateMatching.createIntensity(TemplateScoreType.SUM_DIFF_SQ, ImageFloat32.class);
FactoryTemplateMatching.createIntensity(TemplateScoreType.SUM_SQUARE_ERROR, GrayF32.class);


// apply the template to the image
// apply the template to the image
matchIntensity.process(image, template);
matchIntensity.setInputImage(image);
matchIntensity.process(template, mask);


// get the results
// get the results
ImageFloat32 intensity = matchIntensity.getIntensity();
GrayF32 intensity = matchIntensity.getIntensity();


// adjust the intensity image so that white indicates a good match and black a poor match
// White will indicate a good match and black a bad match, or the reverse
// the scale is kept linear to highlight how ambiguous the solution is
// depending on the cost function used.
float min = PixelMath.min(intensity);
float min = ImageStatistics.min(intensity);
float max = PixelMath.max(intensity);
float max = ImageStatistics.max(intensity);
float range = max - min;
float range = max - min;
PixelMath.plus(intensity, intensity, -min);
PixelMath.plus(intensity, -min, intensity);
PixelMath.divide(intensity, intensity, range);
PixelMath.divide(intensity, range, intensity);
PixelMath.multiply(intensity, intensity, 255.0f);
PixelMath.multiply(intensity, 255.0f, intensity);


BufferedImage output = new BufferedImage(image.width, image.height, BufferedImage.TYPE_INT_BGR);
BufferedImage output = new BufferedImage(image.width, image.height, BufferedImage.TYPE_INT_BGR);
VisualizeImageData.grayMagnitude(intensity, output, -1);
VisualizeImageData.grayMagnitude(intensity, output, -1);
ShowImages.showWindow(output, "Match Intensity");
ShowImages.showWindow(output, "Match Intensity", true);
}
}


public static void main(String args[]) {
public static void main(String[] args) {
 
// Load image and templates
// Load image and templates
String directory = "../data/applet/template/";
String directory = UtilIO.pathExample("template");


ImageFloat32 image = UtilImageIO.loadImage(directory + "desktop.png", ImageFloat32.class);
GrayF32 image = UtilImageIO.loadImage(directory ,"desktop.png", GrayF32.class);
ImageFloat32 templateX = UtilImageIO.loadImage(directory + "x.png", ImageFloat32.class);
GrayF32 templateCursor = UtilImageIO.loadImage(directory , "cursor.png", GrayF32.class);
ImageFloat32 templatePaint = UtilImageIO.loadImage(directory + "paint.png", ImageFloat32.class);
GrayF32 maskCursor = UtilImageIO.loadImage(directory , "cursor_mask.png", GrayF32.class);
ImageFloat32 templateBrowser = UtilImageIO.loadImage(directory + "browser.png", ImageFloat32.class);
GrayF32 templatePaint = UtilImageIO.loadImage(directory , "paint.png", GrayF32.class);


// create output image to show results
// create output image to show results
Line 96: Line 94:
Graphics2D g2 = output.createGraphics();
Graphics2D g2 = output.createGraphics();


// Searches for a small 'x' that indicates where a window can be closed
// Search for the cursor in the image.  For demonstration purposes it has been pasted 3 times
// Only two such objects are in the image so at best there will be one false positive
g2.setColor(Color.RED); g2.setStroke(new BasicStroke(5));
g2.setColor(Color.RED);
drawRectangles(g2, image, templateCursor, maskCursor, 3);
drawRectangles(g2, image, templateX, 3);
// show match intensity image for this template
// show match intensity image for this template
showMatchIntensity(image, templateX);
showMatchIntensity(image, templateCursor, maskCursor);
 
// Now it's try finding the cursor without a mask.  it will get confused when the background is black
g2.setColor(Color.BLUE); g2.setStroke(new BasicStroke(2));
drawRectangles(g2, image, templateCursor, null, 3);


// Now it searches for a specific icon for which there is only one match
// Now it searches for a specific icon for which there is only one match
g2.setColor(Color.BLUE);
g2.setColor(Color.ORANGE); g2.setStroke(new BasicStroke(3));
drawRectangles(g2, image, templatePaint, 1);
drawRectangles(g2, image, templatePaint, null, 1);
 
// Look for the Google Chrome browser icon. There is no match for this icon..
g2.setColor(Color.ORANGE);
drawRectangles(g2, image, templateBrowser, 1);
 
// False positives can some times be pruned using the error score.  In photographs taken
// in the real world template matching tends to perform very poorly


ShowImages.showWindow(output, "Found Matches");
ShowImages.showWindow(output, "Found Matches",true);
}
}


Line 121: Line 115:
*/
*/
private static void drawRectangles(Graphics2D g2,
private static void drawRectangles(Graphics2D g2,
  ImageFloat32 image, ImageFloat32 template,
  GrayF32 image, GrayF32 template, GrayF32 mask,
  int expectedMatches) {
  int expectedMatches) {
List<Match> found = findMatches(image, template, expectedMatches);
List<Match> found = findMatches(image, template, mask, expectedMatches);


int r = 2;
int r = 2;
Line 129: Line 123:
int h = template.height + 2 * r;
int h = template.height + 2 * r;


g2.setStroke(new BasicStroke(3));
for (Match m : found) {
for (Match m : found) {
System.out.printf("Match %3d %3d    score = %6.2f\n",m.x,m.y,m.score);
// this demonstrates how to filter out false positives
// the meaning of score will depend on the template technique
// if( m.score < -5 )  // This line is commented out for demonstration purposes
// continue;
// the return point is the template's top left corner
// the return point is the template's top left corner
int x0 = m.x - r;
int x0 = m.x - r;

Revision as of 13:16, 21 December 2020

Template matching compares a smaller image (the template) against every possible location in a larger target image. A match is declared the fit score is a local peak and above a threshold. Typically template matching is only used in highly controlled environments and doesn't work to well in natural scenes. It's also extremely computationally expensive and larger images/templates are likely to take an excessive amount of time to process.

The example below is intended to demonstrate the strengths and weaknesses of template matching. For each template the number of matches returned needs to be specified. If the number of matches is known then the results are good in this example, but if too many are requested the some of the results are noise. The intensity image is shown for a match. Notice how ambiguous the results are.

Example Code:

Concepts:

  • Template Matching

Example Code

/**
 * Example of how to find objects inside an image using template matching.  Template matching works
 * well when there is little noise in the image and the object's appearance is known and static.  It can
 * also be very slow to compute, depending on the image and template size.
 *
 * @author Peter Abeles
 */
public class ExampleTemplateMatching {
	/**
	 * Demonstrates how to search for matches of a template inside an image
	 *
	 * @param image           Image being searched
	 * @param template        Template being looked for
	 * @param mask            Mask which determines the weight of each template pixel in the match score
	 * @param expectedMatches Number of expected matches it hopes to find
	 * @return List of match location and scores
	 */
	private static List<Match> findMatches(GrayF32 image, GrayF32 template, GrayF32 mask,
										   int expectedMatches) {
		// create template matcher.
		TemplateMatching<GrayF32> matcher =
				FactoryTemplateMatching.createMatcher(TemplateScoreType.SUM_SQUARE_ERROR, GrayF32.class);

		// Find the points which match the template the best
		matcher.setImage(image);
		matcher.setTemplate(template, mask,expectedMatches);
		matcher.process();

		return matcher.getResults().toList();
	}

	/**
	 * Computes the template match intensity image and displays the results. Brighter intensity indicates
	 * a better match to the template.
	 */
	private static void showMatchIntensity(GrayF32 image, GrayF32 template, GrayF32 mask) {
		// create algorithm for computing intensity image
		TemplateMatchingIntensity<GrayF32> matchIntensity =
				FactoryTemplateMatching.createIntensity(TemplateScoreType.SUM_SQUARE_ERROR, GrayF32.class);

		// apply the template to the image
		matchIntensity.setInputImage(image);
		matchIntensity.process(template, mask);

		// get the results
		GrayF32 intensity = matchIntensity.getIntensity();

		// White will indicate a good match and black a bad match, or the reverse
		// depending on the cost function used.
		float min = ImageStatistics.min(intensity);
		float max = ImageStatistics.max(intensity);
		float range = max - min;
		PixelMath.plus(intensity, -min, intensity);
		PixelMath.divide(intensity, range, intensity);
		PixelMath.multiply(intensity, 255.0f, intensity);

		BufferedImage output = new BufferedImage(image.width, image.height, BufferedImage.TYPE_INT_BGR);
		VisualizeImageData.grayMagnitude(intensity, output, -1);
		ShowImages.showWindow(output, "Match Intensity", true);
	}

	public static void main(String[] args) {
		// Load image and templates
		String directory = UtilIO.pathExample("template");

		GrayF32 image = UtilImageIO.loadImage(directory ,"desktop.png", GrayF32.class);
		GrayF32 templateCursor = UtilImageIO.loadImage(directory , "cursor.png", GrayF32.class);
		GrayF32 maskCursor = UtilImageIO.loadImage(directory , "cursor_mask.png", GrayF32.class);
		GrayF32 templatePaint = UtilImageIO.loadImage(directory , "paint.png", GrayF32.class);

		// create output image to show results
		BufferedImage output = new BufferedImage(image.width, image.height, BufferedImage.TYPE_INT_BGR);
		ConvertBufferedImage.convertTo(image, output);
		Graphics2D g2 = output.createGraphics();

		// Search for the cursor in the image.  For demonstration purposes it has been pasted 3 times
		g2.setColor(Color.RED); g2.setStroke(new BasicStroke(5));
		drawRectangles(g2, image, templateCursor, maskCursor, 3);
		// show match intensity image for this template
		showMatchIntensity(image, templateCursor, maskCursor);

		// Now it's try finding the cursor without a mask.  it will get confused when the background is black
		g2.setColor(Color.BLUE); g2.setStroke(new BasicStroke(2));
		drawRectangles(g2, image, templateCursor, null, 3);

		// Now it searches for a specific icon for which there is only one match
		g2.setColor(Color.ORANGE); g2.setStroke(new BasicStroke(3));
		drawRectangles(g2, image, templatePaint, null, 1);

		ShowImages.showWindow(output, "Found Matches",true);
	}

	/**
	 * Helper function will is finds matches and displays the results as colored rectangles
	 */
	private static void drawRectangles(Graphics2D g2,
									   GrayF32 image, GrayF32 template, GrayF32 mask,
									   int expectedMatches) {
		List<Match> found = findMatches(image, template, mask, expectedMatches);

		int r = 2;
		int w = template.width + 2 * r;
		int h = template.height + 2 * r;

		for (Match m : found) {
			System.out.printf("Match %3d %3d    score = %6.2f\n",m.x,m.y,m.score);
			// this demonstrates how to filter out false positives
			// the meaning of score will depend on the template technique
//			if( m.score < -5 )  // This line is commented out for demonstration purposes
//				continue;

			// the return point is the template's top left corner
			int x0 = m.x - r;
			int y0 = m.y - r;
			int x1 = x0 + w;
			int y1 = y0 + h;

			g2.drawLine(x0, y0, x1, y0);
			g2.drawLine(x1, y0, x1, y1);
			g2.drawLine(x1, y1, x0, y1);
			g2.drawLine(x0, y1, x0, y0);
		}
	}
}