next up previous
Next: Supercomponent Associations Up: Theory: Evidence and Association Previous: Theory: Evidence and Association

Property Evidence

Property evidence is calculated by evaluating the fit of structural properties (Chapter 6) to model requirements (Chapter 7). An example of a set of requirements would be a particular surface must be planar and must meet all adjacent connected surfaces at right angles.

There is some controversy over what constitutes evidence, but here, evidence is based only on primitive image properties, such as relative curve orientation, rather than higher level descriptions, such as "rectangular". This decision is partly made because "rectangular" is a distinct conceptual category and, as such, would be included as a distinct generic element in the invocation network. It would then have a description relationship to the desired model.

The context within which data is taken depends on the structure for which property evidence is being calculated. If it is a model SURFACE, then properties come from the corresponding surface hypothesis. If it is an ASSEMBLY, then the properties come from the corresponding surface cluster.

Unary evidence requirements are defined in the model database in one of six forms, depending on whether the values are required or excluded, and whether there are upper, lower or both limits on their range. The complete forms are (where e=evidence_type is the type of evidence):

central include:
UNARYEVID $low$ $<$ e $<$ $high$ PEAK $peak$ WEIGHT $wgt$
above include:
UNARYEVID $low$ $<$ e PEAK $peak$ WEIGHT $wgt$
below include:
UNARYEVID e $<$ $high$ PEAK $peak$ WEIGHT $wgt$
central exclude:
UNARYEVID $low$ $<$ e $<$ $high$ PEAK $peak$ ABSENT WEIGHT $wgt$
above exclude:
UNARYEVID $low$ $<$ e PEAK $peak$ ABSENT WEIGHT $wgt$
below exclude:
UNARYEVID e $<$ $high$ PEAK $peak$ ABSENT WEIGHT $wgt$

If the peak value is the mean of the upper and lower limit, it need not be specified. Each requirement has a weight that scales the contribution of this evidence in the total property evidence evaluation.

Binary evidence requirements are defined similarly, with the key difference that the model also specifies the types of the substructures between which the properties are to hold. The model specification for the binary "central include" form is:

  BINARYEVID low < evidence_type(type1,type2) < high PEAK peak WEIGHT wgt

In IMAGINE I, all evidence types were considered to be unary. If a binary property between two features was expressed, then evidence evaluation would take the best instance of the binary relationship. IMAGINE II made the relationship explicit. The properties used in IMAGINE I were:
NUMLINB number of straight lines in boundary
NUMARCB number of curves in boundary
DBPARO number of groups of parallel lines in boundary
NUM90B number of perpendicular boundary junctions
NUMEQLB number of groups of equal length boundary segments
DCURV boundary segment curvature
DCRVL boundary segment length
DBRORT boundary segment relative orientation
MINSCURV minimum surface curvature
MAXSCURV maximum surface curvature
SURSDA relative surface orientation
ABSSIZE surface area
RELSIZE percent of surface area in surface cluster
SURECC eccentricity of surface

It is possible to generate automatically most of the evidence types from the geometric models, if heuristics for setting the ranges and weight values are given, but all these values were manually chosen here. Appendix A shows some of the evidence constraints for the modeled objects.

Models inherit evidence from their descriptions (discussed here), so only additional evidence (i.e. refinements) need be specified here.

Finally, we consider how the total evidence value is calculated from the individual pieces of evidence. The constraints on this computation are:

Based on the "degree of fit" requirement, a function was designed to evaluate the evidence from a single description. The function is based on a scaled gaussian evaluation model, with the evaluation peaking at the desired value, having positive value within the required range (which need not be symmetric), and tailing off to -1.0. Because there are six types of evidence requirements, six different evidence evaluation functions are needed. However, the excluded types are the negatives of the included types, and the below types are the mirror image of the above types. So, only the "central include" and "above include" are described here. Based on the model definitions above, the "central include" function for the $i^{th}$ evidence constraint is:

  $d_j$ = $j^{th}$ data value
If: $d_j > peak_i $  
  then: $f_{ij} = (\frac{(d_j - peak_i)}{(high_i - peak_i)} * 1.1774)^2$
  else: $f_{ij} = (\frac{(peak_i - d_j)}{(peak_i - low_i)} * 1.1774)^2$
