High performance data layout and processing

A method, a system, and a computer-readable medium are provided which provide an efficient data layout for image data and fast access to samples of an image stored in hierarchical z-order format. An array of image data of a physical entity is ordered in a hierarchical z-order at a computing device. Data blocks are created from the array ordered based on the hierarchical z-order. Data files containing a predetermined number of successive data blocks are created from the created data blocks. A directory structure is created in a file system of a second computing device based on the hierarchical z-order. The created data files are stored in the created directory structure based on the hierarchical z-order.

BACKGROUND

Gigapixel and larger images are becoming increasingly popular due to the availability of high-resolution cameras and inexpensive robots for the automatic capture of large image collections. These tools simplify the acquisition of large stitched panoramas that are becoming easily accessible over the internet. Even more massive images from aerial satellite photography are freely distributed, e.g. from the USGS website. At the same time, computed tomography (CT) and microscopy scans allow acquisition of massive three-dimensional (3D) images for mechanical engineering applications or reconstruction of biological structures. The full potential of such imagery may only be realized by scientists or artists by enhancing, manipulating, and/or compositing the original images. However, using the combined panoramas typically requires offline processing to reduce varying lighting and coloring artifacts or to perform other editing or analysis on the data sets because the real time processing of very large volumetric meshes introduces specific algorithmic challenges due to the impossibility of fitting the input data in the main memory of a computer. The basic assumption of uniform-constant-time access to each memory location is not valid because part of the data is stored out-of-core or in external memory. The performance of most algorithms does not scale well in the transition from the in-core to the out-of-core processing conditions. The performance degradation is due to the high frequency of input/output operations that may start dominating the overall running time. Thus, because of the large data set sizes, enhancing, manipulating, and/or compositing the images or otherwise analyzing the data is computationally expensive.

SUMMARY

In an example embodiment, a method for providing an efficient data layout for image data is provided. An array of image data of a physical entity is ordered in a hierarchical z-order at a computing device. Data blocks are created from the array ordered based on the hierarchical z-order. Data files containing a predetermined number of successive data blocks are created from the created data blocks. A directory structure is created in a file system of a second computing device based on the hierarchical z-order. The created data files are stored in the created directory structure based on the hierarchical z-order.

In another example embodiment, a computer-readable medium is provided having stored thereon computer-readable instructions that, if executed by a computing device, cause the computing device to perform the method of providing an efficient data layout for image data.

In yet another example embodiment, a system is provided. The system includes, but is not limited to, a processor and the computer-readable medium operably coupled to the processor. The computer-readable medium has instructions stored thereon that, if executed by the processor, cause the system to perform the method of providing an efficient data layout for image data.

DETAILED DESCRIPTION

With reference toFIG. 1, a block diagram of a data processing system100is shown in accordance with an example embodiment. Data processing system100may include a data generation system101and a computing device102. Computing device102may include a display104, an input interface106, a computer-readable medium108, a communication interface110, a processor112, and a data processing application114. In the embodiment illustrated inFIG. 1, data generation system101generates data related to a physical entity in two-dimensions, three-dimensions, four-dimensions, etc. In an example embodiment, the data is obtained from a sensor such as a radar, an infrared sensor, an optical sensor, etc. For example, the sensor may be a panoramic camera that obtains two-dimensional data from a vantage point on the earth's surface such as of a city. Alternatively, the sensor may be a satellite based synthetic aperture radar that obtains three-dimensional terrain data of the earth's surface. As another alternative, the sensor may be an infrared sensor that obtains thermal data of the earth's surface. As yet another alternative, the sensor may be part of a medical imaging system such as a magnetic resonance imaging device, a computed tomography scanner, etc. The source of and the dimensionality of the data is not intended to be limiting.

Computing device102may be a computer of any form factor. Different and additional components may be incorporated into computing device102. Display104presents information to a user of computing device102as known to those skilled in the art. For example, display104may be a thin film transistor display, a light emitting diode display, a liquid crystal display, or any of a variety of different displays known to those skilled in the art now or in the future.

Input interface106provides an interface for receiving information from the user for entry into computing device102as known to those skilled in the art. Input interface106may use various input technologies including, but not limited to, a keyboard, a pen and touch screen, a mouse, a track ball, a touch screen, a keypad, one or more buttons, etc. to allow the user to enter information into computing device102or to make selections presented in a user interface displayed on display104. Input interface106may provide both an input and an output interface. For example, a touch screen both allows user input and presents output to the user. Computing device102may have one or more input interfaces that use the same or a different input interface technology.

