Distance transformations in digital images

doi:10.1016/S0734-189X(86)80047-0

Computer Vision, Graphics, and Image Processing

Volume 34, Issue 3, June 1986, Pages 344-371

https://doi.org/10.1016/S0734-189X(86)80047-0 Get rights and content

A distance transformation converts a binary digital image, consisting of feature and non-feature pixels, into an image where all non-feature pixels have a value corresponding to the distance to the nearest feature pixel. Computing these distances is in principle a global operation. However, global operations are prohibitively costly. Therefore algorithms that consider only small neighborhoods, but still give a reasonable approximation of the Euclidean distance, are necessary. In the first part of this paper optimal distance transformations are developed. Local neighborhoods of sizes up to 7×7 pixels are used. First real-valued distance transformations are considered, and then the best integer approximations of them are computed. A new distance transformation is presented, that is easily computed and has a maximal error of about 2%. In the second part of the paper six different distance transformations, both old and new, are used for a few different applications. These applications show both that the choice of distance transformation is important, and that any of the six transformations may be the right choice.

References (13)

G. Borgefors
Distance transformations in arbitrary dimensions
Comput. Vision, Graphics Image Process.
(1984)
A. Rosenfeld et al.
Distance functions on digital pictures
Pattern Recognit.
(1968)
P.E. Danielsson
Euclidean distance mapping
Comput. Graphics Image Process.
(1980)
A. Rosenfeld et al.
Sequential operations in digital picture processing
J. Assoc. Comput. Mach.
(1966)
G. Borgefors
Chamfering: A fast method for obtaining approximations of the Euclidean distance in N dimensions
U. Montanari
A method for obtaining skeletons using a quasi-Euclidean distance
J. Assoc. Comput. Mach.
(1968)

There are more references available in the full text version of this article.

Cited by (1624)

Rule-based continuous line classification using shape and positional relationships between objects in piping and instrumentation diagram
2024, Expert Systems with Applications
Recently, the digitization of piping and instrumentation diagrams (P&IDs) has become increasingly necessary in the plant industry. In previous studies on line recognition in P&IDs, lines were classified according to line signs after line detection. However, detailed studies on the classification of continuous lines are limited. Herein, a rule-based method for classifying continuous lines in a P&ID is proposed. This method uses the shape and positional relationships between objects in the P&ID to classify continuous lines into eight types: drain, annotation, spec break, dimension, extension, leader, thick continuous, and continuous line. A prototype system was developed to validate the proposed method, and line classification experiments were conducted on actual high-density industrial P&ID systems. The experimental results indicated that the average precision, recall, and F1 score for the five P&IDs were 96.300%, 97.945%, and 96.415%, respectively. These results indicate the excellent performance of the proposed method in classifying continuous lines for various P&IDs.
Artificial intelligence and classic methods to segment and characterize spherical objects in micrographs of industrial emulsions
2024, International Journal of Pharmaceutics
The stability of emulsions is a critical concern across multiple industries, including food products, agricultural formulations, petroleum, and pharmaceuticals. Achieving prolonged emulsion stability is challenging and depends on various factors, with particular emphasis on droplet size, shape, and spatial distribution. Addressing this issue necessitates an effective investigation of these parameters and finding solutions to enhance emulsion stability. Image analysis offers a powerful tool for researchers to explore these characteristics and advance our understanding of emulsion instability in different industries. In this review, we highlight the potential of state-of-the-art deep learning-based approaches in computer vision and image analysis to extract relevant features from emulsion micrographs. A comprehensive summary of classic and cutting-edge techniques employed for characterizing spherical objects, including droplets and bubbles observed in micrographs of industrial emulsions, has been provided. This review reveals significant deficiencies in the existing literature regarding the investigation of highly concentrated emulsions. Despite the practical importance of these systems, limited research has been conducted to understand their unique characteristics and stability challenges. It has also been identified that there is a scarcity of publications in multimodal analysis and a lack of a complete automated in-line emulsion characterization system. This review critically evaluates the existing challenges and presents prospective directions for future advancements in the field, aiming to address the current gaps and contribute to the scientific progression in this area.
A hole-filling based approach to controlling structural complexity in topology optimization
2023, Computer Methods in Applied Mechanics and Engineering
Shape and topology optimization problems are usually associated with geometrical restrictions. Effective control of structural complexity during the optimization process is important for various considerations, e.g., functionality, manufacturability, and aesthetics. Most existing approaches characterize structural complexity as the number of cavities. However, for three-dimensional structures, the genus (i.e., the number of tunnels) should also be considered as an additional topological constraint. In this paper, a hole-filling method is integrated into the bi-directional evolutionary structural optimization (BESO) computational framework to control the number and size of existing cavities and tunnels during the form-finding process. In the hole-filling method, excess cavities are filled with solid material and excess tunnels are covered by building sheet-like patches. The minimum size of the truss-like components and the minimum thickness of the sheet-like components can be controlled separately. Several two- and three-dimensional compliance minimization problems are presented to demonstrate the effectiveness and potential applications of the proposed approach. The structural performances of the optimized structures with and without complexity control are compared and analyzed. The results show that the developed methodology can produce structurally efficient designs with controllable topologies. It is also demonstrated that the generation of sheet-like components can considerably increase the stiffness of the optimized structure. The proposed approach is capable of generating diverse and competitive designs for architects and engineers to achieve a fine balance between architectural novelty and structural efficiency.
Optimization of sensor locations for a light pollution monitoring network
2023, Journal of Quantitative Spectroscopy and Radiative Transfer
Light Pollution is an environmental problem that needs to be retrieved by experimental means. However, to the best of our knowledge, there is no methodology nor a quantitative procedure to determine an optimal light pollution monitoring network. In this work, we propose a methodology for locating sensors in a light pollution monitoring network by formulating an optimization problem. We introduce an objective function that measures the representativeness of a set of locations using the spatial semi-variance over an image, and different levels of monitoring needs according to the environmental vulnerability of each location. To apply the methodology to a region of interest, we consider three inputs: a Nighttime-Light Image NTLI, an Environmental Vulnerability Map, and a constrained number of sensors. The output is a set of coordinates to locate sensors that consider the intensity of luminosity in nighttime images and its environmental impact. A case study shows that the methodology locates sensors in the most vulnerable areas in which measurements may optimally represent a wide region of the studied territory.
Analysis of very large voxel datasets
2023, International Journal of Applied Earth Observation and Geoinformation
The paper addresses the problem that large voxel models of detailed scenes in urban environments do not fit inside the (physical or virtual) memory of standard, or even high-end, workstations. It presents an investigation into out-of-core processing options and cloud solutions, while looking in particular for combinations of both. As a result, an octree-based datastructure is proposed. It is implemented in an already available key–value data store system. This solution has the advantage that existing in-core software can be quite easily converted into an out-of-core version. The resulting programs can still be executed on standard workstations with reasonable performance, while the expectation is that they can also be implemented in high-performance distributed multi-processor environments.
Sunshine to Rainstorm: Cross-Weather Knowledge Distillation for Robust 3D Object Detection
2024, Proceedings of the AAAI Conference on Artificial Intelligence

View all citing articles on Scopus

View full text

Distance transformations in digital images

Comput. Vision, Graphics Image Process.

Pattern Recognit.

Comput. Graphics Image Process.

Sequential operations in digital picture processing

J. Assoc. Comput. Mach.

Chamfering: A fast method for obtaining approximations of the Euclidean distance in N dimensions

A method for obtaining skeletons using a quasi-Euclidean distance

J. Assoc. Comput. Mach.