JP2000301782A - Method for computer mounting for executing approximation of gray scale gradation using image forming apparatus in more limited range and printer using the same - Google Patents

Abstract

PROBLEM TO BE SOLVED: To reduce an operation time by alleviating a condition necessary for a memory in terms of a method and a printer wherein a gray scale gradation is approximated using an image forming apparatus in a more limited range. SOLUTION: This printer executes rendering of an object represented by a page description language in scanning of an image forming apparatus (401) and determines based on the rendering an image region having the object subjected to the rendering. At that time, bounding boxes 403, 405 that surround all of the objects subjected to the rendering are determined, then the image region is determined. Input pixels in the image region are subjected to screening (407), but ones outside thereof are not. Thus, the necessary or unnecessary of the screening is discriminated so that a time period required for the screening can be reduced and each row of preference matrix is divided into segments so that use of a memory is improved.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The technical field to which the invention pertains relates to printers, and more specifically to printer electronics for converting input data in page description file format into control signals for a print engine.

[0002]

2. Description of the Related Art Screening is a process of giving the illusion of a continuous tone image on a display on which only digital pixels can be drawn. In the image printing process, a large number of gray levels of the input image must be simulated by the printing device to reproduce a perfect reproduction of the original. However, in a printed image, the pixel resolution may be limited to what is visually perceptible.
Therefore, by grouping adjacent pixels, it is possible to simulate continuous tone in an image.

[0003] Screening can be performed by a threshold method in one of two categories: two-level threshold screening and multi-level threshold screening. In two-level threshold screening, the (x, y) coordinates of the input pixels are used for indexing into a two-dimensional mxn matrix. Each entry in the matrix is a gray level threshold that is compared against the input pixel gray level. A binary value (0 or 1) is output based on the comparison result. Multi-level threshold screening indexes into a three-dimensional look-up table. This three-dimensional lookup table is configured as a two-dimensional preference matrix of M × N size. This preference matrix is a repeatable spatial tile in image space. Each entry in the preference matrix has one number of tone curves that must be used for the (x, y) position. The tone curve is a compensation transfer function that converts the input pixel gray value range into the range of the printing process. The tone curve conversion function is quantized based on a set of thresholds and stored in a look-up table. Each look-up table comprises 2 ^b entries for non-screen input pixel b-bit size. 2 ^b-number of entries includes a corresponding screen output pixels of all c-bit size. This process provides a way to translate the large dynamic range of the input image into a smaller printer dynamic range by mixing colors within the printer dynamic range.

[0004]

SUMMARY OF THE INVENTION The present invention involves approximating grayscale tones using a more limited range of image producing devices, ie, a process known as screening. The present invention identifies when screening is not required. In the rendering processing, an image area having a rendering target is determined. Screening is performed in those areas and not in other areas. Screening divides each row of the preference matrix into segments. The look-up tables associated with these segments are sequentially loaded into the memory cache. Input pixels located in the loaded segment lookup table are screened. The look-up table associated with the next segment of the preference matrix is then loaded into the memory cache and used to screen for input pixels located within that segment. The method can be used to compute M even when the preference matrix has odd row lengths.
, And alternately consider M-1 input pixels and M + 1 input pixels to pack the two output pixels into one data word while performing multi-level screening. Since each set of M-1 or M + 1 input pixels is even, it is possible to consider an even number of pixels for packing into an output data word.

[0005]

FIG. 1 is a block diagram of a network printer system 1 including a multiprocessor integrated circuit 100 configured for image and graphics processing according to the present invention. The multiprocessor integrated circuit 100
1 provides data processing including data manipulation and data calculation for image operations of the network printer system of FIG. 1.

FIG. 1 shows a transceiver 3. Transceiver 3 provides translation and two-way communication between the network printer bus and the communication channel. One example of a system that uses the transceiver 3 is a local area network. The network printer system shown in FIG.
Respond to print requests received via the local area network communication channel. The multiprocessor integrated circuit 100 translates print jobs specified in a page description language such as PostScript.

FIG. 1 shows a system memory 4 connected to a network printer system bus. This memory may include video random access memory, dynamic random access memory, static random access memory, non-volatile memory such as EPROM, FLASH or read only memory, or a combination of these memory types. The multiprocessor integrated circuit 100 may be controlled entirely or partially by a program stored in the memory 4. This memory 4 may also store various types of graphic image data.

In the network printer system of FIG. 1, the multiprocessor integrated circuit 100 communicates with a print buffer memory 5 for printable image details through a pixel map. The multiprocessor integrated circuit 100 controls the image data stored in the print buffer memory 5 via the network printer system bus 2. Data corresponding to this image is recalled from the print buffer memory 5 and supplied to the print engine 6. The print engine 6 provides a mechanism for arranging color dots on a print page. The print engine 6 is further responsive to control signals provided by the multiprocessor integrated circuit 100 for paper and printhead control. The multiprocessor integrated circuit 100 determines and controls where in the print buffer memory 5 the print information is stored. Thereafter, while reading from the print buffer memory 5, the multiprocessor integrated circuit 100 reads the sequence from the print buffer memory 5, the address to be accessed, and the control information necessary for creating a desired print image by the print engine 6. To determine.

According to a preferred embodiment, the present invention uses a multiprocessor integrated circuit 100. This preferred embodiment includes multiple identical processors that implement the invention. Each of these processors will be referred to as a digital image and graphics processor. This description is for convenience only. A processor implementing the present invention may be a single integrated circuit or a processor separately assembled on a plurality of integrated circuits. When implemented on a single integrated circuit, the single integrated circuit may optionally include read-only memory and random access memory used by a digital image and graphics processor.

FIG. 2 shows the configuration of a multiprocessor integrated circuit 100 according to a preferred embodiment of the present invention. The multiprocessor integrated circuit 100 includes two random access memories 10 and 20 each divided into a plurality of sections.
, A crossbar 50, a master processor 60, digital image and graphics processors 71, 72,
73 and 74, a transfer controller 80 that mediates access to the system memory, and a frame controller 90 that can control access to independent first and second image memories. Multiprocessor integrated circuit 100 provides a high degree of computational parallelism useful in image processing and graphics operations, such as in multimedia computing.

The multiprocessor integrated circuit 100 has two random access memories. The random access memory 10 is mainly assigned to the master processor 60. The random access memory 10 has two instruction cache memories 11 and 12, two data cache memories 13 and 14, and a parameter memory 15. These memory sections can be physically the same, but are used differently. The random access memory 20 includes a master processor 60 and digital image / graphics processors 71, 72, 73 and 74.
Is accessible by each of Digital image and graphics processors 71, 72, 73 and 7
4 each have five corresponding memory sections. These include one instruction cache memory, three data memories, and one parameter memory. Thus, the digital image / graphics processor 71 includes the corresponding instruction cache memory 21 and the data memories 22,
3, 24, and a parameter memory 25. The digital image / graphics processor 72 includes a corresponding instruction cache memory 26, data memories 27, 28, 29,
The digital image / graphics processor 73 has a parameter memory 30 and a corresponding instruction cache memory 3.
1, data memories 32, 33 and 34, and a parameter memory 35, and the digital image / graphics processor 74 has a corresponding instruction cache memory 36, data memories 37, 38 and 39, and a parameter memory 40. Like the sections of the random access memory 10, these memory sections can be physically the same, but are used differently. Each of these memory sections of memories 10 and 20 preferably has 2 Kbytes, for a total memory in multiprocessor integrated circuit 100 of 50 Kbytes.

