Image Component Library (ICL)
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Public Types | Public Member Functions | Static Public Member Functions | Private Attributes
icl::filter::ChamferOp Class Reference
Collection of Unary Operations

Chamfering Unit. More...

#include <ChamferOp.h>

Inheritance diagram for icl::filter::ChamferOp:
icl::filter::UnaryOp icl::utils::Configurable

List of all members.

Public Types

enum  hausdorffMetric { hausdorff_max, hausdorff_mean }
 decides which metric is used to calculate the Hausdorff distance More...
enum  outerROIPenaltyMode { noPenalty, constPenalty, distancePenalty }
 decides how to punish model point, that are outside the images ROI, but inside of the image Rect More...

Public Member Functions

 ChamferOp (icl32s horizontalAndVerticalNeighbourDistance=3, icl32s diagonalNeighborDistance=4, int scaleFactor=1, bool scaleUpResult=true)
 Creates a new ChampferOp object with given distances for adjacent image pixels.
virtual ~ChamferOp ()
 destructor
virtual void apply (const core::ImgBase *poSrc, core::ImgBase **ppoDst)
 apply function

Static Public Member Functions

static void renderModel (const std::vector< utils::Point > &model, core::ImgBase **image, const utils::Size &size, icl32s bg=0, icl32s fg=255, utils::Rect roi=utils::Rect::null)
 static utility function to convert a model represented by a point set into a binary image
static double computeDirectedHausdorffDistance (const core::Img32s *chamferImage, const std::vector< utils::Point > &model, hausdorffMetric m=hausdorff_mean, outerROIPenaltyMode pm=noPenalty, icl32s penaltyValue=0)
 utility function to calculate the directed Hausdorff distance between an image and a model
static double computeDirectedHausdorffDistance (const core::Img32s *chamferImage, const core::Img32s *modelChamferImage, ChamferOp::hausdorffMetric m, ChamferOp::outerROIPenaltyMode pm=noPenalty, icl32s penaltyValue=0)
 utility function to calculate the directed Hausdorff distance between an image and a model-image
static double computeSymmetricHausdorffDistance (const core::Img32s *chamferImageA, const core::Img32s *chamferImageB, hausdorffMetric m=hausdorff_mean, ChamferOp::outerROIPenaltyMode pm=noPenalty, icl32s penaltyValue=0)
 utility function to calculate the symmetric Hausdorff distance between an two model images
static double computeSymmetricHausdorffDistance (const std::vector< utils::Point > setA, const utils::Size &sizeA, const utils::Rect &roiA, core::ImgBase **bufferA, const std::vector< utils::Point > setB, const utils::Size &sizeB, const utils::Rect &roiB, core::ImgBase **bufferB, hausdorffMetric m=hausdorff_mean, ChamferOp::outerROIPenaltyMode pm=noPenalty, icl32s penaltyValue=0, ChamferOp coA=ChamferOp(), ChamferOp coB=ChamferOp())
 utility function to calculate the symmetric Hausdorff distance between an two point sets
static double computeSymmeticHausdorffDistance (const core::Img32s *chamferImage, const std::vector< utils::Point > &model, const utils::Size &modelImageSize, const utils::Rect &modelImageROI, core::ImgBase **bufferImageA, core::ImgBase **bufferImageB, hausdorffMetric m=hausdorff_mean, ChamferOp::outerROIPenaltyMode pm=noPenalty, icl32s penaltyValue=0, ChamferOp co=ChamferOp())
 utility function to calculate the symmetric Hausdorff distance between an a point set and an already chamfered image

Private Attributes

icl32s m_iHorizontalAndVerticalNeighbourDistance
 internally used variable for horizontally or vertically adjacent pixels
icl32s m_iDiagonalNeighborDistance
 internally used variable for diagonal adjacent pixels
int m_iScaleFactor
 internal scale factor
bool m_bScaleUpResult
 defines whether to scale up the result image if m_iScaleFactor is > 1
