はじめに
Hough変換は、画像から直線や円を検出する技法として知られています。通常の直交座標上の画像を、極座標の二次元空間（直線検出の場合）に変換したり、三次元の空間（円検出の場合）に変換したりして、そこで最も頻度の高い位置を求め、それを逆変換して、直線や円を検出します。
Hough変換は数学的に興味深く、プログラムの対象として面白いため、多くの論文が見られますが、実用化には多くの問題点もあります。
ここでは最初に、一般的なHough変換の基本プログラムを紹介し、次に交通標識認識への応用に特化したプログラムについて述べます。
対象読者
画像から直線や円を検出する方法に興味を持ち、その一つであるHough変換の仕組みを学びたい人。
必要な環境
J2SE 5.0を使っていますが、J2SE 1.4.2でも大丈夫です。円のためのHough変換にはかなりの時間がかかりますので、CPUパワーの大きいことが望まれます。添付のアプレットを実行する場合、CPUにより数分かかることがあります。あらかじめご承知置きください。
Hough変換とは
Hough変換は、1962年にP.V.C.Houghによって米国特許が取られている古い技法で、直線の検出や円の検出に用いられます。直線の検出の場合、元になる直角座標上の点（x, y）を角度θと距離ρの極座標二次元空間に変換し、角度θと距離ρごとに、その個数をメモリ配列上に加算して行きます（Accumulator CellやVoting Cellなどと呼ばれることがあります）。個数が最大になった組み合わせ（角度θと距離ρの）を元の直角座標に戻したものが、最も直線らしい点の集まりとなります。個数を下げてゆくと、次の候補が順次得られます。角度θと距離ρを細かく分けると、精度が上がりますが、計算時間が長くなり、必要なメモリ容量も増えるのが欠点です。円の検出の場合には、元になる直角座標上の点（x, y）を、円の中心点（centerX, centerY）と半径radiusの三次元空間に変換し、同様の処理を行います。
Hough変換の問題点と解決方法
計算時間が長いこと、大きなメモリ容量が必要なことは、最近の環境では、あまり支障がなくなっています。しかし、次のような根本的な問題があります。
- ノイズが邪魔になる
- 誤差があるので、線幅の狭い直線や円は検出されにくい
- 一本の直線、一個の円を複数個に認識してしまう
直線の検出
図1の左上に示すように、直角座標上の点（x, ｙ）を通るすべての直線は、その直線と直角に交わる垂線のｘ軸との角度theta（θ）と長さrho（ρ）で表わされます。（x, ｙ）をθとρの組み合わせに変換することをHough変換（直線を求めるための）といいます。
Hough変換は、角度θを変化させながら、
ρ = x・cosθ + y・sinθ
によりρを求めます。上の式を用いて、直角座標上の点（x, ｙ）を新しい二次元空間（θ, ρ）上に変換すると、直角座標上の一点はθ-ρ空間上の一本の曲線に対応します。直角座標上の点が多数あると、θ-ρ空間上に多数の曲線が得られます。θ-ρ空間上でこれらの曲線が共有する点があれば、それは元のx-y直角座標上では一本の線上に並ぶことになります。図1の右上は、Hough変換の式を説明したものです。
角度θは、0からπラジアンまで変化させます。θがπ/2を超えると、ρはマイナスの値をとることがあります。これを説明したのが、図1の下方の図です。変換式は、そのまま使えます。
Hough逆変換は、
y = -(cosθ/sinθ)・x + ρ/sinθ
および
x = -(sinθ/cosθ)・y + ρ/cosθ
により、xとyを変化して直線を描きます。前者は、水平に近い直線の描画に適し、後者は、垂直に近い直線の描画に適していますが、一般には、両者を併用します。
円の検出
図2に示すように、直交座標上の点（x, y）を通るすべての円は、円の中心点（centerX, centerY）と半径（radius）で表わされます。（x, y）を、centerX、centerY、radiusの組み合わせに変換することもHough変換（円を求めるための）といいます。
Hough変換は、centerXとcenterYを変化させながら、
radius2 = (x - centerX)2 + (y - centerY)2
の関係によりradiusを求めます。
上の式を用いて、直角座標上の点（x, y）を新しい三次元空間（centerX, centerY, radius）上に変換すると、直角座標上の一点は三次元空間上の1枚の面に対応します。直角座標上の点が多数あると、空間上に多数の曲面が得られます。それらの曲面が共有する点があれば、それは元のx-y直角座標上では一個の円上に並ぶことになります。
円検出のためのHough変換は、画面上のすべての点（x, ｙ）をスキャンしながら、さらにcenterXとcenterYをスキャンさせて二乗や平方根を求めますので、非常に時間が掛かる処理です。そのため、ここで紹介するプログラムでは、高速化のために、distXとdistYから、あらかじめ計算したテーブルを用いてradiusを求めています。ただし、distXはx-centerXの絶対値、distYはy-centerYの絶対値です。
Hough逆変換は、数式を用いるまでもなく、点（centerX, centerY）を中心に半径radiusの円を描きます。
Hough変換基本プログラムの概要
使用する画像のサイズは、X（横）方向がXMAX=320、Y（縦）方向がYMAX=240とします。これらは変更可能です。
この条件では、対角線の長さが400になりますので、Hough変換後のρ（直線の場合）の最大値RHO_MAXは400にしてあります。また、処理を高速化するため、radius（円の場合）の最大値RMAXは60（YMAXの1/4、直径ではYMAXの1/2）に制限してあります。
θは、πラジアンを1024に分割することにし、THETA_MAX=1024とします。
プログラムは、次のステップから成ります。
- 高速化のために、あらかじめ三角関数と半径
radius算出のテーブル（数表）を計算して用意します。 - 黒でエッジを示す原画像を読み込み、パソコン画面上の左に表示します。原画像を二次元配列
data[y][x]にした結果は、Hough変換後に右に表示します。
直線の検出
- 角度
theta（添字は「0～THETA_MAX-1」）と距離rho（「-RHO_MAX～RHO_MAX-1」の値をとりますが添字にマイナスは使えないので、RHO_MAXを加算して添字は「0～2*RHO_MAX-1」）の頻度を蓄積するためのカウンタとして、counter[THETA_MAX][2*RHO_MAX]のメモリ領域を確保します。 - 直角座標上の点（
x,y）を新しい二次元空間（θ,ρ）にHough変換しながら、counter[theta][rho]に頻度を累積します。 counter[theta][rho]の内容が最大になるtheta_maxとrho_maxを求めます。theta_maxとrho_maxを、直角座標上にHough逆変換して（xを変えながらyを描きます。垂直の線は描けないので、事前に判定します）、パソコン右上の画面上に赤色で直線を描画します。theta_maxとrho_maxを、直角座標上にHough逆変換して（yを変えながらxを描きます。水平の線は描けないので、事前に判定します）、6.と同様に描画します。theta_maxとrho_maxの近傍のcounter[theta][rho]をゼロにし、次の最大候補から除外します。- 上記の5.から8.を繰り返します。繰り返しは、
counterの値（直線を構成するピクセルの数）が一定以下になるか、一定個の直線が検出されれば止めます。
円の検出
- 円の中心点（X座標は
centerX、Y座標はcenterYを用い、それぞれ添字は「0～XMAX-1」と「0～YMAX-1」）と半径radius（添字は「0～RMAX-1」）の頻度を蓄積するためのカウンタとして、counter1[XMAX][YMAX][RMAX]のメモリ領域を確保します。 - 直角座標上の点（
x,y）に対して、円を構成する条件となるcenterX、centerY、radiusの組み合わせを求めるHough変換を行い、三次元配列counter1[centerY][centerX][radius]に頻度を累積します。これは非常に時間がかかる処理ですが、テーブルの利用と、半径radiusの制限で高速化を図っています。 counter1[centerY][centerX][radius]の内容が最大になるcenterX_max、centerY_max、radius_maxを求めます。centerX_max、centerY_max、radius_maxの近傍のcounter1[centerY][centerX][radius]をゼロにし、次の最大候補から除外します。centerX_max、centerY_max、radius_maxを用いて、パソコン右上の画面上に青色で円を描画します（Hough逆変換に相当します。）。- 上記の5.から6.を繰り返します。繰り返しは、
counter1の値（円を構成するピクセルの数）が一定以下になるか、一定個の円が検出されれば止めます。
Hough変換基本プログラム
import java.awt.*; import java.awt.image.*; import javax.swing.*; public class Hough extends JApplet{ static final int XMAX=320; static final int YMAX=240; static final int RMAX=60; static final int THETA_MAX=1024; static final int RHO_MAX=400; static final float PIK=(float)Math.PI/THETA_MAX; //三角関数テーブル（サイン） float[] sn=new float[THETA_MAX]; //三角関数テーブル（コサイン） float[] cs=new float[THETA_MAX]; //半径計算用斜線長テーブル short[][] diagonal=new short[YMAX][XMAX]; //二次元化した二値原画像データを格納 byte[][] data=new byte[YMAX][XMAX]; Image img_src; public void init(){ //三角関数テーブルを作成 for(int i=0;i<THETA_MAX;i++){ sn[i]=(float)Math.sin(PIK*i); cs[i]=(float)Math.cos(PIK*i); } //斜線長テーブルを作成 for(int y=0;y<YMAX;y++) for(int x=0;x<XMAX;x++) diagonal[y][x]=(short)(Math.sqrt(y*y+x*x)+0.5); //画像ファイルを読み込み、Image画像img_srcにする img_src=readImageFile("sample.gif"); //img_src画像を二次元配列data[y][x]に変換する changeTo2DDataArray(img_src,data); } //画像ファイルを読み込みImageクラスの画像にするメソッド public Image readImageFile(String filename){ Image img=getImage(getDocumentBase(),filename); MediaTracker mtracker=new MediaTracker(this); mtracker.addImage(img,0); try{ mtracker.waitForAll(); }catch(Exception e){} return img; } //Image画像の黒色のみを二次元配列data[][]に変換するメソッド public void changeTo2DDataArray(Image img, byte[][] _data){ int width=img.getWidth(this); int height=img.getHeight(this); int size=width*height; int[] rgb=new int[size]; Color color; int r,g,b; //img画像の一次元RGB配列を得る PixelGrabber grabber= new PixelGrabber(img,0,0,width,height,rgb,0,width); try{ grabber.grabPixels(); }catch(InterruptedException e){} for(int i=0;i<size;i++){ color=new Color(rgb[i]); r=color.getRed(); g=color.getGreen(); b=color.getBlue(); if(r+g+b==0) _data[i/width][i % width]=1; //黒 else _data[i/width][i % width]=0; //白 } } public void paint(Graphics g){ //画像を描画する位置の設定 int X0=10,Y0=10,X1=340,Y1=260; int x,y; //原画像img_srcを左に描画する g.drawImage(img_src,X0,Y0,this); // ---------------------- Hough変換 -------------------------- //直線の場合 ------------------------------------------------- int theta,rho; //直線検出用頻度カウンタ short[][] counter=new short[THETA_MAX][2*RHO_MAX]; for(y=0;y<YMAX;y++) for(x=0;x<XMAX;x++) if(data[y][x]==1){ for(theta=0;theta<THETA_MAX;theta++){ rho=(int)(x*cs[theta]+y*sn[theta]+0.5); counter[theta][rho+RHO_MAX]++; } } //円の場合 --------------------------------------------------- int centerX,centerY,distX,distY,radius; //円検出用頻度カウンタ short[][][] counter1=new short[YMAX][XMAX][RMAX]; for(y=0;y<YMAX;y++) for(x=0;x<XMAX;x++) if(data[y][x]==1){ for(centerY=0;centerY<YMAX;centerY++){ distY=Math.abs(y-centerY); if(distY>RMAX) continue; for(centerX=0;centerX<XMAX;centerX++){ distX=Math.abs(x-centerX); radius=diagonal[distY][distX]; if(radius>=RMAX) continue; counter1[centerY][centerX][radius]++; } } } // --------------------- Hough逆変換 ------------------------- int end_flag; //繰り返しを終了させるフラグ int count; //検出された直線または円の個数カウンタ //画像データdata[y][x]を右に描画する for(y=0;y<YMAX;y++) for(x=0;x<XMAX;x++) if(data[y][x]==1) g.drawRect(X1+x,Y0+y,0,0); //直線の場合 ------------------------------------------------- int counter_max; int theta_max=0; int rho_max=-RHO_MAX; g.setColor(Color.red); end_flag=0; count=0; do{ count++; counter_max=0; //counterが最大になるtheta_maxとrho_maxを求める for(theta=0;theta<THETA_MAX;theta++) for(rho=-RHO_MAX;rho<RHO_MAX;rho++) if(counter[theta][rho+RHO_MAX]>counter_max){ counter_max=counter[theta][rho+RHO_MAX]; //60ピクセル以下の直線になれば検出を終了 if(counter_max<=60) end_flag=1; else end_flag=0; theta_max=theta; rho_max=rho; } //検出した直線の描画 //xを変化させてyを描く（垂直の線を除く） if(theta_max!=0){ for(x=0;x<XMAX;x++){ y=(int)((rho_max-x*cs[theta_max])/sn[theta_max]); if(y>=YMAX || y<0) continue; g.drawRect(X1+x,Y0+y,0,0); } } //yを変化させてxを描く（水平の線を除く） if(theta_max!=THETA_MAX/2){ for(y=0;y<YMAX;y++){ x=(int)((rho_max-y*sn[theta_max])/cs[theta_max]); if(x>=XMAX || x<0) continue; g.drawRect(X1+x,Y0+y,0,0); } } //近傍の直線を消す for(int j=-10;j<=10;j++) for(int i=-30;i<=30;i++){ if(theta_max+i<0){ theta_max+=THETA_MAX; rho_max=-rho_max; } if(theta_max+i>=THETA_MAX){ theta_max-=THETA_MAX; rho_max=-rho_max; } if(rho_max+j<-RHO_MAX || rho_max+j>=RHO_MAX) continue; counter[theta_max+i][rho_max+RHO_MAX+j]=0; } //長さが60ピクセル以下か、直線が10本検出されたら終了 }while(end_flag==0 && count<10); //円の場合 --------------------------------------------------- int counter1_max; int centerX_max=0; int centerY_max=0; int radius_max=0; g.setColor(Color.blue); end_flag=0; count=0; do{ count++; counter1_max=0; //counter1が最大になるcenterX_max、 //centerY_maxとradius_maxを求める for(centerY=0;centerY<YMAX;centerY++) for(centerX=0;centerX<XMAX;centerX++) for(radius=0;radius<RMAX;radius++) if(counter1[centerY][centerX][radius]>counter1_max){ counter1_max=counter1[centerY][centerX][radius]; //100ピクセル以下の円になれば検出を終了 if(counter1_max<=100) end_flag=1; else end_flag=0; centerY_max=centerY; centerX_max=centerX; radius_max=radius; } //近傍の円を消す for(int k=-5;k<=5;k++){ if(centerY_max+k>=YMAX || centerY_max+k<0) continue; for(int j=-5;j<=5;j++){ if(centerX_max+j>=XMAX || centerX_max+j<0) continue; for(int i=-5;i<=5;i++){ //if(radius_max+i>=RMAX || radius_max+i<0) continue; if(radius_max+i<0) continue; counter1[centerY_max+k] [centerX_max+j][radius_max+i]=0; } } } //検出した円の描画 g.drawOval(X1+centerX_max-radius_max, Y0+centerY_max-radius_max,radius_max*2,radius_max*2); //大きさが100ピクセル以下か、円が5個検出されたら終了 }while(end_flag==0 && count<5); } }
Hough変換基本プログラムで得られた画面
図3で、左は原画像、右は原画像の上に、Hough変換による検出結果を表示したものです。直線と見なすピクセルの集まりの数（ここでは60個と設定）をさらに減らして行くと、偽の直線が出てきます。
交通標識認識へのHough変換の応用
Hough変換の実用的な応用は、あまり見当たりません。筆者は、「止まれ」「進入禁止」などの交通標識の認識がHough変換で可能ではないか、と考えています。これらは、ドライバにとって見過ごしてはならない標識です。ただし、人命にかかわるような応用に用いるのは慎重を要します。
「止まれ」の標識の認識方法
「止まれ」の標識は、上部が広がった正三角形で、赤地に「止まれ」の文字が白抜きで書かれています。原画像から「赤色」を抜き出し、エッジ検出処理をすると、正三角形の図形が得られます。
Hough変換では、正三角形を構成する三本の線のうち、水平の線はθがπ/2、右上がりの線はθがπ/6、右下がりの線はθがπ*(5/6)に変換されますので、これらのθの近傍のみに限定してHough変換すると、これ以外の線は、無視されます。
これら三本の線が揃った場合は、「止まれ」の標識が認識されたとして、ビープ音を出します。上下が逆の場合も三本の線が揃いますが、それとの区別は行っていません。
「進入禁止」の標識の認識方法
「進入禁止」の標識は、円形の赤地の中央部に、横長の白い長方形があります。原画像から「赤色」を抜き出し、エッジ検出処理をすると、円形の中央に横長の長方形がある図形が得られます。
Hough変換では、まず円を検出します。これは、一般的な円の検出と同じです。一方、水平の直線の検出も行い、Hough変換結果のρの値（すなわち、水平の直線の場合は、検出された直線のy座標に相当します。）と円のcenterYとを比較します。centerYの上下に、それぞれ一定の範囲内に水平の線がある場合には、これを「進入禁止」の標識と認識して、ビープ音を出します。
交通標識認識のための変更点
要点のみを以下に示します。詳細は、添付の「Hough1.java」を参照して下さい。
「止まれ」認識用に変更した部分
特定の角度の直線のみをHough変換します。Hough逆変換の際のみに限定しても良いのですが、時間の節約の為に、Hough変換も限定しています。
Hough変換
右上がり60°、水平、右下がり60°のそれぞれの角度に対して、thetaの値でプラスマイナス10の範囲でthetaを変化させます。それ以外の線は無視されます。
//右上がり60°、水平、右下がり60° int[] angle={THETA_MAX/6,THETA_MAX/2,THETA_MAX*5/6}; for(y=0;y<YMAX;y++) for(x=0;x<XMAX;x++) if(data[y][x]==1){ for(int i=0;i<3;i++) for(int j=-10;j<=10;j++){ if(angle[i]+j<0) theta=angle[i]+j+THETA_MAX; else theta=angle[i]+j; rho=(int)(x*cs[theta]+y*sn[theta]+0.5); counter[theta][rho+RHO_MAX]++; } }
Hough逆変換
右上がり60°、水平、右下がり60°のそれぞれの角度に対して、thetaの値でプラスマイナス10の範囲でtheta_maxを探します。それぞれの範囲で直線が検出されるとフラグを立て、全部にフラグが立てば、三角形が見つかったと判断します。
水平の直線が見つかった場合は、「進入禁止」の認識に使用する場合がありますので、ρの値を蓄えておきます。
//右上がり60°の直線 if(THETA_MAX/6-10<theta_max && theta_max<THETA_MAX/6+10) flag1=1; //水平方向の直線 if(THETA_MAX/2-10<theta_max && theta_max<THETA_MAX/2+10){ flag2=1; //「進入禁止」認識用に、水平方向の直線のρを蓄えておく rho_buffer[n++]=rho_max; } //右下がり60°の直線 if(THETA_MAX*5/6-10<theta_max && theta_max<THETA_MAX*5/6+10) flag3=1; //条件が揃ったので、ビープ音を鳴らす if(flag1*flag2*flag3==1) Toolkit.getDefaultToolkit().beep();
「進入禁止」認識用に変更した部分
まず円を認識し、その上半分（centerYとcenterY-radius/2の間）に水平な直線があり、下半分（centerYとcenterY+radius/2の間）に水平な直線があれば「進入禁止」と認識します。
Hough変換
基本プログラムからの変更はありません。
Hough逆変換
n=0; flag1=0; flag2=0; do{ //上半分に直線がある if(rho_buffer[n]>centerY_max-radius_max/2 && rho_buffer[n]<centerY_max) flag1=1; //下半分に直線がある if(rho_buffer[n]>centerY_max && rho_buffer[n]<centerY_max+radius_max/2) flag2=1; }while(rho_buffer[n++]!=0); //ρの蓄積が無くなれば繰り返しを終了 //条件が揃ったので、円を描き、ビープ音を鳴らす if(flag1*flag2==1){ g.drawOval(X1+centerX_max-radius_max, Y0+centerY_max-radius_max,radius_max*2,radius_max*2); Toolkit.getDefaultToolkit().beep(); }
交通標識認識プログラムで得られた画面
図4は、Hough変換基本プログラムを変更して、交通標識の認識に専用化したものの実行結果を示します。これは、実行時の画面をそのまま表示したものではなく、個別の実行結果を編集してあります。上は、原画像（着色してありますが、データとして取り込むのは黒い線の部分のみです。）で、下は実行結果です。下の図で、赤の三角は、「止まれ」を認識したことを示し、同時にビープ音が出ます。青色の丸は、「進入禁止」を認識したことを示し、やはりビープ音が出ます。
黒い原画像のままは、これらが認識されなかったことを意味します（正常動作）。
「止まれ」や「消火栓」の文字の一部が、直線として検出されていますが、これらの文字は、前処理で消すことも可能です。
まとめ
Hough変換は考え方が面白く、プログラム作成の学習対象として好適なので、卒業論文、修士論文、または学会論文誌に多く見かけられます。しかし、連続しているピクセルの検出ではなく、ピクセルの総量で検出するので、人が見た実感とは異なる結果が出る欠点があります。
また、処理に時間がかかる欠点があります。従来、筆者は、実行速度向上のためのテクニックよりは、プログラムの可読性の方を重視してきましたが、今回は、高速化の努力をしました。読者の方には、アルゴリズムが分かりにくかったかも知れません。
Hough変換が交通標識の認識に適しているかどうかは、まだ研究が必要です。安全性にかかわる問題でもあり、高い信頼性が要求されます。
参考資料
この記事は、筆者のウエブサイト「Visual C++を用いた易しい画像処理（15）－Hough変換を用いて、直線と円を検出する－（ただし、現在はVisual C++ 2005 Express Edition版に改定）」を、Java言語を使用して全面的に書き換えたものです。Hough変換のための原画像の準備については、「Visual C++を用いた易しい画像処理（14）－原画像から赤色を抽出し、一旦拡張して縮小する－（ただし、現在はVisual C++ 2005 Express Edition版に改定）」が参考になります。
Hough変換の一般的な参考資料としては、下記があります。
- 『ディジタル画像処理の基礎と応用』 酒井幸市 著、CQ出版、2003年8月
- 『画像処理工学－基礎編』 谷口慶治 編、共立出版、1996年11月