The multiprocessor integrated circuit 100 provides a high data transfer rate between the processor and the memory using a plurality of independent parallel data transfers. Each digital image and graphics processor 71, 72, 73 and 74 has three memory ports each, which may operate simultaneously in each cycle. The instruction port (I) can take in a 64-bit data word from the corresponding instruction cache. The local data port (L) can read one 32-bit data word from a data memory or a parameter memory corresponding to the digital image / graphics processor, or write one 32-bit data word to them. The global data port (G) can read one 32-bit data word from any of the data memory, the parameter memory, and the random access memory 20 and write one 32-bit data word to them. Master processor 60 has two memory ports. The instruction port (I) has an instruction cache 1
A 32-bit instruction word can be taken from any of 1 and 12. The data port (C) is one of the data cache 13 or 14 of the random access memory 10, the parameter memory 15, and one of the data memory, the parameter memory, and the random access memory 20.
Two-bit data words can be read and one 32-bit data word can be written to them. The transfer controller 80 can access any section of the random access memory 10 or 20 via the data port (C). Thus, fifteen parallel memory accesses may be required in any single memory cycle. The random access memories 10 and 20 are divided into 25 memories to support such a large number of parallel accesses.

The crossbar 50 is connected to the master processor 6.
0, each digital image graphic processor 7
1, 72, 73 and 74 and transfer controller 8
0 and the connection between the memories 10 and 20 is controlled. The crossbar 50 has a plurality of intersection points 51 arranged in rows and columns.
Each column of the intersection points 51 corresponds to a single memory section and a corresponding address range. The processor transmits one of the memory intervals through the most significant bit of the address output from the processor.
Request access to one. The address output by this processor propagates along the rows. The crossing point 51 corresponding to the memory section having that address responds by either accepting or denying access to that memory section. If no other processor has requested access to the memory section during the current memory cycle, cross point 51 grants access by connecting the rows and columns. Thus, an address is supplied to the memory section.
The memory section responds by allowing data access at that address. This data access
Either a data read operation or a data write operation may be performed.

If two or more processors request access to the same memory section at the same time, crossbar 50 allows access to only one of the requesting processors. The intersections 51 in each row of the crossbar 50 communicate based on priority and allow access. If two access requests with the same rank occur at the same time, the crossbar 50 grants access on a round robin basis, so that the processor recently granted access has the lowest priority. Each granted access lasts as long as it is necessary to fulfill the request. Since the processor may change each address in each memory cycle, the crossbar 50 can change the interconnection between the processor and the memory section in each cycle.

Master processor 60 preferably performs the primary control functions of multiprocessor integrated circuit 100. Master processor 60 is preferably a 32-bit reduced instruction set computer (RISC) processor that includes a hardware floating point calculation unit. RI
According to the SC architecture, all accesses to memory are performed using load and store instructions, and most integer and logical operations are performed on registers in a single cycle. However, if the floating point arithmetic unit uses the same register file as used by the integer and logic units, it generally takes several cycles to perform the operation. The register scoreboard ensures that the correct register access sequence is maintained.
The RISC architecture is suitable for control functions in image processing. The floating point calculation unit allows for rapid calculation of the image rotation function, which may be important for image processing.

The master processor 60 fetches an instruction word from the instruction cache memory 11 or the instruction cache memory 12. Similarly, the master processor 60
Is the data cache 13 or data cache 1
4. Data is fetched from one of the four. Since each memory section includes 2 Kbytes of memory, there is a 4 Kbyte instruction cache and a 4 Kbyte data cache.
Cache control is an essential function of the master processor 60. As described above, the master processor 60
Other memory sections can be accessed via the crossbar 50.

Each of the four digital image and graphics processors 71, 72, 73 and 74 has a highly parallel digital signal processor (DSP) architecture. FIG. 3 shows an overview of an exemplary digital image graphics processor 71, which includes digital image graphics processors 72, 73.
And 74. The digital image / graphics processor 71 has three separate units: a data unit 110 and an address unit 12.
0 and the program flow control unit 130 are used to achieve a high degree of parallel processing of operations. These three units operate simultaneously with different instructions in the instruction pipeline. In addition, each of these units also has internal parallel processing.

Digital image and graphics processors 71, 72, 73 and 74 can execute independent instruction streams in a multiple instruction multiple data (MIMD) mode. In the MIMD mode, each digital image / graphics processor executes a separate program from its corresponding instruction cache. The instruction cache may be independent or cooperative. In the latter case, crossbar 50 is coupled to shared memory to allow interprocessor communication. Digital image and graphics processors 71, 72, 73 and 74 can also operate in a synchronous MIMD mode. Synchronous MIMD
In the mode, the program flow control unit 130 of each digital image and graphics processor is inhibited from fetching the next instruction until all synchronous processors are ready to start. This synchronous MIMD mode allows the separate programs of the digital image and graphics processor to execute in lockstep as one tightly coupled operation.

Digital image and graphics processors 71, 72, 73 and 74 can execute the same instruction on different data in a single instruction multiple data (SIMD) mode. In this mode, a single instruction stream for the four digital image graphics processors comes from the instruction cache memory 21. Digital image graphics processor 71 controls the capture and branch operations so that crossbar 50 provides the same instructions to other digital image graphics processors 72, 73 and 74. In SIMD mode, the digital image graphics processors are essentially synchronized because the digital image graphics processor 71 controls instruction capture for all digital image graphics processors 71, 72, 73 and 74.

The transfer controller 80 has a direct memory access (DM) for the multiprocessor integrated circuit 100.
A) Combined machine and memory interface. Transfer controller 80 intelligently waits, sets priorities, and manages data requests and cache misses for the five programmable processors. Master processor 60 and digital image and graphics processors 71, 72, 73 and 74 all access memory and systems external to multiprocessor integrated circuit 100 via transfer controller 80. Cache misses in the data cache or instruction cache are automatically handled by the transfer controller 80. The cache service port (S) transmits such a cache miss to the transfer controller 80. The cache service port (S) reads information from the processor, not from memory. Master processor 60 and digital image
The graphic processors 71, 72, 73 and 74 request data transfer from the transfer controller 80 as linked list packet requests. These linked list packet requests also allow multi-dimensional block information to be transferred between source and destination memory addresses. These memory addresses are stored inside the multiprocessor integrated circuit 100 and in the multiprocessor integrated circuit 1.
00 outside. Transfer controller 80 is preferably a dynamic random access memory (DRAM)
Also includes a refresh controller. DRAMs require periodic refreshes to maintain their data.

Frame controller 90 is the interface between multiprocessor integrated circuit 100 and an external image capture and display system. Frame controller 90 provides control over the capture and display devices and automatically manages the movement of data between these devices and memory. To this end, the frame controller 90
Provides simultaneous control for two independent imaging systems. These imaging systems typically include a first imaging system for image capture and a second imaging system for image display. However, the frame controller 9
The use of 0 is controlled by the user. These imaging systems typically include a separate frame memory used for frame grabber or frame buffer storage. Frame controller 90 preferably operates to control a video dynamic random access memory (VRAM) through refresh and shift register control.

The multiprocessor integrated circuit 100 is designed for large-scale image processing. The master processor 60
It performs embedded control, i.e., organizing the activities of the digital image and graphics processors 71, 72, 73 and 74 and interpreting the results produced thereby. Digital image and graphics processors 71, 72, 73 and 74 are suitable for pixel analysis and manipulation. If a pixel is considered high-level for data but low-level for information, typical use would be to use digital image and graphics processors 71, 72,
73 and 74 may test their pixels to convert the raw data into information. This information is then provided to digital image and graphics processors 71, 72, 73 and 7
4 or by the master processor 60. The crossbar 50 mediates communication between processors. The crossbar 50 allows the multiprocessor integrated circuit 100 to be implemented as a shared memory. In this architecture, message exchange need not be the primary type of communication. However, messages can be exchanged via shared memory. The corresponding section of each digital image / graphics processor, crossbar 50, and the corresponding section of memory 20 have the same width. This allows the architecture to be flexible if the addition and removal of each digital image / graphics processor and corresponding memory is modularly adapted to maintain the same pinout.

