Image Component Library (ICL)

Chamfering Unit. More...
#include <ChamferOp.h>
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 modelimage  
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 
Chamfering Unit.
Chamfering is a procedure called EuclideanDistanceTransformation (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 , 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 3x2neighborhood plus a distance value which approximates the distance to a neighborhood pixel. The following pseudocode illustrates the chamfering algorithm:
INPUT := I // image OUTPUT := C // chamferimage // 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 w2 do for y = 1 to h1 do C(x,y) = min( C(x,y), C(x1,y)+d1 , C(x1,y1)+d2 , C(x,y1)+d1 , C(x+1,y1)+d2 ) endfor endfor // step 3 backward loop for x = w2 to 1 do for y = h2 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(x1,y+1)+d2 ) endfor endfor // step 4 finalize borders ( this is a performance approximation here !) // performs a "replicateborder" call to C with a ROI which is one pixel // smaller then the whole image to each direction h1 := h1; h2 := h11; w1 := w1; w2 := w11; for y = 0 to h1 do C(0,y) = C(1,y); C(w1,y) = C(w2,y) ; endfor for x = 0 to w1 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
The chamfering operation complexity is linear to pixel count of an image and it does not change with different input image types:
Imagesize 640x480 single channel (Pentium M 1.6GHz)
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.
A new feature of the ChamferOp class can be activated using the "scaleFactor" argument of the class constructor. If the given scalefactor 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 NNInterpolation this time), or to let the result image become smaller (by the scalefactor) then the input image.
Internally the downscaling 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. (
The HausdorffDistance is a metric to measure the similarity of two point sets and . It is defined by:
where
and is some underlying norm of the points of A and B (e.g. the Euclidean norm) is often called the symmetric HausdorffDistance and is often called the directed HausdorffDistance.
The implementation of the HausdorffDistance measurement refers to the chamfering algorithm to calculate point the "min" distances in constant time.
In addition to the Chamferingoperation provided by the ChamferOp class as an implementation of the UnaryOp interface, the class provides some static functions to calculate the HausdorffDistance. Pointsets 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.
When comparing images using the HausdorffDistance, sometimes a model, represented by a point set must be compared with an image that is represented by a chamfering image . If the image has no full ROI, it is not clear what to do with model points 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 outerROI outliers of the model which are defined by a so called "outerROIPenaltyMode" (implemented as enum).
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.
decides how to punish model point, that are outside the images ROI, but inside of the image Rect
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.
horizontalAndVerticalNeighbourDistance  distance between horizontal adjacent pixels 
diagonalNeighborDistance  distance between diagonal adjacent pixels useful parameter combinations are e.g. :

scaleFactor  TODO 
scaleUpResult  TODO 
virtual icl::filter::ChamferOp::~ChamferOp  (  )  [inline, virtual] 
destructor
virtual void icl::filter::ChamferOp::apply  (  const core::ImgBase *  poSrc, 
core::ImgBase **  ppoDst  
)  [virtual] 
apply function
poSrc  source; image arbitrary parameters; ROI is regarded. If the image has more than one channels, the operation is performed on each channel separately. 
ppoDst  destination image, adapted to the source images ROI (dependent on the clipToROI settings 
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.
chamferImage  base image 
model  model to compare the image with 
m  hausforffMetric to use 
pm  penaltyMode to use 
penaltyValue  penalty 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 modelimage
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.
chamferImage  base image 
modelChamferImage  model to compare the image with 
m  hausforffMetric to use 
pm  penaltyMode to use 
penaltyValue  penalty 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.
chamferImage  observation image ( represents point set A by zero entries ) 
model  second point set setB 
modelImageSize  the size of the chamfering image which is created to represent setB 
modelImageROI  the ROI of the chamfering image which is created to represent setB 
bufferImageA,bufferImageB  image buffer to exploit to chamfer setA and setB 
m  hausforffMetric to use 
pm  penaltyMode to use 
penaltyValue  penalty value to use (if pm is not noPenalty) 
co  ChamferOp object to exploit for the creation of the chamfermap 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);
chamferImageA  first image 
chamferImageB  first image 
m  hausforffMetric to use 
pm  penaltyMode to use 
penaltyValue  penalty 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);
setA  first point set 
sizeA  the size of the chamfering image which is created to represent setA 
roiA  the ROI of the chamfering image which is created to represent setA 
bufferA  image buffer to exploit to chamfer setA 
setB  second point set 
sizeB  the size of the chamfering image which is created to represent setB 
roiB  the ROI of the chamfering image which is created to represent setB 
bufferB  image buffer to exploit to chamfer setB 
m  hausforffMetric to use 
pm  penaltyMode to use 
penaltyValue  penalty value to use (if pm is not noPenalty) 
coA  ChamferOp object to exploit for the creation of the chamfermap for point setA 
coB  ChamferOp object to exploit for the creation of the chamfermap 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
model  model to convert into the binary image representation 
image  destination image (adapted to depth 32s, so it can be chamfered inplace) 
size  destination image size 
bg  image background color value for the destination image 
fg  image foreground (all pixels that are defined by model are set to this value) 
roi  optionally given destination image ROI ( if null, the whole image rect is used, otherwise, only modelpoints, which are inside the images ROI are rendered 
bool icl::filter::ChamferOp::m_bScaleUpResult [private] 
defines whether to scale up the result image if m_iScaleFactor is > 1
internally used variable for diagonal adjacent pixels
internally used variable for horizontally or vertically adjacent pixels
int icl::filter::ChamferOp::m_iScaleFactor [private] 
internal scale factor
temporarily use buffer