PaperlayerView exact revision on arXiv

Source-linked AI summary

RangeRectQuant: Compressing Scientific Fields for Every Future Rectangular Sum

Jiahao Zhang, Xinling Wen, Yu Chen

arXiv:2610.36873v1cs.CV

TL;DR

Archived rasters are often encoded before measurement regions are known, leaving a need for deterministic error bounds on every future rectangle. RangeRectQuant builds a bounded integer reconstruction by characterizing realizable cumulative errors; keeping prefix errors within floor(ε/4) guarantees the prescribed budget for every rectangle, regardless of size.

  • Problem

    Archived rasters need deterministic error bounds for every future rectangle, although measurement regions are unknown at encoding time.

    Source: Related Work · p. 2

  • Method

    RangeRectQuant constructs a bounded integer field by characterizing which cumulative errors remain realizable while preserving designated exact samples.

    Source: Related Work · p. 2

  • Results

    Keeping each prefix error within floor(ε/4) guarantees the prescribed error budget for every rectangle, independently of its size.

    Source: Problem definition · p. 3

  • Takeaways & Limitations

    With the mask transmitted exactly, a mean over k valid samples has error at most ε/k.

    Source: Problem definition · p. 3

    The stated setting assumes integer-valued fields bounded in [0, U] and requires masked or designated protected samples to remain exact.

    Source: Problem definition · p. 3

Abstract

from arXiv · show

Scientific rasters are often stored before the regions to be measured are known. Independent pixel-error bounds can force exact integer reconstruction when one absolute error budget covers every future rectangle. Coordinated changes allow every pixel to change while every rectangular sum remains accurate. A prefix sum accumulates values from the top-left corner. Four such sums determine any rectangular total. RangeRectQuant preserves the pixel range and designated exact samples while controlling errors in prefix sums. At each row position, we characterize exactly which errors let the remaining pixels meet these constraints. These errors form a single integer interval, even when many completions exist. A backward pass finds its endpoints; a forward pass uses them to choose quantized pixels. The resulting field meets the prescribed error budget for every axis-aligned rectangle, with linear work and workspace proportional to one row. Experiments on geographically held-out built-surface and water-occurrence maps show substantial storage savings over alternatives meeting the same requirements. Data producers encode once; later users measure arbitrary rectangles without the source, re-encoding, or query-specific correction.

Related Work · Constructing a Field with Accurate Regional Sums

Prior compression methods target pixelwise distortion, specified downstream quantities, or regional-error control for narrower region families. RangeRectQuant instead constructs a bounded integer field that preserves designated exact samples and guarantees accurate sums for every future rectangle without the source at query time.

Related Work

  • Pointwise compression controls individual reconstruction errors, but one small budget for every regional sum can remove the freedom to change pixels.The passage notes that a uniform pixel tolerance can force exact reconstruction in the worst case under specified conditions.Source: Related Work · p. 2, Table 1 · p. 2
  • Prediction, interpolation, quantization-error coding, and integer representations for astronomical images improve storage-rate and precision tradeoffs.Pointwise distortion remains a central target of scientific compression.Source: Related Work · p. 2
  • Downstream-aware methods address specified quantities, whereas archived rasters require a deterministic budget for every rectangle unknown at encoding time.Prior approaches include field-norm bounds, tailored pixel tolerances, selected ranges or features, and query-aware error or uncertainty objectives.Source: Related Work · p. 2
  • RangeRectQuant supports every future rectangle with a bounded integer field, preserves designated exact samples, and needs no source at query time.It does so by characterizing which cumulative errors remain realizable by valid pixels.Source: Related Work · p. 2
  • Matrix rounding controls regional errors for two nested or disjoint region families.Source: Related Work · p. 2
  • Two-dimensional sigma–delta quantization controls prefix-sum errors, but its stable greedy scheme uses an expanded alphabet that may leave the input range [2].Source: Related Work · p. 2

Problem definition

The problem is to reconstruct an integer field in [0, U] while preserving protected samples and keeping every axis-aligned rectangle’s sum error within ε. The definition contrasts this global constraint with independent pixel bounds and motivates prefix-error control.

