RDH-SPI — Reversible Data Hiding: Sorting-and-Prediction Integration

Paper: Jian Li, Lingxiao Bo, Miaomiao Yang, Bin Ma, Shijun Xiang, Xiaolong Li, Zhenxing Qian, "A New Reversible Data Hiding Algorithm Based On Sorting-and-Prediction Integration" IEEE Transactions on Consumer Electronics, 2026. DOI: 10.1109/TCE.2026.3683088

---

What This Paper Does (Plain English)

Standard RDH methods embed data in the original pixel order — but textured regions cause large prediction errors, hurting image quality. This paper reorders pixels globally before embedding, so similar pixels are always adjacent. The key insight: if you embed data in a smooth sequence, you get both higher capacity and less distortion.

Two innovations:

1. 2D Sorting Criterion = prediction value × local complexity — groups similar pixels together across the whole image
2. Snake-like scanning — traverses the sorted matrix with alternating row directions to avoid abrupt transitions

Then four-layer LPVO embedding exploits this smooth domain for maximum capacity.

---

Full Pipeline Diagram

graph TD

    %% ─── INPUT ──────────────────────────────────────────────────────
    subgraph IN["INPUT"]
        A["📷 Cover Image\nM×N 8-bit grayscale\ne.g. 512×512 Baboon/Lake/Boat\nBoundary: 0→1, 255→254"]
    end

    %% ─── PARTITION ──────────────────────────────────────────────────
    subgraph PART["Step 1 — Image Partitioning  (Fig.1)"]
        B["🔀 Split into 4 Interleaved Regions\nI1 = even-row, even-col\nI2 = even-row, odd-col\nI3 = odd-row,  even-col\nI4 = odd-row,  odd-col\n\nEach pixel's 8 neighbours\nbelong to OTHER 3 regions ✓\n→ Prediction uses only unmodified pixels"]
    end

    %% ─── SORTING CRITERION ──────────────────────────────────────────
    subgraph SC["Step 2 — 2D Sorting Criterion  (Sec.II-A, Eq.1–9)"]

        C["📐 Prediction Value p  (Eq.1–8)\n8 neighbours x1..x8 (from other regions)\n\nHorizontal: h=(h1+h2+h3+h4)/4\n  h1=(x1+x2)/2  h2=(x2+x3)/2\n  h3=(x6+x7)/2  h4=(x7+x8)/2\n\nVertical:   v=(v1+v2+v3+v4)/4\n  v1=(x1+x4)/2  v2=(x4+x6)/2\n  v3=(x3+x5)/2  v4=(x5+x8)/2\n\nDiagonal:   o=(o1+o2+o3+o4)/4\n  o1=(x4+x2)/2  o2=(x4+x7)/2\n  o3=(x5+x2)/2  o4=(x5+x7)/2\n\nx̂ = (h+v+o)/3\np = ⌊x̂×λ+0.5⌋  (λ=2)"]

        D["🌊 Local Complexity l  (Eq.9)\n12 absolute-difference pairs:\n|x1-x2|+|x2-x3|+|x6-x7|+|x7-x8|\n+|x1-x4|+|x4-x6|+|x3-x5|+|x5-x8|\n+|x4-x2|+|x4-x7|+|x5-x2|+|x5-x7|\n\nLow l → smooth region → reliable prediction\nHigh l → textured region → less reliable"]
    end

    %% ─── SNAKE SCAN ─────────────────────────────────────────────────
    subgraph SS["Step 3 — Snake-like Scanning  (Sec.II-B, Fig.3)"]
        E["🐍 Build 2D Matrix\nRows    = prediction values  p ∈ [min(p), max(p)]\nColumns = complexity values l ∈ [min(l), max(l)]\n\nPlace each pixel at cell (p, l)\n(multiple pixels per cell allowed)"]

        F["↔ Snake Scan\nRow 1: columns left → right\nRow 2: columns right → left\nRow 3: left → right  ...\nSkip empty cells\n\nResult: sorted pixel sequence\nwith gradually-varying p and l\n→ smoother than [41]"]

        G["📊 Smoothness Metric  (Eq.10–11)\nLSi = Σ |xi+k - xi+k-1|  (window=7)\nOS = (1/n) Σ LSi\n\nProposed OS < [41] OS < original OS\n→ more compact 2D error histogram\n→ higher embedding efficiency"]
    end

    %% ─── FOUR-LAYER EMBEDDING ────────────────────────────────────────
    subgraph FL["Step 4 — Four-Layer LPVO Embedding  (Sec.III-A)"]

        H["Layer 1: Embed into I1\nReference: I2, I3, I4 (unmodified)\n→ Watermarked I1'"]

        I["Layer 2: Embed into I2\nReference: I1' (updated), I3, I4\n→ Watermarked I2'"]

        J["Layer 3: Embed into I3\nReference: I1', I2' (updated), I4\n→ Watermarked I3'"]

        K["Layer 4: Embed into I4\nReference: I1', I2', I3' (updated)\n→ Watermarked I4'"]

        L["📌 LPVO Prediction  [39]\nDivide sorted sequence into segments of size L\nFor each segment:\n  Sort by pixel value → ranks 1..L\n  e1 = x(1) - x(2)   ← min minus 2nd-min\n  e2 = x(L) - x(L-1) ← max minus 2nd-max\n  K pairs per segment (based on smoothness S)\n\nSegment smoothness S = Σ complexity l\nS ∈ [Ti-1, Ti) → K = 2(m+1-i) pairs\n\nEmbed via 2D histogram shift F [41]:\n  e=0 → embed 1 bit (shift by bit value)\n  e=±1 → shift to make room\n  |e|>1 → range shift (no embed)"]
    end

    %% ─── OUTPUT ──────────────────────────────────────────────────────
    subgraph WM["OUTPUT: Watermarked Image"]
        M["🖼 Watermarked Image\nAll 4 regions embedded\nAuxiliary info in LSBs of first row:\n  Segment size L (2×5 bits)\n  Thresholds (4×10M bits)\n  Final segment index (4×15 bits)"]
    end

    %% ─── EXTRACTION ──────────────────────────────────────────────────
    subgraph EXT["Step 5 — Extraction  (Sec.III-B)"]
        N["🔁 Reverse Layer Order\nI4' → I3' → I2' → I1'\n\nFor each layer (reverse):\n  Re-compute sorting criterion on current image\n  Re-sort → same segment structure\n  Extract bits using inverse mapping F⁻¹\n  Restore original pixel values\n\n✅ Perfect reversibility guaranteed"]
    end

    %% ─── RESULTS ─────────────────────────────────────────────────────
    subgraph RES["RESULTS"]
        O["✅ Verification\nPayload recovery:  PASS ✓\nImage restoration: PASS ✓\n\nTable II (10k bits): avg 60.13 dB\nTable III (20k bits): avg 56.52 dB\nKodak (20k bits): 60.43 dB\nvs RL-based [53]: 59.84 dB (+0.59 dB)"]
    end

    %% ─── CONNECTIONS ─────────────────────────────────────────────────
    A --> B
    B --> C
    B --> D
    C --> E
    D --> E
    E --> F
    F --> G
    G --> H
    H --> I
    I --> J
    J --> K
    K --> L
    L --> M
    M --> N
    N --> O

    IN --> PART
    PART --> SC
    SC --> SS
    SS --> FL
    FL --> WM
    WM --> EXT
    EXT --> RES

    %% ─── STYLES ──────────────────────────────────────────────────────
    style A  fill:#1e1e2e,stroke:#74c7ec,stroke-width:2px,color:#cdd6f4
    style B  fill:#1e1e2e,stroke:#fab387,stroke-width:2px,color:#cdd6f4
    style C  fill:#181825,stroke:#cba6f7,stroke-width:3px,color:#cdd6f4
    style D  fill:#181825,stroke:#cba6f7,stroke-width:3px,color:#cdd6f4
    style E  fill:#1e1e2e,stroke:#89b4fa,stroke-width:2px,color:#cdd6f4
    style F  fill:#181825,stroke:#89dceb,stroke-width:3px,color:#cdd6f4
    style G  fill:#1e1e2e,stroke:#89dceb,stroke-width:2px,color:#cdd6f4
    style H  fill:#002200,stroke:#a6e3a1,stroke-width:2px,color:#a6e3a1
    style I  fill:#002200,stroke:#a6e3a1,stroke-width:2px,color:#a6e3a1
    style J  fill:#002200,stroke:#a6e3a1,stroke-width:2px,color:#a6e3a1
    style K  fill:#002200,stroke:#a6e3a1,stroke-width:2px,color:#a6e3a1
    style L  fill:#181825,stroke:#f9e2af,stroke-width:3px,color:#cdd6f4
    style M  fill:#1e1e2e,stroke:#89b4fa,stroke-width:2px,color:#cdd6f4
    style N  fill:#1e1e2e,stroke:#f38ba8,stroke-width:2px,color:#cdd6f4
    style O  fill:#002200,stroke:#a6e3a1,stroke-width:3px,color:#a6e3a1

