Connected component analysis with multi-thresholding to segment halftones

Systems and methods herein generally relate to image processing, and more particularly to segmentation of images into contone and halftone regions.

When devices are processing images, such as print, copy or scan jobs, different regions in the original image (such as contone, halftone, text and lines) are usually processed differently for rescreening or for compression. Separation of the text region from the rest of the objects is one challenge in the segmentation of images.

Separation of text and halftone regions in a document image is useful for numerous purposes such as for avoiding image quality artifacts when rescreening the image while copying, for better text recognition using OCR on scanned documents, for any type of information extraction such as data in forms, etc., and for better image compression performance.

Exemplary methods herein receive an input image into a computerized device and convert the input image into a grayscale image using the computerized device. These methods also assign blocks to areas of the grayscale image using the computerized device and calculate at least two different gray tone variation threshold measures for each of the blocks based on dynamic maximum and minimum gray tone intensity values and white background values within each of the blocks using the computerized device. Then, these methods can adjust the dynamic range of pixel intensity of the input image using parameters based on background suppression modules.

Such methods create different binary images by applying such different gray tone variation threshold measures to each of the blocks of the grayscale image using the computerized device. The binary images are created simultaneously in parallel processing that can potentially process all blocks simultaneously.

These methods can then identify connected components of a first binary image of the binary images using the computerized device, and compare pixels of each of the connected components of the first binary image with corresponding pixels of a second binary image of the binary images to identify pixel differences. Such pixel differences include white pixel count differences and white-black pixel transition differences. These methods identify halftone areas within the input image based on such pixel differences exceeding limits, using the computerized device. Further, such methods remove the halftone areas from the input image to produce a non-halftone image, which allows these methods to more easily identify connected components in the non-halftone image.

Exemplary image processing and printing devices herein comprise an input/output device receiving an input image and a processor operatively connected to the input/output device (and, if devices have printing capability, can include a marking engine operatively connected to the processor). The processor converts the input image into a grayscale image. Then, the processor can adjust the dynamic range of pixel intensity of the grayscale image using parameters based on background suppression modules. The processor also assigns blocks to areas of the grayscale image and calculates at least two different gray tone variation threshold measures for each of the blocks based on dynamic maximum and minimum gray tone intensity values and white background values within each of the blocks.

Also, the processor creates different binary images by applying such different gray tone variation threshold measures to each of the blocks of the grayscale image. The binary images are created simultaneously in parallel processing that can potentially process all blocks simultaneously.

The processor can then identify connected components of a first binary image of the binary images, and compare pixels of each of the connected components of the first binary image with corresponding pixels of a second binary image of the binary images to identify pixel differences. Such pixel differences include white pixel count differences and white-black pixel transition differences. The processor identifies halftone areas within the input image based on such pixel differences exceeding limits. Further, such a processor removes the halftone areas from the input image to produce a non-halftone image, which allows the processor to more easily identify connected components in the non-halftone image. The processor treats the halftone areas differently relative to other areas of the input image when printing the input image using the marking engine.

These and other features are described in, or are apparent from, the following detailed description.

Various exemplary systems and methods are described in detail below, with reference to the attached drawing figures, in which:

FIG. 1 is a flow diagram of various methods herein;

FIG. 2 is an illustration of an image processed according to methods herein;

FIG. 3 is a schematic diagram illustrating systems herein;

FIG. 4 is a schematic diagram illustrating devices herein; and

FIG. 5 is a schematic diagram illustrating devices herein.

As mentioned above, separation of the text region from the rest of the objects is one challenge in the segmentation of images. Connected component based segmentation is effective for halftone detection, but the threshold dot frequency used in segmentation has to be robust enough to handle a wide range of halftone dot frequency variations. For purposes herein, binarization classifies a region as being a halftone region or not being a halftone region, and connected component based segmentation is an analysis that identifies items that are connected, and therefore continuous in the image (such as text).

When using a single threshold during binarization processing, low dot frequency halftone regions may be processed into visible on/off halftone dots with comparatively larger dot size. While, when using the same threshold in a high dot frequency halftone region, the same binarization may not produce visible on/off halftone dots, or any dots produced is smaller in size. Therefore, when performing connected component based analysis, size based classification is difficult, and the single threshold must be chosen with precision as larger dot sizes in lower dot frequency regions may be misclassified as text, and lesser visible or non-existent dots in the higher dot frequency regions will incorrectly be classified as contone region.

The systems and methods herein perform thresholding and connected component analysis for segmenting text and halftone regions using multiple thresholds. The multi-thresholding processes herein use two or more thresholds to generate two or more binary images from an input image. Using multiple thresholds captures a wider range of halftone frequencies that a single threshold, thereby overcoming one of the challenges of connected component based halftone segmentation. A single threshold from a histogram will not separate the text and halftone as different connected components. The relative run length and relative white pixel count between the multiple binary images generated from the multi-thresholding processing are utilized for halftone detection.

The thresholding process herein uses a block-based approach, which leverages the multi-core architecture and vector processor of modern processing units for optimal implementation of the approach in high speed devices. Therefore, this disclosure presents a framework for segmenting text and halftone region in an image. For a connected component based approach, the input image is thresholded to form a binary image. More specifically, the given image is block level binarized twice (in parallel) to generate two binary images. The thresholds are calculated from background white-point and local pixel values.

Connected regions in the binary image are then labeled. Each labeled feature is analyzed and classified as being halftone or non-halftone regions. One specific feature analyzed is the variation in the gray tone. If proper thresholding is not employed, the gray tone variation may not be distinct enough to properly identify halftone regions. The two binarized images are further analyzed to separate the halftone and text regions in an image.

Reference is now made to the flowchart shown in FIG. 1 , which illustrates aspects of systems and methods herein. More specifically, in item 100 , an image is input by being scanned, delivered, retrieved from memory, or any other conventional process to acquire an image.

In item 102 , these systems and methods convert the input image into a grayscale image using the computerized device. These methods can adjust the dynamic range of pixel intensity of the input image using parameters based on background suppression modules in item 104 . These methods also assign blocks to areas of the grayscale image to divide the image into blocks using the computerized device in item 106 . More specifically, in item 106 , the grayscale, range adjusted image is divided into blocks (or other geometric regions) by assigning geometric features to the image.

In item 108 , these methods calculate at least two different gray tone variation threshold measures for each of the blocks. In the processing in item 108 gray tone variation threshold measures are calculated based on dynamic maximum and minimum gray tone intensity values and white background values within each of the blocks using the computerized device.

In item 110 , such methods create different binary images by applying the different gray tone variation threshold measures (produced in item 108 ) to each of the blocks of the grayscale image (produced in item 104 ) using the computerized device. In a very general sense, a “thresholding” process looks at each pixel value in an image, compares the intensity level (e.g., gray level) of that pixel against a threshold value (such as medium gray) and then changes that pixel's value to black or white ( 0 or 1 ) depending upon whether the pixel's value exceeds the threshold value. In this way, the thresholding process acts to filter out certain intensity levels that are below the threshold from the analysis. As would be understood by those ordinarily skilled in the art, there are many very sophisticated forms of thresholding images, and the term thresholding is intended to include all known processes of applying tone intensity variation measures, whether currently known or developed in the future.

The binary images are created simultaneously in parallel processing by the thresholding process in item 110 . For example, in such parallel processing, all images can be processed simultaneously, or even all blocks within all images can potentially be processed simultaneously, depending upon the capabilities of the processor.

These methods then can identify and label connected components of at least one “first” binary image of the binary images using the computerized device in item 112 . Then, in item 114 , these methods compare pixels of each of the connected components of the first binary image with corresponding pixels of at least one “second” binary image of the binary images to identify pixel differences. Such pixel differences between the first and second binary images found in item 114 include white pixel count differences and white-black pixel transition differences.

With the results from item 114 , these methods identify halftone areas within the input image in item 116 based on such pixel differences exceeding limits, using the computerized device. Such pixel differences can be changed to change the sensitivity of the systems and methods herein. Once the halftone areas are identified in item 116 , such methods can remove the halftone areas from the input image to produce a non-halftone image in item 118 , which allows these methods to more easily identify contone features in the non-halftone image in item 120 . Therefore, these processes identify halftone areas (item 116 ) and contone features (item 120 ) and process such different areas differently when printing, displaying, transmitting, and storing such input images in item 122 .

More specifically, in item 104 , the grayscale image can be preprocessed by adjusting the dynamic range of the pixel's intensity to obtain an image ‘I’. The parameters for adjustment are drawn from existing background suppression modules that are widely available to those ordinarily skilled in the art.

Generally, halftone regions can be identified effectively by measuring the dot frequency of gray tone variation; however, in a halftone region, the transitions in gray level vary inconsistently. An effective thresholding method is useful to capture the gray tone variation, but it is difficult to capture all the transitions using a single threshold. Therefore, with systems and methods herein, block based bimodal thresholding is applied in item 110 to generate at least two binary images from the scanned image; and at least two different approaches are adopted in calculating the local threshold for the block in item 108 . This enables capturing the different frequencies of gray level transitions in halftone regions.

