Sensor - Rules

Arrow_down  Download Sample Code

「Compressive Sensing」が第21回 MATLAB オンライン・プログラミング・コンテストです。

課題

典型的なデジタルカメラには数百万画素以上のセンサーが搭載されています。撮影された画像の画素データは、センサーからメモリに転送されます。メモリ内ではJPEGのようなアルゴリズムでデータが圧縮され、生の画素データは消去されます。よく考えると、ここには無駄があります。せっかく時間、エネルギー、そしてメモリを使ってセンサーからデータを取得したにも関わらず、そのほとんどをすぐに捨ててしまっているからです。最初から必要な画素だけを取得すればいいのではないでしょうか。これが「Compressive Sensing」という概念とこのコンテストの背景にある基本的な考え方です。[参考記事を参照してください]

今回のコンテストでは、「非圧縮」の撮像画像の実画素値を再構成していただきます。これを「圧縮」センサー値、つまり、非圧縮画像内の画素値の合計を取得することにより達成してください。その値をクエリするには、興味のある領域に対してマスクを入力します。すると、そのマスクに応じた画素データの合計が戻ります。非圧縮の画素値を再構成するために要求できる圧縮センサー値には上限があります。 これの参考例を見てみましょう。以下のような行列Aがあるものとします。 
 A =
 [ 0 0 0 0 0 ]
 [ 0 1 0 0 3 ]
 [ 0 1 7 0 0 ]
 [ 0 8 2 2 0 ]
 [ 0 0 0 0 0 ]
次に、以下のようなクエリ用マスクがあるとします: 
 mask =
 [ 0 0 0 0 0 ]
 [ 0 1 1 0 0 ]
 [ 0 1 1 0 0 ]
 [ 0 0 0 0 0 ]
 [ 0 0 0 0 0 ]
マスクを重ね合わせた行列のイメージはこうなります。

マスクが適用された領域の画素値の合計は、9 となります。

構文

エントリーされたコードは、以下のように二つの引数と一つの戻り値がある関数として実行されます: 
 Aest = solver(imageSize, queryLimit)
画像は常に正方形なのでimageSizeは一辺の長さを示します。戻り値Aestは実画像から再構成された推定画像です。エントリーするコード内では、queryLimit回数までqueryImage関数を呼び出すことができます。queryImage関数の構文は以下の通りです。 
 pixelSum = queryImage(mask)
入力するマスクは、論理クラス型でなければなりません。戻り値pixelSumは、マスクされた画像領域内の全ての画素値の合計です。これは以下のような単純な計算で算出されます。 
 pixelSum = sum(A(mask))
この問題の解として最小化したい目的関数は実画像と再構成画像の差の絶対値の合計です。コードではこうなります。 
 imageDiff = abs(Aest - A)
 result = sum(imageDiff(:))
この結果が得点上最も重要な要因です。全体的な採点方法については、下記の「採点」の項目をご覧ください。

参考例

前出の同じ画像行列を再構成しようとしているとします。以下が真であるとします:
  • imageSize = 5
  • queryLimit = 2
実画像を見ることはできないので、大きさについて知りたいとします。最初に思いつくことは、画像全体をクエリすることです。 
 mask = true(imageSize);
 pixelSum = queryImage(mask)

これを実行すると、行列内の全要素の合計である24が戻ります。次に、どこか下位領域をクエリしてみます。 

 mask = false(imageSize)
 mask(2:4,2:5) = true
 pixelSum = queryImage(mask)

なるほど! 答えはまた24です。つまり、除外された領域は全て0だということです。これ以上クエリできるないので、最良の推定は、選択した領域に以下のように均等に配分すりことです。

これは、合計で24の誤差を出します。

その他の注意事項

  • 画素値は常に0と255の間の整数です。
  • 画像は常に正方形です。
  • queryLimit回を超過してqueryImageを呼び出してもエラーにはなりませんが、戻り値は0となります。

採点

あなたのエントリーの総合得点は複数の要因の組み合わせです。最初の二点が最も重要です。残りの二点は副次的な影響があります。
  1. 全ての課題を通しての結果の平均値
  2. コードの実行速度
  3. コードの循環的複雑度 (詳しくは下記を参照してください)
  4. コードのノード数 (詳しくは下記を参照してください)
いずれの要因も最小化するのが目的ですので、コンテスト終了時の最低得点が優勝となります。

循環的複雑度

循環的複雑度は、McCabe複雑度ともいい、プログラムのソースコード内の独立パス数の尺度です。通常、この数値が大きいほど、プログラムの内容の理解が困難になります。またテスト、修正、リファクタリングも難しくなります。