Loading

---

Paper Flow — Plain English

#	Step	What it does	Why
1	Partition	Split image into 4 interleaved groups I1–I4	Neighbours always from other groups → stable prediction
2a	Predict	Compute x̂ from horizontal + vertical + diagonal averages of 8 neighbours	Prediction value p = smooth stable sorting key
2b	Complexity	Sum 12 absolute differences among 8 neighbours	Complexity l tells us how textured the region is
3a	2D Matrix	Place each pixel at matrix position (p, l)	Groups pixels by both similarity AND smoothness
3b	Snake scan	Traverse matrix alternating left↔right per row	Avoids abrupt transitions between complexity levels
4	LPVO embed	Sort segment by value, use 2nd-min/2nd-max as predictors, embed into error=0 positions	Location-based PVO: more efficient than standard PVO
5	Extract	Reverse layer order, re-compute same criterion, inverse histogram shift	Exact reconstruction of both image and payload

Key Insight: Why Snake-Scan Beats Simple Sort

Simple sort [41]:  Sort by p, then by l when p equal
  → When p changes to new value, l jumps from high back to low
  → Abrupt transitions in local complexity
  → Larger prediction errors at those boundaries

Snake scan (ours): Odd rows left→right, even rows right→left
  → When p changes, l continues from where it was (no jump back)
  → Smoother complexity curve → smaller prediction errors
  → More errors near 0 → higher embedding capacity

