We propose a novel quadrilateral based region segmentation method that is favorable for object tracking. Instead of using groups of pixels or regular blocks, it uses groups of connected quadrilaterals to represent regions. The proposed method derives the vertices of each quadrilateral from the edge map using the concept of center of masses. By merging the quadrilaterals, regions can be represented. The proposed method offers better data reduction than pixelwise region representation and better boundary approximation than block-based segmentation methods. Experimental results show that it generates a more reasonable region map, which is more suitable for object tracking, and a smaller number of regions than the seeded region growing, K-means clustering, and constrained gravitational clustering methods.