Exploiting 2D Topology in Labeling Polyhedral Images

1. A Labeling Example

Figure 1 traces the parallel labeling of two blocks, one on top of the other. The parallel labeling starts with the input image and default labels (?} for all the nodes (i.e., vertices, edges, and faces) in the image. Then, it finds all local labeling constraints at all vertices, edges, and face boundaries of the image, de­ scribed respectively by junctions, junction-pairs, and junction­ loops, frames 1 to 3. Attached to each node is the number of locallabelings. Constraint satisfaction and propagation (CSP) is done uniformly at all nodes in the image, from every node to its neighbors, through vertex-edge, edge-face, and face-vertex links. Note the decrease in the number of local labelings at each node, frames 4 to 6.

The face surrounding the two blocks has 16 locallabelings, cor­ responding to the blocks floating in air, or resting against some imaginary surface at some of its bounding edges. The two inter­ pretations correspond to the face labeled as image background (B) or as polyhedral face (F). Note that the blocks sitting on top of a horizontal surface can be thought as the blocks floating in air, and infinitesimally touching the surface. The surround­ ing face is a touchable background, and so is labeled by B, and has only 1 junction-loop. The detection of the background face surrounding the blocks further restricts the labeling of the blocks, Frames 7 and 8 show the final labels at the edges and faces.

2. Image Topology

Just as the vertices, edges, and faces of a 3D polyhedron join 3D blocks (Markowsky and Wesley 1980), the vertices and edges of an image join connected regions of the image, called faces.

Definitions 1 (Topology in a polyhedral image)

· A vertex i8 not only an intersection of distinct edges, but also a junction of distinct faces of the image.

· An edge is not only an intersection of distinct faces, but also a segment connecting distinct vertices.

· A face is a connected region of the image plane locally bounded either by chains/cycles of distinct edges, or by open/closed paths going through distinct vertices.

The topology of the image as junction/connection/boundary of subsets does not hold only at the image boundary 81, and so 81 must be excluded from labeling. Nguyen (1987) proved that:

Theorem 1 The image of a 9D polyhedral scene is always a segmentation of the open subset inside the image boundary 81 into faces, joined by edges and vertices.

3. Enumeration of All Local Labelings

Figures 2 show the label hierarchies for the vertices, edges, and faces . Just as object edges and faces can be represented in terms of object vertices, locallabelings around image edges and faces are naturally represented as n-tuples of labelings at image vertices. Figures. 3 describe the locallabelings around a vertex, an edge, and a face. The junctions for occlusion and tri­ hedral vertices (Huffman 1971, Clowes 1971) are precomputed and stored in a dictionary. Junctions and vertex-labels are related by a ~ relation, which is implicit in the dictionary rep­ resentation. The junctions for multihedral vertices with zero or one hidden face can be enumerated depth-first from the Funda­ mental Junction Equation relating the orientation of the edges, the ordering of the faces, and their respective gradient points around a vertex (Malik 1985).

The junction-loops of a face Fare found by a depth-first search for all consistent labelings around the face boundary 8F. Con­ sistency means that the junctions of any two consecutive ver­ tices must have the same edge-label for the edge connecting these two vertices. Each junction-loop found from depth-first search must be checked to see if the edge-labels of the boundary edges are all consistent with some face-label of F . This later is node-consistency enforced by the ~ relation, relating junction­ loops and face-labels. Similarly, junction-pairs describe local labelings for edges, and are found by an exhaustive but local search.

The maximum number of edge-labels in the edge hierarchy, mE, is constant and equal to five for polyhedral images. The maxi­ mum number of junctions (resp. junction-pairs) at any vertex (resp. edge) of the image, mJ (resp. mp ), is exponential in the complexity of the image, described by the three parameters (max lVI, max lEI, max IFI):

Worse than mJ and mp, the maximum number of junction­ loops at any face of the image, mL, is doubly exponential in the complexity of the image:

4. Constraint Satisfaction and Propagation

Constraints at all nodes in the planar network should be propa­ gated uniformly over all vertex-edge, edge: face, and face-vertex links. The local labeling constraints are the junctions, junction­ pairs, and junction-loops. Let's describe the complete CSP over vertex-edge-face links, after all the local constraints are found and enumerated.

Algorithm 1 (Parallel CSP over vertex-edge-face links) Initialize Vertex-Fifo, Edge-Fifo, and Face-Fifo respectively with all vertices, edges, and faces in the image. Loop until (and (emptyp Vertex-Fifo) (emptyp Edge-Fifo) (emptyp Face-Fifo)) do

1. Loop until (emptyp Vertex-Fifo) do Let V := (pop Vertex-Fifo) .
2. Loop for all edge E; in Edges(V) do Restrict junction-pairs of E; with junctions of V. If the set of junction-pairs of edge E; has been restricted then (insert E; Edge-Fifo) . ·
3. Loop for all face F; in Faces(V) do Restrict junction-loops ofF; with junctions of V . If the set of junction-loops of face F; has been restricted then (insert F; Face-Fifo).
4. Loop until (emptyp Edge-Fifo) do Let E := (pop Edge-Fifo) .
5. Loop for all face F; in Faces(E) do Restrict junction-loops ofF; with junction-pairs of E. If the set of junction-looil!; of face F; has been restricted then (insert F; Face-Fifo) .
6. Loop for all vertex V; in Vertices(E) do Restrict junctions of V; with junction-pairs of E. If the set of junctions of vertex V; has been restricted then (insert V; Vertex-Fifo) .
7. Loop until (emptyp Face-Fifo) do Let F :=(pop Face-Fifo) .
8. Loop for all vertex V; in Vertices(F) do Restrict junctions of V; with junction-loops of F. If the set of junctions of vertex V; has been restricted then (insert V; Vertex-Fifo) .
9. Loop for all edge E; in Edges(F) do Restrict junction-pairs of E; with junction-loops of F . If the set of junction-pairs of edge E; has been restricted then (insert E; Edge-Fifo) .

Algorithm 2 (Restrict junctions of V with junction-pairs of E) Loop for all J in Junctions(V) do

if Loop for all Pin Junction-Pairs(E) never J ~ aref(P, V) then if Loop for all Pin Junction-Pairs(E) thereis aref(P, V) ~ J

then replace J by its sub-junctions else delete J from Junctions(V) .

Complexity 1 The time complexity of constraint satisfaction and propagation over vertez-edge-face links of a polyhedral im­ age I is:

5. Global Consistency

Local consistency are nothing but 1) node consistency between locallabelings and labels for all nodes, and 2) arc consistency between two adjacent nodes for all arcs. Node consistency is enforced by s;; relation when we enumerate the locallabelings at a node. Arc consistency is enforced both ways by the loops in Algorithm 1. Global consistency from local node and arc consistencies at all vertices, edges, ·and faces of the image can be proved by labeling inductively from one face to its neigh­ boring faces, covering the whole image. For proof, the reader is referred to (Nguyen 1987).

Let's compare the parallel labeling algorithm with more gen­ eral results from topology (Hocking and Young 1961, Henle 1979) and from consistency of networks of constraints (Waltz 1975, Montanari 1976, Mackworth 1977, Freuder 1978). Recall that image labeling used to be called line labeling, because the core problem is to label all the lines or edges in the image. The network of edges with links between intersecting edges is not planar. By introducing vertices as new nodes and links between adjacent vertices and edges, the resulting network of edges and vertices is planar. Similarly, we add faces as nodes, and links between faces and their adjacent vertices and edges. The adjacency links describe the boundary relationship 8 be­ tween topological nodes. The planar topology of the image guarrantees that the network of vertices, edges, and faces is planar.

Junctions are used to capture the n-ary constraints among edges intersecting at a common vertex. They are exhaustively enumerated by looking at a 3D corner from different view­ points. A vertex-node is needed to store these junctions. The n-ary constraints among intersecting edges become binary con­ straints between these edges and the common vertex. Similarly, by creating higher level k-nodes and enumerating all the locally consistent labelings for these k-nodes, one can synthesize more extended k-ary constraints, covering finally all the edges in the image (Freuder 1978).

Labeling an imagl! can be seen as putting together a puzzle where the pieces are the vertices, edges, and faces of the im­ age. The pieces are required to have matched labelings at their interfaces. A vertex has junctions as labelings. An edge must have junction-pairs as labelings because it interfaces with its two ending vertices and its two adjacent faces through vertices. Similarly, a face must have junction-loops as local labelings. The segmentation of the image into vertices, edges, and faces guarrantees that labeling over the whole image is equivalent to enumerating the locallabelings at all the pieces, such that they satisfy their respective unary constraints, and doing arc con­ sistency between adjacent pieces, such that. they have matched labelings at their interfaces. From another perspective, the 2D topology allows us to enumerate all the implicit local n-ary constraints, or find the minimal equivalent networks (Monta­ nari 1977), without doing a global search.

Acknowledgments

The work reported here is partially funded by General Elec­ tric Aerospace Business Group. I would like to thank Joseph Mundy, Deepak Kapur, and David Cyrluk for many discus­ sions, and Tomas Lozano-Perez for pointing me to papers on network consistency.