Finding contours with cv::findContours()

With this concept of contour trees in hand, we can look at the cv::findContours() function and see exactly how we tell it what we want and how we interpret its response:

void cv::findContours(
  cv::InputOutputArray    image,         // Input "binary" 8-bit single channel
  cv::OutputArrayOfArrays contours,      // Vector of vectors or points
  cv::OutputArray         hierarchy,     // (optional) topology information
  int                     mode,          // Contour retrieval mode (Figure 14-2)
  int                     method,              // Approximation method
  cv::Point               offset = cv::Point() // (optional) Offset every point
);

void cv::findContours(
  cv::InputOutputArray    image,         // Input "binary" 8-bit single channel
  cv::OutputArrayOfArrays contours,      // Vector of vectors or points
  int                     mode,          // Contour retrieval mode (Figure 14-2)
  int                     method,        // Approximation method
  cv::Point               offset = cv::Point() // (optional) Offset every point
);

The first argument is the input image; this image should be an 8-bit, single-channel image and will be interpreted as binary (i.e., as if all nonzero pixels were equivalent to one another). When it runs, cv::findContours() will actually use this image as scratch space for computation, so if you need that image for anything later, you should make a copy and pass that to cv::findContours(). The second argument is an array of arrays, which in most practical cases will mean an STL vector of STL vectors. This will be filled with the list of contours found (i.e., it will be a vector of contours, where contours[i] will be a specific contour and thus contours[i][j] would refer to a specific vertex in contours[i]).

The next argument, hierarchy, can be either supplied or not supplied (through one of the two forms of the function just shown). If supplied, hierarchy is the output that describes the tree structure of the contours. The output hierarchy will be an array (again, typically an STL vector) with one entry for each contour in contours. Each such entry will contain an array of four elements, each indicating the node to which a particular link from the current node is connected (see Table 14-1).

The mode argument tells OpenCV how you would like the contours extracted. There are four possible values for mode:

cv::RETR_EXTERNAL

Retrieves only the extreme outer contours. In Figure 14-1, there is only one exterior contour, so Figure 14-2 indicates that the first contour points to that outermost sequence and that there are no further connections.

cv::RETR_LIST

Retrieves all the contours and puts them in the list. Figure 14-2 depicts the “hierarchy” resulting from the test image in Figure 14-1. In this case, nine contours are found and they are all connected to one another by hierarchy[i][0] and hierarchy[i][1] (hierarchy[i][2] and hierarchy[i][3] are not used here).⁵

cv::RETR_CCOMP

Retrieves all the contours and organizes them into a two-level hierarchy, where the top-level boundaries are external boundaries of the components and the second-level boundaries are boundaries of the holes. Referring to Figure 14-2, we can see that there are five exterior boundaries, of which three contain holes. The holes are connected to their corresponding exterior boundaries by hierarchy[i][2] and hierarchy[i][3]. The outermost boundary, c0, contains two holes. Because hierarchy[i][2] can contain only one value, the node can have only one child. All of the holes inside of c0 are connected to one another by the hierarchy[i][0] and hierarchy[i][1] pointers.

cv::RETR_TREE

Retrieves all the contours and reconstructs the full hierarchy of nested contours. In our example (Figures 14-1 and 14-2), this means that the root node is the outermost contour, c0. Below c0 is the hole h00, which is connected to the other hole, h01, at the same level. Each of those holes in turn has children (the contours c000 and c010, respectively), which are connected to their parents by vertical links. This continues down to the innermost contours in the image, which become the leaf nodes in the tree.

Figure 14-2. The way in which the tree node variables are used to “hook up” all of the contours located by cv::findContours(). The contour nodes are the same as in Figure 14-1

The next values pertain to the method (i.e., how the contours are represented):

cv::CHAIN_APPROX_NONE

Translates all the points from the contour code into points. This operation will produce a large number of points, as each point will be one of the eight neighbors of the previous point. No attempt is made to reduce the number of vertices returned.

cv::CHAIN_APPROX_SIMPLE

