Segmentation of lip region in color images by fuzzy clustering

Extraction of the lip region is essential to lip reading, which is a field of image processing that is used to obtain meaningful information by the analysis of lip movement from human face images. Many conventional methods for extraction of the lip region have been proposed. One is to identify the lip position by using geometric face structure. Another discriminates lip and skin regions by using color information only. The former is more complex than the latter; however, it can analyze black and white images as well as color images. The latter is simpler than the former; however, it is difficult to discriminate lip and skin regions because of the high similarity between these two regions, and it is less accurate than the former. Conventional methods usually analyze color coordinate systems to extract lip regions rather than analyzing the coordinate system itself. In this paper, the best color coordinate system for lip extraction was selected by the analysis of discriminability. Segmentation of the lip region with this coordinate system and a new feature vector are proposed.     

Segmentation of color lip images by spatial fuzzy clustering

In this paper, we describe the application of a novel spatial fuzzy clustering algorithm to the lip segmentation problem. The proposed spatial fuzzy clustering algorithm is able to take into account both the distributions of data in feature space and the spatial interactions between neighboring pixels during clustering. By appropriate pre- and postprocessing utilizing the color and shape properties of the lip region, successful segmentation of most lip images is possible. Comparative study with some existing lip segmentation algorithms such as the hue filtering algorithm and the fuzzy entropy histogram thresholding algorithm has demonstrated the superior performance of our method.     

Unsupervised multiscale segmentation of color images

This paper proposes a new multiresolution technique for color image representation and segmentation, particularly suited for noisy images. A decimated wavelet transform is initially applied to each color channel of the image, and a multiresolution representation is built up to a selected scale 2^J. Color gradient magnitudes are computed at the coarsest scale 2^J, and an adaptive threshold is used to remove spurious responses. An initial segmentation is then computed by applying the watershed transform to thresholded magnitudes, and this initial segmentation is projected to finer resolutions using inverse wavelet transforms and contour refinements, until the full resolution 2⁰ is achieved. Finally, a region merging technique is applied to combine adjacent regions with similar colors. Experimental results show that the proposed technique produces results comparable to other state-of-the-art algorithms for natural images, and performs better for noisy images.     

Protein synthesis profiling in the developing brain: a graph theoretic clustering approach

Mapping regional brain development in terms of protein synthesis (PS) activity yields insight on specific spatio-temporal ontogenetic patterns. The biosynthetic activity of an individual brain nucleus is represented as a time-series object, and clustering of time-series contributes to the problem of inducing indicative patterns of brain developmental events and forming respective PS chronological maps. Clustering analysis of PS chronological maps, in comparison with epigenetic influences of alpha2 adrenoceptors treatment, reveals relationships between distantly located brain structures. Clustering is performed with a novel graph theoretic clustering approach (GTC). The approach is based on the weighted graph arrangement of the input objects and the iterative partitioning of the corresponding minimum spanning tree. The final result is a hierarchical clustering-tree organization of the input objects. Application of GTC on the PS patterns in developing brain revealed five main clusters that correspond to respective brain development indicative profiles. The induced profiles confirm experimental findings, and provide evidence for further experimental studies.     

Segmentation of small objects in color images

A method for effective segmentation of small objects in color images is presented. It can be used jointly with region growing algorithms. Segmentation of small objects in color images is a difficult problem because their boundaries are close to each other. The proposed algorithm accurately determines the location of the boundary points of closely located small objects and finds the skeletons (seed regions) of those objects. The method makes use of conditions obtained by analyzing the change of color characteristics of the edge pixels along the direction that is orthogonal to the boundaries of adjacent objects. These conditions are generalized for the case of the well-known class of color images having misregistration artifacts. If high-quality seed regions are available, the final segmentation can be performed using one of the region growing methods. The segmentation algorithm based on the proposed method was tested using a large number of color images, and it proved to be very efficient.     

A comparison of the stability characteristics of some graph theoretic clustering methods

Assessing the stability of a clustering method involves the measurement of the extent to which the generated clusters are affected by perturbations in the input data. A measure which specifies the disturbance in a set of clusters as the minimum number of operations required to restore the set of modified clusters to the original ones is adopted. A number of well-known graph theoretic clustering methods are compared in terms of their stability as determined by this measure. Specifically, it is shown that among the clustering methods in any of several families of graph theoretic methods, clusters defined as the connected components are the most stable and the clusters specified as the maximal complete subgraphs are the least stable. Furthermore, as one proceeds from the method producing the most narrow clusters (maximal complete subgraphs) to those producing relatively broader clusters, the clustering process is shown to remain at least as stable as any method in the previous stages. Finally, the lower and the upper bounds for the measure of stability, when clusters are defined as the connected components, are derived.     

Collusion set detection using graph clustering

Many mal-practices in stock market trading—e.g., circular trading and price manipulation—use the modus operandi of collusion. Informally, a set of traders is a candidate collusion set when they have “heavy trading” among themselves, as compared to their trading with others. We formalize the problem of detection of collusion sets, if any, in the given trading database. We show that naïve approaches are inefficient for real-life situations. We adapt and apply two well-known graph clustering algorithms for this problem. We also propose a new graph clustering algorithm, specifically tailored for detecting collusion sets. A novel feature of our approach is the use of Dempster–Schafer theory of evidence to combine the candidate collusion sets detected by individual algorithms. Treating individual experiments as evidence, this approach allows us to quantify the confidence (or belief) in the candidate collusion sets. We present detailed simulation experiments to demonstrate effectiveness of the proposed algorithms.     

The synthesis and analysis of color images

I describe a method for performing the synthesis and analysis of digital color images. The method is based on two principles. First, image data are represented with respect to the separate physical factors, surface reflectance and the spectral power distribution of the ambient light, that give rise to the perceived color of an object. Second, the encoding is made efficient by using a basis expansion for the surface spectral reflectance and spectral power distribution of the ambient light that takes advantage of the high degree of correlation across the visible wavelengths normally found in such functions. Within this framework, the same basic methods can be used to synthesize image data for color display monitors and printed materials, and to analyze image data into estimates of the spectral power distribution and surface spectral reflectances. The method can be applied to a variety of tasks. Examples of applications include the color balancing of color images and the identification of material surface spectral reflectance when the lighting cannot be completely controlled.     

Correcting show-through effects on scanned color document images by multiscale analysis

This paper describes a new approach to restoring scanned color document images where the backside image shows through the paper sheet. A new framework is presented for correcting show-through components using digital image processing techniques. First, the foreground components on the front side are separated from the background and backside components through locally adaptive binarization for each color component and edge magnitude thresholding. Background colors are estimated locally through color thresholding to generate a restored image, and then corrected adaptively through multi-scale analysis along with comparison of edge distributions between the original and the restored image. The proposed method does not require specific input devices or the backside to be input; it is able to correct unneeded image components through analysis of the front side image alone. Experimental results are given to verify effectiveness of the proposed method.     

Sub-optimal solutions to track detection problem using graph theoretic concepts

This paper demonstrates how the problem of tracking targets, which appear as either straight or curved lines in two-dimensional display images (or data images) can be formulated in terms of a directed weighted graph model and how dynamic programming techniques can be efficiently applied to reach an optimal or sub-optimal solution. In general, track detection algorithms providing optimal solutions have good detective ability, but most of them suffer from the inability to detect discontinuous lines or to resolve efficiently pairs of crossing lines. A sub-optimal solution is provided that efficiently overcomes these weaknesses. We focus on modeling the track detection problem in terms of a graph, formulating fast sequential/parallel sub-optimal track detection algorithms and testing them on simulated data in order to show their detective ability. Moreover, we specify the conditions under which sub-optimal algorithms can perform at least as well as their corresponding optimal algorithms. This is significant for the track detection problem where fast, accurate and real-time detection is considered a necessity.     

An FPGA implementation of real-time K-means clustering for color images

K-means clustering is a very popular clustering technique, which is used in numerous applications. In the k-means clustering algorithm, each point in the dataset is assigned to the nearest cluster by calculating the distances from each point to the cluster centers. The computation of these distances is a very time-consuming task, particularly for large dataset and large number of clusters. In order to achieve high performance, we need to reduce the number of the distance calculations for each point efficiently. In this paper, we describe an FPGA implementation of k-means clustering for color images based on the filtering algorithm. In our implementation, when calculating the distances for each point, clusters which are apparently not closer to the point than other clusters are filtered out using kd-trees which are dynamically generated on the FPGA in each iteration of k-means clustering. The performance of our system for 512 × 512 and 640 × 480  pixel images (24-bit full color RGB) is more than 30 fps, and 20–30 fps for 756 × 512 pixel images in average when dividing to 256 clusters.

Extraction of spots in biological images using multiscale products

We present a new method to detect and count bright spots in fluorescence images coming from biological immunomicroscopy experiments. It is based on the multiscale product of subband images resulting from the à trous wavelet transform decomposition of the original image, after thresholding of non-significant coefficients. The multiscale correlation of the filtered wavelet coefficients, which allows to enhance multiscale peaks due to spots while reducing noise, combines information coming from different levels of resolution and gives a clear and distinctive chacterization of the spots. Results are presented for the analysis of typical immunofluorescence images.     

An optimal graph theoretic approach to data clustering: theory andits application to image segmentation

A novel graph theoretic approach for data clustering is presented and its application to the image segmentation problem is demonstrated. The data to be clustered are represented by an undirected adjacency graph 𝒢 with arc capacities assigned to reflect the similarity between the linked vertices. Clustering is achieved by removing arcs of 𝒢 to form mutually exclusive subgraphs such that the largest inter-subgraph maximum flow is minimized. For graphs of moderate size (~ 2000 vertices), the optimal solution is obtained through partitioning a flow and cut equivalent tree of 𝒢, which can be efficiently constructed using the Gomory-Hu algorithm (1961). However for larger graphs this approach is impractical. New theorems for subgraph condensation are derived and are then used to develop a fast algorithm which hierarchically constructs and partitions a partially equivalent tree of much reduced size. This algorithm results in an optimal solution equivalent to that obtained by partitioning the complete equivalent tree and is able to handle very large graphs with several hundred thousand vertices. The new clustering algorithm is applied to the image segmentation problem. The segmentation is achieved by effectively searching for closed contours of edge elements (equivalent to minimum cuts in 𝒢), which consist mostly of strong edges, while rejecting contours containing isolated strong edges. This method is able to accurately locate region boundaries and at the same time guarantees the formation of closed edge contours     

