Four Category Labeling and Block Partitioning Boost Encrypted Image Data Capacity

The rapid expansion of global multimedia transmission has made the outsourcing of visual assets to third-party cloud repositories an indispensable facet of modern digital computing, yet this trend creates substantial vulnerabilities regarding the privacy and confidentiality of sensitive visual records. Reversible Data Hiding in Encrypted Images, commonly abbreviated as RDHEI, addresses this fundamental tension by establishing mechanisms wherein secret metadata can be embedded directly within enciphered pixel arrays while guaranteeing both error-free extraction of the hidden payload and mathematically lossless reconstruction of the original uncompressed image. In a comprehensive study published in Discover Computing, researchers Cheng-Ta Huang, Wai-Long Cheang, Hao-Yu Weng, Wei-Jen Wang, and Chi-Yao Weng present an advanced framework designated as Improved Efficient Parametric Binary Tree Labeling, or IEPBTL. By overcoming the sub-optimal classification rules and rigid global processing constraints of prior binary tree schemes, the newly designed methodology introduces a refined four-tier pixel categorization protocol combined with localized block-based preprocessing. Experimental evaluations across standardized benchmark images and extensive multi-thousand image repositories confirm that this architectural design significantly curbs auxiliary data overhead while expanding the upper boundaries of achievable net embedding payload capacity.

The conceptual foundation of reversible data hiding originated within the unencrypted plaintext domain, relying on classical signal processing techniques including difference expansion, histogram shifting, prediction error expansion, and pixel value ordering to create transient storage room without permanently corrupting carrier representations. While contemporary machine learning integrations such as convolutional attention networks and collaborative encoder-decoder models have demonstrated high embedding performance in plaintext environments, they operate under the prerequisite that cover content can remain completely exposed throughout transmission. To resolve privacy concerns, RDHEI emerged as an intersection between cryptographic protection and reversible signal processing. Contemporary RDHEI methodologies are structurally divided into two sequential paradigms: Vacating Room After Encryption, known as VRAE, and Reserving Room Before Encryption, termed RRBE. Under VRAE pipelines, the host image is subjected to cryptographic scrambling before any redundant space is sought. However, because robust encryption systematically randomizes spatial pixel distributions, inter-pixel correlation is destroyed, severely constraining downstream embedding rates. Conversely, RRBE architectures execute preprocessing operations directly upon the unencrypted carrier to reserve embedding space before cryptographic primitives are applied, exploiting natural spatial correlation through predictive encoding to achieve vastly superior payload capacities.

Within the RRBE domain, parametric binary tree labeling encoding methodologies have gained considerable prominence as effective mechanisms for structuring prediction error distributions into compact bit representations. The lineage of this technical trajectory began with the baseline Parametric Binary Tree Labeling framework introduced by S. Yi and colleagues, which partitioned image pixels into reference pixels, embeddable pixels, and non-embeddable pixels governed by tunable tree depth parameters. Wu and co-workers subsequently advanced this model into Improved Parametric Binary Tree Labeling by optimizing reference pixel selection, utilizing solely the uppermost boundary row and leftmost boundary column rather than repetitive sub-region anchors to conserve carrier capacity. Subsequent refinements by Feng and later by Ren under the banner of Efficient Parametric Binary Tree Labeling incorporated an additional zero-overhead category termed self-recording pixels, which allowed specific prediction errors to encode their own structural boundaries without requiring external registry space. Despite these progressive advancements, existing frameworks retained a systemic inefficiency: pixels failing the embeddable criteria were frequently relegated to non-embeddable classes requiring extensive auxiliary overhead, while prevailing systems enforced global parameter settings that completely ignored spatial variance across heterogeneous image regions.