Compresses horizontal, vertical, and diagonal segments, leaving only their ending points. For many special cases, this can result in a substantial reduction of the number of points returned. The extreme example would be a rectangle (of any size) that is oriented along the x-y axes. In this case, only four points would be returned.

cv::CHAIN_APPROX_TC89_L1 or cv::CHAIN_APPROX_TC89_KCOS

Applies one of the flavors of the Teh-Chin chain approximation algorithm.⁶ The Teh-Chin, or T-C, algorithm is a more sophisticated (and more compute-intensive) method for reducing the number of points returned. The T-C algorithm requires no additional parameters to run.

The final argument to cv::findContours() is offset. This argument is optional. If present, every point in the returned contour will be shifted by this amount. This is particularly useful when either the contours are extracted from a region of interest but you would like them represented in the parent image’s coordinate system, or the reverse case, where you are extracting the contours in the coordinates of a larger image but would like to express them relative to some subregion of the image. 

Polygon approximation with cv::approxPolyDP()

The routine cv::approxPolyDP() is an implementation of one of these two algorithms:⁷

void cv::approxPolyDP(
  cv::InputArray  curve,       // Array or vector of 2-dimensional points
  cv::OutputArray approxCurve, // Result, type is same as 'curve'
  double          epsilon,     // Max distance from 'curve' to 'approxCurve'
  bool            closed       // If true, assume link from last to first vertex
);

The cv::approxPolyDP() function acts on one polygon at a time, which is given in the input curve. The output of cv::approxPolyDP() will be placed in the approxCurve output array. As usual, these polygons can be represented as either STL vectors of cv::Point objects or as OpenCV cv::Mat arrays of size N × 1 (but having two channels). Whichever representation you choose, the input and output arrays used for curve and approxCurve should be of the same type.

The parameter epsilon is the accuracy of approximation you require. The meaning of the epsilon parameter is that this is the largest deviation you will allow between the original polygon and the final approximated polygon. closed, the last argument, indicates whether the sequence of points indicated by curve should be considered a closed polygon. If set to true, the curve will be assumed to be closed (i.e., the last point is to be considered connected to the first point).

The Douglas-Peucker algorithm explained

To better understand how to set the epsilon parameter, and to better understand the output of cv::approxPolyDP(), it is worth taking a moment to understand exactly how the algorithm works. In Figure 14-3, starting with a contour (panel b), the algorithm begins by picking two extremal points and connecting them with a line (panel c). Then the original polygon is searched to find the point farthest from the line just drawn, and that point is added to the approximation.

The process is iterated (panel d), adding the next most distant point to the accumulated approximation, until all of the points are less than the distance indicated by the precision parameter (panel f). This means that good candidates for the parameter are some fraction of the contour’s length, or of the length of its bounding box, or a similar measure of the contour’s overall size.

Figure 14-3. Visualization of the DP algorithm used by cv::approxPolyDP(): the original image (a) is approximated by a contour (b) and then—starting from the first two maximally separated vertices (c)—the additional vertices are iteratively selected from that contour (d–f)

Length using cv::arcLength()

The subroutine cv::arcLength() will take a contour and return its length.

double  cv::arcLength(
  cv::InputArray  points,      // Array or vector of 2-dimensional points
  bool            closed       // If true, assume link from last to first vertex
);

The first argument of cv::arcLength() is the contour itself, whose form may be any of the usual representations of a curve (i.e., STL vector of points or an array of two-channel elements). The second argument, closed, indicates whether the contour should be treated as closed. If the contour is considered closed, the distance from the last point in points to the first contributes to the overall arc length.

cv::arcLength() is an example of a case where the points argument is implicitly assumed to represent a curve, and so is not particularly meaningful for a general set of points.

Upright bounding box with cv::boundingRect()

Of course, the length and area are simple characterizations of a contour. One of the simplest ways to characterize a contour is to report a bounding box for that contour. The simplest version of that would be to simply compute the upright bounding rectangle. This is what cv::boundingRect() does for us:

cv::Rect cv::boundingRect(     // Return upright rectangle bounding the points
  cv::InputArray  points,      // Array or vector of 2-dimensional points
);

The cv::boundingRect() function just takes one argument, which is the curve whose bounding box you would like computed. The function returns a value of type cv::Rect, which is the bounding box you are looking for.

The bounding box computation is meaningful for any set of points, regardless of whether those points represent a curve or are just some arbitrary constellation of points.

A minimum area rectangle with cv::minAreaRect()

One problem with the bounding rectangle from cv::boundingRect() is that it returns a cv::Rect and so can represent only a rectangle whose sides are oriented horizontally and vertically. In contrast, the routine cv::minAreaRect() returns the minimal rectangle that will bound your contour, and this rectangle may be inclined relative to the vertical; see Figure 14-4. The arguments are otherwise similar to cv::boundingRect(). The OpenCV data type cv::RotatedRect is just what is needed to represent such a rectangle. Recall that it has the following definition:

class cv::RotatedRect {
  cv::Point2f center;      // Exact center point (around which to rotate)
  cv::Size2f  size;        // Size of rectangle (centered on 'center')
  float       angle;       // degrees
};

So, in order to get a little tighter fit, you can call cv::minAreaRect():

cv::RotatedRect cv::minAreaRect( // Return rectangle bounding the points
  cv::InputArray  points,        // Array or vector of 2-dimensional points
);

As usual, points can be any of the standard representations for a sequence of points, and is equally meaningful for curves and for arbitrary point sets.

Figure 14-4. cv::Rect can represent only upright rectangles, but cv::RotatedRect can handle rectangles of any inclination

A minimal enclosing circle using cv::minEnclosingCircle()

Next, we have cv::minEnclosingCircle().⁸ This routine works pretty much the same way as the bounding box routines, with the exception that there is no convenient data type for the return value. As a result, you must pass in references to variables you would like set by cv::minEnclosingCircle():

void  cv::minEnclosingCircle(
   cv::InputArray points,        // Array or vector of 2-dimensional points
   cv::Point2f&   center,        // Result location of circle center
   float&         radius         // Result radius of circle
);

The input points is just the usual sequence of points representation. The center and radius variables are variables you will have to allocate and which will be set for you by cv::minEnclosingCircle().

The cv::minEnclosingCircle function is equally meaningful for curves as for general point sets.

Fitting an ellipse with cv::fitEllipse()

As with the minimal enclosing circle, OpenCV also provides a method for fitting an ellipse to a set of points:

cv::RotatedRect cv::fitEllipse(  // Return rect bounding ellipse (Figure 14-5)
  cv::InputArray  points         // Array or vector of 2-dimensional points
);

cv::fitEllipse() takes just a points array as an argument.

At first glance, it might appear that cv::fitEllipse() is just the elliptical analog of cv::minEnclosingCircle(). There is, however, a subtle difference between cv::minEnclosingCircle() and cv::fitEllipse(), which is that the former simply computes the smallest circle that completely encloses the given points, whereas the latter uses a fitting function and returns the ellipse that is the best approximation to the point set. This means that not all points in the contour will even be enclosed in the ellipse returned by cv::fitEllipse().⁹ The fitting is done through a least-squares fitness function.

The results of the fit are returned in a cv::RotatedRect structure. The indicated box exactly encloses the ellipse (see Figure 14-5).

Figure 14-5. Ten-point contour with the minimal enclosing circle superimposed (a) and with the best fitting ellipsoid (b). A “rotated rectangle” is used by OpenCV to represent that ellipsoid (c)

Finding the best line fit to your contour with cv::fitLine()

In many cases, your “contour” will actually be a set of points that you believe is approximately a straight line—or, more accurately, that you believe to be a noisy sample whose underlying origin is a straight line. In such a situation, the problem is to determine what line would be the best explanation for the points you observe. In fact, there are many reasons why one might want to find a best line fit, and as a result, there are many variations of how to actually do that fitting.

