Contour generation for multivalued streamed images using crack codes on a GPU

Main Article Content

M. Usman Butt
John Morris
Nitish Patel
Morteza Biglari-Abhari


We describe an effi cient GPU algorithm which extracts multiple contours from an image. The algorithm uses crack codes to generate contours which sit logically between adjacent image values; it works scan line by scan line and it can generate multiple contours in parallel with an image streamed directly from a camera. Whilst specifi cally targeted at detecting object contours in stereo disparity maps, it can also be used for general segmentation with a trivial change to the code generating the crack code masks. Using a 480 ALU 1.4 GHz nVidia GPU, it can generate ~ 25000 contours from a real 2048 × 768 resolution 128 level disparity map image in ~ 29 ms if the contours are further processed in the GPU or ~ 39 ms if contours are transferred to the host - typically ~ 40 times faster than an OpenCV CPU implementation.

Article Details



Butt, M. U. and Morris, J. 2011. Precise Tracking using High Resolution Realtime Stereo. In: Image and Vision Computing New Zealand (IVCNZ2011), Auckland, New Zealand. IVCNZ, pp. 143–148.

Butt, M. U., Morris, J., Patel, N. and Biglari-Abhari, M. 2014. Contour generation for multivalued streamed images using crack codes on a GPU. The University of Auckland, Tech. Rep.

Cederberg, R. L. 1979.Chain-link coding and segmentation for raster scan Devices. Computer Graphics and Image Processing 10 (3), 224–234.

Chakravarty, I. 1981. A single-pass, chain generating algorithm for region Boundaries. Computer Graphics and Image Processing 15 (2), 182–193.

Chen, L. T., Davis, L. S. and Kruskal, C. P. 1993. Effi cient parallel processing of image contours. Pattern Analysis and Machine Intelligence, IEEE Transactions on 15 (1), 69–81.

Chia, T.-L., Wang, K.-B., Chen, L.-R. and Chen, Z. 2003. A parallel algorithm for generating chain code of objects in binary images. Information Sciences 149 (4), 219–234.

Freeman, H. 1961. On the encoding of arbitrary geometric confi gurations. Electronic Computers, IRE Transactions 2, 260–268.

Gimel’farb, G. L. 2002. Probabilistic regularisation and symmetry in binocular dynamic programming stereo. Pattern Recognition Lett, 23 (4), 431–442.

Kalarot, R. and Morris, J. 2010. Implementation of symmetric dynamic programming stereo matching algorithm using CUDA. In: 16th Korea-Japan JointWorkshop on Frontiers of Computer Vision, pp.141–146.

Khan, T., Morris, J., Javed, K. and Gimelfarb, G. 2009. Salmon: Precise 3D contours in real time. Dependable, Autonomic and Secure Computing, IEEE International Symposium on, vol. 0, pp. 424–429.

Kim, S.-D., Lee, J.-H. and Kim, J.-K. 1988. A new chaincoding algorithm for binary images using run-length codes. Computer Vision, Graphics, and Image Processing 41 (1), 114–128.

Leu, J.-G. 1991. Computing a shape’s moments from its boundary. Pattern Recognition 24 (10), 949–957. Li, H. F., Jayakumar, R. and Youssef, M.1989. Parallel algorithms for recognizing handwritten characters using shape features. Pattern recognition 22 (6), 641–652.

Morrin, I. et al. 1976. Chain-link compression of arbitrary black-white images. Computer Graphics and Image Processing 5 (2), 172–189.

Pavlidis, T. 1978. A minimum storage boundary tracing algorithm and its application to automatic inspection. IEEE Trans. Sytems, Man, and Cybernntics 8 (1), 66–69.

Rosenfeld, A. 1978. Algorithms for image/vector conversion. In: Proceedings of the 5th annual conference on Computer graphics and interactive techniques. ACM, pp. 135–139.

Shih, F. Y. and Wong, W.-T. 1992. A new single-pass algorithm for extracting the mid-crack codes of multiple regions. Journal of Visual Communication and Image Representation 3 (3), 217–224.

Sobel, I.1978. Neighborhood coding of binary images for fast contour following and general binary array processing. Computer graphics and image processing 8 (1), 127–135.

Suzuki, K. A. S. 1985. Topological structure analysis of digitized binary images by border following. Computer Vision, Graphics, and Image Processing 30, pp. 32–46.

Wilson, G. and Batchelor, B. 1990. Algorithm for forming relationships between objects in a scene, Computers and Digital Techniques. IEE Proceedings E 137(2), 151–153.

Zingaretti, P., Gasparroni, M. and Vecci, L. 1998. Fast chain coding of region Boundaries. IEEE Transactions on Pattern Analysis and Machine Intelligence 20 (4), 407–415.