Problem definition

  • The reconstruction Y must stay in [0, U], match X on protected samples, and keep the error in every nonempty axis-aligned rectangle’s sum within ε.The mask is preserved as zeros in both fields; exact transmission of the mask also preserves each region’s valid-sample count.Source: Problem definition · p. 3
  • For k > 0 valid samples, preserving the mask gives a mean error bound of ε/k.Source: Problem definition · p. 3
  • Independent pixel tolerance δ permits sharp worst-case rectangular error A min(⌊δ⌋, U); when U ≥ 1 and ε < A, it certifies the budget only with exact reconstruction.A counts unprotected samples.Source: Problem definition · p. 3
  • A rectangle’s error is an alternating sum of four prefix errors, so bounding each absolute prefix error by B = ⌊ε/4⌋ guarantees the regional budget regardless of rectangle size.The construction maintains this bound while selecting Y values directly.Source: Problem definition · p. 3
  • With Xij = 1, U = 2, and no protected samples, Yij = 1 − (−1)^i+j changes every pixel while each rectangle error is at most four.For HW > 4, independent tolerance of at least one permits an all-twos field with error HW, so certifying budget four requires exact pixels under independent bounds.Source: Problem definition · p. 3

A row transition that includes the value range

Each row is represented as a path through prefix errors, with incoming errors and each new state determining a reconstructed pixel. Transitions must satisfy the prefix bound and source-value range, with protected pixels fixed by their incoming error change.

A row transition that includes the value range

Exact intervals for completing a row

Feasible prefix-error states for completing the remaining row form an exact integer interval, whose endpoints support a backward–forward construction. The construction realizes accurate rectangular sums in linear time with workspace proportional to one row.

Exact intervals for completing a row

  • A backward pass computes interval endpoints, and the forward pass chooses the closest-to-zero feasible state, using a protected pixel’s forced state when applicable.For an unprotected pixel, it chooses a state satisfying (3) when one exists; otherwise it chooses the closest-to-zero integer in the allowed interval.Source: Exact intervals for completing a row · p. 4
  • Feasible prefix-error states form an exact integer interval: backward recurrence intersects [−B, B] with shifted endpoint ranges for unprotected and protected pixels.Backward induction yields the exact feasible sets, and 0 ∈ V0.Source: Exact intervals for completing a row · p. 4
  • The construction guarantees accurate sums for all Θ(H^2W^2) rectangles using O(HW) arithmetic operations and O(W) additional row workspace.The guarantee holds for every bounded integer input, protected set, integer q ≥ 1, and finite ε ≥ 0.Source: Exact intervals for completing a row · p. 5
  • At an unprotected forward choice, feasible pixel values form [s, v] = [t_j + l − a, t_j + h − a], containing κ_j = ⌊v/q⌋ − ⌊(s − 1)/q⌋ coarse values.The count is the number of multiples of q in the feasible interval; any q consecutive integers contain a multiple.Source: Exact intervals for completing a row · p. 5

Encoding the constructed field

The section describes a lossless representation that combines quotient values with fine-pixel positions and remainders. The step size q controls storage while the band B sets accuracy, and candidate constructions retain Theorem 1’s guarantee.

Encoding the constructed field

  • The field is represented as Y = qZ + r, with quotient and remainder arrays coded using LZMA after grouping low and high bytes.Files also store masks and metadata.Source: Encoding the constructed field · pp. 5–6
  • The representation codes quotient values, their count, fine-pixel positions, and remainders by ranks, with a geometry-dependent length bound for q ≥ 2.For q = 1, m = 0 and the bound is ⌈N log2(U + 1)⌉ bits.Source: Encoding the constructed field · pp. 5–6
  • The band B sets accuracy while q controls storage: coarse alphabets reduce quotient cost, whereas fine pixels add position and remainder costs.The quotient alphabet has K = ⌊U/q⌋ + 1 possible values, and m counts fine pixels.Source: Encoding the constructed field · pp. 5–6
  • For a finite nonempty step set Q, candidates retain Theorem 1’s guarantee, ties favor smaller q, and each trial repeats construction and coding.The encoded file length at step q is denoted Lq(X).Source: Encoding the constructed field · p. 6

Evaluation Data and file comparisons

The evaluation compares self-contained files for bounded-integer built-surface and water-occurrence rasters under shared rectangular-sum and validity requirements. RangeRectQuant meets both accuracy and range requirements across the eight reported cases.

Evaluation data

  • The study evaluates building-area and water-occurrence rasters, using 40 additional built-area locations and an independent set of eight water windows; four cities illustrate configuration and step tradeoffs.Built-area data are 2020 Global Human Settlement Layer values in [0, 10000] m2 on a 100 m grid; water data span 1984–2024, with values [0, 100] and missing code 255. Native 1024^2 windows provide central 512^2 and 256^2 crops; budgets range from 25–5000 m2 for built area and 5–1000 percentage points for water.Source: Evaluation Data and file comparisons · p. 6

File comparisons

  • A valid self-contained file must decode without the source, preserve missing and protected samples, and meet the integer-range and rectangular-error requirements.Decoded fields are converted to the required bounded-integer representation and assessed under the same regional-sum requirement.Source: Evaluation Data and file comparisons · pp. 6–7
  • The comparison covers six lossless integer representations, lossless JPEG 2000, SZ3, MGARD, and QPET, with native-byte LZMA and PNG added for water.Representative supported configurations of SZ3, MGARD, and QPET are swept; file sizes include masks, configuration, geospatial metadata, digest, and checksum.Source: Evaluation Data and file comparisons · p. 7

