まだプログラマーですが何か?

プログラマーネタとアスリートネタ中心。たまに作成したウェブサービス関連の話も http://twitter.com/dotnsf

2年前に書いたこのブログエントリの続きのような内容です:
類似画像検索とカラーヒストグラム


類似画像検索を実現するアルゴリズムを調べています。上記のブログエントリでは「カラーヒストグラム」と呼ばれる比較的簡単な方法を紹介しました。今回は Average Hash と呼ばれる方法を紹介します。


まず、この方法は名前に "Hash" というキーワードがついています。一般的なハッシュ(ハッシュ値、ハッシュ関数)では入力値が少しでも異なっていると出力値が全然別の値になる、という特徴があり、その特徴をいかしてパスワード(のハッシュ)を安全に保存したり、ブロックチェーンに応用されたりしています。

ただ今回紹介する Average Hash アルゴリズムで使われるハッシュはその点で意味合いが少し異なり、入力されたデータが似ていた場合に似た値を返すようなハッシュ関数を定義します。このようなハッシュ関数を使って、用意された画像のハッシュ値をあらかじめ求めておきます。そして類似画像を探したい画像についても同じハッシュ関数でハッシュ値を求め、そのハッシュ値が似ている画像は入力データが似ているはずと判断して回答の候補とする、という考え方に基づいた類似画像検索アルゴリズムです。つまり画像として類似しているかどうかを、比較演算が容易なハッシュ値の差で判断しよう、というものです。


より具体的にアルゴリズムを紹介します。例えばハッシュ関数を以下のように定義したとします:
  • 画像のバイナリデータをハッシュ関数の入力値とする
  • nxn のサイズを持つ整数配列がハッシュ関数の出力値とする。なおnは整数値とする
  • ハッシュ関数内ではまず画像を正規化する。具体的には入力画像を縦nピクセル、横nピクセルにリサイズし(画素数はnxn)、更にグレースケール変換する
  • 次にnxnにグレースケールされた画像の各ピクセルの色の濃さ(0~255)を調べ、その値の平均値 avg を求める
  • 再度nxnにグレースケールされた画像の各ピクセルの色の濃さを調べ、その値が avg 以上であればそのピクセルの値は 1 、avg 未満であれば 0 とみなす。これをnxnピクセル分求めて配列にする
  • この配列をハッシュ関数の出力値とする

これだけだと理解しにくいと思ったのでもう少し詳しく順を追って説明します。なお以下の例では n = 16 の例を紹介します。

ハッシュ関数への入力データを以下の画像とします(ちなみにいらすとや様からの画像で、元のサイズは 737x800 ピクセルです):
2019051701



ハッシュ関数ではこの入力画像をまず 16x16 にリサイズし、かつグレースケール化して正規化します。この時点で画像のピクセル数は (16x16=)256 です:
2019051702


この (16x16=)256 個のピクセルを左上から1つずつ取り出して RGB 値を調べます。この値は 0 から 255 の間の整数値で、0 に近いほど黒っぽく、255 に近いほど白っぽいことを意味しています。実際には 16 行ありますが、最初の3行はこのような感じでした:
2019051705


こうして 256 個のピクセルの RGB 値の平均値 avg を求めます。この例では avg = 198.763 であったとします。

改めて 256 個のピクセルの RGB 値をこの avg と比較します。ピクセルの RGB 値が avg 以上だった場合は 1 、avg 未満だった場合は 0 とみなしていきます:
2019051706


この avg と比較した結果を画像の左上から順に並べて配列にします(下図では16個ごとに改行して実際の2次元イメージに近い形にしていますが、実際は改行せずに1次元配列とみなします):
2019051703


この配列がハッシュ値となります。なんとなく元画像の中で白っぽい部分を 1 、黒っぽい部分を 0 とした結果になっていることがわかります。また、このハッシュアルゴリズムだと元画像が似ていると関数実行結果のハッシュ値も似る、ということが理解しやすいと思います。しかもハッシュ値は整数 256 個の配列なので類似性の判断も容易です。

なお、別のこちらの画像(サイズは 470x628)で同じアルゴリズムを実行すると、
smartphone_woman_smile


結果はこのようになりました:
2019051704


どのような画像に対してもまず同じサイズのグレースケール画像に変換しています(つまりグレースケールになった状態での類似性を調べるアルゴリズムです)。また各ピクセルを「その画像の各ピクセルの明るさの平均値よりも明るいか暗いか」で 0 または 1 に変換しています。これによって画像そのものが明るいものだったり暗いものだったりする要素を取り除き、その画像の中での明るい部分と暗い部分に分けるようにしています。そしてその結果がどれだけ似ているのか/似ていないのかを整数配列の類似度という比較的簡単な方法で調べられるようにしている、という特徴があることがわかりますね。


