searchwindow.hh

来自「Motion JPEG编解码器源代码」· HH 代码 · 共 1,997 行 · 第 1/5 页

		// later time.

public:
	// A class to keep track of our progress during a search inside the
	// pixel sorter.  (This has to be public, in order to allow clients
	// to create one, but the definition is hidden down here because the
	// details of it aren't public.)
	class PixelSorterIterator
	{
	public:
		const PixelGroup *m_pSearch;
			// The pixel group being searched for.

		const PixelSorterBranchNode *m_pBranch;
			// The branch being examined.
			// Initialized to &m_oPixelSorter.
			// If NULL, means the search is over.

		const SearchWindowCell *m_pCell;
			// The last cell examined.
			// If equal to m_pBranch->m_oSplitValue, means that the
			// branch hasn't been examined yet.
	};
};



// Default constructor.
template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,
	class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,
	class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,
	class REFERENCEFRAME>
SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,
	REFERENCEFRAME>::SearchWindow()
{
	// No frames yet.
	m_tnWidth = m_tnHeight = PIXELINDEX (0);

	// No information on the sort of search to do yet.
	m_tnSearchRadiusX = m_tnSearchRadiusY = PIXELINDEX (0);
	m_tnTolerance = m_tnTwiceTolerance = PIXEL_TOL (0);

	// No active search yet.
	m_tnX = m_tnY = PIXELINDEX (0);
	m_pReferenceFrame = NULL;

	// No search window yet.
	m_ppSearchWindow = NULL;
	m_pSearchWindowStorage = NULL;
	m_tnSearchWindowPixelLeft = m_tnSearchWindowPixelRight
		= m_tnSearchWindowPixelTop = m_tnSearchWindowPixelBottom
		= m_tnSearchWindowSortLeft = m_tnSearchWindowSortRight
		= m_tnSearchWindowSortTop = m_tnSearchWindowSortBottom
		= PIXELINDEX (0);
}



// Destructor.
template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,
	class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,
	class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,
	class REFERENCEFRAME>
SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,
	REFERENCEFRAME>::~SearchWindow()
{
	// Destroy the search window.
	delete[] m_ppSearchWindow;
	delete[] m_pSearchWindowStorage;
}



// Initializer.
template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,
	class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,
	class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,
	class REFERENCEFRAME>
