next up previous
Next: Non-rigidly Connected Object Verification Up: Constraining Object Existence and Previous: SURFACE Verification

Rigid ASSEMBLY Verification

Rigid ASSEMBLYs should meet both existence and identity requirements.

Most real objects are compact solids and one manifestation of this is connectedness of all object surfaces. Hence, surfaces composing the object must somehow be directly or transitively connected to each other without using unrelated surfaces.

Unfortunately, it is difficult to always determine if two surfaces are directly or indirectly connected. Convex surface orientation discontinuity boundaries definitely mean connectedness, but concave boundaries are ambiguous regarding surface connectivity. Because of self-occlusion, direct connections may not be visible, as when one subcomponent overlaps another. Finally, obscuring objects can prevent observation of adjacency, though surface reconstruction (Chapter 4) eliminates some cases of this. Other cases, like that in Figure 10.3 are not solved by this.

Figure 10.3: Indeterminate Surface Connectivity Behind Obscuring Structure
\begin{figure}\epsfysize =4in
\epsfbox{FIGURES/Fig10.3.ps}\end{figure}

Because of these difficulties, hypotheses will be rejected if it is certain that they cannot be fully connected, i.e., if there are subcomponents between which no connection exists. (Of course, two isolated objects could be connected by hidden structure to a common background, but here we assume objects are seen in general position.)

The implemented test is:

$[E_1]$ All Surfaces Must Be Potentially Connecting
Let:  
  {$D_i$} be the subcomponents used in the hypothesis
  $PC(D_a,D_b)$ means that $D_a$ and $D_b$ are potentially directly connecting and holds if:
  a) $D_a$ and $D_b$ share any type of boundary or
  b) there is a surface cluster with a front-side-obscuring or concave relation to both $D_a$ and $D_b$
  $TC(D_a,D_b)$ be the transitive closure of $PC(D_a,D_b)$
If:  
  for some $D_a$ and $D_b$, $TC(D_a,D_b)$ does not hold
Then: the hypothesis is incorrectly formed.

This test rejects the false cube seen in Figure 10.1.

For rigid objects, the essence of identity is shape, and surface images make this information directly available. Given the surface image, the observed shape could be compared to that of each object from each viewpoint, but this approach is computationally infeasible. A more parsimonious solution follows, which also considers weak segmentation boundaries and occlusion.

Intuitively, correct object identification is assumed if all the right structures are found in the right places. Given the connectivity guaranteed by the above test, merely having the correct components is likely to be adequate, because the subcomponents of most objects only fit together rigidly and completely in one way (disregarding highly regular objects, like blocks). But, because there are likely to be a few counter-examples, especially with symmetric objects and misidentifications of similar surfaces, geometric, as well as topological, consistency is required. The requirement of consistent reference frames will eliminate many arbitrary groupings (and was demonstrated in the previous chapter).

Surfaces that are connected according to the model should be connected in the scene. This does not always imply adjacency is observable, because object boundaries are not visible from all viewpoints.

Occlusion affects verification because some surfaces may be partially or completely missing or a surface may be broken up by closer surfaces. Moreover, true surface boundaries may be obscured. The remaining true surface boundaries will be connected to back-side-obscuring boundaries in different locations. Since these are not model features, they are ignored.

Based on these ideas, the rigid object identity constraints are:

[$R_1$] - Each data subcomponent can have at most one visible forward-facing model subcomponent paired with it. (The converse may not hold because of fragmentation or occlusion).
[$R_2$] - The position of observed subcomponents relative to each other is as predicted for the corresponding model subcomponents.
[$R_3$] - Model subcomponent adjacency implies data subcomponent adjacency and vice versa.

These constraints were implemented as the following tests:

Let:    
  {$F_i$} be the visible forward-facing model SURFACEs  
  {$I_i$} be the image surfaces  
  $\vec{P}_i$ and $\vec{\hat{P}}_j$ be the predicted and observed center-of-mass for the corresponding model and image surfaces $F_i$ and $I_j$  
  $\vec{N}_i$ and $\vec{\hat{N}}_j$ be the predicted and observed surface orientations at the centers-of-mass for the corresponding model and image surfaces $F_i$ and $I_j$  
  $\tau_t$ and $\tau_r$ be thresholds  

