Analysis of the Edge Effect of

It has been observed that many different types of digital halftone algorithms show edge enhancement effects. Edge enhancement is often desirable and can provide an impression of higher image resolution. For example, the Floyd-Steinberg stochastic halftone error diffusion algorithm shifts the visual noise of the image to a higher frequency so that our eyes are unable to see it. In addition, the Floyd-Steinberg algorithm is well known to enhance edge sharpness (7). As a result we will see perceptually an image that has higher resolution as well as lower noise. It has been reported that by changing the way error is diffused in the Floyd-Steinberg algorithm, both the visual noise and the edge enhancement change.However, these effects have been reported only as qualitative visual observations and not as quantitative measurements.

The focus of this research is to develop a quantitative method of analysis the edge enhancement effects in digital halftone algorithms. An experiment was designed to model the edge enhancement by creating two different gray level values, where the junction between these gray level values showed the edge enhancement effects. Error Diffusion and Linear Pixel Shuffling techniques were used to generate the halftones examined in this project (5).

The goal of this research is to develop a metric that can be used to measure edge enhancement effects quantitatively in any digital halftone algorithms. The metric is hoped to give people a better control toward designing digital halftone algorithms.

Some digital halftone algorithms have been observed to create an edge enhancement effect (5)(7), which is often desirable in order to give higher image resolution impression. For example, the Floyd-Steinberg algorithm shifts the visual noise of the image to a higher frequency so that our eyes do not see it. The Floyd-Steinberg algorithm also enhances some edges. However, as will be shown, edges are enhanced only in some directions. The new Linear Pixel Shuffling algorithm developed by Dr. Peter Anderson (5) provides a unique new way to diffuse error and as will be shown enhances edges is all directions.

Error diffusion is a popular digital halftone algorithm that is used to prepare images for viewing on a computer screen or for reproduction of images on low resolution printers (2). Error diffusion algorithms enhance the input edges. It will be shown that by varying the way the propagated error is distributed, the amount of edge enhancement effects on the images is different.

Error diffusion was developed by Floyd and Steinberg in 1976 as a method of preparing an image for computer display. The concept of this method is that the algorithm will calculate the error between the input and the output and uses the error in the calculation of the next output pixel.

The simplest example of the error diffusion technique is the one-dimensional case in which the error is spread out to the next successive pixel only (1). The gray level (0 to 255) of the first input pixel is compared to a threshold gray value of 128.If the input gray value is less than 128, the output pixel is zero, else it is 255. This results in an error equal to the difference between the output and the input gray values. This error can be positive or negative and is added to the next input pixel. Thresulting sum is compared to the threshold value of 128 to determine the output value (0 or 255) of the next pixel, and the error is again calculated and propagated. The process of error is propagation and thresholding is continued to the end of the image. As the process continues, all the input pixel values will be modified by the error value that is generated by the previous processed pixel. This process results in an average gray level equal to the gray level of the input image.

This simple one-dimensional case will not produce edge enhancement effects on the output image. It is usually used only to spread out the errors to the neighboring pixels and improve the appearance of gray scale. The Floyd-Steinberg technique passes error to the closest four neighbor pixels instead of just to the next pixel. The closest four pixels receive a fraction of the total error, and the way in which the error is distributed to the four pixels has an effect on the noise and edge enhancement of the final image (4).

Linear Pixel Shuffling is a new digital halftone technique that provides a method of processing a pixel in images in a pseudo random way rather than in a sequential raster order. Linear Pixel Shuffling is based on the property of a Fibonacci-like sequence of numbers. An advantage of Linear Pixel Shuffling is that it processes the image uniformly and is easy to be implemented (5). It also gives the advantage of having omni-directional error diffusion and also omni-directional edge enhancement effects.

Although edge enhancement effects are often observed in digital halftones; such as in Error Diffusion and Linear Pixel Shuffling technique, no quantitative method of analysis of the effects has been reported. However, the literature has many reports on how to detect edge enhancement effects (3). This experiment is designed to measure quantitatively the edge enhancement generated by different digital halftones algorithm, especially by Error Diffusion and Linear Pixel Shuffling technique. At the end of the project, it is expected to that a technique of measuring quantitatively edge enhancement will be achieved.

The hypothesis of this project is that edge enhancement effects on different digital halftones algorithm can be measured, within experimental error, by designing new metrics of characterizing edge enhancement phenomenon. The metrics can also be used to predict and to control the effect of changing algorithms in the process of generating output images.

