やさしいハフ(Hough)変換講座 ref: http://qiita.com/YSRKEN/items/ee94c7c22599c2374722

hough.java

/* Hough変換のサンプル
 * Hough変換した際は、
 * 直線→横×縦が角度分割数×(2 * 対角線長)に対応する
 * (ここで対角線長を2倍しているのは負数を想定している)
 * 円→横×縦が横×縦×半径に対応する
 */

/* 引数の1つ目が「put」だったなら、counter*.pngを出力する */

import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.ArrayList;
import javax.imageio.ImageIO;

public class hough{
    // 定数
    static final int kAngleSplits = 1024;   //0～πをこの数だけ分割する
    static final int kMinCount = 100;       //カウントがこの数未満なら無視する
    static final int kMaxCircleR = 100; //円がこれ以上の大きさなら無視する
    static final double kTableConst = Math.PI / kAngleSplits;   //計算用定数
    static final double kDegRad = 180 / Math.PI;    //変換用定数
    // 変数
    static int w, h, diagonal, d2;
    static ArrayList<Double> sin_table, cos_table;
    static ArrayList<Integer> dgl_table;
    // main関数
    public static void main(String args[]){
        boolean save_flg = false;
        if(args.length > 0 && args[0].equals("put")) save_flg = true;
        // 画像を読み込み
        BufferedImage load_image;
        try{
            load_image = ImageIO.read(new File("sample.png"));
        }
        catch(Exception error){
            error.printStackTrace();
            return;
        }
        w = load_image.getWidth();
        h = load_image.getHeight();
        System.out.println("画像サイズ：" + w + "x" + h);
        long start = System.nanoTime();
        // 書き込み用画像を用意する
        BufferedImage save_image = new BufferedImage(w, h, BufferedImage.TYPE_INT_BGR);
        Graphics2D g2d = (Graphics2D)save_image.getGraphics();
        g2d.drawImage(load_image, 0, 0, null);
        // 二値化
        ArrayList<Integer> binary_image = toBinaryImage(load_image);
        // 数値計算用のテーブルを事前に用意する
        sin_table = new ArrayList<Double>(kAngleSplits);
        cos_table = new ArrayList<Double>(kAngleSplits);
        for(int t = 0; t < kAngleSplits; t++){
            sin_table.add(Math.sin(kTableConst * t));
            cos_table.add(Math.cos(kTableConst * t));
        }
        dgl_table = new ArrayList<Integer>(w * h);
        for(int y = 0; y < h; y++){
            for(int x = 0; x < w; x++){
                dgl_table.add((int)(Math.sqrt(x * x + y * y) + 0.5));
            }
        }
        // 直線を検出する
        ArrayList<Tuple2> line_list = calcHoughLine(binary_image, save_flg);
        drawHoughLine(save_image, line_list);
        // 円を検出する
        ArrayList<Tuple3> circle_list = calcHoughCircle(binary_image, save_flg);
        drawHoughCircle(save_image, circle_list);
        // 結果を書き出し
        long stop = System.nanoTime();
        System.out.println((stop - start) / 1000 / 1000 + "ms");
        try{
            ImageIO.write(save_image, "png", new File("result.png"));
        }
        catch(Exception error){
            error.printStackTrace();
            return;
        }
    }
    // 画像を二値化して返す
    private static ArrayList<Integer> toBinaryImage(BufferedImage src_image){
        ArrayList<Integer> dst_image = new ArrayList<Integer>(w * h);
        for(int y = 0; y < h; y++){
            for(int x = 0; x < w; x++){
                int color = src_image.getRGB(x, y);
                int r = (color & 0xff0000) >> 16;
                int g = (color & 0xff00) >> 8;
                int b = color & 0xff;
                double Y = 0.299 * r + 0.587 * g + 0.114 * b;   //YCbCr
                if(Y > 127.5)
                    dst_image.add(0);
                else
                    dst_image.add(1);
            }
        }
        return dst_image;
    }
    // 画像をHough変換する(直線偏)
    private static ArrayList<Integer> getHoughLine(ArrayList<Integer> src_image){
        diagonal = (int)Math.sqrt(w * w + h * h);
        d2 = diagonal * 2;
        ArrayList<Integer> dst_image = new ArrayList<Integer>(kAngleSplits * d2);
        for(int r = 0; r < d2; r++){
            for(int t = 0; t < kAngleSplits; t++){
                dst_image.add(0);
            }
        }
        // 座標変換を行い、結果に加算しておく
        for(int y = 0; y < h; y++){
            for(int x = 0; x < w; x++){
                if(src_image.get(y * w + x) == 0) continue;
                for(int t = 0; t < kAngleSplits; t++){
                    int r = (int)(x * cos_table.get(t) + y * sin_table.get(t) + 0.5);
                    int p = (r + diagonal) * kAngleSplits + t;
                    dst_image.set(p, dst_image.get(p) + 1);
                }
            }
        }
        return dst_image;
    }
    // 直線を検出する
    private static ArrayList<Tuple2> calcHoughLine(ArrayList<Integer> src_image, boolean save_flg){
        ArrayList<Integer> counter = getHoughLine(src_image);
        // カウントを画像化する
        int max_count = 0;
        if(save_flg){
            BufferedImage counter_image = new BufferedImage(kAngleSplits, d2, BufferedImage.TYPE_INT_BGR);
            for(int r = 0; r < d2; r++){
                for(int t = 0; t < kAngleSplits; t++){
                    int cnt = counter.get(r * kAngleSplits + t);
                    if(max_count < cnt) max_count = cnt;
                }
            }
            for(int r = 0; r < d2; r++){
                for(int t = 0; t < kAngleSplits; t++){
                    int cnt = counter.get(r * kAngleSplits + t);
                    int color = (int)(255.0 * cnt / max_count);
                    counter_image.setRGB(t, r, color * 0x010101);
                }
            }
            try{
                ImageIO.write(counter_image, "png", new File("counter.png"));
            }
            catch(Exception error){
                error.printStackTrace();
                return null;
            }
        }
        // 最もカウントが多いものから、直線として表示する
        ArrayList<Tuple2> result = new ArrayList<Tuple2>();
        System.out.println("直線の検出結果：");
        while(true){
            // 最もカウントが多いものを検索する
            max_count = 0;
            int t_max = 0, r_max = 0;
            for(int r = 0; r < d2; r++){
                for(int t = 0; t < kAngleSplits; t++){
                    int cnt = counter.get(r * kAngleSplits + t);
                    if(max_count < cnt){
                        max_count = cnt;
                        t_max = t;
                        r_max = r;
                    }
                }
            }
            if(max_count < kMinCount) break;
            result.add(new Tuple2<Integer, Integer>(t_max, r_max));
            System.out.println("　カウント：" + max_count + " 角度：" + (t_max * kTableConst * kDegRad) + " 距離：" + (r_max - diagonal));
            // 類似した周辺のカウントを消去する
            for(int r = -10; r <= 10; r++){
                for(int t = -30; t <= 30; t++){
                    int t2 = t_max + t, r2 = r_max + r;
                    if(t2 < 0){
                        t2 += kAngleSplits;
                        r2 = -r2;
                    }
                    if(t2 >= kAngleSplits){
                        t2 -= kAngleSplits;
                        r2 = -r2;
                    }
                    if(r2 < 0 || r2 >= d2) continue;
                    counter.set(r2 * kAngleSplits + t2, 0);
                }
            }
        }
        return result;
    }
    // 直線を書き出す
    private static void drawHoughLine(BufferedImage image, ArrayList<Tuple2> list){
        Graphics2D g2d = (Graphics2D)image.getGraphics();
        g2d.setColor(Color.BLUE);
        for(Tuple2<Integer, Integer> temp : list){
            int t = temp.t1, r = temp.t2 - diagonal;
            if(t != 0){
                for(int x = 0; x < w; x++){
                    int y = (int)((r - x * cos_table.get(t)) / sin_table.get(t));
                    if(y < 0 || y >= h) continue;
                    g2d.drawRect(x, y, 0, 0);
                }
            }
            if(t != kAngleSplits / 2){
                for(int y = 0; y < h; y++){
                    int x = (int)((r - y * sin_table.get(t)) / cos_table.get(t));
                    if(x < 0 || x >= w) continue;
                    g2d.drawRect(x, y, 0, 0);
                }
            }
        }
    }
    // 画像をHough変換する(円弧偏)
    private static ArrayList<Integer> getHoughCircle(ArrayList<Integer> src_image){
        ArrayList<Integer> dst_image = new ArrayList<Integer>(w * h * kMaxCircleR);
        for(int x = 0; x < w; x++){
            for(int y = 0; y < h; y++){
                for(int r = 0; r < kMaxCircleR; r++){
                    dst_image.add(0);
                }
            }
        }
        // 座標変換を行い、結果に加算しておく
        for(int y = 0; y < h; y++){
            for(int x = 0; x < w; x++){
                if(src_image.get(y * w + x) == 0) continue;
                for(int cy = Math.max(y - kMaxCircleR, 0); cy <= Math.min(y + kMaxCircleR, h - 1); cy++){
                    int dy = Math.abs(cy - y);
                    for(int cx = Math.max(x - kMaxCircleR, 0); cx <= Math.min(x + kMaxCircleR, w - 1); cx++){
                        int dx = Math.abs(cx - x);
                        int r = dgl_table.get(dy * w + dx);
                        if(r >= kMaxCircleR) continue;
                        int p = (cy * w + cx) * kMaxCircleR + r;
                        dst_image.set(p, dst_image.get(p) + 1);
                    }
                }
            }
        }
        return dst_image;
    }
    // 円を検出する
    private static ArrayList<Tuple3> calcHoughCircle(ArrayList<Integer> src_image, boolean save_flg){
        ArrayList<Integer> counter = getHoughCircle(src_image);
        // カウントを画像化する
        int max_count = 0;
        if(save_flg){
            BufferedImage counter_image_c = new BufferedImage(w, h, BufferedImage.TYPE_INT_BGR);
            BufferedImage counter_image_r = new BufferedImage(w, h, BufferedImage.TYPE_INT_BGR);
            for(int y = 0; y < h; y++){
                for(int x = 0; x < w; x++){
                    for(int r = 0; r < kMaxCircleR; r++){
                        int cnt = counter.get((y * w + x) * kMaxCircleR + r);
                        if(max_count < cnt) max_count = cnt;
                    }
                }
            }
            for(int y = 0; y < h; y++){
                for(int x = 0; x < w; x++){
                    int max_count_2 = 0, max_r = 0;
                    for(int r = 0; r < kMaxCircleR; r++){
                        int cnt = counter.get((y * w + x) * kMaxCircleR + r);
                        if(max_count_2 < cnt){
                            max_count_2 = cnt;
                            max_r = r;
                        }
                    }
                    counter_image_c.setRGB(x, y, 0x010101 * (int)(0xff * max_count_2 / max_count));
                    counter_image_r.setRGB(x, y, 0x010101 * (int)(0xff * max_r / kMaxCircleR));
                }
            }
            try{
                ImageIO.write(counter_image_c, "png", new File("counter2_c.png"));
                ImageIO.write(counter_image_r, "png", new File("counter2_r.png"));
            }
            catch(Exception error){
                error.printStackTrace();
                return null;
            }
        }
        // 最もカウントが多いものから、円として表示する
        ArrayList<Tuple3> result = new ArrayList<Tuple3>();
        System.out.println("円の検出結果：");
        while(true){
            // 最もカウントが多いものを検索する
            max_count = 0;
            int x_max = 0, y_max = 0, r_max = 0;
            for(int y = 0; y < h; y++){
                for(int x = 0; x < w; x++){
                    for(int r = 0; r < kMaxCircleR; r++){
                        int cnt = counter.get((y * w + x) * kMaxCircleR + r);
                        if(max_count < cnt){
                            max_count = cnt;
                            x_max = x;
                            y_max = y;
                            r_max = r;
                        }
                    }
                }
            }
            if(max_count < kMinCount) break;
            Tuple3 t3 = new Tuple3<Integer, Integer, Integer>(x_max, y_max, r_max);
            result.add(t3);
            System.out.println("　カウント：" + max_count + " 中心：(" + x_max + "," + y_max + ") 半径：" + r_max);
            // 類似した周辺のカウントを消去する
            for(int y = -5; y <= 5; y++){
                int y2 = y_max + y;
                if(y2 < 0 || y2 >= h) continue;
                for(int x = -5; x <= 5; x++){
                    int x2 = x_max + x;
                    if(x2 < 0 || x2 >= w) continue;
                    for(int r = -5; r <= 5; r++){
                        int r2 = r_max + r;
                        if(r2 < 0) continue;
                        counter.set((y2 * w + x2) * kMaxCircleR + r2, 0);
                    }
                }
            }
        }
        return result;
    }
    // 円を書き出す
    private static void drawHoughCircle(BufferedImage image, ArrayList<Tuple3> list){
        Graphics2D g2d = (Graphics2D)image.getGraphics();
        g2d.setColor(Color.RED);
        for(Tuple3<Integer, Integer, Integer> temp : list){
            int x = temp.t1, y = temp.t2, r = temp.t3;
            g2d.drawOval(x - r, y - r, r * 2, r * 2);
        }
    }
}

// タプル
class Tuple2<T1, T2>{
    public T1 t1;
    public T2 t2;
    public Tuple2(){}
    public Tuple2(T1 t1, T2 t2){
        this.t1 = t1;
        this.t2 = t2;
    }
}
class Tuple3<T1, T2, T3>{
    public T1 t1;
    public T2 t2;
    public T3 t3;
    public Tuple3(){}
    public Tuple3(T1 t1, T2 t2, T3 t3){
        this.t1 = t1;
        this.t2 = t2;
        this.t3 = t3;
    }
}