You are here: Start » Function Reference » Geometry 2D » Geometry 2D Fitting » LocateMultiplePointPatterns

LocateMultiplePointPatterns

Header:	AVL.h
Namespace:	avl
Module:	FoundationPro

Finds occurrences of a pattern in a 2D cloud of (feature) points.

Applications: Can be used to find entire objects after finding their characteristic points with tools such as Template Matching or DL_LocatePoints.

Syntax

void avl::LocateMultiplePointPatterns
(
	const atl::Array<avl::Point2D>& inPoints,
	atl::Optional<const atl::Array<int>&> inPointLabels,
	const atl::Array<avl::Point2D>& inPattern,
	atl::Optional<const atl::Array<int>&> inPatternLabels,
	atl::Optional<const avl::Rectangle2D&> inReferenceFrame,
	const bool inAllowRotation,
	const float inMinAngle,
	const float inMaxAngle,
	const bool inAllowScale,
	const float inMinScale,
	const float inMaxScale,
	const float inTilingFactor,
	const float inMinInitialScore,
	const float inMaxDeviation,
	const float inMinScore,
	const float inMinDistance,
	const bool inDisjointObjectsOnly,
	atl::Array<avl::Rectangle2D>& outObjects,
	atl::Array<atl::Array<avl::Point2D> >& outAlignedPatterns,
	atl::Array<avl::CoordinateSystem2D>& outAlignments,
	atl::Array<atl::Array<avl::Segment2D> >& outPatternSkeletons
)

Parameters

Name	Type	Range	Default	Description
inPoints	const Array<Point2D>&			Input points
inPointLabels	Optional<const Array<int>&>		NIL	Categories that the input points belong to
inPattern	const Array<Point2D>&			Point pattern to be found
inPatternLabels	Optional<const Array<int>&>		NIL	Categories that the pattern points belong to
inReferenceFrame	Optional<const Rectangle2D&>		NIL	Exact position of the model object associated with the pattern in the image
inAllowRotation	const bool		True	Flag indicating whether rotation is allowed as a part of output alignment
inMinAngle	const float		-180.0f	Start of range of possible rotations
inMaxAngle	const float		180.0f	End of range of possible rotations
inAllowScale	const bool		False	Flag indicating whether scale is allowed as a part of output alignment
inMinScale	const float	0.0 -	0.8f	Start of range of possible scales
inMaxScale	const float	0.0 -	1.25f	End of range of possible scales
inTilingFactor	const float	0.000001 - 1.0	0.2f	Defines relative size of the square tile on the plane during initial detection
inMinInitialScore	const float	0.0 - 1.0	0.75f	The minimum proportion of points correctly matched during initial detection
inMaxDeviation	const float	0.0 -	5.0f	Maximal distance between two points considered matched
inMinScore	const float	0.0 - 1.0	0.75f	The minimum proportion of points correctly matched
inMinDistance	const float	0.0 -	10.0f	Minimal distance between centers of two found occurrences
inDisjointObjectsOnly	const bool		False	Flag indicating whether found occurrences can have common points
outObjects	Array<Rectangle2D>&			Bounding rectangles of the found pattern occurrences
outAlignedPatterns	Array<Array<Point2D> >&			The aligned input pattern points
outAlignments	Array<CoordinateSystem2D>&			The transforms that align the input pattern to the input points
outPatternSkeletons	Array<Array<Segment2D> >&			The skeletons of the aligned input pattern points

Description

The filter finds locations of a pattern of points in the set of input points. The possible rotations and scales of the found occurrences can be fully controlled using proper values of inAllowRotation, inMinAngle, inMaxAngle, inAllowScale, inMinScale and inMaxScale parameters.

The location routine consists of three phases. Only the inTilingFactor and inMinInitialScore parameters have an effect on the initial phase. Internally, the whole plane is then divided into square tiles which size depends on inTilingFactor and the average distance between two points from inPoints. A transformation becomes a candidate to be a valid pattern occurrence if at least inMinInitialScore fraction of pattern points reside in the right tiles. The candidate transformation proceeds to the second phase, where it is refined to be possibly best fitted to the data points. The result transformation is considered to be a valid output alignment if at least inMinScore fraction of aligned pattern points are at most inMaxDeviation away from their closest data points.

The end phase's purpose is to select the output alignments according to the inMinDistance and inDisjointObjectsOnly parameters values. The ultimate output is chosen so no two aligned pattern centers are closer than inMinDistance from themselves and, if inDisjointObjectsOnly parameter is set, no two aligned patterns cover the same data point.

The most difficult part to achieve reliable results seems to be the proper setting of the inTilingFactor parameter. Because of its existence, the algorithm will work especially well when the pattern consists of not too many points and distances between them are more or less equal i.e. the ratio of the greatest distance between pattern points and the smallest distance between pattern points is small. If this is not the case and the default value for inTilingFactor does not work well, one should try to adjust the value keeping in mind that the greater values should be used when the pattern visible in the inPoints is distorted and the smaller values will work best when only small distortion is present. In case of further problems with choosing the right inTilingFactor value, one can also try lowering inMinInitialScore value.

The filter performance depends heavily on the number of the pattern points. Because of that fact, it is highly advisable for the pattern to be as small as possible. The performance can be poor even for patterns with more than 15 points. Note that the shape of the pattern also matters. The execution time for symmetrical patterns is generally bigger than for asymmetrical ones.

Examples

inPattern input with selected point pattern to be found

LocateMultiplePointPatterns performed on points acquired by DL_LocatePoints.

Errors

List of possible exceptions: