media/cast/test/utility/barcode.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 // Routines for encoding and decoding a small number of bits into an image
   6 // in a way that is decodable even after scaling/encoding/cropping.
   7 //
   8 // The encoding is very simple:
   9 //
  10 //   ####    ####    ########    ####        ####    ####
  11 //   ####    ####    ########    ####        ####    ####
  12 //   ####    ####    ########    ####        ####    ####
  13 //   ####    ####    ########    ####        ####    ####
  14 //   1   2   3   4   5   6   7   8   9   10  11  12  13  14
  15 //   <-----start----><--one-bit-><-zero bit-><----stop---->
  16 //
  17 // We use a basic unit, depicted here as four characters wide.
  18 // We start with 1u black 1u white 1u black 1u white. (1-4 above)
  19 // From there on, a "one" bit is encoded as 2u black and 1u white,
  20 // and a zero bit is encoded as 1u black and 2u white. After
  21 // all the bits we end the pattern with the same pattern as the
  22 // start of the pattern.
  23
  24 #include <deque>
  25 #include <vector>
  26
  27 #include "base/logging.h"
  28 #include "media/base/video_frame.h"
  29 #include "media/cast/test/utility/barcode.h"
  30
  31 namespace media {
  32 namespace cast {
  33 namespace test {
  34
  35 const int kBlackThreshold = 256 * 2 / 3;
  36 const int kWhiteThreshold = 256 / 3;
  37
  38 bool EncodeBarcode(const std::vector<bool>& bits,
  39                    scoped_refptr<VideoFrame> output_frame) {
  40   DCHECK(output_frame->format() == VideoFrame::YV12 ||
  41          output_frame->format() == VideoFrame::YV16 ||
  42          output_frame->format() == VideoFrame::I420);
  43   int row_bytes = output_frame->row_bytes(VideoFrame::kYPlane);
  44   std::vector<unsigned char> bytes(row_bytes);
  45   for (int i = 0; i < row_bytes; i++) {
  46     bytes[i] = 255;
  47   }
  48   size_t units = bits.size() * 3 + 7;  // White or black bar where size matters.
  49   // We only use 60% of the image to make sure it works even if
  50   // the image gets cropped.
  51   size_t unit_size = row_bytes * 6 / 10 / units;
  52   if (unit_size < 1) return false;
  53   size_t bytes_required = unit_size * units;
  54   size_t padding = (row_bytes - bytes_required) / 2;
  55   unsigned char *pos = &bytes[padding];
  56   // Two leading black bars.
  57   memset(pos, 0, unit_size);
  58   pos += unit_size * 2;
  59   memset(pos, 0, unit_size);
  60   pos += unit_size * 2;
  61   for (size_t bit = 0; bit < bits.size(); bit++) {
  62     memset(pos, 0, bits[bit] ? unit_size * 2: unit_size);
  63     pos += unit_size * 3;
  64   }
  65   memset(pos, 0, unit_size);
  66   pos += unit_size * 2;
  67   memset(pos, 0, unit_size);
  68   pos += unit_size;
  69   DCHECK_LE(pos - &bytes.front(), row_bytes);
  70
  71   // Now replicate this one row into all rows in kYPlane.
  72   for (int row = 0; row < output_frame->rows(VideoFrame::kYPlane); row++) {
  73     memcpy(output_frame->data(VideoFrame::kYPlane) +
  74            output_frame->stride(VideoFrame::kYPlane) * row,
  75            &bytes.front(),
  76            row_bytes);
  77   }
  78   return true;
  79 }
  80
  81 namespace {
  82 bool DecodeBarCodeRows(const scoped_refptr<VideoFrame>& frame,
  83                        std::vector<bool>* output,
  84                        int min_row,
  85                        int max_row) {
  86   // Do a basic run-length encoding
  87   std::deque<int> runs;
  88   bool is_black = true;
  89   int length = 0;
  90   for (int pos = 0; pos < frame->row_bytes(VideoFrame::kYPlane); pos++) {
  91     float value = 0.0;
  92     for (int row = min_row; row < max_row; row++) {
  93       value += frame->data(VideoFrame::kYPlane)[
  94           frame->stride(VideoFrame::kYPlane) * row + pos];
  95     }
  96     value /= max_row - min_row;
  97     if (is_black ? value > kBlackThreshold : value < kWhiteThreshold) {
  98       is_black = !is_black;
  99       runs.push_back(length);
 100       length = 1;
 101     } else {
 102       length++;
 103     }
 104   }
 105   runs.push_back(length);
 106
 107   // Try decoding starting at each white-black transition.
 108   while (runs.size() >=  output->size() * 2 + 7) {
 109     std::deque<int>::const_iterator i = runs.begin();
 110     double unit_size = (i[1] + i[2] + i[3] + i[4]) / 4;
 111     bool valid = true;
 112     if (i[0] > unit_size * 2 || i[0] < unit_size / 2) valid = false;
 113     if (i[1] > unit_size * 2 || i[1] < unit_size / 2) valid = false;
 114     if (i[2] > unit_size * 2 || i[2] < unit_size / 2) valid = false;
 115     if (i[3] > unit_size * 2 || i[3] < unit_size / 2) valid = false;
 116     i += 4;
 117     for (size_t bit = 0; valid && bit < output->size(); bit++) {
 118       if (i[0] > unit_size / 2 && i[0] <= unit_size * 1.5 &&
 119           i[1] > unit_size * 1.5 && i[1] <= unit_size * 3) {
 120         (*output)[bit] = false;
 121       } else if (i[1] > unit_size / 2 && i[1] <= unit_size * 1.5 &&
 122                  i[0] > unit_size * 1.5 && i[0] <= unit_size * 3) {
 123         (*output)[bit] = true;
 124       } else {
 125         // Not a valid code
 126         valid = false;
 127       }
 128       i += 2;
 129     }
 130     if (i[0] > unit_size * 2 || i[0] < unit_size / 2) valid = false;
 131     if (i[1] > unit_size * 2 || i[1] < unit_size / 2) valid = false;
 132     if (i[2] > unit_size * 2 || i[2] < unit_size / 2) valid = false;
 133     i += 3;
 134     DCHECK(i <= runs.end());
 135     if (valid) {
 136       // Decoding successful, return true
 137      return true;
 138     }
 139     runs.pop_front();
 140     runs.pop_front();
 141   }
 142   return false;
 143 }
 144
 145 }  // namespace
 146
 147 // Note that "output" is assumed to be the right size already. This
 148 // could be inferred from the data, but the decoding is more robust
 149 // if we can assume that we know how many bits we want.
 150 bool DecodeBarcode(const scoped_refptr<VideoFrame>& frame,
 151                    std::vector<bool>* output) {
 152   DCHECK(frame->format() == VideoFrame::YV12 ||
 153          frame->format() == VideoFrame::YV16 ||
 154          frame->format() == VideoFrame::I420);
 155   int rows = frame->rows(VideoFrame::kYPlane);
 156   // Middle 10 lines
 157   if (DecodeBarCodeRows(frame,
 158                         output,
 159                         std::max(0, rows / 2 - 5),
 160                         std::min(rows, rows / 2 + 5))) {
 161     return true;
 162   }
 163
 164   // Top 5 lines
 165   if (DecodeBarCodeRows(frame, output, 0, std::min(5, rows))) {
 166     return true;
 167   }
 168
 169   return false;
 170 }
 171
 172 }  // namespace test
 173 }  // namespace cast
 174 }  // namespace media