Chapter 17 The Consistent Labeling Problem

17.1 Introduction

10#10-ary consistent-labeling problem (CLP): 4-tuple 1#1

2#2: set of 3#3 units

125#125: set of possible labels

4#4: unit-constraint relation

4#4: 10#10-ary relation over the set 5#5 of units

6#6: units
7#7 mutually constrain one
another

121#121: unit-label constraint relation

121#121: 10#10-ary relation over the set 8#8 of unit-label pairs

9#9: units
7#7
assigned

corresponding labels
10#10

elements of 121#121: allowable labeling of ordered size-10#10 subsets of unit
set 5#5

labeling of subset
11#11 of 5#5: mapping
12#12 from 13#13 to 125#125

A labeling 3#3 of a subset 13#13 of the units is consistent if whenever
7#7 are in 13#13 and the 10#10-tuple
14#14
is in 4#4, then
15#15
16#16
is in 121#121.

goal of consistent labeling problem: to find one or all consistent-labelings

17.2 Examples of Consistent-Labeling Problems

consistent-labeling problems arise in:

- computer vision
- artificial intelligence
- science
- engineering

17.2.1 The 10#10-Queens Problem

10#10-queens problem: given 17#17 chessboard and 10#10 queens

queens placed on chessboard: no queen captures any other queen

no two queens in same row, same column, or same diagonal of chessboard

10#10-queens problem: modeled as consistent-labeling problem

unit set
18#18: set of rows on chessboard

label set
19#19: set of columns on chessboard

exactly one queen per row: labeling specifies the column where queen placed

unit-constraint relation 4#4: set
20#20

unit-label constraint relation:

21#21

e.g. pair 22#22 is in 121#121 since two queens do not capture each other

e.g. pair 23#23 and 24#24 are not in 121#121

consistent labeling: solve 10#10-queens problem with constraints satisfied

17.2.2 The Latin-Square Puzzle

Latin-square puzzle: 25#25 matrix, 26#26 objects arranged on matrix,
one/square

consider 27#27 puzzle for ease of illustration

object is one of four colors
28#28

object has one of four shapes
29#29

The problem is to arrange the objects such that each row, each column, and
each of the two main diagonals of the matrix contains exactly one object of
each color and exactly one object of each shape.

set of units
30#30: 16 squares of matrix

labels: objects to be placed on squares, e.g. red square, blue triangle, ...

Cartesian product set 31#31

model 4#4 as quaternary constraint:

32#32

The unit-label constraint relation 121#121 would then consist of quadruples of unit-label pairs of the form 33#33, where 34#34 is in 4#4, 35#35 for 36#36, and when 37#37 and 38#38.

17.2.3 The Edge-Orientation Problem

edge-orientation problem: arises in low-level vision

local edge operator: applied to determine edge strength and direction

due to image noise: edge operator output is also noisy

prior knowledge: most edges highly continuous with low curvature

maximum bending angle of any small edge segment: limited to some maximum

e.g. 39#39 northeast of 40#40 (direction upward): 39#39 between
41#41 from horizon

e.g. 39#39 northwest of 40#40 (direction upward): 39#39 between
42#42 from horizon

predicate
43#43: returns true if 44#44 compatible for
45#45, false otherwise

5#5: set of pixels of the image

125#125: set of possible edge orientations, including special value 46#46

47#47: set of possible edge orientations of pixel 40#40

48#48: set of neighboring pixels to pixel 40#40

edge orientation of given pixel: constrained only by neighborhood edge:

49#49

50#50 predicate satisfied: pairs of neighboring pixels have compatible labels

at least one labeled 46#46: pairs of neighboring pixels have compatible labels

unit-label constraint relation:

51#51

52#52

=====Garfield 17:53=====

17.2.4 The Subgraph-Isomorphism Problem

vertices 53#53: set of vertices

edges 54#54: nonreflexive, symmetric binary relation over 53#53

graph 55#55: pair 56#56

It is often necessary to determine whether two graphs representing two
different entities are identical, except for the labels of the vertices,
indicating that the two objects have the same structure.

57#57 isomorphic to 58#58: if there is one-one, onto mapping 3#3

from 53#53 to 59#59, satisfying that
60#60

3#3: graph isomorphism

graph isomorphism from graph 121#121 to graph 61#61

=====Fig. 17.1=====

unit-set 5#5: set of vertices 53#53 of 55#55

label-set 125#125: set of vertices 59#59 of 62#62

unit-constraint relation 4#4: edge set 54#54 of 55#55

unit-label constraint relation 121#121:

63#63

graph-isomorphism problem: dual consistent-labeling problem

graph-isomorphism: 64#64 and its inverse must be consistent labelings

17.2.5 The Relational-Homomorphism Problem

subgraph-isomorphism: special case of relational-homomorphism problem

relational-homomorphism: defined on 10#10-ary relations, instead of binary

homomorphism: also structure-preserving mapping, not necessarily one-one

65#65: two sets

