 |
|
|
|
|
|
 Title: |
US5020121:
Neighborhood block prediction bit compression
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Rosenberg, Charles J.; Hewlett, NY
|
| Assignee: |
Hewlett-Packard Company, Palo Alto, CA
other patents from HEWLETT-PACKARD COMPANY (250060) (approx. 10,220)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1991-05-28
/ 1990-08-16
|
| Application Number: |
US1990000568002
|
| IPC Code: |
Advanced:
G06Q 10/00;
G06T 3/40;
G06T 9/00;
G09G 5/24;
G09G 5/28;
H03M 7/30;
H04N 1/415;
H04N 1/417;
Core:
more...
IPC-7:
G06K 9/36;
|
| U.S. Class: |
Current:
382/238;
358/001.9;
382/243;
400/110;
Original:
382/056;
358/261.3;
382/013;
382/027;
400/110;
|
| Field of Search: |
382/056,54,10,13,14,25,27,9
358/426,261.2,261.3,432,433,133
341/051
364/523
340/748
400/111
|
| Priority Number: |
| 1990-08-16 |
US1990000568002 |
|
| Abstract: |
A method for compression of data used to describe an ideographic character, or a set of such characters such as Japanese, Chinese, Hebrew, Arabic or Tamil characters or a set of two-level images, on a computer screen. The computer screen is divided into an array of non-overlapping pixel sub-blocks, each J pixels wide by K pixels high, and a neighborhood of L adjacent pixels is defined for each target sub-block. The known pixel configuration (white versus black or off versus on) of the neighborhood of pixels is used to predict the rth most probable pixel configuration for each target sub-block, for r=1, 2, . . . , R-1 (R>=2), based on a statistical analysis of the sub-block pixel configurations for all characters in the set. Where a particular target sub-block pixel configuration cannot be predicted from the R-1 pixel configurations associated with the neighborhood pixel configuration, the exact pixel configuration is used. Use of the exact sub-block pixel configuration is not often required. This method allows an average percentage compression or bit savings for the bit map representation that ranges from about 30 percent to about 70 percent, for a well known set of 6802 Kanji characters.
|
| Primary / Asst. Examiners: |
Moore, David K.; Mancuso, Joseph
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Family: |
Show 3 known family members
|
First Claim:
Show all 22 claims |
I claim:
1. A method of compression of data used to describe a collection of ideographic symbols, each represented as a pixel pattern on a block of pixels, the method comprising the steps of:
- decomposing the block of pixels for each ideographic symbol into M×N mutually exclusive, rectangular sub-blocks of pixels, each of size J pixels ×K pixels, where M, N, J and K are positive integers, the sub-blocks being numbered consecutively s=1, 2, . . ., S beginning at a selected corner of the block and proceeding consecutively row-by-row or column-by-column from the selected corner, where each sub-block is also represented by a unique two-dimensional coordinate (m,n) (m=1, 2, . . ., M; n=1, 2, . . ., N);
- for a predetermined integer ml in the range 1<=m1<=M and a predetermined integer n1 in the range 1<=n1 <=N, determining the exact pixel patterns of each of the sub-blocks numbered (m,n) for which m=m1 or n=n1 or both m=m1 and n=n1;
- for each pixel sub-block with coordinates (m,n) with 1<=m<=m1-1 and 1<=n<=n1-1, determining the pixel values of the Contiguous Pixels in the sub-blocks with coordinates (m+1,n), (m+1,n+1) and (m,n+1) and determining the Statistical Profile of the collection of ideographic symbols and associated Contiguous Pixels for each of these sub-blocks;
- for each pixel sub-block with coordinates (m,n) with 1<=m<=m1-1 and n1+1<=n<=N, determining the pixel values of the Contiguous Pixels in the sub-blocks with coordinates (m+1,n), (m+1,n-1) and (m,n-1) and determining the Statistical Profile of the collection of ideographic symbols and associated Contiguous Pixels for each of these sub-blocks;
- for each pixel sub-block with coordinates (m,n) with m1+1<=m<=M and 1<=n<=n1-1, determining the pixel values of the Contiguous Pixels in the sub-blocks with coordinates (m-1,n), (m-1,n+1) and (m,n+1) and determining the Statistical Profile of the collection of ideographic symbols and associated Contiguous Pixels for each of these sub-blocks;
- for each pixel sub-block with coordinates (m,n) with m1+1<=m<=M and n1+1<=n<=N, determining the pixel values of the Contiguous Pixels in the sub-blocks with coordinates (m-1,n), (m-1,n-1) and (m,n-1) and determining the Statistical Profile of the collection of ideographic symbols and associated Contiguous Pixels for each of these sub-blocks;
- for each sub-block numbered s=1, 2, . . ., S for which a Statistical Profile exists, determining, from the Statistical Profile of Contiguous Pixels, the rth most probable pattern of pixels in that sub-block for each of r=1, 2, . . ., R-1, where R is a selected integer <=2, and assigning an index ars corresponding to the choice of the rth most probable pixel pattern for the sub-block numbered s;
- for each sub-block numbered s=1, 2, . . ., S, assigning the index ars, if the predicted pixel pattern corresponding to the index ars is the correct pattern, and assigning an index aRs that requires use of the exact pixel pattern for sub-block s, if none of the R-1 predicted pixel patterns corresponding to the indices ars (r=1, 2, . . ., R-1) is the correct pattern, or if the coordinates (m,n) of the sub-block satisfy m=m1 or n=n1 or both m=m1 and n=n1; and
- associating with each sub-block numbered s=1, 2, . . ., S the assigned index ars or aRs, as the case may be, as an ordered pair of numbers (s, ars) or (s,aRs).
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 39 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other References: |
C. A. Andrews et al., "Adaptive Data Compression", Proc. I.E.E.E., vol. 55(1967), pp. 267-277.
Wang et al., "Machine Recognition of Printed Chinese Characters Via Transformation Algorithms", Pattern Recognition, vol. 5 (1973), pp. 303-321.
(19 pages)
Siromoney et al., "Computer Recognition of Printed Tamil Characters", Pattern Recognition, vol. 10 (1979), pp. 243-247.
M. Nagao, "Data Compression of Chinese Character Patterns", Proc. I.E.E.E., vol. 68 (1980), pp. 818-829.
(12 pages)
Cited by 3 patents
Yamamoto et al., "Recognition of Handprinted Characters by an Outermost Point Method", Pattern Recognition, vol. 12 (1980), pp. 229-236.
(8 pages)
Cited by 5 patents
Chinnuswamy et al., "Recognition of Handprinted Tamil Characters", Pattern Recognition, vol. 12 (1980), pp. 141-152.
(12 pages)
Yhap et al., "An On-Line Chinese Character Recognition System", I.B.M. Jour. Res. Develop., vol. 25 (1981), pp. 187-195.
Spivey, "Data Compression Technique for APA Printer (Change Block Skipping)", , I.B.M. Tech. Disclos. Bull., vol. 23 (1981), pp. 5464-5467.
Fitch and Spivey, "Font Data Reduction by Scan Compression for Ink Jet Printers", I.B.M. Tech. Disclos. Bull., vol. 23 (1981), pp. 5471-5472.
Parhami et al., "Automatic Recognition of Printed Farsi Texts", Pattern Recognition, vol. 14 (1982), pp. 395-402.
M. Kushnir et al., "An Application of the Hough Transform to the Recognition of Printed Hebrew Characters", Pattern Recognition, vol. 16 (1983), pp. 183-191.
(9 pages)
Sugita et al., "Multi-font Kanji Generator", Trans. I.E.C.E., vol. E66 (1983), pp. 377-382.
Ni et al., "Single Pass Method for Labelling Black/White Image Objects", I.B.M. Tech. Disclos. Bull., vol. 26 (1984), pp. 5481-5482.
M. Kushnir et al., "Recognition of Handprinted Hebrew Characters Using Features Selected in the Hough Transform Space", Pattern Recognition, vol. 18 (1985), pp. 103-114.
(12 pages)
Anonymous, "Compression/Decompression of Font Patterns", I.B.M. Tech. Disclos. Bull., vol. 28 (1986), pp. 3563-3564.
El-Sheikh et al., "Computer Recognition of Arabic Cursive Scripts", Pattern Recognition, vol. 21 (1988), pp. 293-302.
(10 pages)
Cited by 3 patents
Maeder, "Local Block Pattern Methods for Binary Image Encoding", Proc. 1988 Ausgraph Conference.
F. H. Cheng et al., "Recognition of Handwritten Chinese Characters by Modified Hough Transform Techniques", I.E.E.E. Trans. on Pattern Analysis and Machine Intelligence, vol. 11 (1989), pp. 429-439.
(11 pages)
|
|
 Nominate this for the Gallery...
|
|
