Compressive Sensing is the 21st MATLAB Online Programming Contest.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.
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.
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.
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.
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)
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.
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.
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.
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.
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.
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:
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 for answers to frequently asked questions about the contest.
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: