searchwindow.hh

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

		++m_tnX;
		return;
	}

	// If the search-window is zero width, we can stop now.
	if (m_tnSearchWindowPixelLeft == m_tnSearchWindowPixelRight)
	{
		++m_tnX;
		return;
	}

	// Make sure that the extent of pixels in the pixel-sorter is
	// consistent with the extent of initialized pixel-groups.
	assert (m_tnSearchWindowSortLeft == m_tnSearchWindowSortRight
		|| m_tnSearchWindowPixelLeft <= m_tnSearchWindowSortLeft);

	// Loop through the left edge of the window, remove all active
	// search-window cells.
	for (tnY = m_tnSearchWindowPixelTop;
		 tnY < m_tnSearchWindowPixelBottom;
		 ++tnY)
	{
		// Get the cell that we may be removing.
		pCell = &(m_ppSearchWindow[tnY][m_tnSearchWindowPixelLeft]);

		// If the cell is in the pixel sorter, remove it.
		if (pCell->m_pForward != NULL
			&& pCell->m_pForward != pCell)
		{
			PixelSorter_Remove (pCell);
		}
	}

	// The search-window now loses its left edge.
	if (m_tnSearchWindowSortLeft != m_tnSearchWindowSortRight
	&& m_tnSearchWindowSortLeft == m_tnSearchWindowPixelLeft)
		++m_tnSearchWindowSortLeft;
	++m_tnSearchWindowPixelLeft;

	// And we're one pixel-group to the right.
	++m_tnX;
}



// Move the window one pixel to the left, removing all pixel
// groups on the right side of the window.
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>::MoveLeft (void)
{
	PIXELINDEX tnY;
		// Used to loop through pixel groups.
	SearchWindowCell *pCell;
		// The search-window cell corresponding to the pixel group being
		// removed from the search-window.

	// If the rightmost edge of the search-window isn't at the edge of
	// the active area, we can stop now.
	if (m_tnX + m_tnSearchRadiusX
			!= m_tnSearchWindowPixelRight - PIXELINDEX (1))
	{
		--m_tnX;
		return;
	}
	
	// If the search-window is zero width, we can stop now.
	if (m_tnSearchWindowPixelLeft == m_tnSearchWindowPixelRight)
	{
		--m_tnX;
		return;
	}

	// Make sure that the extent of pixels in the pixel-sorter is
	// consistent with the extent of initialized pixel-groups.
	assert (m_tnSearchWindowSortRight == m_tnSearchWindowSortLeft
		|| m_tnSearchWindowPixelRight >= m_tnSearchWindowSortRight);

	// The search-window loses its right edge.
	if (m_tnSearchWindowSortRight != m_tnSearchWindowSortLeft
	&& m_tnSearchWindowSortRight == m_tnSearchWindowPixelRight)
		--m_tnSearchWindowSortRight;
	--m_tnSearchWindowPixelRight;

	// Loop through the right edge of the window, remove all active
	// search-window cells.
	for (tnY = m_tnSearchWindowPixelTop;
		 tnY < m_tnSearchWindowPixelBottom;
		 ++tnY)
	{
		// Get the cell that we may be removing.
		pCell = &(m_ppSearchWindow[tnY][m_tnX + m_tnSearchRadiusX]);

		// If the cell is in the pixel sorter, remove it.
		if (pCell->m_pForward != NULL
			&& pCell->m_pForward != pCell)
		{
			PixelSorter_Remove (pCell);
		}
	}

	// And we're one pixel-group to the left.
	--m_tnX;
}



// Move the window down one line, removing all pixel groups on
// the top of the window.
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>::MoveDown (void)
{
	PIXELINDEX tnX;
		// Used to loop through pixel groups.
	SearchWindowCell *pCell;
		// The search-window cell corresponding to the pixel group being
		// removed from the search-window.

	// If the topmost edge of the search-window isn't at the edge of the
	// active area, we can stop now.
	if (m_tnY - m_tnSearchRadiusY != m_tnSearchWindowPixelTop)
	{
		++m_tnY;
		return;
	}

	// If the search-window is zero height, we can stop now.
	if (m_tnSearchWindowPixelTop == m_tnSearchWindowPixelBottom)
	{
		++m_tnY;
		return;
	}

	// Make sure that the extent of pixels in the pixel-sorter is
	// consistent with the extent of initialized pixel-groups.
	assert (m_tnSearchWindowSortTop == m_tnSearchWindowSortBottom
		|| m_tnSearchWindowPixelTop == m_tnSearchWindowSortTop);

	// Loop through the top edge of the window, remove all active
	// search-window cells.
	for (tnX = m_tnSearchWindowPixelLeft;
		 tnX < m_tnSearchWindowPixelRight;
		 ++tnX)
	{
		// Get the cell that we may be removing.
		pCell = &(m_ppSearchWindow[m_tnSearchWindowPixelTop][tnX]);

		// If the cell is in the pixel sorter, remove it.
		if (pCell->m_pForward != NULL
			&& pCell->m_pForward != pCell)
		{
			PixelSorter_Remove (pCell);
		}
	}

	// The search-window loses its top edge.
	if (m_tnSearchWindowSortTop != m_tnSearchWindowSortBottom)
		++m_tnSearchWindowSortTop;
	++m_tnSearchWindowPixelTop;

	// And we're one pixel-group lower.
	++m_tnY;
}



