Method and System for Automatically Detecting an Edge and Width of a Document Utilizing a Scanning System

The present invention is directed to a system and method for automatically detecting the width and edge of a document being scanned by a scanning system. More particularly, the present invention is directed to a method and system for detecting the edge and width of a document being scanned utilizing values calculated from a second order function.

Traditionally, copier, in the office equipment context, refers to light lens xerographic copiers in which paper originals are in fact photographed. The images are focused on an area of a photoreceptor, which is subsequently developed with toner. The developed image on the photoreceptor is then transferred to a copy sheet which in turn is used to create a permanent copy of the original.

In recent years, there has been made available what is known as digital copiers. And the most basic functions, a digital copier performs the same functions as a light lens copier, except that the original image to be copied is not directly focused on a photoreceptor. Instead, with a digital copier, the original image is scanned by a device generally known as a raster input scanner (RIS) which is typically in the form of the linear array of small photosensors.

The original image is focused on the photosensors in the RIS. The RIS converts the various light and dark areas of the original image to a set of digital signals. These digital signals are temporarily retained in a memory and then eventually used to operate a digital printing apparatus when it is desired to print copies of the original or a display screen when it is desired to display the image; i.e., the image is scanned and converted to electrical signals so that the image can be used for other reproduction purposes. The digital signals may also be sent directly to the printing device or display device without being stored in a memory. The digital printing apparatus can be any known type of printing system responsive to digital data, such as a modulating scanning laser which discharges image wide portions of a photoreceptor, or an ink jet printhead.

With the migration of the copying and scanning systems to a digital base system, the systems face different problems than from the light lens or analog copying systems. More specifically, in a digital scanning system, the scanning system needs to locate the actual location of the document so that any desired image processing routines can be applied to the correct pixels of image data.

In describing the present invention, the terms pixel will be utilized. This term may refer to an electrical (or optical, if fiber optics are used) signal which represent the physically measurable optical properties at a physically definable area on a receiving medium. The receiving medium can be any tangible document, photoreceptor, or marking material transfer medium. Moreover, the term pixel may refer to an electrical (or optical, if fiber optics are used) signal which represent the physically measurable optical properties at a physically definable area on a display medium. A plurality of the physically definable areas for both situations represent the physically measurable optical properties of the entire physical image to be rendered by either a material marking device, electrical or magnetic marking device, or optical display device.

Lastly, the term pixel may refer to an electrical (or optical, if fiber optics are used) signal which represents physical optical property data generated from a single photosensor cell when scanning a physical image so as to convert the physical optical properties of the physical image to an electronic or electrical representation. In other words, in this situation, a pixel is an electrical (or optical) representation of the physical optical properties of a physical image measured at a physically definable area on an optical sensor.

In a digital scanning system, it is desirable to perform the image processing routines only upon the image of the document and not upon the image data representing the backing of the platen cover in a platen scanning system or the backing roll in a document feeding system, such a constant velocity transport ("CVT") system. In this application, the term backing roll or backing will be used to describe the area scanned by the digital scanner which is not the document or desired image to be scanned.

Thus, it is important in a digital scanning system to determine the actual location of the document being scanned; i.e., the document's edges and document's width. This locating of the document is particularly important in an engineering document scanning system.

In an engineering document scanning system, the input document can be of any size ranging from 5 inches to more than 36 inches. Conventionally, in one method of determining the location of the document, a user would manually determine the document size and input the width, through a user interface, to the document scanning system before the document was actually scanned. In this conventional method, the document must be centered in the document scanning system to avoid the document image from being clipped.

This conventional manual method reduces productivity and causes wasted copies since a user cannot always input the correct width or center the document accurately in the document scanning. Thus, it would be desirable to have an auto-width detection system to determine the document's width and position when the document is being initially staged for scanning.

Various auto-width detection schemes have been proposed so as to determine the document's width and position when the document is staged; however, these detection methods have not been completely successful because the documents to be scanned in an engineering environment can be very similar to the backing, thus making it difficult to distinguish between the paper and the backing (backing roll or the backing of the platen cover).

This problem is accentuated when the scanner CCD sensor output fluctuates. Moreover, it is possible that a document and scanner can interact to produce an integrating cavity effect which will mask the edge location of the document.

One such conventional auto-width detection method captures a portion of the lead edge of a document that is staged wherein the captured portion of the lead edge includes both image data related to the backing and the document itself. In this automated process, the width and position of a document is calculated by determining whether each CCD sensor element is covered by a backing or document.

In other words, the width detection process becomes a classification process. Each CCD sensor element is either covered by the backing or document. To make this determination, the conventional automatic detection method utilizes the mean of each column of pixels of image data to differentiate between the document and the backing. Examples of this mean data are illustrated in FIGS. 3 and 5 of the present application.

However, since the document's brightness varies from very dark to very bright and since most bond paper and film documents have about the same brightness as the backing, the conventional auto-width detection process often fails to detect the actual location and width of the document. Moreover, since the conventional method relies solely on determining the location and width of the document from mean data, which corresponds to a first order function. The mean data is very susceptible to electrical noise within the CCD sensors or dust and dirt within the actual scanning system. In other words, any excessive electric noise, dust, or dirt could readily render the conventional auto-width detection process ineffective.

In addition to being sensitive to electrical noise, dust, and dirt, the conventional auto-width detection process requires a very sensitive filtering routine to detect the transition from the backing roll to the document, the document's edge. This can be seen in FIGS. 3 and 5 of the present application wherein the transitions from the backing to the document (at about pixel numbers 510 and 245, respectively) are represented by a very narrow pulse spike. Thus, the conventional process requires a very sensitive filtering routine to detect this transition which in turn makes the detection process very sensitive to electrical noise, dust, or dirt.

Therefore, it is desirable to have an automatic detection routine which can accurately detect the location and width of the document being scanned without being sensitive to electrical noise, dust, and/or dirt.

The present invention proposes a method and system for providing automatic detection of the width and position of a document which is substantially insensitive to dust and dirt as well as electrical noise wherein the present invention utilizes second order statistics, such as a standard deviation, in addition to the mean information to determine the actual edges of the document. By utilizing second order statistics, the transition between the backing and the document can be more readily found without the use of sensitive filtering routines.

One aspect of the present invention is a method for automatically detecting an edge of a document in a scanning system. This method scans a portion of the document, generates pixels of image data representing an image density, calculates a set of first values from the image data using a first order function, calculates a set of second values from the image data using a second order function, and determines a physical edge of the document from the set of first values and a set of second values.

Another aspect of the present invention is a system for automatically detecting an edge of a document in a scanning system. The system includes a scanner to scan a portion of the document and to generate pixels of image data representing an image density; first means for calculating a set of first values from the image data using a first order function; second means for calculating a set of second values from the image data using a second order function; and third means for determining a physical edge of the document from the set of first values and the set of second values.

Further objects and advantages of the present invention will become apparent from the following descriptions of the various embodiments and characteristic features of the present invention.

The following is a brief description of each drawing used to describe the present invention, and thus, are being presented for illustration purposes only and should not be limitative of the scope of the present invention, wherein:

FIG. 1 is a schematic of a typical digital scanning system;

FIG. 2 illustrates a typical leadedge image captured during document staging;

FIG. 3 is a graph illustrating mean data at a right edge of a document during document staging;

FIG. 4 is a graph illustrating standard deviation data at a right edge of a document during document staging;

FIG. 5 is a graph illustrating mean data at a left edge of a document during document staging;

FIG. 6 is a graph illustrating standard deviation data at a left edge of a document during document staging;

FIG. 7 illustrates the center clusters and spread of various documents and backing measurements according to the concepts of the present invention;

FIG. 8 is a graphical representation of a distance measurement in feature space according to the concepts of the present invention;

FIG. 9 is a graphical representation of a typical histogram of a document;

FIG. 10 is a block diagram showing a system for automatically detecting a width and position of a document according to the concepts of the present invention;

FIGS. 11 and 12 are flowcharts illustrating a method for automatically detecting a width and position of a document according to the concepts of the present invention; and

FIG. 13 is a graph illustrating the transition between the backing and a document's edge after a edge block has been determined according to the concepts of the present invention.

The following is a detailed description of the present invention. In this description and in the Figures, like reference numbers represent equivalent circuits and/or equivalent functions.