It has been reported that by changing the way error is distributed in error diffusion algorithms, the visual noise of an image will be frequency characteristics of the noise power in the image is changed. In addition, different amounts of edge enhancement are observed.

Root Mean Square (RMS) deviation, also known as standard deviation, is a traditional metric of measuring the average distance of each data members of the sample from the mean. An RMS deviation technique was chosen for this project as the basis for an edge enhancement metric. By using this metric, the amount of edge enhancement can be measured and compared to the noise power in the image which is also characterized using an RMS deviation calculation. Thus, a signal to noise ratio can be defined as the ratio of the edge RMS metric to the noise RMS metric. A signal to noise ratio, SNR, is a metric that is often used to determine whether one can see the difference in an image or not. Usually, signal to noise ratio of three is used as a minimum limit to determine when someone can see the difference in the image (6). In the current project the RMS edge to noise ratio is measured, and a ratio of 3 or greater is assumed qualitatively to be visually significant.

It is sometimes observed that the edge enhancement effect is not symmetrical on both sides of the edge that the amount of edge enhancement on a junction between lower and higher reflectance value on a sample to be different. Thus, the RMS edge enhancement metric developed in this project was designed to characterize not only the overall degree of edge enhancement, but also separately the degree of enhancement on both the low and the high reflectance sides of the edge. The difference between these two edge metrics then provides a measure of the degree of symmetry of the edge enhancement.

Error Diffusion and Linear Pixel Shuffling techniques were used in order to generate different samples. Different samples were needed to test whether the experimental design is valid or not. The size of each sample was 128 x 128 pixels. Most of the samples used in this study were constructed with the dark side on the left from horizontal location 0 to 63 and the bright side on the right from pixel 64 to 127. Figure 1 is an illustration. Edge enhancement is expected along the edge between the two sides of the image. Occasionally edge type artifacts occurred at the extreme left or right of the image, but these were ignored in the study.

Symmetry characteristics of a halftone algorithm were examined by measuring edges in three additional images: one with the bright side on the right; with the bright side on the top (horizontal edge); and with the bright side on the bottom. Each of the edge images, after being formed by the halftone algorithm, was rotated so the bright side was on the right to allow easier application of the edge analysis algorithm.

Each sample was analyzed by first averaging the pixel values in each column of the image. The average pixel value (0 £ P £ 255) for each column was converted to a reflectance, (0 £ S £ 1) by dividing by 255. Each column was labeled by a location index, j from 0 to 127 from left to right. Figure 2 illustrates the mean column reflectance, S, as a function of column location, j, for the example image shown in Figure 1.

Each edge generated by a halftone algorithm was compared to the ideal edge shown as the dotted line step function in Figure 2. The differences between the ideal edge and the measured values of S were calculated at each location, j. As a result of programming artifacts, it was occasionally found that the mean reflectance, S, on each side of the image was not identical to the value selected for the ideal edge. The differences were small (£ 0.05 reflectance) and corrections were made by values of S on the left and right side of the ideal edge in such a way that the RMS deviation between the ideal edge and the measured edge was zero.

Figure 2 illustrates edge enhancement. The mean value of S immediately before the edge (j = 63) is significantly lower than the mean reflectance of the left side of the image. Also, the value of S immediately following the edge (j = 64) is significantly higher than the mean on the right side of the image. In order to extract information from each side of the edge the data was divided into two independent data sets, as shown in Figure 3. The origin in each data set corresponds to the column nearest the edge, and the values of S are shown at locations jj increasing with distance from the edge. The values of S immediately adjacent to the edge at jj=0 are highlighted in Figure 3 with the two dotted lines (-------). These are labeled as SeL and SeR for the S values at the edge on the left and the right of the edge. The horizontal solid lines in Figure 3 (¾¾) show the average S values for the left and the right sides calculated by excluding the S values immediately adjacent to the edge. These are labeled as SmL and SmR in Figure 3. The edge enhancement metrics for the left and the right side of the edge are simply the difference between the dotted and solid lines in Figure 3. Equations (1) and (2) define the edge enhancement magnitudes as EdgeR and EdgeL. Note that positive values of enhancement are defined for both edges.

The Root Mean Square deviation between the mean level SmR and the individual S values is defined by equation (3) as NoiseR. This is a measure of the noise associated with the halftone algorithm on the right side of the edge. Similarly, equation (4) defines the noise of the algorithm on the left side of the edge. The value of k is the number of S values used in the calculation. If edge artifacts on the extreme left or right of the image were observed, those pixels were excluded from the calculation.

