JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 2
Problem: CraterDetection

Problem Statement

    The goal of this challenge is to detect craters in a given set of orbital images taken under various illumination conditions and camera poses.



Training data



You will be provided with a set of images that you can use to develop your algorithm. Directory "A15" contains TIFF images of size 1432x1432 pixels. Directory "LRO" contains JPEG images of size 600x400 pixels. The ground truth consists of a text file (GTF.lms), one per image directory, that contains the crater positions in each image. The position of each crater is denoted by the top left and bottom right corners of the smallest rectangle around the crater. Each line of the ground truth file consists of the following structure:

filename : N : xl1 : yt1 : xr1 : yb1 : ... : xlN : ytN : xrN : ybN : 
where filename is a string containing the image filename to be analyzed, N is an integer containing the total number of craters labeled in the image and xli, yti, xri, ybi are integer values denoting the column position of the top left corner, row position of the top left corner, column position of the bottom right corner, row position of the bottom right corner of the i-th crater in the image stored in file filename. All row and column positions are 0-based.



Note that images in LRO directory are labeled for craters such that:
  • max{width, height} > 25;
  • min{width, height} <= 200.
Here width is the width of the crater's bounding rectangle (i.e., xr - xl + 1) and height is its height (yb - yt + 1). Craters that do not satisfy to these conditions are not included into the ground truth file for LRO directory. However, these restrictions are not in place for images in A15 directory.



Implementation details



You will need to implement 3 methods: init, processImage and getCraters. Each test case in this problem consists of a set of images including 1 A15 image and 15-16 LRO images. Here "A15 image" means a 1432x1432 image similar to training images in A15 directory and "LRO image" is a 600x400 image similar to training images in LRO directory. The grader program will perform the following steps for each test case:
  1. Create an instance of your solution class file.
  2. Call init on this instance.
  3. For each image, call processImage on this instance.
  4. Finally, call getCraters on this instance.
The method init is introduced so that you can perform arbitrary initialization steps required for your solution. The time limit for this method is 30 seconds.



The method processImage is used in order to pass an image where it is necessary to find craters. name contains the name of the image. You can use this parameter to determine whether it's an A15 or an LRO image: name will end with ".tif" for A15 images and with ".jpg" for LRO images. W and H are image width and height in pixels, correspondingly. data contains exactly W*H elements and describes the contents of the image. data[H * x + y] is the value of each of red, green and blue components of the pixel of the image in column x, row y (0-based). Note that all images used are monochrome, so each pixel has the same red, green and blue components. The time limit for this method is 30 seconds per an LRO image and 3 minutes per an A15 image.



You can return arbitrary values from methods init and processImage.



Return value and scoring



The method getCraters is used so that your solution can report all craters that it has found on all processed images. Each element of the returned String[] must describe one crater and be formatted "name xl yt xr yb" (quotes for clarity), where name is the name of the image where this crater is located and xl, yt, xr and yr are the column position of the top left corner, row position of the top left corner, column position of the bottom right corner and row position of the bottom right corner of the crater (all positions are 0-based). The time limit for this method is 30 seconds.



If your solution exceeds time or memory limit, crashes, returns more than 100,000 elements or returns at least one element with invalid data, your score for this test cases is 0. An element is considered to contain invalid data if it's improperly formatted, name doesn't correspond to an image from this test case or xl, yt, xr, yb don't describe a valid rectangle within the image named name.



Otherwise, your score will be calculated using Average Precision metric. The detailed description of this metric can be found below.



Suppose that ground truth for the given test case consists of A craters C0, C1, ..., CA-1 and your solution returned B craters D0, D1, ..., DB-1, in this exact order. Let's say that two rectangles overlap significantly if the ratio between their intersection and their union is strictly larger than 0.3. A crater detection will be considered correct if the reported rectangle overlaps significantly with at least one of the rectangles in the ground truth data for the same image.



The following pseudocode will be used to calculate your score:



matched := array[0..A-1] of booleans, initialized with False values
score := 0.0
detected := 0
For i := 0, 1, ..., B-1:
	For j := 0, 1, ..., A-1:
		If (matched[j] == False) and (Cj.name == Di.name) and
		   (rectangles corresponding to Cj and Di overlap significantly):
			matched[j] := True
			detected := detected + 1
			score := score + (1000000.0 / A) * (detected / (i + 1))
			Break


Note that score depends on the order in which you report the found craters. Generally, the used metric emphasizes returning the correctly detected craters earlier.



Your overall score is the sum of scores on individual test cases.



Additional notes



There will be 1 example test case, 2 submission test cases and 18 system test cases. The example test case will reuse some images from the training set. The submission and system test cases will contain only images not included into the training set.



The restrictions on craters included into the ground truth data are the same for LRO images in submission and system test cases as for LRO images in the training set (you can find them in the end of "Training data" section).



An offline tester is available. You can check its source code for the precise implementation of the scoring method.



Prizes and conditions



In order to receive the prize money, you will need to fully document the derivation of all parameters internal to your algorithm. If these parameters were obtained from the training data set, you will also need to provide the program used to generate these training parameters. There is no restriction on the programming language used to generate these training parameters. Note that all this data 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.
 

Definition

    
Class:CraterDetection
Method:processImage
Parameters:String, int, int, int[]
Returns:int
Method signature:int processImage(String name, int W, int H, int[] data)
 
Method:getCraters
Parameters:
Returns:String[]
Method signature:String[] getCraters()
 
Method:init
Parameters:
Returns:int
Method signature:int init()
(be sure your methods are public)
    
 

Notes

-The memory limit is 1024 MB.
-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). Once your code is compiled, the binary size should not exceed 1 MB.
-The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here.
-The processing server specifications can be found here.
 

Examples

0)
    
This test case contains the following images from the training test set: AS15-M-0103.lev1_sub4.tif, M21859.jpg, M21862.jpg, M21867.jpg, M21869.jpg, M21870.jpg, M21873.jpg, M21875.jpg, M21876.jpg, M21878.jpg, M21880.jpg, M21881.jpg, M21882.jpg, M21884.jpg, M21889.jpg and M21890.jpg.

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.