Fast joint template machining

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.

BACKGROUND

Technical Field

The present disclosure generally relates to image processing and object recognition.

Description of the Related Art

For visual analytics, template matching is a core capability for performing different types of image searches, such as searches for similar or duplicate images or objects. These searches can be used for indexing and clustering of samples, object detection, localization, classification, and geometry measuring. Template matching can also incorporate different features for similarity computing as a working pipeline.

SUMMARY

Some embodiments of the disclosure provide a method or apparatus for identifying one or more targets in an image. A computing device receives an image and a plurality of templates. The templates are sorted into a plurality of clusters of templates. Each cluster is associated with a reference template. Each template of the cluster differs with the reference template of the cluster by less than a radius of the cluster. The computing device identifies a plurality of grid locations in the received image. For each grid location of the image, the computing device (i) compares 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, (ii) selects one or more clusters based on the matching scores of the reference templates of the plurality of clusters for the grid location; and (iii) compares 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. The computing device then reports information based on the comparisons between the plurality of templates and the image content of the plurality of grid locations.

The preceding Summary is intended to serve as a brief introduction to some embodiments of the disclosure. It is not meant to be an introduction or overview of all inventive subject matter disclosed in this document. The Detailed Description that follows and the Drawings that are referred to in the Detailed Description will further describe the embodiments described in the Summary as well as other embodiments. Accordingly, to understand all the embodiments described by this document, a Summary, Detailed Description and the Drawings are provided. Moreover, the claimed subject matter is not to be limited by the illustrative details in the Summary, Detailed Description, and the Drawings, but rather is to be defined by the appended claims, because the claimed subject matter can be embodied in other specific forms without departing from the spirit of the subject matter.

DETAILED DESCRIPTION

Some embodiments of the disclosure provide an efficient method for identifying one or more targets in an image. The method performs a matching operation 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 (prior to the matching operation) and not affect the performance of the joint template matching operation.

FIG. 1illustrates a template-based image target identification method, consistent with an exemplary embodiment of the disclosure. The method provides a set of templates110that are organized into clusters. The method uses the clustered templates to identify matching target objects in a test image190(or an image with potential target objects). As illustrated, the method is implemented by a computing device101that organizes templates into clusters and a computing device102that uses the clustered templates to identify matching targets in the test image.

An image source105provides the test image190. The image source105may provide the test image as part of a sequence of images of a video. The image source105may also provide the test image190as a stand-alone still image, such as a photograph taken of a human body or of an electronic device for diagnostic purposes. The test image190may include image content that resemble one or more target objects that are to be identified through matching operation using the templates110.

The computing device(s)101(labeled as template organizer in the figure) receives templates110(from a template storage115). Each of these templates provides guidelines or sample image content for identifying a specific object or a specific type of objects in an image. The template-organizing computing device101groups or sorts the received templates into clusters of templates. As illustrated, the templates110includes templates for identifying objects A, B, C, etc., and the template-organizing computing device101processes the templates110to group them into clusters1,2,3, etc., each cluster of templates including one or more of the templates110. The information regarding the clusters of templates is recorded as clustering information120(stored in clustering storage125). The grouping of templates into clusters will be further described in Section I below.

The computing device(s)102(labeled as target identifier in the figure) retrieves templates110from the storage115for identifying targets in the test image190by performing matching operations between the test image190and the retrieved templates. The computing device102may select only a subset of the templates110for the matching operations, thereby accelerating the matching operations by avoiding matching operations for the unselected templates. The selection of the subset of templates110is based on the clustering information120stored in the storage125. The target-identifying computing device102generates a target report180that identifies the target objects in the test image190and their corresponding locations/positions in the test image190. The clustering-based template selection and matching operations will be further described in Section II below.

