2.3.2
Figure 2.5: Forbidden edge patterns.
There are two essential ways to impose constraints: exact and inexact. In the inexact way, any violation of the constraints incurs a finite cost. The use of inexact constraints are seen in works on edge and boundary detection using relaxation labeling, e.g.
[Zucker 1976 ; Hanson and Riseman 1979 ; Faugeras and Berthod 1981]. This is also what we have done so far, e.g. with the g function. On the other hand, when the constraints are imposed exactly, any violation is forbidden. For example, if edges are required to form a boundary of single pixel width, the adjacent parallel edges are not allowed. A family of four forbidden edge configurations are given in Fig.2.5; they correspond to, respectively, isolated edge (a terminated boundary), sharp turn, quadruple junction, and ``small structure''.
Let 
be the total number of the occurrences of the forbidden
configurations in 
. When there are no forbidden edge
configurations, 
must hold exactly. Under this constraint,
the MAP edge detection problem may be posed as follows
[Geman et al. 1990 ; Heitz and Bouthemy 1993])
where 
is the posterior energy due to the inexact
constraints. The minimization is performed over all
configurations for which 
. This is a problem of constrained
minimization ( cf.
Section 8.3).
Figure: Horizontal and vertical edges.
The constrained minimization may be
computed by using the penalty method.
Any forbidden local configuration is finally penalized by using an
infinitely large clique potential; the exact constraints are imposed by
gradually increasing the penalties against the violation of inexact
constraints. An example is given below which rules out adjacent,
horizontally parallel edges. Divide 
into a
horizontal edge field 
and a vertical edge field
(
), respectively, as in
Fig.2.6. Each 
and 
variable takes a
value in 
as 
. We may define the following energy
to penalize adjacent, horizontally parallel edges [Koch et al. 1986]
where 
is a constant. The above is non-zero when both
and 
take the value 1, indicating the occurrence of
a pair of horizontally parallel edges. This incurs a penalty
. To prohibit the formation of such edge configurations, we
can gradually increase 
to a sufficiently large value
(
) so that the final minimal solution does not contain any
horizontally parallel edges as a result of energy minimization. In the
same way, 
can be added
to rule out adjacent, vertically parallel edges.