<abstract xmlns="http://www.w3.org/1999/xhtml"><p>We introduce a novel concept of the <italic>augmented Farey table</italic> (AFT). Its purpose is to store the ranks of fractions of a <italic>Farey sequence</italic> in an efficient manner so as to return the <italic>rank</italic> of any query fraction in constant time. As a result, computations on the digital plane can be crafted down to simple integer operations; for example, the tasks like determining the extent of collinearity of integer points or of parallelism of straight lines—often required to solve many image-analytic problems—can be made fast and efficient through an appropriate AFT-based tool. We derive certain interesting characterizations of an AFT for its efficient generation. We also show how, for a fraction not present in a Farey sequence, the rank of the <italic>nearest fraction</italic> in that sequence can efficiently be obtained by the <italic>regula falsi</italic> method from the AFT concerned. To assert its merit, we show its use in two applications—one in polygonal approximation of digital curves and the other in skew correction of engineering drawings in document images. Experimental results indicate the potential of the AFT in such image-analytic applications.</p></abstract>

We introduce a novel concept of the augmented Farey table (AFT). Its purpose is to store the ranks of fractions of a Farey sequence in an efficient manner so as to return the rank of any query fraction in constant time. As a result, computations on the digital plane can be crafted down to simple integer operations; for example, the tasks like determining the extent of collinearity of integer points or of parallelism of straight lines—often required to solve many image-analytic problems—can be made fast and efficient through an appropriate AFT-based tool. We derive certain interesting characterizations of an AFT for its efficient generation. We also show how, for a fraction not present in a Farey sequence, the rank of the nearest fraction in that sequence can efficiently be obtained by the regula falsi method from the AFT concerned. To assert its merit, we show its use in two applications—one in polygonal approximation of digital curves and the other in skew correction of engineering drawings in document images. Experimental results indicate the potential of the AFT in such image-analytic applications.

On the Farey sequence and its augmentation for applications to image analysis

Department of Computer Science and Engineering

International Journal of Applied Mathematics and Computer Science

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"On the Farey sequence and its augmentation for applications to image analysis"}

We introduce a novel concept of the augmented Farey table (AFT). Its purpose is to store the ranks of fractions of a Farey sequence in an efficient manner so...

On the Farey sequence and its augmentation for applications to image analysis

Data publikacji: 23 wrz 2017

Zakres stron: 637 - 658

Otrzymano: 20 paź 2016

Przyjęty: 02 kwi 2017

DOI: https://doi.org/10.1515/amcs-2017-0045

Słowa kluczowe
Farey sequence, Farey table, fraction rank, theory of fractions, image analysis

© 2017 Sanjoy Pratihar et al., published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

On the Farey sequence and its augmentation for applications to image analysis

Data publikacji: 23 wrz 2017

Zakres stron: 637 - 658

Otrzymano: 20 paź 2016

Przyjęty: 02 kwi 2017

DOI: https://doi.org/10.1515/amcs-2017-0045

Słowa kluczoweFarey sequence, Farey table, fraction rank, theory of fractions, image analysis

© 2017 Sanjoy Pratihar et al., published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Słowa kluczowe
Farey sequence, Farey table, fraction rank, theory of fractions, image analysis