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-2016 Wilhelm Burger, Mark J. Burge. All rights reserved. 
007 * Visit http://imagingbook.com for additional details.
008 *******************************************************************************/
009package imagingbook.pub.matching;
010
011import ij.process.ImageProcessor;
012
013/**
014 * Objects of this class calculate an approximate distance transform of a given
015 * image which is assumed to be binary (pixel value 0 = background, foreground otherwise).
016 * 
017 * @author W. Burger
018 * @version 2014-04-20
019 */
020public class DistanceTransform {
021        
022        public enum Norm {L1, L2}
023        private final float[][] D;
024        
025        // default constructor (using L2 norm)
026        public DistanceTransform(ImageProcessor I) {
027                 this(I, Norm.L2);
028        }
029        
030        // alternate constructor (L1 or L2 norm)
031        public DistanceTransform(ImageProcessor I, Norm norm) {
032                D = makeDistanceMap(I, norm);
033        }
034        
035        private float[][] makeDistanceMap(ImageProcessor I, Norm norm) {
036                float m1, m2;
037                switch (norm) {
038                case L1:
039                        m1 = 1; m2 = 2; break;
040                case L2:
041                        m1 = 1; m2 = (float) Math.sqrt(2); break;
042                default:
043                        throw new IllegalArgumentException();
044                }
045                
046                final int M = I.getWidth();
047                final int N = I.getHeight();
048                final float[][] D = new float[M][N];
049                float d0, d1, d2, d3;
050
051                // L->R pass:
052                for (int v = 0; v < N; v++) {
053                        for (int u = 0; u < M; u++) {
054                                D[u][v] = (I.get(u, v) > 0) ? 0 : Float.POSITIVE_INFINITY; // initialize
055                                if (D[u][v] > 0) {      // a background pixel
056                                        d0 = d1 = d2 = d3 = Float.POSITIVE_INFINITY;
057                                        if (u > 0) {
058                                                d0 = m1 + D[u - 1][v];
059                                                if (v > 0)      {
060                                                        d1 = m2 + D[u - 1][v - 1];
061                                                }
062                                        }
063                                        if (v > 0) {
064                                                d2 = m1 + D[u][v - 1];
065                                                if (u < M - 1) {
066                                                        d3 = m2 + D[u + 1][v - 1];
067                                                }
068                                        }
069                                        // at this point D[u][v] == POSITIVE_INFINITY
070                                        D[u][v] = min(d0, d1, d2, d3);  
071                                }
072                        }
073                }
074                
075                // R->L pass:
076                for (int v = N - 1; v >= 0; v--) {
077                        for (int u = M - 1; u >= 0; u--) {
078                                if (D[u][v] > 0) {      // a background pixel
079                                        d0 = d1 = d2 = d3 = Float.POSITIVE_INFINITY;
080                                        if (u < M - 1)  {
081                                                d0 = m1 + D[u + 1][v];
082                                                if (v < N - 1) {
083                                                        d1 = m2 + D[u + 1][v + 1];
084                                                }
085                                        }
086                                        if (v < N - 1) {
087                                                d2 = m1 + D[u][v + 1];
088                                                if (u > 0) {
089                                                        d3 = m2 + D[u - 1][v + 1];
090                                                }
091                                        }
092                                        D[u][v] = min(D[u][v], d0, d1, d2, d3);
093                                }
094                        }
095                }
096                return D;
097        }
098        
099        private float min(float... a) {
100                float minVal = a[0];
101                for (int i = 1; i < a.length; i++) {
102                        if (a[i] < minVal) 
103                                minVal = a[i];
104                }
105                return minVal;
106        }
107        
108        public float[][] getDistanceMap() {
109                return D;
110        }
111        
112
113}