Summarizing level-two topological relations in large spatial datasets

Summarizing topological relations is fundamental to many spatial applications including spatial query optimization. In this article, we present several novel techniques to effectively construct cell density based spatial histograms for range (window) summarizations restricted to the four most important level-two topological relations: contains, contained, overlap, and disjoint. We first present a novel framework to construct a multiscale Euler histogram in 2D space with the guarantee of the exact summarization results for aligned windows in constant time. To minimize the storage space in such a multiscale Euler histogram, an approximate algorithm with the approximate ratio 19/12 is presented, while the problem is shown NP-hard generally. To conform to a limited storage space where a multiscale histogram may be allowed to have only k Euler histograms, an effective algorithm is presented to construct multiscale histograms to achieve high accuracy in approximately summarizing aligned windows. Then, we present a new approximate algorithm to query an Euler histogram that cannot guarantee the exact answers; it runs in constant time. We also investigate the problem of nonaligned windows and the problem of effectively partitioning the data space to support nonaligned window queries. Finally, we extend our techniques to 3D space. Our extensive experiments against both synthetic and real world datasets demonstrate that the approximate multiscale histogram techniques may improve the accuracy of the existing techniques by several orders of magnitude while retaining the cost efficiency, and the exact multiscale histogram technique requires only a storage space linearly proportional to the number of cells for many popular real datasets.

Toward efficient multifeature query processing

In many advanced applications, data are described by multiple high-dimensional features. Moreover, different queries may weight these features differently; some may not even specify all the features. In this paper, we propose our solution to support efficient query processing in these applications. We devise a novel representation that compactly captures f features into two components: The first component is a 2D vector that reflects a distance range ( minimum and maximum values) of the f features with respect to a reference point ( the center of the space) in a metric space and the second component is a bit signature, with two bits per dimension, obtained by analyzing each feature's descending energy histogram. This representation enables two levels of filtering: The first component prunes away points that do not share similar distance ranges, while the bit signature filters away points based on the dimensions of the relevant features. Moreover, the representation facilitates the use of a single index structure to further speed up processing. We employ the classical B+-tree for this purpose. We also propose a KNN search algorithm that exploits the access orders of critical dimensions of highly selective features and partial distances to prune the search space more effectively. Our extensive experiments on both real-life and synthetic data sets show that the proposed solution offers significant performance advantages over sequential scan and retrieval methods using single and multiple VA-files.

Multiphoton high-resolution 3D imaging of Langerhans cells and keratinocytes in the mouse skin model adopted for epidermal powdered immunization

Langerhans cells (LCs) can be targeted with DNA-coated gold micro-projectiles ("Gene Gun") to induce potent cellular and humoral immune responses. It is likely that the relative volumetric distribution of LCs and keratinocytes within the epidermis impacts on the efficacy of Gene Gun immunization protocols. This study quantified the three-dimensional (3D) distribution of LCs and keratinocytes in the mouse skin model with a near-infrared multiphoton laser-scanning microscope (NIR-MPLSM). Stratum corneum (SC) and viable epidermal thickness measured with MPLSM was found in close agreement with conventional histology. LCs were located in the vertical plane at a mean depth of 14.9 mum, less than 3 mum above the dermo-epidermal boundary and with a normal histogram distribution. This likely corresponds to the fact that LCs reside in the suprabasal layer (stratum germinativum). The nuclear volume of keratinocytes was found to be approximately 1.4 times larger than that of resident LCs (88.6 mum3). Importantly, the ratio of LCs to keratinocytes in mouse ear skin (1:15) is more than three times higher than that reported for human breast skin (1:53). Accordingly, cross-presentation may be more significant in clinical Gene Gun applications than in pre-clinical mouse studies. These interspecies differences should be considered in pre-clinical trials using mouse models.

A neural network based technique for automatic classification of road cracks

This paper presents a neural network based technique for the classification of segments of road images into cracks and normal images. The density and histogram features are extracted. The features are passed to a neural network for the classification of images into images with and without cracks. Once images are classified into cracks and non-cracks, they are passed to another neural network for the classification of a crack type after segmentation. Some experiments were conducted and promising results were obtained. The selected results and a comparative analysis are included in this paper.

Playing in continuous spaces: Some analysis and extension of population-based incremental learning

As an alternative to traditional evolutionary algorithms (EAs), population-based incremental learning (PBIL) maintains a probabilistic model of the best individual(s). Originally, PBIL was applied in binary search spaces. Recently, some work has been done to extend it to continuous spaces. In this paper, we review two such extensions of PBIL. An improved version of the PBIL based on Gaussian model is proposed that combines two main features: a new updating rule that takes into account all the individuals and their fitness values and a self-adaptive learning rate parameter. Furthermore, a new continuous PBIL employing a histogram probabilistic model is proposed. Some experiments results are presented that highlight the features of the new algorithms.

Multiscale histograms: Summarizing topological relations in large spatial datasets

Summarizing topological relations is fundamental to many spatial applications including spatial query optimization. In this paper, we present several novel techniques to eectively construct cell density based spatial histograms for range (window) summarizations restricted to the four most important topological relations: contains, contained, overlap, and disjoint. We rst present a novel framework to construct a multiscale histogram composed of multiple Euler histograms with the guarantee of the exact summarization results for aligned windows in constant time. Then we present an approximate algorithm, with the approximate ratio 19/12, to minimize the storage spaces of such multiscale Euler histograms, although the problem is generally NP-hard. To conform to a limited storage space where only k Euler histograms are allowed, an effective algorithm is presented to construct multiscale histograms to achieve high accuracy. Finally, we present a new approximate algorithm to query an Euler histogram that cannot guarantee the exact answers; it runs in constant time. Our extensive experiments against both synthetic and real world datasets demonstrated that the approximate mul- tiscale histogram techniques may improve the accuracy of the existing techniques by several orders of magnitude while retaining the cost effciency, and the exact multiscale histogram technique requires only a storage space linearly proportional to the number of cells for the real datasets.

ANÁLISE DA DENSIDADE ÓPTICA DA SUTURA PALATINA MEDIANA APÓS A EXPANSÃO RÁPIDA DA MAXILA ASSISTIDA CIRURGICAMENTE

A Expansão Rápida da Maxila Assistida Cirurgicamente (ERMAC) é um recurso ortodôntico-cirúrgico utilizado no tratamento das más oclusões com deficiência transversal da maxila em pacientes adultos que apresentam a consolidação da sutura palatina mediana. A proposta neste estudo foi a de avaliar as densidades ópticas da sutura palatina mediana antes da ERMAC (fase I), após o fechamento do parafuso expansor (fase II), após 3 meses do fechamento do parafuso expansor (fase III) e após 6 meses do procedimento cirúrgico. A amostra deste estudo foi constituída por 64 radiografias oclusais de 16 pacientes na faixa etária de 18 a 40 anos, sendo 6 do sexo masculino e 10 do sexo feminino que necessitavam submeter-se à Expansão Rápida da Maxila Assistida Cirurgicamente (ERMAC) e com atresia maxilar superior a 5 mm. Foram obtidas as radiografias oclusais e as imagens digitalizadas das quatro fases do estudo. Duas áreas de interesse foram demarcadas nas imagens digitalizadas, uma entre os incisivos centrais superiores e outra após o término do parafuso expansor. Procedeu-se às leituras das densidades ópticas pelo programa Image Tool for Windows por meio do Histograma. Após a análise estatística dos valores obtidos de densidade óptica das regiões analisadas pela Análise de Variâncias (ANOVA) e comparações múltiplas de Bonferroni (complemento da ANOVA), pode-se concluir que: a densidade óptica na região da sutura palatina mediana nas 4 fases estudadas, apresentou grande variação, compatível com a abertura da referida sutura e posterior neoformação óssea no período pós-operatório; foi observado valor decrescente para as densidades ópticas após o fechamento do parafuso expansor nas regiões A e B ; foi observado que após 3 meses do fechamento do parafuso expansor, as densidades ópticas aumentaram nas regiões A e B . Isso sugeriu neoformação óssea na região da sutura palatina mediana; foi observado que após 6 meses do procedimento cirúrgico, as densidades ópticas aumentaram em relação à fase anterior. Na região A , observou-se que os valores das densidades ópticas não retornaram aos valores pré-tratamento, ou seja, antes da Expansão Rápida da Maxila Assistida Cirurgicamente (ERMAC). Já os valores das densidades ópticas médias da região B retornaram aos valores iniciais, antes da ERMAC. A análise estatística revelou que após 6 meses do procedimento cirúrgico, houve diferença estatisticamente significante ao se avaliar a região A comparando as fases entre si, porém ao se avaliar a região B não houve diferença estatisticamente significante ao se comparar as fases I e IV.

Blood type classification using computer vision and machine learning

In emergency situations, where time for blood transfusion is reduced, the O negative blood type (the universal donor) is administrated. However, sometimes even the universal donor can cause transfusion reactions that can be fatal to the patient. As commercial systems do not allow fast results and are not suitable for emergency situations, this paper presents the steps considered for the development and validation of a prototype, able to determine blood type compatibilities, even in emergency situations. Thus it is possible, using the developed system, to administer a compatible blood type, since the first blood unit transfused. In order to increase the system’s reliability, this prototype uses different approaches to classify blood types, the first of which is based on Decision Trees and the second one based on support vector machines. The features used to evaluate these classifiers are the standard deviation values, histogram, Histogram of Oriented Gradients and fast Fourier transform, computed on different regions of interest. The main characteristics of the presented prototype are small size, lightweight, easy transportation, ease of use, fast results, high reliability and low cost. These features are perfectly suited for emergency scenarios, where the prototype is expected to be used.

