楽譜アーカイブアプリ - その15 確率的ハフ変換

昨日は直線検出のためのハフ変換をおさらいした。昨日のを読み返してみてなにが書いてあるのかすぐわからなかった。難しいのではなくて何が言いたいのかわからない。しばらくしてからアルゴリズムとしてではなく数学的にすっきりしたかったのね、なるほどねえ、とわかった。しかしまわりくどい。たった1日でアカの他人ですわ。

6.2  確率的ハフ変換による直線探索

絨毯爆撃をもう少し賢くやろう、というアルゴリズムがある。これはようするに適当に選んだ点が直線に並んでいたら、その間にも点があるだろう、という考え方である。これを確率的ハフ変換（PPHT、Progressive Probabilistic Hough Transform。Progressiveはどこへ行ったんだ?）という。このアルゴリズムは

1. 点をランダムに取り出す。取り出した点には「取り出した」という目印を付けておく
2. パラメータ平面に軌跡を描く
3. 投票値がある数を超えている目があったら、その目に対応する直線を元画像に引く
4. その直線上に他の点が乗っていないか探す
5. 乗っていた点に「取り出し済み」目印を付ける
6. すべての点が「取り出し済み」になるまで繰り返す

となる。このアルゴリズムだと長い直線が少数あるような画像では非常に速くなる。このアルゴリズムの変形版がいまでもいろいろ提案されている。

このアルゴリズムでは「取り出し済み」の点から直線にそって探索してやれば、連結した線分として点を選び出せる。つまり線の始点と終点が得られる、ということになる。画像上の線が揺らいだりノイズで切れたりすることもあるので数ピクセルのギャップは許すことにすればより、長い直線が得られる場合がある。

これと対比してさっきの絨毯爆撃的ハフ変換を標準ハフ変換と呼ぶ。

6.2.1  標準ハフ変換と確率的ハフ変換のパラメータ

直線のパラメータ(r,θ)ではなくアルゴリズムに外から与える値の意味でパラメータと言う言葉を使っているが、ふたつのアルゴリズムのパラメータを比較してみる。

元画像の画素数を別にすると、標準ハフ変換の場合、外から与えるパラメータは目の分割数M ×Qと、いくつの点が乗っていたら直線とみなすか、という投票値の最小値の3つである。

分解能を高くしようとして目の数を増やすと直線に乗っていると判断される点の数は減って、直線が見つからない、という場合も出てくる。分解能をあげた場合には近傍の直線も探す、という余分な作業をする必要も出てくる。この場合、直線がどのくらい近ければ同一視するか、というのもパラメータになる。

確率的ハフ変換ではこれに加えて

• 元画像に直線を引く投票値の閾値
• 同一の直線とみなすギャップのピクセル数

がある。投票値の閾値を大きくしていくと標準ハフ変換の計算量に近づいていくことになる。分解能に関しては標準ハフ変換と同じことが言える。カメラで撮った自然な画像、例えば建物の稜線を取り出す、とか言う場合にはこういったパラメータの値の選び方は微妙で、適応的に選ぶ必要が出てくる場合もある。

6.2.2  五線譜の傾き検出への応用

今回はあまり難しい画像を対象にするわけではない。問題としては非常に素性のいい部類である。ただし、角度分解能は高い必要がある。なぜなら元画像にもともと平行な直線が多く、0.3°ぐらいの傾きでも見た目でわかってしまうからである。

ただし、もともとカメラ画像ではなく、スキャンした画像なので傾きも±10°以内くらいにはたいてい入る。従ってパラメータ平面も全平面を対象にする必要は無い。

一方で、カメラの自然画像を対象にする場合にはまずエッジ検出をしてその画像に対して直線検出をする場合が多い。今回の場合にはエッジ検出したのでは一本の線の輪郭を取り出してしまうことになり無駄な点を大きく増やしてしまう。

そこでエッジ検出ではなく細線化が必要であるが、細線化によってもともと直線だった部分が変形する場合がある。細線化について次に考える。

コメント 2

この２週間ほど、仙台のギタリスト斎藤功一氏

■仙台市生まれ
■1974年より渡辺範彦氏に師事
■1979年・80年・81年・82年リサイタル開催
■1983年6月仙台市戦災復興記念館ホールに於いて渡仏記念演奏会
■1983年7月渡仏,A,ラゴヤ氏に師事
■1985年6月OGD演奏会に出演
■1989年1991年2000年2001年宮城県芸術祭に出演
■2000年10月戦災復興記念ホールにてソロリサイタルを開催
■2008年6月韓国にて　日・韓交流仙台・大邸演奏会に出演
■宮城県芸術協会会員
■ラフォーレギターシンフォニア代表／ラフォーレギター教室主宰

にリュート組曲１番のプレリュードとアルマンドの譜面を見てもらっていました。

先ほど、お話しをうかがったところでは、「とても素晴らしい」とのことです。
「３弦Fisは、演奏をするのは少し大変ですが、それでもやってみる価値が十分ある素晴らしい編曲」だとのことです。

少し数多くのギタリストに見てもらってご意見を聞いてみようと思っています。


by エトワール (2010-12-12 14:21) 

コメントありがとうございます。
高いご評価を頂いた上に、プロのギタリストの方にまでご紹介を頂き、まったく恐縮してしまいます。
なんだかお手数をおかけしているようで、申し訳ありません。しかし、ご評価いただけるのは大変光栄で、思いがけずとてもうれしいことです。
大変ありがとうございます。
今後ともよろしくお願いします。
by decafish (2010-12-12 22:30)