Disregarding changes in data in a location of a data structure based upon changes in data in nearby locations

• US 5,757,970 A
• Filed: 12/10/1996
• Issued: 05/26/1998
• Est. Priority Date: 05/13/1992
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Callahan, Sean M., Leak, Bruce A.
• Primary Examiner(s): JOHNS, ANDREW W
• Application Number:
  US08/762,590
• Time in Patent Office: 532 Days
• Field of Search: 382/260, 382/261, 382/265, 382/275, 382/236, 382/302, 348/154, 348/155, 348/400, 348/401, 348/402, 348/412, 348/413
• US Class Current: 382/236
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: G06T 9/004 Predictors, e.g. intraframe, interframe coding
• CPC Class Codes: H04N 19/507 using conditional replenishment

Abstract

A method for filtering data to be compressed by frame differencing is disclosed. In applications where large amounts of data must be either stored or transmitted, such as, for example, digital image data, various techniques are used to compress the data. One such technique is frame differencing wherein after a reference frame or key is encoded, only the differences between each frame and the immediately preceding frame in the sequence are encoded. The present invention operates as a pre-process or in conjunction with such a technique by determining which of the changed data points can be disregarded without significantly affecting, for example, the stored image, thereby reducing the amount of data which must be stored or transmitted. The determination is made in the present invention by comparing the pattern of changed data points in the vicinity of the data point under consideration with a set of pre-determined patterns.

Claims

1. A method of compressing an image signal comprising a sequence of frames, said frames having a plurality of corresponding data locations, each of said data locations having pixel data associated therewith, said method comprising the steps of:

comparing said data associated with a first location in a first frame with said data associated with said first location in a second frame;

determining whether a change in said data associated with said first location has occurred between said first frame and said second frame;

determining whether a change in said data between said first frame and said second frame in a predetermined group of locations proximate said first location has occurred, if a change in said data associated with said first location has occurred, to form a pattern of locations wherein said data has changed;

comparing said pattern with at least one predetermined reference pattern; and

,

disregarding said change between said first and said second frames in said data associated with said first location if said pattern matches one of said at least one predetermined reference pattern by copying said pixel data from said first location in said first frame to said first location in said second frame or by flagging said pixel data in one of said first frame and said second frame.

2. A method of compressing an image signal comprising a sequence of frames, said frames having a plurality of corresponding data locations, each of said data locations having data associated therewith, said method comprising the steps of:

comparing said data associated with a first location in a first frame with said data associated with said first location in a second frame;

determining whether a change in said data associated with said first location has occurred between said first frame and said second frame;

determining whether a change in said data between said first frame and said second frame in a predetermined group of locations proximate said first location has occurred, if a change in said data associated with said first location has occurred, to form a pattern of locations wherein said data has changed;

comparing said pattern with at least one predetermined reference pattern; and

,

disregarding said change between said first and said second frames in said data associated with said first location if said pattern matches one of said at least one predetermined reference pattern;

wherein said signal comprises an image signal and said data comprises pixel data; and

wherein said at least one predetermined reference pattern comprises the patterns of;

all locations adjacent said first location not having a change in pixel data associated therewith;

one location adjacent said first location having a change in pixel data associated therewith and remaining locations adjacent said first location and adjacent said one location adjacent said first location not having a change in pixel data associated therewith; and

two locations adjacent said first location having a change in pixel data associated therewith and remaining locations adjacent said first location and adjacent said two locations adjacent said first location not having a change in pixel data associated therewith.

3. A computer readable medium having stored thereon formatted data, said formatted data containing a plurality of data locations, each of said data locations having pixel data associated therewith, said formatted data produced by compressing an image signal comprising a sequence of frames by a compression method, said compression method comprising the steps of:

comparing said data associated with a first location in a first frame with said data associated with said first location in a second frame;

determining whether a change in said data associated with said first location has occurred between said first frame and said second frame;

determining whether a change in said data between said first frame and said second frame in a predetermined group of locations proximate said first location has occurred, if a change in said data associated with said first location has occurred, to form a pattern of locations wherein said data has changed;

comparing said pattern with at least one predetermined reference pattern; and

,