Then:        
  $[R_1]$ For each $I_i$ there is at most one corresponding $F_j$.  
  $[R_2]$ For each corresponding $I_i$ and $F_j$:  
    $\mid \vec{P}_i - \vec{\hat{P}}_j \mid < \tau_t$ ($\tau_t$ = 20.0)
    $\mid \vec{N}_i \circ \vec{\hat{N}}_j \mid > \tau_r$ ($\tau_r$ = 0.8)
  $[R_3]$ Let:   
      $I_a$, $I_b$ be two non-tangential data surfaces  
      $F_a$, $F_b$ be the corresponding model SURFACEs  
    If:    
      $F_a$ and $F_b$ are observably adjacent, $I_a$ and $I_b$ are not observably adjacent, and there is no surface cluster partially obscuring both $I_a$ and $I_b$,
      or  
      $F_a$ and $F_b$ are not observably adjacent and $I_a$ and $I_b$ are observably adjacent  
    Then: the hypothesis is incorrectly formed  
         

Occlusion also has distinctive characteristics, and thus the hypothesis that an object is partially or fully obscured should be subject to some verification. Back-side-obscuring boundaries usually signal this occurrence, though not always. When a curved surface goes from facing the viewer to facing away, self-occlusion occurs without back-side-obscuring boundaries. When back-side-obscuring boundaries are present, though, three new constraints can be added:

[$O_1$] - the back-side-obscuring boundary should lie inside the image region predicted for the SURFACE. Alternatively, the predicted image boundary should lie on or outside the observed image region. Figure 10.4 illustrates this.
[$O_2$] - Back-side-obscuring boundary segments that bound the surface image region must end as the crossbar of a "TEE" junction. This implies that there must be at least three image regions at the junction. Figure 10.5 illustrates this.
[$O_3$] - A non-tangential image surface should be predicted as partially self-obscured during visibility analysis (Chapter 9) if and only if the corresponding data surface has at least one back-side-obscuring boundary whose closer surface is also an object surface.
Figure 10.4: Occlusion Boundaries Lie Inside Predicted Model Boundaries
\begin{figure}\epsfysize =3.5in
\epsfbox{FIGURES/Fig10.4.ps}\end{figure}
Figure 10.5: Occlusion Boundaries End on TEEs at Surfaces
\begin{figure}\epsfysize =4in
\epsfbox{FIGURES/Fig10.5.ps}\end{figure}

Constraint $O_1$ was not applied because parameter estimation errors made it difficult to check this condition reliably (e.g. predicted model and data surfaces did not overlap adequately). Constraint $O_2$ was guaranteed assuming image labeling was correct, which was the case here.

Because of parameter estimation errors, it is likely that there are self-occlusions predicted during raycasting that are not observed (because of surfaces becoming slightly obscured). Hence, the test of verifying predicted self-occlusions was not performed. While it is also possible for slightly obscured data surfaces to be predicted as not obscured, if a self-occlusion was significant enough to be observed, then prediction was likely to show it even with parameter estimation errors. Hence, only the reverse test was implemented:

$[O_3]$ Observed Self-obscured SURFACEs Are Predicted
   
Let:  
  {$D_i$} be the non-tangential partially obscured data surfaces
  {$C_{ij}$} be the closer data surfaces across obscuring boundaries around $D_i$
  $S_i$ be the model SURFACE corresponding to $D_i$
  {$M_k$} be the other model SURFACEs
  front($X,Y$) holds if model SURFACE $X$ is directly or indirectly in front of $Y$. This is found by raycasting and taking the transitive closure.

If:      
  For each $D_i$ and each $C_{ij}$
    If there is a $M_k$ corresponding to $C_{ij}$,
      then front($M_k,S_i$)
Then: the self-occlusion is as predicted by the model.
       

One application of $O_3$ was particularly significant. The robot upper and lower arms are nearly symmetric, so there are two values for the upperarm position and joint angle where the lowerarm can be nearly in the position shown in the test scene. The difference between the two cases is whether the lowerarm is in front of or behind the upperarm. Though the depths of the component reference frames are different in the two cases, parameter tolerances did not completely reject the second alternative. Happily, test $O_3$ did discriminate.


next up previous
Next: Non-rigidly Connected Object Verification Up: Constraining Object Existence and Previous: SURFACE Verification
Bob Fisher 2004-02-26