Image analysis – Image transformation or preprocessing
Reexamination Certificate
2000-07-13
2004-08-24
Couso, Yon J. (Department: 2723)
Image analysis
Image transformation or preprocessing
C382S277000
Reexamination Certificate
active
06782138
ABSTRACT:
FIELD
The present invention relates to processing data, and more particularly to processing multidimensional data.
BACKGROUND
Many multidimensional data processing algorithms are based on multiresolution decompositions. These algorithms include, for example, compression algorithms, noise removal algorithms, and algorithms for the reconstruction of images. The more efficiently these algorithms operate, the better the modern communications and information processing systems in which they are embedded operate. For example, efficient compression algorithms permit fast transmission of information in communication systems. Without efficient compression algorithms, multidimensional data requires an unacceptable amount of bandwidth for transmission and an unacceptable amount of storage for archiving.
Consider, for example, a medical image, such as a mammographic screening image, which may be represented by four six-thousand pixel by six-thousand pixel arrays. A mammographic screening image consists of four images, two images for each of two breasts. Of the two images associated with each breast, one image is a top image and one image is a side image. A pixel is a “picture element,” which is an elementary unit of information contained in an image and is typically represented by an intensity level. If each pixel in the mammographic screening image is represented by sixteen bits, then each pixel may be encoded at one of 65,536 possible intensity levels. To transmit the mammographic screening image without compression, 2.3 billion bits must be sent over a communication link. A typical telephone line is capable of transmitting about 56,000 bits per second, so transmission of a mammographic screening image would require more than ten hours. A ten hour transmission time is unacceptable for transmitting a mammographic screening image, so image compression processing is used to reduce the transmission time.
Prior to processing multidimensional data using some compression methods, such as wavelet compression, the multidimensional data is approximated at several resolution levels. For example, two-dimensional image data is initially divided into two rows and two columns. Each row and each column is subsequently divided into two rows and two columns.
FIG. 1
is an illustration of a sequence of images
100
, including images
101
,
103
,
105
, and
107
, of multidimensional data partitioned into rows and columns. The images
101
,
103
,
105
, and
107
illustrate partitioning a first dimensions
109
(rows) and a second dimension
111
(columns) at a rate of one. Image
101
is partitioned in the first dimension
109
and the second dimension
111
. Each of the partitions in image
101
is partitioned or divided to form image
103
. Each of the partitions in image
103
are partitioned or divided to form image
105
. And each of the partitions in image
105
are partitioned or divided to form image
107
. The partitioning or subdividing of rows and columns continues until an acceptable resolution level is achieved. An acceptable resolution level is a level at which data can be compressed, transmitted, and decompressed, such that the decompressed data includes the information contained in the original data required by a viewer of the received data. For example, in the mammographic screening example described above, the decompressed data must contain enough information related to a cancerous tumor to allow a radiologist to identify the cancerous tumor by viewing the mammographic screening images reconstructed from the compressed data.
Isotropic decomposition is one type of decomposition used in some multidimensional data processing algorithms. To perform isotropic decomposition, one begins with a function &phgr; of one variable such that the set
{&phgr;(
x−j
)|
j&egr;
}
forms a Riesz basis for the span of these functions. Assume that &phgr; satisfies the rewrite rule
φ
(
x
)
=
∑
j
a
j
φ
(
x
-
j
)
(
1
)
for a finite set of coefficients &agr;
j
. Let S
k
be the space of all functions
S
k
:=
{
∑
j
c
j
φ
(
2
k
x
-
j
)
&RightBracketingBar;
c
j
∈
ℝ
}
and choose a bounded projection P
k
from L
p
(
) to S
k
. Under certain conditions (see Daubechies) any ƒ&egr;L
p
(
) can be re-written as
f
=
lim
k
->
∞
P
k
=
P
0
f
+
∑
k
=
1
∞
(
P
k
f
-
P
k
-
1
f
)
where, because of the rewrite rule (1), P
k
ƒ−P
k−1
ƒ is in S
k
. Thus, since P
0
ƒ&egr;S
0
,
f
=
P
0
f
+
∑
k
=
1
∞
(
P
k
f
-
P
k
-
1
f
)
=
∑
j
∈
Z
d
j
φ
(
·
-
j
)
+
∑
k
=
1
∞
∑
j
∈
Z
d
j
,
k
φ
(
2
k
·
-
j
)
.
For suitable functions &phgr; and special projectors P
k
, one can find a function &psgr;, associated with &phgr;, such that
P
k
f
-
P
k
-
1
f
=
∑
j
∈
Z
c
j
,
k
-
1
ψ
(
2
k
-
1
·
-
j
)
(note the new scaling −2
k−1
instead of 2
k
) so that
f
=
∑
j
∈
Z
d
j
φ
(
·
-
j
)
+
∑
k
=
0
∞
∑
j
∈
Z
c
j
,
k
ψ
(
2
k
·
-
j
)
.
For a function ƒ:
→
a similar decomposition holds. Define a set &PSgr; of 2
d
−1 functions defined for x=(x
1
, . . . , x
d
)&egr;
by
Ψ
:=
{
∏
i
=
1
d
v
i
(
x
i
)
&LeftBracketingBar;
v
i
=
φ
or
v
i
=
ψ
}
\
{
∏
i
=
1
d
φ
(
x
i
)
}
together with the function
Φ
(
x
)
=
∏
i
=
1
d
φ
(
x
i
)
.
Then, under suitable conditions, any ƒ in L
p
(
) can be written as
f
=
∑
j
∈
Z
d
d
j
Φ
(
·
-
j
)
+
∑
k
=
0
∞
∑
j
∈
Z
d
∑
ψ
∈
Ψ
c
j
,
k
ψ
(
2
k
·
-
j
)
.
Note that, since x=(x
1
, . . . , x
d
) and the multi-index j=(j
1
, . . . , j
d
),
&psgr;(2
k
x−j
)=&psgr;(2
k
x
1
−j
1
, . . . , 2
k
x
d
−j
d
),
i.e., each of the components x
i
of x has been scaled by the same amount, 2
k
.
One disadvantage of isotropic decomposition is that not all data is isotropic, and anisotropic multidimensional data is not efficiently processed by algorithms based on isotropic decomposition.
For these and other reasons there is a need for the present invention.
SUMMARY
According to one aspect of the present invention, a method is described for forming multi-resolution representations of data. The method includes the operations of partitioning the data in a first dimension at a first rate, and partitioning the data in a second dimension at a second rate, wherein the first rate is not equal to the second rate.
REFERENCES:
patent: 5402148 (1995-03-01), Post et al.
patent: 5727092 (1998-03-01), Sandford, II et al.
patent: 5745392 (1998-04-01), Ergas et al.
patent: 5828849 (1998-10-01), Lempel et al.
patent: 5901249 (1999-05-01), Ito
patent: 6009208 (1999-12-01), Mitra et al.
patent: 6289137 (2001-09-01), Sugiyama et al.
patent: 6345126 (2002-02-01), Vishwanath et al.
patent: 6385248 (2002-05-01), Pearlstein et al.
patent: 6389180 (2002-05-01), Wakisawa et al.
Leisner Christopher J.
Lucier Bradley J.
Couso Yon J.
Purdue Research Foundation
Schwegman Lundberg Woessner & Kluth P.A.
LandOfFree
Method and system for processing multidimensional data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for processing multidimensional data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for processing multidimensional data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3335020