Appendice A
Un Algoritmo per la Selezione della Mediana Approssimata
In questa appendice introdurremo brevemente uno dei risultati conseguiti nel campo degli algoritmi approssimati, relativamente al classico problema della selezione della mediana. In particolare si è realizzato un algoritmo altamente competitivo, facile da implementare e tale da lavorare in-place, senza cioè richiedere ulteriore spazio rispetto a quello occupato dai dati stessi. Le prestazioni sono tali da garantire valori molto vicini alla mediana effettiva, con alta probabilità, con una complessità media pari a 4/3n nel numero dei confronti ed 1/3n nel numero degli scambi richiesti.
Dal punto di vista strettamente legato alla computer graphics, l'algoritmo si presta bene alla realizzazione di un filtro di smoothing, il cosiddetto filtro
mediana, soprattutto con maschere di convoluzione di dimensioni medio-grandi.
In letteratura è possibile trovare un'innumerevole serie di lavori che trattano il problema della selezione della mediana esatta con algoritmi in-place. Il miglior upper bound conosciuto (Dor, Zwick - 1999) è di 3n sul numero dei confronti nel caso peggiore (worst case) ma presenta notevoli difficoltà implementative.
L'algoritmo approssimato proposto invece oltre ad essere nettamente più veloce (3/2n nel numero dei confronti e 1/2n nel numero degli scambi nel caso peggiore) si presta ad un immediata implementazione e restituisce valori che approssimano la mediana con alta precisione.
1. L'Algoritmo
E' conveniente distinguere il caso in cui la cardinalità dell'insieme di input è una potenza di 3 dal caso più generale.
- Se la cardinalità dell'insieme di input è una potenza di 3, denotiamo con r il numero intero tale che n=3r . L'algoritmo procede in r passi, durante i quali esso divide l'input in sottoinsiemi di cardinalità 3, ne calcola la mediana esatta locale che viene promossa al passo successivo. L'algoritmo continua ricorsivamente, utilizzando i risultati locali per calcolare la mediana approssimata dell'intero insieme di partenza. Per diminuire il numero degli scambi gli elementi scelti a ciascun passo non vengono mossi dalla loro originale tripletta. Ciò introduce qualche manipolazione degli indici ma è spesso vantaggioso in termini di complessità. In Fig.1 mostriamo lo pseudo codice dell'algoritmo. La procedura Triplet_Adjust trova la mediana delle triplette che sono indicizzate da due parametri: il primo, detto i, denota la posizione dell'elemento più a sinistra delle triplette
nell'array, mentre il secondo, Step, è la relativa distanza tra gli elementi della tripletta. Con tale implementazione la mediana di ciascuna tripletta è sempre inserita nella posizione di mezzo. La procedura Appproximate_Median consiste semplicemente di successive chiamate a Triplet_Adjust.
Approximate Median Algorithm
Triplet_Adjust(A, i, Step)
Questa procedura sopsta la mediana di una tripletta i cui elementi hanno posto A[i], A[j], A[k] nella posizione di mezzo.
j = i + Step k = i + 2 Step
If ( A[i]<A[j] ) then
If (A[k] < A[i] ) then Swap( A[i],A[j] );
else If (A[k] < A[j] ) then Swap( A[j],A[k] );
else
If (A[i] < A[k] ) then Swap( A[i],A[j] );
else If (A[k] > A[j] ) then Swap( A[j],A[k] );
Approximate_Median(A, r)
Questa procedura restuituisce la mediana approssimata dell'array A[0, …, 3r -1].
Step=1;
Size= 3r;
Repeat r times
i = (Step-1)/2;
While i < Size do
Triplet_Adjust(A, i, Step)
i=i+(3 Step);
End while;
Step=3 Step;
End Repeat;
Return A[(Size-1)/2];
Figura 1. Pseudo codice dell'algoritmo per la mediana approssimata per n= 3r, r∈N.
- Se la cardinalità dell'insieme di input non ricade nel caso precedente l'algoritmo può comunque facilmente essere generalizzato nel modo più naturale. Sia n il numero di elementi di cui si vuole calcolare la mediana dove n = 3⋅ t + k, k∈{0, 1, 2}. E' possibile dividere gli elementi in t-1 triplette più
una tupla di (3+k) elementi. Le prime vengono processate con la procedura Triplet_Adjust di cui sopra, l'ultima tupla viene invece ordinata direttamente e ne viene estratta la mediana esatta. Si procede iterativamente in questo modo utilizzando i risultati di ciascun passo come input per il successivo. Quando il numero di elementi "sopravvissuti", scende al di sotto di una certa soglia, si ordinano gli elementi e se ne calcola così la mediana esatta. Per garantire un certo equilibrio statistico, gli elementi vengono scanditi alternandone la direzione (destra-sinistra, sinistra-destra) ad ogni passo.
2. Analisi dell'Algoritmo: Complessità e Performance
Ciò che è più dispendioso in termini strettamente computazionali è legato al numero di confronti e di scambi eseguiti nella procedura Triplet_Adjust volti alla determinazione della mediana locale. L'analisi di complessità della procedura Approximate_Median è quindi direttamente ricavata direttamente da un'accurata analisi di questi due parametri. La complessità computazionale che ne viene fuori è lineare, ma l'algoritmo si distingue per la semplicità del suo codice e per la sua efficienza (legata al basso valore raggiunto della costante moltiplicativa in oggetto). Se consideriamo l'algoritmo di base di Fig. 1, per n = 3r, r∈ N si hanno i seguenti risultati, la cui dimostrazione può essere trovata direttamente in (Battiato, Cantone, Catalano, Cincotti, Hofri - 1999):
Teorema 1. Dato in input un insieme di cardinalità n = 3r, r∈ N, l'algoritmo Approximate_Median ha una complessità nel caso medio (analisi average-case) pari a 4/3 n nel numero dei confronti e 1/3 n nel numero degli scambi.
Teorema 2. Dato in input un insieme di cardinalità n = 3r, r∈ N, l'algoritmo Approximate_Median ha una complessità nel caso peggiore (analisi worst-case) pari a 3/2 n nel numero dei confronti e 1/2 n nel numero degli scambi.
Oltre all'analisi di complessità risulta fondamentale nello studio degli algoritmi approssimati l'analisi probabilistica legata alla precisione dei risultati. Nel caso dell'algoritmo Approximate_Median di Fig.1 si noti come innanzitutto sia possibile riuscire a trovare un range certo sul rank dell'output, semplicemente osservando l'albero di ricorsione costruito dall'algoritmo. Sia ν(n) il numero di elementi "piccoli" (e simmetricamente "grandi") in termini di rank, che non possono essere selezionati dall'algoritmo. Si dimostra che, detto x l'output dell'algoritmo di Fig.1 ne segue necessariamente:
ν(n) < rank(x) < n - ν(n) + 1 (1) dove:
Il secondo algoritmo, per n generici, si comporta in maniera del tutto simile eccetto per i valori iniziali e per il fatto che viene necessariamente a mancare la simmetria.
Sfortunatamente questi range non sono poi così grandi. Ciò risulta ancora più evidente considerando il rapporto ν(n)/n che è approssimativamente pari a
1 2
)
(n = log3n− ν
(2/3)log3
n. Quindi per n = 33 = 27 i più piccoli (e i più grandi) 7 elementi non vengono selezionati ben il 52% del totale; tale valore però diventa pari al 17.30%
per n = 36 = 729 e soltanto dell'1.73% per n = 312 = 531441.
L'effettiva bontà dell'algoritmo viene valutata quindi in termini probabilistici, studiando opportunamente la seguente la seguente funzione di probabilità:
P(z)= Pr[zn < rank(x) < (1-z)n +1] (2) per 0 ≤ z ≤ 1/2.
Allo stato attuale non esiste una forma chiusa ed analitica di tale funzione, ma sia le approssimazioni seguite ad un analisi teorico statistica sia i risultati sperimentali mostrano chiaramente che al crescere del numero di elementi la distribuzione di probabilità della funzione (2) tende alla distribuzione normale.
Nella tabella che segue alcuni risultati sperimentali evidenziano il comportamento statistico della deviazione d della mediana approssimata da quella esatta. In particolare:
I numeri nella tabella sono valori normalizzati di d espressi in percentuale e indicati con il simbolo d% (il valore 0 indica la mediana esatta mentre il valore 100 il numero più piccolo o più grande dell'array di input). Nel caso di array con cardinalità diversa da una potenza di tre utilizzano il valore 8 come valore di soglia. Ciascuna entry nella tabella si riferisce ad una media di 5000 prove eseguite su array con permutazioni pseudo-random di interi.
approx
exact
M
M
d = −
n Avg. σ Avg. + 2σ Range (95%) (Min-Max) 50 10.27 7.89 26.05 24.49 0.00-44.90 100 8.45 6.63 21.70 20.20 0.00-48.48 35 6.74 5.13 17.00 16.53 0.00-38.02 500 5.80 4.41 14.63 14.03 0.00-29.06 36 4.83 3.71 12.26 12.09 0.00-24.73 1000 4.70 3.66 12.02 11.61 0.00-23.62 37 3.32 2.54 8.41 8.05 0.00-16.83 5000 2.71 2.10 6.91 6.72 0.00-17.20 38 2.31 1.75 5.81 5.67 0.00-11.95 10000 2.53 1.86 6.24 6.04 0.00-11.38 39 1.58 1.18 3.94 3.86 0.00-6.78
Le colonne di tale tabella indicano rispettivamente:
- n la cardinalità dell'insieme di input;
- Avg la media di d% sul campione;
- σ l'errore-standard di d%;
- Range (95%) lo spazio in termini di distanza dalla mediana esatta in cui ricadono il 95% dei valori restituiti dall'algoritmo;
- (Min-Max) gli estremi osservati su d%.
Le ultime due colonne, in particolare ci mostrano la vicinanza della distribuzione in oggetto con quella Gaussiana.
3. Conclusioni
Si è presentato un algoritmo per la ricerca della mediana approssimata, che risulta essere competitivo dal punto di vista computazionale a dispetto della
relativa semplicità dell'idea di base. Inoltre è allo studio una versione estesa dell'algoritmo volto a selezionare il k-esimo elemento.
E' nostra intenzione riuscire ad eseguire una serie di prove comparate volte a confrontare le performance di tale algoritmo, con le tecniche attualmente più diffuse, nell'applicazione a immagini digitali del relativo filtro di smoothing.
Bibliografia
J.M.Acken, How Watermarking Adds Value to Digital Content, Communications of the ACM, Vol.41, No.7 pp. 75-77 July 1998.
C.H. Anderson, W.D. Langer, Statistical Models of Image Texture, Preprint Wanshington University Medical School, 1996.
R.B.Ash, Information Theory, Interscience Publisher, New York, 1965;
S. Battiato, Entropy and Gibbs Distribution in Image Processing: an historical perspective, Preprint, University of Catania, 1999;
S. Battiato, D. Cantone, G. Cincotti, D. Catalano, M. Hofri, An Efficient Algorithm for the Approximate Median Selection Problem, Presented to the Fifth Annual Meeting on the Average-Case on the Analysis of Algorithms, Barcelona, Spain - June 1999. Extended version to appear to CIAC2000, Rome;
S. Battiato, D. Catalano, G. Gallo, R. Gennaro, Robust watermarking for images based on colors manipulation - In Proceedings of 3-rd Workshop on Information Hiding, Dresden 1999;
S. Battiato, D. Catalano, G. Gallo, R. Gennaro, A Color Opponency watermarking scheme for digital images - To appear IST/SPIE International Symposium - Electronic Imaging 2000 - Science & Technology, Security and Watermarking of Multimedia Contents II (ei23).
S. Battiato, G. Gallo, An Information-Theoretical Approach to Saliency Maps Construction, In Proceedings EUFIT'98, Aachen, Germany, Vol.2, pp.1375- 1380, 1998.
S. Battiato, G. Gallo, A Multi-resolution Clustered Approach to Analysis and Synthesis of Texture Images, In Proceedings of Workshop on Texture Analysis in Machine Vision TEXTURE'99, Oulu, Finland, pp.149-156, 1999.
A.E.Bell, G.W.Braudaway, F.Mintzer, Opportunities for Watermarking Standards, Communications of the ACM, Vol.41, No.7, pp.57-64, July 1998.
W.Bender, D.Gruhl, N.Morimoto, Techniques for data hiding, Proceedings of SPIE, Vol.2420, pag 40, 1995.
J.Besag, Spatial interaction and the statistical analysis of lattice systems (with discussion), J. Royal Statist. Soc., series B, Vol.36, pp.192-236, 1973.
J.R. Bergen, B. Julesz, Rapid discrimination of visual patterns, IEEE Transactions on Systems Man and Cybernetics 13,pp.857-863, 1993.
A.L.Berger, S.A.Della Pietra, V.J.Della Pietra, A Maximum Entropy Approach to Natural Language Processing, Computational Linguistics, Vol.22, No.1, 1996.
G.Brassard, P.Bratley, Algorithms, Theory and Practice, Prenctice Hall, 1988.
J.Brassil, S.Low, N.Maxemchuck, L.O'Gorman, Electronic marking and identification techniques to discourage document copying, Proceedings of Infocom'94, pp.1278-1287, 1994.
P.Brodatz, Textures: A Photographic Album for Artists &Designers, Dover, New York, 1966.
J.P. Burg, Maximum entropy spectral analysis, PhD dissertation, Stanford University, Stanford, CA, 1975.
P.J. Burt, E.H. Adelson, The laplacian pyramid as a compact image code, IEEE Transactions on Communications 31, pp.532-540, 1983.
G. Caronni, Assuring ownership rights for digital images, Proceedings of reliable IT Systems, VIS'95, Vieweg Publishing Company, 1995.
H.D. Cheng, J.R. Chen, J. Li, Threshold selection based on fuzzy c-partition entropy approach, Pattern Recognition, Vol.31, No.7, pp.857-870, 1998.
Z. Chi, H. Yan, T. Pham, Fuzzy Algorithm: With Applications to Image Processing and Pattern Recognition, World Scientific, 1996.
I.Cox, J.Kilian, T.Leighton, T.Shamoon, A secure robust watermark for multimedia. IEEE Transaction on Image Processing, Vol.6(12), pp. 1673- 1687, 1997.
S.Craver, Boon-Lock Yeo, M.Yeung, Technical Trials and Legal Tribulations, Communications of the ACM, Vol.41, No.7 pp. 45-56, July 1998.
G. R. Cross, A. K. Jain, Markov Random Field texture models, IEEE, Pattern Anal. Machine Intell., Vol 5, pp.25-39, 1983.
I. Daubechies, Ten lectures on wavelets, Society for Industry and Applied Math, Philadelphia, PA, 1992.
J.S. De Bonet, Multiresolution Sampling Procedure for Analysis and Synthesis of Texture Images, In Computer Graphics, pp.361-368, ACM SIGGRAPH, 1997.
J.S. De Bonet, MIT Jeremy S. De Bonet's home page - Demo of Texture Synthesis,
<http://www.ai.mit.edu/~jsd/Research/TextureSynthesis>, 1999.
J.S. De Bonet, P. Viola, Texture Recognition Using a Non-paramteric Multi-scale Statistical Model, In Proceedings IEEE Conf. on computer Vision and Pattern Recognition, 1998.
S. Della Pietra, V. Della Pietra, J. Lafferty, Inducing features on random fields, IEEE Trans. PAMI, Vol.19, No.4, 1997.
M.A. Delsuc, A new maximum entropy processing algorithm, with applications to nuclear magnetic resonance experiments, In Maximum entropy and Bayesian Methods, Ed. by J.Skilling, Netherlands, pp.285-290, 1989.
P. Diaconis, D. Freedman, On the statistics of vision: the Julesz conjecture, Journal of Mathematical Psychology, 24, 1981.
J. Dickerson, B. Kosko, Fuzzy function learning with covariance ellipsoids, In Proceedings IEEE International Conf. on Neural Network, Vol. III, pp.1162- 1167, San Francisco, USA, 1993.
D. Dor, U. Zwick, Selecting the Median, SIAM Journ. Comp., 28(5), pp.1722:1758, 1999.
M.M. Fleck, D.A. Forsyth, C. Bregler, Finding Naked People, Lectures in Computer Science, 1996.
J.D. Foley, A. Van Dam., S.K. Feiner, J.F. Hughes, Computer Graphics, Principle and Practice, Addison Wesley, 1990;
B.R. Frieden, J. Optical Soc. Amer., Vol.62, pp.511-518, 1972.
B.R. Frieden, Statistical models for the Image restoration problem, Computer Graphics and Image Processing 12, pp.40-59, 1980.
S. Geman, D. Geman, Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images, IEEE Trans. PAMI, Vol.6, No.6, pp.721-741, 1984.
A.S.Glassner, Principle of Digital Images, Morgan Kaufmann Publishers Inc., 1995.
C.M. Goldie, R.G. E. Pinch, Communication theory, Cambridge University Press, 1991.
O. Goldreich, Foundations of Cryptography (Fragments of a Book). Available on- line from <http://theory.lcs.mit.edu/oded/frag.html>, 1998.
R.M. Haralick, Statistical and structural approach to texture, Proceedings IEEE, Vol.67, 1979.
D.J. Heeger, J.R. Bergen, Pyramid-Based texture analysis/synthesis, In Computer Graphics, pp. 229-238, ACM SIGGRAPH, 1995.
C. Hillman, Entropy on the Web,
<http://www.math.washington.edu/~hillman/entropy.html>, 1998.
L.K. Huang, M. J. Wang, Image thresholding by minimizing the measure of fuzziness, Pattern Recognition , No.28, pp.41-51, 1995.
A. Jain, D. Zongker, Feature Selection: Evaluation, Application, and Small Sample Performance, IEEE Trans. PAMI, Vol.19, No.2, pp.153-158, Feb.
1997.
E.T. Jaynes, Information Theory and statistical mechanics, Physical Review 106, pp.620-630, 1957.
E.T. Jaynes, Notes on present status and future prospects, In W.T.Grandy and L.H. Schick, Maximum Entropy and Bayesan Methods, Kluwer, 1-13, 1990.
I. Jolliffe, Principal Component Analysis, New York, Springer Verlag, 1986.
E.Koch, J.Rindfrey, J.Zhao, Copyright proptection for multimedia data, Proceedings of Int. Conf. on Digital Media and Electronic Publishing, 1994.
T. Kohonen, The self-organizing map, In Proceedings of IEEE, 78(9) pp.1464- 1480, 1990.
M. Kutter, F.A.P. Petitcolas, A fair benchmark for image watermarking systems, To in E.Delp et al. (EDS), in Vol.3657, Proceedings of Electronic Imaging'99, Security and Watermarking of Multimedia Contents, San Josè, CA USA, 1999.
E. Levitan, M. Chan, G. T. Herman, Image-Modeling Gibbs Prior, in Graphical Models and Image Processing, Vol.57, No.2, pp.117-130, 1995.
S. Lepsoi, G.E. Oien, Fast Attractor Image Encoding by Adaptive Codebook Clustering, in Fractal Image Compression, Y. Fisher, Ed. Springer Verlag, pp.
177-197, 1994.
C.Luo, E.Koch, J.Zhao, In Business Today and Tomorrow, Communications of the ACM, Vol.41, No.7 pp 67-72, July 1998.
B.M.Macq, J.J.Quisquater, Cryptology for digital TV broadcasting, Proceedings of IEEE, 83(6), pp.944-957, 1957.
K.Matsui, K.Tanaka, Video-steganography, IMA Intellectual property Project Proceedings, Vol.1, pp.187-206, 1994.
N.Memon P.Wah, Wong, Protecting Digital Media Content, Communications of the ACM, Vol.41, No.7 pp 35-43, July 1998.
B. Moghaddam, A. Pentland, Probabilistic Visual learning for Object representation, IEEE Trans. On PAMI, Vol.19, No.7 pp.696-710.
A.N. Netravali, B.G. Haskell, Digital Pictures: Representation and Compression, Application of Communication Theory, Plenum Press, NY, 1988.
J.M. Ogden, E.H. Adelson, J.R. Bergen, P.J. Burt, Pyramid-Based Computer Graphics, RCA Engineer 30, pp.4-15, 1985.
S. Palmer, The psychology of perceptual organization: a transformational approach, Human and Machine Vision, J.Becj, B.Hope, A.Rosenfield eds, Academic Press 1983.
K. Perlin, E.M. Hoffert, Hypertexture, In Computer Graphics, Vol.23, No.3, pp.253-262, ACM SIGGRAPH, 1989.
F.A.P. Petitcolas, The information hiding homepage - digital watermarking &
steganography, <www.cl.cam.ac.uk/~fapp2/steganography/>, 1999.
F.A.P. Petitcolas, R.J. Anderson, M.G. Kuhn, Attacks on copyright marking systems, in David Aucsmith (Ed): Proceedings of Information Hiding, Second International Workshop, IH'98, LNCS 1525, Springer Verlag, pp.219-239.
B. Ramamurthi, A. Gersho, Classified Vector Quantization of Images, IEEE Trans. Comm., COM-34, pp. 1105-115, 1986.
C.E. Shannon, A Mathematical Theory of Communication, The Bell System Technical J., Vol.27, 1948.
C.E. Shannon, Communication Theory of Secrecy Systems, The Bell System Technical J., Vol.28, 1949.
E.P. Simoncelli, E.H. Adelson, Subband Transform, In Subband Image Coding, J.W Woods, Ed. Kluwer Academic Publishers, Norwell, MA, 1990.
E.P. Simoncelli, W.T. Freeman, E.H. Adelson, D.J. Heeger, Shiftable Multiscale Transform, IEEE Transactions on Information Theory 38, pp.587-607, 1992.
K. Sivakumar, J.Goutsias, Morphologically Constrained GRFs: Applications to Texture Synthesis and Analysis, IEEE Trans. Pattern Anal. Machine Intell., Vol.21, No.2, pp.99-113, 1999.
D.R. Stinson, Cryptography: Theory and Practice, CRC Press, 1995.
H.L. Tan, S.B. Gelfand, EJ. Delp, A Cost Minimization Approach to Edge Detection Using Simulated Annealing, IEEE Trans. Pattern Anal. Machine Intell., Vol.14, pp.3-18, 1991.
K.Tanaka, Y.Nakamura, K.Matsui, Embedding secret information into a dithered multi-level image, Proceedings of 1990 IEEE Military Communications Conference, pp. 216-220, 1990.
M. Turk, A. Pentland, Eigenfaces for recognition, J. of Cognitive Neuroscience, Vol.3, No.1, 1991.
R.Van Schyndel, A. Tirkel, C. Osborne, A digital watermark, Proceeding of ICIP, IEEE Press, pp. 86-90, 1994.
R. Vistnes, Texture models and image measures for testure discrimination, Int.l Journal of Computer Vision, Vol.3, pp.313-336,1989.
D. Welsh, Codes and Cryptography, Oxford Science Publications, 1988.
J. Weszka, C.R.Dyer, A. Rosenfelf, A comparative study of texture measures for terrain classification, IEEE Trans. Sys. Man. Cybern., Vol. SMC-6, 1976.
G. Winkler, Image Analysis, Random Fields and dynamic Monte Carlo Methods, Springer-Verlag, 1995.
N. Wu, The Maximum Entropy Method, Springer Verlag Series in Information Sciences, Vol.32, Springer Verlag, 1997.
Y.N. Wu, S. C. Zhu, Equivalence of Ensembles and Fundamental Bounds - A Unified theory of Texture Modeling and Analysis - Submitted to IEEE PAMI 1999.
R.R.Yager, D.P. Filev, A generalized de-fuzzification method via BAD distributions, Intern.Jour.of Intelligent Systems, Vol.6 pp.687-697, 1991.
M.Yeung, Digital Watermarking, Comm. of the ACM, Vol.41, No.7 pp 31-33, July 1998.
M. W. Zemansky, Heat and Thermodynamics, McGraw-Hill, New York, NY 1981.
S. C. Zhu, X. Liu, Y. N. Wu, Statistics Matching and Model Pursuit by Efficient MCMC - A conclusion to Julesz's Texture Quest? - Submitted to IEEE PAMI 1999.
S. C. Zhu, D. Mumford, Prior Learning and Gibbs Reaction-Diffusion, IEEE PAMI,Vol.18, no.11, pp. 1236-1250, Nov. 1997.
S. C. Zhu, Y. N. Wu, D. Mumford, Minimax Entropy Principle and Its Application to texture modeling, Neural Computation Vol.9, No.8, Nov. 1997.
S. C. Zhu, Y. N. Wu, D. Mumford, Filters, Random fields And Maximum Entropy (FRAME), Int’l Journal of Computer Vision, 27(2) 1-20, March/April 1998.