66#66: 10#10-ary relation over set 67#67

68#68: function mapping elements of set 67#67 into set 69#69

composition of 4#4 with 70#70:

71#71

composition of a binary relation 121#121 with a mapping 72#72

=====Fig. 17.2=====

73#73: second 10#10-ary relation

relational homomorphism from 4#4 to 61#61: mapping
68#68 satisfying
74#74

relational homomorphism applied to 10#10-tuple of 4#4: result is 10#10-tuple
of 61#61

relational homomorphism 72#72 from binary relation 121#121 to binary relation 61#61

=====Fig. 17.3=====

finding relational homomorphism: sometimes called relational matching

relational homomorphism: maps elements of 67#67 to 69#69 with same relationships

relational monomorphism: relational homomorphism that is one-one

monomorphism: stronger match than homomorphism

relational isomorphism 3#3 from 10#10-ary relation 4#4 to 10#10-ary relation S:

one-one relational homomorphism from 4#4 to 61#61,

and 75#75 is relational homomorphism from 61#61 to 4#4

relational isomorphism: 65#65 have same number of elements

relational isomorphism: each primitive in 67#67 maps to unique primitive in 69#69

relational isomorphism: each primitive in 67#67 mapped to by a primitive of 69#69

relational isomorphism: each tuple in 4#4 has corresponding one in 61#61, vice
versa

relational isomorphism: strongest kind of match; symmetric match

graph isomorphism: binary-relational isomorphism

relational-homomorphism fits consistent-labeling: like graph-isomorphism

67#67: set of units

69#69: set of labels

unit-constraint relation: relation 4#4 of relational homomorphism

unit-label relation 121#121:

76#76

consistent labeling solution: relational homomorphism from 67#67 to 69#69

17.3 Search Procedures for Consistent Labeling

no consistent labelings: returns the empty set

17.3.1 The Backtracking Tree Search

backtracking tree search:

- begins with first unit of 5#5
- selects second unit of 5#5, begins to construct children of first node
- process continues to level 77#77 of the tree

simple digraph-matching problem:

indegree78#78 indegree79#79, outdegree78#78 outdegree79#79

=====Fig. 17.4=====

portion of the tree search for solving the graph-matching problem

=====Fig. 17.5(a)=====

17.3.2 Backtracking with Forward Checking

backtracking tree search: has exponential time complexity

forward checking: once a unit-label pair 80#80 is instantiated at a node

in the tree, the constraints imposed by the relations

cause instantiation of some future unit-label pairs 81#81

to become impossible

if 82#82 then 83#83 can either be 84#84 or 85#85, ...

=====Fig. 17.5(b)=====

86#86: future-error table

one future-error table for each level of recursion in tree search

87#87: still possible to instantiate 81#81

88#88: 81#81 already been ruled out

89#89; 81#81 impossible from previous level of recursion

status of future-error table during backtracking with forward checking

=====Fig. 17.7=====

segment of backtracking tree search for 6-queen problem

(a) backtracking alone, (b) backtracking with forward checking

=====Fig. 17.6=====

17.3.3 Backtracking with Discrete Relaxation

forward-checking algorithm: prunes search tree of nodes ruled out

discrete relaxation: iterative polynomial complexity procedure

discrete relaxation: greatly reduces search for tightly-constrained problems

discrete relaxation: constrains search further for not tightly constrained
tree

=====function psi=====

execution of the 90#90 operator at the node 91#91 of the tree

=====Fig. 17.8=====

17.3.4 Ordering the Units

better to choose the unit that has the fewest labels left as the next unit

17.3.5 Complexity

consistent-labeling problem: NP-complete problem

forward checking and look-ahead: drastically reduce number of nodes searched

forward checking and look-ahead: do not change overall complexity

17.3.6 The Inexact Consistent-Labeling Problem

extracted line from images: some missing, partially missing, extra, distorted

inexact consistent-labeling problem: allows some error for real-life problems

92#92: no error thus no penalty

93#93: errors equally distributed for 6 edges of G1

94#94: 81#81 impossible from previous level of recursion

tree search: initially called with
95#95

96#96: never allowed to exceed error threshold 97#97

part of the inexact forward checking procedure for digraph matching

=====Fig. 17.10=====

17.4 Continuous Relaxation

discrete algorithms: calling a label either possible or impossible

continuous procedures: associate probability or certainty that 98#98
assigned 124#124

=====Oldie 33:104=====

17.5 Vision Applications

Line Labeling with Discrete Relaxation

assumption: simple blocks world scenes of planar polyhedra

assumption: no shadows or cracks and trihedral vertices

assumption: polygonal planar surfaces

line drawing of simple polyhedral objects

=====Fig. 17.11=====

four types of junctions: L, FORK, ARROW, T

=====Fig. 17.12=====

99#99: convex interior line segments

100#100: concave interior line segments

101#101: boundary line segments with visible surface on right

line labeling of a 2D line drawing of a 3D object

=====Fig. 17.13=====

labelings of the 18 physically possible junctions

