# 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