In the preferred embodiment, all portions of multiprocessor integrated circuit 100 are located on a single integrated circuit. In the preferred embodiment, the multiprocessor integrated circuit 10
0 is formed in a complementary metal oxide semiconductor (CMOS) using a feature size of 0.6 m. The multiprocessor integrated circuit 100 is preferably configured in a pin grid array package having 256 pins. The inputs and outputs are preferably compatible with transistor-transistor logic (TTL) logic voltages. The multiprocessor integrated circuit 100 preferably includes 3 million transistors, 50
The clock rate of MHZ is used.

FIG. 3 shows an overview of each of the exemplary digital image and graphics processors 71;
It is virtually identical to 4. The digital image / graphics processor 71 includes a data unit 110,
It has an address unit 120 and a program flow control unit 130. The data unit 110 performs a logical or arithmetic data operation. Data unit 110
Has eight data registers D7-D0, one status register 210, and one multiple flag register 211. Address unit 120 controls the generation of load / store addresses for local and global data ports. As described further below, address unit 120 has two virtually identical addressing units. One is for local addressing and the other is for global addressing. Each of these addressing units has one ALL "0" read-only register, one stack pointer, five address registers, and three address registers that enable absolute addressing in relative address mode.
And two index registers. The addressing units share a global bit multiplexing control register used to form one combined address from both addressing units. Program flow control unit 130 controls the program flow for digital image and graphics processor 71, including address generation for fetching instructions from the instruction port. The program flow control unit 130 has one program counter PC 701, one address stage instruction pointer IRA 702 that holds the address of the current instruction in the address pipeline stage, and one that holds the address of the current instruction in the execution pipeline stage. One execution stage instruction pointer IRE703 and one subroutine return stage instruction pointer I holding an address for returning from a subroutine.
RRS 704, a set of registers controlling the zero overhead loop, and 4
Four tag registers TAG, collectively called 708, holding the most significant bits of the instruction word of the block
3-TAG0.

The digital image / graphics processor 71 operates on one three-stage pipeline as shown in FIG. The data unit 110, the address unit 120, and the program flow control unit 130
Operate simultaneously by different instructions in one instruction pipeline. Arranged in chronological order, the three stages are a capture stage, an address designation stage, and an execution stage. Thus, at any given time, the digital image and graphics processor 71 is operating based on the different functions of the three instructions. The term pipeline stage is used instead of a clock cycle to indicate that a particular event occurs during the pipeline progression, not during a stall condition.

The program flow control unit 130
Perform all operations that occur during the acquisition pipeline stage. Program flow control unit 130
Has a program counter, loop logic, interrupt logic, and pipeline control logic. During the fetch pipeline stage, the next instruction word is fetched from memory. The address contained in the program counter is compared with the cache tag register to determine whether to store the next instruction word in instruction cache memory 21. Program flow control unit 130
Supplies the address in the program counter to the instruction port address to fetch the next instruction word from the instruction cache memory 21 if it exists. Crossbar 50 sends this address to the corresponding instruction cache, here instruction cache memory 21, thereby returning the instruction word on instruction bus 132. Alternatively, when a cache miss occurs, the transfer controller 80 accesses the external memory to obtain the next instruction word. The program counter is updated. If the following instruction word is at the next consecutive address,
The program flow control unit 130 increments the program counter backward. Alternatively, the program flow control unit 130 loads the address of the next instruction word according to the loop logic or software branch. If the synchronous MIMD mode is active, instruction fetch will wait until all designated digital image graphics processors have synchronized and are indicated by the sync bit in the communication register.

The address unit 120 performs all address calculations in the address pipeline stage. The address unit 120 has two independent address units. One is for the global port and the other is for the local port. When an instruction invokes one or two memory accesses, the address unit 120 generates an address during an address pipeline stage. The address is supplied to the crossbar 50 via the global port address bus 121 and the local port address bus 122 for conflict detection and prioritization. If there is no contention, the accessed memory prepares to grant the requested access, but the memory access occurs during a subsequent execution pipeline stage.

Data unit 110 performs all logic and arithmetic operations in the execution pipeline stages. All logic and arithmetic operations and all data movement to and from memory occur during the execution pipeline stage. The global data port and the local data port complete the memory access started during the address pipeline stage to the execution pipeline stage. The global data port and the local data port perform all data alignment required for memory store, and all data extraction and sign extension required for memory loading. If the program counter is designated as the data destination during the operation of the execution pipeline stage, a two-instruction delay occurs before the branch is taken. Since the next two instructions following such a branch instruction have already been fetched, this delay is required for pipeline operations. When implemented on a RISC processor, other useful instructions may be located at two delay slot locations.

Digital image and graphics processor 71 has three internal 32-bit data buses. These are a local port data bus Lbus103, a global port source data bus Gsrc105, and a global port destination data bus Gdst107. These three buses interconnect the data unit 110, the address unit 120 and the program flow control unit 130. These three buses are local port 1
41 and a data port unit 140 having a global port 145. Data port unit 140 is coupled to crossbar 50 that provides memory access.

The local data port 141 has a buffer 142 for storing data in a memory. The multiplexer / buffer circuit 143 is connected to the local port data bus 144 or from the memory via the crossbar 50, or from the local port address bus 122 or from the global port data bus 148.
Load data on the bus 103. The local port data bus Lbus 103 then carries 32-bit data from a register (store) or memory (load). Advantageously, data unit 1
The arithmetic result in the address unit 120 is complemented by the local port address bus 122 to supplement the
The data can be supplied to the local port data bus Lbus103 via the multiplexer bus 143. This will be further described below. Buffer 142 and multiplexer buffer 143 perform data alignment and extraction. The local port data bus Lbus103 connects to a data register in the data unit 110. The local bus temporary holding register LTD104 is also connected to the local port data bus Lb.
It is connected to us103.

Global port source data bus Gsr
c105 and global port destination data bus Gdst1
07 mediates global data transfer. These global data transfers may be memory accesses, register-to-register transfers, or instruction word transfers between processors. Global port source data bus G
The src 105 carries 32-bit source information for global port data transfer. The data source may be data in any of the registers of the digital image graphics processor 71 or in any of the parameter memories corresponding to any of the digital image graphics processors 71, 72, 73 or 74. The data is stored in the memory via the global port 145.
The multiplexer buffer 146 selects a line from the local port data bus Lbus103 or the global port source data bus Gsrc105, and performs data alignment. The multiplexer buffer 146 is connected to the crossbar 5
This data is written on the global port data bus 148 for application to the memory via 0. Global port source data bus Gsrc 105 also provides data to data unit 110 so that data on global port source data bus Gsrc 105 can be used as one of the arithmetic logic unit sources. This latter connection allows any register of the digital image graphics processor 71 to be a source for arithmetic logic unit operations.

Global port destination data bus Gdst
107 carries 32-bit destination data for global bus data transfer. The destination is one of the registers of the digital image / graphics processor 71. The buffer 147 of the global port 145 performs sourcing of data of the global port destination data bus Gdst107. Buffer 147 performs the required data extraction and sign extension operations. This buffer 115
Works when the data source is memory, and so loading is taking place. The arithmetic logic unit result serves as an alternative data source for the global port destination data bus Gdst 107. This allows any register of the digital image graphics processor 71 to be the destination for arithmetic logic unit operations. The global bus temporary holding register GTD108 is also connected to the global port destination data bus Gdst107.

Multiplexer buffers 143 and 14
Circuitry 6, including 6, is connected between global port source data bus Gsrc 105 and global port destination data bus Gdst 107 to provide register movement for registers. Thus, the global port source data bus Gsr can be transmitted from any register of the digital image / graphics processor 71.
The read on c105 can be written to any register of the digital image / graphics processor 71 via the global port destination data bus Gdst107.

