Edge detection plays an important role in the areas of image processing, multimedia and computer vision. Gradient-based edge detection is a straightforward method to identify the edge points in the original grey-level image. It is intuitive that, in the human vision system, the edge points always appear where the gradient magnitude assumes a maximum. Hexagonal structure is an image structure alternative to traditional square image structure. The geometrical arrangement of pixels on a hexagonal structure can be described as a collection of hexagonal pixels. Because all the existing hardware for capturing image and for displaying image are produced based on square structure, an approach that uses bilinear interpolation and tri-linear interpolation is applied for conversion between square and hexagonal structures. Based on this approach, an edge detection method is proposed. This method performs Gaussian filtering to suppress image noise and computes gradients on the hexagonal structure. The pixel edge strengths on the square structure are then estimated before Canny' edge detector is applied to determine the final edge map. The experimental results show that the proposed method improves the edge detection accuracy and efficiency.