トップ 差分 一覧 ソース 検索 ヘルプ PDF RSS ログイン

独り言日記(2008/12)

独り言日記

年末(2008/12/31)

実家に帰省中。ft-lab.ne.jpに移行してから5年ほど日記を書き続けてるわけですが(過去のまだ生きているサイトもあわせると8年以上にはなるのかな)、だらだらと書いているおかげもあって息が長く続いています。かたくなにブログを拒否し続けてWikiを貫き通してますが、これからもこの調子で行きます(so-netでタダのブログサービスがあるのですけどね、移行が面倒なので)。

今はとある論文をベースにとある機能を実装しているのですが、、、ずっと1ヶ月ほど格闘中。線形代数が絡むのに加えて、収束せずになぜか発散してしまう・・・。個々の機能をチェックしている感じだと理論上はあってると思うのですが、どこかまずい実装がありそう。

年越しはこの問題に取り組んでいくことになりそうです。

それでは良いお年を。

CLAPACK(2008/12/24)

線形代数は深く勉強しないと小手先の理解だけでは先に進みませんねぇ。私の知識ではまだまだ追いつかないようです。今は根本での理解をあきらめて、数値演算ライブラリを頼ることに。

「CLAPACK」

http://www.netlib.org/clapack/

これは固有値や固有ベクトルを求めたり、特異値分解したり、といった線形代数での計算ができます。

以下のページを参考にビルド&テストしてみました。

http://www.alab.t.u-tokyo.ac.jp/~bond/doc/clapack.html

速度も速そうですね。

ただ、元々がFORTRANのライブラリだったそうでそれのルールがあるみたいです。

http://www.vi.cs.is.nagoya-u.ac.jp/watanabe-lab/graduates/01year/hiroyuki/lab/clapack/index.html

行列を渡す場合の配列の並びは列 x 行の順に納めるようにします。

A = \begin{pmatrix} 1&2&3\\ 4&5&6\\ \end{pmatrix}

この場合は、

double A[2 * 3];
A[0] = 1.0; A[2] = 2.0; A[4] = 3.0;
A[1] = 4.0; A[3] = 5.0; A[5] = 6.0;

と入れます。

線形代数の本を購入(2008/12/20)

どうも基礎が出来てないとすぐにつまづいてしまうため、「線形代数 数理科学の基礎」という東京大学出版会から出ている本を買ってきました。一応、自分が勉強したいQR法、householder、特異値分解、などが載っていたので。来年は数学ももっと理解を深めようかと。

線形代数は、本屋の1つの棚を埋めるくらい出版されてるんですね。

