Integrated Circuits and Systems group, IIT Madras

Algorithmic implementation and architectural design of a modified Watershed Algorithm for image segmentation applications

By Kumud Prakash Gupta

Abstract

Keywords: Watershed Transform, MPEG 4, FIFO, Mathematical Morphology, Segmentation The rapid advances in computer hardware, software and communication systems have opened the doors for the new cutting edge technology of multimedia communications. MPEG 4 is the new coding standard for multimedia communications. For MPEG 4 video, the most important functionalities are object-based interactivity, high coding efficiency, and improved error resilience. The content-based visual object representation is certainly the key to interactivity and other content-based functionalities of MPEG 4. However, to take advantage of these features, a prior decomposition of video sequences into semantically meaningful objects is required. Partitioning a video sequence into video object planes by means of automatic or semi automatic segmentation is a very difficult task and, comparatively little research has been undertaken in this field. Mathematical Morphology, the science of change of forms, has come up with many watershed transforms for segmentation. We use watershed transform methods for our present work.

The objective of this work is to propose a novel watershed transform algorithm for object segmentation in MPEG 4 applications, and develop an archirecture for the proposed algorithm. Towards this end, a modified serial watershed algorithm based on ordered queue, using mathematical morphology, is proposed. The proposed algorithm is also better than its original counterpart, Meyer et. al., in terms of memory requirement and speed. It helps in reducing the memory size by about fifty times and increasing the speed depending upon the image, since watershed transform is a data dependent algorithm. The implementation of the proposed algorithm is compared with other parallel watershed implementations, which use a number of processors and therefore are not cost effective. Further, as the memory requirement is quite small compared to the existing algorithms, the main bottleneck of implementing the algorithm as an ASIC/FPGA is eliminated. It also gives a chance to evaluate the behavior of a data dependent algorithm at the chip level. Towards these goals, a suitable architecture has been proposed to implement the watershed algorithm. Its merits are explained in comparison to the existing software implementations. The architecture is functionally simulated and tested using Verilog HDL and synthesized using Synopsys CAD tools.