MythTV  master
BlankFrameDetector.cpp
Go to the documentation of this file.
1 // ANSI C headers
2 #include <cmath>
3 #include <cstdlib>
4 #include <utility>
5 
6 // MythTV headers
7 #include "mythcorecontext.h" /* gContext */
8 #include "mythplayer.h"
9 
10 // Commercial Flagging headers
11 #include "CommDetector2.h"
12 #include "FrameAnalyzer.h"
13 #include "quickselect.h"
14 #include "HistogramAnalyzer.h"
15 #include "BlankFrameDetector.h"
16 #include "TemplateMatcher.h"
17 
18 using namespace commDetector2;
19 using namespace frameAnalyzer;
20 
21 namespace {
22 
23 bool
24 isBlank(unsigned char median, float stddev, unsigned char maxmedian,
25  float maxstddev)
26 {
27  return ((median < maxmedian) ||
28  ((median == maxmedian) && (stddev <= maxstddev)));
29 }
30 
31 int
32 sort_ascending_uchar(const void *aa, const void *bb)
33 {
34  return *(unsigned char*)aa - *(unsigned char*)bb;
35 }
36 
37 int
38 sort_ascending_float(const void *aa, const void *bb)
39 {
40  float faa = *(float*)aa;
41  float fbb = *(float*)bb;
42  return faa < fbb ? -1 : faa == fbb ? 0 : 1;
43 }
44 
45 bool
46 pickmedian(const unsigned char medianval,
47  unsigned char minval, unsigned char maxval)
48 {
49  return medianval >= minval && medianval <= maxval;
50 }
51 
52 void
53 computeBlankMap(FrameAnalyzer::FrameMap *blankMap, long long nframes,
54  const unsigned char *median, const float *stddev,
55  const unsigned char *monochromatic)
56 {
57  /*
58  * Select a "black" value based on a curve, to deal with varying "black"
59  * levels.
60  */
61  const unsigned char MINBLANKMEDIAN = 1;
62  const unsigned char MAXBLANKMEDIAN = 96;
63  const float MEDIANPCTILE = 0.95;
64  const float STDDEVPCTILE = 0.85;
65 
66  long long frameno = 1;
67  long long segb = 0;
68  long long sege = 0;
69 
70  /* Count and select for monochromatic frames. */
71 
72  long long nblanks = 0;
73  for (frameno = 0; frameno < nframes; frameno++)
74  {
75  if (monochromatic[frameno] && pickmedian(median[frameno],
76  MINBLANKMEDIAN, MAXBLANKMEDIAN))
77  nblanks++;
78  }
79 
80  if (!nblanks)
81  {
82  /* No monochromatic frames. */
83  LOG(VB_COMMFLAG, LOG_INFO,
84  "BlankFrameDetector::computeBlankMap: No blank frames.");
85  return;
86  }
87 
88  /* Select percentile values from monochromatic frames. */
89 
90  auto *blankmedian = new unsigned char[nblanks];
91  auto *blankstddev = new float[nblanks];
92  long long blankno = 0;
93  for (frameno = 0; frameno < nframes; frameno++)
94  {
95  if (monochromatic[frameno] && pickmedian(median[frameno],
96  MINBLANKMEDIAN, MAXBLANKMEDIAN))
97  {
98  blankmedian[blankno] = median[frameno];
99  blankstddev[blankno] = stddev[frameno];
100  blankno++;
101  }
102  }
103 
104  qsort(blankmedian, nblanks, sizeof(*blankmedian), sort_ascending_uchar);
105  blankno = min(nblanks - 1, (long long)roundf(nblanks * MEDIANPCTILE));
106  uchar maxmedian = blankmedian[blankno];
107 
108  qsort(blankstddev, nblanks, sizeof(*blankstddev), sort_ascending_float);
109  long long stddevno = min(nblanks - 1, (long long)roundf(nblanks * STDDEVPCTILE));
110  float maxstddev = blankstddev[stddevno];
111 
112  /* Determine effective percentile ranges (for debugging). */
113 
114  long long blankno1 = blankno;
115  long long blankno2 = blankno;
116  while (blankno1 > 0 && blankmedian[blankno1] == maxmedian)
117  blankno1--;
118  if (blankmedian[blankno1] != maxmedian)
119  blankno1++;
120  while (blankno2 < nblanks && blankmedian[blankno2] == maxmedian)
121  blankno2++;
122  if (blankno2 == nblanks)
123  blankno2--;
124 
125  long long stddevno1 = stddevno;
126  long long stddevno2 = stddevno;
127  while (stddevno1 > 0 && blankstddev[stddevno1] == maxstddev)
128  stddevno1--;
129  if (blankstddev[stddevno1] != maxstddev)
130  stddevno1++;
131  while (stddevno2 < nblanks && blankstddev[stddevno2] == maxstddev)
132  stddevno2++;
133  if (stddevno2 == nblanks)
134  stddevno2--;
135 
136  LOG(VB_COMMFLAG, LOG_INFO,
137  QString("Blanks selecting median<=%1 (%2-%3%), stddev<=%4 (%5-%6%)")
138  .arg(maxmedian)
139  .arg(blankno1 * 100 / nblanks).arg(blankno2 * 100 / nblanks)
140  .arg(maxstddev)
141  .arg(stddevno1 * 100 / nblanks).arg(stddevno2 * 100 / nblanks));
142 
143  delete []blankmedian;
144  delete []blankstddev;
145 
146  blankMap->clear();
147  if (monochromatic[0] && isBlank(median[0], stddev[0], maxmedian, maxstddev))
148  {
149  segb = 0;
150  sege = 0;
151  }
152  else
153  {
154  /* Fake up a dummy blank frame for interval calculations. */
155  blankMap->insert(0, 0);
156  segb = -1;
157  sege = -1;
158  }
159  for (frameno = 1; frameno < nframes; frameno++)
160  {
161  if (monochromatic[frameno] && isBlank(median[frameno], stddev[frameno],
162  maxmedian, maxstddev))
163  {
164  /* Blank frame. */
165  if (sege < frameno - 1)
166  {
167  /* Start counting. */
168  segb = frameno;
169  sege = frameno;
170  }
171  else
172  {
173  /* Continue counting. */
174  sege = frameno;
175  }
176  }
177  else if (sege == frameno - 1)
178  {
179  /* Transition to non-blank frame. */
180  long long seglen = frameno - segb;
181  blankMap->insert(segb, seglen);
182  }
183  }
184  if (sege == frameno - 1)
185  {
186  /* Possibly ending on blank frames. */
187  long long seglen = frameno - segb;
188  blankMap->insert(segb, seglen);
189  }
190 
191  FrameAnalyzer::FrameMap::Iterator iiblank = blankMap->end();
192  --iiblank;
193  if (iiblank.key() + *iiblank < nframes)
194  {
195  /*
196  * Didn't end on blank frames, so add a dummy blank frame at the
197  * end.
198  */
199  blankMap->insert(nframes - 1, 0);
200  }
201 }
202 
203 void
204 computeBreakMap(FrameAnalyzer::FrameMap *breakMap,
205  const FrameAnalyzer::FrameMap *blankMap, float fps,
206  int debugLevel)
207 {
208  /*
209  * TUNABLE:
210  *
211  * Common commercial-break lengths.
212  */
213  static constexpr struct {
214  int m_len; /* seconds */
215  int m_delta; /* seconds */
216  } kBreakType[] = {
217  /* Sort by "len". */
218  { 15, 2 },
219  { 20, 2 },
220  { 30, 5 },
221  { 60, 5 },
222  };
223 
224  /*
225  * TUNABLE:
226  *
227  * Shortest non-commercial length, used to coalesce consecutive commercial
228  * breaks that are usually identified due to in-commercial cuts.
229  */
230  static const int kMinContentLen = (int)roundf(10 * fps);
231 
232  breakMap->clear();
233  for (FrameAnalyzer::FrameMap::const_iterator iiblank = blankMap->begin();
234  iiblank != blankMap->end();
235  ++iiblank)
236  {
237  long long brkb = iiblank.key();
238  long long iilen = *iiblank;
239  long long start = brkb + iilen / 2;
240 
241  for (auto type : kBreakType)
242  {
243  /* Look for next blank frame that is an acceptable distance away. */
244  FrameAnalyzer::FrameMap::const_iterator jjblank = iiblank;
245  for (++jjblank; jjblank != blankMap->end(); ++jjblank)
246  {
247  long long brke = jjblank.key();
248  long long jjlen = *jjblank;
249  long long end = brke + jjlen / 2;
250 
251  auto testlen = (long long)roundf((end - start) / fps);
252  if (testlen > type.m_len + type.m_delta)
253  break; /* Too far ahead; break to next break length. */
254 
255  long long delta = testlen - type.m_len;
256  if (delta < 0)
257  delta = 0 - delta;
258 
259  if (delta > type.m_delta)
260  continue; /* Outside delta range; try next end-blank. */
261 
262  /* Mark this commercial break. */
263  bool inserted = false;
264  for (unsigned int jj = 0;; jj++)
265  {
266  long long newbrkb = brkb + jj;
267  if (newbrkb >= brke)
268  {
269  LOG(VB_COMMFLAG, LOG_INFO,
270  QString("BF [%1,%2] ran out of slots")
271  .arg(brkb).arg(brke - 1));
272  break;
273  }
274  if (breakMap->find(newbrkb) == breakMap->end())
275  {
276  breakMap->insert(newbrkb, brke - newbrkb);
277  inserted = true;
278  break;
279  }
280  }
281  if (inserted)
282  break; /* next break type */
283  }
284  }
285  }
286 
287  if (debugLevel >= 1)
288  {
289  frameAnalyzerReportMap(breakMap, fps, "BF Break");
290  LOG(VB_COMMFLAG, LOG_INFO,
291  "BF coalescing overlapping/nearby breaks ...");
292  }
293 
294  /*
295  * Coalesce overlapping or very-nearby breaks (handles cut-scenes within a
296  * commercial).
297  */
298  for (;;)
299  {
300  bool coalesced = false;
301  FrameAnalyzer::FrameMap::iterator iibreak = breakMap->begin();
302  while (iibreak != breakMap->end())
303  {
304  long long iib = iibreak.key();
305  long long iie = iib + *iibreak;
306 
307  FrameAnalyzer::FrameMap::iterator jjbreak = iibreak;
308  ++jjbreak;
309  if (jjbreak == breakMap->end())
310  break;
311 
312  long long jjb = jjbreak.key();
313  long long jje = jjb + *jjbreak;
314 
315  if (jjb < iib)
316  {
317  /* (jjb,jje) is behind (iib,iie). */
318  ++iibreak;
319  continue;
320  }
321 
322  if (iie + kMinContentLen < jjb)
323  {
324  /* (jjb,jje) is too far ahead. */
325  ++iibreak;
326  continue;
327  }
328 
329  /* Coalesce. */
330  if (jje > iie)
331  {
332  breakMap->remove(iib); /* overlap */
333  breakMap->insert(iib, jje - iib); /* overlap */
334  }
335  breakMap->erase(jjbreak);
336  coalesced = true;
337  iibreak = breakMap->find(iib);
338  }
339  if (!coalesced)
340  break;
341  }
342 
343  /* Adjust for blank intervals. */
344  FrameAnalyzer::FrameMap::iterator iibreak = breakMap->begin();
345  while (iibreak != breakMap->end())
346  {
347  long long iib = iibreak.key();
348  long long iie = iib + *iibreak;
349  FrameAnalyzer::FrameMap::iterator jjbreak = iibreak;
350  ++jjbreak;
351  breakMap->erase(iibreak);
352 
353  /* Trim leading blanks from commercial break. */
354  long long addb = *blankMap->find(iib);
355  addb = addb / 2;
356  if (addb > MAX_BLANK_FRAMES)
357  addb = MAX_BLANK_FRAMES;
358  iib += addb;
359  /* Add trailing blanks to commercial break. */
360  long long adde = *blankMap->find(iie);
361  iie += adde;
362  long long sube = adde / 2;
363  if (sube > MAX_BLANK_FRAMES)
364  sube = MAX_BLANK_FRAMES;
365  iie -= sube;
366  breakMap->insert(iib, iie - iib);
367  iibreak = jjbreak;
368  }
369 }
370 
371 }; /* namespace */
372 
374  : m_histogramAnalyzer(ha)
375 {
376  /*
377  * debugLevel:
378  * 0: no debugging
379  * 2: extra verbosity [O(nframes)]
380  */
381  m_debugLevel = gCoreContext->GetNumSetting("BlankFrameDetectorDebugLevel", 0);
382 
383  if (m_debugLevel >= 1)
384  createDebugDirectory(debugdir,
385  QString("BlankFrameDetector debugLevel %1").arg(m_debugLevel));
386 }
387 
390 {
392  m_histogramAnalyzer->MythPlayerInited(player, nframes);
393 
394  m_fps = player->GetFrameRate();
395 
396  QSize video_disp_dim = player->GetVideoSize();
397 
398  LOG(VB_COMMFLAG, LOG_INFO,
399  QString("BlankFrameDetector::MythPlayerInited %1x%2")
400  .arg(video_disp_dim.width())
401  .arg(video_disp_dim.height()));
402 
403  return ares;
404 }
405 
407 BlankFrameDetector::analyzeFrame(const VideoFrame *frame, long long frameno,
408  long long *pNextFrame)
409 {
410  *pNextFrame = kNextFrame;
411 
412  if (m_histogramAnalyzer->analyzeFrame(frame, frameno) ==
414  return ANALYZE_OK;
415 
416  LOG(VB_COMMFLAG, LOG_INFO,
417  QString("BlankFrameDetector::analyzeFrame error at frame %1")
418  .arg(frameno));
419  return ANALYZE_ERROR;
420 }
421 
422 int
423 BlankFrameDetector::finished(long long nframes, bool final)
424 {
425  if (m_histogramAnalyzer->finished(nframes, final))
426  return -1;
427 
428  LOG(VB_COMMFLAG, LOG_INFO, QString("BlankFrameDetector::finished(%1)")
429  .arg(nframes));
430 
431  /* Identify all sequences of blank frames (blankMap). */
432  computeBlankMap(&m_blankMap, nframes,
435  if (m_debugLevel >= 2)
437 
438  return 0;
439 }
440 
441 int
443  const TemplateMatcher *templateMatcher)
444 {
445  /*
446  * See TemplateMatcher::templateCoverage; some commercial breaks have
447  * logos. Conversely, any logo breaks are probably really breaks, so prefer
448  * those over blank-frame-calculated breaks.
449  */
450  const FrameAnalyzer::FrameMap *logoBreakMap = templateMatcher->getBreaks();
451 
452  /* TUNABLE: see TemplateMatcher::adjustForBlanks */
453  const int MAXBLANKADJUSTMENT = (int)roundf(5 * m_fps); /* frames */
454 
455  LOG(VB_COMMFLAG, LOG_INFO, "BlankFrameDetector adjusting for logo surplus");
456 
457  /*
458  * For each logo break, find the blank frames closest to its beginning and
459  * end. This helps properly support CommSkipAllBlanks.
460  */
461  for (FrameAnalyzer::FrameMap::const_iterator ii =
462  logoBreakMap->constBegin();
463  ii != logoBreakMap->constEnd();
464  ++ii)
465  {
466  /* Get bounds of beginning of logo break. */
467  long long iikey = ii.key();
468  long long iibb = iikey - MAXBLANKADJUSTMENT;
469  long long iiee = iikey + MAXBLANKADJUSTMENT;
470  FrameAnalyzer::FrameMap::Iterator jjfound = m_blankMap.end();
471 
472  /* Look for a blank frame near beginning of logo break. */
473  for (auto jj = m_blankMap.begin(); jj != m_blankMap.end(); ++jj)
474  {
475  long long jjbb = jj.key();
476  long long jjee = jjbb + *jj;
477 
478  if (iiee < jjbb)
479  break; /* No nearby blank frames. */
480 
481  if (jjee < iibb)
482  continue; /* Too early; keep looking. */
483 
484  jjfound = jj;
485  if (iikey <= jjbb)
486  {
487  /*
488  * Prefer the first blank frame beginning after the logo break
489  * begins.
490  */
491  break;
492  }
493  }
494 
495  /* Adjust blank frame to begin with logo break beginning. */
496  if (jjfound != m_blankMap.end())
497  {
498  long long jjee = jjfound.key() + *jjfound;
499  m_blankMap.erase(jjfound);
500  if (jjee <= iikey)
501  {
502  /* Move blank frame to beginning of logo break. */
503  m_blankMap.remove(iikey);
504  m_blankMap.insert(iikey, 1);
505  }
506  else
507  {
508  /* Adjust blank frame to begin with logo break. */
509  m_blankMap.insert(iikey, jjee - iikey);
510  }
511  }
512 
513  /* Get bounds of end of logo break. */
514  long long kkkey = ii.key() + *ii;
515  long long kkbb = kkkey - MAXBLANKADJUSTMENT;
516  long long kkee = kkkey + MAXBLANKADJUSTMENT;
517  FrameAnalyzer::FrameMap::Iterator mmfound = m_blankMap.end();
518 
519  /* Look for a blank frame near end of logo break. */
520  for (auto mm = m_blankMap.begin(); mm != m_blankMap.end(); ++mm)
521  {
522  long long mmbb = mm.key();
523  long long mmee = mmbb + *mm;
524 
525  if (kkee < mmbb)
526  break; /* No nearby blank frames. */
527 
528  if (mmee < kkbb)
529  continue; /* Too early; keep looking. */
530 
531  /* Prefer the last blank frame ending before the logo break ends. */
532  if (mmee < kkkey || mmfound == m_blankMap.end())
533  mmfound = mm;
534  if (mmee >= kkkey)
535  break;
536  }
537 
538  /* Adjust blank frame to end with logo break end. */
539  if (mmfound != m_blankMap.end())
540  {
541  long long mmbb = mmfound.key();
542  if (mmbb < kkkey)
543  {
544  /* Adjust blank frame to end with logo break. */
545  m_blankMap.remove(mmbb);
546  m_blankMap.insert(mmbb, kkkey - mmbb);
547  }
548  else
549  {
550  /* Move blank frame to end of logo break. */
551  m_blankMap.erase(mmfound);
552  m_blankMap.remove(kkkey - 1);
553  m_blankMap.insert(kkkey - 1, 1);
554  }
555  }
556  }
557 
558  /*
559  * Compute breaks (breakMap).
560  */
561  computeBreakMap(&m_breakMap, &m_blankMap, m_fps, m_debugLevel);
562 
563  /*
564  * Expand blank-frame breaks to fully include overlapping logo breaks.
565  * Fully include logo breaks that don't include any blank-frame breaks.
566  */
567  for (FrameAnalyzer::FrameMap::const_iterator ii =
568  logoBreakMap->constBegin();
569  ii != logoBreakMap->constEnd();
570  ++ii)
571  {
572  long long iibb = ii.key();
573  long long iiee = iibb + *ii;
574  bool overlap = false;
575 
576  for (auto jj = m_breakMap.begin(); jj != m_breakMap.end(); )
577  {
578  long long jjbb = jj.key();
579  long long jjee = jjbb + *jj;
580  FrameAnalyzer::FrameMap::Iterator jjnext = jj;
581  ++jjnext;
582 
583  if (iiee < jjbb)
584  {
585  if (!overlap)
586  {
587  /* Fully incorporate logo break */
588  m_breakMap.insert(iibb, iiee - iibb);
589  }
590  break;
591  }
592 
593  if (iibb < jjbb && jjbb < iiee)
594  {
595  /* End of logo break includes beginning of blank-frame break. */
596  overlap = true;
597  m_breakMap.erase(jj);
598  m_breakMap.insert(iibb, max(iiee, jjee) - iibb);
599  }
600  else if (jjbb < iibb && iibb < jjee)
601  {
602  /* End of blank-frame break includes beginning of logo break. */
603  overlap = true;
604  if (jjee < iiee)
605  {
606  m_breakMap.remove(jjbb);
607  m_breakMap.insert(jjbb, iiee - jjbb);
608  }
609  }
610 
611  jj = jjnext;
612  }
613  }
614 
615  frameAnalyzerReportMap(&m_breakMap, m_fps, "BF Break");
616  return 0;
617 }
618 
619 int
621  const TemplateMatcher *templateMatcher)
622 {
623  (void)templateMatcher; /* gcc */
624 
625  LOG(VB_COMMFLAG, LOG_INFO, "BlankFrameDetector adjusting for "
626  "too little logo coverage (unimplemented)");
627  return 0;
628 }
629 
630 int
632 {
633  if (m_breakMap.empty())
634  {
635  /* Compute breaks (m_breakMap). */
636  computeBreakMap(&m_breakMap, &m_blankMap, m_fps, m_debugLevel);
637  frameAnalyzerReportMap(&m_breakMap, m_fps, "BF Break");
638  }
639 
640  breaks->clear();
641  for (auto bb = m_breakMap.begin(); bb != m_breakMap.end(); ++bb)
642  breaks->insert(bb.key(), *bb);
643 
644  return 0;
645 }
646 
647 int
649 {
651 }
652 
653 /* vim: set expandtab tabstop=4 shiftwidth=4: */
#define MAX_BLANK_FRAMES
const unsigned char * getMonochromatics(void) const
int finished(long long nframes, bool final)
int reportTime(void) const override
static const long long kNextFrame
Definition: FrameAnalyzer.h:57
int reportTime(void) const
MythCoreContext * gCoreContext
This global variable contains the MythCoreContext instance for the app.
BlankFrameDetector(HistogramAnalyzer *ha, const QString &debugdir)
FrameAnalyzer::FrameMap m_blankMap
HistogramAnalyzer * m_histogramAnalyzer
QSize GetVideoSize(void) const
Definition: mythplayer.h:211
const FrameAnalyzer::FrameMap * getBreaks(void) const
int finished(long long nframes, bool final) override
enum analyzeFrameResult MythPlayerInited(MythPlayer *player, long long nframes) override
int computeForLogoSurplus(const TemplateMatcher *templateMatcher)
float GetFrameRate(void) const
Definition: mythplayer.h:213
enum analyzeFrameResult analyzeFrame(const VideoFrame *frame, long long frameno, long long *pNextFrame) override
enum FrameAnalyzer::analyzeFrameResult analyzeFrame(const VideoFrame *frame, long long frameno)
void frameAnalyzerReportMap(const FrameAnalyzer::FrameMap *frameMap, float fps, const char *comment)
int GetNumSetting(const QString &key, int defaultval=0)
QMap< long long, long long > FrameMap
Definition: FrameAnalyzer.h:43
void createDebugDirectory(const QString &dirname, const QString &comment)
#define LOG(_MASK_, _LEVEL_, _STRING_)
Definition: mythlogging.h:41
const unsigned char * getMedians(void) const
enum FrameAnalyzer::analyzeFrameResult MythPlayerInited(MythPlayer *player, long long nframes)
static int computeForLogoDeficit(const TemplateMatcher *templateMatcher)
const float * getStdDevs(void) const
FrameAnalyzer::FrameMap m_breakMap
void frameAnalyzerReportMapms(const FrameAnalyzer::FrameMap *frameMap, float fps, const char *comment)
int computeBreaks(FrameMap *breaks)