Superpixel Graph Label Transfer (nnGraph) Project

This project provides a reference implementation for the "Superpixel Graph Label Transfer with Learned Distance Metric" work of Gould et al. (ECCV 2014). The project is part of the Darwin software package. Installation instructions and addtional documentation can be found at http://drwn.anu.edu.au.

The project comprises a number of C/C++ applications for building graphs over superpixels (or regions), learning distance metrics, and performing label transform. Below are step-by-step instructions for running the project pipeline and evaluating results. The Python script nnGraphPipeline.py in the projects/nnGraph/examples directory runs the entire pipeline.

See Also

drwnNNGraphNode, drwnNNGraphImageData, drwnNNGraphImage, drwnNNGraph, drwnNNGraphNodeAnnotation

Preparing the Data

This project requires training instance consisting of an image and corresponding pixel annotations (for label transfer). The pixel annotations can be in the form of an integer matrix (text file) the same size as the image or a colour-coded image. The application convertPixelLabels in the drwnProjMultiSeg project can be used to generate the text file format from colour-coded images.

Images and label files should have the same basename (e.g., img001.jpg and img001.txt) and may be stored in the same or different directories. By default the code assumes that images are stored in data/images and labels stored in data/labels with file extensions ".jpg" and ".txt", respectively.

Configuration

The following XML configuration can be used to change the behaviour of the move-making graph optimization algorithm. You can also change the default location of the images, labels, and regions as well as their extensions by modifying the appropriate option.

<drwn>
 <drwnNNGraph>
   <option name="K" value="5" />
   <option name="propagateMove" value="true" />
   <option name="searchMove" value="true" />
   <option name="localMove" value="true" />
   <option name="randProjMove" value="100" />
   <option name="enrichmentMove" value="true" />
   <option name="randExhaustive" value="1" />

   <option name="imgDir" value="data/images/" />
   <option name="lblDir" value="data/labels/" />
   <option name="segDir" value="data/regions/" />
   <option name="imgExt" value=".jpg" />
   <option name="lblExt" value=".txt" />
   <option name="segExt" value=".bin" />
 </drwnNNGraph>
</drwn>

The project uses colors to visualize semantic classes. These are defined in the multi-class segmentation configuration. An example for the 21-class MSRC dataset is shown below:

<drwn>
 <drwnMultiSegConfig>
   <!-- region definitions -->
   <regionDefinitions>
     <region id="-1" name="void" color="0 0 0"/>
     <region id="0" name="building" color="128 0 0"/>
     <region id="1" name="grass" color="0 128 0"/>
     <region id="2" name="tree" color="128 128 0"/>
     <region id="3" name="cow" color="0 0 128"/>
     <region id="4" name="sheep" color="0 128 128"/>
     <region id="5" name="sky" color="128 128 128"/>
     <region id="6" name="airplane" color="192 0 0"/>
     <region id="7" name="water" color="64 128 0"/>
     <region id="8" name="face" color="192 128 0"/>
     <region id="9" name="car" color="64 0 128"/>
     <region id="10" name="bicycle" color="192 0 128"/>
     <region id="11" name="flower" color="64 128 128"/>
     <region id="12" name="sign" color="192 128 128"/>
     <region id="13" name="bird" color="0 64 0"/>
     <region id="14" name="book" color="128 64 0"/>
     <region id="15" name="chair" color="0 192 0"/>
     <region id="16" name="road" color="128 64 128"/>
     <region id="17" name="cat" color="0 192 128"/>
     <region id="18" name="dog" color="128 192 128"/>
     <region id="19" name="body" color="64 64 0"/>
     <region id="20" name="boat" color="192 64 0"/>
   </regionDefinitions>
 </drwnMultiSegConfig>
</drwn>

Other standard Darwin configuration settings can also be controlled through the XML file.

<drwn>
 <drwnCodeProfiler enabled="true" />
 <drwnLogger logLevel="VERBOSE" logFile="" />
 <drwnThreadPool threads="4" />
</drwn>

See Also

Configuration Manager

Generating Superpixels/Regions

The first step is to create a set of overlapping superpixels (or regions) for each image. These will be stored in a drwnSuperpixelContainer object, one for each image. The object is saved in the data/regions directory.

The following shell code snippet demonstrates how to generate superpixels for each JPEG image in the data/images directory. If file with the same basename already exists in data/regions then superpixel generation is skipped for that image.

