{"id":"d21fbcbb-19e2-45df-9fc1-674f13d5d5a1","arxiv_id":"2411.15824","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Variable-size symmetry-based graph Fourier transforms achieve 6.23% BD-rate savings over VVC explicit multiple transform selection at matched complexity in a simulation.","lead":"This paper extends a symmetry-based graph transform family from 8x8 blocks to arbitrary square block sizes and reports bitrate savings of 6.23% to 9.29% over the explicit multiple transform selection used in the VVC video standard, in a simulated coding framework. The result matters because it offers a non-learned, low-complexity transform alternative that could reduce bitrate in future image and video compression standards.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 6.23%/9.29% BD-rate claims rest on an entropy-based residual-domain simulation that omits transform-index signaling and the intra prediction loop; actual VTM gains may be substantially smaller.","rationale":"The reader's weakest_assumption identifies the same root concern: the custom simulation uses an entropy-based rate estimate and per-block transform selection that does not model VVC's arithmetic coder, context modeling, or joint mode/transform decisions. My stress-test sharpens this by pointing to two concrete omissions: transform-index signaling in the rate and the intra prediction feedback loop. Both omissions systematically favor the SBGFTs, which have far more candidate transforms and are evaluated outside the predictive coding loop. The paper's mathematical construction of variable-size SBGFTs appears sound, and the pixel-domain experiments at least include arithmetic coding and fixed-length index bits; however, the headline residual-domain BD-rate numbers do not. Because the issue is addressable by an actual VTM integration or a more faithful rate model, CONDITIONAL remains the appropriate verdict: the central construction is plausible, but the central empirical claim is not yet established as a real codec gain.","tokens_in":20203,"tokens_out":5780,"duration_ms":56640,"concrete_test":"Integrate the F5 configuration into VTM: for each intra luma prediction mode, add the corresponding top-5 SBGFTs as extra candidates in the Explicit MTS transform search, keeping the same QPs, test sequences, and BD-rate metrics, and compare against unmodified VTM Explicit MTS. If the BD-rate saving is substantially below 6.23% (or becomes negative), the entropy-based simulation is confirmed to be an unreliable proxy.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that variable-size SBGFTs outperform VVC Explicit MTS by 9.29% (full set) and 6.23% (top-5 per prediction mode) in BD-rate, with matched encoding complexity. These numbers come from a custom simulation, not a real VVC integration. In Sec. IV-C, residual blocks are extracted from VVC intra prediction and then transform selection uses the RD cost in Eq. (10), where the rate RGi is the Shannon entropy of the quantized coefficients only. No transform-index bits are included in the rate, no arithmetic coder or CABAC context modeling is used, and there is no reconstruction/prediction loop. The BD-rate curves in Fig. 10 and Table IV are built from this entropy proxy. This is load-bearing because the SBGFT sets are much larger than the MTS set: a 64×64 block has 8N−24 = 488 candidate transforms, so the transform-index side information would be far larger than the 1–2 bit MTS flag. Omitting this overhead and ignoring the effect of transform choices on later intra predictions can both inflate the apparent gain. The abstract's phrasing 'outperform the primary transforms integrated in the explicit MTS used in the latest VVC intra-coding' implies a degree of codec integration that the experiments do not actually provide.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper extends the authors' earlier 8x8 Symmetry-based Graph Fourier Transforms (SBGFTs) to arbitrary NxN blocks. The construction adds symmetric connections to a 2D grid graph along horizontal, vertical, diagonal, and anti-diagonal reflection axes, yielding a deterministic dictionary of 8N-24 non-separable transforms with fast implementations based on edge/node symmetry. The authors evaluate the transforms in a multiple-transform RDOT framework, first in the pixel domain against a DCT baseline and then on VVC intra-prediction residuals against the explicit Multiple Transform Selection (MTS) baseline. In the residual-domain simulation, the full variable-size SBGFT set reports a 9.29% BD-rate saving, and a low-complexity configuration using only the top-5 SBGFTs per prediction mode reports a 6.23% saving with roughly unchanged encoding complexity. The paper also analyzes residual symmetry statistics and uses a held-out dataset to select mode-dependent transform subsets.","tokens_in":20470,"tokens_out":6723,"duration_ms":63195,"significance":"If the reported coding gains survive integration into a real VVC-like codec, this would be a meaningful contribution to transform coding: the transform family is deterministic and data-independent, avoids training-set dependence, exploits symmetry for fast non-separable transforms, and includes a practical complexity-reduction strategy. The authors provide a MATLAB implementation, and the low-complexity subset selection is evaluated on separate training and test sequences, which is a methodological strength. The mathematical construction and symmetry-based complexity analysis are clearly presented and appear sound. However, the headline performance claims are currently based on a simplified residual-domain simulation that estimates rate with Shannon entropy and omits transform-index signaling, so the practical significance is contingent on closing that evaluation gap.","major_comments":[{"comment":"The headline BD-rate savings (9.29% for configuration F and 6.23% for F5) are computed in a residual-domain simulation where the rate term R_Gi in Eq. (10) is the Shannon entropy of the quantized transform coefficients only. No transform-index bits are charged for the SBGFT dictionaries, even though the full set has 8N-24 transforms (488 for 64x64 blocks) and the F5 configuration still needs a per-block index among its 5 transforms. The baseline MTS set has only 5 transforms, so omitting side information systematically favors the proposed large dictionaries. Please add the transform-index overhead to the RD cost or, preferably, integrate the transforms into a full VVC-like encoder with arithmetic coding and index signaling, and revise the abstract's claim that SBGFTs 'outperform the primary transforms integrated in the explicit MTS' accordingly.","section":"Sec. IV-C, Eq. (10), Table IV"},{"comment":"The experimental protocol operates on residual blocks pre-extracted from VVC intra prediction and then selects transforms independently per block using the RD cost in Eq. (10). This setup does not include CABAC context modeling, coefficient scanning, or a reconstruction/prediction loop, so it cannot capture how transform choices affect subsequent intra prediction or how the true coded rate responds to different transform dictionaries. Because the entropy proxy is used to select among a much larger set of candidates than the MTS baseline, the reported BD-rate curves in Fig. 10 may be optimistic. I request either a VTM-based evaluation for at least a subset of the test sequences, or an explicit analysis quantifying the gap between the Shannon-entropy rate and the actual arithmetic-coded rate in this setting.","section":"Sec. IV-C, Fig. 10"},{"comment":"The claim that configuration F5 matches the MTS baseline encoding complexity (Delta_TE approximately 0.0%) is not established by the reported methodology. The paper argues that using C=5 candidate transforms matches the number of MTS candidates, but the cost per candidate is not comparable: the proposed SBGFTs are non-separable and require O(N^4) multiplications according to Table I, whereas MTS primary transforms are separable and cheaper. Please report measured encoding times for F5 using the same timing protocol applied to configurations E and F in Sec. IV-D, or explain why the transform search cost is negligible relative to other encoder tasks.","section":"Sec. IV-D, Sec. IV-E, Table IV"}],"minor_comments":[{"comment":"The manuscript contains unresolved citation markers '[?]' in Sec. I and an extraneous block from another paper (IEEE TSP 2024, references [59]-[76] and unrelated author biographies) after the reference list. These must be removed or completed before submission.","section":"Sec. I and reference list"},{"comment":"The notation for the low-complexity configuration is inconsistent: Table II uses 'FC', while the text and Table IV use 'F5'. Please unify the notation and state explicitly that F5 is the C=5 instance of FC.","section":"Table II and Sec. IV-E"},{"comment":"References [24] and [28] are the same paper (Lu and Ortega, ICASSP 2017). Please merge them and correct the in-text citations.","section":"References [24] and [28]"},{"comment":"The caption mentions a red dashed line indicating the percentage of blocks with S_s > 0.7 in at least one symmetry, but this line is not visible in all panels. Please make the plot consistent across block sizes.","section":"Fig. 6"},{"comment":"Please clarify how the counts in Eqs. (4)-(7) sum to 8N-24, especially the handling of the duplicate at n=1 in Algorithm 2 and the behavior for the smallest supported size N=4.","section":"Sec. III-A, Algorithms 1-2"},{"comment":"Only four test sequences are used and BD-rate is reported as a single aggregate number. Per-sequence results would help assess the variability of the reported 6.23% and 9.29% savings.","section":"Sec. IV-C"}],"recommendation":"major_revision","confidential_remarks":"The underlying transform construction is interesting and the deterministic, symmetry-based design is a genuine strength. The main obstacle is the evaluation gap: the central BD-rate claims come from an entropy-based residual-domain simulation that omits transform-index signaling and a full codec loop. I believe this is fixable within a revision, either by adding a real VVC integration or by substantially reframing the claims as a residual-domain study and including the index overhead. Please also verify that the submitted PDF does not contain the extraneous IEEE TSP pages and unresolved citation markers that appear in the current version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: the variable-size SBGFT generalization is a clean, well-defined piece of transform design, but the headline 6.23%/9.29% BD-rate numbers come from a residual-domain simulation that uses Shannon entropy of quantized coefficients as the rate and omits transform-index signaling. Treat those numbers as upper bounds, not as measured VVC gains.\n\nWhat is genuinely new: the authors extend their own 8×8 symmetric graph construction to arbitrary even N, define the 8N−24 graph family, give explicit algorithms, and show the symmetry structure that enables fast non-separable implementation. The low-complexity F5 configuration—top five graphs per prediction mode, chosen on separated training sequences—is a sensible way to keep the RDOT search at MTS-like complexity. The complexity table is honest: the full set doubles encoding time, F5 matches baseline, and decoding is unchanged. The design is deterministic, data-independent, and the MATLAB code is available. That is real value.\n\nThe soft spots are concentrated in the evaluation. In the residual experiments, the rate in Eq. (10) is the Shannon entropy of the quantized coefficients only. For a 64×64 block the full SBGFT set has 488 candidate transforms; no bits for that index are included in the rate. The pixel-domain experiments did include a fixed-length graph index, but the residual experiments appear not to. Also, residual blocks are extracted once from VVC intra prediction and transform selection is per block, so there is no reconstruction loop and no joint transform/prediction decision. Both effects can only inflate the apparent gain relative to a real VVC integration. The abstract's wording, \"outperform the primary transforms integrated in the explicit MTS,\" overstates what the simulation actually shows. I also want the authors to clean up the unresolved \"[?]\" citation placeholders and the appended unrelated IEEE article text at the end of the PDF; that looks like a production accident, but as submitted it is a real defect.\n\nThat said, the central construction is not flawed. I expect the gains to shrink in a real codec, but this transform family is cheap, deterministic, and genuinely different from separable sinusoidal transforms, and the prediction-mode pruning idea deserves testing inside VTM. This paper deserves a refereed revision: keep the construction, add a real VVC experiment or at least a transform-index signaling model and a reconstruction loop, and recalibrate the abstract. I would engage with it.","headline":"The N×N SBGFT construction is real and worth taking seriously, but the headline BD-rate savings are measured in an entropy-based residual simulation without transform-index bits, so expect the gains to shrink in a real VVC integration.","tokens_in":20976,"tokens_out":2643,"would_cite":true,"duration_ms":24674,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Variable-size symmetry-based graph Fourier transforms beat VVC's explicit multiple transform selection on intra residuals, cutting bit rate by 6.23–9.29% at comparable complexity.","keywords":["graph Fourier transform","image compression","video compression","multiple transform selection","VVC","symmetric graphs","intra prediction residuals","rate-distortion optimization"],"falsifier":"Run the per-prediction-mode top-5 SBGFT sets inside a full VVC encoder on the same test sequences and QPs, and measure BD-rate against the Explicit MTS mode; if the simplified rate model in this paper overstates the real codec's behavior, the measured saving will fall below 6.23% or become negative.","tokens_in":20003,"feed_emoji":"📉","tokens_out":9285,"duration_ms":78098,"temperature":0.7,"pith_summary":"This paper claims that a fixed, data-independent family of non-separable graph Fourier transforms can compete with and beat the transform choices engineered into the VVC video standard. The authors generalise their earlier $8\\times8$ Symmetry-based Graph Fourier Transforms (SBGFTs) to any square block size $N \\times N$, building symmetric graphs on the image grid and using the graph Laplacian's eigenvectors as transform bases. Because the graphs are symmetric, the transforms have fast butterfly implementations, so no training data is needed and decoding complexity stays at the baseline. In a VVC-like framework acting on intra-prediction residuals, the full variable-size SBGFT set saves 9.29% bit rate against VVC's Explicit Multiple Transform Selection, and a restricted per-prediction-mode set of five transforms still saves 6.23% with essentially no extra encoding cost. If these numbers survive integration into a real codec, they would justify replacing or supplementing standard sinusoidal transforms with symmetry-based graph transforms.","feed_headline":"Symmetry-based graph transforms beat VVC's MTS by up to 9.29%","feed_subtitle":"A data-free transform family for N×N blocks matches MTS complexity while saving bits on intra residuals.","key_machinery":"The load-bearing object is the Symmetry-based Graph Fourier Transform (SBGFT): a GFT whose graph is a 2D grid graph augmented with weight-1 edges connecting node pairs that are symmetric about a reflection axis. For each block size $N$, the construction enumerates all valid horizontal, vertical, diagonal, and anti-diagonal axes, yielding $8N-24$ graphs, and the eigenvectors of each graph's Laplacian matrix $L = D - W$ form the transform basis. Two symmetry properties do the work: edge symmetry (ES) makes the Laplacian bisymmetric, enabling fast butterfly implementations, and node symmetry (NS) around the reflection axis makes low-frequency basis vectors take similar values on connected symmetric nodes. The paper quantifies this match with a symmetry ratio $S_s$, defined on a graph's support, and shows both that residual blocks have high symmetry along these axes and that SBGFT eigenvectors have nearly perfect symmetry ratios. This combination — sparse, structure-matching bases plus fast computation without any training data — is what carries the compression gain.","core_discovery":"The central discovery is that the eigenvectors of symmetric grid graphs are naturally matched to the structure of intra-prediction residuals, so a Graph Fourier Transform built from them compacts those residuals more tightly than the DCT-II, DCT-VIII, and DST-VII transforms used in VVC's Explicit MTS. A Symmetry-based Graph is constructed by taking the $N \\times N$ grid graph — whose Laplacian eigenvectors are exactly the DCT basis — and adding unit-weight edges between every pair of nodes that are mirror images across a reflection axis in one of four directions (horizontal, vertical, diagonal, anti-diagonal). Each valid axis yields one graph, giving $8N-24$ transforms per block size; the added edges force low-frequency eigenvectors to be locally symmetric, which matches the symmetry found in real residual blocks. The resulting non-separable transforms retain fast implementations because their Laplacians are bisymmetric, and the paper reports BD-rate reductions of 9.29% for the full set and 6.23% for a five-transform-per-mode subset over the VVC baseline.","pith_inferences":["A full VVC integration test would settle whether the entropy-based rate estimate used here under- or over-states the real coding cost; the 9.29% and 6.23% figures are the paper's main claims to reproduce.","The same symmetry-based construction might transfer to chroma residuals or inter-prediction residuals, where directional structure is also common, although the paper does not test those cases.","The per-mode histograms suggest a lightweight signaling scheme could encode the transform index implicitly from the prediction mode, reducing side-information overhead beyond what the paper measures.","The paper's symmetry-ratio data imply that residual blocks are most symmetric along sub-diagonal axes close to the grid center; a codec using rotated prediction directions might shift which reflection axes are optimal."],"forward_implications":["The primary transforms used in VVC's Explicit MTS can be replaced by SBGFTs for every square block size from $4\\times4$ to $64\\times64$ while improving rate-distortion performance.","Restricting each prediction mode to its five most frequently optimal SBGFTs recovers most of the gain, so the transform set size need not grow with block size.","Variable-size SBGFTs roughly double the gain of $8\\times8$-only SBGFTs, so the extension to larger blocks is where most of the benefit lies.","Since decoding time is unchanged and encoding time for the restricted set matches the baseline, the approach is feasible as a practical codec component."],"supporting_citations":[{"why":"Defines the 8×8 SBGFT construction that this paper generalizes to arbitrary square block sizes.","marker":"[21]"},{"why":"Shows the 8×8 SBGFTs beat KLT and Sparse Orthonormal Transform alternatives in energy approximation, motivating the extension.","marker":"[22]"},{"why":"Provides the symmetry-based fast GFT implementation that keeps the non-separable SBGFTs computationally practical.","marker":"[25]"},{"why":"Supplies the eigenvector symmetry result for bisymmetric matrices behind the complexity reduction and the symmetric basis structure.","marker":"[27]"},{"why":"Establishes the rate-distortion optimized transform framework used to select among transforms for each block.","marker":"[12]"},{"why":"Defines the VVC standard and its Explicit MTS configuration, the baseline against which SBGFTs are measured.","marker":"[5]"},{"why":"Identifies the 2D grid graph Laplacian eigenvectors with the DCT basis, anchoring the SBG construction to standard transforms.","marker":"[26]"},{"why":"Earlier fast-implementation result for symmetric non-separable grid transforms that motivates the edge-symmetry property in SBG designs.","marker":"[24]"}],"fun_headline_variants":["Symmetry-based graph transforms beat VVC's MTS by up to 9.29%","SBGFTs outcode VVC's MTS with 9.29% bitrate savings","No data needed: symmetry-based Graph Fourier Transforms top MTS","Variable-size SBGFTs: fast, data-free, and beat VVC's MTS","Symmetry in graphs yields 9.29% bitrate cut over VVC's MTS"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reported savings come from an experiment that approximates bit rate by the entropy of quantized coefficients and picks each block's transform independently; if that approximation does not track how a real VVC encoder spends bits, the savings could shrink or vanish.","fun_headline_variants_meta":{"raw":{"variants":["Symmetry-based graph transforms beat VVC's MTS by up to 9.29%","SBGFTs outcode VVC's MTS with 9.29% bitrate savings","No data needed: symmetry-based Graph Fourier Transforms top MTS","Variable-size SBGFTs: fast, data-free, and beat VVC's MTS","Symmetry in graphs yields 9.29% bitrate cut over VVC's MTS"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000702,"raw_usage":{"total_tokens":3216,"prompt_tokens":1039,"completion_tokens":2177,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":655,"completion_tokens_details":{"reasoning_tokens":2061}},"tokens_in":655,"tokens_out":2177,"duration_ms":13941,"temperature":1.0,"reasoning_tokens":2061,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:51:36.267143+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the per-prediction-mode top-5 SBGFT sets inside a full VVC encoder on the same test sequences and QPs, and measure BD-rate against the Explicit MTS mode; if the simplified rate model in this paper overstates the real codec's behavior, the measured saving will fall below 6.23% or become negative.","supporting_citations":[{"cited_title":"Coding of image intra prediction residuals using symmetric graphs,","cited_arxiv_id":null,"evidence_quote":"Defines the 8×8 SBGFT construction that this paper generalizes to arbitrary square block sizes."},{"cited_title":"Symmetry-based graph Fourier transforms: Are they optimal for image compression?","cited_arxiv_id":null,"evidence_quote":"Shows the 8×8 SBGFTs beat KLT and Sparse Orthonormal Transform alternatives in energy approximation, motivating the extension."},{"cited_title":"Fast graph Fourier transforms based on graph symmetry and bipartition,","cited_arxiv_id":null,"evidence_quote":"Provides the symmetry-based fast GFT implementation that keeps the non-separable SBGFTs computationally practical."},{"cited_title":"Eigenvalues and eigenvectors of symmetric centrosymmetric matrices,","cited_arxiv_id":null,"evidence_quote":"Supplies the eigenvector symmetry result for bisymmetric matrices behind the complexity reduction and the symmetric basis structure."},{"cited_title":"Video coding with rate- distortion optimized transform,","cited_arxiv_id":null,"evidence_quote":"Establishes the rate-distortion optimized transform framework used to select among transforms for each block."},{"cited_title":"Overview of the Versatile Video Coding (VVC) standard and its applications,","cited_arxiv_id":null,"evidence_quote":"Defines the VVC standard and its Explicit MTS configuration, the baseline against which SBGFTs are measured."},{"cited_title":"The discrete cosine transform,","cited_arxiv_id":null,"evidence_quote":"Identifies the 2D grid graph Laplacian eigenvectors with the DCT basis, anchoring the SBG construction to standard transforms."},{"cited_title":"Fast implementation for symmetric non- separable transforms based on grids,","cited_arxiv_id":null,"evidence_quote":"Earlier fast-implementation result for symmetric non-separable grid transforms that motivates the edge-symmetry property in SBG designs."}],"review_version":1}