searchborder.hh

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

		m_paitBorderEndpoints[i] = m_setBorderEndpoints.End();
	}

	// Start in the upper-left corner, and prepare to go right.
	m_tnX = m_tnY = PIXELINDEX (0);
	m_tnStepX = PIXELINDEX (1);
}



// Move one pixel to the right, adding and removing regions from
// the potentially-intersecting list.
template <class PIXELINDEX, class FRAMESIZE>
void
SearchBorder<PIXELINDEX,FRAMESIZE>::MoveRight (Status_t &a_reStatus)
{
	PIXELINDEX tnI;
		// Used to loop through iterators.
	typename IntersectingRegionsSet::Iterator itRemove;
		// An item being removed from the possibly-intersecting set.

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

	// Make sure we knew we were moving right.
	assert (m_tnStepX == 1);

#ifdef PRINT_SEARCHBORDER
	if (frame == 61 && m_setBorderRegions.Size() > 0)
	{
		fprintf (stderr, "Here's what SearchBorder::MoveRight() "
			"starts with (x %d, y %d):\n", int (m_tnX), int (m_tnY));
		for (itRemove = m_setBorderRegions.Begin();
			 itRemove != m_setBorderRegions.End();
			 ++itRemove)
		{
			fprintf (stderr, "\t(%d,%d), motion vector (%d,%d)\n",
				(*itRemove).m_tnIndex, (*itRemove).m_tnLine,
				(*itRemove).m_tnMotionX, (*itRemove).m_tnMotionY);
		}
	}
#endif

	// All active regions with a current-border endpoint at old X, and
	// all active regions with a last-border endpoint at old X + 1, are
	// no longer active.
	for (tnI = ((m_tnY > 0) ? 0 : 1); tnI <= m_tnPGH; ++tnI)
	{
		// Get the endpoint to search along.
		typename BorderExtentBoundarySet::ConstIterator
			&ritEndpoint = m_paitBorderEndpoints[tnI];

		// Make sure it's right where we expect it to be.
		assert (ritEndpoint == m_setBorderEndpoints.End()
			|| (*ritEndpoint).m_tnLine > m_tnY + tnI - PIXELINDEX (1)
			|| ((*ritEndpoint).m_tnLine == m_tnY + tnI - PIXELINDEX (1)
				&& (*ritEndpoint).m_tnIndex
					>= (m_tnX + ((tnI == 0) ? 1 : 0))));

		// Remove all active regions that have endpoints at this index.
		while (ritEndpoint != m_setBorderEndpoints.End()
		&& (*ritEndpoint).m_tnLine == m_tnY + tnI - PIXELINDEX (1)
		&& (*ritEndpoint).m_tnIndex == (m_tnX + ((tnI == 0) ? 1 : 0)))
		{
			// Find the endpoint's corresponding startpoint.
			const BorderExtentBoundary &rHere
				= *((*ritEndpoint).m_pCounterpart);
	
#ifdef PRINT_SEARCHBORDER
			if (frame == 61)
			fprintf (stderr, "Found current-border endpoint, remove "
				"active-border region (%d,%d), "
					"motion vector (%d,%d)\n",
				rHere.m_tnIndex, rHere.m_tnLine,
				rHere.m_tnMotionX, rHere.m_tnMotionY);
#endif
	
			// Now find it & remove it.
			itRemove = m_setBorderRegions.Find (rHere);
			assert (itRemove != m_setBorderRegions.End());
			m_setBorderRegions.Erase (itRemove);
	
			// Move to the next endpoint.
			++ritEndpoint;
		}
	}

	// All active regions with a current-border startpoint at
	// new X + m_tnPGW, and all active regions with a last-border
	// startpoint at new X + m_tnPGW - 1, are now active.
	for (tnI = ((m_tnY > 0) ? 0 : 1); tnI <= m_tnPGH; ++tnI)
	{
		// Get the startpoint to search along.
		typename BorderExtentBoundarySet::ConstIterator
			&ritStartpoint = m_paitBorderStartpoints[tnI];

		// Make sure it's right where we expect it to be.
		assert (ritStartpoint
			== m_setBorderStartpoints.End()
		|| (*ritStartpoint).m_tnLine > m_tnY + tnI - PIXELINDEX (1)
		|| ((*ritStartpoint).m_tnLine == m_tnY + tnI - PIXELINDEX (1)
			&& (*ritStartpoint).m_tnIndex
				>= (m_tnX + m_tnPGW + ((tnI == 0) ? 0 : 1))));

		// Add all active regions that have startpoints at this index.
		while (ritStartpoint != m_setBorderStartpoints.End()
		&& (*ritStartpoint).m_tnLine == m_tnY + tnI - PIXELINDEX (1)
		&& (*ritStartpoint).m_tnIndex
			== (m_tnX + m_tnPGW + ((tnI == 0) ? 0 : 1)))
		{
			const BorderExtentBoundary &rHere = *ritStartpoint;

#ifdef PRINT_SEARCHBORDER
			if (frame == 61)
			{
			fprintf (stderr, "Add active-border region (%d,%d), "
					"motion vector (%d,%d)\n",
				rHere.m_tnIndex, rHere.m_tnLine,
				rHere.m_tnMotionX, rHere.m_tnMotionY);
			}
#endif

#ifndef NDEBUG
			typename IntersectingRegionsSet::InsertResult oInsertResult=
#endif // NDEBUG
				m_setBorderRegions.Insert (a_reStatus, rHere);
			if (a_reStatus != g_kNoError)
				return;
			assert (oInsertResult.m_bInserted);
			
			// Move to the next startpoint.
			++ritStartpoint;
		}
	}

	// Finally, move one step to the right.
	++m_tnX;
}



