×

Rank order smoothers with two-dimensional data model. (English) Zbl 0667.93109

Author’s summary: “Development of the theory of rank order smoothers is motivated by hardware implementation, as well as statistical, considerations. A recently proposed class of rank order smoothers based on minimization of polyhedral convex functions, involving one-dimensional data models, employs minimization algorithms derived from dynamic programming; computations proceed by storing and manipulating arrays of breakpoints of piecewise linear convex functions. Such an approach has certain advantages over alternatives. Foremost among these is the attainment of a fixed point or “root signal” in a single application of the minimization algorithm. Other advantages are the intelligibility of the connection between the rough data and the root signal smooth derived from it, the absence of any significant problem of how to deal with end evalues, compatibility with real time applications, and storage and computation time requirements of the order of the number of pieces of rough data. When experimental comparison was made to median smoothers, better smoothing was observed. On the negative side, such smoothers have been largely restricted to types that behave fundamentally like median smoothers, i.e., have the same sorts of fixed points or root signals. It is shown that by letting the data model be two dimensional, and formulating the dynamic programming method so that variables are eliminated in pairs, then the root signal sets of such smoothers are greatly expanded while the various advantages are retained.”
Reviewer: T.Basar

MSC:

93E14 Data smoothing in stochastic control theory
93E25 Computational methods in stochastic control (MSC2010)
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Rabiner, L. R.; Sambur, M. R.; Schmidt, C. E., Applications of a nonlinear smoothing algorithm to speech processing, IEEE Trans. Acoust. Speech Signal Process, ASSP-23, 552-557 (1975)
[2] Tukey, J. W., Exploratory Data Analysis (1977), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0409.62003
[3] Tyan, S. G., Median filtering: Deterministic properties, (Huang, T. S., Two Dimensional Digital Signal Processing II (1981), Springer-Verlag: Springer-Verlag Berlin/New York)
[4] Gallagher, N. C.; Wise, G. L., A theoretical analysis of the properties of median filters, IEEE Trans. Acoust. Speech Signal Process, ASSP-29, 1136-1141 (1981)
[5] Nodes, T. A.; Gallagher, N. C., Median filters: Some modifications and their properties, IEEE Trans. Acoust. Speech Signal Process, ASSP-30, 739-746 (1982)
[6] McLoughlin, M. P.; Arce, G. R., Deterministic properties of the recursive separable median filter, IEEE Trans. Acoust. Speech Signal Process, ASSP-35, 98-106 (1987)
[7] Fisher, A. L., Systolic algorithms for running order statistics in signal and image processing, J. Digital Systems, 6, 251-264 (1982)
[8] Wendt, P. D.; Coyle, E. J.; Gallagher, N. C., Stack filters, IEEE Trans. Acoust. Speech Signal Process, ASSP-34, 898-911 (1986)
[9] Arce, G. R.; McLoughlin, M. P., Theoretical analysis of the max/median filter, IEEE Trans. Acoust Speech Signal Process, ASSP-35, 60-69 (1987)
[10] Grätzer, G., Lattice Theory (1971), Freeman: Freeman San Francisco, CA · Zbl 0385.06015
[11] Fitch, J. P.; Coyle, E. J.; Gallagher, N. C., Median filtering by threshold decomposition, IEEE Trans. Acoust. Speech Signal Process, ASSP-32, 1183-1188 (1984) · Zbl 0575.93061
[12] Ataman, E.; Aatre, V. K.; Wong, K. M., A fast method for real-time median filtering, IEEE Trans. Acoust. Speech Signal Process, ASSP-28, 415-421 (1980) · Zbl 0522.94002
[13] Butz, A. R., Functions realized by consistent sequential machines, Inform. and Control, 48, 147-191 (1981) · Zbl 0461.68052
[14] Delman, D. J., Digital pipelined hardware median filter design for real-time image processing, (Proc. SPIE Int. Soc. Opt. Eng., 298 (1981)), 184-188
[15] Oflazer, K., Design and implementation of a single chip 1-D median filter, IEEE Trans. Acoust. Speech Signal Process, ASSP-31, 1164-1168 (1983)
[16] Irmin, M. J.; Owens, R. M., Digit-pipelined arithmetic as illustrated by the paste-up system: A tutorial, Computer, 20, 61-73 (1987)
[17] Fitch, J. P., Software and VLSI algorithms for generalized ranked order filtering, IEEE Trans. Circuits and Systems, CAS-34, 553-559 (1987)
[18] David, H. A., Order Statistics (1981), Wiley: Wiley New York · Zbl 0223.62057
[19] Nodes, T. A.; Gallagher, N. C., The output distribution of median type filters, IEEE Trans. Comm., COM-32, 532-541 (1984)
[20] Arce, G. R.; Gallagher, N. C., State description for the root signal set of median filters, IEEE Trans. Acoust. Speech Signal Process, ASSP-30, 894-902 (1982)
[21] Wendt, P. D.; Coyle, E. J.; Gallagher, N. C., Some convergence properties of median filters, IEEE Trans. Circuits and Systems, CAS-33, 276-286 (1986)
[22] Butz, A. R., A class of rank order smoothers, IEEE Trans. Acoust. Speech Signal Process, ASSP-34, 157-165 (1986)
[23] Butz, A. R., Rank Order Smoothers, (Dept. Elec. Eng. Comput. Sci., Rep. 84-01-SCT-01 (Jan. 1984), Northwestern Univ: Northwestern Univ Evanston, IL) · Zbl 0667.93109
[24] Butz, A. R., Some properties of a class of rank order smoothers, IEEE Trans. Acoust. Speech Signal Process, ASSP-34, 614 f (1986)
[25] Butz, A. R., Smoothers Derived from PLC Separable Convex Functions, Dept. Elec. Eng. Comput. Sci., Rep. 86-02-SCT-01 (July 1986)
[26] Rockafellar, R. T., Convex Analysis (1970), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ · Zbl 0202.14303
[27] Narendra, P. M., A separable median filter for image noise smoothing, IEEE Trans. Pattern Anal. Machine Intelligence, PAMI-3, 20-29 (1981)
[28] Nodes, T. A.; Gallagher, N. C., Two-dimensional root structures and convergence properties of the separable median filter, IEEE Trans. Acoust. Speech Signal Process, ASSP-31, 1350-1365 (1983)
[29] Hahn, K. J.; Wong, K. M., Median filtering of cepstra, (Proc. IEEE International Electrical and Electronic Conference. Proc. IEEE International Electrical and Electronic Conference, Toronto (Sept. 1983)), 352-355
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.