所謂不変じゃないハフ変換であれば、回転やリサイズに対応していません。しかし、不変ハフ変換はこれらを対応してくれます。ハフ法は基本的にパターンのマッチングです。例えば右の図にある黒い線でできた形状を絵から探したい。そうなりますと、三つの要素を確定させる必要があります。 1. 位置 2. 回転角度 3. サイズ 最重要となる部分は位置です。図形は回転されているや拡大縮小されているかもしれないので、これに強い解析法が必要になります。一つの方法としては、図に示されたように、角度を利用します。 仮にエッジポイント\( \omega_1 \)を発見しました。\( \omega_1 \)はパターンのどの辺にあるかを知りたい。\( \omega_1 \)とその勾配であれば、パターンのどこでもあるかもしれませんので、検索範囲は大きい過ぎます。このため、\( \omega_1 \)とその勾配から固定の\( \alpha \)を足した方向でエッジポイントを探します。仮に\( \omega_2 \)に到達したとします。\( \omega_2 \)も勾配がありますから。\( \omega_1 \)と\( \omega_2 \)の切線は角\( \beta \)を形成します。この\( \beta \)は回転とサイズに無関係です。\( \omega_1 \)とその\( \beta \)はともになって、位置検索の手がかりになります。\( ( \omega_1, \beta ) \)ではパターンの方向が分かります。\( \omega_1 \)から一定の角度\( k \)に沿って直線を描けば、図形の中心位置を通すことができます。描きながら投票すれば、図形の中心位置は決まります。図形の中心位置は予め設定できます。決まりはないですが、\( \beta \)の値を有効に使うため、図形の中心位置は図形の中に置いた方がいいでしょう。例えばパターンの全座標の平均値に置くなどです。\( k \)はパターンから予め計算できます。\( \beta \)の区間をテーブルに詰め込んで、可能な\(… Read more »
偶然のように見えてしまう必然、数学は証明してくれます。私は勉強している所、楕円の四点が一本の直線にあると、半信半疑でした。しかし、実際に演算してみると、全く偶然ではなかった。 楕円は下記のような式で表現できます。 \[ \left[ \begin{array}{c} x(\theta) \\ y(\theta) \end{array} \right] = \left[ \begin{array}{c} x_0 \\ y_0 \end{array} \right] + \left[ \begin{array}{c} a \times cos(\theta) \\ b \times sin(\theta) \end{array} \right] \] 右の図に示された楕円に、\( (x_0,y_0) \) と \( (x_m,y_m) \) と \( (x_\theta,y_\theta) \) と \( (x_T,y_T) \) が一本の直線にあります。\( (x_1,y_1) \)と\( (x_2,y_2) \)は楕円上の2点です。\(… Read more »
角は画像の中の一種の基礎特徴とも言えます。 もっとも基本的な方法としてはエッジの角度を算出し、近隣のエッジポイントの角度の差を計算します。これは基本的に差分法になりますので、ノイズにとても影響され易いと考えられます。このため、この基本方法から一歩か二歩を進んだ方法にHarris法があります。 Harris法は\( (x,y) \)を中心とする、\( (x+i,y+j) \)のウィンドウを考えます。\( ( (i,j) \in [-w,w]\times[-w,w] ) \) このウィンドウにバイアスを加えて\( (x+i+u,y+j+v) \)と\( (x+i,y+j) \)の差を考えます。もし\( (u,v) \)はエッジの方向にそっているなら、差は小さいはずです。エッジに沿わないなら、差は大きいはずです。Harris法はエッジポイントにおいて、差の合計が最小になるように\( (u,v) \)を探し、最小の合計値を曲率の指標とします。つまり、下記の式になります。 \[ E_{u,v}=\sum_{i=-w}^{w}\sum_{j=-w}^{w}(\frac{\partial P_{x+i,y+j}}{\partial x}u+\frac{\partial P_{x+i,y+j}}{\partial y}v)^2 \] Harris法は\( \{ (u,v) | \| (u,v) \|=1 \} \)において、最小の\( E_{u,v} \)を探します。 一見、単位円に沿って\( (u,v) \)を試していく必要があるようですが、実際はそうではありません。数学は美しく助けてくれます。まずは、詳しく見ましょう。\( E_{u,v} \)は下記の式に分解できます。 \[ E_{u,v}=A(x,y)^2 u^2 + 2… Read more »
2Dフーリエ変換は下記のような形式になります。 \[ F_{u,v}=\frac{1}{N}\sum_{x=0}^{N-1}\sum_{y=0}^{N-1}f_{x,y}e^{-j \frac{2\pi}{N}(ux+vy)} \] 似ているが、2Dの逆フーリエ変換は下記のような形式になります。 \[ f_{x,y}=\frac{1}{N}\sum_{u=0}^{N-1}\sum_{v=0}^{N-1}F_{u,v}e^{j \frac{2\pi}{N}(ux+vy)} \] そして、\( F_{u,v} \)は複素数なので、\( F_{u,v}=|F_{u,v}| e^{j \angle F_{u,v}} \)として分解できます。このため、\( f_{x,y} \)は下記のような形式になります。 \( f_{x,y} \) \( =\frac{1}{N}\sum_{u=0}^{N-1}\sum_{v=0}^{N-1}|F_{u,v}| e^{j \angle F_{u,v}} e^{j \frac{2\pi}{N}(ux+vy)} \) \( =\frac{1}{N}\sum_{u=0}^{N-1}\sum_{v=0}^{N-1}|F_{u,v}| e^{j (\frac{2\pi}{N}(ux+vy) + \angle F_{u,v})} \) \( = \frac{1}{N}\sum_{u=0}^{N-1}\sum_{v=0}^{N-1}|F_{u,v}| [ cos(\frac{2\pi}{N}(ux+vy) + \angle F_{u,v}) + j sin(\frac{2\pi}{N}(ux+vy)… Read more »
Phase Congruency、位相一致は比較的に新しい概念です。一つの数学的評価法として、まだ30年ちょっとの年月しか経ってないようです。数千年の歴史を持つ有名な数学概念と比べれば、完全に新しいですね。こんなものですが、デジタル信号からの特徴抽出に有望かもしれません。とりあえず勉強してみました。 一本のデジタル信号は仮に\( x(n) \)とすれば、\( f(n) \)を\( x(n) \)のフーリエ数列の近似とします。つまり： \(x(n) \doteq f(n) = \frac{\alpha_0}{2} + \sum_{k=1}^{N-1}\alpha_k cos(\frac{2\pi n k}{N}+\phi_k)\) \( \alpha_k \ge 0\) <式1> この場合は、特定点の位相一致\( PC \)は下記の式で求められます。 \( PC(n)=\max_{\phi \in [0,2\pi]}\frac{\sum_{k=1}^{N-1}{\alpha_k}cos(\frac{2\pi n k}{N}+\phi_k-\phi)}{\sum_{k=1}^{N-1}{\alpha_k}} \) <式2> この式の計算はすごく大変ですが、加速する方法はあります。しかし、その前に\( f(n)\)を算出する必要があります。運良く、フーリエ変換からフーリエ数列を導出することはできます。 欲しがるフーリエ数列は<式1>のようなものですが、一気にそこまで行くというのはちょっと難しいので、第一歩としては下記の<式3>を得るようにします。 \( f(n)=a_0+\sum_{k=1}^{N-1}(a_k cos(\frac{2\pi k n}{N}) + b_k sin(\frac{2\pi k n}{N})) \) <式3>… Read more »
パスカル三角形は数学上で大変有名です。三角形は内容は一階層ごとに二項式の係数になっています。下の層の係数は上の層の２個の近隣係数の合計です。例えば下のようなものです。
|
|
1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 |
この例はいわば合計のパスカル三角形です。差分のパスカル三角形もあります。一層目は1と-1になるだけです。計算ルールは同じです。例えば下の物です。
|
|
1 -1 1 0 -1 1 1 -1 -1 1 2 0 -2 -1 1 3 2 -2 -3 -1 1 4 5 0 -5 -4 -1 |
詳しく見てみれば、左右から中間へ合計のパスカル三角形の近隣二項の差を取れば、ぴったりと差分のパスカル三角形になります。 パスカル三角形の内容は二項式計数なので、基本的に下記の有名な式で計算できます。 $$ \left( \begin{array}{c} n \\ k \end{array} \right) =\frac{n!}{(n-k)!k!} =\frac{n(n-1)(n-2) \ldots (n-k+1)}{k!} $$ この計算法の問題点としては、分子と分母ともに２個の大きい数字ができてから割り算をします。結果はオーバーフローはより起こりやすいです。このため、パスカル三角形のような足し算だけで計算したほうが穏便です。もう一点では、一般に掛け算が足し算より遅いです。同様な計算回数であれば、一般に足し算の方が早く終わります。これはコンピュータも人間も同じのようです。 指定サイズ(SIZE)のパスカル三角形の最後の層は下記のようなコードで計算できます。
|
|
P[0]=1; P[1]=1; // 1を-1にすれば、差分のパスカル三角形になります。 for (y=2;y<SIZE;y++) { b=0; for (r=y;r>0;r--) { P[r]=P[r-1]+b; b=P[r-1]; } } |