How to determine the smallest number of small areas to render?

Question

I have two images (pixel arrays), one of which is rendered on the screen. The goal is to render the second. However performance is critical and, in the environment where I am, render each pixel is quite a lot slow. So rendering the entire image over the one that was already there is impractical. Note: everything needs to be done by software.

In order to minimize the rendering time, I intend to make an algorithm that integrates which areas of the images were changed to redraw only those regions. Consider the following:

A = Tempo gasto na execução do algoritmo
R = Tempo gasto para inicializar a renderização de cada região
P = Tempo gasto para enviar um pixel
n = Número de regiões
m = Número de pixels em cada região

T = A + n×(R + m×P)

The goal is to minimize T.

I understand that an algorithm that minimizes the number of regions and the number of pixels sent in each one is NP Complete and that would cause a A exponential. So how to find a solution that is good, even if not the best, in an acceptable period of time?

Answer 1

You didn’t specify the domain of your application, but you can imagine that this is something in which frames are rendered in sequence (like a video, or more likely, a video game) in a restricted computer environment, and so it is important to avoid unnecessary costs with on-screen rendering. If this understanding is correct, then it can also be admitted that the images will always have the same dimensions, right? :)

Well, assuming that this is the case, I would like to propose a solution for images manipulated as two-dimensional matrices of dimensions (n, m):

A = Matriz com os dados da imagem já renderizada
B = Matriz com os dados da nova imagem

The initial idea is to calculate the absolute normalized difference between these matrices to produce a binary image of differences. The equations below (with arithmetic operations on the individual elements of the matrices, i.e., Cij = Aij - Bij and Dij = abs(Cij/Cij)) demonstrate the idea:

(1) C = A - B
(2) D = abs(C / C)

Equation 1 gives a new matrix (C) with the result of the difference between the two original matrices (A and B). Equation 2 normalizes the values in 0 or 1, and ignores Signal. Thus, we obtain the binary matrix (D).

The binary matrix D will contain the value 0 in the pixels where there is no change and the value 1 in the pixels where there is change between the original matrices A and B. Therefore, it serves as a map for the regions where there is divergence between the two images. Note that this calculation has quadratic complexity in relation to the image dimensions (n*m).

In the same loop in which the differences of equation 1 can already be calculated its accumulated sum, so that with a simple check it is possible to ignore the best case (if the cumulative sum is equal to 0, the images are completely identical and there is no further need to do).

If the cumulative sum is different from 0, there are differences between the images and the binary matrix contains the identification of where these differences occur. An algorithm like Region Growth (Region Growing) can then be used to segment the regions of interest.

The idea is simple:

Initialization:

• List of pixels marked as processed is set empty.
• Region list is defined empty.

Processing:

1. In the binary image (D), randomly select any one pixel among those not yet marked as processed. If there are no more unmarked pixels, close.

2. Mark the current pixel as processed. If it has a value of 0 (that is, it does not indicate divergence), go back to step 1. Otherwise, proceed.

3. Create a new region (an array) and add the pixel to it.

4. For each neighboring pixel* to the current pixel:

   4.1. Mark the neighboring pixel as processed. If it has a value of 0 (i.e., does not indicate divergence), go back to step 4. Otherwise, proceed.

   4.2. Add the neighboring pixel to the region.

   4.3. Processing of recursively from step 4, making the neighboring pixel the current pixel.

5. Go back to step 1.

_{* Neighboring pixels are the 8 pixels "around" of the current pixel.}

For example, imagine that the comparison of two images of dimensions (15 x 20), made by equations 1 and 2 defined at the beginning, produces the following binary image (in which the white color represents 0 and the black color represents 1):

Then, the processing of the Region Growth algorithm can occur as follows (depending, of course, on the pixels initially selected randomly for each new region):

Initially (figure 0) there is only the binary image. A pixel is randomly selected and the first region is started (figure 1). Neighbors are added recursively until there is no neighborhood that indicates divergences (figure 4). Thus, a new pixel is selected among those not yet marked as processed (figure 5 - illustrates if, by chance, a pixel was already drawn in a difference region). And the process is repeated (figures 6 on). It is not illustrated in these figures, but after step 14 (or even before step 5, 10 or 13) the algorithm would still process the pixels of the empty regions, but would simply ignore them until finding one of the divergence region or until the end.

At the end, the "square areas" that interest you for rendering can be obtained with the values of lower and higher x and y coordinates of the pixels in each region:

Note that this algorithm also has quadratic complexity in the worst case. In any case, the differences should be small in their (supposed) problem area, as changes from one framework to another are localized. And as ignoring pixels of areas without divergence has linear complexity, in the average case I think it can be a good solution. Maintaining the list of pixels marked as processed safely adds some complexity, but depending on the data structure used it is possible to have the solution complex in n*log(n).

In fact, instead of calculating the binary image before processing the region growth, this can be done dynamically during the processing of the algorithm, using the calculation of the two equations of the beginning directly in the evaluation of divergence of each pixel (current and neighbor)instead of a query to the matrix D.

There are also other approaches that can help you, also based on information about the divergence between the images (which, again, you can pre-calculate or not).

One possibility is to use the Split and Merge algorithm (Splitting and Merging), where the basic idea is to subdivide the image according to a Quadtree to find "uniform" regions (and uniformity, in your case, may be the largest possible amount of divergences in the region). I removed the suggestion of division and conquest because there is another answer precisely with this suggestion. :)

Answer 2

You have an estimate of R and P? This is a case that allows great flexibility in solutions, since its goal is to "render everything that has changed", but not necessarily "render nothing that hasn’t changed". In other words, creating a region admits to include sub-regions that would not need to be rendered again, if this is to increase overall performance. For example:

In addition, it is important to determine whether your goal is to maximize actual performance or to perceived performance? For if your algorithm after N steps determined a scenario in which the performance will be X, is it worth letting the algorithm continue to look for a better solution or not? (i.e. when doing A you always run the risk of increasing T, then if T = X is good enough it may be better to stop the algorithm than to try to reduce n or m all the more).

Algorithm suggestion: divide and conquer

Given these characteristics, I suggest implementing a variation of representation in quaternary tree: start with your full image (n = 1) and see how many pixels are equal (rework) and their proportion in relation to the whole. Consider if it is worth multiplying n for 4 to reduce this rework or not (based on R and P). If it is, divide the image into four parts, and repeat the analysis for each part. Otherwise, stop.

This algorithm is sub-optimal (note the 3 white qudrados in sequence in the last image, which could join in a region only but will not), but it is simple, fast and gives a satisfactory approach. You just have to adjust the parameters according to the performance characteristics of your particular case.

Notes:

• The complexity of the algorithm is O(npixels * log4(npixels)) - because it gives [at most] one pass in the entire image to each division by 4.

• Maybe it is interesting to divide the image by 2 and then by 2 again (in both directions, to see which has the best result) instead of dividing directly by 4. In the above example (assuming you continued and split the image again, getting n = 11) that would reduce n in 2, at the expense of a larger A.

• If P and R were much great in relation to A (i.e. there is no problem in a more expensive algorithm, since it squeezes every pixel of your image), maybe it is worth a search employing heuristics, for example To* ("A-star").

  I began to think of something along this path, but faced with the complexity to implement and test, and faced with the presence of a simpler solution, I did not proceed. If the solution proposed is not good enough, I can add an alternative answer to that.