As deep neural networks constantly improve and provide state-of-the-art solutions to various problems, deployment of these models becomes more common, and so does the importance of protecting these models against malicious attacks attempting to replicate these models. In this paper, we present a novel zero-knowledge method for attacking and stealing knowledge from deep neural networks. Our method utilizes unlabeled data and the predictions of the mentor model we would like to steal. The presented method targets the most protected models which reveal only the minimal amount of information, i.e., the predicted label. We assume no access to any internal information about the model, and no access to the training data. The presented method improves the SOTA performance of attacking protected neural network models. The results show that all classification neural networks are vulnerable to the presented attack method, and any attacker can effectively replicate these models without having access to their architecture, parameters, training data, or softmax outputs.

Deep neural networks (NNs) trained on hyperspectral images are employed typically for the classification of new images collected from the same sensor, assuming similar characteristics to those of the training images. Creating, however, high-quality ground truth (GT) for training is rather complex, especially when attempting to classify multi-temporal images over seasonal changes. To overcome this difficulty, we propose a novel method that utilizes an additional, one-time collection of hyperspectral FENIX images in the Spring along with ground observations from the end of the Fall. The hyperspectral data are then used for simulation of GT for training. At the same time, the field campaign allows for fine-tuning of the NN to achieve enhanced, multi-seasonal hyperspectral image classification. Indeed, we demonstrate how the proposed method successfully classifies new VEN μS images obtained during different seasons.

This paper presents a novel scheme, based on a unique combination of genetic algorithms (GAs) and deep learning (DL), for the automatic reconstruction of Portuguese tile panels, a challenging real-world variant of the jigsaw puzzle problem (JPP) with important national heritage implications. Specifically, we introduce an enhanced GA-based puzzle solver, whose integration with a novel DL-based compatibility measure (DLCM) yields state-of-the-art performance, regarding the above application. Current compatibility measures consider typically (the chromatic information of) edge pixels (between adjacent tiles), and help achieve high accuracy for the synthetic JPP variant. However, such measures exhibit rather poor performance when applied to the Portuguese tile panels, which are susceptible to various real-world effects, e.g., monochromatic panels, non-squared tiles, edge degradation, etc. To overcome such difficulties, we have developed a novel DLCM to extract high-level texture/color statistics from the entire tile information.

Training a deep neural network for classification constitutes a major problem in remote sensing due to the lack of adequate field data. Acquiring high-resolution ground truth (GT) by human interpretation is both cost-ineffective and inconsistent. We propose, instead, to utilize high-resolution, hyperspectral images for solving this problem, by unmixing these images to obtain reliable GT for training a deep network. Specifically, we simulate GT from high-resolution, hyperspectral FENIX images, and use it for training a convolutional neural network (CNN) for pixel-based classification. We show how the model can be transferred successfully to classify new mid-resolution VENμS imagery.

As state-of-the-art deep neural networks are deployed at the core of more advanced Al-based products and services, the incentive for copying them (i.e., their intellectual properties) by rival adversaries is expected to increase considerably over time. The best way to extract or steal knowledge from such networks is by querying them using a large dataset of random samples and recording their output, followed by training a student network to mimic these outputs, without making any assumption about the original networks. The most effective way to protect against such a mimicking attack is to provide only the classification result, without confidence values associated with the softmax layer.In this paper, we present a novel method for generating composite images for attacking a mentor neural network using a student model. Our method assumes no information regarding the mentor's training dataset, architecture, or weights. Further assuming no information regarding the mentor's softmax output values, our method successfully mimics the given neural network and steals all of its knowledge. We also demonstrate that our student network (which copies the mentor) is impervious to watermarking protection methods, and thus would not be detected as a stolen model.Our results imply, essentially, that all current neural networks are vulnerable to mimicking attacks, even if they do not divulge anything but the most basic required output, and that the student model which mimics them cannot be easily detected and singled out as a stolen copy using currently available techniques.

