Comparison of videos with reference frame not starting from zero

webrtc/tools/frame_analyzer/video_quality_analysis.cc

 /*
  *  Copyright (c) 2012 The WebRTC project authors. All Rights Reserved.
  *
  *  Use of this source code is governed by a BSD-style license
  *  that can be found in the LICENSE file in the root of the source
  *  tree. An additional intellectual property rights grant can be found
  *  in the file PATENTS.  All contributing project authors may
  *  be found in the AUTHORS file in the root of the source tree.
  */
 
 #include "webrtc/tools/frame_analyzer/video_quality_analysis.h"
 
 #include <assert.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <algorithm>
 #include <string>
+#include <map>
+#include <utility>
 
 #define STATS_LINE_LENGTH 32
 #define Y4M_FILE_HEADER_MAX_SIZE 200
 #define Y4M_FRAME_DELIMITER "FRAME"
 #define Y4M_FRAME_HEADER_SIZE 6
 
 namespace webrtc {
 namespace test {
 
 using std::string;
@@ skipping 190 matching lines @@
                                 src_u_b, stride_uv, src_v_b, stride_uv,
                                 width, height);
       break;
     default:
       assert(false);
   }
 
   return result;
 }
 
-void RunAnalysis(const char* reference_file_name, const char* test_file_name,
-                 const char* stats_file_name, int width, int height,
+void RunAnalysis(const char* reference_file_name,
+                 const char* test_file_name,
+                 const char* stats_file_reference_name,
+                 const char* stats_file_test_name,
+                 int width,
+                 int height,
                  ResultsContainer* results) {
   // Check if the reference_file_name ends with "y4m".
   bool y4m_mode = false;
   if (std::string(reference_file_name).find("y4m") != std::string::npos) {
     y4m_mode = true;
   }
 
   int size = GetI420FrameSize(width, height);
-  FILE* stats_file = fopen(stats_file_name, "r");
+  FILE* stats_file_ref = fopen(stats_file_reference_name, "r");
+  FILE* stats_file_test = fopen(stats_file_test_name, "r");
 
   // String buffer for the lines in the stats file.
   char line[STATS_LINE_LENGTH];
 
   // Allocate buffers for test and reference frames.
   uint8_t* test_frame = new uint8_t[size];
   uint8_t* reference_frame = new uint8_t[size];
   int previous_frame_number = -1;
 
+  // Maps barcode id to the frame id for the reference video.
+  // In case two frames have same id, then we only save the first one.

[phoglund, 2016/12/08 09:55:44]

Add: "This can happen if there are freezes in the video. There's no point to
compare the same frame twice, which is why we throw away duplicates."

[mandermo, 2016/12/08 18:08:31]

It can also happen that the camera captures two frames after each other and the
barcode did not change in between. In that case the two frames could be
different, but I choose not to handle that fully because it has some other
problems. What scenarios should we comment?

[phoglund, 2016/12/12 12:46:20]

I don't understand when you say the frames have the same barcode but is
different. You mean that the barcode pixels are the same, but other pixels in
the image change? I think the frames should be pixel identical if we capture
faster than the refresh rate. 

+  std::map<int, int> ref_barcode_to_frame;
   // While there are entries in the stats file.
-  while (GetNextStatsLine(stats_file, line)) {
+  while (GetNextStatsLine(stats_file_ref, line)) {
+    int extracted_ref_frame = ExtractFrameSequenceNumber(line);
+    int decoded_frame_number = ExtractDecodedFrameNumber(line);
+
+    // Insert will only add if it is not in map already, so we only keep first.

[phoglund, 2016/12/08 09:55:44]

nit: End this sentence at the ,

[mandermo, 2016/12/08 18:08:31]

Done.

+    ref_barcode_to_frame.insert(
+        std::make_pair(decoded_frame_number, extracted_ref_frame));
+  }
+
+  while (GetNextStatsLine(stats_file_test, line)) {
     int extracted_test_frame = ExtractFrameSequenceNumber(line);
     int decoded_frame_number = ExtractDecodedFrameNumber(line);
+    auto it = ref_barcode_to_frame.find(decoded_frame_number);
+    if (it == ref_barcode_to_frame.end()) {
+      // Not found in the reference video.
+      // TODO(mandermo) print

[phoglund, 2016/12/08 09:55:44]

Yeah, print an error here and continue. You'll have to verify manually this
doesn't happen when you deploy the change.

We could also tend to fail the tool when this happens or we fail to open files
etc, but I think continuing isn't unreasonable. If we fail to find many frames
in the ref file we should get a big drop in unique frames, and the perf sheriff
will take action. So, just add a fprintf here and remove the TODO and we're
good.

[phoglund, 2016/12/12 12:46:20]

Please address

+      continue;
+    }
+    int extracted_ref_frame = it->second;
 
     // If there was problem decoding the barcode in this frame or the frame has
     // been duplicated, continue.
     if (IsThereBarcodeError(line) ||
         decoded_frame_number == previous_frame_number) {
       continue;
     }
 
     assert(extracted_test_frame != -1);
     assert(decoded_frame_number != -1);
 
     ExtractFrameFromYuvFile(test_file_name, width, height, extracted_test_frame,
                             test_frame);
     if (y4m_mode) {
       ExtractFrameFromY4mFile(reference_file_name, width, height,
-                              decoded_frame_number, reference_frame);
+                              extracted_ref_frame, reference_frame);
     } else {
       ExtractFrameFromYuvFile(reference_file_name, width, height,
-                              decoded_frame_number, reference_frame);
+                              extracted_ref_frame, reference_frame);
     }
 
     // Calculate the PSNR and SSIM.
-    double result_psnr = CalculateMetrics(kPSNR, reference_frame, test_frame,
-                                          width, height);
-    double result_ssim = CalculateMetrics(kSSIM, reference_frame, test_frame,
-                                          width, height);
+    double result_psnr =
+        CalculateMetrics(kPSNR, reference_frame, test_frame, width, height);
+    double result_ssim =
+        CalculateMetrics(kSSIM, reference_frame, test_frame, width, height);
 
     previous_frame_number = decoded_frame_number;
 
     // Fill in the result struct.
     AnalysisResult result;
     result.frame_number = decoded_frame_number;
     result.psnr_value = result_psnr;
     result.ssim_value = result_ssim;
 
     results->frames.push_back(result);
   }
 
   // Cleanup.
-  fclose(stats_file);
+  fclose(stats_file_ref);
+  fclose(stats_file_test);
   delete[] test_frame;
   delete[] reference_frame;
 }
 
 void PrintMaxRepeatedAndSkippedFrames(const std::string& label,
-                                      const std::string& stats_file_name) {
-  PrintMaxRepeatedAndSkippedFrames(stdout, label, stats_file_name);
+                                      const std::string& stats_file_ref_name,
+                                      const std::string& stats_file_test_name) {
+  PrintMaxRepeatedAndSkippedFrames(stdout, label, stats_file_ref_name,
+                                   stats_file_test_name);
 }
 
