Hierarchical data representations
How images (or volumes!) can be represented as a hierarchy
Hierarchical data structures can help scientists with all kinds of problems. When I refer to hierarchies, I mean anything that has a tree-like or casicading structure. These hierarchies allow data to be represented with different ganularity, or in other terms, different levels of detail (LOD), in different areas. For instance, in fluid simulations, if there are few fluid particles in a region, we do not need to do fine-grained simulation there. This allows us to focus our computation resources in places that need it most.
We can also use this hierarchy to save data more efficiently. If a large portion of your image is the same color, why should we save that same pixel thousands of times? Different techniques do this in different ways, but popular methods are quadtrees/octrees, k-d trees, and adaptive mesh refinement (AMR).
In some of my recent work, I create an algorithm for compressing a volume (or image in this case) into an hierarchical representation similar to an octree(quadtree) using adaptive mesh refinement. I develop an algorithm that "super resolves", or upscales, hierarchical data into a uniform high resolution. Any super resolution algorithm can be use - bilinear interpolation, bicubic interpolation, and even neural networks (which I use in my paper!). Second, I create an adaptive refinement algorithm that reduces levels of detail (LOD) where able such that my super resolution algorithm can still super resolve the details with some minimum error that is specified by a user. Below is a tool for playing with this algorithm using images. A number of parameters can be tweaked:
- Criteria: the metric that is our error criteria
- Criteria value: the value the super resolved picture must stay below/above
- Minimum chunk size: the smallest size possible for a chunk to be. Must be a power of 2. Smaller values will drastically increase computation time. I recommend nothing smaller than 64, otherwise my Raspberry Pi might explode.
- Maximum downscale amount: How much downscaling is allowed to occur. Must be a power of 2 less than 258. Recommended 8, 16, 32.
- Upscaling technique: The method used when upscaling in the algorithm
- Downscaling technique: The method used when downscaling in the algorithm
Generally, upscaling and downscaling technique should stay how they are. If interested in the code, you cand find it here.
Criteria value:
Maximum Downscaling:
Minimum chunk size:
Be sure that entered values are properly formatted for integers or floats where expected, with no training spaces.
WARNING: minimum chunk sizes 32 and lower paired with relatively high criteria values (high PSNR, low MRE/MSE) can be very slow to compute. Can take up to 40 minutes with extreme settings. Expected load time for default settings above is roughly 1 minute.
PSNR: 89.02, MSE: 8.85, MRE: 0.0500
