Computational modeling and psychophysics in low- and mid-level vision

This thesis addresses a series of topics related to the question of how people find the foreground objects from complex scenes. With both computer vision modeling, as well as psychophysical analyses, we explore the computational principles for low- and mid-level vision.

We first explore the computational methods of generating saliency maps from images and image sequences. We propose an extremely fast algorithm called Image Signature that detects the locations in the image that attract human eye gazes. With a series of experimental validations based on human behavioral data collected from various psychophysical experiments, we conclude that the Image Signature and its spatial-temporal extension, the Phase Discrepancy, are among the most accurate algorithms for saliency detection under various conditions.

In the second part, we bridge the gap between fixation prediction and salient object segmentation with two efforts. First, we propose a new dataset that contains both fixation and object segmentation information. By simultaneously presenting the two types of human data in the same dataset, we are able to analyze their intrinsic connection, as well as understanding the drawbacks of today’s “standard” but inappropriately labeled salient object segmentation dataset. Second, we also propose an algorithm of salient object segmentation. Based on our novel discoveries on the connections of fixation data and salient object segmentation data, our model significantly outperforms all existing models on all 3 datasets with large margins.

In the third part of the thesis, we discuss topics around the human factors of boundary analysis. Closely related to salient object segmentation, boundary analysis focuses on delimiting the local contours of an object. We identify the potential pitfalls of algorithm evaluation for the problem of boundary detection. Our analysis indicates that today’s popular boundary detection datasets contain significant level of noise, which may severely influence the benchmarking results. To give further insights on the labeling process, we propose a model to characterize the principles of the human factors during the labeling process.

The analyses reported in this thesis offer new perspectives to a series of interrelating issues in low- and mid-level vision. It gives warning signs to some of today’s “standard” procedures, while proposing new directions to encourage future research.

Efficient HOG human detection

While Histograms of Oriented Gradients (HOG) plus Support Vector Machine (SVM) (HOG+SVM) is the most successful human detection algorithm, it is time-consuming. This paper proposes two ways to deal with this problem. One way is to reuse the features in blocks to construct the HOG features for intersecting detection windows. Another way is to utilize sub-cell based interpolation to efficiently compute the HOG features for each block. The combination of the two ways results in significant increase in detecting humans-more than five times better. To evaluate the proposed method, we have established a top-view human database. Experimental results on the top-view database and the well-known INRIA data set have demonstrated the effectiveness and efficiency of the proposed method. (C) 2010 Elsevier B.V. All rights reserved.

快速模糊边缘检测算法

通过对Pal.King的模糊边缘检测算法进行改进，提出了一种快速模糊边缘检测算法。该快速算法不但简化了Pal.King算法中复杂的G和G-1运算，而且通过实验，确定了Tr变换中最佳的隶属度阈值，大大地减少了迭代次数。从实验结果中可以看出，该快速算法不但提高了Pal.King算法的效率，而且具有很强的检测模糊边缘和细小边缘的能力。这种快速算法的性能优越，是一种非常实用的、高效的的图像处理算法。

高阶广义屏波动方程叠前深度偏移

Attaining sufficient accuracy and efficiency of generalized screen propagator and improving the quality of input gathers are often problems　of wave equation presack depth migration,　in this paper,a high order formula of generalized screen propagator　for one-way wave equation is proposed by using the asymptotic expansion of single-square-root operator. Based on the formula，a new generalized screen propagator is developed ,which is composed of split-step Fourier propagator and high order correction terms，the new generalized screen propagator not only improving calculation precision without sharply increasing the quantity of computation，facilitates the suitability of generalized screen propagator to the media with strong lateral velocity variation.　As wave-equation prestack depth migration is sensitive to the quality of input gathers, which greatly affect the output，and the available seismic data processing system has inability to obtain traveltimes corresponding to the multiple arrivals, to estimate of great residual statics， to merge seismic datum from different projects and to design inverse Q filter, we establish　difference equations with an embodiment of Huygens’s principle for obtaining traveltimes corresponding to the multiple arrivals,bring forward a time variable matching filter for seismic datum merging by using the fast algorithm called Mallat tree for wavelet transformations， put forward a method for estimation of residual statics by applying the optimum model parameters estimated by iterative inversion with three organized algorithm,i.e,the CMP intertrace cross-correlation algorithm,the Laplacian image edge extraction algorithm,and the DFP algorithm, and present phase-shift inverse Q filter based on Futterman’s amplitude and phase-velocity dispersion formula and wave field extrapolation theory. All of their numerical and real data calculating results shows that our theory and method are practical and efficient. Key words: prestack depth migration, generalized screen propagator, residual statics，inverse Q filter ,traveltime，3D seismic datum mergence

