Attention-driven image interpretation with application to image retrieval

Visual attention, a selective procedure of human's early vision, plays a very important role for humans to understand a scene by intuitively emphasizing some focused regions/objects. Being aware of this, we propose an attention-driven image interpretation method that pops out visual attentive objects from an image iteratively by maximizing a global attention function. In this method, an image can be interpreted as containing several perceptually attended objects as well as a background, where each object has an attention value. The attention values of attentive objectives are then mapped to importance factors so as to facilitate the subsequent image retrieval. An attention-driven matching algorithm is proposed in this paper based on a retrieval strategy emphasizing attended objects. Experiments on 7376 Hemera color images annotated by keywords show that the retrieval results from our attention-driven approach compare favorably with conventional methods, especially when the important objects are seriously concealed by the irrelevant background.     

Recognition of attentive objects with a concept association network for image annotation

With the advancement of imaging techniques and IT technologies, image retrieval has become a bottle neck. The key for efficient and effective image retrieval is by a text-based approach in which automatic image annotation is a critical task. As an important issue, the metadata of the annotation, i.e., the basic unit of an image to be labeled, has not been fully studied. A habitual way is to label the segments which are produced by a segmentation algorithm. However, after a segmentation process an object has often been broken into pieces, which not only produces noise for annotation but also increases the complexity of the model. We adopt an attention-driven image interpretation method to extract attentive objects from an over-segmented image and use the attentive objects for annotation. By such doing, the basic unit of annotation has been upgraded from segments to attentive objects. Visual classifiers are trained and a concept association network (CAN) is constructed for object recognition. A CAN consists of a number of concept nodes in which each node is a trained neural network (visual classifier) to recognize a single object. The nodes are connected through their correlation links forming a network. Given that an image contains several unknown attentive objects, all the nodes in CAN generate their own responses which propagate to other nodes through the network simultaneously. For a combination of nodes under investigation, these loopy propagations can be characterized by a linear system. The response of a combination of nodes can be obtained by solving the linear system. Therefore, the annotation problem is converted into finding out the node combination with the maximum response. Annotation experiments show a better accuracy of attentive objects over segments and that the concept association network improves annotation performance.     

Use of a double Fourier series for three-dimensional shape representation

The representation of three-dimensional star-shaped objects by the double Fourier series (DFS) coefficients of their boundary function is considered. An analogue of the convolution theorem for a DFS on a sphere is developed. It is then used to calculate the moments of an object directly from the DFS coefficients, without an intermediate reconstruction step. The complexity of computing the moments from the DFS coefficients is O(N ² log N), where N is the maximum order of coefficients retained in the expansion, while the complexity of computing the moments from the spherical harmonic representation is O(N ² log ² N). It is shown that under sufficient conditions, the moments and surface area corresponding to the truncated DFS converge to the true moments and area of an object. A new kind of DFS—the double Fourier sine series—is proposed which has better convergence properties than the previously used kinds and spherical harmonics in the case of objects with a sharp point above the pole of the spherical domain.     

Fast multiplication of matrices over a finitely generated semiring

In this paper we show that n×n matrices with entries from a semiring R which is generated additively by q generators can be multiplied in time O(q²nω), where nω is the complexity for matrix multiplication over a ring (Strassen: ω<2.807, Coppersmith and Winograd: ω<2.376).We first present a combinatorial matrix multiplication algorithm for the case of semirings with q elements, with complexity , matching the best known methods in this class.Next we show how the ideas used can be combined with those of the fastest known boolean matrix multiplication algorithms to give an O(q²nω) algorithm for matrices of, not necessarily finite, semirings with q additive generators.For finite semirings our combinatorial algorithm is simple enough to be a practical algorithm and is expected to be faster than the O(q²nω) algorithm for matrices of practically relevant sizes.     

Aspect-Trees: Generation and Interpretation

This contribution presents a new approach to the recognition of a priori known 3-D objects in single 2-D images. The underlying model is embedded in the domain of CAD-based vision using a viewer-centered approach to generate a set of normalized views. They serve as a basis for an optimal selection of properties of features. The aspect idea is used for grouping the values of the properties into aspect-trees. The aim of this approach is to identify the correct view of an object seen in the image and thereby to distinguish between different objects. This is achieved with an appropriate traversion of the aspect-trees which proves the ability of the image interpretation system Aspik to recognize complex objects in different environments robustly and efficiently. The time complexity for recognizing nonoccluded objects is O (n² · m), where n is the number of the considered aspect-trees of the object and m the number of image features.     

A parallel algorithm for generating chain code of objects in binary images

