We propose a novel 3-D human motion and object interaction prediction model that is aware of commonsense knowledge about human–object interaction. We jointly predict human joint motion and human–object interactions. The two prediction results are combined to enforce commonsense knowledge, such as "if the human right hand is predicted to be in contact with an object after 1 second, the distance between the right hand and an object should also be predicted to be small," explicit to the model. Our model uses the raw point cloud representation of the surrounding objects in the environment as input. Using raw point cloud representation allows us to model commonsense knowledge easily and improve accuracy. In particular, it does not require a separate perception system (e.g., object classification, object pose estimation, and so on), as in previous studies, and thus is robust to perception errors. Our model applies a cross-attention mechanism to fuse the environmental point cloud and past human joint poses. The surrounding environment context and past human joint poses are two heterogeneous inputs and cross-attention can be a powerful approach to fuse them. Our model is validated on the KIT Whole-Body Human Motion (WBHM) dataset.

In this paper, we introduce the first published planner to drive a car in dense, urban traffic using Inverse Reinforcement Learning (IRL). Our planner, DriveIRL, generates a diverse set of trajectory proposals and scores them with a learned model. The best trajectory is tracked by our self-driving vehicle's low-level controller. We train our trajectory scoring model on a 500+ hour real-world dataset of expert driving demonstrations in Las Vegas within the maximum entropy IRL framework. DriveIRL's benefits include: a simple design due to only learning the trajectory scoring function, a flexible and relatively interpretable feature engineering approach, and strong real-world performance. We validated DriveIRL on the Las Vegas Strip and demonstrated fully autonomous driving in heavy traffic, including scenarios involving cut-ins, abrupt braking by the lead vehicle, and hotel pickup/dropoff zones. Our dataset, a part of nuPlan, has been released to the public to help further research in this area.

This paper presents a mathematical design of a CEM (Constant Envelope Multiplexing) scheme for three equal power signals to achieve any target CEM power efficiency. The proposed scheme assumes that the chip pulses have one or two sample magnitude values. The design method and the results can be applied to a new satellite navigation system such as KPS (Korea Positioning System.)

Aircraft routing problem is a crucial component for flight automation. Despite recent successes, challenges still remain when the environment is dynamic and uncertain. In this paper, we tackle the following two challenges. First, when the environment is uncertain, it is much safer if the route planner can guarantee a specified level of safety. Second, when the environment is dynamic, the planner needs to adapt to the changes in the environment quickly. To address these challenges, we present three contributions. First, we propose formulating the aircraft routing problem under a dynamic and uncertain environment as a chance constrained stochastic shortest path (CC-SSP) problem. Second, we introduce an anytime algorithm for the CC-SSP problem, which is effective in a dynamic environment with limited planning time. To be more specific, we present two versions of the algorithm and compare their performances. Third, we show that the algorithm can be generalized to solve a larger class of problems called chance constrained partially observable Markov decision process (CC-POMDP).

Humans perceive and describe their surroundings with qualitative statements (e.g., "Alice's hand is in contact with a bottle."), rather than quantitative values (e.g., 6-D poses of Alice's hand and a bottle). Qualitative spatial representation (QSR) is a framework that represents the spatial information of objects in a qualitative manner. Region connection calculus (RCC), qualitative trajectory calculus (QTC), and qualitative distance calculus (QDC) are some popular QSR calculi. With the recent development of computer vision, it is important to compute QSR calculi from the visual inputs (e.g., RGB-D images). In fact, many QSR application domains (e.g., human activity recognition (HAR) in robotics) involve visual inputs. We propose a qualitative spatial representation network (QSRNet) that computes the three QSR calculi (i.e., RCC, QTC, and QDC) from the RGB-D images. QSRNet has the following novel contributions. First, QSRNet models the dependencies among the three QSR calculi. We introduce the dependencies as kinematics for QSR because they are analogous to the kinematics in classical mechanics. Second, QSRNet applies the 3-D point cloud instance segmentation to compute the QSR calculi. The experimental results show that QSRNet improves the accuracy in comparison to the other state-of-the-art techniques.

Human activity recognition is a crucial ingredient in safe and efficient human-robot collaboration. In this paper, we present a new model-based human activity recognition system called logical activity recognition system (LCARS). LCARS requires much less training data compared to learning-based works. Compared to other model-based works, LCARS requires minimal domain-specific modeling effort from users. The minimal modeling is for two reasons: i) we provide a systematic and intuitive way to encode domain knowledge for LCARS and ii) LCARS automatically constructs a probabilistic estimation model from the domain knowledge. Requiring minimal training data and modeling effort allows LCARS to be easily applicable to various scenarios. We verify this through simulations and experiments.

This paper presents an optimal global planner for autonomous tracked vehicles navigating in off-road terrain with uncertain slip, which affects the vehicle as a process noise. This paper incorporates two fields of study: slip estimation and motion planning. For slip estimation, an experimental result from [9] is used to model the effect of the slip on the vehicle in various soil types. For motion planning, a robust incremental sampling based motion planning algorithm (CC-RRT*) is combined with the LQG-MP algorithm. CC-RRT* yields the optimal and probabilistically feasible trajectory by using a chance constrained approach under the RRT* framework. LQG-MP provides the capability of considering the role of compensator in the motion planning phase and bounds the degree of uncertainty to appropriate size. In simulation, the planner successfully finds the optimal and robust solution. In addition, the planner is compared with an RRT* algorithm with dilated obstacles to show that it avoids being overly conservative.

This paper presents a robust motion planning methodology for autonomous tracked vehicles navigating in a rough and unknown environment. Two fields of study are dealt with in this paper: motion planning and slip estimation. For the motion planner, the CC-RRT* algorithm is combined with LQG-MP. The motion planner uses a chance-constrained approach and considers the role of compensator in the planning step to provide a robust yet non-conservative planner. For the slip estimator, a stable yet practical online approach known as IPEM is used. IPEM compares the integrated prediction with the measurement to calculate appropriate parameters. The methodology performs online slip estimation and re-planning iteratively. This guarantees the safe travel of the vehicle even when there is an unexpected terrain change that can be fatal. The simulation result shows that the iterative estimation and re-planning plays a significant role in ensuring the safety of the vehicle.

A novel approach to adapt the macroblock (MB) coding order of chrominance planes is proposed to improve the compression performance of the H.264/AVC intra coder. The proposed algorithm first encodes the luminance plane of an image and then uses the luminance data to determine the MB coding order of the chrominance planes adaptively. The proposed algorithm consists of three steps. First, we estimate the similarities between neighboring chrominance MBs using the luminance gradients. Second, we assign a high priority to a chrominance MB, if it is similar to many neighboring MBs. Finally, we encode the chrominance MBs in the decreasing order of the priorities. Moreover, we develop efficient submodes, representing prediction directions, to exploit the correlations of the MBs along the adaptive scan order. Experimental results show that the proposed algorithm yields significantly better compression performance than H.264/AVC on both YUV 4:4:4 and RGB 4:4:4 images.

We propose a robust stereo matching algorithm for images captured under varying radiometric conditions, such as exposure and lighting variations, based on the cumulative distributions of gradients. The gradient operator extracts local changes in pixel values, which are less sensitive to radiometric variations than the original pixel values. Moreover, the cumulative distribution function (CDF) of gradient vectors reflects the ranks of edge strength levels, and corresponding pixels in stereo images tend to have similar ranks regardless of radio-metric conditions. Therefore, we design the matching cost function based on the dissimilarity of gradient CDF values. However, since multiple pixels in an image may have the same gradient CDF value, we further constrain the correspondence matching by checking the dissimilarity of gradient orientations. Finally, to estimate an accurate disparity at each pixel, we adaptively aggregate matching costs using the color similarity and the geometric proximity of neighboring pixels. Experimental results demonstrate that the proposed algorithm provides more accurate disparities than conventional algorithms, especially under varying lighting conditions.

A graph-based video saliency detection algorithm is proposed in this work. We model eye movements on an image plane as random walks on a graph. To detect the saliency of the first frame in a video sequence, we construct a fully connected graph, in which each node represents an image block. We assign an edge weight to be proportional to the dissimilarity between the incident nodes and inversely proportional to their geometrical distance. We extract the saliency level of each node from the stationary distribution of the random walker on the graph. Next, to detect the saliency of each subsequent frame, we add the criterion that an edge, connecting a slow motion node to a fast motion node, should have a large weight. We then compute the stationary distribution of the random walk with restart (RWR) simulation, in which the saliency of the previous frame is used as the restarting distribution. Experimental results show that the proposed algorithm provides more reliable and accurate saliency detection performance than conventional algorithms.

A novel probabilistic depth-guided multi-view denoising (PDMD) algorithm is proposed in this work. We formulate the multi-view image denoising problem by considering the uncertainties in depth estimates in noisy environments. Specifically, we employ the geometric distributions of nonlocal neighbors, as well as the block similarities, to approximate the probabilities of depth estimates. We then use those probabilities to average all nonlocal neighbors and perform the minimum mean square error (MMSE) denoising. Simulation results show that the proposed PDMD algorithm provides better denoising performance than conventional algorithms.

Abstract—In this paper, we propose a method that infers both accurate depth maps and color-consistent stereo images for radiometrically varying stereo images. In general, stereo matching and performing color consistency between stereo images are a chicken-and-egg problem since it is not a trivial task to simultaneously achieve both goals. Hence, we have developed an iterative framework in which these two processes can boost each other. First, we transform the input color images to log-chromaticity color space, from which a linear relationship can be established during constructing a joint pdf of transformed left and right color images. From this joint pdf, we can estimate a linear function that relates the corresponding pixels in stereo images. Based on this linear property, we present a new stereo matching cost by combining Mutual Information (MI), SIFT descriptor, and segment-based plane-fitting to robustly find correspondence for stereo image pairs which undergo radiometric variations. Meanwhile, we devise a Stereo Color Histogram Equalization (SCHE) method to produce color-consistent stereo image pairs, which conversely boost the disparity map estimation. Experimental results show that our method produces both accurate depth maps and color-consistent stereo images, even for stereo images with severe radiometric differences.

Segmenting a single image into multiple coherent groups remains a challenging task in the field of computer vision. Particularly, spectral segmentation which uses the global information embedded in the spectrum of a given image's affinity matrix is a major trend in image segmentation. This paper focuses on the problem of efficiently learning a full range of pairwise affinities gained by integrating local grouping cues for spectral segmentation. We first construct a sparse multilayer graph whose nodes are both the pixels and the oversegmented regions obtained by an unsupervised segmentation algorithm. By applying the semi-supervised learning strategy to this graph, the intra and interlayer affinities between all pairs of nodes can be estimated without iteration. These pairwise affinities are then applied into the spectral segmentation algorithms. In this paper, two types of spectral segmentation algorithms are introduced: $(K)$-way segmentation and hierarchical segmentation. Our algorithms provide high-quality segmentations which preserve object details by directly incorporating the full-range connections. Moreover, since our full affinity matrix is defined by the inverse of a sparse matrix, its eigendecomposition can be efficiently computed. The experimental results on the BSDS and MSRC image databases demonstrate the superiority of our segmentation algorithms in terms of relevance and accuracy compared with existing popular methods.

We propose a correspondence matching algorithm for multi-view video sequences, which provides reliable performance even when the multiple cameras have significantly different parameters, such as viewing angles and positions. We use an activity vector, which represents the temporal occurrence pattern of moving foreground objects at a pixel position, as an invariant feature for correspondence matching. We first devise a novel similarity measure between activity vectors by considering the joint and individual behavior of the activity vectors. Specifically, we define random variables associated with the activity vectors and measure their similarity using the mutual information between the random variables. Moreover, to find a reliable homography transform between views, we find consistent pixel positions by employing the iterative bidirectional matching. We also refine the matching results of multiple source pixel positions by minimizing a matching cost function based on the Markov random field. Experimental results show that the proposed algorithm provides more accurate and reliable matching performance than the conventional activity-based and feature-based matching algorithms, and therefore can facilitate various applications of visual sensor networks.

We propose a colorization-based prediction algorithm, which reduces the correlation between luminance and chrominance planes, to achieve compact compression of color images. We first develop a priority-based colorization scheme, which adds chrominance values to gray pixels using a set of colored pixels, assuming that neighboring pixels with similar luminance values tend to have similar chrominance values as well. The colorization scheme assigns a high priority to a pixel that has a large number of neighbors with similar luminance values. Then, we employ the colorization scheme to predict the chrominance planes from the luminance plane. Since the priority-based colorization scheme predicts color data accurately even in complicated color regions, the prediction residuals can be efficiently compressed. Simulation results on rich color images show that the proposed algorithm yields better compression performance than H.264/AVC.

A side information generation method using assistant pixels is proposed for distributed video coding (DVC) in this work. To generate higher quality side information frames and improve the rate-distortion (R-D) performance of a DVC system, we propose transmitting assistant pixels, which help to improve the motion estimation accuracy of the decoder at the cost of an overhead bit-rate. Also, we develop a mode decision scheme, which determines the interpolation mode for each block by combining forward and backward motion vectors. Simulation results demonstrate that the proposed algorithm provides better R-D performance than the state-of-the-art DVC algorithm.

This paper proposes a new HDR imaging method in the gradient domain based on the fusion of two images with different exposure. We first formulate an energy function for the binary labeling of each pixel based on the brightness and contrast measure of each image, which gives a binary map that determines whether the under-exposed image is better than the overly exposed one or not. Then a target gradient field is generated by combining the gradient fields of two images according to the binary map. Since the gradient field so combined is generally not integrable, we modify it via Poisson solver. This gradient field is considered that of HDR image and directly compressed to the display scale (in the gradient domain). Experiments show that the gradient domain fusion provides better results than the image domain methods, when fusing two differently exposed images.

Under the popular Bayesian approach, a stereo problem can be formulated by defining likelihood and prior. Likelihoods are often associated with unary terms and priors are defined by pair-wise or higher order cliques in Markov random field (MRF). In this paper, we propose to use high order likelihood model in stereo. Numerous conventional patch based matching methods such as normalized cross correlation, Laplacian of Gaussian, or census filters are designed under the naive assumption that all the pixels of a patch have the same disparities. However, patch-wise cost can be formulated as higher order cliques for MRF so that the matching cost is a function of image patch's disparities. A patch obtained from the projected image by a disparity map should provide a better match without the blurring effect around disparity discontinuities. Among patch-wise high order matching costs, the census filter approach can be easily reduced to pair-wise cliques. The experimental results on census filter-based high order likelihood demonstrate the advantages of high order likelihood over independent identically distributed unary model.

A majority of the existing stereo matching algorithms assume that the corresponding color values are similar to each other. However, it is not so in practice as image color values are often affected by various radiometric factors such as illumination direction, illuminant color, and imaging device changes. For this reason, the raw color recorded by a camera should not be relied on completely, and the assumption of color consistency does not hold good between stereo images in real scenes. Therefore, the performance of most conventional stereo matching algorithms can be severely degraded under the radiometric variations. In this paper, we present a new stereo matching measure that is insensitive to radiometric variations between left and right images. Unlike most stereo matching measures, we use the color formation model explicitly in our framework and propose a new measure, called the Adaptive Normalized Cross-Correlation (ANCC), for a robust and accurate correspondence measure. The advantage of our method is that it is robust to lighting geometry, illuminant color, and camera parameter changes between left and right images, and does not suffer from the fattening effect unlike conventional Normalized Cross-Correlation (NCC). Experimental results show that our method outperforms other state-of-the-art stereo methods under severely different radiometric conditions between stereo images.

This paper studies the problem of learning a full range of pairwise affinities gained by integrating local grouping cues for spectral segmentation. The overall quality of the spectral segmentation depends mainly on the pairwise pixel affinities. By employing a semi-supervised learning technique, optimal affinities are learnt from the test image without iteration. We first construct a multi-layer graph with pixels and regions, generated by the mean shift algorithm, as nodes. By applying the semi-supervised learning strategy to this graph, we can estimate the intra- and inter-layer affinities between all pairs of nodes together. These pair-wise affinities are then used to simultaneously cluster all pixel and region nodes into visually coherent groups across all layers in a single multi-layer framework of Normalized Cuts. Our algorithm provides high-quality segmentations with object details by directly incorporating the full range connections in the spectral framework. Since the full affinity matrix is defined by the inverse of a sparse matrix, its eigen-decomposition is efficiently computed. The experimental results on Berkeley and MSRC image databases demonstrate the relevance and accuracy of our algorithm as compared to existing popular methods.

In this paper, we deal with a generative model for multilabel, interactive segmentation. To estimate the pixel likelihoods for each label, we propose a new higher-order formulation additionally imposing the soft label consistency constraint whereby the pixels in the regions, generated by unsupervised image segmentation algorithms, tend to have the same label. In contrast with previous works which focus on the parametric model of the higher-order cliques for adding this soft constraint, we address a nonparametric learning technique to recursively estimate the region likelihoods as higher-order cues from the resulting likelihoods of pixels included in the regions. Therefore the main idea of our algorithm is to design two quadratic cost functions of pixel and region likelihoods, that are supplementary to each other, in a proposed multi-layer graph and to estimate them simultaneously by a simple optimization technique. In this manner, we consider long-range connections between the regions that facilitate propagation of local grouping cues across larger image areas. The experiments on challenging data sets show that integration of higher-order cues quantitatively and qualitatively improves the segmentation results with detailed boundaries and reduces sensitivity with respect to seed quantity and placement.

We present a new energy model for optical flow estimation on discrete MRF framework. The proposed model yields discrete analog to the prevailing model with diffusion tensor-based regularizer, which has been optimized by variational approach. Inspired from the fact that the regularization process works as a convolution kernel filtering, we formulate the difference between original flow and filtered flow as a smoothness prior. Then the discrete framework enables us to employ a robust penalizer less concerning convexity and differentiability of the energy function. In addition, we provide a new kernel design based on the bilateral filter, adaptively controlling intensity variance according to the local statistics. The proposed kernel simultaneously addresses over-segmentation and over-smoothing problems, which is hard to achieve by tuning parameters. Involving a complex graph structure with large label sets, this work also presents a strategy to efficiently reduce memory requirement and computational time to a tolerable state. Experimental result shows the proposed method yields plausible results on the various data sets including large displacement and textured region.

An algorithm for compensating the effects of backlight in images and videos is proposed in this work. We first determine the region of interest (ROI) to compensate mainly using a saliency map, which is based on darkness, skin color, color and texture prominency features. We then compute the compensating offset value for each pixel. Initial offset values are derived to improve the brightness and the contrast of the ROI, and also to provide temporally consistent output frames in case of the video compensation. Finally, we obtain the final offset values by minimizing an energy function, consisting of a data term and a smoothness term. Simulation results show that the proposed algorithm improves the picture qualities of backlit images and videos efficiently.

This paper deals with feature matching and segmentation of common objects in a pair of images, simultaneously. For the feature matching problem, the matching likelihoods of all feature correspondences are obtained by combining their discriminative power with the spatial coherence constraint that favors their spatial aggregation via object segmentation. At the same time, for the object segmentation problem, our algorithm estimates the object likelihood that each subregion is a commonly existing part in two images by the affinity propagation of the resulted matching likelihoods. Since these two problems are related to each other, our main idea to solve them is to integrate all the priors about them into a unified framework, that consists of several correlated quadratic cost functions. Eventually, all matching and object likelihoods are estimated simultaneously as a solution of linear system of equations. Based on these likelihoods, we finally recover the optimal feature matches and the common object parts by imposing simple sequential mapping and thresholding techniques, respectively. The experiments demonstrate the superiority of our algorithm compared with the conventional methods.

An algorithm to generate a panorama from multi-view images, which contain foreground objects with varying depths, is proposed in this work. The proposed algorithm constructs a foreground panorama and a background panorama separately, and then merges them into a complete panorama. First, the foreground panorama is obtained by finding the translational displacements of objects between source images. Second, the background panorama is initialized using warped source images and then optimized to preserve spatial consistency and satisfy visual constraints. Then, the background panorama is extended by inserting seams and merged with the foreground panorama. Experimental results demonstrate that the proposed algorithm provides visually satisfying panoramas with all meaningful foreground objects, but without severe artifacts in the backgrounds.

The coding gain that can be achieved by improving the coding order of B frames in the H.264/AVC standard is investigated in this work. We first represent the coding order of B frames and their reference frames with a binary tree. We then formulate a recursive equation to find out the binary tree that provides a suboptimal, but very efficient, coding order. The recursive equation is efficiently solved using a dynamic programming method. Furthermore, we extend the coding order improvement technique to the case of multiview video sequences, in which the quadtree representation is used instead of the binary tree representation. Simulation results demonstrate that the proposed algorithm provides significantly better R-D performance than conventional prediction structures.

This paper proposes a new rolled fingerprint construction approach incorporating a state-of-the-art nonrigid image registration method based upon a Markov random field (MRF) energy model. The proposed method finds dense correspondences between images from a rolled fingerprint sequence and warps the entire fingerprint area to synthesize a rolled fingerprint. This method can generate conceptually more accurate rolled fingerprints by preserving the geometric properties of the finger surface as opposed to ink-based rolled impressions and other existing rolled fingerprint construction methods. To verify the accuracy of the proposed method, various comparative experiments were designed to reveal differences among the rolled construction methods. The results show that the proposed method is significantly superior in various aspects compared to previous approaches.

Colorization problem is to find the colors of all pixels X = {xn}n=1,...,|X |, given a grayscale image I with scribbles S with the desired colors. We work in the YUV color space where Y = {yn}n=1,...,|X | is the monochromatic luminance channel, which we will refer to simply as intensity, while U = {un}n=1,...,|X | and V = {vn}n=1,...,|X | are the chrominance channels, encoding the color. Our goal is to complete both the U and V channels, given Y = I. We deal with the only U channel in this paper, since the V channel can be treated in the same manner. In this paper, we propose a new multi-layer graph model and an energy formulation that can incorporate higher-order cues for reliable colorization of natural images. In contrast to most existing energy functions [3] with unary and pairwise constraints, we address the problem of imposing a high-order constraint whereby pixels constituting each region tend to have similar colors to the representative color of the region they belong to. The representative colors of the regions that are generated by unsupervised image segmentation algorithms, act as higher-order cues. Unlike previous parametric models [2], they are automatically obtained by a nonparametric learning technique that estimates them from the resulting pixel colors in a recursive fashion. We formulate this problem in terms of two quadratic energy functions of pixel and region colors, that are supplementary to each other, in our proposed multi-layer graph model and estimate them by a simple optimization technique that minimizes both functions simultaneously. Our proposed algorithm works as follows. We first design an undirected graph G = (Q,E) where the nodes Q = {X ,R} consist of two types: pixels X and regions R, generated by an unsupervised segmentation algorithm such as Mean Shift [1], and the edges E are the links between two nodes as shown in Fig. 1(a). Each pixel xn ∈ X initially has an intensity yn ∈ Y . For each region rk ∈ R, we can generate its properties ȳk as the mean intensity of the inner pixels xn ∈ rk: ȳk = 1 |rk| ∑xn∈rk yn. We then formulate both quadratic energy functions JX and JR for estimating the pixel colors U = {un}n=1,...,|X | and the region colors Ū = {ūk}k=1,...,|R|, respectively, as follows.

Radiometric variations between input images can seriously degrade the performance of stereo matching algorithms. In this situation, mutual information is a very popular and powerful measure which can find any global relationship of intensities between two input images taken from unknown sources. The mutual information-based method, however, is still ambiguous or erroneous as regards local radiometric variations, since it only accounts for global variation between images, and does not contain spatial information properly. In this paper, we present a new method based on mutual information combined with SIFT descriptor to find correspondence for images which undergo local as well as global radiometric variations. We transform the input color images to log-chromaticity color space from which a linear relationship can be established. To incorporate spatial information in mutual information, we utilize the SIFT descriptor which includes near pixel gradient histogram to construct a joint probability in log-chromaticity color space. By combining the mutual information as an appearance measure and the SIFT descriptor as a geometric measure, we devise a robust and accurate stereo system. Experimental results show that our method is superior to the state-of-the art algorithms including conventional mutual information-based methods and window correlation methods under various radiometric changes.

In this paper, we propose a new method that infers accurate depth maps and color-consistent images between radiometrically varying stereo images, simultaneously. In general, stereo matching and performing color consistency between stereo images are a chicken-and-egg problem. Color consistency enhances the performance of stereo matching, while accurate correspondences from stereo disparities improve color consistency between stereo images. We devise a new iterative framework in which these two processes can boost each other. For robust stereo matching, we utilize the mutual information-based method combined with the SIFT descriptor from which we can estimate the joint pdf in log-chromaticity color space. From this joint pdf, we can estimate a linear relationship between the corresponding pixels in stereo images. Using this linear relationship and the estimated depth maps, we devise a stereo color histogram equalization method to make color-consistent stereo images which conversely boost the disparity map estimation. Experimental results show that our method produces both accurate depth maps and color-consistent stereo images even for stereo images with severe radiometric differences.

An efficient colorization scheme for images and videos based on prioritized source propagation is proposed in this work. A user first scribbles colors on a set of source pixels in an image or the first frame of a movie. The proposed algorithm then propagates those colors to the other non-source pixels and the subsequent frames. Specifically, the proposed algorithm identifies the non-source pixel with the highest priority, which can be most reliably colorized. Then, its color is interpolated from the neighboring pixels. This is repeated until the whole image or movie is colorized. Simulation results demonstrate that the proposed algorithm yields more reliable colorization performance than the conventional algorithms.

In this paper, we consider the colorization problem of grayscale images in which some color scribbles are initially given. Our proposed method is based on the weighted color blending of the scribbles. Unlike previous works which utilize the shortest distance as the blending weights, we employ a new intrinsic distance measure based on the random walks with restart (RWR), known as a very successful technique for defining the relevance between two nodes in a graph. In our work, we devise new modified data-driven RWR framework that can incorporate locally adaptive and data-driven restarting probabilities. In this new framework, the restarting probability of each pixel becomes dependent on its edgeness, generated by the Canny detector. Since this data-driven RWR enforces color consistency in the areas bounded by the edges, it produces more reliable edge-preserving colorization results that are less sensitive to the size and position of each scribble. Moreover, if the additional information about the scribbles which indicate the foreground object is available, our method can be readily applied to the object segmentation and matting. Experiments on several synthetic, cartoon and natural images demonstrate that our method achieves much high quality colorization results compared with the state-of-the-art methods.

A novel concept of channel division to improve the performance of distributed video coding is proposed in this work. At the decoder, the proposed algorithm partitions each side information frame into multiple regions with different expected distortions. It is shown that the partitioning is equivalent to the division of the virtual noisy channel from the encoder to the decoder into multiple channels. Then, the proposed algorithm analyzes the noise characteristics of those multiple channels, and allocates a limited bit budget to those channels adaptively to improve the rate-distortion performance. Simulation results demonstrate that the proposed algorithm provides up to 5 dB better performance than the conventional DVC algorithms, as well as reduces the decoding complexity significantly.

In this paper, we propose a fully automatic method to segment bone compartments in magnetic resonance (MR) images of knee joints gathered from a public database for research on knee osteoarthritis (OA), the osteoarthritis initiative (OAI). Considering the fixed scanning parameters which include position and flexion of the knee joint, the proposed method efficiently utilizes both shape and intensity priors obtained from pre-segmented data, and iteratively applies branch-and-mincut to a local subset of configurations of shape templates. More specifically, at each iteration, the optimal among a subset of the whole range in translation, rotation, and scale parameters are decomposed and separately computed, and motion is greedily selected by the lowest energy. Experimental results demonstrate the increased accuracy and efficiency compared to when only shape priors are applied and when branch-and-mincut is applied to the whole range of parameters at once, respectively.

This paper proposes a stereo matching algorithm based on hierarchical belief propagation and occlusion handling. We define a new order for message passing in belief propagation instead of the scanline approach. The primary assumption is that a pixel with a well-defined minimum in its likelihood field is more likely to contain a correct disparity, when compared to a pixel having an ill-defined minimum with several local minima. The order for message passing is determined by the variance of likelihood field at each pixel. The variances evaluate the ambiguity of likelihood fields, and the messages are hierarchically updated along the gradient of ambiguity. The experimental results show that the proposed method estimates the disparities correctly in the hard regions such as large occlusions and textureless regions. The proposed algorithm is currently tied with the best performing algorithm on the Middlebury stereo site.

We propose a novel video codec that can distribute computational complexity between the encoder and the decoder in a flexible manner. Since motion estimation is the most computationally intensive part in video coding, it is important to share the motion estimation task. In the proposed algorithm, the decoder estimates motion vectors by performing a partial three step search. The estimated motion vectors are sent back to the encoder via a feedback channel. The encoder then refines the received motion vectors. In this work, four operation modes corresponding to the encoder to decoder complexity ratios are presented. Experimental results demonstrate that the proposed algorithm allocates the complexity between the encoder and the decoder effectively, while providing promising compression performance.

We propose two temporal feature modulation algorithms that extract a feature from each video frame and modulate the features for a series of frames to embed a watermark codeword. In the first algorithm, the existence of a frame is used as the frame feature, and a watermark codeword is embedded into the original video by skipping selected frames. In the second algorithm, the centers of gravity of blocks in a frame are used as the frame feature. By modifying the centers of gravity, we embed 1-bit information into the frame. Simulation results demonstrate that the proposed algorithms are robust against compression and temporal attacks.

A compact representation scheme is presented for 3-D point data. To describe underlying surface from raw point samples, we dyadically divide a 3-D domain enclosing whole points. Then, local points in each cube are approximated by a plane patch, yielding a multiscale representation of 3-D surface. To reduce the redundancy between different scale models, the geometry innovation is evaluated between different scale planes, which reveals the Euclidian distance between planes. Finally, the geometry innovation coefficients are compressed by a zerotree-based encoder. Based on the multiscale plane representation of 3-D geometry and the efficient plane decomposition method, the proposed scheme provides a desirable framework for 3-D point geometry processing.

This paper presents an efficient feature-based nonrigid registration method for multiphase liver CT volumes. While radiologists routinely examine multiphase liver CT to detect hepatic diseases, they usually search corresponding points between 3D CT volumes by visual inspections using 2D slice images. As the liver is a deformable organ, there exist complex nonrigid transformations between liver CT volumes obtained at difference time points (phases). We introduce a fully automatic registration application for multiphase liver CT volumes. For two given liver CT volumes, we extract 3D features with their descriptors, and estimate correspondences by finding nearest neighbor in descriptor space. An energy function is constructed using the correspondence information and the smoothness measure of free-form deformation model based on B-splines. We integrate an approximated smoothness energy function and a robust correspondence energy estimator controlled by the confidence radius of the matching distance in this energy model. The energy function is optimized by sequentially reducing the confidence radius, and outlier correspondences are discarded systematically during convergence. We propose a highly efficient optimization procedure using the preconditioned nonlinear conjugate gradient method. In the experiments, we will provide quantitative and qualitative results on synthetic and clinical data sets. 1

An efficient registration algorithm working on non-rigid 3D objects is presented. We formulate the registration as a discrete labeling problem on MRFs model whose energy can be minimized by optimization techniques in the literature. Due to the huge search range in three-dimensional space, previous approaches produces a vast amount of labels for a node in the MRFs graph. To reduce the number of labels, we decompose a node into three nodes so that the labels in each node represent just one-dimensional displacement. This procedure introduces a factor node with a clique potential of size three, defining ternary interaction between the decomposed nodes. We convert the factor node into pairwise interactions and adopt the tree-reweighted message passing technique, which guarantees the convergence of lower bound of the energy function. In experiments we use clinical and synthetically deformed 3D medical images. Result shows the proposed method enhances computational efficiency without loss of accuracy. 1

Color information can be used as a basic and crucial cue for finding correspondence in a stereo matching algorithm. In a real scene, however, image colors are affected by various geometric and radiometric factors. For this reason, the raw color recorded by a camera is not a reliable cue, and the color consistency assumption is no longer valid between stereo images in real scenes. Hence the performance of most conventional stereo matching algorithms can be severely degraded under the radiometric variations. In this paper, we present a new stereo matching algorithm that is invariant to various radiometric variations between left and right images. Unlike most stereo algorithms, we explicitly employ the color formation model in our framework and propose a new measure called Adaptive Normalized Cross Correlation (ANCC) for a robust and accurate correspondence measure. ANCC is invariant to lighting geometry, illuminant color and camera parameter changes between left and right images, and does not suffer from fattening effects unlike conventional Normalized Cross Correlation (NCC). Experimental results show that our algorithm outperforms other stereo algorithms under severely different radiometric conditions between stereo images.

An inpainting algorithm for multi-view video sequences is proposed in this work. First, we set a mask region in a view with manual interactions, and find the corresponding masks in the other views using the mask cloning method. Then, we overlay grid points on the mask region in the target view frame. For each grid rectangle, we find the matching patch in the source view frame. Finally, we transform and paste the patches to the target frame. Simulation results illustrate that the proposed algorithm removes objects in the multi-view sequences effectively by exploiting inter-view redundancies.

In this paper, we propose adaptive and flexible quantization and compression algorithms for 3-D point data using vector quantization (VQ) and rate-distortion (R-D) optimization. The point data are composed of the position and the radius of sphere based on QSplat representation. The positions of child spheres are first transformed to the local coordinate system, which is determined by the parent-children relationship. The local coordinate transform makes the positions more compactly distributed in 3-D space, facilitating an effective application of VQ. We also develop a constrained encoding method for the radius data, which can provide a hole-free surface rendering at the decoder side. Furthermore, R-D optimized compression algorithm is proposed in order to allocate an optimal bitrate to each sphere. Experimental results show that the proposed algorithm can effectively compress the original 3-D point geometry at various bitrates.

In this paper, we propose a new method to integrate multiview normal fields using level sets. In contrast with conventional normal integration algorithms used in shape from shading and photometric stereo that reconstruct a 2.5D surface using a single-view normal field, our algorithm can combine multiview normal fields simultaneously and recover the full 3D shape of a target object. We formulate this multiview normal integration problem by an energy minimization framework and find an optimal solution in a least square sense using a variational technique. A level set method is applied to solve the resultant geometric PDE that minimizes the proposed error functional. It is shown that the resultant flow is composed of the well known mean curvature and flux maximizing flows. In particular, we apply the proposed algorithm to the problem of 3D shape modelling in a multiview photometric stereo setting. Experimental results for various synthetic data show the validity of our approach.

In this paper, we propose a new algorithm that solves both the stereo matching and the image denoising problem simultaneously for a pair of noisy stereo images. Most stereo algorithms employ L1 or L2 intensity error-based data costs in the MAP-MRF framework by assuming the naive intensity-constancy. These data costs make typical stereo algorithms suffer from the effect of noise severely. In this study, a new robust stereo algorithm to noise is presented that performs the stereo matching and the image denoising simultaneously. In our approach, we redefine the data cost by two terms. The first term is the restored intensity difference, instead of the observed intensity difference. The second term is the non-local pixel distribution dissimilarity around the matched pixels. We adopted the NL-means (Non Local-means) algorithm for restoring the intensity value as a function of disparity. And a pixel distribution dissimilarity is calculated by using PMHD (Perceptually Modified Hausdorff Distance). The restored intensity values in each image are determined by inferring optimal disparity map at the same time. Experimental results show that the proposed algorithm is more robust and accurate than other conventional algorithms in both stereo matching and denoising.

This paper presents a robust warping method for minutiae based fingerprint matching approaches. In this method, a deformable fingerprint surface is described using a triangular mesh model. For given two extracted minutiae sets and their correspondences, the proposed method constructs an energy function using a robust correspondence energy estimator and smoothness measuring of the mesh model. We obtain a convergent deformation pattern using an efficient gradient based energy optimization method. This energy optimization approach deals successfully with deformation errors caused by outliers, which are more difficult problems for the thin-plate spline (TPS) model. The proposed method is fast and the run-time performance is comparable with the method based on the TPS model. In the experiments, we provide a visual inspection of warping results on given correspondences and quantitative results using database.

An algorithm to construct the optimal prediction structure in multiview video coding (MVC) is proposed in this work. We employ the graph theory as a framework. By considering each frame as a vertex and the motion compensation or disparity compensation as an edge, we represent a prediction structure as a spanning tree. Then, we obtain the optimal structure by finding the minimum spanning tree using the Prim's algorithm. Simulation results demonstrate that the proposed algorithm provides about 0.2-0.4 dB better PSNR performance than the conventional prediction structure, and about 1.5 dB better performance than the simulcast.

We present a multiple description coding (MDC) scheme for 3D plane-based surfaces. First, planes are split into two disjoint subsets, called descriptions, each of which provides an equal contribution in 3D surface reconstruction. To optimize the quality of the decoded surface, planes in each description are adaptively compressed according to the channel error condition. Then, the two compressed bitstreams are transmitted over distinct channels to the decoder. At the decoder, if both channels are available, the two bitstreams are decoded and merged together to reconstruct a high quality surface. If only one channel is available, we employ a hole filling method to fill visual holes and reconstruct a smooth 3D surface. Therefore, the proposed algorithm provides an acceptable 3D surface, even when one channel is totally lost.

Invariant image features can be used to carry watermarks so as to improve the robustness of the watermarks against geometric transformations. However, most previous watermarking algorithms using invariant features are still sensitive to cropping attacks and combinations of rotation, scaling, and translation (RST) attacks. To improve the resilience against these attacks, we propose a multi-bit image watermarking algorithm using local Zernike moments (LZMs). The magnitude of LZMs are dither-modulated to embed watermark bits. To achieve scale invariance, we restore the original sampling rate using invariant centroid and geometric moments. Simulation results demonstrate that the proposed watermarking algorithm is robust against various geometric attacks as well as signal processing attacks.

For efficient image retrieval, most existing methods that adopt a tree-structured hierarchy exploit a subtree pruning scheme, based on the triangle inequality of a distance metric, during the tree traversal. In this paper, we propose a refined pruning scheme for the tree-structured hierarchy by introducing a novel notion of the node distance to subcluster (NDS) and validate it in both theoretical and experimental aspects. Experimental results demonstrate that the proposed method outperforms the existing ones by 10%-25% in terms of retrieval efficiency at the negligible increase of storage for a retrieval system

A novel image compression algorithm based on generalized principal component analysis (GPCA) is proposed in this work. Each image block is first classified into a subspace and is represented with a linear combination of the basis vectors for the subspace. Therefore, the encoded information consists of subspace indices, basis vectors and transform coefficients. We adopt a vector quantization scheme and a predictive partial matching scheme to encode subspace indices and basis vectors, respectively. We also propose a rate-distortion optimized quantizer to encode transform coefficients efficiently. Simulation results demonstrate that the proposed algorithm provides better compression performance than JPEG, especially at low bitrates.

A progressive compression and transmission algorithm for Point-Texture 3-D images is proposed in this work. The proposed algorithm represents a Point Texture image hierarchically using an octree. The geometry information in octree nodes is encoded by the predictive partial matching (PPM) method, while the color information is encoded using the discrete cosine transform (DCT). The encoder achieves the progressive transmission of the 3-D image by transmitting the octree nodes in a top-down manner. We develop a transmission scheme, based on the rate-distortion (R-D) optimization in order to maximize the image quality subject to a given bit budget. Extensive simulation results demonstrate that the proposed algorithm is an efficient method for progressive transmission of 3-D data.

A video fingerprinting algorithm based on frame skipping is proposed in this work. At the encoder side, we skip video frames according to a pattern, specified by a fingerprint. The skipping pattern is designed such that the degradation of video quality is negligible. At the decoder side, the fingerprinted sequence is compared with the original sequence and the skipping pattern is reconstructed. Then, the watermark codeword is decoded from the skipping pattern. Since the selection of skipped frames is a combinatorial problem, the proposed algorithm can provide a large capacity for embedded information. Also, the proposed algorithm is inherently robust against spatial attacks, such as geometrical attacks and spatial filtering attacks. To improve the robustness against temporal attacks, such as frame rate reduction, we introduce the notion of error correction coding into the watermarking embedding. Experimental results show that the proposed algorithm is very robust against various attacks, while satisfying the transparency of embedded watermarks.

In this paper, we present a novel geometry compression scheme for compactly representing 3-D sampled data. The proposed framework is based on the octree structured multiscale geometry representation, where local surface is expressed by multiscale plane descriptions. To reduce planar redundancy between different scale plane approximations in the multiscale pyramid, the multiscale plane pyramid is decomposed and the resulting refinement pyramid is encoded using the zerotree based coding method. The decomposition captures the geometry innovation to refine coarse geometry. Moreover, the zerotree based coding method offers the ordered bitstream according to the contribution for reconstructing the geometry innovation. Therefore, we demonstrate that the proposed algorithm compactly represents the 3-D point samples yielding progressive refinement of the surface geometry.

We propose an algorithm that represents three-dimensional dynamic objects with a semi-regular mesh sequence and compresses the sequence using the spatiotemporal wavelet transform. Given an irregular mesh sequence, we construct a semi-regular mesh structure for the first frame and then map it to subsequent frames based on the hierarchical motion estimation. The regular structure of the resulting mesh sequence facilitates the application of advanced coding schemes and other signal processing techniques. To encode the mesh sequence compactly, we develop an embedded coding scheme, which supports signal-to-noise ratio and temporal scalability modes. Simulation results demonstrate that the proposed algorithm provides significantly better compression performance than the static mesh coder, which encodes each frame independently.

An error resilient three-dimensional (3-D) mesh coding system is proposed in this paper. The encoder uses a shape adaptive data partitioning scheme to alleviate the effect of error propagation. An input mesh surface is coarsely divided into smooth and detailed regions, and each region is further divided into partitions of similar sizes. Then, those partitions are progressively compressed and their joint boundaries are compressed using the boundary edge collapse rule. At the decoder, the boundary edge collapse rule facilitates the seamless assembly of the partitions. When no data is available for a partition due to transmission errors, we employ a concealment scheme based on the projection onto convex sets (POCS) theory. Simulation results demonstrate that the proposed algorithm reconstructs 3-D mesh surfaces faithfully even in severe error prone environments

A method for solving dense stereo matching problem is presented in this paper. First, a new generalized ground control points (GGCPs) scheme is introduced, where one or more disparity candidates for the true disparity of each pixel are assigned by local matching using the oriented spatial filters. By allowing "all" pixels to have multiple candidates for their true disparities, GGCPs not only guarantee to provide a sufficient number of starting pixels needed for guiding the subsequent matching process, but also remarkably reduce the risk of false match, improving the previous GCP-based approaches where the number of the selected control points tends to be inversely proportional to the reliability. Second, by employing a two-pass dynamic programming technique that performs optimization both along and across the scanlines, we solve the typical inter-scanline inconsistency problem. Moreover, combined with the GGCPs, the stability and efficiency of the optimization are improved significantly. Experimental results for the standard data sets show that the proposed algorithm achieves comparable results to the state-of-the-arts with much less computational cost.

A new compound image compression algorithm is proposed, based on shape primitive extraction and coding (SPEC). The SPEC first segments a compound image into text/graphics pixels and pictorial pixels, by extracting the shape primitives of text/graphics. Then all the shape primitives are losslessly compressed with a combined shape-based and palette-based coding algorithm. The remaining pictorial pixels are coded with JPEG2000. Experimental results show that the SPEC has very low complexity and provides visually lossless quality, while yielding competitive compression ratios.

In virtual colonography, precise segmentation is essential for accurate diagnosis. For the segmentation of colon wall, we propose a novel multi-phase deformable model using a level set method. By defining an asymmetric energy functional, the proposed model can simultaneously segment regions with different characteristics. Compared with the conventional multi-phase models, it shows better convergence without ambiguity. Experimental results with real CT images demonstrate that the proposed algorithm outperforms other methods.

In this paper, we propose a novel line feature-based face recognition algorithm. A face is represented by the Face-ARG model, where all the geometric quantities and the structural information are encoded in an Attributed Relational Graph (ARG) structure, then the partial ARG matching is done for matching Face-ARG's. Experimental results demonstrate that the proposed algorithm is quite robust to various facial expression changes, varying illumination conditions and occlusion, even when a single sample per person is given.

A unified approach to rate-distortion (R-D) optimized compression and view-dependent transmission of three-dimensional (3-D) normal meshes is investigated in this work. A normal mesh is partitioned into several segments, which are then encoded independently. The bitstream of each segment is truncated optimally using a geometry distortion model based on the subdivision hierarchy. It is shown that the proposed compression algorithm yields a higher coding gain than the conventional algorithm. Moreover, to facilitate interactive transmission of 3-D data according to a client's viewing position, the server can allocate an adaptive bitrate to each segment based on its visibility priority. Simulation results demonstrate that the view-dependent transmission technique can reduce the bandwidth requirement considerably, while maintaining a good visual quality.

We propose a lossless compression algorithm for three-dimensional point data in graphics applications. In typical point representation, each point is treated as a sphere and its geometrical and normal data are stored in the hierarchical structure of bounding spheres. The proposed algorithm sorts child spheres according to their positions to achieve a higher coding gain for geometrical data. Also, the proposed algorithm compactly encodes normal data by exploiting high correlation between parent and child normals. Simulation results show that the proposed algorithm saves up to 60% of storage space.

In this paper, to represent 2-D shape as a relational structure, i.e. graph, we propose a new shape decomposition scheme composed of two stages: first, a given shape is decomposed into meaningful parts by using the constrained morphological decomposition (CMD) in a recursive manner. More specifically, the CMD adopts the use of the opening operation with the ball-shaped structuring element and the weighted convexity to select the optimal decomposition. Second, the iterative merging stage provides a compact graph-based representation based on the weighted convexity difference. From the experimental results for various and modified 2-D shapes, it is believed that the graph-based representation for 2-D shape coincides with that based on human insight, and also provides robustness to scaling, rotation, noise, shape deformation and occlusion.

Nowadays, the demand on user-friendly querying interface such as query-by-sketch and query-by-editing is an important issue in the content-based retrieval system for 3-D object database. Especially in MPEG-7, P3DS (Perceptual 3-D Shape) descriptor has been developed in order to provide the user-friendly querying, which can not be covered by an existing international standard for description and browsing of 3-D object database. Since the P3DS descriptor is based on the part-based representation of 3-D object, it is a kind of attributed relational gra (ARG) so that the ARG matching algorithm naturally follows as the core procedure for the similarity matching of the P3DS descriptor. In this paper, given a P3DS database from the corresponding 3-D object database, we bring focus into investigating the pros and cons of the target ARG matching algorithms. In order to demonstrate the objective evidence of our conclusion, we have conducted the experiments based on the database of 480 3-D objects with 33 categories in terms of the bull's eye performance, average normalized modified retrieval rate, and precision/recall curve.

In this paper, we propose a novel scalable video coding algorithm based on adaptively weighted multiple reference frame method. To improve the coding efficiency in enhancement layer, double reference picture and double motion vector algorithms are employed for motion compensated prediction. In addition, the enhancement layer is predicted by the adaptively weighted sum of the double motion compensated frames in the enhancement layer and the the current frame in the base layer, according to the input video characteristics. By employing adaptive reference selection scheme at the decoder, the proposed method can reduce the drift problem significantly. experimental results show that the proposed algorithm yields higher PSNR performance compared with the fixed weighted scheme and the H.263+ for various packet loss rate channel conditions.

We propose an overlapped block motion compensation method, called adaptive windowing technique, to improve the performance of variable block-size motion compensation in H.264. First, we restrict the number of neighboring blocks to be overlapped. Then we design adaptive overlapping windows, where each weight is set to be inversely proportional to the distance between the current pixel and the neighboring block. The weights can be computed effciently in both the encoder and the decoder. Also, to further improve the prediction performance, we introduce the notion of reliability of a motion vector based on the block size, and fine-tune the weights according to the reliability. Extensive simulation results show that the proposed algorithm improves the performance of H.264 both objectively and subjectively.

A lossless compression algorithm of 3D point data is proposed in this work. QSplat is one of the efficient rendering methods for 3D point data. In QSplat, each point is assigned a sphere, and the geometry and normal data are stored in the hierarchical structure of bounding spheres. To compress QSplat data, child spheres are sorted based on their limit radii to constrain the indices for the geometry data. Then, the radii and the positions of spheres are encoded separately using the reduced index sets. Also, each normal is encoded using the parent normal context, and the normal indices are reduced by the normal cone information. Simulation results show that the proposed algorithm achieves a high compression ratio by combining the reduced index sets with the context-based entropy coding.

In this paper, we develop a tree-structured predictive partial matching (PPM) scheme for progressive compression of PointTexture images. By incorporating PPM with tree-structured coding, the proposed algorithm can compress 3D depth information progressively into a single bitstream. Also, the proposed algorithm compresses color information using a differential pulse coding modulation (DPCM) coder and interweaves the compressed depth and color information effciently. Thus, the decoder can reconstruct 3D models from the coarsest resolution to the highest resolution from a single bitstream. Simulation results demonstrate that the proposed algorithm provides much better compression performance than a universal Lempel-Ziv coder, WinZip.

This paper describes a new semiglobal method for SFS (shape-from-shading) using graph cuts. The new algorithm combines the local method proposed by Lee and Rosenfeld (1985) and the global method using energy minimization technique. By employing a new global energy minimization formulation, the convex/concave ambiguity problem of the Lee and Rosenfeld method can be resolved efficiently. A new combinatorial optimization technique, graph cuts method is used for the minimization of the proposed energy functional. Experimental results on a variety of synthetic and real-world images show that the proposed algorithm reconstructs the 3-D shape of objects very efficiently.

Recently, the 3-D object retrieval system attempts to integrate 2-D visual descriptors since some applications including e-shopping cannot employ 3-D object as a query. For an example, the multiple views have been developed in MPEG-7, but it cannot consider the spatial distribution of 3-D object and has heavy computational complexity because of the matching procedure in a combinatorial manner. In this paper, a novel descriptor for the 3-D object retrieval system, the regular polyhedral descriptor or regular polyhedron, is proposed. The proposed descriptor, which consists of the selection of equally distributed view positions and matching strategy using the regular polyhedron, is based on the multiple view, but it can improve the multiple view by using the property of the regular polyhedron. Experimental results show that the proposed descriptor has the retrieval performance comparable to the multiple views, in terms of the bull's eye performance (BEP) and average normalized modified retrieval rate (ANMRR).

This paper presents an error analysis for voxel coloring [S.M. Seitz, et al. (1997), K.N. Kutulakos, et al. (2000)], which is one of the well known methods to reconstruct 3D shape from 2D calibrated multiple-view images. In order to analyze the errors arising in the reconstruction process of voxel coloring algorithms, we first model several noise sources in the analytic or statistical way, and then examine the effects of each noise component on the reconstructed 3D model. Specifically, in order to analyze the statistical errors, we focus on the distribution of the image variance, which is employed as photo consistency measurement. And also, we show that how specular components induce errors in reconstructing 3D model. The results of this analysis are very useful for evaluating the statistical confidence of the reconstructed 3D model as well as finding the optimal threshold for the occupancy decision.

Compressed bit streams of 3D mesh data are highly vulnerable to transmission errors due to predictive coding and entropy coding. In this work, we propose an error resilient and progressive coding scheme for 3D meshes. To make a compressed bit stream robust to transmission errors, 3D mesh data is partitioned into several segments, which are then encoded independently. In the decoder, a novel error concealment scheme is employed to improve the visual quality of corrupted segments. Simulation results show that the proposed algorithm provides a good quality reconstruction even in severe error conditions.

In this work, we propose a multi-hypothesis error concealment algorithm, which replaces a lost block with a weighted superposition of more than two reference blocks in previous frames. Three methods are developed to find the set of reference blocks and determine the weighting coefficients. These methods are implemented based on H.26L standard, and their performances are evaluated. It is shown that the proposed multi-hypothesis algorithm provides up to 1.5 dB better performance than the conventional single-hypothesis concealment algorithm.

Abstract Mesh simplification is the process of reducing the number of triangles in a mesh representation of object surface. For a given level of detail or error tolerance, the conventional mesh simplification algorithms maximize the edge length globally, without explicitly considering local object shape. In this paper, we present a shape‐adaptive mesh simplification algorithm that locally maximizes edge length, depending on local shape. The proposed algorithm achieves shape‐adaptive simplification by iteratively maximizing edges between vertices, based on comparison with the ‘optimal’ edge lengths derived from local directional curvatures for a given error tolerance. Edge‐based processing facilitates the local shape adaptation and preserves sharp features. Experimental results demonstrate the efficacy of the proposed algorithm, by showing good visual quality and extremely small approximation error. Copyright © 2003 John Wiley & Sons, Ltd.

In this paper, we propose a new efficient topology estimation algorithm to construct a multiresolution polygonal mesh from measured three-dimensional (3-D) range data. The topology estimation problem is defined under the constraints of cognition, compactness, and regularity, and the algorithm is designed to be applied to either a cloud of points or a dense mesh. The proposed algorithm initially segments the range data into a finite number of Voronoi patches using the K-means clustering algorithm. Each patch is then approximated by an appropriate polygonal and eventually a triangular mesh model. In order to improve the equiangularity of the mesh, we employ a dynamic mesh model, in which the mesh finds its equilibrium state adaptively, according to the equiangularity constraint. Experimental results demonstrate that satisfactory equiangular triangular mesh models can be constructed rapidly at various resolutions, while yielding tolerable modeling error.

Presents a hybrid and parallel system based on artificial neural networks for a face invariant classifier and general pattern recognition problems. A set of face features is extracted by using the eigenpaxel method, which is based on principal component analysis (PCA) of a group of pixels, that is called a paxel. To classify subjects, multi-layer perceptron neural networks (NNs) are trained for each eigenpaxel. These parallel NN kernels provide sage, fast and efficient classification. To combine the results of parallel NNs, a novel judge analyzer is proposed based on bond rating classification and prediction. The proposed judge strategy can detect distinguishable face features even in arguable situations. The proposed method was evaluated on Olivetti and HongIk university (HIU) face databases and it yields a top recognition rate of 95.5% and 94.11% respectively, which are better results than the previous eigenpaxel and NN approach.

We present a new face detection algorithm based on the 1st-order reduced Coulomb energy (RCE) classifier. The algorithm locates frontal views of human faces at any degree of rotation and scale in complex scenes. The face candidates and their orientations are first determined by computing the Hausdorff distance between a simple face abstraction model and binarized test windows in an image pyramid. Then, after normalizing the energy, each face candidate is verified by two subsequent classifiers; a binary image classifier and the 1st-order RCE classifier While the binary image classifier is employed as a pre-classifier to discard nonfaces with minimum computational complexity, the 1st-order RCE classifier is used as the main face classifier for final verification. An optimal training method to construct the representative face model database is also presented. Experimental results show that the proposed algorithm yields a high detection ratio, while yielding no false alarm.

In this paper, we propose a novel scalable video coding algorithm based on adaptively weighted multiple reference frame method. To improve the coding efficiency in the enhancement layer, double reference picture and double motion vector algorithms are employed for motion compensated prediction. Furthermore, an enhancement layer frame is predicted from the adaptively weighted superposition of the corresponding base layer frame and the double motion compensated frames, according to the the input video characteristics and the feedback channel condition. By employing an adaptive reference selection scheme at the decoder, the proposed method can reduce the drift problem significantly. Experimental results show that the proposed algorithm yields higher PSNR performance than H.263+ both in error-free and severe packet loss channel conditions.

In this paper, we propose a progressive compression algorithm for three-dimensional (3D) mesh data, which can efficiently encode the connectivity and geometry information. Using cosine index predictor and vertex confinement rule, the proposed scheme encodes the connectivity information compactly. For the geometry-information coding, a 2-stage geometry predictor is proposed to reduce the prediction error more effectively than the conventional techniques. Simulation results show that the proposed algorithm yields better coding performance than the conventional algorithm.

We propose a progressive encoding algorithm for 3D voxel surfaces, based on the pattern code representation (PCR). In PCR, a voxel surface is represented by a series of pattern codes. It can achieve coding gain, since the pattern codes are highly correlated. In the multi-resolution framework, the coding gain can be further improved by the decimation constraint from the lower resolution surface. Furthermore, an alternative patternbook is adopted for voxels within smooth regions to reduce the number of possible pattern codes. Simulation results show that the proposed algorithm provides better performance than the conventional PCR algorithm.

Mesh simplification is the process of reducing the number of triangles in a mesh representation of object surface. For a given level of detail or error tolerance, the conventional mesh simplification algorithms maximize the edge length globally, without explicitly considering the local object shape. In this paper we present a shape-adaptive mesh simplification algorithm that locally maximizes the edge length, depending on the local shape. The proposed algorithm achieves shape-adaptive simplification by iteratively maximizing edges between vertices, based on a comparison with the "optimal" edge lengths derived from local directional curvatures for a given error tolerance.

Presents an integrated system for navigation parameter estimation using sequential aerial images, where the navigation parameters represent the positional and velocity information of an aircraft for autonomous navigation. The proposed integrated system is composed of two parts: relative position estimation and absolute position estimation. Relative position estimation recursively computes the current position of an aircraft by accumulating relative displacement estimates extracted from two successive aerial images. Simple accumulation of parameter values reduces the reliability of the extracted parameter estimates as an aircraft goes on navigating, resulting in a large positional error. Therefore, absolute position estimation is required to compensate for the positional error generated by the relative position estimation. Absolute position estimation algorithms using image matching and digital elevation model (DEM) matching are presented. In the image matching, a robust-oriented Hausdorff measure (ROHM) is employed, whereas in the DEM matching, an algorithm using multiple image pairs is used. Experiments with four real aerial image sequences show the effectiveness of the proposed integrated position estimation algorithm.

We propose an efficient geometry compression algorithm for three-dimensional (3-D) mesh sequences based on the two-stage vertex-wise motion vector (MV) prediction. In general, the MV of a vertex is highly correlated to those of the adjacent vertices. To exploit this high correlation, we define the neighborhood of a vertex, and predict the MV of the vertex from those of the neighborhood. The error vectors are related to the local shape changes of 3-D objects, and still have redundancy. To remove the redundancy, the error vectors are also predicted, at the second stage, spatially or temporally by using a rate-distortion optimization technique. It is shown that the proposed algorithm has simpler structure than the existing segment-based algorithm, and yields better compression performance.

In this paper, we propose a lossless compression algorithm for three-dimensional (3-D) binary voxel surfaces, based on the pattern code representation (PCR). In PCR, a voxel surface is represented by a series of pattern codes. The pattern of a voxel v is defined as the 3 x 3 x 3 array of voxels, centered on v. Therefore, the pattern code for informs of the local shape of the voxel surface around . The proposed algorithm can achieve the coding gain, since the patterns of adjacent voxels are highly correlated to each other. The performance of the proposed algorithm is evaluated using various voxel surfaces, which are scan-converted from triangular mesh models. It is shown that the proposed algorithm requires only 0.5 approximately 1 bits per black voxel (bpbv) to store or transmit the voxel surfaces.

We present a new 3D camera motion estimation technique using the optical flow from a pair of images taken under a perspective projection. The problem formulation leads to the solution of an overdetermined nonlinear system of equations with respect to the motion parameters. By employing an efficient initial guess algorithm which uses a weak perspective projection and an image coordinate normalization technique, the nonlinear solution can be obtained robustly and accurately. The proposed method has been tested on both several synthetic and real image sequences. The results show that the performance of the proposed algorithm is quite superior to the conventional ones even under more general and noisy situations.

In this paper, we propose a new geometry compression algorithm for 3D mesh sequences, based on vertex-wise motion vector (MV) prediction. In general, the MV of a vertex is highly correlated to those of adjacent vertices. To exploit the high correlation, we define a neighborhood of a vertex, and predict the MV of the vertex from those of the neighborhood. It is shown that the proposed algorithm has simpler structure than the existing segment-based algorithm. Furthermore, simulation results demonstrate that the proposed algorithm yields better compression performance than the existing algorithm.

This paper proposes a motion compensation (MC) algorithm for robust transmission of video sequence, called the double-vector motion compensation (DMC). In the DMC, each block B in a frame is predicted from the weighted superposition of two blocks in the previous two frames, using two motion vectors. Therefore, when one of these two blocks is corrupted during the transmission, the decoder can efficiently suppress its error propagation to the subsequent frames, by predicting B only from the other block. It is shown by analysis that the DMC algorithm yields significantly lower error bounds for the subsequent frames than the conventional MC technique. Furthermore, the DMC algorithm can be combined with an effective concealment algorithm, which is capable of recovering very severe transmission errors, such as loss of an entire frame. A complete video coder, based on the DMC, is implemented by modifying the MC syntax of the H.263 standard and tested intensively in a realistic error prone environment. It is shown that the proposed algorithm provides much better objective and subjective performances than the H.263 coder in the error-prone environment.

In many video-coding standards, the motion vector field is one of the most important data in the compressed bitstream, and its loss can lead to severe degradation in the decoded picture quality. We propose the multiple description motion coding (MDMC) algorithm to enhance the robustness of the motion vector field against transmission errors. In MDMC, the motion vector field is encoded into two descriptions, which are transmitted over distinct channels to the decoder. The decoder is designed to provide an acceptable quality prediction image, even if one of the descriptions is lost during the transmission. Moreover, the decoder can reconstruct a higher quality prediction image, when both the descriptions are received without error. A complete multiple description video coder, based on the MDMC, is implemented by modifying the syntax of the H.263 standard, and tested intensively in a realistic error-prone environment. It is shown that the proposed algorithm provides much better objective and subjective performances than the H.263 coder in the error-prone environment.

Several techniques based on the multiple reference frame scheme have been proposed to improve the motion prediction gain. Though these techniques yield higher prediction gain than the single reference frame scheme, they require tremendous computational complexity during the motion search procedure. Besides, blocking artifacts may be visible along the block boundaries, since each macroblock is predicted independently of its neighbors. To overcome these drawbacks, this paper proposes a novel motion compensation algorithm, based on the double reference frame (DRF), the double motion vector (DMV), and the searching position shifting (SPS) schemes. First, to reduce the motion vector bitrate and the computational complexity of motion search procedure, we constrain the number of reference frames to 2, and use only two motion vectors per block. Second, to alleviate the blocking artifacts and to get the better pel prediction, the searching position shifting scheme is introduced. Experimental results demonstrate that the proposed algorithm yields a 3-4 dB higher prediction gain than the single reference frame scheme. The subjective quality is also improved by alleviating the blocking artifacts.

We address a new algorithm for recognition and reconstruction of 3D polyhedral objects, based on perceptual grouping and graph search technique. Perceptual grouping is performed in a model-based framework, in which decision tree classifier is employed for learning and retrieving geometric information of the 3D model object. On the other hand, in order to extract the polygonal patch structure, initial grouping result is represented by a Gestalt graph. Polygonal patch hypotheses are then generated by graph search and verified by the consistency test with the model. In the experiments, it is shown that the model-based grouping reduces the number of the generated hypotheses efficiently, and furthermore, robust recognition and reconstruction are achieved by means of the graph search technique.

This paper proposes an algorithm for the reduction of blocking artifacts in the transform coded images and videos. The algorithm is based on the filtering of block boundaries. But, the proposed technique is not the actual filtering in the sense that the output is not obtained by multiplying the pixel values with the filter coefficients. Instead of filtering the pixel values through the filter coefficients, the output of the filter is modeled as a typical step response function of the lowpass filter or a functions with similar shapes. Then the blocky signal is just replaced by the modeled output signal which is generated by the library function such as exp or sin. The algorithm can be easily implemented by a lookup-table and very few multiplications, while the objective and subjective performance is comparable to those of other algorithms based on the conventional filtering and POCS (projection onto convex sets).

This paper proposes a novel algorithm for robust transmission of video sequences, based on the multiple description motion coding (MDMC). In the MDMC, the motion vector field is encoded into two descriptions, which are transmitted over distinct channels to the decoder. The decoder is designed to provide an acceptable quality prediction image, even if one of the descriptions is lost during the transmission. Moreover, the decoder reconstructs a higher quality prediction image, if both the descriptions are received without error. A complete multiple description video coder is implemented by modifying the syntax of the H.263 standard. Intensive simulation results show that the proposed algorithm provides much better performance than the H.263 coder in realistic error prone environment.

We propose an error-resilient transmission technique for the H.263 compatible video data stream, based on the data-partitioning technique. The proposed algorithm employs the bit rearrangement technique of the error-resilience entropy coding in each layer, providing unequal error protection against the channel errors, without requiring additional side information. In addition, we propose the recovery algorithm for the lost or erroneous motion vectors. The proposed algorithm is implemented, based on the H.263 standard, and evaluated through intensive computer simulation. The experimental results demonstrate that the proposed algorithm provides acceptable performance both subjectively and objectively at various bit error rates and burst lengths.

We propose a discrete cosine transform (DCT)-based post-processing technique to alleviate the blocking artifacts in transform coded images. In our approach, the high-frequency components, mainly caused by the edge components, are examined through two steps. First, two adjacent homogeneous blocks from the block boundary are found, where the homogeneous block is defined as the block in which no adjacent pixels' difference is larger than the difference of the block boundary. Second, the local frequency characteristics in the homogeneous block are examined through the DCT. Then, we derive the relation between the DCT coefficients of two homogeneous blocks of different sizes. By considering the information about the original edge and the relation, we can detect the high-frequency components, mainly caused by the blocking artifact. The performance of the proposed technique is evaluated on both still and moving images. The simulation results indicate that the proposed technique reduces the blocking artifacts effectively and preserves the original edges faithfully, and its performance is very robust to the degree of degradation in the decoded images.

We propose an algorithm to construct a 3-D surface model from a set of range data, based on non-uniform rational B-splines (NURBS) surface-fitting technique. It is assumed that the range data is initially unorganized and scattered 3-D points, while their connectivity is also unknown. The proposed algorithm consists of three stages: initial model approximation employing K-means clustering, hierarchical decomposition of the initial model, and construction of the NURBS surface patch network. The initial model is approximated by both a polyhedral and triangular model. Then, the initial model is represented by a hierarchical graph, which is efficiently used to construct the G/sup 1/ continuous NURBS patch network of the whole object. Experiments are carried out on synthetic and real range data to evaluate the performance of the proposed algorithm. It is shown that the initial model as well as the NURBS patch network are constructed automatically with tolerable computation. The modeling error of the NURBS model is reduced to 10%, compared with the initial mesh model.

The motion compensation-discrete cosine transform (MC-DCT) coding is an efficient compression technique for a digital video sequence. However, the compressed video signal is vulnerable to transmission errors over noisy channels. In this paper, we propose a robust video transmission algorithm, which protects the compressed video signal by inserting redundant information at the source level. The proposed algorithm encodes every lth frame in the semi-intra frame (S-frame) mode, in which the redundant parity-check DC coefficients (PDCs) are systematically inserted into the compressed bitstream. Then, the decoder is capable of recovering very severe transmission errors, such as loss of an entire frame, in addition to detecting the errors effectively without requesting any information from external devices. The proposed algorithm is implemented based on the H.263 coder, and tested intensively in realistic error prone environment. It is shown that the proposed algorithm provides much better objective and subjective performances than the conventional H.263 coder in the error prone environment.

In this paper, we consider the problem of recognizing 3D object from a single 2D intensity image obtained from unknown position and orientation. We propose the feature set based correspondence algorithm between 3-D model features and 2-D image features, in contrast to the conventional approaches which use a single local feature or fixed number of local features. As a measure of the similarity between feature sets, the Hausdorff distance with explicit paring (HDEP) is proposed and extended to the partial HDEP, using the notion of the partial distance to cope with the problems which occur when there are backgrounds and some of image features are missing or severely deviated from each original value. The 3D object recognition system using this algorithm with hypothesis-verification scheme is implemented and tested on real images with backgrounds and occlusion.

We address a new perceptual grouping algorithm for aerial images, which employs a decision tree classifier and hierarchical multilevel grouping strategy in a bottom-up fashion. In our approach, grouping is performed perceptually on 3D features extracted from 2D images, in which the gestalt principles including collinearity, parallelism and L-typed convergence are encoded by the decision tree learning technique. The decision tree is constructed using training samples obtained from the given 3D reference model. Then, each pair of the extracted 3D line features of an input image is classified into one of the learned gestalt primitives. On the other hand, in multilevel grouping procedure, grouping of collated features are performed from lower to higher level, yielding the structured target model. In order to evaluate the proposed algorithm, experiments are carried out on RADIUS model board images. The results show that grouping is performed effectively to extract man-made structures in aerial images.

Extracting a small number of key frames that can abstract the content of video is very important for efficient browsing and retrieval in video databases. In this paper, the key frame extraction problem is considered from a set-theoretic point of view, and systematic algorithms are derived to find a compact set of key frames that can represent a video segment for a given degree of fidelity. The proposed extraction algorithms can be hierarchically applied to obtain a tree-structured key frame hierarchy that is a multilevel abstract of the video. The key frame hierarchy enables an efficient content-based retrieval by using the depth-first search scheme with pruning., Intensive experiments on a variety of video sequences are presented to demonstrate the improved performance of the proposed algorithms over the existing approaches.

In this paper, a new contour-coding technique for object-oriented video coding is proposed, In our approach, the two-stage motion compensation technique is considered, in order to cope with the rather complex motion of the object. While the object-based motion compensation is performed in the first stage, the second-stage motion compensation is carried out to search the best match of the contours, which are not motion compensated in the first stage. Also by introducing the notion of the error band, the current contours can be properly fitted to the motion compensated contours using the interframe relationship of the contours. In addition, an efficient technique for encoding the contours, simplified by the majority filter, is also proposed. From the simulation result, it is shown that the proposed technique provides better performance than the content-based arithmetic encoding, especially when lossy encoding is allowed. Moreover, by varying the width N of the error band, it is shown that the bit amount for the shape information can be adjusted according to the channel condition.

This paper proposes an adaptive quantization algorithm for video coding using the information obtained from the previously encoded image. Before quantizing the discrete cosine transform coefficients, the properties of reconstruction error of each macro block (MB) are estimated from the previous frame. For the estimation of the error of current MB, a block with the size of MB in the previous frame is chosen. Since the original and reconstructed images of the previous frame are available in the encoder, we can evaluate the tendency of reconstruction error of this block in advance. Then, this error is considered as the expected error of the current MB if it is quantized with the same step size and bit rate. Comparing the error of the MB with the average of overall MBs, if it is larger than the average, a small step size is given for this MB, and vice versa. As a result, the error distribution of the MB is more concentrated to the average, yielding low variance and improved image quality. Especially for low bit applications, the proposed algorithm yields much smaller error variance and higher peak signal-to-noise ratio compared to the conventional TM5. We also propose a modified algorithm for efficient hardware implementation.

Motion compensation-discrete cosine transform (MC-DCT) coding is an efficient compression technique for digital video sequences. However, the compressed video signal is vulnerable to transmission errors over noisy channels. In this paper, we introduce a novel concept of parity-check motion vector (PMV) into the MC-DCT coder in order to improve its error robustness. By inserting the redundant PMVs systematically into the compressed bitstream, the proposed algorithm is capable of recovering very severe transmission errors, such as loss of an entire frame, in addition to detecting the errors effectively without requesting any information from external devices. The proposed algorithm is implemented based on the H.263 coder, and tested intensively in a realistic error prone environment. It is shown that the proposed algorithm provides much better objective and subjective performances than the conventional H.263 coder in the error prone environment.

This paper presents a recovery technique for the image block data corrupted by transmission losses, employing the two-dimensional non-uniform rational B-spline (NURBS) function. In our approach, the control grid points which generate the best approximated surface of the neighboring image data are obtained by an optimization technique. To recover the edge components in the corrupted block more faithfully, the edge linking algorithm is utilized for the estimation of the edge components, and the interpolation algorithms are modified to enhance the edge components. Computer simulation results show that the contents of the corrupted image block data, including the edge components, can he recovered more faithfully than the conventional algorithms.

This work presents a hybrid method for navigation parameter estimation using sequential aerial images, where navigation parameters represent the position and velocity information of an aircraft for autonomous navigation. The proposed hybrid system is composed of two parts: relative position estimation and absolute position estimation. Computer simulation with two different sets of real aerial image sequences shows the effectiveness of the proposed hybrid parameter estimation algorithm.

The aim of motion stereo is to extract the 3-D information of an object from images of a moving camera using the geometric relationships between corresponding points. This paper presents an accurate and robust motion stereo algorithm employing multiple images, taken under a general motion. The object functions for individual stereo pairs are represented, with respect to the distance, then these object functions are integrated considering the position of cameras and the shape of the object functions. By integrating the general motion stereo images, we not only reduce the ambiguities in correspondence, but also improve the precision of the reconstruction. Also by introducing an adaptive window technique, we can alleviate the effect of projective distortion in matching features and improve the accuracy greatly. Experimental results on a synthetic and real data set are presented to demonstrate the performance of the proposed algorithm.

We propose a novel postprocessing technique, based on the theory of projections onto convex sets (POCS), to reduce the blocking artifacts in transform coded images. It is assumed, in our approach, that the original image is highly correlated. Thus, the global frequency characteristics in two adjacent blocks are similar to the local ones in each block. We consider the high-frequency components in the global characteristics of a decoded image, which are not found in the local ones, as the results from the blocking artifact. We employ an N-point discrete cosine transform (DCT) to obtain the local characteristics, and a 2N-point DCT to obtain the global ones, and then derive the relation between the N-point and 2N-point DCT coefficients. A careful comparison of the N-point with the 2N-point DCT coefficients makes it possible to detect the undesired high-frequency components, mainly caused by the blocking artifact. Then, we propose novel convex sets and their projection operators in the DCT domain. The performance of the proposed and conventional techniques are compared on the still images, decoded by JPEG. The results show that, regardless of the content of the input images, the proposed technique yields significantly better performance than the conventional techniques in terms of objective quality, subjective quality, and convergence behavior.

We propose a novel algorithm for fractal video sequence coding, based on the circular prediction mapping and the noncontractive interframe mapping. The proposed algorithm can effectively exploit the temporal correlation in real image sequences, since each range block is approximated by the domain block in the adjacent frame, which is of the same size as the range block. The computer simulation results demonstrate that the proposed algorithm provides very promising performance at low bit rate, ranging from 40-250 kbyte/s.

We investigate the relation between VQ (vector quantization) and fractal image coding techniques, and propose a novel algorithm for still image coding, based on fractal vector quantization (FVQ). In FVQ, the source image is approximated coarsely by fixed basis blocks, and the codebook is self-trained from the coarsely approximated image, rather than from an outside training set or the source image itself. Therefore, FVQ is capable of eliminating the redundancy in the codebook without any side information, in addition to exploiting the self-similarity in real images effectively. The computer simulation results demonstrate that the proposed algorithm provides better peak signal-to-noise ratio (PSNR) performance than most other fractal-based coders.

This paper introduces a novel concept of PMV (parity motion vector) into the MC-DCT (motion compensation-discrete cosine transform) coder, in order to improve its robustness to transmission errors over noisy channels. By inserting the redundant PMVs systematically into the compressed bitstream, the proposed algorithm is capable of recovering very severe transmission errors, such as loss of an entire frame. The proposed algorithm is implemented based on the H.263 coder, and tested intensively in a realistic error prone environment. It is shown that the proposed algorithm provides much better objective and subjective performances than the conventional H.263 coder in the error prone environment.

We propose an algorithm to produce a 3-D CAD model from a set of range data, based on non-uniform rational B-splines (NURBS) surface fitting technique. Our goal is to construct continuous geometric models, assuming that the topology of surface is unknown. In our approach, a divide-and-conquer strategy is adopted, in which the whole range data is partitioned into surface patches. Each patch is sequentially processed to form the quadrilateral face model, which is used to construct the NURBS patch network. Experiments are carried out to evaluate the performance of the proposed algorithm. It is shown that the continuous 3-D model is successfully generated automatically with tolerable computational complexity.

The conventional split-and-merge algorithm is lacking in the adaptability to the image semantics because of its stiff quadtree-based structure. A thresholding technique is employed in the splitting phase of the split-and-merge segmentation scheme to directly reflect the image semantics to the image segmentation results. Thus, the regions which contain distinct subregions can be extracted by one step, which significantly alleviating the computation load and the memory requirements. To overcome the problems, caused by the block-based thresholding, such as edge discontinuities over the borders of quadtree nodes, a prefilter is used to preserve and sharpen the edge information. Applying the proposed algorithm to aerial images results in the reduction of the number of intermediate regions generated in the splitting phase, demonstrating the improved ability to capture the image semantics. The simulation results shows that the proposed algorithm successfully extract arbitrary shaped regions in aerial images.

This paper presents a novel error concealment technique based on the discrete cosine transform (DCT) coefficients recovery and its application to the MPEG-2 bit stream error. Assuming a smoothness constraint on image intensity, an object function which describes the intersample variations at the boundaries of the lost block and the adjacent blocks is defined, and the corrupted DCT coefficients are recovered by solving a linear equation. Our approach can be regarded as a special case of Wang et al.'s (1991). However, we show that the linear equation in the proposed algorithm can be decomposed into four independent subequations, requiring much lower computational load and simpler hardware structure than existing algorithms, while providing adequate performances. To develop a generic error concealment (EC) system, the blocks corrupted by the random bit errors are identified by a multistage error detection algorithm. Thus, the proposed EC system can be applied to more realistic environments, such as concealment of random bit error in MPEG-2 bit stream. Computer simulation results show that the quality of a recovered image is significantly improved even at a bit error rate as high as 10/sup -5/.

This paper discusses a criterion for testing a vector quantizer (VQ) codebook that is obtained by "training". When a VQ codebook is designed by a clustering algorithm using a training set, "time-average" distortion, which is called the training-set-distortion (TSD), is usually calculated in each iteration of the algorithm, since the input probability function is unknown in general and cumbersome to deal with. The algorithm stops when the TSD ceases to significantly decrease. In order to test the resultant codebook, validating-set-distortion (VSD) is calculated on a separate validating set (VS). Codebooks that yield small difference between the TSD and the VSD are regarded as good ones. However, the difference VSD-TSD is not necessarily a desirable criterion for testing a trained codebook unless certain conditions are satisfied. A condition that is previously assumed to be important is that the VS has to be quite large to well approximate the source distribution. This condition implies greater computational burden of testing a codebook. In this paper, we first discuss the condition under which the difference VSD-TSD is a meaningful codebook testing criterion. Then, convergence properties of the VSD, a time-average quantity, are investigated. Finally we show that for large codebooks, a VS size as small as the size of the codebook is sufficient to evaluate the VSD. This paper consequently presents a simple method to test trained codebooks for VQ's. Experimental results on synthetic data and real images supporting the analysis are also provided and discussed.

This correspondence formally defines partial Radon trans- forms for functions of more than two dimensions. It shows that a generalized projection-slice theorem exists which connects planar and hy- perplanar projections of a function to its Fourier transform. In addition, a general theoretical framework is provided for carrying out -dimensional backprojection reconstruction in a multistage fashion through the use of the partial Radon transform.

We propose a novel post-processing technique based on the theory of projections onto convex sets (POCS) to reduce the blocking artifacts in decoded images. Assuming that original image is highly correlated, the global frequency characteristics in two adjacent blocks may be similar to the local one in each block. Thus, we can consider the high frequency components of the global characteristics that do not exist in the local one as the effect caused by blocking artifact. We employ N-point DCT to obtain the local characteristics, and 2N-point DCT to obtain the global one, and then derive the relation between N-point and 2N-point DCT coefficients. The comparison of N-point with 2N-point DCT coefficients makes it possible to detect the undesired high frequency components, caused by the blocking artifact. From the above notion, we propose novel convex sets and their projection operators in the DCT domain. Results of performance evaluation show that regardless of image contents, the proposed technique is superior to the conventional ones, in terms of objective quality, subjective quality and convergence behavior.

This paper proposes a joint image segmentation and motion estimation technique for very low bit rate video coding. In region-based coding, a segmentation algorithm is indispensable. Motivated by the observations of the conventional algorithm, we propose a jointly optimized image segmentation and motion estimation algorithm. In our algorithm, the input image is split into a quadtree structure, and the split regions are merged by a greedy merging algorithm (GMA). In each step of GMA, two regions which have the minimum cost are merged. Since we have chosen the cost as the increase of displaced frame difference (DFD) energy, the image is segmented into a set of regions with minimum DFD energy. By computer simulation, we show the segmentation results have much lower DFD energy compared to the block-based motion estimation.

This paper presents a method for navigation parameter estimation using sequential aerial images, where navigation parameters represent the velocity and position information of an aircraft for autonomous navigation. The proposed navigation parameter estimation system is composed of two parts: relative position estimation and absolute position estimation. Relative position estimation recursively computes the current velocity and position of an aircraft by accumulating navigation parameters extracted from two successive aerial images. However, simple accumulation of parameter values decreases reliability of the extracted parameters as an aircraft goes on navigating, resulting in a large position error. Therefore absolute position estimation is required to compensate for position error generated in the relative position estimation step. A hybrid absolute position estimation algorithm combining image matching and digital elevation model (DEM) matching is presented. In image matching, line segment matching or Hausdorff distance (HD) matching is employed whereas in DEM matching a new algorithm for absolute position estimation by minimizing the variance of displacements is proposed. Computer simulation with real aerial image sequences shows the effectiveness of the proposed algorithm.

We propose a novel fractal image compression technique, which does not require iteration at the decoder. The main problem relating to the conventional noniterative algorithm is that the smooth region cannot be coded efficiently, since the size of the range block is limited to be less than 8/spl times/8. We alleviate this problem by generating two codebooks from a planarly approximated image. In other words, the first codebook is generated by the smoothing operator for large and smooth range blocks and the second codebook is generated by the spatial contraction operator for small and active range blocks, respectively. The computer simulation results on the real images demonstrate that the proposed algorithm provides much better performance than most other fractal-based coders, in terms of the subjective quality as well as the objective quality (PSNR). Moreover, the proposed algorithm is very fast in decoding, since it does not require iteration at the decoder.

In this paper, we present a new post-processing algorithm, based on the theory of projections onto convex sets (POCS), to enhance the quality of decoded images degraded by the blocking artifact. In our approach, by introducing the notion of the global slope, block slope and local slope, a novel linear projection operator is induced. The operator makes the block slopes of two adjacent blocks be equal to the global slope, to alleviate the blocking artifact, while maintaining the local slopes inside the blocks, to preserve most original high frequency components. Computer simulation results on still and moving images show that in the viewpoint of the objective and the subjective quality, the proposed algorithm makes decoded images converge without iteration to the post-processed images, in which the blocking artifact is alleviated effectively, while the conventional algorithms based on the POCS converge with a number of iterations.

This paper presents a new error concealment (EC) technique for DCT based image coding. In our approach, the damaged blocks are recovered utilizing the smoothness property of an image at the boundaries of the blocks. Based on the property, we first define an object function which represents the intersample variations between adjacent blocks. Then, the DCT coefficients which minimize the object function are estimated by finding a solution of a linear equation. And, we show that it can be decomposed and reduced into more simple sub-equations. Thus, the computational complexity of the proposed technique is very low, compared to the existing techniques. Computer simulation results show that the proposed algorithm recovers the damaged blocks even if the block loss rate (BLR) is as high as 10/sup -2/.>

A 3-D shape recovery algorithm, which is based on the hybrid reflectance model and M ring shaped lights for specular surfaces, is presented. We derive a radiance L/sub r/ as a function of slant angle /spl theta//sub n/ of a surface point in polar coordinate. Then, by using the input intensity images and the radiance function, the M slant angle at each point are obtained. The final slant angle is determined as a weighted sum of the M slant angles. Finally, the surface gradient, which is obtained from the slant angle and its contours, is integrated to the depth map. Examples are provided using both synthetic and real data.>

In this paper, we propose an adaptive 3-D subband video coding technique based on the rate-distortion optimal wavelet packet bases. The input image sequence is first transformed by DCT in temporal domain and the lowest temporal frequency frame is split into fine uniform subbands by considering correlation and energy in the frame. Other higher frequency frames show various energy distributions, with respect to the motion in the image sequence. Thus, adaptive 2-D wavelet packet bases, which are optimal in rate-distortion sense, are applied to these high frequency frames. We also propose a coding gain optimized CQF(Conjugate Quadrature Filter) design technique, assuming AR(1) input source model, and apply it to the 3-D subband coding technique. Moreover, we investigate the adaptivity of temporal domain transform by the performance comparisons of the 4-tap and 8-tap DCT. From the simulation results, the proposed 3-D subband coder shows a better performance than the fixed wavelet packet bases scheme. And it is shown that the adaptive temporal transform can considerably improve the 3-D subband coder performance.>

In motion compensated video coding, if motion vectors are lost or received with errors, not only will the current frame be corrupted, but also the errors will propagate to succeeding frames. The effects of errors can be further magnified by the fact that motion vectors are usually coded differentially. In this paper, we propose a technique using motion vector smoothing in the encoder and both boundary matching and motion vector consistency check in the decoder to compensate for lost or erroneously received motion vectors. The proposed technique produces noticeably better results than those reported previously. And the proposed motion vector smoothing algorithm causes virtually no degradation in the decoded image quality when motion vectors have no errors.>

Recently, a variable block size (VBS) motion estimation technique has been employed to improve the performance of the motion compensated transform coding (MCTC). This technique allows larger blocks to be used when smaller blocks provide little gain, saving the bit rates especially for areas containing more complex motion. However, there has been little effort in investigating an efficient VBS motion structure for reducing the motion vector coding rates further. Hence, in this paper, a new VBS motion estimation technique based on a hierarchical structure is proposed, which improves the motion vector encoding efficiency and reduces the number of motion vectors to be transmitted as well. Intensive computer simulations on several moving image sequences show that the MCTC employing the VBS motion estimation provides a performance improvement of 0.7 to approximately 1.0 dB, in terms of PSNR, compared to the fixed block size motion estimation.

In this paper, we propose a new method to design the LOT basis with the view of maximizing the transform coding gain. In our approach, only the linear phase basis is considered, since the nonlinear phase basis is inappropriate to the image coding. The proposed design technique for the LOT basis is mainly based on decomposing the transform matrix into an orthogonal matrix and the prefilter matrix. Based on the decomposition, the prefilter matrix and the orthogonal matrix are designed separately. It is shown that the proposed LOT yields the improved coding gain as compared to the conventional LOT.

A fixed-point-error analysis for several 1D fast DCT algorithms is presented. For comparison, a direct-form approach is also included in the investigation. A statistical model is used as the basis for predicting the fixed-point error in implementing the algorithms, and a suitable scaling scheme is selected to avoid overflow. Closed-form expressions for both the mean and variance for fixed-point error are derived and compared with experimental results. Simulation results show close agreement between theory and experiment, validating the analysis. The results show that one of the algorithms is better than others in terms of average SNR performance. Based on the 1D analysis, attempts are made to investigate the fixed-point-error analysis of the two-column approach for 2D DCT. It is found that the fixed-point-error characteristics of the row-column approach for 2D DCTs is very similar to that of their 1D counterparts.>

An image-coding technique, in which the discrete cosine transform (DCT) is combined with a classified vector quantization (CVQ), is presented. A DCT-transformed input block is classified according to the perceptual feature, partitioned into several smaller vectors, and then vector quantized. An efficient edge-oriented classifier employing the DCT coefficients as feature for classification is used to maintain the edge integrity in the reconstructed image. Based on a smaller geometric mean vector variance, a partition scheme in which 2-D DCT coefficients are divided into several smaller size vectors is also investigated. Because the distortion rate function (DRF) used is essential for the bit allocation algorithm to perform well, attempts have been made to modify the asymptotic DRF to estimate the performance of real VQs at low bit rates, and the modification is shown to be in good agreement with experimental results. Simulation results indicate that a good visual quality of the coded image in the range of 0.4 approximately 0.7 b/pixel is obtained.>

Recently, a novel fast algorithm for 2-D N*N DCT (discrete cosine transform), where N=2/sup m/, was proposed. Only half the number of multiplications required for the conventional row-column approach are needed. However, the relationship between the input-output indices for the postaddition stage in the algorithm is seemingly very irregular. In the present work, the authors derive general and systematic expressions for the relation of the postaddition stage in the 2-D DCT algorithm by representing it in matrix form and developing a method for partitioning the matrices. The results show that the signal flow graph from input to output has a recursive structure where the structure for smaller N appears recursively for larger N. Hence, one can obtain an organized and regular structure for the input-output relation in the postaddition stage.>

A classification algorithm in the discrete cosine transform (DCT) domain for the classified vector quantization (CVQ) technique is proposed. The classifier employs four DCT coefficients of 4*4 subblock as edge-oriented features. The classifier is designed using a cluster-seeking algorithm to ensure that the centroid of a set of vectors in a class always belong to that class. Since the classification is performed in the DCT domain, this approach can be easily extended to the DCT transform coding technique. Simulation results show that a good visual quality of the coded image at fixed rates in the 0.625-0.813 b/pixel (bpp) range is obtained with comparable complexity. The weighted MSE (WMSE) analysis in conjunction with the proposed classifier is discussed.>

An attempt is made at a quantitative understanding of the ALE (adaptive line enhancer) using an adaptive IIR (infinite impulse response) lattice notch filter. The stability of the algorithm is discussed, and an expression for the asymptotic bias of the frequency estimate is provided. The transient behavior of the algorithm is investigated. It is verified by simulation that the analysis substantiates the fast convergent properties shown by N.I. Cho et al. (1989). The cascade structure for retrieving multiple sinusoids is also discussed. The simulation results indicate that the cascade structure based on the lattice ALE algorithm provides results comparable to those described in the recent literature with much less computational complexity (i.e. O(N) versus O(N/sup 2/)), where N is the number of input sinusoids.>

In this paper, we show two basic results to pyramid coding for a progressive image transmission. We first show that in a hierarchical pyramid structure, the transform coding can provide a gain over a simple scalar quantizer. The optimum bit allocation strategy among the Laplacian pyramid for transform coding is also described. Secondly, based on th.e use of transform coding, we show that especially at low bit rates a hierarchical pyramid structure provides a significant gain over encoding of an input image directly. This is particularly attractive to the progressive transmission using a hierarchical pyramid structure.

An image coding technique that combines the discrete cosine transform (DCT) and the classified vector quantizer (CVQ) is described. In this scheme, the DCT domain block is partitioned into vectors and then vector-quantized. The partition of the DCT block into vectors and the CVQ approach result in a much less complex coder than a conventional VQ in the spatial domain. A simple classification algorithm using two DCT coefficients and variance of the input DCT block as features for the classifier is proposed. Adaptive partitioning of the DCT block and bit assignment are found to be essential to achieve the overall goal. With the proposed DCT-CVQ visual quality comparable to that produced by existing coders is demonstrated for rates in the range of 0.45-0.65 bits/pixel.>