Fourier有限差分法深度偏移与正演模拟

With the development of seismic exploration, the target becomes more and more complex, which leads to a higher demand for the accuracy and efficiency in 3D exploration. Fourier finite-difference (FFD) method is one of the most valuable methods in complex structure exploration, which keeps the ability of finite-differenc method in dealing with laterally varing media and inherits the predominance of the phase-screen method in stablility and efficiency. In this thesis, the accuracy of the FFD operator is highly improved by using simulated annealing algorithm. This method takes the extrapolation step and band width into account, which is more suitable to various band width and discrete scale than the commonely-used optimized method based on velocity contrast alone. In this thesis, the FFD method is extended to viscoacoustic modeling. Based on one-way wave equation, the presented method is implemented in frequency domain; thus, it is more efficient than two-way methods, and is more convenient than time domain methods in handling attenuation and dispersion effects. The proposed method can handle large velocity contrast and has a high efficiency, which is helpful to further research on earth absorption and seismic resolution. Starting from the frequency dispersion of the acoustic VTI wave equation, this thesis extends the FFD migration method to the acoustic VTI media. Compared with the convetional FFD method, the presented method has a similar computational efficiency, and keeps the abilities of dealing with large velocity contrasts and steep dips. The numerical experiments based on the SEG salt model show that the presented method is a practical migration method for complex acoustical VTI media, because it can handle both large velocity contrasts and large anisotropy variations, and its accuracy is relatively high even in strong anisotropic media. In 3D case, the two-way splitting technique of FFD operator causes artificial azimuthal anisotropy. These artifacts become apparent with increasing dip angles and velocity contrasts, which prevent the application of the FFD method in 3D complex media. The current methods proposed to reduce the azimuthal anisotropy significantly increase the computational cost. In this thesis, the alternating-direction-implicit plus interpolation scheme is incorporated into the 3D FFD method to reduce the azimuthal anisotropy. By subtly utilizing the Fourier based scheme of the FFD method, the improved fast algorithm takes approximately no extra computation time. The resulting operator keeps both the accuracy and the efficiency of the FFD method, which is helpful to the inhancements of both the accuracy and the efficiency for prestack depth migration. The general comparison is presented between the FFD operator and the generalized-screen operator, which is valuable to choose the suitable method in practice. The percentage relative error curves and migration impulse responses show that the generalized-screen operator is much sensiutive to the velocity contrasts than the FFD operator. The FFD operator can handle various velocity contrasts, while the generalized-screen operator can only handle some range of the velocity contrasts. Both in large and weak velocity contrasts, the higher order term of the generalized-screen operator has little effect on improving accuracy. The FFD operator is more suitable to large velocity contrasts, while the generalized-screen operator is more suitable to middle velocity contrasts. Both the one-way implicit finite-difference migration and the two-way explicit finite-differenc modeling have been implemented, and then they are compared with the corresponding FFD methods respectively. This work gives a reference to the choosen of proper method. The FFD migration is illustrated to be more attractive in accuracy, efficiency and frequency dispertion than the widely-used implicit finite-difference migration. The FFD modeling can handle relatively coarse grids than the commonly-used explicit finite-differenc modeling, thus it is much faster in 3D modeling, especially for large-scale complex media.

基于匹配追踪方法的地震信号时频分析研究