This paper addresses parallel execution of chain code generation on a linear array architecture. The contours in the proposed algorithm are viewed as a set of edges (or contour segments) that can be traced by a top-down contour tracing method to generate the chain codes for the outer and inner object contours. A parallel algorithm that contains the chain code generating rules and operations needed is also described, and the algorithm is mapped onto a one-dimensional systolic array containing processing elements (PEs) to devise this architecture. The architecture extracts the contours of objects and quickly generates the corresponding chain codes after the image data in all rows are inputted in a linear fashion. The total processing time for generating the chain codes in an N×N image is O(3N). By doing so, the real-time requirement is fulfilled and its execution time is independent of the image content. In addition, a partition method is developed to process an image when the parallel architecture has a fixed number of PEs; say two or more. The total execution time for an N×N image by employing a fixed number of PEs is N(N+1)/M+2(M−1), when M is the fixed number of PEs.     

Constant-Time Algorithm for the Euclidean Distance Transform on Reconfigurable Meshes

The Euclidean distance transform (EDT) is an operation to convert a binary image consisting of black and white pixels to a representation where each pixel has the Euclidean distance of the nearest black pixel. The EDT has many applications in computer vision and image processing. In this paper, we present a constant-time algorithm for computing the EDT of an N×N image on a reconfigurable mesh. Our algorithm has two variants. (i) If the image is initially given in an N×N mesh, one pixel per processor, our algorithm requires an N×N×N mesh for computing the EDT. (ii) If the image is given in an N×N² mesh, each row of the image in the first row of a separate N×N mesh, we can compute the EDT in the same N×N² mesh. The AT² bounds for these two variants are O(N⁴) and O(N³) respectively. The best previously known algorithm (Y. Pan and K. Li, Inform. Sci.120 (1999), 209–221) for this problem assumes input similar to the second variant of our algorithm and runs in constant-time on an N²×N² reconfigurable mesh with an AT² bound of O(N⁴). Hence both variants of our algorithm improve upon the processor complexity of the algorithm in Pan and Li (1999) by a factor of N and the second variant improves upon the AT² complexity by a factor of N.     

bigVAT: Visual assessment of cluster tendency for large data sets

Assessment of clustering tendency is an important first step in cluster analysis. One tool for assessing cluster tendency is the Visual Assessment of Tendency (VAT) algorithm. VAT produces an image matrix that can be used for visual assessment of cluster tendency in either relational or object data. However, VAT becomes intractable for large data sets. The revised VAT (reVAT) algorithm reduces the number of computations done by VAT, and replaces the image matrix with a set of profile graphs that are used for the visual assessment step. Thus, reVAT overcomes the large data set problem which encumbers VAT, but presents a new problem: interpretation of the set of reVAT profile graphs becomes very difficult when the number of clusters is large, or there is significant overlap between groups of objects in the data. In this paper, we propose a new algorithm called bigVAT which (i) solves the large data problem suffered by VAT, and (ii) solves the interpretation problem suffered by reVAT. bigVAT combines the quasi-ordering technique used by reVAT with an image display of the set of profile graphs displaying the clustering tendency information with a VAT-like image. Several numerical examples are given to illustrate and support the new technique.     

An automatic region-based image segmentation algorithm for remote sensing applications

Object-based image analysis has proven its potentials for remote sensing applications, especially when using high-spatial resolution data. One of the first steps of object-based image analysis is to generate homogeneous regions from a pixel-based image, which is typically called the image segmentation process. This paper introduces a new automatic Region-based Image Segmentation Algorithm based on k-means clustering (RISA), specifically designed for remote sensing applications. The algorithm includes five steps: k-means clustering, segment initialization, seed generation, region growing, and region merging. RISA was evaluated using a case study focusing on land-cover classification for two sites: an agricultural area in the Republic of South Africa and a residential area in Fresno, CA. High spatial resolution SPOT 5 and QuickBird satellite imagery were used in the case study. RISA generated highly homogeneous regions based on visual inspection. The land-cover classification using the RISA-derived image segments resulted in higher accuracy than the classifications using the image segments derived from the Definiens software (eCognition) and original image pixels in combination with a minimum-distance classifier. Quantitative segmentation quality assessment using two object metrics showed RISA-derived segments successfully represented the reference objects.     

Multimedia Indexing with the SMART system

The storage and retrieval of multimedia data is a crucial problem in multimedia information systems due to the huge storage requirements. It is necessary to provide an efficient methodology for the indexing of multimedia data for rapid retrieval. The aim of this paper is to introduce a methodology to represent, simplify, store, retrieve and reconstruct an image from a repository. An algebraic representation of the spatio-temporal relations present in a document is constructed from an equivalent graph representation and used to index the document. We use this representation to simplify and later reconstruct the complete index. This methodology has been tested by implementation of a prototype system called Simplified Modeling to Access and ReTrieve multimedia information (SMART). Experimental results show that the complexity of an index of a 2D document is O (n^*(n−1)/k) with k≥2 as opposed to the O (n^*(n−1)/2) known so far. Since k depends on the number of objects in an image more complex documents have lower overall complexity.     

A dynamic integration algorithm to model surfaces from multiple range views

