I'd like to develop a system for web animation similar to animated gifs, like this one. I capture a series of screenshots at fixed time intervals, and then I'd like to animate them. I can trivially calculate the pixels which have changed from one frame to another, but I'd then like to calculate a set of rectangles such that blitting those rectangles over the previous frame results in the new one. There's a tradeoff between the number of rectangles and the number of "wasted" pixels, i.e. the number of pixels stored and copied which have not changed between the two frames. Is there a good algorithm for this which would give me control over the tradeoff parameter in some form?
1 Answer
$\begingroup$
$\endgroup$
0
I would say it’s a weighted set covering problem.
In specific, the cost for a set of points is the number of extra pixels in the bounding rectangle of this set.
If the number of diff points is small, you can solve this by linear programming. Otherwise, try some approximated algorithms e.g. greedy.