The computing devices101and102may be different devices that perform the template-organizing and the target-identifying operations at different locations and/or at different times. The computing devices101and102may also be the same device that performs both types of operations. In some embodiments, the computing devices101perform the template organizing operations to generate the clustering information120for distribution and use by multiple different computing devices (e.g., including the computing device102) for subsequent target-identifying operations. The target-identifying operations can be considered as “on-line” real-time operations where performance and/or latency are critical, while the template-organizing operations are “off-line” operations where performance and/or latency are not critical.

The computing device102may also be equipped with communications and/or network circuits for receiving templates and clustering information from the template storage115and/or the clustering storage125. The clustering storage125and the template storage115may also be storage devices that are part of the computing device102. The cluster storage125and the template storage115may also be within the same physical storage device.

I. Clustering of Templates

In some embodiments, standard clustering techniques are used to group the templates into clusters such that templates that are sufficiently similar to each other (e.g., having sufficiently high matching scores) are grouped as one cluster. In some embodiments, templates known for recognizing a same category of objects are grouped as one cluster (e.g., different views or perspective of a same object; small variations of a same visual pattern, etc.). Each cluster of templates is associated with a reference template. Each template of the cluster differs with the reference template of the cluster by less than a radius of the cluster.

FIG. 2conceptually illustrates the clustering of templates based on reference templates, consistent with an exemplary embodiment. The figure conceptually illustrates templates that are stored in the template storage115ofFIG. 1. These templates include templates for objects A, B, C, D, E, F, G, H, I, J, K, L, M, and N, in addition to several more templates that are not labeled in the illustration. These templates are grouped into clusters1,2,3,4, and5. Specifically, in the example ofFIG. 2, cluster1includes templates for objects A, D, E, and M. Cluster2includes templates for objects B, G, H, K, and L. Cluster3includes templates for objects C, F, I, J, and N. Clusters4and5each include several templates that are not labeled.

Each cluster is associated with a reference template. In some embodiments, the template-organizing computing device101identifies the reference template of each cluster from among the templates of the cluster. In some embodiments, the template-organizing computing device101identifies several templates from among the templates110to serve as reference templates, and each identified reference template is in turn used to identify one or more templates from among the templates110to be in the cluster of the reference template. In the example illustrated inFIG. 2, the reference template of cluster1is template291(for object E), the reference template of cluster2is template292(for object G), and the reference template of cluster3is template293(for object J). (The reference templates of clusters4and5are not illustrated.)

For each cluster of templates, the template-organizing computing device101also determines a radius. For some embodiments, the radius of a cluster is determined based on the distances between the reference template of the cluster and the other (non-reference) templates of the cluster. A distance between any two templates may be defined based on a correlation score between the image content of the two templates, or other metrics for measuring the degree of similarity between the two templates. Larger distance values indicate a higher degree of dissimilarity or poorer matching score, while smaller distance values indicate a higher degree of similarity or better matching score.

The template-organizing computing device101computes the distance values between the reference template of the cluster and each of the other templates of the cluster. The largest distance value (i.e., the distance between the reference template and its poorest matching template in the cluster) is in turn identified as the radius or range of the cluster. In the example ofFIG. 2, the radius of cluster1(R1) is defined as the largest distance value between the reference template291(the template for object E) and other templates in cluster1(templates for identifying objects A, D, and M). The radius for cluster2(R2) is defined as the largest distance value between the reference template292(the template for object G) and other templates in cluster2(templates for objects B, H, K, L). The radius of cluster3(R3) is defined as the largest distance value between the reference template293(the template for object J) and other templates in cluster3(templates for objects C, F, I, N). In some embodiments, the template-organizing computing device101selects the reference template of a cluster based on whether the choice of the reference template would result in the smallest possible radius for the cluster.

FIG. 3conceptually illustrates a process300for clustering templates and identifying reference templates, consistent with an exemplary embodiment. In some embodiments, the template-organizing computing device101performs the process300when it generates the clustering information120. In some embodiments, one or more processing units (e.g., processor) of the template-organizing computing device101perform the process300by executing instructions stored in a computer readable medium.

