In this proposal we present a scalable, self-organizing people tracking system for the ICIP 2014 Show&Tell. We describe the people tracking system and show why it is a good candidate for an interactive live demo.

Image thresholding is one of the most common image processing operations, since almost all image processing schemes need some sort of separation of the pixels into different classes. In order to find the thresholds, almost all methods analyze the histogram of the image. In most cases, the optimal thresholds are found by either minimizing or maximizing an objective function, which depends on the positions of the thresholds. We identify two classes of objective functions for which the optimal thresholds can be found by algorithms with low time complexity. We show, that for example the method proposed by Otsu (1979) and other well known methods have objective functions belonging to these classes. By implementing the algorithms in ANSI C and comparing their execution times, we can make a quantitative statement about their performance.

The introduction of Video Objects (VOs) is one of the innovations of MPEG-4. The alpha-plane of a VO defines its shape at a given instance in time and hence determines the boundary of its texture. In packet-based networks, shape, motion, and texture are subject to loss. While there has been considerable attention paid to the concealment of texture and motion errors, little has been done in the field of shape error concealment. In this paper we propose a post-processing shape error concealment technique that uses the motion compensated boundary information of the previously received alpha-plane. The proposed approach is based on matching received boundary segments in the current frame to the boundary in the previous frame. This matching is achieved by finding a maximally smooth motion vector field. After the current boundary segments are matched to the previous boundary, the missing boundary pieces are reconstructed by motion compensation. Experimental results demonstrating the performance of the proposed motion compensated shape error concealment method, and comparing it with the previously proposed weighted side matching method are presented.

For video communications over wireless ad hoc networks, multiple paths with limited bandwidth are common. It therefore presents new challenges to the video encoding. In this paper, we formulate the problem as a multiple path video summarization problem under bit rate constraints, where video summaries are generated to satisfy each channel's rate constraint, while the combined summary at the receiving end achieves the minimum summarization distortion. The optimal solution (within a convex hull approximation) is found by Lagrangian relaxation and dynamic programming. Simulation results demonstrate the effectiveness of the approach.

The need for video summarization originates primarily from a viewing time constraint. A shorter version of the original video sequence is desirable in a number of applications. Clearly, a shorter version is also necessary in applications where storage, communication bandwidth and/or power are limited. In this paper, our work is based on a MINMAX optimization formulation with viewing time, frame skip and bit rate constraints. New metrics for missing frame and video summary distortions are introduced. Optimal algorithm based on dynamic programming is presented along with experimental results.

In object-based video encoding, the encoding of the video data is decoupled into the encoding of shape, motion, and texture information, which enables certain functionalities, like content-based interactivity and content-based scalability. The fundamental problem, however, of how to jointly encode this separate information to reach the best coding efficiency has not been studied thoroughly. In this paper, we present an operational rate-distortion optimal scheme for the allocation of bits among shape, motion, and texture in object-based video encoding. Our approach is based on Lagrangian relaxation and dynamic programming. We implement our algorithm on the MPEG-4 video verification model, although it is applicable to any object-based video encoding scheme. The performance is accessed utilizing a proposed metric that jointly captures the distortion due to the encoding of the shape and texture. Experimental results demonstrate that the gains of lossy shape encoding depend on the percentage the shape bits occupy out of the total bit budget. This gain may be small or may be realized at very low bit rates for certain typical scenes.

The need for video summarization originates primarily from a viewing time constraint. A shorter version of the original video sequence is desirable in a number of applications. Clearly, a shorter version is also necessary in applications where storage, communication bandwidth, and/or power are limited. The summarization process inevitably introduces distortion. The amount of summarization distortion is related to its "conciseness," or the number of frames available in the summary. If there are m frames in the original sequence and n frames in the summary, we define the summarization rate as m/n, to characterize this "conciseness". We also develop a new summarization distortion metric and formulate the summarization problem as a rate-distortion optimization problem. Optimal algorithms based on dynamic programming are presented and compared experimentally with heuristic algorithms. Practical constraints, like the maximum number of frames that can be skipped, are also considered in the formulation and solution of the problem.

