www.pudn.com > gsnake.rar > gsnake.tex
\rhead{Object class GSNAKE}
\section{GSNAKE : Generalized Active Contour Model}
{\tt GSNAKE} is a class for modeling and extracting arbitrary deformable contours. It consists of {\tt PYRAMID} for external energy calculation and {\tt CONTOUR} class for internal energy calculation. {\tt GSNAKE} has the following structure :
\begin{verbatim}
class GSNAKE : public PYRAMID,
public CONTOUR {
protected :
double global_lambda; /* global regularization parameters */
double Eint; /* Total internal energy of snake */
double Eext; /* Total external energy of snake */
double Esnake; /* Total snake energy */
EEXTTYPE EextType; /* external energy type */
EDGE *EdgeMap; /* edge map in current pyramid level */
IMAGE *GaussImg; /* gaussImg in current pyramid level */
};
\end{verbatim}
We initialize GSNAKE using generalized Hough transform (section 3.3 of \cite{kn:thesis}) and minimize its energy using dynamic programming with stratified line search (section 3.4 of\cite{kn:thesis}). The internal energy, {\tt Eint}, measures deviation in shape irregularities, while the external energy, {\tt Eext}, adjust the contour model to match the underlying image feature. Based on parameter selection strategy (section\ 2.2 of \cite{kn:thesis}), {\tt glabal\_lambda}, we regularize the tradeoff between {\tt Eint} and {\tt Eext}, and compute the total energy, {\tt Esnake}. Our implementation allows user to select minimax criterion ({\tt \_LOCAL\_MINMAX}), local regularization parameter ({\tt \_LOCAL\_LAMBDA}) or global lambda parameter selection strategy (within the range of 0.0 to 1.0). {\tt EextType} is the type of external energy used, which includes edge gradient ({\tt \_EDGE}), edge magnitude ({\tt \_EDGEMAG}) and image intensity ({\tt \_INTENSITY}).
%
\subsection{GSNAKE constructor}
\subsubsection*{Synopsis}
\begin{verbatim}
GSNAKE(EextTYPE etype = _EDGE, double glambda = _LOCAL_MINMAX)
\end{verbatim}
\subsubsection*{Arguments}
\tb
{\tt etype} & External energy type, includes intensity
(\_INTENSITY), edge \\
& magnitude only (\_EDGEMAG) and edge gradient (\_EDGE)
image energy.\\
{\tt glambda} & Regularization parameter selection strategy, includes
minmax criterion \\
& (\_LOCAL\_MINMAX) and local regularization (\_LOCAL\_LAMBDA).
\te
\subsubsection*{Description}
The constructor selects {\em minimax} criterion as its parameter selection strategy, and uses edge gradient as its external energy type if user does not specify explicitly.
%
\subsection{GSNAKE destructor}
\subsubsection*{Synopsis}
\begin{verbatim}
~GSNAKE(void)
\end{verbatim}
\subsubsection*{Description}
The destructor initializes {\tt EdgeMap} and {\tt GaussImg} to NULL.
%
\subsection{GSNAKE destructor}
\subsubsection*{Synopsis}
\begin{verbatim}
void reset(void)
\end{verbatim}
\subsubsection*{Description}
{\tt reset} initializes {\tt EdgeMap} and {\tt GaussImg} to NULL
%
\subsection{Generating pyramid images}
\subsubsection*{Synopsis}
\begin{verbatim}
int genPyramid(short level, short verbose)
\end{verbatim}
\subsubsection*{Arguments}
\tb
{\tt level} & Levels of pyramid to be generated. \\
{\tt verbose} & Verbose operation mode.
\te
\subsubsection*{Returns}
\tb
{\tt NOERROR} & Successful Operation.\\
{\tt MEMORYERROR} & Memory allocation error.
\te
\subsubsection*{Description}
{\tt genPyramid} generate {\tt PYRAMID} object based on {\tt EextType} specified. To increase robustness, we use histogram equalization parameters ($high\_pct=1.0$, $low\_pct=1.0$, $ high\_val=1.0$, $low\_val=1.0$) for external energy of type \_INTENSITY, and use default condition parameters ($high\_pct=0.95$, $low\_pct=0.9$, $ high\_val=0.9$, $low\_val=0.2$) for external energy of type \_EDGE and \_EDGEMAG.
%
\subsection{Localization of contour}
\subsubsection*{Synopsis}
\begin{verbatim}
int localize( int _Qx=1, int _Qy=1,
int _NR=1, double _QR=0.25,
int _Nrxy=1, double _Qrxy=0.1,
int _Nt=1, double _Qt=RADIAN(10),
int _Ndx=1, double _Qdx=0.1,
int _Ndy=1, double _Qdy=0.1,
double _R=1.0, double _THETA=0.0 )
\end{verbatim}
\subsubsection*{Arguments}
\tb
{\tt \_Qx, \_Qx} & X and Y resolution of {\tt GHOUGH} accumulator
space.\\
{\tt \_NR} & Number of cells in scale change axis.\\
{\tt \_QR} & Resolution for scale change.\\
{\tt \_Nrxy} & Number of cells in diagonal stretching change.\\
{\tt \_Qrxy} & Resolution for diagonal stretching.\\
{\tt \_Nt} & Number of cells in rotation axis.\\
{\tt \_Qt} & Resolution of rotation (in radian).\\
{\tt \_Ndx, \_Ndy} & Number of cell in X and Y of dilution axis.\\
{\tt \_Qdx, \_Qdy} & X and Y resolution of dilution.\\
{\tt \_R} & Scaling factor.\\
{\tt \_THETA} & Initial angle for reference line gsnake.
\te
\subsubsection*{Returns}
\tb
{\tt NOERROR} & Localisation performed successfully. \\
{\tt MEMORYERROR} & Unable to allocate memory for GHOUGH objects.
\te
\subsubsection*{Description}
Based on resolution and allowable range of transformation specified by users, {\tt localize} performs rigid match of a contour with the underlying image by generalized Hough transform (GHT). If Gaussian image and edge map do not exist, it will generate level 1 {\tt PYRAMID}. Localization will only be performed at highest level of pyramid so as to reduce computational time. To increase accuracy, it activates {\tt fineLocalize} if {\tt \_Qx} or {\tt \_Qy} is greater than 1.
%
\subsection{Fine localization of GSNAKE template}
\subsubsection*{Synopsis}
\begin{verbatim}
void fineLocalize( int _qx = 1, int _qy = 1,
int _cg_col = 0, int _cg_row = 0 );
\end{verbatim}
\subsubsection*{Arguments}
\tb
{\tt \_qx, \_qy} & X and Y resolution of translation. \\
{\tt \_cg\_col, \_cg\_row} & Coordinate of center of gravity.
\te
\subsubsection*{Description}
{\tt fineLocalize} moves the localized contour in a small area of {\tt \_qx} x {\tt \_qy}. It calculates external energy during each move and then relocates the contour at place of lowest energy. To increase efficiency, user can also place contour at location with center ({\tt \_cg\_col, \_cg\_row}) before moving. This is useful when the contour can be in a fixed and small locality.
%
\subsection{Minimization of GSNAKE}
\subsubsection*{Synopsis}
\begin{verbatim}
int minimize( int segmentSpacing = 5, int numSearchSegment = 5,
int snaxelSpacing = 5, unsigned char blowup = 1,
int verbose = 0, double theLambda = _DEFINED_LAMBDA,
int showImg = 1,int img_Xoffset = 0, int img_Yoffset = 0 );
\end{verbatim}
\subsubsection*{Arguments}
\tb
{\tt segmentSpacing} & Coarse search spacing. \\
{\tt numSearchSegment} & Number of searched segments around snaxel.\\
{\tt snaxelSpacing} & Snaxel spacing. \\
{\tt blowup} & Image magnification factor.\\
{\tt verbose} & Verbose Flag. \\
{\tt theLambda} & Lambda value. \\
{\tt showImg} & Indication (0:off 1:on) of whether image is to be
shown. \\
{\tt img\_Xoffset, img\_Yoffset} & Offset of a contour from
an showing image.
\te
\subsubsection*{Description}
Based on dynamic programming with stratified line search algorithm, {\tt minimize} performs coarse to fine energy minimization. As minimization progresses from the highest to lowest pyramid level, it inserts new snaxels at interval of {\tt snaxelSpacing} between two snaxels. The {\tt showImg}, {\tt img\_Xoffset} and {\tt img\_Yoffset} allow greater flexibility when applying minimization over a small region of image. In this case, we can cut image into portions and only perform minimization on portion of interest.
%
\subsection{Marginalizing gsnake to get probablity}
\begin{verbatim}
double marginalize(int nhoodTangent, int nhoodNormal)
\end{verbatim}
\subsubsection*{Arguments}
\tb
{\tt nhoodTangent} & Number of searched segments along the tangent axis
of snaxel.\\
{\tt nhoodNormal} & Number of searched segments along the normal axis
of snaxel.
\te
\subsubsection*{Returns}
Probability of match.
\subsubsection*{Description}
{\tt marginalize} sums probablities and finds location that maximize probablity of matched contour operation. The summation is done in a small region of {\tt nhoodTangent} x {\tt nhoodNormal} around a contour.
%
\subsection{Calculating total energy of a gsnake}
\subsubsection*{Synopsis}
\begin{verbatim}
double ESnake( short level, int verbose = 0 );
\end{verbatim}
\subsubsection*{Arguments}
\tb
{\tt level} & Pyramid level of interest. \\
{\tt verbose} & Flag (0:off 1:on) to operate verbose mode.
\te
\subsubsection*{Returns}
Total energy of {\tt GSNAKE}.
\subsubsection*{Description}
{\tt ESnake} compute the total energy of gsnake by regularizing the internal and external energy of each snaxel.
%
\subsection{Calculating total energy of a snaxel}
\subsubsection*{Synopsis}
\begin{verbatim}
double ESnaxel( SNAXEL *now,
BOOLEAN store = _FALSE, int verbose = 0 );
\end{verbatim}
\subsubsection*{Arguments}
\tb
{\tt *sxptr} & Pointer to target snaxel. \\
{\tt store} & Flag to indicate whether to store snaxel energy. \\
{\tt verbose} & Flag (0:off 1:on) to operate verbose mode.
\te
\subsubsection*{Returns}
Snaxel energy. Returns 1.0 if the snaxel coordinate is invalid.
\subsubsection*{Description}
{\tt Esnaxel} calculates the total energy of a snaxel by regularize its internal and external energy.
%
\subsection{Calculating internal energy of a snaxel}
%
\subsection{Caluclating Internal energy at snaxel co-ordinates}
\begin{verbatim}
double EInternal(SNAXEL *now)
\end{verbatim}
\subsubsection*{Arguments}
\tb
{\tt now} & Pointer to target snaxel.
\te
\subsubsection*{Returns}
Internal energy of a snaxel.
\subsubsection*{Description}
{\tt EInternal} computes the internal energy of a snaxel.
%
\subsection{Calculating external energy of a snaxel}
\subsubsection*{Synopsis}
\begin{verbatim}
double EExternal(SNAXEL *now);
\end{verbatim}
\subsubsection*{Arguments}
\tb
{\tt *now} & Pointer to the target snaxel.
\te
\subsubsection*{Returns}
External energy of a snaxel.
\subsubsection*{Description}
{\tt Eexternal} calculates the external energy of snaxel. If {\tt EextType} is {\tt \_INETNSITY}, it will return value $1-\mbox{intensity}$. If {\tt \_EDGEMAG}, it will return value $1-\mbox{edgeMag}$. Otherwise, it will consider both magnitude and direction of an edge point (Eqn 3.18 of \cite{kn:thesis}).
%
\subsection{Showing GSNAKE}
\subsubsection*{Synopsis}
\begin{verbatim}
void showLine( unsigned char blowup=1, int Xoffset=0, int Yoffset= 0)
\end{verbatim}
\subsubsection*{Arguments}
\tb
{\tt blowup} & Image Magnification factor. \\
{\tt Xoffset, Yoffset} & X and Y offset for image display.
\te
\subsubsection*{Description}
{\tt showLine} draws lines between snaxels so as to form a complete contour. The offset values help in showing a contour at various image position.
%
\subsection{Displaying gsnake and image}
\subsubsection*{Synopsis}
\begin{verbatim}
void show( unsigned char blowup =1,short expand = 1,
int showImg = 1,
int img_Xoffset = 0, int img_Yoffset = 0,
int pt_Xoffset = 0, int pt_Yoffset = 0 );
\end{verbatim}
\subsubsection*{Arguments}
\tb
{\tt blowup} & Image magnification factor. \\
{\tt expand} & Contour expansion factor. \\
{\tt showImg} & Flag tp indicate whether the raw image is
to be shown. \\
{\tt img\_Xoffset, img\_Yoffset} & X and Y offset of image position. \\
{\tt pt\_Xoffset, py\_Yoffset} & X and Y offset of snaxel position.
\te
\subsubsection*{Description}
{\tt show} displays snaxel coordinate on the raw image. If {\tt showImg} and {\tt img\_offset} are not specified, the raw image and snaxel coordinate will be shown on an X window. Otherwise, they will be shown on top of an existing image with offset ({\tt img\_Xoffset}, {\tt img\_Yoffset}). The {\tt pt\_Xoffset} and {\tt pt\_Yoffset} are necessary when showing an expanded contour.
%
\subsection{Manual deformation of a contour}
\subsubsection*{Synopsis}
\begin{verbatim}
void deform(short blowup = 1, short expand = 1)
\end{verbatim}
\subsubsection*{Arguments}
\tb
{\tt blowup} & Image magnification factor. \\
{\tt expand} & Contour expansion factor.
\te
\subsubsection*{Description}
{\tt deform} allows manual deformation of a contour shape. By using a mouse, the user can adjust and move individual snaxel around. The expansion factor is necessary when dealing with an expanded contour.
%
\subsection{Duplicating a GSNAKE}
\subsubsection*{Synopsis}
\begin{verbatim}
GSNAKE *duplicate(GSNAKE *target= NULL)
\end{verbatim}
\subsubsection*{Returns}
\begin{itemize}
\item Pointer to new {\tt GSNAKE} if {\tt target} is NULL. Otherwise,
{\tt target} will be returned.
\item NULL if memory allocation fails.
\end{itemize}
\subsubsection*{Description}
{\tt duplicate} creates an exact duplication of itself including {\tt CONTOUR} and {\tt PYRAMID} if {\tt target} is NULL. Otherwise, only {\tt GSNAKE} parameters and {\tt CONTOUR} but not {\tt PYRAMID} are copied. The rationale for this is that the external energy input should be that of the target {\tt GSNAKE}.
%
\subsection{Getting external energy input type}
\subsubsection*{Synopsis}
\begin{verbatim}
EextTYPE getEextType( void )
\end{verbatim}
\subsubsection*{Returns}
External energy type.
\subsubsection* {Description}
{\tt getEextType} returns the external energy input type. The current state of {\tt EextType} will determine the input type in any function requiring external energy input.
%
\subsection{Getting and writing the regularization parameter}
\subsubsection*{Synopsis}
\begin{verbatim}
double getGLambda( void )
void putGLambda(double _lambda)
\end{verbatim}
\subsubsection* {Description}
These methods facilitate the reading and writing of the regularization parameter. The regularization parameter can also be set at {\tt GSNAKE} constructor.
%
\subsection{Retrieving internal and external energy}
\subsubsection*{Synopsis}
\begin{verbatim}
double getEsnake(void)
double getEint(void)
double getEext(void)
\end{verbatim}
\subsubsection*{Returns}
Internal or external energy value.
\subsubsection* {Description}
These methods provide facility for accessing the energy values of GSNAKE. Since these values are stored during energy calculation routines, they may not be the most updated values.
%
\subsection{Example : Localization and minimization of GSNAKE }
A previous example in the section on {\tt GHOUGH} demonstrated the localization of a contour on an image. However, with {\tt GSNAKE}, all these are performed simply by invoking the class methods.
\begin{verbatim}
void testmain( char *imgfile, /* image file */
char *confile, /* contour file */
int level, /* pyramid level */
short mag, /* image magnifiaction factor */
int sspacing, /* snaxel spacing */
int ispacing, /* search segment spacing */
int nhood, /* number segment */
double lambda, /* regularization parameter */
EEXTTYPE Etype) /* external energy type */
{
GSNAKE mysnake(Etype);
/* If no image file or contour file, cannot continue */
if ( (mysnake.putRawImg(imgfile)) || (mysnake.CONTOUR::read(confile)) )
exit(-1);
/* Displaying the operating parameters */
printf("\n******** Operating Parameters ************\n");
printf("\nImage : %s Contour : %s ", imgfile, confile);
printf("\nSearch Spacing : %d Insertion spacing : %d",
sspacing, ispacing);
printf("\nSearch Nhood : %d, Lambda : %f",nhood, lambda);
printf("\nExternal Energy input : ");
switch (Etype) {
case _INTENSITY :
printf("Intensity");
break;
case _EDGE :
printf("Edge energy");
break;
case _EDGEMAG :
printf("Edge magnitude only");
break;
}
if (verbose) printf("\nVerbose mode on");
printf("\n\n************************************************\n\n");
mysnake.generate( level, 1 );
mysnake.PYRAMID::show( mag, level );
printf("\nPress enter to continue");
getchar();
printf("\nPerforming localization and minimisation");
mysnake.GSNAKE::localize();
mysnake.GSNAKE::minimize(sspacing, nhood, ispacing, mag, verbose,
lambda, 1);
printf("\nEnd of test. Press enter. ");
getchar();
}
\end{verbatim}
This program first reads a contour file and filters an image file as its {\tt rawImg}. Based on the operating parameters, a pyramid is generated and {\tt localize} and {\tt minimize} methods are invoked. The contour used for localization and minimization should preferably be generated from the image itself. This is due to the problem of mismatching coordinates. For example, two contours with the same shape but with coordinates differing by 100 points might not be localized on the same features, depending on the localization parameters. If the localization parameter is too large, the program may take extremely long time. Besides, if the contour is larger than the image, it will probably result in an error.
%
\subsection{Example : Energy calculation I}
This program performs internal, external and total energy calculation of a gsnake before and after manual deformation.
\begin{verbatim}
void testmain( char *imgfile, /* image file */
int level, /* pyramid level */
int mag, /* magnification factor */
char *outfile) /* output file */
{
int row, col; /* image of size colxrow*/
GSNAKE mysnake; /* GSNAKE object */
SNAXEL *sptr; /* SNAXEL object */
short register i;
if (mysnake.putRawImg(imgfile) ) exit(-1);
row = mysnake.PYRAMID::rawImg->getRow();
col = mysnake.PYRAMID::rawImg->getCol();
mysnake.generate(level,1);
/* Autoinitialising of a closed snake */
/* centre at cg of image, radius= smaller of row/col divide by 4 */
printf("\nCreating template from image dimension ..");
mysnake.CONTOUR::init(row/2, col/2,(double)MIN(row,col)/4);
printf("\nPerforming localisation of contour.");
mysnake.localize();
printf("\nLocalized !");
printf("\nPress enter to continue ..");
getchar();
printf("[col row]\tEint\tEext\tEtotal\tLambda\n");
printf("---------\t----\t----\t------\t------\n");
mysnake.ESnake( 0, 1 );
printf("\nTotal energy of snake: %f\n",mysnake.getEsnake() );
/* Manual deformation of snake */
mysnake.deform(mag);
printf("[col row]\tEint\tEext\tEtotal\tLambda\n");
printf("---------\t----\t----\t------\t------\n");
mysnake.ESnake( 0, 1 );
printf("\nTotal energy after deformation : %f\n",
mysnake.getEsnake() );
printf("\nPress enter to continue..");
getchar();
if (outfile) {
printf("\nWriting to file %s\n\n",outfile);
mysnake.CONTOUR::write(outfile);
}
}
\end{verbatim}
The program reads in an image file and automatically generates a {\tt \_CLOSED} contour. {\tt deform} allows the user to adjust manually the contour shape. {\tt ESnake} will calculate and compare energy values before and after deformation.
Manual deformation is useful in cases where the contour is more or less standard and it is only necessary to slightly modify the template to fit the image better. It is also useful for shape learning purposes.
%
\subsection{Example : Energy calculation II}
This program performs internal, external and total energy calculation of a gsnake before and after fine localization.
\begin{verbatim}
void testmain( char *imgfile, /* image file */
int level, /* pyramid level */
int mag, /* magnification factor */
int correlateX, /* X resolution for correlation */
int correlateY, /* Y resolution for correlation */
char *outfile) /* output file */
{
int row, col, i;
GSNAKE mysnake;
SNAXEL *sptr;
if (mysnake.putRawImg(imgfile) ) exit(-1);
row = mysnake.PYRAMID::rawImg->getRow();
col = mysnake.PYRAMID::rawImg->getCol();
mysnake.generate(level,1);
/* Autoinitialising of a closed snake */
/* centre at cg of image, radius= smaller of row/col divide by 4 */
printf("\nCreating template from image dimension ..");
mysnake.CONTOUR::init(row/2, col/2,(double)MIN(row,col)/4);
printf("\nPerforming localisation of contour.");
mysnake.localize();
mysnake.computeCG();
mysnake.computeAvgLength();
printf("\nEnergy values before fine localisation ");
printf("\n Snake energy calculation");
printf("\n********************************");
printf("\n[col row]\tEint\tEext\tEtotal\tLambda\n");
printf("---------\t----\t----\t------\t------\n");
mysnake.ESnake( 0, 1 );
printf("\nTotal energy : %f\n",
mysnake.getEsnake() );
mysnake.show(mag);
printf("\nPress enter to continue ..");
getchar();
mysnake.fineLocalize( correlateX, correlateY );
printf("\nTotal energy after fine localisation ");
printf("\n Snake energy calculation");
printf("\n********************************");
printf("\n[col row]\tEint\tEext\tEtotal\tLambda\n");
printf("---------\t----\t----\t------\t------\n");
mysnake.computeCG();
mysnake.computeAvgLength();
mysnake.ESnake( 0, 1 );
printf("\nTotal energy : %f\n", mysnake.getEsnake() );
mysnake.show(mag);
printf("\nPress enter to continue ..");
getchar();
}
\end{verbatim}
In this program, {\tt fineLocalize} reallocates the contour at a finer resolution. {\tt ESnake} will calculate and compare energy values before and after fine localization.