# US 2006/0050955 A1 · Load allocation when executing image processing using parallel processing

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2006/0050955 A1
- Document ID: US20060050955A1
- Status: Published application
- Kind: A1
- Application number: 11/212,430
- Filed: 2005-08-24
- Published: 2006-03-09
- Earliest claimed: 2004-08-25
- Assignees: Seiko Epson Corporation
- Inventors: Satoshi Yamazaki; Toshiaki Kakutani; Teruyuki Takata; Kohei Utsunomiya
- Web page: https://patentgrep.com/patent/US20060050955A1

## CPC

- H04N 1/46: Colour picture communication systems
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

For image processes performed repeatedly using a plurality of processing units on a plurality of partial images aligned mutually adjacent to each other, specified processing is performed. This image process includes (i) a first-type process segment on first partial image data representing a partial image to generate M types (M is an integer of 2 or greater) of second partial image data; and (ii) the respectively corresponding M types of second-type process segments on the M types of second partial image data. When executing image processing, parallel processing is performed for the second-type process segment relating to the i-th (i is a positive integer) partial image and the first-type process segment relating to any of the (i+1)-th to the (i+p)-th (p is a positive integer) partial images.

## Claims

### Claim 1

An image processing method comprising:
executing first-type processing on a first partial image data representing a partial image to generate a second partial image data;
executing second-type processing on the second partial image data; and
repeating the execution of the first and second-type processing on a plurality of partial images aligned to be adjacent to each other using a plurality of processing units, wherein
a first-type process segment and a second-type process segment are executed parallel using the plurality of processing units, the first-type process segment relating to i-th partial image, and the second-type process segment relating to any of (i+1)-th to (i+p)-th partial images, where i is a positive integer, and p is a positive integer.

### Claim 2 (depends on 1)

The method recited in claim 1, wherein
the first-type process segment converts the first partial image data represented by a first color system into image data represented by a second color system having M color components to generate M types of the second partial image data corresponding to the color components, and
the second-type process segment is halftone processing, where M is an integer of 2 or greater.

### Claim 3 (depends on 1)

The method recited in claim 1 further comprising:
(a) allocating process segments of a subject process segment set to the plurality of processing units in sequence, the subject process segment set including:
at least one second-type process segment which relates to i-th partial image but has not yet been allocated to one of the processing units; and
a plurality of first-type process segments which relate to (i+1)-th to (i+p)-th partial images but have not yet been allocated to the processing units; and
(b) executing the first and second-type process segments in the allocated sequence on allocated processing units respectively, where i is a positive integer, and p is a positive integer.

### Claim 4 (depends on 3)

The method recited in claim 3, further comprising
(c) before the step (a), estimating a load of the first-type process segment of the subject process segment set based on execution results of a preceding first-type process segment; and estimating a load of the second-type process segment of the subject process segment set based on execution results of a preceding second-type process segment of same type, wherein
the step (a) comprises:
(a1) selecting one process segment included in the subject process segment set according to a priority sequence of decreasing estimated loads; and allocating the selected process segment to a processing unit with a lowest total estimated load of process segments already allocated, and
(a2) repeating the step (a1).

### Claim 5 (depends on 1)

The method recited in claim 1 further comprising:
(a) selecting one process segment from among a subject process segment set including: at least one second-type process segment which relates to i-th partial image but has not yet been allocated to one of the processing units; and a plurality of first-type process segments which relate to (i+1)-th to (i+p)-th partial images but have not yet been allocated to the processing units; allocating the selected process segment to one of the plurality of processing units; and executing the selected process segment on the allocated processing units; and
(b) repeating the step (a), where i is a positive integer, and p is a positive integer.

### Claim 6 (depends on 5)

The method recited in claim 5, further comprising:
(c) before the step (a), estimating a load of the first-type process segment of the subject process segment set based on execution results of a preceding first-type process segment; and
estimating a load of the second-type process segment of the subject process segment set based on execution results of a preceding second-type process segment of same type, wherein
the step (a) comprising:
selecting a process with a biggest of the estimated loads within the subject process segment set;
allocating the selected process segment to a processing unit for which processes to be executed first run out; and
executing the selected process on the processing unit.

### Claim 7 (depends on 3)

The method recited in claim 3, wherein
the performing a first-type process segment includes generating M types of the second partial image data by performing the first-type process segment on the first partial image data,
the performing a second-type process segment includes performing corresponding M types of the second-type process segment on the M types of the second partial image data respectively,
the M types of the second partial image data includes a restricted process which is executable only after same type of process relating to a partial image immediately prior is completed, and
the subject process segment set further comprises a restricted process that relates to one of the (i+1)-th to (i+q)-th partial images; has not yet been allocated to one of the processing units; and
when it is assumed that the restricted process has been allocated to one of the processing units, a same type of restricted process relating to immediately prior partial image is completed at a scheduled time for starting execution of the restricted process, where M is an integer of 2 or greater, q is a positive integer.

### Claim 8 (depends on 7)

