conncomp.cpp

barcode readers [ from Image]

//
// ConnComp
//   Finds connected components in a binary (0,255) image.
//   Input is a binary byte image with 0 background and non-zero foreground.
//   Output is a short image with 0 background and each component labeled
//   with a different label.
//
// 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 "ConnComp.h"

#include "Image.h"
#include "GrayImageIter.h"
#include "GrayIndex.h"
#include "ImageSize.h"
#include "Replicate.h"
#include "ShortImageIter.h"

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

using namespace Core;

namespace Algorithm
{

	//
	// Lifecycle
	//
	EXPORT_C CConnComp* CConnComp::NewL()
	{	
		CConnComp *me = new (ELeave) CConnComp;
		CleanupStack::PushL(me);
		me->InitializeL();
		CleanupStack::Pop(me);
		return me;	
	}

	CConnComp::~CConnComp()
	{
		User::Free(iTable);
	}

	CConnComp::CConnComp() :
		ibEmpty(true),
		iTable(NULL)
	{
	}

	// Allocate label table and initialize table size.
	void CConnComp::InitializeL()
	{
		ExtendTableL(TableSize);
	}

	// 
	// Operations
	//
	// Return a new label; if the number of labels exceeds the table size
	// double the table size.
	unsigned short CConnComp::NewLabelL() 
	{
		if (++iCurrentLabel >= inCurrentSize) {
			// we can only use up to 2^16 = 65536 labels since the
			// data type used to store them is unsigned short
			const unsigned int twoP16 = 0x10000;
			if (inCurrentSize == twoP16) {
				_LIT(LTooBigErr, "CConnComp: too many labels");
				User::Panic(LTooBigErr, KErrGeneral);
			}
			ExtendTableL(2*inCurrentSize);
		}
		return iCurrentLabel;
	}

	// Merge two labels, by assigning the mapping of one label to the other.
	void CConnComp::Merge(unsigned short l, unsigned short r)
	{
		l = Lookup(l);
		r = Lookup(r);
		while (l != r) {
			unsigned short nL = iTable[l];
			iTable[l] = r;
			l = nL;
		}
	}

	// Look up the mapping for a label. Reduce the chain length for this mapping
	// to 1 in order to ensure very good complexity.
	unsigned short CConnComp::Lookup(unsigned short l)
	{
		unsigned short origL = l;
		while (l != iTable[l]) {
			l = iTable[l];
		}
		while (origL != l) {
			unsigned short nL = iTable[origL];
			iTable[origL] = l;
			origL = nL;
		}
		return l;
	}	

	void CConnComp::ExtendTableL(unsigned int nNewMaxSize)
	{
		if (iTable) {
			iTable = (unsigned short*) 
				User::ReAllocL(
					iTable, 
					sizeof(unsigned short) * nNewMaxSize);
		} else {
			iTable = (unsigned short*) 
				User::AllocL(sizeof(unsigned short) *nNewMaxSize);
		}
		// initialize new entries in table to identity
		unsigned int i;
		for (i=inCurrentSize; i<nNewMaxSize; i++) {
			iTable[i] = (unsigned short) i;
		}
		inCurrentSize = nNewMaxSize;
	}
	
	//
	// Overrides
	//
	CImage CConnComp::FrontL()
	{
		if (ibEmpty) {
			User::Leave(KErrGeneral);
			return CImage();
		}
		ibEmpty = true;
		return iImage;
	}

	// Label an image. 
	// Any non-zero value is treated identically.
	//The code is written so that the input image is
	// never indexed using multiplicative indexing; instead the indexing
	// purely uses IGrayImageIter operators.
	void CConnComp::PushL(CImage image)
	{
        // first convert the input 0, 255 gray image to a binary 0, 1 short image
		// that we can use to store the image labels
		IReplicate rRepl(image);
		CImage imageShort;
		rRepl.CastL(imageShort, EColor64K);
		image.LockLC(); // lock bitmaps
		IGrayImageIter itByte(image);
		IShortImageIter it(imageShort);
		for (; !it.End(); it.NextRow(), itByte.NextRow()) {
			for (; !it.REnd(); it++, itByte++) {
				if (itByte() == 0) {
					it() = 0;
				} else {
					it() = 1;
				}
			}
		}
		// create and initialize iterators for the pixels up and to the left, up, 
		// up and to the right, and left of the current pixel
		//
		// when processing a pixel at 'it' these iterators have the following positions:
		//     itUL  itU  itUR
		//     itL   it
		//
		it.Reset();
		IShortImageIter itUL = it, itU = it, itUR = it, itL = it;
		// Move the iterators down the their correct positions.
		itU++;
		itUR++; 
		itUR++;
		itL.NextRow();
		it.NextRow(); 
		it++;
		// scan the image. whenever two adjacent pixels are non-zero, merge the two
		// labels if they have not already been merged.
		// the first column is special
		if (itL() != 0) {
			itL() = NewLabelL();
		}
		// the first row is special since there is no row above this row.
		while (!it.REnd()) {
			if (it() != 0) {
				if (itL() != 0) {
					it() = itL();
				} else {
					it() = NewLabelL();
				}
			}
			it++;
			itL++;
		}
		// process all other rows in the image.
		while (true) { // break from within when it gets to end
			// it
			it.NextRow(); 
			if (it.End()) {
				break;
			} else { 
				it++; 
			};		
			// go to the next row
			// itUL
			itUL.NextRow();
			// itU
			itU.NextRow(); 
			itU++;
			// itUR
			itUR.NextRow(); 
			itUR++; 
			itUR++;
			// itL
			itL.NextRow();

			// first column is still special
			if (itL() != 0) {
				if (itUL() != 0) {
					itL() = itUL();
				} else {
					itL() = NewLabelL();
				}
			}
			while (!it.REnd()) {
				if (it() != 0) {
					// The pixels we are considering are
					//    itUL    itU    itUR
					//    itL     it
					bool bAssigned = false;
					if (itUL() != 0) {
						it() = itUL();
						bAssigned = true;
					}
					if (itU() != 0) {
						if (bAssigned) {
							Merge(it(), itU());
						}
						it() = itU();
						bAssigned = true;
					}
					if (!itUR.REnd() && itUR() != 0) {
						if (bAssigned) {
							Merge(it(), itUR());
						}
						it() = itUR();
						bAssigned = true;
					}
					if (itL() != 0) {
						if (bAssigned) {
							Merge(itL(), it());
						}
						it() = itL();
					}
					// if no existing label has been assigned, create a new label
					if (!bAssigned) {
						it() = NewLabelL();
					}
				}
				itUL++;
				itU++;
				if (!itUR.REnd()) {
					itUR++;
				}
				itL++;
				it++;
			}

		}

		for (it.Reset(); !it.End(); it.NextRow()) {
			for (; !it.REnd(); it++) {
				if (it() != 0) {
					it() = Lookup(it());
				}
			}
		}
		CleanupStack::PopAndDestroy(); // release bitmaps
		iImage = imageShort;
		ibEmpty = false;
	}

	bool CConnComp::Empty() const
	{
		return ibEmpty;
	}


};