A Caltech Library Service

Euclidean Distance Approximations From Replacement Product Graphs

Terlep, T. Arthur and Bell, Mark R. and Talavage, Thomas M. and Smith, Douglas L. (2021) Euclidean Distance Approximations From Replacement Product Graphs. IEEE Transactions on Image Processing, 31 . pp. 125-137. ISSN 1057-7149. doi:10.1109/tip.2021.3128319.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Terlep, T. Arthur0000-0002-9648-0074
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.
Funding AgencyGrant Number
NSF Graduate Research FellowshipUNSPECIFIED
Subject Keywords:Chamfer, euclidean distance, distance approximation, replacement product, graph theory, path-finding, eikonal equation, Dijkstra’s algorithm
Record Number:CaltechAUTHORS:20220105-251355000
Persistent URL:
Official Citation:T. A. Terlep, M. R. Bell, T. M. Talavage and D. L. Smith, "Euclidean Distance Approximations From Replacement Product Graphs," in IEEE Transactions on Image Processing, vol. 31, pp. 125-137, 2022, doi: 10.1109/TIP.2021.3128319
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:112719
Deposited By: Tony Diaz
Deposited On:08 Jan 2022 22:12
Last Modified:09 Jan 2022 21:49

Repository Staff Only: item control page