This project implements algorithms based on the PatchMatchGraph data structure described in Gould and Zhang (ECCV 2012), which extends the PatchMatch algorithm of Barnes et al., (SIGGRAPH, 2009; ECCV 2010). The project is part of the Darwin software package. Installation instructions and addtional documentation can be found at http://drwn.anu.edu.au.

Note

The implementation provided here is an improved version of the algorithm that was used to report results in Gould and Zhang (ECCV 2012). Specifically, this version incorporates the following changes:

image pyramids are integral to the patchMatchGraph rather that being externally generated
local and propagation moves search across adjacent pyramid levels
the random search move samples patches from adjacent pyramid levels

Robustness and efficiency changes were also made.

The sample application patchMatchDemo demonstrates the PatchMatchGraph construction on two images. The following command line will run the code on two images imgA.jpg and imgB.jpg and visualize the matches:

../../bin/patchMatchDemo -x -profile -verbose -m 100 \
    -set drwnPatchMatch patchWidth 8 -set drwnPatchMatch patchHeight 8 \
    imgA.jpg imgB.jpg

The following shows an example visualization from the algorithm where the left column shows the two images being matched, the middle column shows the quality of the matches at each pixel location (blue is better), and the right column shows a reconstruction of each image using patches copied from the other image.

A more ellaborate example for building a PatchMatchGraph over multiple images and then using this graph for label transfer is described below.

See Also: drwnPatchMatchGraph, drwnPatchMatchGraphLearner

Building a PatchMatchGraph

These instructions describe how to build a PatchMatchGraph over a given set of images. We will use the example of the Polo dataset, but the steps can easily be adapted to any dataset. The graphs can be quite large so make sure you run on a machine with plenty of memory.

First we will set up a few environment variables:

set BIN_DIR = "${DARWIN}/bin/"
set IMAGE_LIST = "baseNames.txt"
set CONFIG = "poloConfig.xml"
set DATASET = "pmPolo"
set DATADIR = "data/images/"

where BIN_DIR is set to the executables directory, IMAGE_LIST contains the list of image basenames on which the graph will be built, CONFIG contains some configuration parameters, DATA_SET contains the name that will be used to save the PatchMatchGraph and DATA_DIR points to the directory containing the images.

A typical configuration file (poloConfig.xml) may look like:

<drwn>
 <drwnPatchMatch>
   <option name="maxImageSize" value="160" />
   <option name="maxPyramidLevels" value="8" />
   <option name="patchWidth" value="8" />
   <option name="patchHeight" value="8" />
   <option name="K" value="10" />
   <option name="decayRate" value="0.0" />
   <option name="fwdEnrichment" value="10" />
   <option name="allowHFlips" value="true" />
   <option name="allowVFlips" value="false" />
   <option name="localSearch" value="true" />
   <option name="randomExhaustive" value="false" />
 </drwnPatchMatch>
 <drwnCodeProfiler enabled="true" />
 <drwnLogger logLevel="VERBOSE" logFile="polo.log" />
</drwn>

Note that the configuration parameters can also be set on the command line via the -set drwnPatchMatch argument (see Configuration Manager). For example, adding

-set drwnPatchMatch maxImageSize 80

to the command line (after the -config argument) would override the maxImageSize option in the XML file.

The following command line will construct a PatchMatchGraph and save it to three files ${DATASET}.meta, ${DATASET}.index and ${DATASET}.data:

${BIN_DIR}/buildPatchMatchGraph -config ${CONFIG} \

-d ${DATADIR} -e .jpg -m 50 -o ${DATASET} ${IMAGE_LIST}

You can control how the graph is constructed by modifying the various options in the XML configuration file. You can also prevent subsets of images from matching between each other by using equivalence classes. For example, providing the -eqv ${EVAL_LIST} command line option to buildPatchMatchGraph will create an equivalence class containing all images in the file ${EVAL_LIST}. No edges in the PatchMatchGraph will be created between these images. Multiple equivalence classes can be defined with additional -eqv flags, e.g., -eqv ${EVAL_LIST} -eqv -p ${TRAIN_LIST}.

