Three Dimensional Image Processing in Hexagonal Prism Lattice of Z3 Grid

  • Mohd. Sherfuddin Khan Research Scholar G.H Raisoni College of Engineering Nagpur, Maharashtra, India
  • E. G. Rajan President Pentagram research Centre Hyderabad, Telangana State, India
  • Vijay H. Mankar HOD (ECE) Government Polytechnic Ahmednagar, Maharashtra, India
Keywords: Hexagonal Lattice Grid, Hexagonal Lattice Grid Images, Hexagonal Lattice Grid Image Processing


A 2D hexagonal image is an array of what are called pixels which are the coordinates of the hexagonal lattice points decided by the linear horizontal rows and the nonlinear vertical zig-zags. A 2D hexagonal image could also be informally called as image slice or a matrix of pixel values arranged in a hexagonal array. A 3D hexagonal image is viewed as an ordered sequence of 2D hexagonal image slices arranged in the z-direction and the 3D arrangement of voxel values is called as a prism of voxel values. Most of the 3D hexagonal image processing operations are similar to those of 2D hexagonal image processing. 3D hexagonal images are processed with the help of 3D hexagonal scanning windows, whereas 2D hexagonal images are processed with the help of 2D hexagonal scanning windows. For instance, a 3D hexagonal image processing operation like 3D surface detection is carried out using analogous 2D edge detection algorithm on every image slice and the processed slices assembled to visualize 3D surface detected image. In fact, 2D contours of an image slice are called superficial features and closed surfaces of a 3D image are called volumetric features. One can always obtain surface detected version of a 3D hexagonal image by processing the 2D hexagonal image slices using 2D edge detection operation, and consequently the 3D surface detection operation is termed as 2.5D hexagonal image processing. One could also process the 3D hexagonal image data using a 3D surface detection algorithm, in which case it is termed as 3D hexagonal image processing. This is not the case with the operation of skeltonization. One cannot make use of 2.5D skeletonization operation of 2D image slices in order to get skeltonized version of the corresponding 3D image. In fact, one would come across discrepancies and differences when 2.5D skeletonization of 2D hexagonal image slices of a 3D hexagonal image is carried out instead of the direct 3D skeletonization of the 3D hexagonal image. This paper highlights certain 3D algorithms for processing 3D hexagonal images.



Author Biography

Mohd. Sherfuddin Khan, Research Scholar G.H Raisoni College of Engineering Nagpur, Maharashtra, India

E. G. Rajan


Pentagram research Centre

Hyderabad, Telangana State, India


(1) H. Blum, “A Transformation for Extracting New Descriptors of Models for the Perception of Speech and Visual Form”, W. Wathen-Dunn, ed., US: MIT Press, Combridge. pp 362-380. 1967

(2) L.R.Nackman and S. M. Pizer, “Three dimensional axis transform I: Theory”, IEEE Trans. On Pattern analysis and Machine Intelligence, Vol. 7, no. 2, pp. 187-202, March 1985.

(3) Cornea, N. D., Min, P.,“Curve-skeleton properties, applications, and algorithms”, IEEE Transactions on Visualization and Computer Graphics, vol. 13, No. 3, pp. 530-548. May-Jun, 2007

(4) Kalman Palagyi, Erich Sorantin, Emese Balogh, Attila Kuba, Csongor Halmai, Balazs Erdohelyi, and Klaus Hausegger, “A Sequential 3D Thinning Algorithm and Its Medical Applications,” in Proc. 17th international Conf. IPMI, vol. 2082, 2001, pp. 409-415.

(5) Kalman Palagyi and Attila Kuba, “A 3D 6-subiteration thinning algorithm for extracting medial lines,” Pattern Recognition Letters, vol. 19,1998, pp. 613-627.

(6) Kalman Palagyi and Attila Kuba, “Directional 3D thinning using 8 subiterations,” in Proc. 8th international Conf. DGCI, vol. 1568, 1999, pp. 325-336.

(7) Ta-Chih Lee, Rangasami L. Kashyap and Chong-Nam Chu, “Building skeleton models via 3-D medial surface/axis thinning algorithms,” CVGIP : Graphical Models and Image Proc., vol. 56, 1994, pp. 462-478.

(8) Gunilla Borgefors, “Distance transformations in digital images,” Computer Vision, Graphics, and Image Processing, vol. 34, 1986, pp. 344-371.

(9) Gunilla Borgefors, “Distance transformation in arbitrary dimensions,” Computer Vision, Graphics, and Image Processing, vol. 27, 1984, pp. 321-345.

(10) Gunilla Borgefors, “On digital distance transforms in three dimensions,” Computer Vision and Image Understanding, vol. 64, 1996, pp. 368-376.

(11) Frank Y.Shih and Christopher C.Pu, “A skeletonization algorithm by maxima tracking on Euclidean distance transform”, Pattern Recog., vol. 28, 1995, pp. 331-341.