The process300starts when the template-organizing computing device101receives (at310) the templates110for identifying target objects in images (e.g., the test image190). The template-organizing computing device101groups (at315) the received templates into clusters, i.e., which templates belongs to the same cluster. The clustering of templates is described by reference toFIG. 2above.

The template-organizing computing device101identifies (at320) a cluster of templates. The template-organizing computing device101identifies (at330) a reference template for the cluster. The template-organizing computing device101also determines (at340) a radius for the cluster based on the distances between the reference template and other (non-reference) templates of the cluster. The identification of the reference template of a cluster and the determination of the radius of a cluster are described by reference toFIG. 2above.

The template-organizing computing device101determines (at350) whether there is another cluster whose reference template and radius have not been identified. If so, the process return to320. If the reference template and radius for all clusters have been identified, the process proceeds to360.

At360, the template-organizing computing device101stores information of the identified clusters, including information identifying each cluster, the templates of each cluster, the reference template of each cluster, and the radius of each cluster, as the clustering information (120) of the received templates. The same computing device or another computing device can use the stored clustering information to identify target objects in test images at a later time. The process300then ends.

II. Matching Using Clustered Templates

The target-identifying computing device102divides the test image into grid locations. The grid locations are scanned one by one for image content that matches target objects according to the stored templates110. For each grid location, rather than comparing the image content to every available template, the target-identifying computing device102uses the clustering information120to identify only a subset of the available templates for matching operations. Specifically, the target-identifying computing device102compares the image content of the grid location with templates of a few selected clusters while bypassing templates of other clusters.

In some embodiments, the target-identifying computing device102examines the reference template of each cluster to decide whether the cluster should be selected for matching operations with the image content of the grid location. Whether a cluster is to be bypassed or selected is determined based on a matching score or distance value between the reference template of the cluster and the image content of the grid location.

FIG. 4conceptually illustrates the computation of matching scores or distance values for reference templates of different clusters at different grid locations of the test image, consistent with an exemplary embodiment. The figure illustrates an example in which the test image190is divided into 7×5 grid locations (shown as grid locations411-417,421-427,431-437,441-447, and451-457.) The image content of each grid location may overlap with the image content of its neighboring grid locations. (In other words, the grid locations may represent a sliding window over the test image190.)

The target-identifying computing device102performs matching operations against the image content of the test image190for templates291,292, and293, which are reference templates of clusters1,2, and3, respectively (reference templates of other clusters are not illustrated). The result of the matching operations is illustrated as scores maps401,402, and403for the reference templates291,292, and293, respectively. Each scores map shows the distance values or matching scores for all 7×5 grid locations of the test image190. For example, at the grid location424, the distance value between the reference template291and the image content is ‘1’, according to scores map401, the distance value between the reference template292and the image content is ‘4’, according to scores map402, and the distance value between the reference template293and the image content is ‘3’, according to scores map403. As another example, at the grid location436, the distance values between the reference templates291-293and the image content are all ‘2’ according to scores map401-403.

For each grid location, the target-identifying computing device102uses the distance values of the different reference templates to identify clusters that can be bypassed. In some embodiments, identifying clusters that can be bypassed for a given grid location involves computation of the best case score (upper bound matching score or smallest possible distance value) and the worst case score (lower bound matching score or largest possible distance value) of each cluster for that grid location. The best case and worst case scores of a cluster are computed based on the matching score of the cluster's reference template and the radius of the cluster. A cluster is identified as a bypass cluster for that grid location if the cluster's best possible score is worse than the worst possible score of another cluster at that grid location. Conversely, a cluster whose best case score at a grid location is not worse than any of the worst case scores of other clusters cannot be bypassed (hence selected for matching operations at the grid location).

In some embodiments, 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 cluster's reference template for the grid location. (The best case score is capped at zero distance value if the radius of the cluster is greater than the distance value of the reference template.)

