motionsearcher.hh

Motion JPEG编解码器源代码

	tnNotMovedPixels = tnMovedPixels = tnNotMovedFloodedPixels
		= tnFloodedPixels = tnNoMatchNewPixels = tnNewPixels
		= FRAMESIZE (0);

	// If there is a previous frame, do motion-detection against it.
	if (m_nFirstFrame != m_nLastFrame)
	{
		PIXELINDEX tnLastX, tnLastY;
			// Used to zigzag through the frame.

		// Get the reference frame, i.e. the one that we'll do
		// motion-detection against.  (For now, that's the previous
		// frame.  Eventually, we'd like to do motion-detection against
		// several previous frames, but not yet.)
		m_pReferenceFrame = m_ppFrames[m_nLastFrame - 1];

		// Prepare to search within this frame.
		m_oSearchWindow.StartFrame (m_pReferenceFrame);

		// Start by processing parts of the image that aren't moving.
		// Loop through pixel-group-sized chunks of the image, find
		// pixel-groups within the specified tolerance, and set them up
		// in the new reference frame.  Then flood-fill that region,
		// to catch all the borders.
		m_oUsedReferencePixels.Clear();
#if 1
		// (Search for rows of at least 3 pixels.)
		for (i = y = 0; y < m_tnHeight; ++y)
		{
			typename Region_t::Extent oFoundExtent;
				// Any extent of matching pixels we found.
			bool bStartedExtent;
				// true if we've started finding an extent.

			oFoundExtent.m_tnY = y;
			bStartedExtent = false;
			for (x = 0; x <= m_tnWidth; ++x, ++i)
			{
				bool bPixelMatched;
					// True if the new-frame pixel matches the
					// corresponding reference-frame pixel.
	
				// Sanity check.
				assert (y * m_tnWidth + x == i);

				// If these pixels are within the tolerance, then use
				// the previous frame's value in the new frame.
				bPixelMatched = false;
				if (x < m_tnWidth)
				{
					ReferencePixel_t *pPrevPixel;
						// The pixel from the previous frame.

					// Get the two pixels to compare.
					pPrevPixel = m_pReferenceFrame->GetPixel (i);
					assert (pPrevPixel != NULL);
					const Pixel_t &rPrevPixel = pPrevPixel->GetValue();
					const Pixel_t &rNewPixel = a_pPixels[i];
	
					// Compare them.
					if (rPrevPixel.IsWithinTolerance (rNewPixel,
						m_tnZeroTolerance))
					{
						// Remember it matched.
						bPixelMatched = true;

#if 0
						// HACK
						fprintf (stderr, " (%d,%d)",
							int (i % m_tnWidth),
							int (i / m_tnWidth));
#endif
					}
				}

				// Build a region containing all the used
				// reference-frame pixels.
				if (bPixelMatched)
				{
					// This point is in the region.  Start a new
					// extent if we didn't have one already, and add
					// the point to it.
					if (!bStartedExtent)
					{
						oFoundExtent.m_tnXStart = x;
						bStartedExtent = true;
					}
					oFoundExtent.m_tnXEnd = x + 1;
				}

				// This point is not in the region.  Any extent
				// we're building is done.
				else if (bStartedExtent)
				{
					// Add this extent to the region, but only if it's
					// big enough.
					if (oFoundExtent.m_tnXEnd
						- oFoundExtent.m_tnXStart > 2)
					{
						ReferencePixel_t *pPrevPixel;
							// The pixel from the previous frame.
						PIXELINDEX tnX;
						FRAMESIZE tnI;
	
						for (tnX = oFoundExtent.m_tnXStart;
							 tnX < oFoundExtent.m_tnXEnd;
							 ++tnX)
						{
							// Calculate the pixel index.
							tnI = oFoundExtent.m_tnY * m_tnWidth + tnX;

							// Get the two pixels.
							pPrevPixel = m_pReferenceFrame
								->GetPixel (tnX, oFoundExtent.m_tnY);
							assert (pPrevPixel != NULL);
							const Pixel_t &rNewPixel = a_pPixels[tnI];
		
							// Accumulate the value from the new frame.
							pPrevPixel->AddSample (rNewPixel);
			
							// Store the pixel in the new reference
							// frame.
							m_pNewFrame->SetPixel (tnX,
								oFoundExtent.m_tnY, pPrevPixel);
						}
	
						m_oUsedReferencePixels.Merge (a_reStatus,
							oFoundExtent.m_tnY,
							oFoundExtent.m_tnXStart,
							oFoundExtent.m_tnXEnd);
						if (a_reStatus != g_kNoError)
							return;
			
						// That's more pixels that were found not to
						// have moved.
						tnNotMovedPixels += oFoundExtent.m_tnXEnd
							- oFoundExtent.m_tnXStart;
					}

					// Look for another extent.
					bStartedExtent = false;
				}
			}
			--i;	// (we slightly overshot above)

			// Make sure we finished any extent we started.
			assert (!bStartedExtent);
		}
#else
		// (Search for entire pixel-groups.)
		y = 0;
		for (;;)
		{
			PIXELINDEX tnPixelX, tnPixelY;
				// Used to loop through pixels in the pixel-group.

			x = 0;
			for (;;)
			{
				ReferencePixel_t *pPrevPixel;
					// The pixel from the previous frame.
	
				// Loop through the pixels to compare, see if they all
				// match within the tolerance.
				for (tnPixelY = y;
					 tnPixelY < y + PGH;
					 ++tnPixelY)
				{
					for (tnPixelX = x;
						 tnPixelX < x + PGW;
						 ++tnPixelX)
					{
						// Get the two pixels to compare.
						pPrevPixel = m_pReferenceFrame->GetPixel
							(tnPixelX, tnPixelY);
						assert (pPrevPixel != NULL);
						const Pixel_t &rPrevPixel
							= pPrevPixel->GetValue();
						const Pixel_t &rNewPixel
							= a_pPixels[tnPixelY * m_tnHeight
								+ tnPixelX];
		
						// Compare them.
						if (!rPrevPixel.IsWithinTolerance (rNewPixel,
							m_tnZeroTolerance))
						{
							// No match.
							goto noMatch;
						}
					}
				}

				// These pixels are within the tolerance.  Use the
				// previous frame's value in the new frame.
				for (tnPixelY = y;
					 tnPixelY < y + PGH;
					 ++tnPixelY)
				{
					for (tnPixelX = x;
						 tnPixelX < x + PGW;
						 ++tnPixelX)
					{
						// Get the two pixels.
						pPrevPixel = m_pReferenceFrame->GetPixel
							(tnPixelX, tnPixelY);
						assert (pPrevPixel != NULL);
						const Pixel_t &rNewPixel
							= a_pPixels[tnPixelY * m_tnHeight
								+ tnPixelX];
		
						// Accumulate the value from the new frame.
						pPrevPixel->AddSample (rNewPixel);
		
						// Store the pixel in the new reference
						// frame.
						m_pNewFrame->SetPixel (tnPixelX, tnPixelY,
							pPrevPixel);
					}

#ifdef USE_REFERENCEFRAMEPIXELS_ONCE

					// Add this extent to the region.
					m_oUsedReferencePixels.Union (a_reStatus, tnPixelY,
						x, x + PGW);
					if (a_reStatus != g_kNoError)
						return;

#endif // USE_REFERENCEFRAMEPIXELS_ONCE
				}

				// Remember how many not-moved pixels we found.
				tnNotMovedPixels += PGW * PGH;

noMatch:
				// Now move X forward, but in a way that handles
				// frames whose dimensions are not even multiples of
				// the pixel-group dimension.
				if (x + PGW == m_tnWidth)
					break;
				x += PGW;
				if (x > m_tnWidth - PGW)
					x = m_tnWidth - PGW;
			}

			// Now move Y forward, but in a way that handles
			// frames whose dimensions are not even multiples of
			// the pixel-group dimension.
			if (y + PGH == m_tnHeight)
				break;
			y += PGH;
			if (y > m_tnHeight - PGH)
				y = m_tnHeight - PGH;
		}
#endif

		// All zero-motion pixel-group-sized chunks have been found.
		// Now flood-fill the region, to smoothly resolve all the
		// borders.  (Presently, this will set all the relevant
		// new-frame pixels, which is probably a layering violation.)
		m_oUsedReferencePixels.FloodFill (a_reStatus,
			m_oZeroMotionFloodFillControl, false);
		if (a_reStatus != g_kNoError)
			return;

		// Remember how many not-moved pixels we found.
		tnNotMovedPixels = m_oUsedReferencePixels.NumberOfPoints();

		// Find all search-window cells that contain used reference
		// pixels, and invalidate them.
		m_oSearchWindow.Prune (m_oUsedReferencePixels, PIXELINDEX (0),
			PIXELINDEX (0));

		// Now do the motion-compensated denoising.  Start in the
		// upper-left corner of the frame, and zigzag down the frame
		// (i.e. move all the way right, then down one line, then all
		// the way left, then down one line, etc.).  Look for matches
		// for the current pixel-group in the reference frame, and
		// build regions of such matches.
		//
		// (Skip it if they turned motion-detection off.)
		// (Skip it if the zero-motion case resolved all pixels.)
		if (m_nMatchCountThrottle > 0
		&& tnNotMovedPixels != m_tnPixels)
		{
			m_tnX = m_tnY = 0;
			tnLastX = m_tnWidth - PGW;
			tnLastY = m_tnHeight - PGH;
			m_tnStepX = 1;
#ifdef USE_SEARCH_BORDER
			m_oSearchBorder.StartFrame (a_reStatus);
#endif // USE_SEARCH_BORDER
			if (a_reStatus != g_kNoError)
				return;
			for (;;)
			{
				typename SearchWindow_t::PixelGroup oCurrentGroup;
					// The current pixel-group.
				typename SearchWindow_t::PixelSorterIterator itMatch;
					// Used to search for matches for the current
					// pixel-group.
#ifdef THROTTLE_PIXELSORTER_WITH_SAD
				typename MatchedPixelGroupSet::ConstIterator
						itBestMatch;
					// One of the best matches found.
				Tolerance_t tnSAD;
					// The sum-of-absolute-differences between the
					// current pixel group and the match.
#endif // THROTTLE_PIXELSORTER_WITH_SAD
				const typename SearchWindow_t::PixelGroup *pMatch;
					// A pixel-group that matches the current pixel,
					// within the configured tolerance.
				FRAMESIZE tnMatches;
					// The number of matches found.
				FRAMESIZE tnLargestMatch, tnSmallestMatch;
					// The largest/smallest regions that matched this
					// pixel-group.
	
				// Create the current pixel-group.  If any of its pixels
				// have been resolved, skip it.
				{
					PIXELINDEX x, y;
						// Used to loop through the current
						// pixel-group's pixels.
	
					for (y = 0; y < PGH; ++y)
					{
						for (x = 0; x < PGW; ++x)
						{
							PIXELINDEX tnPixelX, tnPixelY;
								// The index of the current pixel.
		
							// Calculate the index of the current pixel.
							tnPixelX = m_tnX + x;
							tnPixelY = m_tnY + y;
		
							// If this pixel has been resolved already,
							// skip this pixel-group.
							if (m_pNewFrame->GetPixel (tnPixelX,
									tnPixelY) != NULL)
								goto nextGroup;
		
							// Set the pixel value in the pixel-group.
							oCurrentGroup.m_atPixels[y][x]
								= a_pPixels[FRAMESIZE (tnPixelY)
									* FRAMESIZE (m_tnWidth)
									+ FRAMESIZE (tnPixelX)];
						}
					}
				}
	
				// Tell the pixel-group where it is.
				oCurrentGroup.m_tnX = m_tnX;
				oCurrentGroup.m_tnY = m_tnY;
	
#if 0
				// HACK
				fprintf (stderr, "Now checking pixel-group, frame %d, "
					"x %d, y %d", frame, int (m_tnX), int (m_tnY));
#endif
	
				// We have two ways to find matches for the current
				// pixel-group.  If there are few existing matches in
				// the area, search for them in the pixel-sorter tree.
				// If there are enough existing matches, just try to
				// expand those.  When we're through, if there are too
				// many matches in the area, and the region sizes have
				// hit a certain limit, just pick the best one,
				// flood-fill it, and get rid of all the other regions
				// in the area.
				tnMatches = 0;
				tnLargestMatch = 0;
				tnSmallestMatch = Limits<FRAMESIZE>::Max;
	
#ifdef EXPAND_REGIONS
				// If it's OK to just expand the existing regions, do
				// so.  (Estimating that most regions have a
				// current-border presence as well as a last-border
				// presence, we do this when we have match-throttle
				// regions in the area.)
				if (m_setBorderRegions.Size()
					> int ((PGH + 1) * m_nMatchCountThrottle))
				{
					typename IntersectingRegionsSet::ConstIterator
							itHere, itNext;
						// Used to loop through the regions.
	
					// HACK
					//fprintf (stderr, ", expanding existing "
					//	"regions.\n");
	
					// Set up the search-window in a radius around the
					// current pixel-group.  (We don't need the pixel
					// sorter, so don't pay for it.)
					m_oSearchWindow.PrepareForSearch (a_reStatus,
						false);
					if (a_reStatus != g_kNoError)
						return;
		
					// Loop through the ranges of equal motion-vectors,
					// check just that pixel-group, and if it matches,
					// add it to the system.
					for (itHere = m_setBorderRegions.Begin();
						 itHere != m_setBorderRegions.End();
						 itHere = itNext)
					{
						// Find the next motion-vector.
						BorderExtentBoundary oKey = *itHere;
						oKey.m_bIsEnding = true;
						oKey.m_pRegion = NULL;
						itNext = m_setBorderRegions.LowerBound (oKey);
	
#ifndef NDEBUG
						// Sanity check: make sure we got exactly where
						// we expected to.
						assert (itNext == m_setBorderRegions.End()
						|| (*itNext).m_tnMotionX
							!= (*itHere).m_tnMotionX
						|| (*itNext).m_tnMotionY
							!= (*itHere).m_tnMotionY);
						--itNext;
						assert ((*itNext).m_tnMotionX
							== (*itHere).m_tnMotionX
						&& (*itNext).m_tnMotionY