Use of fundus imaging in quantification of age-related macular change

This review will discuss the use of manual grading scales, digital photography, and automated image analysis in the quantification of fundus changes caused by age-related macular disease. Digital imaging permits processing of images for enhancement, comparison, and feature quantification, and these techniques have been investigated for automated drusen analysis. The accuracy of automated analysis systems has been enhanced by the incorporation of interactive elements, such that the user is able to adjust the sensitivity of the system, or manually add and remove pixels. These methods capitalize on both computer and human image feature recognition and the advantage of computer-based methodologies for quantification. The histogram-based adaptive local thresholding system is able to extract useful information from the image without being affected by the presence of other structures. More recent developments involve compensation for fundus background reflectance, which has most recently been combined with the Otsu method of global thresholding. This method is reported to provide results comparable with manual stereo viewing. Developments in this area are likely to encourage wider use of automated techniques. This will make the grading of photographs easier and cheaper for clinicians and researchers. © 2007 Elsevier Inc. All rights reserved.

Non-rigid object tracking in complex scenes

A recently proposed colour based tracking algorithm has been established to track objects in real circumstances [Zivkovic, Z., Krose, B. 2004. An EM-like algorithm for color-histogram-based object tracking. In: Proc, IEEE Conf. on Computer Vision and Pattern Recognition, pp. 798-803]. To improve the performance of this technique in complex scenes, in this paper we propose a new algorithm for optimally adapting the ellipse outlining the objects of interest. This paper presents a Lagrangian based method to integrate a regularising component into the covariance matrix to be computed. Technically, we intend to reduce the residuals between the estimated probability distribution and the expected one. We argue that, by doing this, the shape of the ellipse can be properly adapted in the tracking stage. Experimental results show that the proposed method has favourable performance in shape adaption and object localisation.

Using empirical evidence of variations in worker performance to extend the capabilities of discrete event simulations in manufacturing

Discrete event simulation of manufacturing systems has become widely accepted as an important tool to aid the design of such systems. Often, however, it is applied by practitioners in a manner which largely ignores an important element of industry; namely, the workforce. Workers are usually represented as simple resources, often with deterministic performance values. This approach ignores the potentially large effect that human performance variation can have on a system. A long-term data collection exercise is described with the aim of quantifying the performance variation of workers in a typical automotive assembly plant. The data are presented in a histogram form which is immediately usable in simulations to improve the accuracy of design assessment. The results show levels of skewness and range which are far larger than anticipated by current researchers and practitioners in the field.

Оптимизация Оценки Вероятности Ошибочной Классификации в Дискретном Случае

* Работа выполнена при поддержке РФФИ, гранты 07-01-00331-a и 08-01-00944-a

Monte Carlo Method for Reconstruction of Densities

2000 Mathematics Subject Classification: 65C05

Classification of Paintings by Artist, Movement, and Indoor Setting Using MPEG-7 Descriptor Features

ACM Computing Classification System (1998): I.4.9, I.4.10.

A mathematical resolution to log transformations and the binning effect in applied processing of data in flow cytometry

This dissertation develops a new mathematical approach that overcomes the effect of a data processing phenomenon known as “histogram binning” inherent to flow cytometry data. A real-time procedure is introduced to prove the effectiveness and fast implementation of such an approach on real-world data. The histogram binning effect is a dilemma posed by two seemingly antagonistic developments: (1) flow cytometry data in its histogram form is extended in its dynamic range to improve its analysis and interpretation, and (2) the inevitable dynamic range extension introduces an unwelcome side effect, the binning effect, which skews the statistics of the data, undermining as a consequence the accuracy of the analysis and the eventual interpretation of the data. ^ Researchers in the field contended with such a dilemma for many years, resorting either to hardware approaches that are rather costly with inherent calibration and noise effects; or have developed software techniques based on filtering the binning effect but without successfully preserving the statistical content of the original data. ^ The mathematical approach introduced in this dissertation is so appealing that a patent application has been filed. The contribution of this dissertation is an incremental scientific innovation based on a mathematical framework that will allow researchers in the field of flow cytometry to improve the interpretation of data knowing that its statistical meaning has been faithfully preserved for its optimized analysis. Furthermore, with the same mathematical foundation, proof of the origin of such an inherent artifact is provided. ^ These results are unique in that new mathematical derivations are established to define and solve the critical problem of the binning effect faced at the experimental assessment level, providing a data platform that preserves its statistical content. ^ In addition, a novel method for accumulating the log-transformed data was developed. This new method uses the properties of the transformation of statistical distributions to accumulate the output histogram in a non-integer and multi-channel fashion. Although the mathematics of this new mapping technique seem intricate, the concise nature of the derivations allow for an implementation procedure that lends itself to a real-time implementation using lookup tables, a task that is also introduced in this dissertation. ^