# US 2015/0104068 A1 · System and method for locating fiducials with known shape

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0104068 A1
- Document ID: US20150104068A1
- Status: Published application
- Kind: A1
- Application number: 14/515,481
- Filed: 2014-10-15
- Published: 2015-04-16
- Earliest claimed: 2013-10-16
- Assignees: Cognex Corporation
- Applicants: Cognex Corporation
- Inventors: Guruprasad Shivaram; Lowell D. Jacobson; David Y. Li
- Web page: https://patentgrep.com/patent/US20150104068A1

## CPC

- G06T 7/74: {involving reference images or patches}
- G06V 10/44: Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
- G06V 10/754: {involving a deformation of the sample pattern or of the reference pattern; Elastic matching}
- G06T 2207/20081: Training; Learning
- G06T 2207/30164: Workpiece; Machine component
- G06T 2207/30204: Marker
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

This invention provides a system and method for determining the pose of shapes that are known to a vision system that undergo both affine transformation and deformation. The object image with fiducial is acquired. The fiducial has affine parameters, including degrees of freedom (DOFs), search ranges and search step sizes, and control points with associated DOFs and step sizes. Each 2D affine parameter's search range and the distortion control points' DOFs are sampled and all combinations are obtained. The coarsely specified fiducial is transformed for each combination and a match metric is computed for the transformed fiducial, generating a score surface. Peaks are computed on this surface, as potential candidates, which are refined until a match metric is maximized. The refined representation exceeding a predetermined score is returned as potential shapes in the scene. Alternately the candidate with the best score can be used as a training fiducial.

## Claims

### Claim 1

A method for automatically determining pose of a shape undergoing a combination of affine deformation and non-linear deformation with a vision system comprising the steps of:
acquiring an image of an object containing the shape;
performing a coarse location of the shape to identify and select at least one shape candidate matching a predetermined shape;
refining the affine parameters and non-linear distortion parameters for the best matching candidate shape; and
generating a shape representation of at least one refined best matching candidate shape.

### Claim 2 (depends on 1)

The method as set forth in claim 1 wherein the affine deformation is defined by one or more two-dimensional (2D) affine degrees of freedom and the non-linear deformation is defined by at least one of stroke width and spline warp.

### Claim 3 (depends on 2)

The method as set forth in claim 2 wherein the step of performing coarse location comprises moving at least one control point relative to the predetermined shape iteratively to a plurality of control point configurations from a nominal position over a plurality steps based on a predetermined step size and search range and, for each control point configuration, iteratively computing affine transforms relative to the predetermined shape over a plurality of steps based upon a predetermined step size and search range for at least one affine degree of freedom (DOF).

### Claim 4 (depends on 3)

The method as set forth in claim 3 wherein the shape defines a cross with orthogonally oriented arms each defining a stroke width and at least one control point defined by a single point located at an intersecting corner of the arms.

### Claim 5 (depends on 4)

The method as set forth in claim 4 wherein the control point is located in a predetermined quadrant with respect to the arms thereby defining a valid shape.

### Claim 6 (depends on 4)

The method as set forth in claim 4 wherein the shape defines a circle or annulus combined with the cross and further comprising another control point, respectively located on each edge of the circle or annulus.

### Claim 7 (depends on 3)

The method as set forth in claim 3 further comprising discarding control point configurations that result in an invalid shape.

### Claim 8 (depends on 3)

The method as set forth in claim 3 further comprising (a) decomposing the shape into more basic constituent shapes and defining an order of processing based upon a predetermined hierarchy and, (b) for each more basic shape moving at least one control point relative to each more basic shape iteratively to a plurality of control point configurations from a nominal position over a plurality of steps based on a predetermined step size and search range and, (c) for each control point configuration, iteratively computing affine transforms relative to the more basic shape over a plurality of steps based upon a predetermined step size and search range for at least one affine degree of freedom (DOF).

### Claim 9 (depends on 8)

The method as set forth in claim 8 wherein the step of decomposing is performed by a fiducial renderer and the hierarchy comprises and order from shape with largest perimeter to shape with smallest perimeter.

### Claim 10 (depends on 3)

The method as set forth in claim 3 wherein the step of performing the coarse location comprises searching a user-specified search range of affine parameters and non-linear distortion parameters.

### Claim 11 (depends on 3)

The method as set forth in claim 3 further comprising computing a score for each of a plurality of combinations of control point configurations and affine transforms and providing therefrom a score surface in space spanned by affine DOFs and control point DOFs, and selecting a set of peaks on the score surface and refining each peak.

### Claim 12 (depends on 11)

The method as set forth in claim 11 wherein the steps of selecting and refining each peak further comprise selecting one or more of the highest-scoring of the combinations as the shape representation or to locate multiple instances of the shape in the image.

### Claim 13 (depends on 11)

The method as set forth in claim 11 wherein the step of computing the score comprises generating a gradient image and defining probes along edges of the gradient image.

### Claim 14 (depends on 13)

The method as set forth in claim 13 the step of computing the score is based upon an average value of a dot product between the probes and interpolated gradient values at corresponding locations in the gradient image.

### Claim 15 (depends on 14)

The method as set forth in claim 14 wherein the step of computing the score comprises maximizing the score using a hill climbing approach.

### Claim 16 (depends on 3)

The method as set forth in claim 3 further comprising performing the steps of performing and refining, at progressively finer step sizes, iteratively to obtain at least one subsampled image pixel candidate shape.

### Claim 17 (depends on 2)

The method as set forth in claim 2 wherein the shape representation is used as a model image in at least one of a runtime fiducial location operation and generation of a synthetic fiducial image model.

### Claim 18 (depends on 1)

The method as set forth in claim 1 further comprising establishing a boundary around the shape and establishing a unit shape relative to the boundary.

### Claim 19 (depends on 1)

The method as set forth in claim 1 wherein the shape representation is used to locate one or more fiducial/shape during run time operation of the vision system or to refine a synthetic shape based upon the image of the fiducial/shape for training a vision system tool.

### Claim 20

A system for automatically determining pose of a shape undergoing a combination of affine deformation and non-linear deformation with a vision system comprising:
a vision system camera assembly that acquiring an image of an object containing the shape;
a vision system processor that performs a coarse location of the shape to identify and select at least one shape candidate matching a predetermined shape;
a refining process that refines affine parameters and non-linear distortion parameters for the best matching candidate shape that generates a shape representation of at least one refined best matching candidate shape.
