Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1998-07-01
2001-02-27
Au, Amelia (Department: 2723)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S305000
Reexamination Certificate
active
06195463
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a storage device, and more particularly to a storage device which is preferably used for hierarchical encoding and storing of image data.
2. Description of the Related Art
There is a method for encoding high-resolution image data called “hierarchical encoding”, wherein high-resolution image data is used as image data of the lowest hierarchy or first hierarchy and image data of a second hierarchy with fewer pixels than the image data of the first hierarchy is formed, image data of a third hierarchy with fewer pixels than the image data of the second hierarchy is formed, and so on until image data is formed to the highest hierarchy. The image data for each hierarchy is displayed on a monitor with resolution or number of pixels corresponding to that hierarchy. The user is able to select the hierarchically encoded image data corresponding with his/her monitor, and thus view corresponding contents.
However, considering an arrangement in which image data of a certain resolution is used as the image data for the lowest hierarchy or first hierarchy, image data of higher hierarchies is sequentially formed and the hierarchically encoded image data is stored or transferred, extra storage capacity or transferring capacity becomes necessary as compared to arrangements in which only the image data of the lowest hierarchy is stored or sent, because of the increased data of the upper hierarchies.
Accordingly, the present Applicant has in the past proposed a hierarchical encoding method in which there is no increase in storage capacity or the like.
For example, let us consider an arrangement in which the average value of 4 pixels formed of 2 by 2 pixels on the lowest hierarchy is used as the image value of the upper hierarchy, whereby 3-tier hierarchical encoding is performed. As shown in
FIG. 1A
, the average value m
0
of the 4 pixels h
00
, h
01
, h
02
, and h
03
, these being the 2 by 2 pixels to the upper left of the 8 by 8 pixels, this m
0
comprising 1 pixel to the upper left in the second hierarchy. In the same manner, the average value m
1
of the 4 pixels h
10
, h
11
, h
12
, and h
13
to the upper right of the image of the lowest hierarchy, the average value m
2
of the 4 pixels h
20
, h
21
, h
22
, and h
23
to the lower left thereof, and the average value m
3
of the 4 pixels h
30
, h
31
, h
32
, and h
33
to the lower right thereof, are calculated, these each comprising 1 pixel to the upper right, lower left, and lower right of the second hierarchy. Further, the average value q of the 4 pixels m
0
, m
1
, m
2
, and m
3
, these being the 2 by 2 pixels comprising the second hierarchy, is calculated, this average value q being used as the pixel of the image of the highest hierarchy.
In order to store or transfer all the pixels h
00
through h
03
, h
10
through h
13
, h
20
through h
23
, h
30
through h
33
, m
0
through m
3
, and q, in that form without any change, storage capacity equal to m
0
through m
3
and q becomes necessary.
As shown in
FIG. 1B
, let us say that the pixel q of the third hierarchy is placed in the position of the lower right pixel m
3
of the pixels m
0
through m
3
in the second hierarchy. The second hierarchy is thus comprised of the pixels m
0
through m
2
and q.
As shown in
FIG. 1C
, let us say that the pixel m
0
of the second hierarchy is placed in the position of the lower right pixel h
03
of the pixels h
00
through h
03
in the third hierarchy used to obtain the pixel m
0
. The remaining pixels of the second hierarchy, m
1
through m
2
and q are also positioned in the place of the pixels h
13
, h
23
, and h
33
of the first hierarchy. The pixel q has not been directly obtained from pixel h
30
through h
33
, but exists on the second hierarchy instead of the pixel m
3
which has been directly obtained from the pixels h
30
through h
33
, and so pixel q is positioned on the place of the pixel h
33
, instead of pixel m
3
.
As shown in
FIG. 1C
, the entire number of pixels is 4 by 4 pixels totaling 16 pixels, which is unchanged from the number of pixels of the lowest hierarchy as shown in FIG.
1
A. Thus, increase in required storage capacity and the like can be prevented.
Decoding of the pixel m
3
which has been replaced with pixel q and of the pixels h
03
, h
13
, h
23
, and h
33
which have been respectively replaced with pixels m
0
through m
3
is performed as follows.
q is the average value of m
0
through m
3
, so the expression q=(m
0
+m
1
+m
2
+m
3
)/4 holds. Hence, m
3
can be obtained by the expression m
3
=4×q−(m
0
+m
1
+m
2
).
Also, m
0
is the average value of h
00
through h
03
, so the expression m
0
=(h
00
+h
01
+h
02
+h
03
)/4 holds. Hence, h
03
can be obtained by the expression h
03
=4×m
0
−(h
00
+h
01
+h
02
). Also, h
13
, h
23
, and h
33
can be obtained in the same way.
Known arrangements for performing such hierarchical encoding have involved general-use memory such as SRAM (Static Random Access Memory) or DRAM (Dynamic RAM) for storing the hierarchical encoding results being provided externally with an adder for calculating the average values, a shifter, a delay circuit for line delay, and so forth.
In the case shown in
FIG. 1C
, in order to obtain the pixel m
0
of the second hierarchy, the expression m
0
=(h
00
+h
01
+h
02
+h
03
)/4 must be calculated. To that end, an adder for adding the values in the parenthesis, and a shifter for dividing the addition results by 4, i.e., to shift 2 bits to the right, are needed.
Further, in order to obtain the pixel m
0
of the second hierarchy, the pixels h
00
through h
03
which exist over two lines in the first hierarchy become necessary. Supplying of image data to the memory is generally performed in the order of raster scanning. Reading and writing of the image data to the memory is also performed in the order of raster scanning, i.e., one line at a time.
The line that begins with h
00
is delayed one line worth in the delay circuit, waits for the line beginning with h
02
to be supplied, then calculates m
0
, following which the line beginning with h
00
and the line beginning with h
02
are written to the memory.
In this way, known arrangements required that various types of circuits be provided externally to the memory, increasing the size of the device. There has also been the problem in that the various types of circuits provided externally to the memory restricted the processing speed of the overall device.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a storage device, information processing method, and information processing apparatus to solve the above-described problems.
In order to achieve the above object, the present invention provides a storage device, comprising: computing device for computing higher order hierarchy data from lower order hierarchy data; and memory for storing the lower order hierarchy data and the higher order hierarchy data; wherein the computing device and the memory are formed on a single chip.
Also, in order to achieve the above object, the present invention provides an information processing method, comprising: a step for storing the lower order hierarchy data in memory; a step for computing higher order hierarchy data from certain lower order hierarchy data by means of a computing unit provided on the chip on which the memory is formed; and a step for storing the higher order hierarchy data in memory.
Further, in order to achieve the above object, the present invention provides an information processing apparatus having a storage device, the memory comprising: computing device for computing higher order hierarchy data from lower order hierarchy data; and storage means for storing the lower order hierarchy data and the higher order hierarchy data; wherein the computing device and the storage means are formed on a single chip.
REFERENCES:
patent: 4870497 (1989-09-01), Chamzas et al.
patent: 5448310
Kondo Tetsujiro
Nakaya Hideo
Watanabe Tsutomu
Au Amelia
Frommer William S.
Frommer Lawrence & Haug LLP.
Johnson Timothy M.
Sony Corporation
LandOfFree
Multiresolution image processing and storage on a single chip does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiresolution image processing and storage on a single chip, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiresolution image processing and storage on a single chip will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2606362