A similarity measure for silhouettes of 2D objects ispresented, and its properties are analyzed with respectto retrieval of similar objects in an image database.Our measure profits from a novel approach to subdivision of objects into parts of visual form. To compute our similarity measure, we first establish the best possible correspondence of visual parts, which is basedon a correspondence of convex boundary arcs. Thenthe similarity between corresponding arcs is computedand aggregated. We applied our similarity measure toshape matching of object contours in various imagedatabases and compared it to well known approachesin the literature. The experimental results justify thatour shape matching procedure gives an intuitive shapecorrespondence and is stable with respect to noise distortions.

We propose a simple and natural rule for decomposition of 2D objects into parts of visual form. The hierarchical convexity rule states that visual parts axe enclosed by maximal convex boundary arcs (with respect to the object) at various levels of curve evolution. The proposed rule is based on a novel curve evolution method by digital linearization in which a significant visual part will become a convex part at some level of the evolution. The hierarchical convexity rule determines not only parts of boundary curves but directly the visual parts of objects, and the evolution hierarchy induces a hierarchical structure of the obtained visual parts. Further, we derive a shape similarity measure based on the decomposition into visual parts and apply it to shape matching of object contours in an image database. The experimental results justify that our shape matching procedure is stable and robust with respect to noise deformations and gives an intuitive shape correspondence.

A similarity measure for silhouettes of 2D objects is presented, and its properties are analyzed with respect to retrieval of similar objects in an image database. Our measure profits from a novel approach to subdivision of objects into parts of visual form. To compute our similarity measure, we first establish the best possible correspondence of visual parts, which is based on a correspondence of convex boundary arcs. Then the similarity between correspondence arcs is computed and aggregated. We applied our similarity measure to shape matching of object contours in various image databases and compared it to well-known approaches in the literature. The experimental results justify that our shape matching procedure gives an intuitive shape correspondence and is stable with respect to noise distortions.

We propose a simple approach to evolution of digital planar curves that is specially designed to fit discrete nature of curves in digital images. The obtained curve evolution method by digital linearization has many advantages in comparison to curve evolutions in scale-space theories that are usually guided by diffusion equations. We will show that it leads to simplification of shape complexity, analog to evolutions guided by diffusion equations, but with no blurring (i.e., shape rounding) effects and no dislocation of relevant features. Moreover, in our approach the problem to determine the size of discrete steps for numerical implementations does not occur, since our evolution method leads in a natural way to a finite number of discrete evolution steps which are just the iterations of a basic procedure of digital linearization.

We concentrate here on decomposition of 2D objects into meaningfulparts of visual form, orvisual parts. It is a simple observation that convex parts of objects determine visual parts. However, the problem is that many significant visual parts are not convex, since a visual part may have concavities. We solve this problem by identifying convex parts at different stages of a proposed contour evolution method in which significant visual parts will become convex object parts at higher stages of the evolution. We obtain a novel rule for decomposition of 2D objects into visual parts, called the hierarchical convexity rule, which states that visual parts are enclosed by maximal convex (with respect to the object) boundary arcs at different stages of the contour evolution. This rule determines not only parts of boundary curves but directly the visual parts of objects. Moreover, the stages of the evolution hierarchy induce a hierarchical structure of the visual parts. The more advanced the stage of contour evolution, the more significant is the shape contribution of the obtained visual parts.

We propose a simple approach to evolution of polygonal curves that is specially designed to fit the discrete nature of curves in digital images. It leads to simplification of shape complexity with no blurring (i.e. shape rounding) effects and no dislocation of relevant features. Moreover, in our approach the problem to determine the size of discrete steps for numerical implementations does not occur since our evolution method leads in a natural way to a finite number of discrete evolution steps which are just the iterations of a basic procedure of vertex deletion

The Core Experiment CE-Shape-1 for shape descriptors
performed for the MPEG-7 standard gave a unique opportunity to compare various shape descriptors for non-rigid
shapes with a single closed contour. There are two main differences with respect to other comparison results reported
in the literature: (1) For each shape descriptor, the experiments were carried out by an institute that is in favor of
this descriptor. This implies that the parameters for each
system were optimally determined and the implementations
were throughly tested. (2) It was possible to compare the
performance of shape descriptors based on totally different
mathematical approaches. A more theoretical comparison
of these descriptors seems to be extremely hard. In this paper we report on the MPEG-7 Core Experiment CE-Shape1.

A cognitively motivated similarity measure is presented and its properties are analyzed with respect to retrieval of similar objects in image databases of silhouettes of 2D objects. To reduce influence of digitization noise, as well as segmentation errors, the shapes are simplified by a novel process of digital curve evolution. To compute our similarity measure, we first establish the best possible correspondence of visual parts (without explicitly computing the visual parts). Then, the similarity between corresponding parts is computed and aggregated. We applied our similarity measure to shape matching of object contours in various image databases and compared it to well-known approaches in the literature. The experimental results justify that our shape matching procedure gives an intuitive shape correspondence and is stable with respect to noise distortions.

Recently Latecki and Lakaemper (Computer Vision and Image Understanding 73:3, March 1999) reported a novel process for a discrete curve evolution. This process has various application possibilities, in particular, for noise removal and shape simpli cation of boundary curves in digital images. In this paper we prove t h a t the process of the discrete curve evolution is continuous: if polygon Q is close to polygon P, then the polygons obtained by their evolution remain close. This result follows directly from the fact that the evolution of Q corresponds to the evolution of P if Q approximates P. This intuitively means that rst all vertices of Q are deleted that are not close to any v ertex of P, and then, whenever a vertex of P is deleted, then a vertex of Q that is close to it is deleted in the corresponding evolution step of Q.

This paper addresses the problem of piecewise linear approximation of point sets without any constraints on the order of data points or the number of model components (line segments). We point out two problems with the maximum likelihood estimate (MLE) that present serious drawbacks in practical applications. One is that the parametric models obtained using a classical MLE framework are not guaranteed to be close to data points. It is typically impossible, in this classical framework, to detect whether a parametric model fits the data well or not. The second problem is related to accurately choosing the optimal number of model components. We first fit a nonparametric density to the data points and use it to define a neighborhood of the data. Observations inside this neighborhood are deemed informative; those outside the neighborhood are deemed uninformative for our purpose. This provides us with a means to recognize when models fail to properly fit the data. We then obtain maximum likelihood estimates by optimizing the Kullback-Leibler Divergence (KLD) between the nonparametric data density restricted to this neighborhood and a mixture of parametric models. We prove that, under the assumption of a reasonably large sample size, the inferred model components are close to their ground truth model component counterparts. This holds independently of the initial number of assumed model components or their associated parameters. Moreover, in the proposed approach, we are able to estimate the number of significant model components without any additional computation.

A cognitively motivated similarity measure is presented and its properties are analyzed with respect to retrieval of similar objects in image databases of silhouettes of 2D objects. To reduce influence of digitization noise as well as segmentation errors the shapes are simplified by a novel process of digital curve evolution. To compute our similarity measure, we first establish the best possible correspondence of visual parts (without explicitly computing the visual parts). Then the similarity between corresponding parts is computed and aggregated. We applied our similarity measure to shape matching of object contours in various image databases and compared it to well-known approaches in the literature. The experimental results justify that our shape matching procedure gives an intuitive shape correspondence and is stable with respect to noise distortions.

A similarity measure for silhouettes of 2D objects is presented, and its properties are analyzed with respect to retrieval of similar objects in image databases. To reduce influence of digitization noise as well as segmentation errors the shapes are simplified by a new process of digital curve evolution. To compute our similarity measure, we first establish the best possible correspondence of visual parts (without explicitly computing the visual parts). Then the similarity between corresponding parts is computed and summed. Experimental results show that our shape matching procedure gives an intuitive shape correspondence and is stable with respect to noise distortions.

In this paper we present a shape similarity system that is based on correspondence of visual parts, and apply it to robot localization and mapping. This is a particularly interesting application, since the scale selection problem does not occur here and visual parts can be obtained in a very simple way. Therefore, only the problem of subpart selection needs to be solved. Our solution to this problem is based on a contour based shape similarity measure supplemented by a structural arrangement information of visual parts.

(abstract not available)

This paper presents a new approach to the problem of building a global map from laser range data, utilizing shape-based object recognition techniques originally de veloped for tasks in computer vision. In contrast to clas sical approaches, the perceived environment is represented by polygonal curves (polylines), possibly containing rich shape information yet consisting of a relatively small num ber of vertices. The main task, besides the segmentation of raw scan point data into polylines and the removal of noise, is to find corresponding environmental features in consec utive scans to merge the polyline data to a global map. The correspondence problem is solved using shape similarity between the polylines. The approach does not require any odometry data and is robust to discontinuities in robot pose, e.g., when the robot slips. Since higher order objects in the form of polylines are present, our representation is well suited to maintaining global consistency.

(abstract not available)

The paper presents a novel approach for learning object parts by optimizing for recognition performance, utilizing a cognitively motivated strategy to first extract dissimilar parts and then select the most discriminative ones. This method incorporates a part-based shape similarity measure that can compare and match object parts, even when they are distorted or at different scales, enabling effective comparison of object structures for tasks like shape retrieval and classification.

We present a novel geometric model for robot mapping suited for robots equipped with a laser range finder. The geometric representation is based on shape. Cyclic ordered sets of polygonal lines are the underlying data structures. Specially adapted shape matching techniques originating from computer vision are applied to match range scan against the partially constructed map. Shape matching respects for a wider context than conventional scan matching approaches, allowing to disregard pose estimations. The described shape based approach is an improvement of the underlying geometric models of todays SLAM implementations. Moreover, using our object-centered approach allows for compact representations that are well-suited to bridge the gap from metric information needed in robot motion and path planning to more abstract, i.e. topological or qualitative spatial knowledge desired in complex navigational tasks or communication.

This paper presents a new approach to the problem of building a global map from laser range data, utilizing shape based object recognition techniques originally developed for tasks in com- puter vision. In contrast to classical approaches, the perceived en- vironment is represented by polygonal curves (polylines), possibly containing rich shape information yet consisting of a relatively small number of vertices. The main task, besides segmentation of the raw scan point data into polylines and denoising, is to find corresponding environmental features in consecutive scans to merge the polyline- data to a global map. The correspondence problem is solved using shape similarity between the polylines. The approach does not re- quire any odometry data and is robust to discontinuities in robot po- sition, e.g., when the robot slips. Since higher order objects in the form of polylines and their shape similarity are present in our ap- proach, it provides a link between the necessary low-leve...

