Abstract

We present an algorithm for pulse width estimation from blurred and nonlinear observations in the presence of signal dependent noise. The main application is the accurate measurement of image sizes on film. The problem is approached by modeling the signal as a discrete position finite state Markov process, and then determining the transition location that maximizes the a posteriori probability. It turns out that the blurred signal can be represented by a trellis, and the maximum a posteriori probability (MAP) estimation is obtained by finding the minimum cost path through the trellis. The latter is done by the Viterbi algorithm. Several examples are presented. These include the measurement of the width of a road in an aerial photo taken at an altitude of 5000 ft. The resulting width estimate is accurate to within a few inches.

© 1978 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,” IEEE Trans. Inf. Theory,  IT-13, 260–269 (1967).
    [Crossref]
  2. G. Forney, “The Viterbi algorithm,” Proc. IEEE,  61, 268–278 (1973).
    [Crossref]
  3. J. W. Burnett and T. S. Huang, “Image modeling with application to measurement,” , School of Electrical Engineering, Purdue University accessed (March1977).
  4. H. Van Trees, Detection, Estimation, and Modulation, Part I, (Wiley, New York, 1968), p. 71.
  5. G. Roussas, A First Course in Mathematical Statistics (Addison-Wesley, Reading, Mass., 1973).
  6. R. Gonsalves, Cramer-Rao bounds on mensuration errors,” Appl. Opt. 15, 1270–1275 (1976).
    [Crossref] [PubMed]
  7. B. Tuong-Phong, “Illumination for computer generated images,” , University of Utah (July1973).
  8. R. Tarkington, “Kodak panchromatic negative films for aerial photography,” Photogramm. Eng.695–699 (December1959).
  9. D. Paris, “Approximation of the sine wave response of photographic emulsions,” J. Opt. Soc. Am. 51, 988–991 (1961).
    [Crossref]

1976 (1)

1973 (1)

G. Forney, “The Viterbi algorithm,” Proc. IEEE,  61, 268–278 (1973).
[Crossref]

1967 (1)

A. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,” IEEE Trans. Inf. Theory,  IT-13, 260–269 (1967).
[Crossref]

1961 (1)

1959 (1)

R. Tarkington, “Kodak panchromatic negative films for aerial photography,” Photogramm. Eng.695–699 (December1959).

Burnett, J. W.

J. W. Burnett and T. S. Huang, “Image modeling with application to measurement,” , School of Electrical Engineering, Purdue University accessed (March1977).

Forney, G.

G. Forney, “The Viterbi algorithm,” Proc. IEEE,  61, 268–278 (1973).
[Crossref]

Gonsalves, R.

Huang, T. S.

J. W. Burnett and T. S. Huang, “Image modeling with application to measurement,” , School of Electrical Engineering, Purdue University accessed (March1977).

Paris, D.

Roussas, G.

G. Roussas, A First Course in Mathematical Statistics (Addison-Wesley, Reading, Mass., 1973).

Tarkington, R.

R. Tarkington, “Kodak panchromatic negative films for aerial photography,” Photogramm. Eng.695–699 (December1959).

Tuong-Phong, B.

B. Tuong-Phong, “Illumination for computer generated images,” , University of Utah (July1973).

Van Trees, H.

H. Van Trees, Detection, Estimation, and Modulation, Part I, (Wiley, New York, 1968), p. 71.

Viterbi, A.

A. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,” IEEE Trans. Inf. Theory,  IT-13, 260–269 (1967).
[Crossref]

Appl. Opt. (1)

IEEE Trans. Inf. Theory (1)

A. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,” IEEE Trans. Inf. Theory,  IT-13, 260–269 (1967).
[Crossref]

J. Opt. Soc. Am. (1)

Photogramm. Eng. (1)

R. Tarkington, “Kodak panchromatic negative films for aerial photography,” Photogramm. Eng.695–699 (December1959).

Proc. IEEE (1)

G. Forney, “The Viterbi algorithm,” Proc. IEEE,  61, 268–278 (1973).
[Crossref]

Other (4)

J. W. Burnett and T. S. Huang, “Image modeling with application to measurement,” , School of Electrical Engineering, Purdue University accessed (March1977).

H. Van Trees, Detection, Estimation, and Modulation, Part I, (Wiley, New York, 1968), p. 71.

G. Roussas, A First Course in Mathematical Statistics (Addison-Wesley, Reading, Mass., 1973).

B. Tuong-Phong, “Illumination for computer generated images,” , University of Utah (July1973).

Cited By

OSA participates in Crossref's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (17)

FIG. 1
FIG. 1

Trellis for a step edge.

FIG. 2
FIG. 2

Trellis for a blurred step edge.

FIG. 3
FIG. 3

