類似画像を検索する方法を調べみた その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フィルタを使ってエッジの抽出をおこなった画像を、3x3に分割し、各領域のエッジ割合を比較する、という方法のようだ。

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

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

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

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

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

「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回で大体２～３秒だったので、
シグネチャをどっかに保存しておけば、10万画像の線形比較くらいなら許容範囲ではないかと思われる。

激ニコぷんぷん丸のソースコード公開

先日リリースしたiPhoneアプリ「激ニコぷんぷん丸」のソースコードをGitHubにアップした。
特にいいアイデアも浮かばなかったので、多少インパクトがあって実績になりそうなものを作った。
が…色々迷走した挙句、よく分からないアプリが完成した。
使い道がないのでソースコードをGitHubにアップすることにした。
テストコードも書いてなく、あまりいいコードではないけど何かの参考になれば…。

Pinterestのようなインタフェースで、ツイッター上に流れているニコ動を表示するアプリ。
ツイッター上の動画情報は、ツイッターのストリームAPIを使ってリアルタイムに取得している。
クライアント部はObjective-C、サーバ部はRails3(Unicorn + NginX) + MySQL + Redisで出来ている。

とりあえず、クライアントアプリだけ。
pontago/objc-NicoTwi · GitHub

iOS7対応

面倒くさがりなのでブログを書く頻度が少なかったのだが、なるべく細かい記事でも書くことにした。
iOS7がリリースしてしばらく経つのだが、ようやくひと通りiOS7対応が終わった。
後手後手の対応で、アップデートが遅くなってしまいスミマセン。

今回はメジャーアップデートということもあり、大幅なUI変更が加わった。
流行のフラットUIに変わったことで、iOS6以前と両方サポートするアプリは少し大変かもしれない。

ステータスバーが一体化した

一番やっかいな問題が、ステータスバーの一体化だ。
ステータスバーをアプリから操作（色の変更や透過、表示・非表示）出来るようになったため、UINavigationBarなどと違和感なく一体化させることが可能になった。

今まではステータスバーを除いた座標から取得出来ていたのだが、iOS7からはステータスバーの20px分が含まれなくなった。このせいでデザインが崩れてしまうアプリがけっこうあると思う。

手っ取り早いのは、UIWindowをステータスバー分ずらしてしまうことだ。こうすることでiOS6以前と同じように処理することができる。

    if ([[UIDevice currentDevice].systemVersion floatValue] >= 7.0f) {
      [[UIApplication sharedApplication] setStatusBarStyle:UIStatusBarStyleLightContent];
      self.window.clipsToBounds = YES;
      self.window.frame = CGRectMake(0, 20.0f, self.window.frame.size.width, self.window.frame.size.height - 20.0f);
      self.window.bounds = CGRectMake(0, 20.0f, self.window.frame.size.width, self.window.frame.size.height);
    }

UINavigationBarのbarTintColorやtintColorを変更することで、ステータスバーの色も変わる。

Objective-C - iOS7でナビゲーションバーやステータスバーの文字色を変える - Qiita [キータ]

UINavigationBarの戻るが変わった

前のビューに戻るときのボタンが「<」みたいなのになった。
そのため、backBarButtonItemなどにイメージ付きのUIBarButtonItemを設定すると、「<」分ズレて表示がおかしくなる。

僕は手っ取り早く、backBarButtonItemではなく、leftBarButtonItemに設定してしまった。
具体的には、UINavigationControllerを派生したクラスを作成し、pushViewControllerをオーバーロードする。
その中で、viewControllersをカウントし、0以上の場合（一つ以上ビューがプッシュされている）に、戻るボタンを設定する。例えば以下のようなコードになる。

- (void)pushViewController:(UIViewController *)viewController animated:(BOOL)animated {
    if ([self.viewControllers count] > 0) {
      viewController.navigationItem.leftBarButtonItem = [[UIBarButtonItem alloc] 
        initWithImage:[UIImage imageNamed:@"back.png"] style:UIBarButtonItemStylePlain 
          target:self action:@selector(popViewControllerAnimated_)];
    }

    [super pushViewController:viewController animated:animated];
}

- (void)popViewControllerAnimated_ {
    [self popViewControllerAnimated:YES];
}

カスタムUIBarButtonItemのアイコン色が反映されない

