Home

TOYOZUMI Kouichi edited this page Jun 8, 2014 · 7 revisions

KOMADORI

概要

KOMADORIはCommon Lisp用の画像処理ライブラリです。

豊富な関数とマクロにより、高速に動作する実行用コードを生成する画像処理プログラムを簡潔に記述することができます。

動作環境

以下の環境で動作が確認されています。

  • OS X 10.9 Marbericks
  • 3.4 GHz Intel Core i7
  • 24GB 1600MHz DDR3

また、開発にはEmacs上で最新のQuicklisp経由で取得したSLIMEを用いています。

注意点

KOMADORIは開発中のプログラムであり、その動作は極めて不安定であり、動作の安定を保証する自動テスト等の仕組みは何一つ導入されていません。

仕様も大きく変わる可能性があります。

導入

依存ライブラリの入手

KOMADORIは以下のライブラリに依存していますので、入手しておいてください。なお、この依存先はQuicklispから取得するものを除いています。

  • L4S
  • tsugumi
  • com.filmassembler.labs.commonlisp.utilities
  • cl-simd
    • ブランチをfeature/sse3and4.1に切り替える必要があります
    • CL-SIMDのコード中にはSB-C::COMMUTATIVE-ARG-SWAPを使用している部分がありますが、この関数は最近廃止されており、CL-SIMDが更新されていないため、これをCL-SIMD内部に転記して暫定対応しています。現状のMayakaにはユニットテストがないため、完全な試験を行えておらず、予期していない問題が起きる可能性があります。

入手

以下のGitレポジトリをチェックアウトしてください。

https://github.com/TOYOZUMIKouichi/Mayaka.git

SBCL

KOMADORIは現時点でSBCL(Steel Bank Common Lisp)上で動作します。しかし、通常のSBCLのビルドでは動作しない部分が多々あるため、必ず自らビルドしてください。SBCLでセルフブートストラップを行うことは難しいので、まずはHomebrewやMacPortsといったお気に入りのパッケージシステムあるいはSBCLのサイトから直接バイナリを落としてインストールしてください。

次に最新のSBCLをソースコードからビルドする作業に移りますが、その前にビルドオプションを設定する必要があります。KOMADORIはマルチスレッドとSSE(Streaming SIMD 拡張命令)を使用しますので、その機能をビルドに含める必要があります。

https://gist.github.com/TOYOZUMIKouichi/8192448

また、OS XでSBCLをビルドすると、ユニットテストの実行時にエラーが発生することが確認されています。以下のDiffはその問題への対応方法です。

https://gist.github.com/TOYOZUMIKouichi/8157211

SBCLをビルドし、インストールするために、以下に記すコマンドを実行してください。

sh make.sh
sudo sh install.sh

Quicklispと実行用コア

必要ないくつかのライブラリを導入するためにQuicklispを使います。以下に示すスクリプトはSBCLの起動時に利用できる実行用コアを生成します。

https://gist.github.com/TOYOZUMIKouichi/8192468

このスクリプトは~/CommonLisp/core.sbclに実行用コアを生成します。適宜修正して使いやすいところに生成するようにすることをおすすめします。

ASDFの準備

自分のasdf:*central-registry*に登録してあるディレクトリにmayaka.asdl4s.asdcom.filmassembler.labs.commonlisp.utilities.asdtsugumi.asdおよびcl-simd.asdへのシンボリックリンクを張ることを忘れないでください。

実行

SBCLに作成した実行コアを読み込ませながら起動して、Mayakaパッケージをロードすれば、KOMADORIを使うことができます。

$ /usr/local/bin/sbcl --noinform --core ~/CommonLisp/core.sbcl
* (require :mayaka)    

参考資料

  • 手引き やっつけ仕事で作ったcl2markdownで自動生成しているため、一部壊れています。ご了承ください。
  • 入門

よくある、あるいは予想される質問と回答

動作

SBCL以外のCommon Lisp処理系では動作しないのですか?

SBCL固有の機能を多用しているため、SBCL以外のCommon Lisp処理系では動作しません。

OSX以外の環境では動作しないのですか?

試していないのでわかりません。

再帰がなにか変です

内部でインライン展開しているため、再帰を行うと確実に破綻する部分があります。例えばMAP-IMAGE1MAP-IMAGE2はその典型例です。また、DEFUNSAFEもインライン展開を行います。DEFUNを使い、またMAP-IMAGE1MAP-IMAGE2は接頭辞P-C-をつけた最適化を行わない版を試してください。

PRINTFORMATで標準出力への出力ができません

たまに起きます。その出力を埋め込んだ関数の外側で別の出力をしてやると出せるかもしれません。

TIMEが正常に動作しません

コンパイラマクロを利用している場合、TIMEはコンパイラマクロの処理時間を計測に含めないので、正確な実行時間が計測されないことがあります。また、原因不明でTIMEが動作しないということも確認されています。その場合、FLOATING-POINT-INEXACTが出ます。

DEFUNSAFE-がなぜかPROGNに化けます

起きることは確認していますが、原因不明です。とりあえずDEFUNにコンパイルオプションをつけることで当座を凌いでください。

DEFINE-COMPILER-MACROの後、SLIMEの補完がおかしくなります

