Scan line rendering of convolutions

• US 6,580,836 B2
• Filed: 01/21/1998
• Issued: 06/17/2003
• Est. Priority Date: 01/24/1997
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Politis, George
• Primary Examiner(s): Wu, Jingge
• Application Number:
  US09/009,858
• Publication Number:
  US 20020085012A1
• Time in Patent Office: 1,973 Days
• Field of Search: 382/279, 382/307, 382/308, 708/420, 345/433, 345/435, 345/619-394, 345/547
• US Class Current: 382/279
• CPC Class Codes: G06T 5/20 using local operators

Abstract

A convolution operator is applied to an input image to produce an output image. Image pixel data corresponding to at least a predetermined number of scan lines of the input image is provided to a buffer memory adapted to store a portion of the image. The image data may be provided from a source of such data, or alternatively it may be rendered from an object graphics environment. A finite convolution mask is applied to the image pixel data to produce a scan line of the output image. The finite convolution mask has a plurality of coefficients arranged in a predetermined number of rows and a predetermined number of columns, and the predetermined number of scan lines substantially equals at least one of the number of rows or the number of columns of the convolution mask. In a preferred implementation, a scan line of the input image is discarded and a next scan line is provided for each scan line of the output image produced by the convolution.

Claims

1. A method of applying an operator having a finite mask to at least one object selected from a plurality of individually manipulable graphical objects in an image, the image being represented in an object-based graphics environment, said method comprising the steps of:

(a) providing an expression tree representation of the image, the expression tree comprising a plurality of nodes;

(b) associating a render number with at least one of the nodes, the or each render number specifying a number of scan lines to be rendered in advance of a current scan line for the associated node;

(c) providing the finite mask having a plurality of coefficients, wherein the coefficients are arranged in a predetermined number of rows and a predetermined number of columns;

(d) providing a buffer means adapted to store a portion of the at least one object in the image;

(e) rendering to the buffer means at least a predetermined number of scan lines of the at least one object in the image substantially equal to the number of rows or the number of columns of the mask; and

(f) applying the mask to the rendered plurality of scan lines to produce a scan line of an output image.

2. A method according to claim 1, wherein steps (e) and (f) are repeated to produce a plurality of scan lines of the output image, wherein in the rendering step (e) a scan line is discarded and a next scan line is rendered for each scan line of the output image.

3. A method according to claim 1, wherein the nodes are characterised as being either an operator or a primitive.

4. A method according to claim 1, wherein the coefficients of the mask are determined by an arbitrary function.

5. A method as in claim 1, wherein said number of scan lines in advance is related to the number of rows or number of columns of said operator.

6. A method as in claim 5, wherein there are a plurality of operators, and wherein said number of scan lines in advance is related to the cumulative effect of all the operators that apply to the node.

7. A method as claimed in claim 1, wherein the mask is a convolution mask.

8. A method as claimed in claim 1, wherein said predetermined number of scan lines includes at least one scan line rendered in advance of a current scan line.

9. A method of applying an operator having a finite mask to at least one object selected from a plurality of individually manipulable graphical objects in an image, the image being represented in an object-based graphics environment, said method comprising the steps of:

(a) providing an instruction sequence representation of the image;

(b) associating a render number with at least one instruction in the instructing sequence, the or each render number specifying a number of scan lines to be rendered in advance of a current scan line for the associated instruction;

(c) providing the finite mask having a plurality of coefficients, wherein the coefficients are arranged in a predetermined number of rows and a predetermined number of columns;

(d) providing a buffer means adapted to store a portion of the at least one object in the image;

(e) rendering to the buffer means at least a predetermined number of scan lines of the at least one object in the image substantially equal to the number of rows or the number of columns of the mask; and

(f) applying the mask to the rendered plurality of scan lines to produce a scan line of an output image.

10. A method according to claim 9, wherein a subset of said instruction sequence is assembled for the current scan line, said subset consisting only of those instructions which affect the current scan line.

11. A method as in claim 9, wherein said number of scan lines in advance is related to the number of rows or number of columns of said convolution operator.

12. A method as in claim in claim 11, wherein there are a plurality of operators, and wherein said number of scan lines in advance is related to the cumulative effect of all the operators that apply to the node.

13. A method as claimed in claim 9, wherein the mask is a convolution mask.

14. A method of rendering an image in an object-based graphics environment, the image being rendered by applying rendering operations to at least one object selected from a plurality of individually manipulable graphical objects in the image, wherein at least one said rendering operation is defined by a finite mask comprising a plurality of coefficients arranged in a predetermined number of rows and a predetermined number of columns, said method including the steps of:

(a) providing an expression tree representation of the image, the expression tree comprising a plurality of nodes;

(b) associating a render number with at least one of the nodes, the or each render number specifying a number of scan lines to be rendered in advance of a current scan line for the associated node;

(c) providing a buffer means for storing a portion of an input to the operation, wherein the portion comprises at least a predetermined number of scan lines of input data, the predetermined number of scan lines substantially equaling at least one of the number of columns or number of rows of the mask;

(d) applying the finite mask to the stored portion in the buffer means to produce a scan line of output that corresponds to the stored input portion; and

(e) utilizing the scan line of output in at least one subsequent said rendering operation for rendering the image.

15. A method according to claim 14, further comprising repeating steps (c) and (d) to produce a plurality of scan lines of output, wherein in step (c), a scan line is discarded and a next scan line is provided for each scan line of output.

16. A method according to claim 14, wherein the nodes are each selected from the group consisting of an operator and a primitive.

17. A method according to claim 14, wherein the coefficients of the mask are determined by an arbitrary function.

18. A method according to claim 14, wherein the buffer means is configured to retain a limited portion of the image substantially smaller than an entirety of the image.

19. A method as claimed in claim 14, wherein said mask is a convolution mask.

20. A method as claimed in claim 17, wherein the mask is a convolution mask.

21. A method as claimed in claim 14, wherein said predetermined number of scan lines includes at least one scan line rendered in advance of a current scan line.

22. A method of rendering an image in an object-based graphics environment, the image being rendered by applying rendering operations to at least one object selected from a plurality of individually manipulable graphical objects in the image, wherein at least one the rendering operation is defined by a finite mask comprising a plurality of coefficients arranged in a predetermined number of rows and a predetermined number of columns, said method including the steps of:

(a) providing an expression tree representation of the image, the expression tree comprising a plurality of nodes, wherein one or more said nodes have associated therewith a render number that specifies the number of scan lines to be rendered in advance of a current scan line;

(b) storing a portion of the at least one object in a buffer means, wherein the portion comprises at least a predetermined number of rendered scan lines of input data, the predetermined number of rendered scan lines substantially equaling at least one of the number of rows or the number of columns of the finite mask;

(c) applying the finite mask to the stored portion in the buffer means to produce a scan line of output that corresponds to the stored input portion;

(d) utilising the scan line of output in at least one subsequent said rendering operation for rendering the image; and

(e) repeating steps (b) and (c) to produce a plurality of scan lines of output, wherein in step (b) a scan line is discarded from the buffer means and a next scan line is provided for each scan line of output.

23. A method as claimed in claim 22, wherein the mask is a convolution mask.

24. A method as claimed in claim 22, wherein said predetermined number of scan lines includes at least one scan line rendered in advance of a current scan line.

25. Apparatus for applying an operator having a finite mask to at least one object selected from a plurality of individually manipulable graphical objects in an image, said image being represented in an object-based graphics environment, said apparatus comprising:

means for providing an expression tree representation of the image, the expression tree comprising a plurality of nodes;

means for associating, a render number with at least one node of the expression tree, the or each render number with at least one node of the expression tree, the or each render number specifying a number of scan lines to be rendered in advance of a current scan line for the associated node;

first means for providing said finite mask having a plurality of coefficients, wherein said coefficients are arranged in a predetermined number of rows and a predetermined number of columns;

buffer means adapted to store a portion of the at least one object in the image;

second means for rendering to said buffer means at least a predetermined number of scan lines of said at least one object in said image, said predetermined number of scan lines being substantially equal to the number of rows or the number of columns of said finite mask; and

third means for applying the finite mask to said plurality of scan lines to produce a scan line of an output image.

26. Apparatus according to claim 25, wherein for each scan line of said output image produced, said second means discards a previously rendered scan line from said buffer means and provides a further scan line of said input image to said buffer means.