To overcome these architectural constraints, the IEPBTL framework formulates an expanded classification model that divides carrier elements into four independent, mutually exclusive designations: embeddable pixels, self-recording pixels 1, self-recording pixels 2, and non-embeddable pixels. The categorization is determined through mathematical relationships dictated by tree depth variables alpha and gamma, operating over calculated prediction errors. Embeddable pixels are processed by converting their encrypted bit sequences, reversing the order, substituting the leading alpha bits with a standardized identifier codeword, and reversing the sequence back to release eight minus alpha bits for auxiliary or secret payload placement. Self-recording pixels 2 apply an identical sign and offset representation to capture an expanded interval of prediction errors that previously defaulted to non-embeddable status. Non-embeddable pixels are assigned a null value while their true pristine values are recorded as external auxiliary data, meaning the expansion of self-recording classes directly diminishes auxiliary data burdens.

Complementing this classification strategy, the research team implemented a localized preprocessing framework based on independent block partitioning, directly resolving the inefficiencies caused by global embedding assumptions. Conventional RDHEI schemes enforce identical labeling parameters across an entire image canvas, failing to exploit local areas of extreme smoothness where prediction errors are tightly concentrated near zero. Under the proposed preprocessing routine, the carrier image is systematically segmented into regular grids of dimension block height by block width, excluding the outermost boundary row and column which are preserved as structural references. To ensure high predictive accuracy across diverse localized textures, each individual block incorporates a composite dual-predictor mechanism. Pixels situated along the upper and left inner borders of each block are predicted using the Median Edge Detector algorithm, which selects directional edge approximations based on adjacent pixel comparisons. The remaining interior pixels within the block are subsequently evaluated using the Gradient-Adjusted Predictor, which computes horizontal and vertical local gradient differences to dynamically select between directional interpolations and weighted edge estimators.

Following localized prediction error derivation, the framework executes a rigorous optimization protocol for every individual block prior to the initiation of data embedding. Because the selection of parameters alpha and gamma directly governs the proportion of embeddable pixels against non-embeddable elements, the system evaluates all possible integer configurations across the discrete parameter ranges where alpha spans from one to seven and gamma spans from two to seven. This bounded search space limits the required evaluations to a maximum of forty-two candidate pairs per block. The objective function calculates the net embeddable capacity of the block by multiplying the quantity of embeddable pixels by their vacated bit allowance of eight minus alpha, and subtracting the severe storage penalty incurred by non-embeddable pixels, which each require eight bits of auxiliary recording. If the peak calculated capacity for a block evaluates to a negative number, the algorithm designates the segment as a non-embeddable block, assigning both alpha and gamma optimal values of zero. Non-embeddable blocks undergo standard encryption without undergoing pixel labeling or payload embedding, completely eliminating auxiliary data recording penalties for complex local patches.

The generated structural metadata and spatial parameters are bundled into a systematically encrypted auxiliary information package necessary for downstream extraction and cover reconstruction. This auxiliary data structure comprises the global block dimensions recorded in eight bits, the computed optimal alpha and gamma pairs across all partitioned blocks consuming six bits per block, the uncompressed values of the pristine boundary reference pixels requiring eight bits per boundary element, a twenty-two-bit field denoting the total auxiliary information length, and the binary values of any active non-embeddable pixels. Auxiliary Information B, containing the secondary parameters and non-embeddable pixel data, is joined with the length indicator, encrypted via bitwise XOR operations, and embedded sequentially into the primary vacated bits of the designated embeddable pixels before secret payloads are inserted.

Cryptographic integrity and role separation are strictly enforced through a three-party key management model that establishes independent access privileges among content owners, data hiders, and end recipients. The architecture utilizes three distinct, uniformly generated 128-bit cryptographic secret keys: the image encryption key ke, the auxiliary information encryption key km, and the data encryption key kd. The image encryption key initializes a cryptographically secure pseudorandom number generator to generate an eight-bit pseudorandom matrix matching the full carrier dimensions, executing pixel-wise XOR encipherment. The auxiliary and payload keys similarly drive independent pseudorandom sequence generators to protect metadata and secret bitstreams. This distinct cryptographic decoupling ensures that possession of specific key combinations dictates operational privileges. An entity possessing solely the auxiliary key km and image key ke can completely reconstruct the original cover image without gaining access to secret payloads. Conversely, a recipient possessing km and kd can identify embeddable locations and recover the hidden payload while remaining incapable of decrypting the visual cover. Full image and payload retrieval requires the complete triad of keys, supported by a joint brute-force search space of two to the power of 384.