We present, in this paper, a new methodology for spectral unmixing, where a vector of fractions, corresponding to a set of endmembers (EMs), is estimated for each pixel in the image. The process first provides an initial estimate of the fraction vector, followed by an iterative procedure that converges to an optimal solution. Specifically, projected gradient descent (PGD) optimization is applied to (a variant of) the spectral angle mapper objective function, so as to significantly reduce the estimation error due to amplitude (i.e., magnitude) variations in EM spectra, caused by the illumination change effect. To improve the computational efficiency of our method over a commonly used gradient descent technique, we have analytically derived the objective function's gradient and the optimal step size (used in each iteration). To gain further improvement, we have implemented our unmixing module via code vectorization, where the entire process is “folded” into a single loop, and the fractions for all of the pixels are solved simultaneously. We call this new parallel scheme vectorized code PGD unmixing (VPGDU). VPGDU has the advantage of solving (simultaneously) an independent optimization problem per image pixel, exactly as other pixelwise algorithms, but significantly faster. Its performance was compared with the commonly used fully constrained least squares unmixing (FCLSU), the generalized bilinear model (GBM) method for hyperspectral unmixng, and the fast state-of-the-art methods, sparse unmixing by variable splitting and augmented Lagrangian (SUnSAL) and collaborative SUnSAL (CLSUnSAL) based on the alternating direction method of multipliers. Considering all of the prospective EMs of a scene at each pixel (i.e., without a priori knowledge which/how many EMs are actually present in a given pixel), we demonstrate that the accuracy due to VPGDU is considerably higher than that obtained by FCLSU, GBM, SUnSAL, and CLSUnSAL under varying illumination, and is, otherwise, comparable with respect to these methods. However, while our method is significantly faster than FCLSU and GBM, it is slower than SUnSAL and CLSUnSAL by roughly an order of magnitude.

Performing standard unmixing of a hyperspectral image, while taking into account all of the potential endmembers (EMs) in a pixel, is known to be prone to error. Instead, determining first the set of EMs that actually reside in each pixel, leads to enhanced unmixing results. This important insight for achieving higher unmixing accuracy can be exploited efficiently by extracting relevant spatial information from a given image. In this work, we present a new method for spatially adaptive spectral unmixing, called the Gaussian based spatially adaptive unmixing (GBSAU) method. GBSAU takes advantage of the spatial arrangement of the image pixels and their spectral relations in order to determine an actual subset of EMs per pixel. It is based on spatial localization of the EMs by fitting, for each EM, the parameters of the series of spatial Gaussians whose sum represents the EM's fraction surface over the image.

This paper presents a novel deep learning based method for automatic malware signature generation and classification. The method uses a deep belief network (DBN), implemented with a deep stack of denoising autoencoders, generating an invariant compact representation of the malware behavior. While conventional signature and token based methods for malware detection do not detect a majority of new variants for existing malware, the results presented in this paper show that signatures generated by the DBN allow for an accurate classification of new malware variants. Using a dataset containing hundreds of variants for several major malware families, our method achieves 98.6% classification accuracy using the signatures generated by the DBN. The presented method is completely agnostic to the type of malware behavior that is logged (e.g., API calls and their parameters, registry entries, websites and ports accessed, etc.), and can use any raw input from a sandbox to successfully train the deep neural network which is used to generate malware signatures.

Several image registration methods, based on the scaled-invariant feature transform (SIFT) technique, have appeared recently in the remote sensing literature. All of these methods attempt to overcome problems encountered by SIFT in multimodal remotely sensed imagery, in terms of the quality of its feature correspondences. The deterministic method presented in this letter exploits the fact that each SIFT feature is associated with a scale, orientation, and position to perform mode seeking (in transformation space) to eliminate outlying corresponding key points (i.e, features) and improve the overall match obtained. We also present an exhaustive empirical study on a variety of test cases, which demonstrates that our method is highly accurate and rather fast. The algorithm is capable of automatically detecting whether it succeeded or failed.

