Javascriptで細線化
プログラムメモ | 2013/10/19 Sat 21:49
| 2値化画像のラインを細線化するアルゴリズムは沢山ありますが、
ループ回数がどうしても多くなるので、javascriptでの実装例は少ないです。
ここでは、比較的高速なZhang-Suen, NWGと、田村の方式を実装してみます。
実行サンプルはこちら
Zhang-Suenのアルゴリズムは、比較的単純であるので実装し易いです。
ラスタスキャンにより画素情報を読み込み、
調査画素を含む、3x3pixの画素値に対し、3種の条件を満たしていれば、
調査画素を白(1)から黒(0)に置き換えます。
調査画素(P1)を含む、3x3pixの画素に次のように番号を振る。
条件1.
条件2.
条件3(1).
条件3(2).
まず、条件1.2.3(1)の判定を行い、条件を満たした場合、該当画素を除去リストに追加する。
全画素調査後、除去リストに画素があれば、その画素を全て黒(0)に変える。なければ終了する。
次に、条件1.2.3(2)の判定を行い、同様の処理を続ける。
以降、条件3(1)(2)を切り替えながら、条件を満たす画素がなくなるまで、繰り返し行う。
NWG (Nagendraprasad-Wang-Gupta)について は、Zhang-Suenと非常に似た処理であるため、
説明は割愛します。
詳細は、ソースコードか、
A note on the Nagendraprasad-Wang-Gupta thinning algorithm をご覧ください。
Zhang-Suenのアルゴリズムが主に計算による判定を行うのに対し、
田村のアルゴリズムは、図形のマッチングを利用します。
大まかな処理としては、
2種類のパターンがあり、それぞれのパターンは、
3x3の除去パターンと3x3の非除去パターンに分かれる。
(ここで言う除去は、白から黒への変更を意味する。)
ラスタスキャンにより画素情報を読み込み、
各画素について3x3のパターンマッチングを行う。
パターンには次のものがある。
【処理概要】
① パターン1の除去パターンでマッチングすれば②へ、一致しなければ次画素へ。
② パターン1の非除去パターンでマッチングすれば次画素へ、一致しなければ③へ。
③ 該当画素を除去リストに追加し、次画素へ。
④ ①~③の処理を全画素に対して行う。
⑤ 除去リストに画素があれば、その画素を全て黒(0)に変える。なければ終了。
⑥ パターン2の除去パターンでマッチングすれば⑦へ、一致しなければ次画素へ。
⑦ パターン2の非除去パターンでマッチングすれば次画素へ、一致しなければ⑧へ。
⑧ 該当画素を除去リストに追加し、次画素へ。
⑨ ⑥~⑧の処理を全画素に対して行う。
⑩ 除去リストに画素があれば、その画素を全て黒(0)に変える。なければ終了。
⑪ ①に戻る。
【マッチングコード例】
説明の為に、3x3pixで表現される1つのパターンにP0~P8の番号を振ります。
P0~P8を各2bitで表すものとし、
白bit:10, 黒bit:01, どちらでも良いものはbit:00 とします。
各列の先頭2bitに00を付加し、1バイト/列で表現すると、
1パターンは3バイトになります。
例えば、パターン1の除去パターンであれば、
ここで、ある画素を含む3x3pixの状態が次の様になっているとすると
これは、パターン1・非除去パターンの6番目とマッチします。
非除去パターン(6)は、P = 0x040A04で表現されるので
G AND P = P が成り立つ。
この論理式が成り立つ場合に、パターンマッチと認定できます。
田村の方式では、それほどパターンが多くないので、
割と簡単なコーディングで済みます。
説明では削除リストを使っていますが、元データをTypedArray(Uint8Array)にコピーした方が早かったので、
実装では、変えています。(内容的に変わるものではありません。)
Zhang-Suen,NWG,田村で、どの方法が良いかは、入力画像によって変わるので一概には言えません。
サンプルを動かすとわかりますが、処理時間に関しては、NWGより、Zhang-Suenの方が早いです。
NWGは、Zhang-Suenの改良版であるため若干処理が増えているためです。
人間の目で見ると僅かな違いですが、NWGの方が綺麗になっているようです。
田村に関しては、サンプルの画像1・画像2では速度が劣りますが、画像3では圧倒的に早いです。
文字系では妙なひげが出やすいですが、写真等のエッジ抽出画像に対しては良い結果が出ています。
(論文発表順では、【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: プログラムメモ
ループ回数がどうしても多くなるので、javascriptでの実装例は少ないです。
ここでは、比較的高速なZhang-Suen, NWGと、田村の方式を実装してみます。
実行サンプルはこちら
Zhang-Suenのアルゴリズムは、比較的単純であるので実装し易いです。
ラスタスキャンにより画素情報を読み込み、
調査画素を含む、3x3pixの画素値に対し、3種の条件を満たしていれば、
調査画素を白(1)から黒(0)に置き換えます。
調査画素(P1)を含む、3x3pixの画素に次のように番号を振る。

条件1.
外周一周を眺めた時、
(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 )
条件2.
外周の加算(白なら+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 )
条件3(1).
P2 x P4 x P6 = 0 かつ、P4 x P6 x P8 = 0 を満たす。
条件3(2).
P2 x P4 x P8 = 0 かつ、P2 x P6 x P8 = 0 を満たす。
まず、条件1.2.3(1)の判定を行い、条件を満たした場合、該当画素を除去リストに追加する。
全画素調査後、除去リストに画素があれば、その画素を全て黒(0)に変える。なければ終了する。
次に、条件1.2.3(2)の判定を行い、同様の処理を続ける。
以降、条件3(1)(2)を切り替えながら、条件を満たす画素がなくなるまで、繰り返し行う。
NWG (Nagendraprasad-Wang-Gupta)について は、Zhang-Suenと非常に似た処理であるため、
説明は割愛します。
詳細は、ソースコードか、
A note on the Nagendraprasad-Wang-Gupta thinning algorithm をご覧ください。
Zhang-Suenのアルゴリズムが主に計算による判定を行うのに対し、
田村のアルゴリズムは、図形のマッチングを利用します。
大まかな処理としては、
2種類のパターンがあり、それぞれのパターンは、
3x3の除去パターンと3x3の非除去パターンに分かれる。
(ここで言う除去は、白から黒への変更を意味する。)
ラスタスキャンにより画素情報を読み込み、
各画素について3x3のパターンマッチングを行う。
パターンには次のものがある。

【処理概要】
① パターン1の除去パターンでマッチングすれば②へ、一致しなければ次画素へ。
② パターン1の非除去パターンでマッチングすれば次画素へ、一致しなければ③へ。
③ 該当画素を除去リストに追加し、次画素へ。
④ ①~③の処理を全画素に対して行う。
⑤ 除去リストに画素があれば、その画素を全て黒(0)に変える。なければ終了。
⑥ パターン2の除去パターンでマッチングすれば⑦へ、一致しなければ次画素へ。
⑦ パターン2の非除去パターンでマッチングすれば次画素へ、一致しなければ⑧へ。
⑧ 該当画素を除去リストに追加し、次画素へ。
⑨ ⑥~⑧の処理を全画素に対して行う。
⑩ 除去リストに画素があれば、その画素を全て黒(0)に変える。なければ終了。
⑪ ①に戻る。
【マッチングコード例】
説明の為に、3x3pixで表現される1つのパターンにP0~P8の番号を振ります。

P0~P8を各2bitで表すものとし、
白bit:10, 黒bit:01, どちらでも良いものはbit:00 とします。
各列の先頭2bitに00を付加し、1バイト/列で表現すると、
1パターンは3バイトになります。
例えば、パターン1の除去パターンであれば、

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

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

非除去パターン(6)は、P = 0x040A04で表現されるので
G AND P = P が成り立つ。
この論理式が成り立つ場合に、パターンマッチと認定できます。
田村の方式では、それほどパターンが多くないので、
割と簡単なコーディングで済みます。
細線化サンプル
画像を選んでから、田村 or Zhang-Suen oe NWG をクリック!
(Chrome,FireFoxだと0.5秒程度ですが、IE10だと変換に5秒程度掛ります。)
説明では削除リストを使っていますが、元データをTypedArray(Uint8Array)にコピーした方が早かったので、
実装では、変えています。(内容的に変わるものではありません。)
Zhang-Suen,NWG,田村で、どの方法が良いかは、入力画像によって変わるので一概には言えません。
サンプルを動かすとわかりますが、処理時間に関しては、NWGより、Zhang-Suenの方が早いです。
NWGは、Zhang-Suenの改良版であるため若干処理が増えているためです。
人間の目で見ると僅かな違いですが、NWGの方が綺麗になっているようです。
田村に関しては、サンプルの画像1・画像2では速度が劣りますが、画像3では圧倒的に早いです。
文字系では妙なひげが出やすいですが、写真等のエッジ抽出画像に対しては良い結果が出ています。
(論文発表順では、【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 | - | -