图像处理之基于采样距离变换算法

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;
  }
  
}