Steifer and Lewandowski (2019) proposed characterizing tissue in ultrasound images by the Lempel–Ziv complexity of small image windows: each window is flattened into a one-dimensional string by a space-filling curve, discretized over a finite alphabet, and scored by the normalized Lempel–Ziv complexity. Used as a breast-lesion malignancy classifier on the open OASBUD database, it slightly outperformed a pixel-entropy classifier, and the authors identified a coherent set of unresolved issues. The core of what remains open is to determine what this finite-window statistic actually measures and when it can be trusted: the link between Lempel–Ziv complexity and the entropy rate of the underlying stochastic process is guaranteed only asymptotically, while imaging windows yield strings of only ~64–81 symbols. Establishing the method's foundations requires characterizing the bias and variance of the estimator in this short-string regime, building physically plausible probabilistic models of the linearized and discretized pixel-intensity sequences, quantifying the statistic's dependence on acquisition parameters (sampling frequency, image resolution, point-spread function, carrier frequency), deriving principled rules for the linearization curve and alphabet cardinality, and confirming the calibrated characterization on other organs and probes. No resolution of these threads is known in the literature to date.

Background

Quantitative ultrasound (QUS) aims to extract objective tissue properties from ultrasound data rather than rely on visual reading of B-mode images (the standard grayscale display formed from echo envelopes). When a sufficiently dense set of sub-wavelength scatterers is imaged, their coherent interference produces speckle — the characteristic grainy texture of ultrasound images — whose statistics carry information about scatterer number, size, and arrangement, and hence about tissue microstructure. Information-theoretic descriptors are one branch of QUS: parametric maps of local (small-window) Shannon entropy of pixel intensities have been used to discriminate benign and malignant breast lesions, and related entropy-imaging methods have been applied to liver and other organs (e.g., Tsui et al. 2017). The Lempel–Ziv (LZ) complexity, introduced by Lempel and Ziv (1976), offers a different information-theoretic measure for a single symbol string: it counts the number of distinct non-overlapping patterns ('copy history') produced when the string is parsed from left to right by the production rule 'reproduce the shortest prefix not obtainable by copying an earlier substring', normalized so that it approaches 1 for long random strings. Its importance for data analysis comes from coding theory: the Ziv–Lempel compression algorithms (Ziv and Lempel 1978) achieve, asymptotically and without knowing the source distribution, the entropy rate of any stationary ergodic source, and the normalized LZ complexity is correspondingly related to the entropy rate — the average information per symbol that the source generates. Amigó, Szczepański, Wajnryb and Sanchez-Vives (2004) proposed exploiting this connection to estimate (or bound below) the entropy rate of neural spike trains via LZ complexity, arguing for fast practical convergence. However, the rigorous theory is asymptotic: the LZ78-based entropy estimator of Kontoyiannis, Algoet, Suhov and Wyner (1998) converges at the slow rate O(log⁡log⁡n/log⁡n)O(\log\log n/\sqrt{\log n}) in sequence length nn, and Amigó and Kennel (2006) could give variance estimates for the estimator only under simplifying assumptions. For strings of a few dozen symbols — far shorter than any regime covered by the asymptotic theory — what the estimator measures is essentially uncharacterized. Steifer and Lewandowski (2019) brought this tool to QUS: they took raw radio-frequency (RF) and B-mode ultrasound data, divided images into small windows (of order 8×88\times 8 to 9×99\times 9 pixels in their implementation), flattened each window into a one-dimensional string using a space-filling curve (a continuous fractal curve such as the Peano or Hilbert curve that passes through every cell of a square grid, used to linearize two-dimensional data while partly preserving spatial locality), discretized the values over a finite alphabet of cardinality kk, and computed the normalized LZ complexity of the resulting word. Averaged over windows, this complexity served as a tissue-characterizing statistic and, as a feature in a binary classifier of breast-lesion malignancy on the open-access OASBUD database (Piotrzkowska-Wróblewska et al. 2017; 96 lesions, 48 malignant and 48 benign), it slightly improved the receiver-operating-characteristic area under the curve (ROC AUC) relative to the state-of-the-art pixel-entropy classifier. The interpretation of the statistic is information-theoretic — a low windowed LZ complexity indicates more predictable, more strongly correlated tissue texture — but the authors themselves stressed that this interpretation rests on asymptotic results that do not apply at imaging window sizes, and they identified the theoretical and physical foundations of the method as an open research problem.

Problem Statement

