楽譜アーカイブアプリ - その14 直線検出

五線譜をスキャナで取り込んだときの傾きを補正したい。そのための直線検出を考える。

6  直線検出

五線の傾きを検出して、ページごとに微妙にあっちに倒れたりこっちに傾いたりしないようにしたい。傾きを検出するには5本の直線を切り出してその角度を計算すればいい。有効な領域幅いっぱいにあって縦にはたくさん並んでいるので非常に条件のいい問題のはず。直線を検出するのは一般的な手法がある。

直線検出には古典的なハフ変換（Hough Transform）よる方法が一般に使われる。OpenCVの直線検出にもハフ変換（の改良版）が使われているらしい。

6.1  ハフ変換

ハフ変換というのは

のような(a,b)のパラメータを持った2次元上の直線の式を

というパラメータ(r,θ)に変換する

というものである。式-6.2は

と書くことができる。ここで最後の式の左辺は2次元ベクトルの内積である。おかしな変形をしたけれど、つまり点(x,y)は点(r cosθ,r sinθ)を通って(cosθ,sinθ)に垂直な直線上にあるということがわかる。逆に言えば式-6.2で表される直線は、原点からの距離がrでx軸とのなす角がθ±π/2であるような直線を表すことがわかる。

式-6.1と式-6.2の係数を比較すれば

あるいは

などとなることはすぐわかる。

これだけではなにも面白いことはないけれど、ここである点P=(x₀,y₀)を通る直線群Lを考える。

Lは式-6.1を使うと

を満たすような(a,b)の組となる。

一方、式-6.2では

となる。

式-6.4ではすべての直線を表すにはa、bはともに±∞の範囲に広がるが、式-6.5ではどちらも有限の範囲におさまる。

ここでふたつの点P₀=(x₀,y₀)とP₁=(x₁,y₁)を考える。一方の点を通る直線群をL₀とL₁とする。

直線をパラメータで表せば2次元のパラメータ平面上でL₀、L₁は式-6.4や式-6.5によってaとb、あるいはrとθの関係が決まっているので、一本の曲線になる。その2次元のパラメータ平面上での曲線をそれぞれΛ₀とΛ₁とする。

ここでL₀とL₁の両方に含まれる直線が一本あって、2次元のパラメータ平面上ではその直線は曲線Λ₀とΛ₁の交点である。つまり

か、あるいは

である。つまりP₀とP₁の両方を通る直線を探すことはΛ₀とΛ₁の交点を探すことに帰着する。

ここまでは当たり前のことを回りくどく言っているにすぎないんだけど、曲線Λ₀とΛ₁との交点を探すとき、パラメータの表現のしかたが式-6.6では±∞の範囲に広がるが、式-6.7ではどちらも有限の範囲におさまるので、絨毯爆撃的な探索では式-6.7つまり式-6.2で直線を表現した方がずっと簡単である、ということになる。

2点の場合では探索をするまでもないが、多くの点の中から直線に乗った点を探し出すには絨毯爆撃的にやるしかない。

平面上にN( >> 1)個の点が存在するとする。その中のある点P_nを通る直線群はパラメータ空間のひとつの曲線Λ_nが対応する。

N個の曲線の集合Λ_nのうち交点(r_i,θ_i)を共有する部分集合に対応する点はすべてあるひとつの直線を通るということになる。

つまりΛ_nをパラメータ平面(r,θ)に描いてみて、ある点でたくさんの曲線が交わっていたら、それらに対応する点はひとつの直線の上に乗っているということになる。

6.1.1  具体的なアルゴリズム

数学的にはいいとして、実際の画像に適用して直線を検出するアルゴリズムはどうなるのか。

1. まず、パラメータ平面(r,θ)を碁盤の目に区切る。最小単位はどのくらいの分解能で直線を探したいかによる。
2. それぞれの目は数が数えられるようにしておく。そして0に初期化する。
3. 点を端からひとつ選んで、それに対応する曲線Λの軌跡をパラメータ平面に描く。軌跡が通った目に全部1を足す。
4. すべての点に関して以上を繰り返す。
5. 全部終わったら目が数えた軌跡の累積値を多い順に調べる。
6. それぞれの目が数えた値がそれに対応する直線の上に乗っている点の数になる

ということになる。ようするに画像とは別にパラメータ平面の配列を用意して、式-6.1に従って曲線を引いて通った配列要素をインクリメントしていけばいい。

この、目の軌跡の累積値のことをその目に対する「投票値」と呼ぶ。

6.1.2  効率

このアルゴリズムはすべての点に関してパラメータ平面上に曲線を描くことになるので、点の数をN、パラメータ平面の目の数をM ×Qとすると計算量Cはおおまかには

となる。最適化などの繰り返し計算に比べれば計算量の見積もりは簡単だけど、画像を対象にすると点の数が多いので問題となることがある。計算量を減らすためには対象とする点の数を減らすか、目の数（分割数）を減らすしかない。あとは三角関数をいちいち計算せずに表にしておく、とかの程度である。