後、これは関係ないのですが、何を思ったのか琵琶演奏(歌ありのもの。いわゆる弾き語りです)のCD買ってきました。某CD屋に「純邦楽」というジャンルがあり、ここに和太鼓やら雅楽やらのCDがありまして。ちょっと別ジャンルの曲も聴いてみたいなということで歴史ありそうな琵琶を。店員さんが「在庫を探してきますね」といって奥に取りに行って「棚のものでよろしいでしょうか」と言った在庫すらなかったCDです(^_^;;。

平家物語のような戦乱ものをと思ってたのですが、意外と内容が軽いものが多いのかも。買ったCDがそういうのだったのかもしれません。俗っぽいのは「くずれ」琵琶の「チャリ物」というジャンルだそうです。もっと昔から伝わるってのがあればいいのですが、、、琵琶CDはこれしかなかったかなぁ。薩摩琵琶の「小督」(テーマは平家物語に登場する小督局)はその中でも聞きやすかったというか想像していたイメージに近いと感じました。

うろたんだーのCDは延期したらしく、まだ発売されてないようですね(アマゾンによると12/28とのこと)。

低解像度から高解像度の復元(2008/12/19)

調べていることとは直接関係しているものではないのですが、よく「低解像度から高解像度を復元する」というテーマが論文をあさっていると見受けられます。ビデオモザイキングというらしいです。

で、分かりやすいムービーと説明がありました。

http://yokoya.naist.jp/~tomoka-s/videomosaic/index.html

結構高解像度になるもんなんですね。

この界隈というか自然認識や推定系は日本語論文が多いような気がするので、正直助かってます。

上記の特徴点検出は論文を読むとHarrisオペレータかな。特徴点の検出と追跡は、別手法としてKLTを使っても精度よく追跡可能です(ソースコードもありますし)。ということで、特徴点の検出+追跡はもう定型化してるんだなぁと。

QR法による固有値算出(2008/12/16)

「物理のかぎしっぽ」の説明がプログラムもあって分かりかったので実験。

http://hooktail.org/computer/index.php?QR%CB%A1

対称行列は、たとえば以下のようなNxNの正方行列を入れるとします。

1.00000    2.00000    3.00000    4.00000 
2.00000    9.00000    8.00000    5.00000 
3.00000    8.00000   10.00000    6.00000 
4.00000    5.00000    6.00000    7.00000 

これは

A B C D
B E F H    
C F G I
D H I J

のような構造となる行列です。4x4じゃなくてNxNで大きな行列でも可能。これをQR法にて計算すると、

22.83026    0.00000    0.00000    0.00000 
 0.00000   -1.04749   -0.00000    0.00000 
 0.00000   -0.00000    3.84803   -0.00000 
 0.00000    0.00000   -0.00000    1.36921 

が結果として導き出され、行列の左上から右下の(22.83026, -1.04749, 3.84803, 1.36921)が固有値ということになります。

たとえば、複数の頂点がある場合の形状の姿勢や総和としての方向の推定にて使えますね。とあるところにて使う予定ですが、それ以外にも応用できる理論ではありそうです。

この中では、「Householder」と「三重対角化」というのがありますので、掘っていくと派生的にいろいろ勉強すべき内容が出てきますねぇ。一応、理解するためにフルスクラッチでコードを書いてみたのですが、、、、ぶっちゃけ、中身で何をしているのかよく分かってないです(汗)。

論文を熟読中(2008/12/11)

某実装に向けて論文を片っ端から熟読中です。やっぱりサンプルソースなどが添えてあるものは分かりやすいですね。いいかげん、英語をなんとか理解しないととは思ってまして英語のも日本語のも読むようにしてます。どうせ数式が出てきたら日本語も英語もかわらんですし(^_^;;。<自分の理解が追いつかないという意味で

複数の論文に目を通すとだいたいの傾向が分かるのと、分野によってはまだ未開拓の地がありそう、というのも見えてきた気がします。

最近は、複数のサンプリングデータがあってブラックボックスである行列または関数を求めるには?なんてことを考えてます(確率的なものじゃなくて収束を求める、みたいな)。やっぱり、最小二乗法が方法論として出てきますねぇ。その他、いろいろ手段はありそうなのですが一つ一つ地道に実験を繰り返すのが一番確実なのかなと思ってます。論文によっては「この手法はここが弱い」なんて指摘があるのもあるのですが、う〜ん、やってみないことにはなんとも。ということでしばらく奮闘&沸騰中です。

UTF-8かShiftJISかそれ以外か、の判断(2008/12/02)

特定のTipsなんで専用のページを作ってまとめたほうがいいのですが、いかんせんいつも行き当たりばったりに書くので、日記で垂れ流していくことにします。

WindowsおよびMac OS Xでの文字コード変換については、もうOS自身に変換用APIはあるので(Win95のときはそのAPIがなかったため処理を分岐させる、なんて必要があったのですが)素直にそれを使うと早いです。

ちなみに、Windowsかどうかのプリプロセッサは「_WINDOWS」、Macの場合は「__APPLE__」を使って判断してます(FreeStyleWikiの構文上、全角のアンダーバーにしてますが、半角に脳内変換してくださいませ)。

Windowsの場合は「MultiByteToWideChar」でワイドキャラに変換し、「WideCharToMultiByte」で第一引数にCP_UTF8を指定してマルチバイト変換します。文字列操作関数は、ワイドキャラで扱うものは一通りそろってます(wcsで始まる関数)。

Mac OS Xの場合は「TECConvertText」にて変換。以下のように実装できます。

前処理にて(コンストラクタなど)

TextEncoding m_utf8Encoding;   ///< UTF-8のテキストエンコーディング情報
TECObjectRef m_SJIStoUTF8Conv; ///< SJISからUTF-8へのテキストコンバータクラス
TECObjectRef m_UTF8toSJISConv; ///< UTF-8からSJISへのテキストコンバータクラス

// UTF-8エンコーダの作成
m_utf8Encoding = CreateTextEncoding(kTextEncodingUnicodeDefault,
     kTextEncodingDefaultVariant, kUnicodeUTF8Format);

// SJISからUTF-8に変換するコンバータの作成
TECCreateConverter(&m_SJIStoUTF8Conv, kTextEncodingMacJapanese,
     m_utf8Encoding);

// UTF-8からSJISに変換するコンバータの作成
TECCreateConverter(&m_UTF8toSJISConv, m_utf8Encoding,
     kTextEncodingMacJapanese);

後処理にて(デストラクタなど)

TECDisposeConverter(m_SJIStoUTF8Conv);
TECDisposeConverter(m_UTF8toSJISConv);

文字列変換部

// pSJISStr  ... ShiftJISの文字列バッファ
// pUTF8Str  ... UTF-8の文字列が返るバッファ
// return値  文字列長

OSStatus ret = noErr;
unsigned long srcLen, dstLen;
ByteCount actualInputLength;
ByteCount actualOutputLength;
char *pStr;

srcLen = (unsigned long)strlen(pSJISStr);
dstLen = (unsigned long)(srcLen << 2);
    
pStr = (char *)alloca(dstLen + 4);
if(!pStr) return 0;

// SJISをUTF-8に変換する
ret = TECConvertText(m_SJIStoUTF8Conv, (unsigned char *)pSJISStr,
    srcLen, &actualInputLength, (unsigned char *)pStr, dstLen, &actualOutputLength);
    
if(ret != noErr || (int)actualOutputLength >= MaxUTF8StrLen) {
    // エラー
    return 0;
}
   
memcpy(pUTF8Str, pStr, (int)actualOutputLength);
pUTF8Str[actualOutputLength] = '\0';

return (int)actualOutputLength;

Windowsの場合はいろんなサイトに情報があると思うのでここでは割愛します。

で、本題。プログラム内部ではUTF-8で扱うほうが統一できていいと考えてます。ここで文字列はすべてUTF-8で扱うとします。

その場合、たとえばANSI Cの「strchr」の処理をUTF-8でやるにはどうすればいいのでしょうか。「wcschr」でワイドキャラにて扱う?

ですが、この場合はいちいちマルチバイト(UTF-8)からワイドキャラ変換、といった処理を行ってあげないといけません。こりゃ面倒です。ということで、ANSI Cの文字列操作関数をまねたUTF-8文字列操作関数を作ってしまいます。

実はUTF-8は法則がありまして、

http://ash.jp/code/code.htm

のサイトに分かりやすく書いてます。

UTF-8では1つの全角文字が2〜4バイトの可変長で表現されます。1バイト目を見れば、その文字が何バイトで表現されているのかは判断できます。

では、与えられた文字列がUTF-8かShiftJISかそれ以外か、を判断するソースを記載してみます。

 /**
  * 指定の文字列のエンコードの種類を解析
  * @param[in]  pStr  文字列の先頭ポインタ
  * @return エンコードの種類を返す
  */
int GetEncode(const char *pStr)
{
    unsigned char *pStr2;
    int sjisCou, asciiCou, otherCou, len;
    unsigned char chDat, chDat2, chDat3, chDat4;
    int loop;

    if(!pStr) return 0;

    pStr2 = (unsigned char *)pStr;
    if(*pStr2 == '\0') return 0;

    // 文字列の長さの計算
    len = 0;
    pStr2 = (unsigned char *)pStr;
    while(*pStr2) {
        len++;
        pStr2++;
    }

    // ASCIIコードのみの文字列か判定
    pStr2 = (unsigned char *)pStr;
    for(loop = 0; loop < len; loop++) {
        if((*pStr2) >= 0x80) break;
        pStr2++;
    }
    if(loop >= len) return 「ASCIIコードのみ」;

    // UTF-8の判定
    pStr2 = (unsigned char *)pStr;
    for(loop = 0; loop < len; loop++) {
        chDat = *pStr2;

        // http://ash.jp/code/code.htm
        // より、UTF-8は一バイト目が
        // 2進数 0xxxxxxx / 110xxxxx / 1110xxxx / 11110xxx によって、
        // 1〜4バイトで構成される。
        // 2〜4バイト目は0x80 〜 0xbf。 
        if((chDat & 0xf8) == 0xf0) {
            chDat2 = *(pStr2 + 1);
            chDat3 = *(pStr2 + 2);
            chDat4 = *(pStr2 + 3);
            if( chDat2 >= 0x80 && chDat2 <= 0xbf && 
                chDat3 >= 0x80 && chDat3 <= 0xbf &&
                chDat4 >= 0x80 && chDat4 <= 0xbf) {
                pStr2 += 4;
                continue;
            }
            break;

        } else if((chDat & 0xf0) == 0xe0) {
            chDat2 = *(pStr2 + 1);
            chDat3 = *(pStr2 + 2);
            if( chDat2 >= 0x80 && chDat2 <= 0xbf && 
                chDat3 >= 0x80 && chDat3 <= 0xbf) {
                pStr2 += 3;
                continue;
            }
            break;

        } else if((chDat & 0xe0) == 0xc0) {
            chDat2 = *(pStr2 + 1);
            if(chDat2 >= 0x80 && chDat2 <= 0xbf) {
                pStr2 += 2;
                continue;
            }
            break;

        }
        if(chDat <= 0x7f) {
            pStr2++;
            continue;
        }
        break;
    }
    if(loop >= len) return 「UTF-8」;

    // ShiftJISかの判定
    pStr2 = (unsigned char *)pStr;
    sjisCou  = 0;
    asciiCou = 0;
    otherCou = 0;
    while(*pStr2) {
        chDat = *pStr2;
        if(chDat > 0 && chDat < 0x80) asciiCou++;

        if((chDat >= 0x81 && chDat <= 0x9f) || (chDat >= 0xe0 && chDat <= 0xff)) {
            chDat2 = *(pStr2 + 1);
            if((chDat2 >= 0x40 && chDat2 <= 0x7f) || (chDat2 >= 0x80 && chDat2 <= 0xff)) {
                sjisCou++;
                pStr2 += 2;
                continue;
            }
        }
        if(chDat >= 0x80) otherCou++;
        pStr2++;
    }

    if(sjisCou > 0) {
        if(!otherCou) return 「ShiftJISコード」;
    } else {
        if(!otherCou) return 「ASCIIコード」;
    }

    return 「それ以外」;
}

説明は面倒なので省きますが、UTF-8の法則としては

// UTF-8は一バイト目が
// 2進数 0xxxxxxx / 110xxxxx / 1110xxxx / 11110xxx によって、
// 1〜4バイトで構成される。
// 2〜4バイト目は0x80 〜 0xbf。 

がすべてです。どんな言語であってもこれで収めることができますので楽ですね。コレさえ分かれば、UTF-8対応のstrchrなどの文字列操作関数も自前で実装できるかと思います。

/**
 * 文字列中に指定の文字が現れるかチェック
 * @param[in]  pStrData   対象となる文字列
 * @param[in]  searchDat  検索する文字コード
 * @return 文字列が出現したポインタ。NULLの場合は検索失敗。
 */
char *StrChr_UTF8(const char *pStrData, const int searchDat)
{
    unsigned char *pPos, *pRetPos;
    unsigned char cDat, searchC;

    if(!pStrData || !searchDat) return NULL;

    pRetPos = NULL;
    searchC = (unsigned char)searchDat;
    pPos    = (unsigned char *)pStrData;
    while(*pPos) {
        cDat = *pPos;
        if((cDat & 0xf8) == 0xf0) pPos += 4;
        else if((cDat & 0xf0) == 0xe0) pPos += 3;
        else if((cDat & 0xe0) == 0xc0) pPos += 2;
        else {
            if(cDat == searchC) {
                pRetPos = pPos;
                break;
            }
            pPos++;
        }
    }

    if(!pRetPos) return NULL;
    return (char *)pRetPos;
}

な感じ。

実はwxWidgetsが文字列の処理に弱いのです。ASCII文字列圏(?)の方が作ったライブラリなのでいたしかたないのですが、全角圏(?)だと当たり前にできることができてないのが歯がゆいところ。

ということで、C/C++言語アプリで文字列処理をUTF-8で統一する+UTF-8用文字列操作関数、は独自でライブラリ化しておくと後々いろんなところで使い回しができて便利です。

しかし、C/C++もそろそろJavaのような便利ライブラリ(文字列操作含む)を標準化してほしいなぁと思ったりもします。OS依存する部分はというと、

  • GUI部分(画像読み込み、保存含む)
  • 文字列処理
  • スレッド実装
  • ネットワーク命令(socketの初期化処理部など)

とか、たぶんずっとそのまんまなのだろうなぁ。wxWidgetsはがんばって共通で使えるようにはなってますが、、、文字列処理が弱いのはおしいです。

Future's Laboratory 技術格納庫 2004-2013 Yutaka Yoshisaka.