Apparatus and method for compression of facsimile information by pattern matching

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.

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.

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.

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.

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.

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.

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.

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.