FIG. 5conceptually illustrates a method for determining whether to bypass a cluster of templates for matching operations, consistent with an exemplary embodiment. The target-identifying computing device102can perform this method when performing matching operations to identify target objects in the test image190based on templates110. The figure illustrates how a cluster of templates can be eliminated/bypassed from matching operations with the image content of a grid location. Specifically, The figure illustrates how to eliminate cluster1based on the best case scores of clusters1and the worst case score of cluster2.

In the figure, the reference templates of clusters1and2and a given grid location of the test image (grid location442in the example) are represented as positions of a two-dimensional plane. The distances among the different positions represent the difference (or distance value/matching score) among the reference templates and the image content of the grid location. As illustrated, the position501corresponds to reference template291of cluster1, the position502corresponds to reference template292of cluster2, and the position510corresponds to the image content of the grid location442.

The templates of cluster1are represented by a circle521, which centers at the reference template291with radius R1. The circle521represents the range of possible positions that correspond to templates cluster1. The distance535between the position501and the position510represents the distance value or the matching score for the reference template291at the grid location442. The best possible score for the cluster1at the grid location442corresponds to the closest distance (distance531) between the position510and the circle521, i.e., the distance value535of the reference template291minus the radius R1(The worst possible score for the cluster at the grid location442corresponds to the farthest distance539between the position510and the circle521, i.e., the distance value535of the reference template291plus the radius R1.)

To determine whether cluster1should be bypassed or not, the computing device compares the best possible score of cluster1with the worst possible score of other clusters. If the best possible score of cluster1is worse than the worst possible score of any other cluster, then the templates of cluster1will be bypassed. In the example ofFIG. 5, the best possible score of cluster1(distance531) is compared with the worst possible score of cluster2, which corresponds to the farthest distance549between the position510and the circle522, i.e., the distance value of the reference template291plus the radius R2of cluster2. (The circle522represents the range of possible positions that correspond to templates cluster1.)

Based on the example scores map401and402ofFIG. 4, the matching score (distance value) for the reference template291of cluster1at the grid location442is ‘9’, while the matching score for the reference template292of cluster2at the grid location442is ‘4’. The best score of cluster1is therefore 9−R1while the worst score of cluster2is 4+R2. Thus, if 9−R1is larger (worse) than 4+R2, cluster1can be bypassed for matching operations at grid location442; otherwise, cluster1cannot be bypassed unless 9−R1is worse than the worst score of another cluster at the grid location442.

FIG. 6illustrates example comparisons of best case and worst case scores of different clusters for identifying bypass clusters, consistent with an exemplary embodiment. For this example, the identification of bypass clusters is based on a comparison between clusters1,2, and3for all grid locations of the test image190(i.e., grid locations411-417,421-427,431-437,441-447, and451-457). The radius R1of cluster1is 3, the radius R2of cluster2is 2, and the radius R3of cluster3is 1. Comparisons based on other clusters are not illustrated.

The figure shows the scores map401,402, and403of reference templates291,292, and293. Based on the values of R1, R2, and R3. The figure shows best case (upper bound) scores maps601-603for clusters1,2, and3, respectively. The figure also shows the worst case (lower bound) scores maps691-693for clusters1,2, and3, respectively.

The figure illustrates several grid locations in which a cluster can be eliminated (e.g., identified for bypass) because the cluster's best case score is worse than another cluster's worst case score: at grid location423, cluster2can be bypassed because its best case score ‘7’ is worse than the worst case score ‘6’ for cluster3; at grid location455, cluster2can be bypassed because its best case score ‘9’ is worse than the worst case score ‘8’ of cluster1; at grid location437, cluster3can be bypassed because its best case score ‘6’ is worse than the worst case score ‘5’ of cluster2; and at grid location442, both clusters1and2can be bypassed because the best case score of cluster1and cluster2at the grid location (‘6’ and ‘4’ respectively) are both worse than the worst score of cluster3(‘2’).