We do this fitting by minimizing a cost function, which is defined to be:

Here is the set of parameters that define the line, is the ith point in the contour, and r_i is the distance between that point and the line defined by . Thus, it is the function that fundamentally distinguishes the different available fitting methods. In the case of , the cost function will become the familiar least-squares fitting procedure that is probably familiar to most readers from elementary statistics. The more complex distance functions are useful when more robust fitting methods are needed (i.e., fitting methods that handle outlier data points more gracefully). Table 14-2 shows the available forms for and the associated OpenCV enum values used by cv::fitLine().

Table 14-2. Available distance metrics for the distType parameter in cv::fitLine()

distType	Distance metric
cv::DIST_L2		Least-squares method
cv::DIST_L1
cv::DIST_L12
cv::DIST_FAIR		C = 1.3998
cv::DIST_WELSCH		C = 2.9846
cv::DIST_HUBER		C = 1.345

The OpenCV function cv::fitLine() has the following function prototype:

void cv::fitLine(
  cv::InputArray  points,        // Array or vector of 2-dimensional points
  cv::OutputArray line,          // Vector of Vec4f (2d), or Vec6f (3d)
  int             distType,      // Distance type (Table 14-2)
  double          param,         // Parameter for distance metric (Table 14-2)
  double          reps,          // Radius accuracy parameter
  double          aeps           // Angle accuracy parameter
);

The argument points is mostly what you have come to expect, a representation of a set of points either as a cv::Mat array or an STL vector. One very important difference, however, between cv::fitLine() and many of the other functions we are looking at in this section is that cv::fitLine() accepts both two- and three-dimensional points. The output line is a little strange. That entry should be of type cv::Vec4f (for a two-dimensional line), or cv::Vec6f (for a three-dimensional line) where the first half of the values gives the line direction and the second half a point on the line. The third argument, distType, allows us to select the distance metric we would like to use. The possible values for distType are shown in Table 14-2. The param argument is used to supply a value for the parameters used by some of the distance metrics (these parameters appear as the variables C in Table 14-2). This parameter can be set to 0, in which case cv::fitLine() will automatically select the optimal value for the selected distance metric. The parameters reps and aeps represent your required accuracy for the origin of the fitted line (the x, y, z parts) and for the angle of the line (the v_x, v_y, v_z parts). Typical values for these parameters are 1e-2 for both of them.

Finding the convex hull of a contour using cv::convexHull()

There are many situations in which we need to simplify a polygon by finding its convex hull.  The convex hull of a polygon or contour is the polygon that completely contains the original, is made only of points from the original, and is everywhere convex (i.e., the internal angle between any three sequential points is less than 180 degrees). An example of a convex hull is shown in Figure 14-6. There are many reasons to compute convex hulls. One particularly common reason is that testing whether a point is inside a convex polygon can be very fast, and it is often worthwhile to test first whether a point is inside the convex hull of a complicated polygon before even bothering to test whether it is in the true polygon.

Figure 14-6. An image (a) is converted to a contour (b). The convex hull of that contour (c) has far fewer points and is a much simpler piece of geometry

To compute the convex hull of a contour, OpenCV provides the function cv::convexHull():

void cv::convexHull(
  cv::InputArray  points,               // Array or vector of 2-d points
  cv::OutputArray hull,                 // Array of points or integer indices
  bool            clockwise    = false, // true='output points will be clockwise'
  bool            returnPoints = true   // true='points in hull', else indices
);

The points input to cv::convexHull() can be any of the usual representations of a contour. The argument hull is where the resulting convex hull will appear. For this argument, you have two options: if you like, you can provide the usual contour type structure, and cv::convexHull() will fill that up with the points in the resulting convex hull. The other option (see returnPoints, discussed momentarily) is to provide not an array of points but an array of integers. In this case, cv::convexHull() will associate an index with each point that is to appear in the hull and place those indices in hull. In this case, the indexes will begin at zero, and the index value i will refer to the point points[i].

