Hashing-based methods have gained widespread attention in cross-modal retrieval due to their significant potential for spatiotemporal efficiency and query accuracy, driving significant progress. However, most existing algorithms extract similarity information solely from labels, overlooking the consistent semantic similarities embedded in features. Additionally, some algorithms underutilize label semantics, neglecting inherent category relationships and their interplay with feature semantics, which compromises algorithmic effectiveness. Furthermore, current methods often suffer from weak discriminative power and semantic misalignment when embedding similarity information into hash codes, leading to learning biases. To address these short-comings, a Multi-similarity Preserving Semantic-aware Hashing (MPSH) algorithm is proposed. MPSH first learns a shared semantic space from heterogeneous features to generate dynamic feature fusion similarity. Subsequently, it explores label distributions to construct category vectors, which are collaboratively associated with isomorphic feature representations to form a semantic-aware space. Finally, manifold embedding is employed to effectively preserve multi-similarity and data distribution, yielding semantically rich hash representations. Moreover, a non-relaxed discrete optimization algorithm is introduced to accelerate hash code iteration. Extensive experiments on multiple benchmark datasets, comparing MPSH with leading algorithms, demonstrate its superior efficiency and performance.

Representation learning serves as a critical bridge between human cognition and the data world, constituting an essential component of machine learning architectures where comprehensiveness and flexibility are paramount. However, existing multi-view feature selection methods are constrained by the raw-scale representations, neglecting comprehensive depth-breadth integration and flexible adaptability. This paper presents multi-scale fuzzy fusion-based heterogeneous granular-ball flexible representation learning for multi-view feature selection (MFHGBFR). A comprehensive multi-view, multi-scale analytical foundation is established to promote depth-breadth representation learning, where views represent breadth and scales represent depth in human cognition. Heterogeneous granular ball-based flexible representations are adaptively developed via multi-scale fuzzy fusion, effectively capturing intricate data manifolds and implicit fuzzy patterns across multi-granularity spaces. Intricate data manifolds are fitted with heterogeneous rather than conventional homogeneous structures to improve the adaptability of representations' multi-granularity. Implicit fuzzy patterns are extracted with fuzzy approximation operators to mitigate fuzziness and uncertainty in a multi-granularity space. For the first time, granular-ball representation learning and feature selection are adaptively optimized in a unified one-step framework, rather than the conventional two-step frameworks, for flexible adaptability. An effective optimization algorithm with proven convergence is derived. Through the learned high-quality representations, the MFHGBFR manifests superior performance, robustness, and efficiency. Comparative experiments against contemporary state-of-the-art algorithms substantiate these advantages quantitatively and qualitatively.

Multi-view unsupervised feature selection (MV-UFS) has recently gained significant attention as an effective technique for handling high-dimensional multi-view data. Despite recent progress, three flaws are present in most existing MV-UFS methods. First, they predominantly pay attention to the feature dimensionality while neglecting sample size considerations, typically resulting in cubic time complexity concerning sample size (i.e.$\mathcal {O}(n^{3})$) that hinders them in real-world applications. Second, existing methods primarily focus on the relationships between pairwise views, failing to leverage the complex interactions among multiple views effectively. Third, they generally overlook crucial graph semantic information during graph fusion. An ingenious MV-UFS method is presented in this paper, namedJoint Information Interaction and Semantic Fusion for Multi-View Unsupervised Feature Selection (JIISF), to overcome these limitations. Specifically, JIISF devises a multi-view double reduction learning framework that projects original data into a low-dimensional embedding space and dynamically picks out representative anchors, eliminating redundant information while constructing compact view-specific anchor graphs. Meanwhile, JIISF presents a cross-view information interaction scheme, which enables comprehensive information interaction among multiple views rather than being limited to pairwise views. A semantic alignment fusion strategy is presented to learn a diverse, consistent anchor graph with an explicit semantic alignment module, which can preserve diversity while maintaining consistency. Finally, an alternating optimization algorithm is devised to resolve the proposed JIISF, and experimental results on real-life datasets validate its advantage compared with some state-of-the-art UFS and MV-UFS methods.

Hashing techniques have attracted significant attention in cross-modal retrieval tasks due to their high query efficiency and low storage overhead. However, some methods map heterogeneous features and labels into the same semantic space, ignoring their complementary relationship, which leads to semantic loss. When leveraging pairwise similarity relationships, the affinity matrix incurs high computational costs, and the asymmetric proxy strategy lacks sufficient semantic degrading retrieval performance. Additionally, optimizing binary hash codes remains a challenging task. A novel algorithm, Multi-granularity Semantic Complementarity Fusion Hashing (MSCFH), is proposed to address these issues. First, it learns multi-granularity semantic representations from features and labels, then complements their semantics through a complementarity fusion strategy. Subsequently, an asymmetric semantic learning framework is constructed, guided by label similarities, to learn discriminative hash codes. Furthermore, an efficient discrete optimization algorithm is introduced to update the hash codes. Extensive experiments on three benchmark datasets show that the proposed MSCFH demonstrates the best retrieval accuracy and highly competitive training efficiency compared to state-of-the-art approaches.

Graph-based feature selection methods can capture the most discriminative subset of features in multi-label data and have made great strides in recent years. However, most existing methods have three drawbacks: (1) Only binary pairwise relationship is difficult to capture latent structural information in high-dimensional data fully. (2) Using only one distance metric cannot accurately mine the similarity relationship between instances. (3) Ignore the problem that some of the non-obvious labels are missing when labels are abundant. Therefore, this paper proposes a graph diffusion with dual-distance metrics for missing multi-label feature selection named GDMMFS. GDMMFS uses both Euclidean and cosine distances to explore instance correlations and then uses diffusion techniques to transform binary relationship into quaternary relationship, thus obtaining a stable similarity graph. Moreover, GDMMFS utilizes adaptive graphs to learn latent structure information to improve the model’s immunity to interference. Finally, the ℓ 2 , 1 -norm is used as a sparse constraint to guide the weight matrix to capture the most discriminative subset of features. To further consider the possibility of missing label data, GDMMFS constructed a logic matrix to guide the numerical labels in recovering the missing information. Comparison experiments with state-of-the-art related algorithms demonstrate the superiority of the proposed algorithm, and ablation experiments demonstrate the effectiveness of graph diffusion with two-distance metrics.

Feature selection (FS) is essential in machine learning and data mining as it makes handling high-dimensional data more efficient and reliable. More attention has been paid to unsupervised feature selection (UFS) due to the extra resources required to obtain labels for data in the real world. Most of the existing embedded UFS utilize a sparse projection matrix for FS. However, this may introduce additional regularization terms, and it is difficult to control the sparsity of the projection matrix well. Moreover, such methods may seriously destroy the original feature structure in the embedding space. Instead, avoiding projecting the original data into the low-dimensional embedding space and identifying features directly from the raw features that perform well in the process of making the data show a distinct cluster structure is a feasible solution. Inspired by this, this paper proposes a model called A General Adaptive Unsupervised Feature Selection with Auto-weighting (GAWFS), which utilizes two techniques, non-negative matrix factorization, and adaptive graph learning, to simulate the process of dividing data into clusters, and identifies the features that are most discriminative in the clustering process by a feature weighting matrix Θ. Since the weighting matrix is sparse, it also plays the role of FS or a filter. Finally, experiments comparing GAWFS with several state-of-the-art UFS methods on synthetic datasets and real-world datasets are conducted, and the results demonstrate the superiority of the GAWFS.

Multiview data possess different discriminability in different views, which is challenging to catch but crucial for a feature selection model. Multiscale information, which represents vertical exploration in each view, is vital for further mining traits implied in multiview data. However, most existing studies neglect these beneficial multi-granulation characteristics. This study first embeds the multiscale information into the sparse learning framework for multiview feature selection. A class-specific discriminability and multiscale information-based multiview feature selection (CDMIMFS) method is proposed. It explores the fuzzy and uncertain class-specific discriminability which is inherently discrepant in different views by the fuzzy rough set theory. It relaxes the over strict requirement for complete consistency in multiscale information systems to make a trade-off, which further enhances discriminative feature selection. An effective iteration algorithm is proposed to solve the optimization. Both the theoretical proof and experimental demonstration of convergence are provided. Comprehensive experiments are conducted on the CDMIMFS compared with state-of-the-art algorithms. Results on different evaluation metrics exhibit the advantages of the proposed method.

The inherent characteristics involved in data can be mined from multi-scale information systems by extracting information from different value levels of features. In real applications, noise data and irrelevant or redundant features affect the generality of learning models. Therefore, keeping meaningful features and avoiding the effect of noise is essential for feature selection in a multi-scale information system. In bireduct, multi-scale granulation can be used to characterize the importance and correlation of features at different scales. However, little work has taken the distribution of multi-scale data into account when granulating it. In addition, these approaches focus on solving the task of multi-scale data reduction only from the dimension perspective. To this end, a fuzzy-rough bireduct with supervised multi-scale granulation (FrBSmg) is proposed. First, the supervised multi-scale fuzzy granulation based on data distribution is constructed. Then, scaled uncertainty measures are defined to describe the fuzzy relevance of each feature. Furthermore, the global and local distributions of a sample are characterized simultaneously based on the positive region, which can reflect the degree of a sample belonging to some class, and the supervised fuzzy similarity relation can describe the degree of a sample belonging to its class. A strategy of Feature-Correlated Selection and Sample-Noisy Removal is devised for bireduct. Finally, the experimental results on twenty-one public datasets show the effectiveness of FrBSmg.

Traditional multilabel feature selection (MFS) typically relies on pre-computing global information within the feature space. However, in real-world applications, features are dynamically generated and continuously arrive over time, known as streaming features, rendering many existing approaches ineffective. Some MFS methods for streaming features have been developed, several challenges persist: (1) Previous research often uses certain strategies to model streaming feature evaluation, failing to process fuzzy information effectively; (2) The maximum correlation between features and class is emphasized, while inter-class separability is ignored, leading to inaccurate feature evaluation; (3) The continuous influx of streaming features brings the dynamics and unknowns to data distribution, has been largely overlooked in previous work; (4) Streaming feature selection requires immediate feedback on newly arriving features, posing challenges to the algorithm's real-time responsiveness. Motivated by these observations, this paper introduces a novel online MFS strategy for streaming features. First, the weighted manifold distance is designed, and the fuzzy manifold similarity learning strategy is formalized to analyze the instance relationships of unknown distribution. Second, the fuzzy manifold intra-class correlation and inter-class separability are devised to quantify feature discriminability. Finally, a novel multilabel streaming feature analysis framework is established, with feature discriminability as the guiding factor. Incoming features are categorized as weakly relevant, strongly relevant, or redundant, culminating in generating a reliable feature selection subset. Extensive experiments on fifteen public datasets demonstrate that our algorithm achieves competitive performance compared to nine state-of-the-art offline and online algorithms.

The graph regularized nonnegative matrix factorization (GNMF) algorithms have received a lot of attention in the field of machine learning and data mining, as well as the square loss method is commonly used to measure the quality of reconstructed data. However, noise is introduced when data reconstruction is performed; and the square loss method is sensitive to noise, which leads to degradation in the performance of data analysis tasks. To solve this problem, a novel graph regularized sparse NMF (GSNMF) is proposed in this article. To obtain a cleaner data matrix to approximate the high-dimensional matrix, the$l_{1}$-norm to the low-dimensional matrix is added to achieve the adjustment of data eigenvalues in the matrix and sparsity constraint. In addition, the corresponding inference and alternating iterative update algorithm to solve the optimization problem are given. Then, an extension of GSNMF, namely, graph regularized sparse nonnegative matrix trifactorization (GSNMTF), is proposed, and the detailed inference procedure is also shown. Finally, the experimental results on eight different datasets demonstrate that the proposed model has a good performance.

The performance of multilabel learning depends heavily on the quality of the input features. A mass of irrelevant and redundant features may seriously affect the performance of multilabel learning, and feature selection is an effective technique to solve this problem. However, most multilabel feature selection methods mainly emphasize removing these useless features, and the exploration of feature interaction is ignored. Moreover, the widespread existence of real-world data with uncertainty, ambiguity, and noise limits the performance of feature selection. To this end, our work is dedicated to designing an efficient and robust multilabel feature selection scheme. First, the distribution character of multilabel data is analyzed to generate robust fuzzy multineighborhood granules. By exploring the classification information implied in the data under the granularity structure, a robust multilabel$k$-nearest neighbor fuzzy rough set model is constructed, and the concept of fuzzy dependency is studied. Second, a series of fuzzy multineighborhood uncertainty measures in$k$-nearest neighbor fuzzy rough approximation spaces are studied to analyze the correlations of feature pairs, including interactivity. Third, by investigating the uncertainty measure between feature and label, between features, multilabel data is modeled as a complete weighted graph. Then, these vertices are assessed iteratively to guide the assignment of feature weights. Finally, a graph structure-based robust multilabel feature selection algorithm (GRMFS) is designed. The experiments are conducted on 15 multilabel datasets. The results verify the superior performance of GRMFS as compared with nine representative feature selection methods.