The purpose of this paper is to present a technique to create a global map of a robot's surrounding by converting the raw data acquired from a scanning sensor to a compact map composed of just a few generalized polylines (polygonal curves). To merge a new scan with a previously computed map of the surrounding we use an approach that is composed of a local geometric process of merging similar line segments (termed Discrete Segment Evolution) of map and scan with a global statistical control process. The merging process is applied to a dataset gained from a real robot to show its ability to incrementally build a map showing the environment the robot has traveled through.

Humans are able to recognize objects in the presence of significant amounts of occlusion and changes in the view angle. In human and robot vision, these conditions are normal situations and not exceptions. In digital images one more problem occurs due to unstable outcomes of the segmentation algorithms. Thus, a normal case is that a given shape is only partially visible, and the visible part is distorted. To our knowledge there does not exist a shape representation and similarity approach that could work under these conditions. However, such an approach is necessary to solve the object recognition problem. The main contribution of this paper is the definition of an optimal partial shape similarity measure that works under these conditions. In particular, the presented novel approach to shape-based object recognition works

We consider the problem of elastic matching of time series. We propose an algorithm that determines a subsequence of a target time series that best matches a query series. In the proposed algorithm we map the problem of the best matching subsequence to the problem of a cheapest path in a DAG (directed acyclic graph). The proposed approach allows us to also compute the optimal scale and translation of time series values, which is a nontrivial problem in the case of subsequence matching.

The purpose of this paper is to present a technique to create a global map of robots' surroundings by converting the raw data acquired from a scanning sensor to a compact map composed of just a few generalized polylines (polygonal curves). We propose a new approach to merging robots' maps that is composed of a local geometric process of merging similar line segments (termed Discrete Segment Evolution) with a global statistical control process. In the case of single robot, we are able to incrementally build a map showing the environment the robot has traveled through by merging its polygonal map with actual scans. In the case of a robot team, we are able to identify common parts of their partial maps and if common parts are present construct a joint map of the explored environment.

We consider a problem of elastic matching of time series. We propose an algorithm that automatically determines a subsequence b0 of a target time series b that best matches a query series a. In the proposed algorithm we map the problem of the best matching subsequence to the problem of a cheapest path in a DAG (directed acyclic graph). Our experimental results demonstrate that the proposed algorithm outperforms the commonly used Dynamic Time Warping in retrieval accuracy.

Our domain of interest is polygonal (and polyhedral) approximation of point sets. Neither the order of data points nor the number of needed line segments (surface patches) are known. In particular, point sets can be obtained by laser range scanner mounted on a moving robot or given as edge pixels/voxels in digital images. Polygonal approximation of edge pixels can also 1 View

We will provide psychophysical evidence that recognition of parts of object contours is a necessary component of object recognition. It seems to be obvious that the recognition of parts of object contours is performed by applying a partial shape similarity measure to the query contour part and to the known contour parts. The recognition is completed once a sufficiently similar contour part is found in the database of known contour parts. We will derive necessary requirements for any partial shape similarity measure based on this scenario. We will show that existing shape similarity measures do not satisfy these requirements, and propose a new partial shape similarity measure.

The proposed algorithm segments planar structures out of data gained from 3D laser range scanners, typically used in robotics. The approach first fits planar patches to the dataset, using a new, extended expectation maximization (EM) algorithm. This algorithm solves the classical EM problems of insufficient initialization by iteratively determining the number and positions of patches in a split and merge

This paper discusses a framework for integrated Augmented Reality (AR) architecture for indoor thermal performance data visualization that utilizes a mobile robot to generate environment maps. It consists of three modules: robot mapping, Computational Fluid Dynamics (CFD) simulation, and AR visualization. The robot mapping module enables the modelling of spatial geometry using a mobile robot. In order to generate steady approximations to scanned 3D datasets, the paper presents a novel "Split and Merge Expectation-Maximization Patch Fitting" (SMEMPF) planar approximation method. The developed SMEMPF method extends the classical Expectation-Maximization (EM) algorithm. It allows for precise adjustment of patches independent from the initial model. The final result is a set of patches identifying planar macro structures that consist of a collection of supported tiles. These patches are utilized to model the spatial geometry under investigation. The CFD simulation module facilitates the prediction of building performance data based on the spatial data generated using the SMEMPF method. The AR visualization module assists in interactive, immersive visualization of CFD simulation results. Such an integrated AR architecture will facilitate rapid multi-room mobile AR visualizations.

We introduce a new EM framework in which it is possible not only to optimize the model parameters but also the number of model components. A key feature of our approach is that we use nonparametric density estimation to improve parametric density estimation in the EM framework. While the classical EM algorithm estimates model parameters empirically using the data points themselves, we estimate them using nonparametric density estimates. There exist many possible applications that require optimal adjustment of model components. We present experimental results in two domains. One is polygonal approximation of laser range data, which is an active research topic in robot navigation. The other is grouping of edge pixels to contour boundaries, which still belongs to unsolved problems in computer vision.

Our goal is polygonal approximation of laser range data points obtained by a mobile robot. The proposed approach provides a precise estimation of the number of model components (line segments) and their initial parameters independent of their initial values. We use principles of perceptual grouping to evaluate the approximation quality obtained in each Expectation Maximization (EM) step. By evaluating EM approximation quality we are able to recognize a locally optimal solution, and modify the number of model components and their parameters. Consequently, EM can converge only to a globally optimal solution independent of the initial number of model components and their initial parameters.

