楽譜アーカイブアプリ - その17 細線化の続き

昨日細線化を検討して、微妙なところのある難しい問題だと言うことはわかった。じゃあどうする、というのを考える。

7.2  細線化アルゴリズムの検討

細線化のアルゴリズムを自分で考えてもいいんだけど今回特にこれが目的ではないので、一般的な手法を勉強させてもらうことにする。

さっきも書いたけど細線化のアルゴリズムは本当に星の数ほどある。ネットで「細線化」や「Thinning」などで検索すると大量にヒットするし文献検索でもいまだに毎年何本もの論文が出ていることがわかる。比較的新しいアルゴリズムはその論文を手に入れないとわからないが、ネットで簡単に手に入るアルゴリズムは実装が大変なのが多い。つまり、多くの場合分けをして、しかも周り8個の近傍をパターン分けして、網羅的にあるパターンに合致する場合は消して、それ以外は残して、などという表現になっている。

いくつか僕も試してみたけど、その網羅的なパターンをコピーするときにどこか間違うらしくて対称に細くなっていかなかったり、一気に全部消えてしまったりする。どこが間違ってるのか見る気もしなくなってしまう。

まず、実装したソースを示してくれているだけのところはパスする（ソースをコピペすることしかできなくてブログの趣旨に反する）ことにして、アルゴリズムを説明してくれているところを参考にさせてもらった。

例えばここで解説してくれているアルゴリズムは異なる20のパターンを検査する必要がある。パターンの数が多くてなぜこのパターンの組を使うのかよくわからないのと、「フローチャート」としてあげてくれている図が僕にはよく理解できない。「パターン2」に該当して取り除いた場合に「パターン1」に戻っているが、取り除いたらその時点で何もすることはなくなるような気がする。

またここも丁寧に説明してくれているのだけど、やはりどこかで間違ったみたいでその通りになってくれない。

ほかのサイトも大量のパターンの場合分けをするのが多くて、なぜそのパターン分けをするのかが納得できないせいで、なかなかわかった気になれない。Moore近傍を使うなら異なるパターンの数は256通りあるけど、スキャンが2方向の場合には128通り、4方向の場合には64通りになる。これなら全パターンをニューラルネットに入力して望ましい細線化ができるように学習させました、といって全パターンの場合分けを示してくれる方がわからなさ加減は同じでも納得はしやすいかもしれない。

強調しておくけど、決してこれらのサイトが悪い、と言っているのではなく、僕の理解力や注意力集中力と実装能力が低くてどこかを間違ってしまって、説明された通りにできていないのが問題なのである。これらの親切な方々に非は全くない。

ということで親切な方々に心の中でお礼を言って、僕にもできるアルゴリズムを探すことにした。 その基準は

• 画素スキャンに依存するアルゴリズムではなく、全画素一括して処理する
• 画素を残すあるいは消す条件が式で書いてある
• 結果の出来具合や効率は問わない

ということにした。その理由は

7.2.1  画素スキャンに依存するアルゴリズムではなく、全画素一括して処理する

最終的な実装は一画素ごと順番に見ていくことになるので、見ては書き換えて次の画素にいくというアルゴリズムになっている方が効率的でメモリの消費も少ない。ところがこの場合、一方向からのスキャンでは対称な形にならず、必ず2方向（上からと下から）、あるいは4方向（右上、左下、右下、左上からそれぞれ）のスキャンをする必要がある。当然それぞれで検査パターンを回転したり反転する必要がある。これが間違いの元になる。それよりは全画素同時に判断してその次のフェーズで画素の処理をする先日のライフゲーム（Conway's Game of Life）のような2次元のセルオートマトンとして実装できる方が効率は悪いけど簡単になる。

一方で、全画素同時型はMoore近傍を対象にしていると2画素幅の腺を消してしまう。この対策が盛り込まれている必要がある。

7.2.2  画素を残すあるいは消す条件が式で書いてある

また、画素書き換えの条件がパターンの列挙になっているとそれをプログラムにするときに間違いやすい。とくにそのパターン数が多いときはデバグを投げてしまいかねない。おかしな式であっても、パターンの網羅ではなくて条件が理解できるほうが実装するときに間違いが少ない。また、式だと誤解も少ない。

7.2.3  結果の出来具合や効率は問わない

どうしても効率を考えると中途半端に式で表されているよりパターンをすべてチェックするようなアルゴリズムの方が速いし、メモリの使用量も少なくてすむ。ということで効率に関するメリットがあったとしても、上の2条件に合致しないアルゴリズムは遠慮する、ということにする。

ということで、以上の条件に合うアルゴリズムをこれから探す。