Image analysis – Image transformation or preprocessing – Convolution
Reexamination Certificate
1998-01-21
2003-06-17
Wu, Jingge (Department: 2623)
Image analysis
Image transformation or preprocessing
Convolution
C345S619000, C345S547000
Reexamination Certificate
active
06580836
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to image convolution techniques and, in particular, to performing convolutions of digital images or object-based graphics in a scan line rendering environment.
BACKGROUND ART
Current image convolution systems perform image convolutions using semiconductor memory frame buffers. However, this has the potential of limiting the size of an image on which convolutions can be applied to what can be stored in available memory, especially where high speed rendering of an image is required. Further, current systems allow convolutions to be applied only to images formed of pixel-based image data, and not in general to images formed from object-based graphic image data.
With reference to
FIG. 1
, a convolution of an image with an arbitrary mathematical function can be defined as follows. An image
10
can be denoted by a function I(x,y) where x is a position horizontally along a scan line
11
and y is a position vertically down the image
10
from the top left hand corner of the image
10
. A pixel
12
with pixel integer coordinates p and q has a value returned by the function I(x,y) in the region p≦x≦p+1, q≦y+1. In practice, an image is usually represented as a series of colour components, for example, red, green and blue known as RGB-values. Thus, I(x,y) usually denotes several functions, one for each colour component, I
R
(x,y), I
G
(x,y) and I
B
(x,y). The convolution of the image
10
with a predetermined function f(x,y) is mathematically defined as
I
⊗
f
=
∫
-
∞
∞
∫
-
∞
∞
I
(
u
,
v
)
f
(
x
-
u
,
y
-
v
)
ⅆ
u
ⅆ
v
,
(
EQ
1
)
where, in theory, f can be defined over any finite or infinite domain. In practical terms, a convolution is usually performed by representing f(x,y) by a finite mask
21
(also known as a kernel) k
ij
, i=−m, . . . , m, j=−n, . . . , n shown in FIG.
2
and represented so that the centre element, or coefficient of the mask, is the k
00
element
22
. The convolution is calculated at each pixel (p,q) as
∑
i
=
-
m
+
m
∑
j
=
-
n
+
n
I
(
p
+
i
,
q
+
j
)
k
ij
,
(
EQ
2
)
where the use of I denotes a series of independent calculations on each colour component as required.
FIG. 3
shows a calculation of a convolution in accordance with the finite mask
21
of FIG.
2
. Each pixel
31
in an output image
32
depends upon a neighbourhood of a plurality of pixels
33
across a multitude of scan lines of an input image
34
. In conventional systems, a full image semiconductor frame buffer is used to store the input image
34
in its entirety, so that there is no difficulty in accessing this neighbourhood region of pixels.
Throughout this specification, unless otherwise noted, a reference to “memory” is to be construed as a reference to high data transfer rate, preferably a low access time memory, such as semiconductor-based random access memory, which provides substantially higher data transfer rates and lower access times than, for example, a hard disc (magnetic) memory or optical disc memory. Other examples of a high data transfer rate, low access time memory include a bubble memory and mercury delay line memory, and the like.
However, the use of a frame buffer for image convolutions, amongst other image manipulation processes, poses a number of problems and disadvantages. Firstly, although the cost of such memory has dropped over the past few years, such memory remains relatively expensive. Hence, the capacity of such memory as typically used in computer systems, it is often consumed by the simultaneous execution of an operating system and one of more application programs all of which tend to use fast memory resources prior to utilizing slow memory (eg. hard disk) for intermediate storage. Further, the provision of a frame buffer encourages the rendering of graphical objects into pixel-based form thus occupying further memory resources and compounding the above noted problem.
It is therefore an object of the present invention to substantially overcome, or ameliorate, one or more difficulties associated with prior art arrangements.
SUMMARY OF THE INVENTION
The present invention provides for the use of scan line buffers (or band buffers) rather than with conventional frame buffers to perform image convolution operations, and such becomes particularly advantageous when dealing with graphical object-based images.
In accordance with one aspect of the present invention there is provided a method of applying a convolution operator to an image, the method comprising the steps of:
(a) providing a finite convolution mask having a plurality of coefficients, wherein the coefficients are arranged in a predetermined number of rows and a predetermined number of columns;
(b) providing a buffer means adapted to store a portion of the image;
(c) rendering to the buffer means at least a predetermined number of scan lines of the image substantially equal to the number of rows or the number of columns of the convolution mask; and
(d) applying the convolution mask to the rendered plurality of scan lines to produce a scan line of an output image.
Preferably, steps (c) and (d) are repeated to produce a plurality of scan lines of the output image, wherein at the rendering step (c) a scan line is discarded and a next scan line is rendered for each scan line of the output image.
Most preferably, the image is represented in an object-based graphics environment. In such a case, the image is represented by an expression tree representation comprising a plurality of nodes. Typically the nodes are characterised as being either an operator or a primitive. Alternatively the image may be represented by an instruction sequence or by a hierarchical data representation. Generally one or more nodes of the expression tree or each instruction of the instruction sequence have associated therewith a render number. Typically the render number represents the number of scan lines to be rendered in advance of a current scan line for the node or instruction.
Preferably the coefficients of the mask are determined by an arbitrary function.
According to another aspect of the present invention there is disclosed a method of applying a convolution operator to an input image to produce an output image, the method comprising the steps of:
(a) providing to a buffer means adapted to store a portion of the image, image pixel data corresponding to at least a predetermined number of scan lines of the image; and
(b) applying a finite convolution mask to the image pixel data to produce a scan line of the output image, wherein 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.
According to another aspect of the present invention there is disclosed a method of applying a convolution operator to an image represented at least graphical object in an object-based graphics environment, the method comprising the steps of:
(a) providing a finite convolution mask having a plurality of coefficients, wherein the coefficients are arranged in a predetermined number of rows and a predetermined number of columns;
(b) providing a buffer means adapted to store a portion of the image;
(c) rendering at least a predetermined number of scan lines of the at least one graphical object to the buffer means, the predetermined number of scan lines being substantially equal to the number of rows or the number of columns of the convolution mask;
(d) applying the convolution mask to the rendered plurality of scan lines to produce a scan line of an output image.
(e) repeating steps (c) and (d) to produce a plurality of scan lines of the output image, wherein at the rendering step (c) a scan line is discarded from the buffer means
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Wu Jingge
LandOfFree
Scan line rendering of convolutions does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scan line rendering of convolutions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scan line rendering of convolutions will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3106235