Recently, demand for biometric access controls and online payments in smartphones increased, necessitating further investigation and development in this area. This article proposes a new low-cost palm vein recognition system for smartphones using red, green, blue (RGB) images. First, we detect and enhance palm vein patterns, using the saturation channel instead of the red channel as in the existing approaches. Then, to address the challenging contactless capturing problems of smartphones—such as scale variants, rotation, closed fingers, or rings on hand—we introduce an improved method for the region of interest extraction, based on the convex hull, with a new idea for key vector use. We also designed a new lightweight deep learning-based model for smartphones, which was overlooked in previous palm vein recognition studies. The proposed model comprises suitable blocks of convolution, depthwise separable convolution, inverted residual bottleneck, and spatial pyramid pooling module; in addition, the accuracy is enhanced with fusion strategy. Results show that the proposed model is both smaller and more accurate than related models. The integrated proposed model obtains the best equal error rate, 0.49%, and an inference time of 8 ms.

Face recognition can be installed in a surveillance system so that it can be used for monitoring, tracking and access control. An excellent, intelligent surveillance system should be sensitive to the objects far away from the camera. Unfortunately, due to the long-distance, objects like human faces captured by the camera are too small to identify. As to enhance the subtle color differences in the face image, in this paper we first improve the resolution of the captured image using deep convolution neural networks (DCNNs). Then the efficient features are extracted and used to do classification. As for verifying the effectiveness of the proposed method, we used three databases including AR face database, Georgia Tech face database (GT) database, and Labelled Faces in the Wild (LFW) database, altogether, to conduct the training and testing. Compared to the existing approaches, experimental results show that the identification accuracy of the proposed method outperforms any existing approaches.

Air quality forecasting has been regarded as the key problem of air pollution early warning and control management. In this article, we propose a novel deep learning model for air quality (mainly PM2.5) forecasting, which learns the spatial-temporal correlation features and interdependence of multivariate air quality related time series data by hybrid deep learning architecture. Due to the nonlinear and dynamic characteristics of multivariate air quality time series data, the base modules of our model include one-dimensional Convolutional Neural Networks (1D-CNNs) and Bi-directional Long Short-term Memory networks (Bi-LSTM). The former is to extract the local trend features and spatial correlation features, and the latter is to learn spatial-temporal dependencies. Then we design a jointly hybrid deep learning framework based on one-dimensional CNNs and Bi-LSTM for shared representation features learning of multivariate air quality related time series data. We conduct extensive experimental evaluations using two real-world datasets, and the results show that our model is capable of dealing with PM2.5 air pollution forecasting with satisfied accuracy.

Traffic flow prediction has been regarded as a key research problem in the intelligent transportation system. In this paper, we propose an encoder-decoder model with temporal attention mechanism for multi-step forward traffic flow prediction task, which uses LSTM as the encoder and decoder to learn the long dependencies features and nonlinear characteristics of multivariate traffic flow related time series data, and also introduces a temporal attention mechanism for more accurately traffic flow prediction. Through the real traffic flow dataset experiments, it has shown that the proposed model has better prediction ability than classic shallow learning and baseline deep learning models. And the predicted traffic flow value can be well matched with the ground truth value not only under short step forward prediction condition but also under longer step forward prediction condition, which validates that the proposed model is a good option for dealing with the realtime and forward-looking problems of traffic flow prediction task.

Conventional haze-removal methods are designed to adjust the contrast and saturation, and in so doing enhance the quality of the reconstructed image. Unfortunately, the removal of haze in this manner can shift the luminance away from its ideal value. In other words, haze removal involves a tradeoff between luminance and contrast. We reformulated the problem of haze removal as a luminance reconstruction scheme, in which an energy term is used to achieve a favorable tradeoff between luminance and contrast. The proposed method bases the luminance values for the reconstructed image on statistical analysis of haze-free images, thereby achieving contrast values superior to those obtained using other methods for a given brightness level. We also developed a novel module for the estimation of atmospheric light using the color constancy method. This module was shown to outperform existing methods, particularly when noise is taken into account. The proposed framework requires only 0.55 seconds to process a 1-megapixel image. Experimental results demonstrate that the proposed haze-removal framework conforms to our theory of contrast.

Information fusion is capable of fusing and transforming multiple data derived from different sources to provide a unified representation for centralized knowledge mining that facilitates effective decision-making, classification and prediction, etc. Multisource interval-valued data, characterizing the uncertainty phenomena in the data in the form of intervals in different sources, are the most common symbolic data which widely exist in many real-world applications. This paper concentrates on efficient fusing of multisource interval-valued data with the dynamic updating of data sources, involving the addition of new sources and deletion of obsolete sources. We propose a novel data fusion method based on fuzzy information granulation, which translates multisource interval-valued data into trapezoidal fuzzy granules. Given this effectively fusing capability, we develop incremental mechanisms and algorithms for fusing multisource interval-valued data with a dynamic variation of data sources. Finally, extensive experiments are carried out to verify the effectiveness of the proposed algorithms when comparing to six different fusion algorithms. Experimental results show that the proposed fusion method outperforms other related approaches. Furthermore, the proposed incremental fusion algorithms can reduce the computing overhead in comparison with the static fusion algorithm when adding and deleting multiple data sources.

Attribute reduction based on rough set theory has attracted much attention recently. In real-life applications, many decision tables may vary dynamically with time, e.g., the variation of attributes, objects, and attribute values. The reduction of decision tables may change on the alteration of attribute values. The paper focuses on dynamic maintenance of attribute reduction when varying data values of multiple objects. Incremental mechanisms for knowledge granularity are proposed first, which aims to update attribute reduction effectively. Then, a group incremental reduction algorithm with varying data values is developed. When attribute values of multiple objects have been replaced by new ones in decision table, the proposed incremental algorithm can find the new reduct in a much shorter time. The time complexity analysis and experiments on different data sets from UCI have validated that the proposed incremental algorithms are efficient and effective to update the reduction with the variation of attribute values.

Uncertainty and fuzziness generally exist in real-life data. Approximations are employed to describe the uncertain information approximately in rough set theory. Certain and uncertain rules are induced directly from different regions partitioned by approximations. Approximation can further be applied to datamining-related task, e.g., attribute reduction. Nowadays, different types of data collected from different applications evolve with time, especially new attributes may appear while new objects are added. This paper presents an approach for dynamic maintenance of approximations w.r.t. objects and attributes added simultaneously under the framework of decision-theoretic rough set (DTRS). Equivalence feature vector and matrix are defined first to update approximations of DTRS in different levels of granularity. Then, the information system is decomposed into subspaces, and the equivalence feature matrix is updated in different subspaces incrementally. Finally, the approximations of DTRS are renewed during the process of updating the equivalence feature matrix. Extensive experimental results verify the effectiveness of the proposed methods.

Rule induction method based on rough set theory (RST) has received much attention recently since it may generate a minimal set of rules from the decision system for real-life applications by using of attribute reduction and approximations. The decision system may vary with time, e.g., the variation of objects, attributes and attribute values. The reduction and approximations of the decision system may alter on Attribute Values' Coarsening and Refining (AVCR), a kind of variation of attribute values, which results in the alteration of decision rules simultaneously. This paper aims for dynamic maintenance of decision rules w.r.t. AVCR. The definition of minimal discernibility attribute set is proposed firstly, which aims to improve the efficiency of attribute reduction in RST. Then, principles of updating decision rules in case of AVCR are discussed. Furthermore, the rough set-based methods for updating decision rules in the inconsistent decision system are proposed. The complexity analysis and extensive experiments on UCI data sets have verified the effectiveness and efficiency of the proposed methods.

The security and privacy preservation issues are prerequisites for vehicular ad hoc networks. Recently, secure and privacy enhancing communication schemes (SPECS) was proposed and focused on intervehicle communications. SPECS provided a software-based solution to satisfy the privacy requirement and gave lower message overhead and higher successful rate than previous solutions in the message verification phase. SPECS also presented the first group communication protocol to allow vehicles to authenticate and securely communicate with others in a group of known vehicles. Unfortunately, we find out that SPECS is vulnerable to impersonation attack. SPECS has a flow such that a malicious vehicle can force arbitrary vehicles to broadcast fake messages to other vehicles or even a malicious vehicle in the group can counterfeit another group member to send fake messages securely among themselves. In this paper, we provide a secure scheme that can achieve the security and privacy requirements, and overcome the weaknesses of SPECS. Moreover, we show the efficiency merits of our scheme through performance evaluations in terms of verification delay and transmission overhead.

This paper presents the novel multi-bit watermarking using adaptive embedding algorithms with minimum error. These embedding algorithms can embed multi-bit (k-bit, k≥1 ) logo data into cover data only introduce minimum embedding errors which are restricted to ±(2k-1-1)2i-kaccording to the embedding location i. To achieve the goal of minimum embedding error, we introduced the adaptive embedding algorithms to adaptively evaluate the most similar value to replace the original one and which can be divided into three steps: (1) embed logo data into cover data, (2) adaptively adjust the least-significant bits (LSBs) of cover data, and (3) adaptively adjust the maximum-significant bits (MSBs) of cover data. Thus, we called them as adaptive 3-step embedding algorithms. The proposed embedding algorithms are not only achieving minimum error but also suitable to hardware implementation due to they are bit wise and based on logic, arithmetic and bit operations. Many simulations show that the proposed adaptive 3-step embedding algorithms perform good embedding quality for watermarking applications.

Relay is one of the key technologies used by both the Third Generation Partnership Project (3GPP) Long Term Evolution-Advanced (LTE-Advanced) and IEEE 802.16m to ameliorate cell edge throughput. Despite the throughput enhancement achieved by deploying relay stations (RSs), wireless systems supporting relay are vulnerable to frequent handoffs, which deteriorate the dropping performance of realtime communications. This paper proposes a mathematical model to appraise the dropping performance of the eNB-first channel access policy in LTE-Advanced relay networks. The eNB-first policy prefers an eNB-channel over a RS-channel when determining an access channel for a new and a handoff call. Closed-form analytical result is obtained for the dropping probability of the eNB-first policy and based on the result a numerical study is conducted to evaluate the influences of various parameters on the dropping performance. The result developed in this paper can be used to adjust the call admission control strategies to get acceptable dropping performance in LTE-Advanced relay networks.

Abstract This paper presents the architecture design of a high‐efficient and non‐memory Advanced Encryption Standard (AES) crypto‐core to fit WPAN security requirement. The proposed basis transformation approach from Galois Field (28) to Galois Field GF(((22)2)2) can significantly reduce the hardware complexity of the SubBytes Transformation (S‐box). Besides, the on‐the‐fly key expansion function is used to replace the RAM‐based, and the new on‐the‐fly key scheduler fully supports AES‐128, AES‐192 and AES‐256. Moreover, resource‐sharing scheme will also be employed to reduce the hardware complexity of the cipher and decipher. FPGA experiment results show that the AES core works at 175.75 MHz clock. It takes about 33 clocks and 66 clocks to complete an AES‐128 encryption and decryption, respectively. That is, the corresponding throughputs are 681.7 and 340.85 Mbps. The hardware cost of the AES design is about 2420 slices with 3‐in‐1 key scheduler included. Experiment results also show that the proposed design is suitable for integration into the WPAN chips due to its acceptable power dissipation. Copyright © 2010 John Wiley & Sons, Ltd.

Digital Watermarking technology was introduced in the past few years, not only to ensure the ownership of the digital media, but also to ensure the integrity of those digital media. Reversible watermark (which is also called invertible watermark, or erasable watermark) enables to recover back the original data after the content have been authenticated. Such reversibility is highly desired in some sensitive database applications, e.g. in military and medical data. Permanent distortion is one of the main drawbacks of the entire irreversible relational database watermarking schemes. In this paper, we introduce a novel blind reversible watermarking method that ensures ownership protection in the field of Relational Database watermarking. In the proposed method, we utilize a reversible data-embedding technique called prediction-error expansion on integers to achieve reversibility. The experimental result shows that the blindness and robustness of this approach can defend against several kinds of database attacks.

This paper presents the novel multi-bit bitwise adaptive embedding algorithms for data hiding. These embedding algorithms can embed multi-bit (k-bit, k ≥ 1 ) secret data into cover data only introduce minimum embedding error smaller than (2k-1-1)2i-kaccording to the embedding location i. To achieve such a goal, the proposed embedding algorithm adaptively evaluates the most similar value to replace the original one and which can be divided into three steps: (1) embed logo data into cover data, (2) adaptively adjust the least-significant bits (LSBs) of cover data, and (3) adaptively adjust the maximum-significant bits (MSBs) of cover data. The proposed embedding algorithms are not only achieving minimum error but also suitable to hardware implementation due to it is based on logic, algebraic, and bit operations. Many simulations show that the proposed embedding algorithms perform good embedding quality for watermarking and steganography applications.

Abstract: We present a hybrid model named HRKPG that combines the random‐key search method and an individual enhancement scheme to thoroughly exploit the global search ability of particle swarm optimization. With a genetic algorithm, we can expand the area of exploration of individuals in the solution space. With the individual enhancement scheme, we can enhance the particle swarm optimization and the genetic algorithm for the travelling salesman problem. The objective of the travelling salesman problem is to find the shortest route that starts from a city, visits every city once, and finally comes back to the start city. With the random‐key search method, we can search the ability of the particle and chromosome. On the basis of the proposed hybrid scheme of HRKPG, we can improve solution quality quite a lot. Our experimental results show that the HRKPG model outperforms the particle swarm optimization and genetic algorithm in solution quality.

Radio frequency identification has been developed and used in many applications in the real world. Due to the shared wireless channel between tags and the reader during communication, the tag collision arbitration is a significant issue for reducing the communication overhead. This paper presents a novel anti-collision algorithm named New Enhanced Anti-Collision Algorithm (NEAA) using counters and stack to reduce the probability of collision efficiently and to make it possible to identify multiple passive tags in a timeslot. The upper bound of total timeslots for identifying N passive tags is first derived in this paper; suppose the length of a tag ID is n, the upper bound of total timeslots for identifying N (N= 2n) passive tags is derived to be 2n-1- n + 4, when n > 2. This bound is quite tight. Compared to the existing methods proposed by other researchers, the performance evaluation shows that the proposed scheme in this paper consumes fewer timeslots and has better performance for identifying tags.

This paper presents the architecture design of a high efficient and non-memory Advanced Encryption Standard (AES) crypto core to fit WPAN security requirement. The proposed basis transformation approach from Galois Field (28) to Galois Field GF(((22)2)2) can significantly reduce the hardware complexity of the SubBytes Transformation (S-box). Besides, the on-the-fly key expansion function is used to replace the RAM-based, and the new on-the-fly key scheduler fully supports AES-128, AES-192 and AES-256. Moreover, resource-sharing scheme will also be employed to reduce the hardware complexity of the cipher and decipher. Experiment results show that the AES core works at 100 MHz clock it takes about 400 ns and 770 ns to complete an AES-128 encryption and decryption, respectively. That is, the corresponding throughputs are 320 Mbps and 166 Mbps. The hardware cost of the AES design is about 16.4 K logic cells with 3-in-1 key scheduler included. Experiment results also show that the proposed design is suitable for integration into the WPAN system chips due to its acceptable power dissipation.

In a multimodal biometric system, the effective fusion method is necessary for combining information from various single modality systems. In this paper we examined the performance of sum rule-based score level fusion and support vector machines (SVM)-based score level fusion. Three biometric characteristics were considered in this study: fingerprint, face, and finger vein. We also proposed a new robust normalization scheme (reduction of high-scores effect normalization) which is derived from min-max normalization scheme. Experiments on four different multimodal databases suggest that integrating the proposed scheme in sum rule-based fusion and SVM-based fusion leads to consistently high accuracy.

In this paper, we base on data computing blocks (DCBs) and DCT watchdog technology to implement VLIW watchdog processor. 32-bit final DCT signature (F-DCT-S) and several 5-bit relay DCT signatures (R-DCT-S) will be computed by DCT watchdog scheme. These generated signatures are embedded into the instruction memory and then used to do the run time error checking. We use VLIW processor to simulation. In this paper, the processor degradation can be improved by doing the whole block error checking after the branch instruction, the fault detection latency is improved by doing the intermediate error checking at the R-type instruction, and the memory overhead is reduced by storing the R-DCT-S to the R-type instruction. The experimental results show that the proposed watchdog has a very high error detection coverage and shortest error detection latency to detect either single fault or multi-faults, no matter what the fault is transient or intermittent.

This paper proposes a blind watermarking algorithm based on the significant difference of wavelet coefficient quantization for copyright protection. Every seven nonoverlap wavelet coefficients of the host image are grouped into a block. The largest two coefficients in a block are called significant coefficients in this paper and their difference is called significant difference. We quantized the local maximum wavelet coefficient in a block by comparing the significant difference value in a block with the average significant difference value in all blocks. The maximum wavelet coefficients are so quantized that their significant difference between watermark bit 0 and watermark bit 1 exhibits a large energy difference which can be used for watermark extraction. During the extraction, an adaptive threshold value is designed to extract the watermark from the watermarked image under different attacks. We compare the adaptive threshold value to the significant difference which was quantized in a block to determine the watermark bit. The experimental results show that the proposed method is quite effective against JPEG compression, low-pass filtering, and Gaussian noise; the PSNR value of a watermarked image is greater than 40 dB.

In this paper, a program is first divided into several data computing blocks (DCBs) by the branch instruction; each DCB can then be recognized as an image. We then use the one dimension discrete cosine transform (1-D DCT) to compute each DCB to generate several signatures including 5-bits relay DCT signature (R-DCT-S) and 32-bits final DCT signature (F-DCT-S). These generated signatures are embedded into the instruction memory and then used to do the run time error checking. The watchdog should not reduce the processor performance, not increase the fault detection latency and not increase the memory overhead to store the signatures; in this paper, the processor degradation can be improved by doing the whole block error checking after the branch instruction, the fault detection latency is improved by doing the intermediate error checking at the R-type instruction, and the memory overhead is reduced by storing the R-DCT-S to the R-type instruction. The experimental results show that the proposed watchdog has very high error detection coverage and shortest error detection latency to detect either single fault or multi-faults, no matter what the fault is transient or intermittent.

The problem of spyware is incredibly serious and exceeds anyone's imagination. Combining static and dynamic analyses, we propose an integrated architecture to defend against surveillance spyware in this paper. Features extracted from both static and dynamic analyses are ranked according to their information gains. Then using top significant features we construct a Support Vector Machine (SVM) classifier for each client. In order to keep the classifier update-to-date, there is a machine playing as server to collect reports from all clients, retrain, and redistribute the new classifier to each client. Our surveillance spyware detection system (SSDS) has an overall accuracy rate up to 97.9% for known surveillance spywares and 96.4% for unknown ones.

The paper proposes a new fuzzy data-mining algorithm for extracting interesting knowledge from quantitative transactions stored as object data. Each item itself is thought of as a class, and each item purchased in a transaction is thought of as an instance. Instances with the same class (item name) may have different quantitative attribute values since they may appear in different transactions. The proposed fuzzy algorithm can be divided into two main phases. The first phase is called the fuzzy intra-object mining phase, in which the linguistic large itemsets associated with the same classes (items) but with different attributes are derived. The second phase is called the fuzzy inter-object mining phase, in which the large itemsets are derived and used to represent the relationship among different kinds of objects. Experimental results also show the effects of the proposed algorithm.

Two main goals of our e-mail client system are filtering out junk e-mails and blocking e-mail sent out by malicious code. The famous Ling-Spam Corpus was experimented to show the good performance of our system. Moreover, our system can prevent malicious code impersonating SMTP to send out infected e-mail or secrecy of the computer system.

In this paper, we present a constant time algorithm for solving three dimensional block-based medial axis transform (3D BB-MAT, for short) on the array with reconfigurable optical buses (AROB). The main contribution of this work is to exploit the dominance counting method for solving the 3D BB-MAT that was never done previously in the literature. With the advantages of both optical transmission and electronic computation on the AROB model, the constant algorithm is proposed for the medial axis transform of a 3D N x N x N binary image on a 4D AROB using N^4 processors. To the best of our knowledge, this presented result of the dominance counting technique for medial axis transform of block-based is the best O(1) time algorithm known.

We present two O(1)-time algorithms for solving the 2D all nearest neighbor (2D/spl I.bar/ANN) problem, the 2D closest pair (2D/spl I.bar/CP) problem, the 3D all nearest neighbor (3D/spl I.bar/ANN) problem and the 3D-closest pair (3D/spl I.bar/CP) problem of n points on the linear array with a reconfigurable pipelined bus system (LARPBS) from the computational geometry perspective. The first O(1) time algorithm, which invokes the ANN properties (introduced in this paper) only once, can solve the 2D/spl I.bar/ANN and 2D/spl I.bar/CP problems of n points on an LARPBS of size 1/2n/sup 5/3+c/, and the 3D/spl I.bar/ANN and 3D/spl I.bar/CP problems pf n points on an LARPBS of size 1/2n/sup 7/4+c/, where 0 < /spl epsi/ = 1/2/sup c+1/-1 /spl Lt/ 1, c is a constant and positive integer. The second O(1) time algorithm, which recursively invokes the ANN properties k times, can solve the kD/spl I.bar/ANN, and kD/spl I.bar/CP problems of n points on an LARPBS of size 1/2n/sup 3/2+c/, where k = 2 or 3, 0 < /spl epsi/ = 1/2/sup n+1/-1 /spl Lt/ 1, and c is a constant and positive integer. To the best of our knowledge, all results derived above are the best O(1) time ANN algorithms known.

In this paper, we present algorithms for computing the Euclidean distance transform (EDT) of a binary image on the array with reconfigurable optical buses (AROB). First, we develop a parallel algorithm termed as Algorithm Expander which can be implemented in O(1) time on an AROB with N x Ndelta processors, where delta = 1/k, k is a constant and a positive integer. Algorithm Expander is designed to compute a higher dimensional EDT based on the computed lower dimensional EDT. It functions as a general EDT expander for us to expand EDT from a lower dimension to a higher dimension. We then develop parallel algorithms for the two-dimensional (2-D)_EDT of a binary image array of size N x N in O(1) time on an AROB with N x N x Ndelta processors and for the three-dimensional (3-D)_EDT of a binary image of size N x N x N in O(1) time on an AROB with N x N x N x Ndelta processors. To the best of our knowledge, all results derived above are the best O(1) time algorithms known. We then extend it to compute the nD_EDT of a binary image of size Nn in O(n) time on an AROB with Nn+delta processors. We also apply our parallel EDT algorithms to build Voronoi diagram and Voronoi polyhetra (polygons), to find all maximal empty spheres and the largest empty sphere, and to compute the medial axis transform. All of these applications can be solved in the same time complexity on an AROB with the same number of processors as needed for solving the EDT problems in the same dimensions.

The main contribution of this paper is the design of several efficient algorithms for modified run-length chain coding and for computing a shape's moments on arrays with reconfigurable optical buses. The proposed algorithms are based on the boundary representation of an object. Instead of using chain code, the boundary can be represented by a modified run-length chain code, where each entity represents a line segment (two adjacent corner pixels). The sequential nature of the chain code makes it difficult to be parallelized. We first propose two constant time algorithms for boundary extraction and run-length chain coding. To the authors' knowledge, these are the most time efficient algorithms yet published. Based on the modified run-length chain coding, and the advantages of both optical transmission and electronic computation, a constant time parallel algorithm for computing a shape's moments using N x N processors is proposed. Additionally, instead of using N x N processors, a scalable moment algorithm using r x r processors is also derived, where r < N. Based on the product of time and the number of processors used, both proposed parallel algorithms are time and cost optimal.

In a two- or three-dimensional image array, the computation of Euclidean distance transform (EDT) is an important task. With the increasing application of 3D voxel images, it is useful to consider the distance transform of a 3D digital image array. Because the EDT computation is a global operation, it is prohibitively time consuming when performing the EDT for image processing. In order to provide the efficient transform computations, parallelism is employed. We first derive several important geometry relations and properties among parallel planes. We then, develop a parallel algorithm for the three-dimensional Euclidean distance transform (3D-EDT) on the EREW PRAM computation model. The time complexity of our parallel algorithm is O(log/sup 2/ N) for an N/spl times/N/spl times/N image array and this is currently the best known result. A generalized parallel algorithm for the 3D-EDT is also proposed. We implement the proposed algorithms sequentially, the performance of which exceeds the existing algorithms (proposed by Yamada, 1984). Finally, we develop the corresponding parallel programs on both the emulated EREW PRAM model computer and the IBM SP2 to verify the speed-up properties of the proposed algorithms.

We develop a parallel algorithm for the 2D Euclidean distance transform (2D/spl I.bar/EDT, for short) of a binary image of size N /spl times/ N in O(1) time using N/sup 2+/spl delta/+/spl epsi// CRCW processors and a parallel algorithm for the 3D Euclidean distance transform (3D/spl I.bar/EDT, for short) of a binary image of size N /spl times/ N /spl times/ N in O(1) time using N/sup 3+/spl delta/+/spl epsi// CRCW processors, where /spl delta/=1/, /spl epsi/=1/(2/sup c+1/-1), h, and are constants and positive integers. Our 2D/spl I.bar/EDT (3D/spl I.bar/EDT) parallel algorithm can be used to build up Voronoi diagram and Voronoi polygons (polyhedra) in a 2D (3D) binary image also. All of these parallel algorithms can be performed in O(1) time using N/sup 2+/spl delta/+/spl epsi// (N/sup 3+/spl delta/+/spl epsi//) CRCW processors. To the best of our knowledge, all results derived above are the best O(1) time algorithms known.

The main contributions of this paper are in designing fast and scalable parallel algorithms for selection and median filtering. Based on the radix-/spl omega/ representation of data and the prune-and-search approach, we first design a fast and scalable selection algorithm on the arrays with reconfigurable optical buses (AROB). To the authors' knowledge, this is the most time efficient algorithm yet published, especially compared to the algorithms proposed by Han et al (2002) and Pan (1994). Then, given an N /spl times/ N image and a W /spl times/ W window, based on the proposed selection algorithm, several scalable median filtering algorithms are developed on the AROB model with a various number of processors. In the sense of the product of time and the number of processors used, most of the proposed algorithms are time or cost optimal.

The computation model on which the algorithms are developed is the reconfigurable array of processors with wider bus networks (abbreviated to RAPWBN). The main difference between the RAPWBN model and other existing reconfigurable parallel processing systems is that the bus width of each network is bounded within the range [2,[/spl radic/(N)]]. Such a strategy not only saves the silicon area of the chip as well as increases the computational power enormously, but the strategy also allows the execution speed of the proposed algorithms to be tuned by the bus bandwidth. To demonstrate the computational power of the RAPWBN, the channel-assignment problem is derived in this paper. For the channel-assignment problem with N pairs of components, we first design an O(T + [N//spl omega/]) time parallel algorithm using 2N processors with a 2N-row by 2N-column bus network, where the bus width of each bus network is /spl omega/-bit for 2 /spl les/ /spl omega/ /spl les/ [/spl radic/N] and T = [log/sub /spl omega//N] + 1. By tuning the bus bandwidth to the natural log N-bit and the extended N/sup 1/c/-bit (N/sup 1/c/ > log N) for any constant c and c /spl ges/ 1, two more results which run in O(log N/log log N) and O(1) time, respectively, are also derived. When compared to the algorithms proposed by Olariu et al. [17] and Lin [14], it is shown that our algorithm runs in the equivalent time complexity while significantly reducing the number of processors to O(N).

In a two or three-dimensional image array, the computation of Euclidean distance transform (EDT) is an important task. With the increasing application of 3D voxel images, it is useful to consider the distance transform of a 3D digital image array. Because the EDT is a global operation, it is prohibitively time consuming when performing the EDT for image generation. In order to provide the efficient transform computations, parallelism is employed. In this paper we first derive several important geometry relations and properties among parallel planes. We then develop a parallel algorithm for the three-dimensional Euclidean distance transform (3D-EDT) on the EREW PRAM computation model. The time complexity of our parallel algorithm is O(log/sup 2/ N) for an N/spl times/N/spl times/N image array.

The main contribution of this paper is the design of several efficient algorithms for modified run-length chain coding and for computing shape's moments on arrays with reconfigurable optical buses. We first propose two constant time algorithms for boundary extraction and run-length chain coding. Based on the modified run-length chain coding, and the advantages of both optical transmission and electronic computation, a constant time parallel algorithm for computing shape's moments using N/spl times/N processors is proposed. Based on the product of time and the number of processors used, the proposed parallel algorithms are time and cost optimal.

In spite of their good filtering characteristics for vector-valued image processing, the usability of vector median filters is limited by their high computational complexity. Given an N /spl times/ N image and a W /spl times/ W window, the computational complexity of vector median filter is O(W/sup 4/N/sup 2/). In this paper, we design three fast and efficient parallel algorithms for vector median filtering based on the 2-norm (L/sub 2/) on the arrays with reconfigurable optical buses (AROB). For 1 /spl les/ p /spl les/ W /spl les/ q /spl les/ N, our algorithms run in O(W/sup 4/ log W/p/sup 4/), O(W/sup 2/N/sup 2//p/sup 4/q/sup 2/ log W) and O(1) times using p/sup 4/N/sup 2/ / log W, p/sup 4/q/sup 2/ / log W, and W/sup 4/N/sup 2/ log N processors, respectively. In the sense of the product of time and the number of processors used, the first two results are cost optimal and the last one is time optimal.

Computing the moments of a two-dimensional (2-D) image involves a significant amount of multiplications and additions in a direct method. In this paper, we use the suffix sums to compute the 2-D moments instead of using a direct method. This method can reduce the number of multiplications tremendously. By integrating the advantages of both optical transmission and electronic computation, the 2-D moments can be computed in constant time on a 2-D arrays with reconfigurable optical buses (AROB). This result achieves optimal speed-up.

Thresholding is the most commonly used technique in image segmentation. We first propose an efficient sequential algorithm to improve the relative entropy-based thresholding technique. This algorithm combines the concepts of the relative entropy with that of the local entropy and also includes the quadtree hierarchical structure in it. Second, we derive a constant time parallel algorithm to solve this problem on the reconfigurable array of processors with wider bus networks (RAPWBN). The system bus bandwidth determines the capacity of data communication between processors. According to the results as shown by Li and Maresca (1989) and by Maresca and Li (1989), we know that the silicon area used by the switching control mechanism is far less than that used by the processor. Instead of increasing the number of processors, we extend the number of buses to increase the power of a parallel processing system. Such a strategy of utilizing the reconfigurable array of processors with wider bus networks not only has the advantage of saving silicon area but also increases the system power enormously. So, we use the RAPWBN to solve the entropy-based thresholding problem.

With increasing security threats in internet environments, we may therefore want to establish a secure mechanism for data transmissions on each network. This paper presents a mechanism for establishing secure switching local area networks (LANs) by using intelligent switching hubs. Then we can achieve secure internet environments by means of the proposed switching LANs and firewalls. The proposed intelligent switching hub can easily be implemented and it has a short delay time. Also the switching LAN structure proposed in this paper is constructed using a symmetric tree, where the leaves represent user stations, the internal nodes represent intelligent switching hubs, and the links between any pair of nodes (or any pair of node and station) represent full-duplex communication connections. By using the proposed intelligent switching hubs and the link encryption technique, such a switching LAN can prevent eavesdropping and unauthorized access by restricting data delivery and stopping unauthorized users from adding devices to the network to get data. Moreover, it can allow simultaneous communications to exist in different parts of the network, and can isolate certain user stations or subnetworks so that many data transmissions can be simultaneously and securely accomplished.

Clustering techniques are usually used in pattern recognition, image segmentation and object detection. For N patterns and k centers each with M features, in this paper, we first design an O(kM) time optimal parallel algorithm for one pass process of clustering with the k-means method on a linear array of processors with a wider bus network using N/sup 1+1/c/ processors with one bus network, where c is any constant and c/spl ges/1. Then, based on the proposed algorithm, two O(k) and O(1) time optimal parallel clustering algorithms are also derived using MN/sup 1+1/c/ and kMN/sup 1+1/c/ processors with M row and MN row bus networks, respectively. These results improve the best known bounds and achieve cost optimal in their time and processor complexities.

Based on a geometric method, this paper presents an efficient and authenticated cryptoscheme for establishing secure group-oriented data communications in Internet environments. We assume that the Internet environments consist of many hosts, and each host has many users attached to it. The secure group-oriented communication scheme proposed in this paper incorporates the public-key distribution and the trigonometry concepts as the basic theory. Since this scheme does not need any trusted key distribution center to distribute the common secret session key between two parties and can reduce the computation time needed for securely sending messages to a group of receivers by using multiplication operations instead of modular exponentiation, it is quite suitable to be used in Internet environments so that the key distribution is convenient, time-saving and reparable. Furthermore, an authentication protocol is also proposed. Such a protocol can not only identify both the sender and the receiver of a group correctly, but can also make sure the transmitted message has reached its destination safely.

The generalized Fibonacci cubes (abbreviated to GFCs) were recently proposed as a class of interconnection topologies, which cover a spectrum ranging from regular graphs such as the hypercube to semiregular graphs such as the second order Fibonacci cube. It has been shown that the kth order GFC of dimension n+k is equivalent to an n-cube for 0/spl les/n

The parallel computation model upon which the proposed algorithms are based is the hyper-bus broadcast network. The hyper-bus broadcast network consists of processors which are connected by global buses only. Based on such an improved architecture, we first design two O(1) time basic operations for finding the maximum and minimum of N numbers each of size O(log N)-bit and computing the matrix multiplication operation of two N/spl times/N matrices, respectively. Then, based on these two basic operations, three of the most important instances in the algebraic path problem, the connectivity problem, and several related problems are all solved in O(log N) time. These include the all-pair shortest paths, the minimum-weight spanning tree, the transitive closure, the connected component, the biconnected component, the articulation point, and the bridge problems, either in an undirected or a directed graph, respectively.

In this paper, based on the diagonal propagation approach, we first provide an O(N/sup 2/) time sequential algorithm to compute the chessboard distance transform (CDT) of an N/spl times/N image, which is a DT using the chessboard distance metrics. Based on the proposed sequential algorithm, the CDT of a 2-D binary image array of size N/spl times/N can be computed in O (log N) time on the EREW PRAM model using O(N/sup 2//log N) processors, O(log N/log log N) time on the CRCW PRAM model using O(N/sup 2/log log N/log N) processors and O(log N) time on the hypercube computer using O(N/sup 2/) processors. Following the mapping as proposed by Y.H. Lee and S.J. Horng (1995), the algorithm for the MAT is also efficiently derived. The medial axis transform of a 2-D binary image array of size N/spl times/N can be computed in O(log N) time on the EREW PRAM model using O(N/sup 2//log N) processors, O(log N/log log N) time on the CRCW PRAM model using O(N/sup 2/log log N/log N) processors, and O(log N) time on the hypercube computer using O(N/sup 2/) processors. Our algorithms are faster than the best previous results as proposed by J.F. Jenq and S. Sahni (1992).

This paper presents efficient protocols for establishing secure group-oriented communication channels in Internet environments based on a geometric method. Since the data encryption/decryption requires a common secret session key between two communicating parties, finding an efficient way to distribute the group-oriented secret session key in Internet environments has become a nontrivial task. We assume that the Internet environments consist of many hosts, and each host has many users attached to it. The scheme proposed in this paper incorporates the public-key distribution and the trigonometry concepts as the basic theory. Since this scheme does not need any trusted key distribution center to distribute the common secret session key between two groups, it is quite suitable to be used in Internet environments so that the key distribution is convenient, time-saving and reparable. Furthermore, an authentication protocol is also proposed. Such a protocol can not only identify both the sender and the receiver of a group correctly but also make sure that the transmitted message reaches its destination safely.

With increasingly complicated distributed software we must do our best to establish a maintenance mechanism. The paper presents generalized software complexity metrics for measuring the computational complexity of distributed programs, and introduces the notion of communication complexity unit based on the smallest process communication group. We affirm that the smallest process communication group is a unifying mechanism for event and process abstraction whatever distributed programming languages are used and advocate it as a basically generalized communication complexity unit.

A cross-bridge reconfigurable array of processors is a parallel processing system which has the ability to change dynamically the supported interconnection scheme during the execution of an algorithm. Based on this architecture, several O(1) time basic operations such as the transpose, the untranspose, the shift, the unshift and the prefix sum of a binary sequence are first proposed. Then, these basic operations can be used to find the kth smallest element of N m bits unsigned integers in O(m) time using N processors and to sort N data items in O(1) time using O(N/sup 5/3/) processors instead of using O(N/sup 2/) processors as those proposed by other researchers.>

In this paper, instead of using the base-2 number system, we use a base-m number system to represent the numbers used in the proposed algorithms. Such a strategy can be used to design an O(T) time, T=[log/sub m/N]+1, prefix sum algorithm for a binary sequence with N-bit on a cross-bridge reconfigurable array of processors using N processors, where the data bus is m-bit wide. Then, this basic operation can be used to compute the histogram of an n/spl times/n image with G gray-level value in constant time using G/spl times/n/spl times/n processors, and compute the Hough transform of an image with N edge pixels and n/spl times/n parameter space in constant time using n/spl times/n/spl times/N processors, respectively. This result is better than the previously known results. Also, the execution time of the proposed algorithms is tunable by the bus bandwidth.>

Let /spl oplus/ be an associative operation on a domain D. The semigroup problem is to compute a/sub 0//spl oplus/a/sub 1//spl oplus/...a/sub N-1/, where a/sub i/ /spl isin/D, for 0/spl les/i

This paper makes an improvement of computing the list ranking and some related problems on a reconfigurable array of processors (abbreviated to RAP) with wider bus networks by increasing the bus width between processors. Based on such an architecture and a base-n system technique, a constant time basic operation is first introduced for computing the prefix modular n and prefix division n computations of an N-bit binary sequence on a linear RAP using N processors. Then, several fundamental problems can be solved in a constant time on a RAP using N/sup 1+1/c/ processors with N/spl times/N/sup 1+1/c/ bus networks and each bus network with N/sup 1/c/-bit, where c is a constant and e/spl ges/1. These algorithms include the prefix sum of N integers problem, the weight list ranking problem, the Euler tour problem and the tree recursions problem, respectively. Another contribution of this paper is that the execution time of the proposed algorithms is tunable by the bus width.

We show that determine the maximum number of vertex connectivity, test k-vertex connectivity and determine the maximum number of vertex disjoint I_s - l_t paths of interval graphs can be solved either in O(log n) time using O{n) processors for the Unsorted case or in O{logn) time using O{n/logn) processors for the sorted case, and find k-vertex disjoint I_s - I_t paths of interval graphs can be solved in O{k logn) time using O{n^{2}/logn) processors on the EREW PRAM model, respectively. All parallel algorithms are optimal with respect to the time-processor product except the last one.

A reconfigurable array of processors (RAP) is a parallel processing system which has the ability to change dynamically the supported interconnection scheme during the execution of an algorithm.

A reconfigurable array of processors (RAP) is defined to be an array of processors connected to a reconfigurable bus system whose configurations can be dynamically changed. For an n×n image and m×mtemplate, a constant time algorithm for template matching is proposed on a RAP with m×m×n×n×n processors when the domain of the image and the template is Boolean. Even if the domain is integer and each integer is bounded and represented by a q-bits binary sequence, a constant or O(log* m) time algorithm is still obtained. The number of processors needed is increased to 2qm2×2qm2×max {m,n}×n×n and m2×m2×max {m2,n}×n×n, respectively. An O(log m) times algorithm also derived for the domain is integer or real but the number of processors is reduced to m×m×n×n×n.