Seismic signal is a typical non-stationary signal, whose frequency is continuously changing with time and is determined by the bandwidth of seismic source and the absorption characteristic of the media underground. The most interesting target of seismic signal’s processing and explaining is to know about the local frequency’s abrupt changing with the time, since this kind of abrupt changing is indicating the changing of the physical attributes of the media underground. As to the seismic signal’s instantaneous attributes taken from time-frequency domain, the key target is to search a effective, non-negative and fast algorithm time-frequency distribution, and transform the seismic signal into this time-frequency domain to get its instantaneous power spectrum density, and then use the process of weighted adding and average etc. to get the instantaneous attributes of seismic signal. Time-frequency analysis as a powerful tool to deal with time variant non-stationary signal is becoming a hot researching spot of modern signal processing, and also is an important method to make seismic signal’s attributes analysis. This kind of method provides joint distribution message about time domain and frequency domain, and it clearly plots the correlation of signal’s frequency changing with the time. The spectrum decomposition technique makes seismic signal’s resolving rate reach its theoretical level, and by the method of all frequency scanning and imaging the three dimensional seismic data in frequency domain, it improves and promotes the resolving abilities of seismic signal vs. geological abnormal objects. Matching pursuits method is an important way to realize signal’s self-adaptive decomposition. Its main thought is that any signal can be expressed by a series of time-frequency atoms’ linear composition. By decomposition the signal within an over completed library, the time-frequency atoms which stand for the signal itself are selected neatly and self-adaptively according to the signal’s characteristics. This method has excellent sparse decomposition characteristics, and is widely used in signal de-noising, signal coding and pattern recognizing processing and is also adaptive to seismic signal’s decomposition and attributes analysis. This paper takes matching pursuits method as the key research object. As introducing the principle and implementation techniques of matching pursuits method systematically, it researches deeply the pivotal problems of atom type’s selection, the atom dictionary’s discrete, and the most matching atom’s searching algorithm, and at the same time, applying this matching pursuits method into seismic signal’s processing by picking-up correlative instantaneous messages from time-frequency analysis and spectrum decomposition to the seismic signal. Based on the research of the theory and its correlative model examination of the adaptively signal decomposition with matching pursuit method, this paper proposes a fast optimal matching time-frequency atom’s searching algorithm aimed at seismic signal’s decomposition by frequency-dominated pursuit method and this makes the MP method pertinence to seismic signal’s processing. Upon the research of optimal Gabor atom’s fast searching and matching algorithm, this paper proposes global optimal searching method using Simulated Annealing Algorithm, Genetic Algorithm and composed Simulated Annealing and Genetic Algorithm, so as to provide another way to implement fast matching pursuit method. At the same time, aimed at the characteristics of seismic signal, this paper proposes a fast matching atom’s searching algorithm by means of designating the max energy points of complex seismic signal, searching for the most optimal atom in the neighbor area of these points according to its instantaneous frequency and instantaneous phase, and this promotes the calculating efficiency of seismic signal’s matching pursuit algorithm. According to these methods proposed above, this paper implements them by programmed calculation, compares them with some open algorithm and proves this paper’s conclusions. It also testifies the active results of various methods by the processing of actual signals. The problems need to be solved further and the aftertime researching targets are as follows: continuously seeking for more efficient fast matching pursuit algorithm and expanding its application range, and also study the actual usage of matching pursuit method.

Search Space Reduction in QoS Routing

To provide real-time service or engineer constrained-based paths, networks require the underlying routing algorithm to be able to find low-cost paths that satisfy given Quality-of-Service (QoS) constraints. However, the problem of constrained shortest (least-cost) path routing is known to be NP-hard, and some heuristics have been proposed to find a near-optimal solution. However, these heuristics either impose relationships among the link metrics to reduce the complexity of the problem which may limit the general applicability of the heuristic, or are too costly in terms of execution time to be applicable to large networks. In this paper, we focus on solving the delay-constrained minimum-cost path problem, and present a fast algorithm to find a near-optimal solution. This algorithm, called DCCR (for Delay-Cost-Constrained Routing), is a variant of the k-shortest path algorithm. DCCR uses a new adaptive path weight function together with an additional constraint imposed on the path cost, to restrict the search space. Thus, DCCR can return a near-optimal solution in a very short time. Furthermore, we use the method proposed by Blokh and Gutin to further reduce the search space by using a tighter bound on path cost. This makes our algorithm more accurate and even faster. We call this improved algorithm SSR+DCCR (for Search Space Reduction+DCCR). Through extensive simulations, we confirm that SSR+DCCR performs very well compared to the optimal but very expensive solution.

Part-whole relations between food webs and the validity of local food-web descriptions

