Clipping Error

The simplest is to consider all clipped pixels as contributing to the error equally, as is done in algorithm 1. This means applying a 0-1 type discrete error function. Obviously it is not really the same if a pixel with a value just slightly above B, or one with a value very far from B is clipped to B. The problem can be solved by applying an error function linearly penalizing the distance from B (or A for the other side of the interval). A combination of these two error functions, a value limited alternative of the latter can be used as well. All functions are shown in fig. 6.3. Although it seems that applying an error function which is not the discrete 0-1 function can increase the complexity and run time, we will show how an error function of type c in fig. 6.3 can be applied, and the process still runs in linear time (this algorithm was suggested by Attila Neumann).

  
Figure 6.3: Various types of error functions

Let us define the error function as in figure 6.4. error(a,k) gives the error weight of position k for the clipping interval [a,b], where b=a+CLIP.
 

  
Figure 6.4: Error function

for given G and d:
 

We need one additional precomputed array, e[a]. The array e contains influences on the error for each step. It is defined recursively. First let us define f(a) as:
 
and e[0] as:
 

Note that e[0] corresponds to the starting position as seen in fig. 6.5.

  
Figure 6.5: Starting position

We will define as:
 

 

Once the e[a] has been computed, all that has to be done, is to find the minimal e[a] for , and a is then the starting point of the interval.