void
SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,REFERENCEFRAME>::Init
	(Status_t &a_reStatus, PIXELINDEX a_tnWidth, PIXELINDEX a_tnHeight,
	PIXELINDEX a_tnSearchRadiusX, PIXELINDEX a_tnSearchRadiusY,
	PixelValue_t a_tnTolerance)
{
	int i;
		// Used to loop through things.
	FRAMESIZE tnPixels;
		// The number of pixels in each frame.

	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Make sure the sorter bit-mask type is big enough to hold
	// pixel-sorter branch-node child indices.  (Note that this is
	// technically a compile-time assertion.)
	assert (sizeof (SORTERBITMASK) * g_knBitsPerByte
		> PGH * PGW * DIM);

	// Make sure the width & height are reasonable.
	assert (a_tnWidth > PIXELINDEX (0));
	assert (a_tnHeight > PIXELINDEX (0));

	// Make sure the search radius is reasonable.
	assert (a_tnSearchRadiusX > PIXELINDEX (0)
		&& a_tnSearchRadiusY > PIXELINDEX (0)
		&& a_tnSearchRadiusX <= a_tnWidth
		&& a_tnSearchRadiusY <= a_tnHeight);

	// Make sure the tolerance is reasonable.  (A zero tolerance can
	// be used for MPEG-encoding-style motion detection.)
	assert (a_tnTolerance >= 0);

	// Calculate the number of pixels in each frame.
	tnPixels = FRAMESIZE (a_tnWidth) * FRAMESIZE (a_tnHeight);

	// Allocate enough cells for our search window.
	m_pSearchWindowStorage = new SearchWindowCell
		[(a_tnHeight - PGH + 1) * (a_tnWidth - PGW + 1)];
	if (m_pSearchWindowStorage == NULL)
	{
		a_reStatus = g_kOutOfMemory;
		return;
	}

	// Allocate enough space for our line-based index into the
	// search window storage.
	m_ppSearchWindow = new SearchWindowCell * [a_tnHeight - PGH + 1];
	if (m_ppSearchWindow == NULL)
	{
		a_reStatus = g_kOutOfMemory;
		return;
	}

	// Generate pointers to the beginning of each line in the search
	// window.
	SearchWindowCell *pNextLine = m_pSearchWindowStorage;
	for (i = 0; i < (a_tnHeight - PGH + 1); ++i)
	{
		m_ppSearchWindow[i] = pNextLine;
		pNextLine += (a_tnWidth - PGW + 1);
	}

	// Initialize the root of the pixel-sorter tree to split the
	// available range in half.  Also generate search-window cells
	// that represent the minimum/maximum values for pixels.
	{
		PIXELINDEX x, y;
			// Used to loop through pixels.
		PixelValue_t atnMin[DIM], atnHalf[DIM], atnMax[DIM];
			// What we initialize each pixel to.

		// Generate a pixel value that represents half the available
		// range in each dimension, plus the minimums & maximums.
		for (i = 0; i < DIM; i++)
		{
			atnMin[i] = Limits<PixelValue_t>::Min;
			atnHalf[i] = (Limits<PixelValue_t>::Min
				+ Limits<PixelValue_t>::Max) / 2;
			atnMax[i] = Limits<PixelValue_t>::Max;
		}

		// Loop through all pixels in the root of the pixel-sorter tree,
		// initialize them to half the maximum value.  Set up our
		// search-window minimum/maximum too.
		for (y = 0; y < PGH; ++y)
		{
			for (x = 0; x < PGW; ++x)
			{
				m_oPixelSorterMin.m_atPixels[y][x] = Pixel_t (atnMin);
				m_oPixelSorter.m_oSplitValue.m_atPixels[y][x]
					= Pixel_t (atnHalf);
				m_oPixelSorterMax.m_atPixels[y][x] = Pixel_t (atnMax);
			}
		}
	}

	// Finally, store our parameters.
	m_tnWidth = a_tnWidth;
	m_tnHeight = a_tnHeight;
	m_tnSearchRadiusX = a_tnSearchRadiusX;
	m_tnSearchRadiusY = a_tnSearchRadiusY;
	m_tnTolerance = Pixel_t::MakeTolerance (a_tnTolerance);
	m_tnTwiceTolerance = Pixel_t::MakeTolerance (2 * a_tnTolerance);
}



// Purge the pixel sorter.
template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,
	class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,
	class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,
	class REFERENCEFRAME>
void
SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,
	REFERENCEFRAME>::PurgePixelSorter (void)
{
	// Clear out the pixel-sorter.
	for (SORTERBITMASK i = 0; i < m_oPixelSorter.m_knBranches; ++i)
	{
		if (m_oPixelSorter.m_apBranches[i] != NULL)
		{
			delete m_oPixelSorter.m_apBranches[i];
			m_oPixelSorter.m_apBranches[i] = NULL;
		}
	}
}



// Default constructor.
template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,
	class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,
	class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,
	class REFERENCEFRAME>
SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,REFERENCEFRAME>
	::PixelGroup::PixelGroup()
{
	// No location yet.
	m_tnX = m_tnY = PIXELINDEX (0);
}



// Destructor.
template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,
	class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,
	class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,
	class REFERENCEFRAME>
SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,REFERENCEFRAME>
	::PixelGroup::~PixelGroup()
{
	// Nothing to do.
}



// Returns true if the two pixels groups are equal, within
// the given tolerance.
template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,
	class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,
	class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,
	class REFERENCEFRAME>