core::Img32s m_oBufferImage
 temporarily use buffer

Detailed Description

Chamfering Unit.

Chamfering is a procedure called Euclidean-Distance-Transformation (EDT). Input of the Chamfering operation is a binary image. The Chamfering operation creates a map (also called the voronoi surface) which's value at location (x,y) is the distance to the nearest white pixel to the pixel at (x,y) in the image.
Because the calculation of the real euclidean distance to the next white pixel is very expensive $ O(number\,of\,white\,pixels^2)$, an approximation of the euclidean distance is calculated instead.
A good approximation can be obtained by moving a small (3x2)-mask successively over the image in two cycles, where each pixel is assigned to the minimum of all pixels values in the 3x2-neighborhood plus a distance value which approximates the distance to a neighborhood pixel. The following pseudo-code illustrates the chamfering algorithm: 

        INPUT  := I   // image
        OUTPUT := C   // chamfer-image
        
        // step 1 prepare chamfer image
        D1 := "distance between horizontally or vertically adjacent pixels" (e.g. 3)
        D2 := "distance between diagonally adjacent pixels" ( e.g. 4)
        MAX_DISTANCE_VALUE := (I.width+I.height)*max(D1,D2)
  
        for all pixel (x,y) of I do
           if I(x,y) == 255 then 
              C(x,y) = 0   // distance is null there as it is white
           else
              C(x,y) = MAX_DISTANCE_VALUE 
           endif
        endfor
        
        // step 2 forward loop
        w := C.width
        h := C.height
        for x = 1 to w-2 do
            for y = 1 to h-1 do
                 C(x,y) = min( C(x,y), C(x-1,y)+d1 , C(x-1,y-1)+d2 , C(x,y-1)+d1 , C(x+1,y-1)+d2 )
            endfor
        endfor
          
  
        // step 3 backward loop
        for x = w-2 to 1 do
            for y = h-2 to 0 do
                 C(x,y) = min( C(x,y) , C(x+1,y)+d1 , C(x+1,y+1)+d2 , C(x,y+1)+d1 , C(x-1,y+1)+d2 )
            endfor
        endfor
        
  
        // step 4 finalize borders ( this is a performance approximation here !)
        // performs a "replicate-border" call to C with a ROI which is one pixel
        // smaller then the whole image to each direction
        h1 := h-1;
        h2 := h1-1;
        w1 := w-1;
        w2 := w1-1;
        
        for y = 0 to h-1 do
            C(0,y) = C(1,y);
            C(w1,y) = C(w2,y) ;
        endfor
        for x = 0 to w-1 do
            C(x,0) = C(x,1);
            C(x,h1) = C(x,h2) ;
        endfor
  
        // done: C contains an approximation of the voronoi surface of the
        // input image I
        return C

Benchmarks

The chamfering operation complexity is linear to pixel count of an image and it does not change with different input image types:

Image-size 640x480 single channel (Pentium M 1.6GHz)

ROI support

Currently image ROIs are supported, but the chamfering operation will perform step 4 of the above presented algorithm with the image ROI Rect if there is a ROI defined on I.

Explicit scaling

A new feature of the ChamferOp class can be activated using the "scaleFactor" argument of the class constructor. If the given scale-factor is greater then 1, the chamfering operation is applied only on an image, that is scaled down by that factor. The last constructor argument (scaleUpResult) can be used to define whether to scale up the resulting chamfer Image (using NN-Interpolation this time), or to let the result image become smaller (by the scale-factor) then the input image.
Internally the down-scaling is not actually performed, but it is emulated by iterating creating a downscaled chamfer image (Step 1 in the algorithm above). By this means, a scaleFactor of 2 (in x and y direction) provides nearly 400% of the computation speed compared to scale factor 1.
The "scaleUpResult" Feature, however slows down the performace again, as the image scaling operation is more expensive too. (

See also:
BENCH)

Hausdorff-Distance