As noted above, FIG. 1 is a schematic of a typical digital scanning system. As illustrated in FIG. 1, a document 1 is scanned by a CCD sensor 7. In the particular system illustrated in FIG. 1, the document 1 is moved past the CCD sensor 7 through the use of a backing roll 3. The light reflected from the document 1 and the backing roll 3 passes through a lens system 5 which focuses the reflected light upon the CCD sensor 7. The reflected light is focused with respect to an optical center line 13. The reflected image of the document 9 is converted by the CCD sensor 7 into pixels of image data as well as the reflected image of the backing roll 11. Thus, the CCD sensor 7 produces pixels of image data which represent both the reflected image of the backing roll 11 and the reflected image of the document 9.

FIG. 2 illustrates a typical leadedge image captured during document staging. As illustrated in FIG. 2, the leadedge of the image is captured wherein the image data represents both the reflected image of the backing and the actual document. In the example illustrated in FIG. 2, the CCD sensor scans a width of 36 inches.

If the resolution of the CCD sensor is 200 dots per inch, the digital scanning system will produce 7200 pixels of image data per scanline. Each pixel of image data is then assigned a pixel location number from 1 to 7200 in a left to right orientation and a pixel location number from 1 to 7200 in a right to left orientation. These pixel location numbers then form columns of image data as more than one scanline of the leadedge image are captured during the document staging mode. For example, if the scanned leadedge is 25 scanlines, a pixel location number would be a column of 25 pixels wherein the image data of each of these pixels would have been created by the same photosite on the CCD.

An example of these columns of image data is illustrated by reference numeral 21 in FIG. 2. More specifically, a block 21 of columns is illustrated wherein the mean value and the standard deviation of each column is shown. More specifically, for example, for pixel location associated with column i, the mean value is X.sub.i and the standard deviation value is S.sub.i, while the pixel location associated with column i+1, the mean value is X.sub.i+1 and the standard deviation value is S.sub.i+1. These mean and standard deviation values associated with each column are utilized by the present invention in determining the actual edges and width of the document to be scanned.

Further examples of this column-formatted data is illustrated in FIGS. 3-6. More specifically, as noted above, FIG. 3 illustrates the mean values for the pixel locations between pixel 0 and pixel 1200 when scanning from a right to left direction (from backing to document), while FIG. 5 illustrates the mean value for each pixel location from pixel number 0 to pixel number 400 when scanning from a left to right direction. On the other hand, FIG. 4 illustrates the standard deviation value for the pixel locations between pixel number 0 and pixel number 1200 when scanning from a right to left direction, while FIG. 6 illustrates the standard deviation value for each pixel location from pixel number 0 to pixel number 400 when scanning from a left to right direction. In other words, FIGS. 3 and 4 correspond to reading the pixels of image data in a right to left manner while FIGS. 5 and 6 illustrate the reading of data associated with pixel locations in a left to right manner.

As is illustrated in FIGS. 3 and 5, it is difficult to detect the left and right edges of a document utilizing only the mean data because many sources can significantly contribute to the variation seen in the data. More specifically, although the backing has a constant reflectance, the linear CCD has varying response due to element to element variations (photosites on a CCD sensor or photosensor chips in a full width array), optics, and system (electrical) noise. Moreover, dust particles can appear in the image as vertical dark streaks and the documents themselves can vary tremendously due to their texture and fiber content. Lastly, as noted above, some document types such as film and bond paper have reflectance values similar to the backing.

Other sources of variation can be dark documents which cause a reflectance radiance to form near the document's edges, thereby causing the edges to appear as ramps, while dust particles cause various jumps that appear similar to the edge of a film or bond paper. The element to element variation in the CCD sensor or full width array along with system noise can cause reflectance variations that may mask edges. In other words, these various sources of variation cause the detecting of the left and right document edges to become very difficult when solely relying upon mean data.

On the other hand, as illustrated in FIGS. 4 and 6, second order values such as a standard deviation values are utilized in addition to the mean values. By utilizing these second values, values generated from a second order function, the sensitivity to the various sources of variation can be significantly reduced due to the wide gap between the standard deviation for the document and the standard deviation for the backing.

