ghough.tex

图像中非刚性曲线的蛇形检测算法

\rhead {class GHOUGH}
\section{GHOUGH : Generalised Hough Transform Object}
Based on generalized Hough transform (GHT) \cite{kn:ball81}, {\tt GHOUGH} is a class for localizing objects of a particular shape from an input image or edge map. It is defined as follows :

\begin{verbatim} 
class GHOUGH {

    protected :
        IMAGE **Planes;	                /* Planes of accumulator cells */ 
        CONTOUR **Template;             /* Templates under transformations */
        double **Angle;                 /* desired gradient angles */
        int NumPlane;                   /* actual # of planes */
        int Qx, Qy;                     /* X, Y resolutions of planes */
        double QR, Qrxy;                /* scale resolutions */
        double Qt;                      /* theta resolutions */
        double Qdx, Qdy, Qc;            /* dilation resolutions */
        int NR, Nrrxy, Nt, Ndx, Ndy;    /* # of cells in each of the axis */
        double R;                       /* scaling factor */
        double THETA;                   /* initial angle for ref. line angle */
        int plane_max;                  /* store index for blanking */
        int row_max;
        int col_max;
};
\end{verbatim}

Our implementation is capable of localizing contour which may have undergone affine transformation. We separate affine transformation, $T$, into scaling change, $T(R)$, and dilation matrix, $T(d)$, centered at 1, and rotation matrix, $T(t)$, indexed by {\tt THETA} centered at 0, as follows :

\eq
        T = T(R) T(t) T(d)
\en
where
\[
        {\bf T}(r) = R \left[ \begin{array}{cc}
                                rxy & 0 \\
                                0   & rxy
                             \end{array}  \right]
	\mbox{and} \
	{\bf T}(d) = \left[ \begin{array}{rc}
                                1 & dx \\
                                dy & 1
                             \end{array}  \right]
	\mbox{and} \
	{\bf T}(t) = \left[ \begin{array}{rc}
                                \cos(\theta) & \sin(\theta) \\
                                -\sin(\theta) & \cos(\theta)
                             \end{array}  \right]
\]

The {\tt Q} value control the resolution of transformation, while {\tt N} values control the number of cells or allowable range. For a given reference contour, the total instances of transformation generated are $(NR) (Nrxy) (Nt) (Ndx) (Ndy)$.


%
\subsection{GHOUGH constructor}

