“If you have built castles in the air, your work need not be lost; that is where they should be. Now put the foundations under them. ” - Henry David Thoreau, Walden Although engineering is a study entrenched firmly in belief of pr- matism, I have always believed its impact need not be limited to pr- matism. Pragmatism is not the boundaries that define engineering, just the (sometimes unforgiving) rules by which we sight our goals. This book studies two major problems of content-based video proce- ing for a media-based technology: Video Object Plane (VOP) Extr- tion and Representation, in support of the MPEG-4 and MPEG-7 video standards, respectively. After reviewing relevant image and video p- cessing techniques, we introduce the concept of Voronoi Ordered Spaces for both VOP extraction and representation to integrate shape infor- tion into low-level optimization algorithms and to derive robust shape descriptors, respectively. We implement a video object segmentation system with a novel surface optimization scheme that integrates Voronoi Ordered Spaces with existing techniques to balance visual information against predictions of models of a priori information. With these VOPs, we have explicit forms of video objects that give users the ability to - dress and manipulate video content. We outline a general methodology of robust data representation and comparison through the concept of complex partitioning mapped onto Directed Acyclic Graphs (DAGs).