We present a weak matching algorithm for interval graphs, to detect recurrent patterns in multimodal temporal data, with feature time series extracted by nonnegative tensor factorization (NTF). NTF enables latent feature extraction as well as uniform representation of multimodal observables. This work builds on our previous work introducing an interval graph representation framework for multi-sensor data. Salient data regions and their relationships are represented by temporal interval graphs, where observables are captured as time intervals (nodes), and temporally proximate nodes are related by edges. Comparing events is then posed as a subgraph matching problem. However, subgraph matching is notoriously difficult (NP-complete) with polynomial algorithms for only very restricted families of graphs. Even in these cases, perturbations to graph structure from missing or extra nodes and edges can lead to brittle matching results. Indeed, realworld sensing involves noisy environments where extraneous or missing observables interfere with event interval graph structures. To cope with these challenges, we propose a proxy representation of interval graphs via their shortest and longest paths and compare graphs by matching their path sets. We describe an attributed path matching scheme that is robust to inclusions and exclusions of nodes by adapting the longest common subsequence algorithm using dynamic programming for attributed path matching. We demonstrate the efficacy of interval graph analysis of tensor features on real-world multimodal sensor data where we investigate the detectability, similarity, and distinguishability of three sets of known events based on ground truth. We illustrate our results with match matrices and ROC curves.
We present a general framework for integrating disparate sensors to dynamically detect events. Events are often observed as multiple, asynchronous, disparate sensors’ activations in time. The challenge is to reconcile them to infer that a process of interest is underway or has occurred. We abstractly model each sensor as a value-attributed time interval over which it takes values that are relevant to a known process of interest. Process knowledge is incorporated in the detection scheme by defining sensor neighborhood intervals that overlap with temporally neighboring sensor neighborhood intervals in the process. The sensor neighborhoods are represented as nodes of an interval graph, with edges between nodes of overlapping sensor neighborhoods. Sensor activity is then interpreted via this process model by constructing an interval graph time series, for relevant sensor types and process-driven neighborhoods, and looking for subgraphs that match those of the process model graph. A time series that dynamically records the number of sensor neighborhoods overlapping at any given time is used to detect temporal regions of high sensor activity indicative of an event. Multiscale analysis of this time series reveals peaks over different time scales. The peaks are then used to efficiently triage underlying interval subgraphs of sensor activity to examine them for relational patterns similar to the process model graph of interest. Thus, our framework synergistically uses relational as well as scale information to dynamically and efficiently triage sensors related to a process. Multiple processes of interest may be efficiently detected and tracked in parallel using this approach.
Land cover classification uses multispectral pixel information to separate image regions into categories. Image segmentation seeks to separate image regions into objects and features based on spectral and spatial image properties. However, making sense of complex imagery typically requires identifying image regions that are often a heterogeneous mixture of categories and features that constitute functional semantic units such as industrial, residential, or commercial areas. This requires leveraging both spectral classification and spatial feature extraction synergistically to synthesize such complex but meaningful image units. We present an efficient graphical model for extracting such semantically cohesive regions. We employ an initial hierarchical segmentation of images into features represented as nodes of an attributed graph that represents feature properties as well as their adjacency relations with other features. This provides a framework to group spectrally and structurally diverse features, which are nevertheless semantically cohesive, based on user-driven identifications of features and their contextual relationships in the graph. We propose an efficient method to construct, store, and search an augmented graph that captures nonadjacent vicinity relationships of features. This graph can be used to query for semantic notional units consisting of ontologically diverse features by constraining it to specific query node types and their indicated/desired spatial interaction characteristics. User interaction with, and labeling of, initially segmented and categorized image feature graph can then be used to learn feature (node) and regional (subgraph) ontologies as constraints, and to identify other similar semantic units as connected components of the constraint-pruned augmented graph of a query image.
We study spatio-spectral feature extraction and image-adaptive anomaly and change detection on 8-band WorldView 2
imagery using a hierarchical polygonal image segmentation scheme. Features are represented as polygons with spectral
and structural attributes, along with neighborhood structure and containment hierarchy for contextual feature
identification. Further, the hierarchical segmentation provides multiple, coarse-scale, sub-backgrounds representing
relatively uniform regions, which localize and simplify the spectral distribution of an image. This paves the way for
facilitating anomaly and change detection when restricted to the contexts of these backgrounds. For example, forestry,
urban areas, and agricultural land have very different spatio-spectral characteristics and their joint contribution to the
image statistics can result in a complex distribution against which detecting anomalies could in general be a challenging
problem. Our segmentation scheme provides sub-regions in the later stages of the hierarchy that correspond to
homogeneous areas of an image while at the same time allowing inclusion of distinctive small features embedded in
these regions. The exclusion of other image areas by focusing on these sub-backgrounds helps discover these outliers
more easily with simpler methods of discrimination.
By selecting appropriate bands in WorldView2 imagery, the above approach can be used to achieve fine spatio-spectral
control in searching and characterizing features, anomalies, and changes of interest. The anomalies and changes are also
polygons, which have spectral and structural attributes associated with them, allowing further characterization in the
larger context of the image. The segmentation and feature detections can be used as multiple layers in a Geospatial
Information System (GIS) for annotating imagery.
The challenge of finding small targets in big images lies in the characterization of the background clutter. The
more homogeneous the background, the more distinguishable a typical target will be from its background. One
way to homogenize the background is to segment the image into distinct regions, each of which is individually
homogeneous, and then to treat each region separately. In this paper we will report on experiments in which the
target is unspecified (it is an anomaly), and various segmentation strategies are employed, including an adaptive
hierarchical tree-based scheme. We find that segmentations that employ overlap achieve better performance in
the low false alarm rate regime.
The automatic detection, recognition, and segmentation of object classes in remote sensed images is of crucial
importance for scene interpretation and understanding. However, it is a difficult task because of the high
variability of satellite data. Indeed, the observed scenes usually exhibit a high degree of complexity, where
complexity refers to the large variety of pictorial representations of objects with the same semantic meaning and
also to the extensive amount of available details. Therefore, there is still a strong demand for robust techniques for
automatic information extraction and interpretation of satellite images. In parallel, there is a growing interest in
techniques that can extract vector features directly from such imagery. In this paper, we investigate the problem
of automatic hierarchical segmentation and vectorization of multispectral satellite images. We propose a new
algorithm composed of the following steps: (i) a non-uniform sampling scheme extracting most salient pixels in
the image, (ii) an anisotropic triangulation constrained by the sampled pixels taking into account both strength
and directionality of local structures present in the image, (iii) a polygonal grouping scheme merging, through
techniques based on perceptual information, the obtained segments to a smaller quantity of superior vectorial
objects. Besides its computational efficiency, this approach provides a meaningful polygonal representation for
subsequent image analysis and/or interpretation.
KEYWORDS: Image segmentation, Sensors, Edge detection, Image processing, Detection and tracking algorithms, Cameras, Roads, Human vision and color perception, Long wavelength infrared, Shape analysis
We present a spatially adaptive scheme for automatically searching a pair of images of a scene for unusual and
interesting changes. Our motivation is to bring into play structural aspects of image features alongside the spectral
attributes used for anomalous change detection (ACD). We leverage a small but informative subset of pixels, namely
edge pixels of the images, as anchor points of a Delaunay triangulation to jointly decompose the images into a set of
triangular regions, called trixels, which are spectrally uniform. Such decomposition helps in image regularization by
simple-function approximation on a feature-adaptive grid. Applying ACD to this trixel grid instead of pixels offers
several advantages. It allows: 1) edge-preserving smoothing of images, 2) speed-up of spatial computations by
significantly reducing the representation of the images, and 3) the easy recovery of structure of the detected anomalous
changes by associating anomalous trixels with polygonal image features. The latter facility further enables the
application of shape-theoretic criteria and algorithms to characterize the changes and recognize them as interesting or
not. This incorporation of spatial information has the potential to filter out some spurious changes, such as due to
parallax, shadows, and misregistration, by identifying and filtering out those that are structurally similar and spatially
pervasive. Our framework supports the joint spatial and spectral analysis of images, potentially enabling the design of
more robust ACD algorithms.
We present a general scheme for segmenting a radiographic image into polygons that correspond to visual features. This decomposition provides a vectorized representation that is a high-level description of the image. The polygons correspond to objects or object parts present in the image. This characterization of radiographs allows the direct application of several shape recognition algorithms to identify objects. In this paper we describe the use of constrained Delaunay triangulations as a uniform foundational tool to achieve multiple visual tasks, namely image segmentation, shape decomposition, and parts-based shape matching. Shape decomposition yields parts that serve as tokens representing local shape characteristics. Parts-based shape matching enables the recognition of objects in the presence of occlusions, which commonly occur in radiographs. The polygonal representation of image features affords the efficient design and application of sophisticated geometric filtering methods to detect large-scale structural properties of objects in images. Finally, the representation of radiographs via polygons results in significant reduction of image file sizes and permits the scalable graphical representation of images, along with annotations of detected objects, in the SVG (scalable vector graphics) format that is proposed by the world wide web consortium (W3C). This is a textual representation that can be compressed and encrypted for efficient and secure transmission of information over wireless channels and on the Internet. In particular, our methods described here provide an algorithmic framework for developing image analysis tools for screening cargo at ports of entry for homeland security.
We demonstrate how to derive morphological information from micrographs, i.e., grey-level images, of polymeric foams. The segmentation of the images is performed by applying a pulse-coupled neural network. This processing generates blobs of the foams walls/struts and voids, respectively. The contours of the blobs and their corresponding points form the input to a constrained Delaunay tessellation, which provides an unstructured grid of the material under consideration. The subsequently applied Chordal Axis Transform captures the intrinsic shape characteristics, and facilitates the identification and localization of key morphological features. While stochastic features of the polymeric foams struts/walls such as areas, aspect ratios, etc., already can be computed at this stage, the foams voids require further geometric processing. The voids are separated into single foam cells. This shape manipulation leads to a refinement of the initial blob contours, which then requires the repeated application of the constrained Delaunay tessellation and Chordal Axis Transform, respectively. Using minimum enclosing rectangles for each foam cell, finally the stochastic features of the foam voids are computed.
We present an efficient multi-scale shape approximation scheme by adaptively and sparsely discretizing its continuous (or densely sampled) contour by means of points. The notion of shape is intimately related to the notion of contour and, therefore, the efficient representation of the contour of a shape is vital to a computational understanding of the shape. Any discretization of a planar smooth curve by points is equivalent to a piecewise constant approximation of its parameterized X and Y coordinate. Using the Haar wavelet transform for the piecewise approximation yields a hierarchical scheme in which the size of the approximating point set is traded off against the morphological accuracy of the approximation. Our algorithm compresses the representation of the initial shape contour to a sparse sequence of points in the plane defining the vertices of the shape's polygonal approximation. Furthermore, it is possible to control the overall resolution of the approximation by a single, scale- independent parameter.
We present a new method to transform the spectral pixel information of a micrograph into an affine geometric description, which allows us to analyze the morphology of granular materials. We use spectral and pulse-coupled neural network based segmentation techniques to generate blobs, and a newly developed algorithm to extract dilated contours. A constrained Delaunay tessellation of the contour points results in a triangular mesh. This mesh is the basic ingredient of the Chodal Axis Transform, which provides a morphological decomposition of shapes. Such decomposition allows for grain separation and the efficient computation of the statistical features of granular materials.
We present a syntactic and metric two-dimensional shape recognition scheme based on shape features. The principal features of a shape can be extracted and semantically labeled by means of the chordal axis transform (CAT), with the resulting generic features, namely torsos and limbs, forming the primitive segmented features of the shape. We introduce a context-free universal language for representing all connected planar shapes in terms of their external features, based on a finite alphabet of generic shape feature primitives. Shape exteriors are then syntactically represented as strings in this language. Although this representation of shapes is not complete, in that it only describes their external features, it effectively captures shape embeddings, which are important properties of shapes for purposes of recognition. The elements of the syntactic strings are associated with attribute feature vectors that capture the metrical attributes of the corresponding features. We outline a hierarchical shape recognition scheme, wherein the syntactical representation of shapes may be 'telescoped' to yield a coarser or finer description for hierarchical comparison and matching. We finally extend the syntactic representation and recognition to completely represent all planar shapes, albeit without a generative context-free grammar for this extension.
A novel and efficient invertible transform for shape segmentation is defined that serves to localize and extract shape characteristics. This transform -- the chordal axis transform (CAT) -- remedies the deficiencies of the well-known medial axis transform (MAT). The CAT is applicable to shapes with discretized boundaries without restriction on the sparsity or regularity of the discretization. Using Delaunay triangulations of shape interiors, the CAT induces structural segmentation of shapes into limb and torso chain complexes of triangles. This enables the localization, extraction, and characterization of the morphological features of shapes. It also yields a pruning scheme for excising morphologically insignificant features and simplifying shape boundaries and descriptions. Furthermore, it enables the explicit characterization and exhaustive enumeration of primary, semantically salient, shape features. Finally, a process to characterize and represent a shape in terms of its morphological features is presented. This results in the migration of a shape from its affine description to an invariant, and semantically salient feature-based representation in the form of attributed planar graphs. The research described here is part of a larger effort aimed at automating image understanding and computer vision tasks.
Image analysis is an important requirement of many artificial intelligence systems. Though great effort has been devoted to inventing efficient algorithms for image analysis, there is still much work to be done. It is natural to turn to mammalian vision systems for guidance because they are the best known performers of visual tasks. The pulse- coupled neural network (PCNN) model of the cat visual cortex has proven to have interesting properties for image processing. This article describes the PCNN application to the processing of images of heterogeneous materials; specifically PCNN is applied to image denoising and image segmentation. Our results show that PCNNs do well at segmentation if we perform image smoothing prior to segmentation. We use PCNN for obth smoothing and segmentation. Combining smoothing and segmentation enable us to eliminate PCNN sensitivity to the setting of the various PCNN parameters whose optimal selection can be difficult and can vary even for the same problem. This approach makes image processing based on PCNN more automatic in our application and also results in better segmentation.
A novel and efficient pose-invariant guided template matching algorithm, for object recognition in images, is proposed. Template matching is performed in a rotation-scale- translation (pose) invariant fashion, thus greatly reducing the 4-d search space to a single point. The invariance is achieved by preprocessing the input image and associating certain geometric descriptors with the objects in the image. These descriptors completely characterize the affine parameters associated with the objects which must be applied to candidate templates, and the location in the image where the template is to be applied for a match. Preprocessing and matching are performed on a wavelet pyramidal decomposition of the image in a multiresolutional coarse-to-fine fashion for computational efficiency. An efficient search strategy is also proposed for selecting templates in the template database.
An image segmentation scheme based on multiresolutional, successive approximations of the image histogram is proposed. The algorithm begins with a coarse, initial segmentation of the image obtained by selecting thresholds from a coarse sampling of a low-pass filtered version of the image histograms. This segmentation is refined by selecting thresholds from increasingly better approximations of the histogram. The algorithm is linear in the size of the input image and handles images with multimodal histograms. Preliminary results indicate that the approach shows promise as a simple, computationally efficient algorithm for hierarchical image segmentation. The algorithm may easily be embedded in the `split' phase of any of the well known split-and-merge type segmentation algorithms.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.