| プログラムメモ | 2013/10/19 Sat 21:49

２値化画像のラインを細線化するアルゴリズムは沢山ありますが、
ループ回数がどうしても多くなるので、javascriptでの実装例は少ないです。

ここでは、比較的高速なZhang-Suen, NWGと、田村の方式を実装してみます。

実行サンプルはこちら

Zhang-Suenのアルゴリズムは、比較的単純であるので実装し易いです。

ラスタスキャンにより画素情報を読み込み、
調査画素を含む、3x3pixの画素値に対し、3種の条件を満たしていれば、
調査画素を白(1)から黒(0)に置き換えます。

調査画素(P1)を含む、3x3pixの画素に次のように番号を振る。

条件１．

　外周一周を眺めた時、
　(P2->P3->P4->P5->P6->P7->P8->P9->P2)
　黒→白となる並びが一つだけであること。

　(英文:A(P1)=number of 0,1 patterns(transitions from 0 to 1) in the ordered sequence of P2,P3,P4,P5,P6,P7,P8,P9,P2.
　Condition: A(P1) = 1 )

条件２．

　外周の加算(白なら+1)の結果(B)が、2<= B <=6、を満たす。

　(英文:B(P1)=P2+P3+P4+P5+P6+P7+P8+P9 (number of nonzero neighbords of P1.)
　Condition: 2 <= B(P1) <= 6 )

条件３(1)．

　P2 x P4 x P6 = 0 かつ、P4 x P6 x P8 = 0 を満たす。

条件３(2)．

　P2 x P4 x P8 = 0 かつ、P2 x P6 x P8 = 0 を満たす。

まず、条件１．２．３(1)の判定を行い、条件を満たした場合、該当画素を除去リストに追加する。
全画素調査後、除去リストに画素があれば、その画素を全て黒(0)に変える。なければ終了する。

次に、条件１．２．３(2)の判定を行い、同様の処理を続ける。
以降、条件３(1)(2)を切り替えながら、条件を満たす画素がなくなるまで、繰り返し行う。

NWG (Nagendraprasad-Wang-Gupta)については、Zhang-Suenと非常に似た処理であるため、
説明は割愛します。
詳細は、ソースコードか、
A note on the Nagendraprasad-Wang-Gupta thinning algorithm をご覧ください。

Zhang-Suenのアルゴリズムが主に計算による判定を行うのに対し、
田村のアルゴリズムは、図形のマッチングを利用します。

大まかな処理としては、
2種類のパターンがあり、それぞれのパターンは、
3x3の除去パターンと3x3の非除去パターンに分かれる。
（ここで言う除去は、白から黒への変更を意味する。）

ラスタスキャンにより画素情報を読み込み、
各画素について3x3のパターンマッチングを行う。

パターンには次のものがある。

【処理概要】

① パターン１の除去パターンでマッチングすれば②へ、一致しなければ次画素へ。
② パターン１の非除去パターンでマッチングすれば次画素へ、一致しなければ③へ。
③ 該当画素を除去リストに追加し、次画素へ。
④ ①～③の処理を全画素に対して行う。
⑤ 除去リストに画素があれば、その画素を全て黒(0)に変える。なければ終了。

⑥ パターン２の除去パターンでマッチングすれば⑦へ、一致しなければ次画素へ。
⑦ パターン２の非除去パターンでマッチングすれば次画素へ、一致しなければ⑧へ。
⑧ 該当画素を除去リストに追加し、次画素へ。
⑨ ⑥～⑧の処理を全画素に対して行う。
⑩ 除去リストに画素があれば、その画素を全て黒(0)に変える。なければ終了。
⑪ ①に戻る。

【マッチングコード例】

説明の為に、3x3pixで表現される１つのパターンにP0～P8の番号を振ります。

P0～P8を各2bitで表すものとし、
白bit:10, 黒bit:01, どちらでも良いものはbit:00　とします。
各列の先頭2bitに00を付加し、１バイト/列で表現すると、
１パターンは３バイトになります。

例えば、パターン１の除去パターンであれば、

ここで、ある画素を含む3x3pixの状態が次の様になっているとすると

これは、パターン１・非除去パターンの6番目とマッチします。

非除去パターン(6)は、P = 0x040A04で表現されるので

G AND P = P が成り立つ。

この論理式が成り立つ場合に、パターンマッチと認定できます。

田村の方式では、それほどパターンが多くないので、
割と簡単なコーディングで済みます。

