Closed opatiny closed 7 months ago
Here are the different steps required to compute the number of operations.
xMargin
and yMargin
Compute the top/bottom (yMargin
) and left/right (xMargin
) margins to allow for the alignment. These margins correspond to a margin all around the destination image in which the source image can be moved to compute the difference.
if (source.width < destination.width) {
xMargin = Math.round(xFactor * source.width);
} else {
xMargin = Math.round(source.width - destination.width * (1 - xFactor));
}
if (source.height < destination.height) {
yMargin = Math.round(yFactor * source.height);
} else {
yMargin = source.height - destination.height * (1 - yFactor);
}
const minRow = -margins.yMargin;
const minColumn = -margins.xMargin;
const maxRow = destination.height - source.height + margins.yMargin;
const maxColumn = destination.width - source.width + margins.xMargin;
const nbTranslations = (maxRow - minRow + 1) * (maxColumn - minColumn + 1);
We are overestimating the actual number of loop iterations.
const minHeight = Math.min(source.height, destination.height);
const minWidth = Math.min(source.width, destination.width);
const nbOperations = nbTranslations * minHeight * minWidth;
The function was implemented in 5508002f6a33ea90892a609501d0fca307909b25.
The alignment algorithm is really slow because the number of operations to realise is huge. In the final algorithm, we scale the images down for a first raw alignment to enhance the performance. Ideally, we would like to scale the images down automatically, to have approximately always the same computation time independently on the original images size. To do that, we have to be able to compute the total number of operations done depending on the images dimensions.
The algorithm is basically composed of two imbricated loops 1) Loop over all desired translations 2) Sum the difference of all overlapping pixels (loop on the overlapping pixels)
Remark: The images can have different sizes and the source image does not necessarily fit entirely in the destination image!!