One of the key advantages of Federated Learning (FL) is its ability to collaboratively train a Machine Learning (ML) model while keeping clients' data on-site. However, this can create a false sense of security. Despite not sharing private data increases the overall privacy, prior studies have shown that gradients exchanged during the FL training remain vulnerable to Gradient Inversion Attacks (GIAs). These attacks allow reconstructing the clients' local data, breaking the privacy promise of FL. GIAs can be launched by either a passive or an active server. In the latter case, a malicious server manipulates the global model to facilitate data reconstruction. While effective, earlier attacks falling under this category have been demonstrated to be detectable by clients, limiting their real-world applicability. Recently, novel active GIAs have emerged, claiming to be far stealthier than previous approaches. This work provides the first comprehensive analysis of these claims, investigating four state-of-the-art GIAs. We propose novel lightweight client-side detection techniques, based on statistically improbable weight structures and anomalous loss and gradient dynamics. Extensive evaluation across several configurations demonstrates that our methods enable clients to effectively detect active GIAs without any modifications to the FL training protocol.

The issue of out-of-stock (OOS) represents a substantial challenge for retailers, often resulting in significant sales losses. To address this problem, this paper introduces an autonomous mobile robotic platform built on the Robot Operating System (ROS) framework, designed to accelerate the restocking process in supermarkets. The platform autonomously detects empty shelves and notifies human operators, streamlining inventory management. Equipped with advanced navigation capabilities, the proposed system employs a deep learning-based, two-stage architecture that identifies shelving areas and subsequently detects empty shelves. To validate the performance of the proposed two-stage artificial vision algorithm, two datasets were used: the first comprises approximately 2000 images (900 of them collected by our team from three different supermarkets), while the second dataset consists of around 5600 manually annotated images extracted from videos recorded in a supermarket by the robotic platform itself. Additionally, in order to validate the entire robotic system, an extensive experimental evaluation was conducted in a supermarket during regular business hours. The results demonstrate that the proposed platform substantially outperforms human operators, identifying OOS items eight times faster than traditional human operator based methods. This advancement provides valuable assistance to supermarket staff, significantly enhancing operational efficiency.

Internet of Things (IoT) devices are increasingly permeating homes, industries, and many other environments. The need for robust security measures in IoT networks has never been more critical, since they are becoming the preferred target for cyberattacks. In this paper, we address the challenge of detecting abnormal communication patterns in IoT networks using Graph Neural Networks (GNNs). To this end, we have conducted a comprehensive and fair comparison of machine learning approaches and GNNs, for both static and dynamic graphs, across three recent datasets, IoT23, IoTID20, IoT Traces, that contain recordings of network communications among IoT devices in real environments. Differently from the state-of-the-art, we face the problem as a node anomaly detection task under the realistic assumption of only having normal traffic samples for training the GNNs. Furthermore, we have also restricted the false positive rate below 1% to make the system practical for human operators willing to use it as an Anomaly-based IDS (A-IDS). Finally, the experimental results highlight the relevance of structural information to effectively address the task in real-world conditions. • The security of IoT devices is becoming a relevant issue in modern networks. • Host-based analysis is unfeasible in many IoT devices. • Graph Neural Networks are becoming a promising tool for network traffic analysis. • Anomaly detection is the most suitable approach scenarios where attacks are unknow. • A comparison among ML methods and GNNs for anomaly detection is proposed.

This paper presents a novel approach to multi-task visual-guided imitation learning. Upon evaluating the current state-of-the-art method, we observed its capability to replicate the intent of the demonstrator, but with the flaw of manipulating incorrect objects. To address this issue, our study introduces a new approach based on the assumption that explicitly addressing task-relevant problems, such as target object localization, can enhance system performance. Our validation shows that the proposal overtakes the leading method thanks to its ability to drive the robot motion towards the target object.