For loading a saved PatchMatchGraph into Matlab see the mexLoadPatchMatchGraph application in Matlab Interfaces.

Using a PatchMatchGraph for Label Transfer

The PatchMatchGraph constructed above can be used for semantic segmentation by transfering labels from matched patches to the image under test. The code makes use of the Multi-class Image Segmentation infrastructure for visualizing and scoring results so you will need to include the class definitions in the configuration file. For the Polo dataset this is:

<drwnMultiSegConfig>
  <!-- data options -->
  <option name="baseDir" value="./" />
  <option name="imgDir" value="data/images/" />
  <option name="lblDir" value="data/labels/" />
  <option name="cacheDir" value="cached/" />
  <option name="modelsDir" value="models/" />
  <option name="outputDir" value="output/" />
  <option name="imgExt" value=".jpg" />
  <option name="lblExt" value=".txt" />
  <option name="useCache" value="true" />
  <!-- region definitions -->
  <regionDefinitions>
    <region id="-1" name="void" color="0 0 0"/>
    <region id="0" name="grass" color="0 128 0"/>
    <region id="1" name="ground" color="64 0 0"/>
    <region id="2" name="horse" color="128 192 128"/>
    <region id="3" name="person" color="128 64 0"/>
    <region id="4" name="sky" color="128 128 128"/>
    <region id="5" name="tree" color="128 128 0"/>
  </regionDefinitions>
</drwnMultiSegConfig>

Configuration files for the Polo, MSRC and Stanford Background datasets are included in the project directory, ${DARWIN}/projects/patchMatch.

The patchMatchLabelTransfer application implements label transfer. Results can be generated and evaluated using:

mkdir -p output
${BIN_DIR}/patchMatchLabelTransfer -config ${CONFIG} \
    -outLabels .pm.txt -outImages .pm.png ${DATASET} ${IMAGE_LIST}
${BIN_DIR}/scorePixelLabels -config ${CONFIG} -confusion \
    -inLabels .pm.txt ${IMAGE_LIST}

Since the code is run on the entire dataset (and the images were not broken up into equivalence classes) the results can be interpreted as leave-one-out cross-validation (i.e., each image is labeled using the rest of the dataset as training data). Using these instructions you should be able to achieve the following results on the Polo, Stanford Background and MSRC datasets:

Dataset	Images	Patches	Memory	Build Time	Accuracy
6-Class Polo	317	9601972	4.9GB	0:54	89.0
8-Class Stanford	715	22566965	11GB	2:28	71.1
21-Class MSRC	591	17050254	8.4GB	1:42	68.5

With an equivalence class defined for the test set (and evaluation on the test set images only) the following results should be achieved:

Dataset	Images	Test Images	Patches	Memory	Build Time	Accuracy
6-Class Polo	317	237	9601972	4.9GB	0:44	86.7
8-Class Stanford	715	143	22566965	11GB	2:14	69.6
21-Class MSRC	591	256	17050254	8.4GB	1:34	64.9

(Note that these differ slightly from Gould and Zhang (ECCV 2012)).

The labelTransferPipeline.py script runs through the above procedure using the Stanford background dataset.

References

Barnes, C., Shechtman, E., Finkelstein, A., Goldman, D.B., "PatchMatch: A randomized correspondence algorithm for structural image editing." In SIGGRAPH, 2009.

Barnes, C., Shechtman, E., Goldman, D.B., Finkelstein, A., "The generalized PatchMatch correspondence algorithm." In ECCV, 2010.

Barnes, C., "PatchMatch: A Fast Randomized Matching Algorithm with Application to Image and Video." PhD Thesis, 2011.

S. Gould and Y. Zhang, "PatchMatchGraph: Building a Graph of Dense Patch Correspondences for Label Transfer." In ECCV, 2012.