The quantitative performance of the IEPBTL framework was subjected to rigorous empirical evaluation across five classic benchmark images—Man, Airplane, Baboon, Lake, and Peppers—as well as three large-scale image repositories comprising UCID, BOSSbase, and the 256 by 256 resolution version of BOWS2. In baseline evaluations without preprocessing where alpha and gamma were fixed at five and three, IEPBTL achieved an average embedding rate of 2.4179 bits per pixel across the classic images, reaching peak rates of 2.7022 bpp on Man, 2.7907 bpp on Airplane, and 2.7644 bpp on Peppers. When combined with the proposed block-based preprocessing at a sixteen by sixteen block size, payload capacities expanded dramatically, achieving 3.0043 bpp on Man, 3.6408 bpp on Airplane, 1.8312 bpp on Baboon, 2.6846 bpp on Lake, and 3.0370 bpp on Peppers, outperforming competing techniques including EPBTL, MEPBTL, and dual-stage compression schemes. On extensive datasets under an eight by eight block configuration, the method established average embedding capacities of 3.2008 bpp on UCID, 3.7283 bpp on BOSSbase, and 3.3313 bpp on BOWS2, consistently exceeding the three-bit-per-pixel threshold across all tested block configurations.

Despite these substantial payload enhancements, the researchers identified specific constraints associated with structural image complexity, which informed their development of adaptive selection criteria and rigorous security verifications. In highly complex, irregular textures exemplified by the standard Baboon image, the auxiliary information volume under fixed parameters increased by 8.95 percent compared to MEPBTL because non-embeddable pixels require eight bits in IEPBTL rather than gamma bits; however, this was counterbalanced across smoother images where auxiliary data dropped by over twenty percent. To guide optimal parameter selection, the authors introduced an image complexity metric G based on horizontal and vertical Mean Absolute Difference calculations, establishing empirical complexity thresholds of 7.2539 for eight by eight blocks and 3.3662 for sixteen by sixteen blocks. Rigorous statistical evaluations confirmed that marked images exhibit uniform pixel histograms, Shannon entropy values approaching the theoretical eight-bit limit of eight, adjacent pixel correlation coefficients dropping from near unity to near zero, and visual degradation metrics featuring PSNR values between 7.7 and 9.5 decibels and SSIM scores approaching zero, while maintaining a linear computational time complexity of O(M × N).

Subject of Research: Reversible data hiding in encrypted images using improved efficient parametric binary tree labeling

Article Title: Secure reversible data hiding system in encrypted images for improving payload using efficient parametric binary tree labeling

Article References: Huang, C.-T., Cheang, W.-L., Weng, H.-Y., Wang, W.-J., & Weng, C.-Y. (2026). Secure reversible data hiding system in encrypted images for improving payload using efficient parametric binary tree labeling. Discover Computing, 29(1), Article 771. https://doi.org/10.1007/s10791-026-10740-7

Image Credits: AI Generated

DOI: 10.1007/s10791-026-10740-7

Keywords: Reversible Data Hiding, Encrypted Images, Information Security, Parametric Binary Tree Labeling, IEPBTL, Image Preprocessing, Block Partitioning, Median Edge Detector, Gradient Adjusted Predictor, Payload Capacity, Cryptographic Key Separation, Auxiliary Information, Entropy Analysis, Peak Signal to Noise Ratio, Structural Similarity Index, Mean Absolute Difference