The method recited in claim 7, wherein
the subject process segment set further comprises a process that
is a non-restricted process that is not the restricted process among the second-type process segments;
relates to one of the (i+1)-th to (i+q)-th partial images; and
has not yet been allocated to one of the processing units, q is a positive integer.

### Claim 9 (depends on 8)

The method recited in claim 8, wherein
the first-type process segment converts the first partial image data represented by a first color system into image data represented by a second color system having M color components to generate M types of the second partial image data corresponding to the color components, and
the second-type process segment is halftone processing,
the restricted process is a halftone process performed using an error diffusion method, and
the non-restricted process is a halftone process performed using a dither method, where M is an integer of 2 or greater.

### Claim 10

An image processing device for image processing comprising:
a plurality of processing units for repeating execution of first and second-type processing on a plurality of partial images aligned to be adjacent to each other, wherein
the first-type processing is executed on a first partial image data representing a partial image to generate a second partial image data,
the second-type processing is executed on the second partial image data, and
a first-type process segment and a second-type process segment are executed parallel using the plurality of processing units, the first-type process segment relating to i-th partial image, and the second-type process segment relating to any of (i+1)-th to (i+p)-th partial images, where i is a positive integer, and p is a positive integer.

### Claim 11 (depends on 10)

The image processing device recited in claim 10
executing the first and second-type process segments by hyper threading, wherein
each of the processing units is a thread processing unit for processing thread.

### Claim 12 (depends on 10)

The image processing device recited in claim 10
in the first-type process segment, the first partial image data represented by a first color system is converted into image data represented by a second color system having M color components to generate M types of the second partial image data corresponding to the color components, and
the second-type process segment is halftone processing, where M is an integer of 2 or greater.

### Claim 13 (depends on 10)

The image processing device recited in claim 10 further comprising:
an allocation unit for allocating process segments of a subject process segment set to the plurality of processing units in sequence, the subject process segment set including:
at least one second-type process segment which relates to i-th partial image but has not yet been allocated to one of the processing units; and
a plurality of first-type process segments which relate to (i+1)-th to (i+p)-th partial images but have not yet been allocated to the processing units; and
an execution unit for executing the first and second-type process segments in the allocated sequence on allocated processing units respectively, where i is a positive integer, and p is a positive integer.

### Claim 14 (depends on 10)

The image processing device recited in claim 10 further comprising:
an allocation unit for
selecting one process segment from among a subject process segment set including: at least one second-type process segment which relates to i-th partial image but has not yet been allocated to one of the processing units; and a plurality of first-type process segments which relate to (i+1)-th to (i+p)-th partial images but have not yet been allocated to the processing units;
allocating the selected process segment to one of the plurality of processing units; and
executing the selected process segment on the allocated processing units, where i is a positive integer, and p is a positive integer.

### Claim 15

A computer program product for image processing comprising:
a computer readable medium; and
a computer program stored on the computer readable medium, the computer program comprising:
a first portion for executing first-type processing on a first partial image data representing a partial image to generate a second partial image data;
a second portion for executing second-type processing on the second partial image data; and
a third portion for repeating the execution of the first and second-type processing on a plurality of partial images aligned to be adjacent to each other using a plurality of processing units, wherein
a first-type process segment and a second-type process segment are executed parallel using the plurality of processing units, the first-type process segment relating to i-th partial image, and the second-type process segment relating to any of (i+1)-th to (i+p)-th partial images, where i is a positive integer, and p is a positive integer.

### Claim 16 (depends on 15)

The computer program product recited in claim 15, wherein
the third portion executes the first and second-type process segments by hyper threading, wherein
each of the processing units is a thread.

### Claim 17 (depends on 15)

The computer program product recited in claim 15, wherein
in the first-type process segment, the first portion converts the first partial image data represented by a first color system into image data represented by a second color system having M color components to generate M types of the second partial image data corresponding to the color components, and
the second-type process segment is halftone processing, where M is an integer of 2 or greater.

### Claim 18 (depends on 15)

The computer program product recited in claim 15, wherein
the third portion includes:
a forth portion for allocating process segments of a subject process segment set to the plurality of processing units in sequence, the subject process segment set including:
at least one second-type process segment which relates to i-th partial image but has not yet been allocated to one of the processing units; and
a plurality of first-type process segments which relate to (i+1)-th to (i+p)-th partial images but have not yet been allocated to the processing units; and
a fifth portion for executing the first and second-type process segments in the allocated sequence on allocated processing units respectively, where i is a positive integer, and p is a positive integer.

### Claim 19 (depends on 15)

The computer program product recited in claim 15, wherein
the third portion includes:
a fourth portion for
selecting one process segment from among a subject process segment set including:
at least one second-type process segment which relates to i-th partial image but has not yet been allocated to one of the processing units; and
a plurality of first-type process segments which relate to (i+1)-th to (i+p)-th partial images but have not yet been allocated to the processing units;
allocating the selected process segment to one of the plurality of processing units; and
executing the selected process segment on the allocated processing units; and
a fifth portion for having the fourth portion execute repeatedly, where i is a positive integer, and p is a positive integer.
