Patent No. 7,724,981 has been awarded to Donald B. Curtis of Highland, Utah, then assigned to Ancestry.com Operations Inc. of Provo. The patent title is "Adaptive contrast control systems and methods" which doesn't sound like a genealogy product. However, a closer examination shows that it might become one of the most valuable inventions of all time for genealogists.
"Adaptive contrast control systems and methods" really means "improving the quality of electronic documents through adaptive contrast control." In other words, making illegible documents legible again.
"Adaptive contrast control systems and methods" really means "improving the quality of electronic documents through adaptive contrast control." In other words, making illegible documents legible again.
Quoting from the patent:
[0002] With the introduction of the Internet, digital content services are becoming increasingly popular. Companies digitize documents, books, official records, and so on, and make them available to subscribing customers. Thus, scanning and digitizing documents has become an important industry.You can read more at http://www.wipo.int/pctdb/en/wo.jsp?wo=2007014014
[0003] Several problems exist with digital documents. For example, digitized documents are sometimes difficult to read. Reasons for this include poor source documents (e.g., the documents may be too dark, too light (faded), or be old and yellowed, fragile or degenerating) and poor scanning equipment or processes. Persons with less than ideal eye sight often struggle to read digitized documents, and eye strain, even in people with excellent vision, may reduce the effectiveness of reading digitized documents. Many digitized documents are also difficult to read/interpret by automated processes such as OCR. Further, digitized documents are often large in size and require substantial resources to store and significant time to download.
[0004] Others have attempted to solve these problems in several ways. For example, some have used "thresholding" to improve the quality of digitized images. Thresholding is used to convert a gray-scale or color document to a black and white (bitonal) image. The resulting image has very high contrast and is highly compressible. Choosing an appropriate threshold that results in a readable document, however, is an exceptionally difficult problem. Many techniques have been suggested. Some of these techniques are adaptive, that is, they analyze each area of the document independently to determine appropriate thresholds for each area. None of these techniques are reliable enough, however, (especially with hand-written documents) to provide significant confidence that the original document data will not be lost or significantly degraded. Also, adaptive techniques are often computationally expensive, prohibiting their use in real-time or semi-real time situations.
[0005] Others have attempted to use "leveling," which involves choosing the black point and white point (and sometimes the mid-tone) of an image and then interpolating the values of the image based on those values. Auto-leveling analyzes the image to determine the black point and white point of the image automatically, typically based on the histogram of the image (noting where a significant number of values start and end in the histogram). The problem with both leveling and auto-leveling is that different parts of the image may be darker or lighter than other parts, and global image leveling may improve parts of the image without improving others. Also, because the leveling is done based on the entire range of the image, the leveling may be reduced in its effect and not result in as much contrast in the resultant image as is desired.
[0006] Still others have used brightness and/or contrast adjustments. Adjusting the brightness or contrast of a document, whether manually or automatically, has similar disadvantages to the leveling process in that this process is typically done globally across an entire image, not giving the results required for any given sub-location of the image.
[0007] For at least the foregoing reasons, improved systems and methods are needed for improving digitized images.
BRIEF SUMMARY OF THE INVENTION
[0008] Embodiments of the invention provide a method of operating on an image of a document. The method includes, for an electronic file that includes a representation of the document, portioning the representation of the document into non-overlapping areas. Each area includes a matrix of pixels and each pixel has an initial grayscale value and a position in the matrix. The method also includes, for each area, determining a black point value and a white point value. The method further includes, for each pixel in each area, determining a revised pixel grayscale value for the pixel using the pixel's grayscale value, the pixel's position in the matrix, the black point value for the area comprising the pixel, the white point value for the area comprising the pixel, the black point value for at least one area adjacent to the area comprising the pixel, and/or the white point value for at least one area adjacent to the area comprising the pixel. The method also includes producing the image of the document using the revised grayscale values for each pixel.
[0009] In some embodiments, the black point and white point values are determined for each area before a revised pixel value is determined for any given pixel. Producing the image of the document may include printing an image of the document with a facsimile machine, printing an image of the document with a printer, printing an image of the document with a facsimile machine, and/or rendering the image on a display. The method may include
receiving an electronic file that includes. Receiving a representation of the document may include creating the electronic file using a scanner, extracting the electronic file from computer-readable memory, receiving the electronic file at a facsimile machine, creating the electronic file using a copy machine, and/or creating the electronic file using a facsimile machine.
[0010] In some embodiments, determining a black point value and a white point value for each area may include determining a threshold value, determining a background mean and a background standard deviation using pixel grayscale values of pixels having an initial grayscale value on one side of the threshold value, determining a foreground mean and a foreground standard deviation using pixel grayscale values of pixels having an initial grayscale value on an opposite side of the threshold value, receiving a background constant and a foreground constant, calculating the white point value (WP) using the formula WP = backMean + (backStdDev * backConstant), wherein backMean is the background mean, backStdDev is the background standard deviation, and backconstant is the background constant, and calculating the black point value (BP) using the formula BP = foreMean + (foreStdDev * foreConstant), wherein foreMean is the foreground mean, foreStdDev is the foreground standard deviation, and foreconstant is the background constant.
[0011] In still other embodiments, determining a threshold value may include selecting a value that is equidistant from a mean of pixel grayscale values below the threshold value and a mean of pixel grayscale values above the threshold value. Receiving a background constant and a foreground constant may include receiving a user input for at least one of the background constant and the foreground constant. Determining a revised pixel grayscale value for each pixel may include calculating a weighted black point (WBP) for the pixel, calculating a weighted white point (WWP) for the pixel, calculating a scale factor (SF) for the pixel using the formula SF = (GS/(WWP - WBP)), wherein GS is the number of possible values for the pixel's grayscale value, and calculating the revised pixel grayscale value using the formula RPV = (PV - WBP) x SF, wherein PV is the pixel's initial grayscale value. The grayscale value may be a color grayscale value for a primary color in which case the method may include repeating the process for at least a second primary color.
[0012] In still other embodiments, a system for operating on an image of a document includes a processor and computer-executable instructions that program the processor to receive an electronic file that includes a representation of the document, portion the representation of the document into non-overlapping areas. Each area includes a matrix of pixels, each pixel having an initial grayscale value and a position in the matrix. The instructions also program the processor to, for each area, determine a black point value and a white point value, for each pixel in each area, determine a revised pixel grayscale value for the pixel using the pixel's grayscale value, the pixel's position in the matrix, the black point value for the area comprising the pixel, the white point value for the area comprising the pixel, the black point value for at least one area adjacent to the area comprising the pixel, and/or the white point value for at least one area adjacent to the area comprising the pixel. The instructions also program the processor to produce the image of the document using the revised pixel grayscale value for each pixel.
[0013] In still other embodiments, a computer-readable medium has stored thereon computer-executable instructions for programming a processor to operate on an image of a document. The instructions program the processor to, receive an electronic file that includes a representation of the document, portion the representation of the document into non- overlapping areas. Each area includes a matrix of pixels, each pixel having an initial grayscale value and a position in the matrix. The instructions also program the processor to, for each area, determine a black point value and a white point value, for each pixel in each area, determine a revised pixel grayscale value for the pixel using the pixel's grayscale value, the pixel's position in the matrix, the black point value for the area comprising the pixel, the white point value for the area comprising the pixel, the black point value for at least one area adjacent to the area comprising the pixel, and/or the white point value for at least one area adjacent to the area comprising the pixel. The instructions also program the processor to produce the image of the document using the revised pixel grayscale value for each pixel.
[0014] In still other embodiments, a method of operating on an image of a document includes, for an electronic file that includes a representation of the document, portioning the representation of the document into non-overlapping areas. Each area includes a matrix of pixels. Each pixel has an initial grayscale value and a position in the matrix. The method includes, for each area, determining a black point value and a white point value, for each area, determining a confidence value, for each area, determining a revised black point value and a revise white point value by applying the confidence value to the black point value and the white point value, for each pixel in each area, determining a revised pixel grayscale value for the pixel using the revised white point value and the revised black point value; and producing the image of the document using the revised pixel grayscale value for each pixel.
[0015] In some embodiment, determining a revised pixel grayscale value for each pixel in each area includes determining a revised pixel grayscale value for each pixel in each area using the pixel's initial grayscale value, the pixel's position in the matrix, the revised black point value for at least one area adjacent to the area comprising the pixel, and/or the revised white point value for at least one area adjacent to the area comprising the pixel. Determining a confidence value for each area may include determining a confidence value in relation to a difference magnitude between the black point value and the white point value. Determining a confidence value for each area may include determining a confidence value based on a histogram of pixel grayscale values in the area. Determining a confidence value for each area may include determining a confidence value based on a directional correlation among black point values and white point values in adjacent areas.
