motionsearcher.hh

Motion JPEG编解码器源代码

#ifndef __MOTION_SEARCHER_H__
#define __MOTION_SEARCHER_H__

// This file (C) 2004 Steven Boswell.  All rights reserved.
// Released to the public under the GNU General Public License.
// See the file COPYING for more information.

#include "config.h"
#include <assert.h>
#include "mjpeg_types.h"
#include "TemplateLib.hh"
#include "Limits.hh"
#include "DoublyLinkedList.hh"
#include "ReferenceFrame.hh"
#include "SetRegion2D.hh"
#include "BitmapRegion2D.hh"
#include "SearchBorder.hh"

// HACK: for development error messages.
#include <stdio.h>



// Define this to print region unions/subtractions.
#ifdef DEBUG_REGION2D
//	#define PRINTREGIONMATH
#endif // DEBUG_REGION2D



// Define this to print details of the search-border's progress.
#ifdef DEBUG_REGION2D
//	#define PRINT_SEARCHBORDER
#endif // DEBUG_REGION2D



// Define this to expand existing search-border regions, instead of
// using the pixel-sorter, when there are too many regions in the area
// already.
//#define EXPAND_REGIONS



// Define this to prevent reference-frame pixels from being used more
// than once.
#define USE_REFERENCEFRAMEPIXELS_ONCE



// Define this to throttle the output of the pixel-sorter, using only
// those matches with the lowest sum-of-absolute-differences.
#define THROTTLE_PIXELSORTER_WITH_SAD



// Define this to prune all regions in the area of any flood-filled
// region.
#define PRUNE_FLOODFILL_NEIGHBORS



// Define this to use bitmap regions to implement zero-motion
// flood-fill.
#define ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS



// Define this to use bitmap regions to implement match-throttle
// flood-fill.
//#define MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS



// Define this to use a bitmap region to implement the
// used-reference-pixel region.  Don't define it to use a set-based
// region to implement the used-reference-pixel region.
#define USED_REFERENCE_PIXELS_REGION_IS_BITMAP



// Define this to include the code for using the search-border.
//#define USE_SEARCH_BORDER



// We'll be using this variant of the search-window.
#ifdef EXPAND_REGIONS
	#define OPTIONALLY_SORT_PIXEL_GROUPS
#endif // EXPAND_REGIONS
#ifdef THROTTLE_PIXELSORTER_WITH_SAD
	#define CALCULATE_SAD
#endif // THROTTLE_PIXELSORTER_WITH_SAD
#include "SearchWindow.hh"
#undef CALCULATE_SAD
#undef OPTIONALLY_SORT_PIXEL_GROUPS



// The generic motion-searcher class.  It's parameterized by the size of
// elements in the pixels, the dimension of the pixels, the numeric
// type to use in tolerance calculations, the numeric type to use for
// pixel indices, a numeric type big enough to hold the product of the
// largest expected frame width/height, the width/height of pixel groups
// to operate on, a numeric type big enough to hold
// pixel-dimension * pixel-group-width * pixel-group-height bits and
// serve as an array index, and the types of pixels, reference pixels,
// and reference frames to operate on.
// When constructed, it's configured with the number of frames over
// which to accumulate pixel values, the search radius (in separate x
// and y directions), the error tolerances, and throttle values for the
// number of matches and the size of matches.
//
// Pixel values are tracked over several frames.  The idea is, if the
// motion searcher can prove that a particular pixel in several frames
// is really the same pixel, it can use all the pixel's values to
// calculate a more accurate value for it.  Therefore, output is
// delayed by the number of frames specified in the constructor, to
// give the motion-searcher the slack to do this.
//
// The motion-searcher works on groups of pixels.  It iterates
// through a frame, looking for groups of pixels within the search
// radius that match the current group (within the error tolerance).
// It sorts the found pixel-groups by sum-of-absolute-differences,
// and keeps the best match-count-throttle matches.  Once the search is
// done, it tries to flood-fill each match, and the first match to be
// large enough (i.e.  to be match-size-throttle pixel-groups in size or
// larger) is applied to the image.  Any areas of the frame not resolved
// by this method are new information, and new reference pixels are
// allocated for them.
template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,
	class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,
	class SORTERBITMASK,
	class PIXEL = Pixel<PIXEL_NUM,DIM,PIXEL_TOL>,
	class REFERENCEPIXEL
		= ReferencePixel<PIXEL_TOL,PIXEL_NUM,DIM,PIXEL>,
	class REFERENCEFRAME
		= ReferenceFrame<REFERENCEPIXEL,PIXELINDEX,FRAMESIZE> >
class MotionSearcher
{
public:
	typedef PIXEL Pixel_t;
		// Our pixel type.

	typedef REFERENCEPIXEL ReferencePixel_t;
		// Our reference pixel type.

	typedef REFERENCEFRAME ReferenceFrame_t;
		// Our reference frame type.

	typedef PIXEL_NUM PixelValue_t;
		// The numeric type to use in pixel values, in each dimension
		// of our pixels.

