Chapter: Artificial Intelligence

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

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 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:

 

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


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