This work analyzes the relationship between large food webs describing potential feeding relations between species and smaller sub-webs thereof describing relations actually realized in local communities of various sizes. Special attention is given to the relationships between patterns of phylogenetic correlations encountered in large webs and sub-webs. Based on the current theory of food-web topology as implemented in the matching model, it is shown that food webs are scale invariant in the following sense: given a large web described by the model, a smaller, randomly sampled sub-web thereof is described by the model as well. A stochastic analysis of model steady states reveals that such a change in scale goes along with a re-normalization of model parameters. Explicit formulae for the renormalized parameters are derived. Thus, the topology of food webs at all scales follows the same patterns, and these can be revealed by data and models referring to the local scale alone. As a by-product of the theory, a fast algorithm is derived which yields sample food webs from the exact steady state of the matching model for a high-dimensional trophic niche space in finite time. (C) 2008 Elsevier B.V. All rights reserved.

Speech Analysis using Modern Techniques of Nonlinear Dynamics

Medical fields requires fast, simple and noninvasive methods of diagnostic techniques. Several methods are available and possible because of the growth of technology that provides the necessary means of collecting and processing signals. The present thesis details the work done in the field of voice signals. New methods of analysis have been developed to understand the complexity of voice signals, such as nonlinear dynamics aiming at the exploration of voice signals dynamic nature. The purpose of this thesis is to characterize complexities of pathological voice from healthy signals and to differentiate stuttering signals from healthy signals. Efficiency of various acoustic as well as non linear time series methods are analysed. Three groups of samples are used, one from healthy individuals, subjects with vocal pathologies and stuttering subjects. Individual vowels/ and a continuous speech data for the utterance of the sentence "iruvarum changatimaranu" the meaning in English is "Both are good friends" from Malayalam language are recorded using a microphone . The recorded audio are converted to digital signals and are subjected to analysis.Acoustic perturbation methods like fundamental frequency (FO), jitter, shimmer, Zero Crossing Rate(ZCR) were carried out and non linear measures like maximum lyapunov exponent(Lamda max), correlation dimension (D2), Kolmogorov exponent(K2), and a new measure of entropy viz., Permutation entropy (PE) are evaluated for all three groups of the subjects. Permutation Entropy is a nonlinear complexity measure which can efficiently distinguish regular and complex nature of any signal and extract information about the change in dynamics of the process by indicating sudden change in its value. The results shows that nonlinear dynamical methods seem to be a suitable technique for voice signal analysis, due to the chaotic component of the human voice. Permutation entropy is well suited due to its sensitivity to uncertainties, since the pathologies are characterized by an increase in the signal complexity and unpredictability. Pathological groups have higher entropy values compared to the normal group. The stuttering signals have lower entropy values compared to the normal signals.PE is effective in charaterising the level of improvement after two weeks of speech therapy in the case of stuttering subjects. PE is also effective in characterizing the dynamical difference between healthy and pathological subjects. This suggests that PE can improve and complement the recent voice analysis methods available for clinicians. The work establishes the application of the simple, inexpensive and fast algorithm of PE for diagnosis in vocal disorders and stuttering subjects.

Permutation Entropy Based Analysis of Complex Signals for Characterising Change in System Dynamics

Timely detection of sudden change in dynamics that adversely affect the performance of systems and quality of products has great scientific relevance. This work focuses on effective detection of dynamical changes of real time signals from mechanical as well as biological systems using a fast and robust technique of permutation entropy (PE). The results are used in detecting chatter onset in machine turning and identifying vocal disorders from speech signal.Permutation Entropy is a nonlinear complexity measure which can efficiently distinguish regular and complex nature of any signal and extract information about the change in dynamics of the process by indicating sudden change in its value. Here we propose the use of permutation entropy (PE), to detect the dynamical changes in two non linear processes, turning under mechanical system and speech under biological system.Effectiveness of PE in detecting the change in dynamics in turning process from the time series generated with samples of audio and current signals is studied. Experiments are carried out on a lathe machine for sudden increase in depth of cut and continuous increase in depth of cut on mild steel work pieces keeping the speed and feed rate constant. The results are applied to detect chatter onset in machining. These results are verified using frequency spectra of the signals and the non linear measure, normalized coarse-grained information rate (NCIR).PE analysis is carried out to investigate the variation in surface texture caused by chatter on the machined work piece. Statistical parameter from the optical grey level intensity histogram of laser speckle pattern recorded using a charge coupled device (CCD) camera is used to generate the time series required for PE analysis. Standard optical roughness parameter is used to confirm the results.Application of PE in identifying the vocal disorders is studied from speech signal recorded using microphone. Here analysis is carried out using speech signals of subjects with different pathological conditions and normal subjects, and the results are used for identifying vocal disorders. Standard linear technique of FFT is used to substantiate thc results.The results of PE analysis in all three cases clearly indicate that this complexity measure is sensitive to change in regularity of a signal and hence can suitably be used for detection of dynamical changes in real world systems. This work establishes the application of the simple, inexpensive and fast algorithm of PE for the benefit of advanced manufacturing process as well as clinical diagnosis in vocal disorders.