---

Key Equations

Eq.	Formula	Step
Eq.1–2	h = (h1+h2+h3+h4)/4, h1=(x1+x2)/2, …	Horizontal prediction feature
Eq.3–4	v = (v1+v2+v3+v4)/4	Vertical prediction feature
Eq.5–6	o = (o1+o2+o3+o4)/4	Diagonal prediction feature
Eq.7	x̂ = (h+v+o)/3	Initial pixel prediction
Eq.8	p = ⌊x̂×λ+0.5⌋, λ=2	Quantized sorting key
Eq.9	l = Σ 12 adj-diff pairs	Local complexity
Eq.10–11	OS = (1/n) Σ LSi, LSi = 7-window abs-diff	Smoothness metric
LPVO	e1 = x(1) - x(2), e2 = x(L) - x(L-1)	Prediction errors
Embed	`e=0 → shift by bit; e=±1 → shift;	e

---

4-Layer Embedding Structure

Cover image X:
  I1 (even,even) ─┐
  I2 (even,odd)  ─┤ 4 interleaved grids
  I3 (odd,even)  ─┤ (like 4-color checkerboard)
  I4 (odd,odd)   ─┘

Embedding order:
  Layer 1: Sort I1 using {I2,I3,I4} → embed → I1'
  Layer 2: Sort I2 using {I1',I3,I4} → embed → I2'
  Layer 3: Sort I3 using {I1',I2',I4} → embed → I3'
  Layer 4: Sort I4 using {I1',I2',I3'} → embed → I4'

Capacity per layer (Boat 512×512):
  I1: 5842 bits  I2: 5680 bits
  I3: 5537 bits  I4: 5312 bits
  Total: ~22,371 bits  (only 9% degradation layer to layer)

Extraction order (reverse):
  I4' → I3' → I2' → I1' → restored X

---

Results (Paper Tables II/III/V)

Standard Images (PSNR in dB)

Image	10k bits	20k bits
Boat	60.11	55.87
Lake	61.59	56.66
Elaine	59.78	54.95
Peppers	60.55	56.61
Barbara	62.26	58.51
Average	60.13	56.52

Kodak Dataset (20k bits, avg PSNR)

Method	Avg PSNR
[22] Ni HS	60.09
[41] Global Sort	60.39
[53] RL-based	59.84
Proposed	60.43

---

Usage

cd 'c:\iiitvd\New Paper 19.05.2026\RDH_SPI_Matlab'
RDH_SPI

Expected output:

=== RDH: Sorting-and-Prediction Integration ===
    Li et al., IEEE Trans. Consumer Electronics, 2026

Image: 64 × 64 grayscale
Payload: 800 bits

--- EMBEDDING ---
  Layer 1 (I1): X bits embedded, capacity=Y
  Layer 2 (I2): X bits embedded, capacity=Y
  ...
Total embedded: 800 / 800 bits
PSNR: ~58+ dB

--- EXTRACTION ---
Payload recovery:   PASS ✓
Image restoration:  PASS ✓

Files

File	Description
RDH_SPI.m	Complete MATLAB implementation v1.0
README.md	This file — pipeline diagram + equations

Requirements

• MATLAB R2025b+ · No extra toolboxes needed