It should be noted that, advantageously, the digital image and graphics processor 7 from the memory via the global port destination data bus Gdst 107
1 means that the arithmetic logic unit in the data unit 110 can be sourced from any register via the global port source data bus Gsrc 105 while executing the loading of any register. Similarly, the global port source data bus Gsrc10
5, while storing data in any of the registers of the digital image / graphics processor 71 in the memory, the global port destination data bus Gdst10
7, the result of the arithmetic and logic unit operation can be saved to any register of the digital image / graphics processor 71. The usefulness of these data transfers will be described in more detail below.

The program flow control unit 130 receives the fetched instruction word from the instruction cache memory 21 via the instruction bus 132. This captured instruction word is advantageously stored in two 64-bit instruction registers, referred to as the address stage instruction register IRA 751 and the execution stage instruction register IRE 752. Instruction registers IRA and IRE both decode and deliver their contents. Digital image
The graphic processor 71 decodes or
An instruction code bus 1 for transporting the partially decoded instruction contents to the data unit 110 and the address unit 120
33. As described below, one instruction word may have a 32-bit, 15-bit, or 3-bit immediate field. Program flow control unit 130 routes these immediate fields to global port source data bus Gsrc 105 for delivery to its destination.

The digital image / graphics processor 71 has three address buses 121, 122 and 13
One. The address unit 120 generates an address on the global port address bus 121 and the local port address bus 122. As will be described in further detail below, address unit 120 has separate global and local address units that provide addresses on global port address bus 121 and local port address bus 122, respectively. Note that the local address unit 620 may access memory other than the data memory corresponding to the digital image and graphics processor. In that case, the access of the local address unit is performed via the global port address bus 121.
The program flow control unit 130 performs sourcing of instruction addresses on the instruction port address bus 131 from a combination of address bits from the program counter and the cache control logic. These address buses 12
1, 122 and 131 carry address, byte strobe, and read / write information, respectively.

FIG. 5 shows a simplified diagram of the master processor 60. The main blocks of the master processor 60 are a floating point unit (FPU) 201, a register file (RF) 202, and the results of floating point operations and memory loads are registered between the data cache and the floating point unit 201 as sources and attributes. To a register scoreboard (SB) 203 that ensures that their results are available before they are used for accessing their shared write port to file 202, and to on-chip memory via a crossbar A data cache controller 204 that also controls the interface to the external memory via the transfer processor 80, a barrel shifter (BS) 205 for executing a shift instruction, a zero comparison logic 206,
Rightmost detection logic (LMO / RMO) 207, addition,
An integer arithmetic and logic unit (ALU) 208 used for subtraction and logic operations and for calculating the branch target address during a relative branch, and an interrupt pending register (INTPE) for receiving a master processor interrupt signal.
N) 209, an interrupt permission register (IE) 210 for selectively enabling or disabling an interrupt, a program counter register (PC) 211 for holding an address of an instruction to be fetched, and a program for the next instruction. A program counter incrementer (INC) 212 that can increment a counter 211 and send the increment value to a register file as a "return" or "link" address, decode the instruction, and provide control signals to the operating unit. Instruction decoding logic (DEC
ODE) 213, an instruction register (IR) 214 that holds the address of the instruction being executed, an immediate register (IMM) 215 that stores any instruction immediate data, and an interface to the transfer processor 80 for cache filling. An instruction cache controller (ICACHE) 216 that provides instructions to be performed.

FIG. 6 shows the basic pipeline used in the master processor 60. Master processor 60 has a three-stage pipeline that includes the fetch, execute, and memory stages. FIG. 6 shows how three instructions pass through the pipeline. During the fetch stage of the pipeline, the program counter 210 addresses the instruction cache and reads a 32-bit instruction. During the execution stage, instructions are decoded, source operands are read from a register file, operations are performed, and results are written back to the register file. The memory stage is only for loading and storing operations. The address calculated during the execution stage is used to address the data cache,
Data is read and written. When a miss occurs in the instruction cache, the fetch and execute stage is stopped until the request is satisfied. When a miss occurs in the data cache, the memory pipeline stops until the need to start another memory operation, but the capture and execution stages continue to flow.

FIG. 7 shows the basic pipeline for the floating point unit 201. The fetch stage is the same as the above-described integer operation fetch stage. During the unpacking stage of a floating point instruction, all the data necessary to start a floating point operation arrives, including the source operand, opcode, precision and destination address. The two source operands are read from the register file. The operands are then unpacked into the sign, exponent, and mantissa fields, and special case detection is performed. Input exceptions are detected in this cycle. Moreover, input exceptions are passed through the floating point unit 201 and signaled in the same cycle as single precision output exceptions. Other special cases, including signaling not-a-number, quiet not-a-number, infinity, outliers and zero are also detected, and this information is not visible to the user. , Follow the data through different pipeline stages of the manual decimal point unit 201.

All calculations are performed in the operating stage.
Depending on the type of instruction, the operating stage may require several cycles.

When the result of the floating-point unit 201 is determined, some pieces of information on the floating-point operation are recorded in the floating-point status register. All floating point instructions are written only once to the floating point status register.

FIG. 8 shows the steps commonly performed when trying to print a document specified in a page description language such as PostScript. Following receipt of the print file (input data file 301) is translation (processing block 302). In this step, the input PostScript file is translated and converted into an intermediate format called a display list (data file 303).
The display list 303 includes a list of low-level basic words for creating a description page such as trapezoids, fonts, and images. Next, the display list is rendered (processing block 304). Each element of the display list is processed in this step and the output is written to the buffer as a page buffer (data file 305).
The page buffer 305 represents a part of the output image with respect to a specific one color center plane. In the page buffer 305, each pixel is generally represented by 8 bits. When all the elements of the display list 305 have been processed, the page buffer 305 has the output image in an 8-bit format. Next, the page buffer is screened (processing block 306). The resolution supported by the printing device can be anywhere between 1 and 8 bits per pixel.
The page buffer 305 expanded in the rendering step 304 must be converted to a resolution supported by the printer. The data thus converted is called a device image. Each pixel in page buffer 305 must be converted to a corresponding device pixel value. For example, for a 4-bit device pixel, each pixel in page buffer 305 must be converted to a 4-bit value. As a result of a process called this screening,
Screened page buffer (data file 3
07). Next, printing is performed (processing block 30).
8). Each pixel of the screened page buffer 307 is printed on paper. This process is for cyan, yellow,
Repeated for all magenta and black color center planes.

Each page in a typical page output is 8 inches by 11.5 inches. If the print density is 600 pixels per inch, the page contains 33 million pixels. Each pixel needs to be screened. Assuming that it takes T time to screen one pixel, it takes a total of 33 million T hours to screen an entire page for a specific one color center plane. The problem with this method is that
Pixels with a value of 0, that is, pixels that are not the output of the rendering module, are also screened. In a typical page, the effective pixel rate is only a fraction of the total number of pixels. That is why many pixels have a zero value. Table 1 tabulates the evaluation of the percentage of available print area for various page types.

[0044]

[Table 1]

Assuming that only 40% of the pages are written by the rendering module, 60% of the pages undergo unnecessary screening. This means that the total spent on unnecessary screening is 60% of 33 million T units, or 1900 T units. For a text page, only about 30% of the page is the print area. Thus, for text pages, 70% of the screening time is wasted in the blank area. The potential gain for pages with graphic and image information is small, but still significant.

The method of the present invention overcomes this loss. The present invention identifies blank areas and printed areas on a page in one of two ways. The first method screens only the area within the bounding box of the display list element. A second method identifies scan lines that have print pixels.

FIG. 9 shows an application example of the bounding box method for identifying valid and blank print areas. Each rendering module 401 prepares a bounding box surrounding a rendering target. For example, a rendering module 401 for processing a trapezoidal element
Prepares a bounding box 403 surrounding the trapezoid written in the page buffer. Similarly, the font rendering module 401 also performs bounding box 40 on the input characters of the rendered font.
Prepare 5

The output of each rendering module 401 is the rendered element in the page buffer plus the parameters of the bounding box containing the rendered element. When the display list is processed, a list of such bounding boxes is provided to the screening module 407. Screening module 407 considers each bounding box 403 and 405. Screening module 407 only screens the pixels in the bounding box and writes the output into a 4-bit output page buffer 409 for print operation 411.

FIG. 10 shows an application example of the scanning line method for identifying the effective and blank print areas. Providing a bounding box for each module and screening the individual bounding box for each rendering target can be problematic. For complex figures, there may be many small overlapping bounding boxes. Decorated text may also result in duplicate bounding boxes. As a result, many areas may not be able to be erased by the bounding box method. Furthermore, most screening means are effective when operating on long, continuous data, such as a complete scan line. In such a case,
The bounding box method may be less effective.

The scan line method allows to screen all scan lines in an image with valid pixels, but only scan lines. Only scan lines that intersect with the object to be rendered are screened. A data structure such as array 413 indicates whether scan lines are to be screened. A value of 0 indicates that the scan line is not scheduled to be printed, and a value of 1 indicates that the scan line is scheduled to be printed. In the scanline method, there are two outputs after the entire page has been rendered by the rendering module. The first output is a rendered page that contains all the rendered modules. Each pixel of this rendered page is 8 bits. The second output is a scanning line array having the number of elements equal to the number of scanning lines in the page. Each element here has a 1 or 0 indicating whether the scan line requires screening.

Consider a page example shown in FIG. This page has a trapezoid starting at line 10 and ending at line 15, and characters in the rendered font starting at line 14 and ending at line 31. All elements in the scan line array are initialized to zero. As rendering progresses, the rendering module 501 writes 1 to this scan line array, at the location where the object was rendered, corresponding to the line that needs to be screened. In the present example, the scan line array thus has 0 for scan lines 0 through 9, 1 for scan lines 10 through 31, and 0 for scan lines 32 and above. Screening module 503 receives these inputs and scan line array 1
, Ie, only the scan lines 10 to 31 are screened. The screened scan lines are printed in a print operation 503.

This measure is simple. Only minor changes are required in the means of the rendering module and the screening means. The method is very useful for text images where there are many empty scan lines. The time savings are substantial because only non-empty scan lines are screened.

FIG. 11 shows the structure of a three-dimensional lookup table generally used in conventional screening. The pixel locations indicated by the X, Y coordinates are modulo indexed into the MxN preference matrix. Thus, the pixel X coordinate selects one row of the preference matrix at X modulo M. Similarly, the pixel Y coordinate selects one column of the preference matrix in the Y modulo N.

FIG. 12 is an example of a 4 × 4 preference matrix. The data at the access position in the preference matrix points to one of the look-up table sets. Each element in the preference matrix indicates the number of lookup tables. Pixels indicating the element (0, 0) in the preference matrix are stored in the first lookup table LU.
Use T (0). Pixels indicating (0, 1) in the preference matrix use LUT [1]. Pixels indicating (0, 2) in the preference matrix use the lookup table [1]. Pixels indicating (0, 3) in the preference matrix are LU
Use T [2]. Thus, the preference matrix specifies a look-up table used for image screening of pixels of the input image. Similarly, from (1, 0) to (1,
3) Lookup tables are calculated for pixels based on (2,0) to (2,3) and (3,0) to (3,3). In the example of the 4 × 4 preference matrix of FIG.
For a given pixel at (X, Y), select a lookup table in which the preference matrix element at (X modulo 4, Y modulo 4) is used. Thus (0, 1)
Is a LUT [1] for the pixel at (0,5) indicating Indicates (3,0) (7,8)
The lookup table for the pixel at is LUT [0]
It is. Thus, the input pixel locations are mapped onto a preference matrix to select an appropriate look-up table.

Returning to FIG. 11, the indexing modulo selects one of the look-up table sets. The pixel grayscale value will be an index in the selected look-up table. If the pixel has b bits, each look-up table has 2 ^d entries. Each entry has c bits of data within the dynamic range of the printing device having a corresponding screened output pixel of c bits in size. Thus, the screening value V of the pixel at (x, y) is