Identifikation spezieller Funktionen, die durch Rodriguesformeln gegeben sind

Es ist allgemein bekannt, dass sich zwei gegebene Systeme spezieller Funktionen durch Angabe einer Rekursionsgleichung und entsprechend vieler Anfangswerte identifizieren lassen, denn computeralgebraisch betrachtet hat man damit eine Normalform vorliegen. Daher hat sich die interessante Forschungsfrage ergeben, Funktionensysteme zu identifizieren, die über ihre Rodriguesformel gegeben sind. Zieht man den in den 1990er Jahren gefundenen Zeilberger-Algorithmus für holonome Funktionenfamilien hinzu, kann die Rodriguesformel algorithmisch in eine Rekursionsgleichung überführt werden. Falls die Funktionenfamilie überdies hypergeometrisch ist, sogar laufzeiteffizient. Um den Zeilberger-Algorithmus überhaupt anwenden zu können, muss es gelingen, die Rodriguesformel in eine Summe umzuwandeln. Die vorliegende Arbeit beschreibt die Umwandlung einer Rodriguesformel in die genannte Normalform für den kontinuierlichen, den diskreten sowie den q-diskreten Fall vollständig. Das in Almkvist und Zeilberger (1990) angegebene Vorgehen im kontinuierlichen Fall, wo die in der Rodriguesformel auftauchende n-te Ableitung über die Cauchysche Integralformel in ein komplexes Integral überführt wird, zeigt sich im diskreten Fall nun dergestalt, dass die n-te Potenz des Vorwärtsdifferenzenoperators in eine Summenschreibweise überführt wird. Die Rekursionsgleichung aus dieser Summe zu generieren, ist dann mit dem diskreten Zeilberger-Algorithmus einfach. Im q-Fall wird dargestellt, wie Rekursionsgleichungen aus vier verschiedenen q-Rodriguesformeln gewonnen werden können, wobei zunächst die n-te Potenz der jeweiligen q-Operatoren in eine Summe überführt wird. Drei der vier Summenformeln waren bislang unbekannt. Sie wurden experimentell gefunden und per vollständiger Induktion bewiesen. Der q-Zeilberger-Algorithmus erzeugt anschließend aus diesen Summen die gewünschte Rekursionsgleichung. In der Praxis ist es sinnvoll, den schnellen Zeilberger-Algorithmus anzuwenden, der Rekursionsgleichungen für bestimmte Summen über hypergeometrische Terme ausgibt. Auf dieser Fassung des Algorithmus basierend wurden die Überlegungen in Maple realisiert. Es ist daher sinnvoll, dass alle hier aufgeführten Prozeduren, die aus kontinuierlichen, diskreten sowie q-diskreten Rodriguesformeln jeweils Rekursionsgleichungen erzeugen, an den hypergeometrischen Funktionenfamilien der klassischen orthogonalen Polynome, der klassischen diskreten orthogonalen Polynome und an der q-Hahn-Klasse des Askey-Wilson-Schemas vollständig getestet werden. Die Testergebnisse liegen tabellarisch vor. Ein bedeutendes Forschungsergebnis ist, dass mit der im q-Fall implementierten Prozedur zur Erzeugung einer Rekursionsgleichung aus der Rodriguesformel bewiesen werden konnte, dass die im Standardwerk von Koekoek/Lesky/Swarttouw(2010) angegebene Rodriguesformel der Stieltjes-Wigert-Polynome nicht korrekt ist. Die richtige Rodriguesformel wurde experimentell gefunden und mit den bereitgestellten Methoden bewiesen. Hervorzuheben bleibt, dass an Stelle von Rekursionsgleichungen analog Differential- bzw. Differenzengleichungen für die Identifikation erzeugt wurden. Wie gesagt gehört zu einer Normalform für eine holonome Funktionenfamilie die Angabe der Anfangswerte. Für den kontinuierlichen Fall wurden umfangreiche, in dieser Gestalt in der Literatur noch nie aufgeführte Anfangswertberechnungen vorgenommen. Im diskreten Fall musste für die Anfangswertberechnung zur Differenzengleichung der Petkovsek-van-Hoeij-Algorithmus hinzugezogen werden, um die hypergeometrischen Lösungen der resultierenden Rekursionsgleichungen zu bestimmen. Die Arbeit stellt zu Beginn den schnellen Zeilberger-Algorithmus in seiner kontinuierlichen, diskreten und q-diskreten Variante vor, der das Fundament für die weiteren Betrachtungen bildet. Dabei wird gebührend auf die Unterschiede zwischen q-Zeilberger-Algorithmus und diskretem Zeilberger-Algorithmus eingegangen. Bei der praktischen Umsetzung wird Bezug auf die in Maple umgesetzten Zeilberger-Implementationen aus Koepf(1998/2014) genommen. Die meisten der umgesetzten Prozeduren werden im Text dokumentiert. Somit wird ein vollständiges Paket an Algorithmen bereitgestellt, mit denen beispielsweise Formelsammlungen für hypergeometrische Funktionenfamilien überprüft werden können, deren Rodriguesformeln bekannt sind. Gleichzeitig kann in Zukunft für noch nicht erforschte hypergeometrische Funktionenklassen die beschreibende Rekursionsgleichung erzeugt werden, wenn die Rodriguesformel bekannt ist.