Sharing facial pictures through online services, especially on social networks, has become a common habit for thousands of users. This practice hides a possible threat to privacy: the owners of such services, as well as malicious users, could automatically extract information from faces using modern and effective neural networks. In this article, we propose the harmless use of adversarial attacks, i.e., variations of images that are almost imperceptible to the human eye and that are typically generated with the malicious purpose to mislead Convolutional Neural Networks (CNNs). Such attacks have been instead adopted to (1) obfuscate soft biometrics (gender, age, ethnicity) but (2) without degrading the quality of the face images posted online. We achieve the above-mentioned two conflicting goals by modifying the implementations of four of the most popular adversarial attacks, namely FGSM, PGD, DeepFool, and C&W, in order to constrain the average amount of noise they generate on the image and the maximum perturbation they add on the single pixel. We demonstrate, in an experimental framework including three popular CNNs, namely VGG16, SENet, and MobileNetV3, that the considered obfuscation method, which requires at most 4 seconds for each image, is effective not only when we have a complete knowledge of the neural network that extracts the soft biometrics (white box attacks) but also when the adversarial attacks are generated in a more realistic black box scenario. Finally, we prove that an opponent can implement defense techniques to partially reduce the effect of the obfuscation, but substantially paying in terms of accuracy over clean images; this result, confirmed by the experiments carried out with three popular defense methods, namely adversarial training, denoising autoencoder, and Kullback-Leibler autoencoder, shows that it is not convenient for the opponent to defend himself and that the proposed approach is robust to defenses.

In the age of the Internet of Things (IoT), the combination of robotics and artificial intelligence has paved the way for the development of social robots able to undertake realistic conversations with humans, making them the perfect human interface in applications like for instance, robotic house assistants and hotel concierges. Despite the several solutions developed in recent years, the definition of social robot requirements and the software modules needed to meet such requirements has not yet been formalized. In this article, we define the requirements of a social robot and propose a software architecture that includes all the necessary modules to meet them. The proposed architecture, implemented using robot operating system (ROS) nodes, is hardware-independent, enabling its reuse across different robotic platforms with interchangeable types of sensors and actuators. We deployed a social robot based on this architecture to interact with attendees of a real exhibition context and validated the reliability of our proposed solution through a survey of 161 users. The results of the user study indicated a high-quality user experience with the social robot, with scores ranging from 4 to 5 (being 5 the maximum score). Sharing these design choices and evaluation results could significantly benefit the development of future social robotics applications in the context of IoT.

Abstract Current state-of-the-art audio analysis algorithms based on deep learning rely on hand-crafted Spectrogram-like audio representations, that are more compact than descriptors obtained from the raw waveform; the latter are, in turn, far from achieving good generalization capabilities when few data are available for the training. However, Spectrogram-like representations have two main limitations: (1) The parameters of the filters are defined a priori, regardless of the specific audio analysis task; (2) such representations do not perform any denoising operation on the audio signal, neither in the time domain nor in the frequency domain. To overcome these limitations, we propose a new general-purpose convolutional architecture for audio analysis tasks that we call DEGramNet, which is trained with audio samples described with a novel, compact and learnable time–frequency representation that we call DEGram. The proposed representation is fully trainable: Indeed, it is able to learn the frequencies of interest for the specific audio analysis task; in addition, it performs denoising through a custom time–frequency attention module, which amplifies the frequency and time components in which the sound is actually located. It implies that the proposed representation can be easily adapted to the specific problem at hands, for instance giving more importance to the voice frequencies when the network needs to be used for speaker recognition. DEGramNet achieved state-of-the-art performance on the VGGSound dataset (for Sound Event Classification) and comparable accuracy with a complex and special-purpose approach based on network architecture search over the VoxCeleb dataset (for Speaker Identification). Moreover, we demonstrate that DEGram allows to achieve high accuracy with lightweight neural networks that can be used in real-time on embedded systems, making the solution suitable for Cognitive Robotics applications.

Understanding the role played by genetic variations in diseases, exploring genomic variants and discovering disease-associated loci are among the most pressing challenges of genomic medicine. A huge and ever-increasing amount of information is available to researchers to address these challenges. Unfortunately, it is stored in fragmented ontologies and databases, which use heterogeneous formats and poorly integrated schemas. To overcome these limitations, we propose a linked data approach, based on the formalism of multilayer networks, able to integrate and harmonize biomedical information from multiple sources into a single dense network covering different aspects on Neuroendocrine Neoplasms (NENs). The proposed integration schema consists of three interconnected layers representing, respectively, information on the disease, on the affected genes, on the related biological processes and molecular functions. An easy-to-use client-server application was also developed to browse and search for information on the model supporting multilayer network analysis.

Gender recognition from face images is an important application and it is still an open computer vision problem, even though it is something trivial from the human visual system. Variations in pose, lighting, and expression are few of the problems that make such an application challenging for a computer system. Neurophysiological studies demonstrate that the human brain is able to distinguish men and women also in absence of external cues, by analyzing the shape of specific parts of the face. In this paper, we describe an automatic procedure that combines trainable shape and color features for gender classification. In particular the proposed method fuses edge-based and color-blob-based features by means of trainable COSFIRE filters. The former types of feature are able to extract information about the shape of a face whereas the latter extract information about shades of colors in different parts of the face. We use these two sets of features to create a stacked classification SVM model and demonstrate its effectiveness on the GENDER-COLOR-FERET dataset, where we achieve an accuracy of 96.4%.

Graph matching is essential in several fields that use structured information, such as biology, chemistry, social networks, knowledge management, document analysis and others. Except for special classes of graphs, graph matching has in the worst-case an exponential complexity; however, there are algorithms that show an acceptable execution time, as long as the graphs are not too large and not too dense. In this paper we introduce a novel subgraph isomorphism algorithm, VF3, particularly efficient in the challenging case of graphs with thousands of nodes and a high edge density. Its performance, both in terms of time and memory, has been assessed on a large dataset of 12,700 random graphs with a size up to 10,000 nodes, made publicly available. VF3 has been compared with four other state-of-the-art algorithms, and the huge experimentation required more than two years of processing time. The results confirm that VF3 definitely outperforms the other algorithms when the graphs become huge and dense, but also has a very good performance on smaller or sparser graphs.

In the last decades, several systems based on video analysis have been proposed for automatically detecting accidents on roads to ensure a quick intervention of emergency teams. However, in some situations, the visual information is not sufficient or sufficiently reliable, whereas the use of microphones and audio event detectors can significantly improve the overall reliability of surveillance systems. In this paper, we propose a novel method for detecting road accidents by analyzing audio streams to identify hazardous situations such as tire skidding and car crashes. Our method is based on a two-layer representation of an audio stream: at a low level, the system extracts a set of features that is able to capture the discriminant properties of the events of interest, and at a high level, a representation based on a bag-of-words approach is then exploited in order to detect both short and sustained events. The deployment architecture for using the system in real environments is discussed, together with an experimental analysis carried out on a data set made publicly available for benchmarking purposes. The obtained results confirm the effectiveness of the proposed approach.

The detection of illegal roadside parking is becoming more and more interesting in the field of intelligent transportation systems, since it may cause traffic congestion or accidents. In this paper we propose a method able to analyze videos acquired by traditional surveillance cameras and to automatically detect the vehicles stopped in a forbidden area. Two main contributions have been introduced: first, spatio temporal information related to the stopped vehicles are encoded by a heat map; second, the background is not updated by evaluating the movement of the vehicle in a single time instant, but instead the whole movement of the vehicles, encoded into the heat map, is taken into account. Two widely adopted datasets, namely the iLids and the PETS 2000, have been used to experimentally evaluate the proposed approach and the results achieved, compared with state of the art methodologies, confirm its effectiveness.

In this paper we propose an improvement of a human action recognition method that uses a string-based representation and a string edit distance to compare the observed action with reference actions in the training set. In particular, the original improvement is based on a specific formulation of the string edit distance that is more suited to take into account the problems related to noise and to different execution speeds that are observed in an action recognition system. The experimentation has been carried out on two widely adopted datasets, namely the MIVIA and the MHAD datasets, and the obtained results, compared with both the original method and other state of the art approaches, confirm the significance of the proposed improvement and the effectiveness of the method.

In the last years, video surveillance has been employed for roads monitoring in order to detect abnormal events and improve the safety procedures in case of emergency. Certain events, such as car crashes or tire skidding, are difficult or impossible to detect when only the visual information is considered. In this paper we describe a preliminary system to detect events in roads by means of audio analysis. The system that we propose combines short- and long-time analysis of the audio signal in order to detect both impulsive and sustained events. We present the preliminary results achieved by the proposed system on a data set specifically made for roads surveillance, which we made publicly available. We also discuss the architectural deployment of such system in real environments with respect to a model of the noise of road traffic. The achieved results are promising and confirm the effectiveness of the system.

In this paper, we propose a method that is able to detect fires by analyzing videos acquired by surveillance cameras. Two main novelties have been introduced. First, complementary information, based on color, shape variation, and motion analysis, is combined by a multiexpert system. The main advantage deriving from this approach lies in the fact that the overall performance of the system significantly increases with a relatively small effort made by the designer. Second, a novel descriptor based on a bag-of-words approach has been proposed for representing motion. The proposed method has been tested on a very large dataset of fire videos acquired both in real environments and from the web. The obtained results confirm a consistent reduction in the number of false positives, without paying in terms of accuracy or renouncing the possibility to run the system on embedded platforms.