// Remove all search-window pixel groups from the pixel sorter,
// leaving it empty & ready for another frame.
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>::FinishFrame (void)
{
	PIXELINDEX tnX, tnY;
		// Used to loop through pixel groups.

	// Loop through the search-window, invalidate all cells.
	for (tnY = 0; tnY < m_tnHeight - PGH + 1; ++tnY)
	{
		for (tnX = 0; tnX < m_tnWidth - PGW + 1; ++tnX)
		{
			SearchWindowCell *pCell;
				// The search-window cell corresponding to the pixel
				// group being removed from the search-window.

			// Get the cell that we may be removing.
			pCell = &(m_ppSearchWindow[tnY][tnX]);

			// If the cell's pixels are valid, or if it's in the pixel
			// sorter, invalidate it.
			if (pCell->m_pForward != NULL)
			{
				// (Sanity check.)
				assert (pCell->m_pBackward != NULL);
	
				// If this cell is in the pixel-sorter, remove it.
				if (pCell->m_pForward != pCell)
					PixelSorter_Remove (pCell);

				// Invalidate this cell.
				assert (pCell->m_pForward == pCell);
				pCell->Remove();
			}

			// Re-sort it in the next frame.
			pCell->m_pSorter = NULL;
			pCell->m_eDoneSorting = SearchWindowCell::m_knNotDone;
		}
	}

	// The search-window is now empty.
	m_tnSearchWindowPixelLeft = m_tnSearchWindowPixelRight
		= m_tnSearchWindowPixelTop = m_tnSearchWindowPixelBottom
		= m_tnSearchWindowSortLeft = m_tnSearchWindowSortRight
		= m_tnSearchWindowSortTop = m_tnSearchWindowSortBottom
		= PIXELINDEX (0);
	
	// We're done with this frame.  Expect our caller to give us a new
	// one.
	m_pReferenceFrame = 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>
	::PixelSorterBranchNode::PixelSorterBranchNode()
{
#ifndef NDEBUG
	// One more instance.
	++sm_ulInstances;
#endif // NDEBUG

	// The attached search-window-cells form a circular list.  So
	// start the circle.
	m_oSplitValue.m_pForward = m_oSplitValue.m_pBackward
		= &m_oSplitValue;

	// No branches yet.
	for (int i = 0; i < m_knBranches; ++i)
		m_apBranches[i] = NULL;
}



// 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>
	::PixelSorterBranchNode::~PixelSorterBranchNode()
{
#ifndef NDEBUG
	// One less instance.
	--sm_ulInstances;
#endif // NDEBUG

	// Make sure we're the only one in our circular list.
	assert (m_oSplitValue.m_pForward == &m_oSplitValue);

	// Finish off the circular list.
	m_oSplitValue.Remove();

	// Recursively destroy the tree.
	for (int i = 0; i < m_knBranches; ++i)
		delete m_apBranches[i];
}



// Calculate the bitmask to represent the given pixel
// dimension at the given coordinates within the 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>
SORTERBITMASK
SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
	PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,REFERENCEFRAME>
	::PixelSorterBranchNode::GetBitMask (PIXELINDEX a_tnY,
	PIXELINDEX a_tnX, int a_nDimension)
{
	// Make sure the pixel index/dimension are within limits.
	assert (a_tnY >= 0 && a_tnY < PGH);
	assert (a_tnX >= 0 && a_tnX < PGW);
	assert (a_nDimension >= 0 && a_nDimension < DIM);

	// Easy enough.
	return SORTERBITMASK (1)
		<< ((a_tnY * (PGW * DIM) + a_tnX * DIM + a_nDimension));
}



// Determine whether this cell should stay at this level of the tree,
// or calculate the details of the child branch where it should go.
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::ShouldCellStayHere
	(const SearchWindowCell &a_rCell, Tolerance_t a_tnTolerance,
	SORTERBITMASK &a_rtnChildIndex, SearchWindowCell &a_rMin,
	SearchWindowCell &a_rMax) const
{
	PIXELINDEX tnX, tnY;
	int i;
		// Used to loop through pixels & pixel dimensions.

	// Compare the cell's pixel values to our split values, and
	// determine which child branch it should be moved to, or if it
	// should stay at this level.
	a_rtnChildIndex = 0;
	for (tnY = 0; tnY < PGH; ++tnY)
	{
		for (tnX = 0; tnX < PGW; ++tnX)
		{
			// Get the two pixels of interest.
			const Pixel_t &rCellPixel = a_rCell.m_atPixels[tnY][tnX];
			const Pixel_t &rSplitPixel
				= m_oSplitValue.m_atPixels[tnY][tnX];

			// If this pixel value is within the tolerance of
			// the split-point's corresponding pixel, then this
			// cell has to stay at this level of the tree.
			if (DIM == 1
			&& rCellPixel.IsWithinTolerance (rSplitPixel,
				a_tnTolerance))
			{
				return true;
			}

			// 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.
			// Also calculate the min/max for this branch.
			for (i = 0; i < DIM; i++)
			{
				// If this is a multi-dimensional pixel, we have to
				// make sure that none of its axes are within the
				// tolerance either.
				if (DIM > 1)
				{
					// Make copies of the two pixels.
					Pixel_t oCellPixel = rCellPixel;
					Pixel_t oSplitPixel = rSplitPixel;

					// Collapse all dimensions but the current one.
					for (int j = 0; j < DIM; ++j)
						if (j != i)
							oCellPixel[j] = oSplitPixel[j];
					
					// If this axis, all by itself, is within the
					// tolerance, stop here.
					if (oCellPixel.IsWithinTolerance (oSplitPixel,
						a_tnTolerance))
					{
						return true;
					}
				}

				if (rCellPixel[i] > rSplitPixel[i])
				{
					a_rtnChildIndex |= GetBitMask (tnY, tnX, i);
					a_rMin.m_atPixels[tnY][tnX][i]
						= m_oSplitValue.m_atPixels[tnY][tnX][i];
				}
				else
				{
					a_rMax.m_atPixels[tnY][tnX][i]
						= m_oSplitValue.m_atPixels[tnY][tnX][i];
				}
			}
		}