In this paper we introduce new types of square-piece jigsaw puzzles, where in addition to the unknown location and orientation of each piece, a piece might also need to be flipped. These puzzles, which are associated with a number of real world problems, are considerably harder, from a computational standpoint. Specifically, we present a novel generalized genetic algorithm (GA)-based solver that can handle puzzle pieces of unknown location and orientation (Type 2 puzzles) and (two-sided) puzzle pieces of unknown location, orientation, and face (Type 4 puzzles). To the best of our knowledge, our solver provides a new state-of-the-art, solving previously attempted puzzles faster and far more accurately, handling puzzle sizes that have never been attempted before, and assembling the newly introduced two-sided puzzles automatically and effectively. This paper also presents, among other results, the most extensive set of experimental results, compiled as of yet, on Type 2 puzzles.

In this paper we describe the problem of painter classification, and propose a novel hybrid approach incorporating genetic algorithms (GA) and deep restricted Boltzmann machines (RBM). Given a painting, we extract features using both generic image processing (IP) functions (e.g., fractal dimension, Fourier spectra coefficients, texture coefficients, etc.) and unsupervised deep learning (using deep RBMs). We subsequently compare several supervised learning techniques for classification using the extracted features as input. The results show that the weighted nearest neighbor (WNN) method, for which the weights are evolved using GA, outperforms both a support vector machine (SVM) classifier and a standard nearest neighbor classifier, achieving over 90% classification accuracy for the 3-painter problem (an improvement of over 10% relatively to previous results due to standard feature extraction only).

In this paper we propose the first genetic algorithm (GA)-based solver for jigsaw puzzles of unknown puzzle dimensions and unknown piece location and orientation. Our solver uses a novel crossover technique, and sets a new state-of-the-art in terms of the puzzle sizes solved and the accuracy obtained. The results are significantly improved, even when compared to previous solvers assuming known puzzle dimensions. Moreover, the solver successfully contends with a mixed bag of multiple puzzle pieces, assembling simultaneously all puzzles.

This paper demonstrates the use of genetic algorithms for evolving: 1) a grandmaster-level evaluation function, and 2) a search mechanism for a chess program, the parameter values of which are initialized randomly. The evaluation function of the program is evolved by learning from databases of (human) grandmaster games. At first, the organisms are evolved to mimic the behavior of human grandmasters, and then these organisms are further improved upon by means of coevolution. The search mechanism is evolved by learning from tactical test suites. Our results show that the evolved program outperforms a two-time world computer chess champion and is at par with the other leading computer chess programs.

This paper describes the problem of painter classification. We propose solving the problem by using genetic algorithms, which yields very promising results. The proposed methodology combines dimensionality reduction (via image preprocessing) and evolutionary computation techniques, by representing preprocessed data as a chromosome for a genetic algorithm (GA). The preprocessing of our scheme incorporates a diverse set of complex features (e.g., fractal dimension, Fourier spectra coefficients, and texture). The training phase of the GA employs a weighted nearest neighbor (NN) algorithm. We provide initial promising results for the 2- and 3-class cases, which offer significant improvement in comparison to a standard nearest neighbor classifier.

In this paper we propose the first effective automated, genetic algorithm (GA)-based jigsaw puzzle solver. We introduce a novel procedure of merging two "parent" solutions to an improved "child" solution by detecting, extracting, and combining correctly assembled puzzle segments. The solver proposed exhibits state-of-the-art performance solving previously attempted puzzles faster and far more accurately, and also puzzles of size never before attempted. Other contributions include the creation of a benchmark of large images, previously unavailable. We share the data sets and all of our results for future testing and comparative evaluation of jigsaw puzzle solvers.

In this paper we present a genetic algorithm (GA)-based approach for the stereo matching problem. More precisely, the approach presented is a combination of a simple dynamic programming algorithm, commonly used for stereo matching, with a practical GA-based optimization scheme. The performance of our scheme was evaluated on standard test data of the Middlebury benchmark. Specifically, the number of incorrect disparities on these data decreases by approximately 20% in comparison to the original approach (without the use of a GA).

Several image registration methods, based on the scaled-invariant feature transform (SIFT) technique, have appeared recently in the remote sensing literature. All of these methods attempt to overcome problems encountered by SIFT in multi-modal remotely sensed imagery, in terms of the quality of its feature correspondences. The method presented in this paper performs mode seeking (in transformation space) to eliminate outlying corresponding key-points (i.e., features) and improve the overall match obtained. Preliminary experimental results seem to indicate that our method achieves high accuracy and is rather fast in a variety of test cases.