// Move one pixel to the left, adding and removing regions from
// the potentially-intersecting list.
template <class PIXELINDEX, class FRAMESIZE>
void
SearchBorder<PIXELINDEX,FRAMESIZE>::MoveLeft (Status_t &a_reStatus)
{
	int tnI;
		// Used to loop through iterators.
	typename IntersectingRegionsSet::Iterator itRemove;
		// An item being removed from the possibly-intersecting set.

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

	// Make sure we knew we were moving left.
	assert (m_tnStepX == -1);

#ifdef PRINT_SEARCHBORDER
	if (frame == 61 && m_setBorderRegions.Size() > 0)
	{
		fprintf (stderr, "Here's what SearchBorder::MoveLeft() "
			"starts with (x %d, y %d):\n", int (m_tnX), int (m_tnY));
		for (itRemove = m_setBorderRegions.Begin();
			 itRemove != m_setBorderRegions.End();
			 ++itRemove)
		{
			fprintf (stderr, "\t(%d,%d), motion vector (%d,%d)\n",
				(*itRemove).m_tnIndex, (*itRemove).m_tnLine,
				(*itRemove).m_tnMotionX, (*itRemove).m_tnMotionY);
		}
	}
#endif

	// All active regions with a current-border startpoint at
	// old X + m_tnPGW, and all active regions with a last-border
	// startpoint at old X + m_tnPGW - 1, are no longer active.
	for (tnI = ((m_tnY > 0) ? 0 : 1); tnI <= m_tnPGH; ++tnI)
	{
		// Get the current startpoint.
		typename BorderExtentBoundarySet::ConstIterator &ritBorder
			= m_paitBorderStartpoints[tnI];

#ifndef NDEBUG
		// Make sure it's right where we want to be.
		{
			typename BorderExtentBoundarySet::ConstIterator itPrev
				= ritBorder;
			--itPrev;
			assert (ritBorder == m_setBorderStartpoints.End()
			|| (*ritBorder).m_tnLine > m_tnY + tnI - PIXELINDEX (1)
			|| ((*ritBorder).m_tnLine == m_tnY + tnI - PIXELINDEX (1)
				&& ((*ritBorder).m_tnIndex
						> (m_tnX + m_tnPGW - ((tnI == 0) ? 1 : 0))
					&& (itPrev == m_setBorderStartpoints.End()
						|| (*itPrev).m_tnLine
							< m_tnY + tnI - PIXELINDEX (1)
						|| ((*itPrev).m_tnLine
							== m_tnY + tnI - PIXELINDEX (1)
							&& (*itPrev).m_tnIndex
								<= (m_tnX + m_tnPGW
									- ((tnI == 0) ? 1 : 0)))))));
		}
#endif // NDEBUG

		// Remove all active regions that have startpoints at this
		// index.
		while ((--ritBorder) != m_setBorderStartpoints.End()
		&& (*ritBorder).m_tnLine == m_tnY + tnI - PIXELINDEX (1)
		&& (*ritBorder).m_tnIndex
			== (m_tnX + m_tnPGW - ((tnI == 0) ? 1 : 0)))
		{
			const BorderExtentBoundary &rHere = *ritBorder;
	
#ifdef PRINT_SEARCHBORDER
			if (frame == 61)
			{
			fprintf (stderr, "Found current-border startpoint, remove "
					"active-border region (%d,%d), "
					"motion vector (%d,%d)\n",
				rHere.m_tnIndex, rHere.m_tnLine,
				rHere.m_tnMotionX, rHere.m_tnMotionY);
			}
#endif
	
			itRemove = m_setBorderRegions.Find (rHere);
	
#ifdef PRINT_SEARCHBORDER
			if (frame == 61 && itRemove == m_setBorderRegions.End())
			{
				fprintf (stderr, "NOT FOUND!\n"
					"Here's what was found:\n");
				for (itRemove = m_setBorderRegions.Begin();
					 itRemove != m_setBorderRegions.End();
					 ++itRemove)
				{
					fprintf (stderr, "\t(%d,%d), "
							"motion vector (%d,%d)\n",
						(*itRemove).m_tnIndex, (*itRemove).m_tnLine,
						(*itRemove).m_tnMotionX,
						(*itRemove).m_tnMotionY);
				}
			}
#endif
	
			assert (itRemove != m_setBorderRegions.End());
			m_setBorderRegions.Erase (itRemove);
		}
		++ritBorder;
	}

	// All active regions with a current-border endpoint at new X, and
	// all active regions with a last-border endpoint at new X + 1, are
	// now active.
	for (tnI = ((m_tnY > 0) ? 0 : 1); tnI <= m_tnPGH; ++tnI)
	{
		// Get the current startpoint.
		typename BorderExtentBoundarySet::ConstIterator &ritBorder
			= m_paitBorderEndpoints[tnI];

#ifndef NDEBUG
		// Make sure it's right where we want to be.
		{
			typename BorderExtentBoundarySet::ConstIterator itPrev
				= ritBorder;
			--itPrev;
			assert (ritBorder == m_setBorderEndpoints.End()
			|| (*ritBorder).m_tnLine > m_tnY + tnI - PIXELINDEX (1)
			|| ((*ritBorder).m_tnLine == m_tnY + tnI - PIXELINDEX (1)
			|| ((*ritBorder).m_tnIndex > (m_tnX - ((tnI == 0) ? 0 : 1))
				&& (itPrev == m_setBorderEndpoints.End()
					|| (*itPrev).m_tnLine
						< m_tnY + tnI - PIXELINDEX (1)
					|| ((*itPrev).m_tnLine
						== m_tnY + tnI - PIXELINDEX (1)
						&& (*itPrev).m_tnIndex
							<= (m_tnX - ((tnI == 0) ? 0 : 1)))))));
		}
#endif // NDEBUG

		while ((--ritBorder) != m_setBorderEndpoints.End()
		&& (*ritBorder).m_tnLine == m_tnY + tnI - PIXELINDEX (1)
		&& (*ritBorder).m_tnIndex == (m_tnX - ((tnI == 0) ? 0 : 1)))
		{
			// Find the endpoint's corresponding startpoint.
			assert ((*ritBorder).m_bIsEnding);
			const BorderExtentBoundary &rHere
				= *((*ritBorder).m_pCounterpart);

#ifdef PRINT_SEARCHBORDER
			if (frame == 61)
			fprintf (stderr, "Add active-border region (%d,%d), "
					"motion vector (%d,%d)\n",
				rHere.m_tnIndex, rHere.m_tnLine,
				rHere.m_tnMotionX, rHere.m_tnMotionY);
#endif

			// Now insert it.
#ifndef NDEBUG
			typename IntersectingRegionsSet::InsertResult oInsertResult=
#endif // NDEBUG
				m_setBorderRegions.Insert (a_reStatus, rHere);
			if (a_reStatus != g_kNoError)
				return;

#ifdef PRINT_SEARCHBORDER
		if (frame == 61 && !oInsertResult.m_bInserted)
		{
			fprintf (stderr, "FOUND!\nHere's what was found:\n");
			fprintf (stderr, "\t(%d,%d), motion vector (%d,%d)\n",
				(*oInsertResult.m_itPosition).m_tnIndex,
				(*oInsertResult.m_itPosition).m_tnLine,
				(*oInsertResult.m_itPosition).m_tnMotionX,
				(*oInsertResult.m_itPosition).m_tnMotionY);
			fprintf (stderr, "Here are the active regions:\n");
			for (itRemove = m_setBorderRegions.Begin();
				 itRemove != m_setBorderRegions.End();
				 ++itRemove)
			{
				fprintf (stderr, "\t(%d,%d), motion vector (%d,%d)\n",
					(*itRemove).m_tnIndex, (*itRemove).m_tnLine,
					(*itRemove).m_tnMotionX, (*itRemove).m_tnMotionY);
			}
		}
#endif

			assert (oInsertResult.m_bInserted);
		}
		++ritBorder;
	}

	// Finally, move one step to the left.
	--m_tnX;
}



