類似画像を検索する方法を調べみた その1

Google画像検索のような類似画像を検索する方法を調べてみた。

ぱっと思いつくのは、色や形状などの特徴量を比較し、近似しているものを調べていく方法だ。
この手の情報やライブラリは、けっこう出回っているので、一番お手軽にできそうだ。

他のアプローチとしては、特徴量が近似していないものを探しいくことで、類似性を判定する方法もあるそうだ。

画像同士をつきあわせて類似性を判定するのではなく、彼らは問題をまったく別の角度から捉えた。彼らの方法では、ターゲットの画像(A)を大量のランダムな画像と比較して、それらと当の画像との、もっとも著しい違いを記録する(Ra)。そして、もう一つのターゲット画像(B)に対しても同じ記録を作成する(Rb)。この、RaとRbがほぼ同じなら、画像AとBは類似性が高いだろう。

重要なのは'類似'ではなく'違い'だ–まったく新しい着想に基づく高精度の画像検索アルゴリズム | TechCrunch Japan

画像検索とは

テキストキーワードを用いる方法を、TBIR(Text Based Image Retrieval)、
画像特徴を用いる方法を、CBIR(Content Based Image Retrieval)と呼ぶみたいだ。

TBIRは、画像にキーワードを紐付けて、そのキーワードに類似している画像を検索する方法とのこと。
今回はCBIRについて調べていきたいと思う。

形状特徴を利用する方法

検索していると「モノクロ画像検索のための形状特徴」という論文を発見した。
SobelやCannyフィルタを使ってエッジの抽出をおこなった画像を、3×3に分割し、各領域のエッジ割合を比較する、という方法のようだ。

気になったのがaHash(AverageHash)という方法だ。

この手法は「Perceptual Hash」という、「比較可能なハッシュ」を生成するための一手法です。

一般的にMD5SHA1などのハッシュ値は、1バイトでもデータが違えば、まったく違うハッシュ値を返してきますが、「Perceptual Hash」は似たようなデータには似たようなハッシュ値を返してきます。

簡単な画像の類似度計算手法「Average Hash」 » Untitled Blog

どんな方法だろうと見てみると、グレースケール化した画像を8×8ピクセルに縮小化し、色の濃淡でビット列を作成する、ということらしい。

「Average Hash」は以下のような手順で生成することができます。

画像のサイズを縮小 (ブログによれば8×8に縮小)
色をグレースケールにする
画像の各ビクセルを使って色の平均値を計算
それぞれのピクセルで色の濃淡を調べ、その色が平均値よりも濃い場合は1を、薄い場合は0を設定する
結果的に8×8=64ビットのビット列ができあがる

pHashというものもあるらしく、DCT(離散コサイン変換)を使っているらしい。
こちらはライブラリ化しており、下記のサイトからダウンロードできるが、ライセンスはGPLとのこと。
pHash.org: Home of pHash, the open source perceptual hash library

libpuzzle

libpuzzleというライブラリが有名なようで、使っている記事がたくさんヒットした。
PHPから簡単に使えるようになっているらしく、BSDライセンスで扱いやすそうだ。
ラッパーを作れば他の言語からも利用できると思う。
Libpuzzle – A library to find similar pictures

しかもけっこう速そうだ。

なお、うちのCoreSolo(初代Intel Mac mini)な環境では、
シグネチャの生成x100画像で大体1分~1分半。
近似度判定x10000回で大体2~3秒だったので、
シグネチャをどっかに保存しておけば、10万画像の線形比較くらいなら許容範囲ではないかと思われる。

PHPからCOMを使う

WindowsでIEを制御するためにCOMを使ってみた。
PHPからCOMを使うのは簡単で、「php.ini」からCOMを読み込むように設定すればいいみたいだ。
PHP 5.3.15 / 5.4.5 以前は、デフォルトで読み込まれるらしい。

PHP: インストール手順 – Manual

# php.ini
[COM_DOT_NET]
extension=php_com_dotnet.dll

使いたいコンポーネント名を引数に指定して、COMオブジェクトを生成するだけで使える。
navigate関数で指定ページに移動したあとは、DOMを操作するだけだ。

ページ表示後の待機処理

navigate関数呼び出し後、表示が完了するまで待機するのだけど、いくつか方法がある。
busyプロパティを見て判断する方法が一番簡単なようだ。
しかし、この方法だとDOMが構築される前にループを抜けてしまうため、
DOM要素にアクセスするとエラーになる場合がある。

while ($com_ie->busy) {
com_message_pump(3000);
}