The need for video summarization originates primarily from a viewing time constraint. A shorter version of the original video sequence is desirable in a number of applications. Clearly, a shorter version is also necessary in applications where storage, communication bandwidth and/or power are limited. Our work is based on a temporal rate-distortion optimization formulation for optimal summary generation. New metrics for video summary distortion are introduced. Optimal algorithms based on dynamic programming are presented along with the results from heuristic algorithms that can produce near optimal results in real time.

The need for video summarization originates primarily from a viewing time or a bit budget constraint. A shorter version of the original video sequence is desirable in a number of applications. Clearly, a shorter version is also necessary in applications where storage, communication bandwidth and/or power are limited, which translates into a bit budget constraint. Our work is based on a bit rate-summary distortion optimization formulation. New metrics for video summary distortion are introduced. An optimal algorithm based on Lagrangian relaxation and dynamic programming is presented.

The introduction of video objects (VOs) is one of the innovations of MPEG-4. The /spl alpha/-plane of a VO defines its shape at a given instance in time and hence determines the boundary of its texture. In packet-based networks, shape, motion, and texture are subject to loss. In this paper, we propose a post-processing shape error concealment technique that uses the motion compensated boundary information of the previously received /spl alpha/-plane. The proposed approach is based on matching received boundary segments in the current frame to the boundary in the previous frame. This matching is achieved by finding a maximally smooth motion vector field. After the current boundary segments are matched to the previous boundary, the missing boundary pieces are reconstructed by motion compensation. Experimental results demonstrating the performance of the proposed motion compensated shape error concealment method, and comparisons with our previously proposed spatial Hermite spline method are presented.

The introduction of video objects (VOs) is one of the innovations of MPEG-4. The alpha-plane of a VO defines its shape at a given instance in time and hence determines the boundary of its texture. In packet-based networks, shape, motion, and texture are subject to loss. While there has been considerable attention paid to the concealment of texture and motion errors, little has been done in the field of shape error concealment. In this paper, we propose a post-processing shape error-concealment technique that uses geometric boundary information of the received alpha-plane. Second-order Hermite splines are used to model the received boundary in the neighboring blocks, while third order Hermite splines are used to model the missing boundary. The velocities of these splines are matched at the boundary point closest to the missing block. There exists the possibility of multiple concealing splines per group of lost boundary parts. Therefore, we draw every concealment spline combination that does not self-intersect and keep all possible results until the end. At the end, we select the concealment solution that results in one closed boundary. Experimental results demonstrating the performance of the proposed method and comparisons with prior proposed methods are presented.

The problem of finding the optimal set of quantized coefficients for a frame-based encoded signal is known to be of very high complexity. This paper presents an efficient method of finding the operational rate-distortion (RD) optimal set of coefficients. The major complexity reduction lies in the reformulation of the original RD-tradeoff problem, where a new set of coefficients is used as decision variables. These coefficients are connected to the orthogonalization of the set of selected frame vectors and not to the frame vectors themselves. By organizing all possible solutions as nodes in a solution tree, we use complexity saving techniques to find the optimal solution in an even more efficient way. Using an ordered vector selection process, the complexity can be again significantly reduced and efficient run-length encoding becomes feasible. Contrary to the original problem, the new problem can be solved optimally in a reasonable amount of time.

In this paper we introduce a novel line detection algorithm based on a weighted minimum mean square error (MSE) formulation. This algorithm has been developed to enable an autonomous robot to follow a white line drawn on the floor, but is general in nature and widely applicable to line detection problems. Traditional approaches to line detections consist of two stages, an edge detection stage and a line detection stage using the edge detection result. There are several problems with this approach. First, the initial edge detection stage is sensitive to noise. Second, the second stage does not use all the information available in the image and there fore incorrect decisions made by the first stage cannot be corrected in the second stage. The proposed algorithm achieves its robustness by operating in one step, using all pixels of the image (correctly weighted) and not using any thresholds. The detected line is the solution of a weighted MSE problem. The following three questions are answered in the paper: (I) what mathematical model should be used for the line? (II) how should the weighted MSE problem be set up so that the optimal solution results in the parameters of the line model? And (III), how should the pixels in the image be weighted such that a weighted MSE optimal solution results in a robust line detection? Experimental results demonstrate the performance of the algorithm in noiseless and noisy conditions.