Computer-readable medium108is an electronic holding place or storage for information so that the information can be accessed by processor112as known to those skilled in the art. Computer-readable medium108can include, but is not limited to, any type of random access memory (RAM), any type of read only memory (ROM), any type of flash memory, etc. such as magnetic storage devices (e.g., hard disk, floppy disk, magnetic strips, . . . ), optical disks (e.g., compact disk (CD), digital versatile disk (DVD), . . . ), smart cards, flash memory devices, etc. Computing device102may have one or more computer-readable media that use the same or a different memory media technology. Computing device102also may have one or more drives that support the loading of a memory media such as a CD or DVD. Computer-readable medium108may comprise a cache in which data can be stored temporarily for rapid access by processor112. Computer-readable medium108further may comprise a file system in which data files are stored and organized for access by processor112.

Communication interface110provides an interface for receiving and transmitting data between devices using various protocols, transmission technologies, and media as known to those skilled in the art. The communication interface may support communication using various transmission media that may be wired or wireless. Computing device102may have one or more communication interfaces that use the same or a different communication interface technology. Data may be transferred between computing device102and data generation system101using communication interface110. Additionally, communication interface110may provide connectivity to other systems. For example, communication interface110may provide connectivity to a remote file system or database.

Processor112executes instructions as known to those skilled in the art. The instructions may be carried out by a special purpose computer, logic circuits, or hardware circuits. Thus, processor112may be implemented in hardware, firmware, software, or any combination of these methods. The term “execution” is the process of running an application or the carrying out of the operation called for by an instruction. The instructions may be written using one or more programming language, scripting language, assembly language, etc. Processor112executes an instruction, meaning that it performs the operations called for by that instruction. Processor112operably couples with display104, with input interface106, with memory108, and with communication interface110to receive, to send, and to process information. Processor112may retrieve a set of instructions from a permanent memory device and copy the instructions in an executable form to a temporary memory device that is generally some form of RAM. Computing device102may include a plurality of processors that use the same or a different processing technology.

Data processing application114performs operations associated with processing data generated by data generation system101such as constructing an image from imaging data such as optical data obtained from a camera. Some or all of the operations described may be embodied in data processing application114. The operations may be implemented using hardware, firmware, software, or any combination of these methods. With reference to the example embodiment ofFIG. 1, data processing application114is implemented in software stored in computer-readable medium108and accessible by processor112for execution of the instructions that embody the operations of image data processing application114. Data processing application114may be written using one or more programming languages, assembly languages, scripting languages, etc. As known to those skilled in the art, data processing application114may be implemented as a plug-in to a second data processing application.

Components of data processing system100may be positioned in a single location, a single facility, and/or may be remote from one another. Data generation system101and computing device102may be integrated into a single system. Data generation system101and computing device102may be connected directly. For example, data generation system101may connect to computing device102using a cable for transmitting information between data generation system101and computing device102. Data generation system101may connect to computing device102using a network. Data may be stored electronically and accessed using computing device102. Data generation system101and computing device102may not be connected. Instead, the data acquired using data generation system101may be manually provided to computing device102. For example, the data may be stored on electronic media such as a CD, a DVD, a flash drive, etc. After receiving the data, computing device102may initiate processing of the data automatically or under control of an operator of computing device102.

With reference toFIG. 2, example operations associated with data processing application114ofFIG. 1are described. Additional, fewer, or different operations may be performed, depending on the embodiment. The order of presentation of the operations ofFIG. 2is not intended to be limiting. In an operation200, image data is received. For example, the image data may be stored at computing device102and selected for input to data processing application114which receives the image data as an input. As another alternative, the image data may be streamed to computing device102from data generation system101.

In an operation202, an array of data is defined from the data. In an example embodiment, the array is defined in row-major order though this is not required and other traversal orders may be used in defining the array of data.

In an operation204, z-ordered data is defined from the array of data. With reference toFIG. 4, an example of z-ordered data (0, 1, 2, 3, . . . , 15) is shown for a 4×4 array of data arranged in row-major order (i, j). In the two-dimensional case, the z-order curve can be defined recursively by a “z” shape whose vertices are replaced by “z” shapes half its size. Given the binary row-major index of a pixel (i0i1. . . in; j0i1. . . jn), the corresponding z-order index I is computed by interleaving the indices I=j0i0j1i1. . . jninas shown inFIG. 5aresulting in the table as shown inFIG. 6.FIG. 5bshows the same process for a 3D array stored in row-major order (i, j, k).

