Search

The proposed SMRSVC model can provide clear bitrate-reduction and visual merits.Based on the SMRSVC model, we propose a new super-resolution (SR) method.źThe new SR method for the SMRSVC model has superior quality and bitrate performance.ź In this paper, we first propose a new symmetric mixed resolution stereoscopic video coding (SMRSVC) model which can provide clear bitrate-reduction and visual merits. Based on the newly proposed SMRSVC model, we then propose a quality-efficient multiple-example based super-resolution method. In the proposed super-resolution method, the four block examples selected from the forward and backward key-frames, the reference super-resolved frame, and the interview super-resolved frame are referred so as to effectively fuse the high frequency component of the super-resolved current block of the downsampled non-key-frame, and then an enhanced super-resolved non-key-frame is followed. Based on six test stereoscopic video sequences, the experimental results demonstrate that besides the bitrate-saving effect, the proposed super-resolution method for the proposed SMRSVC model also has better quality performance in terms of six well-known quality metrics when compared with several state-of-the-art methods for the previous asymmetric resolution stereoscopic video coding model and the SMRSVC model.

For reducing the cost, most digital cameras are equipped with a CCD or CMOS sensor and a RGB color filter array (CFA) for each pixel to capture one primary color component, and hence produce a mosaic image. Suppose the input mosaic image without the CFA structure information, this paper presents a novel efficient method, consisting of a training-based scheme and an identification scheme, for identifying its CFA structure using the frequency domain approach. Initially, based on a set of training mosaic images with different CFA structures, a training-based scheme is proposed to build up the representative spectrum for every CFA structure. As the model maps, the constructed representative spectra can be reused in subsequent identification processes. The proposed identification scheme first constructs the representative spectrum of the header-less input mosaic image as the query map. Then, a matching scheme is proposed to identify the corresponding CFA structure of the query map from the model maps. Experimental results demonstrate that the proposed identification method has low computational cost and high identification accuracy merits for mosaic images without prior header information, when compared with the state-of-the-art spatial domain-based method by Chiu et al. HighlightsFor the mosaic image without the CFA structure information, we present a frequency domain method for identifying its CFA structure.The proposed method is consisted of a training-based scheme and an identification scheme.Experimental results demonstrate that the proposed identification method has low computational cost and high identification accuracy merits.

Asymmetric multi-view video plus depth based 3D video coding framework.Our proposed coding scheme is specially designed for bitrate-constrained situations.Our proposed coding scheme can significantly reduce the encoding time.The quality of the reconstructed depth video and the virtual view can be improved. Recently, multi-view video plus depth based 3D video (3D-MVD) coding has been studied extensively. This paper presents a fast and efficient asymmetric 3D-MVD coding scheme under specified bitrate constraints. To efficiently encode depth images, a texture image-assisted inter prediction strategy is proposed to determine whether to use a direct copy of the co-located block as the inter prediction so as to skip the normal encoding process. In addition, an adaptive weighted mode in-loop filter strategy is proposed to refine the reconstructed depth image quality. Both strategies help to significantly reduce the encoding time and improve the reconstructed depth image quality under the bitrate constraint. Experiment results showed that the proposed asymmetric 3D-MVD coding scheme does achieve better quality of the reconstructed depth videos and the rendered virtual views at a less encoding-time requirement when compared with the state-of-the-art scheme by Shao et al. and the traditional 5:1 bitrate allocation scheme.

Innovatively modify the Y luma components when performing the subsampling.Our proposed subsampling strategy can resolve the RGB color deviation problem.Our proposed subsampling strategy can achieve better reconstructed video quality. This work proposes an improved version of Yang et al.'s universal subsampling strategy for compressing mosaic videos with arbitrary red-green-blue (RGB) color filter arrays in H.264/AVC. For the subsampled images with 4:2:0 format, Yang et al.'s work retains the original Y luma component, but samples the proper U and V chroma components according to the corresponding mosaic structure for better reconstructing R and B pixels. However, Yang et al.'s strategy suffers from the RGB color deviations due to the U and V chroma subsampling, which results in the quality degradation of the reconstructed mosaic videos. We propose a novel modification for the Y luma component instead of only retaining the Y luma component such that the RGB color deviation problem can be resolved. Experimental results demonstrate that the proposed improved universal subsampling strategy delivers better quality of the reconstructed mosaic and full-color videos, when compared with Yang et al.'s one.