More specifically, for the CCD elements which are covered by the backing, the standard deviation is the sensor electronic noise since the backing is stationary during the scan. However, for the elements of the CCD sensor which are covered by the document, since the document moves during the scanning at document staging, the standard deviation consists of sensor electronic noise plus the document brightness variation. Typically, the document brightness variation is much larger than the sensor electronic noise, and thus, the standard deviation value provides a clean and significant gap when there is a transition from the backing to the document itself.

Moreover, the standard deviation value is more robust against dirt or dust on the backing. A dust or dirt particle on the backing will significantly reduce the mean value, but the sensor noise is still the same because it sees the same spot during the scan. In other words, the mean difference between the backing and the document can be masked by sensor noise and/or dust or dirt on the backing, while the standard deviation difference is clearly visible and well separated since these values are not significantly sensitive to electronic noise or dust and dirt.

In the preferred embodiment of the present invention, the signal-to-noise ratio is further enhanced by lowpass filtering done in the scanner. The image obtained from the scanner, for example, can be scanned at 400 spi and averaged over a 4-pixel-wide window on each scanline to produce a 100-spi image. The effect is to low-pass filter the image. On the backing roll, where the reflectance is independent and identically normally distributed, the variance of scanner noise is reduced by 1/2. But the paper noise has an approximate 1/f.sup.2 power spectrum. Low-pass filtering (averaging) has little effect. This increases the signal-to-noise ratio between the document and backing roll.

In view of the robustness of the standard deviation values, the present invention utilizes a method as illustrated in FIGS. 11 and 12 to determine the edges of the document wherein this method calculates the edges of the document from the mean value, standard deviation values and black pixel count values for each column of pixels of image data. As illustrated in FIG. 11, step S1 determines the background values from a histogram of the leadedge image of the document during document staging.

A typical histogram for an image is illustrated in FIG. 9 wherein the histogram 33 typically includes two separate peaks 31 and 37. Peak 31 represents the white peak value or document background value, while peak 37 represents the black peak value. These peak values, along with a width value 35 of the distribution of the white peak value, are utilized to determine a threshold values which will be utilized in determining whether a pixel is black or white, and whether the document covers the ends of the scanner.

After determining the background values from the histogram, step S2 determines the right and left edge distance. In the preferred embodiment of the present invention, the distance for the left edge is calculated using the following equation:

wherein LocMean is the mean of 8 column means on the left end of the CCD sensor, LocStd is the mean of 8 column standard deviations on the left end of the CCD sensor, LeftMean is scanner response to the backing roll, MEANTOL, STDTHD, and STDTOL are preset values, Wstd is the standard deviation weighting factor. In the preferred embodiment, Wstd=4 for dark substrate, and 2 for other documents. The right edge distance (DistRgt) is calculated using a similar equation with all the values being reflected onto the right side of the scanner device.

After completing step S2, the process determines the mean value, standard deviation value, and black pixel count value for each column of pixels associated with a single pixel location. More specifically, if the leadedge of a document scanned during the document staging contains 30 scanlines, the column of pixels for pixel location 50, for example, would contain 30 pixels of image data wherein each pixel of image data was produced by the same unit photocell of the CCD.

Once these values are calculated, step S4 groups the values for adjacent columns into blocks, in the preferred embodiment of the present invention, the block contains 5 columns of mean values, standard deviation values, and black pixel count values. After grouping the columns of pixel values into blocks, step S5 analyzes each block of data and classifies the block as either backing or document. If it is determined at step S6 that the block was classified as backing, step S7 updates the cluster center value and spread value which are functions of the mean value and standard deviation value of the blocks which have been analyzed. The actual calculations for these values will be discussed in more detail below.

Once all the blocks have been classified as either backing or document, step S9 calculates which block would most likely contain an edge location as well as determines the cost function or associated confidence factor which indicates a confidence level that the block does contain the edge of the document. The edge location is calculated utilizing an adaptive Euclidean distance formula: ##EQU1##

