 Background
Omega is looking for you to help them on implementing 2D barcode reading algorithms on their decoders. The decoders use an embedded ARM core platform. You will be writing algorithms and code to enable the imagebased decoder to recognize several formats of 2D barcodes.
Prizes
The best 5 performers of this contest (according to system test results) will receive the following prizes:
 place: $6000
 place: $4000
 place: $2750
 place: $1500
 place: $750
Additional rewards:
 The solution that scores in the top 5 that uses the least amount of heap and stack memory will be awarded a bonus prize of $500. The exact usage amount for each of the top 5 submissions will be verified after the match.
 The best solution in the top 5 that compiles on ARM will be rewarded a bonus prize of $500.
 The most accurate solution will be rewarded a bonus prize of $750. The performance penalty will not be applied in order to determine the winner of this bonus.
Overview
In this first contest you will need to write an algorithm that detect barcodes in an image and identify their bounding regions. The images that will be given to your algorithm may contain 1D and/or 2D barcodes. An example list of the type of barcodes that you can expect in this match are:
The image may contain several of these barcodes or none at all. Your algorithm should return the RegionOfInterest (ROI) of each barcode in the image. The image resolution can be 1280x960, 640x480 or 320x240 pixels. The size of a barcode can be anything in the range of 13x13 to 800x800. Each region that your algorithm returns should:
 Completely contain the candidate barcode. The ROI should completely enclose and fit the barcode as closely as possible without having the edge(s) of the ROI cutting into the barcode. Your algorithm will be severely penalized if the edge(s) of the ROI cuts into the barcode.
 Describe a rectangular region that has sides that are parallel to both X and Y axis.
 Identify the type of the barcode. (1D or 2D).
 Have a confidence that the ROI contains a barcode.
An example image containing a DataMatrix and UPCA barcode can be seen below:
Implementation
Your task is to implement a ROI_Finder method, whose signatures are detailed in the Definition section below.
int[] imageData contains the unsigned 8 bit image data. However, the pixel intensity values of four pixels are packed into one integer. The size of the image region is specified by numOfRows and numOfCols. Each row in the image will contain numOfCols pixels. Let x be the column and y be the row of a pixel, then the pixel value can be extracted at index [(x+y*numOfCols)/4] of the imageData array. A simple way to access each pixel value would be to cast the int[] imageData to an unsigned char* and read each pixel directly at index [x+y*numOfCols], see the sample submission for an example of how to do this.
You should return a int[] containing the detected barcodes. You may not return more than 6 detections. Each detection must contain 6 values in the following order:
 The left most column of the region. ( minimum x value )
 The top most row of the region. ( minimum y value )
 The right most column of the region. ( maximum x value )
 The bottom most row of the region. ( maximum y value )
 The type of barcode identified. 1 for a 1D barcode and 2 for a 2D barcode.
 Confidence value in the range of [0, 100]. If your algorithm is 100 confident this region contains a barcode, set this value to 100. This value will be used in the scoring formula.
Let R be your return vector and R[i] the element at index i. If your algorithm detected a 2D barcode with width and height 100, at position (10, 20), with 95 confidence, then your R would look something like: R[0] = 10, R[1] = 20, R[2] = 110, R[3] = 120, R[4] = 2, R[5] = 95. If your algorithm detected another barcode in the same image, then R[6] = 200, R[7] = 50, R[8] = 400, R[9] = 150, R[10] = 1, R[11] = 80 would describe a 1D detection at (200,50) with size (200, 100) and 80 confidence.
All regions in your return must be within the image boundaries.
Testing and scoring
There are 10 example tests, 100 provisional tests and 222 system tests.
First of all, let's introduce the concept of regions overlapping significantly. Let B1, B2 be two regions and B3 their intersection. The two boxes are matching if area(B3) >= threshold * max{area(B1), area(B2)}, where area(Bi) is the area of region Bi and threshold is set to 0.3.
The performance score is calculated as 0.75 / (1.0 + ((sqrt(2.0) * T)/0.05)^2 ) + 0.25 (^ denotes power operator), where T is the runtime of your solution in seconds. So for example, the runtime of 0.005 seconds results in ~0.9852 for performance score.
This pseudo code will be used to calculate your score (assuming array R describes your returned detections and array A the true barcodes):
matched := array[0..A1] of booleans, initialized with False values
score := 0.0
numberMatched := 0
For i := 0, 1, ..., R1:
{
true_match := False;
For j := 0, 1, ..., A1:
{
If (matched[j] == False) and
(regions corresponding to Aj and Ri overlap significantly)
{
matched[j] := True
numberMatched := numberMatched + 1
Overlap := Intersection of Aj and Ri
single_score := 10*(AreaOf(Aj) / AreaOf(Ri))^1.29
If (barcodeType(Ri) == barcodeType(Aj)) single_score := single_score + 5
If (AreaOf(Overlap) < AreaOf(Aj)) single_score := 0
score := score + single_score * Confidence(Ri)
true_match := True;
Break out of (For j) loop
}
}
if (true_match == False)
score := score – 15 * Confidence(Ri)
}
if (A.size() == numberMatched)
score := score + 1500
if (score < 0) score := 0
score := score * performance_score;
If your solution exceeds time or memory limit, crashes or returns invalid result, your score for this test case is 0.
The overall score on a set of test cases is the sum of scores on single test cases from the set. The match standings displays overall scores on provisional tests for all competitors who have made at least 1 full test submission. The winners are competitors with the highest overall scores on system tests.
An offline tester/visualizer tool is available. In order to help you get started, a sample solution is available, you are encouraged not to add any additional includes to the solution. The example data can be downloaded here
Special rules and conditions
 Your solution will be compiled with the following flags: std=c++98 W Wall Wnosigncompare O3 s pipe
 Your solution will be compiled for ARM after the match with the following flags: O3 mcpu=cortexa9 mfpu=neon ftreevectorize mfloatabi=(softfp  hard) ffastmath fsingleprecisionconstant
 The only allowed programming language is C++.
 You are not allowed to use SSE instructions. You are not allowed to use inline assembly instructions.
 The sample solution contains a specific API that Omega wants you to implement, you are encouraged to use the coding style and API provided in the sample solution.
 You can include open source code in your submission. Open Source libraries under the BSD, or GPL or GPL2 license will be accepted. Other open source licenses could be accepted too. Just be sure to ask us.
 You are restricted to only use library functions from the following libraries: string.h, ctype.h, math.h. Libraries such as vector may only be used in order for your method to receive input and return the output. Your submissions will be manually verified after the deadline.
 The ROI_Finder method must use each image independently to identify the barcode ROI(s) within that image. In other words, the ROI_Finder will only use the pixel information in that image to identify all the ROIs within that same given image.
 In order to receive the prize money, you will need to fully document your code and explain your algorithm. If any parameters were obtained from the training data set, you will also need to provide the program used to generate these parameters. There is no restriction on the programming language used to generate these training parameters. Note that all this documentation should not be submitted anywhere during the coding phase. Instead, if you win a prize, a TopCoder representative will contact you directly in order to collect this data.
 Match forum is located here. Please check it regularly as important clarifications and updates may be posted there. All clarifications, updates, restrictions and any other information posted at the forum by [topcoder] admins (orange handles) or copilot of this match (handle JacoCronje) should be treated as part of the problem statement. You can click “Watch Forum” if you would like to receive automatic notifications about all posted messages to your email.
 If your solution fails to comply with any restriction contained in the problem statement or posted at match forum within duration of the match, it can be a reason for its disqualification from the competition.