27. Apparatus according to claim 26, wherein said buffer means is sized to store at least two scan lines of the at least one object in the image and said second means provides said scan lines of the at least one object in the image to said buffer means in line-by-line order.

28. Apparatus according to claim 27, wherein said buffer means is sized to store at least a band of scan lines of the at least one object in the image and said second means provides said scan lines of the at least one object in the image to said buffer means in band-by-band order, with a scan line of said band of the image being discarded from said buffer means after convolving with said mask to produce a scan line of said output image.

29. Apparatus according to claim 25, wherein said nodes are each selected from the group consisting of an operator and a primitive.

30. Apparatus according to claim 25, wherein the coefficients of the mask are determined by an arbitrary function.

31. Apparatus according to claim 25, wherein each of said buffer means and said second an third means comprise components of a computer system, said components including a processor of said computer system.

32. Apparatus as claimed in claim 25, wherein said operator is a convolution operator and the mask is a convolution mask.

33. Apparatus as claimed in claim 30, wherein the mask is a convolution mask.

34. Apparatus as claimed in claim 25, wherein said predetermined number of scan lines includes at least one scan lie rendered in advance of a current scan line.

35. Apparatus for applying an operator having a finite mask to at least one object selected from a plurality of individually manipulable graphical objects in an image, said image being represented in an object-based graphics environment, said apparatus comprising:

means for providing an instruction sequence representation, of the image;

means for associating a render number with at least one instruction in said instruction sequence, the or each render number specifying a number of scan lines to be rendered in advance of a current scan line for the instruction;

first means for providing said finite mask having a plurality of coefficients, wherein the coefficients are arranged in a predetermined number of rows and a predetermined number of columns;

buffer means adapted to store a portion of the at least one object in the image;

second means for rendering to said buffer means at least a predetermined number of scan lines of the at least one object in the image, said predetermined number of scan lines being substantially equal to the number of rows or the number of columns of said finite mask; and

third means for applying the finite mask to said plurality of scan lines to produce a scan line of an output image.

36. A computer program product comprising a computer readable medium having a computer program recorded thereon for applying an operator having a finite mask to at least one object selected from a plurality of individually manipulable graphical objects in an input image, the input image being represented in an object-based graphics environment, said computer program comprising:

code for providing an expression tree representation of the image, the expression tree comprising a plurality of nodes, wherein one or more nodes of the expression tree have associated therewith a render number that specifies the number of scan lines to be rendered in advance of a current scan line for the associated node;

code for providing the finite mask having a plurality of coefficients, wherein the coefficients are arranged in a predetermined number of rows and a predetermined number of columns;

code for rendering to a buffer means adapted to store a portion of said at least one object in said image at least a predetermined number of scan lines of the at least one object in the image substantially equal to the number of rows or the number of columns of the finite mask; and

code for applying the finite mask to said rendered plurality of scan lines to produce a scan line of an output image.

37. A computer program product according to claim 36, wherein said computer readable medium includes a disk storage device.

38. A computer program product according to claim 36, wherein said computer readable medium includes a computer network.

39. A computer program product as claimed in claim 36, wherein said operator is a convolution operator and the mask is a convolution mask.

40. A computer program product as claimed in claim 36, wherein said predetermined number of scan lines includes at least one scan line rendered in advance of a current scan line.

41. A computer program product comprising a computer readable medium having a computer program recorded thereon for rendering an image in an object-based graphics environment, the image being represented by an expression tree representation comprising a plurality of nodes, wherein one or more of the nodes have associated therewith a render number that specifies the number of scan lines to be rendered in advance of a current scan line, the image being rendered by applying rendering operations to at least one object selected from a plurality of individually manipulable graphical objects in the image, wherein at least one said rendering operation is defined by a finite mask comprising a plurality of coefficients arranged in a predetermined number of rows and a predetermined number of columns, said computer program comprising:

means for storing a portion of the at least one object in a buffer, wherein the portion comprises at least a predetermined number of rendered scan lines of input data, said predetermined number of rendered scan lines substantially equaling at least one of the number of columns or number of rows of said finite mask;

first means for applying the convolution mask to the stored portion in said buffer to produce a scan line of output that corresponds to the stored input portion; and

second means for utilising said scan line of output in at least one subsequent said rendering operation for rendering the image.