(12) Franz Aurenhammer, “Voronoi diagrams - A Survey of a fundamental geometric data structure,” ACM Computing Surveys, vol. 23, 1991, pp. 345-405.

(13) Jonathan W. Brandt and V. Ralph Algazi, “Continuous skeleton computation by Voronoi diagram,” CVGIP : Image Understanding, vol. 55, 1991, pp. 329-338.

(14) Kenneth E. Hoff III, Tim Culver, John Keyser, Ming Lin and Dinesh Manocha “Fast computation of generalized Voronoi diagrams using graphic hardware,” in Proc. 26th annual Conf.

Computer graphics and interactive technique, 1999, pp. 277-286.

(15) Xiaopeng SUN, J. PAN, and Xiaopeng WEI, “3D Mesh Skeleton Extraction Using Prominent Segmentation”, ComSIS Vol. 7, No. 1, Special Issue, February 2010.

(16) Ma, W., Wu, F.,Ouhyoung M.,“Skeleton Extraction of 3D Objects with Radial Basis Functions”, IEEE Proceedings of Shape Modeling International. Seoul, Korea,pp. 207-215, 2003

(17) Oscar Kin-Chung Au, Chiew-Lan Tai, Hung-Kuo Chu, Daniel Cohen-Or, Tong-Yee Lee,“Skeleton Extraction by Mesh Contraction”, ACM Transactions on Graphics (SIGGRAPH 2008 issue), Vol. 27, No. 3, 44:1-44:10. (2008)

(18) Han-Bing Yan, Shi-Min Hu, Ralph R Martin, and Yong-Liang Yang, “Shape Deformation using a Skeleton to Drive Simplex Transformations”, IEEE Transaction on Visualization and Computer Graphics, vol. 14, No. 3, 693-706. (2008)

(19) Dey T.K., Sun J.,“Defining and Computing Curve-Skeletons with Medial Geodesic Function”, In Proceedings of Eurographics Symp. Geometry Processing, Cagliari, Sardinia, Italy,143-152.(2006)

(20) Telea, A., Vilanova A.,“A robust level-set algorithm for centerline extraction”, in Eurographics/IEEE Symposium on Visualization, Grenoble, France , 185–194.(2003)

(21) Zhang, X., Liu, J., Jaeger Z. Li. M.,“Volume decomposition and hierarchical Skeletonization”, In VRCAI ’08: Proceedings of The 7th ACM International Conference on Virtual-Reality Continuum and Its Applications in Industry. Singapore; December. (2008).

(22) C.W.Niblack, P.B.Gibbons, and D.W.Capson, “Generating skeletons and centerlines from the distance transform”, CVGIP: Graphical Models and Image Processing, vol.54, no.5, pp.420–


(23) T.Saito and J.Toriwaki,“Reverse distance transformation and skeletons based upon the Euclidean metric for n-dimensional digital binary pictures”, IEICE Trans. INF & SYST, Japan, vol.E77-D, no.9, pp.1005–1016 (1994)

(24) Y.Kawase, S.Yokoi, J.Toriwaki, and T.Fukumura, “A thinning algorithm for three-dimensional binary images”, Trans. on IEICE, Japan, vol.J68-D, no.4,pp.481–488 (1985)

(25) La,L.,Lee,S.W.,Suen,C.Y.,“Thinning methodologies- a comprehensive survey”, IEEE Trans. PAMI, Vol. 14, pp. 869-885, 1992.

(26) Mohd sherfuddin khan “Volumetric Features Extraction using 2.5D and 3D Algorithms”international journal of communication networks and distributed systems inderscience publishers issue No.3-4 vol 18 2017 pp:248-263

(27) Mohd sherfuddin khan “ skeletonization of 3D images using 2.5D and 3D Algorithms” 1st International Conference on Next Generation Computing Technologies (NGCT), 2015, At Deharadun, INDIA sept 4-5, pp 971-975

(28) M.Golay, "Hexagonal parallel pattern transformation", IEEE Transactions on computers, Vol. 18, No.8, pp.733- 740, 1969. R.M.Mersereau., "The process of hexagonally sampled Two – dimensional signals", Proceedings of the IEEE, Vol 67, pp.930-949, 1979.

(29) B.Kamgar-Parsi and W.A. Sander, III, "Quantization error in spatial sampling: comparison between square and hexagonal pixels", Computer Vision and Pattern Recognition, Proceedings CVPR ‘89’ pp. 604 – 611, 1989.

(30) B.Kamgar-Parsi, "Quantization error in hexagonal sensory configurations", IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.14, No.6, pp. 665-671, 1992.

(31) J.P.Mylopoulos and T.Pavlidis, "On the topological properties of quantized spaces, I. the notion of dimension", Journal of the ACM (JACM), Vol.18, No.2, pp. 239-246, 1971.