もう一つは、com_event_sink関数で読み込み完了のコールバック関数を指定する方法だ。

class IEEventSinker {
var $completed = false;
var $url = '';
function DocumentComplete(&$dom, $url) {
if ($url == $this->url) {
$this->completed = true;
}
}
function OnQuit() {
$this->completed = false;
}
}
$com_ie = new COM('InternetExplorer.Application', null, CP_UTF8);
$sink = new IEEventSinker();
com_event_sink($com_ie, $sink, 'DWebBrowserEvents2');
while (!$sink->completed) {
com_message_pump(3000);
}

この方法だと読み込み完了のイベントを処理できるので安全らしい。
実際に試したところ、後者の方法でもエラーになることがあった…。
com_message_pump関数を使って、処理待ち状態のメッセージを処理しながらループする。引数の値は、タイムアウトミリ秒だ。0を指定した場合、処理待ちメッセージがなければすぐにFALSEを返す。

ブラウザのビジー状態を判定するための,より良い方法 (WSHでIEを自動操作する際,COMのアプリケーションイベントを利用する) – 主に言語とシステム開発に関して

Yahoo検索を自動化する

Yahoo検索にアクセスしてキーワードを入力後、Submitするものを作ってみた。

<html>sample code.
<?php
class IEEventSinker {
var $completed = false;
var $url = '';
function DocumentComplete(&$dom, $url) {
if ($url == $this->url) {
$this->completed = true;
}
}
function OnQuit() {
$this->completed = false;
}
}
$com_ie = new COM('InternetExplorer.Application', null, CP_UTF8);
$com_ie->visible = true;
$sink = new IEEventSinker();
com_event_sink($com_ie, $sink, 'DWebBrowserEvents2');
$sink->url = 'http://search.yahoo.co.jp/';
$com_ie->navigate($sink->url);
$st = time();
while (!$sink->completed) {
com_message_pump(3000);
if ((time() - $st) >= 5) break;
}
$com_ie->document->forms(0)->p->value = 'php';
$com_ie->document->forms(0)->submit(null);

フォームのClickとSubmitが動かない

最初はWindowsXP上のIE7で試していたのだけど、Windows8上のIE10で上手く動作しない問題が起きた。
フォームの入力は正常にできるのだけど、ClickやSubmitが動作しない。

ググりまくったところ、下記のページを発見し、引数にNULLを指定したところ無事に動作した。
ちなみにIE9以降で起こる問題みたいだ。

Japanese user list of the Ruby programming language ()

参考コード
pontago/php-IECom · GitHub

PHP版Shindigが上手く動かない

オープンソーシャルのアプリを開発する上で、必須といえるShindigShindigでコンテナを構築すればローカルでオープンソーシャルの開発をすることが出来ます。
そこでちょっとハマったことを記録として残しておきます。

まずShindigには、色々なバージョンがある上にJava版とPHP版の二種類が存在します。
以前開発に使っていたのはJava版で、PHPで上手く動かすことが出来なかったため使っていました。が、、、HAS_APPフィルタがなぜか上手く動かない事に気づき、調べてみたもののJavaがほとんど分からず、これを機会にPHP版を新たにインストールしてみた訳です。

Shindigをインストールする

ShindigApacheの所で開発されているようで、下記からダウンロードできます。
Shindig – Download
今回は、Currentの「shindig-1.1-BETA5-incubating-php.zip」を使いました。SVNリポジトリから落とすと、Java版も含まれているため、ディレクトリパスの設定がちょっとめんどうだと思います。

zipを展開し、Webからアクセス出来るように各々で設定してください。注意点は、.htaccessも含まれており、mod_rewriteも必要になるということです。

<VirtualHost *:80>
ServerName shindig.localhost.man
DocumentRoot /home/wwww/shindig # zipを展開したディレクトリ
<Directory />
AllowOverride All # .htaccessを読み込めるようにする
</Directory>
</VirtualHost>

URLパラメータ付きでも動くようにする

上記のようにインストールすれば、とりあえずは動くのですが、僕が使う上でちょっと不便な部分があったので修正しました。
それは、コンテナのURLにパラメータが指定されている場合に上手く動かなかった事です。
正しくパラメータを処理できず、「400 – Bad Request」となってしまいます。

http://shindig.localhost.man/gadgets/files/container/container.html?view=canvas
こんな感じで引数で画面を切り替えていました。