The clockwise argument indicates how you would like to have cv::convexHull() express the hull it computes. If clockwise is set to true, then the hull will be in clockwise order; otherwise, it will be in counterclockwise order. The final argument, returnPoints, is associated with the option to return point indices rather than point values. If points is an STL vector object, this argument is ignored, because the type of the vector template (int versus cv::Point) can be used to infer what you want. If, however, points is a cv::Mat type array, returnPoints must be set to true if you are expecting point coordinates, and false if you are expecting indices.

Testing if a point is inside a polygon with cv::pointPolygonTest()

This first geometry toolkit function is cv::pointPolygonTest(), which allows you to test whether a point is inside of a polygon (indicated by the array contour). In  particular, if the argument measureDist is set to true, then the function returns the distance to the nearest contour edge; that distance is 0 if the point is inside the contour and positive if the point is outside. If the measure_dist argument is false, then the return values are simply +1, –1, or 0 depending on whether the point is inside, outside, or on an edge (or vertex), respectively. As always, the contour itself can be either an STL vector or an n × 1 two-channel array of points.

double cv::pointPolygonTest(   // Return distance to boundary (or just side)
  cv::InputArray contour,      // Array or vector of 2-dimensional points
  cv::Point2f    pt,           // Test point
  bool           measureDist   // true 'return distance', else {0,+1,-1} only
);

Testing whether a contour is convex with cv::isContourConvex()

It is common to want to know whether or not a contour is convex. There are lots of reasons for this, but one of the most typical is that there are a lot of algorithms for working with polygons that either work only on convex polygons or that can be simplified dramatically for the case of convex polygons. To test whether a polygon is convex, simply call cv::isContourConvex() and pass it your contour in any of the usual representations. The contour passed will always be assumed to be a closed polygon (i.e., a link between the last and first points in the contour is presumed to be implied):

bool cv::isContourConvex(      // Return true if contour is convex
  cv::InputArray  contour      // Array or vector of 2-dimensional points
);

Because of the nature of the implementation, cv::isContourConvex() requires that the contour passed to it be a simple polygon. This means that the contour must not have any self-intersections.

Computing moments with cv::moments()

The function that computes these moments for us is:

cv::Moments cv::moments(             // Return structure contains moments
  cv::InputArray points,             // 2-dimensional points or an "image"
  bool           binaryImage = false // false='interpret image values as "mass"'
)

The first argument, points, is the contour we are interested in, and the second, binaryImage, tells OpenCV whether the input image should be interpreted as a binary image. The points argument can be either a two-dimensional array (in which case it will be understood to be an image) or a set of points represented as an N × 1 or 1 × N array (with two channels) or an STL vector of cv::Point objects. In the latter cases (the sets of points), cv::moments will interpret these points not as a discrete set of points, but as a contour with those points as vertices.¹¹ The meaning of this second argument is that if true, all nonzero pixels will be treated as having value 1, rather than whatever actual value is stored there. This is particularly useful when the image is the output of a threshold operation that might, for example, have 255 as its nonzero values. The cv::moments() function returns an instance of the cv::Moments object. That object is defined as follows:

class Moments {
public:
    double m00;                       //   zero order moment               (x1)
    double m10, m01;                  //  first order moments              (x2)
    double m20, m11, m02;             // second order moments              (x3)
    double m30, m21, m12, m03;        //  third order moments              (x4)
    double mu20, mu11, mu02;          // second order central moments      (x3)
    double mu30, mu21, mu12, mu03;    //  third order central moments      (x4)
    double nu20, nu11, nu02;          // second order normalized central (x3)
    double nu30, nu21, nu12, nu03;    //  third order normalized central (x4)
  Moments();
  Moments(
    double m00,
    double m10, double m01,
    double m20, double m11, double m02,
    double m30, double m21, double m12, double m03
  );
  Moments( const CvMoments& moments ); // convert v1.x struct to C++ object
  operator CvMoments() const;          // convert C++ object to v1.x struct
}

A single call to cv::moments() will compute all of the moments up to third order (i.e., moments for which ). It will also compute central moments and normalized central moments. We will discuss those next.

