Abstract

A general formulation of ranked-order filters is developed in two parts: part 1, signal-to-noise-ratio analysis and part 2, construction and analysis of a ranked-order-filter function based on a mathematical logic approach. The filter function is analyzed to define the structure of filter roots for one-dimensional (1-D) and two-dimensional (2-D) window filters as data patterns that are invariant of the filter. The 1-D and 2-D coded window filters defined for roots of repeated patterns of binary data are defined and analyzed. The analysis concludes with an application of the coded window filter to a computer-generated 2-D noisy image containing a binary pattern and an application for feature extraction by a 2-D filter constrained by a predicate function to select only fixed-point root data structures.

© 1998 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. B. R. Frieden, Probability, Statistical Optics and Data Testing (Springer-Verlag, Berlin, 1983), pp. 254–259.
  2. B. I. Justasson, “Median filtering: statistical properties,” in Two-Dimensional Signal Processing II: Transforms and Median Filters, T. S. Huang, ed. (Springer-Verlag, Berlin, 1982), pp. 161–196.
  3. D. Eberly, H. G. Longbotham, J. Aragon, “Complete classifications of roots to 1-dimensional median and ranked-order filters,” IEEE Trans. Acoust. Speech Signal Process. 39, 197–200 (1991).
    [CrossRef]
  4. S. G. Tyan, “Median filtering: deterministic properties,” in Two-Dimensional Signal Processing II: Transforms and Median Filters, T. S. Huang, ed. (Springer-Verlag, Berlin, 1982), pp. 197–218.
  5. H. G. Longbotham, “Theory of order statistic filters and their relationship to FIR filters,” IEEE Trans. Acoust. Speech Signal Process. 37, 275–287 (1989).
    [CrossRef]
  6. H. A. David, Order Statistics, 2nd ed. (Wiley, New York, 1981).
  7. A. Bovick, T. S. Huang, D. Muson, “A generalization of median filtering using linear combinations of order statistics,” IEEE Trans. Acoust. Speech Signal Process. 31, 1342–1350 (1983).
    [CrossRef]
  8. J. R. Shoenfeld, Mathematical Logic (Addison-Wesley, Reading, Mass., 1967), Chaps. 6 and 7.
  9. J. R. Shoenfeld, Mathematical Logic (Addison-Wesley, Reading, Mass., 1967), pp. 282–292.
  10. G. R. Arce, R. E. Foster, “Detail preserving ranked-order based filters for image processing,” IEEE Trans. Acoust. Speech Signal Process. 37, 83–98 (1989).
    [CrossRef]
  11. B. Chellas, Modal Logic: An Introduction (Cambridge U. Press, Cambridge, UK, 1980).

1991

D. Eberly, H. G. Longbotham, J. Aragon, “Complete classifications of roots to 1-dimensional median and ranked-order filters,” IEEE Trans. Acoust. Speech Signal Process. 39, 197–200 (1991).
[CrossRef]

1989

H. G. Longbotham, “Theory of order statistic filters and their relationship to FIR filters,” IEEE Trans. Acoust. Speech Signal Process. 37, 275–287 (1989).
[CrossRef]

G. R. Arce, R. E. Foster, “Detail preserving ranked-order based filters for image processing,” IEEE Trans. Acoust. Speech Signal Process. 37, 83–98 (1989).
[CrossRef]

1983

A. Bovick, T. S. Huang, D. Muson, “A generalization of median filtering using linear combinations of order statistics,” IEEE Trans. Acoust. Speech Signal Process. 31, 1342–1350 (1983).
[CrossRef]

Aragon, J.

D. Eberly, H. G. Longbotham, J. Aragon, “Complete classifications of roots to 1-dimensional median and ranked-order filters,” IEEE Trans. Acoust. Speech Signal Process. 39, 197–200 (1991).
[CrossRef]

Arce, G. R.

G. R. Arce, R. E. Foster, “Detail preserving ranked-order based filters for image processing,” IEEE Trans. Acoust. Speech Signal Process. 37, 83–98 (1989).
[CrossRef]

Bovick, A.

A. Bovick, T. S. Huang, D. Muson, “A generalization of median filtering using linear combinations of order statistics,” IEEE Trans. Acoust. Speech Signal Process. 31, 1342–1350 (1983).
[CrossRef]

Chellas, B.

B. Chellas, Modal Logic: An Introduction (Cambridge U. Press, Cambridge, UK, 1980).

David, H. A.

H. A. David, Order Statistics, 2nd ed. (Wiley, New York, 1981).

Eberly, D.

D. Eberly, H. G. Longbotham, J. Aragon, “Complete classifications of roots to 1-dimensional median and ranked-order filters,” IEEE Trans. Acoust. Speech Signal Process. 39, 197–200 (1991).
[CrossRef]

Foster, R. E.

G. R. Arce, R. E. Foster, “Detail preserving ranked-order based filters for image processing,” IEEE Trans. Acoust. Speech Signal Process. 37, 83–98 (1989).
[CrossRef]

Frieden, B. R.

B. R. Frieden, Probability, Statistical Optics and Data Testing (Springer-Verlag, Berlin, 1983), pp. 254–259.

Huang, T. S.

A. Bovick, T. S. Huang, D. Muson, “A generalization of median filtering using linear combinations of order statistics,” IEEE Trans. Acoust. Speech Signal Process. 31, 1342–1350 (1983).
[CrossRef]

Justasson, B. I.

B. I. Justasson, “Median filtering: statistical properties,” in Two-Dimensional Signal Processing II: Transforms and Median Filters, T. S. Huang, ed. (Springer-Verlag, Berlin, 1982), pp. 161–196.

Longbotham, H. G.

D. Eberly, H. G. Longbotham, J. Aragon, “Complete classifications of roots to 1-dimensional median and ranked-order filters,” IEEE Trans. Acoust. Speech Signal Process. 39, 197–200 (1991).
[CrossRef]

H. G. Longbotham, “Theory of order statistic filters and their relationship to FIR filters,” IEEE Trans. Acoust. Speech Signal Process. 37, 275–287 (1989).
[CrossRef]

Muson, D.

A. Bovick, T. S. Huang, D. Muson, “A generalization of median filtering using linear combinations of order statistics,” IEEE Trans. Acoust. Speech Signal Process. 31, 1342–1350 (1983).
[CrossRef]

Shoenfeld, J. R.

J. R. Shoenfeld, Mathematical Logic (Addison-Wesley, Reading, Mass., 1967), Chaps. 6 and 7.

J. R. Shoenfeld, Mathematical Logic (Addison-Wesley, Reading, Mass., 1967), pp. 282–292.

Tyan, S. G.

S. G. Tyan, “Median filtering: deterministic properties,” in Two-Dimensional Signal Processing II: Transforms and Median Filters, T. S. Huang, ed. (Springer-Verlag, Berlin, 1982), pp. 197–218.

IEEE Trans. Acoust. Speech Signal Process.

D. Eberly, H. G. Longbotham, J. Aragon, “Complete classifications of roots to 1-dimensional median and ranked-order filters,” IEEE Trans. Acoust. Speech Signal Process. 39, 197–200 (1991).
[CrossRef]

H. G. Longbotham, “Theory of order statistic filters and their relationship to FIR filters,” IEEE Trans. Acoust. Speech Signal Process. 37, 275–287 (1989).
[CrossRef]

A. Bovick, T. S. Huang, D. Muson, “A generalization of median filtering using linear combinations of order statistics,” IEEE Trans. Acoust. Speech Signal Process. 31, 1342–1350 (1983).
[CrossRef]

G. R. Arce, R. E. Foster, “Detail preserving ranked-order based filters for image processing,” IEEE Trans. Acoust. Speech Signal Process. 37, 83–98 (1989).
[CrossRef]

Other

B. Chellas, Modal Logic: An Introduction (Cambridge U. Press, Cambridge, UK, 1980).

J. R. Shoenfeld, Mathematical Logic (Addison-Wesley, Reading, Mass., 1967), Chaps. 6 and 7.

J. R. Shoenfeld, Mathematical Logic (Addison-Wesley, Reading, Mass., 1967), pp. 282–292.

H. A. David, Order Statistics, 2nd ed. (Wiley, New York, 1981).

S. G. Tyan, “Median filtering: deterministic properties,” in Two-Dimensional Signal Processing II: Transforms and Median Filters, T. S. Huang, ed. (Springer-Verlag, Berlin, 1982), pp. 197–218.

