~ubuntu-branches/debian/sid/mjpegtools/sid : revision 2

1

#ifndef __MOTION_SEARCHER_H__

2

#define __MOTION_SEARCHER_H__

3

4

5

// Released to the public under the GNU General Public License v2.

6

// See the file COPYING for more information.

7

8

#include "config.h"

9

#include <assert.h>

10

#include "mjpeg_types.h"

11

#include "TemplateLib.hh"

12

#include "Limits.hh"

13

#include "DoublyLinkedList.hh"

14

#include "ReferenceFrame.hh"

15

#include "SetRegion2D.hh"

16

#include "BitmapRegion2D.hh"

17

#include "Vector.hh"

18

19

// HACK: for development error messages.

20

#include <stdio.h>

21

22

23

24

// Define this to print region unions/subtractions.

25

#ifdef DEBUG_REGION2D

26

// #define PRINTREGIONMATH

27

#endif // DEBUG_REGION2D

28

29

30

31

// Define this to print details of the search-border's progress.

32

#ifdef DEBUG_REGION2D

33

// #define PRINT_SEARCHBORDER

34

#endif // DEBUG_REGION2D

35

36

37

38

// Define this to prevent reference-frame pixels from being used more

39

// than once.

40

#define USE_REFERENCEFRAMEPIXELS_ONCE

41

42

43

44

// Define this to throttle the output of the pixel-sorter, using only

45

// those matches with the lowest sum-of-absolute-differences.

46

#define THROTTLE_PIXELSORTER_WITH_SAD

47

48

49

50

// Define this to implement set-regions with vectors.

51

// Don't define this to implement set-regions with skip-lists.

52

#define SET_REGION_IMPLEMENTED_WITH_VECTOR

53

54

55

56

// Define this to implement the SearchBorder's border-extent-boundary-sets

57

// with vectors.

58

// Don't define this to implement the SearchBorder's

59

// border-extent-boundary-sets with skip-lists.

60

//

61

// (Even though this option is specific to the internals of SearchBorder,

62

// it's defined here, since all of our other configuration switches are

63

// here.)

64

#define BORDEREXTENTBOUNDARYSET_IMPLEMENTED_WITH_VECTOR

65

66

67

68

// Define this to use bitmap regions to implement zero-motion

69

// flood-fill.

70

#define ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

71

72

73

74

// Define this to use bitmap regions to implement match-throttle

75

// flood-fill.

76

#define MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

77

78

79

80

// Define this to use bitmap regions to implement pruning flood-fill.

81

//#define PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

82

83

84

85

// Define this to use a bitmap region to implement the

86

// used-reference-pixel region. Don't define it to use a set-based

87

// region to implement the used-reference-pixel region.

88

#define USED_REFERENCE_PIXELS_REGION_IS_BITMAP

89

90

91

92

// We'll be using this variant of the search-border.

93

// (SearchBorder uses SET_REGION_IMPLEMENTED_WITH_VECTOR to configure.)

94

#include "SearchBorder.hh"

95

96

// We'll be using this variant of the search-window.

97

#ifdef EXPAND_REGIONS

98

#define OPTIONALLY_SORT_PIXEL_GROUPS

99

#endif // EXPAND_REGIONS

100

#ifdef THROTTLE_PIXELSORTER_WITH_SAD

101

#define CALCULATE_SAD

102

#endif // THROTTLE_PIXELSORTER_WITH_SAD

103

#include "SearchWindow.hh"

104

#undef CALCULATE_SAD

105

#undef OPTIONALLY_SORT_PIXEL_GROUPS

106

107

108

109

// The generic motion-searcher class. It's parameterized by the size of

110

// elements in the pixels, the dimension of the pixels, the numeric type

111

// to use in tolerance calculations, the numeric type to use for pixel

112

// indices, a numeric type big enough to hold the product of the largest

113

// expected frame width/height, the width/height of pixel groups to

114

// operate on, a numeric type big enough to hold pixel-dimension *

115

// pixel-group-width * pixel-group-height bits and serve as an array

116

// index, and the types of pixels, reference pixels, and reference

117

// frames to operate on. When constructed, it's configured with the

118

// number of frames over which to accumulate pixel values, the search

119

// radius (in separate x and y directions), the error tolerances, and

120

// throttle values for the number of matches and the size of matches.

121

//

122

// Pixel values are tracked over several frames. The idea is, if the

123

// motion searcher can prove that a particular pixel in several frames

124

// is really the same pixel, it can average together all the pixel's

125

// values to calculate a more accurate value for it. Therefore, output

126

// is delayed by the number of frames specified in the constructor, to

127

// give the motion-searcher the slack to do this.

128

//

129

// The motion-searcher works on groups of pixels. It iterates through a

130

// frame, looking for groups of pixels within the search radius that

131

// match the current group (within the error tolerance). It sorts the

132

// found pixel-groups by sum-of-absolute-differences, keeps the best

133

// match-count-throttle matches, and flood-fills each one, storing the

134

// results in the search-border. Future pixel-sorter matches are

135

// checked against this set, to filter out duplicate matches (and the

136

// associated flood-fills).

137

//

138

// Since this process can generate a lot of information, two throttles

139

// are used -- one on the number of matches, and one on the size of the

140

// largest match. If either is exceeded, the largest matches found are

141

// applied to the frame before searching finishes, until neither throttle

142

// is exceeded. This decreases the amount of work to finish the search,

143

// since some of the frame has been resolved already. If the throttle

144

// values are too low, quality may be impacted, but if the throttle

145

// values are too high, performance may be impacted.

146

//

147

// Similarly, if there are no matches for the current pixel-group, then

148

// it is considered new information, and new reference pixels are

149

// allocated for the group and applied to the new frame before the

150

// search is finished. However, these pixels may be overwritten later

151

// by regions that are applied to the frame. This attempts to improve

152

// the efficiency of processing frames that don't match the previous

153

// frame, in a way that doesn't impact quality.

154

//

155

// Once the entire frame has been searched, the found regions are

156

// applied to the frame, from largest match to smallest, and always

157

// flood-filled first to get rid of any resolved pixels. If such a region

158

// is no longer the largest region, it's put back into the pool, and the

159

// largest remaining region is evaluated instead.

160

//

161

// Any areas of the frame not resolved by this method are new

162

// information, and new reference pixels are allocated for them.

163

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

164

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

165

class SORTERBITMASK,

166

class PIXEL = Pixel<PIXEL_NUM,DIM,PIXEL_TOL>,

167

class REFERENCEPIXEL

168

= ReferencePixel<PIXEL_TOL,PIXEL_NUM,DIM,PIXEL>,

169

class REFERENCEFRAME

170

= ReferenceFrame<REFERENCEPIXEL,PIXELINDEX,FRAMESIZE> >

171

class MotionSearcher

172