Central moments are invariant under translation

Given a particular contour or image, the m₀₀ moment of that contour will clearly be the same no matter where that contour appears in an image. The higher-order moments, however, clearly will not be. Consider the m₁₀ moment, which we identified earlier with the average x-position of a pixel in the object. Clearly given two otherwise identical objects in different places, the average x-position is different. It may be less obvious on casual inspection, but the second-order moments, which tell us something about the spread of the object, are also not invariant under translation.¹² This is not particularly convenient, as we would certainly like (in most cases) to be able to use these moments to compare an object that might appear anywhere in an image to a reference object that appeared somewhere (probably somewhere else) in some reference image.

The solution to this is to compute central moments, which are usually denoted μ_{p, q} and defined by the following relation:

where:

and:

Of course, it should be immediately clear that μ₀₀ = m₀₀ (because the terms involving p and q vanish anyhow), and that the μ₁₀ and μ₀₁ central moments are both equal to 0. The higher-order moments are thus the same as the noncentral moments but measured with respect to the “center of mass” of (or in the coordinates of the center of mass of) the object as a whole. Because these measurements are relative to this center, they do not change if the object appears in any arbitrary location in the image.

Normalized central moments are also invariant under scaling

Just as the central moments allow us to compare two different objects that are in different locations in our image, it is also often important to be able to compare two different objects that are the same except for being different sizes. (This sometimes happens because we are looking for an object of a type that appears in nature of different sizes—e.g., bears—but more often it is simply because we do not necessarily know how far the object will be from the imager that generated our image in the first place.)

Just as the central moments achieve translational invariance by subtracting out the average, the normalized central moments achieve scale invariance by factoring out the overall size of the object. The formula for the normalized central moments is the following:

This marginally intimidating formula simply says that the normalized central moments are equal to the central moments up to a normalization factor that is itself just some power of the area of the object (with that power being greater for higher-order moments).

There is no specific function for computing normalized moments in OpenCV, as they are computed automatically by cv::Moments() when the standard and central moments are computed.

Hu invariant moments are invariant under rotation

Finally, the Hu invariant moments are linear combinations of the normalized central moments. The idea here is that, by combining the different normalized central moments, we can create invariant functions representing different aspects of the image in a way that is invariant to scale, rotation, and (for all but the one called h₁) reflection.

For the sake of completeness, we show here the actual definitions of the Hu moments:

Looking at Figure 14-7 and Table 14-3, we can gain a sense of how the Hu moments behave. Observe first that the moments tend to be smaller as we move to higher orders. This should be no surprise because, by their definition, higher Hu moments have more powers of various normalized factors. Since each of those factors is less than 1, the products of more and more of them will tend to be smaller numbers.

Figure 14-7. Images of five simple characters; looking at their Hu moments yields some intuition concerning their behavior

Other factors of particular interest are that the I, which is symmetric under 180-degree rotations and reflection, has a value of exactly 0 for h₃ through h₇, and that the O, which has similar symmetries, has all nonzero moments (though in fact, two of these are essentially zero also). We leave it to the reader to look at the figures, compare the various moments, and build a basic intuition for what those moments represent.

Computing Hu invariant moments with cv::HuMoments()

While the other moments were all computed with the same function cv::moments(), the Hu invariant moments are computed with a second function that takes the cv::Moments object you got from cv::moments() and returns a list of numbers for the seven invariant moments:

void cv::HuMoments(
  const cv::Moments& moments, // Input is result from cv::moments() function
  double*            hu       // Return is C-style array of 7 Hu moments
);

The function cv::HuMoments() expects a cv::Moments object and a pointer to a C-style array you should have already allocated with room for the seven invariant moments.

Structure of the shape module

The shape module is built around an abstraction called a cv::ShapeDistanceExtractor. This abstract type is used for any functor whose purpose is to compare two (or more) shapes and return some kind of distance metric that can be used to quantify their dissimilarity. The word distance is chosen because, in most cases at least, the dissimilarity will have the properties expected of a distance, such as being always non-negative and being equal to zero only when the shapes are identical. Here are the important parts of the definition of cv::ShapeDistanceExtractor.