Rescue robots operate in disaster areas where odometric information is known to be highly unreliable. This paper presents a new approach to odometry independent 2D robot mapping. Scans obtained from different robot positions are assembled to a single global map using alignment based on scan intrinsic information only, namely shape features. The approach detects geometric structures in different scans which are similar by shape and aligns the scans accordingly. The detection of shape similarity is the key to generate global maps even of highly cluttered environments and thus the proposed approach is particularly suitable for applications in the field of rescue robots.

The proposed algorithm segments planar structures out of data gained from 3D laser range scanners, typically used in robotics. The approach first fits planar patches to the dataset, using a new, extended Expectation Maximization (EM) algorithm. This algorithm solves the classical EM problems of insufficient initialization by iteratively determining the number and positions of patches in a split and merge framework. Determining the fitting quality of the gained patches, the approach then allows for segmentation of planar surfaces out of the 3D environment. The result is a set of 2D objects, which can be used as input for classical computer vision applications, in particular for object recognition. Our approach makes it possible to apply classical tools of 2D image processing to solve problems of 3D robot mapping, e.g. landmark recognition.

The paper deals with fitting of planar patches to 3D laser range data obtained by a mobile robot. The number and the initial position of the patches are unknown, hence their estimation is a challenging problem. It is solved by adding iterated steps of split and merge to a modified Expectation Maximization (EM) algorithm. This allows for precise adjustment of the number of patches, independent from the initial model. The proposed approach overcomes the problem of classical EM, which produces an optimal solution only if the number and position of model components is well estimated.

We present a force field based approach for simultaneous alignment of multiple laser scans in robot mapping. It avoids sensitive behavior to wrong data associations and sparse sensing, which are the main challenges e.g. in multi robot mapping under the constraints given in autonomous search and rescue robotics. The presented algorithm solves the alignment problem utilizing a gradient descent approach motivated by physics, but exchanges laws of physics with constraints given by human perception. Experiments on different real world data sets show the successful application of the algorithm.

The paper deals with grouping of edges to contours of
shapes using only local symmetry and continuity. Shape
skeletons are used to generate the search space for a version of the Markov Chain Monte Carlo approach utilizing
particle filters to find the most likely skeleton. Intuitively
this means that grouping of edge segments is performed by
walking along the skeleton. The particle search, which is
an adapted version of a successful algorithm in robot mapping, is assisted by a reference model of a shape, which
is expressed as the sequence of sample points and radii of
maximal skeleton disks. This model is sufficiently flexible to
represent non-rigid deformations, but restrictive enough to
perform well on real, noisy image data. The order of skeleton points (and their corresponding segments) found by the
particles defines the grouping.

This paper describes a novel approach, called Force Field Simulation, to multi robot mapping that works under the constraints given in autonomous search and rescue robotics. Extremely poor prealignment, lack of landmarks, and minimal overlap between scans are the main challenges. The presented algorithm solves the alignment problem of such laser scans utilizing a gradient descent approach motivated by physics, namely simulation of movement of masses in gravitational fields, but exchanges laws of physics with constraints given by human perception. Experiments on different real world data sets show the successful application of the algorithm. We also provide an experimental comparison with classical ICP implementation and a Lu/Milios-type alignment algorithm.

The focus of this paper is on the performance comparison of two simultaneous localization and mapping (SLAM) algorithms namely 6D Lu/Milios SLAM and Force Field Simulation (FFS). The two algorithms are applied to a 2D data set. Although the algorithms generate overall visually comparable results, they show strengths & weaknesses in different regions of the generated global maps. The question we address in this paper is, if different ways of evaluating the performance of SLAM algorithms project different strengths and how can the evaluations be useful in selecting an algorithm. We will compare the performance of the algorithms in different ways, using grid and pose based quality measures.

Alignment of sensor data, typically acquired from cameras, laser range scanners, or sonar sensors, is the basis for all robot mapping tasks. Recent advances in the development of laser range devices make research on laser range alignment a focus of robot mapping research. In contrast to cameras, laser range scanners offer relatively precise depth information, yet the feature density is relatively sparse. ...

(abstract not available)

Merging local maps, acquired by multiple robots, into a global map, (also known as map merging) is one of the important issues faced by virtually all cooperative exploration techniques. We present a novel and simple solution to the problem of map merging by reducing it to the problem of SLAM of a single "virtual" robot. The individual local maps and their shape information constitute the sensor information for the virtual robot. This approach allows us to adapt the framework of Rao-Blackwellized particle filtering used in SLAM of a single robot for the problem of map merging.

The paper shows how particle filters can be used to establish visually consistent partial correspondences between similar features in unrestricted 2D point sets representing shapes. Given an update rule, the PF system has the advantage that global constraints can be learned. We motivate and define the update rule for the given task and show its superior performance in comparison to 0 Views

Given two shapes, the correspondence between distinct visual features is the basis for most alignment processes and shape similarity measures. This paper presents an approach introducing particle filters to establish perceptually correct correspondences between point sets representing shapes. Local shape feature descriptors are used to establish correspondence probabilities. The global correspondence structure is calculated using additional constraints based on domain knowledge. Domain knowledge is characterized as prior distributions expressing hypotheses about the global relationships between shapes. These hypotheses are generated during the iterative particle filtering process. Experiments using standard alignment techniques, based on the given correspondence relationships, demonstrate the advantages of this approach.

We present a system to increase the performance of feature correspondence based alignment algorithms for laser scan data. Alignment approaches for robot mapping, like ICP or FFS, perform successfully only under the condition of sufficient overlap of features between individual scans. This condition is often not met, for example in sparsely scanned environments or disaster areas for search and rescue robot tasks. Assuming mid level world knowledge (in the presented case, weak presence of noisy, roughly linear or rectangular-like objects) our system augments the sensor data with hypotheses ('Virtual Scans') about ideal models of these objects. These hypotheses are generated by analyzing the current aligned map estimated by the underlying iterative alignment algorithm. The augmented data is used to improve the alignment process. Feedback between the data alignment and the data analysis confirms, modifies, or discards the Virtual Scans in each iteration. Experiments with a simulated scenario and real world data from a rescue robot scenario show the applicability and advantages of the approach.

We present a new similarity measure between a single shape and a shape group as a basis for shape clustering following the paradigm of context dependent shape comparison: clusters are generated in the context of a reference shape, defined by the query shape it is compared to. Tightly coupled, the distance measure is the basis for a soft k-means like framework to achieve robust clustering. Successful application of the system along with generation of shape prototypes is demonstrated in comparison to latest approaches using elastic deformation

In this paper we present a system to enhance the performance of feature correspondence based alignment algorithms for laser scan data. We show how this system can be utilized as a new approach for evaluation of mapping algorithms. Assuming a certain a priori knowledge, our system augments the sensor data with hypotheses ('Virtual Scans') about ideal models of objects in the robot's environment. These hypotheses are generated by analysis of the current aligned map estimated by an underlying iterative alignment algorithm. The augmented data is used to improve the alignment process. Feedback between data alignment and data analysis confirms, modifies, or discards the Virtual Scans in each iteration. Experiments with a simulated scenario and real world data from a rescue robot scenario show the applicability and advantages of the approach. By replacing the estimated 'Virtual Scans' with ground truth maps our system can provide a flexible way for evaluating different mapping algorithms in different settings.

Merging local maps, acquired by multiple robots, into a global map, (also known as map merging) is one of the important issues faced by virtually all cooperative exploration techniques. We present a novel and simple solution to the problem of map merging by reducing it to the problem of SLAM of a single "virtual" robot. The individual local maps and their shape information constitute the sensor information for the virtual robot. This approach allows us to adapt the framework of Rao-Blackwellized particle filtering used in SLAM of a single robot for the problem of map merging.

Decomposing a shape into meaningful components plays a strong role in shape-related applications. In this paper, we combine properties of skeleton and boundary to implement a general shape decomposition approach. It is motivated by recent studies in visual human perception discussing the importance of certain shape boundary features as well as features of the shape area; it utilizes certain properties of the shape skeleton combined with boundary features to determine protrusion strength. Experiments yield results similar to those from human subjects on abstract shape data. Also, experiments of different data sets prove the robustness of the combined skeleton-boundary approach.

This paper discusses a framework for integrated augmented reality (AR) architecture for indoor thermal performance data visualization that utilizes a mobile robot to generate environment maps. It consists of three modules: robot mapping, computational fluid dynamics (CFD) simulation, and AR visualization. The robot mapping module enables the modeling of spatial geometry using a mobile robot. In order to generate steady approximations to scanned three-dimensional data sets, the paper presents a novel “split-and-merge expectation-maximization patch fitting” (SMEMPF) planar approximation method. It allows for precise adjustment of patches independent from the initial model. The final result is a set of patches identifying planar macrostructures that consist of a collection of supported tiles. These patches are used to model the spatial geometry under investigation. The CFD simulation module facilitates the prediction of building performance databased on the spatial data generated using the SMEMPF method. The AR visualization module assists in interactive and immersive visualization of CFD simulation results. Such an integrated AR architecture will facilitate rapid multiroom mobile AR visualizations.

In this paper we present a system to enhance the performance of feature correspondence based alignment algorithms for laser scan data. We show how this system can be utilized as a new approach for evaluation of mapping algorithms. Assuming a certain a priori knowledge, our system augments the sensor data with hypotheses ('Virtual Scans') about ideal models of objects in the robot's environment. These hypotheses are generated by analysis of the current aligned map estimated by an underlying iterative alignment algorithm. The augmented data is used to improve the alignment process. Feedback between data alignment and data analysis confirms, modifies, or discards the Virtual Scans in each iteration. Experiments with a simulated scenario and real world data from a rescue robot scenario show the applicability and advantages of the approach. By replacing the estimated 'Virtual Scans' with ground truth maps our system can provide a flexible way for evaluating different mapping algorithms in different settings.

(abstract not available)

Mobile robotic mapping is now considered to be a sufficiently mature field with demonstrated successes in various domains. While there has been much progress made in the development of computationally efficient and consistent mapping schemes, it is still murky at best on how these maps can be evaluated. We are motivated by the absence of an accepted standard for quantitatively measuring the performance of robotic mapping systems against user-defined requirements. It is our belief that the development of standardized methods for quantitatively evaluating existing robotic technologies will improve the utility of mobile robots in already established application areas, such as vacuum cleaning, robot surveillance, and bomb disposal, but will also enable the proliferation and acceptance of such technologies in other emerging markets. This Chapter summarizes our preliminary efforts by bringing together the research community towards addressing this important problem which has ramifications not only from a research perspective but also from consumers', robot manufacturers', and developers' viewpoints.