mkdir -p data/regions
foreach IMGFNAME ( data/images/*.jpg )
    set SEGFNAME = data/regions/${IMGFNAME:r:t}.bin
    if (! -e ${SEGFNAME}) then
        ${BIN_DIR}/generateSuperpixels -verbose -m SUPERPIXEL \
            -g 24 -g 17 -g 12 -g 8 -g 6 -g 4 -o ${SEGFNAME} ${IMGFNAME}
    endif
end

Here ${BIN_DIR} should be set to the Darwin bin directory. The "-g" flags specify the rough scale of the image over-segmentation (from 24-by-24 down to 4-by-4). The "-m SUPERPIXEL" flag can be changed to "-m SLIC" for SLIC superpixels. The application visualizeSuperpixels can be used to visualize the resulting set of superpixels.

See Also

generateSuperpixels

Initializing the Superpixel Graph

After generating superpixels for each image in the training set we initialize the superpixel graph by adding a node for every superpixel. We also associate a feature vector (and class label) with each node. The following code will read all images in the MSRC training and validation sets (specified in msrcTrainValList.txt) and add them to a graph. The graph is saved as "nnMSRC.init_train".

${BIN_DIR}/nnGraphInitialize -verbose -profile -log nnMSRC.log -threads 8 \
    -config nnGraphConfig.xml -o nnMSRC.init_train msrcTrainValList.txt

We pre-process the test set in the same way for later evaluation.

${BIN_DIR}/nnGraphInitialize -verbose -profile -log nnMSRC.log -threads 8 \
    -config nnGraphConfig.xml -o nnMSRC.init_test msrcTestList.txt

Learning the Distance Metric

We could build our nearest neighbour graph based on the raw features (using Euclidean distance). However, better results are possible if we learn a distance metric appropriate to the task. The nnGraphLearnTransform application allows various distance metrics to be learned. Note that once the distance metric is learned we apply a transformation to the feature vectors so that evaluating the Euclidean distance on the transformed features is equivalent to evaluating the learned distance metric on the raw features.

The following shell commands learn a distance metric based of the Large-Margin Nearest Neighbor (LMNN) algorithm of Weinberger and Saul (JMLR, 2006) and then transforms the training set features ready for finding nearest neighbours.

${BIN_DIR}/nnGraphLearnTransform -verbose -profile -log nnMSRC.log -threads 8 \
    -set drwnNNGraph K 5 -t LMNN -o nnMSRC_lmnn_5.xform nnMSRC.init_train

${BIN_DIR}/nnGraphApplyTransform -verbose -profile -log nnMSRC.log -threads 8 \
    -o nnMSRC_lmnn_5 nnMSRC_lmnn_5.xform nnMSRC_5.init_train

Optimizing the Superpixel Graph Edges

We are now ready to add and optimize the edges in our graph so that they reflect nearest neighbour matches over superpixels. The code first adds edges randomly and then proceeds to find better matches through a sequence of search moves. You can change which search moves get run in the nnGraphConfig.xml file.

${BIN_DIR}/nnGraphOptimize -verbose -profile -log nnMSRC.log -threads 8 \
    -config nnGraphConfig.xml -set drwnNNGraph K 5 -m 50 \
    -i nnMSRC_lmnn_1 -o nnMSRC_lmnn_5 msrcTrainValList.txt

Performing Label Transfer on Test Set

We are now ready to evaluate performance on the test set. We first add nodes corresponding to superpixels from image in the test set to the graph (applying the appropriate feature transformation).

${BIN_DIR}/nnGraphMerge -verbose -profile -log nnMSRC.log -threads 8 \
    -config nnGraphConfig.xml -o nnMSRC_lmnn_5 -t nnMSRC_lmnn_5.xform \
    nnMSRC_lmnn_5 nnMSRC.init_test

Next we add and optimize edges from images in the test set to those in the training set. We do this on all test set images simultaneously. The fact that we have already built a graph over training set images helps the move making algorithm to find good matches quickly.

${BIN_DIR}/nnGraphOptimize -verbose -profile -log nnMSRC.log -threads 8 \
    -config nnGraphConfig.xml -set drwnNNGraph K 5 -m 50 \
    -i nnMSRC_lmnn_5 -o nnMSRC_lmnn_5 -eqv msrcTestList.txt msrcTestList.txt

Note

The "-eqv msrcTestList.txt" option ensures that we do not add edges between any two images coming from the test set.

We can now transfer labels from the training set images to the test set images and evaluate accuracy.

mkdir -p output

${BIN_DIR}/nnGraphLabelTransfer -config msrcConfig.xml -verbose -profile -log nnMSRC.log -threads 8 \
    -config nnGraphConfig.xml -set drwnNNGraph K 5 -outImages .lmnn_5.png -outLabels .lmnn_5.txt \
    nnMSRC_lmnn_5 msrcTestList.txt

${BIN_DIR}/scorePixelLabels -config msrcConfig.xml -verbose -profile -log nnMSRC.log -threads 8 \
    -inLabels .lmnn_5.txt msrcTestList.txt   

The code will print global and class-averaged accuracy. Annotated images are also saved in the output directory (with extension ".lmnn_5.png").

Performing Label Transfer on a Novel Image (Online Labelling)

We can also process images one at a time. This is useful for labeling novel images. The first step is to create and save regions/superpixels for the novel image.

${BIN_DIR}/generateSuperpixels -verbose -m SUPERPIXEL \
    -g 24 -g 17 -g 12 -g 8 -g 6 -g 4 -o <segFile> <imgFile>

Next we can use the nnGraphOnlineLabelTransfer application to connect the novel image to the nearest neighbour graph and perform label transfer. The following command line shows how to use the previously learned distance metric and graph to transfer labels onto an unseen image.

${BIN_DIR}/nnGraphOnlineLabelTransfer -config msrcConfig.xml -verbose -profile \
    -m 50 -t nnMSRC_lmnn_5.xform -outLabel <outLabelFile> -outImage <outImageFile> \
    nnMSRC_lmnn_5 <imgFile> <segFile>

Note

The application need to load and process labels for all the images in the graph before performing label transfer. This can be slow. If the application is called multiple times the processing can be sped up by caching the labels. See the -labelCache option.

References

• S. Gould, J. Zhao, X. He, and Y. Zhang, "Superpixel Graph Label Transfer with Learned Distance Metric." In ECCV 2014.