houghcircle.cpp

来自「barcode readers [ from Image]」· C++ 代码 · 共 245 行

//
// HoughCircle
//   Finds the center of a circle in an image which consists of
//   potential circle-edges.
//
// Copyright (C) 2003, 2006 by Jon A. Webb (Contact via GMail; username is jonawebb)
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
// 
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
// 
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
//

#include "HoughCircle.h"

#include "Array.h"
#include "Debug.h"
#include "Image.h"
#include "GrayImageIter.h"
#include "GrayIndex.h"
#include "ImageSize.h"
#include "Replicate.h"

#include <e32math.h>
#include <e32std.h>
#include <fbs.h>

using namespace Core;

namespace Algorithm
{
	EXPORT_C CHoughCircle* CHoughCircle::NewL()
	{	
		return new (ELeave) CHoughCircle();	
	}

	CHoughCircle::~CHoughCircle()
	{
	}

	CHoughCircle::CHoughCircle() 
	{
	}

	// Input parameters:
	//   image: the input image. non-edge pixels are 0, edge pixels are non-zero.
	//   nMinSize, nMaxSize: the minimum and maximum radii of the circle
	// Output parameters:
	//   cx, cy: the circle center
	//   r: the circle radius
	//   nPeak: number of edge pixels in this circle
	void CHoughCircle::FindCircleL(CImage image, 
                                   int nMinSize, 
                                   int nMaxSize, 
                                   int& cx, 
                                   int& cy, 
                                   int& r, 
                                   int& nPeak)
	{
		TPoint **pCircle = new (ELeave) TPoint* [nMaxSize - nMinSize + 1];
		CleanupStack::PushL(pCircle);
		CArray<CImage> &pHoughs(*CArray<CImage>::NewL(nMaxSize - nMinSize + 1));
		CleanupStack::PushL(&pHoughs);
		CArray<IGrayIndex> &pIndex(*CArray<IGrayIndex>::NewL(nMaxSize - nMinSize + 1));
		CleanupStack::PushL(&pIndex);
		IReplicate rRepl(image);

		int i=0, j=nMinSize;
		for (; j<=nMaxSize; i++, j++) {
			// calculate the bounds of a circle of each radius
			pCircle[i] = new (ELeave) TPoint [j];
			CleanupStack::PushL(pCircle[i]);
			TInt k=0;
			for (; k<j; k++) {
				TReal rHypot = j*j - k*k;
				TReal rResult = 0;
				User::LeaveIfError(Math::Sqrt(rResult, rHypot));
				TInt32 yCoord = 0;
				User::LeaveIfError(Math::Int(yCoord, rResult));
				pCircle[i][k].SetXY(k,yCoord);
			}	
			
			// allocate and initialize all the images we'll be using as Hough accumulators
			rRepl.CastL(pHoughs[i]); 
			pIndex[i] = IGrayIndex(pHoughs[i]);
			IGrayImageIter it = IGrayImageIter(pHoughs[i]);
			for (; !it.End(); it.NextRow()) {
				while (!it.REnd()) {
					it++() = 0;
				}
			}

		}
		CDebug::ShowImage(image);
		IImageSize rSize(image);
		IGrayImageIter itIn(image);
        for (i=0; !itIn.End(); itIn.NextRow(), i++) {
			for (j=0; !itIn.REnd(); itIn++, j++) {
				if (itIn() != 0) {
					int k=0, l=nMinSize;
					for (; l<=nMaxSize; k++, l++) {
						int m=0;
						for (; m<l; m++) {
							int row = i-pCircle[k][m].iX; // r-, c-
							int col = j-pCircle[k][m].iY;
							if (col>=0) {
								if (row>=0) {
									pIndex[k][row][col]++;
								}
								row = i+pCircle[k][m].iX;    // r+, c-
								if (row<rSize.Height()) {
									pIndex[k][row][col]++;
								}
							} else {
								row = i+pCircle[k][m].iX;
							}
							col = j+pCircle[k][m].iY;    // r+, c+
							if (col<rSize.Width()) {
								if (row<rSize.Height()) {
									pIndex[k][row][col]++;
								}
								row = i-pCircle[k][m].iX;    // r-, c+
								if (row>=0) {
									pIndex[k][row][col]++;
								}
							}
						}
					}
				}
			}
		}
		// now find the peak
		nPeak = -1;
		for (i=0, j=nMinSize; j<=nMaxSize; i++, j++) {
			IGrayImageIter it(pHoughs[i]);
			int row=0;
			for (; !it.End(); it.NextRow(), row++) {
				int col=0;
				for (; !it.REnd(); it++, col++) {
					if (it() > nPeak) {
						nPeak = it();
						cx = row;
						cy = col;
						r = j;
					}
				}
			}
		}
		for (i=nMaxSize-nMinSize; i>=0; i--) {
			CleanupStack::Check(pCircle[i]);
			CleanupStack::PopAndDestroy(); // pCircle[i]
		}
		CleanupStack::Check(&pIndex);
		CleanupStack::PopAndDestroy(); // pIndex
		CleanupStack::Check(&pHoughs);
		CleanupStack::PopAndDestroy(); // pHoughs
		CleanupStack::Check(pCircle);
		CleanupStack::PopAndDestroy(); // pCircle

	}