Graph-based algorithms for comparison and prediction of household-level energy use profiles

We present an efficient graph-based algorithm for quantifying the similarity of household-level energy use profiles, using a notion of similarity that allows for small time–shifts when comparing profiles. Experimental results on a real smart meter data set demonstrate that in cases of practical interest our technique is far faster than the existing method for computing the same similarity measure. Having a fast algorithm for measuring profile similarity improves the efficiency of tasks such as clustering of customers and cross-validation of forecasting methods using historical data. Furthermore, we apply a generalisation of our algorithm to produce substantially better household-level energy use forecasts from historical smart meter data.

A collocation method for solving singular integro-differential equations

This paper describes a collocation method for numerically solving Cauchy-type linear singular integro-differential equations. The numerical method is based on the transformation of the integro-differential equation into an integral equation, and then applying a collocation method to solve the latter. The collocation points are chosen as the Chebyshev nodes. Uniform convergence of the resulting method is then discussed. Numerical examples are presented and solved by the numerical techniques.

Real orthogonal polynomials in frequency analysis

We study the use of para-orthogonal polynomials in solving the frequency analysis problem. Through a transformation of Delsarte and Genin, we present an approach for the frequency analysis by using the zeros and Christoffel numbers of polynomials orthogonal on the real line. This leads to a simple and fast algorithm for the estimation of frequencies. We also provide a new method, faster than the Levinson algorithm, for the determination of the reflection coefficients of the corresponding real Szego polynomials from the given moments.

Guided Bus Rapid Transit

Electrical Bus Rapid Transit (eBRT) is a charging electrical public transport which brings a clean, high performance, and affordable cost alternative from the conventional traffic vehicles which work with combustion and hybrid technology. These buses charge the battery in every bus stop to arrive at the next station. But, this charging system needs an appropriate infrastructure called pantograph, and it requires a high precision bus location to maintain battery lifetime, energy saving and charging time. To overcome this issue Vicomtech and Datik has planned a project based on computer vision to help to the driver to locate the vehicle in the correct place. In this document, we present a mono camera bus driver guided fast algorithm because these vehicles embedded computers do not support high computation and precision operations. In addition to the frequent lane sign, there are more accurate geometric beacons painted on the road to bring metric information to the vision system. This method uses segmentation to binarize the image discriminating the background space. Besides it detects, tracks and counts different lane mark contours in addition to classify each special painted mark. Besides it does not need any calibration task to calculate longitudinal and cross distances because we know the lane mark sizes.