It is noted that the coefficients (a) and (z) are set according to an estimated document type which is determined utilizing the histogram peaks and spread of the histogram around the white peak as illustrated in FIG. 9. Moreover, it is noted that the average mean value (avgmean[i]) and the average standard deviation (avgstd[i]) are the cluster center coordinates for the backing (FIG. 7). The standard deviation of the mean (stddevmean[i-1]) and the standard deviation of the standard deviation (stddevstd[i-1]) provide the measure of the spread of the backing. Both the cluster center and the spread are dependent upon the scanner calibration, document brightness (integrated cavity effect), and scanner noise. Therefore, these values must be adaptable from scan to scan and from edge of the scanner to the document edge.

The calculation of the block having a possible edge location and cost function is carried out a predetermined number of times wherein each iteration of the calculation uses less stringent criteria and competence coefficients to determine whether an edge appears within a block. In other words, in each iteration of the calculation for the edge block location and cost function, the k.sub.-- factor values of the distance formula described above are changed. In the preferred embodiment of the present invention, the edge block location and associated cost function are calculated for three separate iterations using three different k.sub.-- factor values wherein the first k.sub.-- factor value is 2.5, the second k.sub.-- factor value is 3, and the last k.sub.-- factor value is 4.

After the iterations are complete, the edge block locations and associated cost functions for the different k factors are analyzed to find the best possible edge block location (the block location having the highest confidence level) at step S12. Utilizing the block having the best possible edge location, step S13 finds the physical edge of the document in the edge block utilizing a derivative method in two dimensional space.

The determination of the best possible edge block considers whether any of the three blocks agree and compares their associated cost functions. If two or more blocks locations agree, this block location is chosen as the best possible edge block location and the associated cost function is reduced or the confidence factor is increased. The chosen best possible edge block is further analyzed to detect whether there are any black pixels within the chosen block. Depending on whether any black pixels are found or whether the associated cost function is greater than a predetermined value, the chosen best possible edge block is maintained as the chosen edge block or the process indicates that there has been failure in detecting the edge of the document.

Prior to step 13, the edge location is found within the block 21 of FIG. 2. At step S13, the actual edge is determined by utilizing three pixel blocks; the chosen best possible edge block and the two adjacent blocks. These three blocks are analyzed utilizing a derivative method to determine which pixel location is the actual location of the physical edge of the document.

A software implementation example of the above described method is set forth in Table 1 below. This table sets forth an example of software code which carries out the functions described above to find the edges of a document using second statistics. Although the process of the present invention has been implemented in software, it can also be readily implemented in hardware.

FIG. 13 illustrates a possible example of this analysis wherein block 43 represents the best possible edge block and blocks 41 and 45 represent the adjacent blocks to the best possible edge block. The data in blocks 41, 43, and 45 are analyzed utilizing a derivative method until the pixel location 47 of the actual edge of the document is determined.

FIG. 7 is a graphical representation of the calculation of a cluster center or a backing value and the spread for a backing as well as the cluster center and spread values for a film document and a bond paper document. It is noted that cluster centers can move in response to the scanning across the image as well as from scan to scan. Although the data reflected in FIG. 7 appears roughly elliptical, this data becomes spherical around the point (locmean, locstd) when the data is normalized with respect to the standard deviation of the mean and the standard deviation of the standard deviation. An example of this normalized data is illustrated in FIG. 8.

As illustrated in FIG. 8, the center point of the sphere is (XO.sub.i, SO.sub.i) wherein XO.sub.i is the mean of the means of the previously analyzed blocks and SO.sub.i is the mean of the standard deviations of the previously analyzed blocks. Moreover, the spread of this data is equal to the standard deviation of the means of the previously analyzed blocks and the standard deviation of the standard deviations of the previously analyzed blocks. FIG. 8 also illustrates how the changing of the k factor in the distance formula changes the effect of the spread on the distance calculation.

As noted above, in determining whether a block would be chosen as the edge block location, the distance between the cluster center and a point represented by the coordinate (avgmean, avgstd), representing the present block being analyzed, is calculated. The greater the distance value, the more likely that the block contains document.

More specifically, the distance to probability relationship is clearly seen in FIGS. 3-6 wherein the transition points between the backing and the document cause jumps in the data thus indicating a significant distance between the mean and standard deviation of the block being analyzed and the mean of the means of the previously analyzed blocks and the mean of the standard deviations of the previously analyzed blocks.

When an edge is encountered, avgmean and avgstd will jump in value. The statistics locmean and locstd lag the rest, causing d.sub.i to increase suddenly. However, there may be false alarms. This is handled as follows.