When embedding hidden data in 3D images, conventional reversible data hiding methods, which are designed for 2D gray and color images, can be applied to color and depth maps. However, directly applying these methods to depth maps may cause synthesis errors and lead to visual artifacts in the rendered virtual views. Two novel reversible data hiding methods based on the depth no-synthesis-error (D-NOSE) model are proposed to embed hidden data in the depth maps of 3D images. The proposed methods can preserve the quality of the rendered virtual view and achieve substantially higher embedding capacity. Experimental results show that the proposed methods achieve better performance than the existing state-of-the-art methods in terms of both embedding capacity and the quality of the rendered virtual views.

Using discrete representation of line segments, recently Lee and Park presented an efficient discrete Hough transform (DHT) to improve the robustness of the standard HT (SHT). However, the DHT has much higher computational complexity than the SHT. In this paper, we present an orientation-based DHT (ODHT) which consists of two strategies, the parameter space-selection strategy and the voting space-reduction strategy, to substantially reduce the computational complexity of the DHT. Besides its low computational merit, the proposed ODHT can also improve the detection accuracy of the DHT. Experimental results demonstrated that the proposed ODHT leads to 79.26 % average execution-time improvement ratio and better detection accuracy when compared with the state-of-the-art DHT by Lee and Park.

Currently, two error propagation-free discrete cosine transform (DCT)-based data hiding algorithms, one by Ma et al. and the other by Lin et al., were presented for H.264/AVC intra-coded frames. However, the state-of-the-art video codec, high efficiency video coding (HEVC), adopts both integer DCT and discrete sine transform (DST) such that the previous DCT-based algorithms cannot fully utilize available capacity for data hiding in HEVC. This paper presents the first DCT/DST-based data hiding algorithm for HEVC intra-coded frames where the block DCT and DST coefficient characteristics are investigated to locate the transformed coefficients that can be perturbed without propagating errors to neighboring blocks. Experimental results confirm the merits of the proposed algorithm in providing the intra-frame error propagation-free advantage, the quality improvement for marked images, the compression power inherited from HEVC, and the superiority of embedding capacity for low bitrate coding when compared with the previous two algorithms for H.264/AVC.

In this paper, we propose a novel quality-efficient de-interlacing method for H.264-coded video sequences with various resolutions. In the proposed method, using the syntax elements provided in H.264 bitstreams, four new and efficient strategies are delivered for inter-coded macroblocks to improve the quality of de-interlaced video sequences as well as alleviate the error propagation side effect. Based on the real and generated interlaced video sequences with various common resolutions, experimental results demonstrate the proposed de-interlacing method achieves better quality in terms of both objective and subjective measures when compared with the recently published method by Dong and Ngan.

Compressing mosaic video sequences is necessary for storage and transmission over the internet. However, mosaic video sequences with different red-green-blue (RGB) color filter arrays (CFAs) require different compression schemes. We propose a two-stage universal intra coding scheme for compressing mosaic video sequences with arbitrary RGB-CFAs in high efficiency video coding (HEVC). Based on the associated mosaic structure, the proposed scheme first demosaics the neighboring reference pixels and then predicts the color value of the target pixel using the color values of the identical color components in the demosaiced reference pixels. Experimental results demonstrate that the proposed universal intra coding scheme achieves substantial improvement on bitrate while preserving the quality of the reconstructed video sequences.

Recently, Ma et al. proposed an efficient error propagation-free discrete cosine transform-based (DCT-based) data hiding algorithm that embeds data in H.264/AVC intra frames. In their algorithm, only 46% of the 4x4 luma blocks can be used to embed hidden bits. In this paper, we propose an improved error propagation-free DCT-based perturbation scheme that fully exploits the remaining 54% of luma blocks and thereby doubles the data hiding capacity of Ma et al.'s algorithm. Further, in order to preserve the visual quality and increase the embedding capacity of the embedded video sequences, a new set of sifted 4x4 luma blocks is considered in the proposed DCT-based perturbation scheme. The results of experiments on twenty-six test video sequences confirm the embedding capacity superiority of the proposed improved algorithm while keeping the similar human visual effect in terms of SSIM (structural similarity) index.

Highlights? We develop a new GEDP scheme to reduce the prediction errors. ? We present an RDH algorithm based on GEDP scheme. ? We design a new systematic way to determine the appropriate thresholds. ? We propose an embedding order determination strategy to reduce distortion. ? The proposed algorithm is superior to four state-of-the-art algorithms. In this paper, we present an efficient RDH algorithm based on a new gradient-based edge direction prediction (GEDP) scheme. Since the proposed GEDP scheme can generate more accurate prediction results, the prediction errors tend to form a sharper Laplacian distribution. Therefore, the proposed algorithm can guarantee larger embedding capacity and produce better quality of marked images. The determination of appropriate thresholds is also a critical issue for a RDH algorithm, so we design a new systematic way to tackle this problem. In addition, a modified embedding order determination strategy is presented to reduce the distortion of a marked image. Based on typical test images, experimental results demonstrate the superior properties of the proposed algorithm in terms of embedding capacity and marked image quality.

Randomized approaches for circle detections are often used for the advantages of less computational time and memory requirements. However, randomized approaches involve examining a large number of candidate circles and may not be suitable for real-time applications. In this paper, a screening strategy based on the symmetric property of the circle is adopted to select the promising candidates for further investigation, resulting in substantial reduction in the computational time while maintaining the accuracy. Empirical results show that, under the same accuracy level, the proposed symmetry-based method achieves the improvement ratios of 40%-90% on the execution-time when compared to four state-of-the-art randomized methods.

Binarization plays an important role in document image processing, especially in degraded documents. For degraded document images, adaptive binarization methods often incorporate local information to determine the binarization threshold for each individual pixel in the document image. We propose a two-stage parameter-free window-based method to binarize the degraded document images. In the first stage, an incremental scheme is used to determine a proper window size beyond which no substantial increase in the local variation of pixel intensities is observed. In the second stage, based on the determined window size, a noise-suppressing scheme delivers the final binarized image by contrasting two binarized images which are produced by two adaptive thresholding schemes which incorporate the local mean gray and gradient values. Empirical results demonstrate that the proposed method is competitive when compared to the existing adaptive binarization methods and achieves better performance in precision, accuracy, and F-measure.

In this paper, we present a novel edge sensing-based demosaicing algorithm for digital time delay and integration (DTDI) mosaic images, which are captured by DTDI line-scan cameras and suitable for industrial print inspection. We propose to use Sobel- and interpolation-based masks to extract more accurate gradient information in the color difference domain. The extracted gradient information is utilized to assist the design of the proposed demosaicing algorithm. By experimenting on more than one thousand and three hundred test DTDI mosaic images, the results demonstrate the efficiency of the proposed demosaicing algorithm in terms of demosaiced image quality.

The current major theme in contrast enhancement is to partition the input histogram into multiple sub-histograms before final equalization of each sub-histogram is performed. This paper presents a novel contrast enhancement method based on Gaussian mixture modeling of image histograms, which provides a sound theoretical underpinning of the partitioning process. Our method comprises five major steps. First, the number of Gaussian functions to be used in the model is determined using a cost function of input histogram partitioning. Then the parameters of a Gaussian mixture model are estimated to find the best fit to the input histogram under a threshold. A binary search strategy is then applied to find the intersection points between the Gaussian functions. The intersection points thus found are used to partition the input histogram into a new set of sub-histograms, on which the classical histogram equalization (HE) is performed. Finally, a brightness preservation operation is performed to adjust the histogram produced in the previous step into a final one. Based on three representative test images, the experimental results demonstrate the contrast enhancement advantage of the proposed method when compared to twelve state-of-the-art methods in the literature.

A reversible data hiding algorithm which uses prediction errors in the color difference domain for mosaic images with the Bayer color filter array (CFA) is proposed. Furthermore, the proposed algorithm can be extended to deal with the digital time delay and integration (DTDI) mosaic images and Lukac and Plataniotis (LP) mosaic images. Experimental results on CFA, DTDI, and LP mosaic images demonstrate that the proposed algorithm can achieve high embedding capacity while maintaining good image quality.

Highlights? MSHE is the basis of HE by suppressing the impact of smoother regions in an image. ? MSHE determines the textured regions in an image by a mean-shift based approach. ? MSHE proposes a function to balance the PSNR and Weber's law for termination. This paper presents a novel mean-shift based histogram equalization method called the MSHE method. The key insight of the proposed MSHE method is that the basis of histogram equalization could be based on textured regions in an image, while impact of smoother regions should be suppressed. Using a mean-shift based approach, the sets of textured regions in an image are determined by finding regions which have a high density of edge concentration. In addition, a new cost function is presented to balance the image quality and contrast enhancement effect for search termination in the proposed algorithm. Based on three typical test images, experimental results show that our proposed MSHE method is quite competitive with the previous eleven methods, such as the HE, BBHE, DSIHE, POHE, RSWHE, DHE, BPDHE, SRHE, GHE, FHE, and THShap.

Highlights? We point out two computational bottlenecks in the SOFM-based learning model. ? We propose a pruning-based search strategy for finding winning neurons. ? We propose a LUT-based lateral update interaction. ? Experimental results demonstrate that our proposed method have 35% execution-time improvement ratio in average. Based on the self-organization of Kohonen feature map (SOFM), recently, Pei et al. presented an efficient color palette indexing method to construct a color table for compression. Taking the palette indexing method as a representative, this paper presents two new strategies, the pruning-based search strategy and the lookup table (LUT)-based update strategy, to speed up the learning process in the SOFM. Based on four typical testing images, experimental results illustrate that our proposed two strategies have 35% execution-time improvement ratio in average. The practical improvement ratio is very close to that in the theoretical analysis.

The histogram modification (HM) method proposed by Ni et al. is very efficient for reversible data hiding (RDH). Besides the excellent execution-time performance, Ni et al.’s HM-based RDH (HMRDH) method has a high PSNR lower bound of marked images. In this short communication, an observation on Ni et al.’s HM-based RDH (HMRDH) method is pointed out that the distortion of the marked image from Ni et al.’s method is dependent on the number of 1’s in the watermark. From this observation, we first present a watermark complement scheme to reduce the distortion occurred in Ni et al.’s HMRDH method. Later, combinatorial analysis for average distortion ratio of the proposed scheme is provided. This analysis motivates us to present a block-based complement scheme to improve the distortion reduction further. The tradeoff between the distortion and the number of partitioned blocks is also investigated. Taking nine well-known trademarks as the test watermarks and two cover images with different types of content, experimental results demonstrated the distortion reduction and higher PSNR lower bound advantages of the proposed block-based watermark complement scheme.

Circle detection is fundamental in pattern recognition and computer vision. The randomized approach has received much attention for its computational benefit when compared with the Hough transform. In this paper, a multiple-evidence-based sampling strategy is proposed to speed up the randomized approach. Next, an efficient refinement strategy is proposed to improve the accuracy. Based on different kinds of ten test images, experimental results demonstrate the computation-saving and accuracy effects when plugging the proposed strategies into three existing circle detection methods.

Lookup table-based inverse halftoning (LiH) is a popular approach to reconstruct the gray image from an input halftone image. In this paper, two improved LiH algorithms are presented. We first present a vector- and lookup table-based (VLUT-based) IH algorithm, called the VLIH algorithm, to improve the image quality of the previous LiH algorithm. Different from the previous LiH algorithm which only utilizes the gray value of each pixel to build up the LUT, our proposed VLIH algorithm considers both the gray value of each pixel and its eight neighboring pixels to build up the VLUT. Combining the proposed VLUT and the DCT-based learning scheme, an efficient texture-based VLUT (TVLUT) is built up and it constitutes the kernel of the second proposed IH algorithm called the TVLIH algorithm. Under thirty training images, with satisfactory execution-time requirement, experimental results demonstrate the quality advantage of our proposed VLIH and TVLIH algorithms when compared to the previously published three LiH algorithms.

This research is aimed to devise an anthropomorphic robotic head with a human-like face and a sheet of artificial skin that can read a randomly composed simplified musical notation and sing the corresponding content of the song once. The face robot is composed of an artificial facial skin that can express a number of facial expressions via motions driven by internal servo motors. Two cameras, each of them installed inside each eyeball of the face, provide vision capability for reading simplified musical notations. Computer vision techniques are subsequently used to interpret simplified musical notations and lyrics of their corresponding songs. Voice synthesis techniques are implemented to enable the face robot to sing songs by enunciating synthesized sounds. Mouth patterns of the face robot will be automatically changed to match the emotions corresponding to the lyrics of the songs. The experiments show that the face robot can successfully read and then accurately sing a song which is assigned discriminately.

This paper presents a gradient-based adaptive error diffusion method with edge enhancement effect while preserving the smoothness effect. The proposed method not only can modulate the threshold in halftoning dynamically but also can determine the weights of the error diffusion filter adaptively to diffuse the quantization error to neighboring pixels properly. Under six testing images, experimental results demonstrate that our proposed new error diffusion method has a good compromise between the edge enhancement effect in the halftone image and the image quality effect in the corresponding inverse halftone image when compared to the methods by Floyd-Steinberg, Eschbach and Knox, Hwang et al., Li, and Feng et al., but it has some execution-time degradation.

Recently, Cauchie et al. presented an adaptive Hough transform-based algorithm to successfully solve the center-detection problem which is an important issue in many real-world problems. This paper presents a fast randomized algorithm to solve the same problem. With similar memory requirement and accuracy, the computational complexity analysis and comparison show that our proposed algorithm performs much better in terms of efficiency. We have tested our algorithm on 13 real images. Experimental results indicated that our algorithm has 38% execution-time improvement over Cauchie et al.'s algorithm. The extension of the proposed algorithm to detect multiple centers is also addressed.

For fractal image encoding, based on a special measure called the one-norm of normalized block, this paper presents a novel kick-out method to discard impossible domain blocks in early stage for the current range block. It leads to speed up the encoding time. Since our proposed kick-out method is based on Jacquin's full search method, both methods need to search the whole image and the decoded image quality are the same. Based on five typical testing images, our proposed method has 22% execution time improvement ratio in average when compared with Jacquin's full search method. Combining our proposed method with Truong et al.'s DCT inner product method, Lai et al.'s kick-out method, or both methods, the encoding-time performance can be improved further.

Detecting lines correctly from a digital image is an important crucial step in many real-word applications. In this paper, we present an orientation-based strategy to filter out those inappropriate edge pixels before performing the line-detection task. Due to the effective strategy, both the memory size and the computation time are significantly reduced during a Hough transform-based detection process. Further, the proposed elimination strategy can also speed up the randomized-based detection process. Taking four previously developed line-detection techniques as comparison targets, experimental results have shown that our proposed orientation-based elimination strategy is superior to the previous line-detection methods in terms of memory requirement and computation time.

The recently published edge- and lookup table-based inverse halftoning (ELIH) algorithm has shown its quality and superiority when compared with the previous lookup table-based IH algorithm. This paper presents a new finite state machine model (FSMM)-based search method to speed up the existing ELIH algorithm significantly while preserving the same image quality as in the ELIH algorithm. From the observation that the sliding window for the ELIH algorithm moves from left to right one position; there are therefore one output column and one input column which are introduced at each step and thus a simple finite state machine can track the transitions from the current window movement to the next. This is faster than a full search in the lookup table. Under thirty typical testing images adopted from Meşe’s website, experimental results demonstrated that the proposed FSMM-based ELIH algorithm has an improvement in execution time of 20% to 80%, with a typical improvement of 50%, when compared to the ELIH algorithm.

Binarization is an important basic operation in image processing community. Based on the thresholded value, the gray image can be segmented into a binary image, usually consisting of background and foreground. Given the histogram of input gray image, based on minimizing the within-variance (or maximizing the between-variance), the Otsu method can obtain a satisfactory binary image. In this paper, we first transfer the within-variance criterion into a new mathematical formulation, which is very suitable to be implemented in a fast incremental way, and it leads to the same thresholded value. Following our proposed incremental computation scheme, an efficient heap- and quantization-based (HQ-based) data structure is presented to realize its implementation. Under eight real gray images, experimental results show that our proposed HQ-based incremental algorithm for binarization has 36% execution-time improvement ratio in average when compared to the Otsu method. Besides this significant speedup, our proposed HQ-based incremental algorithm can also be applied to speed up the Kittler and Illingworth method for binarization.

In this paper, a new and efficient edge-preserving algorithm is presented for color contrast enhancement in CIE Lu^'v^' color space. The proposed algorithm not only can enhance the color contrast as the previous algorithm does, but also has an edge-preservation effect. In addition, the spurious edge points occurred due to the color contrast enhancement can be well reduced using the proposed algorithm. This is the first edge-preserving algorithm for color contrast enhancement in color space. Furthermore, a novel color image segmentation algorithm is presented to justify the edge-preservation benefit of the proposed color contrast enhancement algorithm. Based on some real images, experimental results demonstrate the advantages of color contrast enhancement, edge-preservation effect, and segmentation result in our proposed algorithm.

Given a closed curve with n points, based on the local integral square error and the curvature constraint criteria, this paper presents a novel two-pass O(Fn+mn^2)-time algorithm for solving the closed polygonal approximation problem where m(@?n) denotes the minimal number of covering feasible segments for one point and empirically the value of m is rather small, and F (@?n^2) denotes the number of feasible approximate segments. Based on some real closed curves, experimental results demonstrate that under the same number of segments used, our proposed two-pass algorithm has better quality and execution-time performance when compared to the previous algorithm by Chung et al. Experimental results also demonstrate that under the same number of segments used, our proposed two-pass algorithm has better quality, but has some execution-time degradation when compared to the currently published algorithms by Wu and Sarfraz et al.

Video transmission plays an important role in multimedia communication. Due to transmission error; robust video transmission has become increasingly important in providing better quality of services. Based on our proposed novel adaptive estimation scheme, this paper presents an efficient hybrid error concealment algorithm for robust video transmission. Using the information of neighboring macroblocks (MBs) of the corrupted MBs, the corrupted MBs are first classified into three types. According to the type of the corrupted MB, our proposed adaptive estimation scheme could adopt the Bezier surface estimation, the first-order plane estimation, or the centroid of major cluster estimation to conceal the corrupted MB efficiently. Based on six testing video sequences, experimental results demonstrate that our proposed hybrid error concealment algorithm can improve the video quality and the execution-time performance over different loss rates.

Shape detection is a fundamental problem in image processing field. In shape detection, lines, circles, and ellipses are the three most important features. In the past four decades, the robustness and the time speedup are two main concerned issues in most developed algorithms. Previously, many randomized algorithms were developed to speed up the computation of the relevant detection successfully. This paper does focus on the time speedup issue. Based on Bresenham’s drawing paradigm, this paper first presents a novel lookup table (LUT)-based voting platform. According to the proposed LUT-based voting platform, we next present a novel computational scheme to significantly speed up the computation of some existing randomized algorithms for detecting lines, circles, and ellipses. Moreover, the detailed time complexity analyses are provided for the three concerned features under our proposed computational scheme and these derived nontrivial analyses also show the relevant computational advantage. Under some real images, experimental results illustrate that our proposed computational scheme can significantly speed up the computation of some existing randomized algorithms. In average, the execution-time improvement ratios are about 28%, 56%, and 48% for detecting lines, circles, and ellipses, respectively, and these improvement ratios are vary close to the theoretic analyses.

This short communication presents two notes for singular value decomposition (SVD)-based watermarking scheme. The presented notes can increase the invisibility and capacity when embedding the watermark into U and V components of the SVD.

Previously, several efficient Hilbert scan-based operations were presented, but they all suffer from the constraint that the image size must be 2^rx2^r. Considering an image with arbitrary size I"1xI"2, this paper first presents an efficient snake scan-based algorithm for coding the Hilbert curve of the given image. The proposed coding algorithm takes O(k+logU) time to code the Hilbert order of one pixel where k denotes the number of the quadrants and U=min(I"1,I"2). Next, a memory-saving Hilbert curve representation called HCGL is presented for representing the encoded Hilbert curve and it can be constructed in O(L^2logL) time where L=max(I"1,I"2). Based on the HCGL representation of arbitrary-sized image, an application to window query is presented and the proposed window query algorithm takes O(MlogL+P) time where M denotes the number of generated maximal quadtree blocks and P denotes the number of output codes. Under the same PSNR (Peak Signal to Noise Ratio), experimental results demonstrate that our proposed HCGL representation outperforms some existing related algorithms in terms of execution-time and BPP (Bit Per Pixel). In addition, our proposed window query algorithm has been justified in the GIS (Geographical Information System) application.

Based on the recently published point symmetry distance (PSD) measure, this paper presents a novel PSD measure, namely symmetry similarity level (SSL) operator for K-means algorithm. Our proposed modified point symmetry-based K-means (MPSK) algorithm is more robust than the previous PSK algorithm by Su and Chou. Not only the proposed MPSK algorithm is suitable for the symmetrical intra-clusters as the PSK algorithm does, the proposed MPSK algorithm is also suitable for the symmetrical inter-clusters. In addition, two speedup strategies are presented to reduce the time required in the proposed MPSK algorithm. Experimental results demonstrate the significant execution-time improvement and the extension to the symmetrical inter-clusters of the proposed MPSK algorithm when compared to the previous PSK algorithm.

In this paper, a novel hybrid gray image representation using spatial- and DCT-based approach is presented. In the first phase, according to the bintree decomposition principle under the specified error, an S-tree spatial data structure (SDS) is used to represent the decomposed bintree of the input gray image. In the constructed S-tree SDS, the leaves are partitioned into two types, namely the homogeneous leaves and the nonhomogeneous leaves. The homogeneous leaf is used to represent one rectangular or square homogeneous subimage with smooth, i.e., low frequency, content and the nonhomogeneous leaf is used to represent one nonhomogeneous subimage with nonsmooth, i.e., high frequency, content. In the second phase, each nonhomogeneous leaf is encoded by the DCT-based coding scheme for reducing the memory requirement. Based on some real gray images, experimental results show that our proposed gray image representation over the previously published S-tree- and shading-based SDS has about 63.08% memory-saving improvement ratio in average. Finally, we investigate the computational benefit when computing moments on our proposed gray image representation directly.

Recently, Su and Chou presented an efficient point symmetry-based K-means algorithm. Extending their point symmetry-based K-means algorithm, this paper presents a novel line symmetry-based K-means algorithm for clustering the data set with line symmetry property. Based on some real data sets, experimental results demonstrate that our proposed line symmetry-based K-means algorithm is rather encouraging.

Computing lower order moments is important in image processing. Suppose the input grey image with size NxN has been compressed into the block representation where the number of blocks is K, commonly K

Recently, Shen et al. [IEEE Transactions on Image Processing 2003;12:283-95] presented an efficient adaptive vector quantization (AVQ) algorithm and their proposed AVQ algorithm has a better peak signal-to-noise ratio (PSNR) than that of the previous benchmark AVQ algorithm. This paper presents an improved AVQ algorithm based on the proposed hybrid codebook data structure which consists of three codebooks-the locality codebook, the static codebook, and the history codebook. Due to easy maintenance advantage, the proposed AVQ algorithm leads to a considerable computation-saving effect while preserving the similar PSNR performance as in the previous AVQ algorithm by Shen et al. [IEEE Transactions on Image Processing 2003;12:283-95]. Experimental results show that the proposed AVQ algorithm over the previous AVQ algorithm has about 75% encoding time improvement ratio while both algorithms have the similar PSNR performance.

Recently, Webb presented some efficient indexing methods for decoding reversible variable length codes (RVLCs) which are used to encode MPEG-4 DCT coefficients. Given an RVLC, this paper presents two new indexing methods for decoding the RVLCs of MPEG-4 DCT coefficients. Compromising the time requirement, our proposed decoding methods need the least row memory requirement when compared to Webb's methods.

Vector quantization (VQ) is a well-known compression method. In the encoding phase, given a block represented as a vector, searching the closest codeword in the codebook is a time-consuming task. An efficient law-of-cosine-based search algorithm for VQ is presented in this correspondence. In our proposed algorithm, some new formulae and a dynamic rule for selecting the fixed vector are presented to speed up the search process. Experimental results reveal that our proposed search algorithm has better execution-time when compared to the current result by Mielikainen and the previous result by Huang et al.

Recently, a fast spatial combinative lifting algorithm (SCLA) for performing the wavelet transform (WT) was presented by Meng and Wang, and the SCLA speeds up the well-known lifting scheme presented by Daubechies and Sweldens. Employing the concept in the block-based WT by Bao and Kuo, this letter presents an efficient cache-based SCLA (CSCLA) for performing the WT. Theoretically, the number of total arithmetical operations required in the proposed CSCLA is equal to that in the SCLA. Experimental results confirm the computational advantage of our proposed CSCLA when compared to some other previous results. In addition, the VTune Performance Analyzer is used to evaluate the cache performance among the concerning algorithms.

Image segmentation, which partitions the image into homogeneous regions, is a fundamental operation in image processing. Suppose the input gray image with size N × N has been compressed into the compressed image via quadtree and shading representation. Assume that the number of blocks in the representation is B , commonly B N 2 due to the compression effect. This paper first derives some closed forms for computing the mean/variance of any block and for calculating the two statistical measures of any merged region in O (1) time. It then presents an efficient O ( Bα ( B ))-time algorithm for performing region segmentation on the compressed image directly where α ( B ) is the inverse of the Ackerman's function and is a very slowly growing function. With the same time complexity, our results extend the pioneering results by Dillencourt and Samet from the map image to the gray image. In addition, with four real images, experimental results show that our proposed algorithm has about 55.4% execution time improvement ratio when compared to the previous fastest region-segmentation algorithm by Fiorio and Gustedt whose O ( N 2 )-time algorithm is run on the original N × N gray image.

Motion estimation is one of the kernel issues in MPEG series. In this correspondence, a novel two-phase Hilbert-scan-based search algorithm for block motion estimation is presented. First in the intra-phase, a segmentation of the Hilbert curve is applied to the current block, then a novel coarse-to-fine data structure is developed to eliminate the impossible reference blocks in the search window of the reference frame. In the inter-phase, a new prediction scheme for estimating the initial motion vector of the current block is presented. Experimental results reveal that when compared to the GAPD algorithm, our proposed algorithm has better execution time and estimation accuracy performance. Under the same estimation accuracy, our proposed algorithm has better execution time performance when compared to the FS algorithm. In addition, when comparing with the TSS algorithm, our proposed algorithm has better estimation accuracy performance, but has worse execution time performance.

The slope-intercept Hough transform (SIHT) is one of the two types of line-detection methods. However, the disadvantage of the SIHT is its low memory utilization, say 50%. Based on the affine transformation, this paper presents a new method to improve the memory utilization of the SIHT from 50% to 100%. According to the proposed affine transformation, we first present a basic SIHT-based algorithm for detecting lines. Instead of concerning floating-point operations in the basic SIHT-based algorithm, an improved SIHT-based algorithm, which mainly concerns integer operations, is presented. Besides the memory utilization advantage, experimental results reveal that the improved SIHT-based algorithm has more than 60% execution time improvement ratio when compared to the basic SIHT-based algorithm and has more than 33% execution time improvement ratio when compared to another type of line-detection methods, such as the (r,θ)-based HT algorithm and its variant. The detailed complexity analyses for all the related algorithms are also investigated and we show that the time complexity required in the improved SIHT-based algorithm is the least.

Thresholding is a fundamental operation in image processing. Based on the pairwise nearest neighbor technique and the variance criterion, this theme presents two fast adaptive thresholding algorithms. The proposed first algorithm takes O (( m − k ) mτ ) time where k denotes the number of thresholds specified by the user; m denotes the size of the compact image histogram, and the parameter τ has the constraint 1⩽ τ ⩽ m . On a set of different real images, experimental results reveal that the proposed first algorithm is faster than the previous three algorithms considerably while having a good feature-preserving capability. The previous three mentioned algorithms need O ( m k ) time. Given a specific peak-signal-to-noise ratio (PSNR), we further present the second thresholding algorithm to determine the number of thresholds as few as possible in order to obtain a thresholded image satisfying the given PSNR. The proposed second algorithm takes O (( m − k ) mτ + γN ) time where N and γ denote the image size and the fewest number of thresholds required, respectively. Some experiments are carried out to demonstrate the thresholded images that are encouraging. Since the time complexities required in our proposed two thresholding algorithms are polynomial, they could meet the real-time demand in image preprocessing.

Considering a binary image, a new two-phase representation is presented in this paper to reduce the memory requirement in the conventional tree-based spatial data structures (SDSs) such as the linear quadtree, DF-expression, S-tree representation, etc. Experimental results show that not only our proposed two-phase representation has a better memory-saving effect but it also can speed up the coding-time when compared to the existing SDSs. We also show that our proposed two-phase representation has a better computational performance when running geometric operations, such as computing the area and the centroid, on the proposed two-phase representation directly.

Given a polygonal curve P in three-dimensional (3-D) space, the polygonal approximation (PA) problem in this research is to find a polygon P′ to approximate P either with the minimal polygonal segments under a given error or, conversely, with the minimal error under a specified number of segments allowable. The former PA problem is called the PA-# problem; the latter PA problem is called the PA-e problem. Given a 3-D P with n nodes, under the local integral square error criterion, this paper first presents an O(n2)-time algorithm for solving the PA-# problem using O(n) space. Then we present an O(n 2 log n) -time algorithm for solving the PA-e using O(n2) space. Finally, a sampling technique is employed to reduce the memory requirement from O(n2) to O(n). Some experiments are carried out to confirm the theoretical analysis.

In image processing, moments are useful tools for analyzing shapes. Suppose that the input grey image with size N×N has been compressed into the compressed image using the block representation, where the number of blocks used is K, commonly K

Given a compressed image in the restricted quadtree and shading format, this paper presents a fast algorithm for computing 2D discrete cosine transform (DCT) on the compressed grey image directly without the need to decompress the compressed image. The proposed new DCT algorithm takes O(K2logK+N2) time where the decompressed image is of size N×N and K denotes the number of nodes in the restricted quadtree. Since commonly K