linefithough.cpp

barcode readers [ from Image]

//
// Fit a line to a vector of data. Uses method from section 15.2 of
//   "Numerical Recipes in C : The Art of Scientific Computing"
//   by William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling.
//   Cambridge University Press; 2 edition (October 30, 1992).
//   The original source of this code was the fit function from
//   Section 15.2 of the book. See http://library.lanl.gov/numerical/bookcpdf.html
//   for a complete PDF of the book.
//
// Copyright (C) 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 "LineFitHough.h"

namespace Algorithm
{

    EXPORT_C CLineFitHough* CLineFitHough::NewL(int nMinY, int nMaxY, TReal fMinSlope, TReal fMaxSlope, int nSteps)
    {
        CLineFitHough* pMe = new (ELeave) CLineFitHough(nMinY, nMaxY, fMinSlope, fMaxSlope, nSteps);
		CleanupStack::PushL(pMe);
		pMe->ConstructL();
		CleanupStack::Pop(pMe);
		return pMe;
    }

	CLineFitHough::CLineFitHough(int nMinY, int nMaxY, TReal fMinSlope, TReal fMaxSlope, int nSteps) :
		iAccumulator(NULL),
		ifMaxSlope(fMaxSlope),
		ifMinSlope(fMinSlope),
		inMaxY(nMaxY),
		inMinY(nMinY),
		inSlopeSteps(nSteps),
		inYSteps(nMaxY-nMinY+1)
    {
    }

	void CLineFitHough::ConstructL()
	{
		__ASSERT_DEBUG(inYSteps > 1 && inSlopeSteps > 1, User::Invariant());
		iAccumulator = new (ELeave) int [inSlopeSteps * inYSteps];
	}

    CLineFitHough::~CLineFitHough(void)
    {
		delete [] iAccumulator;
    }

    void CLineFitHough::DoIt(CArrayFix<TPoint>* pPoints, int& nY, TReal& fSlope, int& nPoints)
    {
		// first zero the accumulator
		Mem::FillZ(iAccumulator, sizeof(int) * inSlopeSteps * inYSteps);

		// now fill it
		int i;
		for (i=0; i<pPoints->Count(); i++) {
			TPoint p = pPoints->At(i);
			int j;
			int *pAccum = iAccumulator;
			// compute initial intercept
			TReal fInt = p.iY - p.iX * ifMinSlope;
			// this is the amount the intercept will change for each
			// step in slope
			TReal fIntUpdate = p.iX * (ifMaxSlope - ifMinSlope) / (inSlopeSteps - 1);
			for (j=0; j<inSlopeSteps; j++) {
				TInt16 nInt;
				Math::Int(nInt, fInt);
				if (nInt >= inMinY && nInt <= inMaxY) {
					pAccum[nInt - inMinY]++;
				}
				pAccum += inYSteps;
				// update intercept
				fInt -= fIntUpdate;
			}
		}

		// find the maximum
		int nMaxCount = -1;
		int nMaxY = 0, nMaxSlope = 0;
		int *pAccum = iAccumulator;
		for (i=0; i<inSlopeSteps; i++) {
			int j;
			for (j=0; j<inYSteps; j++) {
				if (*pAccum > nMaxCount) {
					nMaxSlope = i;
					nMaxY = j;
					nMaxCount = *pAccum;
				}
				pAccum++;
			}
		}
		if (nMaxCount > -1) {
			nY = nMaxY + inMinY;
			fSlope = TReal(nMaxSlope) * (ifMaxSlope - ifMinSlope) / TReal(inSlopeSteps - 1) + ifMinSlope;
			nPoints = nMaxCount;
		} else {
			nPoints = 0;
		}
	}

};