V = LUT [preference_matrix [x% m] [y% n] [image [x] [y]]

This prior art places some demands on available on-chip memory. The preference matrix has a maximum of 512 row sizes. This requires a 1K byte area in the on-chip memory, including the memory that processes the odd preference matrix row dimensions addressed in the next interval. Processor integrated circuits require buffers for input and output. When 2K bytes are allocated to the input / output buffer using two buffers for input / output, 4K bytes of memory are required. When the above-described multiprocessor integrated circuit 100 is used, about 0.5 is used as a parameter space for defining a transfer request.
K bytes are required. These memory requirements add up to about 5.5K. When using the digital image graphics processors 71, 72, 73 and 73 of the multiprocessor integrated circuit 100 in the margin, these memory requirements leave only about 2K bytes for the lookup table. This means that up to eight look-up tables can exist in the on-chip memory of digital image and graphics processors 71, 72, 73 and 73.

Many practical embodiments use 4-bit data in a printing device image. Most data processors provide a minimum addressable unit of 8 or 1 bit. Thus, two 4-bit pixels are processed simultaneously and packed into one 1-byte output. This is not a problem if the preference matrix has an even number of pixels per row. Given a preference matrix of row size 6, the screened outputs of pixels 0 and 1 are written to output address 0, pixels 2 and 3 are written to output address 1,
Pixels 4 and 5 are written to output address 2.

FIG. 13 illustrates a problem of the prior art that occurs in the case of a preference matrix having a row size of an odd number of elements. In this example, the preference matrix has a row size of three. When packing nibbles into bytes, a problem arises with the odd number of elements.
The screened output of pixels 0 and 1 is output address 0
Is written to. Processing pixel 2 results in one 4
Produces a bit output. Because the output memory is byte addressable and not 4-bit addressable,
This 4-bit output cannot be written alone to the output memory. This special case requires special handling for read / modify / write operations, thereby reducing throughput.

FIG. 14 schematically shows a method proposed by the present invention to solve this problem. A look-up table cache is maintained in on-chip memory. As previously calculated, the multiprocessor integrated circuit 1
At 00 eight look-up tables can always be maintained in on-chip memory. To simplify this caching, the preference matrix rows are divided into preference segments. This removes the limit on the maximum number of lookup tables.

The input image is processed one scanning line at a time. Each row of the preference matrix is divided into eight element preference segments. As shown in the example of FIG. 14, a preference matrix of row size 16 has a preference segment 0 having elements 0 to 7,
It is divided into preference segments 1 having elements 8 to 15. The current input line is processed for these preference segments. A look-up table belonging to the first preference segment is brought to the on-chip memory, and all pixels corresponding to this segment are processed and output. The process is repeated for the remaining segments in turn. Note that the digital image and graphics processor 7
The memory organization of the data memory associated with 1, 72, 73 and 74 is to permit data transfer in units of these preference segments.

Does non-segmented processing waste a lot of time waiting for the look-up tables to be transferred on-chip, or do all separate look-up tables need to be implemented on-chip? Was either. The preferred segment method of the present invention allows screening by caching preferred segments without either of these disadvantages.

To simplify the processing, each entry of the look-up table has 8 bits. As the preference segment is processed, eight input elements are screened into four bytes. The output buffer is created by such a 4-byte segment. This reduces the bandwidth of the transfer controller 80 to 50%. This is because only eight look-up tables can be stored in the on-chip memory. If the 16 look-up table entries are 4-bit entries, 16 look-up tables are cached. This allows a preference segment of 16 elements and the transfer controller 8
Produces an 8-byte output giving 100% utilization of 0.

FIG. 15 illustrates the method of the present invention for processing a preference matrix having an odd row size. If the preference matrix row size is odd size, the preference matrix is doubled. As a result,
It becomes even size. As shown in FIG. 15, six input pixels of eight bits each are screened into six four-bit nibbles and packed into six byte words. Doubling the preference matrix is achieved by duplicating the preference matrix at its size. This makes the tile size 2
Double that, each such tile is made from two identical halves. The pixel size in the doubled direction is not modulo M but modulo 2M
Is indexed by This doubling requires more space to store the preference table.
However, this doubling reduces computational complexity,
Make the calculations uniform.

A brief description of the method is given below in the form of pseudo code. According to this example, the input buffer size is 2K bytes and the output buffer size is 1K bytes. // Process one row of image at a time from row = 0 to image height for row = 0 to image height pref_row_num = image_y% Preference matrix height Transfer preference matrix [pref_row_num] Chip if preference matrix width is odd Duplicate upper buffer // The preference line is divided into preference segments, each 8 entries long. // Inputs are processed for preference segments. pref_count indicates // an integer number of such preference segments in the preference bank. pref_count = pref_row_size / 8 for i = 0 to pref_count-1 Obtain preference_segment [i] Obtain LUTBLOCK [i] input Obtain block corresponding to preference_segment [i] Input / screen Read 2 bytes from input, read 4 bits Screen for value // combine these values to form an 8-bit value and write to output buffer for (m = 0; m <PAGE_WIDTH; m + = 8) for (k = 0; k <8; k +2) * output ++ = (LUT [k] [input [m = k]] << 4) | LUT [k + 1] [input [m + k + 1] end for PAGE_WIDTH / 2 size output end for end for

This is an implementation, the digital image and graphics processors 71, 72,
Only one resource 73 and 74 is used, and the other processor's resources are not consumed. Screening is limited to one of these processors, allowing other processors to independently perform other operations.

Lookup table, input / output buffer,
By properly locating the preference matrix rows in the on-chip memory, the double buffering mechanism can be extended to look-up tables and preference matrix rows. This avoids waiting for the lookup table to load when the next preference segment is processed and waiting for the preference matrix row to load when processing the next scanline.

Due to the fact that the screened output value is one nibble (4 bits) and the limitation that the memory arrangement is byte (8 bits) addressable,
The core method of screening requires processing two pixels at a time. Therefore, the core method of screening according to the prior art has the following steps. Step 1: Screen the pixel pointed to by input_pointer to 4 bits and hold in the first temporary memory location. Step 2: input_pixel_pointer is incremented. Step 3: Increment pref_pointer. Step 4: Screen the pixel pointed to by input_pointer to 4 bits and hold in the second temporary memory location. Step 5: Increment input_pointer. Step 6: Increment pref_pointer. Step 7: Pack the first and second temporary nibbles into 8 bits. Step 8: Store the packed value in the position indicated by output_pointer. Step 9: Increment output_pointer.

A loop is set to be executed for all pixels in one row, and when the length of the row is equal to L, the total number of loops is L / 2. When the preference matrix pointer is incremented and matched within the loop for each pixel pair, the tile size of the preference matrix must be even. If M is even, a single pointer (indicating a preference matrix row) wrapping around an array of size M can be used as is in the loop. To extend the same concept in the odd case, the scan lines need to be tiled modulo 2M.
As a result, the matching of the preference matrix pointer can be performed for each pixel pair, and the core method of screening two pixels at a time can be used here.

FIG. 16 schematically illustrates a prior art method of indexing into a look-up table for screening using a preference matrix having an odd number M. To screen a row of pixels by the prior art method for odd M, an outer loop is performed that is performed on the total number of pixels. Within this loop range for each pixel pair, whenever the circular pointer reaches 2M, program matching is performed to reset the circular pointer to the beginning of the array. As shown in FIG. 16, loop_pref_pointer is
When f_pointer_end is reached, loop_pref_pointer becomes pr
Reset to ef_pointer_start.

The prior art screening loop has the following steps. Step 1: loop_pref_pointer is converted to pref_pointer_
Set to start. Step 2: Repeat steps 3 and 4 for i = 1 to i 1/2. Step 3: [All steps of the core method of screening] Step 4: loop_pref_pointer becomes pref_pointer_
Checks if it is equal to end. If true, reset the pointer to the beginning of the array, ie, loop_pref_poin
ter is set to pref_pointer_start. Otherwise, continue the loop. The same method is extended for odd M preference matrices. In that case, the scanning line has a modulus M
And the loop is reset every M pixels, that is, each time the pointer reaches pref_end_pointer. Note that pref_end_pointer is pref_po
inter_start + M−1. The screening loop has the same steps as the odd M case.

The prior art method described above has poor processing power because the preference matrix modulo matching is performed in a loop. This prior art method also requires a 2 Mbyte size array to store the preference matrix on chip for odd M.

The proposed method of the present invention seeks to alleviate the above problem by not matching the preference matrix pointer in a loop. The proposed method also reduces the memory storage requirements of the preference matrix for odd M cases. The present invention uses the same screening core method as the prior art. In the proposed method of the present invention, the scanning line is tiled with the preference matrix row size M in the case of an even number M and 2M in the case of an odd number M, and an outer loop and an inner loop are set. The inner loop consists of a screening core method, which is performed on M / 2 pixels for even M and for M pixels for odd M.

If a scan line does not start and end at a tile boundary, the scan line is divided into three parts. These are the start part to the boundary of one tile (M or 2M), the end part continuing from the penultimate tile boundary to the end of the scan line, and the middle part consisting of a complete tile. The middle part is processed using outer and inner loops, while setting a partial inner loop to screen for pixels at the start and end. For line lengths smaller than the tile size, a partial inner loop is used. Odd or even M
The method of having inner and outer loops in the case of is also described below.

FIG. 17 schematically illustrates the method of the present invention for indexing a look-up table for screening with a preference matrix having an odd number M. The proposed method uses two pointers in the preference matrix array.
The preference matrix is stored in an M + 1 size array. The first entry in this array is the Mth element of the preference matrix row. This is followed by M elements of the preference matrix row. The scan line is split into 2M modulus and the inner loop is split into two loops. One of the loops is performed on pixels from 1 to M + 1 and the other is from 1 to M-1
This is performed for the pixels of. These two inner loops have M in each entry
Use preference matrix start pointers of +1 and M-1.
If M is odd, then M + 1 and M-1 are even, so the inner loop performed on the (M + 1) / 2 and (M-1) / 2 pairs of pixels will still have the same screening core method. Can be used. Within these loops, the preference matrix pointer is only incremented. At the end of the loop, the two preference matrix pointers are M + 1
Alternatively, it is reset to the head of the preference matrix array of M-1. The outer loop is performed for 2M tiles in the scan line.

The screening loop has the following steps. Step 1: Calculate the number of tiles to be processed tile_cnt = L / (2 * M), giving the total number of outer loops. Step 2: loop_pref_pointer1 is converted to pref_pointer
Set to _M-1_start. Step 3: Repeat steps 4 to 9 for k = 1 to k tile_cnt. Step 4: loop_pref_pointer is converted to pref_pointer_
Reset to start_M-1. Step 5: Step 6 is repeated for i = 1 to i (M-1) / 2. Step 6: [All steps of the core method of screening] Step 7: Loop_pref_pointer is converted to pref_pointer_
Set to M + 1. Step 8: Step 9 for i = 1 to i (M + 1) / 2
repeat. Step 9: [All steps of the core screening method]

If a scan line does not start and end at a 2M tile boundary, the start and end portions of that scan line will be processed separately. These processes have only partial inner loops (no outer loops needed) where the preference matrix pointer starts at the appropriate M + 1 or M-1.
The order of the M + 1 or M-1 pointers depends on where in the 2M tile the scan line starts.

The proposed method has a scan line divided into even modulo M tiles. There are two loops. M /
The inner loop for two pixels uses the core method of two-pixel screening. The outer loop is performed for the number of tiles in the scan line to be screened. There is a pointer which is incremented in the inner loop, and the pointer is reset to indicate the head of the preference matrix array size M in the entry of the outer loop and to indicate the head of the preference matrix at the end of each inner loop. .

The screening loop has the following steps. Step 1: Calculate the number of tiles to be processed. tile_
cnt = L / M gives the count of the outer loop. Step 2: loop_pref_pointer is converted to pref_pointer_
Set to start. Step 3: Repeat steps 4 to 6 for k = 1 to k tile_cnt. Step 4: loop_pref_pointer is converted to pref_pointer_
Reset to start. Step 5: Repeat step 6 for i = 1 to i M / 2. Step 6: [All steps of the core method of screening]

If a scan line does not start and end at an M tile boundary, the start and end portions of that scan line will be processed separately. These processes have only a partial inner loop (no required outer loop) where the preference matrix pointer indicates the starting entry.

The following is an analysis performed to calculate the throughput of the proposed method as compared to the current method. The comparison is performed by an instruction per one pixel processing. Instructions in this analysis refer to arithmetic or addressing operations. The terms used in this subject are: IPP _CM = all instructions per pixel using the prior art method LOOP−IPP _CM = all instructions per pixel executed by loop using the prior art method LS _CM = prior art method Setup instructions per pixel used IPP _PM = all instructions per pixel using the method of the invention LOOP-IPP-O _PM = all instructions per pixel (M odd) executed by a loop using the method of the invention LOOP-IPP− E _PM = all instructions per pixel (M even) executed by a loop using the method of the invention LS _PM = setup instructions per pixel using the method of the invention All terms above are scan lines of length L and preference matrix rows. This is the case of size M.

In the case of the prior art method, IPP _CM = LOOP−IPP _CM + LS _CM where LOOP−IPP _CM = (1+ (L / 2) * 1
1)) / L and L / 2 are the number of pixel pairs, and the number of instructions in the loop for one pixel pair is 11. LS _CM = 5 / L where the preference matrix (x mod M and y mo
The number of instructions to set up the pointer for dN) is five.