With continuing reference toFIG. 2, in an operation206, a hierarchical z-order (HZ-order) is determined as shown inFIG. 7based on the z-order index. As shown inFIG. 8a, to start the process, a first bit802is set to one and is added to the left of the given z-order index I800forming a second z-order index I801, and an exit bit804is set to zero. With reference toFIG. 8b, the hierarchical z-order is computed by shifting second z-order index I801to the right until the first one-bit exits in exit bit804. As shown inFIG. 8b, the z-order index I801is shifted to the right and first bit802is set to zero in all subsequent shifts until exit bit804is one. The resulting index Ih806comprised of the right most bits is the hierarchical z-order.

As an example conversion from the z-order index to the hierarchical z-order index, assume the given z-order index is 0010110100. The conversion results in the hierarchical z-order index of 0010010110 based on the following steps:

As indicated in the far right column ofFIG. 7, the hierarchical z-order provides an index that supports hierarchical access to the data. The starting hierarchical z-order index for each resolution level can be directly computed. For example, in a squared array, level0contains one sample and all other levels h contain 2h−1samples. Therefore, the starting hierarchical z-order index of level h, Istarth, is 2m−hwhere m is the number of bits of the largest hierarchical z-order index. Within each level, samples are ordered according to plain z-order and can be traversed using a stack algorithm described below using the appropriate sub-sampling rate. Thus, iteration of the array in hierarchical z-order can be accomplished by processing one resolution level at a time until the appropriate level of resolution is obtained based on the current processing on the data.

To provide efficient access to any sub-region of the data without internal caching and without opening a data block more than once, the data can be stored based on blocks of data organized in the hierarchical z-order. With continuing reference toFIG. 2, in an operation208, an indication of a block size, a record size, and a group size is received. For example, the block size, the record size, and the group size may be set to default values in computer readable medium108, received as an input from a user of data processing application114, calculated based on an array size, etc. In an operation210, a directory structure is created. For example, with reference toFIG. 9a, two levels of directories are created to store the data files, a first directory level900and a second directory level902which are formed as subdirectories of first directory level900.FIG. 9aillustrates a storage model for images of predetermined maximum resolution. With reference toFIG. 9b, a storage model for images of a variable adaptive maximum resolution is shown with the same data stored in a more flexible structure where prefix subdirectories composed of all zeroes are eliminated from the address computation shown inFIG. 9cso that all their content is moved to higher levels in the directory structure

With continuing reference toFIG. 2, in an operation212, data blocks of the indicated block size are created from the received image data in hierarchical z-order. For example, with reference toFIG. 9, data blocks904having a block size of five are created from consecutive samples of the data reordered in hierarchical z-order.

With continuing reference toFIG. 2, in an operation214, data files are created from a sequence of data blocks based on the indicated record size. For example, with reference toFIG. 9a, a first data file906with a record size of three includes three successive data blocks, a second data file908includes the next three successive data blocks and based on a defined group size of two, the data files are clustered in groups of two in a subdirectory. Thus, a sequence of consecutive blocks is grouped into a record and records are clustered in groups, which are organized hierarchically within the created directory structure. Consider, for example, the case ofFIG. 9cwhere each directory contains 2lfiles or subdirectories, each file contains 2mblocks, each block contains 2nsamples. Using the storage structure illustrated inFIG. 9a, an index Ih910defines a position for a data sample in a block given by the last n bits912of index Ih910, within a file at a block index given by the next m bits914of index Ih910, within the file given by the next l bits916of index Ih910within a hierarchy of subdirectories for which each index is given by the next l bits918,920,922,924of index Ih910. Consequently, the total number of directories, files, and blocks depend on the values of the parameters l, m, and n. Using the storage structure illustrated inFIG. 9b, the position of the same sample index Ih910is computed in the same way after removing all of the leading zeroes924on the left of index Ih910. This makes the storage position of the coarse samples independent of the total number of bits in Ihand allows adding new samples of arbitrarily finer resolution.

