searchwindow.hh

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

	}

	// The cell can move into a child branch.
	return false;
}



// If the given pixel group straddles this level of the tree
// (i.e. because one of its pixel values equals its
// corresponding split point), then return true.
// Otherwise, calculate the index of the child branch that
// should take this cell, and return false.
// In either case, determine whether any search-window cells
// that had to stop at this level of the tree could possibly
// intersect the given pixel-group.
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>
	::PixelSorterBranchNode::DoesPixelGroupStopHere
	(const PixelGroup *a_pPixelGroup, Tolerance_t a_tnTwiceTolerance,
	SORTERBITMASK &a_rtnChildIndex, bool &a_rbMatchAtThisLevel) const
{
	PIXELINDEX tnX, tnY;
	int i;
		// Used to loop through pixels & pixel dimensions.
	bool bPixelGroupStopsHere;
		// True if one of the pixel-group's pixels exactly matches
		// its corresponding split-point.
	
	// Make sure they gave us a pixel-group.
	assert (a_pPixelGroup != NULL);

	// Compare the group's pixel values to our split values, and
	// determine which child branch it should descend, or if it
	// should stop at this level.
	a_rtnChildIndex = 0;
	bPixelGroupStopsHere = false;
	a_rbMatchAtThisLevel = false;
	for (tnY = 0; tnY < PGH; ++tnY)
	{
		for (tnX = 0; tnX < PGW; ++tnX)
		{
			// Get the two pixels of interest.
			const Pixel_t &rGroupPixel
				= a_pPixelGroup->m_atPixels[tnY][tnX];
			const Pixel_t &rSplitPixel
				= m_oSplitValue.m_atPixels[tnY][tnX];

			// Determine the effect each dimension has on the
			// bitmask that we use to determine the index of the
			// child branch that this cell should descend into.
			// (If the pixel value is right on a branch, then all
			// pixels that would match it have been found at this
			// level.)
			for (i = 0; i < DIM; i++)
			{
				if (rGroupPixel[i] == rSplitPixel[i])
					bPixelGroupStopsHere = true;
				if (rGroupPixel[i] > rSplitPixel[i])
					a_rtnChildIndex |= GetBitMask (tnY, tnX, i);

				// If the current pixel is within twice the tolerance
				// of the split-point, then some of the search-window
				// cells that had to stop at this point in the tree may
				// match the current pixel-group.  (And once we figure
				// that out, we don't have to check any other pixels for
				// this property.)
				if (!a_rbMatchAtThisLevel)
				{
					// Make copies of the two pixels.
					Pixel_t oGroupPixel = rGroupPixel;
					Pixel_t oSplitPixel = rSplitPixel;

					// Collapse all dimensions but the current one.
					for (int j = 0; j < DIM; ++j)
						if (j != i)
							oGroupPixel[j] = oSplitPixel[j];
					
					// If this axis, all by itself, is within twice the
					// tolerance, then we can no longer rule out matches
					// at this level.
					if (oGroupPixel.IsWithinTolerance (oSplitPixel,
						a_tnTwiceTolerance))
					{
						a_rbMatchAtThisLevel = true;
					}
				}
			}
		}
	}

	// Return whether the pixel group can descend into a child branch.
	return bPixelGroupStopsHere;
}



// Set our split values to the midpoint between the given
// minimum & maximum.
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>
	::PixelSorterBranchNode::SplitValues (const PixelGroup &a_rMin,
	const PixelGroup &a_rMax)
{
	PIXELINDEX tnX, tnY;
	int nDim;
		// Used to iterate through pixel-groups.

	// Loop through all the pixels & their dimensions, calculate each
	// split value.
	for (tnY = 0; tnY < PGH; ++tnY)
		for (tnX = 0; tnX < PGW; ++tnX)
			for (nDim = 0; nDim < DIM; ++nDim)
				m_oSplitValue.m_atPixels[tnY][tnX][nDim] = PIXEL_NUM
					((PIXEL_TOL (a_rMin.m_atPixels[tnY][tnX][nDim])
					+ PIXEL_TOL (a_rMax.m_atPixels[tnY][tnX][nDim]))
						/ 2);
}



