BibTeX entry

@PHDTHESIS{199906Benoit_Huet,
  AUTHOR={Benoit Huet},
  TITLE={Object Recognition From Large Libraries of Line Patterns},
  SCHOOL={University of York},
  MONTH=Jun,
  YEAR=1999,
  URL={http://www.bmva.org/theses/1999/1999-huet.pdf},
}

Abstract

The overall aim of this thesis is to provide a hierarchical framework of methodologies for recognising objects represented as line patterns from large structural libraries. One of the novel aspects of our work is a new shape representation for rapidly indexing and recognising line-patterns from large databases. The basic idea is to exploit both geometric attributes and structural information to compute a twodimensional relational pairwise geometric histogram. Shapes are indexed by searching for the line-pattern that maximises the cross-correlation of the normalised histogram bin-contents. A sensitivity study reveals that the structural gating of the histogram not only improves recognition performance, but it also overcomes the problem of saturation when large patterns are being recalled. This technique provides the first level of the hierarchy, which is used to prune the database of many unwanted candidates. The intermediate level of our hierarchical framework is based on a novel similarity measure for object recognition from large libraries of line-patterns. This operates at a more local image level than the histogram based indexing layer. The measure is derived from a Bayesian consistency criterion and resembles the Hausdorff distance. This consistency criterion has been developed for locating correspondence matches between attributed relational graphs using iterative relaxation operations. Our aim here, is to simplify the consistency measure so that it may be used in a non-iterative manner without the need to compute explicit correspondence matches. This considerably reduces the computational overheads and renders the consistency measure suitable for large-scale object recognition. A sensitivity study reveals that the method is capable of delivering a recognition accuracy of 94%. A Bayesian graph matching algorithm for data-mining from large structural databases operates as final level of the hierarchy. The matching algorithm uses both edge-consistency and node attribute similarity to determine the a posteriori probability of a query graph for each of the candidate matches in the reduced database generated by the lower levels of the hierarchy. The node feature-vectors are constructed by computing normalised histograms of pairwise geometric attributes. Attribute similarity is assessed by computing the Bhattacharyya distance between the histograms. Recognition is realised by selecting the candidate with the largest a posteriori probability. Here the recognition technique is shown to significantly outperform a number of algorithm alternatives. For each of the above methodologies a thorough sensitivity study is undertaken for a library of over 2500 lines-patterns. We investigate the algorithms under linedropout, line fragmentation, line addition and line end-point position errors. The analysis reveals the robustness of each method on its own as well as within the hierarchical framework. This suggests that there is a degree of complementarity between the approaches.