EP0060694A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Apparatus and method for compressing digital data
Assignee: NCR Canada Ltd
•
Filing: 1982-03-12
•
Granted: —
•
Expires: 2002-03-12
Abstract
Abstract in a method and apparatus for compressing digital data derived from an image, a prediction table, which is pregenerat- ed based on a number of sample images, generates a predicted pixel and source state for each pixel of the original image, as the original image is scanned. The predicted pixel is the expected value of the pixel when considering the values of a group of adjoining pixels, while the source state is indicative of the probability that the predicted pixel is in error. Prediction error pixels are then generated and grouped according to their respective source states to form a plurality of run length symbols with each symbol comprising a white portion and a black portion, which symbols are stored sequentially in order of formation in a memory device (25) according to their respective source states. The symbols are used to provide address data for a memory device (85) which generate variable length code words that are transmitted to a receiving station and decoded using the reverse of the aforementioned process to form a facsimile image.
Inventors
- 👤 Ambati Subramaniam
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-05 01:38
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/004; G06T9/005; H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42; H04; H04N; H04N1/00; H04N1/41; H04N1/411; H04N1/413; H04N1/417
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
370 words
Apparatus for processing digital data derived from an image, including: conversion means (10) adapted to convert said digital data into varying run lengths of first type data elements and second type data elements; first storage means (52, 54) adapted to store a specified number of said data elements in a pre-defined pattern at any particular time; prediction means (22) adapted to predict for each original data element received from said conversion means the type of said data element based upon the types of data elements stored within said first storage means; classifying means (23) adapted to classify each of said predicted data elements into one of a plurality of source states, and providing a signal representative of said source state, wherein each source state is indicative of the degree of probability that said predicted data element is in error; and comparison means (58) adapted to compare each of said predicted data elements from said prediction means to its corresponding original data element from said first conversion means to generate a plurality of prediction error data elements, each of said prediction error data elements maintaining the same relationship to a given source state signal as its corresponding predicted data element; characterized by symbol forming means (24) adapted to form a plurality of symbols, wherein each symbol includes a group of prediction error data elements having the same source state and arranged as a section of data representing a first type prediction error data element and a section of data representing a second type prediction error data element; control means adapted to control the generation of said symbols by said symbol forming means; second storage means (25), coupled b said formation means, adapted to store said symbols in the sequence in which they are generated by said symbol forming means (24); third storage means (85), coupled to said second storage means, adapted to store a plurality of code words which are representative of each of said symbols contained in said second storage means (25); and output means (86, 92, 94) adapted to transmit selected code words from said third storage means over a transmission medium, in response to receipt by said third storage means of symbols corresponding to said selected code words.
Claim 2
Dependent Claim
370 words
Apparatus for processing digital data derived from an image, including: conversion means (10) adapted to convert said digital data into varying run lengths of first type data elements and second type data elements; first storage means (52, 54) adapted to store a specified number of said data elements in a pre-defined pattern at any particular time; prediction means (22) adapted to predict for each original data element received from said conversion means the type of said data element based upon the types of data elements stored within said first storage means; classifying means (23) adapted to classify each of said predicted data elements into one of a plurality of source states, and providing a signal representative of said source state, wherein each source state is indicative of the degree of probability that said predicted data element is in error; and comparison means (58) adapted to compare each of said predicted data elements from said prediction means to its corresponding original data element from said first conversion means to generate a plurality of prediction error data elements, each of said prediction error data elements maintaining the same relationship to a given source state signal as its corresponding predicted data element; characterized by symbol forming means (24) adapted to form a plurality of symbols, wherein each symbol includes a group of prediction error data elements having the same source state and arranged as a section of data representing a first type prediction error data element and a section of data representing a second type prediction error data element; control means adapted to control the generation of said symbols by said symbol forming means; second storage means (25), coupled b said formation means, adapted to store said symbols in the sequence in which they are generated by said symbol forming means (24); third storage means (85), coupled to said second storage means, adapted to store a plurality of code words which are representative of each of said symbols contained in said second storage means (25); and output means (86, 92, 94) adapted to transmit selected code words from said third storage means over a transmission medium, in response to receipt by said third storage means of symbols corresponding to said selected code words.
Claim 3
Dependent Claim
24 words
Apparatus according to claim 1, characterized in that said plurality of source states comprises four source states S0, S1, S 2 and S 3.
Claim 4
Dependent Claim
121 words
Apparatus according to claim 2, characterized in that state S 0 contains those prediction error data elements for which the probability that the prediction is in error is less than or equal to 025; source state S 1 contains those prediction error data elements for which the probability that the prediction is .in error is greater than .025 but less than or equal to .050; source state S 2 contains those prediction error data elements for which the probability that the prediction is in error is greater than .050 but less than or equal to .075; and source state S 3 contains those prediction error data elements for which the probability that the prediction is in error is greater than .075.
Claim 5
Dependent Claim
22 words
Apparatus according to claim 1, characterized in that first type data elements are black and said second type data elements are white.
Claim 6
Dependent Claim
15 words
Apparatus according to claim 1, characterized in that sa code words include variable length words.
Claim 7
Dependent Claim
89 words
Apparatus according to claim 1, characterized in that prediction means (22) includes a read only memory device (56) containing a plurality of predicted data elements which were pre-generated based upon prior analysis of a plurality of images similar in nature to the image to be digitized and in that said classifying means includes said read only memory device (56), which further contains a plurality of source state elements which were pre-generated based upon prior analysis of a plurality of images similar in nature to the image to be digitized.
Claim 8
Dependent Claim
43 words
Apparatus according to claim 1, characterized by addressing means (72, 74, 76) adapted to provide addresses for said second storage means (25) whereby said symbols may be stored in said second storage means (25) according to the sequential occurrence of said source states.
Claim 9
Dependent Claim
72 words
Apparatus according to claim 7, characterized in that said addressing means includes an address storage device (72) adapted to store a first sequence of addresses for said second storage means (25), first address counter means (74) adapted to produce a second sequence of addresses for said second storage means (25) and second address counter means (76) adapted to supply the location of the next available address in said second storage means (25).
Claim 10
Dependent Claim
231 words
Apparatus according to claim 1, characterized by receiving means (28) adapted to receive said code words from said transmission medium; fourth storage means (104), coupled to said receiving means (28) adapted to store a plurality of symbols which are representative of each of said code words, wherein each of said symbols is related to one of said source states; fifth storage means (112), coupled to said fourth storage means (104) adapted to store each symbol as it is generated from said fourth storage means (104); further conversion means (114a-h) adapted to convert each of said symbols into a plurality of prediction error elements in one of said set of source states; sixth storage means (122, 124) adapted to store a specified number of data elements in a pre-defined pattern at any particular time; seventh storage means (118) adapted to store a plurality of predicted data elements and a plurality of source state elements which are outputted in response to an address corresponding to a specific arrangement of data elements within said sixth storage means (122, 124); further comparison means (120) adapted to compare each predicted data element outputted from said seventh storage means (118) to its corresponding prediction error data element outputted from said second conversion means, to produce a facsimile data element; and by image forming means (128, 130) adapted to convert said facsimile data elements into a digital image.
Claim 11
Independent Claim
288 words
A method for processing digital data from an image, including the steps of: converting said digital data into wrying run lengths of a first type data element and a second type data element; receiving a continuous stream of said digital data and storing said data in first storage means (52, 54), which stores a specific number of data elements in a pre-defined pattern at any particular time; generating a predicted data element and a corresponding source state element, which represents one of a set of source states for each original data element received from said image, where said predicted data element reflects the probable type of data element from the image with respect to a specific arrangement of other data elements within said storage means, and said source state element reflects the degree of probability that said corresponding predicted data element is in error; and comparing each predicted data element to its corresponding original data element from said image to generate a prediction error data element, where said prediction error data element is associated with the same source state as its corresponding predicted data element; characterized by the steps of counting said prediction error data elements and storing said elements according to type and source state in order to form a plurality of symbols in each of said source states, each symbol being arranged as a section of data representing a first type prediction error data element and a section of data representing a second type prediction error data element; inputting each of said symbols to a storage device (85) as an address thereof; outputting from said storage device (85) code words representative of each of said digital symbols; and transmitting said code words over a transmission medium.
Claim 12
Independent Claim
288 words
A method for processing digital data from an image, including the steps of: converting said digital data into wrying run lengths of a first type data element and a second type data element; receiving a continuous stream of said digital data and storing said data in first storage means (52, 54), which stores a specific number of data elements in a pre-defined pattern at any particular time; generating a predicted data element and a corresponding source state element, which represents one of a set of source states for each original data element received from said image, where said predicted data element reflects the probable type of data element from the image with respect to a specific arrangement of other data elements within said storage means, and said source state element reflects the degree of probability that said corresponding predicted data element is in error; and comparing each predicted data element to its corresponding original data element from said image to generate a prediction error data element, where said prediction error data element is associated with the same source state as its corresponding predicted data element; characterized by the steps of counting said prediction error data elements and storing said elements according to type and source state in order to form a plurality of symbols in each of said source states, each symbol being arranged as a section of data representing a first type prediction error data element and a section of data representing a second type prediction error data element; inputting each of said symbols to a storage device (85) as an address thereof; outputting from said storage device (85) code words representative of each of said digital symbols; and transmitting said code words over a transmission medium.
Claim 13
Dependent Claim
79 words
A method according to claim 10, characterized in that the step of generating a predicted data element and a corresponding source state element includes the steps of: addressing a second storage means (56) using the arrangement of data elements stored in said first storage means (52, 54) as the address; and outputting a predicted data element and its corresponding source state element from said second storage means (56) for each address generated by said first storage means (52, 54).
Claim 14
Dependent Claim
102 words
A method according to claim 10, characterized in that the step of counting said prediction error data elements and storing said elements according to type and source state in order to form a plurality of symbols in each of said source states includes the steps of: transmitting each prediction error data element to a plurality of counters (68a-h), with a separate counter used for each type and source state, until a symbol is formed in a source state; and transmitting each symbol to a third storage means (25), where said symbols are stored, according to source state, in the order of formation.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.