In the method of the present invention for an odd number M, IPP _PM = LOOP-IPP-O _PM + LS _PM where L >> 2M, LOOP-IPP-O _PM = (2+ (L
/ M) + (L * 9/2)) / L If L <2M, LOOP-IPP- _OPM = (2 + L +
(L * 9/2)) / L where the number of instructions in the inner loop for one pixel pair is 11
One instruction is for resetting the preference matrix pointer at the head of the array, that is, at the (M + 1) th or (M-1) th array in the outer loop. If L> M, LS _PM = 20 / L If L <M, LS _PM = 12 / L where the number of instructions for setting up the inner loop is 20 for L> M and 12 for L <M.

In the case of an even number M, in the method of the present invention, IPP _PM = LOOP-IPP-E _PM + LS _PM where L >> M, LOOP-IPP-E _PM = (2+ (L /
M) + (L * 9/2)) / L If L <M, LOOP-IPP-E _PM = (2 + L + (L
* 9/2)) / L where the number of instructions in the inner loop for one pixel pair is 11
One instruction is for resetting the preference matrix pointer at the head of the array, that is, at the (M + 1) th or (M-1) th array in the outer loop. If L> M, LS _PM = 20 / L If L <M, LS _PM = 12 / L where the number of instructions for setting up the inner loop is 20 for L> M and 12 for L <M. Note that the total number of setup instructions is based on the requirements set in the worst case. The total number of loops is determined assuming that a zero overhead loop counter is supported by the program flow control unit 130 of the digital image and graphics processors 71, 72, 73 and 74.
Moreover, it is assumed to be widely supported by digital signal processors.

FIG. 18 is a plot of the percentage reduction in processing time versus scan line length for the method of the present invention as compared to the prior art method. In FIG. 18, the processing time is considered to be directly related to the number of instructions. FIG. 18 shows (10) for M equal to 8, 9, 80 and 90 at various line lengths.
A plot of 0- (IPP _Pm * 100) / IPP _CM )% is shown. For line lengths longer than L_break, the proposed method shows an innovative increase in processing efficiency compared to current methods.
The break length L_break is 16 / (1-1 / M). For small line lengths, the overhead per pixel caused by the loop setup of the proposed method and the pointer reset outside the loop requires more instructions for scan lines than the prior art method. As the line length increases, the relative contribution of the overhead of the method of the invention decreases. The breakeven point is at L_break. Beyond L_break, the relative contribution of overhead decreases significantly,
Eventually it reaches a state of saturation that can be ignored. In the case of an odd number M as compared with the related art, the proposed method uses ((M−
1) Reduce on-chip memory requirements by * 100) / (2M)%, or less than 50%. For even M, for a long line length exceeding 180 pixels compared to the prior art,
The proposed method results in a reduction of 15.82% (for even M = 8, 9) and 18% (for even M = 80, 90). For odd M, for long line lengths exceeding 180 pixels compared to the prior art, the proposed method is up to 16.18.
% (Even M = 8, 9) and 18% (even M = 8)
0, 90). Processing efficiency is the length of the wire
It is innovatively improved when it is increased more than L_break and reaches saturation at various maximum improvement values for various M values. Typical line length for screening is L_break
Since it is much larger than (18 pixels), the proposed method has significant advantages.

The application of the proposed method is typically used in real-time multi-level threshold screening, which is an essential part of embedded raster image (RIP) software. Implementing screening on a multiprocessor integrated circuit 100 that has squeezed on-chip memory must balance memory requirements with processing time to satisfy real-time execution. The proposed method wisely allocates on-chip resources by using a processing loop with processing that has minimal overhead per pixel. Thus, the proposed method contributes to achieving the restriction of real-time embedded execution in terms of both memory and processing time. This concept can be easily extended even when the number of input bits and the number of output bits are different.

With respect to the above description, the following items are further disclosed. (1) In a computer-implemented method for approximating grayscale gradations using a more limited range imager, render an object represented in a page description language into a scan of the imager. Determining an image region having a rendered object based on the rendering; andscreening the scan input pixels to a more restricted range of image pixels within the image region having the rendered object, Not screening input pixels of the scan outside of the image area having the rendered object. (2) determining the image region comprises determining a bounding box surrounding all of the rendered objects and minimally surrounding the rendered objects, wherein the step of screening the input pixels comprises determining in which bounding box the input pixels The method of claim 1, further comprising screening, wherein the step of not screening input pixels comprises not screening input pixels that are outside all bounding boxes. (3) determining the image area comprises determining a scan line that includes a portion of the rendered object, and screening the input pixels includes determining the input pixel on any scan line that includes the portion of the rendered object; 2. The method of claim 1, further comprising screening, wherein the step of not screening the input pixels comprises not screening input pixels on any scan lines that do not include any portion of the rendered object.

(4) A transceiver capable of performing bidirectional communication through a communication channel, a memory, a print engine capable of arranging color dots on a print page in accordance with received image data and control signals, and A printer comprising a transceiver, the memory, and a programmable data processor connected to the print engine, the programmable data processor receiving print data for a page to be printed from the communication channel via the transceiver. Converting the print data into image data and control signals for supplying the print engine to the corresponding page for printing the corresponding page, including approximating the gray scale gradation. Indicates the target expressed in the page description language Rendering a scan of a page to be printed, determining an image region having a rendered object based on the rendering, an image of a more restricted range of input pixels of the scan within the image region having the rendered object Controlling the print engine in response to the image data and control signals to print the corresponding page, screening the pixels, not screening the input pixels of the scan outside of the image area having the rendered object. That the printer is configured to do. (5) Determine the image area by surrounding all rendered objects and determining the bounding box that minimally surrounds the rendered object, screening input pixels in any bounding box and out of all bounding boxes The printer of claim 4 wherein said data processor is further programmed to not screen input pixels. (6) determining a scan line that includes a portion of the rendered object, screening input pixels on any scan line that includes the portion of the rendered object, and inputting on any scan line that does not include the portion of the rendered object; The printer of claim 4, wherein said data processor is further programmed to not screen any pixels.

