JPH11224331A - Raster image generation device and raster image generation method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To reduce a memory required for the processing of scanned images by reducing source images as needed, then dividing them into partial-images and encoding only the partial image contributing to the plotting of a device image. SOLUTION: Image information is received and stored in the memory 4. When an interpreter 10 detects the plotting request of the scanned image, the image data (source image) of the scanned image are inputted and supplied through a bus 3 to an image input means 20. The image input means 20 is connected to a reduction means 21 and a row buffer 24. The row buffer 24 is connected to a division means 22 and the output of the division means 22 is supplied to an encoding means 23. The source image is divided into the partial images. There are cases that the source image is reduced and then divided into the partial images. The image is encoded by referring to overlap information 14 for the respective partial images and the code 17 of the partial image which is the output of the encoding means 23 is stored in the memory 4.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for generating raster image data for a printer or a raster output device or an image drawing apparatus for performing drawing. In particular, the present invention relates to a raster image generating apparatus and a raster image generating method for performing affine transformation on an image, cutting out the image into an arbitrary shape, and drawing the image at an arbitrary position on an output image.

[0002]

2. Description of the Related Art In addition to character data, graphic data such as straight lines, curves, and polygons (these are referred to as line art), and scanned images obtained by scanning and inputting photographs, handwritten documents, printed matter, etc., are output to a printer or the like. A page description language (hereinafter abbreviated as PDL) is widely used as an image description method for performing the above. Representative PDLs include Xerox Interpress (registered trademark of Xerox) and Adobe Systems PostS.
Script (registered trademark of Adobe Systems) is known. For details of Interpress, see S.M. J. Harrigton and R.M. R. Buc
INTERPPRESS: The Sour
ce Book-The Document and
Page Description Language
for PerformancePrinting- "
Brendy (1988), Japanese translation, "Interpress-A Page Description Language for Electronic Publishing-", Maruzen (1989). For more information on PostScript, see "PostScript" by Adobe Systems.
pt Language Reference Man
ual Second Edition "Addiso
n-Wesley (1990), Japanese translation “Page Description Language PostScript Reference Manual No. 2
Edition "ASCII (1991).

[0003] The image of the scanned image portion is represented by a raster which is a two-dimensional set of pixels. A raster is a data structure in which pixels are arranged on rectangular coordinates. For raster input / output, pixels are first input or output while scanning in the X-axis direction for one row, and then scanning is shifted by one row in the Y-axis direction to similarly input or output one row. By performing this for all rows, input or output of an image is achieved. X
Scanning in the axial direction is also called main scanning, and scanning in the Y-axis direction is also called sub-scanning.

[0004] The PDL is designed to be able to handle line art and scanned image data independently of the resolution of the image output device. For example, in PostScript, line art can be described in an arbitrary space (user space) defined by a user.
The tScript processing system converts the data into a device space depending on the resolution of the IOT. As for the scanned image data, a raster having an arbitrary resolution is input and converted into a device space. A raster image input as a scanned image is also called a source image, and in PDL, an arbitrary number of source images can be drawn on one output image (called a device image).

[0005] PostScript has three spaces: a user space, a device space, and a source space. PostScript draws in a user space of infinite size and precision. The device space is a space having a finite range and accuracy depending on a device that outputs an image. The mapping from user space to device space is defined using an affine transformation, and the transformation matrix is
Let it be 1. The source space is a space defined such that each pixel is a square having a side length of 1, and the relationship with the user space is defined using an affine transformation M2 from the user space to the source space. Therefore, the affine transformation M from the source space to the device space first performs an affine transformation M2 ^-1 from the source space to the user space (the affine transformation M2 ^-1 is a transformation M2
The affine transformation M1 may be performed from the user space to the device space. Therefore, the affine transformation M from the source space to the device space is represented by M2 ^-1 and M1 as follows.

[0006]

## EQU1 ## M = M1 · M2 ⁻¹

The coordinates (x, y) in the source space and the coordinates (X, Y) in the device space are linked by the following equation.

[0008]

(X, Y, 1) ^T = M · (x, y, 1) ^T (x, y, 1) ^T = M ⁻¹ · (X, Y, 1) ^T where (v _{1, v 2, v 3)} T is the vector (v _1,
v ₂ , v ₃ ).

The specific contents of the affine transformation matrix M are shown in the following equation.

[0010]

(Equation 3)

[0011] Each element can take an arbitrary value (however, an inverse matrix M ^-1 must exist).

The enlargement / reduction and rotation are represented by elements a, b, c and d, and the translation is represented by elements u and v.

[0013]

X = ax + by + u Y = cx + dy + v

[0014]

## EQU5 ## The following condition, ad-bc ≠ 0

[0015] there is a reverse transformation matrix M ^-1 when the is established, each element of the inverse transform matrix M ^-1 as shown below,

[0016]

(Equation 6)

Then, each element can be described as shown below.

[0018]

A ′ = d / (ad-bc) b ′ = − b / (ad−bc) c ′ = − c / (ad−bc) d ′ = a / (ad−bc) u ′ = ( bv-du) / (ad-bc) v '= (cu-av) / (ad-bc)

Therefore, the coordinates (X, Y) of the device space
, The corresponding coordinates (x, y) on the source space can be easily obtained.

[0020]

X = a'X + b'Y + u'y = c'X + d'Y + v '

In order to determine the pixel at the coordinates (X, Y) of the device image, the coordinates (x,
It is sufficient to read out the pixel for y). This is called inverse sampling.

Techniques for drawing image processing described in PDL and generating pixel information for output to an image output device are described in, for example, "Decomposer for Multiple Page Description Languages" written by Onozawa et al., Fuji Xerox Technical Report, No. 8, pp. 61-68, (199
3) and a technique invented by Hori et al. And disclosed in JP-A-5-224637.

These techniques can generally be implemented on a computer system using software describing processing steps.

In the technique disclosed in Japanese Patent Application Laid-Open No. Hei 5-224637, a PDL is input at an input unit, and the PDL is interpreted and executed by an interpreter. As a result, the drawing information is stored in the storage unit as segment information on a scanning line in the device space. A line segment in which continuous pixels on a scanning line have the same attribute is defined as a segment. Device pixels drawn in line art have the same attribute when the pixels have the same color. Device pixels rendered in a scanned image have the same attribute when they are derived from the same source image. The segment information has a data structure having, for example, the following combined list structure when described in a C language style.

[0025]

(Equation 9)

The segments on the scanning line are represented by a combined list from the left (smaller X coordinate value) to the right (larger X coordinate value). One segment is represented by one node in the linked list. The segment is from X coordinate X0 to X
The pixel value exists in the range up to 1, and the pixel value is indicated by the pointer pp. The next field of the node of a certain segment points to the node of the segment on the right. At the rightmost node on the scan line, n to indicate the rightmost
A special value in the ext field, for example, NULL (= 0)
Insert The dp field indicates whether the segment is derived from drawing a line art or a scanned image. In the case of a scanned image, the leftmost pixel of the segment is the address indicated by the pointer pp, the pixel on the right is the address of pp + 1, and the pixel on the right is pp
The pixel is accessed in the form of a +2 address.

The device image is composed of a plurality of scanning lines. Assume that the height of the device image, that is, the number of scanning lines is HD. In order to represent the entire device image, an array dev of the number of elements HD composed of pointers to the above data structure
Image is provided, and the array devImage is set so that the Y-th array element is a pointer to the node of the leftmost segment of the Y scan line in the device space.
The definition of this array is described as follows in C language.

[0028]

[Mathematical formula-see original document] structure edge_list * de
vImage [HD];

In the technique described in Japanese Patent Application Laid-Open No. Hei 5-224637, the video signal generation unit reads segment information in the order of scanning, reads output pixels using pointers to pixels, and sends the output pixels to the output unit. The general processing procedure here is described as follows in C language.

[0030]

[Equation 11]

After the source image is image-converted by the image converter, the scanned image image converted for the device image is stored in the page memory as an image of WD × HD pixels in the scanning order. The pp of the node of the segment of the scanned image indicates a pixel stored in the page memory. The pixel is a pixel corresponding to the left end pixel of the segment.

In the prior art disclosed in Japanese Patent Application Laid-Open No. 5-224637, a transformation process including affine transformation such as enlargement / reduction and rotation is performed by an image conversion unit. Many techniques are already known for affine transformation of raster images, but they can be roughly classified into the following four types.

A) Oblique axis conversion, 90 ° rotation, enlargement /
Combination with reduction. For example, JP-A-62-1776
75, the source image is rotated by 90 °, the oblique axis conversion with reduction is performed, and the source image is rotated by −90 ° and the oblique axis conversion with enlargement is performed. To achieve. In the above series of processing, between the processing steps, it is necessary to store the image on the input side and the image on the output side of each processing in the buffer memory. Therefore, it is necessary to provide a page memory for at least two images.

B) Copying pixels of a source image to corresponding locations on a device image. Determining the device coordinates from the source coordinates is called forward sampling. Specifically, as shown in FIG. 22A, the pixel coordinates (x, y) of the source image are linearly transformed by a transformation matrix M to obtain the coordinates (X, Y) of the device space, and the source image is located at the pixel position of the device space. Is copied. For example, JP-A-61-88374, JP-A-62-20074, JP-A-62-139082, JP-A-63-184878,
It is disclosed in JP-A-4-55986 and JP-A-5-250466. In this technique, since the input image can be processed in the scanning order, it is necessary to provide a page memory for the processed image.

C) Obtaining source coordinates corresponding to device coordinates and reading a source image to obtain pixels of the device image.
Determining the source coordinates from the device coordinates is called inverse sampling. Specifically, as shown in FIG. 22B, the pixel coordinates (X, Y) in the device space are converted to the inverse transformation matrix M ^-1.
To obtain the coordinates (x, y) in the source space,
The pixel of the source image is copied to the device space (X, Y). For example, it is disclosed in JP-A-62-145483, JP-A-62-256089, JP-A-63-116193, JP-A-63-129476, and JP-A-4-64177. This technique requires a page memory for unprocessed images. Further, in order to combine with the technique of JP-A-5-224637, a separate page memory is required, so it is necessary to provide a page memory for a total of two images.

D) An affine transformation is performed in two steps, a step of enlarging / reducing and a step of rotating. ,
Since it is necessary to store the image on the input side and the image on the output side of each processing in the page memory between the processing steps, it is necessary to provide a page memory for two images.

Any of the above techniques requires at least one page memory for storing the entire image.

[0038]

Problems to be Solved by the Invention
In the technology of No. 7, the size of the memory required for forming the device image can be reduced by expressing the drawing information in segments, but the portion effective for the reduction is only the portion drawn as line art. In order to render a scanned image, a memory for at least one image (called a page memory) is required for affine transformation and for holding the image itself. For example, A4 at resolution of 600 SPI
If one pixel of the full-color raster data of the size is expressed by a total of 4 bytes of four colors of cyan, magenta, yellow, and black, the amount of data becomes about 140 MByte.

A page memory is generally a semiconductor memory, especially a D memory.
RAM (Dynamic Random Access Memory)
It is configured using DRAM is used because it is an inexpensive memory device among semiconductor memories. However, providing a memory of 140 Mbytes for an A4 size image and 280 Mbytes for an A3 size image is DR.
It is very expensive to use AM.

Virtual storage is known as a technique for processing large data using a memory smaller than the data size in a computer. For general principles of virtual memory, see John L. Hennessy & David
A. A textbook “Computer Architecture AQ” by Paterson
Authentic Approach ", Sec
on Edition; 1996; Morgan K
aufmann Publishers, Inc. The description is omitted because it is described in Chapter 5.7. When the page memory is configured by using the virtual storage technology, 140 Mbytes of A4 size data is transferred between the main storage and the magnetic disk constituting the secondary storage, but the read / write speed of the magnetic disk is at most 10 MByte.
Because of e / sec, the time required for the round-trip transfer between the main memory and the secondary memory takes 28 seconds or more. Replacing the semiconductor memory with a cheaper magnetic disk by the introduction of virtual storage improves cost but causes another problem that processing speed is reduced.

JP-A-62-154152, JP-A-7-1
According to the technique disclosed in JP 21690, an image is divided into blocks, small images are created, compressed for each small image, stored on a magnetic disk, and a portion required for processing is expanded and stored as pixels in a main memory. This makes it possible to reduce the amount of data transferred to and from the secondary storage. However, if there is no new image area in the main storage and there is no free space in the main storage to load the area, First, select one of the areas currently in use,
By compressing the selected area and sending the compressed data to the secondary storage, a space is created in the main storage for a new image area,
The compressed data of the area is read from the secondary storage, decompressed and returned to an image, and written to the area of the main storage. Thereafter, the processing interrupted by the absence of the image area in the main memory is restarted. Therefore, since the image compression and decompression processes must be performed sequentially, there is a problem that the processing time becomes longer. Also, depending on the sequence of image processing, compression / expansion of a specific small image may be repeated many times, so that there is a problem in that the image quality of the image in that portion deteriorates due to the image compression / expansion.
This is because lossy compression is often used to efficiently compress an image.

An image output apparatus using today's xerography technology is a Doc manufactured and sold by Fuji Xerox Co., Ltd.
Some uColor 4040 image output devices can output 40 full-color images per second. In order to use such a high-speed image output device efficiently, a PD
It is desired that the L processing side also performs processing in 1.5 seconds or less per sheet. That is, the drawing of the scanned image is also 1.5.
It must be processed in seconds or less.

A raster is an aggregate of pixels having a two-dimensional structure, but the memory of the computer system has a one-dimensional structure. Therefore, when storing the raster in the memory, usually, one row of pixels in the main scanning direction is stored in a continuous location of the memory, and the next row of pixels is stored in the continuous location in the continuous location. , And subsequent rows are stored similarly. For this reason, pixels on the left and right of a certain pixel (excluding the left and right ends of the image) are stored in adjacent addresses in the memory, but pixels above and below a certain pixel are stored in addresses corresponding to one pixel row (this Is AW). One line is about 500 for an A4 size image with a resolution of 600 SPI.
The number of pixels is 0 (in the case of the horizontal arrangement) or about 7,000 pixels (in the case of the vertical arrangement). Therefore, if one pixel is 4 bytes, the AW is equivalent to about 20,000 bytes in the case of a vertical arrangement, and is equivalent to about 28000 bytes in the case of a horizontal arrangement.

The affine transformation of ± 90 ° rotation can be realized by sequentially reading pixels in the y-axis direction and writing or outputting pixels in the x-axis direction. Reading of pixels from the memory occurs at discrete locations for the address AW.

In affine transformation involving rotation at an arbitrary angle except ± N × 180 ° (N is an integer), writing is performed when pixels are read out along a scanning line on a source image and stored in a device image after coordinate conversion. A destination address or a read destination address when pixels along a scanning line on a device image are read from a source image using inverse conversion occurs at discrete locations in the memory. The write destination address or the read destination address distance depends on the angle, but is generally on the order of AW.

The CPU of today's high-performance computer is 300 MHZ
It operates at a time of z or more, that is, a cycle time of 3.3 ns or less, and can execute a plurality of (2 to 3) instructions in one cycle. In such a CPU, a memory access instruction is executed about once per cycle. On the other hand, the DRAM constituting the main memory has a row address cycle time of about 100 ns, a column address access time of about 40 ns in a high speed page mode DRAM, and an ED.
O (Extended Data Output) mode DRAM, about 25 ns, Synchronous
In the case of a DRAM, it is about 10 ns. There is a large difference between the memory access rate of the CPU and the rate of the DRAM, and even if the CPU is high speed, a wait occurs when accessing the DRAM, and the processing speed is greatly reduced.
In order to solve this problem, today's computers employ a hierarchical storage mechanism using a cache memory. For general principles of cache memory, see John L. Hen
nessy & David A. A textbook “Computer Arch” by both Paterson
item A Quantitative A
Propach ", Second Edition; 1
996; Morgan Kaufmann Publics
hers, Inc. Since the description is omitted in Section 5.2, the memory access pattern of the CPU generally includes a temporal locality that a memory location accessed at a certain time has a high probability of subsequently accessing the memory location, and a certain memory When a location is accessed, there is a spatial locality that the probability of accessing the vicinity is high.
On the other hand, a semiconductor memory has a property that a small-capacity memory has a short access time, that is, fast, whereas a large-capacity memory has a long access time, that is, a slow access time. CP
A small-capacity high-speed memory is arranged in one or a plurality of layers between the U and the DRAM, and control is performed so that data referred to by the CPU is placed in the small-capacity high-speed memory. This small-capacity high-speed memory is called a cache memory. If the data requested by the CPU is in the cache memory, the data is supplied from the cache memory. If the data is not in the cache memory, the main memory constituted by the DRAM is read and the CPU
Collectively writes in the cache memory a block consisting of the word requested to be read and words in the vicinity of the word, and returns the read word to the CPU. In today's high-performance computers, a 1'st cache memory that operates at the same clock as the CPU is provided on a CPU chip, and a 2'nd cache that operates at a clock slower than the CPU is often provided outside the chip.
The size of the 1'st cache is 16 KB to 64 KB
Approximately Byte, the 2'nd cache is larger than the 1'st cache and is approximately 256 KB to 1 MByte.

The operation of the cache memory in the inverse sampling of the affine transformation involving rotation will be described. Here, the rotation angle is 90 °. In this case, pixels are inversely sampled by moving Δx = 0 and Δy = 1 on the source coordinates for each device pixel. At the time of inverse sampling of a certain pixel, the following operation occurs. Since the pixel has not been accessed before that, a cache miss occurs, a read occurs in the DRAM of the main memory, and the CPU stops during that time. The cache control system also reads out the right and left (x-axis direction) pixels stored at the address adjacent to the pixel and stores it in the cache memory. The CPU accesses the pixel one row down in the source space as the inverse sampling of the next pixel (on the right in the device space). Since the pixel has not been stored in the cache yet, a cache miss occurs again, and the CPU waits for reading from the DRAM. In the process of reverse sampling on the scanning lines in the device space, the cache misses in accessing all the pixels, and the CPU waits for the operation of the DRAM. CPU
Then performs an inverse sampling of the scan line one row down in device space. In this case, the pixel of the inverse sampling destination was stored in the cache memory at the time of inverse sampling of the pixel of the upper scanning line. However, since the size of the cache memory is finite and the number of pixels on one scanning line is usually larger than the number of entries (the number of blocks) in the cache, the pixels once stored in the cache are evicted from the cache memory due to a subsequent cache miss. At this point, it does not exist in the cache. Therefore, a cache miss occurs again. A similar cache miss occurs in all the pixels on this scanning line, and the pixels are read from the DRAM every time the reverse sampling is performed. What has been described above occurs in all scanning lines, and C
The PU cannot immediately receive the pixel value from the cache and waits for a slow DRAM to proceed with the processing. At a distance on an address corresponding to one scanning line, the DRAM exceeds the address range in which the high-speed mode for changing only the column address can be used. Therefore, a new row address must be given each time the DRAM is accessed. The operating speed of the DRAM in that case is at most about 10 MHz. CPU is 300MHz
, But the cache memory does not work at all during the reverse sampling process, so the D
Overall processing proceeds at the operating speed of the RAM.

The case described above is not a special case in which the cache memory of the CPU cannot operate. When .DELTA.y.noteq.0, access is made to discrete memory locations on the main memory, so that there is no effect of the cache memory. Only when Δy = 0, an access occurs in a continuous address direction, so that the prefetch effect (spatial locality) of the cache memory works effectively. But,
There are many more cache misses compared to the cache operation at the time of general program execution.

For an image with a resolution of 600 SPI and A4 size, 35 × 10
^Six reads to main memory occur. DRAM
Has a row address cycle time of 100 ns (mi
n), it takes 3.4 seconds in total for only DRAM access. In addition, since the overhead time of the DRAM controller and the overhead time of the system bus are required, the total wait time of the CPU is further increased. The CPU also takes time for other processing. Therefore, an image cannot be processed at a performance corresponding to the image output apparatus, that is, 1.5 seconds / sheet. Since access to the DRAM is a bottleneck, it cannot be improved even if the number of CPUs is increased using multiprocessor technology.

[0050]

In order to solve the above-mentioned various problems of the prior art, a raster image generating apparatus and a raster image generating method according to the present invention have the following configurations. It is characterized by.

A raster image generating method according to the present invention includes an image dividing step of dividing a raster image into a plurality of partial images, an encoding step of encoding the partial images obtained in the image dividing step, and obtaining a code of the partial images. A decoding order determining step for determining a decoding order of the codes of the partial images obtained in the encoding step; and decoding the codes of the partial images in accordance with the order determined in the decoding order determining step, and storing the partial images in the memory means. Decoding step, a coordinate space conversion step of converting the geometric information expressed in the first coordinate space into the second coordinate space, and generating an address on the memory means corresponding to the geometric position in the second coordinate space. And a step of reading out the memory means using the address generated in the address generating step. And butterflies.

In the raster image generating method according to the present invention, the first coordinate space is a device space, the second coordinate space is a source space, and the coordinate space conversion step is as follows.
Inverting raster scan information forming a drawing geometry of a scanned image on a device space into a source space to obtain geometric information in the source space, that is, raster scan information. Generating address information of the pixels of the partial image on the memory means corresponding to the pixels of the scanned image in the device space using the raster scan information on the source space obtained in the step, and using the address information. It is characterized in that pixels are sequentially read from the memory means and pixels of the scanned image in the device space are sequentially acquired.

Further, the raster image generating method of the present invention further comprises an overlap detecting step for checking an overlap between the partial image obtained in the image dividing step and a geometrical shape obtained from drawing information input to the raster image generating apparatus. ,
A partial image selection step of selecting a partial image that contributes to the drawing of the device image according to the overlap detection result in the overlap detection step, and the encoding step is performed only for the partial image selected in the partial image selection step. The encoding step is a step of obtaining a code of the partial image.

In the raster image generating method according to the present invention, the overlap detecting step reads out the outline information of the scanned image from the drawing information, and performs the inverse of the affine transformation designated at the time of drawing the read scanned image. Performing a transformation to map the contour information to the source space of the scanned image, and to detect an area of the partial image which is inside or overlaps the contour of the mapped source space. I do.

Further, the raster image generating method of the present invention
A reduced raster image generating step of performing reduction of the raster image to generate a reduced raster image, wherein the image dividing step executes division of the reduced raster image generated in the reduced raster image generating step into partial images It is characterized by the following.

The raster image generating apparatus according to the present invention further comprises: an image dividing means for dividing the raster image into a plurality of partial images;
Coding means for coding the partial image generated by the image dividing means to obtain the code of the partial image; decoding means for decoding the code of the partial image generated by the coding means and storing the code in the memory means; Coordinate space converting means for converting geometric information expressed in a space into a second coordinate space; address converting means for generating an address on a memory means corresponding to a geometric position in the second coordinate space; Decoding order determining means for determining a decoding order for decoding the codes of the partial images generated by the decoding means, wherein the partial images decoded in accordance with the decoding order determined by the decoding order determining means are stored in the memory means, and the first coordinates A configuration is provided in which the pixels of the partial image stored in the memory means are read out using the memory address obtained by providing the geometric information of the space to the coordinate conversion means and supplying the output to the address conversion means. And wherein the Rukoto.

In the raster image generating apparatus according to the present invention, the first coordinate space is a device space, the second coordinate space is a source space, and the coordinate space converting means scans on the device space. The raster scan information forming the drawing geometric shape of the image is inversely transformed into the source space to obtain the geometric information in the source space, that is, the raster scan information. Means for generating address information of the pixels of the partial image on the memory means corresponding to the pixels of the scanned image in the device space using the raster scan information in the device space, and sequentially using the address information generated by the address conversion means. A configuration is provided in which pixels are read from the memory means and pixels of a scanned image in the device space are sequentially acquired. And wherein the Rukoto.

The raster image generating apparatus according to the present invention further comprises an overlap detecting means for detecting an overlap between the partial image generated by the image dividing means and a geometric shape obtained from drawing information input to the raster image generating apparatus. Has,
Selecting a partial image that contributes to the drawing of the device image in accordance with the result of the overlap detection by the overlap detection unit, and encoding only the selected partial image by the encoding unit to obtain a code of the partial image. I do.

Further, the raster image generating apparatus of the present invention has an overlap detecting means for detecting an overlap between the partial image generated by the image dividing means and a geometric shape obtained from drawing information inputted to the raster image generating apparatus. The partial image is selectively read by the dividing means in accordance with the result of the overlap detection by the overlap detecting means, and the read partial image is encoded by the encoding means.

Further, in the raster image generating apparatus according to the present invention, the overlap detecting means reads out the outline information of the scanned image from the drawing information, and performs an inverse transformation of the affine transformation designated when the read out scanned image is drawn. Executing contour information in the source space of the scanned image, and detecting an inner part of the contour of the mapped source space or an area of a partial image overlapping the contour. .

Further, the raster image generating apparatus of the present invention has a reducing means for reducing the raster image to generate a reduced raster image, and the image dividing means includes a partial image processing unit for the reduced raster image generated by the reducing means. Is performed.

Further, the raster image generating apparatus of the present invention synchronizes the decoding timing position of the partial image executed by the decoding means with the conversion timing position in the first coordinate space where the conversion is executed by the coordinate conversion means. It is characterized in that it is configured to operate by making it operate.

Further, the raster image generating apparatus of the present invention has a table for associating the second coordinate space with the memory address in the address converting means, and the table is constituted by an independent table for each input raster image. It is characterized by having.

According to the first, second and fifth aspects of the present invention,
The source raster image is divided into a plurality of partial images of a predetermined size as it is or after being reduced. Here, the divided partial images are encoded for each partial image, and a code having a smaller data amount than the original partial image is obtained. The code is stored in the memory means. When the device images are scanned in raster order, the order in which the partial images appear on the scan is checked, and that order is defined as the decoding order of the partial image codes. In accordance with the decoding order, the code is decoded, the partial image is reproduced, and stored in a predetermined location of the memory means. Device space is the first coordinate space, source space is the second
Coordinate space. Raster scan information forming the drawing geometric shape of the scanned image in the device space is inversely transformed into the source space to obtain geometric information in the source space, that is, raster scan information. Using the obtained raster scan information in the source space, the address information of the pixels of the partial image on the memory means corresponding to the pixels of the scanned image in the device space is generated. Using the address information, the pixels are sequentially read from the memory means to sequentially obtain the pixels of the scanned image in the device space.

According to the third, fourth and fifth aspects of the present invention, the source raster image is divided into a plurality of partial images of a predetermined size as it is or after being reduced. The geometrical shape of the portion where the source image is drawn in the device space is determined, and it is checked whether or not the geometrical shape and the partial image are in an overlapping relationship. The partial images having an overlapping relationship are encoded for each partial image, and a code having a smaller data amount than the original partial image is obtained. The code is stored in the memory means. When the device images are scanned in raster order, the order in which the partial images appear on the scan is checked, and that order is defined as the decoding order of the partial image codes. In accordance with the decoding order, the code is decoded, the partial image is reproduced, and stored in a predetermined location of the memory means. The device space is defined as a first coordinate space, and the source space is defined as a second coordinate space. Raster scan information forming the drawing geometric shape of the scanned image in the device space is inversely transformed into the source space to obtain geometric information in the source space, that is, raster scan information. Using the obtained raster scan information in the source space, the address information of the pixels of the partial image on the memory means corresponding to the pixels of the scanned image in the device space is generated. Using the address information, the pixels are sequentially read from the memory means to sequentially obtain the pixels of the scanned image in the device space.

According to the present invention, a raster image in a source space is divided into a plurality of partial images of a predetermined size after being directly reduced by a dividing means or at a predetermined reduction ratio. I do. Each partial image is supplied to the encoding means to obtain the code of the partial image. The amount of data is reduced by encoding. The code of the partial image is stored in the memory means. The decoding order determining means checks the order in which the partial images appear on the scan when the device images are scanned in the raster order, and determines the order as the decoding order of the partial image codes. The decoding means decodes the codes of the partial images according to the decoding order determined by the decoding order determining means to create a partial image. The partial image is stored at a predetermined location in the memory means. The device space is defined as a first coordinate space, and the source space is defined as a second coordinate space. The coordinate conversion means inputs raster scan information forming a drawing geometric shape of the scanned image represented in the device space, performs inverse conversion to the source space, and outputs geometric information in the source space, that is, raster scan information. The address generation unit inputs raster scan information in the source space and generates address information of a pixel of the partial image on the memory unit corresponding to a pixel of the scanned image in the device space.
The pixels of the scanned image portion of the device image are obtained by sequentially reading the pixels of the partial image stored in the memory means using the address information.

According to the eighth, tenth and eleventh aspects of the present invention, the raster image in the source space is divided into a plurality of partial images of a predetermined size after being reduced by a dividing means as it is or at a predetermined reduction ratio. The overlap detecting means obtains a geometric shape of a portion where the source image is drawn in the device space,
It is checked whether or not this geometrical shape and the partial image are in an overlapping relationship. The encoding unit inputs and encodes each of the partial images for which the overlap has been detected by the overlap detection unit to obtain a code of the partial image. The amount of data is reduced by encoding. The code of the partial image is stored in the memory means. The decoding order determining means checks the order in which the partial images appear on the scan when the device images are scanned in the raster order, and determines the order as the decoding order of the partial image codes. The decoding means decodes the codes of the partial images according to the decoding order determined by the decoding order determining means to create a partial image. The partial image is stored at a predetermined location in the memory means. Device space first
And the source space is a second coordinate space. The coordinate conversion means inputs raster scan information forming a drawing geometric shape of the scanned image represented in the device space, performs inverse conversion to the source space, and outputs geometric information in the source space, that is, raster scan information. The address generation means inputs raster scan information in the source space,
Address information of pixels of the partial image on the memory means corresponding to the pixels of the scanned image in the device space is generated. The pixels of the scanned image portion of the device image are obtained by sequentially reading the pixels of the partial image stored in the memory means using the address information.

According to the ninth, tenth and eleventh aspects of the present invention, the raster image in the source space is divided into a plurality of partial images of a predetermined size after being reduced by a dividing means as it is or at a predetermined reduction ratio. The overlap detecting means obtains a geometric shape of a portion where the source image is drawn in the device space,
It is checked whether or not this geometrical shape and the partial image are in an overlapping relationship. The dividing unit forms a partial image for the partial image for which the overlap is detected by the overlap detecting unit, and outputs the partial image to the encoding unit. The encoding means inputs each partial image and performs encoding to obtain a code of the partial image. The amount of data is reduced by encoding. The code of the partial image is stored in the memory means. The decoding order determining means checks the order in which the partial images appear on the scan when the device images are scanned in the raster order, and determines the order as the decoding order of the partial image codes. The decoding means decodes the codes of the partial images according to the decoding order determined by the decoding order determining means to create a partial image. The partial image is stored at a predetermined location in the memory means. The device space is defined as a first coordinate space, and the source space is defined as a second coordinate space. The coordinate conversion means inputs raster scan information forming a drawing geometric shape of the scanned image represented in the device space, performs inverse conversion to the source space, and outputs geometric information in the source space, that is, raster scan information. The address generation unit inputs raster scan information in the source space and generates address information of a pixel of the partial image on the memory unit corresponding to a pixel of the scanned image in the device space. The pixels of the scanned image portion of the device image are obtained by sequentially reading the pixels of the partial image stored in the memory means using the address information.

According to the twelfth aspect, the decoding means decodes the code of the partial image in accordance with the decoding order determined by the decoding order determining means, restores the partial image, and stores the partial image in the memory means. The drawing information in the space is read out in the order of the scanning line, and the coordinate conversion means reversely converts the information into the second coordinate space, that is, the source space. Synchronize the processing timing.

According to the thirteenth aspect of the present invention, the address conversion means refers to an independent address conversion table for each source image and converts the partial image position in the second coordinate space, that is, the source space, into the partial image in the memory means. , The address of the pixel is calculated, and the value of the pixel is obtained.

[0071]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS The details of a raster image generating method and a raster image generating apparatus according to the present invention will be described with reference to three embodiments.

[Embodiment 1] First, a raster image generating method and a processing procedure of a raster image generating apparatus according to a first embodiment will be described with reference to FIG. The process forks a process in the middle, and a plurality of processes cooperate while performing synchronization to perform the process.

In the first step S01 of the processing procedure, a PDL describing drawing information is input. Next, step S
At 02, the input PDL is interpreted and executed by the interpreter. When the interpreter detects a scan image drawing request, it forks a process consisting of a series of processes from steps S10 to S13, and the process forks a process S03.
Operate in parallel with the following steps.

In step S10, a scanned image is input. The image is input in the form of raster data or a code for data compression. In the latter case, the code is decoded into raster data in this step. Hereinafter, this raster data is used as a source image. In step S11, the source image is divided into tiles by a square partial image of 64 × 64 pixels. At the time of division, the source image may be reduced and then divided into a partial image of 64 × 64 pixels according to an instruction of the interpreter. When the image is reduced, the image after the reduction is regarded as a source image and processed. In step S12, an image is encoded for each partial image. At this time, the encoding is performed only when the encoding condition of the partial image is TRUE with reference to the overlapping information created in step S20 described later. The code created here is written in a memory location corresponding to the location of the partial image in step 13. When the encoding of each partial image and the writing of the code are all completed, the process ends.

