C言語でHough変換での直線検出処理の実現

[ホッチキス]

初めて質問させていただきます。何かとご迷惑をかけるかもしれませんがよろしくお願いします。
今C言語でのHough変換を行うプログラムを作成中です。
まずアルゴリズムについてですが、
①エッジ検出処理、2値化処理をした画像を読み込む
②明度値が255のポイントをサーチし0<θ<360の範囲でρ = x * cos(θ) + y * sin(θ)を計算し配列に投票を行う。
③②の投票した配列から最大値を検出。
④最大値を画像として出力。
であっていますでしょうか？

今作成しているプログラムではρθのハフ空間の画像出力まで成功しており、
後は最大値の検出、それをxy画像空間で出力する方法が分かりません。
そこを教えていただきたいです。

int H[][]には投票した結果
int rho_maxには計算したrhoの最大値
int h,wには入力画像の縦横のサイズが入っています。

導き出したrho_mとtheta_mを出力処理の関数に渡して画像として出力したいです。
画像を出力するアルゴリズムも教えてください。

追加でピークが複数あった場合の処理も教えてほしいです。

コード:

void peakHough(int H[][360],int rho_max, int h, int w, int *rho_m, int *theta_m)
{
int i, theta, rho, max, cnt;
int M[1000][2];
int rh=0;
int th=0;


//-----最大値を抽出-----

    cnt = 0;
    max = 0;

    for(theta=0; theta<360; theta++){
      for(rho=0; rho<rho_max; rho++){

        if(H[rho][theta] > max){
          max = H[rho][theta];
          rh = rho;
          th = theta;           
        }
      }
    }

/*
        printf("%d %d\n",rho,theta);
    for(theta=0; theta<360; theta++){
      for(rho=0; rho<rho_max; rho++){

        if(H[rho][theta] = max)
          M[cnt][0] = rho;
          M[cnt][1] = theta;
          cnt++;
      }
    }
*/
    *rho_m = rh;
    *theta_m = th;

}
 

[usao]

結果が１つで良いなら
> 最大値
でしょうが，個数が不明な場合はハフ空間に投票された投票値の極大値を検出することになります．
どれを採用して，どれを採用しないのか，には工夫が要ります．
（人間が結果の具合を見ながら閾値調整するとか，あるいは経験的な値とかで
　投票値に対する閾値を与えることができるなら良いのですが，問題次第です．）
また，正解の付近に投票が散らばってしまうことへの対策も必要です．
（不真面目には，適度に投票値をぼかすとか）

ρとθに対する線をx-y空間に描画したい場合は…
適当に検索すれば，どんな線なのかを図で示しているものが見つかるかと思うので，その線を引けば良いかと思います．
（原点から角度θ方向に長さρの線分を引いたときに，その線分の末端を通って，それに垂直な線だったかと．）

[ホッチキス]

自分の中でも最大値の検出については不明な部分が多いです。
今のところは質門に記述したソースコードのコメントの部分で
最大値と同じ場所が無いかサーチした後、
複数の点があった場合は平均値を出して
四捨五入した結果を最大値として
格納しようかと思っているのですがどうでしょうか？

コード:

    for(theta=0; theta<360; theta++){
      for(rho=0; rho<rho_max; rho++){

        if(H[rho][theta] = max)
          M[cnt][0] = rho;
          M[cnt][1] = theta;
          //printf("%d %d\n",M[cnt][0] ,M[cnt][1]);
          cnt++;

    for(i=0; i<cnt; i++){
      rh = rh + M[i][0];　　　　//全ての点を合算
      th = th + M[i][1];
    }

    printf("cnt=%d\n",cnt); 　　

    rh = rintf ( rh / cnt);        //カウントした最大値の点の数で割り四捨五入
    th = rintf ( th / cnt);   

    *rho_m = rh;
    *theta_m = th;

[usao]

> if(H[rho][theta] = max)
ここは == ですよね．


平均値…の話ですが，それを投票空間全域でやってしまうと，
例えば，画像上に直線が２本あり，それらへの投票結果がたまたま同じ投票値になったような場合に
「本来の２本とは全く異なる謎の１本の直線」という結果になってしまいますよね．

投票空間全域ではなく，見つけた最大値の「近傍について」行うなら，
散らばってしまった投票結果から１本の直線を決定する方法の１つにはなるように思います．
ただ，そういう方向での結果の統合処理を行うにしても
「最大値と（偶然に）投票値が等しい場所」だけを考えるよりも，
投票値を重みとした加重平均を取る等の方が現実的かなと思います．

（最後の四捨五入については，それを行う背景がわからないので判断つきません．
　パラメタ値を整数にする必要があるのでしょうか．）

[ホッチキス]

>見つけた最大値の「近傍について」行う場合は、下のプログラムのどこを改変したらいいでしょうか？
近傍の範囲指定をどう行ったら良いかわからないです。上下？なのか左右？なのか

コード:

    for(theta=0; theta<360; theta++){
      for(rho=0; rho<rho_max; rho++){
 
        if(H[rho][theta] == max)
          M[cnt][0] = rho;
          M[cnt][1] = theta;
          //printf("%d %d\n",M[cnt][0] ,M[cnt][1]);
          cnt++;
 
    for(i=0; i<cnt; i++){
      rh = rh + M[i][0];　　　　//全ての点を合算
      th = th + M[i][1];
    }
 
    printf("cnt=%d\n",cnt); 　　
 
    rh = rintf ( rh / cnt);        //カウントした最大値の点の数で割り四捨五入
    th = rintf ( th / cnt);   
 
    *rho_m = rh;
    *theta_m = th;
 

[usao]

「近傍」とはどんな範囲を見れば良いのか？　というのは…問題依存かな，と思います．
例えば，簡単には，

コード:

//最大値が見つかった場所
int MaxVotePos_Rho = 投票空間を走査して最大値が見つかった場所のρ方向index
int MaxVotePos_Theta = 同 θ方向index
//「近傍」の大きさ
int dRho = 3;
int dTheta = 2;
//最大値が見つかった場所を中心とする矩形範囲を走査　（※概念説明なので，投票空間範囲外参照チェック等を省略）
for( theta=MaxVotePos_Theta-dTheta; theta<=MaxVotePos_Theta+dTheta; ++Theta )
{
  for( rho=MaxVotePos_Rho-dRho; rho<=MaxVotePosRho+dRho; ++rho )
  {
    ...
  }
}

みたいなのが思いつくけれども，
(1)「そのdRhoやdThetaの値の根拠は何なのですか？」
(2)「何で矩形なのですか？　円じゃいけないんですか？　ちょっと考えるとせめて楕円の方がどうのこうの」
等々…