ShiftDetector< A > Struct Template Reference

Estimates the translation of a Gray8 region relative to a background. More...

#include <SimdShift.hpp>

Public Types
enum	TextureType {   TextureGray ,   TextureGrad }
enum	DifferenceType {   AbsDifference ,   SquaredDifference }
typedef A< uint8_t >	Allocator
typedef Simd::View< A >	View
typedef Simd::Point< ptrdiff_t >	Point
typedef Simd::Point< double >	FPoint
typedef Rectangle< ptrdiff_t >	Rect

Public Member Functions
	ShiftDetector ()
	~ShiftDetector ()
void	InitBuffers (const Point &frameSize, size_t levelCount, TextureType textureType=TextureGray, DifferenceType differenceType=AbsDifference)
void	SetBackground (const View &background, bool makeCopy=true)
bool	Estimate (const View &current, const Rect &region, const Point &maxShift, double hiddenAreaPenalty=0, ptrdiff_t regionAreaMin=REGION_CORRELATION_AREA_MIN)
bool	Estimate (const View &current, const Rect &region, int maxShift, double hiddenAreaPenalty=0, ptrdiff_t regionAreaMin=REGION_CORRELATION_AREA_MIN)
Point	Shift () const
FPoint	RefinedShift () const
double	Stability () const
double	Correlation () const

Static Public Attributes
static const ptrdiff_t	REGION_CORRELATION_AREA_MIN = 25

Detailed Description

template<template< class > class A>
struct Simd::ShiftDetector< A >

Estimates the translation of a Gray8 region relative to a background.

ShiftDetector finds the translation that moves a rectangle onto the background window matching a current Gray8 image. The usual type is ShiftDetector<Simd::Allocator>. View is Simd::View<A>, so the background and the current image use that allocator. Point is an integer pixel shift and also the frame size (x is the width, y is the height). FPoint is the sub-pixel shift. Rect is the half-open correlation window [left, right) x [top, bottom).

The structure owns a context created by SimdShiftDetectorInitBuffers and released by SimdRelease. The context keeps a background pyramid and a current pyramid. Each upper level is the 2x reduction of the level below (SimdReduce2x2). levelCount includes the full-resolution level. ShiftDetectorFileSpecialTest uses 4 levels. ShiftDetectorRandSpecialTest uses 6 levels for a 1920x1080 frame.

Call InitBuffers, then SetBackground, then Estimate. Estimate returns false while the context is missing, while the window area is below regionAreaMin, or while the coarse-to-fine search cannot place the window. After a true result, Shift(), RefinedShift(), Stability() and Correlation() read the base pyramid level. The integer shift is the translation from the initial rectangle to the matching background window. The match is region.Shifted(Shift()), so the current image lies at (region.left + shift.x, region.top + shift.y). ShiftDetectorFileSpecialTest loads a Gray8 image, takes the current view from background.Region(region.Shifted(10, 10)) with region = Rect(64, 64, 192, 192), and calls Estimate(current, region, 32). That shift is (10, 10). ShiftDetectorRandSpecialTest builds a 1920x1080 Gray8 frame, places a 256-pixel ring, shrinks the window with AddBorder(-32), and calls Estimate(background.Region(region), region.Shifted(ss), ms * 2) with ms = region.Width() / 4. The first argument is the background crop of the unshifted window. The second argument is that window translated by ss, so the matching translation is -ss.

The initial rectangle lies inside the background: Left() >= 0, Top() >= 0, Right() <= frame width and Bottom() <= frame height. current.Size() equals region.Size(). The search may then move the window. A candidate that leaves more than half of the window outside the frame makes Estimate return false. A smaller hidden part is scored with hiddenAreaPenalty.

TextureGray compares the gray pixels. TextureGrad compares the saturated sum of absolute X and Y gradients from Simd::AbsGradientSaturatedSum (border pixels of that texture are 0). AbsDifference minimizes the mean absolute difference and reports correlation 1 - difference/255. SquaredDifference minimizes the mean squared difference and reports correlation 1 - sqrt(difference)/255. Equal images give correlation 1. The file test keeps the defaults TextureGray and AbsDifference. The random test passes TextureGray and SquaredDifference.