In this paper we propose a novel method for the detection of events of interest through audio analysis. The system that we propose is based on the representation of the audio streams through a Gammatone image, which describes the time-frequency distribution of the energy of the signal; this representation is inspired by the functioning of the human auditory system. A pool of AdaBoost cascade classifiers, one for each class of events of interest, is involved in the event detection stage. The performance of the proposed system has been evaluated on a large data set of audio events for surveillance applications and the achieved results, compared with two state of the art approaches, confirm its effectiveness.

In this paper we propose a novel method for recognizing human actions by exploiting a multi-layer representation based on a deep learning based architecture. A first level feature vector is extracted and then a high level representation is obtained by taking advantage of a Deep Belief Network trained using a Restricted Boltzmann Machine. The classification is finally performed by a feed-forward neural network. The main advantage behind the proposed approach lies in the fact that the high level representation is automatically built by the system exploiting the regularities in the dataset; given a suitably large dataset, it can be expected that such a representation can outperform a hand-design description scheme. The proposed approach has been tested on two standard datasets and the achieved results, compared with state of the art algorithms, confirm its effectiveness.

In this paper, we examine the main advances registered in the last ten years in Pattern Recognition methodologies based on graph matching and related techniques, analyzing more than 180 papers; the aim is to provide a systematic framework presenting the recent history and the current developments. This is made by introducing a categorization of graph-based techniques and reporting, for each class, the main contributions and the most outstanding research results.

In this paper we propose a novel approach for the audio-based detection of events. The approach adopts the bag of words paradigm, and has two main advantages over other techniques present in the literature: the ability to automatically adapt (through a learning phase) to both short, impulsive sounds and long, sustained ones, and the ability to work in noisy environments where the sounds of interest are superimposed to background sounds possibly having similar characteristics. The proposed method has been experimentally validated on a large database of sounds, including several kinds of background noise, which are superimposed to the sounds to be recognized. The obtained performance has been compared with the results of another audio event detection algorithm from the literature, showing a significant improvement.

In this paper a novel method for action recognition based on the bag of visual words approach is proposed. The main contribution is to model each action through a high level features vector computed as the histogram of the visual words: the visual words are extracted by analyzing global descriptors of the scene and their occurrences are evaluated according to a codebook, a kind of dictionary, which encodes the typical visual words, automatically extracted during the learning phase. The classification is performed by using an SVM classifier, trained only by using high level features vectors, in order to increase the overall reliability of the system. The experimentation has been conducted over two recently proposed datasets, the MIVIA and the MHAD, the promising results confirm the robustness and the stability of the proposed approach.

In this paper, we report on the first edition of the HEp-2 Cells Classification contest, held at the 2012 edition of the International Conference on Pattern Recognition, and focused on indirect immunofluorescence (IIF) image analysis. The IIF methodology is used to detect autoimmune diseases by searching for antibodies in the patient serum but, unfortunately, it is still a subjective method that depends too heavily on the experience and expertise of the physician. This has been the motivation behind the recent initial developments of computer aided diagnosis systems in this field. The contest aimed to bring together researchers interested in the performance evaluation of algorithms for IIF image analysis: 28 different recognition systems able to automatically recognize the staining pattern of cells within IIF images were tested on the same undisclosed dataset. In particular, the dataset takes into account the six staining patterns that occur most frequently in the daily diagnostic practice: centromere, nucleolar, homogeneous, fine speckled, coarse speckled, and cytoplasmic. In the paper, we briefly describe all the submitted methods, analyze the obtained results, and discuss the design choices conditioning the performance of each method.

The psychological overcharge issue related to human inadequacy to maintain a constant level of attention in simultaneously monitoring multiple visual information sources makes necessary to develop enhanced video surveillance systems that automatically understand human behaviors and identify dangerous situations. This paper introduces a semantic human behavioral analysis (HBA) system based on a neuro-fuzzy approach that, independently from the specific application, translates tracking kinematic data into a collection of semantic labels characterizing the behavior of different actors in a scene in order to appropriately classify the current situation. Different from other HBA approaches, the proposed system shows high level of scalability, robustness and tolerance for tracking imprecision and, for this reason, it could represent a valid choice for improving the performance of current systems.

Audio analytic systems are receiving an increasing interest in the scientific community, not only as stand alone systems for the automatic detection of abnormal events by the interpretation of the audio track, but also in conjunction with video analytics tools for enforcing the evidence of anomaly detection. In this paper we present an automatic recognizer of a set of abnormal audio events that works by extracting suitable features from the signals obtained by microphones installed into a surveilled area, and by classifying them using two classifiers that operate at different time resolutions. An original aspect of the proposed system is the estimation of the reliability of each response of the individual classifiers. In this way, each classifier is able to reject the samples having an overall reliability below a threshold. This approach allows our system to combine only reliable decisions, so increasing the overall performance of the method. The system has been tested on a large dataset of samples acquired from real world scenarios, the audio classes of interests are represented by gunshot, scream and glass breaking in addition to the background sounds. The preliminary results obtained encourage further research in this direction.

This paper presents a novel algorithm for the removal of reflections generated by objects on reflecting floors. The algorithm uses both chromatic properties of the reflections and geometrical constraints on their positions; however, it does not make use of a model of the reflected objects, and so it can be applied to scenes containing several kinds of objects (e.g., people, baggage, animals, vehicles, etc.). The proposed method has been validated by an extensive set of experiments on a large video database. In these experiments, the method has been compared to two other recent reflection removal algorithms. The experimental results show that the proposed method is fast and effective, both in absolute terms and in comparison with the other algorithms.

Tracking moving objects across events that break the continuity of the trajectory, such as occlusions or temporary exits from the scene, usually requires that a model of the objects of interest is created and maintained. Commonly used model representations are prone to errors when the objects can change the direction of their motion. In this paper we introduce a novel model representation, the MultiView Appearance Model, specifically devised to deal with the issue. The algorithms that create and update the model also take into account the problem of object apparent size changes due to perspective. An experimental evaluation of the proposed model representation has been performed on the PETS2010 dataset. The results show a consistent improvement of the performances in comparison with another well-known appearance model.

In this paper we introduce a new software platform for the realization of intelligent video-surveillance applications and, more generally, of real-time video stream processing systems. The platform is implemented as a middleware, providing general purpose services, and a collection of dynamically loaded modules carrying out domain-specific tasks. The architecture of the platform follows a data-flow paradigm, where the application is organized as a processing network whose nodes are activated by the middleware as soon as their inputs are available and a processor is ready. This architecture is beneficial both with respect to the development process, simplifying the module implementation and favoring the reuse of software components, and with respect to the performance, since the middleware can automatically parallelize the processing using the available processors or cores. The platform has been validated by converting an existing video surveillance application, demonstrating both the improvement in the development process and the performance increment.

This paper presents a novel method to count people for video surveillance applications. Methods in the literature either follow a direct approach, by first detecting people and then counting them, or an indirect approach, by establishing a relation between some easily detectable scene features and the estimated number of people. The indirect approach is considerably more robust, but it is not easy to take into account such factors as perspective or people groups with different densities. The proposed technique, while based on the indirect approach, specifically addresses these problems; furthermore it is based on a trainable estimator that does not require an explicit formulation of a priori knowledge about the perspective and density effects present in the scene at hand. In the experimental evaluation, the method has been extensively compared with the algorithm by Albiol et al, which provided the highest performance at the PETS 2009 contest on people counting. The experimentation has used the public PETS 2009 datasets. The results confirm that the proposed method improves the accuracy, while retaining the robustness of the indirect approach.

This paper presents a method for counting people in a scene by establishing a mapping between some scene features and the number of people avoiding the complex foreground detection problem. The method is based on the use of SURF features and of an ∈-SVR regressor to provide an estimate of this count. The algorithm takes specifically into account problems due to partial occlusions and to perspective.

In this paper a system for autonomous video surveillance in relatively unconstrained environments is described. The system consists of two principal phases: object detection and object tracking. An adaptive background subtraction, together with a set of corrective algorithms, is used to cope with variable lighting, dynamic and articulate scenes, etc. The tracking algorithm is based on a matrix representation of the problem, and is used to face splitting and occlusion problems. When the tracking algorithm fails in following actual object trajectories, an appearance-based module is used to restore object identities. An experimental evaluation, carried out on the PETS2009 dataset for tracking, shows promising results.

