Kd-Trees for Document Layout Analysis ∗
Christoph Dalitz · 2009
Kd-trees allow for efficient nearest neighbor searches and can therefore be useful for layout analysis problems in document image analysis. Two alternative customizations of the k nearest neighbor search in kd-trees are presented, such that it returns only within line or between line neighbors. One customization is based on a modified distance metric, which does not entirely suppress unwanted neighbors, but makes them less likely to be returned. The other customization is based on a search predicate. Both customizations have been implemented in the Gamera framework for document analysis and recognition. In experiments performed on the UW dataset, the probability for an unwanted neighbor with the modified distance metric turned out to be low, while the runtime of the search was considerably less than that of the search with a predicate.