Java代码怎么实现图像采样距离变换算法

Question

如题所述

Answer 1

算法是别人提出来的，感兴趣可以搜索《Distance Transforms of Sampled Functions》这篇论文，网上也有很多实现的代码，但是结构不是很好，而且很分散不是一个完整的算法。所以我整理了一下，写成一个单独的类，只要简单调用一下即可出结果图片。至于算法原理什么的，我真很难解释清楚，大致的思想是基于能量最小化的，分别进行行与列的1D距离变变换采样。

package com.gloomyfish.image.transform;    
    
import java.awt.image.BufferedImage;    
    
import com.gloomyfish.filter.study.GrayFilter;    
/**   
 *    
 * @author gloomyfish   
 *   
 */    
public class FastDistanceTransformAlg extends GrayFilter {    
    public final static double INF = 1E20;    
    private int backgroundColor = 0; // default black    
    
    public int getBackgroundColor() {    
        return backgroundColor;    
    }    
    
    public void setBackgroundColor(int backgroundColor) {    
        this.backgroundColor = backgroundColor;    
    }    
    
    @Override    
    public BufferedImage filter(BufferedImage src, BufferedImage dest) {    
        int width = src.getWidth();    
        int height = src.getHeight();    
        dest = super.filter(src, null);    
            
        //    
        int[] inPixels = new int[width*height];    
        float[] outPixels = new float[width*height];    
        getRGB( dest, 0, 0, width, height, inPixels );    
        int index = 0;    
        for(int row=0; row<height; row++) {    
            int tr = 0;    
            for(int col=0; col<width; col++) {    
                index = row * width + col;    
                tr = (inPixels[index] >> 16) & 0xff;    
                if(tr == backgroundColor)    
                    outPixels[index] = (float)INF;    
                else    
                    outPixels[index] = 0;                       
            }    
        }    
            
        // transform along columns    
        float[] f = new float[Math.max(width, height)];    
        for(int col=0; col<width; col++) {    
            for(int row=0; row<height; row++) {    
                index = row * width + col;    
                f[row] = outPixels[index];    
            }    
            float[] disColumns = distance1DTransform(f, height);                
            for(int row=0; row<height; row++) {    
                index = row * width + col;    
                outPixels[index] = disColumns[row];    
            }    
        }    
            
        // transform along rows    
        for (int row = 0; row < height; row++) {    
          for (int col = 0; col < width; col++) {    
            index = row * width + col;    
            f[col] = outPixels[index];    
          }    
          float[] disColumns = distance1DTransform(f, width);          
          for (int col = 0; col < width; col++) {    
            index = row * width + col;    
            outPixels[index] = disColumns[col];    
          }    
        }    
            
        // post sqrt calculation    
        int[] result = new int[width*height];    
        for(int row=0; row<height; row++) {    
            for(int col=0; col<width; col++) {    
                index = row * width + col;    
                int pc = clamp(Math.sqrt(outPixels[index]));    
                result[index] = (255 << 24) | (pc << 16) | (pc << 8) | pc;    
            }    
        }    
        setRGB( dest, 0, 0, width, height, result );    
        return dest;    
    }    
        
    public static int clamp(double c)    
    {    
        return c > 255 ? 255 : (c < 0 ? 0 : (int)c);    
    }    
        
    /**   
     * 1D distance transform using squared distance   
     *    
     * @param data   
     * @param n   
     * @return   
     */    
    private float[] distance1DTransform(float[] f, int n)    
    {    
          float[] d = new float[n];    
          int[] v = new int[n];    
          double[] z = new double[n+1];    
          int k = 0;    
          v[0] = 0;    
          z[0] = -INF;    
          z[1] = +INF;    
          for (int q = 1; q <= n-1; q++) {    
            double s  = ((f[q]+square(q))-(f[v[k]]+square(v[k])))/(2*q-2*v[k]);    
            while (s <= z[k]) {    
              k--;    
              s  = ((f[q]+square(q))-(f[v[k]]+square(v[k])))/(2*q-2*v[k]);    
            }    
            k++;    
            v[k] = q;    
            z[k] = s;    
            z[k+1] = +INF;    
          }    
    
          k = 0;    
          for (int q = 0; q <= n-1; q++) {    
            while (z[k+1] < q)    
              k++;    
            d[q] = (float)square(q-v[k]) + f[v[k]];    
          }    
          return d;    
    }    
        
    private double square(double v)    
    {    
        return v*v;    
    }    
        
}