bool
SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,REFERENCEFRAME>
	::PixelGroup::IsWithinTolerance (const PixelGroup &a_rOther,
	Tolerance_t a_tnTolerance
#ifdef CALCULATE_SAD
							 , Tolerance_t &a_rtnSAD
#endif // CALCULATE_SAD
													) const
{
	PIXELINDEX tnX, tnY;
		// Used to loop through pixels.

	// Compare the two pixel groups, pixel by pixel.
#ifdef CALCULATE_SAD
	a_rtnSAD = 0;
#endif // CALCULATE_SAD
	for (tnY = 0; tnY < PGH; ++tnY)
	{
		for (tnX = 0; tnX < PGW; ++tnX)
		{
#ifdef CALCULATE_SAD
			Tolerance_t tnSAD;
				// The sum-of-absolute-differences between these two
				// pixels.
#endif // CALCULATE_SAD

			// Get the two pixels of interest.
			const Pixel_t &rThisPixel = m_atPixels[tnY][tnX];
			const Pixel_t &rOtherPixel = a_rOther.m_atPixels[tnY][tnX];

			// If this pixel value is not within the tolerance of
			// the corresponding pixel in the other group, exit now.
			if (!rThisPixel.IsWithinTolerance (rOtherPixel,
				a_tnTolerance
#ifdef CALCULATE_SAD
							 , tnSAD
#endif // CALCULATE_SAD
									))
			{
				return false;
			}

#ifdef CALCULATE_SAD
			// Sum up the sum-of-absolute-differences.
			a_rtnSAD += tnSAD;
#endif // CALCULATE_SAD
		}
	}

	// The pixel groups are equal, within the given tolerance.
	return true;
}



// Default constructor.
template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,
	class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,
	class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,
	class REFERENCEFRAME>
SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,REFERENCEFRAME>
	::SearchWindowCell::SearchWindowCell()
{
	// We haven't been put into the pixel-sorter yet.
	m_pSorter = NULL;
	m_eDoneSorting = m_knNotDone;
}



// Destructor.
template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,
	class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,
	class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,
	class REFERENCEFRAME>
SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,REFERENCEFRAME>
	::SearchWindowCell::~SearchWindowCell()
{
	// Nothing to do.
}



// Begin searching through a frame.
// Provide the frame to search through.
template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,
	class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,
	class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,
	class REFERENCEFRAME>
void
SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,
	REFERENCEFRAME>::StartFrame (ReferenceFrame_t *a_pReferenceFrame)
{
	// Make sure they gave us a frame.
	assert (a_pReferenceFrame != NULL);
	
	// Remember the frame we're operating on this pass.
	m_pReferenceFrame = a_pReferenceFrame;
	
	// We'll be checking the upper-left corner first.
	m_tnX = m_tnY = PIXELINDEX (0);
}



// Prepare for searching, i.e. find all search-window cells within the
// search radius of the current pixel-group that aren't in the
// pixel-sorter already, and put them there.
template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,
	class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,
	class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,
	class REFERENCEFRAME>
void
SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,
	REFERENCEFRAME>::PrepareForSearch (Status_t &a_reStatus,
	bool a_bSortPixels)
{
	PIXELINDEX tnSearchWindowPixelLeft, tnSearchWindowPixelRight,
			tnSearchWindowPixelTop, tnSearchWindowPixelBottom;
		// What the search window should look like when we're done.
	PIXELINDEX tnX, tnY;
		// Used to loop through pixel groups.
	PIXELINDEX tnSearchLeft, tnSearchRight, tnSearchTop, tnSearchBottom;
		// The part of the search window that we actually loop through.
	SearchWindowCell *pCell;
		// The search-window cell corresponding to the pixel group being
		// manipulated.

	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

#ifndef OPTIONALLY_SORT_PIXEL_GROUPS

	// (If we're not doing the expanding-regions variant, make sure
	// they always want to add search-window cells to the pixel-sorter.)
	assert (a_bSortPixels);

#endif // OPTIONALLY_SORT_PIXEL_GROUPS

	// Make sure we have a new frame & reference frame to work with.
	assert (m_pReferenceFrame != NULL);

	// The search window starts in a radius around the index of the
	// current pixel group.
	tnSearchWindowPixelLeft = m_tnX - m_tnSearchRadiusX;
	tnSearchWindowPixelRight = m_tnX + m_tnSearchRadiusX
		+ PIXELINDEX (1);