荒い写真の空白を埋める数学の魔法「compressed sensing」!(動画あり)

荒い写真の空白を埋める数学の魔法「compressed sensing」!(動画あり) 1

「もっとズームしてくれ...そうそこだ...そいつの顔をもっとエンハンスしてくれないか...」と頼むと技師がカチャカチャやって容疑者Aの顔がクッキリ―というドラマでお馴染みのシーンが現実に

これを可能にしたのはスタンフォード大学エマニュエル・キャンデス(Emmanuel Candes)教授とUCLAテレンス・タオ(Terence Tao)教授が開発した「compressed sensing(CS)」という技法です。

映画のフェイクUIとは別物。このオバマの写真みたいに、低画素のざらざらなイメージ(左)も高画素のきれいなイメージ(右)に加工できるんですよ。

主に研究目的で開発されたもので、例えばMRIスキャンもデータを丸々じゃなく、少量だけスキャンして残りの部分は予想で埋めることができるので、時間が大幅に短縮できます。

それにしても、まばらな画像の間を素早く埋めるのに必要なナンバークランチング(大量の演算)を全部どうこなすのだろう? 画像はそれこそ幾通りも考えられる。それを全部分析するとなると、膨大な時間がかかり兼ねない。だが、Candès教授とTao教授には、最もまばらな画像というのはそれを構成するブロックの数も最小だということが分かっていた。さらにL1最小化を使えばそれが探せる、それも素早く探せる、ということも。

それを実行に移すには、まず不完全な画像をアルゴリズムにかけ、空いた隙間を大きなカラーのブロックで埋めるところから着手する。で、例えば仮に緑のピクセルが近場に固まっていたら、緑と緑の隙間を大きな緑の長方形でドッカリ埋めるとか、そんなようなことをやる。黄色のピクセルの塊を見つけたら黄色の長方形で埋める。いろんな色が散在するエリアは、もっと小さな小さな長方形や他のかたちのもので各カラーの間を埋める。それを何度も何度も繰り返しやっていく。するとしまいには考えうる中で最も少ない構成ブロックの組み合わせで100万ピクセル(メガピクセル)が全部カラーで埋まった画像が出来上がるのだ。

その画像が最もまばらな画像だとか、自分が復元しようと考えていたものとまったく同じ画像になるという100%の保証はない。が、Candès教授とTao教授は仕上がりの画像が実物と異なる可能性は限りなく小さいことを数学的にデモしてみせた。ラップトップの処理にはまだ数時間かかる可能性もあるが、幼児の両肺の呼吸を1分長く止めさせるのに比べたら、コンピュータで1時間長く待つ方が好ましい。

ワイヤードの記事を読むと、麻酔で呼吸を2分間も止めておく必要もないので体に負担もかからず、既にスタンフォード大学ルシル・パッカード小児病院などで使われている、とありますね。

L1最小化を活用するというアイディアはCandès教授が2004年2月、「Shepp-Logan Phantom」という画像をコンピュータで眺めていた時に思いついたそうです。これはコンピュータ科学者やエンジニアがアルゴリズムのテストで使う画像で、『未知との遭遇』で出てくる宇宙人みたいなものです。教授はその時、MRIスキャンが未完で終わった時に出る幽霊みたいな画像をなんとかスッキリできる方法はないものだろうかとイロイロ試行錯誤していました。

で、ふと「l1を使えば、ちょっとはスッキリするんじゃないかな?」と閃いて、そのアルゴリズムをキーに打ち込んでみたんです。すると...

 クッキリすっきり細部までレンダリングされてしまったのです、魔法のように! あまりのことに、教授はびっくり仰天。「そんな馬鹿な、あり得ない」と思ったそうです。

「それは喩えて言うならこの僕が、10桁の銀行口座番号の頭3桁もらって残り7桁をヤマ勘でぴったり当てたというぐらいのあり得なさですよ」(教授)

タイプが異なる他の心霊写真っぽい画像で同じ実験を試してみたんですけど、毎度毎度クッキリスッキリなるではあ~りませんか! 

これはエラいこっちゃ、ということで、さっそくUCLAの仲間のTao教授を研究に引き入れて論文を共同執筆。発表からまだ6年しか経ってないのに、この「compressed sensing(CS)」にヒントを得た論文は既に何千と執筆されており、これ関連の研究には米政府から何億円という予算がつきました。また、2006年には全米科学財団(NSF)最高の栄誉であるWaterman賞に輝き、賞金50万ドルも獲得。

2007年に話題になったSeam Carvingは2008年秋CS4に統合されましたが、こちらは将来、医療・軍事など様々な分野に応用が期待されています。まだ化学分野の研究用途に限られてますけど、もしかしたら僕らみんなの家にある写真を自動的にエンハンスしてエンハンスしてエンハンスしまくる時代の第1歩かもしれませんね。すごい!

 

[Wired]

Adam Frucci(原文/satomi)