Non-linear aggregation mapping compression of image data and method

• US 5,809,172 A
• Filed: 04/17/1996
• Issued: 09/15/1998
• Est. Priority Date: 04/17/1996
• Status: Expired due to Term

• Current Assignee: Canon Ayutthaya Limited (Canon Inc.)
• Original Assignee: Canon Ayutthaya Limited (Canon Inc.)
• Inventors: Melen, Roger D.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): TADAYON, BIJAN
• Application Number:
  US08/634,059
• Time in Patent Office: 881 Days
• Field of Search: 382/166, 382/168, 382/172, 382/173, 382/181, 382/190, 382/209, 382/232, 382/224, 382/233, 382/234, 382/235, 382/236, 382/237, 382/238, 382/239, 382/240, 382/244, 382/248, 382/251, 382/252, 382/253, 382/254, 382/270, 382/272, 382/273, 382/274, 382/275, 382/309, 382/284, 382/293, 382/276, 382/277, 382/278, 382/302, 382/307, 382/308, 434/43, 434/38, 395/126, 395/127, 395/135, 395/501, 395/131, 345/200, 345/136, 340/980
• US Class Current: 382/232
• CPC Class Codes: H04N 1/41 Bandwidth or redundancy reduction by scanning H04N1/17 ; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00

Abstract

General apparatus 10 for carrying out non-linear aggregation compression and storage of pixel data is presented. Scanner device 10S receives record documents 10R containing record images 10D for providing analog data 10A. Analog-to-digital converter 12A digitizes the amplitudes of the analog data to provide digital data stream 12D. Mapping device 14 defines a non-linear series of aggregation segments (A, B, C . . . X, Y, and Z) along the scale of intensity which are aggregated to an aggregation level (a, b, c, . . . x, y, or z) within each segment. The basic steps of the general method are: Retrieving pixel image data from a data source to form data stream 12D; Defining a non-linear series of aggregation segments; Determining an aggregation level within each aggregation segment; Aggregating the intensity scale levels within each aggregation segment; Compressing the aggregated pixel data; and Storing the non-linearly aggregated pixel data in a memory device.

Claims

1. A method of non-linearly aggregating pixel data into aggregation segments and storing the pixel data comprising the steps of:

retrieving pixel data from a data source, the pixel data having levels of intensity scale defining information contained within the pixel data, the intensity scale levels extending along a scale of intensity from a minimum intensity end to a maximum intensity end with center intensity scale levels therebetween;

defining a non-linear series of short and extended aggregation segments along the scale of intensity of the retrieved pixel data, the short segments in the series having the same length formed by S levels of intensity scale, and the extended segments in the series having varying lengths formed by more than S levels of intensity scale;

determining an aggregation level within each aggregation segment of the segmented scale of intensity, each aggregation level corresponding to an intensity scale level within the aggregation segment;

aggregating the intensity scale levels within each aggregation segment of the segmented scale of intensity, by setting all of the intensity scale levels therein to the aggregation level for that segment, which introduces partial loss of intensity scale information in the aggregation segments, the amount of intensity scale information lost from each aggregation segment is greater for the extended segments; and

storing the non-linearly aggregated pixel data in data storage means.

2. The method of claim 1, wherein the short segments have high intensity scale information content and the extended segments have low intensity scale information content.

3. The method of claim 2, wherein the segmented scale of intensity has a region of adjacent short segments.

4. The method of claim 3, wherein the extended segments near the minimum intensity end and near the maximum intensity end are the longest of the aggregation segments and the extended segments become shorter toward the region of adjacent short segments.

5. The method of claim 2, wherein the number of intensity scale levels included in the extended segments progressively changes along the scale of intensity.

6. The method of claim 5, wherein the extended segments include progressively fewer intensity scale levels along the scale of intensity from the minimum intensity end toward the maximum intensity end.

7. The method of claim 5, wherein the extended segments include progressively more intensity scale levels along the scale of intensity from the minimum intensity end toward the maximum intensity end.

8. The method of claim 5, wherein the extended segments include progressively fewer intensity scale levels along the scale of intensity from the minimum intensity end toward the center intensity scale levels, and include progressively fewer intensity scale levels along the scale of intensity from the maximum intensity end toward the center intensity scale levels.

9. The method of claim 1, wherein the number of intensity scale levels S in each short aggregation segment is 2, and the number of intensity scale levels in each extended aggregation segment is greater than 2.

10. The method of claim 1, wherein the number of intensity scale levels S in each short aggregation segment is 1 forming a single level segment preserving all intensity scale information in the single level segments, and the number of intensity scale levels in each extended aggregation segment is greater than 1 forming a multiple level segment.

11. The method of claim 10, wherein the retrieved pixel data contains stroke based symbols formed by stroke foreground pixels having intensities near one end of the scale of intensity, and non-stroke background pixels having intensities near the other end of the scale of intensity, and transition ground pixels having intensities near the center of the scale of intensity, the transition ground pixels forming a transition interface between the stroke foreground and the non-stroke background.

12. The method of claim 11, wherein the stroke foreground pixels are aggregated into multiple level segments with partial loss of intensity scale information, and non-stroke background pixels are aggregated into multiple level segments with partial loss of intensity scale information, and transition ground pixels are single level segments of preserved intensity scale information.

13. The method of claim 11, wherein during the retrieving step the pixel data containing the stroke based symbols is retrieved from a data memory means.

14. The method of claim 11, wherein the step of retrieving the pixel data containing the stroke based symbols includes the following steps:

scanning a data source document to obtain analog pixel data of the stroke based symbols; and

converting the analog pixel data into digital pixel data.

15. The method of claim 14, wherein the step of defining a series of aggregation segments is accomplished by an intensity scale mapping device which receives the digital pixel data and maps each intensity scale level therein to a segment of the series of aggregation segment.

16. The method of claim 15, wherein the step of determining an aggregation level within each aggregation segment is accomplished by the intensity scale mapping device which assigns an intensity scale level within each aggregation segment as the aggregation level therefor.

17. The method of claim 16, wherein the step of aggregating the intensity scale levels within each aggregation segment is accomplished by the intensity scale mapping device which maps all of the intensity scale levels within each aggregation segment to the aggregation level therefor.

18. The method of claim 14, wherein the data source document has a light background intensity and the strokes thereon have a dark foreground intensity.

19. The method of claim 18, wherein the light background intensity has a background color hue and the dark foreground intensity has a foreground color hue.

20. The method of claim 18, wherein the light background intensity is white and the dark foreground intensity is black.

21. The method of claim 11, wherein the step of defining a non-linear series of aggregation segments comprises:

identifying a dominant background intensity scale level near the background end of the scale of intensity having the most background pixels;

determining a fundamental background aggregation segment having B intensity scale levels which includes the dominant background level;

defining a non-linear series of background aggregation segments each having a progressively decreasing number of intensity scale levels, beginning with the fundamental background segment of B intensity scale levels and continuing with smaller segments to a lower limit of one intensity scale level.

22. The method of claim 21, wherein the step of identifying the dominant background level further comprises the steps of:

providing histogram data which reveals the number pixels in each intensity scale levels in the background end of the scale of intensity, and

selecting the background intensity scale level having the most pixels.

23. The method of claim 21, wherein the fundamental background segment extends from the background end of the scale of intensity toward the center intensity scale levels, and includes the dominant background level plus a pre# of adjacent intensity scale levels on the center side of the dominant background level.

24. The method of claim 21, wherein the aggregation level of the fundamental background segment is the dominant background level.

25. The method of claim 21, wherein the aggregation level of the fundamental background segment is the dominant background level, and the aggregation level of the remaining segments is proximate the center intensity scale level is each segment.

26. The method of claim 11, wherein the step of defining a non-linear series of aggregation segments comprises:

identifying a dominant foreground intensity scale level near the foreground end of the scale of intensity having the most foreground pixels;

determining a fundamental foreground aggregation segment having F intensity scale levels which includes the dominant foreground level;

defining a non-linear series of foreground aggregation segments each having a progressively decreasing number of intensity scale levels, beginning with the fundamental foreground segment of F intensity scale levels and continuing with smaller segments to a lower limit of one intensity scale level.

27. The method of claim 26, wherein the step of identifying the dominant foreground level further comprises the steps of:

providing histogram data which reveals the number pixels in each intensity scale levels in the foreground end of the scale of intensity, and

selecting the foreground intensity scale level having the most pixels.

28. The method of claim 26, wherein the fundamental foreground segment extends from the foreground end of the scale of intensity toward the center intensity scale levels, and includes the dominant foreground level plus a pre# of adjacent intensity scale levels on the center side of the dominant foreground level.

29. The method of claim 26, wherein the aggregation level of the fundamental foreground segment is the dominant foreground level.

30. The method of claim 26, wherein the aggregation level of the fundamental foreground segment is the dominant foreground level, and the aggregation level of the remaining segments is proximate the center intensity scale level is each segment.

31. The method of claim 1, wherein the aggregation level within each multiple level segment along the scale of intensity is the minimum intensity scale level within that segment.

32. The method of claim 1, wherein the aggregation level within each multiple level segment along the scale of intensity is the maximum intensity scale level within that segment.

33. The method of claim 1, wherein the aggregation level within each multiple level segment along the scale of intensity is the minimum intensity scale level within the segment at the minimum end of the scale of intensity, and is the maximum intensity scale level within the segment at the maximum end of the scale of intensity, and progressively increases towards the maximum intensity scale level along the scale of intensity toward the maximum end.

34. The method of claim 1, after the aggregating step and before the storing step, comprising the additional step of:

compressing the aggregated pixel data to reduce the storage requirements thereof.

35. The method of claim 34, wherein the step of compressing is run-length encoding.

36. Apparatus for non-linearly aggregating pixel data into aggregation segments and the storing pixel data, comprising:

data source means providing the pixel data having levels of intensity scale which define the information contained within the pixel data, the intensity scale levels extending along a scale of intensity from a minimum intensity end to a maximum intensity end with center intensity scale levels therebetween;

retrieval means for retrieving the pixel data from the data source means;

definition means responsive to the pixel data retrieved by the retrieval means, for defining a non-linear series of short and extended aggregation segments along the scale of intensity, the short segments in the series having the same length formed by S levels of intensity scale, and the extended segments in the series having varying lengths formed by more than S levels of intensity scale;

determination means responsive to the series of aggregation segments from the definition means, for determining an aggregation level within each aggregation segment, each aggregation level corresponding to an intensity scale level within the aggregation segment;

aggregation means responsive to the aggregation segments and the aggregation levels therein, for aggregating the intensity scale levels within each aggregation segment by setting all of the intensity scale levels to the aggregation level for that segment, which introduces partial loss of intensity scale information in the aggregation segments, the amount of intensity scale information lost from each aggregation segment is greater for the extended segments; and

data storage means for storing the non-linearly aggregated pixel data in data storage means.

37. The apparatus of claim 36, wherein the segmented scale of intensity has a center region of adjacent short aggregation segments having high intensity scale information content, and regions of extended aggregation segments having low intensity scale information content near the minimum intensity end and near the maximum intensity end, which extended regions become shorter toward the region of adjacent short aggregation segments.

38. The apparatus of claim 37, wherein the number of intensity scale levels S in each short aggregation segment is 1 forming a single level segment in which all intensity scale information is preserved, and the number of intensity scale levels in each extended aggregation segment is greater than 1 forming a multiple level segment.

39. The apparatus of claim 36, wherein the retrieved pixel data contains stroke based symbols formed by stroke foreground pixels having intensities near one end of the scale of intensity which are aggregated into multiple level segments with partial loss of intensity scale information, and non-stroke background pixels having intensities near the other end of the scale of intensity which are aggregated into multiple level segments with partial loss of intensity scale information, and transition ground pixels having intensities near the center of the scale of intensity which are single level segments of preserved intensity scale information, the transition ground pixels forming a transition interface between the stroke foreground and the non-stroke background.

40. The apparatus of claim 39 wherein the data source means is a data source document, and wherein the retrieval means further comprises:

scanning means for scanning a data source document to obtain analog pixel data of the stroke based symbols; and

converting means for converting the analog pixel data into digital pixel data.

41. The apparatus of claim 40, wherein the definition means for defining the series of aggregation segments is an intensity scale mapping device which receives the digital pixel data and maps each intensity scale level therein to a segment of the series of aggregation segments.

42. The apparatus of claim 41, wherein the determination means for determining an aggregation level within each aggregation segment is included in the intensity scale mapping device which assigns an intensity scale level within each aggregation segment as the aggregation level therefor.

43. The apparatus of claim 42, wherein the aggregation means for aggregating the intensity scale levels within each aggregation segment is included in the intensity scale mapping device which maps all of the intensity scale levels within each aggregation segment to the aggregation level therefor.

44. The apparatus of claim 39, wherein:

the non-linear series of aggregation segments has a dominant background intensity scale level near the background end of the scale of intensity having the most background pixels and a dominant foreground intensity scale level near the foreground end of the scale of intensity having the most foreground pixels;

the non-linear series of aggregation segments has a fundamental background aggregation segment having B intensity scale levels including the dominant background level as the aggregation level therein, and a fundamental foreground aggregation segment having F intensity scale levels including the dominant foreground level as the aggregation level therein;

the aggregation segments have a progressively decreasing number of intensity scale levels, beginning with the fundamental segments and continuing with smaller segments to a lower limit of one intensity scale level.

45. A method of processing a pixel image comprising the steps of:

retrieving an input pixel image having levels of intensity extending along a scale of intensity from a minimum intensity end to a maximum intensity end with center intensity scale levels therebetween;

generating an intensity histogram of the input pixel image having N intensity levels along the scale of intensity;

defining M segments of intensity levels in the input image based on the intensity histogram, including

a foreground segment formed by pixels near one end of the scale of intensity and

a background segment formed by pixels near the other end of the scale of intensity and

center segments therebetween,

in which is M<

N;

setting an aggregation level value within each of the M segments of intensity levels defining a non-linear series of M aggregation levels; and

converting the input image of N intensity levels to a converted image of M intensity levels.

46. The method of claim 45 comprising the additional step of data compression of the converted image.

47. The method of claim 46 wherein the data compression is lossless compression.