The following discussion presents the two different adaptive thresholding approaches applied in item 110 to convert the gray tone image ‘I’ into binary images ‘I 1 ’ and ‘I 2 ’ respectively.

The gray tone image is split into blocks of distinct m×n pixels kernel size, represented as ‘B’.

(i) In Binary image I 1 , for each block m×n

where

max B & min B are the maximum and minimum intensity values in the block ‘B’ in I 1 . WhitePoint is the white point value obtained from background suppression module. B U & B L are the constants representing upper and lower block thresholds limits. w 1 & w 2 are gain values.

If the difference between the max intensity and min intensity in the block falls within the B U & B L range—the threshold is selected as (max B +min B )*w 1 ; which enables to select a mid threshold value. In this work w 1 is selected as 0.4 and B U & B L are selected as ‘200’ and ‘0’ in one embodiment. However, this is just an example and each different application could use different values.

If the difference between the max intensity and min intensity in the block does not fall within the B U & B L range, there is large intensity change. In this case WhitePoint is scaled with w 2 as threshold, here w 2 is selected as 1.05. Since the segmentation is applied on the background suppressed image, w 2 is selected higher than 1.

(ii) For Binary image I 2 , for each block m×n

where

max B & min B are the maximum and minimum value in a block (B) for I 2 .

B T1 , BT2 & B T3 are the ranges for t (B) 2 t 1 , t 2 , t 3 and t 4 are the threshold ranges selected through experimentations as

As mentioned above in item 112 , connected components are identified and labeled. Connected component based processing is performed on the binary image ‘I 1 ’. Labels are assigned to each group of connected binary pixels for the image ‘I 1 ’. Let the total number of labels in ‘T 1 ’ be ‘N’ and let I 1 (X) refer to X th label in the image I 1 and [M x , N x ] refers to the set of coordinates of the pixels in label ‘X’.

[Connected component labeling is applied only to I 1 and not applied to image I 2 ].

As mentioned above, in item 114 , the pixels of the connected components are compared with corresponding pixels in the second binary image, and in one example can filter the halftone region using a white pixel count, and in another can filter the halftone regions using transition.

The number of white pixels in every label I 1 (X) and number of white pixels in the I 2 (M x, Nx ) are analyzed. [I 2 (M x, Nx ) represents the regions in image I 2 having coordinates of label X]. Detecting the above features will assist to segment the halftone regions from the non-halftone regions separately.

Next, the white pixel count is determined by calculating the following aspects.

For each label ‘X’ in I 1 , Let

(i) Area A(x) be the total number of pixels in label ‘X’ (ii) wc 1 (X) be the number of white pixels in label ‘X’ of image I 1 (iii) wc 2 (X) be the number of white pixels in the set (M x ,N x ) of image I 2 (iv) I s (X) be the resultant segmented tag plane.

T wc is constant threshold for white count w 3 is gain value.

Threshold and gain values are selected through experimentations with respect to input image resolution.

The labels that do not satisfy the white-count conditions are further analyzed through a transition condition in item 114 . Here, the transition refers to rate of switching between white pixel to black pixel and its vice-versa. Measured transition count in I 1 (X) and I 2 (M x ,N x ) are utilized in this step to detect the halftone region.

Let

(i) ‘z 1 ’ be set of horizontal scanlines in the label ‘X’ of image I 1 sampled to measure transition. (ii) ‘z 2 ’ be set of vertical scanlines in the label ‘X’ of image I 1 sampled to measure transition. (iii) TR 1 (z 1 ) be number of transitions along z 1 of label ‘X’ in Image I 1 . (iv) TR 1 (z 2 ) be number of transitions along z 2 of label ‘X’ in Image I 1 . (v) TR 2 (z 1 ) be number of transitions along z 1 in I 2 (M x ,N x ). (vi) TR 2 (z 2 ) be number of transitions along z 2 in I 2 (M x ,N x ). (vii) ‘X h ’, ‘X w ,’ be the height and width of the label ‘X’ respectively.