A novel unmixing methodology is presented, searching for a fraction combination of end-members (EMs) that reconstructs the integrated source signal. The search starts with computing an initially estimated unmixing solution and then assesses combinations selected at random within an envelope surrounding this estimated solution. From each of these combinations, it then progresses iteratively along a path of neighboring combinations, so as to minimize the spectral angle between the corresponding (integrated) signatures and the source signal, until reaching a satisfactory solution. The new iterative fraction combination search (IFCS) was compared to the standard least squares unmixing (LSU). An assessment of both methods was conducted with a real Airborne Visible/Infrared Imaging Spectrometer image and nine synthetic images generated by randomly selecting fractions for two up to ten EMs derived from this real image. Considering all these EMs for the unmixing solution (not knowing specifically which or how many of them are actually mixed at each pixel), the IFCS method performed considerably better than LSU.

This paper demonstrates the use of genetic algorithms for evolving a grandmaster-level evaluation function for a chess program. This is achieved by combining supervised and unsupervised learning. In the supervised learning phase the organisms are evolved to mimic the behavior of human grandmasters, and in the unsupervised learning phase these evolved organisms are further improved upon by means of coevolution.

In this paper we demonstrate how genetic algorithms can be used to reverse engineer an evaluation function's parameters for computer chess. Our results show that using an appropriate mentor, we can evolve a program that is on par with top tournament-playing chess programs, outperforming a two-time World Computer Chess Champion. This performance gain is achieved by evolving a program with a smaller number of parameters in its evaluation function to mimic the behavior of a superior mentor which uses a more extensive evaluation function. In principle, our mentor-assisted approach could be used in a wide range of problems for which appropriate mentors are available.

Image registration is an important element in data processing for remote sensing with many applications and a wide range of solutions. Despite considerable investigation the field has not settled on a definitive solution for most applications and a number of questions remain open. This article looks at selected research issues by surveying the experience of operational satellite teams, application-specific requirements for Earth science, and our experiments in the evaluation of image registration algorithms with emphasis on the comparison of algorithms for subpixel accuracy. We conclude that remote sensing applications put particular demands on image registration algorithms to take into account domain-specific knowledge of geometric transformations and image content.

The task of image registration can be divided into two major components, i.e., the extraction of control points or features from images, and the search among the extracted features for the matching pairs that represent the same feature in the images to be matched. Manual extraction of control features can be subjective and extremely time consuming, and often results in few usable points. On the other hand, automated feature extraction allows using invariant target features such as edges, corners, and line intersections as relevant landmarks for registration purposes. In this paper, we present an extension of a recently developed morphological approach for automatic extraction of landmark chips and corresponding windows in a fully unsupervised manner for the registration of multispectral images. Once a set of chip-window pairs is obtained, a (hierarchical) robust feature matching procedure, based on a multiresolution overcomplete wavelet decomposition scheme, is used for registration purposes. The proposed method is validated on a pair of remotely sensed scenes acquired by the Advanced Land Imager (ALI) multispectral instrument and the Hyperion hyperspectral instrument aboard NASA’s Earth Observing-I satellite.

The future of remote sensing will see the development of spacecraft formations, and with this development will come a number of complex challenges such as maintaining precise relative position and specified attitudes. At the same time, there will be increasing needs to understand planetary system processes and build accurate prediction models. One essential technology to accomplish these goals is the integration of multiple source data. For this integration, image registration and fusion represent the first steps and need to be performed with very high accuracy. In this paper, we describe studies performed in both image registration and fusion, including a modular framework that was built to describe registration algorithms, a Web-based image registration toolbox, and the comparison of several image fusion techniques using data from the EO-1/ALI and Hyperion sensors