# src/gadgets/servlet/FileServlet.php
# 40行目の下にパラメータを無視するようなコード追加
#
$file = str_replace(Config::get('web_prefix') . '/gadgets/files/', '', $_SERVER["REQUEST_URI"]);
$file = Config::get('javascript_path') . $file;
// ここを追加
$file = substr($file, 0, strlen($file) - strlen(strstr($file, '?')));
// make sure that the real path name is actually in the javascript_path, so people can't abuse this to read
// your private data from disk .. otherwise this would be a huge privacy and security issue
if (substr(realpath($file), 0, strlen(realpath(Config::get('javascript_path')))) != realpath(Config::get('javascript_path'))) {

署名付きリクエストに対応する

署名付きリクエストとは何か、それはオープンソーシャル開発をする上、外部サーバを呼び出したい場合にとても重要になってきます。「makeRequest」というJavaScript関数を使用し、外部サーバに非同期にリクエストを送るわけですが、ここで重要なのは、リクエストが改ざんされないように署名するということです。

Shindigで署名付きリクエストを使うために、opensslで秘密鍵と証明書を作成します。

$ openssl req -newkey rsa:1024 -days 365 -nodes -x509 -keyout test.pem -out test.pem -subj '/CN=mytestke
$ openssl pkcs8 -in test.pem -out private.key -topk8 -nocrypt -outform PEM

とりあえず: [Apache Shindig][お勉強][OpenSocial] メモ118 gadgets.io.makeRequest 認証認可タイプSIGNEDをやってみる(RSA-SHA1で署名)

出来た証明書と鍵をcertsディレクトリに保存し、Shindigの設定ファイルを書き換えます。

# config/container.php
'private_key_file' => realpath(dirname(__FILE__) . '/../certs') . '/private.key',
'public_key_file' => realpath(dirname(__FILE__) . '/../certs') . '/test.pem',
'private_key_phrase' => '',

これで問題なしと思われたのですが、上手く署名付きリクエストをおこなう事が出来ませんでした。

パラメータ付きURLから上手くmakeRequestがおこなえない

makeRequestで外部サーバを呼び出すときに、パラメータを付加すると上手く動かないという現象が発生しました。

var url = 'http://localhost/gadget/canvas?ts=1277893054';
gadgets.io.makeRequest(url, null, this.makeParams(data));

タイムスタンプ値を末尾に付加してリクエストを送っていたのですが、「?ts=1277893054」が問題で、このパラメータを上手く処理出来ていないために失敗しているようでした。

# src/gadgets/oauth/OAuth.php
# 186行目のbuild_signatureが実際に署名をおこなっている箇所になります。
public function build_signature(&$request, OAuthConsumer $consumer, $token) {
$base_string = $request->get_signature_base_string();
// Fetch the private key cert based on the request
$cert = $consumer->getProperty(OAuthSignatureMethod_RSA_SHA1::$PRIVATE_KEY);
// Pull the private key ID from the certificate
//FIXME this function seems to be called both for a oauth.json action where
// there is no phrase required, but for signed requests too, which do require it
// this is a dirty hack to make it work .. kinda
if (! $privatekeyid = @openssl_pkey_get_private($cert)) {
if (! $privatekeyid = @openssl_pkey_get_private($cert, Config::get('private_key_phrase') != '' ? (Config::get('private_key_phrase')) : null)) {
throw new Exception("Could not load private key");
}
}
// Sign using the key
$signature = '';
if (($ok = openssl_sign($base_string, $signature, $privatekeyid)) === false) {
throw new OAuthException("Could not create signature");
}
// Release the key resource
@openssl_free_key($privatekeyid);
return base64_encode($signature);
}

openssl_pkey_get_private関数によって、秘密鍵を取得し、$base_stringに対して署名していることが分かります。この$base_stringの中身はこうなっていました。

POST&http%3A%2F%2Flocalhost%3A3000%2Fgadget%2Fcanvas&dummy%3D1%26oauth_consumer_key%3Dcont%26oauth_nonce%3D96bd6e6d4103d3c5197f26d5dd6e3463%26oauth_signature_method%3DRSA-SHA1%26oauth_timestamp%3D1277893517%26oauth_token%3D%26opensocial_app_id%3Dappid%26opensocial_app_url%3Durl%26opensocial_owner_id%3Djohn.doe%26opensocial_viewer_id%3Djohn.doe%26ts%3D1277893516%26xoauth_public_key%3Dhttp%253A%252F%252Fshindig.localhost.man%252Fpublic.cer%26xoauth_signature_publickey%3Dhttp%253A%252F%252Fshindig.localhost.man%252Fpublic.cer

この時に「ts%3D1277893516」の文字列があり、パラメータ「ts」も含めて署名されている事が分かります。

続いて実際に外部サーバにリクエストを送る部分です。

# src/gadgets/SigningFetcher.php
# 111行目のsignRequestが送信リクエストを作成します。
# 174行目にクエリーストリングを処理する箇所があり、送信先リクエストにパラメータを追加して渡しています
$newQuery = '';
foreach ($req_req->get_parameters() as $key => $param) {
if (! isset($forPost[$key])) {
$newQuery .= urlencode($key) . '=' . urlencode($param) . '&';
}
}
# 問題の箇所
// and stick on the original query params too
if (isset($parsedUri['query']) && ! empty($parsedUri['query'])) {
$oldQuery = array();
parse_str($parsedUri['query'], $oldQuery);
foreach ($oldQuery as $key => $val) {
$newQuery .= urlencode($key) . '=' . urlencode($val) . '&';
}
}

一見問題ないように見えますが、$req_req->get_parameters関数が返す値には、既にクエリーストリングも処理されており、二重でクエリーストリングが処理されていることになります。
パラメータの二重化によって、署名されたリクエストと異なる値になってしまい、外部サーバでの署名確認時にエラーとなってしまいます。

パラメータが二重処理されたリクエストです。パラメータ「ts」が二つあることが分かります。

http://localhost/gadget/canvas?oauth_nonce=0c8c8040978beed7b0221f655ef50303&oauth_timestamp=1277893863&oauth_consumer_key=cont&ts=1277893863&opensocial_owner_id=john.doe&opensocial_viewer_id=john.doe&opensocial_app_id=appid&opensocial_app_url=url&oauth_token=&xoauth_signature_publickey=http%3A%2F%2Fshindig.localhost.man%2Fpublic.cer&xoauth_public_key=http%3A%2F%2Fshindig.localhost.man%2Fpublic.cer&oauth_signature_method=RSA-SHA1&oauth_signature=KTo5X7QxKg8mSpDiaGjljeyKAlmdMLO%2BbPrAr0qYycqAzqTSw8t44p2lXmdRZendFwEpbKLPZy9tAoJ98X9YVkOHjXsp6D19%2BtFBCgSQDJzuvWxHC6xKiRnw2iR0M0HcKSNeMf6x45W%2FJM9rwxT%2BdUYrDZ%2BO4IKbq1etvQj6nWs%3D&ts=1277893863&

src/gadgets/SigningFetcher.phpの181行目〜187行目までをコメントアウトすることで回避できます。

html_sanitize is not defined

これでようやく署名付きリクエストに対応出来たかと思われましたが、次に新たな問題が発生しました。
コンテナ内で「Tabs」Featureを利用した時に「html_sanitize is not defined」というJavaScriptエラーが出ることです。
どうやら、core Featureでhtml-sanitizer.jsというのを読み込むコードが足りないようです。

# src/gadgets/GadgetFeatureRegistry.php
// Make html-santitization work see SHINDIG-346
if ($content == 'res://com/google/caja/plugin/html-sanitizer.js') {
$content= 'http://google-caja.googlecode.com/svn/trunk/src/com/google/caja/plugin/html-sanitizer.js';
} 

このような記述があり、html-sanitizer.jsだけ特別な処置がされているようです。
今回は、Tabs Featureにhtml-sanitizer.jsを読み込ませるコードを追加します。具体的には、feature.xmlに以下のように追加します。

# features/src/main/javascript/features/tabs/feature.xml
<feature>
<name>tabs</name>
<gadget>
<!-- for gadgets.util.sanitizeHtml -->
<script src="res://com/google/caja/plugin/html-sanitizer.js"/>
<script src="tabs.js"/>
<script src="taming.js"/>
</gadget>
</feature>

これでまともに使えるようになりました。PHP版Shindigは地雷が多いのでJava版を使ったほうが簡単ということでしょうか。それともやり方がおかしいのか・・・?

PHPにPOSTでBase64の文字列を渡すときは注意

RubyのZlibで圧縮したデータをBase64にして、PHPのスクリプトにPOSTで渡すってことをやっていたのですが、圧縮データを展開できる時と、できない時があって悩んでしまった。

よくよく調べると、そもそもBase64をデコード出来ていなかった。それで調べてみると、PHPのドキュメントの下に書いてありました。
PHP: base64_decode – Manual
どうやら、POSTでデータを渡すと、Base64の「+」記号が勝手にスペースに変換されてしまうらしい。
以下のように修正したところ無事に動きました。

## str_replace でスペースを+に置換
$data = base64_decode(str_replace(' ', '+', $data));
## ヘッダ分を差し引いてあげないとだめなのね・・・
$_data = gzinflate(substr($data, 10, -8));

ちなみにRuby側です。
Zlib::MAX_WBITSに+16を足すと、前後に圧縮データ情報も付加されたGZIP形式になるそうです。

z = Zlib::Deflate.new Zlib::BEST_COMPRESSION, Zlib::MAX_WBITS + 16
param = [z.deflate(data, Zlib::FINISH)].pack('m')
z.close

携帯開発環境をMoxyからSSBに

今までの開発環境はMoxyを利用させて頂いていたのですが、OSを入れ直したついでにMoxyを新しくしようとしたところ、どうしてもうまく動かすことができませんでした。古いのでいいかと思ったのですが、SSBというのが目につきました。

どうやらこいつは、Rubyで出来ている携帯開発環境(ブラウザ?)らしい。インストールもあっさりできてたので、こっちを使って見ることにしました。どうもRailsで出来ているのかと思ったら違うみたい・・・。インタフェースも今風です。

SSBのダウンロード先

ssb –
CodeRepos::Share – Trac

早速、動かしてみたのですが一つだけハマりました。PHPのNet_UserAgent_Mobileを使っていたので、初期の設定で以下のようなエラーがでました。

DoCoMo/2.0 P905i(c100;TB;ser000000000000000;icc0000000000000000): might be new variants. Please contact the author of Net_UserAgent_Mobile!

ソースを確認したところ、マッチするUserAgentがないとエラーになるようです。ここで引っかかっています。

if (preg_match('/^icc(\w{20})?$/', $value, $matches)) {

どうやら、初期の設定だとiccが15桁なので20桁に変更してあげれば無事動きました。

はじめてのSQLite

はじめてSQLiteさわってみました。

さくらのワンコイン共有サーバ使っているのですがMySQLのDBは一つしか作れないのですね・・・。
不安定で遅い!というイメージだったので敬遠していたところがあったのですがMySQLより速い?らしい。よく考えたら軽い実装なのだから当たり前なのかな?

サーバの設定ではデフォで使えるようになっていた(PHP)ので、さっそくDBを作ってみよう!と思ったのだけど、よく考えたら安いプランでシェルが使えなかった。WebベースのSQLiteManagerというのを入れてみました。phpmyadminみたいなものみたいです。

無事にDBを作ってテーブルを流し込みました。型とか大丈夫なのかな?と心配でしたが、すんなりいって一安心。SQLiteは型の概念がほとんどないらしい。

ここまではよかったのですが、ここからちょっと引っかかりました。
PHPで昔作ったものでADODBというライブラリを使っていたのですが、DSNをSQLiteに書き換えても上手く動きません。

sqlite:///home/hogehoge/sqlite/hoge.db
SQL logic error or missing database

こんなエラーが出ました。パーミッション?SQL?と色々いじってみたのですが解決せず・・・。でもよく考えるとSQLiteManagerでは動いていた気がしました。ADODBのソースを見てみる事に・・・。

どうも独自に内部でDSNを処理しているらしく、parse_url関数の部分でエラーになってるっぽいです。ホスト名の指定がないせいで、正しいURLと解釈されないのが原因でした。絶対パスで指定するのが間違ってるのかな・・・?

sqlite://localhost/home/hogehoge/sqlite/hoge.db

こんな感じに直してみたらまだエラー。さらにソースを覗いてみると

if (empty($argHostname) && $argDatabasename) $argHostname = $argDatabasename;

どうもホスト名が空じゃないとだめらしい・・・。これは無理かなと思い、別の方法を考えることに。

$con =& NewADOConnection('sqlite');
$con->Connect('/home/hogehoge/sqlite/hoge.db');

これで動きました!これが一番簡単みたい。でもどうしてもDSNで指定したいと思い、ソースを眺めてたらこんな記述がありました。

if (($at2 = strpos($origdsn,'@/')) !== FALSE) {
// special handling of oracle, which might not have host
$fakedsn = str_replace('@/','@adodb-fakehost/',$fakedsn);
}

どうやら@を使えばホスト名を指定しなくてもOKらしいです。結局これで解決しました。

# ちなみに@の後に/を二つ書かないと一つ目は消されるみたい
sqlite://@//home/hogehoge/sqlite/hoge.db

そんなこんなで小一時間かかりました。
そういえば、NOW()なんてのも動かないんですね・・・。