The problem is to establish the information-theoretic and physical foundations of windowed Lempel–Ziv-complexity tissue characterization in ultrasound imaging — that is, to determine what the finite-window statistic actually measures and under which imaging conditions it can be trusted, so that complexity-based tissue maps admit a principled physical interpretation. Concretely, the open agenda identified by Steifer and Lewandowski (2019) comprises the following interrelated parts of this single objective: (1) characterizing the windowed normalized LZ complexity as an estimator in the imaging regime — its bias and variance relative to the entropy rate of the underlying stochastic process at the short string lengths actually used (windows of order 8×88\times 8 to 9×99\times 9 pixels as used in the Steifer–Lewandowski implementation, i.e., strings of 64–81 symbols after linearization and discretization), outside the infinite-length regime of the asymptotic LZ76/LZ78 theory (the 1976 and 1978 Lempel–Ziv results); (2) establishing physically plausible probabilistic models for the symbol sequences produced by the pipeline — the joint and conditional distributions of neighboring pixel intensities after linearization by a space-filling curve and discretization over an alphabet of cardinality kk, grounded in the scattering and imaging physics that generate speckle; (3) quantifying how the LZ statistic depends on data-acquisition parameters — signal sampling frequency, image resolution, point-spread function (the imaging system's spatial impulse response), and carrier frequency (the center frequency of the transmitted ultrasound pulse) — theoretically and empirically, including whether and how calibration could make the statistic comparable across scanners and protocols; (4) deriving principled rules for choosing the linearization (space-filling) curve and the alphabet cardinality kk, settling whether the Hilbert-curve linearization underperformance reported by Steifer and Lewandowski (2019) is a general property or dataset-specific; and (5) validating the resulting calibrated characterization on organs and probes other than the breast data on which the method was developed (for example thyroid or liver, or different transmit frequencies). A resolution of the stated objective requires parts (1)–(4): the characterization of the finite-window estimator (1), the probabilistic models for the linearized and discretized sequences (2), the acquisition-parameter dependence (3), and the rules for the linearization curve and alphabet cardinality (4); part (5) is a downstream empirical validation that presupposes (1)–(4) and cannot be established independently of them, so an answer confined to a subset of parts (1)–(5) resolves exactly that subset and leaves the remaining parts open.

References

  1. Tomasz Steifer, Marcin Lewandowski (2019). Ultrasound tissue characterization based on the Lempel–Ziv complexity with application to breast lesion classification. Biomedical Signal Processing and Control 51:235–242. DOI 10.1016/j.bspc.2019.02.020. https://doi.org/10.1016/j.bspc.2019.02.020
  2. Tomasz Steifer, Marcin Lewandowski (2019). Quantitative Ultrasound via the Lempel-Ziv complexity. 2019 IEEE International Ultrasonics Symposium (Glasgow, Scotland, October 6–9, 2019), Program Digest, WePoS-17.3. https://ewh.ieee.org/conf/ius/2019/media/files/0766.pdf
  3. A. Lempel, J. Ziv (1976). On the Complexity of Finite Sequences. IEEE Transactions on Information Theory 22(1):75–81. DOI 10.1109/TIT.1976.1055501. https://doi.org/10.1109/TIT.1976.1055501
  4. J. Ziv, A. Lempel (1978). Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory 24(5):530–536. DOI 10.1109/TIT.1978.1055934. https://doi.org/10.1109/TIT.1978.1055934
  5. José M. Amigó, Janusz Szczepański, Elek Wajnryb, Maria V. Sanchez-Vives (2004). Estimating the Entropy Rate of Spike Trains via Lempel-Ziv Complexity. Neural Computation 16(4):717–736. DOI 10.1162/089976604322860677. https://doi.org/10.1162/089976604322860677
  6. José M. Amigó, Matthew B. Kennel (2006). Variance estimators for the Lempel-Ziv entropy rate estimator. Chaos 16(4):043102. DOI 10.1063/1.2347102. https://doi.org/10.1063/1.2347102
  7. I. Kontoyiannis, P. H. Algoet, Yu. M. Suhov, A. J. Wyner (1998). Nonparametric entropy estimation for stationary processes and random fields, with applications to English text. IEEE Transactions on Information Theory 44(3):1319–1327. DOI 10.1109/18.669425. https://doi.org/10.1109/18.669425
  8. Po-Hsiang Tsui, Chin-Kuo Chen, Wen-Hung Kuo, King-Jen Chang, Jui Fang, Hsiang-Yang Ma, Dean Chou (2017). Small-window parametric imaging based on information entropy for ultrasound tissue characterization. Scientific Reports 7:41004. DOI 10.1038/srep41004. https://doi.org/10.1038/srep41004
  9. Hanna Piotrzkowska-Wróblewska, Katarzyna Dobruch-Sobczak, Michał Byra, Andrzej Nowicki (2017). Open access database of raw ultrasonic signals acquired from malignant and benign breast lesions. Medical Physics 44(11):6105–6109. DOI 10.1002/mp.12538. https://doi.org/10.1002/mp.12538
  10. Ruihan Yao, Yufeng Zhang, Keyan Wu, Zhiyao Li, Meng He, Baoping Fengyue (2022). Quantitative assessment for characterization of breast lesion tissues using adaptively decomposed ultrasound RF images. Biomedical Signal Processing and Control 75:103559. DOI 10.1016/j.bspc.2022.103559. https://doi.org/10.1016/j.bspc.2022.103559
  11. Jiancheng Yin, Wentao Sui, Xuye Zhuang, Yunlong Sheng, Yongbo Li (2025). Two-Dimensional Image Lempel–Ziv Complexity Calculation Method and Its Application in Defect Detection. Entropy 27(10):1014. DOI 10.3390/e27101014. https://doi.org/10.3390/e27101014
  12. Jiancheng Yin, Xuye Zhuang, Wentao Sui, Yunlong Sheng (2025). Parallel Lempel–Ziv complexity: an efficient computing framework of Lempel–Ziv complexity. Measurement Science and Technology 36(8):086108. DOI 10.1088/1361-6501/adefff. https://doi.org/10.1088/1361-6501/adefff
  13. Jiancheng Yin, Wentao Sui, Xuye Zhuang, Yunlong Sheng (2025). Attention Lempel-Ziv complexity: an improved Lempel-Ziv complexity with high computational efficiency for bearing early fault detection. Results in Engineering 26:105518. DOI 10.1016/j.rineng.2025.105518. https://doi.org/10.1016/j.rineng.2025.105518
  14. Q. Guo, B. Song, F. Xie, M. Xie, X. Jiao (2025). Utilization of Complexity to Quantify the Regularity and Stochasticity of Nanocrystal Structure. Acta Physica Polonica A 147(5):422–431. DOI 10.12693/aphyspola.147.422. https://doi.org/10.12693/aphyspola.147.422