001/*******************************************************************************
002 * This software is provided as a supplement to the authors' textbooks on digital
003 * image processing published by Springer-Verlag in various languages and editions.
004 * Permission to use and distribute this software is granted under the BSD 2-Clause
005 * "Simplified" License (see http://opensource.org/licenses/BSD-2-Clause).
006 * Copyright (c) 2006-2023 Wilhelm Burger, Mark J. Burge. All rights reserved.
007 * Visit https://imagingbook.com for additional details.
008 ******************************************************************************/
009package imagingbook.common.image.matching;
010
011import ij.process.ImageProcessor;
012
013/**
014 * <p>
015 * Instances of this class calculate an approximate distance transform of a given image which is assumed to be binary
016 * (pixel value 0 = background, non-zero = foreground). For the L2 norm, the resulting distances are only an
017 * approximation. See Sec. 23.2.2 (Alg. 23.2) of [1] for additional details.
018 * </p>
019 * <p>
020 * [1] W. Burger, M.J. Burge, <em>Digital Image Processing &ndash; An Algorithmic Introduction</em>, 3rd ed, Springer
021 * (2022).
022 * </p>
023 *
024 * @author WB
025 * @version 2022/09/16
026 */
027public class DistanceTransform {
028
029        /**
030         * Enum type for different distance norms used to calculate distance transforms.
031         *
032         * @see DistanceTransform
033         */
034        public enum DistanceType {
035                /** L1 distance (Manhattan distance) */ L1,
036                /** L2 distance (Euclidean distance) */ L2;
037        }
038        
039        private final float[][] D;
040        
041        /**
042         * Constructor using the default distance norm ({@link DistanceType#L2}).
043         * @param I the input image
044         */
045        public DistanceTransform(ImageProcessor I) {
046                 this(I, DistanceType.L2);
047        }
048        
049        /**
050         * Constructor using the specified distance norm.
051         * @param I the input image
052         * @param norm the distance norm
053         */
054        public DistanceTransform(ImageProcessor I, DistanceType norm) {
055                D = makeDistanceMap(I, norm);
056        }
057        
058        // -----------------------------------------------------------------
059        
060        private float[][] makeDistanceMap(ImageProcessor I, DistanceType norm) {
061                float m1, m2;
062                switch (norm) {
063                case L1:
064                        m1 = 1; m2 = 2; break;
065                case L2:
066                        m1 = 1; m2 = (float) Math.sqrt(2); break;
067                default:
068                        throw new IllegalArgumentException("unhandled norm " + norm);
069                }
070                
071                final int M = I.getWidth();
072                final int N = I.getHeight();
073                final float[][] D = new float[M][N];
074                float d0, d1, d2, d3;
075
076                // L->R pass:
077                for (int v = 0; v < N; v++) {
078                        for (int u = 0; u < M; u++) {
079                                if (I.get(u, v) != 0) {         // a foreground pixel
080                                        D[u][v] = 0;
081                                }
082                                else {                                          // a background pixel
083                                        d0 = d1 = d2 = d3 = Float.POSITIVE_INFINITY;
084                                        if (u > 0) {
085                                                d0 = m1 + D[u - 1][v];
086                                                if (v > 0)      {
087                                                        d1 = m2 + D[u - 1][v - 1];
088                                                }
089                                        }
090                                        if (v > 0) {
091                                                d2 = m1 + D[u][v - 1];
092                                                if (u < M - 1) {
093                                                        d3 = m2 + D[u + 1][v - 1];
094                                                }
095                                        }
096                                        D[u][v] = min(d0, d1, d2, d3);  
097                                }
098                        }
099                }
100                
101                // R->L pass:
102                for (int v = N - 1; v >= 0; v--) {
103                        for (int u = M - 1; u >= 0; u--) {
104                                if (D[u][v] > 0) {      // a background pixel
105                                        d0 = d1 = d2 = d3 = Float.POSITIVE_INFINITY;
106                                        if (u < M - 1)  {
107                                                d0 = m1 + D[u + 1][v];
108                                                if (v < N - 1) {
109                                                        d1 = m2 + D[u + 1][v + 1];
110                                                }
111                                        }
112                                        if (v < N - 1) {
113                                                d2 = m1 + D[u][v + 1];
114                                                if (u > 0) {
115                                                        d3 = m2 + D[u - 1][v + 1];
116                                                }
117                                        }
118                                        D[u][v] = min(D[u][v], d0, d1, d2, d3);
119                                }
120                        }
121                }
122                return D;
123        }
124        
125        private float min(float... a) {
126                float minVal = a[0];
127                for (int i = 1; i < a.length; i++) {
128                        if (a[i] < minVal) 
129                                minVal = a[i];
130                }
131                return minVal;
132        }
133
134        /**
135         * Returns the distance map as a 2D float array with the same size as the original image.
136         *
137         * @return the 2D distance map.
138         */
139        public float[][] getDistanceMap() {
140                return D;
141        }
142
143}