Abstract
This thesis is concerned with the probabilistic relaxation labelling algorithm and its application to low level image analysis. In general terms there exists a labelling problem of assigning one of a set of labels to each of the nodes of a lattice. If the initial information based on measurements on each node is inconclusive due to noise or uncertainty in the measurement process, contextual information in the form of constraints imposed by the mutual relationships between individual nodes may be used to reduce or even resolve the ambiguity. The probabilistic relaxation algorithm is a method of achieving this. A review of the main topics in the field of probabilistic relaxation is presented. A revised approach, developed recently for the generalized graph labelling problem, that incorporates the use of binary measurements was adopted for the case when the objects to be labelled are arranged in a rectangular grid with known adjacency relations. There is a large number of problems within the field of image analysis which may be formulated as such labelling problems. In this case a dictionary of permissible label configurations is available. The novelty of this work lies on the inclusion of measurements concerning binary relations between the objects to be labeled. These are compared with the corresponding binary relations between the nodes of the dictionary. This way, one of the major objections to probabilistic relaxation, namely the disregard of the data after the initial assignment of probabilities, is removed. This is then compared with previous methods. We show that the inclusion of binary relations greatly improves the performance of algorithms for edge detection and compare our approach with previously developed dictionary based approaches, both theoretically and experimentally. Also, a comparison with other edge-postprocessing strategies is provided. The probabilistic relaxation method developed was also applied as a postprocessing technique to the problem of line labelling with aim to refine the initial labelling via contextual information. In this particular problem the assumptions made by the theory are more closely applicable than in any other case, due to the way the results from the filtering stage were used.