\subsubsection*{Synopsis}
\begin{verbatim}
	GHOUGH(int _Qx=1, int _Qy=1, 
               int _NR=1, double  _QR=0.25, 
               int _Nrxy=1, double _Qrxy=0.25,
               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*{Description}
The constructor initializes the values of transformation parameters.


%
\subsection{GHOUGH destructor}

\subsubsection*{Synopsis}
\begin{verbatim}
	~GHOUGH()
\end{verbatim}

\subsubsection*{Description}
The destructor frees the memory allocated to {\tt Template}, {\tt Planes} and {\tt Angle}, and resets the plane indexing values.


%
\subsection{Resetting GHOUGH object}

\subsubsection*{Synopsis}
\begin{verbatim}
	reset()
\end{verbatim}

\subsubsection*{Description}
The destructor frees the memory allocated to {\tt Template}, {\tt Planes} and {\tt Angle}, and resets the plane indexing values.


%
\subsection{Finding one contour}

\subsubsection*{Synopsis}
\begin{verbatim}
	CONTOUR *localize(CONTOUR *reference, IMAGE *img)
	CONTOUR *localize(CONTOUR *reference, EDGE *edgeMap)
\end{verbatim}

\subsubsection*{Arguments} 
\tb
	{\tt reference} & Reference contour. \\
	{\tt *edgeMap}  & Edge map. \\
	{\tt *img}  & Gaussian image or intensity image.
\te	

\subsubsection*{Returns}
Localized contour.

\subsubsection*{Description}
{\tt localize} performs general Hough transform to locate the desired image feature. It generates various instance of transformation contours and correlates them with the underlying image or edge map. The instance which consists of maximun count at center of gravity after correlation, is considered as the best fit of template.

%
\subsection{Finding multiple contours}

\subsubsection*{Synopsis}
\begin{verbatim}
	CONTOUR **localize(CONTOUR *reference, IMAGE *img, int numFind)
	CONTOUR **localize(CONTOUR *reference, EDGE *edgeMap, int numFind)
\end{verbatim}

\subsubsection*{Arguments} 
\tb
	{\tt reference} & Reference contour. \\
	{\tt *edgeMap}  & Edge map. \\
	{\tt *img}  & Gaussian image or intensity image. \\
	{\tt numFind} & Number of localized contours.
\te	

\subsubsection*{Returns}
List of localized contours.

\subsubsection*{Description}
{\tt localize} performs general Hough transform to locate multiple desired image features. It generates various instance of transformation contours and correlates them with the underlying image or edge map. The instances which consist of first {\tt numFind} maximun count at center of gravity after correlation, are considered as the best fit of templates and will be stored in decreasing order.


%
\subsection{Example : Localization of a contour}
The following example demonstrates the match of a rigid contour with the underlying image by generalized Hough transform.

\begin{verbatim}
void testmain( char *imgfile,           /* image file */
               char *cfile,             /* contour file */
               int mag,                 /* magnification factor */
               short level )            /* pyramid level */
{
        PYRAMID mypyramid;              /* PYRAMID object */
        EDGE    *edgemap;               /* EDGE object */
        CONTOUR mycontour;              /* CONTOUR object */
        CONTOUR *localised;             /* CONTOUR object */
        SNAXEL  *sptr;                  /* SNAXEL object */
        GHOUGH  GHT_OBJ;                /* GHOUGH object */
        int     row, col;               /* image of col x row */

        if ( mypyramid.putRawImg(imgfile) )
                exit (-1);

        if (mycontour.read(cfile))
                exit(-1);

        /* Generate pyramid in verbose mode to level 3 */
        mypyramid.generate(level, 1);

        /* Get highest level in pyramid */
        printf("\n Perform localization ... wait\n");
        edgemap = mypyramid.getEdge(level - 1);
        localised = GHT_OBJ.localize( &mycontour, edgemap );

        /* show image */
        mypyramid.rawImg->show(mag);
        for ( sptr=localised->getHead(); sptr; sptr=sptr->getNext() )
                sptr->show( mypyramid.rawImg,
                            ROUNDOFF(sptr->getRow())*mag,
                            ROUNDOFF(sptr->getCol())*mag);

        printf("\nPress enter to end.");
        getchar();
}
\end{verbatim}

{\tt generate} builds one level of edge map and Gaussian pyramid images. With edge map as an input image, {\tt localize} places a contour on the image feature of interest.

	
%
\subsection{Example : Localization of multiple contours}

\begin{verbatim}
void testmain( char *imgfile,           /* image file */
               char *cfile,             /* contour file */
               short numgsnake,         /* number of desired snakes */
               int mag,                 /* magnification factor */
               short level )            /* pyramid level */
{
        PYRAMID mypyramid;              /* PYRAMID object */
        EDGE    *edgemap;               /* EDGE object */
        CONTOUR mycontour;              /* CONTOUR object */
        CONTOUR **localised;            /* CONTOUR object */
        SNAXEL  *sptr;                  /* SNAXEL object */
        GHOUGH  GHT_OBJ;                /* GHOUGH object */
        int     row, col;               /* image of col x row */
        int     ratio;
 
        if ( mypyramid.putRawImg(imgfile) )
                exit (-1);

        if (cfile) {

                if (mycontour.read(cfile))
                        exit(-1);
        }

        else {

        /* Initialise a closed contour in the centre of the test image */
        /* Radius of circle = smaller of row and col divide by 5 */
        /* The values are arbitrary */

                row = mypyramid.rawImg->getRow();
                col = mypyramid.rawImg->getCol();

                mycontour.init(row/2,col/2,(double) MIN(row,col)/5,8);
        }

        /* Generate pyramid in verbose mode to level 3 */

        mypyramid.generate(level, 1);
        mypyramid.show(mag,level);
        printf("\nPress enter to continue.");
        getchar();

        printf("\nCo-ordinates before transform\n ");
        mycontour.print();
        mypyramid.rawImg->show(mag);

        for (sptr=mycontour.getHead();sptr;sptr=sptr->getNext())
                sptr->show( mypyramid.rawImg,
                            ROUNDOFF(sptr->getRow())*mag,
                            ROUNDOFF(sptr->getCol())*mag );

        printf("\nPress enter to continue.");
        getchar();

        /* Use external energy input Edge.The edge object used is the
           highest level one because the search area  will be the
           smallest */
        ratio = mypyramid.getLevel()-1;

        /* Reduce contour to size of highest edge */
        mycontour.expand(LEVEL(-ratio));

        /* Get highest level in pyramid */
        edgemap = mypyramid.getEdge(ratio);
        localised = GHT_OBJ.localize( &mycontour, edgemap, numgsnake );

        register short i;

        for ( i=0; i< numgsnake; i++ ) {

            printf("\nLocalised contour [%d] on image.\n", i );

            /* Get the localised gsnake. */
            /* Contour will be in natural image size */
            localised[i]->expand(LEVEL(ratio));
            localised[i]->print();

            mypyramid.rawImg->show(mag);
            for ( sptr=localised[i]->getHead(); sptr; sptr=sptr->getNext() )
                    sptr->show( mypyramid.rawImg,
                            ROUNDOFF(sptr->getRow())*mag,
                            ROUNDOFF(sptr->getCol())*mag);
            printf("\n\nPress Enter to Continue\n");
            getchar();
        }
}
\end{verbatim}

In this program, {\tt generate} builds a pyramid of edge map and Gaussian images, which are treated as input to general Hough transform (GHT). Since GHT performs only at the highest level of pyramid so as to reduce computational time, {\tt expand} reduces the size of contour by {\tt LEVEL(ratio)}. {\tt localize} then finds the {\tt numgsnake} of image features of interest.