	// Given a known circle center and an edge image, find the circle having
	// that center and the most edge pixels.
	// Input parameters:
	//   image: the input image. non-edge pixels are 0, edge pixels are non-zero.
	//   nMinSize, nMaxSize: the minimum and maximum radii of the circle
	//   cx, cy: the circle center
	// Output parameters:
	//   r: the circle radius
	//   nPeak: number of edge pixels in this circle
    void CHoughCircle::FindCircleGivenCenterL(CImage image, 
                                              int nMinSize, 
                                              int nMaxSize, 
                                              int cx, 
                                              int cy, 
                                              int& r, 
                                              int& nPeak)
	{
		int *pHoughs = new (ELeave) int [nMaxSize - nMinSize + 1];
		CleanupStack::PushL(pHoughs);
		TReal fMinSize = TReal(nMinSize);
		TReal fMaxSize = TReal(nMaxSize);
		TInt32 nMinLookup;
		Math::Int(nMinLookup, (fMinSize - 0.5f) * (fMinSize - 0.5f));
		TInt32 nMaxLookup;
		Math::Int(nMaxLookup, (fMaxSize + 0.5f) * (fMaxSize + 0.5f));
        int *pSqrt = new (ELeave) int [nMaxLookup - nMinLookup];
		CleanupStack::PushL(pSqrt);

        int i=0;
		for (; i<=nMaxSize-nMinSize; i++) {
            pHoughs[i] = 0;
		}
        // build a lookup table for sqrt
        for (i=nMinLookup; i<nMaxLookup; i++) {
			TReal rSquare = i;
			TReal rResult = 0.0;
			User::LeaveIfError(Math::Sqrt(rResult, rSquare));
            TInt32 nSqrt = 0;
			User::LeaveIfError(Math::Int(nSqrt, rResult));
            // assure rounding happens the right way
            if (nSqrt<nMinSize) {
                nSqrt = nMinSize;
            } else if (nSqrt > nMaxSize) {
                nSqrt = nMaxSize; 
            }
            pSqrt[i-nMinLookup] = nSqrt - nMinSize;
        }

        IGrayImageIter itIn(image);
        for (itIn.Reset(), i=0; !itIn.End(); itIn.NextRow(), i++) {
            int j=0;
			for (; !itIn.REnd(); itIn++, j++) {
				if (itIn() != 0) {
                    int nHypot = (i-cx) * (i-cx) + (j-cy) * (j-cy);
                    if (nHypot >= nMinLookup && nHypot < nMaxLookup) {
                        pHoughs[pSqrt[nHypot - nMinLookup]] ++;
                    }
                }
            }
        }
		// now find the peak
		nPeak = -1;
		for (i=0; i<=nMaxSize-nMinSize; i++) {
            if (pHoughs[i] > nPeak) {
                nPeak = pHoughs[i];
                r = i + nMinSize;
            }
        }

		CleanupStack::PopAndDestroy(); // pSqrt
		CleanupStack::PopAndDestroy(); // pHoughs
	}

};