Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
1998-09-09
2002-11-12
Tran, Phuoc (Department: 2621)
Image analysis
Image compression or coding
Transform coding
C382S250000, C382S277000, C382S281000
Reexamination Certificate
active
06480631
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a technique for image processing. In particular, this invention relates to an image processing apparatus and methods that can rotate, enlarge, reduce, clip and overlap images at low cost and high speed.
2. Discussion of the Related Art
Generally, image processing can be largely divided into two types. One type is geometrical processing which changes the position of the pixels. The other type is pixel value processing which changes the value of the pixels. Examples of geometrical processing are affine transformation, such as rotation, enlargement or reduction of images, and clipping or overlapping of images which cut out pixels. Pixel value processing includes color correction and filter processing.
Among these types of image processing, the rotating process differs substantially from the others. In general, image data is processed in the order of the raster scan, and the result is output in that order as well. On the other hand, when rotating images, the order of input and output of data differs at the source, or input side, and the destination, or output side.
When data is input from the source side according to the raster scan order and is rotated, it is written diagonally on the destination side. In this case, random access of image data is necessary at the destination side. This is called a sequential transform method. When image data is sent so that it appears in the raster scan order at the destination side, random access is necessary at the source side. This is known as an inverse transform method.
In both methods, random access is necessary either on the source side or the destination side. To make random access possible, page memory is used in existing technologies. In the case of the sequential transform method, the rotated image is created in the page memory of the destination side. On the other hand, in the inverse transform method, all images are first written in the page memory and then rotated. Methods that can reduce the amount of time needed for sending image data and for calculating coordinates have been suggested hitherto based on these two methods.
One of these methods is disclosed by Japanese Laid-Open Patent Application No.61-161576. This method aims to increase the speed of the image rotation process by dividing the images into blocks and processing them locally.
FIG. 16
is a block diagram illustrating this method. The image input unit
10
stores input image data
200
in a page memory of the source side
49
. The inverse transform coordinate calculating unit
29
calculates the source side coordinate by inversely transforming the center pixel of the local data at the destination side. This coordinate is then output as the inverse transform coordinate
229
.
The page memory reading unit
48
sends the source side address of the local data
228
to the source side page memory
49
. The inverse transform coordinate
229
is the center of the source side address of the local data
228
. The source side page memory
49
stores input image data
200
and sends local data
230
to local data transform unit
51
as indicated by the source side address
228
. The local data
230
is, for example, a 3×3 pixel block data.
The local data transform unit
51
reads local data
230
and performs such transform processing as rotation, enlargement or reduction according to the transforming information
231
stored in transforming ROM
52
. The local transform unit
51
then outputs the transformed local data
240
to the destination side page memory
79
. Page memory writing unit
78
sends the destination side address
269
to the destination side page memory
79
, which corresponds to inverse transform coordinate
229
. The destination side page memory
79
stores the transformed local data
240
and then sends the local data
270
to image output unit
80
according to the destination side address
269
. Image output unit
80
then outputs the output image.
FIG. 17
describes a process in which the rotating process of an image is separated into local rotation and global rotation based on the above method. When local data
400
is rotated around pixel
420
, which is the center of rotation, it becomes local data
430
. However, since pixels must be aligned either horizontally or vertically, the actual object of the rotation process is to obtain post-rotation local data
450
and its coordinate. In this method, the post-rotation local data
450
is attained by locally rotating local data
430
around post-rotation center pixel
440
. According to this method, by tabulating the destination coordinate within local data correspondent to rotation angle &agr; and storing the table in ROM, there is no need to calculate coordinates for every local data since the processing is uniform for all local data. The post-rotation center pixel
440
can be calculated for each local data from the pre-rotation center pixel
410
, center pixel
420
and rotation angle &agr;.
As can be seen from the above, the rotation process of this method is characterized by two separate processes: local processing based on transforming ROM
52
, and global processing to obtain the address of the local data at its destination. The local processing is simplified enough to be performed at high speed by hardware, and the global processing can reduce the number of calculations. The problem with this method, however, is the high cost of the apparatus as a whole. Page memories are generally very expensive and this method assumes the need for two page memories.
The method explained hereafter reduces the cost of the apparatus by eliminating the need for page memories. This method is used in the inventions of Japanese Laid-Open Patent Applications Nos.62-140175 and 62-20074. In the first method, the rotating process is divided into local processing and global processing. When performing merely local processing, only the memory enough to store local data is needed. The second method eliminates global processing by using only a low-capacity buffer memory and performing the reading process many times across horizontal lines of data.
FIG. 18
is a block diagram illustrating this method. The parts_that perform the same function as in
FIG. 16
have the same numbers and are therefore, not explained here in repetition.
The buffer reading unit
46
sends to the reading buffer
47
the source side address
227
of local data, the center of which is the inverse transform coordinate
229
. The reading buffer
47
stores the input image data
200
in the order of the raster scan and then sends local data
230
to the local data transforming unit
51
according to the source side address information
227
. The buffer writing unit
76
sends to writing buffer
77
the destination side address
26
which corresponds to the inverse transform coordinate
229
. The writing buffer
77
stores the transformed local data
240
, and then sends output image data
270
to the image output unit
80
according to the destination side address
268
.
In the above method, the smaller the reading buffer
47
, the lower the cost. Reading buffer
47
can be formed when there is enough capacity to store the number of lines needed when rotating local data at least forty-five degrees.
FIG. 19
shows the flow of local data((
1
)~(
6
)) from image input to image output. As shown in FIG.
19
:
(1) The inverse transform coordinate (X
src
, Y
src
), which corresponds to the center (X
des
, Y
des
) of the local data, is calculated. The input image data is divided into blocks with regard to the coordinates of the destination side.
(2) The local data, the center of which is the inverse transform coordinate, is read and stored in the reading buffer
47
. In performing this process, speedy reading by random access is not possible when low-priced hard disks are used. In such a case, all image data comprising the line including the local data in question are read.
(3) The local data, the center of which is the inverse transform coordinate, is read out from the re
Ihara Fujio
So Ikken
Tomida Koumei
Yokose Taro
Alavi Amir
Fuji 'Xerox Co., Ltd.
Oliff & Berridg,e PLC
Tran Phuoc
LandOfFree
Geometrical image processing apparatus and method of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Geometrical image processing apparatus and method of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Geometrical image processing apparatus and method of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2940536