US 6,205,248 B1Granted

Method and system for compressing data in a multi-channel image processing system

AssigneeNCR Corporation

InventorJohn O. G. Vieth

Life of this patent

Estimating the term…

Loading patent…

Abstract

A system and method for processing image data from a document and for producing a compressed binarized version of the image data for transmission to or use by subsequent users. Processing of the image data is done in parallel after the scanning of the document is started but before the entire document is scanned. A splitter is used to divide a scan line of image data produced by an imager at the scan line into a plurality of channels, with each channel having at least one overlap area of pixels and with the overlap areas of pixels being used to avoid errors between channels. Thresholding and compression are performed by each one of the channels in parallel. The compression is performed in a direction which is perpendicular to the direction of scanning and conforms to a standard compression algorithm like CCITT Group 4.

Claims10

Dependent claims

A method of compressing non-transposed data comprising the steps:

(a) receiving successive non-transposed columns of binary pixels representing data on a document using a document scanner, with said successive non-transposed columns of binary pixels including a first non-transposed column of binary pixels and a last non-transposed column of binary pixels to be processed, said successive non-transposed columns of binary pixels being derived from the same document;
(b) using an examining window to extend over a predetermined number of said successive non-transposed columns along a direction which is perpendicular to the direction of said columns so as to present a row of said binary pixels, with said using step using only one binary pixel from each of said non-transposed columns of binary pixels for said row of binary pixels;
(c) generating a change of color bit for each of the binary pixels in the examining window, starting with said first non-transposed column of binary pixels while said examining window is moved towards said last non-transposed column of binary pixels;
(d) examining a pixel in a target row under consideration in said window with regard to a reference row and designating coding according to a predetermined code which uses said reference row for compressing pixels in said target row, with said reference row and said target row being perpendicular to said successive non-transposed columns of binary pixels;
(e) compressing said target row starting with said first non-transposed column of binary pixels while said examining window is moved towards said last non-transposed column of binary pixels, with said compressing step (e) being initiated after receiving said first non-transposed column of binary pixels but before said last non-transposed column of binary pixels is received;
(f) repeating steps (b), (c), (d), and (e) for the remaining non-transposed columns of binary pixels on the document.

3 more elements

A method of processing non-transposed data comprising the steps of:

(a) scanning a document using a document scanner in a first direction to generate successive non-transposed scan lines of pixels corresponding to an image on the document, with said successive non-transposed scan lines of pixels including a first non-transposed scan line of pixels and a last non-transposed scan line of pixels to be processed, said successive non-transposed scan lines of pixels being derived from the same document;
(b) dividing each non-transposed scan line of pixels into a plurality of processing channels so that each processing channel comprises a predetermined number of the pixels in each of said scan lines and each processing channel has boundaries which are aligned in a second direction which is perpendicular to said first direction;
(c) accumulating a predetermined number of said non-transposed scan lines of pixels as successive non-transposed scan lines are generated prior to performing compression on said pixels, with said predetermined number of non-transposed scan lines having an oldest non-transposed scan line and a newest non-transposed scan line therein;
(d) compressing the predetermined number of non-transposed scan lines of pixels in each of the processing channels simultaneously so as to perform parallel compression, with the compression in each processing channel being performed by using a reference row which is parallel to a target row being compressed, with the reference and target rows being perpendicular to said first direction and parallel to said boundaries of said processing channels, and with said compressing being performed on said target rows, and with said accumulating step including only one said pixel from each one of said successive non-transposed scan lines of pixels in said target rows, with said compressing starting with said first non-transposed scan line of pixels and working towards said last non-transposed scan line of pixels before said last non-transposed scan line of pixels has been generated by said scanning step (a);
and
(e) repeating said compressing step for the remaining non-transposed scan lines of pixels on said document by dropping off at least the oldest non-transposed scan line and picking up at least the newest non-transposed scan line in said predetermined number of non-transposed scan lines as said scanning proceeds across the same document using the document scanner.

3 more elements

A system for processing non-transposed data comprising:

a document scanner for scanning a document in a first direction to generate successive non-transposed scan lines of pixels corresponding to an image on the document, with said successive non-transposed scan lines of pixels including a first non-transposed scan line of pixels and a last non-transposed scan line of pixels to be processed, said successive non-transposed scan lines of pixels being derived from the same document;
means for dividing each non-transposed scan line of pixels into a plurality of processing channels so that each processing channel comprises a predetermined number of the pixels in each of said scan lines and each processing channel has boundaries which are aligned in a second direction which is perpendicular to said first direction;
means for accumulating a predetermined number of said non-transposed scan lines of pixels as successive non-transposed scan lines are generated prior to performing compression on said pixels, with said predetermined number of non-transposed scan lines having an oldest non-transposed scan line and a newest non-transposed scan line therein;
means for compressing the predetermined number of non-transposed scan lines of pixels in each of the processing channels simultaneously so as to perform parallel compression, with the compression in each processing channel being performed by using a reference row which is parallel to a target row being compressed, with the reference and target rows being perpendicular to said first direction and parallel to said boundaries of said processing channels;
and
said means for compressing being effective to compress the remaining non-transposed scan lines of pixels on said document by dropping off at least the oldest non-transposed scan line and picking up at least the newest non-transposed scan line of pixels in said predetermined number of non-transposed scan lines of pixels as said scanning proceeds across the document using said document scanner with each said target row including only one said pixel from each one of said successive non-transposed scan lines of pixels, and with the compression being initiated with said first non-transposed scan line of pixels while working towards said last non-transposed line of pixels but before said last non-transposed scan line of pixels has been generated by said document scanner.

3 more elements

A method of processing non-transposed image data on a document having first and second dimensions, with said document having lines of data thereon aligned substantially parallel to said first dimension, said method comprising the steps of:

(a) feeding said document in a direction parallel to said first dimension of said document;
(b) scanning said document using a document scanner in a scanning direction which is perpendicular to said first dimension of said document and perpendicular to said lines of data to generate successive non-transposed scan lines of pixels including a first non-transposed scan line of pixels and a last non-transposed scan line of pixels, said successive non-transposed scan lines of pixels being derived from the same document;
(c) arranging a minimum number of said non-transposed scan lines of pixels to present rows of said pixels perpendicular to said scanning direction to enable compression by a compression algorithm using a reference row which is parallel to said rows of said pixels and perpendicular to said scanning direction, with each one of said rows of said pixels including only one said pixel from each said successive non-transposed scan lines of pixels, with said compression algorithm generating Relative Address codes, hereinafter referred to as Re-Ad codes, and with said compression being initiated with said first non-transposed scan line of pixels while working towards said last non-transposed scan line of pixels but before said last non-transposed scan line of pixels has been generated by said scanning step (b);
(d) storing said Re-Ad codes in a memory for each of said rows of pixels as said scanning proceeds from said first non-transposed scan line of pixels towards said last non-transposed said scan line of pixels using the document scanner;
(e) dropping off an oldest one of said successive non-transposed scan lines of pixels and picking up a newest one of said successive non-transposed scan lines of pixels so as to maintain said minimum number of said non-transposed scan lines of pixels for generating said Re-Ad codes for said rows of said pixels as said scanning proceeds from said first one of said successive non-transposed scan lines of pixels for said document towards said last one of said successive non-transposed scan lines of pixels thereon;
(f) repeating said steps (d) and (e) until said last non-transposed scan line of pixels is encountered;
(g) withdrawing said Re-Ad codes from said memory starting with a first of said rows of said pixels;
(h) repeating said step (g) for the rows of said pixels remaining in said memory;
and
(i) concatenating said Re-Ad codes from steps (g) and (h) to present compressed data corresponding to said image data on said document.

7 more elements

A method of processing non-transposed image data on a document having first and second dimensions, with said first dimension being longer than said second dimension, and with said document having lines of data thereon aligned substantially parallel to said first dimension, said method comprising the steps of:

(a) scanning said document using a document scanner in a first direction which is perpendicular to said first dimension of said document and perpendicular to said lines of data to generate successive non-transposed scan lines of pixels including a first non-transposed scan line of pixels and a last non-transposed scan line of pixels, said successive non-transposed scan lines of pixels being derived from the same document;
(b) arranging a minimum number of said non-transposed scan lines of pixels to present rows of said pixels perpendicular to said first direction to enable compression by a compression algorithm using a reference row which is parallel to said rows of said pixels and perpendicular to said first direction, with said compression algorithm generating Relative Address codes, hereinafter referred to as Re-Ad codes, and with said arranging step (b) being effective for including only one pixel from each of said successive non-transposed scan lines of pixels in said rows of pixels, and with said compression being initiated after said first non-transposed scan line of pixels is generated but before said last non-transposed scan line of pixels is generated by said scanning step (a);
(c) storing said Re-Ad codes in a memory for each of said rows of said pixels as said scanning proceeds from a first one of said non-transposed scan lines of pixels to a last one of said non-transposed scan lines of pixels;
(d) dropping off an oldest one of said non-transposed scan lines of pixels and picking up a newest one of said non-transposed scan lines of pixels so as to maintain said minimum number of non-transposed scan lines of pixels for generating said Re-Ad codes for said rows of pixels as said scanning proceeds from said first one of said non-transposed scan lines of pixels on said document to said last one of said non-transposed scan lines of pixels thereon;
(e) repeating said steps (c) and (d) until said last one of said non-transposed scan lines of pixels is encountered;
(f) withdrawing said Re-Ad codes from said memory starting with the Re-Ad codes associated with a first one of said rows of pixels and concatenating said Re-Ad codes until a last one of said Re-Ad codes is withdrawn from said memory.

3 more elements

A method of processing non-transposed data comprising the steps of:

(a) scanning a document using a document scanner in a first direction to generate successive non-transposed scan lines of pixels corresponding to an image on the document and including a first non-transposed scan line of pixels and a last non-transposed scan line of pixels, said successive non-transposed scan lines of pixels being derived from the same document;
(b) dividing each non-transposed scan line of pixels into a plurality of processing channels so that each processing channel comprises a predetermined number of the pixels in each of said scan lines and each processing channel has boundaries including rows of pixels which are aligned in a second direction which is perpendicular to said first direction;
(c) accumulating a predetermined number of said non-transposed scan lines of pixels as successive non-transposed scan lines of pixels are generated prior to performing compression on said pixels, with said predetermined number of non-transposed scan lines having an oldest non-transposed scan line of pixels and a newest non-transposed scan line of pixels therein;
(d) compressing the predetermined number of non-transposed scan lines of pixels in each of the processing channels simultaneously so as to perform parallel compression, with the compression in each processing channel being performed by using a reference row which is parallel to a target row of pixels being compressed to generate compressed row data for each of the rows of pixels in a channel, with the reference and target rows being perpendicular to said first direction and parallel to said boundaries of said processing channels, with each said target row including only one pixel from each of said successive non-transposed scan lines of pixels, and with said compression being initiated after said first non-transposed scan line of pixels is generated but before said last non-transposed scan line of pixels has been generated by said scanning step;
(e) storing the compressed row data in successive rows in a memory for each of the rows of pixels within a channel;
(f) dropping the oldest non-transposed scan line and picking up said newest non-transposed scan line for each of the processing channels to maintain said predetermined number of said non-transposed scan lines of pixels for compressing as said successive non-transposed scan lines of pixels are generated;
(g) repeating said steps (d), (e), and (f) for the remaining non-transposed scan lines until a last non-transposed scan line of pixels is compressed;
(h) concatenating the compressed row data for each of the channels in parallel to obtain a stream concatenated codes for each of the channels;
and
(i) concatenating the stream of concatenated codes for a first of said channels to a last of said channels to arrive at a stream of concatenated codes corresponding to said successive non-transposed scan lines of pixels.

7 more elements

Dependencies are inferred from the claim text.