EXISTING TECHNIQUES OF VISUAL PROCESSING - Video Object Extraction and Representation: Theory and Applications - page 44

problem, but also solves all the optimal subproblems and returns their
relationship to the final optimal solution.
The dynamic programming technique can only be applied only if two
particular qualities of the optimization problem are satisfied: optimal
substructure and overlapping subproblems [Cormen et al., 1990]. The
optimal substructure property requires that “an optimal solution to the
problem contains within it optimal solutions to subproblems [Cormen
et al., 1990] (p. 309).” By solving optimal subproblems, dynamic pro-
gramming can calculate the optimal solution. The overlapping subprob-
lem property assumes that there are finite number of subproblems that
can be produced and their computation can be shared among all the op-
timal subproblem calculations. This reuse of computation in subproblem
dependency and subproblem definition allows the dynamic programming
to be efficient and optimal. However, for optimization problems that
do not have these properties, we must first translate the problem into
dynamic programming form. Although we gain optimality from the dy-
namic programming technique, the translation often affects the quality
of the final solution.

6. COMPRESSED DOMAIN
Although there exists a strong correlation between coding and rep-
resentation, it is important to realize where coding for compression
and content-based information processing converge and diverge. In sec-
tion 5., we noted how the MPEG-1 / 2 syntaxes were related to our query
and extraction efforts. Since the majority of video data will be in the
compressed form, we wish to operate in the compressed domain. How-
ever, we must be wary of those coding efforts (such as MPEG-1 / 2) whose
focus is on coding efficiency.
The compressed domain representation of a video sequence often con-
tains preprocessed information that can aid content-based processing.
However, when working in the compressed domain, we must assume
that we cannot reference the original video and must be wary of mistak-
ing coding artifacts for content. On the encoder side, coding artifacts
may be embedded into the data, especially when the coding effort is
aimed toward coding efficiency and not toward content-based function-
alities. In cases where the compressed domain features are straightfor-
ward representations of the video content such as DC coefficients of the
DCT components macroblocks, analysis upon the compressed domain
can leverage the encoder processing into content-based video processing
[Yeo and Liu, 1995]. Other compressed domain features (macroblock
references) features may not correspond to the ideal content informa-
tion (the projected motion of an object). in MPEG-1 / 2,

For instance,