We propose a generic computational framework for maintaining a discrete geometric structure defined by a collection of static and mobile objects. We assume that the mobile objects move incrementally, that is, in discrete time steps. We assume that the structure to be maintained is a function of the current locations of the mobile and static objects (independent of their prior motion). Unlike other models for kinetic computation, we place no restrictions on the motion nor on its predictability. In order to handle unrestricted incremental motion, our framework is based on the coordination of two computational entities. The first is the incremental motion algorithm. It is responsible for maintaining the structure and a set of certificates, or conditions, that prove the structure’s correctness. The other entity, called the motion processor, is responsible for handling all the low-level aspects of motion, including computing and/or tracking the motion of the mobile objects, answering queries about their current positions and velocities, and validating that the object motions satisfy simple motion estimates, which are generated by the incremental motion algorithm. Computational efficiency is measured in terms of the number of interactions between these two entities.

While automatic image registration algorithms are usually being evaluated with regards to their accuracy, it is often useful to relate this accuracy to the "initial conditions", i.e., the distance between the initial navigation geolocation and the correct result. This paper describes a modular framework that was built to describe registration algorithms, and utilize this framework to attempt to classify different registration components and algorithms in terms of their responses to the initial conditions. Performances would be evaluated on synthetic data, multitemporal and multisensor data. All results of the study would be presented at the conference and would be useful for two different purposes: (1) provide automatic quality assessment of the geolocation of remote sensing data by performing interalgorithm consistency studies; and (2) be the foundations for the design of future on-board applications including planetary exploration.

We address the problem of finding the shortest path between two points in an unknown real physical environment, where a traveling agent must move around in the environment to explore unknown territory. We introduce the Physical-A* algorithm (PHA*) for solving this problem. PHA* expands all the mandatory nodes that A* would expand and returns the shortest path between the two points. However, due to the physical nature of the problem, the complexity of the algorithm is measured by the traveling effort of the moving agent and not by the number of generated nodes, as in standard A*. PHA* is presented as a two-level algorithm, such that its high level, A*, chooses the next node to be expanded and its low level directs the agent to that node in order to explore it. We present a number of variations for both the high-level and low-level procedures and evaluate their performance theoretically and experimentally. We show that the travel cost of our best variation is fairly close to the optimal travel cost, assuming that the mandatory nodes of A* are known in advance. We then generalize our algorithm to the multi-agent case, where a number of cooperative agents are designed to solve the problem. Specifically, we provide an experimental implementation for such a system. It should be noted that the problem addressed here is not a navigation problem, but rather a problem of finding the shortest path between two points for future usage.

The goal of the project described in this paper is to build a prototype of an operational system, which will provide registration within subpixel accuracy of multitemporal Landsat data, acquired by either Landsat-5 or Landsat-7 Thematic Mapper instruments. Integrated within an automated mass processing system for Landsat data, the input to our registration system consists of scenes that have been geometrically and radiometrically corrected, as well as preprocessed for detection of clouds and cloud shadows. Such preprocessed scenes are then georegistered relative to a database of Landsat chips. This paper describes the entire registration process, including the use of landmark chips, feature extraction performed by an overcomplete wavelet representation, and feature matching using statistically robust techniques. Knowing the approximate longitudes and latitudes or the UTM coordinates of the four corners of each incoming scene, a subset of the chips that represent landmarks included in the scene are selected to perform the registration. For each of these selected landmark chips, a corresponding window is extracted from the incoming scene, and each chip-window pair is registered using a robust wavelet feature-matching methodology. Based on the transformations from the chip-window pairs, a global transformation is then computed for the entire scene using a variant of a robust least median of squares estimator. Empirical results of this registration process, which provided subpixel accuracy for several multitemporal scenes from different study areas, are presented and discussed.

Finding local interrelations (hypotheses) among attributes within very large databases of high dimensionality is an acute problem for many databases and data mining applications. These include, dependency modeling, clustering large databases, correlation and link analysis. Traditional statistical methods are concerned with the corroboration of (a set of) hypotheses on a given body of data. Testing all of the hypotheses that can be generated from a database with millions of records and dozens of fields is clearly infeasible. Generating, on the other hand, a set of the most "promising" hypotheses (to be corroborated) requires much intuition and ingenuity. We present an efficient method for ranking the multidimensional hypotheses using image processing of data visualization. In the heart of the method lies the use of visualization techniques and image processing ideas to rank subsets of attributes according to the relation between them in the databases. Some of the scalability issues are solved by concise generalized histograms and by using an efficient on-line computation of clustering around a median with only five additional memory words. In addition to presenting our algorithmic methodology, we demonstrate its efficiency and performance by applying it to real census data sets, as well as synthetic data sets.

