widths2bars.cpp

barcode readers [ from Image]

//
// CWidths2Bars
// Given an array of edge positions compute a string
// representing the bar code widths corresponding to those edge
// positions.
//
// 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 "Widths2Bars.h"

namespace Algorithm
{

    EXPORT_C CWidths2Bars* CWidths2Bars::NewL(TReal rMinWidth, TReal rMaxWidth, TReal rEps, int nMinBars)
    {
        return new (ELeave) CWidths2Bars(rMinWidth, rMaxWidth, rEps, nMinBars);
    }

    CWidths2Bars::CWidths2Bars(TReal rMinWidth, TReal rMaxWidth, TReal rEps, int nMinBars) :
	    inMinBars(nMinBars),
		irEps(rEps),
		irMaxWidth(rMaxWidth),
		irMinWidth(rMinWidth)
    {
		if (inMinBars < 2) {
			inMinBars = 2;
		}
    }

    CWidths2Bars::~CWidths2Bars(void)
    {
    }

    bool CWidths2Bars::FindBarsL(CArrayFix<TReal>* pPositions, CArrayFix<char>*& pBars, int& nBarStart, int& nBarEnd)
	{
		if (pPositions->Count() < inMinBars) {
			return false;
		}
		CArrayFixFlat<TReal>& widths(*new CArrayFixFlat<TReal>(16));
		CleanupStack::PushL(&widths);
		// transform the edge positions into an array of bar widths
		// skip over bars that are too narrow
		int i;
		TReal rPosPrev = (*pPositions)[0];
		for (i=1; i<pPositions->Count(); i++) {
			// the invariant here is that widths 0..i-1 holds all
			// bar widths from pPositions where the bar width is
			// greater than the minimum 
			TReal rPosThis = (*pPositions)[i];
			TReal rWidth = rPosThis - rPosPrev;
			if (rWidth >= irMinWidth) {
				widths.AppendL(rWidth);
			} else {
				// skip this bar -- it represents noise.
				// do not update rPosPrev -- which will cause
				// the previous bar to be continued
			}
			rPosPrev = rPosThis;
		}
		if (widths.Count() < inMinBars) {
			CleanupStack::PopAndDestroy(&widths);
			return false;
		}
		// now find the shortest bar width in the array
		TReal rShortest = widths[0];
		for (i=0; i<widths.Count()-1; i++) {
			if (widths[i] < rShortest) {
				rShortest = widths[i];
			}
		}
		// there may be several bars around this width; we average them to get
		// the true shortest bar width, so long as they're within irEps
		int nBars = 0;
		TReal rSum = 0.0;
		for (i=0; i<widths.Count()-1; i++) {
			if (widths[i] < rShortest * (1.0+irEps)) {
				rSum += widths[i];
				nBars += 1;
			}
		}	
		// get the average shortest width
		rShortest = rSum / nBars;
		// divide all bars by the shortest so we can talk in terms of bar
		// width relative to the shortest from now on
		for (i=0; i<widths.Count(); i++) {
			widths[i] /= rShortest;
		}	
		// bars greater than the maximum width are dead space on one side or another
		// of a bar code. Since we are looking for a single bar code we determine which
		// series of bars separated by a too-wide bar is the longest and use that
		int nBestStart = 0, nBestLength = 0;
		int nCurStart = 0, nCurLength = 0;
		for (i=0; i<widths.Count(); i++) {
			// the invariant here is that nBestStart ... nBestEnd is the
			// best sequence of bars, with no internal bar greater than
			// irMaxWidth in width, for all widths from 0..i-1
			// Also nCurStart...nCurEnd is the sequence of bars from the
			// last best sequence to i-1
			if (widths[i] > irMaxWidth) { // a new bar sequence end
				// is it longer than the best sequence so far
				if (nCurLength > nBestLength) {
					nBestStart = nCurStart;
					nBestLength = nCurLength;
				}
				nCurStart = i + 1;
				nCurLength = 0;
			} else {
				nCurLength += 1;
			}
		}
		// check if the final bar sequence was longer than the best
		if (nCurLength > nBestLength) {
			nBestStart = nCurStart;
			nBestLength = nCurLength;
		}
		if (nBestLength < inMinBars) {
			CleanupStack::PopAndDestroy(&widths);
			return false;
		}
		// delete the other elements from the array
		// remove the first nBestStart elements from the array
		// which will bring the element at nBestStart to the front
		if (nBestStart > 0) {
			widths.Delete(0, nBestStart);
		}
		// and all the elements after the ones we want
		if (nBestLength < widths.Count()) {
			widths.Delete(
				nBestLength, 
				widths.Count() - nBestLength);
		}

		// now transform the array into an array of output bar relative widths
		pBars = new (ELeave) CArrayFixFlat<char>(128);
		for (i=0; i<widths.Count(); i++) {
			// the invariant here is that widths 0..i-1 have been turned into
			// digits
			TInt32 nRelative;
			Math::Int(nRelative, widths[i] + 0.49); // round
			pBars->AppendL((unsigned char) Min(nRelative, 255));
		}
		CleanupStack::PopAndDestroy(&widths);
		return true;
	}

}; // namespace Algorithm