This paper addresses the problem of piecewise linear approximation of point sets without any constraints on the order of data points or the number of model components (line segments). We point out two problems with the maximum likelihood estimate (MLE) that present serious drawbacks in practical applications. One is that the parametric models obtained using a classical MLE framework are not guaranteed to be close to data points. It is typically impossible, in this classical framework, to detect whether a parametric model fits the data well or not. The second problem is related to accurately choosing the optimal number of model components. We first fit a nonparametric density to the data points and use it to define a neighborhood of the data. Observations inside this neighborhood are deemed informative; those outside the neighborhood are deemed uninformative for our purpose. This provides us with a means to recognize when models fail to properly fit the data. We then obtain maximum likelihood estimates by optimizing the Kullback-Leibler Divergence (KLD) between the nonparametric data density restricted to this neighborhood and a mixture of parametric models. We prove that, under the assumption of a reasonably large sample size, the inferred model components are close to their ground truth model component counterparts. This holds independently of the initial number of assumed model components or their associated parameters. Moreover, in the proposed approach, we are able to estimate the number of significant model components without any additional computation.

From mundane and repetitive tasks to assisting first responders in saving lives of victims in disaster scenarios, robots are expected to play an important role in our lives in the coming years. Despite recent advances in mobile robotic systems, lack of widely accepted performance metrics and standards hinder the progress in many application areas such as manufacturing, healthcare, and search and rescue. In this paper, we outline the importance of the development of standardized methods and objective performance evaluation/benchmarking of existing and emerging robotic technologies. We provide a survey of significant past efforts by researchers and developers around the globe and discuss how we can leverage such efforts in advancing the state-of-the-art. Using an example of designing a ‘standard’ evaluation toolkit for robotic mapping, we illustrate some of the problems faced in
developing objective performance metrics whilst accommodating the requirements and restrictions imposed by the intended domain of operation and other practical considerations.

Map confidence, or map quality based on regional consistency is an important measure to evaluate the quality of robot maps. It is classically handled analyzing occupancy grids, which is an unnatural choice if the map is not represented by data points, but by line segments. We define a map-confidence measure that is tailored for segment based maps, without leaving the compact data representation by segments. The presented confidence measure is not based on comparison to ground truth data, but evaluates the map (ground truth free) based on map consistency.

Line segment based representation of 2D robot maps is known to have advantages over raw point data or grid based representation gained from laser range scans. It significantly reduces the size of the data set. It also contains higher geometric information, which is necessary for robust post processing. The paper describes an algorithm to convert global 2D robot maps to line segment representation, using a pre-aligned set of point-based single scans as input. Mean-shift clustering on the set of all line segments is utilized to merge perceptually similar segments to single instances: locally linear features in the environment are unambiguously represented by single line segments in the final global map. Apart from a scaling parameter, the approach is parameter free. Experiments on real world data sets prove its applicability in the field of robot mapping.

The Performance Metrics for Intelligent Systems workshop is the only one of its kind dedicated to defining measures and methodologies of evaluating performance of intelligent systems. Started in 2000, the PerMIS series focuses on applications of performance measures to practical problems in commercial, industrial, homeland security, and military applications. It has proved to be an excellent forum for discussions and partnerships, dissemination of ideas, and future collaborations between researchers, graduate students, and practitioners from industry, academia, and government agencies.

This paper discusses a framework for integrated augmented reality ͑AR͒ architecture for indoor thermal performance data visualization that utilizes a mobile robot to generate environment maps. It consists of three modules: robot mapping, computational fluid dynamics ͑CFD͒ simulation, and AR visualization. The robot mapping module enables the modeling of spatial geometry using a mobile robot. In order to generate steady approximations to scanned three-dimensional data sets, the paper presents a novel "split-and-merge expectation-maximization patch fitting" ͑SMEMPF͒ planar approximation method. It allows for precise adjustment of patches independent from the initial model. The final result is a set of patches identifying planar macrostructures that consist of a collection of supported tiles. These patches are used to model the spatial geometry under investigation. The CFD simulation module facilitates the prediction of building performance databased on the spatial data generated using the SMEMPF method. The AR visualization module assists in interactive and immersive visualization of CFD simulation results. Such an integrated AR architecture will facilitate rapid multiroom mobile AR visualizations.

Constructing correspondences between points characterizing one shape with those characterizing another is crucial to understanding what the two shapes have in common. These correspondences are the basis for most alignment processes and shape similarity measures. In this paper we use particle filters to establish perceptually correct correspondences between point sets characterizing shapes. Local shape feature descriptors are used to establish the probability that a point on one shape corresponds to a point on the other shape. Global correspondence structures are calculated using additional constraints on domain knowledge. Domain knowledge is characterized by prior distributions which serve to characterize hypotheses about the global relationships between shapes. These hypotheses are formulated online. This means global constraints are learnt during the particle filtering process, which makes the approach especially interesting for applications where global constraints are hard to define a priori. As an example for such a case, experiments demonstrate the performance of our approach on partial shape matching.

We present a system to increase the performance of feature correspondence based alignment algorithms for laser scan data. Alignment approaches for robot mapping, like ICP or FFS, perform successfully only under the condition of sufficient feature overlap between single scans. This condition is often not met, e.g. in sparsely scanned environments or disaster areas for search and rescue robot tasks. Assuming mid level world knowledge (in the presented case the weak presence of noisy, roughly linear or rectangular-like objects) our system augments the sensor data with hypotheses ('Virtual Scans') about ideal models of these objects, based on analysis of a current estimated map of the underlying iterative alignment algorithm. Feedback between the data alignment and the data analysis confirms, modifies, or discards the Virtual Scan data in each iteration. Experiments with a simulated scenario and real world data from a rescue robot scenario show the applicability and advantages of the approach.

