**Name**

**km_match_si** Compute similitude-invariant matches between pieces of meaningful boundaries of two images

**Command Synopsis**

**km_match_si** *maxError1* *maxError2* *minLength* *minComplex* *levlines1* *levlines2* *dict1* *dict2* *matchings* *matching_pieces*

maxError1: maximum Hausdorff distance between normalized codes allowed

maxError2: maximum Hausdorff distance (in pixels) between de-normalized codes (to the frame of image 2) allowed

minLength: minimum arclength (in pixels) a matching piece of curve must have to be considered as valid

minComplex: minimum angle variation (in rad.) a matching piece of curve must have to be considered a valid

levlines1: meaningful boundaries of image 1

levlines2: meaningful boundaries of image 2

dict1: dictionary of similitude-invariant codes of image 1

dict2: dictionary of similitude-invariant codes of image 2

matchings: list containing the indices of the matching codes

matching_pieces: matchings information: index_curve1_in_levlines1, index_curve2_in_levlines2, index_matching_begins_in_curve1, index_matching_ends_in_curve1, index_matching_begins_in_curve2, index_matching_ends_in_curve2, performance

**Function Summary**

void km_match_si (maxError1 , maxError2 , minLength , minComplex , levlines1 , levlines2 , dict1 , dict2 , matchings , matching_pieces )

float maxError1 , maxError2 ;

float minLength , minComplex ;

Flists levlines1 , levlines2 , dict1 , dict2 ;

Flist matchings , matching_pieces ;

**Description**

The first task perfomed by this module is to determine which pairs of
normalized codes from `dict1`

and `dict2`

are good
candidates to match. This is done by calling the
`km_prematchings`

module : for every similitude-invariant
code in `dict1`

, this module gets its pre-matching codes in
`dict2`

. The maximum Hausdorff distance between normalized codes
allowed here is `maxError1`

. Notice that the purpose of the
pre-matching step is to discard matchings that are clearly bad, in
order to reduce computational burden (since the extension step is much
more heavy). That's why the `maxError1`

threshold should not be
too much restrictive; `maxError1`

= 0.2 or 0.3 is a reasonable
choice.

Then matching extension is performed for all pre-matchings. For every
pair
(_{1},_{2}) of ``pre-matched'' pieces of
curve (sub-curves of
_{1} and
_{2}, resp.),
the euclidean transformation that maps
_{1}'s local frame
to
_{2}'s local frame is computed. Then, this
transformation is used to put
_{1} and
_{2} in
the frame of image 2. In this frame, lengths and distances between
curves are measured in pixels. The matching extension step is based on
the following parameters: `maxError2`

, `minLength`

and
`minComplex`

.

`maxError2`

controls the euclidean pixel distance between corresponding points of both curves (extracted by regular sampling in their normalized frames).`minLength`

controls the minimum arc length required to both matched pieces of curve (in their original image frames) to be considered as a valid matching pair. In other words, initial pieces of curve are extended until their distance exceeds`maxError2`

; if their arc length is less than`minLength`

, the matching pair is not considered as a valid one.- Matching pieces of curve whose arc length is greater than
`minLength`

are considered to be valid if their total angle variation is greater than`minComplex`

.

For every piece of curve in image 1 we keep, among all possible valid matching pieces, the one which maximizes the following criterion:

Performance = ,

where
*l*_{1} = *arclength*(*S*_{1}),
*l*_{2} = *arclength*(*S*_{2}),
*L*_{1} = *arclength*(*C*_{1})
and
*L*_{2} = *arclength*(*C*_{2}).

Finally, the result is written in two different formats in Flists
`matching`

and `matching_pieces`

.

`matching`

is a 2 dimensional Flist that contains all pairs (*i*_{1},*i*_{2}), where*i*_{1}is the index of the original normalized code in dictionary`dict1`

and*i*_{2}is the index of the original normalized code in dictionary`dict2`

.`matching_pieces`

is a 7 dimensional Flist containing the following information:*First and second elements*: indices*NCurve*1 and*NCurve*2, which identify curves_{1}and_{2}in Flists`levlines1`

and`levlines2`

, resp.*Thirth and fourth elements*: first and last indices of the matching piece, in curve*NCurve*1.*Fifth and sixth elements*: first and last indices of the matching piece, in curve*NCurve*2.*Seventh element*: performance.

This last output is to be used with the MegaWave2
module `km_savematchings`

. The
outputs of `km_savematchings`

are two Flists that contain all pieces of
curve in image 1 and image 2 that match; they can be displayed using
`fkview`

.

For more details, see J.-L. Lisani's PhD dissertation [Lis01] or [LMMM03].

**See Also**

**Version 1.0**

Last Modification date : Thu Apr 10 19:35:23 2003

**Author**

Jose-Luis Lisani, Pablo Muse, Frederic Sur