<!DOCTYPE html>
<html>
<!-- 
// (c)Hundredsoft Corporation. 2013 All right reserved.
//
//    UTF-8で保存して下さい
-->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no" />
<title>細線化サンプル</title>

<script type="text/javascript">
//
// Zhang-Suen Algorithm
//
var zhangsuen = function(imgdata){
    var w = imgdata.width;
    var h = imgdata.height;
    var ind = imgdata.data;

    var x, y, rAry;
    var bFlag = true;

    for (var k=0; k<100 && bFlag; k++){
        if (!(k & 1)){
            bFlag = false;
        }
        rAry = new Uint8Array(ind);
        for (y=1; y<h-1; y++){
            for (x=1; x<w-1; x++){
                var i = (y*w + x)*4;
                if (rAry[i]){
                    var a,b,p1,p2,p3,p4,p5,p6,p7,p8,p9;
                    // [p9 p2 p3]
                    // [p8 p1 p4]
                    // [p7 p6 p5]
                    p1 = 1;
                    p2 = (rAry[i-w*4  ]) ? 1 : 0;
                    p3 = (rAry[i-w*4+4]) ? 1 : 0;
                    p4 = (rAry[i    +4]) ? 1 : 0;
                    p5 = (rAry[i+w*4+4]) ? 1 : 0;
                    p6 = (rAry[i+w*4  ]) ? 1 : 0;
                    p7 = (rAry[i+w*4-4]) ? 1 : 0;
                    p8 = (rAry[i    -4]) ? 1 : 0;
                    p9 = (rAry[i-w*4-4]) ? 1 : 0;
                    a = 0;
                    if (!p2 && p3){a++;}
                    if (!p3 && p4){a++;}
                    if (!p4 && p5){a++;}
                    if (!p5 && p6){a++;}
                    if (!p6 && p7){a++;}
                    if (!p7 && p8){a++;}
                    if (!p8 && p9){a++;}
                    if (!p9 && p2){a++;}
                    b = p2+p3+p4+p5+p6+p7+p8+p9;

                    if (a == 1 && 2 <= b && b <= 6){
                        if ((!(k & 1) && p2*p4*p6 == 0 && p4*p6*p8 == 0)
                         || ( (k & 1) && p2*p4*p8 == 0 && p2*p6*p8 == 0))
                        {
                            ind[i] = ind[i+1] = ind[i+2] = 0;
                            bFlag = true;
                        }
                    }
                }
            }
        }
    }
};

//
// NWG Algorithm
//
var nwg_method = function(imgdata){
    var w = imgdata.width;
    var h = imgdata.height;
    var ind = imgdata.data;

    var x, y, rAry;
    var bFlag = true;

    for (var k=0; k<100 && bFlag; k++){
        bFlag = false;
        rAry = new Uint8Array(ind);
        for (y=1; y<h-1; y++){
            for (x=1; x<w-1; x++){
                var i = (y*w + x)*4;
                if (rAry[i]){
                    var a,b,c,e,f,p0,p1,p2,p3,p4,p5,p6,p7;
                    // [p7 p0 p1]
                    // [p6    p2]
                    // [p5 p4 p3]
                    p0 = (rAry[i-w*4  ]) ? 1 : 0;
                    p1 = (rAry[i-w*4+4]) ? 1 : 0;
                    p2 = (rAry[i    +4]) ? 1 : 0;
                    p3 = (rAry[i+w*4+4]) ? 1 : 0;
                    p4 = (rAry[i+w*4  ]) ? 1 : 0;
                    p5 = (rAry[i+w*4-4]) ? 1 : 0;
                    p6 = (rAry[i    -4]) ? 1 : 0;
                    p7 = (rAry[i-w*4-4]) ? 1 : 0;
                    a = 0;
                    if (!p0 && p1){a++;}
                    if (!p1 && p2){a++;}
                    if (!p2 && p3){a++;}
                    if (!p3 && p4){a++;}
                    if (!p4 && p5){a++;}
                    if (!p5 && p6){a++;}
                    if (!p6 && p7){a++;}
                    if (!p7 && p0){a++;}
                    b = p0+p1+p2+p3+p4+p5+p6+p7;

                    if (2 <= b && b <= 6){
                        c = 0;
                        if ((p0+p1+p2+p5 == 0 && p4+p6 == 2)
                         || (p2+p3+p4+p7 == 0 && p0+p6 == 2)){
                            c = 1;
                        }
                        if (a == 1 || c == 1){
                            e = (p2+p4) * p0 * p6;
                            f = (p0+p6) * p2 * p4;
                            if ((!(k & 1) && e == 0)
                             || ( (k & 1) && f == 0)){
                                ind[i] = ind[i+1] = ind[i+2] = 0;
                                bFlag = true;
                            }
                        }
                    }
                }
            }
        }
    }
};

//
// 田村 Algorithm
//
var tamura = function(imgdata){
    // [p0 p1 p2]
    // [p3 p4 p5]
    // [p6 p7 p8]
    //
    // P[0-8]を2bitで表す。白bit:10, 黒bit:01, その他bit:00
    // 先頭にbit00を付加し、１バイト/列で１つのパターンを３バイトで表現。
    // Bit並びは、00[p0][p1][p2]00[p3][p4][p5]00[p6][p7][p8]とする。

    // 除去するパターン(1)
    var pat1  = new Array(0x040800, 0x000900);
    // 除去しないパターン(1)
    var pat1n = new Array(0x040a09, 0x182900,
                0x001908, 0x042804, 0x081900, 0x040a04, 0x001824, 0x241800,
                0x060900, 0x000906, 0x192a11, 0x190a19, 0x112a19, 0x192819);

    // 除去するパターン(2)
    var pat2  = new Array(0x000804, 0x001800);
    // 除去しないパターン(2)
    var pat2n = new Array(0x182804, 0x001a09,
                0x001908, 0x042804, 0x081900, 0x040a04, 0x001824, 0x241800,
                0x060900, 0x000906, 0x192a11, 0x190a19, 0x112a19, 0x192819);

    var w = imgdata.width;
    var h = imgdata.height;
    var ind = imgdata.data;

    var bFlag = true;
    for (var k=0; k<100 && bFlag; k++){
        bFlag = false;
        var rAry = new Uint8Array(ind);
        var pat, patn;
        if (k & 1){
            pat = pat2;
            patn = pat2n;
        }else{
            pat = pat1;
            patn = pat1n;
        }

        var x,y;
        for (y=1; y<h-1; y++){
            for (x=1; x<w-1; x++){
                var i = (y*w + x)*4;
                if (rAry[i]){
                    var f = 0x000800;

                    if (rAry[i-w*4-4]){f |= 0x200000;}
                    else              {f |= 0x100000;}
                    if (rAry[i-w*4    ]){f |= 0x080000;}
                    else              {f |= 0x040000;}
                    if (rAry[i-w*4+4]){f |= 0x020000;}
                    else              {f |= 0x010000;}
                    if (rAry[i      -4]){f |= 0x002000;}
                    else              {f |= 0x001000;}
//                    if (rAry[i        ]){f |= 0x000800;}
//                    else              {f |= 0x000400;}
                    if (rAry[i      +4]){f |= 0x000200;}
                    else              {f |= 0x000100;}
                    if (rAry[i+w*4-4]){f |= 0x000020;}
                    else              {f |= 0x000010;}
                    if (rAry[i+w*4    ]){f |= 0x000008;}
                    else              {f |= 0x000004;}
                    if (rAry[i+w*4+4]){f |= 0x000002;}
                    else              {f |= 0x000001;}

                    // 除去するパターンに一致
                    if ((f & pat[0]) == pat[0] || (f & pat[1]) == pat[1]){
                        // 除去しないパターンに一致
                        if ((f & patn[ 0]) == patn[ 0] || (f & patn[ 1]) == patn[ 1]
                         || (f & patn[ 2]) == patn[ 2] || (f & patn[ 3]) == patn[ 3]
                         || (f & patn[ 4]) == patn[ 4] || (f & patn[ 5]) == patn[ 5]
                         || (f & patn[ 6]) == patn[ 6] || (f & patn[ 7]) == patn[ 7]
                         || (f & patn[ 8]) == patn[ 8] || (f & patn[ 9]) == patn[ 9]
                         || (f & patn[10]) == patn[10] || (f & patn[11]) == patn[11]
                         || (f & patn[12]) == patn[12] || (f & patn[13]) == patn[13]){
                            ;
                        }else{
                            ind[i] = ind[i+1] = ind[i+2] = 0;
                            bFlag = true;
                        }
                    }
                }
            }
        }
    }
};

var thinning = function(pattern){
    var chk = document.getElementById('difftm')
    var cvs = document.getElementById('IDcanvas')
    var ctx = cvs.getContext("2d");
    var imgdata = ctx.getImageData(0, 0, cvs.width, cvs.height);
    var stt = new Date;
    if (pattern == 0){
        tamura(imgdata);
    }else if (pattern == 1){
        zhangsuen(imgdata);
    }else{
        nwg_method(imgdata);
    }
    chk.innerHTML = "ConvertTime:" + ((new Date) - stt) + "ms";
    ctx.putImageData(imgdata, 0, 0);
};

var init = function(filename){
    var cvs = document.getElementById('IDcanvas')
    var ctx = cvs.getContext("2d");
    var img = new Image();
    img.onload = (function(){
        ctx.drawImage(img, 0, 0);
    });
    img.src = filename;
};
</script>
</head>

<body onload="init('test.png');">
<canvas id="IDcanvas" width="512" height="512"></canvas>
<hr />
<input type="button" value="画像１" style="width:100px; height:50px;" onclick="init('test.png'); return false;">
<input type="button" value="画像２" style="width:100px; height:50px;" onclick="init('test2.png'); return false;">
<input type="button" value="画像３" style="width:100px; height:50px;" onclick="init('test3.png'); return false;">
<br />
<input type="button" value="田村" style="width:100px; height:50px;" onclick="thinning('0'); return false;">
<input type="button" value="Zhang-Suen" style="width:100px; height:50px;" onclick="thinning('1'); return false;">
<input type="button" value="NWG" style="width:100px; height:50px;" onclick="thinning('2'); return false;">

<hr />
画像を選んでから、田村 or Zhang-Suen oe NWG をクリック！<br />
（Chrome,FireFoxだと0.5秒程度ですが、IE10だと変換に5秒程度掛ります。）<br />
<br />
<div id="difftm"></div>
</body>
</html>

説明では削除リストを使っていますが、元データをTypedArray(Uint8Array)にコピーした方が早かったので、
実装では、変えています。(内容的に変わるものではありません。)

Zhang-Suen,NWG,田村で、どの方法が良いかは、入力画像によって変わるので一概には言えません。
サンプルを動かすとわかりますが、処理時間に関しては、NWGより、Zhang-Suenの方が早いです。
NWGは、Zhang-Suenの改良版であるため若干処理が増えているためです。
人間の目で見ると僅かな違いですが、NWGの方が綺麗になっているようです。

田村に関しては、サンプルの画像１・画像２では速度が劣りますが、画像３では圧倒的に早いです。
文字系では妙なひげが出やすいですが、写真等のエッジ抽出画像に対しては良い結果が出ています。

(論文発表順では、【Hilditch(1968)】→【田村(1978)】→【Zhang-Suen(1984)】→【NWG(1989)】)

今回実装していませんが、
Hilditchの方法は細線化処理の元祖とも言えますが、十分な結果が得られない場合があるらしい。
Rosenfeldは、Zhang-Suen,NWG,田村に比べ、かなり処理が重くなるらしい。
（参考： Comparing Hilditch, Rosenfeld, Zhang-Suen,and Nagendraprasad - Wang-Gupta Thinning ）

実行サンプルはこちら

IE10/Chrome/FF/Androidで、確認しています。

IE9は、TypedArray(Uint8Array)に対応していないので、削除リストを使う方式に修正する必要があります。
IE10でも、Uint8ClampedArray（飽和演算付き8bit）には対応していないので、
このサンプルでは、Uint8Arrayを使っています。
(Chrome,FFでの、ImageData.dataの型はUint8ClampedArrayです。)

このループ数になるとChromeやFFは速いですが、IEだとかなり遅いので、
画像サイズによっては、Web Workersによるマルチスレッド化を検討する必要があります。
但し、IEではImageData.dataの型(CanvasPixelArray)が異なるので、注意が必要です。

--------------- 文献 ---------------
【田村の方式】
H. Tamura: A comparison of line thinning algorithms from digital geometry viewpoint, Proc. 4th Int. Joint Conf. on Pattern Recognition, pp. 715 - 719 (1978.11)

【Zhang-Suenの方式】
Zhang, T. Y. and Suen, Ching Y., “A Fast Parallel Algorithms ForThinning Digital Patterns”,Communication of the ACM,Vol 27, No. 3,Maret 1984, pp.236-239.

【NWGの方式】
P.S.P. Wang and Y.Y. Zhang (1989). A fast and flexible thinning algo-rithm. IEEE Transactions on Computation C-38, 741–745

Tags: プログラムメモ

author : HUNDREDSOFT | - | -

Hundredsoft

Javascriptで細線化