FIG. 7conceptually illustrates identification of bypass clusters for all grid locations of the test image190, consistent with an exemplary embodiment. For each grid location, clusters that are bypassed are illustrated with strike-through. For example, templates in cluster3are bypassed for grid location455, and templates in both clusters1and2are bypassed for grid location422, etc. Clusters not illustrated with strike-through cannot be bypassed.

FIG. 8conceptually illustrates a process800for using clustered templates to identify target objects in a test image, consistent with an exemplary embodiment. The process uses clustering information regarding the templates to identify clusters of templates to bypass during matching operations. In some embodiments, one or more processing units (e.g., processor) of the target-identifying computing device102perform the process800by executing instructions stored in a computer readable medium.

The process800starts when the target-identifying computing device102receives (at810) a test image. The test image can be a still image or an image in a video. The test image is divided into grid locations (e.g., by the target-identifying computing device102). Each grid location includes a piece of the image content of the test image. The image content of neighboring grid locations may overlap as grid locations represent a sliding window over the test image. The target-identifying computing device102receives (at820) templates (e.g., templates110from the template storage115) for identifying target objects in images. The target-identifying computing device102also receives (at830) clustering information (e.g., by retrieving120from the clustering information storage125) for the templates. The clustering information may include information identifying each cluster, the templates of each cluster, the reference template of each cluster, and the radius of each cluster, etc.

The target-identifying computing device102identifies (at840) a grid location in the test image to search for target objects based on the templates. The target-identifying computing device102then compares (at850) each cluster's reference template with the image content of the identified grid location to produce a matching score (e.g., distance value based on correlation). For each cluster, the target-identifying computing device102computes (at855) a best case score and a worst case score at the grid location based on the radius of the cluster and the matching score of the cluster's reference template. For each cluster, the target-identifying computing device102determines (860) whether the cluster can be bypassed at the grid location based on the best case score of the cluster and the worst case scores of other clusters. Specifically, any cluster whose best case score is worse than the worst case score of any other cluster can be bypassed. The identification of bypass clusters is described by reference toFIG. 4-7.

The target-identifying computing device102then compares (at870) each template of each non-bypass cluster with the image content of the grid location to identify a matching template (or to determine whether there is a matching template at all). In some embodiments, the target-identifying computing device102identifies any template having matching score better than a certain threshold (e.g., distance value less than a threshold value) as being a matching template. This operation may result in zero, one, or multiple matching template(s).

The target-identifying computing device102determines (at880) whether there is another grid location to examine. If so, the process returns to840to examine another grid location and determine which clusters of template to bypass/select for comparison. If the current grid location is the last grid location, the process proceeds to890.

The target-identifying computing device102reports (at890) information based on the comparisons between the clustered templates and the image content of the grid locations. In some embodiments, such reported information may include which target objects were found in which grid locations based on which templates have matching scores better than a threshold at those grid locations. The process800then ends.

III. Example Electronic System

Computer readable program instructions described herein can be downloaded to respective computing/processing devices from a computer readable storage medium or to an external computer or external storage device via a network, for example, the Internet, a local area network, a wide area network and/or a wireless network. The network may comprise copper transmission cables, optical transmission fibers, wireless transmission, routers, firewalls, switches, gateway computers and/or edge servers. A network adapter card or network interface in each computing/processing device receives computer readable program instructions from the network and forwards the computer readable program instructions for storage in a computer readable storage medium within the respective computing/processing device. Computer readable program instructions for carrying out operations of the present disclosure may be assembler instructions, instruction-set-architecture (ISA) instructions, machine instructions, machine dependent instructions, microcode, firmware instructions, state-setting data, configuration data for integrated circuitry, or either source code or object code written in any combination of one or more programming languages, including an object oriented programming language such as Smalltalk, C++, or the like, and procedural programming languages, such as the “C” programming language or similar programming languages. The computer readable program instructions may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). In some embodiments, electronic circuitry including, for example, programmable logic circuitry, field-programmable gate arrays (FPGA), or programmable logic arrays (PLA) may execute the computer readable program instructions by utilizing state information of the computer readable program instructions to personalize the electronic circuitry, in order to perform aspects of the present disclosure.