This paper presents a dynamic integration algorithm to triangulate a surface from multiple range views. This integration technique is based on the reparameterization of the canonic subsets of the Venn diagram of the set of range views. We compute a model based onN views from a model based onN–1 views by processing only the surface segments visible in theN ^th view. An experimental result shows that the proposed integration algorithm can process complex multipart objects containing holes.     

Salient object detection with low-rank approximation and ℓ2,1-norm minimization

Salient object detection is an important issue in computer vision and image procession in that it can facilitate humans to locate conspicuous visual regions in complex scenes rapidly and improve the performance of object detection and video tracking. In recent years, low-rank matrix approximation has been proved to be favorable in image saliency detection and gained a great deal of attention. An underlying assumption of low-rank recovery is that an image is a combination of background regions being low-rank and salient objects being sparse, which corresponds to tough non-smooth optimization problems. In this paper, by incorporating ℓ_2,1-norm minimization, we obtain the corresponding smooth optimization problems and propose two effective algorithms with proved convergence. To guarantee the robustness of the proposed methods, the input image is divided into patches and each patch is approximately represented by its mean value. Besides, multi-scale visual features of each patch of the given image are extracted to capture common low-level features such as color, edge, shape and texture. The salient objects of a given image are indicated with sparse coefficients solved by the low-rank matrix approximation problem. Saliency maps are further produced with integration of the high-level prior knowledge. Finally, extensive experiments in four real-world datasets demonstrate that the proposed methods come with competitive performance over the eight compared state-of-the-arts.     

A new factorization of the mass matrix for optimal serial and parallel calculation of multibody dynamics

This paper describes a new factorization of the inverse of the joint-space inertia matrix M. In this factorization, M ^?1 is directly obtained as the product of a set of sparse matrices wherein, for a serial chain, only the inversion of a block-tridiagonal matrix is needed. In other words, this factorization reduces the inversion of a dense matrix to that of a block-tridiagonal one. As a result, this factorization leads to both an optimal serial and an optimal parallel algorithm, that is, a serial algorithm with a complexity of O(N) and a parallel algorithm with a time complexity of O(logN) on a computer with O(N) processors. The novel feature of this algorithm is that it first calculates the interbody forces. Once these forces are known, the accelerations are easily calculated. We discuss the extension of the algorithm to the task of calculating the forward dynamics of a kinematic tree consisting of a single main chain plus any number of short side branches. We also show that this new factorization of M ^?1 leads to a new factorization of the operational-space inverse inertia, Λ ^?1, in the form of a product involving sparse matrices. We show that this factorization can be exploited for optimal serial and parallel computation of Λ ^?1, that is, a serial algorithm with a complexity of O(N) and a parallel algorithm with a time complexity of O(logN) on a computer with O(N) processors.     

Object-oriented change detection for the city of Harare,Zimbabwe

Object building and the extraction of homogeneous landscape units on which spatial statistics can be applied is useful in assessing land use and land cover change. Object-oriented processing techniques are becoming more popular compared to traditional pixel-based image analysis. A hierarchical image segmentation approach was adopted to extract the objects from multi-temporal Landsat images over Zimbabwe. The spatial arrangement of t₀ and t₁ objects was independent as the segmentation process was independently applied, although object change of t₁ was based on t₀ boundaries. We applied a Standardized, Object Oriented, Automatic Classification (SOOAC) method based on fuzzy logic. The error matrix for the TM image had an overall accuracy of 95.6% and a KIA value of 94.7%, the ETM showed slightly lower overall accuracy. Various LULC changes were identified over the 13 year period per object and also per class, mainly vegetation decrease. Object-oriented change information is necessary in decision support systems and uncertainty management strategies. This approach addresses some of the major issues in object-based GIS change analysis as it is based on stable object geometry.     

Adaptive reversible image watermarking scheme

This paper presents an adaptive block sized reversible image watermarking scheme. A reversible watermarking approach recovers the original image from a watermarked image after extracting the embedded watermarks. Without loss of generality, the proposed scheme segments an image of size 2^N × 2^N adaptively to blocks of size 2^L × 2^L, where L starts from a user-defined number to 1, according to their block structures. If possible, the differences between central ordered pixel and other pixels in each block are enlarged to embed watermarks. The embedded quantity is determined by the largest difference in a block and watermarks are embedded into LSB bits of above differences. Experimental results show that the proposed adaptive block size scheme has higher capacity than conventional fixed block sized method.     

Thinning algorithms based on quadtree and octree representations

Thinning is a critical pre-processing step to obtain skeletons for pattern analysis. Quadtree and octree are hierarchical data representations in image processing and computer graphics. In this paper, we present new 2-D area-based and 3-D surface-based thinning algorithms for directly converting quadtree and octree representations to skeletons. The computational complexity of our thinning algorithm for a 2-D or a 3-D image with each length N is respectively O(N²) or O(N³), which is more efficient than the existing algorithms of O(N³) or O(N⁴). Furthermore, our thinning algorithms can lessen boundary noise spurs and are suited for parallel implementation.