Trellis for a pulse.

FIG. 4
FIG. 4

The observation model.

FIG. 5
FIG. 5

Typical blurred and noisy scan lines.

FIG. 6
FIG. 6

Estimated width versus S/N.

FIG. 7
FIG. 7

Variance versus S/N.

FIG. 8
FIG. 8

Transmitted light intensity pattern with S/N = 2.25.

FIG. 9
FIG. 9

Effect of unknown levels on accuracy of estimates. The abscissa is S/N.

FIG. 10
FIG. 10

Effect of unknown levels on variance of estimates. The abscissa is S/N.

FIG. 11
FIG. 11

Computer-generated cylinder.

FIG. 12
FIG. 12

Ideal scan line across a cylinder.

FIG. 13
FIG. 13

Blurred and noisy scan line across a cylinder.

FIG. 14
FIG. 14

Road intersection in Warren County, Indiana.

FIG. 15
FIG. 15

Section of one of the roads in Fig. 14.

FIG. 16
FIG. 16

Scan line across the road of Fig. 15.

FIG. 17
FIG. 17

Line spread function of film-lens combination.

Tables (3)

Tables Icon

TABLE I Radius measurements.

Tables Icon

TABLE II Road width measurement results.

Tables Icon

TABLE III The effect of fc on width estimates.

Equations (27)

Equations on this page are rendered with MathJax. Learn more.

Prob ( i 1 = a 1 ) = 1 , Prob ( i M = a 2 ) = 1 , Prob ( i k + 1 = a j i 1 , , i k ) = Prob ( i k + 1 = a j i k ) ,
Prob ( i k + 1 = a 1 i k = a 1 ) = p 11 , Prob ( i k + 1 = a 2 i k = a 1 ) = p 12 , Prob ( i k + 1 = a 1 i k = a 2 ) = 1.
Prob ( y 1 = h ( a 1 , , a 1 ) ) = 1 , Prob ( y k + 1 = h ( a 1 , , a 1 ) y k = h ( a 1 , , a 1 ) ) = p 11 , Prob ( y k + 1 = h ( a 1 , , a 1 , a 2 ) y k = h ( a 1 , , a 1 ) ) = p 12 , Prob ( y k + 1 = h ( a 1 , , a 2 , a 2 ) y k = h ( a 1 , , a 1 , a 2 ) ) = 1 , Prob ( y k + 1 = h ( a 2 , , a 2 ) y k = h ( a 1 , a 2 , , a 2 ) ) = 1 Prob ( y M = h ( a 2 , , a 2 ) ) = 1
P ( I Z ) I = Î = max ,
P ( ξ Z ) ξ = ξ ˆ = max .
l = 1 M P ( ξ l + 1 ξ l ) p [ z l h ( ξ l ) ] ,
l = 1 M ( - log P ( ξ l + 1 ξ l ) - log p ( z l h ( ξ l ) ) l = 1 M Γ ( ξ l ) .
Γ ( ξ l + 1 , ξ l ) Γ ( ξ ˆ 1 l ) + Γ ( ξ l + 1 )
π α * π α .
n w * = n 2 * - n 1 * , p α * = Prob ( n w * = α ) = β π β * π α - β * ,
p α = Prob ( n w = α ) α π β π α - β ,
Var ( n w ) - Var ( n w * ) = α 2 ( p α - p α * ) 0.
P ( E n ) = 2 Q ( T n / 2 σ ) ,
Q ( x ) = x 1 2 π e - ( y 2 / 2 ) d y , T n 2 = Δ 2 j = - t n + t [ U 1 ( j ) - U 1 ( j - n ) ] 2 ,
Δ 2 = ( a 1 - a 2 ) 2 .
P ( E n ) = 2 Q [ T n / 2 ( σ + σ t ) ] ,
y k = log b k + 0.15
σ y k = 0.1 y k 1 / 3
SNR = maximum change in density due to signal maximum noise standard deviation .
a l = 10 [ h ( â l ) - 0.15 ]
P ( Z I ) I = Î ,
p ( Z w 0 , w 1 ) w 0 = ŵ 0 , w 1 = ŵ 1
min w 0 , w 1 k = 1 M log p ( z k w 0 , w 1 ) .
k = 1 M ( z k - y k ) 2 / σ k 2 ,
T 1 ( f ) = 1 1 + ( 2 π f / 250 ) 2
T 2 ( f ) = 2 π { cos - 1 ( f f c ) - f f c [ 1 - ( f f c ) 2 ] 1 / 2 } , f c = 48 cycles / mm .
( 1 / 2 σ k 2 ) ( z k - y k ) 2 - log [ 1 / ( 2 π ) 1 / 2 σ k ] ;