// Move down a line, finding all regions that can no longer be
// contiguous with new matches, and handing them back to the client.
template <class PIXELINDEX, class FRAMESIZE>
void
SearchBorder<PIXELINDEX,FRAMESIZE>::MoveDown (Status_t &a_reStatus)
{
	typename BorderExtentBoundarySet::Iterator itBorder, itNextBorder;
		// Used to run through the last-border.
	typename IntersectingRegionsSet::Iterator itActive, itNextActive;
		// Used to run through the active-borders set.
	int i;
		// Used to loop through things.

	// Run through the last border, disconnect the regions from all
	// endpoints.  If that leaves a region with no references and no
	// siblings, then the region is fully constructed, and it gets
	// handed back to the client.
	for (i = 0; i < 2; ++i)
	{
		BorderExtentBoundarySet &rBorder
			= ((i == 0) ? m_setBorderStartpoints: m_setBorderEndpoints);

		for (itBorder = rBorder.Begin();
			 itBorder != rBorder.End()
			 	&& (*itBorder).m_tnLine <= m_tnY - 1;
			 itBorder = itNextBorder)
		{
			// Make sure we're actually on the last-border.  (The loop
			// is more permissive than this, so that we can catch
			// errors rather than just get stuck on them.)
			assert ((*itBorder).m_tnLine == m_tnY - 1);

			// Find the next border to examine.
			itNextBorder = itBorder;
			++itNextBorder;

			// Get the endpoint here, and its under-construction region.
			BorderExtentBoundary &rEndpoint = *itBorder;
			RegionUnderConstruction *pRegion = rEndpoint.m_pRegion;

			// That's one less reference to this region.  (Note that, by
			// deliberate coincidence, setting the endpoint's region to
			// NULL won't affect the sort order, so this is safe.)
			rEndpoint.m_pRegion = NULL;
			--pRegion->m_tnReferences;
	
			// Are there any references left to this region?
			if (pRegion->m_tnReferences == 0)
			{
				// Does this region have any siblings?  (A region would
				// get siblings if it got merged with another
				// under-construction region.)
				if (pRegion->m_pForward == pRegion)
				{
					// No.  The region is fully constructed.  Move it to
					// the list of regions that'll get applied to the
					// new frame's reference-image representation.
					pRegion->Remove();	// (no more circular list)
					OnCompletedRegion (a_reStatus, pRegion->m_pRegion);
					if (a_reStatus != g_kNoError)
					{
						delete pRegion->m_pRegion;
						pRegion->m_pRegion = NULL;
						delete pRegion;
						return;
					}
				}
				else
				{
					// Yes.  Just remove ourself as a sibling.
					pRegion->Remove();
				}
	
				// We don't need this under-construction region
				// any more.
				pRegion->m_pRegion = NULL;
				delete pRegion;
			}

			// Finally, remove this startpoint/endpoint.
			rBorder.Erase (itBorder);
		}
	}

	// Run through the active-borders set, remove all references that
	// came from the now-cleared last-border.
	if (m_tnY > 0)