Image analysis – Image compression or coding
Reexamination Certificate
1999-12-03
2001-08-14
Patel, Jay (Department: 2721)
Image analysis
Image compression or coding
C382S173000
Reexamination Certificate
active
06275615
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to method and apparatus for detecting predetermined attributes (e.g., texture) of data signals (e.g., video and audio signals), and more specifically to a method and apparatus for detecting feature patterns of characters or graphics as the predetermined attributes of video signals (i.e., data signals).
Further, the present invention relates to a method and apparatus for an image segmentation to divide a picture into a plurality of regions to recognize and process the divided regions on the basis of video signal levels, and further to easily represent a boundary of the divided regions.
First, the prior art technique related to the method and apparatus for detecting data signal attributes will be described hereinbelow.
(1) As a novel compression coding technique for a grayscale image, fractal coding technique has been so far studied (for instance, as disclosed by Document 1: “Fractal Image Coding: A Review”, A. E. Jacquin, Proceedings of the IEEE, VOL. 81, No.10, October, 1993). In this technique, an original square picture to be coded is divided into a plurality of blocks, as shown in
FIG. 1
, and a coder decides a similar region or regions for each block on the basis of the other blocks in the same picture. Here, “similar” implies the relationship between the blocks in which the picture patterns can be roughly equalized to each other, by a linear reduction transform in the picture, a simple pixel arrangement transform (such as revolution in units of 90 degrees and mirror image reversal, etc.), and a liner transform of pixel values. The above-mentioned linear transform is referred to as an affine transform. Here, in the case of digital video signals, since a picture is constructed by a number of discrete pixels, the reduction transform in a picture is the same as the sampling of pixels.
Now, as shown in
FIG. 2
, the assumption is made that there exists a similar region
152
whose vertical and horizontal sizes are twice as large as those of a block
151
, and the block
151
is composed of 4×4 pixels and the similar region
152
is composed of 8×8 pixels. Here, when the pixel arrangement is not transformed, for instance, a pixel
153
located on the upper left side of the block
151
corresponds to a white point
155
of the similar region
152
. However, there exists no pixel at this position
155
. In this case, therefore, the value of the pixel
153
is determined by an average value of four pixels
154
surrounding the white point
155
. As described above, the reduction transform can be obtained by sampling 4×4 pixel data from the 8×8 pixel data.
Further, the fractal coder outputs (a) the position and the sizes of a similar region for each block, (b) the transform method of pixel arrangement, and (c) the data required for pixel value transform method as code data. The outputted coded data are transmitted or stored. In the reduction transform method in a picture, since the coded output data can be decided unequivocally in accordance with the size of the similar region and the size of the previously determined blocks, it is unnecessary to transmit and store the code data.
FIG. 4
is a block diagram showing a prior art fractal coder. Original picture data
301
are stored in a frame memory
302
. On the basis of a signal
304
for designating the linear transform applied from a control section
303
, picture data
305
in a designated region are read from the frame memory
302
, and then inputted to a size reduction transform section
306
. The size reduction transform section
306
reduces the picture data
305
in the region to the same size of the block (i.e., the same number of pixels of the block). The reduced data
307
are transmitted to the transform section
308
. The transform section
308
executes the adorementioned-mentioned linear transforms other than the size reduction transform, and the transformed data
309
are inputted to a difference section
311
. On the other hand, the block data
310
are inputted from the frame memory
302
to the difference section
311
. The difference section
311
calculates a difference between the block data
310
and the transformed data
309
, and transmits a difference
312
to a control section
303
. As described above, the control section
303
designates several sorts of linear transforms, and decides the linear transform of the minimum difference
312
as the similarity transform of the block. The decided data are outputted as codes
313
to the outside.
FIG. 3
is a block diagram showing a prior art fractal decoder for decoding an original picture on the basis of the codes transmitted from the fractal coder as described above. In the drawing, codes
501
are inputted to a transform section
502
. Further, an original picture is previously stored in a frame memory
503
. Any images can be used as the original picture. In accordance with the data included in the codes
501
, the similar region data
504
for each block are read from the frame memory
502
. The similar region data
504
are processed in accordance with the data included in the codes
501
. The processing executed by the transform section
501
is intra-picture reduction transform, pixel arrangement transform, and pixel value transform. The transformed data
505
are transmitted to the frame memory
503
, and overwritten on the corresponding blocks of the frame memory
503
. The above-mentioned rewriting of pixel values are executed for all the blocks, respectively to obtain a first replacement picture. After that, on the basis of the first replacement picture, the similar replacement as with the case of the first replacement is executed again to obtain a second replacement picture. After the above-mentioned replacements have been iterated several times, since the picture stored in the frame memory
503
can be converged to a picture roughly equal to the original picture, the converged picture is outputted to the outside as a reconstructed image
506
. The reconstructed image
506
will not change any more even if replaced repeatedly. In other words, the following expression can be obtained
F(A)=A
where A denotes a reconstructed image and F denotes a replacement transform.
The fact that an image is reconstructed on the basis of the fractal coding/decoding is to obtain an image A which can satisfy the above expression. In the case where the transform F is the reduction transform, the conventional method utilizes such a nature that any image can approach an image A gradually after the replacement transforms F have been iterated.
FIG. 5A
is a block diagram showing a prior art fractal decoder. First, any desired initial pictures can be stored in a picture memory
401
. In general, this initial picture is different from an original picture. Input codes
402
are read from a storage medium
403
, for instance. Further, similarity region data
405
of the first block are read from the picture memory
401
. The data
405
read from the picture memory
401
are transformed by a position transform section
404
in accordance with the transform designated by the position transform codes
406
of the first block, and then transmitted to a pixel value transform section
407
. In the pixel value transform section
407
, the transform executed is designated by the pixel value transform codes
408
of the first block. The transformed data
409
are returned to the picture memory
401
. In the picture memory
401
, the first block pixels are replaced with the transformed data. The pixel replacement by the similarity transform as described above are executed for the second block and after in the same way, to obtain the first transformed picture. The obtained picture is different from the original picture in general.
After that, the similar replacement transforms for each block are executed by use of the first transformed picture stored in the picture memory
401
, to obtain the second transformed picture. By repeating the above-mentioned replacement transforms, the picture in the pic
Ida Takashi
Kagoshima Takehiko
Sanbonsugi Yoko
Takahashi Hiroshi
Foley & Lardner
Kabushiki Kaisha Toshiba
Patel Jay
LandOfFree
Method and apparatus for image representation and/or... 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 image representation and/or..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for image representation and/or... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2533109