-void PrintMaxRepeatedAndSkippedFrames(FILE* output, const std::string& label,
-                                      const std::string& stats_file_name) {
-  FILE* stats_file = fopen(stats_file_name.c_str(), "r");
-  if (stats_file == NULL) {
-    fprintf(stderr, "Couldn't open stats file for reading: %s\n",
-            stats_file_name.c_str());
+namespace {
+std::vector<std::pair<int, int> > GetBarcodeNrToFrequency(FILE* file) {

[phoglund, 2016/12/08 09:55:44]

Number

[phoglund, 2016/12/08 09:55:44]

I would love to have unit tests for these guys since they're so complex. Reading
files in the unit tests is fine, just check in some sample ref files for test
data. 

The second problem is the output of the functions is printed to stdout. 
PrintMaxRepeatedAndSkippedFrames cleverly takes a FILE* output parameter
already, so it's easy to just pass in a suitable FILE* from your test and verify
the right things were written in. I'd just mkstemp() a file in the test and then
verify the right things were printed.

You can also consider refactoring 

PrintMaxRepeatedAndSkippedFrames(stdout, label, stats_file_ref_name,
                                 stats_file_test_name);

to

int max_repeated = ComputeMaxRepeated(...);
int skipped = ComputeSkipped(...);
printf(... max_repeated, max_skipped)

and write tests for the Compute* functions.

[mandermo, 2016/12/08 18:08:31]

I agree the code needs to be easier to test. Maybe it convenient to have the
repeated and skipped code in the same function. How should we signal errors for
the Compute function(s)? How should errors be signaled for the user? Should the
errors be printed to stderr or stdout? We can still verify the output to file by
opening the output file for reading after in the test case.

Is there a reason we use C IO and not the C++ iostreams? Is it performance
critical? We could send in std::istream&s for the stat files and an
std::ostream& for the output. The test code can use stringstreams to stub the
input and output.

[phoglund, 2016/12/12 12:46:20]

Errors are not returned up the chain today, and I don't see you need to do that
here either? fprintf + return is fine, unless you see any benefits of returning
errors up the chain.

<iostream> is banned for Chrome code because it bloats the binary size, and
string streams are only allowed for logging. See
https://google.github.io/styleguide/cppguide.html#Streams. I really don't see
how that would make anything better.

+  std::vector<std::pair<int, int> > frame_cnt;

[phoglund, 2016/12/08 09:55:44]

It feels a lot more natural to make this a map. Frame id mapped to frequency, I
think that makes sense. I think you can make your update logic cleaner as well.
I think this will work:

frame_frequency.insert(std::pair<int, int>(decoded_frame_number, 0);
frame_frequency[decoded_frame_number]++;

insert is a no-op if the key already exists. If that doesn't work you can look
at the retval from insert to get an iterator pointing at the element, and
increment that instead.

http://www.cplusplus.com/reference/map/map/insert/

[phoglund, 2016/12/08 09:55:44]

frame_frequency?

[mandermo, 2016/12/08 18:08:30]

frame_frequency.insert(std::pair<int, int>(decoded_frame_number, 0);
frame_frequency[decoded_frame_number]++;
Can be simplified to either only
frame_frequency[decoded_frame_number]++;
because if it is not there, the value is value-initialized and is initialized to
zero because it is an int.
It can also be replaced with:
frame_frequency.insert(std::make_pair(decoded_frame_number, 0)).first->second++;

The current function name for this function is probably not the best. The reason
I choose a vector is to remember the order of the frames. To handle situations
where the video wrap around like this:
ref:  4567123
test:   67 23
Then I want 1 skipped frame. With a map for the test video, then I don't know
how to arrive at 1 skipped frame. It is easy to make a mistake and think that
test video start at frame 2 and that frame 4,5 are skipped.

[mandermo, 2016/12/08 18:08:31]

Maybe it is more of a frame count than a frequency.

[phoglund, 2016/12/12 12:46:20]

Right, it's actually a vector of frame "clusters", e.g. where you found repeated
frames. I was mislead by the bad function name. My comment below assumed you
actually had a frame:frequency mapping.

So actually this
ref  111234444445678
test 111111234444445678

produces 3-1-1-6-1-1-1-1
and      6-1-1-6-1-1-1-1

I think that does make sense. In that case the vector should be called
frame_clusters or something.

It would be nice if we could subtract 6-3 = 3 here, but you need to do some
serious thinking to ensure the videos are correctly lined up. What if the ref
video starts recording 1 second before the test video? In that case you need to
align the start of the test and ref videos.

Maybe it's better to hope there are no freezes in the ref video and just print
the freezes in the test video...

[mandermo, 2016/12/21 16:42:06]

I have renamed the function now and added a comment. I align the videos in the
beginning

+  char line[STATS_LINE_LENGTH];
+  while (GetNextStatsLine(file, line)) {
+    int decoded_frame_number = ExtractDecodedFrameNumber(line);
+    if (frame_cnt.empty() || frame_cnt.back().first != decoded_frame_number) {
+      frame_cnt.push_back(std::make_pair(decoded_frame_number, 1));
+    } else {
+      ++frame_cnt.back().second;
+    }
+  }
+  return frame_cnt;
+}
+}  // namespace
+
+void PrintMaxRepeatedAndSkippedFrames(FILE* output,
+                                      const std::string& label,
+                                      const std::string& stats_file_ref_name,
+                                      const std::string& stats_file_test_name) {
+  FILE* stats_file_ref = fopen(stats_file_ref_name.c_str(), "r");
+  FILE* stats_file_test = fopen(stats_file_test_name.c_str(), "r");
+  if (stats_file_ref == NULL) {
+    fprintf(stderr, "Couldn't open reference stats file for reading: %s\n",
+            stats_file_ref_name.c_str());
     return;
   }
-  char line[STATS_LINE_LENGTH];
+  if (stats_file_test == NULL) {
+    fprintf(stderr, "Couldn't open test stats file for reading: %s\n",
+            stats_file_test_name.c_str());
+    fclose(stats_file_ref);
+    return;
+  }
 
-  int repeated_frames = 1;
   int max_repeated_frames = 1;
   int max_skipped_frames = 1;
-  int previous_frame_number = -1;
 
-  while (GetNextStatsLine(stats_file, line)) {
-    int decoded_frame_number = ExtractDecodedFrameNumber(line);
+  std::vector<std::pair<int, int> > frame_cnt_ref =

[phoglund, 2016/12/08 09:55:44]

frame_frequency_ref

[mandermo, 2016/12/08 18:08:30]

Maybe it is more of a frame count than a frequency.

+      GetBarcodeNrToFrequency(stats_file_ref);
 
-    if (decoded_frame_number == -1) {
-      continue;
+  std::vector<std::pair<int, int> > frame_cnt_test =
+      GetBarcodeNrToFrequency(stats_file_test);
+
+  fclose(stats_file_ref);
+  fclose(stats_file_test);
+
+  auto it_ref = frame_cnt_ref.begin();
+  auto it_test = frame_cnt_test.begin();
+  auto end_ref = frame_cnt_ref.end();
+  auto end_test = frame_cnt_test.end();
+
+  if (it_test != end_test) {

[phoglund, 2016/12/08 09:55:44]

if (it_test == end_test) the test file is empty, which is pretty absurd. I think
you can make this boundary condition a guard clause:

if (it_test == end_test || it_ref == end_ref) {
  fprintf(output, "Either test or ref file is empty, nothing to print");
  return;
}

...

[mandermo, 2016/12/08 18:08:31]

Done. Should I print to output or to stderr like the rest of the code?

I have done some other changes that was possible after this change.

+    while (it_ref != end_ref && it_ref->first != it_test->first) {

[phoglund, 2016/12/08 09:55:44]

It's hard to read what happens here. Maybe extract a function
FindFirstFrameInRefVideo?

[mandermo, 2016/12/08 18:08:31]

Commented the code better.

[mandermo, 2016/12/08 18:08:31]

Done. Should I print to output or to stderr like the rest of the code?

+      ++it_ref;
     }
+    if (it_ref == end_ref) {
+      fprintf(stderr,
+              "The barcode in the test videos first frame is not in the "
+              "reference video.");
+      return;
+    }
+    max_repeated_frames =

[phoglund, 2016/12/08 09:55:44]

Also not sure if this algorithm is correct. To compute repeated frames, suppose
the following sequence:

ref  111234444445678
test 111111234444445678

In that case, freq(ref, 1) = 3 and freq(test, 1) = 6, so we correctly get 6-3 =
3 repeated frames. But what if the test runs so long that the ref file wraps:

ref  111234444445678
test 111111234444445678111234444445678

In that case freq(ref, 1) = 3 but freq(test, 1) = 9, and it claims that frame 1
is repeated 6 times. The correct answer is 3. In fact, the second 111 sequence
isn't even a freeze since it didn't freeze any more frames than were already
frozen in the ref file. The frequency count approach fails if there's wrapping.
I guess we can avoid that by always having a longer ref file than the time we
run tests...

Or wait actually, I think your approach is correct after all. We can assume the
ref recording will be about as long as the test recording, and it should _also_
wrap unless the ref file is super long:

ref  111234444445678111234444445678
test 111111234444445678111234444445678

In that case your algorithm produces the right answer 3. It breaks down in some
cases though:

ref  121212121212
test 1112111211121112

Here freq(ref, 1) = 6 and freq(test, 1) = 12, so max_repeated = 6, but the
longest freeze is actually 3. I doubt this is actually a problem though since
the above freeze pattern looks pretty bizarre. It will tend to be

123444444445677778 etc, and then it will work.

Try to comment how this works, and write unit tests to illustrate the various
edge cases and assumptions here. You can also make the code more readable with
some variables:

This is also hard to read, extracting some variables might help:

int test_frame_frequency = it_test->second;
int ref_frame_frequency = it_ref->second;

// If a frame shows up more in the test video it's likely been frozen.
int suspected_freeze = test_frame_frequency - ref_frame_frequency + 1;

[mandermo, 2016/12/08 18:08:30]

Lets make the unittests and see what output we get.

[phoglund, 2016/12/12 12:46:20]

Ok, I think counting the frame clusters like your code is today, is a better
approach. Disregard most of my comment above, since it finds that frame
frequency counting is bad when the videos wrap and not necessarily start in the
same place.

[mandermo, 2016/12/21 16:42:06]

Done.

+        std::max(max_repeated_frames, it_test->second - it_ref->second + 1);
+  }
 
-    // Calculate how many frames a cluster of repeated frames contains.
-    if (decoded_frame_number == previous_frame_number) {
-      ++repeated_frames;
-      if (repeated_frames > max_repeated_frames) {
-        max_repeated_frames = repeated_frames;
-      }
-    } else {
-      repeated_frames = 1;
+  for (;;) {
+    ++it_test;
+    if (it_test == end_test) {
+      break;
     }
+    int skipped_frames = 0;
+    ++it_ref;
+    while (it_ref != end_ref && it_ref->first != it_test->first) {
+      skipped_frames += it_ref->second;
+      ++it_ref;
+    }
+    if (it_ref == end_ref) {
+      fprintf(stderr,
+              "The barcode in the test video is not in the reference video.");
+      return;
+    }
+    if (skipped_frames > max_skipped_frames) {
+      max_skipped_frames = skipped_frames;
+    }
+    max_repeated_frames =
+        std::max(max_repeated_frames, it_test->second - it_ref->second + 1);
+  }
 
-    // Calculate how much frames have been skipped.
-    if (decoded_frame_number != 0 && previous_frame_number != -1) {
-      int skipped_frames = decoded_frame_number - previous_frame_number - 1;
-      if (skipped_frames > max_skipped_frames) {
-        max_skipped_frames = skipped_frames;
-      }
-    }
-    previous_frame_number = decoded_frame_number;
-  }
   fprintf(output, "RESULT Max_repeated: %s= %d\n", label.c_str(),
           max_repeated_frames);
   fprintf(output, "RESULT Max_skipped: %s= %d\n", label.c_str(),
           max_skipped_frames);
-  fclose(stats_file);
 }
 
 void PrintAnalysisResults(const std::string& label, ResultsContainer* results) {
   PrintAnalysisResults(stdout, label, results);
 }
 
 void PrintAnalysisResults(FILE* output, const std::string& label,
                           ResultsContainer* results) {
   std::vector<AnalysisResult>::iterator iter;
 
@@ skipping 12 matching lines @@
     for (iter = results->frames.begin(); iter != results->frames.end() - 1;
          ++iter) {
       fprintf(output, "%f,", iter->ssim_value);
     }
     fprintf(output, "%f] score\n", iter->ssim_value);
   }
 }
 
 }  // namespace test
 }  // namespace webrtc