The search starts at the coarsest level whose window area is still at least regionAreaMin. The shift begins at (0, 0), and shift.x and shift.y are doubled on the way to the next finer level. At level i a candidate is limited to max((maxShift >> i) + 1, 2) pixels of that level on each axis. Visiting a candidate outside that limit makes Estimate return false. The coarsest level hill-climbs from (0, 0) for up to that many steps. Each finer level hill-climbs for up to 3 steps around the doubled shift. Estimate returns false when the center is still moving after those steps.

Using example:

#include "Simd/SimdShift.hpp"
#include <iostream>
 
int main()
{
    typedef Simd::ShiftDetector<Simd::Allocator> ShiftDetector;
 
    ShiftDetector::View background;
    background.Load("../../data/image/forest.jpg", ShiftDetector::View::Gray8);
 
    ShiftDetector detector;
    detector.InitBuffers(background.Size(), 4, ShiftDetector::TextureGray, ShiftDetector::AbsDifference);
    detector.SetBackground(background);
 
    ShiftDetector::Rect region(64, 64, 192, 192);
    ShiftDetector::View current = background.Region(region.Shifted(10, 10));
 
    if (detector.Estimate(current, region, 32))
    {
        ShiftDetector::Point shift = detector.Shift();
        ShiftDetector::FPoint refined = detector.RefinedShift();
        std::cout << "Shift = (" << shift.x << ", " << shift.y << "). " << std::endl;
        std::cout << "Refined = (" << refined.x << ", " << refined.y << "). " << std::endl;
        std::cout << "Stability = " << detector.Stability()
            << ", correlation = " << detector.Correlation() << ". " << std::endl;
    }
    else
        std::cout << "Can't find shift for current image!" << std::endl;
 
    return 0;
}

Note

This is a C++ wrapper around SimdShiftDetectorInitBuffers, SimdShiftDetectorSetBackground, SimdShiftDetectorEstimate and SimdShiftDetectorGetShift. The Python class Simd.ShiftingDetector calls those C functions with the same texture, difference, level count, penalty and area arguments.

Member Typedef Documentation

Allocator

typedef A<uint8_t> Allocator

Allocator of the caller's Gray8 views. Simd::Allocator is the type used by the tests.

View

typedef Simd::View<A> View

Gray8 image. SetBackground requires this format. The frame size is View::Size().

Point

typedef Simd::Point<ptrdiff_t> Point

Integer shift (x, y), or a frame size (width, height). Point() is an unset frame size.

FPoint

typedef Simd::Point<double> FPoint

Sub-pixel shift returned by RefinedShift(). TestShift wraps an integer point in this type before SquaredDistance.

Rect

typedef Rectangle<ptrdiff_t> Rect

Half-open correlation window [left, right) x [top, bottom).

Member Enumeration Documentation

TextureType

enum TextureType

Texture stored in the background and current pyramids.

InitBuffers keeps this choice for the life of the context. A different value recreates the context. TextureGray is the default and is the texture used by both special tests. SimdShiftDetectorTextureGray and SimdShiftDetectorTextureGrad are the C API names of these values. The Python enumeration Simd.ShiftDetectorTexture uses Gray and Grad in the same order.

Enumerator
TextureGray	Compare the original Gray8 pixels. SetBackground with makeCopy == false stores a view of the caller's background at pyramid level 0. The file test and the random test both use TextureGray.
TextureGrad	Compare Simd::AbsGradientSaturatedSum of the Gray8 image. For an inner pixel the texture is min(|src[x+1,y] - src[x-1,y]| |src[x,y+1] - src[x,y-1]|, 255). Border pixels are 0. SetBackground always writes this texture into the owned pyramid.

DifferenceType

enum DifferenceType

Difference minimized by Estimate, and the source of Correlation().

The stored difference is the sum of per-pixel differences divided by the area of the compared window. A partly hidden window is then multiplied by the hidden-area factor from Estimate. AbsDifference is the default. The random test passes SquaredDifference. SimdShiftDetectorAbsDifference and SimdShiftDetectorSquaredDifference are the C API names. The Python enumeration Simd.ShiftDetectorDifference uses Abs and Squared in the same order.

Enumerator
AbsDifference	Mean absolute difference. The search uses Simd::AbsDifferenceSum and, for a fully visible 3x3 neighborhood, Simd::AbsDifferenceSums3x3. Correlation() is 1 - difference/255.
SquaredDifference	Mean squared difference. The search uses Simd::SquaredDifferenceSum. ShiftDetectorRandSpecialTest selects this metric. Correlation() is 1 - sqrt(difference)/255.

Constructor & Destructor Documentation

ShiftDetector()

ShiftDetector

(

)

Creates an empty detector.

The texture is TextureGray, the difference is AbsDifference, the level count is 0 and the frame size is Point(). The context is empty, so Estimate returns false until InitBuffers.

~ShiftDetector()

~ShiftDetector

(

)

Releases the shift-detector context.

Calls SimdRelease when InitBuffers has created a context.

Member Function Documentation

InitBuffers()

void InitBuffers	(	const Point &	frameSize,
		size_t	levelCount,
		TextureType	textureType = TextureGray,
		DifferenceType	differenceType = AbsDifference
	)

Creates the pyramids for a background of the given size.

Calls SimdShiftDetectorInitBuffers. The frame size is the background size: x is the width and y is the height, the same point as View::Size(). levelCount is the number of pyramid levels including the full-resolution level. The file test passes background.Size() and 4. The random test passes background.Size(), 6, TextureGray and SquaredDifference.

A second call with the same frame size, level count, texture and difference keeps the existing context and the background already stored in it. Any other combination releases that context and creates a new one. SetBackground is required again after a new context is created.

Parameters

[in]	frameSize	- background size in pixels. x is the width, y is the height.
[in]	levelCount	- number of pyramid levels, including level 0. Each next level is half the size.
[in]	textureType	- texture compared by Estimate. The default is TextureGray.
[in]	differenceType	- difference minimized by Estimate. The default is AbsDifference.

SetBackground()

void SetBackground	(	const View &	background,
		bool	makeCopy = true
	)

Builds the background pyramid from a Gray8 image.

The image size equals the frame size passed to InitBuffers, and background.format is View::Gray8. Both special tests pass the same view that was measured by InitBuffers, with the default copy.

TextureGray and makeCopy == true copy the pixels into pyramid level 0. TextureGray and makeCopy == false make level 0 a view of background.data. That buffer then stays alive and unchanged until the next SetBackground or until the destructor. Upper levels are still owned images. TextureGrad writes Simd::AbsGradientSaturatedSum into the owned level 0. The call then builds the upper levels with Simd::Build and SimdReduce2x2.

Parameters

[in]	background	- Gray8 background of the size passed to InitBuffers.
[in]	makeCopy	- copy a TextureGray background into the context. The default is true.

Estimate() [1/2]

bool Estimate	(	const View &	current,
		const Rect &	region,
		const Point &	maxShift,
		double	hiddenAreaPenalty = 0,
		ptrdiff_t	regionAreaMin = REGION_CORRELATION_AREA_MIN
	)

Estimates the translation of the current image relative to the background.

Calls SimdShiftDetectorEstimate. current is Gray8 and current.Size() equals region.Size(). region is the initial position of that image in background coordinates. The returned shift moves this rectangle onto the match: background.Region(region.Shifted(shift)) is the window that corresponds to current. The file test builds current as background.Region(region.Shifted(10, 10)) and passes the unshifted region, so the integer shift is (10, 10). The random test passes the unshifted crop as current and region.Shifted(ss) as the initial window.

The initial rectangle lies inside the frame. Estimate returns false when the context is missing, when region.Area() is below regionAreaMin, or when the search leaves the per-level shift limit. It also returns false when a candidate keeps less than half of the window inside the frame. A debug build requires the frame size to differ from Point(), which is the state left by the default constructor.

maxShift is the largest absolute translation, in full-resolution pixels, accepted along each axis. At pyramid level i the limit in that level's pixels is max((maxShift >> i) + 1, 2). The file test passes the integer overload, which uses the same limit on both axes. This overload is the one that can give X and Y different limits. The C API receives them as maxShiftX and maxShiftY.

hiddenAreaPenalty weights a window that crosses the frame border. The visible part is the shifted window clipped by the frame and moved back. Its mean difference is multiplied by 1 + (initialArea - visibleArea) * hiddenAreaPenalty / initialArea. The default 0, used by both special tests, leaves the mean difference unchanged. A positive penalty lowers Correlation() because the stored difference includes this factor.

regionAreaMin selects the pyramid levels. The base level and every coarser level whose area is still at least this value take part in the search. The search starts at the coarsest of those levels.

Parameters

[in]	current	- Gray8 image of the same size as region.
[in]	region	- initial half-open window inside the background. The shift is applied to this rectangle.
[in]	maxShift	- maximal absolute shift along X (maxShift.x) and Y (maxShift.y), in full-resolution pixels.
[in]	hiddenAreaPenalty	- extra weight of the hidden fraction of the window. The default is 0.
[in]	regionAreaMin	- minimal window area. The default is REGION_CORRELATION_AREA_MIN (25).

Returns

true when a shift was found. Read Shift(), RefinedShift(), Stability() and Correlation() after a true result.

Estimate() [2/2]

bool Estimate	(	const View &	current,
		const Rect &	region,
		int	maxShift,
		double	hiddenAreaPenalty = 0,
		ptrdiff_t	regionAreaMin = REGION_CORRELATION_AREA_MIN
	)

Estimates the translation with one limit for both axes.

Forwards to Estimate(current, region, Point(maxShift, maxShift), hiddenAreaPenalty, regionAreaMin). ShiftDetectorFileSpecialTest calls Estimate(current, region, 32). ShiftDetectorRandSpecialTest calls Estimate(background.Region(region), region.Shifted(ss), ms * 2), where ms is region.Width() / 4.

Parameters

[in]	current	- Gray8 image of the same size as region.
[in]	region	- initial half-open window inside the background.
[in]	maxShift	- maximal absolute shift along both X and Y, in full-resolution pixels.
[in]	hiddenAreaPenalty	- extra weight of the hidden fraction of the window. The default is 0.
[in]	regionAreaMin	- minimal window area. The default is REGION_CORRELATION_AREA_MIN (25).

Returns

true when a shift was found. Read Shift(), RefinedShift(), Stability() and Correlation() after a true result.

Shift()

Point Shift

(

)

const

Returns the integer shift from the last successful Estimate.

The point is the base-level translation in full-resolution pixels. region.Shifted(Shift()) is the matching background window. The file test prints this point. An empty detector returns Point(). Read this value when Estimate has returned true.

Returns

integer shift (x, y).

RefinedShift()

FPoint RefinedShift

(

)

const

Returns the sub-pixel shift from the last successful Estimate.

The value is the integer shift plus an offset fitted from the 3x3 difference neighborhood of the base level. The fit is a parabola on the averaged rows and columns of that neighborhood. When the minimum touches the border of the searched neighborhood, or a neighbor is missing, the fitted offset is (-1, -1) and Stability() is 0. TestShift wraps an integer point in FPoint and passes RefinedShift() to Simd::SquaredDistance. An empty detector returns FPoint().

Returns

sub-pixel shift (x, y).

Stability()

double Stability

(

)

const

Returns the stability of the shift from the last successful Estimate.

The value is 0 when the best difference sits on the border of the searched neighborhood, when a 3x3 neighbor is missing, or when the fitted sub-pixel offset lies outside [-0.75, 0.75]. Otherwise it is (average of five samples on the far side of the minimum - interpolated minimum) / that average. A value close to 1 is a sharp minimum. An empty detector returns 0.

Returns

stability of the found shift.

Correlation()

double Correlation

(

)

const

Returns the correlation of the best shift from the last successful Estimate.

The correlation is taken from the best average difference at the base level. AbsDifference uses 1 - difference/255. SquaredDifference uses 1 - sqrt(difference)/255. Equal images give

1. hiddenAreaPenalty is included in the stored difference, so a positive penalty on a partly hidden window lowers this value. An empty detector returns 0.

Returns

correlation of the background and the current image.

Field Documentation

REGION_CORRELATION_AREA_MIN

const ptrdiff_t REGION_CORRELATION_AREA_MIN = 25

static

Minimal area of a correlation window, in pixels.

Estimate uses this value when regionAreaMin is omitted. The file test and the random test rely on that default. A window with a smaller area makes Estimate return false. A pyramid level is used only while its window area is still at least this value. The Python wrapper passes 25, the same constant.