Loading patent…
AssigneeSiemens Medical Solutions USA, Inc.
InventorsPascal Cathier, Senthil Periaswamy
Estimating the term…
A method of storing a digital image in a computer memory includes providing a N-dimensional digital image, defining an offset for each image element (x1, . . . , xN) by the formula offset ( x 1 , … , x N ) = ∑ i ∑ n = 1 N K x n ( i ) x ni , where i is summed over all bits and n is summed over all dimensions. The coefficient K for the ith bit of the nth dimension is defined as K x n ( i ) = ( ∏ j = 1 n - 1 f ( x j , 2 i + 1 , sx j ) ) 2 i ( ∏ j = n + 1 N f ( x j , 2 i , sx j ) ) , where xj is the jth dimension, f(x,G,sxj)=min(G,sxj−└x┘G) G is a power of 2, sxj represents the size associated with a given dimension, and └x┘G=x−x mod G. Image elements are stored in the computer memory in an order defined by the offset of each image element.
A method of addressing a digital image in a computer memory, said method comprising the steps of:
A method of addressing a digital image in a computer memory, said method comprising the steps of:
A method of addressing a digital image in a computer memory storage system, said method comprising the steps of:
A method of addressing a digital image in a computer memory storage system, said method comprising the steps of:
A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for addressing a digital image in a computer memory, said method comprising the steps of:
A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for addressing a digital image in a computer memory, said method comprising the steps of:
Dependencies are inferred from the claim text.
From the US filing history. Foreign family members aren’t listed.
Drawings are temporarily unavailable. Open the PDF at USPTO
About 10 months of term left · ends 6 Sep 2027 (estimated)
This invention relates to cache storage management in medical image processing.
Efficiency is an important factor for any real-life application development. In the field of image processing, the success of many theories is related to the existence of fast algorithms, e.g. Fast Fourier transforms or wavelets. Even simple concepts like distance transforms are still an active research field for increasing computation times.
When dealing with large volumetric images, however, a hardware issue known as cache-misses appears, and may become a bottleneck of an algorithm. In many cases, independently of the particular algorithm being used, the most time consuming task is accessing each voxel in the volumetric data. The reason for this is that many algorithms require a spatially local 3-D neighborhood (for example, convolution), and that the standard lexicographic storage order of pixels, for which spatially close points are often distant to each other in memory, causes many cache misses, which are very expensive.
FIG. 1 is a schematic diagram comparing a traditional image memory storage with a collimator image storage scheme according to an embodiment of the invention.
FIG. 2(a) is a schematic diagram illustrating image addressing according to an optimal storage ordering scheme according to an embodiment of the invention.
FIG. 2(b) is a schematic diagram illustrating image addressing according to a lexicographic ordering scheme according to an embodiment of the invention.
Exemplary embodiments of the invention as described herein generally include systems and methods for cache friendly memory addressing and ordering schemes. In the interest of clarity, not all features of an actual implementation which are well known to those of skill in the art are described in detail herein.
As used herein, the term “image” refers to multi-dimensional data composed of discrete image elements (e.g., pixels for 2-D images and voxels for 3-D images). The image may be, for example, a medical image of a subject collected by computer tomography, magnetic resonance imaging, ultrasound, or any other medical imaging system known to one of skill in the art. The image may also be provided from non-medical contexts, such as, for example, remote sensing systems, electron microscopy, etc. Although an image can be thought of as a function from R3 to R, the methods of the inventions are not limited to such images, and can be applied to images of any dimension, e.g. a 2-D picture or a 3-D volume. For a 2- or 3-dimensional image, the domain of the image is typically a 2- or 3-dimensional rectangular array, wherein each pixel or voxel can be addressed with reference to a set of 2 or 3 mutually orthogonal axes. The terms “digital” and “digitized” as used herein will refer to images or volumes, as appropriate, in a digital or digitized format acquired via a digital acquisition system or via conversion from an analog image.
An issue with traditional image memory storage in connection with image processing comes from the fact that voxels that are close to each other in the image volume are not necessarily close to each other in memory. Therefore, local operations may have to look to locations in memory that are far away and are thus not cached. More specifically, for all voxels, there is at least one direct neighbor that lies far away in memory. This arises from the fact that volumes are stored in lexicographic order: the first slice in stored, followed by the second, etc. Neighbors in the z direction are thus separated in memory by an entire slice, which can be quite big (for example, 512%512 unsigned shorts, i.e. 512 Kb). In an ideal case, the image would be stored so that close points in space are also close in memory, but this is not topologically possible. An alternative is to reduce the occurrence of memory-scattered neighborhoods.