# RSIMS: Large-Scale Heterogeneous Remote Sensing Images Management System
## 2 Materials and Methods
### RSIMeta: Metadata Management of Large-Scale Images with Heterogeneous Structures
#### 2.2.2 Remote Sensing Images Index and Retrieval Based on Hilbert Curve
Figure 7: Transition matrixes for Hilbert curves. Auxiliary variables and functions are explained as follows:  
* M = [T1 matrix, T2 matrix, T3 matrix, T4 matrix];
* function HilbertGrid(k, x, y): calculate the position of the grid in Cartesian coordinate system;
* function binary(m): convert decimal to binary;
* function query_code(matrix, grid): query the code from the curve-transition matrix of some type based on the identification of the grid;
* function query_type(matrix, grid): query the Hilbert curve shape type of level(k \(-\) 1) from the curve-transition matrix of some type based on the identification of the grid. Considering that remote sensing images from different sources have different sizes, the second level (the _param(k)_ in Algorithm 1) should be determined dynamically. The rule is that the expected Hilbert level should be the smallest one whose corresponding grids is larger than the average size of all remote sensing images from the same platform. Taking the Landsat for example, the average area of all Landsat images is about 4 \(\times\) 104 km\({}^{2}\), so the second Hilbert level for Landsat images is 5. The whole process can be illustrated with Figure 8. Remote sensing images of the same type are encoded into Hilbert codes (\(C_{0}\)) based on the basic 8*8 global grids for distributed storage, and then for optimized spatial intersection query, every single remote sensing image is further encoded into a longer Hilbert code (\(C_{1}\)), which is dynamically based on the image size. To take advantage of the multi-level Hilbert grids storage structure, the spatial query region is also subdivided into multiple Hilbert grids for better retrieval performance. Finding a Hilbert grid which just contains the query area is simple and can reduce the query scope, but this way would include too many disjoint images, which still need lots of time to select the target images. We designed another algorithm to subdivide the query area into Hilbert grids which are consistent with remote sensing datasets. After that, complex and slow spatial intersection computing can be transformed to simpler and faster string matching. The process includes two parts: one for calculating Hilbert grids coverage, and the other for Hilbert grids encoding. The steps of calculating Hilbert grids coverage are described as follows. Suppose that \(S\) is the vector boundary of the remote sensing image, \(B\) is the bounding box of \(S\), and \(G\) is the minimum set of grids covering \(B\). The relationship of \(S\) (blue line zone), \(B\) (green line zone), and \(G\) (red line zone) is shown as Figure 9.  
Figure 4.0 Remote sensing image encoding and storage. The steps are described as follows:  
1. Subdivide \(G\) into four sub-regions (represented by \(SG\)) of almost the same size;
2. Iterate over \(SG\), and evaluate the spatial relationship between each sub-region of \(SG\) and \(S\). If the sub-region is contained in \(S\), then put the sub-region in the list of results; if the sub-region intersects with S, then set the sub-region as a new \(G\), and then return to step (1); if the sub-region and \(S\) are disjoint, then omit the sub-region. Pseudo codes are show as Algorithm 2:  
```
GridRegions = [ ] functionHilbertCoverage(region) {  ext = GridExtent(region) if ext < GRID_EXT * 4: GridRegions.push(ext) return  rgs = QuarterDivide(region) for rg in rgs: if S.contains(rg): GridRegions.push(rg) if S.intersects(rg): HilbertGrids(rg)
```  
**Algorithm 2** Hilbert grid coverage  
After processed by Algorithm 2, regions generated still can't be used directly because some regions are not consecutive in the Hilbert code order and some smaller regions can be merged into a bigger one for better retrieval performance. As shown in Figure 10, green grids are consistent with Hilbert multi-level grids and blue grids generate from Algorithm 2. From Figure 10, we can know that some blue grids can't be encoded by Hilbert curve, so we design Algorithm 3 to subdivide-and-merge blue grids into green grids.