Fast agglomerative clustering using a k-nearest neighbor graph

We propose a fast agglomerative clustering method using an approximate nearest neighbor graph for reducing the number of distance calculations. The time complexity of the algorithm is improved from O(tauN²) to O(tauN log N) at the cost of a slight increase in distortion; here, tau denotes the lumber of nearest neighbor updates required at each iteration. According to the experiments, a relatively small neighborhood size is sufficient to maintain the quality close to that of the full search     

Information theoretic clustering using a k-nearest neighbors approach

We develop a new non-parametric information theoretic clustering algorithm based on implicit estimation of cluster densities using the k-nearest neighbors (k-nn) approach. Compared to a kernel-based procedure, our hierarchical k-nn approach is very robust with respect to the parameter choices, with a key ability to detect clusters of vastly different scales. Of particular importance is the use of two different values of k, depending on the evaluation of within-cluster entropy or across-cluster cross-entropy, and the use of an ensemble clustering approach wherein different clustering solutions vote in order to obtain the final clustering. We conduct clustering experiments, and report promising results.     

Fast multiscale clustering and manifold identification

We present a novel multiscale clustering algorithm inspired by algebraic multigrid techniques. Our method begins with assembling data points according to local similarities. It uses an aggregation process to obtain reliable scale-dependent global properties, which arise from the local similarities. As the aggregation process proceeds, these global properties affect the formation of coherent clusters. The global features that can be utilized are for example density, shape, intrinsic dimensionality and orientation. The last three features are a part of the manifold identification process which is performed in parallel to the clustering process. The algorithm detects clusters that are distinguished by their multiscale nature, separates between clusters with different densities, and identifies and resolves intersections between clusters. The algorithm is tested on synthetic and real data sets, its running time complexity is linear in the size of the data set.     

Structural modelling and integrative analysis of microelectromechanical systems product using graph theoretic approach

Micro-electromechanical systems (MEMS) as an enabling technology is seen to play a more and more important role for the main stream of industry of the future by broadening its applications to information, communications and bio technologies. Development of MEMS devices, however, still relies on knowledge and experience of MEMS experts due to the design and fabrication process complexity. It is difficult to understand the trade-offs inherent in the system and achieve an optimal structure without any MEMS-related insight. An attempt is made to develop an integrated systems model for the complete structure of the MEMS product system in terms of its constituents and interactions between the constituents. The hierarchical tree structures of the MEMS system and its subsystems are presented up to component level. For characterization, analysis and identification of MEMS product system, three different mathematical models say graph theoretic model, matrix model and permanent model are presented. These models are associated with graph theory, matrix method and variable permanent function by considering the various subsystems, subsubsystems up to component level, their connectivity and interdependency of the MEMS product system. The developed methodology is explained with an example. The proposed modeling and analysis is extendable to the subsystems and the component level. An overall structural analysis can be carried out by following a ‘top-down’ approach or ‘bottom-up’ approach. Understanding of MEMS product structure will help in the improvement of performance, cost, design time, and so on.     

Segmentation and classification of hyperspectral images using watershed transformation

Hyperspectral imaging, which records a detailed spectrum of light for each pixel, provides an invaluable source of information regarding the physical nature of the different materials, leading to the potential of a more accurate classification. However, high dimensionality of hyperspectral data, usually coupled with limited reference data available, limits the performances of supervised classification techniques. The commonly used pixel-wise classification lacks information about spatial structures of the image. In order to increase classification performances, integration of spatial information into the classification process is needed. In this paper, we propose to extend the watershed segmentation algorithm for hyperspectral images, in order to define information about spatial structures. In particular, several approaches to compute a one-band gradient function from hyperspectral images are proposed and investigated. The accuracy of the watershed algorithms is demonstrated by the further incorporation of the segmentation maps into a classifier. A new spectral-spatial classification scheme for hyperspectral images is proposed, based on the pixel-wise Support Vector Machines classification, followed by majority voting within the watershed regions. Experimental segmentation and classification results are presented on two hyperspectral images. It is shown in experiments that when the number of spectral bands increases, the feature extraction and the use of multidimensional gradients appear to be preferable to the use of vectorial gradients. The integration of the spatial information from the watershed segmentation in the hyperspectral image classifier improves the classification accuracies and provides classification maps with more homogeneous regions, compared to pixel-wise classification and previously proposed spectral-spatial classification techniques. The developed method is especially suitable for classifying images with large spatial structures.     

Analyzing temporal patterns of topic diversity using graph clustering

The Journal of Supercomputing - During a disaster, social media can be both a source of help and of danger: Social media has a potential to diffuse rumors, and officials involved in disaster...