{

173

public:

174

typedef PIXEL Pixel_t;

175

// Our pixel type.

176

177

typedef REFERENCEPIXEL ReferencePixel_t;

178

// Our reference pixel type.

179

180

typedef REFERENCEFRAME ReferenceFrame_t;

181

// Our reference frame type.

182

183

typedef PIXEL_NUM PixelValue_t;

184

// The numeric type to use in pixel values, in each dimension

185

// of our pixels.

186

187

typedef PIXEL_TOL Tolerance_t;

188

// The numeric type to use in tolerance calculations.

189

190

MotionSearcher();

191

// Default constructor.

192

193

virtual ~MotionSearcher();

194

// Destructor.

195

196

void Init (Status_t &a_reStatus, int a_nFrames,

197

PIXELINDEX a_tnWidth, PIXELINDEX a_tnHeight,

198

PIXELINDEX a_tnSearchRadiusX, PIXELINDEX a_tnSearchRadiusY,

199

PixelValue_t a_nZeroTolerance, PixelValue_t a_nTolerance,

200

FRAMESIZE a_nMatchCountThrottle,

201

FRAMESIZE a_nMatchSizeThrottle);

202

// Initializer. Provide the number of frames over which to

203

// accumulate pixel data, the dimensions of the frames, the

204

// search radius, the error tolerances, and the match throttles.

205

206

const ReferenceFrame_t *GetFrameReadyForOutput (void);

207

// If a frame is ready to be output, return it, otherwise return

208

// NULL.

209

// Call this once before each call to AddFrame(), to ensure that

210

// AddFrame() has the space to accept another frame. Note that

211

// this implies the data in the returned frame will be

212

// invalidated by AddFrame().

213

214

void AddFrame (Status_t &a_reStatus, const Pixel_t *a_pPixels);

215

// Add another frame to be analyzed into the system.

216

// The digested version will eventually be returned by either

217

// GetFrameReadyForOutput() or GetRemainingFrames().

218

219

const ReferenceFrame_t *GetRemainingFrames (void);

220

// Once there is no more input, call this repeatedly to get the

221

// details of the remaining frames, until it returns NULL.

222

223

void Purge (void);

224

// Purge ourselves of temporary structures that aren't normally

225

// freed at the end of a frame. (Most are.)

226

// Should be called every once in a while (e.g. every 10 frames).

227

228

private:

229

int m_nFrames;

230

// The number of reference frames we use.

231

232

PIXELINDEX m_tnWidth;

233

PIXELINDEX m_tnHeight;

234

FRAMESIZE m_tnPixels;

235

// The dimensions of each reference frame.

236

237

PIXELINDEX m_tnSearchRadiusX, m_tnSearchRadiusY;

238

// The search radius, i.e. how far from the current pixel

239

// group we look when searching for possible moved instances of

240

// the group.

241

242

Tolerance_t m_tnTolerance, m_tnTwiceTolerance;

243

// The error tolerance, i.e. the largest difference we're

244

// willing to tolerate between pixels before considering them

245

// to be the same pixel. Also, twice the tolerance.

246

247

Tolerance_t m_tnZeroTolerance;

248

// The error tolerance for the zero-motion pass.

249

250

FRAMESIZE m_nMatchCountThrottle;

251

// How many matches we're willing to have for the current

252

// pixel group before we just flood-fill the largest one and

253

// apply it now.

254

255

FRAMESIZE m_nMatchSizeThrottle;

256

// The size (measured in number of pixels) that the largest

257

// region in the area of the current pixel-group can be before

258

// we just flood-fill the largest one and apply it now.

259

260

PixelAllocator<REFERENCEPIXEL,FRAMESIZE> m_oPixelPool;

261

// Our source for new reference pixels.

262

263

ReferenceFrame_t **m_ppFrames;

264

// Our reference frames; an array of pointers to frames.

265

266

int m_nFirstFrame, m_nLastFrame;

267

// The range of frames that contain useful info.

268

// When both equal 0, no frames contain useful info.

269

// When m_nFirstFrame is 0 and m_nLastFrame is m_nFrames,

270

// it's time for GetFrameReadyForOutput() to emit a frame.

271

// When m_nFirstFrame is greater than zero but less than

272

// m_nLastFrame, it means our client is calling

273

// GetRemainingFrames().

274

275

ReferenceFrame_t *m_pNewFrame;

276

// The reference-frame representation of the new frame.

277

// Points to one of the instances in m_ppFrames[].

278

279

ReferenceFrame_t *m_pReferenceFrame;

280

// The reference frame, against which the new frame is

281

// compared.

282

// Points to one of the instances in m_ppFrames[].

283

284

const Pixel_t *m_pNewFramePixels;

285

// The pixels of the new frame (i.e. the raw version).

286

287

PIXELINDEX m_tnX, m_tnY;

288

// The index of the current pixel group. Actually the index

289

// of the top-left pixel in the current pixel group. This

290

// gets moved in a zigzag pattern, back and forth across the

291

// frame and then down, until the end of the frame is reached.

292

293

PIXELINDEX m_tnStepX;

294

// Whether we're zigging or zagging.

295

296

typedef Region2D<PIXELINDEX,FRAMESIZE> BaseRegion_t;

297

// The base class for all our region types.

298

299

#ifdef SET_REGION_IMPLEMENTED_WITH_VECTOR

300

typedef Vector<typename BaseRegion_t::Extent,

301

typename BaseRegion_t::Extent,

302

Ident<typename BaseRegion_t::Extent,

303

typename BaseRegion_t::Extent>,

304

Less<typename BaseRegion_t::Extent> >

305

RegionImp_t;

306

#else // SET_REGION_IMPLEMENTED_WITH_VECTOR

307

typedef SkipList<typename BaseRegion_t::Extent,

308

typename BaseRegion_t::Extent,

309

Ident<typename BaseRegion_t::Extent,

310

typename BaseRegion_t::Extent>,

311

Less<typename BaseRegion_t::Extent> >

312

RegionImp_t;

313

#endif // SET_REGION_IMPLEMENTED_WITH_VECTOR

314

// The container class that implements our set-based region.

315

316

typedef SetRegion2D<PIXELINDEX,FRAMESIZE,RegionImp_t> Region_t;

317

typedef typename Region_t::Allocator RegionAllocator_t;

318

// How we use SetRegion2D<>.

319

320

typedef BitmapRegion2D<PIXELINDEX,FRAMESIZE> BitmapRegion_t;

321

// How we use BitmapRegion2D<>.

322

323

typedef SearchBorder<PIXELINDEX,FRAMESIZE> BaseSearchBorder_t;

324

// The base class for the type of search-border we'll be using.

325

326

typedef typename BaseSearchBorder_t::MovedRegion MovedRegion;

327

// A moved region of pixels that has been detected.

328

329

RegionAllocator_t m_oRegionAllocator;

330

// Used by all our set-regions to allocate space for their extents.

331

332

typedef Set<MovedRegion *,

333

typename MovedRegion::SortBySizeThenMotionVectorLength>

334

MovedRegionSet;

335

typedef typename MovedRegionSet::Allocator MovedRegionAllocator_t;

336

MovedRegionAllocator_t m_oMovedRegionSetAllocator;

337

MovedRegionSet m_setRegions;

338

// All moving areas detected so far.

339

// Sorted by decreasing size, then increasing motion vector

340

// length, i.e. the order in which they should be applied to

341

// the reference-frame version of the new frame.

342

343

#ifdef USED_REFERENCE_PIXELS_REGION_IS_BITMAP

344

BitmapRegion_t m_oUsedReferencePixels;

345

#else // USED_REFERENCE_PIXELS_REGION_IS_BITMAP

346

Region_t m_oUsedReferencePixels;

347

#endif // USED_REFERENCE_PIXELS_REGION_IS_BITMAP

348

// The region describing all parts of the reference frame that

349

// have been found in the new frame.

350

351

#ifdef USED_REFERENCE_PIXELS_REGION_IS_BITMAP

352

BitmapRegion_t m_oTestedZeroMotionPixels;

353

#else // USED_REFERENCE_PIXELS_REGION_IS_BITMAP

354

Region_t m_oTestedZeroMotionPixels;

355

#endif // USED_REFERENCE_PIXELS_REGION_IS_BITMAP

356

// The region describing all parts of the reference frame that

357

// have been tested in the zero-motion pass.

358

359

MovedRegion m_oMatchThrottleRegion;

360

// The region that's applied to the frame before motion

361

// detection is finished. Allocated here to avoid lots of

362

// creation & destruction.

363

364

#ifdef MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

365

BitmapRegion_t m_oFloodFillRegion;

366

#endif // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

367

// The region that does the flood-filling for the

368

// match-throttle-region.

369

370

void ApplyRegionToNewFrame (Status_t &a_reStatus,

371

const MovedRegion &a_rRegion);

372

// Apply this region to the new frame.

373

374

typedef SearchWindow<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

375

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

376

REFERENCEFRAME> SearchWindow_t;

377

// The type of search-window we'll be using.

378

379

SearchWindow_t m_oSearchWindow;

380

// The search window. It contains all the cells needed to

381

// analyze the image.

382

383

#ifdef THROTTLE_PIXELSORTER_WITH_SAD

384

385

// A pixel group that matches the current pixel-group, with the

386

// given sum-of-absolute-differences.

387

class MatchedPixelGroup

388

{

389

public:

390

Tolerance_t m_tnSAD;

391

// The sum-of-absolute-differences.

392

393

const typename SearchWindow_t::PixelGroup *m_pGroup;

394

// The pixel group.

395

396

MatchedPixelGroup();

397

// Default constructor.

398

399

MatchedPixelGroup (Tolerance_t a_tnSAD,

400

const typename SearchWindow_t::PixelGroup *a_pGroup);

401

// Initializing constructor.

402

403

~MatchedPixelGroup();

404

// Destructor.

405

406

// A comparison class, suitable for Set<>.

407

class SortBySAD

408

{

409

public:

410

inline bool operator() (const MatchedPixelGroup &a_rLeft,

411

const MatchedPixelGroup &a_rRight) const;

412

};

413

};

414

415

typedef Set<MatchedPixelGroup,

416

typename MatchedPixelGroup::SortBySAD>

417

MatchedPixelGroupSet;

418

typedef typename MatchedPixelGroupSet::Allocator MPGS_Allocator_t;

419

// The type for a set of matched pixel-groups.

420

421

MPGS_Allocator_t m_oMatchAllocator;

422

MatchedPixelGroupSet m_setMatches;

423

// All the matches for the current pixel-group that we

424

// want to use.

425

426

#endif // THROTTLE_PIXELSORTER_WITH_SAD

427

428

// The search-border, specialized to put completed regions into

429

// m_setRegions.

430

class SearchBorder_t : public BaseSearchBorder_t

431

{

432

private:

433

typedef BaseSearchBorder_t BaseClass;

434

// Keep track of who our base class is.

435

436

public:

437

SearchBorder_t (MovedRegionSet &a_rsetRegions,

438

typename MovedRegion::Allocator &a_rAlloc

439

= MovedRegion::Extents::Imp::sm_oNodeAllocator);

440

// Constructor. Provide a reference to the set where

441

// completed regions will be stored.

442

443

virtual void OnCompletedRegion (Status_t &a_reStatus,

444

typename SearchBorder_t::MovedRegion *a_pRegion);

445

// Tell BaseSearchBorder_t how to hand us a completed region.

446

447

private:

448

MovedRegionSet &m_rsetRegions;

449

// A reference to our list of completed regions.

450

};

451

452

SearchBorder_t m_oSearchBorder;

453

// The search border, i.e. all regions on the border between

454

// the searched area and the not-yet-searched area, the regions

455

// still under construction.

456

457

FRAMESIZE SearchBorder_AddNewRegion (Status_t &a_reStatus,

458

PIXELINDEX a_tnMotionX, PIXELINDEX a_tnMotionY);

459

// Add a new region, with the given motion vector, to the

460

// search border.

461

// Flood-fills its area before adding.

462

// Returns the size of the added region.

463

464

FRAMESIZE SearchBorder_MatchThrottle (Status_t &a_reStatus,

465

FRAMESIZE a_nMatchCount,

466

PIXELINDEX &a_rtnMotionX, PIXELINDEX &a_rtnMotionY);

467

// Get the best region that matched the current pixel-group

468

// (which is usually the largest active-region). Expand it as far

469

// as it can go, i.e. flood-fill in its area. If it's no longer

470

// the largest region, put it back and try again. Otherwise, apply

471

// it to the new frame now.

472

//

473

// Pass the number of pixel-group matches as an argument. If a

474

// best-region candidate is found to have no unresolved pixels,

475

// it's no longer considered a pixel-group match, and that may lead

476

// to the discovery that the match-count-throttle is no longer

477

// being exceeded.

478

//

479

// Returns the number of points flood-filled, and backpatches the

480

// motion vector associated with the best region.

481

// May return zero if analysis reveals that the match-throttles

482

// weren't really exceeded.

483

484

// A class that helps implement the zero-motion flood-fill.

485

class ZeroMotionFloodFillControl

486

#ifdef ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

487

: public BitmapRegion_t::FloodFillControl

488

#else // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

489

: public Region_t::FloodFillControl

490

#endif // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

491

{

492

private:

493

#ifdef ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

494

typedef typename BitmapRegion_t::FloodFillControl BaseClass;

495

// Keep track of who our base class is.

496

#else // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

497

typedef typename Region_t::FloodFillControl BaseClass;

498

// Keep track of who our base class is.

499

#endif // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

500

501

MotionSearcher *m_pMotionSearcher;

502

// The motion-searcher we're working for.

503

504

public:

505

#ifdef ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

506

ZeroMotionFloodFillControl();

507

#else // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

508

ZeroMotionFloodFillControl

509

(typename BaseClass::Allocator &a_rAllocator

510

= Region_t::Extents::Imp::sm_oNodeAllocator);

511

#endif // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

512

// Default constructor. Must be followed by Init().

513

514

void Init (Status_t &a_reStatus,

515

MotionSearcher *a_pMotionSearcher);

516

// Initializer.

517

518

// Redefined FloodFillControl methods.

519

520

bool ShouldUseExtent (typename

521

ZeroMotionFloodFillControl::BaseClass::Extent &a_rExtent);

522

// Return true if the flood-fill should examine the given

523

// extent. May modify the extent.

524

525

bool IsPointInRegion (PIXELINDEX a_tnX, PIXELINDEX a_tnY);

526

// Returns true if the given point should be included in the

527

// flood-fill.

528

};

529

530

friend class ZeroMotionFloodFillControl;

531

// Allow the zero-motion flood-fill-control class direct access.

532

533

ZeroMotionFloodFillControl m_oZeroMotionFloodFillControl;

534

// Used to implement flood-filling the result of the

535

// zero-motion search.

536

537

// A class that helps implement the match-throttle flood-fill.

538

class MatchThrottleFloodFillControl

539

#ifdef MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

540

: public BitmapRegion_t::FloodFillControl

541

#else // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

542

: public Region_t::FloodFillControl

543

#endif // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

544

{

545

private:

546

#ifdef MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

547

typedef typename BitmapRegion_t::FloodFillControl BaseClass;

548

// Keep track of who our base class is.

549

#else // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

550

typedef typename Region_t::FloodFillControl BaseClass;

551

// Keep track of who our base class is.

552

#endif // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

553

public:

554

#ifdef MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

555

MatchThrottleFloodFillControl();

556

#else // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

557

MatchThrottleFloodFillControl

558

(typename BaseClass::Allocator &a_rAllocator

559

= Region_t::Extents::Imp::sm_oNodeAllocator);

560

#endif // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

561

// Default constructor. Must be followed by Init().

562

563

void Init (Status_t &a_reStatus,

564

MotionSearcher *a_pMotionSearcher);

565

// Initializer.

566

567

void SetupForFloodFill (PIXELINDEX a_tnMotionX,

568

PIXELINDEX a_tnMotionY);

569

// Set up to to a flood-fill. Provide the motion vector.

570

// Call this before doing a flood-fill with this control

571

// object.

572

573

// Redefined FloodFillControl methods.

574

575

bool ShouldUseExtent (typename Region_t::Extent &a_rExtent);

576

// Return true if the flood-fill should examine the given

577

// extent. May modify the extent.

578

579

bool IsPointInRegion (PIXELINDEX a_tnX, PIXELINDEX a_tnY);

580

// Returns true if the given point should be included in the

581

// flood-fill.

582

583

private:

584

MotionSearcher *m_pMotionSearcher;

585

// The motion-searcher we're working for.

586

587

PIXELINDEX m_tnMotionX, m_tnMotionY;

588

// The motion vector to be used for this flood-fill.

589

};

590

591

friend class MatchThrottleFloodFillControl;

592

// Allow the match-throttle flood-fill-control class direct access.

593

594

MatchThrottleFloodFillControl m_oMatchThrottleFloodFillControl;

595

// Used to implement flood-filling a region before

596

// motion-searching is done.

597

598

// A class that helps implement the pruning flood-fill, i.e. the one

599

// that removes resolved pixels from a candidate moved-region.

600

class PruningFloodFillControl

601

#ifdef PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

602

: public BitmapRegion_t::FloodFillControl

603

#else // PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

604

: public Region_t::FloodFillControl

605

#endif // PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

606

{

607

private:

608

#ifdef PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

609

typedef typename BitmapRegion_t::FloodFillControl BaseClass;

610

// Keep track of who our base class is.

611

#else // PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

612

typedef typename Region_t::FloodFillControl BaseClass;

613

// Keep track of who our base class is.

614

#endif // PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

615

public:

616

#ifdef PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

617

PruningFloodFillControl();

618

#else // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

619

PruningFloodFillControl

620

(typename BaseClass::Allocator &a_rAllocator

621

= Region_t::Extents::Imp::sm_oNodeAllocator);

622

#endif // PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

623

// Default constructor. Must be followed by Init().

624

625

void Init (Status_t &a_reStatus,

626

MotionSearcher *a_pMotionSearcher);

627

// Initializer.

628

629

void SetupForFloodFill (PIXELINDEX a_tnMotionX,

630

PIXELINDEX a_tnMotionY);

631

// Set up to to a flood-fill. Provide the motion vector.

632

// Call this before doing a flood-fill with this control

633

// object.

634

635

// Redefined FloodFillControl methods.

636

637

bool ShouldUseExtent (typename Region_t::Extent &a_rExtent);

638

// Return true if the flood-fill should examine the given

639

// extent. May modify the extent.

640

641

bool IsPointInRegion (PIXELINDEX a_tnX, PIXELINDEX a_tnY);

642

// Returns true if the given point should be included in the

643

// flood-fill.

644

645

private:

646

MotionSearcher *m_pMotionSearcher;

647

// The motion-searcher we're working for.

648

649

PIXELINDEX m_tnMotionX, m_tnMotionY;

650

// The motion vector to be used for this flood-fill.

651

};

652

653

friend class PruningFloodFillControl;

654

// Allow the zero-motion flood-fill-control class direct access.

655

656

PruningFloodFillControl m_oPruningFloodFillControl;

657

// Used to implement flood-filling a region to remove any

658

// resolved pixels.

659

};

660

661

662

663

// Default constructor.

664

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

665

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

666

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

667

class REFERENCEFRAME>

668

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

669

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

670

REFERENCEFRAME>::MotionSearcher()

671

: m_oRegionAllocator (1048576),

672

m_oMovedRegionSetAllocator (262144),

673

m_setRegions (typename MovedRegion::SortBySizeThenMotionVectorLength(),

674

m_oMovedRegionSetAllocator),

675

m_oMatchThrottleRegion (m_oRegionAllocator),

676

#ifdef THROTTLE_PIXELSORTER_WITH_SAD

677

m_oMatchAllocator (65536),

678

m_setMatches (typename MatchedPixelGroup::SortBySAD(),

679

m_oMatchAllocator),

680

#endif // THROTTLE_PIXELSORTER_WITH_SAD

681

m_oSearchBorder (m_setRegions, m_oRegionAllocator)

682

#ifndef ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

683

, m_oZeroMotionFloodFillControl (m_oRegionAllocator)

684

#endif // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

685

#ifndef MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

686

, m_oMatchThrottleFloodFillControl (m_oRegionAllocator)

687

#endif // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

688

#ifndef PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

689

, m_oPruningFloodFillControl (m_oRegionAllocator)

690

#endif // PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

691

{

692

// No frames yet.

693

m_nFrames = 0;

694

m_ppFrames = NULL;

695

m_nFirstFrame = m_nLastFrame = 0;

696

m_tnWidth = m_tnHeight = PIXELINDEX (0);

697

m_tnPixels = FRAMESIZE (0);

698

699

// No information on the sort of search to do yet.

700

m_tnSearchRadiusX = m_tnSearchRadiusY = PIXELINDEX (0);

701

m_tnZeroTolerance = m_tnTolerance = m_tnTwiceTolerance

702

= PIXEL_TOL (0);

703

m_nMatchCountThrottle = 0;

704

m_nMatchSizeThrottle = 0;

705

706

// No active search yet.

707

m_tnX = m_tnY = m_tnStepX = PIXELINDEX (0);

708

m_pNewFrame = NULL;

709

m_pReferenceFrame = NULL;

710

m_pNewFramePixels = NULL;

711

}

712

713

714

715

// Destructor.

716

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

717

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

718

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

719

class REFERENCEFRAME>

720

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

721

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

722