In an operation216, header information is defined that describes the various parameters such as the dimension of the received image data, the block size, the record size, the group size, etc. For example, with continuing reference toFIG. 9a, a header907includes header information. Each record may have header907that specifies which of its blocks are actually present, and if the data is stored in a raw format or a compressed format, and if the data is stored in a compressed format, an indicator of the compression format. In a first example implementation, a single file having a header describing the parameters of the format, i.e., interleaving sequence, block size, record size, etc., followed by the binary representation of the blocks. In a second example implementation, the header information may be stored in a special header file and each record in a separate file without a header.

With continuing reference toFIG. 9a, a pointer909in header907points to the position of the block within a record. This accommodates blocks of variable size (e.g. for compression), blocks out of order (e.g. following creation order), and avoids wasting space when blocks are missing. Optionally, a bit per sample can be used to specify if each sample is part of the input image or not which accommodates images of arbitrary size and samples that can be part of only part of a block. The sizes of blocks, records, and groups can be adjusted to better optimize the performance of the memory structure where the image is stored. For example, on a file system each directory can store efficiently a group of 256 files and/or subdirectories, a file can contain 128 blocks, and each block can contain 4096 data samples. In general, it is better if the sizes are powers of two because this simplifies some of the index computations.

In an operation218, the created data files are stored in the created directory structure. Incomplete arrays and arrays of arbitrary size can be stored. The use of a file system to store and access the hierarchy using directories is not intended to be limiting and can be implemented with search trees or hash tables or other hierarchical reference mechanisms and stored in single databases or across multiple files or accessing each record or group in different storage locations distributed over the Internet or other heterogeneous storage infrastructures.

Thus, the hierarchy of groups is implemented as a hierarchy of directories each containing a predetermined maximum number of subdirectories and possibly records. The leaves of each directory contain only records. To open a file, the path to the file is reconstructed, and the file system is used to locate the file directly. In particular, the path to a record can be constructed by taking the hierarchical z-order address of the first sample in the record, representing the address as a string, and partitioning the string into groups of characters naming directories, subdirectories, and the record file. Because blocks, records, and/or groups can be missing, the arrays of data need not cover the entire index space. In fact, received image data can easily be stored with different regions sampled at different resolutions. With the storage structure shown inFIG. 9b, the resolution can even be increased after the initial image creation.

With reference toFIG. 10, a data layout of the data blocks904obtained for a two dimensional (2D) matrix reorganized using the hierarchical z-order index is shown. Each gray region shows where the block of data is distributed in the 2D array. In particular, the first block is the set of coarsest levels of the data distributed uniformly on the 2D array. The next block is the next level of resolution still covering the entire matrix. The next two levels are finer data covering each half of the array. The subsequent blocks represent finer resolution data distributed with increasing locality in the 2D array.

With reference toFIG. 3, second example operations associated with data processing application114ofFIG. 1are described. Additional, fewer, or different operations may be performed, depending on the embodiment. The order of presentation of the operations ofFIG. 3is not intended to be limiting. In an operation300, an indicator of image data to process is received. For example, a user of data processing application114may select a data file to process using input interface106. In general, the processing described with reference toFIG. 2may have been performed previously so that the directory structure and hierarchical z-ordered data blocks have been created for the image data selected for processing. In an operation302, a path is constructed to the first record of the indicated image data. For example, as discussed above, the path to the file is reconstructed by taking the hierarchical z-order address of the first sample in the record, representing the address as a string, and partitioning the string into groups of characters naming directories, subdirectories, and the record file.

In an operation304, a resolution level to load is determined based on a function associated with the processing of the image data. For example, the resolution level may be set as a default based on a default zoom level of an image and a display resolution. In an operation306, a data file path to each file is determined based on the selected resolution level and the hierarchical z-order. In an operation308, the files are opened and read. In an operation310, the image is displayed in display104.

In an operation312, a stack algorithm is implemented as part of the display of the image. A stack is an ordered list of items organized in a data structure based on the principle of last in first out. Items are removed from the list (stack) in a reverse order to the order of their addition. Any abstract data type can be an item or element of the stack. There are two main operations; push and pop. The “push” operation adds (stores) items to the list (stack). The “pop” operation removes (deletes) an item from the list (stack), and returns or exports a value for the item to the calling application.