Object-based video coding requires the transmission of the object shape. This shape is sent as a binary /spl alpha/-plane. In lossy packet-based networks, such as the Internet, this information has a nonnegligible probability of not arriving at the receiver, and hence its loss needs to be concealed. In this paper we propose a shape concealment technique utilizing Hermite splines. The algorithm has the following steps: (I) the received boundary is detected and the lost boundary parts are grouped using the packet loss pattern. (II) for each of these lost boundary parts, the received boundary points that border the area of the lost boundary parts are collected. These boundary points are then modelled by a second order Hermite spline. This model is subsequently used to match the velocity along the received boundary with the velocity of the concealing cubic Hermite spline. (Ill) since in most cases there are more than one concealing splines we draw every spline combination that does not result in an intersection and keep all possible results until the end. (IV) if there are more than one possible solutions we select the one that results in one overall closed nonintersecting boundary and fill the interior of the boundary to get the concealed /spl alpha/-plane. Experimental results which demonstrate and compare the performance of the proposed concealment method are given at the end of the paper.

In object-based video, the encoding of the video data is decoupled into the encoding of shape, motion and texture information, which enables certain functionalities like content-based interactivity and scalability. However, the problem of how to jointly encode these separate signals to reach the best coding efficiency has never been solved thoroughly. In this paper, we present an operational rate-distortion optimal bit allocation scheme that provides a solution to this problem. Our approach is based on the Lagrangian relaxation and dynamic programming. Experimental results indicate that the proposed optimal encoding approach has considerable gains over an ad-hoc method without optimization. Furthermore the proposed algorithm is much more efficient than exhaustive search.

In this paper, we consider the rate-distortion optimal encoding of shape information using a skeleton decomposition and the minimum maximum (minmax) distortion criterion. For bit budget constrained video communication applications, whose goal is to achieve as low as possible but almost constant distortion, the minmax criterion is the natural choice. We propose a 4D DAG (directed acyclic graph) shortest path algorithm implemented by dynamic programming to solve the minimum rate problem, and also provide a solution for the dual minimum distortion problem. Experimental results indicate that our algorithm has an outstanding performance compared with existing methods.

MPEG-4 is the first multimedia standard that supports the decoupling of a video object into object shape and object texture information, which consequently brings up the optimal encoding problem for object-based video. In this paper, we present an operational rate-distortion optimal bit allocation scheme between shape and texture for MPEG-4 encoding. Our approach is based on the Lagrange multiplier method, while the adoption of dynamic programming techniques enables its higher efficiency over the exhaustive search algorithm. Our work will not only benefit the further study of joint shape and texture encoding, but also make possible the deeper study of optimal joint source-channel coding of object-based video.

In this paper, we present a new shape-coding approach, which decouples the shape information into two independent signal data sets; the skeleton and the boundary distance from the skeleton. The major benefit of this approach is that it allows for a more flexible tradeoff between approximation error and bit budget. Curves of arbitrary order can be utilized for approximating both the skeleton and distance signals. For a given bit budget for a video frame, we solve the problem of choosing the number and location of the control points for all skeleton and distance signals of all boundaries within a frame, so that the overall distortion is minimized. An operational rate-distortion (ORD) optimal approach using Lagrangian relaxation and a four-dimensional direct acyclic graph (DAG) shortest path algorithm is developed for solving the problem. To reduce the computational complexity from O(N(5)) to O(N(3)), where N is the number of admissible control points for a skeleton, a suboptimal greedy-trellis search algorithm is proposed and compared with the optimal algorithm. In addition, an even more efficient algorithm with computational complexity O(N(2)) that finds an ORD optimal solution using a relaxed distortion criterion is also proposed and compared with the optimal solution. Experimental results demonstrate that our proposed approaches outperform existing ORD optimal approaches, which do not follow the same decomposition of the source data.