(abstract not available)

We present a system for 2D robot mapping which is entirely based on line segment representation of the environment. The system consists of multiple modules, i.e. scan number reduction, global scan alignment, scan merging and segmenterror filtering, which give an example of the simplicity of mid level data processing and the advanced possibilities opened by segment based design. The compact segment representation enables creation and optimization of a global pose graph for scan registration, which is the core of the mapping system. Experiments verify the applicability to real world data sets and lead to very compact maps, which represent single linear features, e.g. walls, with single line segments.

(abstract not available)

With funding from the Commerce Department's National Institute of Standards and Technology (NIST) Measurement Science and Engineering Research Grants, the authors have recently embarked on a three year project to create and experimentally validate a framework by which automated guided vehicles (AGVs) can automatically generate a sufficiently accurate internal map (world model) of its surroundings. The work presented in this paper discusses challenges involved and reports on a possible extension to a previously developed mapping technique in evaluating world models of such dynamic and unstructured environments. The paper also reports on the authors' views in bringing together the community to collectively address this problem from end-users', vendors' and developers' points of view.

(abstract not available)

(abstract not available)

This paper describes a fast plane extraction algorithm for 3D range data. Taking advantage of the point neighborhood structure in data acquired from 3D sensors like range cameras, laser range finders and Microsoft Kinect, it divides the plane-segment extraction task into three steps. The first step is a 2D line segment extraction from raw sensor data, interpreted as 2D data, followed by a line segment based connected component search. The final step finds planes based on connected segment component sets. The first step ..

This paper introduces an approach to classify robot environments based on planar segments extracted from 3D data. In a preprocessing step, point data from a 3D range sensor is transformed to planar patches, ie raw data is transformed to a mid level geometric representation. This step allows for a robust, simple and straightforward feature extraction. The features are fed into a learning algorithm, resulting in binary classification into two different types of indoor environments, hallways and office spaces. The main contribution ...

(abstract not available)

This article introduces the Temple Map Evaluation Toolkit (TMET), which is a tool for evaluating robotic maps produced by existing mapping algorithms. The toolkit performs ground truth based evaluation, ie it compares similarities between a map defined as ground truth and a target map. TMET allows for hybrid evaluation, since methods for pose based as well as grid based evaluation are implemented. For pose based evaluation, the user can define regions on the ground truth map which are handled as transformable sub-maps.

The paper describes a novel real-time algorithm for finding 3D geometric primitives (cylinders, cones and spheres) from 3D range data. In its core, it performs a fast model fitting with a model update in constant time (O(1)) for each new data point added to the model. We use a three stage approach.The first step inspects 1.5D sub spaces, to find ellipses. The next stage uses these ellipses as input by examining their neighborhood structure to form sets of candidates for the 3D geometric primitives. Finally, candidate ellipses are fitted to the geometric primitives. The complexity for point processing is O(n); additional time of lower order is needed for working on significantly smaller amount of mid-level objects. This allows the approach to process 30 frames per second on Kinect depth data, which suggests this approach as a pre-processing step for 3D real-time higher level tasks in robotics, like tracking or feature based mapping.

We consider the assembly of a three dimensional (3D) structure by a team of heterogeneous robots capable of online sensing and error correction during the assembly process. The automated assembly problem is posed as a general 3D tiling problem where the assembly components/tiles consist of various shapes and sizes. For a desired 3D structure, we first compute the partition of the assembly strategy into N c sub-components that can be executed in parallel by a team of N c assembly robots. To enable online error detection and correction during the assembly process, mobile robots equipped with visual depth sensors are tasked to scan, identify, and track the state of the structure. The objective is to enable online detection of missing assembly components and reassignment of these components to the team of assembly robots. We present the development of the planning, sensing, and control strategies employed and report on the experimental validation of these strategies using our multi-robot testbed.

This paper introduces a dynamic mapping algorithm based on line segments. The use of higher level geometric features allows for fast and robust identification of inconsistencies between incoming sensor data and an existing robotic map. Handling of these inconsistencies using a partial-segment likelihood measure produces a system for robot mapping that evolves with the changing features of a dynamic environment. The algorithm is tested in a large scale simulation of a storage logistics center, a real world office environment, and compared against the current state of the art.

The paper describes a novel real-time algorithm for finding 3D geometric primitives (cylinders, cones and spheres) from 3D range data. In its core, it performs a fast model fitting with a model update in constant time (O(1)) for each new data point added to the model. We use a three stage approach.The first step inspects 1.5D sub spaces, to find ellipses. The next stage uses these ellipses as input by examining their neighborhood structure to form sets of candidates for the 3D geometric primitives. Finally, candidate ellipses are fitted to the geometric primitives. The complexity for point processing is O(n); additional time of lower order is needed for working on significantly smaller amount of mid-level objects. This allows the approach to process 30 frames per second on Kinect depth data, which suggests this approach as a pre-processing step for 3D real-time higher level tasks in robotics, like tracking or feature based mapping.

