Total views : 507
A Hybrid Convex Hull Algorithm for Fingertips Detection
Objectives: This article presents a hybrid convex hull algorithm to reduce computational resources in fingertips detection from an image. Methodology: In this paper, we suggest to reduce the computational resources by leveraging on two proven algorithms and techniques in order to extract the convex hull vertices directly from a binary image without going through the edge detection process. This is done by embedding Bresenham algorithm within Jarvis March to replace most of the work required in the edge detection process. Findings: The hybrid convex hull algorithm which we have suggested requires only four global extreme points to begin with and thus the pre-processing step takes much less resources. The new algorithm yields time complexity of O(N2). Novelty/Improvement: The hybrid convex hull algorithm offers a direct way to detect the convex hull of the original image without edge detection process.
Bresenham Algorithm, Convex Hull, Fingertips detection, Jarvis March.
- o'Rourke J. Computational Geometry in C.2nd Edition. Cambridge University Press; 1998 Oct 13.
- Rosenfeld A, Kak AC. Digital Picture Processing. Volume 1. 2nd Edition. Academic Press: New York, 1985.
- Bass LJ, Schubert SR. On Finding the Disc of Minimum Radius Containing a Given Set of Points. Mathematics of Computation. 1967 Oct 1; 21(100): 712–4.
- Graham RL. An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters. 1972 Apr; 10(3):132–3.
- Sklansky J. Measuring Concavity on a Rectangular Mosaic. IEEE transactions On Computers.1972 Dec 1; C-21(12):1355–64.
- Bykat A. Convex Hull of a Finite Set of Points in Two Dimensions. Information Processing Letters. 1978 Oct 31; 7(6):296–8.
- Sklansky J. Finding the Convex Hull of a Simple Polygon. Pattern Recognition Letters. 1982 Dec 31; 1(2):79–83.
- Toussaint GT, ElGindy H. A Counterexample to an Algorithm for Computing Monotone Hulls of Simple Polygons. Pattern Recognition Letters. 1983 May 31; 1(4):219–22.
- Team OD. Open CV Reference Manual. Version 2.2. 2010; 1073. Available from: http://docs.opencv.org/3.0-beta/opencv2refman.pdf. Date accessed: 17/06/2016.
- Jarvis RA. On the Identification of the Convex Hull of a Finite Set of Points in the Plane. Information Processing Letters. 1973 Mar 31; 2(1):18–21.
- Preparata FP, Hong SJ. Convex Hulls of Finite Sets of Points in Two and Three Dimensions. Communications of the ACM. 1977 Feb 1; 20(2):87–93.
- Preparata FP, Shamos MI. Computational Geometry: An Introduction. Springer, New York, 1985.
- Ye QZ. A Fast Algorithm for Convex Hull Extraction in 2D Images. Pattern Recognition Letters. 1995 May 31; 16(5): 531–7.
- Yu MP, Lo KC. Object Recognition by Combining Viewpoint Invariant Fourier Descriptor and Convex Hull. IEEE Proceedings of the 2001 International Symposium on Intelligent Multimedia, Video and Speech Processing, Hong Kong. 2001; 401–4.
- Zhang X, Tang Z, Yu J, Guo M. A Fast Convex Hull Algorithm for Binary Image. Informatica. 2010; 34(3):369–76.
- Shrivakshan GT, Chandrasekar C. A Comparison of Various Edge Detection Techniques used in Image Processing. IJCSI International Journal of Computer Science Issues. 2012 Sep; 9(5):272–6.
- Woun BS, Tan GY, Wong YP, Ng E. Partitioning Method in Noise Reduction to Improve Hand Detection, IJFCC International Journal of Future Computer and Communication. 2013 Oct 1; 2(5):395–8.
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.