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 Cd
, the sum of the costs for reference and
sensed component dissimilarities Cc , and the sum
of penalty costs for missing components Cm . Thus, the total cost is
given by
Ct = Cd + Cc + Cm
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 n1 is to the right
of n2 by d1 units and the two are connected by a joint
The blocks n1 and n2 are above
the rectangular block n3 by d2 and d3 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,
Gn, Gb)
Where N = { n1, n2, . . ., nk}is
a set of nodes, A = {a n1, an2, . . . , ank}
is an alphabet of node attributes, B = { b1, b2, . . . ,
bm}is a set of directed branches (b = (ni, nj)),
and Gn and Gb 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
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.