B. R. Frieden, Probability, Statistical Optics and Data Testing (Springer-Verlag, Berlin, 1983), pp. 254–259.

B. I. Justasson, “Median filtering: statistical properties,” in Two-Dimensional Signal Processing II: Transforms and Median Filters, T. S. Huang, ed. (Springer-Verlag, Berlin, 1982), pp. 161–196.

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 (12)

Fig. 1
Fig. 1

Fixed point of ϑ(9).

Fig. 2
Fig. 2

Fixed point of ϑ+(L).

Fig. 3
Fig. 3

Multivalued fixed-point examples of ϑ+(9).

Fig. 4
Fig. 4

Elementary quasi-root of ϑ(L).

Fig. 5
Fig. 5

Elementary quasi-root of ϑ+(L).

Fig. 6
Fig. 6

Cross-hatch root of ϑ+(L).

Fig. 7
Fig. 7

Φmed3(13, 21).

Fig. 8
Fig. 8

Roots of 2-D coded window filter ΦmedEp(L, M).

Fig. 9
Fig. 9

Elementary roots of Φmed3(13, 21).

Fig. 10
Fig. 10

Φmed3(13, 21): rt(1). Top to bottom: target image, noisy image, filtered image.

Fig. 11
Fig. 11

Boy on Dobbins Island: (a) original image, (b) ϑ+(13) iff Rc=co&Ag(ui).

Fig. 12
Fig. 12

Chesapeake navigation marker: (a) original image, (b) ϑ+(13) iff Rc=co&Ag(ui).

Tables (1)

Tables Icon

Table 1 Verification of SNRmed(x)

Equations (164)

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

Pw(x)=N1N-1m-xpx(x)-xpx(x)dxm  ×1--xpx(x)dxndx.
Pw(x)=N1N-1m-x[Px(x)]m[1-Px(x)]npx(x)dx.
Pw(y)=B-1(m+1, n+1)0Px(x)ym(1-y)ndy,
ywα=B-1(m+1, n+1)01ym+a(1-y)ndy,
yw=B(m+2, n+1)B(m+1, n+1),
yw2=B(m+3, n+1)B(m+1, n+1).
m=n=(N-1)/2;
ymed=12,σmed(y)=-4(N+2)1,
m=N-1,n=0;
ymax=N(N+1),
σmax(y)=N(N+1)2(N+2)1/2,
m=0,n=N-1;
ymin=1/(N+1),σmin(y)=σmax(y).
Px-1(yw)=xw.
σw(x)=12Px-1(y)|t-t+.
SNRw(x)=xwσw(x).
Px(x)=1brectx-ab,
ymed=1bxmed-a+b2,
xmed=bymed+a-b2,
xmed=a.
σw(x)=12b(y)+a-b2t-t+
 σmed(x)=bσmed(y),
 SNRmed(x)rect=2abN+2.
z=(x-x)2σ(x);
Pz(z)=12[1+erf(z)].
ymed=12(1+erf(zmed)],
ymed+σmed(y)=12{1+erf[zmed+σmed+(z)]},
σw(z)=12[erf-1(2y-1)|t-t+].
erf(σmed+)=erf(σmed-),
zmed=0,
erf[σmed(z)]=2σmed(y).
σmed(z)=erf-1[2σmed(y)].
xmed=x,
σmed(x)=2σ(x)σmed(z),
SNRmed(x)Normal=x2σ(x)erf-1(-N+21).
Px(x)=1-exp(-x/a),
xw=-a ln(1-yw),
σw(x)=-a2ln1-yw-σw(y)1-yw+σw(y),
SNRw(x)exp=-a ln(1-yw)σw(x).
rect(x): xi=2aRANF(y),a=5,b=2a,
exp(x):xi=-a[1-ln(yi)],yi=RANF(y),
a=5,
normal(x):xi=Rnormal(a, σ),a=5,
σ=a/23.
ui: (u)i=[(u)i, (u)i+1, , (u)i+N-1],
vi=vi, vi+1, , vi+N-1.
β(vi, j)=vi+j-vi,vi+j>vi,j<N,
β(vi, j)=0vi+jvi,
β(vi, j)=vji,
vji=ji,
vji=v0i,v1i, , vN-1i.
u=(u1, , un-2k),
u=i=1n-2kui.
KR(a)=0,R(a),=1,R(a),
G(a)=μxR(a, x)
G(a)=μx[KR(a, x)=0],R(a, x).
F(a)=G1(a),R1(a),
F(a)=Gq(a),Rq(a),
F(a)=μx[R1(a), x=G1(a)  Rq(a),x=Gq(a)],
F(a)=G1(a)·KR(a)++Gq(a)·KR(a).
F(u, u)=P(u1, u1),R(u1),
 
