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:

1. begins with first unit of 5#5
2. selects second unit of 5#5, begins to construct children of first node
3. process continues to level 77#77 of the tree
paths from root to any successful nodes at level 77#77: consistent labelings
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

1. 107#107 defined everywhere on 67#67
( 108#108, such that 109#109)
2. 107#107 is single-valued on 69#69
(109#109 and 110#110 imply 111#111)
3. 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