Image analysis – Image compression or coding – Contour or chain coding
Reexamination Certificate
2000-10-26
2004-04-27
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Contour or chain coding
Reexamination Certificate
active
06728412
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
Not applicable.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to an image coding method, and more particularly to a real-time image data compressing method in accordance with feature points detection to thereby encode an image signal with high efficiency, and also to an apparatus for the same.
2. Description of Prior Art
Digitized images require a notoriously large amount of storage space and bandwidth to store and transmit the image data. For example, a 24-bit color picture of an 8.5 inch by 11 inch page, at a modest resolution of 300 dots per inch, occupies as much as 25 megabytes of data. Video images are even more data intensive, requiring data handling and transmission rates of about a billion bits per second.
According to a typical conventional image compression method, information is coded to improve the efficiency of image transmission and storage so as to suppress information redundancy which is normally present in digital image data.
Various compression techniques are known for compressing digital data into compressed form. For instance, run-length encoding (RLE), Huffman coding, Lempel-Ziv-Welch (LZW), Shannon-Fano, and Discrete Cosine Transform (DCT) coding are all examples of compression techniques for compressing image data.
With respect to an original including a bi-level image, compression methods such as one-dimensional runlength image coding, e.g. Modified Huffman (MH), two-dimensional image coding methods, e.g. Modified READ (MR) and Modified Modified READ (MMR), and the Joint Bi-level Image Expert Group (JBIG) system using a hierarchical encoding function are known and have already been adapted to facsimile communication. MH scheme uses, as an information source, the number of successive pixels of the same level of the binary image signal. MR and MMR schemes exploit the difference between run changing points on a coding line and an immediately preceding line and encode bi-level images on the line-by-line basis. However, these coding schemes are not essentially suitable for compressing color imagery. On the other hand, color documents used in offices have gradually increased in number with the recent spread of full-color copying machines and printers of high image quality. In addition, a number of new applications have emerged which utilize the transmission of color image data through limited bandwidth data links.
For compressing a color image, the JPEG system has been accepted as a standard by the International Organization for Standardization (ISO) and Telecommunication Standardization Sector (TSS, former CCITT). However, JPEG and other existing techniques for compressing color imagery require a relatively significant amount of memory and data processing to compress and then decompress the data. Such processing requires a relatively lengthy time period, and therefore, the compression and decompression of the data can not be implemented in high data rate, real-time applications. In addition, these techniques do not fully exploit information redundancies found in most images. When lossy coding techniques, such as JPEG, are used, image quality deterioration tends to occur around the edges as the compression rate increases.
Region-based, or vector-based, image coding techniques have been proposed for still image compression based on the principle of segmentation of an image into a set of regions and encoding the resulting contours. Most efficient region encoding techniques utilize the so-called chain codes, which generally refer to 8-chain code representation for each region boundary pixel introduced in H. Freeman, “Computer Processing of Line Drawings”, Computer Surveys, vol. 6 (1), pp. 57-97 (1974). Briefly, in a chain code method the raster image is scanned until a pixel, which is at the border of a region, is located. The surrounding pixels are then scanned in a predetermined order to determine the next border pixel and encode shift direction. This new pixel then becomes the current pixel and the operation of next border pixel determination is repeated until the last border pixel is found. At the end of encoding process, the compressed data are represented as a set of chain codes for each uniform pixel region in the image.
While existing chain code algorithms oftentimes allow for significant improvement in compression of noiseless images as compared to conventional block-based coding schemes, their main drawbacks are inherent complexity and high memory buffer requirements. Bypassing a contour of region usually implicates storing the full image or its significant part in memory, as well as repetitive random access to image elements across the image, making these methods infeasible for real time applications. Conventional techniques based on line by line contour tracing are limited to only bitonal, e.g., black and white, image representation.
The above techniques for compressing digitized images represent only a few of the techniques that have been devised. However, none of the known techniques yet achieves compression ratios and coding speed sufficient to support the huge still and video data storage and transmission requirements expected in the near future. In addition, for real time, high quality still and moving image transmission, none of the conventional compression and decompression algorithms is considered simple enough and commercially reasonable to be able to process very dense data inputs with minimum latency times.
Accordingly, there is an urgent need for a new image coding technique which achieves high compression ratios without sacrificing quality, and does so with a greatly reduced requirement for extensive computations.
BRIEF SUMMARY OF THE INVENTION
In accordance with the present invention, the above problems are solved by a method, or apparatus, for compressing an input data stream into compressed data by sequential detection of feature points representing object boundaries, simultaneous boundary following, and encoding the continuous feature points in a compact chain link form.
The present invention resides in the realization that an image can be represented by outline boundaries of regions containing pixels of similar characteristics and these boundaries can be detected on the fly as sets of continuous feature points and efficiently encoded in a chain-linked output code. As such, the invention enables input image data to be processed directly, line by line, and without the need to store the image or its significant fraction in memory and thus offers significant advantages in terms of processing and memory buffer requirements.
According to one aspect of the invention there is provided an image coding method in which an input image data is scanned, one line at a time, to detect continuous feature points on a scan line in the image and to represent the feature point displacements on adjacent scan lines as a function of detected displacements of previous feature points associated with the same boundary thereby to reduce the amount of data used to define the image.
According to another aspect of the invention there is provided an image coding apparatus comprising a line scanner for supplying digital image data and feature point detection, a boundary matcher/follower for associating continuous feature points on adjacent lines in the supplied image, memory buffers for temporal storage of feature point data, and a coder for chain link encoding the continuous feature point sequences, thereby to reduce the amount of data defining the image.
According to a further aspect of the invention, there is provided an image coding method in which continuous object boundaries are traced independently of each other on the line-by-line basis, however the information on nearby color transitions in the current and at least one adjacent line is used to check a boundary for continuity.
Furthermore, according to the invention, predictive coding can be used to encode continuous feature point sequences. Predictive coding is based on spatial stochastic correlation of feature points
Couso Jose L.
S.V.V. Technology Innovations, Inc.
LandOfFree
Method and apparatus for on-the-fly image coding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for on-the-fly image coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for on-the-fly image coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3207292