We are proposing a novel method that makes it possible to analyze high-dimensional data with arbitrary shaped projected clusters and high noise levels. At the core of our method lies the idea of subspace validity. We map the data in a way that allows us to test the quality of subspaces using statistical tests. Experimental results, both on synthetic and real data sets, demonstrate the potential of our method.

In this paper, we investigate how to further exploit the various characteristics of mean shift, in an attempt to achieve a robust and efficient clustering module for remotely sensed data. A mean shift algorithm has shown o be promising in various image-processing applications, specifically in cluster analysis.

Unsupervised clustering is a fundamental building block in numerous image processing applications. One of the most popular and widely used clustering schemes for remote sensing applications is the ISOCLUS algorithm, which is based on the ISODATA method. The algorithm is given a set of n data points in d-dimensional space, an integer k indicating the initial number of clusters, and a number of additional parameters. The general goal is to compute the coordinates of a set of cluster centers in d-space, such that those centers minimize the mean squared distance from each data point to its nearest center. This clustering algorithm is similar to another well-known clustering method, called k-means. One significant feature of ISOCLUS over k-means is that the actual number of clusters reported might be fewer or more than the number supplied as part of the input. The algorithm uses different heuristics to determine whether to merge lor split clusters. As ISOCLUS can run very slowly, particularly on large data sets, there has been a growing .interest in the remote sensing community in computing it efficiently. We have developed a faster implementation of the ISOCLUS algorithm. Our improvement is based on a recent acceleration to the k-means algorithm of Kanungo, et al. They showed that, by using a kd-tree data structure for storing the data, it is possible to reduce the running time of k-means. We have adapted this method for the ISOCLUS algorithm, and we show that it is possible to achieve essentially the same results as ISOCLUS on large data sets, but with significantly lower running times. This adaptation involves computing a number of cluster statistics that are needed for ISOCLUS but not for k-means. Both the k-means and ISOCLUS algorithms are based on iterative schemes, in which nearest neighbors are calculated until some convergence criterion is satisfied. Each iteration requires that the nearest center for each data point be computed. Naively, this requires O(kn) time, where k denotes the current number of centers. Traditional techniques for accelerating nearest neighbor searching involve storing the k centers in a data structure. However, because of the iterative nature of the algorithm, this data structure would need to be rebuilt with each new iteration. Our approach is to store the data points in a kd-tree data structure. The assignment of points to nearest neighbors is carried out by a filtering process, which successively eliminates centers that can not possibly be the nearest neighbor for a given region of space. This algorithm is significantly faster, because large groups of data points can be assigned to their nearest center in a single operation. Preliminary results on a number of real Landsat datasets show that our revised ISOCLUS-like scheme runs about twice as fast.

The study of global environmental changes involves the comparison, fusion, and integration of multiple types of remotely-sensed data at various temporal, radiometric, and spatial resolutions. Results of this integration may be utilized for global change analysis, as well as for the validation of new instruments or for new data analysis. Furthermore, future multiple satellite missions will include many different sensors carried on separate platforms, and the amount of remote sensing data to be combined is increasing tremendously. For all of these applications, the first requires step is fast and automatic registration, and as this need for automating registration techniques is being recognized, it becomes necessary to survey all the registration methods which may be applicable to Earth and space science problems and to evaluate their performances on a large variety of existing remote sensing data as well as on simulated data of soon-to-be-flown instruments. In this paper we present one of the first steps toward such as exhaustive quantitative evaluation. First, the different components of image registration algorithms are reviewed, and different choices for each of these components are described. Then, the results of the evaluation of the corresponding algorithms combing these components are described. Then, the results of the evaluation of the corresponding algorithms combining these components are presented on several datasets. The algorithms are based on gray levels or wavelet features and compute rigid transformations (including scale, rotation, and shifts). Test datasets include synthetic data as well as data acquired over several EOS Land Validation Core Sites with the IKONOS and the Landsat-7 sensors.