iOS7になってから、ボタンに設定した画像がtinColor（青色とか）で塗りつぶされるようになった。
UIBarButtonItem内にUIButtonをカスタムビューとして設定していたのだが、tintColorで塗りつぶされなかった。
どうやら、UIButtonの種類が、UIButtonTypeSystemまたは、UIButtonTypeRoundedRectの場合にのみtinColorで塗りつぶしされるようだ。

EZ-NET: iOS 7 では標準ボタンの画像が tintColor で塗りつぶされる : iPhone プログラミング

UITableViewのセル背景色が反映されない

UITableViewCellの背景色は、デフォルトで白？になったようだ。
変更する方法は、tableView:willDisplayCell:forRowAtIndexPath:か、tableView:cellForRowAtIndexPath:のどちらかから、backgroundColorをclearColor（もしくは好きな色）に変更するといい。

- (void)tableView:(UITableView *)tableView willDisplayCell:(UITableViewCell *)cell forRowAtIndexPath:(NSIndexPath *)indexPath {
    cell.backgroundColor = [UIColor clearColor];
}

疲れたのでこのへんで。

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

タクトスイッチを使う

温度計にモード切り替え（最高温度、最低温度）を付けたかったので、タクトスイッチの使い方を調べることにした。
まずは、マイコンを使わずにタクトスイッチを使って、LEDを点灯・消灯させる。
かなり苦戦したのだけど、いろいろな人に教えてもらって何とか完成させることができた。

タクトスイッチの構造

タクトスイッチは押すとカチッと手応えのある押しボタンだ。押している間だけ電流が流れるらしい。
足は4本付いていて、押すことで2本の足が接続され電流が流れるという、単純な仕組みのようだ。

下記のページを参考にさせてもらった。
arduino使い方：スイッチの入/切でＬＥＤを点灯

タクトスイッチを使ってLEDを操作

押している間だけLEDを点灯させる回路を作ってみることにした。
回路は下記のページを参考に組んでみた。

スイッチ回路 - Hinemos amo!

マイコンを使ってタクトスイッチを操作

続いて、マイコンを使ってLEDを点灯させてみることにした。

PD3にLEDを接続、PD4にタクトスイッチのアノードを接続した。
PD4は入力になるため、DDRDレジスタでビット4を0にし、PD3は出力で使うため、ビット3を1にする。
また、内部プルアップを有効にするために、PORTDレジスタのビット3を1にする必要がある。

これは、スイッチがどこにも接続されていない場合、電圧が不安定になり0なのか1なのか分からなくなってしまうためだ。
それを防ぐためにスイッチとの間に抵抗をはさむ必要があり、これをプルアップ抵抗という。
AVRの場合、プルアップ抵抗を内蔵しているので、上記のようにPORTDレジスタのビットを立てると、内部プルアップ抵抗が有効になる。

あとは、bit_is_clear関数でPD4が0になっているかチェックし、LEDの点灯させるだけだ。
bit_is_clear関数は、第一引数にチェックするレジスタ（PORTBやPORTD）、第二引数にチェックするビット番号を指定する。
0になっているとtrueが返ってくる。同様にbit_is_set関数は、1になっているとtrueが返ってくるようだ。
この関数を使えば、簡潔に記述することができる。

この回路はそのものズバリのものが、下記ページに書いてあったので参考にさせてもらった。
LED点灯 （ IO入出力 ）
top

長押しを判定する

スイッチのオン・オフの他に、長押しを実装してみることにした。
モード切り替えはスイッチの短押しを使って、最高温度や最低温度は長押しでリセット出来るようにするためだ。

長押しを判定するためにタイマ割り込みを使うことにした。しかし、とてもむずかしく長い道のりとなった…。
短押しと、長押しを判断するのがこんなにむずかしいとは思わなかった。
普段何気なく使うことが多いのだけど、単純な仕組みでも一から作るとなるとむずかしいもんだ。

回路図は下記のようになった。

タイマ割り込みを使う

タイマ割り込みについては説明しているサイトがたくさんあるので割愛する。
下記のサイトが詳しく説明されていて参考になった。
http://d.hatena.ne.jp/hijouguchi/20100620/1276997802

簡単に説明すると、カウンタ用レジスタ（TCNT0）があって、一定周期毎にこのレジスタの値がカウントアップされていく。
レジスタがオーバーフローしたり、設定した値に到達すると割り込みハンドラが呼び出されるというものだ。