C = { C + 1 if ⁢ ⁢ TR 1 ⁡ ( z 1 ) > TR 2 ⁡ ( z 1 ) C otherwise ;

C = { C + 1 if ⁢ ⁢ TR 1 ⁡ ( z 2 ) > TR 2 ⁡ ( z 2 ) C otherwise ;

I s will became a tag plane for the input image I′, which will have ‘0’ for halftone regions and ‘1’ for non halftone regions, which will be text and lines.

In a multi-core architecture, label's feature calculation and filtering can be done in parallel. This method can be further optimized using vector processors.

FIG. 2 illustrates images in various stages of the above processing. More specifically, item 250 shows an image after it has been converted to grayscale (item 102 ) and the range has been dynamically adjusted. From this, the block-based binary processing creates two images 252 and 254 by applying different thresholds (item 110 ). Finally, based on pixel differences between the blocks in images 252 and 254 , the non-halftone image 256 is produced in item 118 . Note that in FIG. 2 , the blocks are shown as being within a grid on items 252 and 254 . Again, each block can be thresholded in parallel with all other blocks to make processing faster and more efficient.

As shown in FIG. 3 , exemplary system systems and methods herein include various computerized devices 200 , 204 located at various different physical locations 206 . The computerized devices 200 , 204 can include print servers, printing devices, personal computers, etc., and are in communication (operatively connected to one another) by way of a local or wide area (wired or wireless) network 202 .

FIG. 4 illustrates a computerized device 200 , which can be used with systems and methods herein and can comprise, for example, a print server, a personal computer, a portable computing device, etc. The computerized device 200 includes a controller/processor 224 and a communications port (input/output) 226 operatively connected to the processor 224 and to the computerized network 202 external to the computerized device 200 . Also, the computerized device 200 can include at least one accessory functional component, such as a graphic user interface assembly 236 that also operate on the power supplied from the external power source 228 (through the power supply 222 ).

The input/output device 226 is used for communications to and from the computerized device 200 . The processor 224 controls the various actions of the computerized device. A non-transitory computer storage medium device 220 (which can be optical, magnetic, capacitor based, etc.) is readable by the processor 224 and stores instructions that the processor 224 executes to allow the computerized device to perform its various functions, such as those described herein. Thus, as shown in FIG. 4 , a body housing has one or more functional components that operate on power supplied from an alternating current (AC) source 228 by the power supply 222 . The power supply 222 can comprise a power storage element (e.g., a battery, etc).

FIG. 5 illustrates a computerized device that is a printing device 204 , which can be used with systems and methods herein and can comprise, for example, a printer, copier, multi-function machine, multi-function device (MFD), etc. The printing device 204 includes many of the components mentioned above and at least one marking device (printing engines) 210 operatively connected to the processor 224 , a media path 216 positioned to supply sheets of media from a sheet supply 214 to the marking device(s) 210 , etc. After receiving various markings from the printing engine(s), the sheets of media can optionally pass to a finisher 208 which can fold, staple, sort, etc., the various printed sheets. Also, the printing device 204 can include at least one accessory functional component (such as a scanner/document handler 212 , etc.) that also operates on the power supplied from the external power source 228 (through the power supply 222 ).

Consistent with the previous description, exemplary image processing and printing devices herein 200 , 204 comprise an input/output device 226 receiving an input image and a processor 224 operatively connected to the input/output device 226 (and, if devices have printing capability, can include a marking engine 210 operatively connected to the processor 224 ). The processor 224 converts the input image into a grayscale image. The processor 224 also assigns blocks to areas of the grayscale image and calculates at least two different gray tone variation threshold measures for each of the blocks based on dynamic maximum and minimum gray tone intensity values and white background values within each of the blocks. Then, the processor 224 can adjust the dynamic range of pixel intensity of the input image using parameters based on background suppression modules.

Also, the processor 224 creates different binary images by applying such different gray tone variation threshold measures to each of the blocks of the grayscale image. The binary images are created simultaneously in parallel processing that can potentially process all blocks simultaneously.

The processor 224 can then identify connected components of a first binary image of the binary images, and compare pixels of each of the connected components of the first binary image with corresponding pixels of a second binary image of the binary images to identify pixel differences. Such pixel differences include white pixel count differences and white-black pixel transition differences. The processor 224 identifies halftone areas within the input image based on such pixel differences exceeding limits. Further, such a processor 224 removes the halftone areas from the input image to produce a non-halftone image, which allows the processor 224 to more easily identify connected components in the non-halftone image. The processor 224 treats the halftone areas differently relative to other areas of the input image when printing the input image using the marking engine 210 .

Many computerized devices are discussed above. Computerized devices that include chip-based central processing units (CPU's), input/output devices (including graphic user interfaces (GUI), memories, comparators, processors, etc. are well-known and readily available devices produced by manufacturers such as Dell Computers, Round Rock Tex., USA and Apple Computer Co., Cupertino Calif., USA. Such computerized devices commonly include input/output devices, power supplies, processors, electronic storage memories, wiring, etc., the details of which are omitted herefrom to allow the reader to focus on the salient aspects of the systems and methods described herein. Similarly, scanners and other similar peripheral equipment are available from Xerox Corporation, Norwalk, Conn., USA and the details of such devices are not discussed herein for purposes of brevity and reader focus.

The terms printer or printing device as used herein encompasses any apparatus, such as a digital copier, bookmaking machine, facsimile machine, multi-function machine, etc., which performs a print outputting function for any purpose. The details of printers, printing engines, etc., are well-known and are not described in detail herein to keep this disclosure focused on the salient features presented. The systems and methods herein can encompass systems and methods that print in color, monochrome, or handle color or monochrome image data. All foregoing systems and methods are specifically applicable to electrostatographic and/or xerographic machines and/or processes.

For purposes herein, a “pixel” refers to the smallest segment into which an image can be divided. Received pixels of an input image are associated with a color value defined in terms of a color space, such as color, intensity, lightness, brightness, or some mathematical transformation thereof. Pixel color values may be converted to a chrominance-luminance space using, for instance, a RBG-to-YCbCr converter to obtain luminance (Y) and chrominance (Cb,Cr) values. It should be appreciated that pixels may be represented by values other than RGB or YCbCr.

Thus, an image input device is any device capable of obtaining color pixel values from a color image. The set of image input devices is intended to encompass a wide variety of devices such as, for example, digital document devices, computer systems, memory and storage devices, networked platforms such as servers and client devices which can obtain pixel values from a source device, and image capture devices. The set of image capture devices includes scanners, cameras, photography equipment, facsimile machines, photo reproduction equipment, digital printing presses, xerographic devices, and the like. A scanner is one image capture device that optically scans images, print media, and the like, and converts the scanned image into a digitized format. Common scanning devices include variations of the flatbed scanner, generally known in the arts, wherein specialized image receptors move beneath a platen and scan the media placed on the platen. Modern digital scanners typically incorporate a charge-coupled device (CCD) or a contact image sensor (CIS) as the image sensing receptor(s). The scanning device produces a signal of the scanned image data. Such a digital signal contains information about pixels such as color value, intensity, and their location within the scanned image.

Further, an image output device is any device capable of rendering the image. The set of image output devices includes digital document reproduction equipment and other copier systems as are widely known in commerce, photographic production and reproduction equipment, monitors and other displays, computer workstations and servers, including a wide variety of color marking devices, and the like.

To render an image is to reduce the image data (or a signal thereof) to viewable form; store the image data to memory or a storage device for subsequent retrieval; or communicate the image data to another device. Such communication may take the form of transmitting a digital signal of the image data over a network.

A contone is a characteristic of a color image such that the image has all the values (0 to 100%) of gray (black/white) or color in it. A contone can be approximated by millions of gradations of black/white or color values. The granularity of computer screens (i.e., pixel size) can limit the ability to display absolute contones. The term halftoning means a process of representing a contone image by a bi-level image such that, when viewed from a suitable distance, the bi-level image gives the same impression as the contone image. Halftoning reduces the number of quantization levels per pixel in a digital image. Over the long history of halftoning, a number of halftoning techniques have been developed which are adapted for different applications.

Traditional clustered dot halftones were restricted to a single dot frequency because they were generated using periodic gratings that could not be readily varied spatially. Halftoning techniques are widely employed in the printing and display of digital images and are used because the physical processes involved are binary in nature or because the processes being used have been restricted to binary operation for reasons of cost, speed, memory, or stability in the presence of process fluctuations. Classical halftone screening applies a mask of threshold values to each color of the multi-bit image. Thresholds can be stored as a matrix in a repetitive pattern. Each tile of the repetitive pattern of the matrix is a halftone cell. Digital halftones generated using threshold arrays that tile the image plane were originally designed to be periodic for simplicity and to minimize memory requirements. With the increase in computational power and memory, these constraints become less stringent. Digital halftoning uses a raster image or bitmap within which each monochrome picture element or pixel may be ON or OFF (ink or no ink). Consequently, to emulate the photographic halftone cell, the digital halftone cell contains groups of monochrome pixels within the same-sized cell area.

Further, the terms automated or automatically mean that once a process is started (by a machine or a user), one or more machines perform the process without further input from any user.

It is appreciated that the above-disclosed and other features and functions, or alternatives thereof, may be desirably combined into many other different systems or applications. Various presently unforeseen or unanticipated alternatives, modifications, variations, or improvements therein may be subsequently made by those skilled in the art which are also intended to be encompassed by the following claims. Unless specifically defined in a specific claim itself, steps or components of the systems and methods herein cannot be implied or imported from any above example as limitations to any particular order, number, position, size, shape, angle, color, or material.