Monthly Archives: September 2015

角検出のHarris法

MathLearner 2015年9月30日 No Comments

角は画像の中の一種の基礎特徴とも言えます。もっとも基本的な方法としてはエッジの角度を算出し、近隣のエッジポイントの角度の差を計算します。これは基本的に差分法になりますので、ノイズにとても影響され易いと考えられます。このため、この基本方法から一歩か二歩を進んだ方法に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実数データのフーリエ分解の実関数形態を考える

MathLearner 2015年9月26日 No Comments

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 »

位相一致を考える

MathLearner 2015年9月22日 No Comments

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 »

実在する画像のみを使用する(JavaScript)

MathLearner 2015年9月20日 No Comments

画像を画像サーバーにアップすることはよくあります。全容の画像サーバー出なくても、時間の経過につれ、元々あった画像がなくなっている場合があります。この場合は、ただ画像が無いことをユーザーに見せるか、それとも、画像がないこと自体もユーザーに知らせないのか、二者択一になります。もし後者を選ぶ場合であれば、大体３種類の方法があります。方法１一つはサーバー再度でチェックを行います。今実在している画像のみをブラウザに送ります。この方法は明らかに大量画像に対応できません。負担がサーバーに大きく集中し、現実的な良策とは言えません。方法２残りの二種類の方法はどっちもクライアント再度でJavaScriptで画像の確認を行います。中により簡単な、いわば中間策は、<img>タグのonerrorイベントに自身を削除させるコードを入れさせます。例えばこのコード：

<img src="..." onerror="this.parentNode.removeChild(this);">

1	<img src="..." onerror="this.parentNode.removeChild(this);">

このコードはシンプルで、シンプル過ぎて、ロード中の仮画像は表示されます。せめて、この仮画像は出てほしくないなぁ～と思うなら、ロードに結果が出るまでは透明にするのが一つの方法です。例えば、下記のコードです。

<img
 style="opacity: 0"
 onerror="this.parentNode.removeChild(this);"
 onload="this.style.opacity=1;">

<img

style="opacity: 0"

onerror="this.parentNode.removeChild(this);"

onload="this.style.opacity=1;">

方法３方法２のバージョンアップとして考えてみれば、画像が成功にロードできる場合に限ってこの画像を実行しましょう。つまり、方法２のonloadに現在画像をページ上の他所に実装するコードを入れます。しかし、ここはこのやり方をあえてせず、この機能をJavaScriptのクラスに清潔にまとめたいと思います。しかも、もうちょっと制御を入れます。仮に、画像一覧があります。順番どおりにユーザーに見せたいです。しかし、単純な方法２を改装するところで、これは達成し辛いというわけではないですが、ページ上で多少ゴチャゴチャになるところがでてくるかもしれません。このため、コードをカプセル化します。下記のようなコードになます。

var ImageExists=function (urls,onImgReady) {
    this.imgs=[];
    this.urls=urls;
    if (typeof onImgReady=='function')
        this.onImgReady=onImgReady;
    else
        this.onImgReady=function () {};
    this.idxNextToReport=0;

    this.run=function ()
    {
        var container=this;
        for (var i=0;i<this.urls.length;i++)
        {
            var img=new Image();
            var imginfo;
            imginfo={
                "status": "unknown",
                "obj" : img,
            };
            this.imgs.push(imginfo);
            img.index=i;
            img.onload=function () {
                container.imgs[this.index].status='ok';
                container._someImageReady();
            };
            img.onerror=function () {
                container.imgs[this.index].status='err';
                container._someImageReady();
            };
            img.src=this.urls[i];
        }
    };

    this._someImageReady=function () {
        while (this.idxNextToReport<this.imgs.length)
        {
            if (this.imgs[this.idxNextToReport].status=="unknown")
                break;
            if (this.imgs[this.idxNextToReport].status=='ok')
                this.onImgReady(this.imgs[this.idxNextToReport].obj.src);
            this.idxNextToReport++;
        }
    };
};