This paper presents a method to find the operational rate-distortion optimal solution for an overcomplete signal decomposition. The idea of using overcomplete dictionaries, or frames, is to get a sparse representation of the signal. Traditionally, suboptimal algorithms, such as Matching Pursuit (MP), is used for this purpose. When using frames in a lossy compression scheme, the major issue is to find the best possible rate-distortion (RD) tradeoff. Given the frame and the Variable Length Code (VLC) table embedded in the entropy coder, the solution of the problem of establishing the best RD tradeoff has a very high complexity. The proposed approach reduces this complexity significantly by structuring the solution approach such that the dependent quantizer allocation problem reduces into an independent one. It is important to note that this large reduction in complexity is achieved without sacrificing optimality. The optimal rate-distortion solution depends on the VLC table embedded in the entropy coder. Thus, VLC optimization is part of this work. We show experimentally that the new approach outperforms Rate-Distortion Optimized Matching Pursuit, previously proposed in [1].

The encoding of shape information is a distinguishing feature of MPEG-4. In error prone communication networks, it is important and efficient to conceal shape errors spatially, so as to avoid propagation of errors in the video frames. The proposed system first defines the missing area's four rectangular neighbors. It then detects in the neighbors the lines that intersect the borders and redefines them in a geometric coordinate system. These lines are paired under some optimization objective so that they connect smoothly in the missing area. Each pair is extrapolated and corrected recursively until a close curve is formed. Test results on various sequences under various error rates are presented and compared with other shape concealment methods.

This paper investigates ways to explore the between frame correlation of shape information within the framework of an operationally rate-distortion (ORD) optimized coder. Contours are approximated both by connected second-order spline segments, each defined by three consecutive control points, and by segments of the motion-compensated reference contours. Consecutive control points are then encoded predictively using angle and run temporal contexts or by tracking the reference contour. We utilize a novel criterion for selecting global object motion vectors, which improves the efficiency. The problem is formulated as a Lagrangian minimization and solved using dynamic programming. Furthermore, we employ an iterative technique to remove dependency on a particular variable length code and jointly arrive at the ORD globally optimal solution and an optimized conditional parameter distribution.

This paper investigates the problem of optimal lossy encoding of object contours in the inter mode. Contours are approximated by connected second-order spline segments, each defined by three consecutive control points. Taking into account correlations in the temporal direction, control points are chosen optimally in the rate-distortion sense. Applying motion to contours in the reference frame followed by the temporal context extraction, we predict the next control point location, given the previously encoded one. Based on the chosen differential encoding scheme and an additive MPEG-4 based distortion metric, the problem is formulated as Lagrangian minimization. We utilize an iterative procedure to jointly find the optimal solution and the associated DPCM parameter probability mass functions.

This paper investigates how the between frame correlation of shape information can be exploited within the framework of an operationally rate-distortion (ORD) optimized coder. Contours are approximated either by connected second-order spline segments, each defined by three consecutive control points, or by segments of the motion-compensated reference contours. Consecutive control points are then encoded predictively using angle and run temporal contexts or by tracking the reference contour. We employ a novel criterion for selecting global object motion vectors, which further improves efficiency. The problem is formulated as Lagrangian minimization and solved using Dynamic Programming (DP). Furthermore, we employ an iterative technique to remove dependency on a particular VLC and jointly arrive at the OPD globally optimal solution and an optimized conditional parameter distribution.

This paper investigates how context-based DPCM techniques can be used in conjunction with an operationally rate-distortion (ORD) optimized shape coder. Object contours are approximated by connected second-order spline segments, each defined by three consecutive control points, and, in the case of the inter mode, by segments of the motion-compensated reference contours. In scalable intra mode and non-scalable inter mode shape coding, consecutive control points are encoded predictively, using an angle and run framework, with respect to corresponding contexts in the reference frame and the base layer, respectively. We employ a novel criterion for selecting global object motion vectors in the inter mode, which further improves efficiency.

In this paper, we review a general framework for the optimal bit allocation among dependent quantizers based on the minimum maximum (MINMAX) distortion criterion. The pros and cons of this optimization criterion are discussed and compared to the well-known Lagrange multiplier method for the minimum average (MINAVE) distortion criterion. We argue that, in many applications, the MINMAX criterion is more appropriate than the more popular MINAVE criterion. We discuss the algorithms for solving the optimal bit allocation problem among dependent quantizers for both criteria and highlight the similarities and differences. We point out that any problem which can be solved with the MINAVE criterion can also be solved with the MINMAX criterion, since both approaches are based on the same assumptions. We discuss uniqueness of the MINMAX solution and the way both criteria can be applied simultaneously within the same optimization framework. Furthermore, we show how the discussed MINMAX approach can be directly extended to result in the lexicographically optimal solution. Finally, we apply the discussed MINMAX solution methods to still image compression, intermode frame compression of H.263, and shape coding applications.

This paper describes efficient and optimal encoding and representation of object contours. Contours are approximated by connected second-order spline segments, each defined by three consecutive control points. The placement of the control points is done optimally in the rate-distortion (RD) sense and jointly with their entropy encoding. We utilize a differential scheme for the rate and an additive area-based metric for the distortion to formulate the problem as a Lagrangian minimization. We investigate the sensitivity of the resulting operational RD curve on the variable length codes used and propose an iterative procedure arriving at the entropy representation of the original boundary for any given rate-distortion tradeoff.

We address the problem of the efficient encoding of object boundaries. This problem is becoming increasingly important in applications such as content-based storage and retrieval, studio and television postproduction, and mobile multimedia applications. The MPEG-4 visual standard will allow the transmission of arbitrarily shaped video objects. The techniques developed for shape coding within the MPEG-4 standardization effort are described and compared first. A framework for the representation of shapes using their contours is presented next. Such representations are achieved using curves of various orders, and they are optimal in the rate-distortion sense. Finally, conclusions are drawn.

In this paper, we present fast and efficient methods for the lossy encoding of object boundaries that are given as eight-connect chain codes. We approximate the boundary by a polygon, and consider the problem of finding the polygon which leads to the smallest distortion for a given number of bits. We also address the dual problem of finding the polygon which leads to the smallest bit rate for a given distortion. We consider two different classes of distortion measures. The first class is based on the maximum operator and the second class is based on the summation operator. For the first class, we derive a fast and optimal scheme that is based on a shortest path algorithm for a weighted directed acyclic graph. For the second class we propose a solution approach that is based on the Lagrange multiplier method, which uses the above-mentioned shortest path algorithm. Since the Lagrange multiplier method can only find solutions on the convex hull of the operational rate distortion function, we also propose a tree-pruning-based algorithm that can find all the optimal solutions. Finally, we present results of the proposed schemes using objects from the Miss America sequence.

We propose an optimal quadtree (QT)-based motion estimator for video compression. It is optimal in the sense that for a given bit budget for encoding the displacement vector field (DVF) and the QT segmentation, the scheme finds a DVF and a QT segmentation which minimizes the energy of the resulting displaced frame difference (DFD). We find the optimal QT decomposition and the optimal DVF jointly using the Lagrangian multiplier method and a multilevel dynamic program. We introduce a new, very fast convex search for the optimal Lagrangian multiplier lambda(*), which results in a very fast convergence of the Lagrangian multiplier method. The resulting DVF is spatially inhomogeneous, since large blocks are used in areas with simple motion and small blocks in areas with complex motion. We also propose a novel motion-compensated interpolation scheme which uses the same mathematical tools developed for the QT-based motion estimator. One of the advantages of this scheme is the globally optimal control of the tradeoff between the interpolation error energy and the DVF smoothness. Another advantage is that no interpolation of the DVF is required since we directly estimate the DVF and the QT-segmentation for the frame which needs to be interpolated. We present results with the proposed QT-based motion estimator which show that for the same DFD energy the proposed estimator uses about 25% fewer bits than the commonly used block matching algorithm. We also experimentally compare the interpolated frames using the proposed motion compensated interpolation scheme with the reconstructed original frames.

In this paper we introduce an optimal bit allocation scheme for dependent quantizers for the minimum maximum distortion criterion. First we show how minimizing the bit rate for a given maximum distortion can be achieved in a dependent coding framework using dynamic programming (DP). Then we employ an iterative algorithm to minimize the maximum distortion for a given bit rate, which invokes the DP scheme. We prove that it converges to the optimal solution. Finally we present a comparison between the minimum total distortion criterion and the minimum maximum distortion criterion for the encoding of an H.263 Intra frame. In this comparison we also point out the similarities between the proposed minimum maximum distortion approach and the Lagrangian multiplier based minimum total distortion approach.

A major problem in object oriented video coding is the efficient encoding of the shape information of arbitrarily shaped objects. Efficient shape coding schemes are also needed in encoding the shape information of video object planes (VOP) in the MPEG-4 standard. In this paper, we present an efficient method for the lossy encoding of object shapes which are given as 8-connect chain codes (Meier et al., 1997). We approximate the object shape by a second order B-spline curve and consider the problem of finding the curve with the lowest bit rate for a given distortion. The presented scheme is optimal, efficient and offers complete control over the trade-off between bit-rate and distortion. We present results with the proposed scheme using objects shapes of different sizes.

We address the fundamental problem of optimally splitting a video sequence into two sources of information, the displaced frame difference (DFD) and the displacement vector field (DVF). We first consider the case of a lossless motion-compensated video coder (MCVC), and derive a general dynamic programming (DP) formulation which results in an optimal tradeoff between the DVF and the DFD. We then consider the more important case of a lossy MCVC, and present an algorithm which solves the tradeoff between the rate and the distortion. This algorithm is based on the Lagrange multiplier method and the DP approach introduced for the lossless MCVC. We then present an H.263-based MCVC which uses the proposed optimal bit allocation, and compare its results to H.263. As expected, the proposed coder is superior in the rate-distortion sense. In addition to this, it offers many advantages for a rate control scheme. The presented theory can be applied to build new optimal coders, and to analyze the heuristics employed in existing coders. In fact, whenever one changes an existing coder, the proposed theory can be used to evaluate how the change affects its performance.

We present a theory for the optimal bit allocation among quadtree (QT) segmentation, displacement vector field (DVF), and displaced frame difference (DFD). The theory is applicable to variable block size motion-compensated video coders (VBSMCVC), where the variable block sizes are encoded using the QT structure, the DVF is encoded by first-order differential pulse code modulation (DPCM), the DFD is encoded by a block-based scheme, and an additive distortion measure is employed. We derive an optimal scanning path for a QT that is based on a Hilbert curve. We consider the case of a lossless VBSMCVC first, for which we develop the optimal bit allocation algorithm using dynamic programming (DP). We then consider a lossy VBSMCVC, for which we use Lagrangian relaxation, and show how an iterative scheme, which employs the DP-based solution, can be used to find the optimal solution. We finally present a VBSMCVC, which is based on the proposed theory, which employs a DCT-based DFD encoding scheme. We compare the proposed coder with H.263. The results show that it outperforms H.263 significantly in the rate distortion sense, as well as in the subjective sense.

We address the fundamental problem of optimally splitting a video sequence into two sources of information, the displaced frame difference (DFD) and the displacement vector field (DVF). We first consider the case of a lossless motion compensated video coder (MCVC) and derive a general dynamic programming (DP) formulation which results in an optimal tradeoff between the DVF and the DFD. We then consider the more important case of a lossy MCVC and present an algorithm which solves optimally the bit allocation between the rate and the distortion. This algorithm is based on Lagrangian relaxation and the DP approach introduced for the lossless MCVC. We then present an H.263-based MCVC which uses the proposed optimal bit allocation scheme and compare its results to H.263. As expected, the proposed coder is superior in the rate-distortion sense.

In this paper, we present a fast and optimal method for the lossy encoding of object boundaries which are given as 8-connect chain codes. We approximate the boundary by a polygon and consider the problem of finding the polygon which can be encoded with the smallest number of bits for a given maximum distortion. The presented scheme is an extension of the approaches introduced in [l, 2], in that the admissible polygon vertices belong to a band around the original boundary and a new vertex encoding scheme is proposed.