Apparatus and method for 2-dimensional data compression

A method for compressing an original image to obtain a compressed image, the original image having a pixel array, the pixel array having target pixels and prior pixels, each prior pixel being located in a position within the pixel array prior to each target pixel, the method comprising the steps of:

• (a) repeatedly traversing the pixel array according to a predetermined non-linear traversing pattern to locate a longest matching prior pixel string, if any, matching a target pixel string;
• (b) generating a copy token referencing such longest matching prior pixel string as a compressed representation of such matching target pixel string;
• and
• (c) generating a literal token for each target pixel having no matching prior pixel.

A system for compressing an original image to obtain a compressed image, the original image having a pixel array, the pixel array having target pixels and prior pixels, each prior pixel being located in a position within the pixel array prior to each of the target pixels, the system comprising:

• (a) means for repeatedly traversing the pixel array according to a predetermined non-linear traversing pattern to locate a longest matching prior pixel string, if any, matching a target pixel string;
• (b) means for generating a copy token referencing such longest matching prior pixel string as a compressed representation of such matching target pixel string;
• and
• (c) means for generating a literal token for each target pixel having no matching prior pixel.

A computer program for compressing an original image to obtain a compressed image, the original image having a pixel array, the computer program being tangibly stored on a media readable by a computer system, the computer program being adapted for configuring the computer system upon being read and executed by the computer system to perform the functions of:

• (a) repeatedly traversing the pixel array according to a predetermined non-linear traversing pattern to locate a longest matching prior pixel string, if any, matching a target pixel string;
• (b) generating a copy token referencing such longest matching prior pixel string as a compressed representation of such matching target pixel string;
• and
• (c) generating a literal token for each target pixel having no matching prior pixel.

A method for compressing image data, the image data comprising an array of pixels, the array of pixels having an initial target pixel and prior pixels, each prior pixel being located before the initial target pixel within the array of pixels, the method comprising the steps of:

• (a) traversing the image data according to a reverse non-linear traversing pattern in a reverse direction within the array of pixels;
• (b) locating an initial matching prior pixel, if any, that matches the initial target pixel;
• (c) if an initial matching prior pixel is located, traversing, according to a linear traversing pattern in a forward direction within the array of pixels, both the pixels succeeding the initial target pixel and the pixels succeeding the initial matching prior pixel until a target pixel succeeding the initial target pixel does not match a prior pixel succeeding the initial matching prior pixel, thereby defining a matching data string;
• (d) continuing traversing the image data in the non-linear traversing pattern and attempting to locate another prior pixel that matches the initial target pixel;
• (e) if another matching prior pixel is located, defining another matching data string in accordance with step (c);
• (f) repeating steps (d) and (e) to define all matching data strings;
• (g) determining which of the matching data strings is a longest matching data string;
• (h) encoding the longest matching data string as a copy token.

A method for compressing image data, the image data comprising an array of pixels, including target pixels and prior pixels, each prior pixel being located in a position within the array of pixels prior to the target pixels, the method comprising the steps of:

• (a) traversing the prior pixels according to a predetermined non-linear traversing pattern having a beginning and an end, the beginning occurring at a first prior pixel having a predetermined location with respect to an initial target pixel, the end occurring at a final prior pixel having another predetermined location with respect to the initial target pixel;
• (b) locating an initial matching prior pixel, if any, from among the prior pixels being traversed according to the non-linear predetermined traversing pattern, the initial matching prior pixel matching the initial target pixel;
• (c) if an initial matching prior pixel is located, traversing, according to a linear traverse path, both the target pixels succeeding the initial target pixel and the prior pixels succeeding the initial matching prior pixel, each succeeding target pixel having a corresponding succeeding prior pixel along the linear traverse path;
• (d) comparing each succeeding target pixel to the corresponding succeeding prior pixel and continuing traversing in the linear traverse path until a succeeding target pixel is located that does not match the corresponding succeeding prior pixel, thereby locating a non-matching prior pixel;
• (e) defining a matching data string as a string of pixels beginning with the initial matching prior pixel and ending with the prior pixel immediately preceding the non-matching prior pixel in the array of pixels;
• (f) continuing traversing the prior pixels in the non-linear traversing pattern, beginning with a prior pixel preceding the initial matching prior pixel within the non-linear traversing pattern, and attempting to locate another prior pixel that matches the initial target pixel;
• (g) if another matching prior pixel is located, repeating steps (c) through (e) to define another matching data string;
• (h) repeating steps (f) and (g) until reaching the final prior pixel;
• (i) if only one matching data string is defined, characterizing the one matching data string as a longest matching data string;
• (j) if a plurality of matching data strings are defined, determining which of the plurality of matching data strings is the longest matching data string;
• and
• (k) encoding the longest matching data string as a copy token.