ファイル内には、複数の関数が含まれる可能性がありますので、あるファイルの複雑度は、そこに含まれる関数のいずれかの最大複雑度により定義されます。標準的な指標は、個々の関数の複雑度を10以下に抑えることですので、このコンテストでは、10を超過した複雑度に応じて得点が上がります。つまり、全ての関数の複雑度が10以下のエントリーには、複雑度のペナルティーは課されません。

MATLABでは、mlintで「cyc」オプションを指定することにより、どの関数でもその循環的(またはMcCabe)複雑度を計測できます。例えば、この例を試してください: 

>> mlint -cyc magic.m

エントリーの複雑度をより簡単に判定できるように、コンテスト用の配布ファイルにgetComplexity.m関数を含めました。

ノード数

これは、コードの長さの大まかな尺度ですが、コメントや変数名の長さではペナルティーは課されません。 

t = mtree('your code');
length(t.nodesize)

実行時間とサイズの上限

実行に180秒(3分)以上かかるエントリーはタイムアウトし、失格となります。

コードのサイズは、データベースの構造により制限されます。Mコードを格納するコンテスト用MySQLデータベースのコラムはText型で、最長65,535バイトに制限されています。この上限を超過するエントリーはエラーとなります。

エントリーの作成

コンテストにエントリーするのに必要なファイルは、MATLAB Central File ExchangeにあるZIPファイルに含まれています。このZIPファイルをダウンロードして解凍すると、以下に解説するファイルを入手できます。

構文

メインのルーチンはsolver.mです。その構文は上出の通りです。変数名は重要ではありません。この関数をZIPファイルに含まれるテスト環境でテストするには、runcontest.mを実行します。 

 >> runcontest

コンテストについて

コンテストは、三つの期間に分割されています。一週間の期間のほどんどは、コードを自由に交換できる通常モードとなりますが、最初の二日間は、個々のエントリーについての情報の一部が隠蔽されます。

  • Darkness (水曜日12 PM～木曜日12 PM) コンテスト一日日は、どのエントリーもコードや得点が見られません。
  • Twilight (木曜日12 PM～金曜日12 PM) コンテスト二日目は、得点は見られますが、コードは見られません。
  • Daylight (金曜日12 PM～水曜日12 PM) コンテスト残存期間は、 (Late-Stage Twilight期間を除き)、全てのエントリーの得点とコードが見られます。
全ての時間は米国東部夏時間です。日本時間では、Darknessは木曜日1 AM～金曜日1 AMとなります。

他者との協力やと既存エントリーの編集

一旦エントリーが提出されると、変更できません。しかし、どのエントリーも閲覧、編集、新規エントリーとしての再提出が可能です。提出されたエントリーはどれでも閲覧やコピーが自由です。既存のエントリーへの改変が得点を改善できれば、このコンテストの優勝者を決定する上では、改変者がそのコードの「著者」になります。既存のエントリーを研究して最適化することは奨励しています。

また、解決策や戦略などを他者と話し合うことも奨励しています。このために用意したスレッドへMATLAB CentralのNewsreaderから投稿してください。

細則

利用が許可されている関数は、$MATLAB/toolbox/matlabにある基本MATLABパッケージ内で提供されているものとし、$MATLABはMATLABルートディレクトリを指すものとします。他のツールボックスの関数は利用できません。エントリーは、最新版のMATLAB上でテストされます。

以下の利用は禁止されています:
  • MEXファイル
  • Javaコマンドやオブジェクトの作成
  • eval, feval, inline, function handlesなど
  • !, dos, unixなどのシェル エスケープ
  • Handle Graphicsコマンド
  • ActiveXコマンド
  • File I/Oコマンド
  • Debuggingコマンド
  • Printingコマンド
  • Simulinkコマンド
  • tic, toc, flops, clock, pauseなどのベンチマーク用コマンド
  • error, clear, persistent

ハッキング

コンテストのシステムを侵害するエントリーは許されていません。コンテストの参加者全員に対する配慮として、システムの不正利用をしないようにお願いします。

採点、実行、あるいはエラー条件を操作してテスト環境内のパズルを抽出することも禁じます。限定的な範囲で、これは過去のコンテストの要素の一つでしたが、Blockbuster Contestでは、Alan Chalker氏が科学の領域まで高めてしまいました。Tweak bombingその他の手法によりコンテストのテスト環境にエントリーをチューニングすることは許可されていますが、システムの処理能力を圧倒しないようお願いします。

FAQ

コンテストについてよくある質問への回答は、FAQで確認してください。

About named visibility periods

Contests are divided into segments where some or all of the scores and code may be hidden for some users. Here are the segments for this contest:

  • Daylight - You can see scores and code for all entries.
  • Twilight - You can see scores but no code.
  • Darkness - You can't see the code or scores for any of the entries.