このアルゴリズムを使ってあらかじめ用意した画像の Average Hash 値を調べておきます。そして類似した画像を調べたい画像データが送られてきた場合にまず同じアルゴリズムで 256 個の1次元配列である Average Hash 値を求めれば、「0 と 1 が一致している数が多いほど似ている」と判断できることになります。

この方法であれば(実行パフォーマンスの様子を見ながらではありますが)nの値を大きくしたり、Hash 値を 0 か 1 にするのではく RGB 値をそのまま使って nxn 次元のユークリッド距離を求めることでより精度の高い類似画像検索が可能になります。あるいは別の応用としてグレースケールの手続きを省略して、カラー画像のまま比較することも可能です。


という、類似画像検索のアルゴリズムの1つを紹介しました。そんなに難しい数学知識を必要とせず、比較的理解も実装も応用もしやすいアルゴリズムだと思っています。


わけわからないタイトルになってしまいました。これは
  • ウェブブラウザの JavaScript を使わずに、HTML と CSS でマウスの軌跡を追跡する方法が発見された
  • 実際に確認できるサンプルが Go 言語で実装されていたので、JavaScript に移植してみた
ということです。

まず、元ネタはこれです:
Researcher Finds CSS-Only Method to Track Mouse Movements

spyware


セキュリティの研究者である Davy Wybiral 氏の以下のデモ動画付きツイートを紹介する形で伝えられていました。このデモでは JavaScript が無効にされた Tor ブラウザが使われていますが、確かに左画面でのマウスの動きが右画面で確認できています。左の画面をユーザーが使っていて、右画面ではそこでのマウスの動きがほぼリアルタイムに再現されています:




もともとウェブページにおいては JavaScript を利用することでマウスの動きを検知することができるようになっています。移動したり、クリックしたり、クリックが開放されたり、といったタイミングや、そのイベントが発生したときのマウス位置を知ること自体はこれまでも可能でした。

ただし、それには JavaScript が有効になっている、という条件があります。多くのウェブブラウザにおいて、JavaScript ははじめから有効になっているもので、あえて無効になるよう設定しない限りは有効なままです。また最近のウェブページも JavaScript が有効になっている前提で作られているものが多いので、JavaScript が有効であることが特別に危険ということはないと思っています。 一方で JavaScript を使ったイタズラページが存在していることも事実で、あえて JavaScript を無効にしてから利用する、というシーンが(それによって思い通りに動かない、ということはあるかもしれませんが)ないわけではありません。


・・・という中での今回のニュースです。安全性を高める目的でウェブブラウザの JavaScript を無効にしていても、マウスの動きがウェブページ提供側に知られてしまう可能性(というか方法)があった、というものでした。上述の Davy 氏が Go 言語で作成したサンプルも公開されています(みるとわかりますが、このシンプルなコードだけで実現できるという明瞭さ!):
https://gist.github.com/wybiral/c8f46fdf1fc558d631b55de3a0267771


で、自分がこれを参考にしてサーバーサイド JavaScript である、Node.js 向けに移植したサンプルを作ってみた、というものでした。なのでサブジェクトは正確には
 『クライアント JavaScriptを使わずにCSSでマウスを追跡する方法』をサーバーサイド JavaScript で実装してみた
という感じになりますかね。

ちなみに移植したコードはこちら:
https://github.com/dotnsf/noscript-tracking.js


で、(ブラウザ側の)JavaScript を使わずにどうやってマウスの座標を調べるのか、という話です。具体的には CSS の :hover 疑似クラスと、その background 属性に画像を指定することで、特定のエリアに入ったことを知らせるリクエストをサーバー側に発生させる、という方法によって実現しています。

上記移植コードを見ると、2つのページが定義されています。1つはコンテキストルート( "/" )へのリクエストがあった際に表示される index ページで、そのテンプレートは views/index.ejs です。もう1つは "/watch" へのリクエストがあった際に表示される watch ページ(テンプレートは views/watch.ejs)です。index ページには JavaScript は一切使われていないのですが、このページの上でマウスを動かすと、その軌跡がほぼリアルタイムに watch ページから確認できるようになる、という内容のサンプルです:
2019051501
(↑左が index ページ、右が watch ページ。index ページ上でマウスを動かす様子が watch ページ上に表示されている)


では JavaScript を使わずに、どうやって index ページから watch ページへマウスの軌跡を知らせているかを説明します。今回ブラウザの JavaScript は使いませんが、サーバーサイドのロジックは必要になります。要はスタンドアロンでどうにかできる、というものではないということです。