var ImageExists=function (urls,onImgReady) {

this.imgs=[];

this.urls=urls;

if (typeof onImgReady=='function')

this.onImgReady=onImgReady;

else

this.onImgReady=function () {};

this.idxNextToReport=0;

this.run=function ()

{

var container=this;

for (var i=0;i<this.urls.length;i++)

{

var img=new Image();

var imginfo;

imginfo={

"status": "unknown",

"obj" : img,

};

this.imgs.push(imginfo);

img.index=i;

img.onload=function () {

container.imgs[this.index].status='ok';

container._someImageReady();

};

img.onerror=function () {

container.imgs[this.index].status='err';

container._someImageReady();

};

img.src=this.urls[i];

}

};

this._someImageReady=function () {

while (this.idxNextToReport<this.imgs.length)

{

if (this.imgs[this.idxNextToReport].status=="unknown")

break;

if (this.imgs[this.idxNextToReport].status=='ok')

this.onImgReady(this.imgs[this.idxNextToReport].obj.src);

this.idxNextToReport++;

}

};

このコードでは、実在している画像のみをコーラーに報告します。同時に、報告の順は画像URLの順です。使用方法に関しては、下記のサンプルをご参考下さい。

var urls=[
"http://www.graphicstock.com/eiwoffjgh.jpg",
"http://cdn.1001freedownloads.com/icon/thumb/387305/File-Adobe-Dreamweaver-JavaScript-icon.png",
"http://www.freeimages.com/eiwofjgh.jpg",
"http://thinketg.com/wp-content/uploads/2014/09/js.png",
"http://pixabay.com/eiwoffjgh.jpg",
"http://www.stockfreeimages.com/eiwoffjgh.jpg",
"http://www.dreamstime.com/eiwoffjgh.jpg",
"http://www.antrromet.com/img/icon_js.png",
"http://www.mackenziearmstrongcreative.com/images/jsIcon.png"
];
var IR=new ImageExists(urls,function (url) {
    var img=document.createElement('IMG');
    img.src=url;
    document.body.appendChild(img);
});
IR.run();

var urls=[

"http://www.graphicstock.com/eiwoffjgh.jpg",

"http://cdn.1001freedownloads.com/icon/thumb/387305/File-Adobe-Dreamweaver-JavaScript-icon.png",

"http://www.freeimages.com/eiwofjgh.jpg",

"http://thinketg.com/wp-content/uploads/2014/09/js.png",

"http://pixabay.com/eiwoffjgh.jpg",

"http://www.stockfreeimages.com/eiwoffjgh.jpg",

"http://www.dreamstime.com/eiwoffjgh.jpg",

"http://www.antrromet.com/img/icon_js.png",

"http://www.mackenziearmstrongcreative.com/images/jsIcon.png"

];

var IR=new ImageExists(urls,function (url) {

var img=document.createElement('IMG');

img.src=url;

document.body.appendChild(img);

});

IR.run();

実例を見る

Marr-Hildrethエッジ検出法

MathLearner 2015年9月19日 No Comments

もう一つの二次差分エッジ検出法はMarr-Hildreth法です。これはガウススムージングから由来します。マグニチュードを無視すれば、二元ガウス関数は下記の形式を取ります。 $ g(x,y;\sigma)=e^{-\frac{x^2+y^2}{2\sigma^2}} $ $ g(x,y;\sigma) $の微分を二回計算すれば下記のような式になります。 $ \triangledown^2g(x,y;\sigma)=\frac{1}{\sigma^2}{\left( \frac{(x^2+y^2)}{\sigma^2}-2 \right)}e^{-\frac{x^2+y^2}{2\sigma^2}} $ この式の$ x $と$ x $に座標を割り当てるとMarr-Hildreth法のテンプレートが出来上がります。ただし、注意点があります。このテンプレートは修正が必要です。原因はこのテンプレートの合計はゼロではないからです。ゼロでないと、各座標において算出された二次差分は全体的に正数か負数に偏ることが発生します。結局ゼロ交差でのエッジの検出はできなくなります。これ点を注意した上で結果を見てみましょう。画像が大きいため、この処理結果を得るには120秒掛かりました。

エッジ検出のためのラプラシアン演算子を考察する

MathLearner 2015年9月19日 No Comments

一次差分法でエッジを検出する方法はありますが、さらに考えますと、一次差分が最大値に至ったときにエッジが記録されます。一次差分が最大値に達する点は、二次差分の符号が変わる時でもあります。なので、二次差分の符号が変わる点を割り出せば、エッジが分かるはずです。この中、もっとも簡単なものかも知れませんが、ラプラシアン法があります。ラプラシアン法は下記のようなテンプレートを使用します。 $ \left[ \begin{array}{rrr} 0 & -1 & 0 \\ -1 & 4 & -1 \\ 0 & -1 & 0 \end{array} \right] $ このテンプレートの出力結果は図1にあります。結構酷いですね。じゃあ、もうちょっと平均してみましょうか、なので、下記のような周辺8点を全部入れましょう。 $ \left[ \begin{array}{rrr} -1 & -1 & -1 \\ -1 & 8 & -1 \\ -1 & -1 & -1 \end{array} \right] $… Read more »

Cannyエッジ検出法

MathLearner 2015年9月19日 No Comments

Cannyエッジ検出法は一般に四つのステップがあります。ガウススムージング Sobel法によるエッジ検出非最大値抑制ヒステリシス閾値化 Sobel法では、ある程度のスムージングが効いています。ただ、その標準偏差は変えられない。Sobel法の前に別途スムージングのステップを組めば、より良いノイズ耐性は期待できます。 Sobel法では、一個の画素に対して、横と縦二回の検査があります。横と縦に方向での明暗変化の強さが求められ、エッジの方向は分かるようになります。仮に、横と縦の変化量を$ Mx $と$ My $とすれば、エッジの方向は下記の式で算出されます。 $\theta=tan^{-1}\left( \frac{My}{Mx} \right)$ もちろん、$ Mx $と$ My $の符号を考慮に入れれば、$ [0,2\pi) $ の角度は求められます。この角度を非最大値抑制のステップで活用します。非最大値抑制の目的は、検出されたエッジを細くするためです。明暗変化は上げ下げしているので、綿花のもっとも激しいところをエッジにし、そのたの画素をエッジにしないことが目的です。画像の画素は離散しているため、一つの画素の周辺は八個の画素しかありません。しかし、エッジの方向は非常に多いです。現在対象の画素は最大であるかどうかをより正確に検出するため、Canny法は数値補間を使用します。イメージとしては図1をご覧ください。図1に大きい丸は実在する画素を意味します。$ M(\cdot,\cdot) $は画素の明るさです。$ M1$と$ M2$は補間によって算出される非実在の画素の明るさです。図1の実線の直線はエッジで、点線はエッジを跨ぐノーマル方向です。画素がノーマル方向において、最大である場合に限ってエッジにいると認定されます。この様な画素だけが保留され、そうでない点は全部消されます。ステップ3直後の効果をまずは見てみましょう。図2を詳しく見てみますと、薄い灰色の顔の輪郭は見られます。また、人の目ではなかなか見えないですが、図2に黒に使い画素は多々あります。見せるためだけ、これらの点を全部明るくしたバージョンは図3です。黒に近い点は所謂ノイズで形成されています。エッジから除外されるべきです。これはステップ4、ヒステリシス、の役割です。ヒステリシスとは延滞です。エッジに充分なり得る一点から初め、周辺に探って行きます。エッジになり得ない点を除き、すべての点はエッジにする。結果は驚きほどです。図4です。輪郭だけが残りました。顔の主要特徴は残されています。 Canny法の欠点はスピードにあります。ステップ1とステップ2はかなり時間を食います。もちろんテンプレートサイズを小さくされば時間短縮になります。効果は少し落ちますが、まあ～、そんなに悪くない。

パスカル三角形の計算方法(合計と差分)

MathLearner 2015年9月19日 No Comments

パスカル三角形は数学上で大変有名です。三角形は内容は一階層ごとに二項式の係数になっています。下の層の係数は上の層の２個の近隣係数の合計です。例えば下のようなものです。

          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 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

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];
    }
}

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];

}

