Skip to content

Instantly share code, notes, and snippets.

@YSRKEN
Created October 24, 2015 14:34
Show Gist options
  • Save YSRKEN/2157d53f6c52cae47939 to your computer and use it in GitHub Desktop.
Save YSRKEN/2157d53f6c52cae47939 to your computer and use it in GitHub Desktop.
やさしいハフ(Hough)変換講座 ref: http://qiita.com/YSRKEN/items/ee94c7c22599c2374722
/* 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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment