JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: OmegaDetector
Problem: OmegaDetector

Problem Statement

    

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 image-based 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:
  1. place: $6000
  2. place: $4000
  3. place: $2750
  4. place: $1500
  5. 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 Region-Of-Interest (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:

  1. The left most column of the region. ( minimum x value )
  2. The top most row of the region. ( minimum y value )
  3. The right most column of the region. ( maximum x value )
  4. The bottom most row of the region. ( maximum y value )
  5. The type of barcode identified. 1 for a 1D barcode and 2 for a 2D barcode.
  6. 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..A-1] of booleans, initialized with False values					
score := 0.0
numberMatched := 0
For i := 0, 1, ..., R-1:
{
       true_match := False;
       For j := 0, 1, ..., A-1:
       {
           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 -Wno-sign-compare -O3 -s -pipe
  • Your solution will be compiled for ARM after the match with the following flags: -O3 -mcpu=cortex-a9 -mfpu=neon -ftree-vectorize -mfloat-abi=(softfp | hard) -ffast-math -fsingle-precision-constant
  • 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.
 

Definition

    
Class:OmegaDetector
Method:ROI_Finder
Parameters:int[], int, int
Returns:int[]
Method signature:int[] ROI_Finder(int[] imageData, int numOfRows, int numOfCols)
(be sure your method is public)
    
 

Notes

-Time limit is 5 seconds which include only time spend within your code and the memory limit is 2MB. Although there might be slightly more memory available, we are looking for solutions that do not use more than 2MB of memory.
-There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger).
-The compilation time limit is 60 seconds. You can find information about compilers that we use, compilation options and processing server specifications here. Note that this problem uses different compilation options than the default ones specified at this page.
 

Examples

0)
    
SEED=1
1)
    
SEED=2
2)
    
SEED=3
3)
    
SEED=4
4)
    
SEED=5
5)
    
SEED=6
6)
    
SEED=7
7)
    
SEED=8
8)
    
SEED=9
9)
    
SEED=10

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.