As a result of the execution of the interpreter in step S02, various drawing commands, such as drawing characters, drawing straight lines, drawing curves, and filling closed spaces, are sent to step S03 in accordance with the PDL drawing information. .
In step S03, drawing information in the device space is formed based on the drawing command. In the embodiment, Japanese Patent Laid-Open No.
The technique similar to the technique disclosed in Japanese Patent No. 24637 is used, and the drawing information is generated and recorded as segment information on a scanning line in the device space. When the interpreter detects the end of drawing for one page, it forks three processes. One is from step S20 to S21
The second is a process consisting of a series of processes from steps S22 to S24, and the third is a process consisting of a series of processes from steps S30 to S34.

In step S20, it is determined whether or not each of the partial images obtained by dividing the source image contributes to the rendering of the scanned image portion of the device image. In PDL such as PostScript, a source image is affine-transformed, cut out in an arbitrary figure shape, and then drawn on a device image. Furthermore, after drawing on a device image, an arbitrary line art may be overwritten on a scanned image image. For this reason, the contour shape of the scanned image portion in the device space has an arbitrary shape. Only pixels existing inside the contour shape or in a partial image intersecting with the contour shape contribute to drawing of the device image. In step S12, a partial image invalid for drawing is encoded.
There is no point in writing to memory at 13. Therefore, the superposition of the effective partial image, that is, the partial image and the closed region of an arbitrary shape is detected, and this is notified to the step S12 as the encoding condition, that is, the overlap information.

In step S21, a set of valid partial images is mapped onto a device image, and when a scan line in the device space is scanned from top to bottom, a new partial image that appears on the scan line is examined. A table in which a list of newly appearing partial images is prepared for each scanning line is prepared. In this table, the partial images are sorted and arranged in the scanning line order. Since the output of the device image is performed by scanning in the scanning line order and outputting the pixels, this table may be used to decode the partial image newly output on the scanning line Y before outputting the scanning line Y. Therefore, creation of this table determines the decoding order. The decoding order information is transmitted to step S22. This process ends when step S21 is completed.

In step S22, the code of the partial image written in the memory in step S13 is read from the memory using the decoding order information created in step S21. In step S23, the code is decoded to restore the partial image, and in step 24, the partial image is written to the memory. This process is completed when the code memory read / decode / image memory write processing is completed for all the partial images described in the decoding order information.

Steps S30 and S33 are selectively activated by a pixel segment which is drawing information. If the pixel segment is a line art, 1 + X1-X0 pixels (where X0 is the X coordinate of the left end of the segment and X1 is the right end) are created in step S33 and output in step S34. When the pixel segment is a scanned image, first, in step S30, the coordinates of each pixel from the start point to the end point of the segment in the device space are converted to the source space to obtain the coordinates of the pixel in the source space. Next, in step S31, each source coordinate value is converted into an address of the pixel on the memory, the pixel is read from the memory in step S32 using the address, and output in step S34. The pixel read from the memory in step S34 is the pixel written in the memory in step S24. The above processing is performed for one page, that is, for the rightmost segment in order from the leftmost segment on the scanning line from the first scanning line to the last scanning line. This process ends when the processing for one page is completed.

FIG. 2 shows an overall block diagram of the first embodiment of the present invention. In this embodiment, the CPU 1 and the I / O means 2
And a memory 4 on a computer system connected by a bus 3. The CPU 1 reads and executes a program instruction word stored in the memory 4. In the course of the execution of the program, various data stored in the memory 4 is loaded into the CPU 1, various operations are performed according to the program, and the result is stored in the memory 4. The I / O means 2 is a keyboard, a CRT display, a magnetic disk, a floppy disk drive, a CD-ROM drive, a network I / F, and the like. The keyboard and CRT display are used by the operator to operate the computer system. The magnetic disk is used to store various data as a file for a long term or temporarily. The floppy disk drive is used for reading and writing a floppy disk, and its main purpose is to load a program for initializing the system and diagnosing a failure. CD-RO
The M drive is used to read a CD-ROM, and is used to install various application programs and the like.

The memory 4 is a main memory of the computer system. The PDL interpreter 10 is stored in the memory 4 in the form of a program. The drawing information generating means 11, the overlap detecting means 12, and the decoding order determining means 13 are also stored in the memory 4 in the form of a program. These are CP
Performed by U1.

The image information described in PDL is received using the network I / F and stored in the magnetic disk. It is read from the magnetic disk and stored in the memory 4. The interpreter 10 interprets and executes the PDL description on the memory 4. The interpreter 10 gives a drawing command to the drawing information generating means 11 as a result of the execution. The drawing information generating means 11 converts various drawing commands into drawing information of the resolution of the device space. The rendering command of the font, graphics, and scanned image is converted into segment information along the scanning lines of the device space using the technology disclosed in Japanese Patent Application Laid-Open No. 5-224637 and stored in the memory 4 as the rendering information 16. . In the present embodiment, unlike Japanese Patent Application Laid-Open No. 5-224637, processing of a circumscribed rectangle of a scanned image is performed, but processing of the scanned image itself is not performed here.

The overlap detecting means 12 reads the drawing information 16 stored in the memory 4, detects the overlap between the outline information of the scanned image and the partial image, and stores the overlap information 14 for each partial image in the memory 4. . The details of the overlap detection will be described later.

The decoding order determining means 13 reads the overlapping information 14 stored in the memory 4, determines the decoding order when decoding the codes of the partial images, and stores the decoding order information 15 in the memory 4. The details of the determination of the decoding order will be described later.

The image data of the scanned image is input using the network I / F, and is temporarily stored on the magnetic disk. It is read from the magnetic disk and provided to the image input means 20 via the bus 3. The image input means 20 is connected to the reduction means 21 and the row buffer 24. The row buffer means 24 is further connected to the dividing means 22. The output of the dividing unit 22 is configured to be supplied to the encoding unit 23. The code 17 of the partial image output from the encoding means 23 is stored in the memory 4. The reduction unit 21 reduces the size of the raster image when writing the raster image into the row buffer 24. The encoding unit 23 encodes only the partial image to be encoded with reference to the overlap information 14 stored in the memory 4 at the time of encoding.

The decoding means 25 inputs the code 17 of the partial image stored in the memory 4 via the bus 3 based on the decoding order information 15 stored in the memory 4, decodes the code, and decodes the partial image. And store it in memory 28.

The coordinate conversion means 26 inputs the segment information relating to the scanned image of the drawing information 16 stored in the memory 4 and converts the coordinates of the pixels on the segment expressed in the device space into the line segments in the source space. Convert to the coordinates of the upper pixel. The segment information related to the line art is stored in a coordinate conversion unit 26, an address conversion unit 27, and a memory 2.
8 and is supplied directly to the image output means 29. The coordinate information of the source space, which is the output of the coordinate conversion means 26, is supplied to the address conversion means 27. Address conversion means 27
Converts the coordinate information of the source space into the address of the corresponding pixel of the corresponding partial image on the memory 28, and sends the address to the memory means 28. The memory means 28 reads out the pixels of the partial image on the memory at the address given from the address conversion means 27 and outputs the read out pixels to the image output means 2.
9. The image output means 29 generates a line art pixel from the line art segment information and combines it with the scanned image pixel to produce an IOT as an output image.
(Image Output Terminal: image output device).

Next, each means of the first embodiment will be described in more detail.

The drawing information generating means 11 converts the fonts, graphics, contours of the scanned image, etc. specified by the interpreter 10 into a shape at the resolution of the device space, and expresses them as segments on the scanning lines of the device space. The drawing information generating unit 11 of the embodiment expresses all segments on all the scanning lines of the device image using a structure similar to the data structure described in the related art, and stores it as the drawing information 16 in the memory 4. In the present embodiment, the generation of the drawing information is performed by the same technology as the technology disclosed in Japanese Patent Application Laid-Open No. 5-224637.

As a result, for example, the drawing information 16 relating to the scanning line Y1 of the device image shown in FIG. 3 is expressed in the form illustrated in FIG. All scan lines are in the array devImag
It is accessible from e []. Array devImage
[] Has elements of the number of scanning lines HD, and each array element is a pointer to a node of the left end segment of each scanning line. When scanning with respect to the scanning line Y1, first, devImage
[Y1] is read, and a pointer to the node of the segment at the left end of the scanning line is obtained. Next, the node of the leftmost segment is obtained using the pointer. The color of the left end segment Seg1 whose X coordinate is from 0 to X1-1 is white of the line art, the pointer pp in the node indicates a white pixel, and dp
Indicates 0, and next indicates the node of the segment on the right. The second segment Seg2 from the left is a part of the character "A", the X coordinate is from X1 to X2-1, derived from line art, and the color is gray. Third segment S from the left
eg3 occupies the X coordinates X2 to X3-1 and the character "A"
The color is white in the linerat in the background part of. The fourth segment Seg4 from the left occupies the X coordinates X3 to X4-1, is part of the character "A", and is line-latched and gray in color. The fifth segment Seg5 from the left occupies the X coordinates X4 to X5-1 and is a line rate and white in color. The sixth segment Seg6 from the left is from X coordinate X5 to X6
-1 and derived from scanned images. The seventh segment Seg7 from the left is the rightmost segment, occupies the X coordinate X6 to WD-1, and is a line rate and white in color. The drawing information 16 includes information on each segment, that is, the X coordinate values of the left end and the right end of the segment (x0 respectively).
X1), a pointer pp to the color information of the segment, a flag dp indicating that the segment is derived from line art or a scanned image, and a pointer next to the node of the segment on the right side are stored in the node of the segment. I have. In the related art, the pointer pp is a pointer to pixel data, but in the embodiment, pp is a pointer to pixel data in a line art segment and a pointer to a table described later in a scanned image segment. Segment Seg1, Seg3, Seg
Since 5, Seg7 is a white segment derived from line art, pp of each node has a pointer to an area for storing data of white pixel values, and 0 is entered in dp.
Segments Seg2 and Seg4 are gray segments derived from Rheinrad, so each node pp has a pointer to an area for storing gray pixel values, and dp
Is 0. The segment Seg6 is a segment derived from the scanned image. A pointer to a table of pointers to partial images stored in the memory 28 is stored in pp, and 1 is set in dp to indicate a segment of the scanned image. Is done. Right end segment Seg7
Is set to NULL for next.

The scanned image portion of the device image is obtained by affine transforming a 512 × 512 pixel square source image abcd of FIG. 5 to obtain a parallelogram ABCD on the device space as shown in FIG. Rectangle E
Clipping is performed by FGH, and the inside is drawn on a device image.

The source image abcd can be divided into 8 × 8 partial images. When the partial image is mapped to the device space, it becomes an 8 × 8 parallelogram shown in FIG.

