概率模型在游程编码图像处理中的应用

需积分: 10 75 浏览量更新于2024-09-10 收藏 874KB PDF 举报

"A probabilistic model for run-length coding of pictures - 游程编码" 游程编码（Run-Length Coding，RLC）是一种数据压缩技术，尤其适用于处理具有大量连续相同值的数据，如图像处理中的像素序列。在图像中，相邻像素可能有相同的颜色，游程编码就是通过记录连续相同值的长度来减少数据量，从而实现压缩。文章提到的Capon提出了一种概率模型来优化游程编码。在该模型中，他利用概率统计的方法来预测和编码连续的相同值序列。这可以通过建立一个数学模型来实现，模型基于一个假设的生成序列，即注册器（register）产生的序列A，A，A，...，A_k。这些值用S_i表示，其中i从1到n。根据文章内容，我们可以推断出以下关键点： 1. 序列关系：式(19)和(20)定义了序列中相邻元素之间的关系，即b_i = a_i - l 和 B_i - l = b_i。这表明序列中的变化是连续的，并且可以通过前一个元素来预测当前元素。 2. 计算公式：式(21)和(22)给出了如何从之前的元素计算当前元素的公式，例如C_i = b_i - l。这有助于构建预测模型，以便更高效地编码游程。 3. 序列性质：根据式(23)和(24)，可以得出e_i 的表达式，这与序列中的元素变化有关。这些公式揭示了序列的内在结构，对于压缩算法的设计至关重要。 4. 最大长度移位寄存器：文中提到，由于使用的是最大长度移位寄存器，这意味着序列B_i 可以看作是A_i 序列的一个位移版本。最大长度移位寄存器产生的序列具有特定的周期性，这种特性在编码和解码过程中非常有用，因为它确保了可逆性。 5. 感谢与引用：作者感谢了Dr. B. Elspas关于最大长度反馈移位寄存器及其推广的启发性讨论，并引用了R.W. Hamming和D.Slepian的相关工作，这表明游程编码和相关理论是建立在早期错误检测与纠正代码以及信息论基础之上的。游程编码在实际应用中，特别是在图像压缩领域，如传真、扫描和医学图像处理，具有广泛的应用。通过建立概率模型，可以更有效地估计和压缩连续重复的像素值，提高压缩效率并降低存储需求。同时，这种模型还能够适应不同图像的统计特性，使得压缩更具适应性。

Capon: A Probabilistic Model for Run-Length Coding of Pictures

Let the values of Xi (see Fig. 2) for the register pro-

ducing A,, A,, . . . A, be S,, S,, . . . S,-,. Then we must

have

and

bc = a,-l

B--l

by = C S&i

i-l

i = 2,3, --- Ic - 1

(19)

(20)

Ci = bi-,

i = 2, 3, ..a k - 1

(21)

k-1

&“I = C Sib,.

(22)

i=l

Furthermore, n-e have from (16) and (17)

d, = ai + bi

ei = bi + ci.

Then

(23)

(24)

h + ~1

k-1

= z Si(ai + bJ

(25)

157

Furthermore, for i = 2, 3, . . . k - 1

ei = bi + ci

= ai-l + biml

= d,-l.

(26)

Now, since the arguments given will apply to any two

successive Bi, (25) and (26) show that, the sequence of the

B, may be obtained from the same shift register as the

Ai. Finally, since this is a maximal-length shift register,

the sequence of the Bi must just be a shifted version of

the sequence of the Ai, and (18) must hold.

ACKNOWLEDGMENT

The author is indebted to Dr. B. Elspas for several

illuminating discussions on maximal-length feedback

shift registers and their generalizations.

[II

[31

[41

[51

[Cl

[71

[81

BIBLIOGRAPHY

R. W. Hamming, “Error correcting

and error detecting codes,”

Bell Sys. Tech. J., vol. 29, pp. 147-160.; April, 1950.

D. Slepian, “A class of binary signaling alphabets,” Bell Sys.

Tech. J., vol. 35, pp. 203-234; January, 1956.

I. S. Reed, “A class of multiple-error-correcting codes and the

decoding scheme,”

IRE TRANS. ON INFORMATiON THEORY,

vol. IT-4, pp. 38-49; September, 1954.

J. H. Green, Jr. and R. L. San Soucie, “An error correcting

encoder and decoder of high efficiency,” PROC. IRE, vol. 46,

gp. g”,iKl,‘,‘4?‘; October, 1958.

Several Bmary-Sequence Generators,” Lincoln

Lab., M.I.$., Lexington, Mass., Tech. Rept. No. 95; September

12, 1955.

S. W. Golomb,

“Sequences With Randomness Properties,”

Glenn L. Martin Co., Baltimore, Md., Final Rept. on Contract

No. W 36-039SC-54-36611; June 14, 1955.

B. Elspas, “Theory of autonomous linear sequential networks,”

IRE TRANS. ON CIRCUIT THEORY, vol. CT-6, pp. 45-60; March,

1959.

W. Marsh, “Table of Irreducible Polynomials Over GF(2)

Through Degree 19,” National Security Agency, Washington,

D. C., October 24, 1957.

A Probabilistic Model for Run-Length Coding of Pictures*

JACK CAPONt

Summary-A first-order Markoff process representation for

pictures is proposed in order to study the picture coding system

known as run-length coding (differential-coordinate encoding). A

lower bound for the saving in channel capacity is calculated on

the basis of this model, and is compared with the results obtained

by previous investigators. In addition, this representation is shown

to yield an insight into the run-length coding system which might

not otherwise be obtained. The application of this probabilistic

model to an “elastic” system of run-length coding is also discussed.

* Manuscript received by the PGIT, December 22, 1958. This

work was done when the author was employed by the Ford Instru-

ment

Company, Long Island City, N. Y., during the summer of

1958.

t Federal Scientific Corporation,. New York, N. Y. Formerly

with the Dept. Elec. Engrg., Columbia University, New York, N. Y.

T has been recognized that a saving in either time

or bandwidth is possible by exploiting the large-

scale redundancies in pictures. One of the first

proposals advanced for taking advantage of these re-

dundancies is the variable sweep system of Cherry and

G0uriet.l The authors found that theoretically a saving

of approximately seven in either time or bandwidth is

possible with their system.

1 E. C. Cherry and G. G. Gouriet, “Some possibilities for the

compression of television by recoding,”

Proc. IEE, vol. 100, pt. III,

pp. 9-18; January, 1953.

下载后可阅读完整内容，剩余6页未读，立即下载

sbx19850629

粉丝: 8
资源: 12

概率模型在游程编码图像处理中的应用

概率模型检查器PRISM评估云渲染系统可靠性的新方法：定量计算

Principles of the Spin Model Checker.pdf

一个分布式K互斥算法的概率模型检测

使用diffusion probabilistic model 生成时间序列的python代码

probabilistic heat-map

ecoc2020 tu1j-6 probabilistic and geometric shaping for next-generation 100g

robabilistic U-Net:

bert-bilstm-crf

请使用python和pytorch完成振动信号故障诊断任务，要求是：首先将一维振动时序信号转化成灰度图，并使用diffusion probabilistic model对灰度图像进行数据增广，接着对增广后的数据集输入CNN进行训练，评估模型效果。

package jgibblda;

最新资源