Heuristics development

From MASH Wiki

Here you will find information about the installation of the SDK, compilation of the heuristics and interaction with the MASH platform. Check the heuristic implementation page for detailed explanation about the heuristics themselves, their structure, the meaning of the methods they have to implement, and their life-cycle.

1 Requirements
2 Download
3 Compilation
4 Implementation of a new heuristic
5 Simple example: The Identity heuristic
6 Interpretation of the features computed by your heuristic
7 Another example: The MeanThreshold heuristic
8 Upload of your heuristic
- 8.1 Your private space
- 8.2 The public space
9 Implementation guidelines

Requirements

The MASH SDK uses CMake to allows the compilation of the heuristics on any platform. You'll need to install at least the version 2.6.

You'll also need a C++ compiler. The following are supported:

On Linux: gcc 4
On MacOS X: XCode 3.1 and gcc 4 (install the Developer tools from the Apple developers site, free registration required)
On Windows: Visual Studio 2005, Visual Studio 2008 and Visual C++ 2008 Express (which is free)

Others might also work, but are up to you (patch welcome!).

Download

Download the MASH SDK from the downloads page and decompress it.

Using a shell/terminal

~$ tar -xvzf mash_sdk_0.5.0.tar.gz
~$ ln -s mash_sdk_0.5.0 mash_sdk
~$ cd mash_sdk

Compilation

The first step is to generate the files needed to compile the SDK on your platform/compiler (Makefiles, XCode project or Visual Studio solution) using CMake. Then use them as usual to compile the SDK. On each platform, CMake comes as both a command-line tool and a GUI-based one. The usage of the command-line tool is shown below. See the CMake: Quick Start Guide or the CMake: Getting Started pages for more details.

It is recommended to generate the makefiles/IDE projects in a separate directory. In the description below that directory is ~/mash_sdk/build/. The compiled executables and libraries will be located in a bin subfolder of this directory.

Using a shell/terminal

~/mash_sdk$ mkdir build
~/mash_sdk$ cd build
~/mash_sdk/build$ cmake ..
...
~/mash_sdk/build$ make

Test of your compilation

~/mash_sdk/build$ cd bin
~/mash_sdk/build/bin$ ./testheuristic examples/identity car.ppm results.txt

You should obtain:

Image:
  File:          car.ppm
  Size:          128x128
  Format:        'RGB' 
Parameters:
  Coordinates:   (63, 63)
  ROI extent:    63
Heuristic:
  Name:          examples/identity
  Dimension:     16129


Test terminated correctly.

The mash_sdk/data folder contains some test images. When looking for an image (in the above example: car.ppm), the testheuristic program will first look in that folder to find it. That's why you don't have to provide the full path to the images in that folder. You can still test your heuristic on any image found on your computer by providing its full path to the testheuristic program.

Implementation of a new heuristic

In the following sections, and when implementing a new heuristic, you will follow these steps:

Copy the file heuristics/template.cpp into heuristics/your_user_name/your_heuristic_name.cpp. It is recommended to keep all your heuristics into a subfolder of heuristics with your username (in lower-case).
OR use the provided Python script do to most of the job for you (recommended)
Re-generate the makefiles for your platform (this must be done only once, after the creation of the source file that will contain your heuristic).
Edit the file to implement your heuristic (we'll see an example below).
Compile, test and debug it.

Once the heuristic behaves correctly on your machine, you are ready to upload it!

Using a shell/terminal

~/mash_sdk$ mkdir heuristics/your_user_name
~/mash_sdk$ cp heuristics/template.cpp heuristics/your_user_name/your_heuristic_name.cpp
~/mash_sdk$ cd build
~/mash_sdk/build$ cmake ..
...
-- Found heuristic: your_user_name/your_heuristic_name
...

(implement your heuristic)

...
~/mash_sdk/build$ make
...
~/mash_sdk/build$ cd bin
~/mash_sdk/build/bin$ ./testheuristic your_user_name/your_heuristic_name car.ppm results.txt

Using a script to create your heuristic

Instead of copying manually the template file, you can use the create_heuristic.py Python script. It will also customize the file for you. This let you go quicker to the fun part: implementing your idea.

~/mash_sdk$ ./create_heuristic.py your_user_name your_heuristic_name

How to debug your heuristic

By default, when using gcc, everything is compiled with the debug symbols, so you can use gdb as usual. Note that each heuristic is located into its own dynamic library, which is loaded at runtime. So the symbols defined by your implementation aren't known by gdb at launch time.

Users of XCode of Visual Studio can use their debugger as usual.

Simple example: The `Identity` heuristic

Let's look at a simple heuristic example! (Note that you can find a more detailed explanation on the Heuristic implementation page)

The job of a heuristic is to compute some features, given an image, the coordinates of a point in this image and the extent of a region of interest around that point:

You can see from that diagram that a heuristic has a dimension: the number of features computed (this dimension can be dependent of the size of the region of interest). But what exactly is a feature? A floating-point number. The meaning of each feature is up to the heuristic.

A region of interest is a square area, centered on a point. It is defined by its extent and the coordinates of the point. Its dimensions (width and height) are given by: $e x t e n t * 2 + 1$ (in pixels).

All the heuristic are implemented as a class, inheriting from Heuristic. Heuristic defines some methods that must be implemented by each heuristic, and others that are optional. Heuristic also has the following attributes (or class variables), which contains the informations at your disposable to compute the features:

class Heuristic
{
    ....
 
    unsigned int    roi_extent;     // Extent of the region of interest currently processed
    coordinates_t   coordinates;    // Coordinates of the point currently processed
    Image*          image;          // The image currently processed
};

With coordinates_t defined as follows:

struct coordinates_t
{
    unsigned int x; // X position in pixels
    unsigned int y; // Y position in pixels
};

We will now implement an Identity heuristic: the features are a direct copy of the pixels contained in the region of interest. The complete source code is in heuristics/examples/identity.cpp. Note that this heuristic is the one implemented by default when you create a new heuristic. When using the create_heuristic.py Python script, you can ask for an empty heuristic.

First we declare our heuristic class, by inheriting from Heuristic:

class IdentityHeuristic: public Heuristic
{
    //_____ Construction / Destruction __________
public:
    IdentityHeuristic();
    virtual ~IdentityHeuristic();
 
 
    //_____ Implementation of Heuristic __________
public:
    virtual unsigned int dim();
 
    virtual scalar_t computeFeature(unsigned int feature_index);
};

The methods declared here are the only ones that are required. In later examples, we'll implement some of the optional methods.

Next come the construction function of the heuristic. This is a function that returns a new instance of our class:

extern "C" Heuristic* new_heuristic()
{
    return new IdentityHeuristic();
}

The first required method is dim(). It must return the size of the features vector (the number of features computed by the heuristic). In this example, we'll compute as many features as the number of pixels in the region of interest:

unsigned int IdentityHeuristic::dim()
{
    // We have has many features than pixels in the region of interest
    unsigned int roi_size = roi_extent * 2 + 1;
    return roi_size * roi_size;
}

Note: roi_extent is the only attribute initialized when dim() is called!

The second required method is the one that computes the features: computeFeature(). Given an image, a point, the extent of the region of interest and the index of the feature to compute, this method must return the value of that feature. In our case, it is simply the value of the corresponding pixel.

Before we jump into the implementation of the computeFeature() method, we need to know how to retrieve the value of a pixel of the image. The Image class is declared in mash/image.h. The following bits are relevant for our example, in which we will work on grayscale (8 bits) images:

typedef unsigned char byte_t;
 
class Image
{
    ...
 
public:
    //----------------------------------------------------------------------
    // Returns the width of the image, in pixels 
    //----------------------------------------------------------------------
    unsigned int width() const;
 
    //----------------------------------------------------------------------
    // Returns the height of the image, in pixels 
    //----------------------------------------------------------------------
    unsigned int height() const;
 
    //----------------------------------------------------------------------
    // Returns a pointer to the pixels in grayscale (8 bits) format
    //----------------------------------------------------------------------
    byte_t* grayBuffer() const;
 
    //----------------------------------------------------------------------
    // Returns an array of pointers to the lines of the grayscale pixel
    // buffer
    //----------------------------------------------------------------------
    byte_t** grayLines() const;
 
    ....
};

There's two ways to access the pixels:

Use a one-dimensional array of <image width>x<image height> pixels. This forces you to compute the offset of the desired pixel like that:

// Access the grayscale pixel at (x, y)
byte_t* pBuffer = image->grayBuffer();
byte_t mypixel = pBuffer[y * image->width() + x];

Use an array of pointers to the lines of the image. This allows you to write a shorter code like:

// Access the grayscale pixel at (x, y)
byte_t** pLines = image->grayLines();
byte_t mypixel = pLines[y][x];

See the Image manipulation page for examples about the colored (RGB) images.

Let's go back at our computeFeature() method. The trickiest part is to determine the pixel position from the feature index:

scalar_t IdentityHeuristic::computeFeature(unsigned int feature_index)
{
    // Compute the coordinates of the top-left pixel of the region of interest
    unsigned int x0 = coordinates.x - roi_extent;
    unsigned int y0 = coordinates.y - roi_extent;
 
    // Compute the coordinates of the pixel corresponding to the feature, in
    // the region of interest
    unsigned int roi_size = roi_extent * 2 + 1;
    unsigned int x = feature_index % roi_size;
    unsigned int y = (feature_index - x) / roi_size;
 
    // Return the pixel value corresponding to the desired feature
    byte_t** pLines = image->grayLines();
    return (scalar_t) pLines[y0 + y][x0 + x];
}

That's it! You can now compile and test your identity heuristic. See the next section to learn how to check that your heuristic produce the correct results.

Interpretation of the features computed by your heuristic

The default output of the testheuristic program only informs you that everything went OK (or that an error occurred). The features computed are written in the results file (in all the above example: results.txt).

To also display the features in your shell, use the -v option:

~/mash_sdk/build/bin$ ./testheuristic -v examples/identity car.ppm results.txt

Now imagine that (as in our Identity example) the features vector could be interpreted as a (grayscale) image. testheuristic can produces a PNG image file instead of a text one. The syntax is the following:

./testheuristic --outformat=image --outsize=<width>x<height> --outrange=<min>..<max> <heuristic name> <image name> <results file>
 
With:
    --outsize=<width>x<height>: Dimensions of the image. <width> * <height> must
                                be equal to the dimension of the features vector
                                returned by the heuristic
    --outrange=<min>..<max>:    Minimum and maximum value of the features. Used
                                to map the range of the features into the one of
                                the pixels of the image. The features outside
                                this range are clamped.

Using a shell/terminal

To create an image containing the features computed by the Identity heuristic (which are the grayscale pixels in the region of interest), do:

~/mash_sdk/build/bin$ ./testheuristic \
    --outformat=image \
    --outsize=127x127 \
    --outrange=0..255 \
    examples/identity car.ppm result.png

Note the value of the --outsize parameter: since the extent of the region of interest is 63 pixels (as reported by testheuristic), its width and height are equal to

e x t e n t * 2 + 1 = 127

pixels.

Source image	Result image

The features can also be exported in CSV (comma-separated values) format, by doing:

~/mash_sdk/build/bin$ ./testheuristic --outformat=csv --outsize=<nbcolumns> <heuristic name> <image name> <results file>
 
With:
    --outsize=<nbcolumns>: Number of columns (default: 1)

Another example: The `MeanThreshold` heuristic

Sometimes, in order to compute one feature, you'll need to do some complex calculation over a group of pixels. If that calculation is the same for all the features, it will be a bad idea (performance-wise) to redo it at each call of the computeFeature() method. The purpose of the prepareForCoordinates() and finishForCoordinates() methods is to allow you to precompute anything you need for a specific point.

We will now implement a MeanThreshold heuristic: the features indicates if the corresponding (grayscale) pixels are above or below the mean value of the region of interest. The complete source code is in heuristics/examples/meanThreshold.cpp.

As always, we declare our heuristic class, by inheriting from Heuristic:

class MeanThresholdHeuristic: public Heuristic
{
    //_____ Construction / Destruction __________
public:
    MeanThresholdHeuristic();
    virtual ~MeanThresholdHeuristic();
 
 
    //_____ Implementation of Heuristic __________
public:
    virtual unsigned int dim();
 
    virtual void prepareForCoordinates();
 
    virtual scalar_t computeFeature(unsigned int feature_index);
 
 
    //_____ Attributes __________
protected:
    float _mean;
};

Notice the prepareForCoordinates() method. This one is optional, and is called exactly once for each processed point, before any computeFeature() call. A corresponding finishForCoordinates() method exists, called exactly once after all the needed features were computed for a given point. If your prepareForCoordinates() method allocates some memory, you must release it in finishForCoordinates().

Also note the new Attributes section, which declares the attribute _mean that will contain the precomputed mean value of the region of interest.

The next parts are the same than for the Identity heuristic: a construction function and a dim() method indicating that we'll compute as many features as the number of pixels in the region of interest:

extern "C" Heuristic* new_heuristic()
{
    return new MeanThresholdHeuristic();
}
 
unsigned int MeanThresholdHeuristic::dim()
{
    // We have has many features than pixels in the region of interest
    unsigned int roi_size = roi_extent * 2 + 1;
    return roi_size * roi_size;
}

Next comes the implementation of prepareForCoordinates(), in which we compute the mean value of the pixels of the region of interest, and store it in the _mean attribute:

void MeanThresholdHeuristic::prepareForCoordinates()
{
    // Compute the coordinates of the top-left pixel of the region of interest
    unsigned int x0 = coordinates.x - roi_extent;
    unsigned int y0 = coordinates.y - roi_extent;
 
    // Compute the mean value of the region of interest
    byte_t** pLines = image->grayLines();
 
    _mean = 0.0f;
    for (unsigned int y = 0; y < roi_extent * 2 + 1; ++y)
    {
        for (unsigned int x = 0; x < roi_extent * 2 + 1; ++x)
            _mean += pLines[y0 + y][x0 + x];
    }
 
    _mean /= dim();
}

Since we aren't allocating any memory here, we don't need to implement 'finishForCoordinates().

And now we can compute our features, by comparing each pixel value with the mean one. We return 1.0 when the pixel value is above (or equal) to the mean one, 0.0 otherwise. Note that those values are arbitrary. The meaning of the features is heuristic-dependent. No assumption about this is made by the MASH system.

scalar_t MeanThresholdHeuristic::computeFeature(unsigned int feature_index)
{
    // Compute the coordinates of the top-left pixel of the region of interest
    unsigned int x0 = coordinates.x - roi_extent;
    unsigned int y0 = coordinates.y - roi_extent;
 
    // Compute the coordinates of the pixel corresponding to the feature, in
    // the region of interest
    unsigned int roi_size = roi_extent * 2 + 1;
    unsigned int x = feature_index % roi_size;
    unsigned int y = (feature_index - x) / roi_size;
 
    // Compute the feature value
    byte_t** pLines = image->grayLines();
    if (pLines[y0 + y][x0 + x] >= _mean)
        return 1.0f;
 
    return 0.0f;
}

As with the Identity heuristic, the features vector of this one can be interpreted as an image, so lets look at it:

Using a shell/terminal

~/mash_sdk/build/bin$ ./testheuristic \
    --outformat=image --outsize=127x127 \
    --outrange=0.0..1.0 \
    examples/MeanThreshold car.ppm car_result.png

~/mash_sdk/build/bin$ ./testheuristic \
    --outformat=image \
    --outsize=127x127 \
    --outrange=0.0..1.0 \
    examples/MeanThreshold cup.ppm cup_result.png

~/mash_sdk/build/bin$ ./testheuristic \
    --outformat=image \
    --outsize=127x127 \
    --outrange=0.0..1.0 \
    examples/MeanThreshold duck.ppm duck_result.png

Source image	Result image

Note: There is also a prepareForImage() method, called only once before the processing of an image, and a corresponding finishForImage() method, that must deallocate any memory allocated by prepareForImage().

Upload of your heuristic

Your private space

Go to the heuristics page. At the top, in the Upload a new heuristic file box, select your source file and click on Upload. You will be asked to give us the right to compile it. Your heuristic will be uploaded, compiled and tested.

If one step of the testing of your heuristic fail, the details of the failure are shown (like the compilation errors for instance). You can then upload another file that fix the problem.

At this point, your heuristic is in your private space. You are the only one who can see it. The heuristics in your private space are not used in the public experiments. You can use them in your own private experiments.

The public space

Once you are happy with your heuristic, you can publish it (put it in the public space, where everyone can see it). Before doing so, you are encouraged to enter some informations about it, in order to help other users to find your heuristic, and understand it.

To publish your heuristic, go on its page and click on the icon. You will need to confirm that you really want to publish it, under the GPLv2 license.

At this point, everybody can see your heuristic, and it will be used in the public experiments. You can still use it in your own private experiments.

You can also upload a new version of one of your heuristics. Only the latest public version of an heuristic is used in the public experiments.

Implementation guidelines

Dont' allocate any memory in dim(). This method can be called multiple times, leading to memory leaks. Allocate your memory in the constructor of the class, prepareForImage() or prepareForCoordinates() (and do not forget to release it!)
Always clean up the memory in finishForImage() if prepareForImage() allocates something
Always clean up the memory in finishForCoordinates()' if prepareForCoordinates() allocates something
Precomputes as much as possible: your heuristic isn't allowed to takes its time. It must respond quickly, otherwise it might not be used in the experiments.

Heuristics development

From MASH Wiki

Contents

Requirements

Download

Compilation

Implementation of a new heuristic

Simple example: The `Identity` heuristic

Interpretation of the features computed by your heuristic

Another example: The `MeanThreshold` heuristic

Upload of your heuristic

Your private space

The public space

Implementation guidelines

Views

Navigation

Search

Personal

Toolbox

Heuristics development

From MASH Wiki

Contents

Requirements

Download

Compilation

Implementation of a new heuristic

Simple example: The Identity heuristic

Interpretation of the features computed by your heuristic

Another example: The MeanThreshold heuristic

Upload of your heuristic

Your private space

The public space

Implementation guidelines

Views

Navigation

Search

Personal

Toolbox

Simple example: The `Identity` heuristic

Another example: The `MeanThreshold` heuristic