Finding the skeleton of 2D shape and contours: implementation of Hamilton-Jacobi skeleton

Abstract

This paper presents the details of the flux-ordered thinning algorithm, which we refer to as the Hamilton-Jacobi Skeleton (HJS). It computes the skeleton of any binary 2D shape. It is based on the observation that the skeleton points have low average outward flux of the gradient of the distance transform. The algorithm starts by computing the distance function and approximating the flux values for all pixels inside the shape. Then a procedure called homotopy preserving thinning iteratively removes points with high flux while preserving the homotopy of the shape. In this paper, we implement the distance transform using a fast sweeping algorithm. We present numerical experiments to show the performance of HJS applied to various shapes. We point out that HJS serves as a multi-scale shape representation, a homotopy classifier, and a deficiency detector for binary 2D shapes. We also quantitatively evaluate the shape reconstructed from the medial axis obtained by HJS.