The ratio of edge enhancement to RMS noise for the right side of the edge is defined as SNRR as shown in equation (5). Similarly SNRL is defined in equation (6). These metrics are used to compare the edge enhancement characteristics of different halftone algorithms, as described in the Results section of this report. In addition, and overall enhancement metric was defined as SNRt as shown in equation (7).

In many cases unsymmetrical edge enhancement effects that were observed occur on the junction; therefore, the difference between SNRR and SNRL is defined as a metric of asymmetry as shown in equation (8).

This definition of ASYM is negative if the right side of the edge is enhanced more than the left side. ASYM = 0 if there is no edge enhancement, and >0 if the left side is enhanced more than the right side.

A. Floyd-Steinberg Error Diffusion

The edge enhancement metric was applied to several different samples to see whether or not it is a useful analytical metric. Each sample represented a different type of error diffusion. The edge enhancement metric was compared to what was observed visually. If a sample gave a visual impression of higher edge enhancement, it was expected that the analytical metrics of edge enhancement also would be higher.Traditional error diffusion and omni-directional error diffusion based on Linear Pixel Shuffling were used to generate the samples. Visual inspection of the halftone images was done by displaying the images on a CRT monitor. Analysis of the edge enhancement metrics was performed on the bitmap files directly, and none of the images were actually printed for analysis. Thus, all edge effects reported in this report are due to the error diffusion algorithms and not to printer artifacts. The printed images shown in the figures are for illustration only and were not used to obtain quantitative data.

Figure 4. is the simplest example of the error diffusion technique, where the error is only spread to the next successive pixel. Visual examination of the resulting edge image did not show a visually significant enhancement, and the edge metrics agree with this observation. Thus, edge enhancement requires more than simply forward diffusion of error. It requires a more involved distribution of error.

Figure 5. illustrates the results for the most commonly used form of the Floyd-Steinberg algorithm. The matrix, M, shows the amount of error that is spread from the location of the pixel being processed, X, to its neighbors. As we expected, the Floyd-Steinberg algorithm gives a significant edge enhancement. The edge enhancement metric, SNRt, says the edge is significantly enhanced relative to noise, and the ASYM metric tells us enhancement occurs primarily on the right side of the edge. This agreed well with visual inspection. The lack of significant edge effect on the right side of the edge is somewhat surprising since some error is passed to the left of the X location. However, only 3/16th of the error is passed to the left, and the left edge is not enhanced significantly relative to the noise power of the left gray level. The magnitude and direction of the edge effect is consistent with these authors visual observations.

If Figure 6 the error is diffused only in the forward direction, but unlike Figure 4. it is diffused equally to the next two pixels.Somewhat unexpectedly, this produces an edge enhancement that is significantly greater than that shown in Figure 4.The asymmetry of the edge effect makes sense intuitively because error is diffused in only one direction.The analytical results were found to be in agreement with the authors visual assessment.

Figure 7 shows another a Floyd-Steinberg type system in which error was diffused equally to the right and to the left. The edge effect, SNRt, is quite large for this example, and enhancement is quite symmetrical.Again this result agrees with visual observation and makes sense intuitively.However, close inspection of the sample illustrated in Figure 7 suggested to this author that there may be cases in which the edge is enhanced too much.The degree of edge enhancement desirable in a halftone algorithm may depend on the addressability of the printer and the printer transfer function.This is a topic appropriate for an additional project and was not further explored here.

The results of the analysis using different error diffusion kernels with the well known technique of Floyd-Steinberg demonstrates the usefulness of the analytical metrics developed in this project for measuring edge enhancement.Thus, the analysis technique was applied in an examination of edge effects associated with an entirely new type of error diffusion algorithm recently developed by Prof. Peter Anderson of the RIT Computer Science Department (5). This new error diffusion technique is referred to as omni-directional because it is capable of diffusing error in all spatial directions around the central pixel, X, being processed.This is possible because the technique is not an ordinary raster process but a process that addresses the pixels in the image in a pseudo-random way.The pixels are each addressed once, but only once.When each pixel, X, is processed, the error is diffused according to a kernel that allows error to be passed in any direction.Figure 8 provides an illustration.Note the error kernel allows diffusion of fractional error in all directions from the central pixel.Although error can be diffused in all spatial directions, only examples showing diffusion toward the right and down were examined in this project.Future work will include an examination of error diffusion in all directions simultaneously.