If the source image can be divided into Bx × By partial images, the overlap information 14 is Bx × By as shown in FIG.
It is configured as a table having × By elements and stored in the memory 4. An entry in the table stores a logical value of 1 (true) or 0 (false).

The overlap detecting means 12 first sets the overlap information 1
All entries in the table No. 4 are set to 0. Thereafter, the overlap detecting means 12 reads out the outline information of the scanned image from the drawing information 16 stored in the memory 4 and performs an inverse transformation of the affine transformation designated when drawing the scanned image, thereby obtaining the outline. Map the information into the source space of the scanned image. Pixels that contribute to rendering the scanned image portion of the device image are inside the inversely transformed contour shape. Therefore, only a partial image existing inside the inversely transformed outer shape or a partial image existing on the contour contributes to the drawing of the device image. Therefore, the overlap detecting means 12 may select such a partial image. Selection of a partial image is performed as follows. The segments of the scanned image in the drawing information 16 are sequentially read, and the segments are inversely transformed and mapped to the source space. Since the segment is a rectangle having a width of X1-X0 and a height of 1 in the device space, it becomes a parallelogram in the source space when inversely transformed. Find the partial image that overlaps this parallelogram. This is equivalent to drawing a parallelogram at the resolution of the partial image, that is, converting the resolution of the parallelogram with the accuracy of the partial image. Many techniques are known for resolution conversion of figures.
For example, James D. Foley and Andries
A textbook co-authored by Van Dam "Computer
Representative techniques are described in Chapter 11 of "Graphics". In the present embodiment, resolution conversion is performed using the scan line algorithm described in section 11.7. As a result of the resolution conversion, a partial image overlapping with the parallelogram is detected. FIG. 8 shows, in gray, a partial image that overlaps with the inversely transformed contour shape efgh in the partial image of the source image in FIG. The elongated parallelogram is the inverse of a segment in device space. The overlap with the partial image may be detected for each parallelogram of the segment, and the union of the overlapping partial images may be obtained. The overlap detection means 12
In the table of the overlapping information 14, "1" is written in the entry corresponding to the detected partial image. The overlap detecting means 12 performs the above processing on the segments of the drawing information 16 derived from all the scanned images. After the processing is completed, 1 is written in the overlap information 14 in the entries of all the partial images that contribute to the device image. FIG. 9 shows an example of the overlap information 14 when the affine transformation and clipping are performed on the source image of FIG. 5 to obtain the device image of FIG.

The decoding order determining means 13 first selects, from among the four vertices of the partial image, the vertex having the minimum Y coordinate value when converted to the device space, and sets it as the representative point of the partial image. The decoding order determining means 13 determines the coordinates (64 ·) of the representative point for all partial images (xB, yB) contributing to the drawing of the device image from the overlap information 14 stored in the memory 4.
xB + xoff, 64 · yB + yoff) is affine-transformed, and the Y coordinate value Y (xB, yB) and the partial image number (x
B, yB). Here, xoff and yoff are given as follows.

[0096]

[Table 1]

Next, the values of Y (xB, yB) of each partial image are sorted in ascending order, and the result is stored in the memory 4 as decoding order information 15.

The above process will be described by taking as an example a case where the source image shown in FIG. 5 is subjected to affine transformation and clipping and is drawn on a device image as shown in FIG. In this example, the upper left vertex of the partial image is a representative point of the partial image. Therefore, the Y coordinate value Y (xB, yB) of the representative point after affine transformation is

[0099]

## EQU12 ## Y (xB, yB) = 64.c.xB + 64.
dy · B + v. Here, c, d, and v are affine transformation parameters.

The partial images contributing to the drawing of the scanned image of the device image are the parts shown in gray in FIG. 8, and their Y (xB, yB) are calculated, and the order of the partial images when they are arranged in ascending order Are (2,0), (1,1),
(0,2), (3,0), (2,1), (1,2),
(0,3),. . . . . Becomes Decoding order determining means 13
Stores the value of Y (xB, yB) and the partial image number (xB, yB) in the memory 4 as the decoding order information 15 in the form shown in FIG.

The scanning at the time of outputting the device image starts from the scanning line of Y = 0, and is performed until the value of Y is increased by one and reaches HD-1. Therefore, in scanning at the time of output, the first point where the partial image contributing to the device image intersects the scanning line is a representative point of the partial image. Further, Y (xB, yB) appears on the scanning line in order from the partial image having a small value. Accordingly, the codes of the partial images are decoded and returned to the partial images in the order sorted in ascending order by the Y (xB, yB) values of the representative points of the partial images,
Control is performed so that the partial image is restored before scanning the scanning line Y. Thus, the scanning load of the scanning line Y can immediately obtain the pixels of the scanned image. In the example of FIG. 10, the scanning line Y in the device space is set to 0.
When scanning in order from, the code of the partial image (1, 1) is decoded before Y = Y (1, 1). Y = Y (0,
The partial image (0, 2) is decoded by 2). Similarly, the partial images (3, 0), (2, 1), (1, 2),
(0,3),. . . . Respectively, Y = Y (xB, yB)
Before decryption. Thus, Y (xB, y
By decoding the codes of the partial images in the order sorted in B), it becomes possible to prepare the partial images by the time of scanning the device image.

When the input image data is encoded data, the image input means 20 decodes the code of the image to form raster data, and supplies the pixels to the reduction means in the order of scanning. In the embodiment, a decoder for a JPEG code which is often used for compression of a scanned image is provided.

The size of the source image is assumed to be width WS and height HS. The size of the reduced source image is defined as width Wi and height Hi.
And The reduction ratio of the image in the x-axis direction is nx, and the reduction ratio of the image in the y-axis direction is ny. When nx is 3, the image is reduced to 1/3 in the x-axis direction. When ny is 2, the image is reduced to half the size in the y-axis direction.

The reducing means 21, the dividing means 22, and the row buffer 24 are connected to each other, and they are collectively shown in FIG. The row buffer 24 is composed of a RAM, and writes an input pixel at a memory position of a write address generated by the reduction unit 21. Writing is reduction means 2
1 is controlled by the write enable signal WE generated in step S1. The read address is supplied from the dividing unit 22 to the RAM, the pixel is output, and the pixel is sent to the encoding unit 23. The row buffer can store 64 scan lines of the reduced source image. 512K in total in the embodiment
A × 4 byte SRAM is used, and the length of one row is a maximum of 8K (8192) pixels. One pixel can support up to four color components in four bytes.

The reducing means 21 supplies x of the pixel of the source image.
XS counter 210 for counting coordinate positions, yS counter 211 for counting y coordinate positions, nx counter 2
12, an ny counter 213, an xi counter 214 for counting the x coordinate position of the reduced source image, and a yi counter 21 for counting the y coordinate position of the reduced source image
5, an AND gate 216 and an address generator 217 are provided.

The operation of the reduction means 21 will be described with reference to the timing chart of the operation of the reduction means shown in FIG.

The xs counter 210 increases by one from 0 to WS-1 each time a pixel is input. When a new pixel is input when the value reaches WS-1, the value returns to 0. This means that one line of the source image has been input, and the end of the input of one line is notified to the yS counter 211 and the ny counter.

The yS counter 211 increases by one from 0 to HS-1 each time one line of the source image is input. H
When the input of one line is completed at S-1, the process returns to 0. This means that the input of the source image has been completed.

The nx counter 212 counts up from 0 to nx-1 each time one pixel is input, and when it reaches nx-1, returns to 0 again with pixel input. nx counter value is 0
Indicates that the xi counter 214 and the AND gate 2
16 is notified. The nx counter indicates the timing of thinning out pixels when the source image is reduced in the x direction. When the value of the nx counter is other than 0, pixels are thinned out. For example, nx =
In the case of 2, when the nx counter is 1, pixels are thinned out. Therefore, the source image is reduced by half in the x-axis direction. nx = 3
In this case, when the nx counter is 1 or 2, pixels are thinned out. As a result, the source image is reduced to 1/3 in the x-axis direction. When the reduction of the source image is not performed, 1 is set as nx. In this case, since the nx counter always keeps 0, no pixel thinning in the x-axis direction occurs, and no reduction in the x-axis direction of the source image occurs.

The xi counter 214 increases by one from 0 to Wi-1 every time the nx counter = 0 is notified. Wi-
When the notification of nx counter = 0 is received at the time of 1, it returns to 0.
This means that one line of the reduced source image has been completed, and this is notified to the address generator 217.

The ny counter 213 counts up from 0 to ny-1 every time one line of the source image is input.
When it reaches -1, it returns to 0 again by the notification of the input of one line of the source image. When the value of the ny counter indicates 0, it is notified to the yi counter 215 and the AND gate 216. The ny counter indicates the timing of thinning out pixels when the source image is reduced in the y direction. When the value of the ny counter is other than 0, pixels are thinned out. For example, when ny = 2, the ny counter is 1
At this time, the scanning lines are thinned out. Therefore, the source image is reduced by half in the y-axis direction. When ny = 3, the ny counter is 1
In the case of ２2, the scanning lines are thinned out. Thereby, the source image is reduced to 1/3 in the y-axis direction. When the source image is not reduced, 1 is set as ny. In this case, since the ny counter always keeps 0, no thinning of the scanning lines in the y-axis direction occurs, and no reduction of the source image in the y-axis direction occurs.

The yi counter 214 increases by one from 0 to Hi-1 every time the ny counter = 0 is notified. Hi-
When the notification of the ny counter = 0 is received at the time of 1, it returns to 0.
This means that the input of the source image has been completed. The yi counter 214 also detects completion of input every 64 lines. Completion of input every 64 lines and completion of input of source image
2 is notified.

The AND gate 216 detects the condition of nx counter = 0 and ny counter = 0. When this condition is true, the input pixel is a pixel that is not thinned out in any of the x and y directions. Therefore, the output of the AND gate 216 is used as the write enable signal WE to the RAM of the row buffer 24.
Supply as The RAM writes the input pixel at this time based on the WE signal. The write destination address at that time will be described in detail below.

The address generator 217 has the xi counter 2
Using the value of 14 and the value of the yi counter 215, an address is generated as shown below.

[0115]

## EQU13 ## Write address = 8192 × (value of yi counter% 64) + value of xi counter

Here, "%" means an operation for taking a remainder. Continuous 8K words in the RAM of the row buffer are fixedly assigned to one row of the reduced source image. FIG. 14 schematically shows pixel assignment in the row buffer RAM.
The first 8192 words of the RAM contain the first, 65th, 129th, 193rd,. . . Is stored. The second and 66th lines are stored in the next 8192 words. Similarly, the 64th line, the 128th line, etc.
Stored in the last 8192 words of M. Therefore, as can be seen from FIG. 14, a partial image for one horizontal row is stored in the RAM of the row buffer.

The dividing means 22 is provided with an address generator 220, an xB counter 221 and a yB counter 222.

