Patch Distance Algorithm Details

Back to index

The first stage of our algorithm requires matching patches with different sampling patterns. In order to compute a patch distance between two differently sampled patches, samples captured with shorter exposures (we call source samples) are blurred to match a sample captured with a longer exposure (we call the target sample).

The sampling pattern is stored with sample information for every high-speed pixel as shown in the image below.

The following code computes a patch distance between patches at locations p1 and p2. Patches have dimensions NxNxT.

double patchDistance(Video input, SamplingPattern pattern, Coord p1, Coord p2) {
  double totalDistance = 0.0, totalWeight = 0.0;
  // Loop over spatial locations in the reference patch
  for (int dx = 0; dx != N; dx++) {
    for (int dy = 0; dy != N; dy++) {
      SamplingSequence sequence1 = pattern(p1);
      SamplingSequence sequence2 = pattern(p2);

      int i = 0;
      // Loop over temporal extent of reference patch
      while (i < T) {
        // Choose which sequence is the target (sequence1)
        if (sequence1[i].exposure < sequence2[i].exposure ||
            (sequence1[i].exposure == sequence2[i].exposure &&
             coverage(i, sequence1[i]) < coverage(i, sequence2[i]))) {
          swap(sequence1, sequence2);
          swap(p1, p2);
        }

        // Target sample information
        int length1 = sequence1[i].exposure;
        int start1 = i - sequence1[i].offset;
        int end1 = start1 + length1;
        double input1 = input(p1.x + dx, p1.y + dy, p1.t + i);
        bool saturated1 = (input1 >= SaturationLevel);
        // Coverage of the reference patch
        int cover1 = min(end1, T) - max(start1, 0);

        int j = start1;
        double var2 = 0.0;
        double value2 = 0.0;
        bool saturated2 = false;
        // Loop over source samples
        while (j < end1) {
          int length2 = sequence2[j].exposure;
          int start2 = j - sequence2[j].offset;
          int end2 = start2 + length2;
          // Coverage of the target sample
          int cover2 = min(end1, end2) - max(start1, start2);
          double wgt = (double)cover2 / length2;
          double input2 = input(p2.x + dx, p2.y + dy, p2.t + j);
          if (input2 >= SaturationLevel)
            saturated2 = true;
          value2 += wgt * input2;
          var2 += wgt * wgt;
          j = end2;
        } // End source loop

        double weight = cover1 / (1.0 + var2);
        // Give less weight if there was saturation
        if (saturated1 || saturated2) {
          weight *= (saturated1 && saturated2) ? 0.0 : 0.125;
        } 
        double resid = value2 - input1;
        totalDistance += weight * resid * resid;
        totalWeight += weight;

        // Advance to the end of the target sample
        i = end1;
      } // End temporal loop
    }
  } // End spatial loop

  return totalDistance / totalWeight;
}

int coverage(int dt, SampleInfo sample) {
  return min(dt - sample.offset + sample.exposure, T) - max(dt - sample.offset, 0);
}
	

Back to index