MythTV: BlankFrameDetector.cpp Source File

00001 // ANSI C headers
00002 #include <cstdlib>
00003 #include <cmath>
00004 
00005 // MythTV headers
00006 #include "mythcorecontext.h"    /* gContext */
00007 #include "mythplayer.h"
00008 
00009 // Commercial Flagging headers
00010 #include "CommDetector2.h"
00011 #include "FrameAnalyzer.h"
00012 #include "quickselect.h"
00013 #include "HistogramAnalyzer.h"
00014 #include "BlankFrameDetector.h"
00015 #include "TemplateMatcher.h"
00016 
00017 using namespace commDetector2;
00018 using namespace frameAnalyzer;
00019 
00020 namespace {
00021 
00022 bool
00023 isBlank(unsigned char median, float stddev, unsigned char maxmedian,
00024         float maxstddev)
00025 {
00026     return ((median < maxmedian) ||
00027             ((median == maxmedian) && (stddev <= maxstddev)));
00028 }
00029 
00030 int
00031 sort_ascending_uchar(const void *aa, const void *bb)
00032 {
00033     return *(unsigned char*)aa - *(unsigned char*)bb;
00034 }
00035 
00036 int
00037 sort_ascending_float(const void *aa, const void *bb)
00038 {
00039     float faa = *(float*)aa;
00040     float fbb = *(float*)bb;
00041     return faa < fbb ? -1 : faa == fbb ? 0 : 1;
00042 }
00043 
00044 bool
00045 pickmedian(const unsigned char medianval,
00046         unsigned char minval, unsigned char maxval)
00047 {
00048     return medianval >= minval && medianval <= maxval;
00049 }
00050 
00051 void
00052 computeBlankMap(FrameAnalyzer::FrameMap *blankMap, long long nframes,
00053         const unsigned char *median, const float *stddev,
00054         const unsigned char *monochromatic)
00055 {
00056     /*
00057      * Select a "black" value based on a curve, to deal with varying "black"
00058      * levels.
00059      */
00060     const unsigned char     MINBLANKMEDIAN = 1;
00061     const unsigned char     MAXBLANKMEDIAN = 96;
00062     const float             MEDIANPCTILE = 0.95;
00063     const float             STDDEVPCTILE = 0.85;
00064 
00065     long long       frameno, segb, sege, nblanks;
00066     long long       blankno, blankno1, blankno2;
00067     long long       stddevno, stddevno1, stddevno2;
00068     unsigned char   *blankmedian, maxmedian;
00069     float           *blankstddev, maxstddev;
00070 
00071     /* Count and select for monochromatic frames. */
00072 
00073     nblanks = 0;
00074     for (frameno = 0; frameno < nframes; frameno++)
00075     {
00076         if (monochromatic[frameno] && pickmedian(median[frameno],
00077                     MINBLANKMEDIAN, MAXBLANKMEDIAN))
00078             nblanks++;
00079     }
00080 
00081     if (!nblanks)
00082     {
00083         /* No monochromatic frames. */
00084         LOG(VB_COMMFLAG, LOG_INFO,
00085             "BlankFrameDetector::computeBlankMap: No blank frames.");
00086         return;
00087     }
00088 
00089     /* Select percentile values from monochromatic frames. */
00090 
00091     blankmedian = new unsigned char[nblanks];
00092     blankstddev = new float[nblanks];
00093     blankno = 0;
00094     for (frameno = 0; frameno < nframes; frameno++)
00095     {
00096         if (monochromatic[frameno] && pickmedian(median[frameno],
00097                     MINBLANKMEDIAN, MAXBLANKMEDIAN))
00098         {
00099             blankmedian[blankno] = median[frameno];
00100             blankstddev[blankno] = stddev[frameno];
00101             blankno++;
00102         }
00103     }
00104 
00105     qsort(blankmedian, nblanks, sizeof(*blankmedian), sort_ascending_uchar);
00106     blankno = min(nblanks - 1, (long long)roundf(nblanks * MEDIANPCTILE));
00107     maxmedian = blankmedian[blankno];
00108 
00109     qsort(blankstddev, nblanks, sizeof(*blankstddev), sort_ascending_float);
00110     stddevno = min(nblanks - 1, (long long)roundf(nblanks * STDDEVPCTILE));
00111     maxstddev = blankstddev[stddevno];
00112 
00113     /* Determine effective percentile ranges (for debugging). */
00114 
00115     blankno1 = blankno;
00116     blankno2 = blankno;
00117     while (blankno1 > 0 && blankmedian[blankno1] == maxmedian)
00118         blankno1--;
00119     if (blankmedian[blankno1] != maxmedian)
00120         blankno1++;
00121     while (blankno2 < nblanks && blankmedian[blankno2] == maxmedian)
00122         blankno2++;
00123     if (blankno2 == nblanks)
00124         blankno2--;
00125 
00126     stddevno1 = stddevno;
00127     stddevno2 = stddevno;
00128     while (stddevno1 > 0 && blankstddev[stddevno1] == maxstddev)
00129         stddevno1--;
00130     if (blankstddev[stddevno1] != maxstddev)
00131         stddevno1++;
00132     while (stddevno2 < nblanks && blankstddev[stddevno2] == maxstddev)
00133         stddevno2++;
00134     if (stddevno2 == nblanks)
00135         stddevno2--;
00136 
00137     LOG(VB_COMMFLAG, LOG_INFO,
00138         QString("Blanks selecting median<=%1 (%2-%3%), stddev<=%4 (%5-%6%)")
00139             .arg(maxmedian)
00140             .arg(blankno1 * 100 / nblanks).arg(blankno2 * 100 / nblanks)
00141             .arg(maxstddev)
00142             .arg(stddevno1 * 100 / nblanks).arg(stddevno2 * 100 / nblanks));
00143 
00144     delete []blankmedian;
00145     delete []blankstddev;
00146 
00147     blankMap->clear();
00148     if (monochromatic[0] && isBlank(median[0], stddev[0], maxmedian, maxstddev))
00149     {
00150         segb = 0;
00151         sege = 0;
00152     }
00153     else
00154     {
00155         /* Fake up a dummy blank frame for interval calculations. */
00156         blankMap->insert(0, 0);
00157         segb = -1;
00158         sege = -1;
00159     }
00160     for (frameno = 1; frameno < nframes; frameno++)
00161     {
00162         if (monochromatic[frameno] && isBlank(median[frameno], stddev[frameno],
00163                     maxmedian, maxstddev))
00164         {
00165             /* Blank frame. */
00166             if (sege < frameno - 1)
00167             {
00168                 /* Start counting. */
00169                 segb = frameno;
00170                 sege = frameno;
00171             }
00172             else
00173             {
00174                 /* Continue counting. */
00175                 sege = frameno;
00176             }
00177         }
00178         else if (sege == frameno - 1)
00179         {
00180             /* Transition to non-blank frame. */
00181             long long seglen = frameno - segb;
00182             blankMap->insert(segb, seglen);
00183         }
00184     }
00185     if (sege == frameno - 1)
00186     {
00187         /* Possibly ending on blank frames. */
00188         long long seglen = frameno - segb;
00189         blankMap->insert(segb, seglen);
00190     }
00191 
00192     FrameAnalyzer::FrameMap::Iterator iiblank = blankMap->end();
00193     --iiblank;
00194     if (iiblank.key() + *iiblank < nframes)
00195     {
00196         /*
00197          * Didn't end on blank frames, so add a dummy blank frame at the
00198          * end.
00199          */
00200         blankMap->insert(nframes - 1, 0);
00201     }
00202 }
00203 
00204 void
00205 computeBreakMap(FrameAnalyzer::FrameMap *breakMap,
00206         const FrameAnalyzer::FrameMap *blankMap, float fps,
00207         int debugLevel)
00208 {
00209     /*
00210      * TUNABLE:
00211      *
00212      * Common commercial-break lengths.
00213      */
00214     static const struct {
00215         int     len;    /* seconds */
00216         int     delta;  /* seconds */
00217     } breaktype[] = {
00218         /* Sort by "len". */
00219         { 15,   2 },
00220         { 20,   2 },
00221         { 30,   5 },
00222         { 60,   5 },
00223     };
00224     static const unsigned int   nbreaktypes =
00225         sizeof(breaktype)/sizeof(*breaktype);
00226 
00227     /*
00228      * TUNABLE:
00229      *
00230      * Shortest non-commercial length, used to coalesce consecutive commercial
00231      * breaks that are usually identified due to in-commercial cuts.
00232      */
00233     static const int MINCONTENTLEN = (int)roundf(10 * fps);
00234 
00235     breakMap->clear();
00236     for (FrameAnalyzer::FrameMap::const_iterator iiblank = blankMap->begin();
00237             iiblank != blankMap->end();
00238             ++iiblank)
00239     {
00240         long long brkb = iiblank.key();
00241         long long iilen = *iiblank;
00242         long long start = brkb + iilen / 2;
00243 
00244         for (unsigned int ii = 0; ii < nbreaktypes; ii++)
00245         {
00246             /* Look for next blank frame that is an acceptable distance away. */
00247             FrameAnalyzer::FrameMap::const_iterator jjblank = iiblank;
00248             for (++jjblank; jjblank != blankMap->end(); ++jjblank)
00249             {
00250                 long long brke = jjblank.key();
00251                 long long jjlen = *jjblank;
00252                 long long end = brke + jjlen / 2;
00253 
00254                 long long testlen = (long long)roundf((end - start) / fps);
00255                 if (testlen > breaktype[ii].len + breaktype[ii].delta)
00256                     break;      /* Too far ahead; break to next break length. */
00257 
00258                 long long delta = testlen - breaktype[ii].len;
00259                 if (delta < 0)
00260                     delta = 0 - delta;
00261 
00262                 if (delta > breaktype[ii].delta)
00263                     continue;   /* Outside delta range; try next end-blank. */
00264 
00265                 /* Mark this commercial break. */
00266                 bool inserted = false;
00267                 for (unsigned int jj = 0;; jj++)
00268                 {
00269                     long long newbrkb = brkb + jj;
00270                     if (newbrkb >= brke)
00271                     {
00272                         LOG(VB_COMMFLAG, LOG_INFO,
00273                             QString("BF [%1,%2] ran out of slots")
00274                                 .arg(brkb).arg(brke - 1));
00275                         break;
00276                     }
00277                     if (breakMap->find(newbrkb) == breakMap->end())
00278                     {
00279                         breakMap->insert(newbrkb, brke - newbrkb);
00280                         inserted = true;
00281                         break;
00282                     }
00283                 }
00284                 if (inserted)
00285                     break;  /* next break type */
00286             }
00287         }
00288     }
00289 
00290     if (debugLevel >= 1)
00291     {
00292         frameAnalyzerReportMap(breakMap, fps, "BF Break");
00293         LOG(VB_COMMFLAG, LOG_INFO,
00294             "BF coalescing overlapping/nearby breaks ...");
00295     }
00296 
00297     /*
00298      * Coalesce overlapping or very-nearby breaks (handles cut-scenes within a
00299      * commercial).
00300      */
00301     for (;;)
00302     {
00303         bool coalesced = false;
00304         FrameAnalyzer::FrameMap::iterator iibreak = breakMap->begin();
00305         while (iibreak != breakMap->end())
00306         {
00307             long long iib = iibreak.key();
00308             long long iie = iib + *iibreak;
00309 
00310             FrameAnalyzer::FrameMap::iterator jjbreak = iibreak;
00311             ++jjbreak;
00312             if (jjbreak == breakMap->end())
00313                 break;
00314 
00315             long long jjb = jjbreak.key();
00316             long long jje = jjb + *jjbreak;
00317 
00318             if (jjb < iib)
00319             {
00320                 /* (jjb,jje) is behind (iib,iie). */
00321                 ++iibreak;
00322                 continue;
00323             }
00324 
00325             if (iie + MINCONTENTLEN < jjb)
00326             {
00327                 /* (jjb,jje) is too far ahead. */
00328                 ++iibreak;
00329                 continue;
00330             }
00331 
00332             /* Coalesce. */
00333             if (jje > iie)
00334             {
00335                 breakMap->remove(iib);             /* overlap */
00336                 breakMap->insert(iib, jje - iib);  /* overlap */
00337             }
00338             breakMap->erase(jjbreak);
00339             coalesced = true;
00340             iibreak = breakMap->find(iib);
00341         }
00342         if (!coalesced)
00343             break;
00344     }
00345 
00346     /* Adjust for blank intervals. */
00347     FrameAnalyzer::FrameMap::iterator iibreak = breakMap->begin();
00348     while (iibreak != breakMap->end())
00349     {
00350         long long iib = iibreak.key();
00351         long long iie = iib + *iibreak;
00352         FrameAnalyzer::FrameMap::iterator jjbreak = iibreak;
00353         ++jjbreak;
00354         breakMap->erase(iibreak);
00355 
00356         /* Trim leading blanks from commercial break. */
00357         long long addb = *blankMap->find(iib);
00358         addb = addb / 2;
00359         if (addb > MAX_BLANK_FRAMES)
00360             addb = MAX_BLANK_FRAMES;
00361         iib += addb;
00362         /* Add trailing blanks to commercial break. */
00363         long long adde = *blankMap->find(iie);
00364         iie += adde;
00365         long long sube = adde / 2;
00366         if (sube > MAX_BLANK_FRAMES)
00367             sube = MAX_BLANK_FRAMES;
00368         iie -= sube;
00369         breakMap->insert(iib, iie - iib);
00370         iibreak = jjbreak;
00371     }
00372 }
00373 
00374 };  /* namespace */
00375 
00376 BlankFrameDetector::BlankFrameDetector(HistogramAnalyzer *ha, QString debugdir)
00377     : FrameAnalyzer()
00378     , histogramAnalyzer(ha)
00379     , fps(0.0f)
00380     , debugLevel(0)
00381 {
00382     /*
00383      * debugLevel:
00384      *      0: no debugging
00385      *      2: extra verbosity [O(nframes)]
00386      */
00387     debugLevel = gCoreContext->GetNumSetting("BlankFrameDetectorDebugLevel", 0);
00388 
00389     if (debugLevel >= 1)
00390         createDebugDirectory(debugdir,
00391             QString("BlankFrameDetector debugLevel %1").arg(debugLevel));
00392 }
00393 
00394 enum FrameAnalyzer::analyzeFrameResult
00395 BlankFrameDetector::MythPlayerInited(MythPlayer *player, long long nframes)
00396 {
00397     FrameAnalyzer::analyzeFrameResult ares =
00398         histogramAnalyzer->MythPlayerInited(player, nframes);
00399 
00400     fps = player->GetFrameRate();
00401 
00402     QSize video_disp_dim = player->GetVideoSize();
00403 
00404     LOG(VB_COMMFLAG, LOG_INFO,
00405         QString("BlankFrameDetector::MythPlayerInited %1x%2")
00406             .arg(video_disp_dim.width())
00407             .arg(video_disp_dim.height()));
00408 
00409     return ares;
00410 }
00411 
00412 enum FrameAnalyzer::analyzeFrameResult
00413 BlankFrameDetector::analyzeFrame(const VideoFrame *frame, long long frameno,
00414         long long *pNextFrame)
00415 {
00416     *pNextFrame = NEXTFRAME;
00417 
00418     if (histogramAnalyzer->analyzeFrame(frame, frameno) ==
00419             FrameAnalyzer::ANALYZE_OK)
00420         return ANALYZE_OK;
00421 
00422     LOG(VB_COMMFLAG, LOG_INFO,
00423         QString("BlankFrameDetector::analyzeFrame error at frame %1")
00424             .arg(frameno));
00425     return ANALYZE_ERROR;
00426 }
00427 
00428 int
00429 BlankFrameDetector::finished(long long nframes, bool final)
00430 {
00431     if (histogramAnalyzer->finished(nframes, final))
00432         return -1;
00433 
00434     LOG(VB_COMMFLAG, LOG_INFO, QString("BlankFrameDetector::finished(%1)")
00435             .arg(nframes));
00436 
00437     /* Identify all sequences of blank frames (blankMap). */
00438     computeBlankMap(&blankMap, nframes,
00439             histogramAnalyzer->getMedians(), histogramAnalyzer->getStdDevs(),
00440             histogramAnalyzer->getMonochromatics());
00441     if (debugLevel >= 2)
00442         frameAnalyzerReportMapms(&blankMap, fps, "BF Blank");
00443 
00444     return 0;
00445 }
00446 
00447 int
00448 BlankFrameDetector::computeForLogoSurplus(
00449         const TemplateMatcher *templateMatcher)
00450 {
00451     /*
00452      * See TemplateMatcher::templateCoverage; some commercial breaks have
00453      * logos. Conversely, any logo breaks are probably really breaks, so prefer
00454      * those over blank-frame-calculated breaks.
00455      */
00456     const FrameAnalyzer::FrameMap *logoBreakMap = templateMatcher->getBreaks();
00457 
00458     /* TUNABLE: see TemplateMatcher::adjustForBlanks */
00459     const int       MAXBLANKADJUSTMENT = (int)roundf(5 * fps);  /* frames */
00460 
00461     LOG(VB_COMMFLAG, LOG_INFO, "BlankFrameDetector adjusting for logo surplus");
00462 
00463     /*
00464      * For each logo break, find the blank frames closest to its beginning and
00465      * end. This helps properly support CommSkipAllBlanks.
00466      */
00467     for (FrameAnalyzer::FrameMap::const_iterator ii =
00468                 logoBreakMap->constBegin();
00469             ii != logoBreakMap->constEnd();
00470             ++ii)
00471     {
00472         /* Get bounds of beginning of logo break. */
00473         long long iikey = ii.key();
00474         long long iibb = iikey - MAXBLANKADJUSTMENT;
00475         long long iiee = iikey + MAXBLANKADJUSTMENT;
00476         FrameAnalyzer::FrameMap::Iterator jjfound = blankMap.end();
00477 
00478         /* Look for a blank frame near beginning of logo break. */
00479         for (FrameAnalyzer::FrameMap::Iterator jj = blankMap.begin();
00480                 jj != blankMap.end();
00481                 ++jj)
00482         {
00483             long long jjbb = jj.key();
00484             long long jjee = jjbb + *jj;
00485 
00486             if (iiee < jjbb)
00487                 break;      /* No nearby blank frames. */
00488 
00489             if (jjee < iibb)
00490                 continue;   /* Too early; keep looking. */
00491 
00492             jjfound = jj;
00493             if (iikey <= jjbb)
00494             {
00495                 /*
00496                  * Prefer the first blank frame beginning after the logo break
00497                  * begins.
00498                  */
00499                 break;
00500             }
00501         }
00502 
00503         /* Adjust blank frame to begin with logo break beginning. */
00504         if (jjfound != blankMap.end())
00505         {
00506             long long jjee = jjfound.key() + *jjfound;
00507             blankMap.erase(jjfound);
00508             if (jjee <= iikey)
00509             {
00510                 /* Move blank frame to beginning of logo break. */
00511                 blankMap.remove(iikey);
00512                 blankMap.insert(iikey, 1);
00513             }
00514             else
00515             {
00516                 /* Adjust blank frame to begin with logo break. */
00517                 blankMap.insert(iikey, jjee - iikey);
00518             }
00519         }
00520 
00521         /* Get bounds of end of logo break. */
00522         long long kkkey = ii.key() + *ii;
00523         long long kkbb = kkkey - MAXBLANKADJUSTMENT;
00524         long long kkee = kkkey + MAXBLANKADJUSTMENT;
00525         FrameAnalyzer::FrameMap::Iterator mmfound = blankMap.end();
00526 
00527         /* Look for a blank frame near end of logo break. */
00528         for (FrameAnalyzer::FrameMap::Iterator mm = blankMap.begin();
00529                 mm != blankMap.end();
00530                 ++mm)
00531         {
00532             long long mmbb = mm.key();
00533             long long mmee = mmbb + *mm;
00534 
00535             if (kkee < mmbb)
00536                 break;      /* No nearby blank frames. */
00537 
00538             if (mmee < kkbb)
00539                 continue;   /* Too early; keep looking. */
00540 
00541             /* Prefer the last blank frame ending before the logo break ends. */
00542             if (mmee < kkkey || mmfound == blankMap.end())
00543                 mmfound = mm;
00544             if (mmee >= kkkey)
00545                 break;
00546         }
00547 
00548         /* Adjust blank frame to end with logo break end. */
00549         if (mmfound != blankMap.end())
00550         {
00551             long long mmbb = mmfound.key();
00552             if (mmbb < kkkey)
00553             {
00554                 /* Adjust blank frame to end with logo break. */
00555                 blankMap.remove(mmbb);
00556                 blankMap.insert(mmbb, kkkey - mmbb);
00557             }
00558             else
00559             {
00560                 /* Move blank frame to end of logo break. */
00561                 blankMap.erase(mmfound);
00562                 blankMap.remove(kkkey - 1);
00563                 blankMap.insert(kkkey - 1, 1);
00564             }
00565         }
00566     }
00567 
00568     /*
00569      * Compute breaks (breakMap).
00570      */
00571     computeBreakMap(&breakMap, &blankMap, fps, debugLevel);
00572 
00573     /*
00574      * Expand blank-frame breaks to fully include overlapping logo breaks.
00575      * Fully include logo breaks that don't include any blank-frame breaks.
00576      */
00577     for (FrameAnalyzer::FrameMap::const_iterator ii =
00578                 logoBreakMap->constBegin();
00579             ii != logoBreakMap->constEnd();
00580             ++ii)
00581     {
00582         long long iibb = ii.key();
00583         long long iiee = iibb + *ii;
00584         bool overlap = false;
00585 
00586         for (FrameAnalyzer::FrameMap::Iterator jj = breakMap.begin();
00587                 jj != breakMap.end();
00588             )
00589         {
00590             long long jjbb = jj.key();
00591             long long jjee = jjbb + *jj;
00592             FrameAnalyzer::FrameMap::Iterator jjnext = jj;
00593             ++jjnext;
00594 
00595             if (iiee < jjbb)
00596             {
00597                 if (!overlap)
00598                 {
00599                     /* Fully incorporate logo break */
00600                     breakMap.insert(iibb, iiee - iibb);
00601                 }
00602                 break;
00603             }
00604 
00605             if (iibb < jjbb && jjbb < iiee)
00606             {
00607                 /* End of logo break includes beginning of blank-frame break. */
00608                 overlap = true;
00609                 breakMap.erase(jj);
00610                 breakMap.insert(iibb, max(iiee, jjee) - iibb);
00611             }
00612             else if (jjbb < iibb && iibb < jjee)
00613             {
00614                 /* End of blank-frame break includes beginning of logo break. */
00615                 overlap = true;
00616                 if (jjee < iiee)
00617                 {
00618                     breakMap.remove(jjbb);
00619                     breakMap.insert(jjbb, iiee - jjbb);
00620                 }
00621             }
00622 
00623             jj = jjnext;
00624         }
00625     }
00626 
00627     frameAnalyzerReportMap(&breakMap, fps, "BF Break");
00628     return 0;
00629 }
00630 
00631 int
00632 BlankFrameDetector::computeForLogoDeficit(
00633         const TemplateMatcher *templateMatcher)
00634 {
00635     (void)templateMatcher;  /* gcc */
00636 
00637     LOG(VB_COMMFLAG, LOG_INFO, "BlankFrameDetector adjusting for "
00638                                "too little logo coverage (unimplemented)");
00639     return 0;
00640 }
00641 
00642 int
00643 BlankFrameDetector::computeBreaks(FrameAnalyzer::FrameMap *breaks)
00644 {
00645     if (breakMap.empty())
00646     {
00647         /* Compute breaks (breakMap). */
00648         computeBreakMap(&breakMap, &blankMap, fps, debugLevel);
00649         frameAnalyzerReportMap(&breakMap, fps, "BF Break");
00650     }
00651 
00652     breaks->clear();
00653     for (FrameAnalyzer::FrameMap::Iterator bb = breakMap.begin();
00654             bb != breakMap.end();
00655             ++bb)
00656         breaks->insert(bb.key(), *bb);
00657 
00658     return 0;
00659 }
00660 
00661 int
00662 BlankFrameDetector::reportTime(void) const
00663 {
00664     return histogramAnalyzer->reportTime();
00665 }
00666 
00667 /* vim: set expandtab tabstop=4 shiftwidth=4: */