Controls

  • The fixed-margin control changes 2 × 2 blocks to preserve row and column sums, while the sum-pyramid control splits square totals among four children within valid ranges.The pyramid files store pixels or deviations of child totals from proportional parent shares.Source: Evaluation Data and file comparisons · p. 7

File comparisons

  • Stable greedy two-dimensional sigma–delta has 2.22–6.76% out-of-range pixels, while clipping raises regional error to thousands of times the budget; RangeRectQuant meets both requirements in all eight cases.Figure 4 plots maximum rectangle error divided by budget and marks invalid pixels or over-budget errors.Source: Figure 4 · p. 7, Evaluation Data and file comparisons · p. 7

Rate across locations and budgets

The results show storage savings across built-area locations and water maps, with the size of the savings depending on the budget and valid-file alternatives. At the smallest water budgets, native-byte lossless files remain smaller.

Rate across locations and budgets

  • Adding valid sum-pyramid files retains forty wins at budgets 100 and 1000, with savings of 32.55% and 41.30%.Table 2 reports file rates in bits per pixel, including masked positions, against the smallest valid external files.Source: Rate across locations and budgets · p. 7, Table 2 · p. 8
  • Water savings begin at budget 25 and reach 65.35% at 1000; all eight locations win from 250, while native-byte lossless files are smaller at 5 and 10.Water budgets use percentage-point sums.Source: Rate across locations and budgets · p. 7, Figure 5 · p. 8
  • All 960 built-area files change pixels and are smaller than the smallest valid lossless, scientific-compressor, or fixed-margin file, with aggregate reductions of 16.23–72.17%.Figure 5 covers forty built-area locations at three sizes; its curves require valid files everywhere, and gaps mark incomplete coverage.Source: Rate across locations and budgets · p. 7, Figure 5 · p. 8

Rate decomposition

Quotient–remainder coding reduces storage relative to direct 16-bit LZMA while preserving the error budget for every rectangle. Step sweeps and an eight-step probe also preserve the constraints, with the main rate comparisons retaining the fixed step.

Rate decomposition

  • 15.20% and 11.03% savings over direct 16-bit LZMA at budgets 100 and 1000 also beat byte-shuffled coding (Figure 6).These comparisons use identical fields.Source: Rate decomposition · p. 8
  • Remainders cost 0.070 and 0.086 bits per pixel; removing them exceeds the budget in all 320 fields.Source: Rate decomposition · p. 8
  • Step sweeps at four configuration locations and four separate cities preserve all constraints, with fine choices matching (6).Source: Rate decomposition · p. 8
  • 15.04% and 8.30% further savings at budgets 100 and 1000 come from an eight-step probe on four cities using common metadata and (8).Search averages 1.20 s per field.Source: Rate decomposition · p. 8
  • Main rate comparisons retain the fixed step.Source: Rate decomposition · p. 8

Protected samples and scalability

Nested protected sets preserve exact samples and pixel range while maintaining regional accuracy, with warm construction and verification taking 22–25 ms. Scalability tests report encoding and decoding times for native 4096^2 London fields and construction throughput.

Protected samples and scalability

  • 22–25 ms suffices for warm construction with verification across forty configurations that retain exact samples, pixel range, and regional accuracy.The configurations use nested protected sets of up to 10%.Source: Protected samples and scalability · p. 8
  • On native 4096^2 London fields, median encoding took 7.84 s and decoding 1.14 s at budget 100; construction alone reached 18.39 million pixels per second.Measurements used a 16 GB Apple M4 and were medians of three warmed, single-thread repetitions.Source: Protected samples and scalability · p. 9

Conclusion

RangeRectQuant uses exact completion intervals to enable coordinated quantization that preserves pixel range and the accuracy of every rectangular sum. Built-surface and water-occurrence studies demonstrate file savings.

  • Uniform independent pixel-error bounds can force exact reconstruction, whereas exact completion intervals enable linear-time coordinated quantization that preserves pixel range and every rectangular-sum error guarantee.The method quantizes within the intervals of errors that leave the remaining pixels able to satisfy the constraints.Source: Conclusion · p. 9
  • Built-surface and water-occurrence studies demonstrate file savings with RangeRectQuant.Source: Conclusion · p. 9
  • The repository provides code, data, core experiments, and extended figures at https://github.com/Marchematics/RangeRectQuant.Source: Conclusion · p. 9

Related papers

Loading 2610.36873v1…