A Simple Model for On-Sensor Phase-Detection Autofocusing Algorithm

Open Access JCC

[4,18]. Hence, the overall complexity is then O(nlog2n).

When, in turn, the Kief er-Wolfowitz algorithm is used to

determine the focus position , the number of test points in

which the correlation is computed is usually fixed (and

slightly larger than O(logn)).5

6.6. Image Readout Issues

Using the image sensor for focusing is clearly beneficial

from the video compatibility point of view. However, it

also means that the algorithm speed is limited by the

sensor framerate. Clearly, this problem is more signifi-

cant in CD algorithms than in PD ones (especially in a

single-ima g e open-loop version of the latter), but in ei-

ther case can further be alleviated when a sensor at hand

offers random access to pixels and one is interested in

focusing in a selected region of the scene.

Acknowledgements

The work is supported by the NCN gran t UMO-2011/01/

B/ST7/00666 .

REFERENCES

[1] J. W. Goodman, “Statistical Optics,” Wiley-Interscience,

New York, 2000.

[2] P. Seitz and A. J. Theuwissen, “Single-Photon Imaging,”

Springer, 2011.

http://dx.doi.org/10.1007/978-3-642-18443-7

[3] S. J. Ray, “Applied Photographic Optics,” 3rd Edition,

Focal Pre ss , Oxford, 2004.

[4] J. Kiefer, “Sequential Minimax Search for a Maximum,”

Proceedings of the American Mathematical Society, Vol.

4, No. 3, 1953, pp. 502-506.

http://dx.doi.org/10.1090/S0002-9939-1953-0055639-3

[5] H. J. Kushner and G. G. Yin, “Stochastic Approximation

and Recursive Algorithms and Applications,” 2nd Edition,

Springer, New York, 2003.

[6] G. Lippmann, “Epreuves Reversibles Donnant la Sensa-

tion du Relief,” Journal of Theoretical and Applied

Physics, Vol. 7, No. 1, 1908, pp. 821-825.

http://dx.doi.org/10.1051/jphystap:019080070082100

[7] L. Kovacs and T. Sziranyi, “Focus Area Extraction by

Blind Deconvolution for Defining Regions of Interest,”

IEEE Transactions on Pattern Analysis and Machine In-

telligence, Vol. 29, No. 6, 2007, pp. 1080-1085.

http://dx.doi.org/10.1109/TPAMI.2007.1079

[8] K. S. Pradeep and A. N. Rajagopalan, “Improving Shape

from Focus Using Defocus Cue,” IEEE Transactions on

Image Processing, Vol. 16, No. 7, 2007, pp. 1920-1925.

http://dx.doi.org/10.1109/TIP.2007.899188

[9] A. N. R. R. Hariharan, “Shape-from-Focus by Tensor

Voting,” IEEE Transactions on Image Processing, Vol.

21, No. 7, 2012, pp. 3323-3328.

http://dx.doi.org/10.1109/TIP.2012.2190612

[10] M. Subbarao and J.-K. Tyan, “Selecting the Optimal Fo-

cus Measure for Autofocusing and Depth-from-Focus,”

IEEE Transactions on Pattern Analysis and Machine In-

telligence, Vol. 20, No. 8, 1998, pp. 864-870.

http://dx.doi.org/10.1109/34.709612

[11] P. Śliwiński, “Autofocusing with the Help of Orthogonal

Series Transforms,” International Journal of Electronics

and Telecommunications, Vol. 56, No. 1, 2010, pp. 31-37.

http://dx.doi.org/10.2478/v10177-010-0004-5

[12] A. Cohen and J.-P. D’Ales, “Nonlinear Approximation of

Random Functions,” SIAM Journal of Applied Mathe-

matics, Vol. 57, No. 2, 1997, pp. 518-540.

http://dx.doi.org/10.1137/S0036139994279153

[13] R. A. DeVore, B. Jawerth and B. Lucier, “Image Com-

pression through Wavelet Transform Coding,” IEEE

Transactions on Information Theory, Vol. 38, No. 2, 1992,

pp. 719-746. http://dx.doi.org/10.1109/18.119733

[14] A. Chambolle, R. A. DeVore, N. Y. Lee, and B. J. Lucier,

“Nonlinear Wavelet Image-Processing—Variational-

Problems, Compression, and Noise Removal through

Wavelet Shrinkage,” IEEE Transactions on Image Pro-

cessing, Vol. 7, No. 3, 1998, pp. 319-335.

http://dx.doi.org/10.1109/83.661182

[15] D. L. Donoho, M. Vetterli, R. A. DeVore and I. Daube-

chies, “Data Compression and Harmonic Analy sis,” IEEE

Transactions on Information Theory, Vol. 44, No. 6, 1998,

pp. 2435-2476. http://dx.doi.org/10.1109/18.720544

[16] R. M. Gray and L. D. Davisson, “An Introduction to Sta-

tistical Signal Processing,” Cambridge University Press,

New York, 2011.

[17] S. Yakowitz, P. L’ecuyer and F. Vázquez-Abad, “Global

Stochastic Optimization with Low-Dispersion Point Sets,”

Operations Re search, Vol. 48, No. 6, 2000, pp. 939 -950.

http://dx.doi.org/10.1287/opre.48.6.939.12393

[18] W. H. Press, S. A. Teukolsky, W. T. Vetterling and B. P.

Flannery, “Numerical Recipes in C++: The Art of Scien-

tific Computing,” Cambridge University Press, Cambridge,

2009.

[19] J. Kiefer and J. Wolfowitz, “Stochastic Estimation of the

Maximum of a Regression Function,” The Annals of Ma-

thematical Statistics, Vol. 23, No. 3, 1952, pp. 462-466.

http://dx.doi.org/10.1214/aoms/1177729392

[20] C. Horn and S. Kulkarni, “Convergence of the Kiefer-

Wolfowitz Algorithm under Arbitrary Disturbances,”

American Control Conference, Vol. 3, 1994, pp. 2673-

2674.

[21] T. L. Lai, “St oc hast ic Approximation: Invited Paper,” The

Annals of Statistics, Vol. 31, No. 2, 2003, pp. 391-406.

http://dx.doi.org/10.1214/aos/1051027873

[22] R. Rubinstein, “Smoothed Functionals in Stochastic Op-

timization,” Mathematics of Operations Research, Vol. 8,

No. 1, 1983, pp. 26-33.

http://dx.doi.org/10.1287/moor.8.1.26

[23] J. Kreimer and R. Y. Rubinstein, “Nondifferentiable Op-

timization via Smooth Approximation: General Analyti-

cal Approach,” Annals of Operations Research, Vol. 39,

No. 1, 1992, pp. 97-119.

5Without the warranty that the exact focus position is found.