Apparatus and method for compression of facsimile information by pattern matching
First Claim
1. A method of encoding a facsimile image including a plurality of picture elements (pixels) which lie along a series of scan lines, comprising the steps of:
- (a) comparing incoming patterns contained in portions of said image with a sequence of previously processed patterns stored in a library to determine the existence of a match between said incoming and stored patterns,(b) encoding, for each incoming pattern which matches a stored pattern, its location in said image and an identification number associated with said stored pattern, said encoding step being performed irrespective of whether said each incoming pattern intersects a border between said adjacent portions of said image, and(c) storing patterns in said library for which no matching pattern is found,wherein said storing step includes(d) arranging said patterns so that frequently occurring patterns are processed in said comparing step before infrequently occurring patterns.
1 Assignment
0 Petitions
Accused Products
Abstract
A technique and apparatus for facsimile encoding wherein patterns isolated in each incoming image or picture are compared against stored library patterns, and an identification number associated with a matching pattern and its location in the facsimile are encoded in place of a pixel-by-pixel pattern description. The library of stored patterns used for matching purposes is organized such that frequently occurring patterns are examined early in the matching process, decreasing processing time. Identification numbers associated with matched patterns on each scanning line are numerically sorted, so that the ID'"'"'s can be differentially encoded. At any time during pattern matching, detection of significant differences between the incoming pattern and a particular library pattern generates a reject decision, immediately terminating that match attempt. If desired features of the incoming patterns can be compared to library pattern features, using tight and then loose screening criteria, in order to preselect patterns used in the matching process.
-
Citations
16 Claims
-
1. A method of encoding a facsimile image including a plurality of picture elements (pixels) which lie along a series of scan lines, comprising the steps of:
-
(a) comparing incoming patterns contained in portions of said image with a sequence of previously processed patterns stored in a library to determine the existence of a match between said incoming and stored patterns, (b) encoding, for each incoming pattern which matches a stored pattern, its location in said image and an identification number associated with said stored pattern, said encoding step being performed irrespective of whether said each incoming pattern intersects a border between said adjacent portions of said image, and (c) storing patterns in said library for which no matching pattern is found, wherein said storing step includes (d) arranging said patterns so that frequently occurring patterns are processed in said comparing step before infrequently occurring patterns. - View Dependent Claims (2)
-
-
3. A method of encoding a facsimile image including a plurality of picture elements (pixels) which lie along a series of scan lines comprising the steps of:
-
(a) comparing incoming patterns contained in portions of said image with a sequence of previously processed patterns stored in a library to determine the existence of a match between said incoming and stored patterns, (b) encoding, for each incoming pattern which matches a stored pattern, its location in said image and an identification number associated with said stored pattern, and (c) storing patterns in said library for which no matching pattern is found, wherein said storing step includes (d) arranging said patterns so that frequently occurring patterns are processed in said comparing step before infrequently occurring patterns, and wherein said encoding step includes the steps of; (e) sorting identification numbers of those of said stored patterns which match incoming patterns on one of said scan lines in numerical order, and (f) differentially encoding said sorted identification numbers.
-
-
4. A method of encoding a facsimile image including a plurality of picture elements (pixels) which lie along a series of scan lines comprising the steps of:
-
(a) comparing incoming patterns contained in portions of said image with a sequence of previously processed patterns stored in a library to determine the existence of a match between said incoming and stored patterns, (b) encoding, for each incoming pattern which matches a stored pattern, its location in said image and an identification number associated with said stored pattern, and (c) storing patterns in said library for which no matching pattern is found, wherein said storing step includes (d) arranging said patterns so that frequently occurring patterns are processed in said comparing step before infrequently occurring patterns, and wherein said comparing step includes the steps of; (e) comparing a sub-block of pixels in one of said incoming patterns with the corresponding sub-block of pixels in a selected stored pattern, (f) discontinuing said comparing step for said selected pattern and repeating said comparing step using another pattern in said sequence if said pixels in said sub-blocks differ by more than a predetermined amount, and (g) repeating said comparing step for remaining sub-blocks of pixels in said incoming pattern if said pixels in said sub-blocks do not differ by said predetermined amount.
-
-
5. A method of encoding a facsimile image including a plurality of picture elements (pixels) which lie along a series of scan lines comprising the steps of:
-
(a) comparing incoming patterns contained in portions of said image with a sequence of previously processed patterns stored in a library to determine the existence of a match between said incoming and stored patterns, (b) encoding, for each incoming pattern which matches a stored pattern, its location in said image and an identification number associated with said stored pattern, and (c) storing patterns in said library for which no matching pattern is found, wherein said storing step includes (d) arranging said patterns so that frequently occurring patterns are processed in said comparing step before infrequently occurring patterns, wherein said method further includes the step of associating a low identification number with frequently occurring patterns.
-
-
6. Apparatus for encoding a facsimile signal representing the on/off status of elements (pixels) of a picture, said pixels lying along a plurality of scan lines, including:
-
pattern extraction means for extracting patterns from sequentially processed, contiguous regions of said picture, each of said patterns including a plurality of connected pixels, at least some of said patterns extending to a border between successively processed ones of said regions, means for storing a plurality of previously processed patterns each having an associated identification (ID) number, matching means jointly responsive to said extraction means and said storing means for comparing said extracted patterns with stored patterns, and coding means responsive to said matching means for encoding for each matching pattern (a) its location in said picture and (b) its associated identification number, and means for arranging said stored patterns such that frequently occurring patterns are matched before less frequently occurring patterns. - View Dependent Claims (7, 11)
-
-
8. Apparatus for encoding a facsimile signal representing the on/off status of elements (pixels) of a picture, said pixels lying along a plurality of scan lines, including:
-
pattern extraction means for extracting patterns from regions of said picture, each of said patterns including a plurality of connected pixels, means for storing a plurality of previously processed patterns each having an associated identification (ID) number, matching means jointly responsive to said extraction means and said storing means for comparing said extracted patterns with stored patterns, and coding means responsive to said matching means for encoding for each matching pattern (a) its location in said picture and (b) its associated identification number, and means for arranging said stored patterns such that frequently occurring patterns are matched before less frequently occurring patterns, wherein said feature comparing means includes; means for individually comparing said selected features of said incoming and stored patterns using a variable threshold. - View Dependent Claims (12)
-
-
9. Apparatus for encoding a facsimile signal representing the on off status of elements (pixels) of a picture, said pixels lying along a plurality of scan lines, including:
-
pattern extraction means for extracting patterns from regions of said picture, each of said patterns including a plurality of connected pixels, means for storing a plurality of previously processed patterns each having an associated identification (ID) number, matching means jointly responsive to said extraction means and said storing means for comparing said extracted patterns with stored patterns, and coding means responsive to said matching means for encoding for each matching pattern (a) its location in said picture and (b) its associated identification number, and means for arranging said stored patterns such that frequently occurring patterns are matched before less frequently occurring patterns, wherein said stored pattern arranging means includes (a) means for storing information describing the association between said identification number and said stored patterns, and (b) means for rearranging said stored association information at the end of each of said scan lines that contain a pattern, whereby frequently matched patterns are associated with lower identification numbers. - View Dependent Claims (10)
-
-
13. Apparatus for encoding a signal representing the intensity values of elements (pixels) of a picture which lie along a series of scan lines, including:
-
(a) means for isolating patterns within blocks of pixels, each of said blocks including a plurality of border pixels between successively processed blocks, each isolated pattern comprising connected pixels with similar intensity values, ones of said isolated patterns including at least some of said border pixels, (b) first storing means for storing previously processed patterns and associated identification numbers, (c) means for matching each isolated pattern with selected stored patterns by sequentially comparing a sub-block of pixels in said isolated pattern with spatially corresponding sub-blocks in said selected stored patterns, (d) means responsive to said matching means for encoding (1) the location of a matched pattern in said picture, and (2) a code word representing said identification number associated with said matched pattern, and (e) means for selecting ones of said stored patterns for matching as a function of the frequency with which said patterns occurred in previously processed blocks of pixels. - View Dependent Claims (15, 16)
-
-
14. Apparatus for encoding a signal representing the intensity values of elements (pixels) of a picture which lie along a series of scan lines, including:
-
(a) means for isolating patterns within blocks of pixels, each pattern comprising connected pixels with similar intensity values, (b) first storing means for storing previously processed patterns and associated identification numbers, (c) means for matching each isolated pattern with selected stored patterns by sequentially comparing a sub-block of pixels in said isolated pattern with spatially corresponding sub-blocks in said selected stored patterns, (d) means responsive to said matching means for encoding (1) the location of a matched pattern in said picture, and (2) a code word representing said identification number associated with said matched pattern, (e) means for selecting ones of said stored patterns for matching as a function of the frequency with which said patterns occurred in previously processed blocks of pixels, and (f) means for sorting identification numbers assigned to stored patterns which match patterns contained on one of said scan lines in said picture in numerical order, wherein said encoding means is arranged to differentially encode said sorted identification numbers.
-
Specification