REFERENCEFRAME>::~MotionSearcher()

723

{

724

// Free up any remaining moved regions. (Testing for a non-zero

725

// size is defined to be safe even if the set hasn't been

726

// initialized, i.e. if we get destroyed before our Init() has been

727

// called.)

728

if (m_setRegions.Size() > 0)

729

{

730

typename MovedRegionSet::Iterator itHere;

731

// The location of the next region to destroy.

732

733

// Loop through the moved-regions set, remove each item,

734

// destroy it.

735

while (itHere = m_setRegions.Begin(),

736

itHere != m_setRegions.End())

737

{

738

// Get the moved-region to destroy.

739

MovedRegion *pRegion = *itHere;

740

741

// Remove it from the set.

742

m_setRegions.Erase (itHere);

743

744

// Destroy the region.

745

m_oSearchBorder.DeleteRegion (pRegion);

746

}

747

}

748

749

// Destroy the reference frames.

750

for (int i = 0; i < m_nFrames; i++)

751

{

752

m_ppFrames[i]->Reset();

753

delete m_ppFrames[i];

754

}

755

delete[] m_ppFrames;

756

}

757

758

759

760

// Initializer.

761

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

762

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

763

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

764

class REFERENCEFRAME>

765

void

766

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

767

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,REFERENCEFRAME>::Init

768

(Status_t &a_reStatus, int a_nFrames, PIXELINDEX a_tnWidth,

769

PIXELINDEX a_tnHeight, PIXELINDEX a_tnSearchRadiusX,

770

PIXELINDEX a_tnSearchRadiusY, PixelValue_t a_tnZeroTolerance,

771

PixelValue_t a_tnTolerance, FRAMESIZE a_nMatchCountThrottle,

772

FRAMESIZE a_nMatchSizeThrottle)

773

{

774

int i;

775

// Used to loop through things.

776

FRAMESIZE tnPixels;

777

// The number of pixels in each frame.

778

779

// Make sure they didn't start us off with an error.

780

assert (a_reStatus == g_kNoError);

781

782

// Make sure they gave us a reasonable number of frames.

783

// (We need at least one for the new frame and one to

784

// compare against the new frame. We prefer more.)

785

assert (a_nFrames >= 2);

786

787

// Make sure the width & height are reasonable.

788

assert (a_tnWidth > PIXELINDEX (0));

789

assert (a_tnHeight > PIXELINDEX (0));

790

791

// Make sure the search radius is reasonable.

792

assert (a_tnSearchRadiusX > PIXELINDEX (0)

793

&& a_tnSearchRadiusY > PIXELINDEX (0)

794

&& a_tnSearchRadiusX <= a_tnWidth

795

&& a_tnSearchRadiusY <= a_tnHeight);

796

797

// Make sure the match throttles are reasonable.

798

assert (a_nMatchCountThrottle >= 0

799

&& a_nMatchCountThrottle

800

<= a_tnSearchRadiusX * a_tnSearchRadiusY);

801

assert (a_nMatchSizeThrottle > 0);

802

803

// Calculate the number of pixels in each frame.

804

tnPixels = FRAMESIZE (a_tnWidth) * FRAMESIZE (a_tnHeight);

805

806

// Initialize our pixel pool.

807

m_oPixelPool.Initialize (a_reStatus, tnPixels * FRAMESIZE (a_nFrames));

808

if (a_reStatus != g_kNoError)

809

return;

810

811

// Allocate space for our pointers to frames.

812

m_ppFrames = new ReferenceFrame_t * [a_nFrames];

813

if (m_ppFrames == NULL)

814

{

815

a_reStatus = g_kOutOfMemory;

816

return;

817

}

818

// (Initialize each one to NULL, in case we run out of memory while

819

// trying to allocate frames -- if we don't do this, we'll end up

820

// trying to delete garbage pointers.)

821

for (i = 0; i < a_nFrames; ++i)

822

m_ppFrames[i] = NULL;

823

// (Save this parameter now, to make it possible to destroy an

824

// incompletely-initialized object.)

825

m_nFrames = a_nFrames;

826

827

// Allocate our reference frames.

828

for (i = 0; i < a_nFrames; ++i)

829

{

830

// Allocate the next reference frame.

831

m_ppFrames[i] = new ReferenceFrame_t (a_reStatus, a_tnWidth,

832

a_tnHeight);

833

if (m_ppFrames[i] == NULL)

834

{

835

a_reStatus = g_kOutOfMemory;

836

return;

837

}

838

if (a_reStatus != g_kNoError)

839

return;

840

}

841

842

// Initialize the search-window.

843

m_oSearchWindow.Init (a_reStatus, a_tnWidth, a_tnHeight,

844

a_tnSearchRadiusX, a_tnSearchRadiusY, a_tnTolerance);

845

if (a_reStatus != g_kNoError)

846

return;

847

848

// Initialize our set of matches. (We'll use this to sort the

849

// incoming matches by how closely it matches the current

850

// pixel-group, and we'll throw away fuzzier matches.)

851

#ifdef THROTTLE_PIXELSORTER_WITH_SAD

852

typename MatchedPixelGroupSet::InitParams oInitSetMatches (rand(),

853

true /* allocate internal nodes from allocator */);

854

m_setMatches.Init (a_reStatus, true, oInitSetMatches);

855

if (a_reStatus != g_kNoError)

856

return;

857

#endif // THROTTLE_PIXELSORTER_WITH_SAD

858

859

// Initialize our moved-regions set.

860

m_setRegions.Init (a_reStatus, true);

861

if (a_reStatus != g_kNoError)

862

return;

863

864

// Initialize the moved-region extents allocator.

865

#ifdef SET_REGION_IMPLEMENTED_WITH_VECTOR

866

m_oRegionAllocator.Init (a_reStatus);

867

if (a_reStatus != g_kNoError)

868

return;

869

#endif // SET_REGION_IMPLEMENTED_WITH_VECTOR

870

871

// Initialize our used reference-pixels container.

872

#ifdef USED_REFERENCE_PIXELS_REGION_IS_BITMAP

873

m_oUsedReferencePixels.Init (a_reStatus, a_tnWidth, a_tnHeight);

874

#else // USED_REFERENCE_PIXELS_REGION_IS_BITMAP

875

m_oUsedReferencePixels.Init (a_reStatus, m_oRegionAllocator);

876

#endif // USED_REFERENCE_PIXELS_REGION_IS_BITMAP

877

if (a_reStatus != g_kNoError)

878

return;

879

#if defined (USED_REFERENCE_PIXELS_REGION_IS_BITMAP)

880

#if defined (DEBUG_REGION2D)

881

// HACK: too expensive, test region class elsewhere.

882

m_oUsedReferencePixels.SetDebug (false);

883

#endif // DEBUG_REGION2D

884

#endif // USED_REFERENCE_PIXELS_REGION_IS_BITMAP

885

886

// Initialize our tested zero-motion-pixels container.

887

#ifdef USED_REFERENCE_PIXELS_REGION_IS_BITMAP

888

m_oTestedZeroMotionPixels.Init (a_reStatus, a_tnWidth, a_tnHeight);

889

#else // USED_REFERENCE_PIXELS_REGION_IS_BITMAP

890

m_oTestedZeroMotionPixels.Init (a_reStatus, m_oRegionAllocator);

891

#endif // USED_REFERENCE_PIXELS_REGION_IS_BITMAP

892

if (a_reStatus != g_kNoError)

893

return;

894

#if defined (USED_REFERENCE_PIXELS_REGION_IS_BITMAP)

895

#if defined (DEBUG_REGION2D)

896

// HACK: too expensive, test region class elsewhere.

897

m_oTestedZeroMotionPixels.SetDebug (false);

898

#endif // DEBUG_REGION2D

899

#endif // USED_REFERENCE_PIXELS_REGION_IS_BITMAP

900

901

// Initialize our match-throttle region.

902

m_oMatchThrottleRegion.Init (a_reStatus);

903

if (a_reStatus != g_kNoError)

904

return;

905

906

// Initialize the region that does the flood-filling for the

907

// match-throttle-region.

908

#ifdef MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

909

m_oFloodFillRegion.Init (a_reStatus, a_tnWidth, a_tnHeight);

910

if (a_reStatus != g_kNoError)

911

return;

912

#if defined (DEBUG_REGION2D)

913

// HACK: too expensive, test region class elsewhere.

914

m_oFloodFillRegion.SetDebug (false);

915

#endif // DEBUG_REGION2D

916

#endif // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

917

918

// Initialize the search-border.

919

// Note that the search-border is not given the value of

920

// the externally-set match-size-throttle. That was done

921

// back when throttling happened at the end of a pixel-group

922

// search if any of the resulting regions exceeded the

923

// match-size-throttle. Now, those large regions are kept

924

// in the search-border until all the new conditions for

925

// throttling are met.

926

m_oSearchBorder.Init (a_reStatus, a_tnWidth, a_tnHeight,

927

a_tnSearchRadiusX, a_tnSearchRadiusY, PGW, PGH,

928

/* a_nMatchSizeThrottle */ a_tnWidth * a_tnHeight);

929

if (a_reStatus != g_kNoError)

930

return;

931

932

// Finally, store our parameters. (Convert the tolerance value to

933

// the format used internally.)

934

//m_nFrames = a_nFrames; (Stored above)

935

m_tnWidth = a_tnWidth;

936

m_tnHeight = a_tnHeight;

937

m_tnPixels = tnPixels;

938

m_tnSearchRadiusX = a_tnSearchRadiusX;

939

m_tnSearchRadiusY = a_tnSearchRadiusY;

940

m_tnZeroTolerance = Pixel_t::MakeTolerance (a_tnZeroTolerance);

941

m_tnTolerance = Pixel_t::MakeTolerance (a_tnTolerance);

942

m_tnTwiceTolerance = Pixel_t::MakeTolerance (PixelValue_t (2)

943

* a_tnTolerance);

944

m_nMatchCountThrottle = a_nMatchCountThrottle;

945

m_nMatchSizeThrottle = a_nMatchSizeThrottle;

946

947

// Initialize our flood-fill controllers. (This happens after we

948

// store our parameters, because these methods may need those

949

// values.)

950

m_oZeroMotionFloodFillControl.Init (a_reStatus, this);

951

if (a_reStatus != g_kNoError)

952

return;

953

m_oMatchThrottleFloodFillControl.Init (a_reStatus, this);

954

if (a_reStatus != g_kNoError)

955

return;

956

m_oPruningFloodFillControl.Init (a_reStatus, this);

957

if (a_reStatus != g_kNoError)

958

return;

959

}

960

961

962

963

// If a frame is ready to be output, return it, otherwise return

964

// NULL.

965

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

966

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

967

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

968

class REFERENCEFRAME>

969

const typename MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,

970

FRAMESIZE, PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

971

REFERENCEFRAME>::ReferenceFrame_t *

972

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

973

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

974

REFERENCEFRAME>::GetFrameReadyForOutput (void)

975

{

976

ReferenceFrame_t *pFrame;

977

// The frame to return to the caller.

978

int i;

979

// Used to loop through things.

980

981

// If we have space for the new frame in our reference frames, then

982

// it's not time to emit a frame yet. (We delay emitting frames for

983

// as long as possible, in order to calculate the most accurate

984

// pixel values.)

985

if (m_nFirstFrame != 0 || m_nLastFrame != m_nFrames)

986

return NULL;

987

988

// Get the frame to return to the caller.

989

pFrame = m_ppFrames[0];

990

991

// Shift the remaining frames down.

992

for (i = 1; i < m_nFrames; ++i)

993

m_ppFrames[i - 1] = m_ppFrames[i];

994

995

// Our caller will read the data in the frame. By the time the

996

// caller calls AddFrame(), we'll need to use this frame again.

997

// So put it at the end of the list.

998

--m_nLastFrame;

999

m_ppFrames[m_nLastFrame] = pFrame;

1000

1001

// Finally, return the frame to our caller.

1002

return pFrame;

1003

}

1004

1005

1006

1007

// HACK: developer debugging output.

1008

extern "C" { extern int frame, verbose; };

1009

1010

// Add another frame to be analyzed into the system.

1011

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

1012

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

1013

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

1014

class REFERENCEFRAME>

1015

void

1016

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

1017

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,REFERENCEFRAME>::AddFrame

1018

(Status_t &a_reStatus, const Pixel_t *a_pPixels)

1019