The computer readable program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other device to cause a series of operational steps to be performed on the computer, other programmable apparatus or other device to produce a computer implemented process, such that the instructions which execute on the computer, other programmable apparatus, or other device implement the functions/acts specified in the flowchart and/or block diagram block or blocks. The flowchart and block diagrams in the Figures (e.g.,FIGS. 3 and 8) illustrate the architecture, functionality, and operation of possible implementations of systems, methods, and computer program products according to various embodiments of the present disclosure. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of instructions, which comprises one or more executable instructions for implementing the specified logical function(s). In some alternative implementations, the functions noted in the blocks may occur out of the order noted in the Figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts or carry out combinations of special purpose hardware and computer instructions.

FIG. 9shows a block diagram of the components of data processing systems900and950that may be used to implement a system for clustering templates and/or a system for identifying targets in a test bench based on clustered templates (e.g., the template-organizing computing device101and/or the target-identifying device102) in accordance with an illustrative embodiment of the present disclosure. It should be appreciated thatFIG. 9provides only an illustration of one implementation and does not imply any limitations with regard to the environments in which different embodiments may be implemented. Many modifications to the depicted environments may be made based on design and implementation requirements.

Data processing systems900and950are representative of any electronic device capable of executing machine-readable program instructions Data processing systems900and950may be representative of a smart phone, a computer system, PDA, or other electronic devices. Examples of computing systems, environments, and/or configurations that may represented by data processing systems900and950include, but are not limited to, personal computer systems, server computer systems, thin clients, thick clients, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, network PCs, minicomputer systems, and distributed cloud computing environments that include any of the above systems or devices.

The data processing systems900and950may include a set of internal components900and a set of external components950illustrated inFIG. 9. The set of internal components900includes one or more processors920, one or more computer-readable RAMs922and one or more computer-readable ROMs924on one or more buses926, and one or more operating systems928and one or more computer-readable tangible storage devices930. The one or more operating systems928and programs such as the programs for executing the processes300and800are stored on one or more computer-readable tangible storage devices930for execution by one or more processors920via one or more RAMs922(which typically include cache memory). In the embodiment illustrated inFIG. 9, each of the computer-readable tangible storage devices930is a magnetic disk storage device of an internal hard drive. Alternatively, each of the computer-readable tangible storage devices930is a semiconductor storage device such as ROM924, EPROM, flash memory or any other computer-readable tangible storage device that can store a computer program and digital information.

The set of internal components900also includes a R/W drive or interface932to read from and write to one or more portable computer-readable tangible storage devices986such as a CD-ROM, DVD, memory stick, magnetic tape, magnetic disk, optical disk or semiconductor storage device. The instructions for executing the processes300and800can be stored on one or more of the respective portable computer-readable tangible storage devices986, read via the respective R/W drive or interface932and loaded into the respective hard drive930.

The set of internal components900may also include network adapters (or switch port cards) or interfaces936such as a TCP/IP adapter cards, wireless Wi-Fi interface cards, or 3G or 4G wireless interface cards or other wired or wireless communication links. Instructions of processes or programs described above can be downloaded from an external computer (e.g., server) via a network (for example, the Internet, a local area network or other, wide area network) and respective network adapters or interfaces936. From the network adapters (or switch port adaptors) or interfaces936, the instructions and data of the described programs or processes are loaded into the respective hard drive930. The network may comprise copper wires, optical fibers, wireless transmission, routers, firewalls, switches, gateway computers and/or edge servers.

The set of external components950can include a computer display monitor970, a keyboard980, and a computer mouse984. The set of external components950can also include touch screens, virtual keyboards, touch pads, pointing devices, and other human interface devices. The set of internal components900also includes device drivers940to interface to computer display monitor970, keyboard980and computer mouse984. The device drivers940, R/W drive or interface932and network adapter or interface936comprise hardware and software (stored in storage device930and/or ROM924).