The address generator is activated upon receiving notification of the completion of the input of the 64 rows of the yi counter 214, and generates a pixel address of the RAM of the row buffer. The generated address is supplied to the RAM, the pixel is read from the RAM, and sent to the encoding unit 23 as an output pixel. The reading of the pixels is controlled so as to be synchronized by the pixel output strobe signal supplied from the encoding means 23. The pixel strobe signal is configured to be provided to the address generator 220, which updates the pixel read address only when the pixel strobe signal is asserted. The address generator 220 moves the partial image stored in the RAM from left to right (see FIG. 14) and, for the partial image, 64 64 × 8 pixel blocks in the partial image as shown in FIG.
The addresses are generated such that the pixels in the 8 × 8 pixel block are read in the order shown in FIG. That is, the read address is

[0119]

## EQU14 ## Read address = 64 × B + Offset
1 (x ′, y ′) + Offset2 (x ″, y ″).

Here, xB is the number of the partial image in the x coordinate direction, x 'and y' are the block numbers of the 8 × 8 pixel block in the x and y coordinate directions, and x ″ and y ″ are 8 × 8. If the coordinate position is within the pixel block, Offse
t1 (x ′, y ′) and Offset2 (x ″, y ″) are respectively

[0121]

15] Offset1 (x ′, y ′) = 65536y ′ + 8
x ′ Offset2 (x ″, y ″) = 8192y ″ + x ″.

When the control algorithm of the variables xB, x ', y', x ", y" is described in C language style, the following is obtained.

[0123]

(Equation 16)

By reading out the pixels in such an order, the pixels in the partial image can be converted into raster blocks for the encoding means 23 described later and read out.

The xB counter 221 is a yi counter 214
Is cleared to 0 by the completion notification of the input of 64 lines. The xB counter 221 counts up xB. Each time 64 × 64 pixels in the partial image are read, the value of xB increases by one. The value of xB is incremented from 0 to a value one smaller than the number Bx of partial images on one scanning line of the reduced source image. Lastly, when xB = Bx, it notifies the yB counter 222 that the output of the partial image for one horizontal row has been completed. When xB = Bx, no read address is generated. After that, the completion of the input of 64 lines of the yi counter 214 is notified and cleared to zero.

The yB counter 222 is cleared to 0 when a source image is input, and increments the value by +1 each time the xB counter 221 notifies that a partial image for one row has been output.

As shown in FIG. 16, partial images are arranged so as to coincide with each other using the upper left of the reduced source image as the origin. The partial image is arranged so as to cover the reduced source image. That is, Bx is a minimum integer satisfying Wi-1 <64Bx. Similarly, By is a minimum integer satisfying Hi-1 <64By. The partial image is cut out first in the horizontal direction from the partial image at the upper left corner. When the partial image is reached to the right end, the partial image one line below is cut out in the same manner, and thereafter the same is performed to the last line.

The xB counter and the yB counter indicate the coordinate numbers of the partial images (xB, yB), and are sent to the encoding means 23 together with the output pixels.

[0129] The encoding means 23 uses JPEG (Joint).
Photographic Expert Grou
Use the baseline process algorithm in p). This algorithm divides an image into blocks of 8 × 8 pixels, subjects the blocks to discrete cosine transform, and then performs quantization and Huffman coding. The details of the algorithm and the implementation are described in, for example, the monthly magazine interface published by CQ Publishing, December 1991, pages 160 to 182, and the description is omitted here. JP
EG is a standard compression / decompression algorithm for scanned images.
It can be reduced to zero. The pixels read from the row buffer 24 by the dividing means 22 in the order shown in FIG. 15 are input to the encoding means 13. The encoding means performs discrete cosine transform, quantization, and Huffman encoding in units of 8 × 8 pixel blocks. The code output is written to the memory 4. As shown in FIG. 17, the coordinate numbers (xB, y
A table B) is provided. The code is stored in a data structure of a linked list structure including a link part and a code storage unit. The link part of this data structure stores a pointer to the next node in 4 bytes. NULL is stored in the link part of the terminal node as a mark indicating the terminal. The code storage is 60 bytes. Codes that cannot be stored in the code storage unit of one node are stored in the code storage unit of the next node indicated by the link unit. There may be unused portions in the sign storage of the terminal node. EOC at the end of the partial image code to indicate the end of the code
(End Of Code) code is entered. Encoding means 2
Reference numeral 3 operates as follows when codes of the partial image (xB, yB) are generated, and stores the codes in the memory 4.

1) First, one unused node is taken out and its address is stored in the table at the location (xB, yB)
To be stored. 2) Codes are sequentially written to the code storage of the node. 3) If the EOC code is rewritten in the code storage unit, NULL is written in the link part of the node and the partial image (x
(B, yB) is completed. 4) If the code storage unit becomes full before the EOC code can be rewritten, one new unused node is taken out, its address is written into the link part of the current node, and thereafter, the process goes to step 2) for the new node and the processing is performed. repeat.

By doing so, the variable length code can be efficiently stored in the memory 4 and the code of the partial image can be easily read.

The encoding means 23 further outputs the partial image (x
When encoding (B, yB), the table of the overlap information 14 (see FIG. 7) stored in the memory 4 is referred to, and (x, yB) is referred to.
Encoding is performed only when the element corresponding to (B, yB) is 1, that is, when the element is logically true. In this case, NULL indicating that there is no code is written in the corresponding portion of the table shown in FIG.

The decoding means 25 refers to the scanning line number Y and reads out the partial image number (xB, yB) related to the scanning line in the decoding order information 15 stored in the memory 4. Table 17 of the partial image stored in the memory 4 (FIG. 1)
7), the combined list structure of the codes of the partial images is accessed using (xB, yB). The code is read from the code storage of the node part of the linked list structure,
Supply the code to the decoder for the baseline algorithm. If the link part of the node is NULL, after supplying 60 bytes of the code storage part to the decoder, decoding of the code of the partial image is finished. If the node part is not NULL, after supplying all 60 bytes of the code storage part to the decoder, lin
The same processing is performed for the next node by following the k section. l
When the “ink” part is NULL, the decoder finds the EOC code in the middle of decoding 60 bytes for storing the code. The decoder discards the data after the EOC code. The decoding means 25 is 64
The pixels of the partial image of x64 pixels are obtained and stored in the memory 28.

FIG. 18 shows the structure of the coordinate conversion means 26.
As shown in FIG. 18, the coordinate conversion means 26 includes four multipliers 2601, 602, 2603, and 2604 and six adders 2605, 2606, 2607, 2608, and 261.
3, 2614 and two selectors 2609, 2610
, Two registers 2611 and 2612, and a subtractor 26
15, a down counter 2616, and a control circuit 2617
And The coordinate transformation means 26 receives parameters (a ', b', c ', d', u ', v') for inverse transformation, that is, coordinate transformation from the device space to the source space.
These parameters are calculated by the interpreter 10 from the affine transformation parameters and supplied to the coordinate transformation means 26.
The coordinate conversion means 26 further calculates the Y coordinate value Y of the segment,
A left end X coordinate value X0 and a right end X coordinate value X1 of the segment are input.

Multipliers 2601 and 2602 and adder 260
5, 2607 are connected as shown in FIG. 11, and by using these,

[0136]

X0 = a'.X0 + b'.Y + u 'is obtained.

The multipliers 2603 and 2604 and the adders 2606 and 2608 are connected as shown in FIG.

[0138]

## EQU18 ## y0 = c'.X0 + d'.Y + v 'is obtained. (X0, y0) is the left end point (X
(0, Y) are transformed back into the source space.

When the left end point (X0, Y) of the segment is input and (x0, y0) is calculated, the control circuit 2617 controls the selectors 2609 and 2610 to control x0 and y0.
Is loaded into the registers 2611 and 2612, respectively. The register 2611 holds the x-coordinate of the source space after the coordinate conversion, and the register 2612 holds the y-coordinate of the source space after the coordinate conversion. 1 to the right in device space
The movement of the pixel, that is, the movement of the vector (1, 0) corresponds to the movement of the vector (a ′, c ′) in the source space.
Therefore, the x-coordinate value of the next pixel is added by adding the value of the register 2611 and a 'using the adder 2613, and the value of the register 2612 and' are added by using the adder 2614 to obtain the next pixel. Coordinate values can be obtained.

The subtractor 2615 inputs X1 and X0, obtains the difference between the X coordinate values at both ends of the segment, obtains information X1-X0 regarding the segment length, and supplies it to the down counter 2616. The down counter 2616 checks the value, and if the value is 0
While the value is larger, the value of the counter is decremented by one, and when it is 0, 1 is output to the signal zero and the value is kept at 0. The down counter 2616 is used to control repetition for the number of pixels on the segment. Signal zero = 1
Means that the right end pixel of the segment is being processed, and the control circuit generates a control signal so that the processing stops generating x and y until data of a new segment is input.

The coordinate conversion means 26 receives the scanning line number Y which increases by one from 0 to HD-1, and obtains the segment information related to the scanning line from the drawing information 16 stored in the memory 4 for each scanning line. Are sequentially read from the leftmost segment of the scanning line to the rightmost segment. The segment information on the scanning line is represented by a data structure in a linked list format as described above, and is linked from the left segment to the right segment by a pointer. The array devImage is an array accessed using a scan line number as an index, and each element stores a pointer to a node associated with the leftmost segment of the scan line. The coordinate conversion means of the segment on the scanning line operates in the following procedure.

1. DevImag using scan line number Y
e [Y] is read to obtain the address of the node of the leftmost segment.

[0143] 2. The contents of the node are read using the address of the node. Thus, a left end X coordinate X0, a right end X coordinate X1, a pointer pp, a flag dp, and a pointer next to a node on the right side are obtained.

[0144] 3. If the flag dp is 0, the node is a line art node. The memory 4 is accessed by the pointer pp to obtain the pixel value P, and the data set (X1
−X0 + 1, P) is supplied to the image output means 29. X1
-X0 + 1 is the segment length.

If the flag dp is not 0, the node is a node of a scanned image. Therefore, the X1-X0 + 1 coordinate values converted from the device space coordinates into the source space coordinates by the means described above are used as the address conversion means 27. And the value of the pointer pp is also supplied to the address conversion means 27.

[0146] 4. Check the pointer next. NUL
If L, there is no segment on the right side, so the process ends.
If it is not NULL, the value of netxt is set as the address of the new node, and the process proceeds to the processing step 2.

After the coordinate conversion of the segment on one scanning line is completed, the coordinate conversion means 26 waits for the instruction of the coordinate conversion of the segment for the next scanning line by the scanning line signal Y.

The memory 28 stores a partial image that overlaps the scanning line being output of the device image. As shown in FIG. 19, the memory 28 further stores the coordinates (xB, y
An address conversion table 280 for linking B) with the address where the partial image is stored is stored. The address conversion table 280 is a table accessed using xB and yB, and stores the address of the partial image (xB, yB) stored in the memory 28. The address conversion unit 27 inputs the value of the pointer pp and the coordinate value (x, y) in the source space after the coordinate conversion for each pixel in the device space from the coordinate conversion unit 26. The partial image (xB, yB) to which the pixel belongs from the coordinates (x, y) of the pixel
Is easy to determine. The quotients may be xB and yB by dividing x and y by 64, respectively. The coordinate position (xoffset, yoffset) of the pixel in the partial image is x, y
Xoffset, the remainder when each is divided by 64,
yoffset. Specifically, the lower 6 bits of x
Is xoffset, and the remaining upper bits are xB. Similarly, the lower 6 bits of y are set to yoffset, and the remaining upper bits are set to yB.

