RELATIONAL MATCHING BY DISCRETE RELAXATION

This paper describes a symbolic approach to relational matching. The n ovelty of the method lies in its Bayesian modelling of relational cons istency which leads to a global matching criterion with a unique mathe matical structure and robustness to error. Unlike many alternatives in the literature, the method is not limited to the use of binary constr aints; it can accommodate N-ary relations of varying order. In consequ ence of this assumed model, the consistency of match is gauged by a co mpound exponential function of a higher-order Hamming distance between symbolic relations; there is a single exponential associated with eac h potential relational mapping. These exponential functions naturally soften the symbolic constraints represented by the relational mappings . This compound exponential structure also bestows a number of tangibl e benefits over the use of quadratic alternatives. In the first instan ce, it both renders the method more robust to errors and allows it to operate effectively in a large space of relational mappings. Moreover, this robustness to inconsistency means that the method may be operate d without the need for an explicit null matching process. Unmatchable entities are identified by a constraint filtering operation once the r elaxation scheme has converged. The utility of the method is illustrat ed on the matching of hedge structures in SAR images against their car tographic representation in a digital map.