We consider the assembly of a three-dimensional (3D) structure by a team of heterogeneous robots capable of online sensing and error correction during the assembly process. We build on our previous work and address the partitioning of the assembly task to maximize parallelization of the assembly process. Specifically, we consider 3D structures that can be assembled from a fixed collection of heterogeneous tiles that vary in shapes and sizes. Given a desired 3D structure, we first compute the partition of the assembly strategy into Na subcomponents that can be executed in parallel by a team of Na assembly robots. The assembly robots then perform online workload balancing during construction to minimize assembly time. To enable online error detection and correction during the assembly process, mobile robots equipped with visual depth sensors are tasked to scan, identify, and track the state of the structure. The result is a cooperative assembly framework where assembly robots can balance their individual workloads online by trading assembly components while scanning robots detect and reassign missing assembly components online. We present the integration of the planning, sensing, and control strategies employed in our framework and report on the experimental validation of the strategy using our multi-robot testbed.

First there was opera. Then there was rock opera. Now, two Temple faculty members are giving the world robot opera. Three research robots will join five singers and a chorus to present "Galatea_Reset" for three 90-minute performances in Temple’s Conwell Dance Theater on Sept. 20-21. The autonomous robots will produce all of the music and sounds as well as portray characters in the lyrical theater production. A collaborative work between Maurice Wright, Laura H. Carnell Professor of Music Composition in the Boyer College of Music and Dance, and Rolf Lakaemper, associate professor of computer and information sciences in the College of Science and Technology, "Galatea_Reset" tells the mythological story of sculptor Pygmalion, who falls in love with his creation Galatea only to have her brought to life for him by the Goddess Venus.

Humanoid robots are increasingly used to perform human mimicking tasks, such as walking, grasping, standing and sitting on objects. To generate poses interactively using a humanoid robot, the performed poses should be controlled to satisfy any potential interaction with the surrounding environment. In this paper, a simulated humanoid robot "NAO" is used to discover a fitness-based optimal sitting pose performed on various types of sittable-objects, varying in shape and height. Using an initial set of random valid sitting poses as the input generation, genetic algorithm (GA) is applied to construct the fitness-based optimal sitting pose for the robot to fit well on the sittable-object (i.e. box and ball). The used fitness criteria reflecting pose stability (i.e. how feasible the pose is based on real world physical limitation), converts poses into numerical stability level. The feasibility of the proposed approach is measured through a simulated environment using V-Rep simulator which shows how the GA is able to generate a fitness-based optimal sitting-pose. The real "NAO" robot is used to perform results generated by the simulation.

(not available)

The paper describes a novel real-time algorithm for finding 3D geometric primitives (cylinders, cones and spheres) from 3D range data. In its core, it performs a fast model fitting with a model update in constant time (O(1)) for each new data point added to the model. We use a three stage approach.The first step inspects 1.5D sub spaces, to find ellipses. The next stage uses these ellipses as input by examining their neighborhood structure to form sets of candidates for the 3D geometric primitives. Finally, candidate ellipses are fitted to the geometric primitives. The complexity for point processing is O(n); additional time of lower order is needed for working on significantly smaller amount of mid-level objects. This allows the approach to process 30 frames per second on Kinect depth data, which suggests this approach as a pre-processing step for 3D real-time higher level tasks in robotics, like tracking or feature based mapping.

The work presented in this paper is part of a project to enable humanoid robots to build a semantic understanding of their environment adopting unsupervised self-learning techniques. Here, we propose an approach to learn 3-dimensional human-pose conformations, i.e. structural arrangements of a (simplified) human skeleton model, given only a minimal verbal description of a human posture (e.g. "sitting", "standing", "tree pose"). The only tools given to the robot are knowledge about the skeleton model, as well as a connection to the labeled images database "google images". Hence the main contribution of this work is to filter relevant results from an images database, given a human-pose specific query words, and to transform the information in these (2D) images into a 3D pose that is the most likely to fit the human understanding of the keywords. Steps to achieve this goal integrate available 2D human-pose estimators using still images, clustering techniques to extract representative 2D human skeleton poses, and the 3D-pose from 2D-pose estimation. We evaluate the approach using different query keywords representing different postures.

This paper introduces a system for real-time, visual 3D scene description. A scene is described by planar patches and conical objects (cylinders, cones and spheres). The system makes use of sensor's natural point order, dimensionality reduction and fast incremental model update (in O(1)) to first build 2D geometric features. These features approximate the original data and form candidate sets of possible 3D object models. The candidate sets are used by a region growing algorithm to extract all targeted 3D objects. This two step (raw data to 2D features to 3D objects) approach is able to process 30 frames per second on Kinect depth data, which allows for real-time tracking and feature based robot mapping based on 3D range data.

The focus of this paper lies on the creation of 3D hu- man skeleton from a set of 2D images. Unlike available approaches, which utilize a single 2D image for 3D recon- struction, the prosecuted approach utilities a set of multi- ple images, which are obtained from a simple query to the google image database. We only assume, that a query key- word can be linked to a set of images, which contain a rep- resentative subset related to the query. We expect the data to also contain false (i.e. non human-pose related) images. Our approach uses a human-pose based 3D shape context model for matching human-poses in 3D space, and filter them using a hierarchical binary clustering approach. The performance of this approach is evaluated using different query keywords.

Recovering a 3D human-pose in the form of an abstracted skeleton from a 2D image suffers from loss of depth information. Assuming the projected human-pose is represented by a set of 2D landmarks capturing the human-pose limbs, recovering back the original 3D locations is an ill posed problem. To recover a 3D configuration, camera localization in 3D space plays a major role, an inaccurate camera localization might mislead the recovery process. In this paper, we propose a 3D camera localization model using only human-pose appearance in a 2D image (i.e., the set of 2D landmarks).