#ifndef NDEBUG

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>
uint32_t
SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,REFERENCEFRAME>
	::PixelSorterBranchNode::sm_ulInstances;

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>
uint32_t
SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,REFERENCEFRAME>
	::GetPixelSorterNodeCount (void)
{
	return PixelSorterBranchNode::GetInstances();
}

#endif // NDEBUG



// Add this search-window cell to the pixel-sorter, creating
// new branch nodes as needed.
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>
typename SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,
	REFERENCEFRAME>::PixelSorterBranchNode *
SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,
	REFERENCEFRAME>::PixelSorter_Add (Status_t &a_reStatus,
	SearchWindowCell *a_pCell, PixelSorterBranchNode *a_pLastSorter,
	int8_t &a_reDoneSorting)
{
	PixelSorterBranchNode *pCurrentBranch;
		// Where we are in the pixel-sorter tree.

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

	// Make sure they gave us a cell to add.
	assert (a_pCell != NULL);

	// Make sure the cell is within the search radius.
	assert (AbsoluteValue (a_pCell->m_tnX - m_tnX)
		<= m_tnSearchRadiusX);
	assert (AbsoluteValue (a_pCell->m_tnY - m_tnY)
		<= m_tnSearchRadiusY);

	// If we know where the cell should go, just put it there and exit.
	if (a_pLastSorter != NULL && a_reDoneSorting)
	{
		a_pLastSorter->m_oSplitValue.InsertAfter
			(&(a_pLastSorter->m_oSplitValue), a_pCell);
		return a_pLastSorter;
	}

	// Initialize our traversal's minimum/maximum to the full range.
	// This will get modified as we move down the tree.
	m_oRangeMin = m_oPixelSorterMin;
	m_oRangeMax = m_oPixelSorterMax;

	// Traverse the tree, figure out where the new search-window cell
	// should be put.  Create new branch nodes as needed.
	pCurrentBranch = ((a_pLastSorter == NULL)
		? &m_oPixelSorter : a_pLastSorter);
	for (;;)
	{
		SORTERBITMASK tnChildIndex;
			// The index of the child branch node that should take the
			// newly-added cell.

		// If this branch node has no cells, just put the new cell here
		// and exit.  (This is almost like balancing the search tree.)
		if (pCurrentBranch->m_oSplitValue.m_pForward
			== &(pCurrentBranch->m_oSplitValue))
		{
			pCurrentBranch->m_oSplitValue.InsertAfter
				(&(pCurrentBranch->m_oSplitValue), a_pCell);
			a_reDoneSorting = SearchWindowCell::m_knDoneEnough;
			return pCurrentBranch;
		}

		// If the cell must stay at this level of the tree, then put
		// the cell at this level & exit.
		if (pCurrentBranch->ShouldCellStayHere (*a_pCell, m_tnTolerance,
			tnChildIndex, m_oRangeMin, m_oRangeMax))
		{
			// Hook this cell up to the branch's cell list.
			pCurrentBranch->m_oSplitValue.InsertAfter
				(&(pCurrentBranch->m_oSplitValue), a_pCell);

			// We're done.
			a_reDoneSorting = SearchWindowCell::m_knDone;
			return pCurrentBranch;
		}

		// The cell should descend into a child branch.  If that child
		// exists, then descend.
		if (pCurrentBranch->m_apBranches[tnChildIndex] != NULL)
		{
			pCurrentBranch = pCurrentBranch->m_apBranches[tnChildIndex];
			continue;
		}

		// Try to create the child branch that the cell should go into.
		pCurrentBranch->m_apBranches[tnChildIndex]
			= new PixelSorterBranchNode;
		if (pCurrentBranch->m_apBranches[tnChildIndex] == NULL)
		{
			// We ran out of memory.  Just put the cell here.
			pCurrentBranch->m_oSplitValue.InsertAfter
				(&(pCurrentBranch->m_oSplitValue), a_pCell);
			a_reDoneSorting = SearchWindowCell::m_knDoneEnough;
			return pCurrentBranch;
		}
		pCurrentBranch = pCurrentBranch->m_apBranches[tnChildIndex];

		// Set its split value to the midpoint between the min/max for
		// this child.
		pCurrentBranch->SplitValues (m_oRangeMin, m_oRangeMax);

		// Put the cell here.
		pCurrentBranch->m_oSplitValue.InsertAfter
			(&(pCurrentBranch->m_oSplitValue), a_pCell);

		// If new branch nodes are created below us, we could go deeper
		// into the tree, but in the interest of tree-balancing, we stop
		// here.  (We don't want to potentially create a new branch node
		// when this cell gets re-inserted; we'll just be happy where we
		// are.)
		a_reDoneSorting = SearchWindowCell::m_knDoneEnough;
		return pCurrentBranch;
	}
}



