Darkness 2010-04-28 12:00:00 UTC
 
Twilight 2010-04-29 12:00:00 UTC
 
Daylight 2010-04-30 12:00:00 UTC
 
Finish 2010-05-05 12:00:00 UTC

Sensor - Rules

Arrow_down  Download Sample Code

Compressive Sensing is the 21st MATLAB Online Programming Contest.

The Problem

A typical digital camera contains a sensor with many millions of individual pixels. After the picture is taken, pixel data is pulled off the chip and placed in memory. Once in memory, the image data is compressed using something like the JPEG algorithm, at which point the raw pixel data is thrown away. On reflection, this seems to be sub-optimal. We went to a lot of trouble (costing us valuable time, energy, and memory) to get all that data off the chip, only to immediately toss most of it in the trash. Why not just grab fewer pixels in the first place? That's the general idea behind compressive sensing, and it's the basis for this contest. [See reference here]

For this contest, you are to reconstruct the actual pixel values of an "uncompressed" sensor image. You will do this by requesting "compressed" sensor values, each of which is the sum of pixel values within the uncompressed image. To query the values, supply a mask for the region you're interested in, and in return you will receive the sum of the pixel data corresponding to that mask. There is a limit on how many compressed sensor values you can request in order to attempt to reconstruct the uncompressed pixel values. Here's what it looks like in practice. Imagine starting with the matrix A shown below. 
 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 ]
Now suppose you had a query mask that looks like this: 
 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 ]
Here is a picture of the matrix with a mask superimposed.

Note that the sum of the pixels in the masked region is 9.

Syntax

Your code will be called with two input arguments and one output argument like so: 
 Aest = solver(imageSize, queryLimit)
The image is always square, so imageSize refers to the edge length. The return argument Aest is your reconstructed estimate of the actual image. Inside your entry, you will be able to call the query function queryImage up to queryLimit times. The queryImage function has this syntax. 
 pixelSum = queryImage(mask)
The input mask must be of class logical. The output pixelSum will return the total sum of all the pixel values in the masked region of the image. It's a simple calculation that looks like this. 
 pixelSum = sum(A(mask))
The cost of the solution, which you want to minimize, is the sum of the absolute difference between the actual image and your reconstruction. In code, 
 imageDiff = abs(Aest - A)
 result = sum(imageDiff(:))
This result is the most important part of your score. For more information about how the overall score is calculated, see "Scoring" below.

Example

Let's suppose you're trying to reconstruct the same image matrix shown in the example above. Assume the following to true:
  • imageSize = 5
  • queryLimit = 2
Since you can't see the actual image, you want to get a sense of how big it is. Your first guess might be to query the entire shape. 
 mask = true(imageSize);
 pixelSum = queryImage(mask)

This would return a value of 24, since it's the sum of all the elements in the matrix. Your next guess might be to query some subregion. 

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

Aha! The answer is still 24. That means we know that all of the excluded region is zero. Since we're out of guesses, our best estimate is to spread the pixel sum of 24 across the selected region like so.

This generates a total error of 24.

Other Notes

  • Pixel values are always integers between 0 and 255.
  • Images are always square.
  • Calls to queryImage in excess of queryLimit do not error out, but return the value zero.

Scoring

The overall score for your entry is a combination of several factors. The first two in this list are the most important. The other two have a milder effect.
  1. Your average result across all the problems
  2. How fast your code runs
  3. The cyclomatic complexity of your code (more information below)
  4. The node count of your code (more information below)
Since each of these is to be minimized, the lowest overall score at the end of the contest wins.

Cyclomatic Complexity

Cyclomatic complexity, also known as McCabe complexity, is a measure of the number of independent paths through a program's source code. Typically, as this number gets higher, it becomes more difficult to understand what's happening in a program. This makes it harder to test, modify, and refactor.

Since a file can contain multiple functions, the complexity for any given file is defined as the MAXIMUM complexity of any functions contained in it. A good practice is to keep the complexity for each function below 10, so for this contest your overall score will increase according to the complexity in excess of 10. So there is no complexity penalty for submissions in which all functions have a complexity of 10 or less.

You can measure the cyclomatic (or McCabe) complexity of any function in MATLAB using the "cyc" switch for mlint. Try this, for example: 

 
>> mlint -cyc magic.m

We have also included a getComplexity.m function with the contest distribution to make it easier to find the complexity for your entry.

Node Count

This is a rough measure of how long your code is, but it will not penalize you for comments and variable name length. 

t = mtree(filename,'-file');
length(t.nodesize)

Time and Size Limits

Your entry will time out and be disqualified if it takes more than 180 seconds (three minutes).

The code is limited in size by the database architecture. The column in our MySQL database that stores the M-code is of type text, which is limited of 65535 characters. Submissions longer than this limit will fail.

Developing Your Entry

The files you need to get started on the contest are included in a ZIP-file available on the MATLAB Central File Exchange. If you download and uncompress this ZIP-file, you will have the files described below.

Syntax

The main routine is solver.m. The syntax is described above. Variable names are unimportant. To test this function with the test suite in the ZIP-file, run runcontest.m. 

 
 >> runcontest

About the Contest

The contest is divided into three segments. Most of the week will run as usual, with free sharing of code, but the first two days of the contest will hide some of the information about each entry.

  • Darkness (Wed. 16:00 UTC to Thurs. 16:00 UTC). During the first day of the contest, you can't see the code or scores for any of the entries.
  • Twilight (Thurs. 16:00 UTC to Fri. 16:00 UTC). During the second day of the contest, you can see scores but no code.
  • Daylight (Fri. 16:00 UTC to Wed. 16:00 UTC). For the remainder of the contest (with the exception of Late-Stage Twilight) you can see scores and code for all entries.
All times are Coordinated Universal Time (UTC).

Collaboration and Editing Existing Entries

Once an entry has been submitted, it cannot be changed. However, any entry can be viewed, edited, and resubmitted as a new entry. You are free to view and copy any entry in the queue. If your modification of an existing entry improves its score, then you are the "author" for the purpose of determining the winners of this contest. We encourage you to examine and optimize existing entries.

We also encourage you to discuss your solutions and strategies with others. You can do this by posting to the thread that we've started from our newsreader.

Fine Print

The allowable functions are those contained in the basic MATLAB package available in $MATLAB/toolbox/matlab, where $MATLAB is the root MATLAB directory. Functions from other toolboxes will not be available. Entries will be tested against the latest version of MATLAB.

The following are prohibited:
  • MEX-files
  • Java commands or object creation
  • eval, feval, inline, function handles, etc.
  • Shell escape such as !, dos, unix
  • Handle Graphics commands
  • ActiveX commands
  • File I/O commands
  • Debugging commands
  • Printing commands
  • Simulink commands
  • Benchmark commands such as tic, toc, flops, clock, pause
  • error, clear, persistent

Hacking

Entries that compromise the contest machinery are not allowed. Out of consideration for everyone participating in the contest, we ask that you not abuse the system.

Extraction of puzzles in the test suite by manipulating the score, runtime, or error conditions is also forbidden. Tuning the entry to the contest test suite via multiple entries is permitted, but we ask that you not overwhelm the queue.

FAQ

Check our FAQ for answers to frequently asked questions about the contest.

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:

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