class ShapeContextDistanceExtractor : public ShapeDistanceExtractor {
  public:
  ...
  virtual float computeDistance( InputArray contour1, InputArray contour2 ) = 0;
};

Individual shape distance extractors are derived from this class. We will cover two of them that are currently available. Before we do, however, we need to briefly consider two other abstract functor types: cv::ShapeTransformer and cv::HistogramCostExtractor.

class ShapeTransformer : public Algorithm {

public:
  virtual void estimateTransformation(
    cv::InputArray      transformingShape,
    cv::InputArray      targetShape,
    vector<cv::DMatch>& matches
  ) = 0;

  virtual float applyTransformation(
    cv::InputArray      input,
    cv::OutputArray     output      = noArray()
  ) = 0;

  virtual void warpImage(
    cv::InputArray      transformingImage,
    cv::OutputArray     output,
    int                 flags       = INTER_LINEAR,
    int                 borderMode  = BORDER_CONSTANT,
    const cv::Scalar&   borderValue = cv::Scalar()
  ) const = 0;
};

class HistogramCostExtractor : public Algorithm {

public:
  virtual void  buildCostMatrix(
    cv::InputArray      descriptors1,
    cv::InputArray      descriptors2,
    cv::OutputArray     costMatrix
  )                                                 = 0;

  virtual void  setNDummies( int nDummies )         = 0;
  virtual int   getNDummies() const                 = 0;

  virtual void  setDefaultCost( float defaultCost ) = 0;
  virtual float getDefaultCost() const              = 0;
};

The shape transformer classes are used to represent any of a wide class of algorithms that can remap a set of points to another set of points, or more generally, an image to another image. Affine and perspective transformations (which we have seen earlier) can be implemented as shape transformers, as is an important transformer called the thin plate spline transform. The latter transform derives its name from a physical analogy with a thin metal plate and essentially solves for the mapping that would result if some number of “control” points on a thin metal plate were moved to some set of other locations. The resulting transform is the dense mapping that would result if that thin metal plate were to respond to these deformations of the control points. It turns out that this is a widely useful construction, and it has many applications in image alignment and shape matching. In OpenCV, this algorithm is implemented in the form of the functor cv::ThinPlateSplineShapeTransformer.

The histogram cost extractor generalizes the construction we saw earlier in the case of the earth mover distance, in which we wanted to associate a cost with “shoveling dirt” from one bin to another. In some cases, this cost is constant or linear in the distance “shoveled,” but in other cases we would like to associate a different cost with moving counts from one bin to another.  The EMD algorithm had its own (legacy) interface for such a specification, but the cv::HistogramCostExtractor base class and its  derived classes give us a way to handle general instances of this problem. Table 14-5 shows a list of derived cost extractors.

For each of these extractors and transformers, there is a factory method with a name like createX(), with X being the desired functor name—for example, cv::createChiHistogramCostExtractor(). With these two types in hand, we are now ready to look at some specializations of the shape distance extractor.

The shape context distance extractor

As mentioned at the beginning of this section, OpenCV 3 contains an implementation of shape context distance [Belongie02], packaged inside a functor derived from cv:: ShapeDistanceExtractor. This method, called cv::ShapeContextDistanceExtractor, uses the shape transformer  and histogram cost extractor functors in its implementation.

namespace cv {

  class ShapeContextDistanceExtractor : public ShapeDistanceExtractor {

    public:
    ...
    virtual float computeDistance( 
      InputArray contour1, 
      InputArray contour2 
    ) = 0;
  };

  Ptr<ShapeContextDistanceExtractor> createShapeContextDistanceExtractor(
    int   nAngularBins                          = 12,
    int   nRadialBins                           = 4,
    float innerRadius                           = 0.2f,
    float outerRadius                           = 2,
    int   iterations                            = 3,
    const Ptr<HistogramCostExtractor> &comparer 
                                        = createChiHistogramCostExtractor(),
    const Ptr<ShapeTransformer>       &transformer
                                        = createThinPlateSplineShapeTransformer()
  );

}

