Fast Discrete Radon Transformation
Channel: Kevin's Mathematical Musings
Date: 2021-05-24

The organ card reader software finishes with the Discrete Radon Transformation, a fast and exact method for detecting straight lines in an image.

See https://www.youtube.com/playlist?list=PLJfJkAAvFdDViweW23xzXpbE2cDJx4YVR for the full playlist of this series.

For further video enjoyment, check out Cliff Stoll’s video on the Klein bottle. https://www.youtube.com/watch?v=AAsICMPwGPY

00:00 Introduction
01:05 Review: the Hough transform
02:43 Problems with Hough transform
04:26 Discrete Radon transform
06:47 Why is discrete Radon slow?
07:42 Fast DRT - Setup
10:08 Fast DRT - Divide and conquer
12:15 Fast DRT - Error analysis
13:54 Fast DRT - Symmetry
15:34 Fast DRT - Topology
20:41 Conclusions
21:03 Coming attractions

FOR FURTHER READING

William H. Press. “Discrete Radon transform has an exact, fast inverse
and generalizes to operations other than sums along lines.”
Proc. Nat. Acad. Sci. 103:51 (December 19, 2006), pp. 19249-19254
https://www.pnas.org/cgi/doi/10.1073/pnas.0609228103

Paul V.C. Hough. “Method and means for recognizing complex patterns”.
U,S. Patent 3.069,654 (December 18, 1962).
https://patents.google.com/patent/US3069654A/en

George G. Moshos. “Error analysis of binary rate multipliers.”
NASA Technical Note TN D-3124. Cleveland, O.: NASA Lewis Research
Center, December, 1965.
https://ntrs.nasa.gov/api/citations/19660002866/downloads/19660002866.pdf

IMAGES

“Portrait of Johann Radon” https://commons.wikimedia.org/wiki/File:Johann_Radon_cr.jpg
Copyright expired in US.

Wannapik Studio, “Old West Gambling Gambler Poker Card Player”
https://www.wannapik.com/vectors/4468#!
CC-BY-3.0 https://creativecommons.org/licenses/by/3.0/

David Benbennick. “Möbius Strip”
https://commons.wikimedia.org/wiki/File:M%C3%B6bius_strip.jpg
GNU Free Documentation License, version 1.2 or later
https://www.gnu.org/licenses/fdl-1.3.html

Ole Husby, “Klein Bottle” https://www.flickr.com/photos/khianti/5093670519
CC-BY-SA 2.0 https://creativecommons.org/licenses/by-sa/2.0/

Conseil Européen pour la Récherche Nucléaire (CERN). “The decay of a
lambda particle in the 32 cm hydrogen bubble chamber.”
https://cds.cern.ch/record/39474
License terms:https://copyright.web.cern.ch/

Trammell Hudson (“autopilot”). “Space Rocks (game)”
https://commons.wikimedia.org/wiki/File:Space_Rocks_(game).jpg
CC-BY-SA 3.0 https://creativecommons.org/licenses/by-sa/3.0/

“The M.I.T Numerical Controlled Machine Tool.” Douglas T. Ross,
“Papers on Automatic Programming for Numerically Controlled Machine Tools.”
Cambridge, Mass.:MIT, January 7, 1958, p. 3.
http://www.bitsavers.org/pdf/mit/whirlwind/apt/APT_Reports_Jan58.pdf
Published in the US without notice of copyright prior to
the enactment of the US Copyright Act of 1976.

International Emergency Medicine Education Project. “Abdominal pain CT
shows cholecyctitis” https://www.flickr.com/photos/iem-student/29673235938
CC-BY-NC-SA 2.0 https://creativecommons.org/licenses/by-nc-sa/2.0/

All other images are original to
the videographer.

MUSIC

J.S. Bach, Prelude and Fugue No. 6 in A major, BWV 536 from
Das Wohltempierte Klavier, Teil I. Recorded by Evgeniy E. Moshkin,
3 August 2018 using the Hauptwerk virtual pipe organ software with
the Freisach sample set. https://imslp.org/wiki/File:PMLP111692-bwv536.ogg
CC-BY-NC-SA 4.0 https://creativecommons.org/licenses/by-nc-sa/4.0/


© 2021 Kevin B. Kenny
CC-SA-NC 4.0 https://creativecommons.org/licenses/by-nc-sa/4.0/