楽譜アーカイブアプリ - その18 細線化アルゴリズムの検討 [考え中の問題]
3日前の記事で、僕にもできそうな細線化のアルゴリズムを探すことにした。昨日はPowerBook G4を看取ったあと、ウェブに上がっている細線化のアルゴリズムを探した。
このアルゴリズムは図-7.3の、P1の画素を消去するかどうかを、P2からP9までのMoore近傍の画素と、さらにその外のP11とP15の状態を使って決める。
その条件とは画素が描かれている状態を1、消去された状態を0として
のすべての条件が満たされたとき、画素P1を消去する（0にする）。というもの。ただし、ここでnを1〜9あるは11、15としてpnを画素Pnの値（0あるいは1）であるとする。また、A(P1)は周りの画素P2からぐるっと回ってP9でさらにP2に戻ったとき、0があってその次に1が来る回数で、B(P1)というのはP2からP9の中の1の画素の数。
全画素一括処理のアルゴリズムなので2画素幅の線の問題があるが、それをMoore近傍の8画素に加えてそのさらに上と右にふたつ離れた2個の画素の情報も使った4番目と5番目の条件で解決している。
アルゴリズムの詳細は、もとのpdfを見てもらった方が手っ取り早い。
図中上が、僕がHPの複合機で読み込んだ五線譜の一部で、2値化してある。汚いけど僕の持ってる楽譜の中では比較的条件のいい方。そして下がそれをこのMAで細線化したもの。五線譜の細線化にはこれで十分という感じ。しかし、付点音符の点も1ドットの点として残っている。今回の場合、細線化の時点ではなくなってくれたほうがいい。詳しく見てみると、
テスト用の実装なのでエクスキューズ付きだけど、1000×2500画素ぐらいのページを細線化するのに秒を超える時間がかかった。実際にやるときには、結局効率が問題になるかもしれない。
7.3 採用したアルゴリズム
先日の方針でネットで見ることのできる都合10本近くのアルゴリズムを確認した。その中からこれの中にあるMA（Modified Algorithm）というのを使わせてもらうことにした。これは1988年の論文なので非常に古い部類だけど、上の条件に合致する。これにはなんでそのアルゴリズムでうまくいくのかをRDというアルゴリズムとの対比で書かれているので参考になる。めちゃわかりにくいけど。このアルゴリズムは図-7.3の、P1の画素を消去するかどうかを、P2からP9までのMoore近傍の画素と、さらにその外のP11とP15の状態を使って決める。
全画素一括処理のアルゴリズムなので2画素幅の線の問題があるが、それをMoore近傍の8画素に加えてそのさらに上と右にふたつ離れた2個の画素の情報も使った4番目と5番目の条件で解決している。
アルゴリズムの詳細は、もとのpdfを見てもらった方が手っ取り早い。
7.4 アルゴリズムのテスト
とりあえず、アルゴリズムの検証のためにさく、っとテストプログラムを書いて五線譜を読ませてみたのが図-7.4。- ゴミ（1ドットの孤立点）は残る
- 2n ×2nドット正方形の領域は消えてなくなる
- (2n+1) ×(2n+1)ドット正方形の領域は孤立点として残る
- ドット1列でも違う長方形は残る
- 角っこが欠けたような正8角形のような領域も孤立点として残る
- ドーナッツのような多重連結性は保存される
テスト用の実装なのでエクスキューズ付きだけど、1000×2500画素ぐらいのページを細線化するのに秒を超える時間がかかった。実際にやるときには、結局効率が問題になるかもしれない。
2010-12-19 21:52
nice!(0)
コメント(2)
トラックバック(0)
少し小旅行をしていて不在してました。
ギターは、ブラジルバリサンドル（ブラジル産ハカランダ）、ローズウッド（インド産）が主要原料ですが、ハカランダはワシントン条約にかかり、生の木材では今は輸入できなくなったはずです。
インドネシアで生産しているギターは、合板の安価なものばかりです。ヤマハも手工ギターは国内で作っているようです。
以前、ヤマハのギター開発に携わった方からお話しを聞いたことがありましたが、何もしらないサラリーマンがお金はいくらでも出すので、スペイン製のギターと同じ品質のものを作れといわれ、ラミレスを１台解体し、アグアドのレントゲンをとって研究したそうです。でも、技術指導にきた、アグアドは、５時に帰る奴らに、ギターはできない。魂がこもっていないからだといわれたそうです。
結局、ヤマハのギターは、そこそこの品質まで行きつきましたが、世界一の名器になることはなかったですね。
by エトワール (2010-12-19 23:50)
ハカランダはワシントン条約ですか。ピアノ以外の弦楽器は木が命なのでつらいですね。
楽器をバラシやレントゲンのリバースエンジニアリングで作れるようになるとは僕にはとても思えません。いかにも楽器をテレビやCDプレーヤと同じ工業製品とみなしていたということがわかるエピソードですね、そんなことがあったというのはまったく知りませんでした。いずれにしても当時のヤマハの人たちが5時に帰れたとは思えませんが。
ヤマハは巨大な楽器メーカになって有名オーケストラの楽器メンテナンスとかもやってますが、あらためて考えると得意なのはピアノ金管楽器フルートサックスと何種類かの打楽器で、弦楽器木管楽器はありません。そう考えると、結局「木」が問題だったんでしょうか．．．
by decafish (2010-12-20 20:51)