大事なのは、クロック数と分周比から何秒ごとに割り込みハンドラが呼び出されるのかを考えることだと思う。
今回は、ATTINY2313を8MHzで動かしていて、分周比を1024に設定した。（他にも256や8など設定できる）
分周比は、「TCCR0B」レジスタで設定する。分周比1024なので、0b00000101となった。

8000000(8MHz) / 1024(分周比) = 7812.5Hz

となるので、1秒間に7812回動作するとうことだ。

1(秒) / 7812(Hz) = 約0.000128秒 = 0.128ms（ミリ秒）

0.128ms毎にカウントアップされていくことになる。
今回はカウンタ用レジスタがオーバーフローしたときに割り込みハンドラを呼び出すようにした。
カウンタ用レジスタは8ビットなので、256になるとオーバーフローすることになる。

0.128(ms) * 256 = 32.768ms

約32ms毎に割り込みハンドラが呼び出されるようだ。

タイマ割り込みの実行

タイマ割り込みを使うためには、「interrupt.h」をインクルードする。
TCCR0Bレジスタ、TIMSKレジスタを設定した後、sei関数を呼び出すことで実行される。
sei関数は、全割り込みを有効にさせる関数だ。逆にcei関数は、全割り込みを無効にさせる関数になる。

割り込みハンドラは、ISRマクロを使って設定する。
最初ISRは関数だと思ったのだけど、よくよく見てみるとマクロになっていた。
第一引数に使うハンドラ名を入れる。
今回は、TIMER0のオーバーフローということで以下のようになった。

ISR(TIMER0_OVF_vect) {
}

長押しをどのように判断するか

短押しと長押しを区別させるのに苦労した。
32ms毎にスイッチが押されているか判断し、3秒以上押されてい場合に、長押しと判断させることにした。
3秒未満でスイッチを離した場合は、短押しとなるようにした。

押した場合に判定させてしまうと、短押しと長押しのイベントが同時に起きてしまい、動作がおかしくなってしまう。
なので、長押しと区別させるために、短押しの場合、リリース時（スイッチを離した時）に判定させることで上手くいった。

また、長押しされている時間を調べるために変数にハンドラ呼び出された回数を保存することにしたのだけど、ずっと長押ししているとカウンタ変数がオーバーフローしてしまい誤動作するということがあった。
カウンタ変数を大きいものして一時しのぎすることも出来るのだけど、今回は「長押し判定時間の3秒を越えた場合、カウントアップさせない」ことで対応した。

今回のコードもGitHubにアップした。
pontago/avr-TactSwitchTest · GitHub

参考サイト
[AVRexample] Timer0 オーバーフロー | 花夢電科雑多猫
無機物の週末 超☆ゆとり的電子工作 その２！
http://d.hatena.ne.jp/hijouguchi/20100620/1276997802
http://www.hokutodenshi.co.jp/PUPPYSupportPage/ensyu/timer/timer2.html
AVR timer(1) | stastaka's Blog
タイマ/カウンタ1を使う
[example] 外部割り込み - 花夢電科雑多猫 マニュアル&メモ
つくろぐ 技術系

トランジスタアレイを使う

トランジスタや抵抗の数を減らすためにトランジスタアレイを使うことにした。
トランジスタアレイは、TD62064APGというNPN型の4chのものを使用した。

7セグ3桁のトランジスタ・抵抗を置き換える

7セグで使っていたトランジスタと抵抗を置き換えることにした。
7セグ一つに対して、トランジスタ1つと抵抗が二つ減ることになるので、だいぶスッキリするはずだ。

4chなので、O1~4、I1〜4が各セットあり、中央にGND、そしてCOM（コモン）が二つある。
Oはアウトプット、Iはインプットということらしい。
I1〜4にマイコン、O1〜4は7セグのコモンと接続する。
COMには、トランジスタを保護するためのダイオードが付いていて、これをフリーホイルダイオードというらしい。
誘導性コイル負荷（モータ、ソレノイド、リレー等）を使わなければ、特に接続する必要はないようだ。

ベース抵抗なども付いているので、計算などは必要なく、そのまま置き換えればいいだけなので簡単だった。

回路図を書いてみる

あまりにもさっくり終わってしまったので、回路図を書いてみることにした。
最初はドローソフトで適当に書いてみたのだけど、回路図を描くのが意外と楽しかったので、専用ツールを使って書き直した。