	typedef PIXEL_TOL Tolerance_t;
		// The numeric type to use in tolerance calculations.

	MotionSearcher();
		// Default constructor.

	virtual ~MotionSearcher();
		// Destructor.

	void Init (Status_t &a_reStatus, int a_nFrames,
			PIXELINDEX a_tnWidth, PIXELINDEX a_tnHeight,
			PIXELINDEX a_tnSearchRadiusX, PIXELINDEX a_tnSearchRadiusY,
			PixelValue_t a_nZeroTolerance, PixelValue_t a_nTolerance,
			int a_nMatchCountThrottle, int a_nMatchSizeThrottle);
		// Initializer.  Provide the number of frames over which to
		// accumulate pixel data, the dimensions of the frames, the
		// search radius, the error tolerances, and the match throttles.

	const ReferenceFrame_t *GetFrameReadyForOutput (void);
		// If a frame is ready to be output, return it, otherwise return
		// NULL.
		// Call this once before each call to AddFrame(), to ensure that
		// AddFrame() has the space to accept another frame.  Note that
		// this implies the data in the returned frame will be
		// invalidated by AddFrame().

	void AddFrame (Status_t &a_reStatus, const Pixel_t *a_pPixels);
		// Add another frame to be analyzed into the system.
		// The digested version will eventually be returned by either
		// GetFrameReadyForOutput() or GetRemainingFrames().

	const ReferenceFrame_t *GetRemainingFrames (void);
		// Once there is no more input, call this repeatedly to get the
		// details of the remaining frames, until it returns NULL.
	
	void Purge (void);
		// Purge ourselves of temporary structures.
		// Should be called every once in a while (e.g. every 100
		// frames).

private:
	int m_nFrames;
		// The number of reference frames we use.

	PIXELINDEX m_tnWidth;
	PIXELINDEX m_tnHeight;
	FRAMESIZE m_tnPixels;
		// The dimensions of each reference frame.

	PIXELINDEX m_tnSearchRadiusX, m_tnSearchRadiusY;
		// The search radius, i.e. how far from the current pixel
		// group we look when searching for possible moved instances of
		// the group.

	Tolerance_t m_tnTolerance, m_tnTwiceTolerance;
		// The error tolerance, i.e. the largest difference we're
		// willing to tolerate between pixels before considering them
		// to be different.  Also, twice the tolerance.

	Tolerance_t m_tnZeroTolerance;
		// The error tolerance for the zero-motion pass.

	int m_nMatchCountThrottle;
		// How many matches we're willing to have for the current
		// pixel group before we decide the area is highly patterned
		// and use an alternative algorithm for detecting motion.
		// (The standard algorithm for detecting motion does a bad job
		// with highly patterned areas, using up way too much time and
		// space than would be reasonable.)

	int m_nMatchSizeThrottle;
		// The number of times the size of a pixel-group that the
		// biggest region in the area of the current pixel-group can
		// be before we just flood-fill it and apply it now.

	PixelAllocator<REFERENCEPIXEL,FRAMESIZE> m_oPixelPool;
		// Our source for new reference pixels.

	ReferenceFrame_t **m_ppFrames;
		// Our reference frames; an array of pointers to frames.

	int m_nFirstFrame, m_nLastFrame;
		// The range of frames that contain useful info.
		// When both equal 0, no frames contain useful info.
		// When m_nFirstFrame is 0 and m_nLastFrame is m_nFrames,
		// it's time for GetFrameReadyForOutput() to emit a frame.
		// When m_nFirstFrame is greater than zero but less than
		// m_nLastFrame, it means our client is calling
		// GetRemainingFrames().

	ReferenceFrame_t *m_pNewFrame;
		// The reference-frame representation of the new frame.

	ReferenceFrame_t *m_pReferenceFrame;
		// The reference frame, against which the new frame is
		// compared.
	
	const Pixel_t *m_pNewFramePixels;
		// The pixels of the new frame (i.e. the raw version).
	
	PIXELINDEX m_tnX, m_tnY;
		// The index of the current pixel group.  Actually the index
		// of the top-left pixel in the current pixel group.  This
		// gets moved in a zigzag pattern, back and forth across the
		// frame and then down, until the end of the frame is reached.
	
	PIXELINDEX m_tnStepX;
		// Whether we're zigging or zagging.

	typedef Region2D<PIXELINDEX,FRAMESIZE> BaseRegion_t;
		// The base class for all our region types.

	typedef SetRegion2D<PIXELINDEX,FRAMESIZE> Region_t;
	typedef typename Region_t::Allocator RegionAllocator_t;
		// How we use SetRegion2D<>.

	typedef BitmapRegion2D<PIXELINDEX,FRAMESIZE> BitmapRegion_t;
		// How we use BitmapRegion2D<>.

	typedef SearchBorder<PIXELINDEX,FRAMESIZE> SearchBorder_t;
		// The base class for the type of search-border we'll be using.
	
	typedef typename SearchBorder_t::MovedRegion MovedRegion;
		// A moved region of pixels that has been detected.
	
