Document image analysis by probabilistic network and circuit diagram extraction

Informatica, Oct, 2005 by Andras Barta, Istvan Vajk

3. Constructing a prior probability distribution, p(x). This distribution describes the background knowledge.

Based on the network definition various inference problems can be solved. The main advantage of the Bayesian framework is that both predictive and diagnostic evidence can be included. The predictive evidence [e.sup. ] provides high level hypothesis support and it propagates downward in the network. The diagnostic evidence [e.sup.-] is the actually observed event and it provides an upward information flow. This message propagation can be applied to casual polytrees or singly connected networks that is networks with no loops. This bidirectional flow provides the inference of the network. It can be calculated by the Pearl's message passing algorithm [8]. The predictive and diagnostic evidence is separated and the propagation of their effect is described by two variables, the [lambda] and [pi] messages,

[lambda](x) = p([e.sup.-] | x)

[pi](x) = p(x | [e.sup. ]) (2)

The probability of the node given the evidence is calculated from these messages based on the Bayes rule.

p(x | [e.sup. ],[e.sup.-]) = [alpha]p([e.sup.-] | x, [e.sup. ])p(x | [e.sup. ], = [alpha]p([e.sup.-] | x)p(x | [e.sup. ]) = a[lambda](x)[pi](x) (3)

where [alpha] is a normalizing constant. The propagation from one node to the other is controlled by the conditional probability p(y | x). In case of trees the messages are calculated by the following propagation rules:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (4)

A node receives messages from all of its child nodes and sends a message to its parent (Figure 1).

[FIGURE 1 OMITTED]

This local updating can be performed recursively. Every node has a probability value that quantifies the belief of the corresponding object. The objects with high belief values are identified as the real objects of the image.

4.1 Node Description

How to assign the physical meaning to the nodes is a crucial issue. Here, we define the node value to identify the image bases. If the library contains L bases or image features, then the nodes can take the value of 1,2, .. , L. The model also introduces a belief or probability value at each node. This value determines the probability that the given image feature describes the image based on the evidence or knowledge. The value of the node has multinomial probability distribution with L-1 possible states

p([l.sub.1][l.sub.2], ... , [l.sub.K-1] | e),

where [l.sub.i] is the library reference or index to the [[zeta].sub.i] image base. As more evidence enters the network the node probabilities are recalculated. The features with high belief values are identified as the real components of the image. This provides a robust description, since it is not necessary to achieve exact match for the identification.

Since objects are position dependent, their description should be position dependent also. That means that to describe an object by image bases they have to be transferred to the position of the object. In this work the image base transformation includes displacement, rotation and scaling. The objects have hierarchical structure. Every feature or image element is described by the combination of other transferred image elements. In other words, an image feature is represented by lower level image bases