And the evaluation $e_j$ is:  
  $g_{ij} = 2 * exp(-\frac{f_{ij}}{2}) - 1$

The constant 1.1774 ensures the evaluation equals 0 when the data value equals $high$ or $low$. The "above include" function for the $i^{th}$ evidence constraint is:

  $d_j$ = $j^{th}$ data value
If: $d_j > peak_i $  
  then: $f_{ij} = 0.0$
  else: $f_{ij} = (\frac{(peak_i - d_j)}{(peak_i - low_i)} * 1.1774)^2$
And the evaluation $e_j$ is:  
  $g_{ij} = 2 * exp(-\frac{f_{ij}}{2}) - 1$

Figure 8.7 illustrates these functions. Their gaussian form is appealing because it is continuous and smooth and relates well to gaussian error distributions from property estimation. Other functions meet the requirements, but stronger requirements could not be found that define the function more precisely.

Figure 8.7: Data Evaluation Functions
\begin{figure}\epsfysize =6.5in

A property constraint's evaluation is given by the data value that best satisfies the constraint. This is because model-to-data correspondences have not been made yet, so the evaluations are undirected. As the point of invocation is suggestion, any datum within the constraint range is contributory evidence, and correct models will have all their constraints satisfied. Hence, the final evidence value for this constraint is given by:

e_i = max_j(g_{ij})

This portion of the invocation network is illustrated in Figure 8.8.
Figure 8.8: Best Evaluation Selection Network Fragment
\begin{figure}\epsfysize =4in

The evaluation of binary property evidence takes into account the plausibility of the subcomponents as well as the property value itself. Thus:

h_{abi} = c_1 * g_i(a,b) + c_2 * p_{ar} + c_2 * p_{bs} + c_3

is the evidence evaluation function for the $i^{th}$ binary evidence constraint, relating model subcomponent $r$ to model subcomponent $s$, when using the value of the given property between data features $a$ and $b$. $g_i(a,b)$ is the same evaluation function as for the unary properties ($g_{ij}$), $p_{ar}$ and $p_{bs}$ are the plausibilities that data feature $a$ has model identity $r$, data feature $b$ has model identity $s$, and $c_1$, $c_2$ and $c_3$ are constants that express the relative importance of the different terms ( $c_1 = 0.8, c_2 = 0.4, c_3 = -0.6$). The final binary property evidence value is:

e_i = max_{ab}(h_{abi})

This picks the best evidence over all pairs of immediate subfeatures in the data context.

The evaluations for individual property requirements then need to be integrated. One function that satisfies the evidence integration constraints is a weighted harmonic mean:

  $e_i$ be the data evaluation for the $i^{th}$ property constraint
  $w_i$ be the weight for that evidence type
  $evd_{prop} = harmmean(\{(e_i,w_i)\})$
  $A = \sum w_i$
  $B = \sum \frac{w_i}{e_i + 2}$
  $harmmean(\{(e_i,w_i)\}) = \frac{A}{B} - 2$

If no property evidence is available, this computation is not applied. The modified harmonic mean is continuous, gives additional weight to negative evidence and integrates all values uniformly. Moreover, it has the property that:

$= harmmean(\{(e_1,w_1), (harmmean(\{(e_2,w_2),(e_3,w_3)\}),w_2+w_3)\})$

This means that we can add evidence incrementally without biasing the results to the earlier or later values (provided that we also keep track of the weighting of the values). The offset of 2 is used to avoid problems when the plausibility is near -1, and was chosen because it gave good results. The integrated property evidence has a weight that is the sum of the individual property weights: $w_{prop} = \sum w_i$.

This harmonic mean can be implemented in a value passing network, as shown in Figure 8.9, which integrates the evidence values $e_i$ with weights $w_i$. Here, the square boxes represent unary or binary arithmetic units of the designated type, and circular units represent either constants, or the evidence values imported from the above calculation.

Figure 8.9: Harmonic Mean Network Fragment Integrating Property Evidence
\begin{figure}\epsfysize =6in

next up previous
Next: Supercomponent Associations Up: Theory: Evidence and Association Previous: Theory: Evidence and Association
Bob Fisher 2004-02-26