Internet DRAFT - draft-santin-ssrg
draft-santin-ssrg
Network Working Group I. M. Santin
Internet-Draft Chosen Few Software
Intended status: Experimental 10 November 2023
Expires: 13 May 2024
Scalable Streaming Raster Graphics v1.0
draft-santin-ssrg-00
Abstract
This document describes the Scalable Streaming Raster Graphics (SSRG)
specification for the modern Web. An unfortunate truth of the modern
internet is that digital equity has been secondary to the expansion
of broadband in the most developed areas of the world. This in turn
makes it much harder for developing nations to gain a competitive
foothold in the digital market due to lackluster download speeds
limiting access to content-rich applications and educational
resources.
The SSRG specification, dubbed "Surge" by its creator, intends to
bridge "The Digital Divide" using techniques of classical quadtree
image compression and Laplacian image pyramids to create a more
scalable and equitable browsing experience for low-bandwidth users
while still providing standard features such as perceptually lossless
image quality at competitive compression rates. The format
efficiently encodes a multi-resolution version of the stored image
that can be streamed sequentially in order of increasing pixel
resolution using conventional mechanisms of the HTTP protocol.
The specification comes in three main parts:
1. SSRG stream format
2. Decoding algorithm
3. HTTP conventions
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Santin Expires 13 May 2024 [Page 1]
Internet-Draft Scalable Streaming Raster Graphics v1.0 November 2023
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on 13 May 2024.
Copyright Notice
Copyright (c) 2023 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document. Code Components
extracted from this document must include Revised BSD License text as
described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Revised BSD License.
Table of Contents
1. Brief Notice . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1. Sampling . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2. Decomposition . . . . . . . . . . . . . . . . . . . . . . 4
2.3. Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4. Analysis . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Part A: SSRG stream format . . . . . . . . . . . . . . . . . 5
3.1. Header format . . . . . . . . . . . . . . . . . . . . . . 5
3.2. Pixel format . . . . . . . . . . . . . . . . . . . . . . 6
3.2.1. Explicit coding (bit-by-bit) . . . . . . . . . . . . 6
3.2.2. Differential coding (bit-by-bit) . . . . . . . . . . 6
3.3. Chunk format . . . . . . . . . . . . . . . . . . . . . . 7
4. Part B: Decoding algorithm . . . . . . . . . . . . . . . . . 7
5. Part C: HTTP conventions . . . . . . . . . . . . . . . . . . 8
5.1. MIME Headers . . . . . . . . . . . . . . . . . . . . . . 8
5.2. Compression format . . . . . . . . . . . . . . . . . . . 9
6. Security Considerations . . . . . . . . . . . . . . . . . . . 9
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9
8. Author's Addresses . . . . . . . . . . . . . . . . . . . . . 9
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 9
9.1. Normative References . . . . . . . . . . . . . . . . . . 9
9.2. Informative References . . . . . . . . . . . . . . . . . 9
Santin Expires 13 May 2024 [Page 2]
Internet-Draft Scalable Streaming Raster Graphics v1.0 November 2023
1. Brief Notice
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119. [RFC2119]
2. Introduction
The SSRG specification, dubbed "Surge" by its creator, intends to
bridge "The Digital Divide" using techniques of classical quadtree
image compression and Laplacian image pyramids to create a more
scalable and equitable browsing experience for low-bandwidth users
while still providing standard features such as perceptually lossless
image quality at competitive compression rates. The format
efficiently encodes a multi-resolution version of the stored image
that can be streamed sequentially in order of increasing pixel
resolution using conventional mechanisms of the HTTP protocol.
Before describing the physical storage format for SSRG images, it is
helpful to contextualize its various quirks within the context of the
main compression algorithm. This algorithm is not a part of the
specification itself, and can vary from implementation to
implementation. As mentioned in the abstract of this document, the
SSRG format makes use of quadtree compression techniques and
Laplacian image pyramids to efficiently encode the same image sampled
at multiple resolutions.
2.1. Sampling
For the sake of demonstration, the following sections will describe a
typical approach for quad-tree image compression. However, the
author notes that the actual approach used to encode SSRG images is
slightly more convoluted, and is respectful of a larger variety of
non-square image dimensions.
To effectively estimate the source image at different resolution
levels, our example implementation will center the source image
within a 2^n x 2^n pixel grid so an N-depth region quadtree can be
used for decomposition. Importantly, each node of the quadtree is
tagged with the value of a sampling function for the square region it
represents, as well as a flag that signifies whether this node has:
a. no children
b. all four of its possible children.
This information is crucial to the objective of the compression
algorithm, which is described next.
Santin Expires 13 May 2024 [Page 3]
Internet-Draft Scalable Streaming Raster Graphics v1.0 November 2023
2.2. Decomposition
The sampling function used in this example will be a simple mean-area
function, which takes the mean color value of all the pixels in a
given square region as the sample. Complementary to the sampling
function is the error function, which at a high level should return
some error metric E such that its value can be used by a threshold
function to decide whether the sampled value for a given region is
sufficiently representative of all its constituent pixels. This
ideally means that E = 0.0 when all of the pixels in the given region
have the same color value (i.e it is totally uniform). From this we
also derive that when the error threshold for the compression
algorithm is zero, the quadtree decomposition data can be used to
reconstruct the source image perfectly. Therefore, our example
compression algorithm can be used in either lossy or lossless modes,
depending on the error threshold.
In this example, the error metric will be defined by the standard
deviation of all the pixel color values in the source image for a
given region. This is convenient to calculate considering we are
already doing the work to compute the mean color value. To do this
efficiently, all of the pixels are embedded as unit vectors in a
4-space where the directionless vector (0, 0, 0, 0) represents 50%
grey at 50% opacity. Then, to create a notion of "difference" (which
is required to calculate the variance of the set), one takes the dot
product of each vector with the embedded mean value. Important to
note is that by using this specific spatial notion of standard
deviation, the error function is conveniently placed in the
continuous range of [0, 1].
2.3. Algorithm
Given both the sampling and error functions, alongside the square
framing of the source image, one can proceed with the following
recursive decomposition algorithm:
1. Initialize R as the full square region of the aforementioned 2^n
x 2^n grid
2. Calculate the mean and error values (M and E) for region R
3. (a) Store the resulting mean as quadtree node N(R)
4. If E exceeds the error threshold E_max do the following:
1. Flag N(R) as containing children
2. Split R into northwest, northeast, southwest, and southeast
quadrants. Assign them to r[0..3] respectively.
3. (b) For each quadrant r[k], calculate the mean and error
values (m[k] and e[k]) and recursively call steps 3(a) thru
5, substituting R for r[k], M for m[k], and E for e[k].
5. Return to caller / halt
Santin Expires 13 May 2024 [Page 4]
Internet-Draft Scalable Streaming Raster Graphics v1.0 November 2023
2.4. Analysis
Using the above algorithm, one can immediately recognize that such a
decomposition is ideal for eliminating 2-dimensional, spatial
redundancies in the source image. One can increase the compression
ratio even further by borrowing a page from the book of Laplacian
image pyramids, which uses differential coding across increasingly
"blurry" copies of the original image to achieve lower spatial
entropy and sample density. The SSRG encoder does exactly this, only
treating the hierarchical levels of the image tree as an alternative
to the typical subsampling procedure of the technique.
3. Part A: SSRG stream format
The SSRG stream format is simple in its principles but complex in its
various quirks. It was designed with a few key goals in mind, listed
below:
* Minimalistic: the format should be simple to implement and require
little processing overhead to decode
* Optimized: the format should make the best possible use of its
allocated resources, especially in terms of storage & memory
* Portable: the format should be unambiguous in its specification
and able to be implemented on the vast majority of web platforms
* Conservative: the format should be built intentionally with
sufficient extra storage space for future expansion
Additionally, every SSRG stream is written in little-endian byte
order, and with the following order of data chunks:
1. Header
2. Chunk #1
3. Chunk #2
4. ....
5. Chunk #N
Where each "chunk" is a successive depth iteration of a breadth-first
traversal of the given image tree (which itself is obtained through a
decomposition method similar to that described in the introduction).
The structure of the header is described next.
3.1. Header format
Below is a table consisting of all the fields in the header:
Santin Expires 13 May 2024 [Page 5]
Internet-Draft Scalable Streaming Raster Graphics v1.0 November 2023
+========+=====================+====================================+
| Offset | Bytes 0 - 3 | Bytes 4 - 7 |
+========+=====================+====================================+
| 0x00 | FourCC ASCII SSRG | uint32 Image Width |
+--------+---------------------+------------------------------------+
| 0x08 | uint32 Image Height | sint32 Mean Pixel |
| | | Value (Explicit) |
+--------+---------------------+------------------------------------+
| 0x10 | uint32 Chunk #1 | uint32 Chunk #2 |
| | Size | Size |
+--------+---------------------+------------------------------------+
| ... | ... | ... |
+--------+---------------------+------------------------------------+
| ... | uint32 Chunk #N | |
| | Size | |
+--------+---------------------+------------------------------------+
Table 1
3.2. Pixel format
In some cases, a little-endian, signed, 32-bit integer read from an
SSRG stream represents a pixel value. One such case is at offset
0x0C of the file header described above. Furthermore, pixel values
can either use explicit or differential coding. Explicitly coded
pixel values are interpreted literally with no extra computation,
while differentially coded pixel values are expressed as a signed,
per-channel distance from a known value.
3.2.1. Explicit coding (bit-by-bit)
Physical representation: rrrrrrrrggggggggbbbbbbbbaaaaaaaS(MSB)
Abstract interpretation: 32-bit full color pixel value in RGBA byte-
order; Two's complement representation takes one bit away from the
alpha channel for sign information (described in detail under "Chunk
format").
3.2.2. Differential coding (bit-by-bit)
Physical representation: rrrrrrrsgggggggsbbbbbbbsaaaaaasS(MSB)
Abstract interpretation: four signed, 8-bit integer values which are
packed together in RGBA byte-order; the bytes represent a per-
component signed distance between this pixel's value, and that of
some other pixel which is known prior. The last byte (alpha) is
treated as a 7-bit signed integer, leaving the most significant bit
of the double-word to represent its own independent sign. The author
Santin Expires 13 May 2024 [Page 6]
Internet-Draft Scalable Streaming Raster Graphics v1.0 November 2023
notes that the absolute value of the the packed pixel must be
obtained before properly decoding sign and magnitude information for
each individual color channel.
3.3. Chunk format
Chunks consist always of a uniform series of signed 32-bit integers.
Depending on the sign of a given integer in the stream, it may or may
not be followed by another associated integer. Beginning with the
first integer after the header, if it is positive, the next integer
will also be positive and represent a relative offset value to an
integer in the next chunk. If it is negative, the tentative pair is
considered incomplete, and the stream pointer does not advance.
Furthermore, the absolute value of this integer is used for all
further processing.
The first value of a given pair should always be treated as a
differentially coded pixel value.
The second value of a given pair, if it exists, should always be
treated as an offset value to the first child of this node. Further,
its two LSBs MUST be cleared to obtain the actual offset value. The
author notes that these two bits are reserved for future revisions of
the SSRG stream specification.
Readers are encouraged to read the next section and/or view the
reference implementation attached to this Internet-Draft for more
context and information about how one might properly decode SSRG
streams [surge-web].
4. Part B: Decoding algorithm
As was briefly discussed under "Introduction", the actual decoding
algorithm used by compliant implementations differs slightly in
complexity. In reality, the quad-tree based algorithm outlined
earlier only functions properly for square images with dimensions
equal to some power of two. Therefore, the author considers such an
implementation of the SSRG format incomplete, and lacking of a key
feature: _support for rectangular images of arbitrary dimensions._
As it turns out, this key feature can be quite easily implemented as
an extension of the original quad-tree algorithm, only instead of
every pixel of every "chunk" having exactly four subsamples, they may
have any arbitrary number of subsamples so long as the following
criteria are met:
1. The pixel in question precisely represents a square region of the
original image.
Santin Expires 13 May 2024 [Page 7]
Internet-Draft Scalable Streaming Raster Graphics v1.0 November 2023
2. The pixel is divisible into n x n spatially uniform sub-regions,
where n is prime.
Instituting these two requirements allows one to extend the quad-tree
decomposition method to work for square images of arbitrary size, as
the dimensions of the original image along both axes can be
factorized, and subsequently "chunked" based on each of these prime
factors. However, two exceptions to these criteria are needed to
adapt the algorithm to function for rectangular images of arbitrary
size:
For a rectangular image K with an aspect ratio of N:M,
1. The pixel representing the overall mean value of K CAN be
rectangular
2. This "root" pixel (residing in Chunk #0 of the image) is
divisible into N x M spatially uniform sub-regions, where N and M
are coprime.
Finally, having outlined these criteria, one can modify the quad-tree
decomposition algorithm discussed at the beginning of this document
such that the image tree can be subdivided into an arbitrary number
of square regions, per axis, at each recursive step. Note well that
both the aspect ratio and prime factorizations of the input image
dimensions can be computed from the width and height values provided
in the header alone.
The author recognizes that the explanation provided in this part of
the specification is somewhat ambiguous and lacks the type of precise
clarity required to write an appropriate implementation. For this
reason, she highly recommends viewing the official decoder
implementation attached to this document as a reference point [surge-
web].
5. Part C: HTTP conventions
All WWW servers that plan to support the SSRG specification should
properly use the following conventions in HTTP responses [RFC9113]
serving requests for SSRG format images.
5.1. MIME Headers
The Content-Type header to be used when serving SSRG formatted
streams should be: application/x-cfs-surge
Santin Expires 13 May 2024 [Page 8]
Internet-Draft Scalable Streaming Raster Graphics v1.0 November 2023
5.2. Compression format
To maintain competitive storage efficiency in comparison to other
popular lossless formats on the web, SSRG files should be encoded,
compressed, and stored _offline_. The author of this specification
highly recommends that GZip compression is used for SSRG streams both
at-rest and in-transit. This includes setting the Content-Encoding
response header to gzip whenever SSRG resource streams are requested.
6. Security Considerations
The author of this Internet-Draft does not anticipate that any
serious considerations should arise from the adoption and usage of
the SSRG specification on the Web.
7. IANA Considerations
This document has no IANA actions.
8. Author's Addresses
This document is written, edited, and maintained by Isabelle M.
Santin. Curious readers are encouraged to contact her at
isabelle@chosenfewsoftware.com
(mailto:isabelle@chosenfewsoftware.com).
9. References
9.1. Normative References
[RFC2119] S. Bradner, "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March
1997, https://www.rfc-editor.org/info/rfc2119 (https://www.rfc-
editor.org/info/rfc2119).
[RFC9113] M. Thomson, Ed., Mozilla, C. Benfield, Ed., Apple Inc.,
"HTTP/2", RFC 9113, DOI 10.17487/RFC9113, June 2022, https://www.rfc-
editor.org/info/rfc9113 (https://www.rfc-editor.org/info/rfc9113).
9.2. Informative References
[surge-web] "Example JavaScript SSRG stream decoder", November 2023,
https://github.com/IsaMorphic/surge-web
(https://github.com/IsaMorphic/surge-web).
Santin Expires 13 May 2024 [Page 9]
