読者です 読者をやめる 読者になる 読者になる

2次元との戦い

日記

画像処理を利用したプログラムの開発をしているのだけど、ある認識のためにたくさんの手法を実装しては試すということを繰り返していて、画像処理という手法そのものの限界というか拘束性みたいなものを強く感じることとなった。
そもそも画像処理というのは、人間の視覚を模して作られた2次元のセンサに入る光をRGBに分解して利用して出力を得るという物であり、その生のデータはそのままの状態では実はものすごく限られた情報なのだ。人というのは、ある絵というか視覚情報を得ると、その対象に対する色々な情報をあっという間に脳内に組み立ててしまう。2次元の絵があるとつい、その感覚でこれは簡単に識別出来ると思ってしまうのだが、実際はそこのメタ情報を前提としてしまっていて、これがなかなか簡単にはプログラムに落とし込めないのである。
ここにピークが出るからと言って安易に閾値を採用し環境の変化に大変弱いプログラムを作ることになり、まぁかくも世の中の見えるものとははかないのだな、みたいな仏教的感想を得られるのである。

以下追記(2012年11月10日)

先日オライリーアルゴリズムクイックリファレンスをちらっと見たところ、上で悩んでた状況の大半はアルゴリズムの問題だったのでは……という気付きを得た。ずっとこの絵が苦手で近寄らなかったのだけど、人生を損してました。でも貧乏ゆえまだ買ってない。目次*1を見ればわかるんだけど、リファレンスって銘打ってるけど、実際はアルゴリズムについての割と普通の技術書ぽい。
アナログ入力のセンサの値を見て状態を判断するというのにも使えそうなので、ちゃんと勉強しておきたい。いやはやアルゴリズムってのは探索とソートだけではなかったんですね……反省。

アルゴリズムクイックリファレンス
George T. Heineman Gary Pollice Stanley Selkow
オライリージャパン
売り上げランキング: 89341

目次
まえがき

第I部
1章 アルゴリズムは大事だ
    1.1 問題を理解せよ
    1.2 必要なら実験しろ
    1.3 救援のためのアルゴリズム
    1.4 ついでの話
    1.5 この話の教訓
    1.6 参考文献

2章 アルゴリズムの数学
    2.1 問題インスタンスのサイズ
    2.2 関数の成長率
    2.3 最良、平均、最悪時の分析
    2.4 性能でグループ分けする
    2.5 異種の演算の混合
    2.6 ベンチマーク
    2.7 最後に一言
    2.8 参考文献

3章 パターンとドメイン
    3.1 パターン――コミュニケーションの言語
    3.2 アルゴリズムのパターン形式
    3.3 疑似コードのパターン形式
    3.4 設計形式
    3.5 評価実験の形式
    3.6 ドメインアルゴリズム
    3.7 浮動小数点計算
    3.8 手動メモリ割り付け
    3.9 プログラミング言語を選ぶ
    3.10 参考文献

第II部
4章 整列アルゴリズム
    4.1 概観
    4.2 挿入ソート
    4.3 中央値ソート
    4.4 クイックソート
    4.5 選択ソート
    4.6 ヒープソート
    4.7 数え上げソート
    4.8 バケツソート
    4.9 整列アルゴリズムの選択基準
    4.10 参考文献

5章 探索
    5.1 概観
    5.2 逐次探索
    5.3 二分探索
    5.4 ハッシュに基づいた探索
    5.5 二分木探索
    5.6 参考文献

6章 グラフアルゴリズム
    6.1 概観
    6.2 深さ優先探索
    6.3 幅優先探索
    6.4 単一始点最短経路
    6.5 全対最短経路
    6.6 最小被覆木アルゴリズム
    6.7 参考文献

7章 AIにおける経路発見
    7.1 概観
    7.2 深さ優先探索
    7.3 幅優先探索
    7.4 A*探索
    7.5 比較
    7.6 ミニマックス
    7.7 NegMax
    7.8 アルファベータ法

8章	ネットワークフローアルゴリズム
    8.1 概観
    8.2 最大フロー
    8.3 二部マッチング
    8.4 増加道についての考察
    8.5 最小コストフロー
    8.6 積み替え
    8.7 輸送
    8.8 割り当て
    8.9 線形プログラミング
    8.10 参考文献

9章 計算幾何学
    9.1 概観
    9.2 凸包走査
    9.3 線分走査法
    9.4 最近傍質問
    9.5 範囲質問
    9.6 参考文献

第III部
10章 他のすべてがうまくいかなかったとき
    10.1 主題の変形
    10.2 近似アルゴリズム
    10.3 オフラインアルゴリズム
    10.4 並列アルゴリズム
    10.5 乱択(Randomized)アルゴリズム
    10.6 間違うかもしれないがその確率を減少させたアルゴリズム
    10.7 参考文献

11章 結び
    11.1 概観
    11.2 原則:汝のデータを知れ
    11.3 原則:問題を小さく分割せよ
    11.4 原則:正しいデータ構造を選べ
    11.5 原則:性能を上げるにはストレージを追加せよ
    11.6 原則:解が明らかでないなら、探索を構築せよ
    11.7 原則:解が明らかでないなら、解を持つ別の問題に帰着させよ
    11.8 原則:アルゴリズムを書くのは難しい、アルゴリズムを試験するのはもっと難しい

第IV部
付録 ベンチマーク
    A.1 統計の基礎
    A.2 ハードウェア
    A.3 例
    A.4 報告
    A.5 精度

索引
訳者あとがき