In this section we are going to explain how the clipped image area can be minimized. Our goal is again to find an [A,B] interval, of known contrast C, and clipping all color components outside [A,B] just as in the previous chapters. Instead of the logarithmic histogram, we should use a 3D representation, to preserve the information to which pixel each color component belongs. We will use a discrete space, just as before, and we will use a logarithmic axis for the same reason we used a logarithmic histogram. The problem of finding the interval now becomes the problem of finding the cube which contains the most pixels. Note that the cube can only be shifted along the line r=g=b, as we have to apply the same [A,B] interval to all color components. The problem is illustrated in figure 6.6. Although it might seem to be a complex problem from computational geometry it can be solved in linear time. First note that all pixels that lie outside the sweep formed by moving the cube cannot ever be contained in the cube. Such pixels can immediately be considered as error-pixels.
Figure 6.6: Minimum area loss idea
The idea of the algorithm is to pretabulate the influence of every pixel on all steps. This is done quite simply with two lists. Let's call them inclusion and exclusion lists. The inclusion list contains the effect on the total error if the cube is moved forward, so that the pixel is just included in the cube, and the exclusion list contains the effect on the total error when the pixel just leaves the cube. The pseudo code is given in algorithm 2.
Pixels outside the cube are considered as equally weighted error-pixels whether they are near the cube or very far away. The inclusion of various error functions is straight forward, and although the complexity and the run time are increased, it can be still done in a linear time.