disregarding said change between said first and said second frames in said data associated with said first location if said pattern matches one of said at least one predetermined reference pattern by copying said pixel data from said first location in said first frame to said first location in said second frame or by flagging said pixel data in one of said first frame and said second frame.

4. A computer readable medium having stored thereon a plurality of instructions, said instructions executable by a processor and which, when executed by said processor, cause said processor to perform the steps of:

accessing an image signal, said image signal comprising a sequence of frames, said frames having a plurality of corresponding data locations, each of said data locations having pixel data associated therewith;

comparing said data associated with a first location in a first frame with said data associated with said first location in a second frame;

determining whether a change in said data associated with said first location has occurred between said first frame and said second frame;

determining whether a change in said data between said first frame and said second frame in a predetermined group of locations proximate said first location has occurred, if a change in said data associated with said first location has occurred, to form a pattern of locations wherein said data has changed;

comparing said pattern with at least one predetermined reference pattern; and

,

disregarding said change between said first and said second frames in said data associated with said first location if said pattern matches one of said at least one predetermined reference pattern by copying said pixel data from said first location in said first frame to said first location in said second frame or by flagging said pixel data in one of said first frame and said second frame.

5. A computer readable medium having stored thereon a plurality of instructions, said instructions executable by a processor and which, when executed by said processor, cause said processor to perform the steps of:

receiving compressed data;

decompressing said compressed data, wherein said compressed data was created by a method comprising the steps of;

comparing said data associated with a first location in a first frame with said data associated with said first location in a second frame;

determining whether a change in said data associated with said first location has occurred between said first frame and said second frame;

determining whether a change in said data between said first frame and said second frame in a predetermined group of locations proximate said first location has occurred, if a change in said data associated with said first location has occurred, to form a pattern of locations wherein said data has changed;

comparing said pattern with at least one predetermined reference pattern; and

,

disregarding said change between said first and said second frames in said data associated with said first location if said pattern matches one of said at least one predetermined reference pattern by copying said pixel data from said first location in said first frame to said first location in said second frame or by flagging said pixel data in one of said first frame and said second frame; and

displaying an image represented by said compressed data.

6. A method of displaying an image, said method comprising the steps of:

receiving compressed data;

decompressing said compressed data, wherein said compressed data was created by a method comprising the steps of;

comparing said data associated with a first location in a first frame with said data associated with said first location in a second frame;

determining whether a change in said data associated with said first location has occurred between said first frame and said second frame;

determining whether a change in said data between said first frame and said second frame in a predetermined group of locations proximate said first location has occurred, if a change in said data associated with said first location has occurred, to form a pattern of locations wherein said data has changed;

comparing said pattern with at least one predetermined reference pattern; and

,

disregarding said change between said first and said second frames in said data associated with said first location if said pattern matches one of said at least one predetermined reference pattern by copying said pixel data from said first location in said first frame to said first location in said second frame or by flagging said pixel data in one of said first frame and said second frame; and

displaying said image represented by said compressed data.

7. A method of displaying an image, said method comprising the steps of:

receiving compressed data;

decompressing said compressed data, wherein said compressed data was created by a method comprising the steps of;

comparing said data associated with a first location in a first frame with said data associated with said first location in a second frame;

determining whether a change in said data associated with said first location has occurred between said first frame and said second frame;

determining whether a change in said data between said first frame and said second frame in a predetermined group of locations proximate said first location has occurred, if a change in said data associated with said first location has occurred, to form a pattern of locations wherein said data has changed;

comparing said pattern with at least one predetermined reference pattern; and

,

disregarding said change between said first and said second frames in said data associated with said first location if said pattern matches one of said at least one predetermined reference pattern;

wherein said signal comprises an image signal and said data comprises pixel data; and

wherein said at least one predetermined reference pattern comprises the patterns of;

all locations adjacent said first location not having a change in pixel data associated therewith;

one location adjacent said first location having a change in pixel data associated therewith and remaining locations adjacent said first location and adjacent said one location adjacent said first location not having a change in pixel data associated therewith; and

two locations adjacent said first location having a change in pixel data associated therewith and remaining locations adjacent said first location and adjacent said two locations adjacent said first location not having a change in pixel data associated therewith; and

displaying said image represented by said compressed data.