=====Fig. 17.14=====

each face is a plane, not a curved surface

an impossible object: no valid label for the line marked with circle

=====Fig. 17.15=====

Fraser's spiral: illusory spiral evoked by concentric circles

point a finger at a point, use another hand to trace the circle

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 1.1=====

seeing versus thinking: difficult to see a cube in (a)

ambiguous Necker cube: lower-left corner or upper-right corner is closer?

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 1.2=====

Zollner Illusion: diagonals are parallel

Poggendorf Illusion: two diagonal segments collinear

Helmholtz's Squares: two squares appear rectangular

Muller-Lyer Illusion: both lines have the same length

Hering Illusion: two horizontal and parallel straight lines appear bowed

Wundt Illusion: two horizontal and parallel straight lines appear bowed

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 1.3=====

Poseidon and the Mermaid: mermaid's tail fin is Poseidon's moustache

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 1.4=====

Young Girl/Old Woman: young girl's chin is old woman's nose

Vase/Faces: black region is background or foreground

Pop In/Pop Out: spontaneous reversal of perceived concavities and convexities

Six Cubes/Seven Cubes: reversal of perceived concavities and convexities

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 1.5=====

Belvedere: seven geometrical inconsistencies not readily apparent

1. middle-level pillars cross from front to rear, and vice versa

2. ladder's base inside the building, but its top outside

3. topmost level at right angles to middle level

4. cube examined by person on bench: geometrically impossible

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 1.6=====

Penrose Triangle: if it's polyhedron, it could not form closed loop

Penrose staircase: descends (ascends) all the way around to starting step

Escher Cube: top inconsistent with its base

two-pronged trident: three prong terminals with two prong base

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 1.7=====

consistent line labels necessary but not sufficient for physical realizability

(a) line drawing with no consistent labeling

(b) consistent labeling of line drawing of impossible polyhedron

(c) physically realizable line drawing with unrealizable consistent labeling

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 4.9=====

interpretation changes when image turned upside down

right-side up: two lava cones with craters

upside down: two craters with mounds

implicit assumption: scene is lit from above

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 1.8=====

set of units 5#5: set of line segments of the line drawing

set of labels 125#125: label set
102#102

only lines that meet at a junction constrain one another

103#103

unit-label constraint relation 121#121: defined according to legal labeling

Inexact Matching in Two-Dimensional Shape Recognition

2D shape matching: recognition task in many machine vision applications

2 shape primitives: simple, near-convex pieces and intrusions into boundary

primitives: allowed to overlap

intrusion relation 104#104: (simple part 1, intrusion, simple part 2)

104#104: two simple parts touch or nearly touch and form boundary of intrusion

protrusion relation 105#105: (intrusion 1, simple part, intrusion 2)

105#105: simple part protrudes between two intrusions

decomposition of polygonal shape into primitives

=====Fig. 17.16=====

17.5.1 Image Matching Using Continuous Relaxation

initial strong matches: provide context for matching less well-defined objects

initial strong matches: islands of confidence

features: region size, intensity, location, texture, shape measures

relationships among primitives: adjacency, relative position, distance

17.6 Characterizing Binary-Relation Homomorphisms

106#106

107#107 is a homomorphism of 121#121 into 61#61 if and only if

- 107#107 defined everywhere on 67#67

( 108#108, such that 109#109) - 107#107 is single-valued on 69#69

(109#109 and 110#110 imply 111#111) - 112#112

17.6.1 The Winnowing Process

113#113 implies
114#114

how functions that are homomorphisms are constrained

=====Fig. 17.17=====

115#115 implies
116#116

how functions that are homomorphisms are constrained

=====Fig. 17.18=====

digraph for the example relations 121#121 and 61#61

=====Fig. 17.19=====

4#4: check if there is outgoing or incoming arrows

=====Fig. 17.20=====

all pairs in 121#121 as rows, all pairs in 61#61 as columns

112#112 implies
117#117, thus 118#118

from table at left, derive 119#119

=====Fig. 17.21=====

repeat above process using 119#119

=====Fig. 17.22=====

successive eliminations of mapping possibilities by successive winnowing

120#120: choose 121#121 from 1 thus 121#121 cannot be anything else

120#120: 3, 4 can only be 122#122 or 123#123, thus generate left table
of 124#124

from left table of 124#124 generate 124#124

repeat above process to generate 125#125

=====Fig. 17.23=====

17.6.2 Binary-Relation Homomorphism Characterization

17.6.3 Depth-First Search for Binary-Relation Homomorphisms

tabulation of basis relations that are defined everywhere

126#126 as above; others derived similarly

=====Fig. 17.24=====

tree determined by depth-first search: range 127#127 allowed to repeat

=====Fig. 17.25=====

eight homomorphisms and their corresponding homomorphic images

=====Fig. 17.26=====

=====IPPR Conf. on Comp. Vis., Graphics, and Image Processing=====

=====paper.outline=====

=====joke=====

2002-02-26