Fast joint template machining

Patent metadata

Field	Value
Publication number	US-10346716-B2
Application number	US-201715706610-A
Country	US
Kind code	B2
Filing date	Sep 15, 2017
Priority date	Sep 15, 2017
Publication date	Jul 9, 2019
Grant date	Jul 9, 2019

Abstract

An efficient method and apparatus for identifying one or more targets in an image is presented. A matching operation is performed that compares the image against multiple templates jointly. The multiple templates are sorted into multiple clusters. The joint template matching operation achieves an improvement in performance by focusing on a subset of the clusters. For each grid location, clusters whose reference templates have low matching scores with the image content of the grid location are bypassed or excluded from the matching operation. This saving in computation load is made possible by the clustering of the templates, which can be performed offline and does not affect the performance of the joint template matching operation.

First claim

What is claimed is:

1. A computer-implemented method comprising:
receiving an image;
receiving a plurality of templates that are sorted into a plurality of clusters of templates, each cluster associated with a reference template, wherein each template of the cluster differs with the reference template of the cluster by less than a radius of the cluster;
identifying a plurality of grid locations in the received image; and
for each grid location of the image:
comparing the reference template of each of the plurality of clusters with the image content of the grid location to produce a matching score for the reference template;
selecting one or more clusters based on the matching scores of the reference templates of the plurality of clusters for the grid location; and
comparing each template of each selected cluster with the image content of the grid location to determine whether the template matches the image content of the grid location; and

reporting information based on the comparison between the plurality of templates and the image content of the plurality of grid locations
for each grid location of the image and for each cluster, identifying a best case score and a worst case score for the cluster,
wherein the best case score of a cluster is computed by subtracting the cluster's radius from a distance value of the cluster's reference template for the grid location and the best case score of the cluster is computed by adding the cluster's radius with the distance value of the clusters reference template for the grid location.

2. The computer-implemented method of claim 1 , further comprising:
for each grid location of the image and for each cluster, identifying a best case score and a worst case score for the cluster based on the matching score of the cluster's reference template for the grid location and the radius of the cluster.

3. The computer-implemented method of claim 2 , wherein selecting one or more clusters based on the matching scores of the reference templates for the grid location comprises identifying a cluster to bypass based on the best case scores and worst case scores of the clusters, respectively, wherein the image content of the grid location is not compared with the templates of the identified cluster.

4. The computer-implemented method of claim 3 , wherein a cluster is identified as a bypass cluster for the grid location when the cluster's best case score is worse than the worst score of another cluster for the grid location.

5. The computer-implemented method of claim 1 , wherein the templates of each cluster are identified for recognizing a same category of targets.

6. The computer-implemented method of claim 1 , further comprising receiving clustering information identifying each cluster, the templates of each cluster, the reference template of each cluster, and the radius of each cluster.

7. A computing device comprising:
a communications circuit configured to receive a plurality of templates that are sorted into a plurality of clusters of templates, each cluster associated with a reference template, wherein each template of the cluster differs with the reference template of the cluster by less than a radius of the cluster;
a set of processing units;
a storage device storing a set of instructions, wherein an execution of the set of instructions by the set of processing units configures the computing device to perform acts, comprising:
receiving an image comprising a plurality of, grid locations;
for each grid location of the image:
comparing the reference template of each of the plurality of clusters with the image content of the grid location to produce a matching score for the reference template;
selecting one or more clusters based on the matching scores of the reference templates of the plurality of clusters for the grid location; and
comparing each template of each selected cluster with the image content of the grid location to determine whether the template matches the image content of the grid location; and

reporting information based on the comparisons between the plurality of templates and the image content of the plurality of grid locations
for each grid location of the image and for each cluster, identifying a best case score and a worst case score for the cluster,
wherein the best case score of a cluster is computed by subtracting the cluster's radius from a distance value of the cluster's reference template for the grid location and the best case score of the cluster is computed by adding the cluster's radius with the distance value of the clusters reference template for the grid location.

8. The computing device of claim 7 , wherein execution of the set of instructions further configures the computing device to perform acts comprising:
for each grid location of the image and for each cluster, identifying a best case score and a worst case score for the cluster based on the matching score of the cluster's reference template for the grid location and the radius of the cluster.

9. The computing device method of claim 8 , wherein selecting one or more clusters based on the matching scores of the reference templates for the grid location comprises identifying a cluster to bypass based on the best case scores and worst case scores of the clusters, wherein the image content of the grid location is not compared with the templates of the identified cluster.

10. The computing device of claim 9 , wherein a cluster is identified as a bypass cluster for the grid location when the cluster's best case score is worse than the worst score of another cluster for the grid location.

11. The computing device of claim 7 , wherein the templates of each cluster are identified for recognizing a same category of targets.

12. The computing device of claim 7 , wherein the communications circuit is further configured to receive clustering information identifying each cluster, the templates of each cluster, the reference template of each cluster, and the radius of each cluster.

13. A computer program product comprising:
one or more non-transitory computer-readable storage device and program instructions stored on at least one of the one or more non-transitory storage devices, the program instructions executable by a processor, the program instructions comprising sets of instructions for:
receiving an image;
receiving a plurality of templates that are sorted into a plurality of clusters of templates, each cluster associated with a reference template, wherein each template of the cluster differs with the reference template of the cluster by less than a radius of the cluster;
identifying a plurality of grid locations in the received image; and
for each grid location of the image:
comparing the reference template of each of the plurality of clusters with the image content of the grid location to produce a matching score for the reference template,
selecting one or more clusters based on the matching scores of the reference templates of the plurality of clusters for the grid location; and
comparing each template of each selected cluster with the image content of the grid location to determine whether the template matches the image content of the grid location; and
reporting information based on the comparison between the plurality of templates and the image content of the plurality of grid locations
for each grid location of the image and for each cluster, identifying a best case score and a worst case score for the cluster,
wherein the best case score of a cluster is computed by subtracting the cluster's radius from a distance value of the cluster's reference template for the grid location and the best case sc

Assignees

• IBM

Inventors

• Gao Peng
• Hu Guo Qiang
• Huang Jing Chang
• Yan jun chi
• Zhu Jun

Classifications

• G06V10/763

  Non-hierarchical techniques, e.g. based on statistics of modelling distributions · CPC title

• G06V30/1914

  Determining representative reference patterns, e.g. averaging or distorting patterns; Generating dictionaries, e.g. user dictionaries · CPC title

• G06V30/19173

  Classification techniques · CPC title

• G06V40/50 Primary

  Maintenance of biometric data or enrolment thereof · CPC title

• G06V10/751

  Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching · CPC title