A method for compressing a stream of image data in a data compression system into a stream of encoded image data and for decompressing the stream of encoded image data into a decompressed image, the stream of image data comprising an array of pixels, the data compression system including a pixel pointer for indicating a target pixel being scanned, the method comprising the steps of:

• (a) scanning at least one of the pixels in array of pixels to obtain prior scanned pixels, each prior scanned pixel having a location within the array of pixels;
• (b) searching the prior scanned pixels for a matching data string that matches a string of pixels being scanned, including:
• (1) scanning an initial target pixel, the initial target pixel having a position in the array of pixels;
• (2) traversing the prior scanned pixels according to a predetermined non-linear traversing pattern;
• (3) determining whether any of the prior scanned pixels being traversed matches the initial target pixel being scanned, thereby locating an initial matching prior scanned pixel;
• (4) advancing the pixel pointer to a next target pixel to be scanned, the next target pixel being located at a position within the array of pixels immediately following the position of the initial target pixel;
• (5) determining whether the next target pixel matches a succeeding prior scanned pixel, the succeeding prior scanned pixel having a position in the array of pixels immediately following the initial matching prior scanned pixel;
• (6) advancing the pixel pointer and repeating step b(5) and thereby locating all succeeding prior scanned pixels that match the pixel indicated by the pixel pointer, until a matching prior scanned pixel is not found, thereby defining the matching data string;
• (c) determining an offset representing a location, relative to the initial target pixel in the array of pixels, of the initial matching prior scanned pixel;
• (d) determining a string length of the matching data string, the string length being the number of matching prior scanned pixels in the matching data string;
• (e) converting the matching data string to a copy token, the copy token comprising the offset of the initial matching scanned pixel and the string length of the matching data string;
• and
• (f) encoding the copy token.

A method for compressing a stream of image data in a data compression system and for decompressing the stream of image data into a decompressed image, the stream of image data comprising an array of pixels, the array of pixels being capable of being subdivided into strings incorporating at least one of the pixels from the array of pixels, the method comprising the steps of:

• (a) scanning the array of pixels according to a predetermined non-linear traversing pattern to obtain prior scanned pixels;
• (b) comparing pixels being scanned to the prior scanned pixels to determine whether any pixels being scanned match any of the prior scanned pixels;
• (c) generating a matching data string for each string, if any, of at least one pixel being scanned that has a corresponding string of at least one prior scanned pixel that matches the pixel being scanned, each matching data string including image data corresponding to the matching prior scanned pixel;
• (d) if any matching data strings are generated, converting each such matching data string into a copy token;
• (e) if a pixel being scanned has no matching prior scanned pixel, converting the pixel being scanned into a literal token;
• (f) encoding the copy tokens, if any, and the literal tokens to obtain an encoded token set;
• (g) transmitting the encoded token set;
• (h) decoding the encoded token set to obtain a decoded token set;
• and
• (i) expanding the decoded token set to obtain the decompressed image.

A data compression system for compressing a stream of image data into a stream of encoded image data and for decompressing the stream of encoded image data into a decompressed image, the stream of image data comprising an array of pixels, the data compression system including a pixel pointer for indicating a target pixel being scanned, the system comprising:

• (a) a scanner for scanning at least one of the pixels in the array of pixels to obtain prior scanned pixels, each prior scanned pixel having a location within the array of pixels;
• (b) means for searching the prior scanned pixels for a matching data string that matches a string of pixels being scanned, including:
• (1) means for scanning an initial target pixel, the initial target pixel having a position in the array of pixels;
• (2) means for traversing the prior scanned pixels using a predetermined non-linear traversing pattern;
• (3) first comparing means for determining whether any of the prior scanned pixels matches the initial target pixel being scanned, thereby locating an initial matching prior scanned pixel;
• (4) means for advancing the pixel pointer to a next target pixel to be scanned, the next target pixel being located at a position within the array of pixels immediately following the position of the initial target pixel;
• (5) second comparing means for determining whether the next target pixel matches a succeeding prior scanned pixel, the succeeding prior scanned pixel having a position in the array of pixels immediately following the initial matching prior scanned pixel;
• (6) means for advancing the pixel pointer and repeating step b(5) and for thereby locating all succeeding prior scanned pixels that match the pixel indicated by the pixel pointer, until a matching prior scanned pixel is not found, thereby defining the matching data string;
• (c) means for determining an offset representing a location, relative to the initial target pixel in the array of pixels, of the initial matching prior scanned pixel;
• (d) means for determining a string length of the matching data string, the string length being the number of matching prior scanned pixels in the matching data string;
• (e) a converter for converting the matching data string to a copy token, the copy token comprising the offset of the initial matching prior scanned pixel and the string length of the matching data string;
• and
• (f) an encoder for encoding the copy token.

A system for compressing a stream of image data and for decompressing the stream of image data into a decompressed image, the stream of image data comprising an array of pixels, the array of pixels being capable of being subdivided into strings incorporating at least one of the pixels from the array of pixels, the system comprising:

• (a) a scanner for scanning the array of pixels in a predetermined non-linear traversing pattern to obtain prior scanned pixels;
• (b) a comparator for comparing pixels being scanned to the prior scanned pixels to determine whether any pixels being scanned match any of the prior scanned pixels;
• (c) means for generating a matching data string, if any, for each string of at least one pixel being scanned that has a corresponding string of at least one prior scanned pixel that matches the pixel being scanned, each matching data string including image data corresponding to the matching prior scanned pixel;
• (d) if any matching data strings are generated, a converter for converting each such matching data string into a copy token;
• (e) if a pixel being scanned has no matching prior scanned pixel, a converter for converting the pixel being scanned into a literal token;
• (f) an encoder for encoding the copy tokens, if any, and the literal tokens to obtain an encoded token set;
• (g) a transmitter for transmitting the encoded token set;
• (h) a decoder for decoding the encoded token set to obtain a decoded token set;
• and
• (i) means for expanding the decoded token set to obtain the decompressed image.

A computer program for compressing a stream of image data into a stream of encoded image data and for decompressing the stream of encoded image data into a decompressed image, the stream of image data comprising an array of pixels, the computer program being tangibly stored on a media readable by a computer system, the computer system including a pixel pointer for indicating a target pixel being scanned, the computer program being adapted for configuring the computer system upon being read and executed by the computer system to perform the functions of:

• (a) scanning at least one of the pixels in the array of pixels to obtain prior scanned pixels, each prior scanned pixel having a location within the array of pixels;
• (b) searching the prior scanned pixels for a matching data string that matches a string of pixels being scanned, including:
• (1) scanning an initial target pixel, the initial target pixel having a position in the array of pixels;
• (2) traversing the prior scanned pixels according to a predetermined non-linear traversing pattern;
• (3) determining whether any of the prior scanned pixels being traversed matches the initial target pixel being scanned, thereby locating an initial matching prior scanned pixel;
• (4) advancing the pixel pointer to a next target pixel to be scanned, the next target pixel being located at a position within the array of pixels immediately following the position of the initial target pixel;
• (5) determining whether the next target pixel matches a succeeding prior scanned pixel, the succeeding prior scanned pixel having a position in the array of pixels immediately following the initial matching prior scanned pixel;
• (6) advancing the pixel pointer and repeating function b(5) and thereby locating all succeeding prior scanned pixels that match the pixel indicated by the pixel pointer, until a matching prior scanned pixel is not found, thereby defining the matching data string;
• (c) determining an offset representing a location, relative to the initial target pixel in the array of pixels, of the initial matching prior scanned pixel;
• (d) determining a string length of the matching data string, the string length being the number of matching prior scanned pixels in the matching data string;
• (e) convening the matching data string to a copy token, the copy token comprising the offset of the initial matching scanned pixel and the string length of the matching data string;
• and
• (f) encoding the copy token.

A computer program for compressing a stream of image data and for decompressing the stream of image data into a decompressed image, the stream of image data comprising an array of pixels, the array of pixels being capable of being subdivided into strings incorporating at least one of the pixels from the array of pixels, the computer program being tangibly stored on a media readable by a computer system, the computer program being adapted for configuring the computer system upon being read and executed by the computer system to perform the functions of:

• (a) scanning the array of pixels according to a predetermined non-linear traversing pattern to obtain prior scanned pixels;
• (b) comparing pixels being scanned to the prior scanned pixels to determine whether any pixels being scanned match any of the prior scanned pixels;
• (c) generating a matching data string for each string of at least one pixel being scanned that has a corresponding string of at least one prior scanned pixel that matches the pixel being scanned, each matching data string including image data corresponding to the matching prior scanned pixel;
• (d) if any matching data strings are generated, converting each such matching data string into a copy token;
• (e) if a pixel being scanned has no matching prior scanned pixel, converting the pixel being scanned into a literal token;
• (f) encoding the copy tokens, if any, and the literal tokens to obtain an encoded token set;
• (g) transmitting the encoded token set;
• (h) decoding the encoded token set to obtain a decoded token set;
• and
• (i) expanding the decoded token set to obtain the decompressed image.

A method for compressing an incoming data stream, the incoming data stream comprising a plurality of incoming data segments, a group of two or more of the plurality of incoming data segments comprising an incoming data string, the method comprising the steps of:

• (a) reading the incoming data stream to obtain prior data, the prior data including a plurality of prior data segments, a group of two or more of the plurality of prior data segments comprising a prior data string;
• (b) searching the prior data in a predetermined non-linear traversing pattern for longest matching prior data strings, each longest matching prior data string comprising a prior data string and matching an incoming data string from the incoming data stream;
• (c) if any longest matching prior data strings are found in the prior data, compressing the longest matching prior data strings to obtain compressed strings and encoding the compressed strings as copy tokens;
• (d) for any incoming data segment having no matching prior data segment, encoding such incoming data segment as a literal token;
• and
• (e) outputting the copy tokens, if any, and the literal tokens.

A system for compressing an incoming data stream, the incoming data stream comprising a plurality of incoming data segments, a group of two or more of the plurality of incoming data segments comprising an incoming data string, the system comprising:

• (a) means for reading the incoming data stream to obtain prior data, the prior data including a plurality of prior data segments, a group of two or more of the plurality of prior data segments comprising a prior data string;
• (b) means for searching the prior data in a predetermined non-linear traversing pattern for longest matching prior data strings, each longest matching prior data string comprising a prior data string and matching an incoming data string from the incoming data stream;
• (c) if any longest matching prior data strings are found in the prior data, a compressor for compressing the longest matching prior data strings to obtain compressed strings and an encoder for encoding the compressed strings as copy tokens;
• (d) for any incoming data segment having no matching prior data segment, an encoder for encoding such incoming data segment as a literal token;
• and
• (e) a port for outputting the copy tokens, if any, and the literal tokens.

A method for compressing data, the data including a plurality of data segments having an order, the plurality of data segments including target segments and prior segments, the prior segments preceding the target segments within the order of the plurality of data segments, the method comprising the steps of:

• (a) selecting an initial target segment;
• (b) traversing the prior segments according to a predetermined non-linear traversing pattern;
• and
• (c) locating a longest matching string of prior segments that matches a string of target segments, the string of target segments commencing at the initial target segment, the string of prior segments having an initial matching prior segment lying within the predetermined non-linear traversing pattern.

A system for compressing data, the data including a plurality of segments having an order, the plurality of segments including target segments and prior segments, the prior segments preceding the target segments within the order of the plurality of segments, the system comprising:

• (a) means for selecting an initial target segment;
• (b) means for traversing the prior segments according to a predetermined non-linear traversing pattern;
• and
• (c) means for locating a longest matching string of prior segments that matches a string of target segments, the string of target segments commencing at the initial target segment, the string of prior segments having an initial matching prior segment lying within the predetermined non-linear traversing pattern.

A computer program for compressing data, the data including a plurality of segments having an order, the plurality of segments including target segments and prior segments, the prior segments preceding the target segments within the order of the plurality of segments, the computer program being tangibly stored on a media readable by a computer system, the computer program being adapted for configuring the computer system upon being read and executed by the computer system to perform the functions of:

• (a) selecting an initial target segment;
• (b) traversing the prior segments according to a predetermined non-linear traversing pattern;
• and
• (c) locating a longest matching string of prior segments that matches a string of target segments, the string of target segments commencing at the initial target segment, the string of prior segments having an initial matching prior segment lying within the predetermined non-linear traversing pattern.