Calculate set of rectangles covering pixel diffs?
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.