Align low-res images of a moving feet

Question

I have a pressure platform that provides 64x128 pixel grayscale images (1px aprox 5mm) of a subject walking on top of it.

If I capture the whole step, I can obtain the average distribution of pressure for all the frames. Just by averaging (in fact the operator used is the max of each pixel) I obtain what I need. That is because at each timestep, each point in the foot always touches the same sensor.

The difficult case is when I put this pressure platform below a treadmill. From the point of view of the pressure platform, the user is "sliding", i.e. each sensor captures information from different parts of the foot at different times.

What this means is that there is an offset $o_i$ between $image_i$ and $image_{i-1}$.

Right now I have two algorithms: one local (that works in real time, providing a rough estimation) another global (very slow, though unoptimized).

The local one is just to check the offset (with subpixel accuracy of, say, 0.1px, so linearly interpolating the images) that minimizes the SSD between both images, that is: $$ o_i = argmin_{o} ||translate(image_i, o) - image_{i-1}|| $$

which results in images like this:

The global method is to maximize a focus measure over the aggregated image, that is, if we take $O$ as the vector of all the alignments for a whole step consisting of $N$ images then:

$$ O^* = argmax_O = focus(\sum_i^N translate(image_i, o_i)) $$ Here I use the variance of the laplacian as focus measure, and it results in images like this:

As you can see, the alignment is much better, particularly noticeable in the front of the foot (the left part of the image).

To implement it, I initialize $O$ with the alignment from the local algorithm, then iterate through each element assigning the value that maximizes the global focus of the resulting image (leaving the rest fixed). I perform multiple passes until a maximum is reached (no change of global focus respect last iteration).

The following link has a video of a whole sequence, aligned using the local algorithm: https://i.stack.imgur.com/jz5pb.jpg

The displacement is only in the X direction, so only a positive real number is estimated. In the case of the video, that step is 182 images, so the parameters are 182 positive real numbers. For the global method, I just do a brute force search over all the parameters, and reduce the search space by optimizing over a finite list of parameters (e.g. $0.3, 0.35, 0.4, 0.45, 0.5, 0.55$) which I know are in the range of possible offsets (just take min/max of the local algorithm output and add some tolerance).

The question is two-fold:

1. Is there any other algorithm/measure that I could try in order to solve the alignment problem
2. Is there another way of optimizing my current global algorithm instead of the brute force approach I am following?

Answer 1

Very interesting problem

I will focus on the second aspect of your question, how to improve it. What I would do next, based on the experience you shared is to combine the two methods.

One problem of your first approach is that it accumulates the errors in the alignment between multiple images. A possible approach would be to use your focus measure to align the images iteratively.

$$ F_{i} = F_{i-1} + translate(image_{i}, o_{i}) $$

$$ o_i = \arg\min_{o}\quad focus\left[ F_{i} + translate\left(image_{i}, o\right) \right]$$

This approach is maybe not the best at the beginning, but after the first step it have the advantage of not accumulating errors in the same way as if you compute $o_i$ as using only $image_i$ and $image_{i-1}$. Notice that $F_{i-1}$ aggregates all the previously aligned images, so if the one image is not aligned very well it will make so much difference since it sees how it was aligned before.

This is maybe not going to be as good as your global method. What I would try, to improve your global method is to make the displacement continuous with some type of interpolation, because a continuous optimization problem is much easier to solve than a discrete optimization problem, because can use the gradient information[1]. I am sure you are not doing the search for all the offsets independently that would be $s^N$, where $s$ is the number of possibilities in your search list.

Also instead of limiting the the displacements to a given range I think you could simply add some cost to the differences of the displacements $k \sum ||o_i - o_{i-1}||^2$, this makes sure that if have a high relative displacement between two frames the cost function will indicate that this is unreasonable.