The Hausdorff-Distance is a metric to measure the similarity of two point sets $A=\{a_1,...,a_n\}$ and $B=\{b_1,...,b_m\}$. It is defined by:

\[ H(A,B) := max ( h(A,B), b(B,A) ) \]

where

\[ h(A,B) := \max\limits_{a_i \in A} \min\limits_{b_j \in B} || a - b || \]

and $ || . || $ is some underlying norm of the points of A and B (e.g. the Euclidean norm) $H(A,B)$ is often called the symmetric Hausdorff-Distance and $h(a,b)$ is often called the directed Hausdorff-Distance.
The implementation of the Hausdorff-Distance measurement refers to the chamfering algorithm to calculate point the "min" distances in constant time.

Hausdorff-Distance measurement functions

In addition to the Chamfering-operation provided by the ChamferOp class as an implementation of the UnaryOp interface, the class provides some static functions to calculate the Hausdorff-Distance. Point-sets can here be defined as a std::vector<Point> or directly as a chamfer'd image, which can increase calculation performance when comparing one Base- image (chamfered once) with many models.

Hausdorff-Distance ROI penalties

When comparing images using the Hausdorff-Distance, sometimes a model, represented by a point set $A=\{a_1,...,a_n\}$ must be compared with an image that is represented by a chamfering image $I(x,y)$. If the image has no full ROI, it is not clear what to do with model points $a_i$ that are inside of the image rect but outside the images ROI. To increase performance, the image is just chamfered inside of its ROI, so no correct chamfering information (nearest white pixel distances) are available outside of the images ROI. The ChamferOp class provides 3 heuristics to tackle outer-ROI outliers of the model which are defined by a so called "outerROIPenaltyMode" (implemented as enum).

  1. noPenalty outliers are skipped
  2. constPenalty outliers are punished with a constant value, that can be set manually
  3. distancePenalty outliers are punished proportionally to the distance to the images ROI (the distance value can be weighted linearly by a manually given factor)

Copying

Please note, that ChampferOp instances are copied shallowly. By this means, you can cheaply pass ChampferOp instances to function calls, but this ops share their internal image buffer, so in some cases inpredictable behaviour can occur.

Member Enumeration Documentation

enum icl::filter::ChamferOp::hausdorffMetric

decides which metric is used to calculate the Hausdorff distance

Enumerator:
hausdorff_max 

implements $h(A,B) := \max\limits_{a_i \in A} \min\limits_{b_j \in B} || a - b || $

hausdorff_mean 

implements $h(A,B) := < \min\limits_{b_j \in B} || a - b || >_{a_i \in A} $

enum icl::filter::ChamferOp::outerROIPenaltyMode

decides how to punish model point, that are outside the images ROI, but inside of the image Rect

Enumerator:
noPenalty 

outer ROI model pixels are not regarded

constPenalty 

outer ROI model pixels are punished with a constant penalty value

distancePenalty 

outer ROI model pixels are punished proportionally to the distance to the ROI

Constructor & Destructor Documentation

icl::filter::ChamferOp::ChamferOp ( icl32s  horizontalAndVerticalNeighbourDistance = 3,
icl32s  diagonalNeighborDistance = 4,
int  scaleFactor = 1,
bool  scaleUpResult = true 
)

Creates a new ChampferOp object with given distances for adjacent image pixels.

Parameters:
horizontalAndVerticalNeighbourDistancedistance between horizontal adjacent pixels
diagonalNeighborDistancedistance between diagonal adjacent pixels useful parameter combinations are e.g. :
  • 1,1 ( equal distance )
  • 1,2 ( equal to the city block distance )
  • 2,3 ( weak approximation of the euclidean distance 1:sqrt(2) )
  • 3,4 ( better approximation of the euclidean distance 1:sqrt(2) )
  • 7,10 ( good approximation of the euclidean distance 1:sqrt(2) )
  • 7071,10000 ( nearly perfect approximation of the euclidean distance 1:sqrt(2) ) Note: As it is more common, this constructor automatically sets the clipToROI property of the parent UnaryOp class to false
