Image analysis – Image transformation or preprocessing – General purpose image processor
Reexamination Certificate
1998-10-05
2001-04-17
Au, Amelia (Department: 2723)
Image analysis
Image transformation or preprocessing
General purpose image processor
C382S205000, C382S304000, C345S505000
Reexamination Certificate
active
06219466
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to improved techniques for pixel data propagation using a linearly connected array of processors, and more specifically to such techniques via which pixel data propagation within a two-dimensional image is implemented at a considerably high speed.
2. Description of the Related Art
In order to specify or distinguish a region from others within a two-dimensional digital image, it is known in the art to use a so-called “parallel propagation processing technique” using a linear processor array. According to this technique, starting from one or more distinctive pixels in the two-dimensional digital image, unique pixel data is written into in parallel to the surrounding pixels. This technique is applicable to the case where a plurality of regions within a two-dimensional image are to be distinguished by labeling different unique numbers to respective regions. Further, the above mentioned technique is also used to determine a shape of a region in a two-dimensional image by tracing the contour thereof. A linear processor array per se is well known in the art, which is disclosed in U.S. Pat. Nos. 5,319,586 and 5,630,154 merely by way of example.
Before turning to the present invention, it is deemed preferable to briefly describe a conventional technique with reference to
FIGS. 1A-1C
and
2
.
FIG. 1A
is a diagram schematically showing a two-dimensional pixel image
10
which consists of X by Y pixels. For the sake of simplifying the disclosure, the image
10
is such as to include a region
12
to be specified for later operations which are irrelevant to the present invention. In order to distinguish the region
12
from the remaining portion of the image
10
, it is necessary to write unique data into each pixel of the region
12
. In brief, the present invention is concerned with the writing of such unique data into an area to be distinguished.
Referring to
FIG. 1B
, there is shown part of a conventional parallel image processing apparatus
13
which comprises a plurality of local memories
14
(
1
)-
14
(X), a plurality of buffers
16
(
1
)-
16
(X), and a plurality of processing elements (PEs)
18
(
1
)-
18
(X). More specifically, the PEs
18
(
1
)-
18
(X) are respectively assigned to the one-line pixels stored in the local memories
14
(
1
)-
14
(X). The image
10
of
FIG. 1A
is written into the local memories
14
(
1
)-
14
(X) each of which stores one-column (or one-line) pixel data. A controller
20
controls the overall operation of the PEs
18
(
1
)-
18
(X).
Assuming that if a given buffer stores a pixel from which the data propagation process is to be initiated, the PE assigned to the buffer in question has already written or registered the address of the propagation start pixel in the buffer.
FIG. 1C
is a diagram showing part of the arrangement of FIG.
1
B. In
FIG. 1C
, a center pixel (or reference pixel) in the buffer
14
(N) (1<N<X) is a pixel from which data propagation may be implemented to the pixel positions
1
-
8
which surrounds the center pixel. To be more precise, the pixel positions
1
-
8
are the possible positions to which a unique data can be propagated. That is, prior to implementing the data propagation, it is necessary to check if the data propagation should be implemented to each pixel position. It is understood that if the pixel position
1
is outside the region to be specified, the data propagation to the position
1
is not permitted. The operations of propagating the data of the center pixel (or reference pixel position) to one of the surrounding pixels are identical with one another, and hence, only the operation from the center pixel to the pixel position
1
will be described with reference to FIG.
2
.
In
FIG. 2
, at step
30
, a check is made to determine if data propagation to the pixel position
1
is necessary. If the answer is negative, the operation is terminated. Otherwise, the program goes to step
32
at which the PE
18
(N) propagates a unique data to the right neighboring (adjacent) PE
18
(N+1). At step
34
, PE
18
(N) transfers the address of the position
1
to PE(N+1). Following this, at step
36
, PE(N+1) writes the unique data propagated from PE(N) to the position
1
whose address has been informed from PE(N). At step
38
, PE(N+1) registers the address information of pixel position
1
at the buffer.
The above mentioned conventional technique, however, suffers from the problem that the number of processing steps becomes very large. That is, as shown in
FIG. 2
, four steps
32
,
34
,
36
and
38
are necessary at each iteration. Further, if the unique data at the center pixel should be propagated to all the eight surrounding positions
1
-
8
, PE(N) must implement three times of data propagation to each of the right and left adjacent processing elements PE(N−1) and PE(N+1). In addition, PE(N) must carry out the data propagation two times within itself in connection with the position
2
and
7
.
SUMMARY OF THE INVENTION
If is therefore an object of the present invention to provide an apparatus for implementing pixel data propagation using a linear processor array at a high speed relative to a conventional technique.
The object is fulfilled by improved techniques wherein an image processing apparatus is provided with a linear processor array which includes a plurality of linearly coupled processing elements. The apparatus further includes a plurality of local memories each of which takes a form of one-dimensional pixel data memories. The local memories are respectively assigned to the plurality of processing elements. Further, the local memories are arranged so as to store in combination a two-dimensional pixel image to be processed. A plurality of buffers are respectively assigned to the processing elements. Each buffer stores pixel location information of at least one center pixel from which a unique pixel value is to be propagated if the center pixel exists on a corresponding local memory. With the arrangement mentioned above, in order to accelerate pixel data propagation in the two-dimensional pixel image, a plurality of register units are respectively assigned to the plurality of processing elements. Each register can be accessed by the adjoining processing elements and has first to third memory fields. The first memory field receives the at least one center pixel from the associated buffer. The second memory field stores the unique pixel data. The third memory field stores pixel positions which surround the center pixel and to which the unique pixel data should be propagated.
One aspect of the present invention resides in
1
. An image processing apparatus comprising: a linear processor array which includes a plurality of linearly coupled processing elements; a plurality of local memories each taking a form of one-dimensional pixel data memories, said local memories being respectively assigned to said plurality of processing elements, said plurality of local memories being arranged so as to store in combination a two-dimensional pixel image to be processed; a plurality of buffers respectively assigned to said plurality of processing elements, each of said buffers storing pixel location information of at least one center pixel from which a unique pixel value is to be propagated if said center pixel exists on a corresponding local memory; and a plurality of register units respectively assigned to said plurality of processing elements, each register being accessed by adjoining processing elements and having first to third memory fields, said first memory field receiving said at least one center pixel from the associated buffer, said second memory field storing the unique pixel data, and said third memory field storing pixel positions which surround the center pixel and to which the unique pixel data should be propagated.
REFERENCES:
patent: 4484346 (1984-11-01), Sternberg et al.
patent: 5048108 (1991-09-01), Basille et al.
patent: 5117468 (1992-05-01), Hino et al.
patent: 5136662 (199
Au Amelia
Foley & Lardner
NEC Corporation
Wu Jingge
LandOfFree
Apparatus for implementing pixel data propagation using a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for implementing pixel data propagation using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for implementing pixel data propagation using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2475203