searchborder.hh

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

#ifndef __SEARCH_BORDER_H__
#define __SEARCH_BORDER_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 "SetRegion2D.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



// The generic search-border class.  It's parameterized by the numeric
// type to use for pixel indices and a numeric type big enough to hold
// the product of the largest expected frame width/height.
// When constructed, it's configured with the size of the frame in which
// it operates, and the width/height of pixel groups to operate on.
//
// The search border keeps track of all regions on the border between
// the searched area and the not-yet-searched area.  It also constructs
// regions so that each one is contiguous, and not contiguous with any
// other region.  When no new pixel-group could possibly intersect a
// region, that region is removed from the border and handed back to
// the client.
//
// The meaning of the regions it keeps track of is abstract.  The
// original purpose was to help the motion-searcher keep track of moved
// regions, i.e. pixels in the new frame that match pixels in the
// reference frame, only moved.  But it could presumably be used for
// other purposes, e.g. if it assembled regions of pixels that had
// exactly one frame reference, it could be used to detect bit noise,
// film lint/scratches, or even LaserDisc rot.
//
// As the search-border proceeds through the frame, it maintains a list
// of all regions that intersect with the current pixel-group.  That
// way, when it comes time to add a new match, all regions that
// intersect it are already known.
template <class PIXELINDEX, class FRAMESIZE>
class SearchBorder
{
public:
	typedef SetRegion2D<PIXELINDEX,FRAMESIZE> Region_t;
		// How we use Region2D<>.

	class MovedRegion;
		// A moved region of pixels that has been detected.
		// Derived from Region_t; defined below.

	SearchBorder();
		// Default constructor.

	virtual ~SearchBorder();
		// Destructor.

	void Init (Status_t &a_reStatus, PIXELINDEX a_tnWidth,
			PIXELINDEX a_tnHeight, PIXELINDEX a_tnPGW,
			PIXELINDEX a_tnPGH);
		// Initializer.  Provide the dimension of the frame and the
		// dimension of pixel-groups.

	void StartFrame (Status_t &a_reStatus);
		// Initialize the search-border, i.e. start in the upper-left
		// corner.

	void MoveRight (Status_t &a_reStatus);
		// Move one pixel to the right, adding and removing regions from
		// the potentially-intersecting list.

	void MoveLeft (Status_t &a_reStatus);
		// Move one pixel to the left, adding and removing regions from
		// the potentially-intersecting list.

	void MoveDown (Status_t &a_reStatus);
		// Move down a line.  Find all regions that can no longer
		// be contiguous with new matches, and hand them back to the
		// client.  Then rotate the border structures, making the
		// least-recent current border into the last border, etc.

	inline FRAMESIZE NumberOfActiveRegions (void) const;
		// Return the number of regions that would intersect with the
		// current pixel-group.

	FRAMESIZE AddNewMatch (Status_t &a_reStatus,
			PIXELINDEX a_tnMotionX, PIXELINDEX a_tnMotionY);
		// Accept a new match for a pixel-group, with the given
		// motion-vector.  May cause regions under construction to get
		// merged together.
		// Returns the size of the region containing the current
		// pixel-group.

	MovedRegion *ChooseBestActiveRegion (Status_t &a_reStatus);
		// Remove all regions that matched the current pixel-group,
		// except for the best one, and return it.

	void FinishFrame (Status_t &a_reStatus);
		// Clean up the search border at the end of a frame, e.g. hand
		// all remaining regions back to the client.
	
	virtual void OnCompletedRegion (Status_t &a_reStatus,
			MovedRegion *a_pRegion) = 0;
		// Hand a completed region to our client.  Subclasses must
		// override this to describe how to do this.
	
	// A moved region of pixels that has been detected.
	// All extents are in the coordinate system of the new frame; that
	// makes it easy to unify/subtract regions without regard to their
	// motion vector.
	class MovedRegion : public Region_t
	{
	private:
		typedef Region_t BaseClass;
			// Keep track of who our base class is.

	public:
		MovedRegion (typename BaseClass::Allocator &a_rAlloc
				= BaseClass::Extents::Imp::sm_oNodeAllocator);
			// Default constructor.  Must be followed by Init().

		MovedRegion (Status_t &a_reStatus, typename BaseClass::Allocator
				&a_rAlloc = BaseClass::Extents::Imp::sm_oNodeAllocator);
			// Initializing constructor.  Creates an empty region.

		MovedRegion (Status_t &a_reStatus, const MovedRegion &a_rOther);
			// Copy constructor.

		void Init (Status_t &a_reStatus);
			// Initializer.  Must be called on default-constructed
			// regions.

		void Assign (Status_t &a_reStatus, const MovedRegion &a_rOther);
			// Make the current region a copy of the other region.

		virtual ~MovedRegion();
			// Destructor.

		inline void SetMotionVector (PIXELINDEX a_tnX,
				PIXELINDEX a_tnY);
			// Set the motion vector.

		inline void GetMotionVector (PIXELINDEX &a_rtnX,
				PIXELINDEX &a_rtnY) const;
			// Get the motion vector.

		// Comparison class, suitable for Set<>.
		class SortBySizeThenMotionVectorLength
		{
		public:
			inline bool operator() (const MovedRegion *a_pLeft,
				const MovedRegion *a_pRight) const;
		};

		inline FRAMESIZE GetSquaredMotionVectorLength (void) const;
			// Get the squared length of the motion vector.
			// Needed by SortBySizeThenMotionVectorLength.

	private:
		PIXELINDEX m_tnX, m_tnY;
			// The motion vector associated with this region.

		FRAMESIZE m_tnSquaredLength;
			// The squared length of the motion vector.
			// Used for sorting.
	};

private:
	PIXELINDEX m_tnWidth, m_tnHeight;
		// The dimension of each reference frame.

	PIXELINDEX m_tnPGW, m_tnPGH;
		// The dimension of pixel groups.

	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.

	// A region under construction.  Contains a MovedRegion that's
	// known to be on the border between the searched area and the
	// not-yet-searched area.
	// If two regions being constructed get merged, one is modified to
	// point to the other's contained MovedRegion, and they're put into
	// a doubly-linked-list with each other.
	// When there are no more references to a region, and it has no
	// siblings in the doubly-linked list, that means the region is no
	// longer on the border, and can be handed back to the
	// search-border's client.
	class RegionUnderConstruction
		: public DoublyLinkedList<RegionUnderConstruction>
	{
	public:
		MovedRegion *m_pRegion;
			// The region being constructed.

		FRAMESIZE m_tnReferences;
			// The number of beginnings/endings of extents of this
			// region that are on the border.  When this goes to zero,
			// and we have no siblings in the doubly-linked-list, then
			// that means no other matches could possibly be added to
			// the region, and m_pRegion will get handed back to the
			// search-border's client.

		RegionUnderConstruction();
			// Default constructor.

		~RegionUnderConstruction();
			// Destructor.

	private:
		typedef DoublyLinkedList<RegionUnderConstruction> BaseClass;
			// Keep track of who our base class is.

#ifndef NDEBUG

		// Count the number of region objects in existence.
		private:
			static uint32_t sm_ulInstances;
		public:
			static uint32_t GetInstances (void)
				{ return sm_ulInstances; }
	
#endif // NDEBUG
	};

	// A class that keeps track of region extents on the border between
	// the searched area and the not-yet-searched area, i.e. the only
	// regions that have a chance of growing.
	class BorderExtentBoundary
	{
	public:
		PIXELINDEX m_tnIndex;
			// The index of the endpoint of an extent.

		PIXELINDEX m_tnLine;
			// The vertical line on which this endpoint resides.
			// Used to quickly tell current-border endpoints apart from
			// last-border endpoints, and for no other reason.

		bool m_bIsEnding;
			// false if this is the beginning of an extent, true if
			// it's the end of an extent.

		BorderExtentBoundary *m_pCounterpart;
			// The ending to go with this beginning, or the beginning to
			// go with this ending.

		RegionUnderConstruction *m_pRegion;
			// The region with the given extent.

		PIXELINDEX m_tnMotionX, m_tnMotionY;
			// The region's motion vector.  Copied here so that our sort
			// order doesn't depend on m_pRegion's contents, i.e. so
			// that we thrash memory less.

		BorderExtentBoundary();
			// Default constructor.

		BorderExtentBoundary (PIXELINDEX a_tnIndex, PIXELINDEX a_tnLine,
				bool a_bIsEnding, RegionUnderConstruction *a_pRegion);
			// Initializing constructor.

		~BorderExtentBoundary();
			// Destructor.

#ifndef NDEBUG
		bool operator == (const BorderExtentBoundary &a_rOther) const;
			// Equality operator.
#endif // NDEBUG

		// Comparison class, suitable for Set<>.
		class SortByIndexThenTypeThenMotionVectorThenRegionAddress
		{
		public:
			inline bool operator() (const BorderExtentBoundary &a_rLeft,
				const BorderExtentBoundary &a_rRight) const;
		};

		// Comparison class, suitable for Set<>.
		class SortByMotionVectorThenTypeThenRegionAddress
		{
		public:
			inline bool operator() (const BorderExtentBoundary &a_rLeft,
				const BorderExtentBoundary &a_rRight) const;
		};
	};

	typedef Set<BorderExtentBoundary, typename BorderExtentBoundary
		::SortByIndexThenTypeThenMotionVectorThenRegionAddress>
		BorderExtentBoundarySet;
	BorderExtentBoundarySet m_setBorderStartpoints,
			m_setBorderEndpoints;
		// The borders, i.e. the startpoint/endpoints for every
		// region under construction, for every line in the current
		// pixel-group's vertical extent.
	
	typename BorderExtentBoundarySet::ConstIterator
			*m_paitBorderStartpoints,
			*m_paitBorderEndpoints;
		// The next last/current-border startpoints/endpoints whose
		// regions will be added or removed, when we move left or right.
		// (m_tnPGH + 1 iterators allocated for each.)

	typedef Set<BorderExtentBoundary, typename BorderExtentBoundary
		::SortByMotionVectorThenTypeThenRegionAddress>
		IntersectingRegionsSet;
	IntersectingRegionsSet m_setBorderRegions;
		// All regions that could possibly intersect the current pixel
		// group, should a match be found.  Sorted by motion vector,
		// since matches must be added to a region with the exact same
		// motion vector.  There may be more than one such region; that
		// means the current match causes those regions to be contiguous
		// and thus they will get merged together.
		// (Note that this set is also sorted by type, i.e. whether
		// it's a beginning or end.  We only put beginnings into this
		// set.  This extra sort criteria is used to help us find the
		// range of regions that all have the same motion vector, to let
		// us set up an umambiguous upper-bound for the search.)

#ifndef NDEBUG
public:
	static uint32_t GetRegionUnderConstructionCount (void)
		{ return RegionUnderConstruction::GetInstances(); }
#endif // NDEBUG
};



// Default constructor.
template <class PIXELINDEX, class FRAMESIZE>
SearchBorder<PIXELINDEX,FRAMESIZE>::SearchBorder()
{
	// No frame dimensions yet.
	m_tnWidth = m_tnHeight = PIXELINDEX (0);

	// No active search yet.
	m_tnX = m_tnY = m_tnStepX = PIXELINDEX (0);
}



// Destructor.
template <class PIXELINDEX, class FRAMESIZE>
SearchBorder<PIXELINDEX,FRAMESIZE>::~SearchBorder()
{
	// Make sure our client didn't stop in the middle of a frame.
	assert (m_setBorderStartpoints.Size() == 0);
	assert (m_setBorderEndpoints.Size() == 0);
	assert (m_setBorderRegions.Size() == 0);

	// Free up our arrays of iterators.
	delete[] m_paitBorderStartpoints;
	delete[] m_paitBorderEndpoints;
}



// Initializer.
template <class PIXELINDEX, class FRAMESIZE>
void
SearchBorder<PIXELINDEX,FRAMESIZE>::Init (Status_t &a_reStatus,
	PIXELINDEX a_tnWidth, PIXELINDEX a_tnHeight, PIXELINDEX a_tnPGW,
	PIXELINDEX a_tnPGH)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Make sure the width & height are reasonable.
	assert (a_tnWidth > PIXELINDEX (0));
	assert (a_tnHeight > PIXELINDEX (0));

	// Initialize the sets that implement our border-regions.
	m_setBorderStartpoints.Init (a_reStatus, true);
	if (a_reStatus != g_kNoError)
		return;
	m_setBorderEndpoints.Init (a_reStatus, true);
	if (a_reStatus != g_kNoError)
		return;
	m_setBorderRegions.Init (a_reStatus, false);
	if (a_reStatus != g_kNoError)
		return;

	// Allocate space for our iterators into the startpoint/endpoint
	// sets.  (These move left/right/down with the current pixel-group,
	// and run over regions that get added/removed from the border
	// regions set.)
	m_paitBorderStartpoints = new typename
		BorderExtentBoundarySet::ConstIterator[a_tnPGH + 1];
	m_paitBorderEndpoints = new typename
		BorderExtentBoundarySet::ConstIterator[a_tnPGH + 1];
	if (m_paitBorderStartpoints == NULL
		|| m_paitBorderEndpoints == NULL)
	{
		delete[] m_paitBorderStartpoints;
		delete[] m_paitBorderEndpoints;
		return;
	}

	// Finally, store our parameters.
	m_tnWidth = a_tnWidth;