The results shown in Figure 8 illustrate edge enhancement on one side of the edge but not the other, as one would expect for and asymmetric diffusion kernel.However, the edge in this example was oriented horizontally as shown so that the error in the kernel that was diffused in the down direction toward the dark side of the image. As predicted, the dark side of the edge was enhanced.

In order to further analyze the edge effect in the Linear Pixel Shuffling algorithm, the edge was rotated 180 degrees and processed with the same kernel, as shown in Figure 9. Again the result was found in agreement with what was expected and it was predictable as it also enhanced the light side of the edge. The analytical results were also found to make sense intuitively.

The effects of edge enhancement found for the omni-direction algorithm were further examined by changing the mean gray level of the two sides of the edge.As shown in Figure 10, a reduction in the gray level difference between the two levels significantly reduced the amount of edge enhancement. That edge enhancement would vary with the size of the edge step makes intuitive sense.If the two edges are of the same gray level, certainly no edge enhancement will occur.

Edge enhancement effects are often observed in digital halftones, but little has been reported in the literature on techniques for quantitative analysis of the effect. This project provides a metric that is useful for measuring the edge effect of halftone algorithms that correlates well with these authors visual observations.The metric is calculated directly in the spatial domain using average pixel magnitudes in the region of the edge.The metric calculated an edge effect for each side of the edge relative to the noise power in the gray level adjacent to the edge.

Attempts were made during the project to extract useful information form frequency analysis of the edges and the halftone noise.However, the signal/noise for metrics defined in the frequency domain were not found to be useful or to correlate well with visual observation.Thus, the spatial frequency approach was abandoned, and the project focused exclusively on the metrics defined in the spatial domain, as described in the body of this report.

In application of the edge analysis technique to several traditional Floyd-Steinberg halftones, the results demonstrated the utility and reliability of the analytical technique.Thus, the technique was applied to an entirely new class of error diffusion halftones developed by Prof. Peter Anderson (5).The results also agreed entirely with visual observations of the authors.

Edge enhancement effects were not always observed to occur over only a single pixel.Indeed, when error was diffused over a distance of two pixels from the central X pixel, enhancement was often observed to occur in the two pixels next to the edge.Moreover, visual inspection seems to suggest that edge effects, even for diffusion of error by only one pixel dimension, can extend beyond one pixel location.In some cases the data seemed visually to suggest behavior similar to an exponential decay in edge enhancement at increasing distances from the edge.Since in most cases the edge/noise ratio declined nearly to 1:1 even at the second pixel away form the edge, the results of this analysis were unable to provide statistically significant evidence for this decaying edge effect.To demonstrate such an effect this analysis will have to be applied to edge images over a significantly greater number of pixels.

The objective of the project was to determine whether a convenient analytical metric could be developed that would provide researchers with a tool for calculating the degree of edge enhancement for any given halftone algorithm. The results of the project strongly indicate this can be achieved. The metrics and procedures developed in this project were shown to correlate with the visual impression of edge enhancement made by the author. To demonstrate the utility of the analysis, it was applied to an entirely different and new kind of halftone algorithm developed by Prof. Peter Anderson (5). The results again agreed entirely with the author's visual evaluation, and this strongly indicates the analysis is capable of providing useful guidance in halftone development projects. Indeed, plans are being made to applying this analysis to the development and evaluation of new halftone algorithms.

Unsymmetrical edge enhancement effects will continue to be examined. In particular, attempts are planned to examine the quantitative relationship between the percent and direction of error diffusion and the magnitude and direction of edge enhancement.The hope is to develop a catalog of experience that will serve as a guide in selecting halftone patterns for particular applications.The study also is expected to lead to insights about the causative relationships between edge enhancement and the error kernel distribution.

Another very interesting, but still very tentative, observation is that edges are enhanced over a distance of more than one pixel location, even when error is diffused only by one pixel location.The first necessity will be to verify whether or not this effect is real.This will require significantly larger edge images of significantly more pixels.However, if the edge effect does decay as one moves several pixels from the edge, then it may be possible to impose some shape on the edge decay curve by designing diffusion kernels appropriately.This would be of particular use as the technology of computer printers achieves higher addressability.

The success of the edge enhancement metrics described in this report will lead to significant research opportunities in the field of hard copy imaging and halftone algorithm development.Thus, the project has clearly achieved its goal, and as a result many new project opportunities have been developed.

Introduction

Background

Theory

Results

A. Floyd-Steinberg Error Diffusion

Discussion

Conclusion