原因不明です。とりあえずDEFINE-COMPILER-MACROの行だけコメントアウトして、最後に外す、という方法で今のところ対処しています。

わけのわからないエラーがでます

ごめんなさい。

MayakaはSBCLの内部機能をかなり使っているため、原因不明のエラーが出ることがあります。お手数ですが発生したコードを送っていただければ見るだけ見て見ます。対応は期待しないでください。

そのほか何か、明言されていない異常があります

お手数ですがk-toyozumi@filmassembler.comまでご連絡いただけると幸いです。ただし対応をお約束するものではありません。

一般

KOMADORIってなんですか?

Common Lispの画像処理ライブラリと考えておけばまず間違いありません。

ライセンスはどうなっていますか?

ソースコードといくつかの文書は修正BSDライセンスで提供されています。著作権は豊住耕一および東京電機大学ビジュアルコンピューティング研究室にあります。著作権表記は以下に示します。

Copyright 2010-2014 TOYOZUMI Kouichi at Tokyo Denki University, Visual Computing Laboratory.

なお、 入門の著作権は別であり、これは独占的に提供しているものです。

連絡先はどちらですか?

k-toyozumi@filmassembler.comにお願いします。

なぜKOMADORIなのですか?

そもそもKOMADORIは映像処理を行うために開発されており、一コマずつ手作業で処理するのが億劫でしかし既存の映像処理アプリケーションでは手が足りないときに使うために開発されています。一コマずつ処理して仕上げる、「コマ撮り」の意味です。

KOMADORIの長所はなんですか?

画素を直接操作するレベルのプログラムを簡潔に実装でき、またそのプログラムが高速に動作することです。また汎用プログラミング言語であるかつ動的プログラミング言語でありかつマルチパラダイムプログラミング言語であるCommon Lispの上に実装されているので、言語間ブリッジなどを使わずに実用的で大規模なプログラムを書くことができます。

なぜCommon Lispなのですか?

マクロを利用して、簡単に最適化を行えるためです。これがないと、KOMADORIの実行速度を得ることができません。また実装言語がCommon Lispである理由はKOMADORIの長所でもあります。

言語X、ライブラリYとどちらが速いですか?

様々な条件に左右されるためはっきりとしたことは言えません。但し、テスト上ではCを上回る速度を示す場合もあります。

L4Sってなんですか?

KOMADORIの最適化の基礎部分を提供しているライブラリです。

tsugumiってなんですか?

KOMADORIが画像を読み書きする際に使うCで書かれたライブラリです。

Mayakaってなんですか?

KOMADORIの現在の中核部分です。KOMADORIのコンセプトは以前MagicNumberという別の実装で作られていましたが、その後SIMD演算を導入した新たな実装BUDDYが作られ、さらにその後最適化機能を大幅に強化し機能を充実させ新しい中核が作られました。それがMayakaです。

なぜMayakaなのですか?

Mayaka: A Yet Another Kernel from Asahi-choの再帰的頭字語で、「旭町から来たもう一つの中核」の意味です。東京都足立区千住旭町で開発されたため、この名前になっています。

なぜほぼ全ての文字列が日本語なのですか?

自分のために作ったからであり、自分は日本語が一番わかりやすいからです。

実装

名前やエラーメッセージの英語がおかしいです

ごめんなさい。

コード規約はありますか

特に文書化はしていませんが緩やかなルールに基づいて書いてます。ただし、未だ発展途上のため、統一されていない部分が数多くあります。

いくつかのコンパイラノートが抑制されているのはなぜですか?

GENERICから逃れる作業をしていない、いくつかの実装部において、コンパイラノートが大量に出現することを回避するために抑制しています。

最適化処理について教えてください

主にインライン展開、型宣言付加、配列境界検査の排除、SIMD演算の利用、評価時期の最適化を行っています。

現在の実装については、コードを読むのが一番早いと思われます。可能な限り文書化文字列を埋め込んでいますし、コメントも書いてあり、すべて日本語です。

以前の実装についてはいくつかの論文を発表しています。

  • Kouichi Toyozumi, Kazuki Kumagai, Tokiichiro Takahashi, "LIC:A Domain-Specific Language for Video and Image Processing", IWAIT(International Workshop on Advanced Image Technology) 2012, 143 (2012).
  • 豊住耕一, 熊谷一樹, 高橋時市郎, "動画像処理のための動的プログラミング環境の開発", 映像表現フォーラム 2011 (2011).
  • 豊住耕一, 熊谷一樹, 高橋時市郎, "動画像処理のパラメタ決定支援ツールとその高速化の検討", 第10回情報科学技術フォーラム, 6L-5 (2011).
  • 豊住耕一, 高橋時市郎, "拡張演算命令を用いた画像処理用ドメイン固有言語LICの高速化", 第11回情報科学技術フォーラム, 4J-1 (2012).

論文タイトルにあるLICってなんですか?

Lisp Image Composerの略です。論文を発表する際に名前がどうしても必要だというのと、MagicNumberだと混同を招くというので、取りあえずつけた名前ですが、趣味に合わないので所謂黒歴史となりました。

ドメイン固有言語ではなかったのですか?

昔はその気配があったのですが、よりCommon Lispの標準のように使えるようにしていった結果、普通にCommon Lispのライブラリとしてしまっても問題ない様子になったのでとりあえずそう呼んでいないだけです。