Each scan of X (mean) and S (standard deviation) marks a status array with 0, 1, or 2 depending on whether d is less than or equal to a k.sub.-- factor, greater than the k.sub.-- factor or much greater than the k.sub.-- factor, the k.sub.-- factor being equal to k above in the distance equation. A zero (0) indicates `backing`, 1 means `probably in the document` and 2 means `definitely in the document`. For the first scan, k.sub.-- factor is set small, in the preferred embodiment 2.5, and then progressively larger on each scan (3 and 4 in the preferred embodiment). After the each scan, a status array contains values 0, 1, or 2. The status array is updated using the cost of misclassification (i.e., cost of type I or II errors) to yield edge candidates.

For example if x be such that status[x]=1 or 2, the cost associated with deciding that an edge is at x is computed as the sum of status[i], i<x, plus the count of 0's in status[i], i>x. The minimum cost position is the edge candidate. This is stored along with its misclassification cost.

In the preferred embodiment, after three scans with increasing k.sub.-- factor, three edge candidates plus their misclassification costs are produced. These three candidates are analyzed to create a single edge estimate and cost. These costs are converted into confidence coefficients 0, 1, or 2 which have the same meaning as before. The same procedure is used to estimate the both edges, just the scanning process going in opposite directions. This procedure estimates the edge to within 5 pixels in the preferred embodiment since a block consists of 5 pixel columns. The best (lowest cost) candidate is chosen to further pinpoint the edge.

To find the exact edge, the process uses the selected block and the two adjacent blocks to the left and right. This data is then re-configured, in the preferred embodiment into blocks of 3 pixel columns and the means and standard deviations are computed column-wise, yielding means mX.sub.i, mS.sub.i and standard deviations sX.sub.i, sS.sub.i, i=1, . . . ,BLOCK.sub.-- SIZE. These values are used in a distance calculation similar to the one described above:

wherein MEANTOL and STDTOL are preset values. The biggest jump of D.sub.i is used to estimate the edge within three pixels. Finally, the edge position is found by interpolating neighboring values. This step counteracts the effect of edge shadows produced by the integrating cavity effect.

FIG. 10 illustrates a block diagram of a circuit which is utilized to determine the edge location of the document to be scanned. As illustrated in FIG. 10, a CCD sensor array 100 produces image data which is fed into a histogram circuit 102, a mean calculation circuit 106, a standard deviation calculation circuit 105, and a buffer 107. The histogram circuit 102 determines the histogram of the image data as well as calculates the background values discussed above. These background values are then fed to memory 103 to be stored temporarily for further processing.

The mean calculating circuit 106 calculates the mean value for each column of pixels, as well as the other mean calculations discussed above, and sends the mean values to the memory 103. The standard deviation calculating circuit 105 receives the image data as well as mean data from memory 103 to determine the standard deviation, as well as the other standard deviation calculations discussed above, of the data for each column and sends the standard deviation values to the memory 103. An image determination circuit 104 which carries out the precise processes described above, is connected to memory 103 and buffer 107 so as to receive the proper data needed to calculate the physical edge of the document to be scanned.

As described above, the second order statistics (standard deviation S.sub.i) are used in addition to the mean to determine the document's edges. This utilization of second order statistics provide a more reliable process for detecting the edges and which is not sensitive to sensor electronic noise or dust and/or dirt.

Although the present invention has been described in detail above, various modifications can be implemented without departing from the spirit of the present invention. For example, the preferred embodiment of the present invention has been described with respect to a CCD sensor array; however, this auto-width detection method is readily implemented with a full width array scanning system. Moreover, the auto-width detection method of the present invention can be readily implemented on an ASIC, programmable gate array, or in software, thereby enabling the placement of this process in a scanner, electronic subsystem, printer, or display device.

Lastly, the present invention has been described with respect to a monochrome or black/white environment. However, the concepts of the present invention are readily applicable to a color environment. Namely, auto-width detection process of the present invention can be applied to each color space value representing the color pixel.

While the present invention has been described with reference to various embodiments disclosed herein before, it is not to be combined to the detail set forth above, but is intended to cover such modifications or changes as made within the scope of the attached claims. ##SPC1##