In k-means clustering we are given a set of n data points in d-dimensional space ℜd and an integer k, and the problem is to determine a set of k points in ℜd, called centers, to minimize the mean squared distance from each data point to its nearest center. No exact polynomial-time algorithms are known for this problem. Although asymptotically efficient approximation algorithms exist, these algorithms are not practical due to the extremely high constant factors involved. There are many heuristics that are used in practice, but we know of no bounds on their performance.We consider the question of whether there exists a simple and practical approximation algorithm for k-means clustering. We present a local improvement heuristic based on swapping centers in and out. We prove that this yields a (9+ε)-approximation algorithm. We show that the approximation factor is almost tight, by giving an example for which the algorithm achieves an approximation factor of (9-ε). To establish the practical value of the heuristic, we present an empirical study that shows that, when combined with Lloyd's algorithm, this heuristic performs quite well in practice.

An artificial neural network (ANN) for change detection from multi-temporal satellite images, which was reported in I. Feldberg (2001), has been further developed and tested, as part of a study of an area of high spatio-temporal heterogeneity along a climatic gradient between humid and and climate regions. Four recognition classes, "positive change", "negative change", "false change", and "no change" were learned by a backpropagation feedforward ANN and then applied to Landsat images that were acquired over the study area in 1992 and 1997. A comparison with existing classification techniques indicates, in many instances, significantly improved performance due to the ANN developed.

A new technique utilizing combination of feature extraction by change vector analysis and analysis of distances between features allows improvement in change detection of linear features such as roads and water channels. The technique reduces false detection of changes due to image calibration differences, illumination differences and misregistration. The method was applied to areas of steep climatic gradient between Mediterranean and extreme desert regions.

In k-means clustering, we are given a set of n data points in d-dimensional space R/sup d/ and an integer k and the problem is to determine a set of k points in Rd, called centers, so as to minimize the mean squared distance from each data point to its nearest center. A popular heuristic for k-means clustering is Lloyd's (1982) algorithm. We present a simple and efficient implementation of Lloyd's k-means clustering algorithm, which we call the filtering algorithm. This algorithm is easy to implement, requiring a kd-tree as the only major data structure. We establish the practical efficiency of the filtering algorithm in two ways. First, we present a data-sensitive analysis of the algorithm's running time, which shows that the algorithm runs faster as the separation between clusters increases. Second, we present a number of empirical studies both on synthetically generated data and on real data sets from applications in color quantization, data compression, and image segmentation.

Computing discrete two-dimensional (2-D) convolutions is an important problem in image processing. In mathematical morphology, an important variant is that of computing binary convolutions, where the kernel of the convolution is a 0-1 valued function. This operation can be quite costly, especially when large kernels are involved. We present an algorithm for computing convolutions of this form, where the kernel of the binary convolution is derived from a convex polygon. Because the kernel is a geometric object, we allow the algorithm some flexibility in how it elects to digitize the convex kernel at each placement, as long as the digitization satisfies certain reasonable requirements. We say that such a convolution is valid. Given this flexibility we show that it is possible to compute binary convolutions more efficiently than would normally be possible for large kernels. Our main result is an algorithm which, given an m x n image and a k-sided convex polygonal kernel K, computes a valid convolution in O(kmn) time. Unlike standard algorithms for computing correlations and convolutions, the running time is independent of the area or perimeter of K, and our techniques do not rely on computing fast Fourier transforms. Our algorithm is based on a novel use of Bresenham's (1965) line-drawing algorithm and prefix-sums to update the convolution incrementally as the kernel is moved from one position to another across the image.

means clustering is a very popular clustering technique, which is used in numerous applications.Given a set of n data points in R d and an integer k, the problem is to determine a set of k points R d, called centers, so as to minimize the mean squared distance from each data point to its nearest center.A popular heuristic for k-means clustering is Lloyd's algorithm.In this paper we present a simple and efficient implementation of Lloyd's k-means clustering algorithm, which we call the filtering algorithm.This algorithm is very easy to implement.It differs from most other approaches in that it precomputes a kd-tree data structure for the data points rather than the center points.We establish the practical efficiency of the filtering algorithm in two ways.First, we present a data-sensitive analysis of the algorithm's running time.Second, we have implemented the algorithm and performed a number of empirical studies, both on synthetically generated data and on real data from applications in color quantization, compression, and segmentation.

