Home | | **Artificial Intelligence** | | **Computational Intelligence** | | **Artificial Intelligence** | Partial Matching

For many AI applications complete matching between two or more structures is inappropriate

**Partial Matching**

For many AI applications complete matching between
two or more structures is inappropriate

For example, input representations of speech
waveforms or visual scenes may have been corrupted by noise or other unwanted
distortions.

In such cases, we do not want to reject the input
out of hand. Our systems should be more tolerant of such problems

We want our system to be able to find an acceptable
or best match between the input and some reference description

Compensating for Distortions

Finding an object in a photograph given only a
general description of the object is a common problems in vision applications

For example, the task may be to locate a human face
or human body in photographs without the necessity of storing hundreds of
specific face templates

A better approach in this case would be to store a
single reference description of the object

Matching between photographs regions and
corresponding descriptions then could be approached using either a measure of
correlation, by altering the image to obtain a closer fit

If nothing is known about the noise and distortion
characteristics, correlation methods can be ineffective or even misleading. In
such cases, methods based on mechanical distortion may be appropriate

For example, our reference image is on a transparent
rubber sheet. This sheet is moved over the input image and at each location is
stretched to get the best match alignment between the two images

The match between the two can then be evaluated by
how well they correspond and how much push-and-pull distortion is needed to
obtain the best correspondence

Use the number of rigid pieces connected with
springs. This pieces can correspond to low level areas such as pixels or even
larger area segments

To model any restrictions such as the relative
positions of body parts, nonlinear cost functions of piece displacements can be
used

The costs can correspond to different spring
tensions which reflect the constraints

For example, the cost of displacing some pieces
might be zero for no displacement, one unit for single increment displacements
in any one of the permissible directions, two units for two position
displacements and infinite cost for displacements of more than two increments.
Other pieces would be assigned higher costs for unit and larger position
displacements when stronger constraints were applicable

The matching problem is to find a least cost
location and distortion pattern for the reference sheet with regard to the
sensed picture

Attempting to compare each component of some
reference to each primitive part of a sensed picture is a combinatorially
explosive problem

In using the template-spring reference image and
heuristic methods to compare against different segments of the sensed picture,
the search and match process can be made tractable

Any matching metric used in the least cost
comparison would need to take into account the sum of the distortion costs C_{d}
, the sum of the costs for reference and

sensed component dissimilarities Cc , and the sum
of penalty costs for missing components C_{m} . Thus, the total cost is
given by

C_{t} = C_{d} + C_{c} + C_{m}
Finding Match Differences

Distortions occurring in representations are not
the only reason for partial matches

For example, in problem solving or analogical
inference, differences are expected. In such cases the two structures are
matched to isolate the differences in order that they may be reduced or
transformed. Once again, partial matching techniques are appropriate

In visual application, an industrial part may be
described using a graph structure where the set of nodes correspond to
rectangular or cylindrical block subparts

The arc in the graph correspond to positional
relations between the subparts

Labels for rectangular block nodes contain length,
width and height, while labels for cylindrical block nodes, where location can
be above, to the right of, behind, inside and so on

In Fig 8.5 illustrates a segment of such a graph

In the fig the following abbreviations are used

Interpreting the graph, we see it is a unit
consisting of subparts, mode up of rectangular and cylindrical blocks with
dimensions specified by attribute values

The cylindrical block n_{1} is to the right
of n_{2} by d_{1} units and the two are connected by a joint

The blocks n_{1} and n_{2} are above
the rectangular block n_{3} by d_{2} and d_{3} units
respectively, and so on

Graphs such as this are called attributed
relational graphs (ATRs). Such a graph G is defined as a sextuple G = (N, B, A,
G_{n}, G_{b})

Where N = { n_{1}, n_{2}, . . ., n_{k}}is
a set of nodes, A = {a n_{1}, an_{2}, . . . , an_{k}}
is an alphabet of node attributes, B = { b_{1}, b_{2}, . . . ,
b_{m}}is a set of directed branches (b = (n_{i}, n_{j})),
and G_{n} and G_{b} are functions for generating node and
branch attributes respectively

When the representations are graph structures like
ARGs, a similarity measure may be computed as the total cost of transforming
one graph into the other

For example, the similarity of two ARGs may be
determined with the following steps:

o Decompose the ARGs into basic
subgraphs, each having a depth of one Compute the minimum cost to transform
either basic ARG into the other one subgraph-by-subgraph

Compute the total transformation cost from the sum
of the subgraph costs

An ARG may be transformed by the three basic
operations of node or branch deletions, insertions, or substitutions, where
each operation is given a cost based on computation time or other factors

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.