F(u, u)=P(un-2k, un-2k),R(un-2k),
R(ui)˜μx[KR(ui, x)=0],
P(ui, ui)=μx{H[G(ui, x),vi]}.
O(ui)=(ui)jη0j, , (ui)pηN-1p.
G[ui, (ai)mvmi]=μx{x=πmN-1[O(ui)] & (ai)vmi=x},
H{G[ui, (ai)kvki], vi}=μxx<N[(ai)vxi=(ai)vki  (ai)vxi=(0)vxi],
P(ui, ui)
=[(0)v0i, , (0)vk-1i, (ai)vki, (0)vk+1i, (0)vN-1i],
F(u, u)=P(u1, u1)·KR(u1), ,P(uq, uq)KR(uq),
q=n-2k,k=(N-1)/2.
ui(ui, , ui+2k)=[x|Rc(x, ui, , ui+2k, cor(c)],
c: (ui)jvji=(ui)jηlj,j=k=l,
k=(N-1)/2; vki=ηlk=ki
O(ui)=(ui)jη0j(ui)iηk-1j(ui)kvkk(ui)jηk+1j(ui)kηN-1j,
(ui)kvki=(ui)kηkk  vki=ηkk.
O(ui+1)=(ui+1)jη0j(ui+1)kvki+1(ui+1)k-1vk-1i+1(ui+1)jηN-1j,
O(ui+1)=(ui+1)jη0i(ui+1)k-1vk-1i+1(ui+1)kvki+1(ui+1)jηN-1j,
O(ui+k)=(ui+k)jη0j(ui+k)jηk-1i(ui+k)kvki+k(ui+k)0v0i+k,j>k
O(ui+k)=(ui+k)0v0i+k(ui+k)kvki+k(ui+k)jηk+1i(ui+k)jη2kj,j>k.
π0N-1[O(ui)]orπN-1N-1[O(ui)],
H{G[ui, (ai)2kv2ki], ui}=μxx<N[(ai)vxi=(ai)v2ki  (ai)vxi=(0)vxi],
ui=0 1 2 1 4 5 5 5 5 6 6 7 6,
i=1 2 3 4 5 6 7 8 9 10 11 12 13,
0 1 2 1 4 5 5 5 5 6 6 7 6,
vj1; j=0 1 2 3 4 5 6 7 8,
O(u1)=5η085η175η265η354(η44=v41)2η521η631η710η80,
P(u1, u1)=0 0 0 0 4 0 0 0 0.
0 1 2 1 4 5 5 5 5 6 6 7 6,
vj2; j=0 1 2 3 4 5 6 7 8,
O(u2)=6η085η175η265η355(η44=v42)4v322η611η721η80,
P(u2, u2)=0 0 0 0 5 0 0 0 0.
0 1 2 1 4 5 5 5 5 6 6 7 6,
vj3; j=0 1 2 3 4 5 6 7 8,
O(u3)=6η086η175η265η355(η44=v43)5v334v232η701η81,
P(u3, u3)=0 0 0 0 5 0 0 0 0.
0 1 2 1 4 5 5 5 5 6 6 7 6,
vj4; j=0 1 2 3 4 5 6 7 8,
O(u4)=7η086η176η265η355(η44=v44)5v345v244v141η80,
P(u4, u4)=0 0 0 0 5 0 0 0 0.
0 1 2 1 4 5 5 5 5 6 6 7 6,
vj5, j=0 1 2 3 4 5 6 7 8,
O(u5)=7η076η186η266η355(η44=v45)5v355v255v154v05,
P(u5, u5)=0 0 0 0 5 0 0 0 0.
I(u, u)=P(u1, u1)·KR(u1), ,P(u5, u5)·KR(u5)=0 0 0 0 4 5 5 5 5 0 0 0 0.
S1(29)=00000123450000012345555500000.
φmed(9) * S1(29)=1(21),
1(29)=00000111110000012345555500000.
S2(29)=20110225470102012545575610201.
2(29)=00002222222111112455555520000.
φmin(9) * φmax(9) * φmed (9) * S1(37)=3(37):
S1(37)=0000201102254701020125455756102010000,
3(37)=0000000022222222222224555555200000000.
P(ui, ui)=00, , avki, , 02k,R(ui),
P(ui, ui+1)=00, , bvki+1, , 02k,R(ui+1).
O(ui)=a0, , ak, bk+1, , b2k,
O(ui+1)=a0, , ak-1, bk, , b2k,
cor[cos(1)]: u=a  b, a>b,
cor[cos(2)]: vki=ηlk,
cor[cos(3)]: ui=(a)vji(jodd),(b)vji(jeven),
i,j,j=0,2k,keven.
prob(biterror)=Nk+1i=1k+1pi(1-p)k+1-i.
ϕmed1(3)=(),
S3(23)=00000101010101010100000,
ϕmed1(3) * S3(23)=00000101010101010100000.
ϕmed2(5)=(),
S4(28)=0000100110011001100110010000,
ϕmed2(5) * S4(28)=0000100110011001100110010000.
ϕmed3(7)=(),
S5(28)=0000101011010110101101010000,
ui=(ui)0v0i, εp(ui)1v1i, , ε2(ui)k-1vk-1i, (ui)kvki,ε2(ui)k+1vk+1i, , εp(ui)2k-1v2k-1i, (ui)2kv2ki;ϕmedEk(2k+1): (εpε2ε2εp),
Ep=(ε1, , εp).
ϑ(25)=°°°°°°°°°°°°°°°°°°°°°°°°,
ϑ+(9)=°°°°°°°°.
X×Y=(ζ|δX, γY, ζδ,γ),
uζ=(uζ)00v00ζ, , (uζ)2k,2kv2k,2kζ),
L=N2,N=2k+1,
O(uζ)=(uδγ)ρση0ρσ(uδγ)kkvkkδγ(uδγ)ρσηL-1ρσ.
O(uζ)=(uδ+k,γ+k)00v00δ+k, γ+k(uδ+k,γ+k)kkvkkδ+k, γ+k(uδ+k,γ+k)k+1, k+1ηk+1k+1, k+1.(uδ+k,γ+k)ρσηL-1ρσ
O(uζ)=(uδ+k,γ+k)ρση0ρσ(uδ+k,γ+k)k-1, k-1ηk-1k-1, k-1(uδ+k,γ+k)kkvkkδ+k, γ+k(uδ+k,γ+k)00v00δ+k, γ+k.
uζ=ρ{μx[x=(uζ)ρkvp, kζ]}ρ<N
& σ{μy[y=(uζ)k,σvk, σζ]}σ<N;
L=2N-1,N=2k+1.
uζ=[(uζ)0kv0kζ, , (uζ)2k,kv2k,kζ,(uζ)k0vk0ζ, , (uζ)k,2kvk, 2kζ],
O(uζ)=(uζ)0kv0kζ(uζ)kkvkkζ(uζ)ρ,kηk+1ρk(uζ)ρ,kη2kρk
& (uζ)kση0kσ
(uζ)kσηk-1kσ(uζ)kkvkkζ(uζ)kσηk+1kσ(uζ)k,ση2kkσ
O(uζ)=(uζ)k0vk0ζ(uζ)kkvkkζ(uζ)kσηk+1kσ(uζ)kση2kkσ
& (uζ)ρkη0ρk
(uζ)ρkηk-ρk(uζ)kkvkkζ(uζ)πkηk+1ρk(uζ)ρkη2kρk,
Pat(1): °°°°°°°°°°°°*************.
Pat(2): °°°°°°°°°*°°***°°***°°***.
A=1010000010100000,B=0000010100000101,
C=0000101000001010,D=0101000001010000.
ABorCDiffAB={0}=Cd,
Cond.().
A, B, C, D,
AB, CD, AC, BC, AD, BD,
(AC)(AD)or(BC)(BD)
AB={0}=CD,
AD={0}=AC,
BC={0}=BD,Cond.(+).

Metrics