□Data
☆meta data
メタデータ
データについての情報を記述したデータ
目的のデータを探し出す手助けとするために作成
☆文字コード
◎概念
◆符号化文字集合
CCS: Coded Character Set
文字コードで表現可能な文字の範囲
※代表的な日本語の符号化文字集合
1. JIS X0201 + 0208 + 0212
⇒ISO-2022-JP, Shift JIS, EUC-JPが用いる
ASCII文字、日本語文字、少数の記号
2. UCS (ISO-10646)
⇒Unicodeの文字集合。日本語を含む各国語含まれる
◆エンコーディング
CES: Character Encoding Scheme
文字を実際のバイト列に落とすときの計算式
＿◇ワイドキャラクタ
wide character
全ての文字に対して同じバイト数を使う
⇒処理が簡単
※libcにはANSI Cで規定されているワイドキャラクタ文字列APIが含まれる。
＿◇マルチバイトキャラクタ
multibyte character
文字の種類によって使うバイト数を変える
⇒保存や転送の効率が良い
＿◇文字コードへの対処方法
①文字コード決めうち
簡単だが、用途限定される
②適当に推測
Unicode含めると現実的ではない
③文字コード名を受け渡す
今のところいつもできるわけではない
※GNU libcには相互変換のための iconv ライブラリが含まれる。
※鬼車
EUC-JP, Shift JIS, UTF-8対応の正規表現ライブラリ
Perl5拡張含む
http://www.geocities.jp/kosako3/oniguruma/
◆多言語化
multilingualization
処理対象にする文字コードを増やす
※M17N
◆地域化
localization
プログラムの動作を地域の慣習に合わせる
※L10N
◆国際化
internationalization
実行時に対応地域を切り替えられるように作る
※I18N
※gettext
プログラムのメッセージを国際するためのライブラリ
http://www.gnu.org/software/gettext/
＿◇ロケール
locale
国と言語と文字コードの組み合わせ
例）
ja_JP.eucJP
ja 日本語
JP 日本
eucJP EUC-JP文字コード
※環境変数
LANG
LC_ALL
LC_TIME
などで指定する
※setlocale(3)により、ライブラリ関数の挙動がロケールにあわせて変化する
printf(3)
scanf(3)
strtol(3)
strftime(3)
など
◎ASCII
7bit ASCII
ANSIが1963年にデータ交換用の標準文字コードして規定したもの
⇒ANSI X3.4-1986
0x00~0x1F 通信制御用
0x20 SPACE
0x21~0x2F 記号
0x30~0x39 数字
0x3A~0x3F 記号
0x40 @
0x41~0x5A A-Z
0x5B~0x60 記号
0x61~0x7A a-z
0x7B~0x7E 記号
0x7F DEL
0x00 NULL
0x09 HT
0x0A LF
0x0B VT
0x0C FF
0x0D CR
0x0E SO
0x0F SI
0x1B ESC
◎ISO646
7ビットコード化文字集合。7ビットASCIIの部分集合となっている。各国の国内規格によりかわらない文字を既定した不変コード集合と0x23,0x24を当てはめた基本符号表、国際標準版の3レベルある。
※各国での文字コードの入れ替えを許可した部分
ASCII JIS-X0201
0x23 #
0x24 $
0x40 @
0x5B [
0x5C ＼ \
0x5D ]
0x5E ^
0x60 _
0x7B {
0x7C |
0x7D }
0x7E ~ (上棒）
ISO646英国 #->ポンド記号
ISO646ドイツ、フランスでは８，１０文字変更
＿◇JIS X0201
JISの定めたASCIIに相当する文字セット
ASCIIに加えて半角のカタカナを規定
~ が ￣（こちらは９７年の改定で~でも良くなった）
＼ が \
に割り当てられたために、表示が混乱した
※ISO8859に相当する8ビット部分の定義もあり
0x89-0x9F 定義なし
0xA0-0xDF 半角カナなど
0xE0-0xFF 定義なし
◎ISO8859
7bitのISO646を8ビットに拡張したもの
前半はISO646のままで、広範に各国固有の文字を割り当て
ISO8859-1 Latin1 西ヨーロッパ
⇒英語版Windowsのデフォルト文字コードとほぼ同じ
ISO8859-2 Latin2 東ヨーロッパ
ISO8859-3 Latin3 南ヨーロッパ
ISO8859-4 Latin4 北ヨーロッパ
ISO8859-5 Latin/Cyrillic キリル文字
他にもLatinには10まで変種あり
※地域の各国の文字を１文書の中で混在させることができる
※コードとして利用さているのは
0xA0-0xFF
※日本語はISO8859規格に含まれておらず、JIS X 0201がISO8859を考慮して制定された。
◎コードページ437
英語版MS-DOSなどで使われていた８ビットコード
◎コードページ1252
英語版Windowsの標準
◎JIS C 6226
1978年に韓国された日本国内の最初の漢字コード規格
通称：旧JIS
◎JIS X0208
通称 新JISだが
-1983
-1990
-1997 （シフトＪＩＳ符号化も規格化）
のバージョンがあり。-1983は旧JISとの互換性の無さが問題になった。
２バイト文字（漢字）セット
第１バイト 21h～7Eh
第２バイト 21h～7Eh
を２つ組み合わせて１文字を表す。２バイト文字への切り替えは、３文字エスケープシーケンスによる。
ESC $ B ->２バイト文字
ESC ( B ->１バイト文字
第１バイトが21h～4Fhまでが第１水準。第２バイトが50h～7Ehまでが第２水準。
…..＿◇文字コードとエスケープシーケンス
＿◇文字コードとエスケープシーケンス
必ず文章の最後では、半角文字に戻す規約がある。
ASCII 1B 28 42
JIS X 0201-1976 Roman 1B 28 42
JIS X 0201-1976 カタカナ 1B 28 42
JIS C 6226-1978 1B 28 40
JIS X 0208-1983 1B 28 42
JIS X 0208-1990 1B 28 42 / 1B 28 40
JIS X 0208-1997 1B 28 42 / 1B 28 40
JIS X 0212-1990 1B 24 28 44
◎JIS X0212
JIS X0208に含まれない漢字を補うための符号化文字集合。補助漢字セット。
◎ISO 2022-JP
JISコードを国際規格として表現した名前
主としてインターネットメールで使われる。
※マルチバイト
◎EUC Extended Unix Code
0～127まではASCIIと一致する。MSB=1となるコードは２バイト文字。
漢字コードはJISコードに0x8080を足す。
半角カナは0x8E00を足して２バイトにする。
マルチバイト
◎SJIS
マイクロソフトがエスケープシーケンスを使用せず、半角文字と漢字文字を識別するために、JIS X0201の半角文字が使っていない領域にJIS漢字コードをシフトさせたもの
0x8140~0x9FFC, 0xE040~0xFCFCの２ヶ所に分離
第１バイト 81h～9Fh, E0h～FCh
第２バイト 40h～7Eh, 80h～FCh
F040以降は多く外字領域として使われる。
ＪＩＳコード2121hを8140h起点にそのまま流しこんだ形。JISが94×94の空間なのに対して、SJISは188x(31+16+13)
※WindowsとMacOS(9)以前で使われていた
※JIS Xに機種依存も維持を含めた符号化文字集合を使っているので、厳密にはＪＩＳとは異なる
Windows-31J
CP932
※マルチバイト
※CP932
コードページ932
日本語版Windowsの標準文字コード
JIS X 0209:1990のキャラクタセットに加えて、NEC PC-9801特殊文字とIBM拡張文字を含む
⇒NEC特殊文字とIBM拡張文字は、異なる文字が同じUnicode文字にマップされることがありえるので、可逆変換が保証されない。
◎EBCDIC Extended Binary Coded Decimal Interchange Code
IBM System/360 で使用するために開発された英数字8ビットコード体系。
0xC0~C9 A..I
0xD0~D9 J..R
0xE0~E9 S..Z
0xF0~F9 0..9
◎ISO 10646
世界中の文字を取り込むためにISOが開発を進めたが、後にUnicodeと統一され、ISOからは
ISO 10646-1
Unicode Consortumからは、
Unicode 1.1
として内容一致した形で策定された
＿◇ISO 10646 UCS-4
４バイトコード
文字を３１ビットで符号化
全１２８群、各群２５６面
１面は２５６ｘ２５６
ただし、第１群(0)の第０面は、BMPと呼ばれる基本多言語面。各群で独自に使えるのは１～２５５面
BMP: Basic Multilingual Plane
⇒ISO/IEC 10646-1で既定
英数字、記号、日本／中国／韓国の漢字、ハングルなども含む
※UCS: Universal Multiple-Octet Coded Character Set
＿◇ISO 10646 UCS-2
２バイトコード。Unicode(UTF-16)とほぼ同一、ただし多言語面は１面のみ
UCS-4のBMPを取り出して１６ビット化したものに近い。
第０面BMPは１０２４ｘ１０２４サイズ
※半角文字も２バイトとなる
◎Unicode
IBM, Microsoft, Appleなどが中心となって Unicode Consortiumが制定。ISO 10646-1と内容一致
＿◇UTF-16
UCS-2と一部のUCS-4の文字をコード化
２バイトコード。
※サロゲート・コードにより２個の１６ビット値を使って拡張をおこなっている
⇒２バイトの文字の割り当てのない0xd800から0xdfffを2個組み合わせて1024*1024（約100万)の文字を表す
⇒ここにUCS-4のBMPより後ろの16面を格納する
半角文字も２バイトとなる
⇒ワイドキャラクタ
※Javaと.NETは内部的にUTF-16
※合成文字 combining characterがある
フランス語などのアクセント記号
※２バイトコードのため、既存のライブラリなどにそのまま通そうとすると、問題が起こる。(ASCIIコードも上位バイトに０が入っている）
※エンディアン
UTF-16 little endianとUTF-16 big endianがある。
＿◇UTF-8
UCS Transfer Format-8
UTF-16を8ビット単位可変長で表現したもの
１文字は１バイト～６バイトになる
⇒マルチバイト
⇒アスキーコードはそのまま１バイト
※アルファベットや数字。。。ASCIIと同一の１バイト
日本語は３バイト
※XMLはUTF-8を推奨。PerlもUTF-8
※文字集合はＵＣＳ－２
※エンコーディング
ISO/IEC 10646
0x01～0x7f 最上位ビット”0″の１バイト
0x80～0x7ff 最上位”110″の第１バイト＋
最上位”10″の第２バイト
0x800～0xffff 最上位”1110″の第１バイト＋
最上位”10″の第２バイト＋
最上位”10″の第３バイト
0x10000～0x1fffff
最上位”11110″の第１バイト＋
最上位”10″の第２バイト＋
最上位”10″の第３バイト＋
最上位”10″の第４バイト
＿◇BOM
Byte Order Mark
リトル/ビッグの判別の判別のためにファイル先頭に付加される
UTF-16 ２バイト
リトル FF FE
ビッグ FE FF
UTF-8 ３バイト
EF BB BF
＿◇ハン・ユニフィケーション
China, Japan, Koreaの頭文字でCJK
BMPの中に漢字を押し込めるために意味が同じで字形だけ違う異体字を同じコードに押し込めてしまった
※1つの言語であればあまり問題ないが、複数言語を取り扱う場合には複数のフォントの切替が必要になる。
☆浮動小数点演算
http://754r.ucbtest.org/
浮動小数点の危険
http://www.lahey.com/float.htm
◎DEC, HP, IBM
◆DEC VAX (D Format)
①
radix: 2
number of digits:24
Emin:-128
Emax:126
max.value:1.7…e38
②
radix: 2
number of digits:56
Emin:-128
Emax:126
max.value:1.7…e38
◆HP 28, 48G
radix:10
number of digits:12
Emin:-500
Emax:498
max.value:9.9…e498
◆IBM 370 and 390
IBM Hex浮動小数点形式
※指数が４ビット単位なので、頭に０がつまることがあり、有効ビット数は３ビット範囲で変動する
①単精度
符号１ビット、指数７ビット、Fraction２４ビット
最上位ビットの左に小数点があり、整数部は０とみなす。
指数部の底は16．EXPは64が０のバイアス表現
radix:16
number of digits:6(24bits)
Emin:-65
Emax:62
max.value:7.2…e75
②倍精度
radix:16
number of digits:14(56bits)
Emin:-65
Emax:62
max.value:7.2…e75
◆CRAY-1
倍精度
符号１ビット、指数１５ビット（バイアスは１６３８４）、２を底とする
Ｆｒａｃｔｉｏｎ４８ビット、最上位ビットの左に「０．」があるものとする。
※非常に広い範囲の指数を扱うことができるが、データの有効ビット数は少ない。
◎IEEE形式浮動小数点数
※元はインテル８０８７であり、バークレーのカーン、クーネン、ストーンの３名で起案されたのでＫＣＳと呼ばれた。
※ＤＥＣはＫＣＳに反対し、ＶＡＸフォーマットを押した。
※２進表現の場合、正確に０．１は表現できない
⇒実際に格納されている値は２進法小数による最近傍代表値である
⇒１０進法の異なる数で２進の最近似値が同じものは数多く存在する
⇒もっとも短い表現を選ぶのが人間にとっては分かり易い
◆IEEE Std 754-1985
David Stevenson(Zilog)が議長
＿◇特徴
①指数部は２を底。
②正規化された数値の最上位ビットは必ず１となるので、これをヒドンビットと称して省略し、１ビットを稼いでいる
③指数部は単精度では１２７の下駄はかせ表現
④指数部が０の場合はデノーマル(Denormal)数を表す
⑤最少と最大の指数は特別なデータを表す
※ゼロの表現
EXP, Fractionがオール０
符号は０と１があり得るので、＋０、－０の表現がある
⇒通常は区別する必要ないが、符号を取り出す演算では差がでる
※無限大とＮａＮ
EXP最大値（単精度255、倍精度2047）でFractionが0は無限大
符号ビットにより正負がある。
EXP最大値でFractionにゼロでない値が入っている場合はNaN(Not a Number)
⇒NaNは０÷０、０×無限大のような数値では表現できない結果
⇒NaNを入力として含む演算結果もNaNとなる
⇒最終結果にNaNがあれば、途中の異常を検出できる
⇒メモリをNaNで埋めておけば、初期化しないデータで演算することなどを発見できる
※quietNaNとsignalingNaN
quietNaN 単に伝播していくだけ
signalingNaN 入力に現れるとトラップを発生
※演算の規定
無限の精度で計算を行った結果について規定の丸めを行って、データフォーマットに格納する場合と同じ結果を与えなければならない。
⇒無限精度という規定から、例えば切り上げと行う場合には、精度以下の下位のどこか１ビットにでも１が立つのであれば最下位ビットに１を加える必要がある
⇒ガードビット、ラウンドビット、スティッキービットが必要
ガードビット：最下位ビットの直下
ラウンドビット：その下
スティッキービット：さらにその下の全ビットのＯＲを示す
※誤差を含んだ数値で計算を行う
⇒πなどの無理数や、循環小数は表現できない
⇒得られた結果の含む誤差が分からない。
⇒これに対して区間演算を行えば正確な答えの範囲が保証される
※区間演算(Interval Arithmetic)
⇒常に数値は上限と下限のペアで持ち、演算結果で最大となる組み合わせが上限、最小が下限となるように計算していく
⇒上限の場合は切り上げ、下限は切り捨て
⇒IEEE754では区間演算対応のための丸めが定義されている
※トラップ
異常演算が起こるたびにＯＳに割り込むと性能が低下するので、トラップの原因を記憶し、後で処置をするのが普通
⇒ＩＡ３２ではトラップ６種にマスクビットがありＯＳ割り込みをマスク。トラップを示すフラグは自動ではクリアされずＯＲされる。
＿◇短精度
世界標準のIEEE 形式の短精度浮動小数点数。
bit 31 S:符号
bit 30-23 E:指数
bit 22-0 F:仮数
(-1)^S (1.F)*2^E-127
符号桁（S）が1ビット、指数部（E）が8ビット、仮数部（F）が23ビット、合計32ビット。
符号桁と仮数部で絶対値表現の小数を示す。Fは23ビットではあるが、最上位に”1″を暗に1ビット追加した実質24ビットの数として解釈する。これを正規化された仮数という。ただし、指数部Eが0と255のときは特別なモノを示す。
※浮動小数点数では、指数部に負の数が現れたとき、指数部に一定の数を足し、常に正数とすることが多いが、これをバイアスという。
指数部はバイアスをもち。実際の指数部の大きさeはEから127引いた数で示される（e=E-127）。
e は128から-127を表している。eが127から-126までの値をとるときは、上記のように正規化された仮数を表す。
eが128の場合は無限大や非数（NaN）、eが-127のときはゼロや非正規化数を表す。非正規化数では仮数を（0.F）として表現し、指数は2-126を示す。
e=128 F=0 のとき (-1)^S ∞
e=128 F≠0のとき 非数 NaN
e=-127 F=0のとき (-1)^S 0
e=-127 F≠0のとき (-1)^S 2^-126 (0.F) 非正規数化
＿◇倍精度形式
符号桁は1ビット、指数部は11ビットで1023のバイアス、仮数部は52ビットである。eが1024のときは無限大や非数、eが-1023のときはゼロや非正規化数を表す。1024＞e ＞-1023のときは正規化された（1.F）で示される合計53ビットのデータが表現される。
＿◇4倍精度
指数部が符号桁1ビット、15ビット、仮数部は112ビットである。バイアスは-16383で表現形式は上記と同等である。
＿◇拡張倍精度
符号桁が1ビット、指数部が15ビット、仮数部が64ビット合計80ビットである。
＿◇段階的アンダーフロー
Gradual Underflow
アンダーフローが起きた場合、直ぐにゼロになるのでなく、ヒドンビットを０として、有効ビット数を徐々に低下させながら計算を続けられる
⇒通常の浮動小数点数とは異なる処理（正規化のためのシフト）が必要となる
⇒デノーマル数についてはソフトウエア処理のプロセッサも多い
※デノーマル数の処理は速度が遅くなるため、デノーマル数を自動的にゼロにし、トラップを発生させないプロセッサも多い
⇒x86 MXCSRレジスタdenormals-are-zeroフラグ
◆IEEE Std 754R
①binary 128
radix:2
number of digits:112+1
Emin:-16382
Emax:16383
max.value:1.2…e4932
②decimal 64
radix:10
number of digits:16
Emin:-383
Emax:384
max.value:9.9…9e384
◆IEEE 754-2008
※基本的な２進浮動小数点演算
積和演算が規格に追加された
128ビット長の4倍精度の浮動小数点数も正式のデータ形式が定義された
（Fraction112, Exponent15)
⇒1985版ではFraction64ビット以上、Exponent15ビット以上という拡張倍精度データ形式であった（インテル8087の80ビット長の拡張倍精度など）
※１０進浮動小数点演算の追加
◎初等関数の演算についての福井先生ノート
http://edu-gw2.math.cst.nihon-u.ac.jp/~kurino/2005/analysis/20051101/memo.txt
初等関数の計算
◆関数近似
単純には.. テーラー展開
多項式 / 連分数
※テーラー展開は、h が 0 の近くでは誤差が小さいが、h が大きくなると、誤差が大きくなる。
望ましい誤差曲線
近似区間の誤差の最大が、最小になるように係数を調整
min-max 近似 ( 最良近似 )
※この為には、誤差カーブが決らないといけない→しかし、誤差カーブが解るということは、真値が解るということ
※真値が解らないから、関数近似をしている..
例）24 bit の真値を計算するには ( まるめ誤差のことを考えると.. ) 倍精度の 64 bit で計算し、テーラーの項目をふやせば、時間がかかるが、ある程度求めることができる。
※ハードウェアの bit 数は、限界があるのでソフトウェアでの多倍長ルーチン。
※真値がわかっても..与えられた真値と、近似関数から、min-max を計算するのも非線形な計算なので大変
※関数近似の大家、日大の故山下先生、小野先生、多田先生、浜田先生
①三角関数の近似
sin が理解れば、cos も解る。
# できるだけ計算をサボりたいので..
周期関数なので [0,2π]
形が対称なので [0,π]
同じ対称なので [0,π/2]
加法定理を使えば、更に π/4, π/6 まで狭めることができる。
# 人の好き嫌いでπ/4, π/6を選ぶ
# π/4 : 計算する区間は広いが、折畳む手間が少い
# π/6 : 計算する区間は狭いが、折畳む手間が多い
## 計算量的には、どっちもどっち
\sin{x} のテーラ展開
f(x)=\sin{x}
f(x+h)= f(x)+\frac{h}{1!}f'(x)+\frac{h^2}{2!}f”(x)+\frac{h^3}{3!}f”'(x)+\frac{h^4}{4!}f^{(4)}(x) + ..
より、
\sin{x+h}= \sin{x}+\frac{h}{1!}\cos{x}-\frac{h^2}{2!}\sin{x}-\frac{h^3}{3!}\cos{x}+\frac{h^4}{4!}\sin{x} + ..
ここで x = 0 を代入すれば、
\sin{h}= \frac{x}{1!}-\frac{x^3}{3!}+\frac{h^5}{5!}-\frac{h^7}{7!} ..
これが、近似式
0 <= h <= π/4 < 1 ※階乗の計算は速く大きくなるので収束は速い ※さらに、これを min-max にすると… \sin{h}=h-0.1.666h^3 + 0.083h^5 .. のようになる。 # ここらへんの係数の調整は、それだけで、ノウハウが沢山ある !! ※引数の誤差の問題 周期関数なので、 x の計算をするときには、 x mod 2π を計算すれば良いが.. x の値がすごく大きいと、 x mod 2π の精度が悪くなってしまう.. => 桁落が生れる
# 名古屋の二宮先生
# x を a + b x 2π の形で、計算する !!
# => a の所に誤差は出ない。
※πの値に含まれる誤差も問題 !!
# 計算機の中で、何を使っているかは良くわからない !!
# \arctan{1} で π/2 を計算する..
位相の誤差がしょうじている
# 丁度、符号が変るあたりが、怪しい。
# ここらへんは、sin 関数固有の問題
# tan も別な点で気を付ける必要がある
②sqrt は、多項式近似でもよいが、ニュートン法が速くてよい。
f(x) = x^2 – a
とし、
f(x) = 0
の解αを求めれば、
α = \sqrt{a}
となる。
※ニュートン法
f'(x) = 2x
より、
x_{k+1} = x_k – \frac{f(x_k)}{f'(x_k)}
なので、
x_{k+1} = x_k – \frac{(x_k^2-a)}{2x_k}
= \frac{1}{2}( x_k + \frac{a}{x_k} )
初期値の x_0 が問題だが、一般には、テーブルをもっている。単精度の値がでれば、もう１回で、倍精度の精度が出る
# cf 二次収束
a が 0 に近いと収束が速い ( 大きいと遅くなる )。
a が大きい時は、
a = A * 4^n 1 \le A \lt 4
とすれば、
\sqrt{a} = \sqrt{A*4^n}
= \sqrt{A}*\sqrt{4^n}
= \sqrt{A}*2^n
となる。
こうすれば、x_0 のテーブルも小くできる。
※4 でわる、2 をかけるは、非常に単純な計算…指数部を調整するだけ。
cf. 一松信、「関数近似」教育出版
培風館の「関数近似」の三冊 ( 最後に、定数表があるので厚い )
ハーツの本
# 関数近似を行っている先生は少い
※関数近似は、計算機の前から研究されている
30 年前に、関数近似に関する衝撃があった。
HP 35 : プログラム電卓
50 万円 : 一松先生 日本で最初
30 万円 : 平野先生
◆多項式近似ではない近似
計算機が得意な、論理演算、シフト等で関数計算をする。⇒多項式近似は、浮動小数点計算ができることを前提としている
⇒浮動小数点計算ではなく、論理演算やシフトで計算したい
＿◇CORDIC
x を二進数展開し、各桁を x_i で表す
x_i = 0 / 1
x = \sum{i= 0}^n{x_i 2^{-i}}
sin の加法公式を使うと..
\sin{A+B} = \sin{A}\cos{B}+\cos{B}\sin{A}
\sin{x} = \sin{\sum{i= 0}^n{x_i 2^{-i}}}
= …
展開した先の値にかんしては関数表をを作る
関数表は、まばらなので、全部記憶してなくて、シフトで計算すればよいので、それほど大きな表にならない
シフトと和で計算ので掛け算と良くにた計算でできる。
# 手計算の時代には、考えられなかった手法
# 仮におもいついても、実行できなかっただろう..
※STL ( Successiable, Table, Lookup )
Intel の Chip の関数表に誤りがあった
※CODIC のよい点
bit 数がふえても、loop 数が増えるだけで実現できる
◆折畳み
計算する空間を縮小する手法
関数の性質を巧く利用して行う
初等関数はだいたい、性質がよい
\tan だけはだめ
結果が無限に飛ぶのは性質が悪い
\log は、
\log{x*2^n} = \log{x} + n\log{2}
なので、なんとかなる。
◎CORDIC
COordinate Rotation DIgital Computer.
http://www.dspguru.com/info/faqs/cordic.htm
◎ERROR
◆Approximation error
「近似」による真値との差
◆Evaluation error
有限の桁数による誤差
◎TEST
①Hough’s UCBTEST
http://www.netlib.org/fp/ucbtest.tgz
②MPCHECK
http://www.loria.fr/~zimmerma/free/
③Test of Mathematical Functions of the Standard C Library
http://www.vinc17.org/research/testlibm/index.html.en
☆正規表現マッチャ
◆Rob Pike作
＿◇仕様
文字 意味
c 文字 c そのもの
. 任意の一文字
^ 入力文字列の先頭にマッチ
$ 入力文字列の末尾にマッチ
* 直前の文字の0回以上の反復
＿◇コード
/* match */
int march(char *regexp, char *text)
{
if (regexp[0] == ‘^’)
return matchhere(regexp+1, text);
do {
if (matchhere(regexp, text))
return 1;
} while (*text++ != ‘\0’);
return 0;
}
/* matchhere テキスト先頭正規表現マッチ*/
int matchhere(char *regexp, char *text)
{
if (regexp[0] == ‘\0’)
return 1;
if (regexp[1] == ‘*’)
return matchstar(regexp[0], regexp+2, text);
if (regexp[0] == ‘$’ && regexp[1] == ‘\0’)
return *text == ‘\0′;
if (*text!=’\0′ && (regexp[0]==’.’ || regexp[0]==*text))
return matchhere(regexp+1, text+1);
return 0;
}
/* matchstar C*型の正規表現をテキスト先頭からマッチ*/
int matchstar(int c, char *regexp, char *text)
{
do {
if (matchhere(regexp, text))
return 1;
} while (*text != ‘\0′ && (*text++==c || c==’.’));
return 0;
}
☆GRAPHICS
◎Graphics基礎
◆色の三原色
＿◇光の三原色
赤
青
緑
赤と緑をまぜると黄色
緑と青をまぜるとシアン
青と赤をまぜるとマゼンタ
赤、緑、青をまぜると白となる
＿◇印刷の三原色
シアン(Cyan) 青緑 （赤い光を吸収）
マゼンタ(Magenta) 赤紫 （緑の光を吸収）
イエロー(Yellow) 黄色 （青の光を吸収）
例）シアンとマゼンタをまぜると、赤と緑が吸収され青のみ反射される
※混ぜ合わせると全ての色を吸収するはずだが、完全な黒にするのは難しいので、通常は、黒インクを併用する
◆色空間と表色系
※色空間
各色の成分の濃度を軸にとった空間で、色はその空間内の点として示される。
※表色系
＿◇マンセル表色系
色相(hue) 色の種類
明度(brightness) 明るさ
彩度(chromaticness) 鮮やかさ
※HSV方式
※HSL方式
◆三原色
＿◇光の三原色
赤
マゼンタ
青
シアン
緑
黄
全部重ねると白
＿◇印刷の三原色
シアン(Cyan: 青緑）
青
マゼンタ(Magenta: 赤紫）
赤
黄（Yellow）
緑
全部重ねると黒
＿◇マンセル表色系
A.H.Munsell
色相(hue)
明度(brightness)
彩度(chromaticness)
※HSV方式、HSL方式
＿◇RGB
Red
Green
Blue
３原色の加法混色混合
＿◇sRGB
standard RGB
IECが定めたRGB
⇒一般的デジカメなどで採用
RGB各０～２５５、16777216色
＿◇HSI
Hue 色相
Saturation 彩度
Intensity 明度
＿◇フルカラー
※２４ビット画像
ＲＧＢ各８ビット
※３２ビット画像
２４ビット画像＋マスクチャンネル８ビット
⇒アルファチャンネル
◆2D描画
＿◇曲線
①Spline curve
②Bezier curve
＿◇ブラシ処理
①tint paint
ブラシの色と背景の色をまぜ、水彩の重ね塗りのような効果を得る
②value paint
ブラシで描いた部分の明るさを変化させる
＿◇Aliasing
Jaggyが生じることをAliasingという。これを目立たなくする処理がアンチエイリアシング
＿◇トーンカーブ
明るさの補正
＿◇フィルタ
フィルタ行列をつかって画素の値を再計算する。
ボカシ 周囲画素の値と平均化
シャープ化 中央5で上下、左右-1…明るさの変化大
エッジ抽出 ((1 0)(0 -1))…斜めに隣り合う画素
エンボスはエッジ抽出後に濃度調整
※フィルタの前後で明るさが変わらないようにするためには、フィルタ行列の係数の和が１でないとならない。
＿◇レイヤ
＿◇マスク
画像の任意の部分を透明にする機能
◆3D描画
＿◇座標系
右手系：右手の親指ｘ、人差し指Ｙ，中指ｚ
ＣＡＤ
左手系：左手の親指ｘ、人差し指Ｙ，中指ｚ
３ＤＣＧ
※ワールド座標、ローカル座標
※アフィン変換
平行移動
拡大、縮小
回転
せん断（スキュー）
※回転
右手の親指を回転軸の方向にむけたとき、他の指の方向が＋となる。
＿◇モデリング
立体オブジェクトを作り、立体空間の任意の位置に配置していく作業
①ワイヤフレームモデル
頂点のデータおよび各頂点の組み合わせとしてあらわされる線分のデータからなる。
②サーフェスモデル
ワイヤフレームモデルに加えて線分の組み合わせで面を表す。
ポリゴン(polygon)
立体を表現するために使われるひとつひとつの多角形。通常３角形。
複数の曲面（パッチ）
Bスプライン曲面
ベジェ曲面
NURBS曲面
③ソリッドモデル
球、立方体、円筒等の基本的な形の立体（プリミティブ）を組み合わせて立体を作る。ソリッドモデルの足し算、引き算、掛け算も論理演算（ブーリアン）とよぶ。
CSG表現 Constructive Solid Geometry representation
④立体モデルの生成
回転
スイープ。
ポイントスイープ
ベベル（カドに丸みを持たせる）
メタボール
電荷と等電位面を使って曲面を表現する。
フラクタル図形
※フリーソフト
POB-Ray レイトレーシング
DOGA CGアニメ、初心者OK
六角大王
＿◇モデリング：Extrusion
平面図の積み重ねで立体をつくる
＿◇モデリング：Rathe
平面図を回転させて立体をつくる
＿◇モデリング：デフォルトオブジェクト
部品を組み合わせて立体をつくる
※球や立方体などのプリミティブを組み合わせ変形される。
＿◇テクスチャマッピング
①Surface Texture Mapping
２次元の画像を３次元の物体に貼り付ける。
②バンプマッピング
デコボコの形状をマッピングするためにシェーディングをかけるときの面の向きを変化させる→陰影の付き方が変化し、デコボコに見える。
③環境マッピング
リフレクションマッピング（反射）reflection
映りこみを表現。マッピングしたい物体のまわりに球や円筒をおき映りこませる背景をマッピング。視点から物体を反射して到達したマッピング背景の色を物体の色とする。
リフラクションマッピング（屈折）refraction
④ソリッドテクスチャ
Solid Texture Mapping
３次元空間中に模様データを作成しておく。ここから立体を切り出すと模様が現れる。
⇒フラクタルなどを使って数式で生成する
＿◇ライティング
Lighting
＿◇シェーディング
陰 光の方向と面の向きにより面の明るさが変化する
シェーディング
影 物体が光をさえぎって光があたらない部分
シャドウイング
拡散反射（ディヒューズ）＜＞鏡面反射（スペキュラ）
環境光（アンビエント）
屈折
フラットシェーディング（ポリゴン平面のまま）
つなぎ目が目立つ
スムースシェーディング
なめらかに変化させる
グローシェーディング
ポリゴンの頂点の明るさと距離から計算
計算量すくないがハイライト表現など苦手
フォンシェーディング
法線のむきを補完して明るさを計算する。
光源
平行光源 太陽、光源からの距離で明るさ変わらない
点光源 ランプ、遠ざかると暗くなる、一枚の平面でも明るさが一様にならない
スポット光源 スポットライト
＿◇レイトレーシング（光線追跡法）
視点からビューウインドウの全ての画素に向かって視線を伸ばす。物体にぶつかったら、その面でのテクスチャ情報から色を、照明と面の関係から明るさを決める。反射があればさらに光線を追跡し、屈折があれば、屈折した光線を追跡する。
ラジオシティ
レイトレーシングのシャープすぎる画像を面素ごとの光の相互反射を考慮してぼかすことで自然にしたもの
＿◇レンダリング
投影
①透視投影
視点から、投影面（ビューウインドウ）ごしに３Ｄ物体を見る形
座標系を右Ｘ，上Ｙ，手前Ｚとし、
物体の３次元座標を(x,y,z)とし、視点は、(0,0,f)にあったとするとビューウインドウ上に投影される位置(x*,y*)は、
x* = x * (f /(f-z))
y* = y * (f /(f-z))
※視点を頂点としてビューウインドウの対角の２点がなす角を視覚という。
※視点を頂点とする４角錐をビューボリュームという。
※視点、ビューウインドウ間の距離を焦点距離と呼ぶ。焦点距離が短ければ広い範囲が写り物体は小さく見え、焦点距離が長ければ物体は大きく見える
※写らない文体を切り取る処理をクリッピングという。
②平衡投影
平行光線で投影面に投影
陰線消去、陰面消去
①Zソート法
一番奥にあるポリゴンから書いていく。上塗りされることで隠れる。複雑な図形の場合はうまく表示できない場合あり。②Zバッファ法
画素毎に奥行きの情報を一時的に記憶しておき、もっとも近いポリゴンの色でその画素を塗る。
③スキャンライン法
スキャンライン毎に面の奥行きを調べる。透明物体やアンチエイリアシングの処理も行えるので、Zバッファ法よりリアルだが時間がかかる。
＿◇ボリュームレンダリング
ボクセル(voxel)
雲や霧、立体の内部透視なども表現可能。
◆アニメーション
＿◇morphing
クロスディゾルブ
ワーピング
＿◇パーティクル
煙や炎などを小さな粒子の集まりで表現する
＿◇モーションブラー
＿◇モーションキャプチャ
＿◇インバースキネマティクス
◆ソフトウエア
＿◇OpenGL
＿◇Direct3D
＿◇VRML (Virtual Reality Modeling Language)
◆BMP
①ファイル先頭の２文字は”BM”である。
②以下にファイルヘッダがくる。intは４バイト、shortは２バイト。
typedef struct
{
/* File Header */
unsigned int fileSize;
unsigned short unused0;
unsigned short unused1;
unsigned int rasterOffset;
/*Infomation Header */
unsigned int headerSize;
unsigned int picWidth;
unsigned int picHeight;
unsigned short plane;
unsigned short colorBit;
unsigned int Compression;
unsigned int ImageSize;
unsigned int resolutionW;
unsigned int resolutionH;
unsigned int numOfidxCol;
unsigned int numOfimpCol;
} bmpFileHeader;
③インデックスカラーの場合、以下のCLUTが続く。１エントリ４バイト。
typedef struct
{
unsigned char B;
unsigned char G;
unsigned char R;
unsigned char filler;
} bmpCLUT;
④ラスタデータ（４バイトの倍数にパック）。左下隅が原点。左から右へ、下から上へ。ピクセル内では画像左がＬＳＢ。
☆CG
◎ＣＧ
◆BitBlt
初期のWindowsのBitBlt関数は、ある種のミニコンパイラを含んでおり、ラスタ演算を受け取ると、BitBlt関数がスタック上に8086の機械語命令をサブルーチン形式で生成し、それを呼び出していた。
※３項ラスタ演算
パターンP 11110000
ソースS 11001100
行き先D 10101010
この８通りの組み合わせに対応する結果は256通りありえる。
◆曲線
＿◇スプライン曲線
spline curve
指定した点を通るなめらかな曲線
＿◇ベジェ曲線
Bezier curve
※ルノーの車のデザイナーであったベジェが考案した。
アンカーポイントの両側に方向ポイントがあり、これを動かすことで曲線の形を変えることができる
◆塗りつぶし
＿◇tint paint
ブラシの色と背景の色を混ぜ合わせる。
水性絵具の重ね塗り風
＿◇value paint
ブラシで描いた部分の明るさを変化させる。
◆アンチエイリアシング
ジャギー(Jaggy)を目立たなくする処理
◆補正
＿◇トーンカーブ
明るさの補正に使う
◆フィルタ
＿◇フィルタ行列
＿◇シャープ化
となりあう画素の濃度値を引き算⇒輪郭での変化を大きくする
0 -1 0
-1 5 -1
0 -1 0
＿◇エッジ抽出
1 0
0 -1
＿◇エンボス
エッジ抽出した画像に適当な値を加えて明るくする
◎３Ｄ描画
◆モデリングとレンダリング
※モデリング
立体のデータをつくる
※レンダリング
画面上に表示する
＿◇ワイヤフレームモデル
wireframe model
頂点の座標と、頂点と頂点を結ぶ線のデータから立体の骨組みのみを定義する。
⇒面についての情報なし
＿◇サーフェスモデル
surface model
頂点と、線のデータに加え、線からくみたてられる面の情報が定義される。
⇒物体の内部を示す情報はない
※ポリゴン
立体を表現するために使われるひとつひとつの多角形
⇒通常３角形のポリゴンが使われる（３頂点からはかならず平面が定義されるので）
※曲面表現
Bスプライン曲面
ベジェ曲面
NURBS曲面
⇒複数の曲面（パッチ）
＿◇ソリッドモデル
solid model
中身が詰まったモデル。球、立方体などの基本図形（プリミティブ）を組み合わせ、それらの間の論理演算で複雑な図形を定義する
⇒ＣＳＧ表現
Constructive Solid Geometry representation
＿◇立体モデルの生成：回転とスイープ
※回転
断面形状から立体化
※スイープ
２次元形状を直線や曲線にそってスイープ
※ポイントスイープ
スイープしながら大きさを変え、１点に集中させる
※ベベル
立体のカドの部分に丸みを持たせる処理
＿◇立体モデルの生成：メタボール
meta-ball
※クーロン力の考え方で複数の点においた電荷から電位が等しくなる点を物体の面として考える。
＿◇隠線消去、隠面消去
※Zソート法
ポリゴンを奥行方向の順にならべて奥から描いてゆく
⇒簡単だが、複雑な形状ではソートできずにうまく描けないこともある
※Zバッファ法
画素毎に奥行の判断をする
⇒ビデオゲーム向き
※スキャンライン法
走査線にそったスキャンライン面毎に奥行を調べる
⇒画素毎のZバッファでできない、アンチエイリアシング処理などが可能
⇒ガラスのような透明物体の表現にも向く
＿◇シェーディングとシャドウイング
※陰 (shade)
物体表面で、面の向きと光の方向とにより、面の明るさが変化して暗くなる部分
※影 (shadow)
物体が光をさえぎって、他の物体上に光が当たらない部分
※フラットシェーディング
ポリゴンは平面なのでポリゴンの中のシェーディングは一定
※スムーズシェーディング
ポリゴンは平面だが、ポリゴンの中でシェーディングを変化させ、あたかも曲面のように見せる
⇒グーローシェーディング
ポリゴン内部の明るさは、各頂点からの距離から計算する
演算簡単だが、ハイライト表現には向かない
⇒フォンシェーディング
ポリゴンの頂点毎の法線方向から、内部の法線の方向を補間してもとめる
＿◇拡散反射と鏡面反射
※拡散反射
ディヒューズ
表面がざらざらしたものの反射
※鏡面反射
スペキュラ
⇒物体の表面の一部にハイライトを生じる
＿◇環境光と屈折
※環境光
⇒間接光、アンビエント
＿◇光源
平行光源
点光源
スポット光源
⇒点光源にカサをつけたもの
◆投影方法、視点
＿◇透視投影
ビューウインドウ（投影面）の手前にある視点から投影面の後ろにある図形を透視してみる
＿◇平行投影
平行な交戦で図形を投影面に映し出す。ＣＡＤなどで使われる
＿◇視点
※視角
ビューウィンドウの対角の２点のなす角
※ビューボリューム
視点を頂点とし、視角のなかに含まれる４角錐
⇒ビューボリュームに含まれない部分を切り取る処理＝クリッピング
⇒処理面をクリッピング面
※焦点距離
視点からビューウィンドウまでの距離
⇒焦点距離が小さいと視野角が大きくなる⇒相対的に物体は小さく見える
⇒焦点距離が大きいと視野角は小さくなる⇒狭い範囲が映し出されるので大きく見える
◆座標系
親指＝X
人差し指＝Y
中指＝Z
Zが奥行方向
＿◇右手系と左手系
※右手系
CADなどで主として使われる
※左手系
３ＤＣＧは通常こちら
＿◇ワールド座標とローカル座標
ワールド座標だけだと物体の回転、変形の計算が面倒なので、それぞれの立体毎にローカル座標を定義することが多い
◆フラクタル
◆ジオメトリ
アプリケーション内で定義した空間上の立体モデルの座標をスクリーン座標に変換するための演算処理
◆表面処理
＿◇テクスチャ
モデルの表面に紙や金属、木、砂といった質感を与えるための処理
２次元の写真や模様などの画像を３次元物体の表面に張り付ける
※テクスチャマッピング
※ソリッドテクスチャ
２Ｄでなく３Ｄのテクスチャを用意し、切断面を見せる
＿◇バンプマッピング
実際の物体表面をデコボコにさせるのは大変なので、シェーディングを計算するときの面の向きをマッピングにより変化させ、表面にデコボコがあるように見せる
⇒あまり大きな凹凸表現はできない
＿◇環境マッピング
※リフレクション
reflection
周囲の映像を物体外部の仮想円筒などにマッピングし、物体表面の色をそこから決める
反射
※リフラクション
refraction
屈折
リフレクションどうような方法で、屈折効果を狙う
◆レイトレーシング
＿◇レイトレーシング
＿◇ラジオシティ
◆ボリュームレンダリング
※ボクセル
voxel
◎画像処理
◆ビデオコーデック
符号化、復号化
ブロック単位で、動きベクトル探索、DCT、量子化など
※スレッド並列性
◆ISP
Image Signal Processing
光学系の補正や、センサの傷補正、画素単位の処理が中心
※データ並列性
◆超解像度処理
フレーム内での超解像度処理
フレーム間での超解像度処理
＿◇フレーム内での超解像度処理
１フレーム内の入力信号から高解像度画像を推測（主として輝度信号）
※フレーム間より軽いが、画素に誤りがでる可能性がある。
※入力のサンプリングポイントの間の画素の補間
⇒単純な線形フィルタ⇒波形滑らか⇒メリハリなし
⇒前後だけでなく他の走査線などの情報も加味して推定
※適用領域の限定
全画面に一律適用⇒遠近感がなくなり平面的画像となる
①テクスチャ、エッジ、平坦の３領域分割
⇒テクスチャ（輝度信号が細かく変化している領域）にのみ超解像度を適用
②遠近解析⇒前面映像にのみ適用。拝啓には適用しない。
※再構成法
アップコンバートした画像をダウンコンバートしたものと
元画像の差分をとり、アップコンバートした画像に補正処理をかける方式
＿◇フレーム間での超解像度処理
複数フレームを処理
※１枚１枚の解像度が低くても、フレーム間で画素がずれていれば解像度を高められる
⇒対象物が写る画素がフレーム間でずれなければならない
（対象物の位置情報、移動量の推定が必要）
特定対象物の画素位置あわせ⇒入力映像以上のサンプリングポイント
※メモリ量、処理量がおおくなるが、雑音除去でき、原理的にも高精度
◆画像認識
特徴抽出（データ並列度高い）
識別、統計量計算（短いデータ並列＋スレッド並列）
推論、判断
☆Audio/Video
◎Audio
◆μ-Law, A-Law
コンバインディング・アルゴリズム
携帯、IP電話のコーデックで使われた
サンプリング8kHz, １サンプル1バイト
＿◇PCMU(G.711 mu-Law; μ-Law)
日米
＿◇PCMA(G.711 A-Law; A-Law)
欧州
◎Video
◆AVI
Windows系OSの標準的動画フォーマット。元々はVideo for Windows向けに開発
＿◇バージョンと種類
①AVI 1.0
ファイルサイズ上限2GB。ファイルヘッダ、音声、映像が一つのブロックに
②AVI 2.0
ファイルサイズ上限はOSの扱えるファイルサイズ。Video for Windowsでなく、DirectShowでアクセスする
③参照AVI
ファイルヘッダと音声が一つのブロックだが、映像は複数の別ブロックにいれることができ、擬似的にファイルサイズの上限を撤廃。AVI 1.0と大差ないアクセスが可能。
◆WMV
ストリーミング念頭にMPEG4をもとにしている。固定ビットレートと可変ビットレートに対応。
320×240 … 400Kbps
640×480 … 800Kbps~1Mbps
Windows Media Player必須。ＭＳの独自フォーマット。