The drawing information generating means 11 operates to store the address of the address conversion table 280 in the pointer pp of the node of the segment of the scanned image. Therefore, the address conversion means 27 knows the location of the address conversion table in the memory 28 using the pointer pp passed by the coordinate conversion means. (XB, y) obtained from (x, y)
The entry of the address conversion table is read using B), and the base address of the partial image in the memory 28 is obtained. Base address and (xoffset, yoffs
et) to determine the address of the pixel, and
Is read out. The read pixels are sent to the image output means 29.

FIG. 19 shows that the segments of the scanned image on the scanning line Y are the partial images (0, 2), (1, 2),
The contents of the memory 28 when passing through (1, 1), (2, 1), and (2, 0) are schematically shown.

If the segment is derived from a scanned image, the image output means 29 outputs the pixels read from the memory 28 by the address conversion means 28 as they are. If the segment is derived from line art, the pixel information P obtained from the image conversion means 26 and the length L of the segment
Is used to output the pixel value P L times. Image output means 29
, The pixels of the device image are output in the raster scan order, and the output pixels are sent to the IOT to form an image on paper or a CRT.

Here, the use of the reducing means 21 will be described again. Assume a source image as shown in FIG. For the sake of explanation, this source image has a size of 8 × 8 pixels. It is assumed that the source image is drawn on the device image by performing a rotation of −45 ° and reducing 1 / (2√2) in both the x and y directions. The straight line obtained by inversely converting the scanning line in the device space at that time is the oblique straight line in FIG. 21A. The black points on the straight line are the positions of the pixels in the device space, that is, the places where the segments of the device image are inversely transformed and the pixels of the source image are sampled at the time of inverse sampling. When the reduction ratio is larger than 1/2 as in this example, only pixels at discrete positions on the source image are read. In the example of FIG. 21a, the source image has a total of 64 pixels, but only 8 pixels are sampled and contribute to the formation of the device image. 7/8 of all pixels are useless. When the partial image including many useless pixels is read from the row buffer 24 and encoded by the encoding unit 23 and the code is stored in the memory 4, extra time is required to read from the row buffer 24, and the processing time in the encoding unit 23 Becomes longer and the code size becomes larger, so that the writing time to the memory 4 becomes longer, and a larger area for storing the code 17 of the partial image is required. In addition, the time required to read the code from the memory 4 is increased, and the processing time in the decoding unit 25 is also increased. Further, since the segment of the scanned image on the scanning line overlaps with more partial images, more partial images must be stored in the memory 28 and the size of the memory 28 must be increased. That is, there is a problem that the memory size increases and the cost increases, and a problem that the processing time increases. This problem becomes more serious as the reduction ratio of the affine transformation increases.