// Remove this search-window cell from 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>::PixelSorter_Remove (SearchWindowCell *a_pCell)
{
	// Make sure they gave us a cell to remove.
	assert (a_pCell != NULL);

	// Make sure the cell is in the pixel-sorter.
	assert (a_pCell->m_pForward != NULL
		&& a_pCell->m_pForward != a_pCell);

	// Remove the cell from the pixel-sorter.
	a_pCell->Remove();

	// Put it back into a list with itself.  (This marks the cell as
	// having been initialized, saving us from having to do that work
	// again.)
	a_pCell->m_pForward = a_pCell->m_pBackward = a_pCell;
}



// Begin a search through the pixel sorter for the given pixel group.
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>::StartSearch
	(PixelSorterIterator &a_rIterator, const PixelGroup &a_rSearch)
{
	// Remember what cell we're searching for.
	a_rIterator.m_pSearch = &a_rSearch;

	// Start searching at the top of the tree.
	a_rIterator.m_pBranch = &m_oPixelSorter;

	// Remember to search this branch's cells.
	a_rIterator.m_pCell = &(a_rIterator.m_pBranch->m_oSplitValue);
}



// If there is another pixel group that matches the one being
// searched for, returns true and backpatches information on the
// matched pixel group.  If the search is over, returns false.
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>
const typename SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,
	FRAMESIZE,PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,
	REFERENCEFRAME>::PixelGroup *
SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,
	REFERENCEFRAME>::FoundNextMatch
	(PixelSorterIterator &a_rIterator
#ifdef CALCULATE_SAD
									 , Tolerance_t &a_rtnSAD
#endif // CALCULATE_SAD
															) const
{
	SORTERBITMASK tnChildIndex;
		// The index of the branch node child that the search
		// descends down next.

	// Make sure they didn't try to search past the end.
	assert (a_rIterator.m_pBranch != NULL);

	// Loop until we find a match or reach the bottom of the tree.
	for (;;)
	{
		bool bPixelGroupStopsHere;
			// true if we don't have to descend further down the tree.
		bool bMatchesAtThisLevel;
			// true if it's possible for the current pixel-group to
			// match pixel-groups that had to stop at this level in the
			// tree.

		// Move past the last match we found.  (This also works if the
		// branch was just entered, i.e. we're pointing at the branch
		// node's split values.)
		a_rIterator.m_pCell = a_rIterator.m_pCell->m_pForward;

		// See if we should descend the tree, and whether this
		// pixel-group could possibly match any search-window cells that
		// had to stay at this level of the tree.
		bPixelGroupStopsHere = a_rIterator.m_pBranch
			->DoesPixelGroupStopHere (a_rIterator.m_pSearch,
			m_tnTwiceTolerance, tnChildIndex, bMatchesAtThisLevel);

		// Loop through the cells attached to this branch, look for
		// matches, return if we find one.
		while (a_rIterator.m_pCell
			!= &(a_rIterator.m_pBranch->m_oSplitValue))
		{
#ifndef NDEBUG
			// If there are not supposed to be any matches at this
			// level of the search-tree, and the current search-window
			// cell is stuck at this level, then make sure there's no
			// match.
			if (!bMatchesAtThisLevel
				&& a_rIterator.m_pCell->m_eDoneSorting
					== SearchWindowCell::m_knDone)
			{
#ifdef CALCULATE_SAD
				assert (!a_rIterator.m_pCell->IsWithinTolerance
					(*(a_rIterator.m_pSearch), m_tnTolerance,
					a_rtnSAD));
#else // CALCULATE_SAD
				assert (!a_rIterator.m_pCell->IsWithinTolerance
					(*(a_rIte