アルゴリズムの超おおざっぱなメモ

探索木

• 幅優先探索：キュー(FIFO)
• 深さ優先探索：スタック(LIFO)
• 順位優先探索：ヒープ（順序付きキューでも可）

二分木

• 二分木：子はたかだか２つ
• 二分探索木：子はたかだか２つ、左子<親<右子
• 完全二分木：子はたかだか２つ、かつ偏りがない
• ヒープ木：完全二分木、かつ頂点は最小値

クラスの話

• P：決定性（deterministic）アルゴリズムを使って多項式（Polynomial）時間で解ける問題
• NP：非決定性（Nondeterministic）アルゴリズムでうまくいくと多項式（Polynomial）時間で解ける問題
判定問題
• NP困難：多項式時間で解けない
巡回セールスマン問題(TSP)とか、いわゆる最適化問題
• NP完全（難しいかどうかわからない問題）：NP困難でNPに属しているもの
論理式の充足可能性問題(SAT)とか

Algolithm noteてゆうサイトがいい感じだった

[MacOSX;OpenCV＋OpenGL+ARToolKit]メモ

とりあえず、しょっちゅう引っかかるのでメモっとく

OpenCV

「OpenCV プログラミングブック」を買った人がはまる罠

---

cvCreateCameraCapture( -1 ) -> ダメ、カメラが見つからないといわれる
cvCreateCameraCapture( CV_CAP_ANY )

---

OpenCVのMakefile

---

CXX = g++ -Wall -O2
CXXFLAGS = `pkg-config --cflags opencv`
LDFLAGS = `pkg-config --libs opencv`

.cpp:
[Tabコード]$(CXX) $@.cpp $(CXXFLAGS) $(LDFLAGS) -o $@

---

とすると、「test.cpp」をコンパイルするときは「make test」でできる。

OpenGL

OpenGLのMakefile

---

CC = gcc -Wall -O2
FRAMEWORKS = -framework OpenGL -framework GLUT -framework Foundation

.c:
[Tabコード]$(CC) $@.c $(FRAMEWORKS) -o $@

---

とすると、「test.c」をコンパイルするときは「make test」でできる。

OpenGLのヘッダファイル

---

GL/glut.h -> GLUT/glut.h
GL/glu.h -> OpenGL/glu.h
GL/gl.h -> OpenGL/gl.h

---

windowsようのOpenGLの参考書を使うとはまる、こんな罠で半日つぶした俺orz

ARToolKit

Marker_infoの中身

---

area：ラベリングされたピクセル数、つまりマーカの面積（？）
id：マーカのID
dir：マーカの角度を0~3で表す？arGetTransMat()で使う大切な数字らしい
double cf：一致度
double pos[2]：マーカの中心位置
double line[4][3]：マーカの周りのlineの
double vertex[4][2]：マーカの四隅の位置（？）

---

[OpenCV]視差画像のテスト 2

先日に引き続き、巫女さんにてつだってもらった

Pixel-to-Pixel Stereoではピクセル間の距離をはかっているらしいので、こんどは距離が短くなるように平行移動の距離を短くしてみた、あとカメラはRICHO製のデジカメを使用して画質アッップ、ピクセル間の違いが大きい方がいいのかどうか先鋭化をした画像も試してみた。