Understanding the demo

Understanding the Demo

When building the demo (setting BUILD_DEMO in CMake to ON), a small dataset from our HPG 2016 paper -- a 320 x 256 px plane sweep with max. 96 labels per node -- is downloaded. The demo itself is a short program demonstrating how to use mapMAP as a library, importing the dataset, handing mapMAP the input data and starting the optimization.

On this introductory wiki page, we'll go step-by-step through the process. After reading this, you should be able to use mapMAP's basic functionality in your own project.

So... let's start!

The boilerplate part

First, we include all necessary header files for mapMAP at once:

#include "mapmap/full.h"

Second, for our convenience, let's use its namespace (mapMAP, but we recommend using the macro NS_MAPMAP) by default:

using namespace NS_MAPMAP;

For performance, MAPMAP relies heavily on vectorization and usually takes the data type (float/double for using SSE and successors) and SIMD vector width (1/4/8 for float and 1/2/4 for double, the latter ones only with AVX) as parameter. Note that by using our CMake file, only code supported by your computer is generated. Thus, you need to select one type and vector width that matches your architecture. For convenience, we define shortcuts:

using cost_t = float;
const uint_t simd_w = sys_max_simd_width<cost_t>();

If simd_w does not match your computer's architecture, compilation will fail. Therefore, we offer sys_max_simd_width<cost_t>() to automatically choose.

Creating the graph (topology)

Since pairwise MRFs are usually stored as an undirected graph, we now create ours. In the demo, the graph (as list of all edges) is read from the data file. In mapMAP, the user needs to specify the number of nodes initially, then can add edges:

std::unique_ptr<Graph<cost_t>> graph;
graph = std::unique_ptr<Graph<cost_t>>(new Graph<cost_t>);

uint32_t min_id, max_id;
float weight;
for(uint32_t e_id = 0; e_id < num_edges; ++e_id)
{
     /* just read the edge data from the file */
     io.read((char *) &min_id, sizeof(uint32_t));
     io.read((char *) &max_id, sizeof(uint32_t));
     io.read((char *) &weight, sizeof(float));

     /* this is important - the edge is created here */
     graph->add_edge(min_id, max_id, weight);
}

After adding all edges, we instruct the graph to run a BFS, discovering (dis)connected components. These will be exploited for additional parallelism:

/* finalize component lists for base graph */
graph->update_components();

Creating the label set

After successfully creating the graph, we now specify the set of feasible labels per node. To create storage, do

std::unique_ptr<LabelSet<cost_t, simd_w>> label_set;
label_set = std::unique_ptr<LabelSet<cost_t, simd_w>>(new LabelSet<cost_t, simd_w>(num_nodes, COMPRESS));

where COMPRESS determines if the label sets should be compressed. While that saves memory, it also increases your time for constructing the problem - the employed hash matching as a O(N^2) runtime. Independent of your choice, create a vector with the feasible labels for each node and set it:

std::vector<_iv_st<cost_t, simd_w>> lset(n_labels);
/** fill vector here... */
label_set->set_label_set_for_node(n, lset);

This allows efficient modelling of the sparse case.

Setting the unary costs

Unary costs are functions that consume a node ID and a label (or the label's ID in the sparse case) and returns a cost value. While you are free to implement a cost function of your own, in this example we use a simple look-up table. For each node, a cost vector is created that contains the costs in the same order as the labels in the vector set above:

using unary_t = UnaryTable<cost_t, simd_w>;

std::unique_ptr<unary_t> unaries;
unaries = std::unique_ptr<unary_t>(new unary_t(graph.get(), label_set.get()));
std::vector<_s_t<cost_t, simd_w>> costs(n_labels);
/* fill cost table here ... */
unaries->set_costs_for_node(n, costs);

Setting the pairwise costs

Pairwise costs represent the costs on the edges of the graph - consuming labels (and possibly IDs) of the incident nodes and returning a cost value. In this example, we use truncated linear costs: c(l_1, l_2) = min(2, abs(l_1 - l_2)):

using pairwise_t = PairwiseTruncatedLinear<cost_t, simd_w>;

std::unique_ptr<pairwise_t> pairwise;
pairwise = std::unique_ptr<pairwise_t>(new pairwise_t(2));

Configuring and starting the solver

With the data at hand, we can now create the templated solver itself:

mapMAP<cost_t, simd_w, unary_t, pairwise_t> mapmap;
mapmap.set_graph(graph.get());
mapmap.set_label_set(label_set.get());
mapmap.set_unaries(unaries.get());
mapmap.set_pairwise(pairwise.get());

and finally, we may start the optimization:

mapmap.optimize(solution);

The optimization's progress can be monitored via the console output. Please note that the termination criterion as well as the grouping algorithm for nodes in the multilevel heuristic can be customized. If none is specified, mapMAP groups node having the same label and stops after 5 iterations without a decrease in energy.

Important: The solution vector filled by mapMAP contains indices into the node's label set, not the labels itself! To retrieve the labeling , execute the following:

std::vector<_iv_st<cost_t, simd_w>> labeling(num_nodes);
for(uint32_t n = 0; n < num_nodes; ++n)
{
    labeling[n] = label_set->label_from_offset(n, solution[n]);
}

Optional: Changing the termination criteria

Instead of the mentioned default criterion, we might want the solver to stop if, after 5 iterations, less than an improvement of 0.01% in objective value has been made. Expressing that is possible through a specific termination criterion:

std::unique_ptr<TerminationCriterion<cost_t, simd_w>> terminate;
/* ... */
terminate = std::unique_ptr<TerminationCriterion<cost_t, simd_w>>(new StopWhenReturnsDiminish<cost_t, simd_w>(5,0.0001));
/* ... */
mapmap.set_termination_criterion(terminate.get());