	RegionAllocator_t m_oRegionAllocator;
		// Used by all our set-regions to allocate their space.

	typedef Set<MovedRegion *,
		typename MovedRegion::SortBySizeThenMotionVectorLength>
		MovedRegionSet;
	MovedRegionSet m_setRegions;
		// All moving areas detected so far.
		// Sorted by decreasing size, then increasing motion vector
		// length, i.e. the order in which they should be applied to
		// the reference-frame version of the new frame.

#ifdef USED_REFERENCE_PIXELS_REGION_IS_BITMAP
	BitmapRegion_t m_oUsedReferencePixels;
#else // USED_REFERENCE_PIXELS_REGION_IS_BITMAP
	Region_t m_oUsedReferencePixels;
#endif // USED_REFERENCE_PIXELS_REGION_IS_BITMAP
		// The region describing all parts of the reference frame that
		// have been found in the new frame, in the zero-motion pass.

	MovedRegion m_oMatchThrottleRegion;
		// The region that's applied to the frame before motion
		// detection is done.  Allocated here to avoid lots of
		// creation & destruction.
	
	void ApplyRegionToNewFrame (Status_t &a_reStatus,
			const MovedRegion &a_rRegion);
		// Apply this region to the new frame.

	typedef SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,
			PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,
			REFERENCEFRAME> SearchWindow_t;
		// The type of search-window we'll be using.
	
	SearchWindow_t m_oSearchWindow;
		// The search window.  It contains all the cells needed to
		// analyze the image.

#ifdef THROTTLE_PIXELSORTER_WITH_SAD

	// A pixel group that matches the current pixel-group, with the
	// given sum-of-absolute-differences.
	class MatchedPixelGroup
	{
	public:
		Tolerance_t m_tnSAD;
			// The sum-of-absolute-differences.
		const typename SearchWindow_t::PixelGroup *m_pGroup;
			// The pixel group.

		MatchedPixelGroup();
			// Default constructor.

		MatchedPixelGroup (Tolerance_t a_tnSAD,
				const typename SearchWindow_t::PixelGroup *a_pGroup);
			// Initializing constructor.

		~MatchedPixelGroup();
			// Destructor.

		// A comparison class, suitable for Set<>.
		class SortBySAD
		{
		public:
			inline bool operator() (const MatchedPixelGroup &a_rLeft,
				const MatchedPixelGroup &a_rRight) const;
		};
	};

	typedef Set<MatchedPixelGroup,
			typename MatchedPixelGroup::SortBySAD>
			MatchedPixelGroupSet;
		// The type for a set of matched pixel-groups.

	MatchedPixelGroupSet m_setMatches;
		// All the matches for the current pixel-group that we
		// want to use.

#endif // THROTTLE_PIXELSORTER_WITH_SAD

#ifdef USE_SEARCH_BORDER

	// The search-border, specialized to put completed regions into
	// m_setRegions.
	class SearchBorder : public SearchBorder_t
	{
	public:
		SearchBorder (MovedRegionSet &a_rsetRegions);
			// Constructor.  Provide a reference to the set where
			// completed regions will be stored.

		virtual void OnCompletedRegion (Status_t &a_reStatus,
				typename SearchBorder::MovedRegion *a_pRegion);
			// Tell SearchBorder_t how to hand us a completed region.
	
	private:
		MovedRegionSet &m_rsetRegions;
			// Our list of completed regions.
	};

	SearchBorder m_oSearchBorder;
		// The search border, i.e. all regions on the border between
		// the searched area and the not-yet-searched area, the regions
		// still under construction.

	FRAMESIZE SearchBorder_FloodFill (Status_t &a_reStatus,
			PIXELINDEX &a_rtnMotionX, PIXELINDEX &a_rtnMotionY);
		// Remove all regions that matched the current pixel-group,
		// except for the best one.  Expand it as far as it can go,
		// i.e. flood-fill in its area.  Then apply it to the new
		// frame now.  Returns the number of points flood-filled.

#endif // USE_SEARCH_BORDER

	// A class that helps implement the zero-motion flood-fill.
	class ZeroMotionFloodFillControl
#ifdef ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS
		: public BitmapRegion_t::FloodFillControl
#else // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS
		: public Region_t::FloodFillControl
#endif // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS
	{
	private:
#ifdef ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS
		typedef typename BitmapRegion_t::FloodFillControl BaseClass;
			// Keep track of who our base class is.
#else // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS
		typedef typename Region_t::FloodFillControl BaseClass;
			// Keep track of who our base class is.
#endif // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

		MotionSearcher *m_pMotionSearcher;
			// The motion-searcher we're working for.

	public:
#ifdef ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS
		ZeroMotionFloodFillControl();
			// Default constructor.  Must be followed by Init().
#else // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS
		ZeroMotionFloodFillControl
				(typename BaseClass::Allocator &a_rAllocator
					= Region_t::Extents::Imp::sm_oNodeAllocator);
			// Partially-initializing constructor.
			// Must be followed by Init().