OSXでも使える回路図作成ツールを探してみると、BSchV3というのを見つけた。古くからあるツールで有名らしい。
回路図の読み方を調べつつ適当に描いてみた。合ってるかな？

参考
電子部品使い方：マイコン出力のスイッチ(トランジスタ２)
トランジスタアレイ「TD62083AP」のホントの使い方
初歩のＰＩＣ【１８】デジタルは５Ｖであらず・出力編
Qt-BSch3V の使い方 - ルギア君の戯言

USBシリアル変換モジュールを使う

またもや電子工作をサボってしまった…。
プライベートもプログラミングをバリバリやってる人はすごいと思う。

この間マイコン先生から電子工作用の部品を色々いただいた。
ジャンパー線やLCDなど便利なものばかり…感謝感謝。

どうやら半年くらいご無沙汰だったみたいだ。
今回さわったシリアル変換モジュールなどの部品は、実は正月に買っておいた。
ケースやら基盤なども買い込んだので、早いところ温度計を完成させてもいいのだけど、リハビリも兼ねてシリアル通信をやってみることにした。

USBシリアル変換モジュールをマイコンに接続

購入したシリアル変換モジュールは、秋月電子で売っていたもので、FT232RLというUSB-シリアル変換用のICが基盤にくっついるものだ。
接続は簡単で、バスパワーでUSBから電源を確保できるので、GND、TXDとRXDをマイコンと接続するだけで大丈夫らしい。
マイコンはATTINY2313を使用した。

TXDとRXD

変換モジュールに付属されていた説明書にも記載されているのだけど、TXDは「通信データ出力」、RXD「通信データ入力」ということらしい。
これをマイコン側のTXDとRXDにクロスして接続する。最初にクロスで接続することに気づかず焦った。
要は、変換モジュールのTXDをマイコンのRXDに、変換モジュールのRXDをマイコンのTXDに接続する。

変換モジュールとPCを接続

ドライバが必要なようだったので、下記のサイトからダウンロードした。MacBookAirを使っていたので、OSX版をインストールした。
Virtual COM Port Drivers

screenでシリアル通信も出来るようだったのだけど、他に使いやすいものがないか探したところ、CoolTermというアプリを発見した。とりあえず、こいつで行くことにした。
Roger Meier's Freeware

USART（UART）

詳しい説明はググれば出てくるのでざっくり説明すると、
1本の信号線上の信号をプロトコルに従い「1」、「0」でデータを送る通信方法。
全二重の非同期通信、半二重の同期通信の二通りがあるようだ。

ボーレート

変復調速度のことでマイコンのクロック数によって設定する値が変わる。マイコンのデータシートに一覧が載っているので、クロック数と通信速度から適切なものを選べばいい。
一般的な通信速度9600bpsで通信することにした。
マイコンのクロック数は8MHzなので、設定するボーレートは51となった。

シリアル通信してみる

よく使われている設定でシリアル通信をおこなうことにした。
設定内容は、非同期通信、パリティ禁止、停止ビット1bit、データビット長8ビット。

まずは初期化処理のコードは下記のようにした。

UBRRL = 51; // 9600bps
UCSRB= (1 << RXEN) | (1 << TXEN);
UCSRC = (1 << UCSZ1) | (1 << UCSZ0);

UBRRLレジスタにボーレート値を入れる。
UCSRBレジスタで、RXENとTXENのビットを立てる。RXENが「受信許可」、TXENが「送信許可」になる。
UCSRCレジスタは、UCSZ1とUCSZ0が「データビット長」になる。
8ビットの場合は、「011」になるので、UCSZ1とUCSZ0の両方のビットを立てればOKだ。
本当は、UCSZ2もあるのだけど、これはUCSRBレジスタのほうに入っている…紛らわしい。今回は8ビットなので特に設定する必要はない。

コードは、ググればたくさん出てくるし、データシートにも書いてあるので特に迷うことはなかった。
とりあえず、シリアル通信の送受信を実装し、ターミナルから送信した文字列をそのままエコーバックさせるコードを書いてみた。

コードはこちら
pontago/avr-SirialTest · GitHub

参考サイト

有効なWikiNameではありません - AVR・ARM等々 覚え書き
エラー - henteko.org
電子工作の知恵袋 ＞ 通信規格 ＞ ＵＡＲＴ その１ 基本