The reduction means 21 is used when the reduction ratio of the affine transformation is large. FIG. 21B shows that nx =
2, ny = 2 is set, and the reduced source obtained by reducing the source image of FIG. 21A to １ ／ in the x direction and に in the y direction is an image. When the reduction is performed by the reduction unit 21, the interpreter 10 and the drawing information generation unit 11 consider the reduction by the reduction unit 21 and create the drawing information 16 and the like as if the reduced source image is regarded as a source image. Conversion means 2
6, the inverse transformation parameters (a ′, b ′, c ′,
d ', u', v ') are determined. In the reduced image of FIG. 21B, eight pixels out of a total of sixteen pixels contribute to drawing of the device image. Therefore, as compared with the case where the source image is not reduced, the processing time can be reduced, and the memory area for storing codes and partial images can be reduced.

[Embodiment 2] FIG. 20 shows a block diagram of the second embodiment. In the present embodiment, a raster image input by an IIT (image input device) is rotated by 0 ° or 90 ° to enlarge /
This is implemented in a device (copier) for reducing and outputting to the IOT. This embodiment is similar to the first embodiment, but
The input image is directly supplied to the image input means 20. Also,
In the memory 4, the drawing information generating means 11 and the code order determining means 1
3 are stored. When the CPU executes the former program, the drawing information 16 is stored in the memory 4. When CPU1 executes the latter program,
Decoding order information 15 is created and stored in the memory 4.

The enlargement / reduction ratio and the rotation angle are designated by buttons on the panel of the copying machine. These information are stored in the I / O means 2
Enter through.

The drawing information generating means 11 calculates the shape of the output image based on the enlargement / reduction ratio and the rotation angle, creates segment information and stores it as drawing information 16 in the memory 4. Second
In the embodiment, a white region of the upper, lower, left, and right margins and an input scanned image located at the center of the device image are drawn on the device image. Each scanning line in the upper margin and the lower margin has only one white segment having a width of WD. For each scanning line in the other part,
There are three segments, the left end segment is a white segment having a left margin width, the middle segment is a scanned image segment input as an input image, and the right end segment is a white segment having a right margin width. . The drawing information generation unit 11 further calculates the reduction ratios nx and ny of the reduction unit and the inverse conversion parameters (a ′, b ′, c ′, d ′, u ′, v ′) based on the enlargement / reduction ratio and the rotation angle.
Is calculated, nx and ny are set in the reduction means 21, and the inverse transformation parameter is set in the coordinate transformation means 26.

The decoding order determining means 13 determines the decoding order based on the rotation angle. In the case of a rotation of 0 °, Bx partial images (n, 0) (from n = 0 to Bx−1) are first decoded, and then Bx partial images (n, 1) are sequentially arranged between 64 lines.
(N = 0 to Bx−1), partial image (n, 2) (n
= 0 to Bx−1), partial image (n, 3) (n = 0)
To Bx-1), and finally, the partial image (n,
By-1) (n = 0 to Bx-1) is decoded, and the above order and scanning line number are stored in the memory means 4 as decoding order information 15. For a 90 ° rotation, first B
y partial images (Bx-1, n) (n = 0 to By-1
), And then sequentially by-line the By partial images (Bx−2, n) (n = 0 to By−1) and the partial images (Bx−3, n) (n = 0 to By-1
), Partial image (Bx−4, n) (n = 0 to By−
1), and finally, the partial image (0, n) (n =
(From 0 to By-1), the above order and the scanning line number are stored in the memory means 4 as decoding order information 15.

The raster data generated by scanning the original in the IIT is supplied to the image input means 20 as an input image. The image input unit 20 supplies the input image data to the reduction unit 21. The reducing means 21, the row buffer 24 and the dividing means 22 operate in the same manner as described in the first embodiment,
The partial image is cut out and pixels are sequentially supplied to the encoding unit 23.

The encoding means 23 encodes the partial image unconditionally and stores the code 17 of the partial image in the memory 4. Since most of the input scanned images are output in a copying machine, almost no partial image can be omitted even if the partial image is selectively encoded. Therefore, the encoding means 23 of the second embodiment does not perform selective encoding. The encoding algorithm and the method of writing the code in the memory 4 are the same as those described in the first embodiment.

The decoding means 25, the coordinate conversion means 26, the address conversion means 27, the memory 28, and the image output means 29
This embodiment has the same configuration as that of the first embodiment, and operates in the same manner as the first embodiment. That is, the decoding order information 15 is read, the code of the partial image is decoded in synchronization with the output scanning line number Y of the device image, and stored in the memory 28. At the same time, scanning line number Y
Is read from the drawing information 16, the segment is converted to pixel coordinates in the source space by the coordinate conversion means 27, the pixel coordinates are converted to the address of the memory 28 by the address conversion means 27, and the address is The pixels of the partial image stored in the memory 28 are read and supplied to the image output means 29, and output to the IOT as an output image.

[Embodiment 3] In the third embodiment, an address conversion table is provided in the memory 28 for each source image as shown in FIG. The segment on the scanning line Y1 in FIG. 24 is stored in the memory 4 as drawing information in a form as illustrated in FIG.

FIG. 26 shows a block diagram of the coordinate conversion means 26 of the third embodiment. New CAM (Content
Address Memory) means 2618 is provided. The drawing information 16 is input to the input of the CAM unit 2618.
Pp value (address of the address conversion table) of the segment node read from the
18 to the inverse transformation parameters (a ′, b ′, c ′,
d ′, u ′, v ′).
The address of the address conversion table corresponding to the source image is stored in the tag part of the entry of the CAM means, and the inverse conversion parameter is stored in the data part. The CAM unit checks whether the input pp value matches the tag portion of each entry, and outputs the data portion of the matched entry.

The interpreter 10 and the drawing information generating means
The address of the address conversion table and the inverse conversion parameter for each source image are stored in the CAM unit of the coordinate conversion unit 26.

The coordinate conversion means 26 reads the node of the segment, reads the CAM means with the value of pp, and obtains an inverse conversion parameter. Since an address conversion table exists for each source image, the value of pp is unique for each source image. Accordingly, an inverse transformation parameter can be obtained for each source image, and the coordinate transformation means 26 can perform a different inverse transformation for each source image. Source coordinate value obtained by inverse transformation and p
The value of p is passed to the address conversion means 27.

The address conversion means 27 obtains the address of a pixel in the memory 28 using a unique address conversion table for each source image using the value of pp. The method of creating the pixel address has been described in the first embodiment, and a description thereof will be omitted.

[Other Embodiments] In the embodiment described above, the row buffer 24, the memory 4 and the memory 28 are provided. However, in the present invention, these need not be physically separate memory means, One or two memory means may be shared.

In the embodiment described above, the reduction means can perform only integer unit reduction, but the present invention is not limited to this, and the reduction means may be configured to perform reduction at an arbitrary ratio. At that time, the reduction unit, the row buffer, and the division unit can be configured to perform interpolation using adjacent pixels. With this configuration, it is possible to reduce image quality deterioration (for example, jaggy or moiré) due to reduction.

In the embodiment described above, the address conversion means is configured to read out the pixel closest to the coordinate value in the source space obtained by the inverse conversion from the memory 28 and supply it to the image output means. However, the present invention is not limited to this, and a configuration may be adopted in which a pixel value is obtained by complementing a pixel adjacent to a coordinate value in the source space. With this configuration, it is possible to reduce image quality deterioration (for example, jaggy) due to affine transformation.

In the embodiment described above, the drawing information 16 is configured to hold the drawing information as a scanning line segment of the device image, and the coordinate conversion means 26 performs the coordinate conversion of the line segment. However, for example, a trapezoid, rectangle, or triangle parallel to the scanning line may be used for holding the drawing information.

In the embodiment described above, the partial image is a square of size 64 × 64 pixels. However, the present invention is not limited to this, and the square may be a rectangle.
Also, the size may be changed. If the size of the partial image is a power of 2, it is easy to calculate the number of the partial image from the coordinate values in the source space and the pixel position in the partial image. If the size of the partial image is increased, the size of various tables can be reduced, but the area for holding the partial image in the memory 28 increases. On the other hand, when the size of the partial image is reduced, the size of various tables increases, but the area for holding the partial image in the memory 28 decreases. When dealing with an A4-A3 size image of 600 SPI, a partial image of 64 × 64 pixels is preferable in terms of cost and performance.

[0171]

As described above, according to the present invention, rotation, scaling, or more general affine transformation processing of a scanned image, clipping processing using an arbitrary external shape of a scanned image, scanning In the process of overwriting line art on the image,
At the time of inputting the source image, the source image is reduced as necessary, the source image is divided into partial images, and only the partial images that contribute to the drawing of the device image are encoded, thereby reducing and holding the data amount. In the raster scan of the device image, the order of referring to the partial images is determined using inverse sampling, and the codes of the partial images are decoded in accordance with the order while synchronizing with the raster scan. At this time, only the necessary partial images are held as images, and inverse sampling is performed on them to perform affine transformation and output of pixels inside the outline of the scanned image. By doing so, the memory required for processing the scanned image can be significantly reduced, and a low-cost processing device can be obtained. Further, since the transfer time can be reduced by reducing the data amount of the scanned image by encoding, the image processing can be executed at high speed.
Further, since the partial image is encoded once and decoded only once, even if the lossy compression algorithm is used, the deterioration of the image can be minimized.

By synchronizing the decoding timing of the partial image by the decoding means 25 with the timing regarding the scanning line of the coordinate conversion means 26 and the address conversion means 27, the coordinate conversion means 26 and the address conversion means 27 need the partial image. Immediately before, the data can be decoded by the decoding means 25 and stored in the memory 28, so that the size of the area required for storing the partial image in the memory 28 can be minimized, and the cost of the apparatus can be reduced. The decoding means 25, the coordinate conversion means 26 and the address conversion means 27 are configured to be operable simultaneously. Further, when scanning a scanning line during output scanning, a partial image is restored and stored in the memory 28. Therefore, the coordinate conversion means 26 and the address conversion means 2
7, the memory 28 can be read immediately, and the processing can be speeded up.

Since the partial image can be created after the source image has been reduced in advance using the reducing means 21, the number of partial image images can be reduced. This makes it possible to reduce the total amount of codes of the partial images stored in the memory 4. Further, since the number of partial images to be stored in the memory 28 can be reduced, the size of the area required for storing the partial images in the memory 28 can be minimized. These reductions in memory size can reduce the cost of the device. Further, since the total amount of data of the partial image is also reduced, the data transfer time is reduced, and the processing can be sped up.

An address conversion table is stored in the memory 28 for each source image, and a pointer to an address conversion table for a segment of a scanned image in the drawing information 16 is a pointer to an address conversion table related to the segment. I did it. The address conversion means 27 can perform address conversion for each source image. As a result, even when an arbitrary number of source images are simultaneously drawn on a device image, the amount of memory used can be reduced, costs can be reduced, processing can be speeded up, and image degradation can be minimized.

[Brief description of the drawings]

FIG. 1 is a diagram illustrating a flowchart illustrating steps of a process according to a first embodiment of the present invention.

FIG. 2 is a diagram illustrating a block diagram of a first embodiment of the present invention.

FIG. 3 is a diagram illustrating an example of a device image.

FIG. 4 is a diagram showing an internal representation of drawing information of a scanning line Y1 in FIG.

FIG. 5 is a diagram illustrating an example of a source image.

FIG. 6 is a diagram illustrating a relationship between a source image and a device image in a device space.

FIG. 7 is a diagram showing an expression format of overlap information.

FIG. 8 is a diagram showing an overlap between a partial image and a contour shape.

FIG. 9 is a diagram illustrating an example of overlap information.

FIG. 10 is a diagram illustrating the order of decoding.

FIG. 11 is a diagram illustrating an example of decoding order information.

FIG. 12 is a block diagram showing a configuration of a reducing unit, a dividing unit, and a row buffer.

FIG. 13 is a timing chart showing the operation of the reducing means, the dividing means, and the row buffer.

FIG. 14 is a diagram showing addresses in a row buffer and how to use them.

FIG. 15 is a diagram illustrating a reading order of pixels.

FIG. 16 is a diagram showing the cutout order of partial images.

FIG. 17 is a diagram illustrating storage of codes of partial images in a memory.

FIG. 18 is a block diagram of a coordinate conversion unit.

FIG. 19 is a diagram illustrating a relationship between an address conversion table and a partial image.

FIG. 20 is a block diagram of a second embodiment of the present invention.

FIG. 21 is an explanatory diagram of an operation of a reduction unit.

FIG. 22 is an explanatory diagram of affine transformation and inverse transformation.

FIG. 23 is a diagram illustrating a relationship between an address conversion table and a partial image according to the third embodiment.

FIG. 24 is a diagram illustrating an example of a device image.

25 is a diagram showing an internal representation of drawing information of a scanning line Y1 in FIG.

FIG. 26 is a diagram showing an embodiment of the coordinate conversion means in the third embodiment.

[Explanation of symbols]

1 CPU, 2 I / O means, 3 buses, 4 memories,
Reference Signs List 10 interpreter, 11 drawing information generating means, 12
Overlap detection means, 13 decoding order determination means, 14 overlap information, 15 decoding order information, 16 drawing information, 17 divided image code, 20 image input means, 21 reduction means,
22 division means, 23 encoding means, 24 row buffers, 25 decoding means, 26 coordinate conversion means, 27 address conversion means, 28 memory, 29 image output means, 2
601, 602, 2603, 2604 multiplier, 26
05, 2604, 2607, 2608, 2613, 26
14 adder, 2609, 2610 selector, 261
1,612 register, 2615 subtractor, 2616
Down counter, 2617 control circuit

Claims (13)

[Claims] 1. A raster image generating method in a raster image generating apparatus, comprising: an image dividing step of dividing a raster image into a plurality of partial images; and encoding a partial image obtained in the image dividing step to encode the partial image. An encoding step of obtaining a partial image obtained in the encoding step; a decoding order determining step of determining a decoding order of the code of the partial image obtained in the encoding step; and decoding the code of the partial image according to the order determined in the decoding order determining step. A decoding step of storing the partial image in a memory unit; a coordinate space conversion step of converting geometric information expressed in a first coordinate space into a second coordinate space; and a geometric space in the second coordinate space. An address generation step of generating an address on the memory means corresponding to a position; Raster image generation method characterized by a step of reading the memory means by using the dress. 2. The method according to claim 1, wherein the first coordinate space is a device space, the second coordinate space is a source space, and the coordinate space conversion step is a step of converting a drawing geometry of the scanned image in the device space. Inversely converting the raster scan information to be formed into a source space to obtain geometric information in the source space, that is, raster scan information, wherein the address generation step includes a raster scan on the source space obtained in the coordinate space conversion step. Generating address information of the pixels of the partial image on the memory means corresponding to the pixels of the scanned image in the device space by using the information, and sequentially reading the pixels from the memory means using the address information, Claims characterized by having a configuration for sequentially acquiring pixels of a scanned image in space Item 1
2. The raster image generation method according to 1. 3. The method according to claim 1, wherein the raster image generating method further includes an overlap detecting step of checking an overlap between the partial image obtained in the image dividing step and a geometric shape obtained from drawing information input to the raster image generating apparatus. And according to the overlap detection result in the overlap detection step,
A partial image selecting step of selecting a partial image that contributes to drawing of the device image, wherein the encoding step is a step of encoding only the partial image selected in the partial image selecting step to obtain a sign of the partial image. 2. The method according to claim 1, wherein
Or the raster image generation method according to 2. 4. The overlap detecting step reads out outline information of a scanned image from the drawing information, and executes an inverse transformation of an affine transformation designated when the read scanned image is drawn. 4. A step of mapping contour information to a source space of the scanned image and detecting an inner part of the contour of the mapped source space or a region of the partial image overlapping the contour. The described raster image generation method. 5. The reduced raster image generating method further includes a reduced raster image generating step of generating a reduced raster image by performing reduction of the raster image. 5. The raster image generating method according to claim 1, wherein the generated reduced raster image is divided into partial images. 6. A raster image generating apparatus, comprising: an image dividing unit that divides a raster image into a plurality of partial images; an encoding unit that encodes a partial image generated by the image dividing unit to obtain a code of the partial image; Decoding means for decoding the code of the partial image generated by the encoding means and storing it in a memory means; coordinate space converting means for converting geometric information expressed in a first coordinate space into a second coordinate space; Address conversion means for generating an address on the memory means corresponding to a geometric position in the second coordinate space; decoding order determination for determining a decoding order for decoding a code of the partial image generated by the encoding means Means for storing a partial image decoded according to the decoding order determined by the decoding order determining means in the memory means, and storing the geometric information of the first coordinate space in the memory means. Raster image generating apparatus characterized by having the structure of reading the pixels of the stored partial image in the memory means with a memory address given its output obtained by supplying to said address translation means to target conversion means. 7. The first coordinate space is a device space, the second coordinate space is a source space, and the coordinate space conversion means converts a drawing geometric shape of the scanned image on the device space. Means for inversely transforming the raster scan information to be formed into a source space to obtain geometric information in the source space, ie, raster scan information, wherein the address conversion means performs raster scan on the source space obtained by the coordinate space conversion means. Means for generating address information of pixels of the partial image on the memory means corresponding to the pixels of the scanned image in the device space using the information, and sequentially using the address information generated by the address conversion means. Means for reading pixels from the means and sequentially acquiring the pixels of the scanned image in the device space The raster image generating apparatus according to claim 6, wherein: 8. The apparatus according to claim 1, wherein the raster image generating apparatus further includes an overlap detection unit configured to detect an overlap between the partial image generated by the image dividing unit and a geometric shape obtained from drawing information input to the raster image generating apparatus. Means for selecting a partial image that contributes to the rendering of a device image in accordance with the result of the overlap detection by the overlap detection means, and encoding only the selected partial image by the encoding means, The code is obtained.
Or the raster image generating device according to 7. 9. The raster image generating device, comprising: an overlap detecting unit configured to detect an overlap between the partial image generated by the image dividing unit and a geometric shape obtained from drawing information input to the raster image generating unit. Wherein the partial image is selectively read out by the division unit in accordance with an overlap detection result by the overlap detection unit, and the read-out partial image is encoded by the encoding unit. Item 8. The raster image generation device according to item 6 or 7. 10. The overlap detecting unit reads out outline information of a scanned image from the drawing information, and executes an inverse transformation of an affine transformation designated when drawing the read scanned image, 9. The image processing apparatus according to claim 8, wherein contour information is mapped to a source space of the scanned image, and a portion inside the contour of the mapped source space or a region of the partial image overlapping the contour is detected. Or the raster image generating apparatus according to 9. 11. The raster image generating apparatus further includes a reducing unit that generates a reduced raster image by performing reduction of the raster image, and the image dividing unit includes a reduced raster image generated by the reducing unit. 11. The raster image generating apparatus according to claim 6, wherein the image is divided into partial images. 12. In the raster image generating apparatus, a decoding timing position of a partial image executed by using the decoding means and a conversion timing position of a first coordinate space where conversion is executed by the coordinate conversion means are determined. 12. The raster image generating apparatus according to claim 6, wherein the raster image generating apparatus operates synchronously. 13. The raster image generating apparatus, wherein the address conversion means has a table for associating a second coordinate space with a memory address, and the table is constituted by an independent table for each input raster image. The raster image generating apparatus according to claim 6, wherein: