searchwindow.hh

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

#ifndef __SEARCH_WINDOW_H__
#define __SEARCH_WINDOW_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 "ReferenceFrame.hh"



// Define this to sort pixel-groups only when asked.
//#define OPTIONALLY_SORT_PIXEL_GROUPS



// Define this to calculate and return the sum-of-absolute-differences
// associated with each found match.
//#define CALCULATE_SAD



// The generic search-window 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 width/height of frames,
// the search radius (in the X and Y directions), and the error
// tolerance.
//
// The search-window works on groups of pixels.  It allows the client
// to iterate through a frame and look for pixel-groups within the
// search radius that match a given pixel-group (within the error
// tolerance).
//
// This class was originally an integral part of MotionSearcher, but
// was split out to allow the search-window to be used in other
// contexts, e.g. for the radius search in yuvmedianfilter.
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 SearchWindow
{
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.

	SearchWindow();
		// Default constructor.

	virtual ~SearchWindow();
		// Destructor.

	void Init (Status_t &a_reStatus, PIXELINDEX a_tnWidth,
			PIXELINDEX a_tnHeight, PIXELINDEX a_tnSearchRadiusX,
			PIXELINDEX a_tnSearchRadiusY, PixelValue_t a_nTolerance);
		// Initializer.  Provide the dimensions of the frames, the
		// search radius, and the error tolerance.
	
	void PurgePixelSorter (void);
		// Purge the pixel sorter.
		// Should be called every once in a while (e.g. every 100
		// frames).  Otherwise, it uses up way too much memory and
		// starts hitting virtual memory & otherwise performs bad.
	
	// A pixel group.
	class PixelGroup
	{
	public:
		Pixel_t m_atPixels[PGH][PGW];
			// The pixels we represent.

		PIXELINDEX m_tnX, m_tnY;
			// The index of the upper-left pixel in this pixel-group.

		PixelGroup();
			// Constructor.

		~PixelGroup();
			// Destructor.

		bool IsWithinTolerance (const PixelGroup &a_rOther,
				Tolerance_t a_tnTolerance
#ifdef CALCULATE_SAD
				, Tolerance_t &a_rtnSAD
#endif // CALCULATE_SAD
									   ) const;
			// Returns true if the two pixels groups are equal, within
			// the given tolerance, and backpatches the sum-of-absolute-
			// differences in a_rtnSAD.  a_tnTolerance must have been
			// generated by Pixel_t::MakeTolerance().
	};

	void StartFrame (ReferenceFrame_t *a_pReferenceFrame);
		// Begin searching through a frame.
		// Provide the frame to search through.

	void PrepareForSearch (Status_t &a_reStatus, bool a_bSortPixels);
		// Prepare for searching, i.e. find all search-window cells
		// within the search radius of the current pixel-group that
		// aren't initialized, and do so.
		// If a_bSortPixels is true, then additionally find all
		// search-window cells within the search radius of the current
		// pixel-group that aren't in the pixel-sorter already, and put
		// them there.
		// This must be called before StartSearch()/FoundNextMatch() if
		// any of the Move*() methods have been called.
	
#ifdef OPTIONALLY_SORT_PIXEL_GROUPS

	const SearchWindowCell &GetCell (PIXELINDEX a_tnY,
			PIXELINDEX a_tnX) const;
		// Return the cell at this index.

#endif // OPTIONALLY_SORT_PIXEL_GROUPS

	template <class REGION>
	void Prune (const REGION &a_rAppliedRegion,
			PIXELINDEX a_tnOffsetX, PIXELINDEX a_tnOffsetY);
		// Prune the search-window, i.e. find all pixel-groups that now
		// contain used reference-pixels, and remove them from the
		// window and from the pixel-sorter.

	void MoveRight (void);
		// Move the window one pixel to the right, removing all pixel
		// groups on the left edge of the window.

	void MoveLeft (void);
		// Move the window one pixel to the left, removing all pixel
		// groups on the right edge of the window.

	void MoveDown (void);
		// Move the window down one line, removing all pixel groups on
		// the top edge of the window.

	void FinishFrame (void);
		// Remove all search-window pixel groups from the pixel sorter,
		// leaving it empty & ready for another frame.

	// A class to keep track of our progress during a search inside the
	// pixel sorter.
	class PixelSorterIterator;

	void StartSearch (PixelSorterIterator &a_rIterator,
			const PixelGroup &a_rSearch);
		// Begin a search through the pixel sorter for the given pixel
		// group.

	const PixelGroup *FoundNextMatch
			(PixelSorterIterator &a_rIterator
#ifdef CALCULATE_SAD
			, Tolerance_t &a_rtnSAD
#endif // CALCULATE_SAD
								   ) const;
		// If there is another pixel group that matches the one being
		// searched for, returns the matched pixel group, and
		// backpatches the sum-of-absolute-differences.
		// If the search is over, returns NULL.

#ifndef NDEBUG
	static uint32_t GetPixelSorterNodeCount (void);
		// Return the number of allocated pixel-sorters.
#endif // NDEBUG

private:
	PIXELINDEX m_tnWidth;
	PIXELINDEX m_tnHeight;
		// 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.

	ReferenceFrame_t *m_pReferenceFrame;
		// The reference frame, against which the new frame is
		// compared.
	
	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.
	
	// A pixel group within the search radius of the current
	// pixel group.  Lists of these are attached to pixel-sorter
	// nodes (defined below).
	class PixelSorterBranchNode;
	class SearchWindowCell : public PixelGroup,
		public DoublyLinkedList<SearchWindowCell>
	{
	public:
		PixelSorterBranchNode *m_pSorter;
			// The branch of the pixel-sorter where this cell was
			// placed, the last time it was in the pixel-sorter.

		enum { m_knNotDone = 0, m_knDoneEnough = 1, m_knDone = 2 };
		int8_t m_eDoneSorting;
			// m_knDone if m_pSorter is the lowest node in the tree
			// where this cell could be placed, m_knNotDone if it's
			// possible for this cell to descend further into the tree,
			// m_knDoneEnough if it's possible but not happening.

		SearchWindowCell();
			// Default constructor.

		~SearchWindowCell();
			// Destructor.
	};

	SearchWindowCell **m_ppSearchWindow;
	SearchWindowCell *m_pSearchWindowStorage;
		// The search window.  It contains all the cells needed to
		// analyze the image.
		// m_ppSearchWindow consists of pointers to various areas within
		// m_pSearchWindowStorage; this is done solely to keep the code
		// for accessing cells simpler & easier to understand.

	PIXELINDEX m_tnSearchWindowPixelLeft, m_tnSearchWindowPixelRight,
			m_tnSearchWindowPixelTop, m_tnSearchWindowPixelBottom;
		// The extent of the search window that contains valid values
		// in the pixel-groups.  Generally (m_tnX - m_tnSearchRadiusX)
		// to (m_tnX + m_tnSearchRadiusX), & (m_tnY - m_tnSearchRadiusY)
		// to (m_tnY + m_tnSearchRadiusY), but it gets clipped by the
		// frame boundaries, and, if a run of current pixel-groups
		// contain resolved pixels, will lag until the current
		// pixel-group contains all unresolved pixels.

	PIXELINDEX m_tnSearchWindowSortLeft, m_tnSearchWindowSortRight,
			m_tnSearchWindowSortTop, m_tnSearchWindowSortBottom;
		// The extent of the search window that's been put into the
		// pixel sorter.  Generally (m_tnX - m_tnSearchRadiusX) to
		// (m_tnX + m_tnSearchRadiusX), and (m_tnY - m_tnSearchRadiusY)
		// to (m_tnY + m_tnSearchRadiusY), but it gets clipped by the
		// frame boundaries, and, if a run of current pixel-groups
		// contain resolved pixels, will lag until the current
		// pixel-group contains all unresolved pixels.

	// A branch node in the pixel-sorter tree.  One node partitions
	// search-window cells (i.e. pixel groups within the search radius)
	// into several subtrees, and contains a list of cells that can't be
	// pushed further down the tree.  Used to locate matches for the
	// current pixel group in quasi-logarithmic time.
	class PixelSorterBranchNode
	{
	public:
		SearchWindowCell m_oSplitValue;
			// A cell that contains the split values for each dimension
			// of each pixel of the groups being partitioned.  The
			// contained forward/backward pointers are used to form a
			// list of all real pixel groups (i.e. pixel groups within
			// the search radius) connected to this node.

		enum { m_knBranches = 1 << (PGH * PGW * DIM) };
			// The number of branches from each node.  There's two for
			// each combination of pixel & dimension.

		PixelSorterBranchNode *m_apBranches[m_knBranches];
			// This node's child branches.
			//
			// The bit-mask for the branch that represents a particular
			// pixel-group/pixel-dimension (x,y,dim) is calculated by
			// the formula "1 << (y * (PGW * DIM) + x * DIM + dim)".
			//
			// If the searched-for pixel is greater than its counterpart
			// in the pixel-sorter node, its corresponding bit-mask is
			// added to a running total.  When done, that total is the
			// index of the branch to descend down.  If the searched-for
			// pixel is equal to its counterpart (within the tolerance),
			// the search stops at this level.  It only takes one pixel
			// dimension like this to stop the descent.
			//
			// This way, a search for matches only has to follow one
			// series of branches all the way to the bottom of the tree
			// (i.e. there's no need for a queue of branches to try),
			// and there's no need for an incoming pixel group to end up
			// in more than one branch, no matter what the tolerance.

		PixelSorterBranchNode();
			// Default constructor.

		~PixelSorterBranchNode();
			// Destructor.

		static SORTERBITMASK GetBitMask (PIXELINDEX a_tnY,
				PIXELINDEX a_tnX, int a_nDimension);
			// Calculate the bitmask to represent the given pixel
			// dimension at the given coordinates within the pixel
			// group.

		bool ShouldCellStayHere (const SearchWindowCell &a_rCell,
				Tolerance_t a_tnTolerance,
				SORTERBITMASK &a_rtnChildIndex,
				SearchWindowCell &a_rMin,
				SearchWindowCell &a_rMax) const;
			// If the given cell should stay at this level of the tree
			// (i.e. because one of its pixel values is within the
			// tolerance value of its corresponding split point), then
			// return true.  Otherwise, calculate the index of the
			// child branch that should take this cell, and modify
			// a_rMin and a_rMax (which start as the min/max pixel
			// values for the current branch node) to be the min/max
			// for the child branch node.  (If this function returns
			// true, a_rMin and a_rMax are undefined.)

		bool DoesPixelGroupStopHere (const PixelGroup *a_pPixelGroup,
				Tolerance_t a_tnTwiceTolerance,
				SORTERBITMASK &a_rtnChildIndex,
				bool &a_rbMatchAtThisLevel) const;
			// If the given pixel group straddles this level of the tree
			// (i.e. because one of its pixel values equals its
			// corresponding split point), then return true.
			// Otherwise, calculate the index of the child branch that
			// should take this cell, and return false.
			// In either case, determine whether any search-window cells
			// that had to stop at this level of the tree could possibly
			// intersect the given pixel-group.

		void SplitValues (const PixelGroup &a_rMin,
				const PixelGroup &a_rMax);
			// Set our split values to the midpoint between the given
			// minimum & maximum.

#ifndef NDEBUG

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

	PixelSorterBranchNode m_oPixelSorter;
		// The pixel sorter, i.e. the root of a tree of pixel-sorter
		// branch nodes that partitions all unresolved pixel-groups
		// within the search radius.
	SearchWindowCell m_oPixelSorterMin, m_oPixelSorterMax;
		// The minimum/maximum values for pixels.  Used to help
		// PixelSorter_Add() generate pixel values for new branch nodes.
	SearchWindowCell m_oRangeMin, m_oRangeMax;
		// Cells that contain the minimum/maximum values for pixels
		// at the current level of the pixel-sorter tree.  Used to
		// generate values for new branch nodes.  (These were local
		// variables in PixelSorter_Add(), but the construction &
		// destruction cost actually showed up in the profile!  So
		// they were moved here.)

	PixelSorterBranchNode *PixelSorter_Add (Status_t &a_reStatus,
			SearchWindowCell *a_pCell,
			PixelSorterBranchNode *a_pLastSorter,
			int8_t &a_reDoneSorting);
		// Add this search-window cell to the pixel-sorter, creating
		// new branch nodes as needed.  If this cell has been in the
		// pixel-sorter before, a_pLastSorter is where it was; this
		// avoids duplicated work.
		// Returns the pixel-sorter node where this cell is now
		// attached, and a_reDoneSorting is backpatched with whether the
		// cell could have descended further down the tree, but wasn't
		// for tree-balancing reasons.

	void PixelSorter_Remove (SearchWindowCell *a_pCell);
		// Remove this search-window cell from the pixel-sorter.
		// Does not remove branch nodes; it's assumed that created
		// branch nodes will most likely become useful again at some