scaleFactorTODO
scaleUpResultTODO
virtual icl::filter::ChamferOp::~ChamferOp ( ) [inline, virtual]

destructor

Member Function Documentation

virtual void icl::filter::ChamferOp::apply ( const core::ImgBase *  poSrc,
core::ImgBase **  ppoDst 
) [virtual]

apply function

Parameters:
poSrcsource; image arbitrary parameters; ROI is regarded. If the image has more than one channels, the operation is performed on each channel separately.
ppoDstdestination image, adapted to the source images ROI (dependent on the clipToROI settings
See also:
UnaryOp) and set up to depth32s. Note: to perform an in-place chamfering operation, use 
                       ImgBase *image = new Img32s(...);
                       ...
                       apply(image,&image)

Implements icl::filter::UnaryOp.

static double icl::filter::ChamferOp::computeDirectedHausdorffDistance ( const core::Img32s *  chamferImage,
const std::vector< utils::Point > &  model,
hausdorffMetric  m = hausdorff_mean,
outerROIPenaltyMode  pm = noPenalty,
icl32s  penaltyValue = 0 
) [static]

utility function to calculate the directed Hausdorff distance between an image and a model

For each model point the nearest image pixel distance (expressed by the entries of the given chamferImage is calculated.

Parameters:
chamferImagebase image
modelmodel to compare the image with
mhausforffMetric to use
pmpenaltyMode to use
penaltyValuepenalty value to use (if pm is not noPenalty)
static double icl::filter::ChamferOp::computeDirectedHausdorffDistance ( const core::Img32s *  chamferImage,
const core::Img32s *  modelChamferImage,
ChamferOp::hausdorffMetric  m,
ChamferOp::outerROIPenaltyMode  pm = noPenalty,
icl32s  penaltyValue = 0 
) [static]

utility function to calculate the directed Hausdorff distance between an image and a model-image

For each model point - each point inside the model images ROI, that is 0 (zero value in a chamfer image complies a point there) - the nearest image pixel distance (expressed by the entries of the given chamferImage is calculated.

Parameters:
chamferImagebase image
modelChamferImagemodel to compare the image with
mhausforffMetric to use
pmpenaltyMode to use
penaltyValuepenalty value to use (if pm is not noPenalty)
static double icl::filter::ChamferOp::computeSymmeticHausdorffDistance ( const core::Img32s *  chamferImage,
const std::vector< utils::Point > &  model,
const utils::Size &  modelImageSize,
const utils::Rect &  modelImageROI,
core::ImgBase **  bufferImageA,
core::ImgBase **  bufferImageB,
hausdorffMetric  m = hausdorff_mean,
ChamferOp::outerROIPenaltyMode  pm = noPenalty,
icl32s  penaltyValue = 0,
ChamferOp  co = ChamferOp() 
) [static]

utility function to calculate the symmetric Hausdorff distance between an a point set and an already chamfered image

In some cases, the user has a current observation (an image) and a model, which should be fitted into this image by variation of some intrinsic model parameters. In this case, it is much faster to chamfer the observation image once, before chamfering variated models into an image buffer, so this is actually the most common function.

Parameters:
chamferImageobservation image ( represents point set A by zero entries )
modelsecond point set setB
modelImageSizethe size of the chamfering image which is created to represent setB
modelImageROIthe ROI of the chamfering image which is created to represent setB
bufferImageA,bufferImageBimage buffer to exploit to chamfer setA and setB
mhausforffMetric to use
pmpenaltyMode to use
penaltyValuepenalty value to use (if pm is not noPenalty)
coChamferOp object to exploit for the creation of the chamfer-map for point setB
static double icl::filter::ChamferOp::computeSymmetricHausdorffDistance ( const core::Img32s *  chamferImageA,
const core::Img32s *  chamferImageB,
hausdorffMetric  m = hausdorff_mean,
ChamferOp::outerROIPenaltyMode  pm = noPenalty,
icl32s  penaltyValue = 0 
) [static]

utility function to calculate the symmetric Hausdorff distance between an two model images

The following code explains this function 

          double ab = computeDirectedHausdorffDistance(chamferImageA,chamferImageB,m,pm,penaltyValue);
          double ba = computeDirectedHausdorffDistance(chamferImageB,chamferImageA,m,pm,penaltyValue);
          return m==hausdorff_mean ? (ab+ba)/2 : iclMax(ab,ba);
Parameters:
chamferImageAfirst image
chamferImageBfirst image
mhausforffMetric to use
pmpenaltyMode to use
penaltyValuepenalty value to use (if pm is not noPenalty)
static double icl::filter::ChamferOp::computeSymmetricHausdorffDistance ( const std::vector< utils::Point >  setA,
const utils::Size &  sizeA,
const utils::Rect &  roiA,
core::ImgBase **  bufferA,
const std::vector< utils::Point >  setB,
const utils::Size &  sizeB,
const utils::Rect &  roiB,
core::ImgBase **  bufferB,
hausdorffMetric  m = hausdorff_mean,
ChamferOp::outerROIPenaltyMode  pm = noPenalty,
icl32s  penaltyValue = 0,
ChamferOp  coA = ChamferOp(),
ChamferOp  coB = ChamferOp() 
) [static]

utility function to calculate the symmetric Hausdorff distance between an two point sets

The following code explains this function 

          renderModel(setA,bufferA,sizeA,0,255,roiA);
          renderModel(setB,bufferB,sizeB,0,255,roiB);
          coA.apply(*bufferA,bufferA);
          coB.apply(*bufferB,bufferB);
          return computeSymmetricHausdorffDistance((*bufferA)->asImg<icl32s>(),(*bufferB)->asImg<icl32s>(),m,pm,penaltyValue);
Parameters:
setAfirst point set
sizeAthe size of the chamfering image which is created to represent setA
roiAthe ROI of the chamfering image which is created to represent setA
bufferAimage buffer to exploit to chamfer setA
setBsecond point set
sizeBthe size of the chamfering image which is created to represent setB
roiBthe ROI of the chamfering image which is created to represent setB
bufferBimage buffer to exploit to chamfer setB
mhausforffMetric to use
pmpenaltyMode to use
penaltyValuepenalty value to use (if pm is not noPenalty)
coAChamferOp object to exploit for the creation of the chamfer-map for point setA
coBChamferOp object to exploit for the creation of the chamfer-map for point setB
static void icl::filter::ChamferOp::renderModel ( const std::vector< utils::Point > &  model,
core::ImgBase **  image,
const utils::Size &  size,
icl32s  bg = 0,
icl32s  fg = 255,
utils::Rect  roi = utils::Rect::null 
) [static]

static utility function to convert a model represented by a point set into a binary image

Parameters:
modelmodel to convert into the binary image representation
imagedestination image (adapted to depth 32s, so it can be chamfered in-place)
sizedestination image size
bgimage background color value for the destination image
fgimage foreground (all pixels that are defined by model are set to this value)
roioptionally given destination image ROI ( if null, the whole image rect is used, otherwise, only model-points, which are inside the images ROI are rendered

Member Data Documentation

bool icl::filter::ChamferOp::m_bScaleUpResult [private]

defines whether to scale up the result image if m_iScaleFactor is > 1

icl32s icl::filter::ChamferOp::m_iDiagonalNeighborDistance [private]

internally used variable for diagonal adjacent pixels

icl32s icl::filter::ChamferOp::m_iHorizontalAndVerticalNeighbourDistance [private]

internally used variable for horizontally or vertically adjacent pixels

int icl::filter::ChamferOp::m_iScaleFactor [private]

internal scale factor

core::Img32s icl::filter::ChamferOp::m_oBufferImage [private]

temporarily use buffer

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Generated on Mon Aug 25 2014 16:08:02 for Image Component Library (ICL) by   doxygen 1.7.6.1