Indirect immunofluorescence (IIF) imaging is the recommended laboratory technique to detect autoantibodies in patient serum, but it suffers from several issues limiting its reliability and reproducibility. IIF slides are observed by specialists at the fluorescence microscope, reporting fluorescence intensity and staining pattern and looking for mitotic cells. Indeed, the presence of such cells is a key factor to assess the correctness of slide preparation process and the reported staining pattern. Therefore, the ability to detect mitotic cells is needed to develop a complete computer-aided-diagnosis system in IIF, which can support the specialists from image acquisition up to image classification. Although recent research in IIF has been directed to image acquisition, image segmentation, fluorescence intensity classification and staining pattern recognition, no works presented methods suited to classify such cells. Hence, this paper presents an heterogeneous set of features used to describe the peculiarities of mitotic cells and then tests five classifiers, belonging to different classification paradigms. The approach has been evaluated on an annotated dataset of mitotic cells. The measured performances are promising, achieving a classification accuracy of 86.5 %.

This paper presents a novel method to count people for video surveillance applications. The problem is faced by establishing a mapping between some scene features and the number of people. Moreover, the proposed technique takes specifically into account problems due to perspective. In the experimental evaluation, the method has been compared with respect to the algorithm by Albiol et al., which provided the highest performance at the PETS 2009 contest on people counting, using the same datasets. The results confirm that the proposed method improves the accuracy, while retaining the robustness of Albiol's algorithm.

This paper presents a novel method for reflection removal in the context of an object detection system. The method is based on chromatic properties of the reflections and does not require a geometric model of the objects. An experimental evaluation of the proposed method has been performed on a large database, showing its effectiveness.

Several video analysis applications perform object detection using a background subtraction approach. Camouflage can be a serious problem for these applications, since the objects of interest may appear fragmented into small,disconnected pieces, with a dramatic negative impact on later processing phases such as classification or tracking. Nevertheless, this problem is largely underestimated in the literature. In this paper an effective, model-based solution is presented for the case of people detection. The proposed method acts as a post-processing phase, grouping together the fragmented blocks to restore the original object. A quantitative evaluation of the effectiveness of this method has been performed on real world videos from a video-surveillance application. The videos used for the experiments (with metadata) have been made publicly available on the Internet.

In some Computer Vision applications there is the need for grouping, in one or more clusters, only a part of the whole dataset. This happens, for example, when samples of interest for the application at hand are present together with several noisy samples. In this paper we present a graph-based algorithm for cluster detection that is particularly suited for detecting clusters of any size and shape, without the need of specifying either the actual number of clusters or the other parameters. The algorithm has been tested on data coming from two different computer vision applications. A comparison with other four state-of-the-art graph-based algorithms was also provided, demonstrating the effectiveness of the proposed approach.

A common problem encountered in structural pattern recognition is the difficulty of constructing classification models or rules from a set of examples, due to the complexity of the structures needed to represent the patterns. In this paper, we present an extension of a method for structural learning. The goal of the method is to find descriptions which are general (in other words, are successfully applicable to recognize objects different from the ones in the training set), preserving at the same time their discrimination ability. This method has been applied to predictive toxicology evaluation, that is the inference of the cancerogenic characteristics of chemical compounds.

In this paper we face the problem of partitioning the news videos into stories, and of their classification according to a predefined set of categories. In particular, we propose to employ a multi-level probabilistic framework based on the hidden Markov models and the Bayesian networks paradigms for the segmentation and the classification phases, respectively. The whole analysis is carried out exploiting information extracted from the video and the audio tracks using techniques of superimposed text recognition, speaker identification, speech transcription, anchor detection. The system was tested on a database of Italian news videos and the results are very promising

A recent paper posed the question: "Graph Matching: What are we really talking about?". Far from providing a definite answer to that question, in this paper we will try to characterize the role that graphs play within the Pattern Recognition field. To this aim two taxonomies are presented and discussed. The first includes almost all the graph matching algorithms proposed from the late seventies, and describes the different classes of algorithms. The second taxonomy considers the types of common applications of graph-based techniques in the Pattern Recognition and Machine Vision field.

We present an algorithm for graph isomorphism and subgraph isomorphism suited for dealing with large graphs. A first version of the algorithm has been presented in a previous paper, where we examined its performance for the isomorphism of small and medium size graphs. The algorithm is improved here to reduce its spatial complexity and to achieve a better performance on large graphs; its features are analyzed in detail with special reference to time and memory requirements. The results of a testing performed on a publicly available database of synthetically generated graphs and on graphs relative to a real application dealing with technical drawings are presented, confirming the effectiveness of the approach, especially when working with large graphs.