Given two images of roughly the same scene, image registration is the process of determining the transformation that most nearly maps one image to another.This problem is of particular interest in remote sensing applications, where it is known that two images correspond to roughly the same gecgraphic region, but the exact alignment between the images io not known.There are many approaches to image registration.We will consider an approach based on extracting a Ret of point features from each of the two images, and thus reducing the problem to a point pattern matching problem.Because of measurement errors and the presence of outlying data points in either of the images, it is important that the diotance measure between two point sets be robust to theeo cffecto.We will measure distances using the partial Hauodorff distance, An important element of image registration applications is that the search begins with a priori information on the bounds of transformation, and a good algorithm should be able to take advantage of this information.Point matching can be a computationally intensive task, and there have been a number of algorithms and approaches proposed for solving this problem, both from theoretical and applied standpoints.One common approach is based on a *Dopartmont of Computer

Consider a set of S of n data points in real d -dimensional space, R d , where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess S into a data structure, so that given any query point q ∈ R d , is the closest point of S to q can be reported quickly. Given any positive real ϵ, data point p is a (1 +ϵ)- approximate nearest neighbor of q if its distance from q is within a factor of (1 + ϵ) of the distance to the true nearest neighbor. We show that it is possible to preprocess a set of n points in R d in O(dn log n ) time and O(dn) space, so that given a query point q ∈ R d , and ϵ > 0, a (1 + ϵ)-approximate nearest neighbor of q can be computed in O ( c d , ϵ log n ) time, where c d,ϵ ≤ d ⌈1 + 6d/ϵ⌉ d is a factor depending only on dimension and ϵ. In general, we show that given an integer k ≥ 1, (1 + ϵ)-approximations to the k nearest neighbors of q can be computed in additional O(kd log n ) time.

This paper treats the problem of detecting straight or circular pieces of road in noisy aerial images. It first uses a local nonlinear operator to detect pixels whose neighborhoods are line-like, and then applies (robust) estimation techniques to find sets of such pixels that lie on, or near straight or circular loci. An (unbiased) ordinary least squares estimator cannot handle outlying data; on the other hand, conventional robust techniques for fitting circular arcs are severely affected by digitization effects and the fact that road circular segments are typically short and shallow. We therefore introduce an estimator that is both robust and statistically efficient.

A robotic agent operating in an unknown and complex environment may employ a search strategy of some kind to perform a navigational task such as reaching a given goal. In the process of performing the task, the agent can attempt to discover characteristics of its environment that enable it to choose a more efficient search strategy for that environment. If the agent is able to do this, we can say that it has "learned to navigate" — i.e., to improve its navigational performance. This paper describes how an agent can learn to improve its goal-finding performance in a class of discrete spaces, represented by graphs embedded in the plane. We compare several basic search strategies on two different classes of "random" graphs and show how information collected during the traversal of a graph can be used to classify the graph, thus allowing the agent to choose the search strategy best suited for that graph.

The conventional ordinary least squares (OLS) method of fitting a line to a set of data points is very unreliable when the amount of random noise in the input (such as an image) is significant compared with the amount of data that is correlated with the lane itself. In this paper we present an analytic method of separating the data of interest from the outliers. We assume that the overall data (i.e., the line data plus the noise) can be modeled as a mixture of two statistical distributions. Applying a variant of the method of moments (MoM) to the assumed model yields an analytic estimate of the desired line.

In fitting a straight line to a noisy image, the least-squares method becomes highly unreliable either when the noise distribution is nonnormal or when it is contaminated by outliers. The authors propose a nonparametric method, the median of the intercepts, to overcome these difficulties. This method is free of assumptions about the noise distribution and insensitive to outliers, and it does not require quantization of the parameter space. Thus, unlike the Hough transform, its outcome does not depend on the bin size. The method is efficient and its implementation does not involve practical difficulties such as local minima or poor convergence of iterative procedures.>