Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published November 22, 2021 | public
Journal Article

Euclidean Distance Approximations From Replacement Product Graphs

Abstract

We introduce a new chamfering paradigm, locally connecting pixels to produce path distances that approximate Euclidean space by building a small network (a replacement product) inside each pixel. These "RE-grid graphs" maintain near-Euclidean polygonal distance contours even in noisy data sets, making them useful tools for approximation when exact numerical solutions are unobtainable or impractical. The RE-grid graph creates a modular global architecture with lower pixel-to-pixel valency and simplified topology at the cost of increased computational complexity due to its internal structure. We present an introduction to chamfering replacement products with a number of case study examples to demonstrate the potential of these graphs for path-finding in high frequency and low resolution image spaces which motivate further study. Possible future applications include morphology, watershed segmentation, halftoning, neural network design, anisotropic image processing, image skeletonization, dendritic shaping, and cellular automata.

Additional Information

© 2021 IEEE. Manuscript received January 29, 2021; revised July 3, 2021, September 10, 2021, and October 23, 2021; accepted November 7, 2021. Date of publication November 22, 2021; date of current version November 30, 2021. This work was supported by the National Science Foundation through the Graduate Research Fellowship Program. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Dong Xu. The authors would like to thank Joseph Rispoli, Colin Wright, Amit Patel, Jason Williford, Eric Moorhouse, Brad Fitzgerald, and Elwyn Berlekamp for helpful discussions.

Additional details

Created:
September 15, 2023
Modified:
October 23, 2023