With reference toFIGS. 11a-11j, a stack algorithm supporting fast index computation and data queries is described. The stack contains tuples or parameter lists including (split_dimension, I_start, min_i, max_i, min_j, max_j, num_elements). To start the process, with reference toFIG. 11a, the tuple t0=(1, 0, 0, 3, 0, 3, 16) is pushed onto the stack where in this example split_dimension=1, I_start=0, min_i=0, max_i=3, min_j=0, max_j=3, num_elements=16 as shown for the case illustrated inFIG. 4. At each iteration, the top-most element t is popped from the stack. If t contains only a single element, the current I_start is output as the hierarchical z-order index and the corresponding sample is fetched from the file structure. Otherwise, as shown with reference toFIG. 11b, the region represented by t is split into two pieces along the axis given by split_dimension, and the corresponding tuples are created such as t1=(0, 0, 0, 3, 0, 1, 8) and t2=(0, 8, 0, 3, 2, 3, 8). For example, the tuple parameter num_elements is divided by two because the region is divided in two and the tuple parameters min_i, max_i, min_j, and max_j are changed to indicate the appropriate boundaries for the two new regions. The elements of t1and t2can be computed from t by simple bit manipulation of each element of the tuple as shown inFIG. 12. In the case of a square array, the split dimension is flipped each time a tuple is split. However, a specific split order can also be stored to accommodate rectangular arrays.FIGS. 11c-11jshow the first eight iterations of the stack algorithm outputting the first four elements in the array ofFIG. 4.

To use this algorithm for fast range queries, each tuple is tested against a query box (or an arbitrarily shaped query region) as it comes off the stack and discarded if no overlap exists between the tuple and the query box. Since the row-major indices describing the bounding box of each tuple are computed concurrently (min_i, max_i, min_j, max_j), the intersection test is straightforward for a box. It is also simple to estimate conservatively for an arbitrary query region. Furthermore, the method applies virtually unchanged to traverse samples in z-order that sub-sample an array uniformly along each axis, where the sub-sampling rate along each axis could be different. Based on this, the array can be traversed in hierarchical z-order by processing one level at a time, adding Istarthto the I_start of each tuple.

In practice, the stack tuples may not be subdivided to the level of a single sample. Instead, depending on the platform, a parameter n may be selected and a table built with the sequence of z-order indices for an array with 2nelements. When executing the stack algorithm, each time a tuple t with 2nelements appears, the table is looped through instead of splitting t. By accessing only the necessary samples in strict hierarchical z-order, the stack-based algorithm guarantees that only the minimal number of disk blocks are touched and each block is loaded just once.

For progressively refined zooms in a given area, the algorithm can be applied with a minor variation. In particular, the size of the bounding box represented in a tuple can be reduced each time the tuple is pushed back onto the stack. In this way, even for a progressively refined zoom, only the needed data blocks are accessed, and the data blocks are only accessed once.

In an operation314, a data query is received, for example, from a selection made by a user of data processing application114using input interface106. As an example, the user may pan, zoom in, zoom out, or edit the displayed image. For example, in editing the image, the user may apply complex operators such as seamless cloning, panorama stitching, tone mapping, etc. The stack algorithm is used to provide a rapid response to the data query. The displayed resolution level may change dependent on the actions performed by the user in interacting with data processing application114. For example, with reference toFIG. 12, a lower resolution level is displayed as the user pans the image. When the user stops panning, a higher resolution image shown with reference toFIG. 13, is displayed based on the rapidly accessible hierarchical z-ordered data and use of the stack algorithm. Using the described methods, data processing application114provides interactive editing of images that exceed hundreds of gigapixels in size.

The word “example” is used herein to mean serving as an example, instance, or illustration. Any aspect or design described herein as “example” is not necessarily to be construed as preferred or advantageous over other aspects or designs. Further, for the purposes of this disclosure and unless otherwise specified, “a” or “an” means “one or more”. The example embodiments may be implemented as a method, apparatus, or article of manufacture using standard programming and/or engineering techniques to produce software, firmware, hardware, or any combination thereof to control a computer to implement the disclosed embodiments.

The foregoing description of example embodiments of the invention have been presented for purposes of illustration and of description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed, and modifications and variations are possible in light of the above teachings or may be acquired from practice of the invention. The functionality described may be implemented in a single executable or application or may be distributed among modules that differ in number and distribution of functionality from those described herein. Additionally, the order of execution of the functions may be changed depending on the embodiment. The embodiments were chosen and described in order to explain the principles of the invention and as practical applications of the invention to enable one skilled in the art to utilize the invention in various embodiments and with various modifications as suited to the particular use contemplated. It is intended that the scope of the invention be defined by the claims appended hereto and their equivalents.