In this paper we will try to characterize the role that graphs are conquering within the pattern recognition field. To this aim, a taxonomy built considering the most common applications of graph based techniques in the pattern recognition and image processing field is presented and discussed.

During the last two decades, the attempts to find effective solutions to the problem of learning any kind of structured information have been splitting the scientific community. A "holy war" has been fought between the advocates of a symbolic approach to learning and the advocates of a connectionist approach. One of the most repeated claims of the symbolic party has been that symbolic methods are able to cope with structured information while connectionist ones are not. However, in the last few years, the possibility of employing connectionist methods for structured data has been widely investigated and several approaches have been proposed. A novel algorithm for learning structured descriptions, ascribable to the category of symbolic techniques, is proposed. It faces the problem directly in the space of graphs by defining the proper inference operators, as graph generalization and graph specialization, and obtains general and consistent prototypes with a low computational cost with respect to other symbolic learning systems. The proposed algorithm is compared with a recent connectionist method for learning structured data (P. Frasconi et al., 1998), with reference to a problem of handwritten character recognition from a standard database on the Web. The orthogonality of the two approaches strongly suggests their combination in a multiclassifier system so as to retain the strengths of both of them, while overcoming their weaknesses. The results on an experimental case study demonstrated that the adoption of a parallel combination scheme of the two algorithms could improve the recognition performance by about 10 percent. A truce or an alliance between the symbolic and the connectionist worlds?.

The performance of an attributed relational graph (ARG) matching algorithm, tailored for dealing with large graphs, is evaluated in the context of a real application. The detection of component parts in CAD images of mechanical drawings. The matching problem is a graph-subgraph isomorphism and the algorithm exploits semantic information about nodes while does not require information about the topology of the graphs to be matched. Experimental results, compared with those obtained with a different method, show the overall efficiency of the algorithm and the matching time reduction obtainable by exploiting the semantic information held by ARGs.

A three-stage serial multi-expert system for facing the problem of signature verification is proposed. The first two stages, respectively devoted to the recognition of random and simple forgeries and of skilled forgeries, employ suitable criteria for estimating the reliability of the performed classification. In case of uncertainty the signature is forwarded to the successive stage which takes the final decision, taking into account the decisions of the previous stages together with their reliability estimations. Criteria for selecting the features to be used at each stage and for computing classification reliability and reliability thresholds are discussed The obtained results are compared with those achieved, on the same database of 49 writers, by other existing systems.

A graph matching algorithm is illustrated and its performance compared with that of a well known algorithm performing the same task. According to the proposed algorithm the matching process is carried out by using a state space representation: a state represents a partial solution of the matching between two graphs, and a transition between states corresponds to the addition of a new pair of matched nodes. A set of feasibility rules is introduced for pruning states corresponding to partial matching solutions not satisfying the required graph morphism. Results outlining the computational cost reduction achieved by the method are given with reference to a set of randomly generated graphs.

A novel description method is presented. It is based on the combination of structural and statistical approaches, and is applied to the problem of unconstrained isolated handwritten character recognition. Characters are preliminarily decomposed in terms of structural primitives (circular arcs) and successively described in terms of statistical features (geometrical moments suitably normalized). A multilayer perceptron is adopted in the classification stage. Results of the method on the digits of the ETL Database are reported.

The paper illustrates an algorithm for the inexact matching of attributed relational graphs. A sample graph is considered matchable with one of the prototypes if, by using a defined set of syntactic and semantic transformations, it can be made isomorphic to the graph of the prototype. The applicability of a transformation is contextually defined, i.e. each transformation can be defined with reference to a prototype, and can be applied only when the sample graph is being matched with that prototype. The reduction of the computational complexity with respect to a brute-force approach is given with reference to an OCR application.

This paper proposes a structural description scheme using circular arcs as primitives. On this scheme, a metric for defining a distance between pairs of circular arcs and relations among them, is introduced and its main properties are discussed. This metric is based on a set of perceptive criteria which allow to increase its effectiveness in application domains characterized by high variability in the shape of the visual patterns. The whole approach is general enough to be satisfactorily used in a wide class of applications. The metric has been validated by employing it in a nearest neighbour classifier, which has been used for automatic recognition of handwritten digits extracted from a standard character database.