(7) A computer-implemented method for approximating grayscale gradations via a preference matrix using a more limited range imager, wherein each row of the preference matrix is divided into at least two fixed-size segments. Splitting; loading a look-up table associated with one of the segments of the preference matrix into cache memory; and via the look-up table associated with the one segment of the preference matrix. Screening input pixels such that all pixels on the selected scan line are located within the one segment of the preference matrix;
Loading a look-up table associated with the next segment of the preference matrix into a cache memory; and screening input pixels via the look-up table associated with the next segment of the preference matrix; When all the pixels on the selected scan line are located in the next segment of the preference matrix, and wherein the pixels of the selected scan line located in all segments of the preference matrix are Continuing until screened.

(8) A transceiver capable of performing bidirectional communication through a communication channel, a memory, a print engine capable of arranging color dots on a print page in accordance with received image data and control signals, and A printer comprising a transceiver, the memory, and a programmable data processor connected to the print engine, the programmable data processor transmitting print data corresponding to a page to be printed from the communication channel via the transceiver. Receiving the print data and printing the corresponding page, the print data is programmed to be converted into image data and control signals for providing to the print engine, wherein the conversion comprises converting each row of the preference matrix into at least two rows. Before splitting into two fixed dimension segments Loading a look-up table associated with one of the segments of a preference matrix into the cache memory; screening input pixels via the look-up table associated with the one segment of the preference matrix; Wherein all pixels on the selected scan line are located within the one segment of the preference matrix, and the look-up table associated with the next segment of the preference matrix is stored in the cache memory. Screening input pixels via the look-up table associated with the next segment of the preference matrix, wherein all pixels on the selected scan line are within the next segment of the preference matrix. , All segments of the preference matrix And a control unit for controlling the print engine in response to the image data and the control signal to print a corresponding page. Done, printer.

(9) A computer that packs two output pixels into a single data word while approximating grayscale gradations using a preference matrix with an odd row length using a more limited range imager. In the method of implementation, alternately consider M-1 input pixels and M + 1 input pixels so that each set of M-1 and M + 1 input pixels is even. Generating a corresponding pair of output pixels for each paired input pixels, and packing each pair of output pixels into a corresponding one output data word.

(10) A transceiver capable of performing bidirectional communication through a communication channel, a memory, a print engine capable of arranging color dots on a print page in accordance with received image data and control signals, and A printer comprising a transceiver, the memory, and a programmable data processor connected to the print engine, the programmable data processor transmitting print data corresponding to a page to be printed from the communication channel via the transceiver. Receiving the print data and converting the print data into image data and control signals for supplying the print engine to the print engine in order to print the corresponding page.
And M + 1 input pixels are considered alternately, such that each set of M-1 and M + 1 input pixels is even, for each pair of input pixels considered Generating a corresponding pair of output pixels and packing each pair of output pixels into a corresponding one of the output data words using an image forming device having a more limited range of gray scale tones. Packing the two output pixels into a single data word while approximating via a preference matrix with odd row length, and controlling the print engine in response to the image data and control signals to print the corresponding page A printer configured to do so.

(11) The present invention includes approximating the gray scale gradation using a more limited range image forming apparatus, that is, a process known as screening. The present invention reduces the time required for screening by identifying when screening is not needed. In the first embodiment, the rendering process (401)
Generates a minimum surrounding bounding box (403, 404) that surrounds all of the rendered objects.
In an alternative embodiment, focus is on a scan line that includes a portion of the rendered object (413). This screening improves memory usage by dividing each row of the preference matrix into segments. The look-up tables associated with these segments are sequentially loaded into the memory cache. Input pixels located in the loaded segment lookup table are screened. Thereafter, the look-up table associated with the next segment of the preference matrix is loaded into the memory cache and used to screen for input pixels located within that segment. Even if the preference matrix has an odd row length, the method considers M-1 input pixels and M + 1 input pixels alternately with M as the row length, thereby performing two-level screening while performing multilevel screening. Pack the output pixels into one data word.

[Brief description of the drawings]

FIG. 1 is a diagram showing a system architecture of an image processing system using the present invention.

FIG. 2 illustrates the architecture of a single integrated circuit multiprocessor that forms a preferred embodiment of the present invention.

FIG. 3 is a block diagram showing one of the digital image graphics processors shown in FIG. 2;

FIG. 4 is a schematic diagram illustrating pipeline stages of operations of the digital image graphics processor shown in FIG. 2;

FIG. 5 is a diagram showing the architecture of a master processor in a preferred embodiment of the present invention.

FIG. 6 is a diagram showing an integer pipeline operation of the master processor.

FIG. 7 is a diagram showing a floating-point pipeline operation of the master processor.

FIG. 8 is a diagram showing steps typically executed when printing a document specified in a page description language.

FIG. 9 is a diagram showing an application example of the bounding box method.

FIG. 10 is a diagram showing an application example of a scan line method.

FIG. 11 is a diagram showing the structure of a three-dimensional lookup table typically used in prior art screening.

FIG. 12 is a diagram showing an example of a 4 × 4 preference matrix.

FIG. 13 is a diagram illustrating a problem of the related art that occurs in the case of a preference matrix having a row size of an odd number of elements.

FIG. 14 schematically illustrates one aspect of the method of the present invention.

FIG. 15 illustrates a method of the present invention for processing a preference matrix having an odd number of row sizes.

FIG. 16 schematically illustrates a conventional method of indexing a lookup table for screening with a preference matrix having an odd number M.

FIG. 17 schematically illustrates a method of the invention for indexing a look-up table for screening with a preference matrix having an odd number M.

FIG. 18 is a diagram plotting the reduction rate of the processing time with respect to the line length of the method of the present invention as compared with the conventional method.

[Explanation of symbols]

 401 Rendering module 403, 405 Bounding box 407 Screening module 409 Page buffer 411 Printing 413 Scan line array

Continuation of front page (72) Inventor S. Rabiy India Karnataka, Bangalore, Ganganagar Extension, Force Cross, Second Maine, 70 (72) Inventor Vivek Kumar Sakul United States Texas, Plano, Fairmont 5901 (72) Inventor Earl. Srinivasan India Bangalore, Vijayanagal, Marushii Layout 69 F term (reference) 2C087 BA02 BA03 BA04 BA06 BA07 BA12 BC05 BD24 5B021 BB02 DD20 GG05 LG07 LG08 5B057 CA01 CA18 CB01 CB16 CE13 CE20 CH04 CH14

Claims (2)

[Claims] 1. A computer-implemented method for approximating grayscale tones using a more limited range imager, rendering an object represented in a page description language into a scan of the imager. Determining an image region having a rendered object based on the rendering; screening input pixels of the scan for a more restricted range of image pixels within the image region having the rendered object; Not screening the input pixels of the scan outside of the image area having the object. 2. A transceiver capable of bidirectional communication over a communication channel; a memory; a print engine capable of arranging color dots on a printed page in response to received image data and control signals; And a programmable data processor connected to the memory and the print engine, the programmable data processor receiving print data for a page to be printed from the communication channel via the transceiver. Programming the print data into image data and control signals for supplying the print engine to the corresponding page for printing the corresponding page, including approximating the grayscale gradations, the approximation comprising: Prints objects expressed in page description language Rendering a scan of the page to be rendered; determining an image region having a rendered object based on the rendering; a more restricted range of image pixels within the image region having the rendered object. Screening the input pixels of the scan outside the image area having the rendered object, and controlling the print engine in response to the image data and the control signal to print a corresponding page. , Configured to be performed by a printer.