{

1020

FRAMESIZE i;

1021

// Used to loop through pixels.

1022

FRAMESIZE tnNotMovedZeroMotionPixels, tnNotMovedThrottledPixels,

1023

tnNotMovedPixels, tnMovedThrottledPixels, tnMovedPixels,

1024

tnNoMatchNewPixels, tnNewPixels;

1025

// Statistics on the result of our analysis -- the number of

1026

// pixels that didn't move, the number that moved, the number

1027

// found by flood-filling, and the number of new pixels.

1028

1029

// Make sure they didn't start us off with an error.

1030

assert (a_reStatus == g_kNoError);

1031

1032

// Make sure we can accept a new frame.

1033

assert (m_nFirstFrame == 0 && m_nLastFrame < m_nFrames);

1034

1035

// Get the reference frame that will become the new frame.

1036

m_pNewFrame = m_ppFrames[m_nLastFrame];

1037

m_pNewFramePixels = a_pPixels;

1038

1039

// Reset the new frame, so that it doesn't refer to any pixels.

1040

// (This frame was previously returned by GetFrameReadyForOutput(),

1041

// so it wasn't safe to reset it until now.)

1042

m_pNewFrame->Reset();

1043

1044

// Reset our statistics.

1045

tnNotMovedZeroMotionPixels = tnNotMovedThrottledPixels

1046

= tnNotMovedPixels = tnMovedThrottledPixels = tnMovedPixels

1047

= tnNoMatchNewPixels = tnNewPixels = FRAMESIZE (0);

1048

1049

// If there is a previous frame, do motion-detection against it.

1050

if (m_nFirstFrame != m_nLastFrame)

1051

{

1052

PIXELINDEX tnLastX, tnLastY;

1053

// Used to zigzag through the frame.

1054

1055

// Get the reference frame, i.e. the one that we'll do

1056

// motion-detection against. (For now, that's the previous

1057

// frame. Eventually, we'd like to do motion-detection against

1058

// several previous frames, but not yet.)

1059

m_pReferenceFrame = m_ppFrames[m_nLastFrame - 1];

1060

1061

// Prepare to search within this frame.

1062

m_oSearchWindow.StartFrame (m_pReferenceFrame);

1063

m_oSearchBorder.StartFrame (a_reStatus);

1064

if (a_reStatus != g_kNoError)

1065

return;

1066

1067

// Start by processing parts of the image that aren't moving.

1068

// Loop through pixel-group-sized chunks of the image, find

1069

// pixel-groups within the specified tolerance, and flood-fill

1070

// them. If the resulting region exceeds the match-size-throttle,

1071

// apply it now. Either way, remember the region that was found

1072

// (so that the region doesn't have to be found again).

1073

//

1074

// Skip if they specified a zero for the tolerance.

1075

m_oUsedReferencePixels.Clear();

1076

m_oTestedZeroMotionPixels.Clear();

1077

if (m_tnZeroTolerance != 0)

1078

{

1079

m_tnY = 0;

1080

for (;;)

1081

{

1082

PIXELINDEX tnPixelX, tnPixelY;

1083

// Used to loop through pixels in the pixel-group.

1084

1085

m_tnX = 0;

1086

for (;;)

1087

{

1088

ReferencePixel_t *pPrevPixel;

1089

// The pixel from the previous frame.

1090

#ifdef ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

1091

typename BitmapRegion_t::ConstIterator itExtent;

1092

#endif // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

1093

// Used to convert between region types.

1094

1095

// Loop through the pixels to compare, see if they all

1096

// match within the tolerance.

1097

for (tnPixelY = m_tnY;

1098

tnPixelY < m_tnY + PGH;

1099

++tnPixelY)

1100

{

1101

for (tnPixelX = m_tnX;

1102

tnPixelX < m_tnX + PGW;

1103

++tnPixelX)

1104

{

1105

// If a pixel in this pixel-group has already

1106

// been tested in this pass, skip it.

1107

if (m_oTestedZeroMotionPixels.DoesContainPoint

1108

(tnPixelY, tnPixelX))

1109

goto noMatch;

1110

1111

// Get the two pixels to compare.

1112

pPrevPixel = m_pReferenceFrame->GetPixel

1113

(tnPixelX, tnPixelY);

1114

assert (pPrevPixel != NULL);

1115

const Pixel_t &rPrevPixel

1116

= pPrevPixel->GetValue();

1117

const Pixel_t &rNewPixel

1118

= a_pPixels[tnPixelY * m_tnWidth

1119

+ tnPixelX];

1120

1121

// Compare them.

1122

if (!rPrevPixel.IsWithinTolerance (rNewPixel,

1123

m_tnZeroTolerance))

1124

{

1125

// No match.

1126

goto noMatch;

1127

}

1128

}

1129

}

1130

1131

// These pixels are within the zero-motion tolerance.

1132

// Set up a region describing the current pixel-group.

1133

#ifdef ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

1134

m_oFloodFillRegion.Clear();

1135

for (tnPixelY = m_tnY;

1136

tnPixelY < m_tnY + PGH;

1137

++tnPixelY)

1138

{

1139

m_oFloodFillRegion.Merge (a_reStatus, tnPixelY,

1140

m_tnX, m_tnX + PGW);

1141

if (a_reStatus != g_kNoError)

1142

return;

1143

}

1144

#else // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

1145

m_oMatchThrottleRegion.Clear();

1146

for (tnPixelY = m_tnY;

1147

tnPixelY < m_tnY + PGH;

1148

++tnPixelY)

1149

{

1150

m_oMatchThrottleRegion.Merge (a_reStatus, tnPixelY,

1151

m_tnX, m_tnX + PGW);

1152

if (a_reStatus != g_kNoError)

1153

return;

1154

}

1155

#endif // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

1156

1157

// Set its motion vector.

1158

m_oMatchThrottleRegion.SetMotionVector (0, 0);

1159

1160

// Set its location. (Needed only for debugging

1161

// purposes.)

1162

#ifndef NDEBUG

1163

m_oMatchThrottleRegion.m_tnX = m_tnX;

1164

m_oMatchThrottleRegion.m_tnY = m_tnY;

1165

#endif // !NDEBUG

1166

1167

// Flood-fill this match, so as to get its full extent.

1168

#ifdef ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

1169

m_oFloodFillRegion.FloodFill (a_reStatus,

1170

m_oZeroMotionFloodFillControl, false, true);

1171

#else // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

1172

m_oMatchThrottleRegion.FloodFill (a_reStatus,

1173

m_oZeroMotionFloodFillControl, false, true);

1174

#endif // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

1175

if (a_reStatus != g_kNoError)

1176

return;

1177

1178

// Now copy the results of the flood-fill to the

1179

// match-throttle region.

1180

#ifdef ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

1181

m_oMatchThrottleRegion.Clear();

1182

for (itExtent = m_oFloodFillRegion.Begin();

1183

itExtent != m_oFloodFillRegion.End();

1184

++itExtent)

1185

{

1186

// Get the current extent.

1187

const typename BitmapRegion_t::Extent &rExtent

1188

= *itExtent;

1189

1190

// Copy it to the match-throttle region.

1191

m_oMatchThrottleRegion.Union

1192

(a_reStatus, rExtent.m_tnY,

1193

rExtent.m_tnXStart, rExtent.m_tnXEnd);

1194

if (a_reStatus != g_kNoError)

1195

return;

1196

}

1197

#endif // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

1198

1199

// All of these reference pixels have been tested.

1200

// There's no need to test them again.

1201

{

1202

typename MovedRegion::ConstIterator itExtent;

1203

for (itExtent = m_oMatchThrottleRegion.Begin();

1204

itExtent != m_oMatchThrottleRegion.End();

1205

++itExtent)

1206

{

1207

// Get the current extent.

1208

const typename MovedRegion::Extent &rExtent

1209

= *itExtent;

1210

1211

// Add it to our running total of tested

1212

// zero-motion reference-pixels.

1213

m_oTestedZeroMotionPixels.Union

1214

(a_reStatus, rExtent.m_tnY,

1215

rExtent.m_tnXStart, rExtent.m_tnXEnd);

1216

if (a_reStatus != g_kNoError)

1217

return;

1218

}

1219

}

1220

1221

// If this match is larger than the

1222

// match-size-throttle, apply it now.

1223

if (m_oMatchThrottleRegion.NumberOfPoints()

1224

>= m_nMatchSizeThrottle)

1225

{

1226

// Apply this region to the new frame.

1227

ApplyRegionToNewFrame (a_reStatus,

1228

m_oMatchThrottleRegion);

1229

if (a_reStatus != g_kNoError)

1230

return;

1231

1232

// That's more resolved pixels.

1233

tnNotMovedZeroMotionPixels

1234

+= m_oMatchThrottleRegion.NumberOfPoints();

1235

1236

// Clean up after ourselves.

1237

m_oMatchThrottleRegion.Clear();

1238

}

1239

1240

// Otherwise, just dispose of it.

1241

// m_oTestedZeroMotionPixels will prevent us from

1242

// finding it again.

1243

else

1244

m_oMatchThrottleRegion.Clear();

1245

1246

noMatch:

1247

// Now move X forward, but in a way that handles

1248

// frames whose dimensions are not even multiples of

1249

// the pixel-group dimension.

1250

if (m_tnX + PGW == m_tnWidth)

1251

break;

1252

m_tnX += PGW;

1253

if (m_tnX > m_tnWidth - PGW)

1254

m_tnX = m_tnWidth - PGW;

1255

}

1256

1257

// Now move Y forward, but in a way that handles

1258

// frames whose dimensions are not even multiples of

1259

// the pixel-group dimension.

1260

if (m_tnY + PGH == m_tnHeight)

1261

break;

1262

m_tnY += PGH;

1263

if (m_tnY > m_tnHeight - PGH)

1264

m_tnY = m_tnHeight - PGH;

1265

}

1266

1267

// Clean up after ourselves.

1268

m_oTestedZeroMotionPixels.Clear();

1269

}

1270

1271

// Now do the motion-compensated denoising. Start in the

1272

// upper-left corner of the frame, and zigzag down the frame

1273

// (i.e. move all the way right, then down one line, then all

1274

// the way left, then down one line, etc.). Look for matches

1275

// for the current pixel-group in the reference frame, and

1276

// build regions of such matches.

1277

//

1278

// (Skip it if they turned motion-detection off.)

1279

if (m_tnTolerance > 0)

1280

{

1281

// Start searching in the upper-left corner, and prepare to

1282

// move right.

1283

m_tnX = m_tnY = 0;

1284

tnLastX = m_tnWidth - PGW;

1285

tnLastY = m_tnHeight - PGH;

1286

m_tnStepX = 1;

1287

1288

// Loop until the entire frame has been searched.

1289

for (;;)

1290

{

1291

typename SearchWindow_t::PixelGroup oCurrentGroup;

1292

// The current pixel-group.

1293

typename SearchWindow_t::PixelSorterIterator itMatch;

1294

// Used to search for matches for the current

1295

// pixel-group.

1296

#ifdef THROTTLE_PIXELSORTER_WITH_SAD

1297

typename MatchedPixelGroupSet::ConstIterator

1298

itBestMatch;

1299

// One of the best matches found.

1300

Tolerance_t tnSAD;

1301

// The sum-of-absolute-differences between the

1302

// current pixel group and the match.

1303

#endif // THROTTLE_PIXELSORTER_WITH_SAD

1304

const typename SearchWindow_t::PixelGroup *pMatch;

1305

// A pixel-group that matches the current pixel,

1306

// within the configured tolerance.

1307

FRAMESIZE tnMatches;

1308

// The number of matches found.

1309

1310

// Create the current pixel-group. If any of its pixels

1311

// have been resolved, skip it.

1312

{

1313

PIXELINDEX x, y;

1314

// Used to loop through the current

1315

// pixel-group's pixels.

1316

1317

for (y = 0; y < PGH; ++y)

1318

{

1319

for (x = 0; x < PGW; ++x)

1320

{

1321

PIXELINDEX tnPixelX, tnPixelY;

1322

// The index of the current pixel.

1323

1324

// Calculate the index of the current pixel.

1325

tnPixelX = m_tnX + x;

1326

tnPixelY = m_tnY + y;

1327

1328

// If this pixel has been resolved already,

1329

// skip this pixel-group.

1330

if (m_pNewFrame->GetPixel (tnPixelX,

1331

tnPixelY) != NULL)

1332

goto nextGroup;

1333

1334

// Set the pixel value in the pixel-group.

1335

oCurrentGroup.m_atPixels[y][x]

1336

= a_pPixels[FRAMESIZE (tnPixelY)

1337

* FRAMESIZE (m_tnWidth)

1338

+ FRAMESIZE (tnPixelX)];

1339

}

1340

}

1341

}

1342

1343

// Tell the pixel-group where it is.

1344

oCurrentGroup.m_tnX = m_tnX;

1345

oCurrentGroup.m_tnY = m_tnY;

1346

1347

// HACK

1348

#if 0

1349

fprintf (stderr, "Now checking pixel-group, frame %d, "

1350

"x %d, y %d\n", frame, int (m_tnX), int (m_tnY));

1351

#endif

1352

1353

// No matches yet.

1354

tnMatches = 0;

1355

1356

// Find matches for the current pixel-group. Search for

1357

// them in the pixel-sorter tree, make sure each wasn't

1358

// already found (i.e. isn't already in the search-border),

1359

// flood-fill each one, and add each to the search-border.

1360

//

1361

// If the number of matches in the area exceeds the

1362

// match-count-throttle, or if the largest region found

1363

// exceeds the match-size-throttle, then pick the largest

1364

// region that intersects the current pixel-group and apply

1365

// it to the frame now.

1366

1367

// Set up the search-window in a radius around the

1368

// current pixel-group.

1369

m_oSearchWindow.PrepareForSearch (a_reStatus, true);

1370

if (a_reStatus != g_kNoError)

1371

return;

1372

1373

// Search for matches for the current pixel-group

1374

// within the search radius.

1375

m_oSearchWindow.StartSearch (itMatch, oCurrentGroup);

1376

#ifdef THROTTLE_PIXELSORTER_WITH_SAD

1377

m_setMatches.Clear();

1378

while (pMatch = m_oSearchWindow.FoundNextMatch (itMatch,

1379

tnSAD), pMatch != NULL)

1380

#else // THROTTLE_PIXELSORTER_WITH_SAD

1381

while (pMatch = m_oSearchWindow.FoundNextMatch (itMatch),

1382

pMatch != NULL)

1383

#endif // THROTTLE_PIXELSORTER_WITH_SAD

1384

{

1385

// Calculate its motion vector.

1386

PIXELINDEX tnMotionX = pMatch->m_tnX - m_tnX;

1387

PIXELINDEX tnMotionY = pMatch->m_tnY - m_tnY;

1388

1389

#ifdef PRINT_SEARCHBORDER

1390

//if (frame == 61 && DIM == 2)

1391

fprintf (stderr, "Found match at (%d,%d), "

1392

"motion vector (%d,%d)\n",

1393

int (m_tnX), int (m_tnY),

1394

int (tnMotionX), int (tnMotionY));

1395

#endif // PRINT_SEARCHBORDER

1396

1397

// Make sure this match is within the search

1398

// radius. (Sanity check.)

1399

assert (AbsoluteValue (tnMotionX)

1400

<= m_tnSearchRadiusX);

1401

assert (AbsoluteValue (tnMotionY)

1402

<= m_tnSearchRadiusY);

1403

1404

// Make sure all matches refer to unused

1405

// reference-frame pixels.

1406

#ifndef NDEBUG

1407

#ifdef USE_REFERENCEFRAMEPIXELS_ONCE

1408

{

1409

PIXELINDEX x, y;

1410

// Used to loop through the current

1411

// pixel-group's pixels.

1412

1413

for (y = 0; y < PGH; ++y)

1414

{

1415

for (x = 0; x < PGW; ++x)

1416

{

1417

PIXELINDEX tnPixelX, tnPixelY;

1418

// The index of the current pixel.

1419

1420

// Calculate the index of the current

1421

// pixel.

1422

tnPixelX = pMatch->m_tnX + x;

1423

tnPixelY = pMatch->m_tnY + y;

1424

1425

// Make sure this reference-frame pixel

1426

// hasn't been used already.

1427

assert (!m_oUsedReferencePixels

1428

.DoesContainPoint (tnPixelY,

1429

tnPixelX));

1430

}

1431

}

1432

}

1433

#endif // USE_REFERENCEFRAMEPIXELS_ONCE

1434

#endif // !NDEBUG

1435

1436

// That's one more match.

1437

++tnMatches;

1438

1439

// See if a region with this motion vector already

1440

// intersects/borders the current pixel-group, and

1441

// get its size.

1442

bool bExistingMatch = m_oSearchBorder.HasExistingMatch

1443

(tnMotionX, tnMotionY);

1444

1445

// HACK

1446

#if 0

1447

fprintf (stderr, "\tFound match, "

1448

"motion vector (%d,%d)",

1449

int (tnMotionX), int (tnMotionY));

1450

if (!bExistingMatch)

1451

fprintf (stderr, " - new\n");

1452

else

1453

fprintf (stderr, " - existing\n");

1454

#endif

1455

1456

#ifdef THROTTLE_PIXELSORTER_WITH_SAD

1457

1458

// If a region with this motion vector already

1459

// intersects/borders the current pixel-group, then

1460

// this match can be skipped.

1461

if (!bExistingMatch)

1462

{

1463

// If this match is better than our worst so

1464

// far, get rid of our worst & use the new one

1465

// instead.

1466

if (m_setMatches.Size() == m_nMatchCountThrottle)

1467

{

1468

typename MatchedPixelGroupSet::Iterator

1469

itWorst;

1470

// The worst match found so far.

1471

1472

// Get the worst match. (It's at the end of

1473

// the list.)

1474

itWorst = m_setMatches.End();

1475

--itWorst;

1476

1477

// If the new item is better than our worst,

1478

// get rid of our worst to make room for the

1479

// new item.

1480

if (tnSAD < (*itWorst).m_tnSAD)

1481

m_setMatches.Erase (itWorst);

1482

}

1483

1484

// If this match is close enough to the current

1485

// pixel-group, make a note of it.

1486

if (m_setMatches.Size() < m_nMatchCountThrottle)

1487

{

1488

m_setMatches.Insert (a_reStatus,

1489

MatchedPixelGroup (tnSAD, pMatch));

1490

if (a_reStatus != g_kNoError)

1491

return;

1492

}

1493

}

1494

1495

#else // THROTTLE_PIXELSORTER_WITH_SAD

1496

1497

// If a region with this motion vector doesn't already

1498

// intersect/border the current pixel-group, then

1499

// flood-fill it and add it to the search-border.

1500

if (!bExistingMatch)

1501

{

1502

// Add this region to the search-border.

1503

(void) SearchBorder_AddNewRegion (a_reStatus,

1504

tnMotionX, tnMotionY);

1505

if (a_reStatus != g_kNoError)

1506

return;

1507

}

1508

1509

#endif // THROTTLE_PIXELSORTER_WITH_SAD

1510

}

1511

1512

#ifdef THROTTLE_PIXELSORTER_WITH_SAD

1513

1514

// Now loop through all the good matches found, flood-fill

1515

// each one, and add them to the search-border.

1516

for (itBestMatch = m_setMatches.Begin();

1517

itBestMatch != m_setMatches.End();

1518

++itBestMatch)

1519

{

1520

PIXELINDEX tnMotionX, tnMotionY;

1521

// The motion vector of this match.

1522

1523

// Get the current match.

1524

const MatchedPixelGroup &rMatch = *itBestMatch;

1525

1526

// Calculate its motion vector.

1527

tnMotionX = rMatch.m_pGroup->m_tnX - m_tnX;

1528

tnMotionY = rMatch.m_pGroup->m_tnY - m_tnY;

1529

1530

// Add this region to the search-border.

1531

(void) SearchBorder_AddNewRegion (a_reStatus,

1532

tnMotionX, tnMotionY);

1533

if (a_reStatus != g_kNoError)

1534

return;

1535

}

1536

1537

// All done with the matches.

1538

m_setMatches.Clear();

1539

1540

#endif // THROTTLE_PIXELSORTER_WITH_SAD

1541

1542

// If it's time to throttle matches, do so.

1543

//

1544

// The idea is that matches are only throttled when the

1545

// match-count-throttle is exceeded, and the largest

1546

// matches are applied until the match-size-throttle is

1547

// satisfied. Previously, matches could be throttled if

1548

// only the match-size-throttle was exceeded. But this

1549

// led to bad matches getting applied before a better match

1550

// could be found, which led to an "earthquaking" sort of

1551

// artifact in dark, cloudy areas of the picture. This

1552

// ended up being the simple fix for that problem!

1553

//

1554

// Now, the challenge is to pick a match-size-throttle that

1555

// keeps the denoiser running quickly without missing many

1556

// good matches, and a match-count-throttle that keeps the

1557

// number of candidates high enough to avoid the shaking

1558

// artifact described above.

1559

if (tnMatches >= m_nMatchCountThrottle

1560

/* || m_oSearchBorder.GetSizeOfLargestActiveRegion()

1561

>= m_nMatchSizeThrottle */)

1562

{

1563

// Get the largest active-region from the search-border

1564

// and apply it now. Then, keep doing that as long

1565

// as the largets active-region exceeds the match-size-

1566

// throttle.

1567

// This allows at least one region to be applied if the

1568

// match-count-throttle is exceeded, and allows the

1569

// search-border to avoid doing expensive work for

1570

// regions that exceed the match-size-throttle.

1571

do

1572

{

1573

FRAMESIZE tnThrottledPixels;

1574

PIXELINDEX tnMotionX, tnMotionY;

1575

1576

// Take the largest region that the current

1577

// pixel-group matched, flood-fill it, and apply it

1578

// to the new frame now, eliminating any competing

1579

// moved-regions encountered along the way.

1580

tnThrottledPixels = SearchBorder_MatchThrottle

1581

(a_reStatus, tnMatches, tnMotionX, tnMotionY);

1582

if (a_reStatus != g_kNoError)

1583

return;

1584

1585

// HACK

1586

#if 0

1587

fprintf (stderr, "Match throttle: frame %d, "

1588

"x %03d, y %03d, %03d matches, "

1589

"%04d flood \r", frame,

1590

int (m_tnX), int (m_tnY), int (tnMatches),

1591

int (tnThrottledPixels));

1592

#endif

1593

1594

// That's more pixels found by match-throttling.

1595

if (tnMotionX == 0 && tnMotionY == 0)

1596

tnNotMovedThrottledPixels += tnThrottledPixels;

1597

else

1598

tnMovedThrottledPixels += tnThrottledPixels;

1599

} while (m_oSearchBorder.GetSizeOfLargestActiveRegion()

1600

>= m_nMatchSizeThrottle);

1601

}

1602

1603

// If no matches were found for the current pixel-group,

1604

// and there are no active border-regions in the area,

1605

// then we've found new information.

1606

//

1607

// NOTE: this dramatically speeds up the analysis of

1608

// frames that contain mostly new info, but probably

1609

// impacts quality. Flood-fills are allowed to override

1610

// the result, though.

1611

//

1612

// NOTE: We no longer test whether there are any active

1613

// border-regions in the area. The logic is, they've been

1614

// flood-filled, and if they don't extend into the current

1615

// pixel-group, then it's safe to consider the current

1616

// pixel-group to be new information.

1617

else if (tnMatches == 0)

1618

{

1619

PIXELINDEX tnX, tnY;

1620

1621

for (tnY = m_tnY; tnY < m_tnY + PGH; ++tnY)

1622

{

1623

for (tnX = m_tnX; tnX < m_tnX + PGW; ++tnX)

1624

{

1625

// Allocate a new reference pixel.

1626

ReferencePixel_t *pNewPixel

1627

= m_oPixelPool.Allocate();

1628

1629

// Store the new pixel in the reference frame.

1630

m_pNewFrame->SetPixel (tnX, tnY, pNewPixel);

1631

1632

// Give it the value from the new frame.

1633

pNewPixel->AddSample (a_pPixels[tnY

1634

* m_tnWidth + tnX]);

1635

}

1636

}

1637

}

1638

1639

nextGroup:

1640

// Move to the next pixel-group.

1641

if ((m_tnStepX == 1 && m_tnX == tnLastX)

1642

|| (m_tnStepX == -1 && m_tnX == 0))

1643

{

1644

// We need to move down a line. If we're already on

1645

// the last line, we're done with the frame.

1646

if (m_tnY == tnLastY)

1647

break;

1648

1649

// We should have found enough matches during this line

1650

// to safely apply all regions that exceed the

1651

// match-size-throttle.

1652

if (m_oSearchBorder.GetSizeOfLargestActiveRegion()

1653

>= m_nMatchSizeThrottle)

1654

{

1655

// Get the largest active-region from the

1656

// search-border and apply it now. Then, keep

1657

// doing that as long as the largets active-region

1658

// exceeds the match-size-throttle.

1659

// This allows at least one region to be applied if

1660

// the match-count-throttle is exceeded, and allows

1661

// the search-border to avoid doing expensive work

1662

// for regions that exceed the match-size-throttle.

1663

tnMatches = 0;

1664

do

1665

{

1666

FRAMESIZE tnThrottledPixels;

1667

PIXELINDEX tnMotionX, tnMotionY;

1668

1669

// Take the largest region that the current

1670

// pixel-group matched, flood-fill it, and

1671

// apply it to the new frame now, eliminating

1672

// any competing moved-regions encountered

1673

// along the way.

1674

tnThrottledPixels = SearchBorder_MatchThrottle

1675

(a_reStatus, tnMatches,

1676

tnMotionX, tnMotionY);

1677

if (a_reStatus != g_kNoError)

1678

return;

1679

1680

// HACK

1681

#if 0

1682

fprintf (stderr, "Match throttle: frame %d, "

1683

"x %03d, y %03d, %03d matches, "

1684

"%04d flood \r", frame,

1685

int (m_tnX), int (m_tnY), int (tnMatches),

1686

int (tnThrottledPixels));

1687

#endif

1688

1689

// That's more pixels found by

1690

// match-throttling.

1691

if (tnMotionX == 0 && tnMotionY == 0)

1692

tnNotMovedThrottledPixels

1693

+= tnThrottledPixels;

1694

else

1695

tnMovedThrottledPixels

1696

+= tnThrottledPixels;

1697

} while

1698

(m_oSearchBorder.GetSizeOfLargestActiveRegion()

1699

>= m_nMatchSizeThrottle);

1700

}

1701

1702

// Move down a line.

1703

m_oSearchWindow.MoveDown();

1704

m_oSearchBorder.MoveDown (a_reStatus);

1705

if (a_reStatus != g_kNoError)

1706

return;

1707

++m_tnY;

1708

1709

// HACK

1710

//fprintf (stderr, "Now on line %d\r", int (m_tnY));

1711

1712

// Now move across the frame in the other direction,

1713

// i.e. zigzag.

1714

m_tnStepX = -m_tnStepX;

1715

}

1716

else if (m_tnStepX == 1)

1717

{

1718

// Move right one pixel.

1719

m_oSearchWindow.MoveRight();

1720

m_oSearchBorder.MoveRight (a_reStatus);

1721

if (a_reStatus != g_kNoError)

1722

return;

1723

++m_tnX;

1724

}

1725

else

1726

{

1727

// Move left one pixel.

1728

assert (m_tnStepX == -1);

1729

m_oSearchWindow.MoveLeft();

1730

m_oSearchBorder.MoveLeft (a_reStatus);

1731

if (a_reStatus != g_kNoError)

1732

return;

1733

--m_tnX;

1734

}

1735

}

1736

1737

// Get all the remaining moved-regions from the search-border.

1738

m_oSearchBorder.FinishFrame (a_reStatus);

1739

if (a_reStatus != g_kNoError)

1740

return;

1741

1742

// We've found all the possible moved regions between the

1743

// new frame and the reference frame.

1744

// Loop through the moved regions found by motion-detection,

1745

// prune them of already-resolved pixels, and apply each one

1746

// to the new frame.

1747

//fprintf (stderr, "Applied extents:"); // HACK

1748

while (m_setRegions.Size() > 0)

1749

{

1750

typename MovedRegionSet::Iterator itRegion;

1751

MovedRegion *pRegion;

1752

// The moved region to apply next.

1753

PIXELINDEX tnMotionX, tnMotionY;

1754

// The region's motion vector.

1755

1756

// Get the moved region to apply next.

1757

itRegion = m_setRegions.Begin();

1758

pRegion = *itRegion;

1759

m_setRegions.Erase (itRegion);

1760

pRegion->GetMotionVector (tnMotionX, tnMotionY);

1761

1762

// Flood-fill the candidate region, re-testing all the

1763

// extents. This removes parts that have been resolved

1764

// already.

1765

m_oPruningFloodFillControl.SetupForFloodFill

1766

(tnMotionX, tnMotionY);

1767

pRegion->FloodFill (a_reStatus,

1768

m_oPruningFloodFillControl, true, false);

1769

if (a_reStatus != g_kNoError)

1770

return;

1771

1772

// If that makes it smaller than the next highest-

1773

// priority region we found, put it back in & try again.

1774

itRegion = m_setRegions.Begin();

1775

if (itRegion != m_setRegions.End()

1776

&& pRegion->NumberOfPoints()

1777

< (*itRegion)->NumberOfPoints())

1778

{

1779

// Are there enough points left in this region for

1780

// us to bother with it?

1781

if (pRegion->NumberOfPoints() < PGW * PGH)

1782

{

1783

// No. Just get rid of it.

1784

m_oSearchBorder.DeleteRegion (pRegion);

1785

}

1786

else

1787

{

1788

// Yes. Put the region back into our set, to be

1789

// tried later.

1790

#ifndef NDEBUG

1791

typename MovedRegionSet::InsertResult

1792

oInsertResult =

1793

#endif // !NDEBUG

1794

m_setRegions.Insert (a_reStatus, pRegion);

1795

if (a_reStatus != g_kNoError)

1796

{

1797

m_oSearchBorder.DeleteRegion (pRegion);

1798

return;

1799

}

1800

assert (oInsertResult.m_bInserted);

1801

}

1802

1803

// Try the region that's now the highest priority.

1804

continue;

1805

}

1806

1807

// Apply this region to the new frame.

1808

ApplyRegionToNewFrame (a_reStatus, *pRegion);

1809

if (a_reStatus != g_kNoError)

1810

{

1811

m_oSearchBorder.DeleteRegion (pRegion);

1812

return;

1813

}

1814

1815

// That's more resolved pixels.

1816

if (tnMotionX == 0 && tnMotionY == 0)

1817

tnNotMovedPixels += pRegion->NumberOfPoints();

1818

else

1819

tnMovedPixels += pRegion->NumberOfPoints();

1820

1821

// We're done with this region.

1822

m_oSearchBorder.DeleteRegion (pRegion);

1823

}

1824

}

1825

1826

// Prepare for searching the next frame.

1827

m_oSearchWindow.FinishFrame();

1828

}

1829

1830

// Motion-searching is done. Loop through the reference frame's

1831

// pixels, find any unresolved pixels, and create a new pixel for

1832

// them, using the data in the new frame.

1833

for (i = 0; i < m_tnPixels; ++i)

1834

{

1835

ReferencePixel_t *pNewPixel;

1836

1837

// If this pixel is still unresolved, give it the value of

1838

// the corresponding pixel in the new frame.

1839

pNewPixel = m_pNewFrame->GetPixel (i);

1840

if (pNewPixel == NULL)

1841

{

1842

// Allocate a new reference pixel.

1843

ReferencePixel_t *pNewPixel = m_oPixelPool.Allocate();

1844

1845

// Store the new pixel in the reference frame.

1846

m_pNewFrame->SetPixel (i, pNewPixel);

1847

1848

// Give it the value from the new frame.

1849

pNewPixel->AddSample (a_pPixels[i]);

1850

1851

// That's one more new pixel.

1852

++tnNewPixels;

1853

}

1854

else if (pNewPixel != NULL

1855

&& pNewPixel->GetFrameReferences() == 1)

1856

{

1857

// Count up the earlier-found new pixel. (It wasn't safe to

1858

// count them until flood-filling had a chance to override

1859

// this decision.)

1860

++tnNoMatchNewPixels;

1861

}

1862

}

1863

1864

// Make sure all pixels were accounted for.

1865

// (This is a big sanity check.)

1866

assert (tnNotMovedZeroMotionPixels + tnNotMovedThrottledPixels

1867

+ tnNotMovedPixels + tnMovedThrottledPixels + tnMovedPixels

1868

+ tnNoMatchNewPixels + tnNewPixels == m_tnPixels);

1869

1870

// All done. Remember that the data in the new frame is now valid.

1871

++m_nLastFrame;

1872

1873

// Make sure none of the pixels have more references than we have

1874

// frames. (Sanity check.)

1875

#ifndef NDEBUG

1876

#ifdef USE_REFERENCEFRAMEPIXELS_ONCE

1877

for (i = 0; i < m_tnPixels; ++i)

1878

{

1879

int16_t nRefs = m_pNewFrame->GetPixel (i)->GetFrameReferences();

1880

assert (nRefs > 0);

1881

assert (nRefs <= m_nFrames);

1882

}

1883

#endif // USE_REFERENCEFRAMEPIXELS_ONCE

1884

#endif // !NDEBUG

1885

1886

// We'll have a new reference-frame and new-frame in the next pass.

1887

m_pReferenceFrame = m_pNewFrame = NULL;

1888

m_pNewFramePixels = NULL;

1889

1890

// HACK: print the pixel statistics.

1891

if (verbose >= 1)

1892

{

1893

float fInversePixelsPercent = 100.0f / float (m_tnPixels);

1894

1895

fprintf (stderr, "Frame %d: %.1f%%+%.1f%%+%.1f%% not-moved, "

1896

"%.1f%%+%.1f%% moved, %.1f%%+%.1f%% new\n",

1897

frame,

1898

(float (tnNotMovedZeroMotionPixels) * fInversePixelsPercent),

1899

(float (tnNotMovedThrottledPixels) * fInversePixelsPercent),

1900

(float (tnNotMovedPixels) * fInversePixelsPercent),

1901

(float (tnMovedThrottledPixels) * fInversePixelsPercent),

1902

(float (tnMovedPixels) * fInversePixelsPercent),

1903

(float (tnNoMatchNewPixels) * fInversePixelsPercent),

1904

(float (tnNewPixels) * fInversePixelsPercent));

1905

}

1906

1907

// Print the allocation totals.

1908

#ifndef NDEBUG

1909

fprintf (stderr, "%lu moved-regions, %lu pixel-sorters\n",

1910

(unsigned long) m_oSearchBorder.GetMovedRegionCount(),

1911

(unsigned long) m_oSearchWindow.GetPixelSorterNodeCount());

1912

#endif // !NDEBUG

1913

1914

// Purge all remaining temporary memory allocations.

1915

m_oMatchThrottleRegion.Purge();

1916

#ifndef ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

1917

m_oZeroMotionFloodFillControl.Purge();

1918

#endif // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

1919

#ifndef MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

1920

m_oMatchThrottleFloodFillControl.Purge();

1921

#endif // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

1922

#ifndef PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

1923

m_oPruningFloodFillControl.Purge();

1924

#endif // PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

1925

1926

// Make sure our temporary memory allocations have been purged.

1927

assert (m_oRegionAllocator.GetNumAllocated() == 0);

1928

assert (m_oMovedRegionSetAllocator.GetNumAllocated() == 0);

1929

}

1930

1931

1932

1933

// Once there is no more input, call this repeatedly to get the

1934

// details of the remaining frames, until it returns NULL.

1935

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

1936

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

1937

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

1938

class REFERENCEFRAME>

1939

const typename MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,

1940

FRAMESIZE,PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

1941

REFERENCEFRAME>::ReferenceFrame_t *

1942

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

1943

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

1944

REFERENCEFRAME>::GetRemainingFrames (void)

1945

{

1946

ReferenceFrame_t *pFrame;

1947

// The frame to return to the caller.

1948

1949

// If there are no frames left, let our caller know.

1950

if (m_nFirstFrame == m_nLastFrame)

1951

return NULL;

1952

1953

// Get the frame to return to the caller.

1954

pFrame = m_ppFrames[m_nFirstFrame];

1955

1956

// Remember not to hand it to the caller ever again.

1957

++m_nFirstFrame;

1958

1959

// Finally, return the frame to our caller.

1960

return pFrame;

1961

}

1962

1963

1964

1965

// Purge ourselves of temporary structures.

1966

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

1967

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

1968

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

1969

class REFERENCEFRAME>

1970

void

1971

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

1972

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

1973

REFERENCEFRAME>::Purge (void)

1974

{

1975

// Clear out the pixel-sorter.

1976

m_oSearchWindow.PurgePixelSorter();

1977

}

1978

1979

1980

1981

#ifdef THROTTLE_PIXELSORTER_WITH_SAD

1982

1983

// Default constructor.

1984

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

1985

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

1986

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

1987

class REFERENCEFRAME>

1988

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

1989

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

1990

REFERENCEFRAME>::MatchedPixelGroup::MatchedPixelGroup()

1991

{

1992

// No match yet.

1993

m_tnSAD = 0;

1994

m_pGroup = NULL;

1995

}

1996

1997

1998

1999

// Initializing constructor.

2000

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2001

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2002

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2003

class REFERENCEFRAME>

2004

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2005

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2006

REFERENCEFRAME>::MatchedPixelGroup::MatchedPixelGroup

2007

(Tolerance_t a_tnSAD,

2008

const typename SearchWindow_t::PixelGroup *a_pGroup)

2009

: m_tnSAD (a_tnSAD), m_pGroup (a_pGroup)

2010

{

2011

// Nothing else to do.

2012

}

2013

2014

2015

2016

// Destructor.

2017

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2018

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2019

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2020

class REFERENCEFRAME>

2021

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2022

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2023

REFERENCEFRAME>::MatchedPixelGroup::~MatchedPixelGroup()

2024

{

2025

// Nothing to do.

2026

}

2027

2028

2029

2030

// A comparison operator, suitable for Set<>.

2031

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2032

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2033

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2034

class REFERENCEFRAME>

2035

inline bool

2036

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2037

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2038

REFERENCEFRAME>::MatchedPixelGroup::SortBySAD::operator()

2039

(const MatchedPixelGroup &a_rLeft,

2040

const MatchedPixelGroup &a_rRight) const

2041

{

2042

// Easy enough.

2043

return (a_rLeft.m_tnSAD < a_rRight.m_tnSAD);

2044

}

2045

2046

#endif // THROTTLE_PIXELSORTER_WITH_SAD

2047

2048

2049

2050

// Apply this region to the new frame.

2051

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2052

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2053

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2054

class REFERENCEFRAME>

2055

void

2056

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2057

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,REFERENCEFRAME>

2058

::ApplyRegionToNewFrame (Status_t &a_reStatus,

2059

const MovedRegion &a_rRegion)

2060

{

2061

PIXELINDEX tnMotionX, tnMotionY;

2062

// The region's motion vector, i.e. the offset between the

2063

// new-frame pixel and the corresponding reference-frame pixel.

2064

typename MovedRegion::ConstIterator itExtent;

2065

// An extent to apply to the new frame.

2066

PIXELINDEX x;

2067

// Used to loop through pixels.

2068

2069

// Make sure they didn't start us off with an error.

2070

assert (a_reStatus == g_kNoError);

2071

2072

// Get this region's motion vector.

2073

a_rRegion.GetMotionVector (tnMotionX, tnMotionY);

2074

2075

// Loop through the region's extents, locate every pixel it

2076

// describes, and set it to the corresponding pixel in the

2077

// reference-frame representation of the new frame.

2078

for (itExtent = a_rRegion.Begin();

2079

itExtent != a_rRegion.End();

2080

++itExtent)

2081

{

2082

// Get the next extent.

2083

const typename MovedRegion::Extent &rExtent = *itExtent;

2084

2085

// Loop through the pixels it represents, set each

2086

// new-frame pixel to the corresponding reference-frame

2087

// pixel.

2088

for (x = rExtent.m_tnXStart; x < rExtent.m_tnXEnd; ++x)

2089

{

2090

#ifdef PRINT_SEARCHBORDER

2091

if (m_pNewFrame->GetPixel (x, rExtent.m_tnY) != NULL

2092

&& m_pNewFrame->GetPixel (x, rExtent.m_tnY)

2093

->GetFrameReferences() != 1)

2094

{

2095

fprintf (stderr, "Pixel (%d,%d) already resolved\n",

2096

int (x), int (rExtent.m_tnY));

2097

}

2098

#endif // PRINT_SEARCHBORDER

2099

2100

// Make sure this new-frame pixel hasn't been

2101

// resolved yet.

2102

assert (m_pNewFrame->GetPixel (x, rExtent.m_tnY)

2103

== NULL

2104

|| m_pNewFrame->GetPixel (x, rExtent.m_tnY)

2105

->GetFrameReferences() == 1);

2106

2107

// Get the corresponding reference-frame pixel.

2108

ReferencePixel_t *pReferencePixel

2109

= m_pReferenceFrame->GetPixel (x + tnMotionX,

2110

rExtent.m_tnY + tnMotionY);

2111

assert (pReferencePixel != NULL);

2112

2113

// Set the new-frame pixel to this reference pixel.

2114

m_pNewFrame->SetPixel (x, rExtent.m_tnY,

2115

pReferencePixel);

2116

2117

// Accumulate the new-frame value of this pixel.

2118

pReferencePixel->AddSample

2119

(m_pNewFramePixels[FRAMESIZE (rExtent.m_tnY)

2120

* FRAMESIZE (m_tnWidth) + FRAMESIZE (x)]);

2121

}

2122

}

2123

2124

#ifdef USE_REFERENCEFRAMEPIXELS_ONCE

2125

2126

// All of these reference pixels have been used.

2127

for (itExtent = a_rRegion.Begin();

2128

itExtent != a_rRegion.End();

2129

++itExtent)

2130

{

2131

// Get the current extent.

2132

typename MovedRegion::Extent oExtent = *itExtent;

2133

2134

// Move it along the motion vector.

2135

oExtent.m_tnY += tnMotionY;

2136

oExtent.m_tnXStart += tnMotionX;

2137

oExtent.m_tnXEnd += tnMotionX;

2138

2139

// Make sure it's already in the frame.

2140

assert (oExtent.m_tnY >= 0 && oExtent.m_tnY < m_tnHeight

2141

&& oExtent.m_tnXStart >= 0 && oExtent.m_tnXEnd <= m_tnWidth);

2142

2143

// Add it to our running total of used reference-pixels.

2144

m_oUsedReferencePixels.Union (a_reStatus, oExtent.m_tnY,

2145

oExtent.m_tnXStart, oExtent.m_tnXEnd);

2146

if (a_reStatus != g_kNoError)

2147

return;

2148

}

2149

2150

#endif // USE_REFERENCEFRAMEPIXELS_ONCE

2151

2152

// Remove all pixel-groups containing used reference pixels from

2153

// the search window.

2154

m_oSearchWindow.Prune (a_rRegion, tnMotionX, tnMotionY);

2155

}

2156

2157

2158

2159

// Default constructor.

2160

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2161

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2162

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2163

class REFERENCEFRAME>

2164

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2165

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2166

REFERENCEFRAME>::SearchBorder_t::SearchBorder_t

2167

(MovedRegionSet &a_rsetRegions,

2168

typename MovedRegion::Allocator &a_rAlloc)

2169

: BaseClass (a_rAlloc), m_rsetRegions (a_rsetRegions)

2170

{

2171

// Nothing else to do.

2172

}

2173

2174

2175

2176

// Receive a completed region from the search-border.

2177

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2178

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2179

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2180

class REFERENCEFRAME>

2181

void

2182

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2183

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2184

REFERENCEFRAME>::SearchBorder_t::OnCompletedRegion

2185

(Status_t &a_reStatus,

2186

typename SearchBorder_t::MovedRegion *a_pRegion)

2187

{

2188

// Make sure they didn't start us off with an error.

2189

assert (a_reStatus == g_kNoError);

2190

2191

// Make sure they gave us a completed region.

2192

assert (a_pRegion != NULL);

2193

2194

// Put it in our list.

2195

if (a_pRegion->NumberOfPoints() < PGW * PGH)

2196

{

2197

// This region is too small to be bothered with.

2198

// Just get rid of it.

2199

DeleteRegion (a_pRegion);

2200

}

2201

else

2202

{

2203

#ifndef NDEBUG

2204

typename MovedRegionSet::InsertResult oInsertResult =

2205

#endif // !NDEBUG

2206

m_rsetRegions.Insert (a_reStatus, a_pRegion);

2207

if (a_reStatus != g_kNoError)

2208

return;

2209

assert (oInsertResult.m_bInserted);

2210

}

2211

}

2212

2213

2214

2215

// Add a new region, with the given motion vector, to the

2216

// search border. Flood-fills its area before adding.

2217

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2218

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2219

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2220

class REFERENCEFRAME>

2221

FRAMESIZE

2222

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2223

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2224

REFERENCEFRAME>::SearchBorder_AddNewRegion (Status_t &a_reStatus,

2225

PIXELINDEX a_tnMotionX, PIXELINDEX a_tnMotionY)

2226

{

2227

PIXELINDEX tnY;

2228

// Used to loop through the pixel-group's lines.

2229

2230

// Set up a region describing the current pixel-group.

2231

#ifdef MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

2232

m_oFloodFillRegion.Clear();

2233

for (tnY = m_tnY; tnY < m_tnY + PGH; ++tnY)

2234

{

2235

m_oFloodFillRegion.Merge (a_reStatus, tnY, m_tnX,

2236

m_tnX + PGW);

2237

if (a_reStatus != g_kNoError)

2238

return 0;

2239

}

2240

#else // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

2241

m_oMatchThrottleRegion.Clear();

2242

for (tnY = m_tnY; tnY < m_tnY + PGH; ++tnY)

2243

{

2244

m_oMatchThrottleRegion.Merge (a_reStatus, tnY, m_tnX,

2245

m_tnX + PGW);

2246

if (a_reStatus != g_kNoError)

2247

return 0;

2248

}

2249

#endif // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

2250

2251

// Set its motion vector.

2252

m_oMatchThrottleRegion.SetMotionVector (a_tnMotionX, a_tnMotionY);

2253

2254

// Set its location. (Needed only for debugging purposes.)

2255

#ifndef NDEBUG

2256

m_oMatchThrottleRegion.m_tnX = m_tnX;

2257

m_oMatchThrottleRegion.m_tnY = m_tnY;

2258

#endif // !NDEBUG

2259

2260

// Flood-fill this match, so as to get its full extent.

2261

m_oMatchThrottleFloodFillControl.SetupForFloodFill (a_tnMotionX,

2262

a_tnMotionY);

2263

#ifdef MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

2264

m_oFloodFillRegion.FloodFill (a_reStatus,

2265

m_oMatchThrottleFloodFillControl, false, true);

2266

#else // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

2267

m_oMatchThrottleRegion.FloodFill (a_reStatus,

2268

m_oMatchThrottleFloodFillControl, false, true);

2269

#endif // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

2270

if (a_reStatus != g_kNoError)

2271

return 0;

2272

2273

// Now copy the results of the flood-fill to the match-throttle

2274

// region, so that it can be added to the search-border.

2275

#ifdef MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

2276

m_oMatchThrottleRegion.Clear();

2277

typename BitmapRegion_t::ConstIterator itExtent;

2278

for (itExtent = m_oFloodFillRegion.Begin();

2279

itExtent != m_oFloodFillRegion.End();

2280

++itExtent)

2281

{

2282

// Get the current extent.

2283

const typename BitmapRegion_t::Extent &rExtent = *itExtent;

2284

2285

// Copy it to the match-throttle region.

2286

m_oMatchThrottleRegion.Merge

2287

(a_reStatus, rExtent.m_tnY,

2288

rExtent.m_tnXStart, rExtent.m_tnXEnd);

2289

if (a_reStatus != g_kNoError)

2290

return 0;

2291

}

2292

#endif // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

2293

2294

// Get the size of the flood-filled region.

2295

FRAMESIZE tnThisMatch = m_oMatchThrottleRegion.NumberOfPoints();

2296

2297

// Add this match to our growing set of moved regions.

2298

m_oSearchBorder.AddNewRegion (a_reStatus,

2299

m_oMatchThrottleRegion);

2300

if (a_reStatus != g_kNoError)

2301

return 0;

2302

2303

// Make sure that emptied the region.

2304

// (AddNewRegion() is supposed to do that; this will catch any

2305

// changes in that behavior.)

2306

assert (m_oMatchThrottleRegion.NumberOfPoints() == 0);

2307

2308

// Return the size of the flood-filled region.

2309

return tnThisMatch;

2310

}

2311

2312

2313

2314

// Get the best region that matched the current pixel-group

2315

// (which is usually the largest active-region). Expand it as far

2316

// as it can go, i.e. flood-fill in its area. If it's no longer

2317

// the largest region, put it back and try again. Otherwise, apply

2318

// it to the new frame now.

2319

//

2320

// Pass the number of pixel-group matches as an argument. If a

2321

// best-region candidate is found to have no unresolved pixels,

2322

// it's no longer considered a pixel-group match, and that may lead

2323

// to the discovery that the match-count-throttle is no longer

2324

// being exceeded.

2325

//

2326

// Returns the number of points flood-filled, and backpatches the

2327

// motion vector associated with the best region.

2328

// May return zero if analysis reveals that the match-throttles

2329

// weren't really exceeded.

2330

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2331

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2332

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2333

class REFERENCEFRAME>

2334

FRAMESIZE

2335

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2336

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2337

REFERENCEFRAME>::SearchBorder_MatchThrottle (Status_t &a_reStatus,

2338

FRAMESIZE a_nMatchCount,

2339

PIXELINDEX &a_rtnMotionX, PIXELINDEX &a_rtnMotionY)

2340

{

2341

MovedRegion *pSurvivor;

2342

// The only region to survive pruning -- the largest one, with

2343

// the shortest motion vector.

2344

2345

// Make sure they didn't start us off with an error.

2346

assert (a_reStatus == g_kNoError);

2347

2348

// Keep testing best-active-region candidates until one really is the

2349

// best, or until the match-throttles are no longer being exceeded.

2350

while (m_oSearchBorder.GetSizeOfLargestActiveRegion() > 0)

2351

{

2352

// Get the best active region to apply to the frame now.

2353

// This also gives us the size of the second-best active-region.

2354

FRAMESIZE tnSecondBestActiveRegionSize = 0;

2355

pSurvivor = m_oSearchBorder.ChooseBestActiveRegion (a_reStatus,

2356

tnSecondBestActiveRegionSize);

2357

if (a_reStatus != g_kNoError)

2358

return 0;

2359

2360

// Get the region's motion vector.

2361

pSurvivor->GetMotionVector (a_rtnMotionX, a_rtnMotionY);

2362

2363

// Remove all pixels that were already resolved.

2364

m_oPruningFloodFillControl.SetupForFloodFill

2365

(a_rtnMotionX, a_rtnMotionY);

2366

pSurvivor->FloodFill (a_reStatus,

2367

m_oPruningFloodFillControl, true, false);

2368

if (a_reStatus != g_kNoError)

2369

{

2370

m_oSearchBorder.DeleteRegion (pSurvivor);

2371

return 0;

2372

}

2373

2374

#ifdef PRINT_SEARCHBORDER

2375

if (frame == 61 && DIM == 2)

2376

{

2377

fprintf (stderr, "Flood-filled region:\n");

2378

PrintRegion (*pSurvivor);

2379

fprintf (stderr, "\n");

2380

}

2381

#endif // PRINT_SEARCHBORDER

2382

2383

// Remember the number of points in the region.

2384

FRAMESIZE tnSurvivorSize = FRAMESIZE (pSurvivor->NumberOfPoints());

2385

2386

// If this region has no unresolved pixels (or too few), try again.

2387

if (tnSurvivorSize < PGW * PGH)

2388

{

2389

// This region is no longer needed.

2390

m_oSearchBorder.DeleteRegion (pSurvivor);

2391

2392

// Go back and try again.

2393

continue;

2394

}

2395

2396

// If this region is no longer the best choice, put it back

2397

// and try again.

2398

if (tnSurvivorSize < tnSecondBestActiveRegionSize)

2399

{

2400

// Put it back.

2401

m_oSearchBorder.AddNewRegion (a_reStatus, *pSurvivor);

2402

m_oSearchBorder.DeleteRegion (pSurvivor);

2403

if (a_reStatus != g_kNoError)

2404

return 0;

2405

2406

// If the match-size-throttle is no longer exceeded,

2407

// then let our caller know that no throttling was needed.

2408

if (tnSecondBestActiveRegionSize < m_nMatchSizeThrottle)

2409

return 0;

2410

2411

// Try again.

2412

continue;

2413

}

2414

2415

// Apply this region to the new frame.

2416

ApplyRegionToNewFrame (a_reStatus, *pSurvivor);

2417

if (a_reStatus != g_kNoError)

2418

{

2419

m_oSearchBorder.DeleteRegion (pSurvivor);

2420

return 0;

2421

}

2422

2423

// Clean up the region, return the number of points it had.

2424

m_oSearchBorder.DeleteRegion (pSurvivor);

2425

return tnSurvivorSize;

2426

}

2427

2428

// No region was applied to the frame.

2429

return 0;

2430

}

2431

2432

2433

2434

// Default constructor.

2435

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2436

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2437

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2438

class REFERENCEFRAME>

2439

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2440

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2441

REFERENCEFRAME>::ZeroMotionFloodFillControl

2442

#ifdef ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

2443

::ZeroMotionFloodFillControl()

2444

#else // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

2445

::ZeroMotionFloodFillControl

2446

(typename BaseClass::Allocator &a_rAllocator)

2447

: BaseClass (a_rAllocator)

2448

#endif // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

2449

{

2450

// We don't know who we're working for yet.

2451

m_pMotionSearcher = NULL;

2452

}

2453

2454

2455

2456

// Initializer.

2457

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2458

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2459

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2460

class REFERENCEFRAME>

2461

void

2462

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2463

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2464

REFERENCEFRAME>::ZeroMotionFloodFillControl::Init

2465

(Status_t &a_reStatus, MotionSearcher *a_pMotionSearcher)

2466

{

2467

// Make sure they didn't start us off with an error.

2468

assert (a_reStatus == g_kNoError);

2469

2470

// Make sure they gave us a motion-searcher.

2471

assert (a_pMotionSearcher != NULL);

2472

2473

// Initialize our base class.

2474

BaseClass::Init (a_reStatus

2475

#ifdef ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

2476

, a_pMotionSearcher->m_tnWidth,

2477

a_pMotionSearcher->m_tnHeight

2478

#endif // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

2479

);

2480

if (a_reStatus != g_kNoError)

2481

return;

2482

2483

// Remember which motion-searcher we're working for.

2484

m_pMotionSearcher = a_pMotionSearcher;

2485

}

2486

2487

2488

2489

// Return true if the flood-fill should examine the given

2490

// extent. May modify the extent.

2491

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2492

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2493

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2494

class REFERENCEFRAME>

2495

bool

2496

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2497

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2498

REFERENCEFRAME>::ZeroMotionFloodFillControl::ShouldUseExtent

2499

(typename ZeroMotionFloodFillControl::BaseClass::Extent &a_rExtent)

2500

{

2501

#ifdef ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

2502

2503

// Make sure the extent doesn't need to be clipped.

2504

assert (a_rExtent.m_tnY >= 0

2505

&& a_rExtent.m_tnY < m_pMotionSearcher->m_tnHeight

2506

&& a_rExtent.m_tnXStart >= 0

2507

&& a_rExtent.m_tnXStart < m_pMotionSearcher->m_tnWidth

2508

&& a_rExtent.m_tnXEnd > 0

2509

&& a_rExtent.m_tnXEnd <= m_pMotionSearcher->m_tnWidth);

2510

2511

#else // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

2512

2513

// If this extent is completely off the screen, skip it.

2514

if (a_rExtent.m_tnY < 0

2515

|| a_rExtent.m_tnY >= m_pMotionSearcher->m_tnHeight

2516

|| a_rExtent.m_tnXStart >= m_pMotionSearcher->m_tnWidth

2517

|| a_rExtent.m_tnXEnd <= 0)

2518

return false;

2519

2520

// If this extent is partially off the screen, clip it.

2521

if (a_rExtent.m_tnXStart < 0)

2522

a_rExtent.m_tnXStart = 0;

2523

if (a_rExtent.m_tnXEnd > m_pMotionSearcher->m_tnWidth)

2524

a_rExtent.m_tnXEnd = m_pMotionSearcher->m_tnWidth;

2525

2526

#endif // ZERO_MOTION_FLOOD_FILL_WITH_BITMAP_REGIONS

2527

2528

// Let our caller know to use this extent.

2529

return true;

2530

}

2531

2532

2533

2534

// Returns true if the given point should be included in the

2535

// flood-fill.

2536

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2537

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2538

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2539

class REFERENCEFRAME>

2540

bool

2541

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2542

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2543

REFERENCEFRAME>::ZeroMotionFloodFillControl::IsPointInRegion

2544

(PIXELINDEX a_tnX, PIXELINDEX a_tnY)

2545

{

2546

// If this pixel has been resolved, skip it.

2547

if (m_pMotionSearcher->m_pNewFrame->GetPixel (a_tnX, a_tnY) != NULL)

2548

return false;

2549

2550

// Get the pixels of interest.

2551

const Pixel_t &rNewPixel = m_pMotionSearcher->m_pNewFramePixels

2552

[a_tnY * m_pMotionSearcher->m_tnWidth + a_tnX];

2553

ReferencePixel_t *pRefPixel

2554

= m_pMotionSearcher->m_pReferenceFrame->GetPixel (a_tnX, a_tnY);

2555

2556

// If the new pixel is close enough to the reference pixel, the

2557

// point is in the region.

2558

if (rNewPixel.IsWithinTolerance

2559

(pRefPixel->GetValue(), m_pMotionSearcher->m_tnZeroTolerance))

2560

{

2561

// The point is in the region.

2562

return true;

2563

}

2564

2565

// The point is not in the region.

2566

return false;

2567

}

2568

2569

2570

2571

// Default constructor.

2572

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2573

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2574

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2575

class REFERENCEFRAME>

2576

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2577

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2578

REFERENCEFRAME>::MatchThrottleFloodFillControl

2579

#ifdef MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

2580

::MatchThrottleFloodFillControl()

2581

#else // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

2582

::MatchThrottleFloodFillControl

2583

(typename BaseClass::Allocator &a_rAllocator)

2584

: BaseClass (a_rAllocator)

2585

#endif // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

2586

{

2587

// We don't know who we're working for yet.

2588

m_pMotionSearcher = NULL;

2589

}

2590

2591

2592

2593

// Initializer.

2594

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2595

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2596

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2597

class REFERENCEFRAME>

2598

void

2599

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2600

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2601

REFERENCEFRAME>::MatchThrottleFloodFillControl::Init

2602

(Status_t &a_reStatus, MotionSearcher *a_pMotionSearcher)

2603

{

2604

// Make sure they didn't start us off with an error.

2605

assert (a_reStatus == g_kNoError);

2606

2607

// Make sure they gave us a motion-searcher.

2608

assert (a_pMotionSearcher != NULL);

2609

2610

// Initialize our base class.

2611

BaseClass::Init (a_reStatus

2612

#ifdef MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

2613

, a_pMotionSearcher->m_tnWidth,

2614

a_pMotionSearcher->m_tnHeight

2615

#endif // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

2616

);

2617

if (a_reStatus != g_kNoError)

2618

return;

2619

2620

// Remember which motion-searcher we're working for.

2621

m_pMotionSearcher = a_pMotionSearcher;

2622

}

2623

2624

2625

2626

// Set up to to a flood-fill.

2627

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2628

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2629

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2630

class REFERENCEFRAME>

2631

void

2632

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2633

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2634

REFERENCEFRAME>::MatchThrottleFloodFillControl::SetupForFloodFill

2635

(PIXELINDEX a_tnMotionX, PIXELINDEX a_tnMotionY)

2636

{

2637

// Save the motion vector.

2638

m_tnMotionX = a_tnMotionX;

2639

m_tnMotionY = a_tnMotionY;

2640

}

2641

2642

2643

2644

// Return true if the flood-fill should examine the given

2645

// extent. May modify the extent.

2646

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2647

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2648

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2649

class REFERENCEFRAME>

2650

bool

2651

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2652

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2653

REFERENCEFRAME>::MatchThrottleFloodFillControl::ShouldUseExtent

2654

(typename Region_t::Extent &a_rExtent)

2655

{

2656

#ifdef MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

2657

2658

// Make sure the extent doesn't need to be clipped.

2659

assert (a_rExtent.m_tnY >= 0

2660

&& a_rExtent.m_tnY < m_pMotionSearcher->m_tnHeight

2661

&& a_rExtent.m_tnXStart >= 0

2662

&& a_rExtent.m_tnXStart < m_pMotionSearcher->m_tnWidth

2663

&& a_rExtent.m_tnXEnd > 0

2664

&& a_rExtent.m_tnXEnd <= m_pMotionSearcher->m_tnWidth);

2665

2666

// If this extent (with its motion vector) is completely off the

2667

// screen, skip it.

2668

if (a_rExtent.m_tnY + m_tnMotionY < 0

2669

|| a_rExtent.m_tnY + m_tnMotionY >= m_pMotionSearcher->m_tnHeight

2670

|| a_rExtent.m_tnXStart + m_tnMotionX >= m_pMotionSearcher->m_tnWidth

2671

|| a_rExtent.m_tnXEnd + m_tnMotionX <= 0)

2672

return false;

2673

2674

// If this extent (with its motion vector) is partially off the

2675

// screen, clip it.

2676

if (a_rExtent.m_tnXStart + m_tnMotionX < 0)

2677

a_rExtent.m_tnXStart = -m_tnMotionX;

2678

if (a_rExtent.m_tnXEnd + m_tnMotionX > m_pMotionSearcher->m_tnWidth)

2679

a_rExtent.m_tnXEnd = m_pMotionSearcher->m_tnWidth - m_tnMotionX;

2680

2681

#else // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

2682

2683

// If this extent is completely off the screen, skip it.

2684

if (a_rExtent.m_tnY < 0

2685

|| a_rExtent.m_tnY >= m_pMotionSearcher->m_tnHeight

2686

|| a_rExtent.m_tnXStart >= m_pMotionSearcher->m_tnWidth

2687

|| a_rExtent.m_tnXEnd <= 0

2688

|| a_rExtent.m_tnY + m_tnMotionY < 0

2689

|| a_rExtent.m_tnY + m_tnMotionY >= m_pMotionSearcher->m_tnHeight

2690

|| a_rExtent.m_tnXStart + m_tnMotionX >= m_pMotionSearcher->m_tnWidth

2691

|| a_rExtent.m_tnXEnd + m_tnMotionX <= 0)

2692

return false;

2693

2694

// If this extent is partially off the screen, clip it.

2695

if (a_rExtent.m_tnXStart + m_tnMotionX < 0)

2696

a_rExtent.m_tnXStart = -m_tnMotionX;

2697

if (a_rExtent.m_tnXEnd + m_tnMotionX > m_pMotionSearcher->m_tnWidth)

2698

a_rExtent.m_tnXEnd = m_pMotionSearcher->m_tnWidth - m_tnMotionX;

2699

if (a_rExtent.m_tnXStart < 0)

2700

a_rExtent.m_tnXStart = 0;

2701

if (a_rExtent.m_tnXEnd > m_pMotionSearcher->m_tnWidth)

2702

a_rExtent.m_tnXEnd = m_pMotionSearcher->m_tnWidth;

2703

2704

#endif // MATCH_THROTTLE_FLOOD_FILL_WITH_BITMAP_REGIONS

2705

2706

// Let our caller know to use this extent.

2707

return true;

2708

}

2709

2710

2711

2712

// Returns true if the given point should be included in the

2713

// flood-fill.

2714

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2715

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2716

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2717

class REFERENCEFRAME>

2718

bool

2719

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2720

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2721

REFERENCEFRAME>::MatchThrottleFloodFillControl::IsPointInRegion

2722

(PIXELINDEX a_tnX, PIXELINDEX a_tnY)

2723

{

2724

// Get the new pixel, if any.

2725

ReferencePixel_t *pNewPixel = m_pMotionSearcher->m_pNewFrame

2726

->GetPixel (a_tnX, a_tnY);

2727

2728

// We can potentially flood-fill this pixel if it's unresolved or

2729

// if it thinks it's new data.

2730

if (pNewPixel == NULL || pNewPixel->GetFrameReferences() == 1)

2731

{

2732

// Get the reference pixel's coordinates.

2733

PIXELINDEX tnRefX = a_tnX + m_tnMotionX;

2734

PIXELINDEX tnRefY = a_tnY + m_tnMotionY;

2735

2736

// If the corresponding reference pixel hasn't been

2737

// used already, see if it matches our pixel.

2738

#ifdef USE_REFERENCEFRAMEPIXELS_ONCE

2739

if (!m_pMotionSearcher->m_oUsedReferencePixels.DoesContainPoint

2740

(tnRefY, tnRefX))

2741

#endif // USE_REFERENCEFRAMEPIXELS_ONCE

2742

{

2743

// If the new pixel is close enough to it, the point is in

2744

// the region.

2745

ReferencePixel_t *pRefPixel

2746

= m_pMotionSearcher->m_pReferenceFrame->GetPixel

2747

(tnRefX, tnRefY);

2748

const Pixel_t &rNewPixel = m_pMotionSearcher

2749

->m_pNewFramePixels[a_tnY

2750

* m_pMotionSearcher->m_tnWidth + a_tnX];

2751

if (rNewPixel.IsWithinTolerance (pRefPixel->GetValue(),

2752

m_pMotionSearcher->m_tnTolerance))

2753

{

2754

// Let our caller know the point is in the region.

2755

return true;

2756

}

2757

}

2758

}

2759

2760

// Let our caller know the point is not in the region.

2761

return false;

2762

}

2763

2764

2765

2766

// Default constructor.

2767

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2768

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2769

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2770

class REFERENCEFRAME>

2771

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2772

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2773

REFERENCEFRAME>::PruningFloodFillControl

2774

#ifdef PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

2775

::PruningFloodFillControl()

2776

#else // PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

2777

::PruningFloodFillControl

2778

(typename BaseClass::Allocator &a_rAllocator)

2779

: BaseClass (a_rAllocator)

2780

#endif // PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

2781

{

2782

// We don't know who we're working for yet.

2783

m_pMotionSearcher = NULL;

2784

}

2785

2786

2787

2788

// Initializer.

2789

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2790

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2791

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2792

class REFERENCEFRAME>

2793

void

2794

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2795

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2796

REFERENCEFRAME>::PruningFloodFillControl::Init

2797

(Status_t &a_reStatus, MotionSearcher *a_pMotionSearcher)

2798

{

2799

// Make sure they didn't start us off with an error.

2800

assert (a_reStatus == g_kNoError);

2801

2802

// Make sure they gave us a motion-searcher.

2803

assert (a_pMotionSearcher != NULL);

2804

2805

// Initialize our base class.

2806

BaseClass::Init (a_reStatus

2807

#ifdef PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

2808

, a_pMotionSearcher->m_tnWidth,

2809

a_pMotionSearcher->m_tnHeight

2810

#endif // PRUNING_FLOOD_FILL_WITH_BITMAP_REGIONS

2811

);

2812

if (a_reStatus != g_kNoError)

2813

return;

2814

2815

// Remember which motion-searcher we're working for.

2816

m_pMotionSearcher = a_pMotionSearcher;

2817

}

2818

2819

2820

2821

// Set up to to a flood-fill.

2822

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2823

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2824

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2825

class REFERENCEFRAME>

2826

void

2827

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2828

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2829

REFERENCEFRAME>::PruningFloodFillControl::SetupForFloodFill

2830

(PIXELINDEX a_tnMotionX, PIXELINDEX a_tnMotionY)

2831

{

2832

// Save the motion vector.

2833

m_tnMotionX = a_tnMotionX;

2834

m_tnMotionY = a_tnMotionY;

2835

}

2836

2837

2838

2839

// Return true if the flood-fill should examine the given

2840

// extent. May modify the extent.

2841

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2842

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2843

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2844

class REFERENCEFRAME>

2845

bool

2846

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2847

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2848

REFERENCEFRAME>::PruningFloodFillControl::ShouldUseExtent

2849

(typename Region_t::Extent &a_rExtent)

2850

{

2851

// Make sure the extent doesn't need to be clipped.

2852

// (This style of flood-filling doesn't try to generate new extents

2853

// that would have to be filtered.)

2854

assert (a_rExtent.m_tnY >= 0

2855

&& a_rExtent.m_tnY < m_pMotionSearcher->m_tnHeight

2856

&& a_rExtent.m_tnXStart >= 0

2857

&& a_rExtent.m_tnXStart < m_pMotionSearcher->m_tnWidth

2858

&& a_rExtent.m_tnXEnd > 0

2859

&& a_rExtent.m_tnXEnd <= m_pMotionSearcher->m_tnWidth);

2860

2861

// Let our caller know to use this extent.

2862

return true;

2863

}

2864

2865

2866

2867

// Returns true if the given point should be included in the

2868

// flood-fill.

2869

template <class PIXEL_NUM, int DIM, class PIXEL_TOL, class PIXELINDEX,

2870

class FRAMESIZE, PIXELINDEX PGW, PIXELINDEX PGH,

2871

class SORTERBITMASK, class PIXEL, class REFERENCEPIXEL,

2872

class REFERENCEFRAME>

2873

bool

2874

MotionSearcher<PIXEL_NUM,DIM,PIXEL_TOL,PIXELINDEX,FRAMESIZE,

2875

PGW,PGH,SORTERBITMASK,PIXEL,REFERENCEPIXEL,

2876

REFERENCEFRAME>::PruningFloodFillControl::IsPointInRegion

2877

(PIXELINDEX a_tnX, PIXELINDEX a_tnY)

2878

{

2879

// Get the new pixel, if any.

2880

ReferencePixel_t *pNewPixel = m_pMotionSearcher->m_pNewFrame

2881

->GetPixel (a_tnX, a_tnY);

2882

2883

// We can potentially flood-fill this pixel if it's unresolved or

2884

// if it thinks it's new data.

2885

if (pNewPixel == NULL || pNewPixel->GetFrameReferences() == 1)

2886

{

2887

// Get the reference pixel's coordinates.

2888

PIXELINDEX tnRefX = a_tnX + m_tnMotionX;

2889

PIXELINDEX tnRefY = a_tnY + m_tnMotionY;

2890

2891

// If the corresponding reference pixel hasn't been

2892

// used already, it matches our pixel.

2893

#ifdef USE_REFERENCEFRAMEPIXELS_ONCE

2894

if (!m_pMotionSearcher->m_oUsedReferencePixels.DoesContainPoint

2895

(tnRefY, tnRefX))

2896

#endif // USE_REFERENCEFRAMEPIXELS_ONCE

2897

{

2898

// Let our caller know the point is in the region.

2899

return true;

2900

}

2901

}

2902

2903

// Let our caller know the point is not in the region.

2904

return false;

2905

}

2906

2907

2908

2909

#endif // __MOTION_SEARCHER_H__