(32) J.P.Mylopoulos and T.Pavlidis, "On the topological properties of quantized spaces, II. connectivity and order of connectivity", Journal of the ACM (JACM), Vol 18,No 2, pp.247- 254,1971.

(33) R.Vitulli, et al., "Aliasing effects mitigation by optimized sampling grids and impact on image acquisition chains", Geoscience and Remote Sensing Symposium, IGARSS '02, pp. 979-981, 2002.

(34) Eric Anterrieu, Philippe Waldteufel and André Lannes, “Apodization Functions for 2-D Hexagonally Sampled Synthetic Aperture Imaging Radiometers”, IEEE Transactions On Geoscience And Remote Sensing, Vol. 40, No. 12, pp. 2531-2542, December 2002.

(35) Lee Middleton and Jayanthi Sivaswamy , “Hexagonal Image Processing – A Practical approach”, Springer-Verlag London Limited, 2005.

(36) Senthil Periaswamy, “Detection of Micro calcifications in Mammograms Using Hexagonal Wavelets”, Thesis work, University of South Carolina, 1996.

(37) L. Condat, D. Van De Ville, and T. Blu, “Hexagonal versus orthogonal lattices: A new comparison using approximation theory,” in Proceedings of IEEE, ICIP,Vol. 3, Sept. 2005.

(38) M. Unser, “Splines: A perfect fit for signal and image processing,” IEEE Signal Processing Magazine., Vol. 16, No. 6, pp. 22–38, Nov. 1999.

(39) D. Van De Ville, W. Philips, and I. Lemahieu, “Least-squares spline resampling to a hexagonal lattice,” Signal Processing: Image Communication, Vol. 17, No. 5, pp. 393–408, May 2002.

(40) L. Condat and D. Van De Ville , “Quasi-interpolating spline models for hexagonally sampled data,” IEEE Transactions on Image Processing, Vol. 16, No. 5, May 2007, pp.1195-1206.

(41) P. Th´evenaz, T. Blu, and M. Unser, “Interpolation revisited,” IEEE Transactions on Medical Imaging , Vol. 19, No.7, pp. 739–758, July 2000.

(42) D. E. Dudgeon and M. E. Mersereau, Multidimensional Signal Processing. Englewood Cliffs, NJ: Prentice-Hall, 1984.

(43) D. Van De Ville, T. Blu,M. Unser,W. Philips and I. Lemahieu, “Hex-spline: A novel family for hexagonal lattices,” IEEE Transactions on Image Processing, Vol. 13, No. 6, June 2004, pp.758–772.

(44) Laurent Condat and Dimitri Van De Ville,“Three-directional box-splines: Characterization and efficient evaluation,” IEEE Signal Processing Letters., Vol. 13, No. 7, July 2006 , pp. 417–420.

(45) C. de Boor, K. Hollig, and S. Riemenschneider, “Box Splines”: Springer-Verlag, 1993, Applied Mathematical Sciences,Vol. 98.

(46) H. Prautzsch and W. Boehm, “Box splines,” in Handbook of Computer Aided Geometric Design. Berlin: Springer, 2001.

(47) Lee, T.S, “Image Representation Using 2D Gabor Wavelets, IEEE Transactions on Pattern Analysis and Machine Intelligence, ” Vol. 18, Issue 10, 1996, pp. 951-979.

(48) Xu, Y., Zhang, X ,“ Gabor Filter bank and its Application in the Fingerprint Texture Analysis,” PDCAT 2005, pp. 829-831.

(49) Huang, L., Shimizu, A., Kobatake, H , “Classification-Based Face Detection Using Gabor Filter Features,” Proceedings of the IEEE International Conference on Automatic Face and Gesture Recognition, 2004, pp. 397-402.

(50) Jain, A.K., Prabhakar, S., Hong, L., Pankanti, S,“Filter bank-Based Fingerprint Matching,” IEEE Transactions on Image Processing, Vol. 9, Issue 5, 2000, pp. 846-859.

(51) Jones, J.P., Palmer, L.A, “An Evaluation of the Two-Dimensional Gabor Filter Model of Simple Receptive Fields in Cat Striate Cortex, “ Journal of Neurophysiology, Vol. 58, Issue 6, 1987, pp. 1233-1258.

(52) Veni. S, K.A. Narayanankutty, Satyapal Reddy.L, Vidya.P ,“ Wavelet based Edge detection and Multiresolution analysis on Hexagonal Sampled Grid Using Interpolation,” proceedings ICSIP - 2009 , August 12-14 2009 , Excel publications, ISBN:978-93-80043-26-5,pp.186-200.

(53) Veni.S, K.A.Narayanankutty , Vidya.P ,“ Performance analysis of Edge Detection methods on hexagonal sampling Grid,” International Journal of Electronics Engineering and Research (IJEER), Research India publications Vol.1, No. 4 (2009) ,pp. 313–328.