Recursive Image Part Search Algorithm Complexity Estimation

Most common part for many approaches to object localization on image is a "sliding window" algorithm, which requires an exhaustive search in a wide range of window positions and size combinations. It can be assumed that a recursive approach of searching some image parts with a rejection of most areas at each step of the recursion could be more efficient in some cases. This article provides a recursive image part search algorithm description and an estimation of this algorithm's complexity. It also contains a comparison of complexity between the recursive algorithm and the "sliding window" algorithm. According to the results, an efficiency identifying condition for using the recursive algorithm instead of the "sliding window" algorithm is provided. According to the proposed criterion we proved the effectiveness of using the recursive algorithm in some cases.

References

[1] Shet V. Street View and reCAPTCHA technology just got smarter. Google Security Blog: website (in Russ.). Available at: https://security.googleblog.com/2014/04/street-view-and-recaptcha-technology.html (accessed 10.01.2017).

[2] Silveira J., Ferreira M.J., Santos C., Martins T. Computer vision techniques applied to the quality control of ceramic plates. Proc. IEEE Int. Conf. on Industrial Technology. Gippsland, ICIT, 2009. Available at: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.973.1308&rep=rep1&type=pdf (accessed 15.01.2017).

[3] Kuzmanic I., Vujovic I., Soda J. Damage detection in materials based on computer vision wavelet algorithm, advanced structured materials. Heidelberg, Germany, Springer Cham Heidelberg, 2014, pp. 157-186.

[4] Richards B., Dayton J., Enriquez M., Gan M., Liu J., Quintana J. Obstacle avoidance system for UAVs using computer vision. Cal Poly Pomona Student RSCA Conference. Pomona, California State Polytechnic University, 2014.

[5] Guizzo E. How Google’s self-driving car works. IEEE Spectrum: website. Available at: http://spectrum.ieee.org/automaton/robotics/artificial-intelligence/how-google-self-driving-car-works (accessed 09.01.2017).

[6] Lepetit V. On computer vision for augmented reality. International Symposium on Ubiquitous Virtual Reality. 2008, pp. 13-16. DOI: 10.1109/ISUVR.2008.10 Available at: http://ieeexplore.ieee.org/document/4568635

[7] Forsyth D.A., Ponce J. Computer vision: a modern approach. 2nd Edition. Upper Saddle River, New Jersey, Pearson Education, Inc., 2011. 793 p.

[8] Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to algorithms. Mit Press, 2001. 1180 p. (Russ. ed.: Algoritmy: postroenie i analiz. Moscow, Vil’yams Publ., 2015. 1328 p.).

[9] Bykova V.V. Mathematical methods for the analysis of recursive algorithms. Zhurnal SFU. Ser. Matematika i fizika [Journal of Siberian Federal University. Ser. Mathematics and Physics], 2008, vol. 1, no. 3, pp. 236-246 (in Russ.). Available at: http://elib.sfu-kras.ru/bitstream/handle/2311/772/%20%20%20%20%20%20.pdf;jsessionid=743184DA481880B26C8DF7F248CA40CA?sequence=1

[10] Murphy K., Torralba A., Eaton D., Freeman W. Object detection and localization using local and global features. In: Toward category-level object recognition. Heidelberg, Germany, Springer Berlin Heidelberg, 2006, pp. 382-400. DOI: 10.1007/11957959_20 Available at: http://link.springer.com/chapter/10.1007/11957959_20

[11] Erhan D., Szegedy S., Toshev A., Anguelov D. Scalable object detection using deep neural networks. IEEE Conf. on Computer Vision and Pattern Recognition. 2014, pp. 2155-2162. DOI: 10.1109/CVPR.2014.276 Available at: http://ieeexplore.ieee.org/document/6909673

[12] Dalal N., Triggs B. Histograms of oriented gradients for human detection. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition (CVPR’05). 2005, vol. 1, pp. 886-893. DOI: 10.1109/CVPR.2005.177 Available at: http://ieeexplore.ieee.org/document/1467360

[13] Corvee E. Body parts detection for people tracking using trees of histogram of oriented gradient descriptors. 7th IEEE Int. Conf. on Advanced Video and Signal Based Surveillance. 2010, pp. 469-475. DOI: 10.1109/CVPR.2005.177 Available at: http://ieeexplore.ieee.org/document/5597093

[14] Paul V., Jones M. Robust real-time face detection. International Journal of Computer Vision. 2004, vol. 57, no. 2, pp. 137-154. DOI: 10.1023/B:VISI.0000013087.49260.fb Available at: http://link.springer.com/article/10.1023/B%3AVISI.0000013087.49260.fb

[15] Rokach L., Maimon O. Classification trees, data mining and knowledge discovery handbook. New York, Springer US, 2010, pp. 149-151.