Sobelエッジ検出法

MathLearner 2015年9月19日 No Comments

画像処理の試み　一次差分法でエッジ検出にもっとも基本的なエッジ検出方として一次差分法を紹介しました。右の図に示されたように、素描のような影が出て悪くない感じですね。用途によっては、これ結果は良いでしょう。でも、エッジ検出の観点から見れば、この結果はあまりいいとは言えません。頬と額のエリアに注目してみましょう。頬と額はかなり黒塗りされています。その黒さは全部エッジの誤認です。誤認の原因は、原始画像は一見滑らかに色が変化しているように見えても、実際に局部の画像を拡大して見れば、多くのでこぼこは見れます。一次差分法はこのでこぼこを明暗の差として認識し、エッジとしました。一次差分が頻繁の名鑑変化を広いスケールで見れず、画素の組み合わせは安易に明暗変化として認識してしまう。この性質は人間の目と大きい違いがあります。この問題を解消した炒め、よく使用される方法は、エッジ検出の前に何らかの方法でスムージングをかけます。一次差分の問題点を具体的に見てみましょう。 $y_1(n)=x(n)-x(n-1)$ (1) $y_2(n)=x(n)-x(n-2)$ (2) (1)はもっとも基本的な一次差分です。図1からは高周波では反応が強いです。これがあのでこぼこの原因です。(2)はよくある改善法として、高周波数においては、応答は落ちます。これによって所謂高周波ノイズの影響は小さくなります。Sobel法は(2)を使用しています。でもこれだけではありません。画像は縦と横の二方向あります。一方向で差分を検出している時に、もう一方向のデータにあまり影響されては困る。このため、Sobel法は一方で差分をしている同時に、もう一方ではスムージングを行います。スムージングの方法はガウススムージングの整数バージョンです。つまり、二項式の係数を使用します。このやり方は不思議かも知れませんが、実際に数字のスケールだけが番って、値間の倍数で考えればまったく同じく見えます。実例で見ましょう。図2に、緑と赤の２本の曲線があります。ほぼ完全に重なっていますね。赤い方はガウスで緑の方は二項式係数です。二項式係数使用しますと、複雑な指数関数を使用しなくともガウス同等な効果を得られます。ただ一点だけを注意する必要があります。二項式が長すぎると係数が大き過ぎになり、オーバーフローが発生します。ある基準によると、ガウスは最良な画像スムージング法とも言われます。周波数応答は下の図3に記されます。この周波数応答の形状はまさにガウスその物です。はっきりとローパスフィルターが映っています。縦方向のエッジを検出するためのSobelテンプレート下記のような行列です。横方向のエッジを検出するためのSobelテンプレートは縦方向の転置です。 \( \left[ \begin{array}{rrrrrrrrr} {1} & {6} & {14} & {14} & {0} & {-14} & {-14} & {-6} & {-1}\\ {8} & {48} & {112} & {112} & {0} & {-112} & {-112} & {-48} & {-8}\\ {28} &… Read more »

ブロックされないように新ウインドウ開く方法を考える。

MathLearner 2015年9月18日 No Comments

iOS 8/9のSafariでは、<a href=”window.open(…)”>では、開かれるウインドウは阻止されてしまう現象があります。一つの方法としては、<a href=”#” onclick=”window.open(…)”>のように変えることです。つまり、hrefにウインドウを開くコードを入れずに、onclickの方に入れます。上記の現象はいつ起きるかは本当にバージョンによるかもしれません。今後にもonclickが通用する事を祈るしかないかもしれません。より確実な方法はどうかは確定できないですが、下記のようなJavaScriptもできます。

var fo=document.createElement('FORM');
// フォーム対象を作ります。

fo.action='/receive.php';
// 開かれるウインドウの内容を提供するURLです。

fo.method='GET';
// HTTPメソッドはGETにします。POSTにしても構わないですが。

fo.target='_blank';
// 目標タブの名称を指定。
// これが未設定、または'_self'の場合は、現在のウインドウで表示されるので
// 必ず設定しましょう。

var inp1=document.createElement('INPUT');
inp1.type='text';
inp1.name='param1'; // クエリのパラメータ名を指定
inp1.value='パラメータ1の値';

var inp2=document.createElement('INPUT');
inp2.type='text';
inp2.name='param2'; // クエリのパラメータ名を指定
inp2.value='パラメータ2の値';

fo.appendChild(inp1);
fo.appendChild(inp2);
// 入力項目をフォームに追加

document.body.appendChild(fo);
fo.submit(); // フォームを提出する。

document.body.removeChild(fo);
// 使い終わったフォームを削除する。

var fo=document.createElement('FORM');

// フォーム対象を作ります。

fo.action='/receive.php';

// 開かれるウインドウの内容を提供するURLです。

fo.method='GET';

// HTTPメソッドはGETにします。POSTにしても構わないですが。

fo.target='_blank';

// 目標タブの名称を指定。

// これが未設定、または'_self'の場合は、現在のウインドウで表示されるので

// 必ず設定しましょう。

var inp1=document.createElement('INPUT');

inp1.type='text';

inp1.name='param1'; // クエリのパラメータ名を指定

inp1.value='パラメータ1の値';

var inp2=document.createElement('INPUT');

inp2.type='text';

inp2.name='param2'; // クエリのパラメータ名を指定

inp2.value='パラメータ2の値';

fo.appendChild(inp1);

fo.appendChild(inp2);

// 入力項目をフォームに追加

document.body.appendChild(fo);

fo.submit(); // フォームを提出する。

document.body.removeChild(fo);

// 使い終わったフォームを削除する。

なぜ、fo.actionにURLパラメータを直接に書き込まないかというと、iPhoneで「?」以降の文字列が全部失われるという現象が観測されている。なので、この方法をあえて避けました。