まず index ページについて、index ページにアクセスすると画面には格子状(今回の例では 50x50)のブロックが表示されます。個々の格子は <p> タグで構成されています。格子は見えないスタイルにすることも可能ですが、今回は視覚的にわかりやすいようにあえて枠線を表示することで見やすくしています。

そしてスタイルシートを使って、個々の格子(<p>)に :hover 疑似クラスと、その時に背景画像が設定されるよう指定します(つまり各格子の上にマウスが来ると、その格子に背景画像が表示されるように設定します)。

これが CSS だけでマウス軌跡を追跡する方法の肝になります。つまり「ある格子の上をマウスが通過した時に、画像を表示するようなリクエストがサーバー側に送られ」ます。そしてサーバー側はそのようなリクエストに対してエラー処理を行い(つまり画像は表示されない=何も変わらない)、画像を表示する変わりにリクエスト内容を記録します。これによってどの格子の上をマウスが通過したのか、という情報をサーバー側に溜めることが可能になります:
2019051603


そしてもう1つの watch ページ側では上記の処理によってサーバー側に記録されたマウスの軌跡情報ごと取得し、index ページと同様の格子ブロックを描画します。ただしその際にマウスが通過した格子だけには背景色が設定され、マウスが通過していない格子と視覚的に違いがわかるようにしています:
2019051604


この2つのページを横に並べて表示し、index ページ(下図左)上でマウスを動かすと、その情報が watch ページ(下図右)上で確認できる、ということが実現できています。なるほどね~。
2019051501


※僕のコードでは watch ページをリロードする機能までは実装していないので、F5 キーや Ctl+R などで watch ページを定期的に更新する必要がありますが、リアルタイムでサーバー側には記録されている、ということがわかると思います。



自分の「人生最初のプログラミング」は BASIC でした。

それも Visual Basic でなければ、N-88 BASIC でもありません。SHARP 製ポケットコンピュータに標準付属されていた BASIC(正式名称は知りません)で、一人用ブラックジャックなどを作って遊んでいたのでした。そんなわけで BASIC はそれなりの思い入れのあるプログラミング言語の一つです。

