IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i15p3336-d1206207.html
   My bibliography  Save this article

On a Fast Hough/Radon Transform as a Compact Summation Scheme over Digital Straight Line Segments

Author

Listed:
  • Dmitry Nikolaev

    (Institute for Information Transmission Problems RAS, 127051 Moscow, Russia
    Smart Engines Service LLC, 117312 Moscow, Russia)

  • Egor Ershov

    (Institute for Information Transmission Problems RAS, 127051 Moscow, Russia)

  • Alexey Kroshnin

    (Institute for Information Transmission Problems RAS, 127051 Moscow, Russia
    International Laboratory of Stochastic Algorithms and High-Dimensional Inference, Higher School of Economics, 109028 Moscow, Russia)

  • Elena Limonova

    (Smart Engines Service LLC, 117312 Moscow, Russia
    Federal Research Center Computer Science and Control RAS, 119333 Moscow, Russia)

  • Arseniy Mukovozov

    (Smart Engines Service LLC, 117312 Moscow, Russia)

  • Igor Faradzhev

    (Smart Engines Service LLC, 117312 Moscow, Russia
    Deceased.)

Abstract

The Hough transform, interpreted as the discretization of the Radon transform, is a widely used tool in image processing and machine vision. The primary way to speed it up is to employ the Brady–Yong algorithm. However, the accuracy of the straight line discretization utilized in this algorithm is limited. In this study, we propose a novel algorithm called A S D 2 that offers fast computation of the Hough transform for images of arbitrary sizes. Our approach adopts a computation scheme similar to the Brady–Yong algorithm but incorporates the best possible line discretization for improved accuracy. By employing the Method of Four Russians, we demonstrate that for an image of size n × n where n = 8 q and q ∈ N , the computational complexity of the A S D 2 algorithm is O ( n 8 / 3 ) when summing over O ( n 2 ) digital straight line segments.

Suggested Citation

  • Dmitry Nikolaev & Egor Ershov & Alexey Kroshnin & Elena Limonova & Arseniy Mukovozov & Igor Faradzhev, 2023. "On a Fast Hough/Radon Transform as a Compact Summation Scheme over Digital Straight Line Segments," Mathematics, MDPI, vol. 11(15), pages 1-22, July.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:15:p:3336-:d:1206207
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/15/3336/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/11/15/3336/
    Download Restriction: no
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:11:y:2023:i:15:p:3336-:d:1206207. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.