In the essence, the Shape Context algorithm computes a representation of each of the two (or N) compared shapes. Each representation considers a subset of points on the shape boundary and, for each sampled point, it builds a certain histogram reflecting the shape appearance in polar coordinates when viewed from that point. All histograms have the same size (nAngularBins * nRadialBins). Histograms for a point pi in shape #1 and a point qj in shape #2 are compared using classical chi-squared distance. Then the algorithm computes the optimal 1:1 correspondence between points (p’s and q’s) so that the total sum of chi-squared distances is minimal. The algorithm is not the fastest—even computing the cost matrix takes N*N*nAngularBins*nRadialBins, where N is the size of the sampled subsets of boundary points—but it gives rather decent results, as you can see in Example 14-4.

#include "opencv2/opencv.hpp"
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;
using namespace cv;

static vector<Point> sampleContour( const Mat& image, int n=300 ) {

  vector<vector<Point> > _contours;
  vector<Point> all_points;
  findContours(image, _contours, RETR_LIST, CHAIN_APPROX_NONE);
  for (size_t i=0; i <_contours.size(); i++) {
    for (size_t j=0; j <_contours[i].size(); j++)
      all_points.push_back( _contours[i][j] );

  // If too little points, replicate them
  //
  int dummy=0;
  for (int add=(int)all_points.size(); add<n; add++)
    all_points.push_back(all_points[dummy++]);

  // Sample uniformly
  random_shuffle(all_points.begin(), all_points.end());
  vector<Point> sampled;
  for (int i=0; i<n; i++)
    sampled.push_back(all_points[i]);
  return sampled;
}

int main(int argc, char** argv) {

  string path    = "../data/shape_sample/";
  int indexQuery = 1;

  Ptr<ShapeContextDistanceExtractor> mysc = createShapeContextDistanceExtractor();

  Size sz2Sh(300,300);
  Mat img1=imread(argv[1], IMREAD_GRAYSCALE);
  Mat img2=imread(argv[2], IMREAD_GRAYSCALE);
  vector<Point> c1 = sampleContour(img1);
  vector<Point> c2 = sampleContour(img2);
  float dis = mysc->computeDistance( c1, c2 );
  cout << "shape context distance between " <<
     argv[1] << " and " << argv[2] << " is: " << dis << endl;

  return 0;

}

Check out the ...samples/cpp/shape_example.cpp example in OpenCV 3 distribution, which is a more advanced variant of Example 14-4.

Hausdorff distance extractor

Similarly to the Shape Context distance, the Hausdorff distance is another measure of shape dissimilarity available through the cv::ShapeDistanceExtractor interface. We define the Hausdorff [Huttenlocher93] distance, in this context, by first taking all of the points in one image and for each one finding the distance to the nearest point in the other. The largest such distance is the directed Hausdorff distance. The Hausdorff distance is the larger of the two directed Hausdorff distances. (Note that the directed Hausdorff distance is, by itself, not symmetric, while the Hausdorff distance is manifestly symmetric by construction.) In equations, the Hausdorff distance H() is defined in terms of the directed Hausdorff distance h() between two sets A and B as follows:¹³

with:

Here is some norm relative to the points of A and B (typically the Euclidean distance).

In essence, the Hausdorff distance measures the distance between the “worst explained” pair of points on the two shapes. The Hausdorff distance extractor can be created with the factory method: cv::createHausdorffDistanceExtractor().

cv::Ptr<cv::HausdorffDistanceExtractor> cv::createHausdorffDistanceExtractor(
  int   distanceFlag = cv::NORM_L2,
  float rankProp     = 0.6
);

Remember that the returned cv::HausdorffDistanceExtractor object will have the same interface as the Shape Context distance extractor, and so is called using its cv::computeDistance() method.