そしてヤフオクでたまたま見つけたファミリーベーシックを落札することができ、いつかこいつでプログラミング環境を・・・と思ったまま2年近く経ってしまいました。 (^^; この連休を使って改めてファミリーベーシックによるプログラミング環境を構築してみました。どれだけ需要があるか不明ですが(笑)、その経緯をまとめました。


まず「ファミリーベーシック」を知らない人向けの説明を。これは任天堂伝説の家庭用ゲーム機であるファミリーコンピュータ(以下、ファミコン)を使って動かすプログラミングソフトです。ファミコンは8ビットCPUを搭載した本体に ROM カセットと呼ばれるゲームカートリッジを差し込んで使うことで、様々なゲームソフトを楽しむことができました。2016 年には代表的な 30 本のゲームソフトを内蔵した「ファミコンミニ」が発売されて話題になりました。

ファミリーベーシックはそんなファミコンのソフトの1つで 1984 年(昭和 59 年)に発売されました。完成されたゲームそのものを楽しむというよりも、音楽を演奏したり、ビット絵を描いたり、、といった創作活動を楽しむソフトカートリッジでした。またコントローラーもファミコン付属のものを使うのではなく、ファミリーベーシックカートリッジに付属している外付けキーボードを接続して、キーボードによる入力がサポートされていました。このファミリーベーシックが持つ機能の1つが「BASIC 言語によるプログラミングと実行」でした。まだプログラミングが今ほど一般的でなかった時代にリリースされた、画期的すぎるソフトウェアでした。

そんなファミリーベーシックをヤフオクで(実行環境などをよく調べずに)落札し、しばらく経って実際にプログラミング環境を整えてみよう、と思い立ったのでした。普通に安いファミコン互換機(以下、FC互換機)を所有していたので、それを使って接続すればよい、と軽く考えていたのですが、いざ実際にパッケージを開けて接続してみようと思ったら意外な問題が発覚しました。



ファミリーベーシックは外付けキーボードを使うプログラミングソフトなのですが、この外付けキーボードはゲームコントローラーの代わりに本体に付けるものだとばかり思っていました(なのでファミコンのゲームコントローラーが使えるFC互換機であれば動かせると思っていました)。しかし実際には上記ツイートのようにエキスパンドコネクタと呼ばれる拡張インターフェースを使って接続する必要があるものだった、という事実が発覚したのでした。

自分が所有していたFC互換機を調べてみてもエキスパンドコネクタは付属していませんでした。ということは、少なくともこの時点で所有している機器だけではカセットを挿してソフトを起動することができてもキーボードを使って操作することはできない、ということです。それではプログラミング環境としてはあまりに貧弱なので、改めてエキスパンドコネクタ付きのFC互換機を探す必要がありました。

で、秋葉原に向かって、こういうのに詳しそうな「スーパーポテト」というお店へ行き、店長さんと相談しながら調べてみました。結論としては以下の2つの選択肢から選ぶ必要がありそうでした:
 ・互換機ではない「中古のファミコン」を購入するか、
 ・レトロフリークというFC互換機を、コントローラーアダプターセット付きで購入する

実はもう少し選択肢があるかと勝手に思い込んでいたのですが、エキスパンドコネクタ付属というのは思っていた以上に高い壁となりました。FC互換機で付属しているものは皆無で、唯一レトロフリークだけはオプション機器であるコントローラーアダプターセットがあればエキスパンドコネクタのインターフェースを持つこともできる、という状態でした。ちなみにFC互換機は安いものだと 2000 円前後で購入できるのですが、レトロフリークをコントローラーアダプター付きで購入すると 20000 円を超えます。出費額が完全に想定外。。。

ちなみにFC互換機でなく、本物のファミコンを中古で買う、という選択肢もありました(値段は少しだけこちらの方が安い)が、これだと AV 出力がアナログ、つまり昔のアナログ端子を持ったテレビでないと接続できません。一方のレトロフリークは HDMI 接続もできるという長所もあり、結論として、現在ファミリーベーシック環境を揃えるならレトロフリークが必要、ということになると思います。というわけでレトロフリークを購入しました:



こういってしまってはアレですが、昭和59年発売のゲームソフトを今の環境で再現する、という需要そのものが少ないと思っています。いますが、一方で「レトロフリークでファミリーベーシックを動かす」という環境での実現例を探すことができませんでした。「もしかしたら動かなかったりして・・」という不安に駆られつつも、実際に試せば済む話なので挑戦してみました(結論としては問題なく動きました)。

まずは普通(?)にレトロフリークを箱から取り出してセットアップします。本体にコントローラーを接続し、また HDMI ケーブルをモニターに接続して、それぞれの電源を ON にします。普通に起動しました。一般的なファミコンゲームソフトを動かすだけであれば、ゲーム ROM カセットをレトロフリークに差し込めば動くはず:
IMG_6241


さてここからがファミリーベーシックを使う場合のセットアップです。レトロフリーク付属のコントローラーアダプターがこれ。このアダプタにエキスパンドコネクタのインターフェースもついているので、こいつをレトロフリークに接続します:
IMG_6242


コントローラーアダプターをレトロフリークに接続し、そのエキスパンドコネクタにファミリーベーシックのキーボードを接続します。そしてファミリーベーシックのゲーム ROM も挿入:
IMG_6243


そして電源 ON ! おお!起動してるっぽい!! 
IMG_6245


そしてコントローラーのボタンを適当に押すと、なにやらメッセージが。「ワタシハファミリーコンピュータ デス」。ほうほう、そうですか。カタカナで聞かれるのがもう昔っぽい:
IMG_6248


そして「アナタハ ダレデスカ? ナマエヲ イレテクダサイ」と聞かれました。いよいよキーボード入力・・・ おお、普通に認識している!! レトロフリーク+HDMI 接続環境でもファミリーベーシックとそのキーボードはちゃんと動くようです:
IMG_6246


ちなみにこのキーボード、よく見ると "BS(Back Space)" キーがありません。間違えて入力した場合は矢印キーで戻って上書きしていくスタイルのようです:
IMG_6247


※ついでに書いておくと、このキーボードの F キーや J キーに他のキーと比べた特徴がなく、ブラインドタッチが非常に難しい、という難点がありました。。


そして約 30 年ぶりとなる古典 BASIC のプログラミング。当然スクリーンエディタ的な便利なものはなくて、プログラミングモードの画面に行番号を付けて入力していく感じ。とりあえず "HELLO WORLD."、まあ普通に動く動く: 
IMG_6251


なお、このソフトはプログラミングだけでなく、楽譜(音源)を入力して演奏させたり、日付を入力して(バイオリズム的な?)占いをすることもできます。世間では令和対応が間に合うとか間に合わないとか話題ですが、昭和59年製のこのソフトでは当然平成対応もしていません(笑):
IMG_6249


まあ表記以外は別にこれで困らないんだよな。。


今でもファミリーベーシックはヤフオクアマゾンで売られていることを見つけることがあって、入手困難というレベルではないと思っています。 ノスタルジーからつい買ってしまった人が現代の環境で実際に動かす際の参考になれば。



このページのトップヘ