Automatic analysis of facial actions (AFA) can reveal a person’s emotion, intention, and physical state, and make possible a wide range of applications. To enable reliable, valid, and efficient AFA, this thesis investigates automatic analysis of facial actions through transductive, supervised and unsupervised learning. Supervised learning for AFA is challenging, in part, because of individual differences among persons in face shape and appearance and variation in video acquisition and context. To improve generalizability across persons, we propose a transductive framework, Selective Transfer Machine (STM), which personalizes generic classifiers through joint sample reweighting and classifier learning. By personalizing classifiers, STM offers improved generalization to unknown persons. As an extension, we develop a variant of STM for use when partially labeled data are available. Additional challenges for supervised learning include learning an optimal representation for classification, variation in base rates of action units (AUs), correlation between AUs and temporal consistency. While these challenges could be partly accommodated with an SVM or STM, a more powerful alternative is afforded by an end-to-end supervised framework (i.e., deep learning). We propose a convolutional network with long short-term memory (LSTM) and multi-label sampling strategies. We compared SVM, STM and deep learning approaches with respect to AU occurrence and intensity in and between BP4D+ [282] and GFT [93] databases, which consist of around 0.6 million annotated frames. Annotated video is not always possible or desirable. We introduce an unsupervised Branch-and-Bound framework to discover correlated facial actions in un-annotated video. We term this approach Common Event Discovery (CED). We evaluate CED in video and motion capture data. CED achieved moderate convergence with supervised approaches and enabled discovery of novel patterns occult to supervised approaches.

Neste texto são propostos algoritmos de filtragem adaptativa de baixo custo computacional para o processamento de sinais lineares no sentido amplo e para beamforming. Novas técnicas de filtragem adaptativa com baixo custo computacional são desenvolvidas para o processamento de sinais lineares no sentido amplo, representados por números complexos ou por quaternions. Os algoritmos propostos evitam a redundância de estatísticas de segunda ordem na matriz de auto correlação, o que é obtido por meio da substituição do vetor de dados original por um vetor de dados real contendo as mesmas informações. Dessa forma, evitam-se muitas operações entre números complexos (ou entre quaternions), que são substituídas por operações entre reais e números complexos (ou entre reais e quaternions), de menor custo computacional. Análises na media e na variância para qualquer algoritmo de quaternions baseados na técnica least-mean squares (LMS) são desenvolvidas. Também é obtido o algoritmo de quaternions baseado no LMS e com vetor de entrada real de mais rápida convergência. Uma nova versão estável e de baixo custo computacional do algoritmo recursive least squares (RLS) amplamente linear também é desenvolvida neste texto. A técnica é modificada para usar o método do dichotomous coordinate descent (DCD), resultando em uma abordagem de custo computacional linear em relação ao comprimento N do vetor de entrada (enquanto o algoritmo original possui custo computacional quadrático em N). Para aplicações em beamforming, são desenvolvidas novas técnicas baseadas no algoritmo adaptive re-weighting homotopy. As novas técnicas são aplicadas para arrays em que o número de fontes é menor do que o número de sensores, tal que a matriz de auto correlação se torna mal-condicionada. O algoritmo DCD é usado para obter uma redução adicional do custo computacional. / In this text, low-cost adaptive filtering techniques are proposed for widely-linear processing and beamforming applications. New reduced-complexity versions of widely-linear adaptive filters are proposed for complex and quaternion processing. The low-cost techniques avoid redundant secondorder statistics in the autocorrelation matrix, which is obtained replacing the original widely-linear data vector by a real vector with the same information. Using this approach, many complex-complex (or quaternion-quaternion) operations are substituted by less costly real-complex (or real-quaternion) computations in the algorithms. An analysis in the mean and in the variance is performed for quaternion-based techniques, suitable for any quaternion least-mean squares (LMS) algorithm. The fastest-converging widely-linear quaternion LMS algorithm with real-valued input is obtained. For complex-valued processing, a low-cost and stable version of the widely-linear recursive least-squares (RLS) algorithm is also developed. The widely-linear RLS technique is modified to apply the dichotomous coordinate descent (DCD) method, which leads to an algorithm with computational complexity linear on the data vector length N (in opposition to the original WL technique, for which the complexity is quadratic in N). New complex-valued techniques based on the adaptive re-weighting homotopy algorithm are developed for beamforming. The algorithms are applied to sensor arrays in which the number of interferer sources is less than the number of sensors, so that the autocorrelation matrix is ill-conditioned. DCD iterations are applied to further reduce the computational complexity.

Neste texto são propostos algoritmos de filtragem adaptativa de baixo custo computacional para o processamento de sinais lineares no sentido amplo e para beamforming. Novas técnicas de filtragem adaptativa com baixo custo computacional são desenvolvidas para o processamento de sinais lineares no sentido amplo, representados por números complexos ou por quaternions. Os algoritmos propostos evitam a redundância de estatísticas de segunda ordem na matriz de auto correlação, o que é obtido por meio da substituição do vetor de dados original por um vetor de dados real contendo as mesmas informações. Dessa forma, evitam-se muitas operações entre números complexos (ou entre quaternions), que são substituídas por operações entre reais e números complexos (ou entre reais e quaternions), de menor custo computacional. Análises na media e na variância para qualquer algoritmo de quaternions baseados na técnica least-mean squares (LMS) são desenvolvidas. Também é obtido o algoritmo de quaternions baseado no LMS e com vetor de entrada real de mais rápida convergência. Uma nova versão estável e de baixo custo computacional do algoritmo recursive least squares (RLS) amplamente linear também é desenvolvida neste texto. A técnica é modificada para usar o método do dichotomous coordinate descent (DCD), resultando em uma abordagem de custo computacional linear em relação ao comprimento N do vetor de entrada (enquanto o algoritmo original possui custo computacional quadrático em N). Para aplicações em beamforming, são desenvolvidas novas técnicas baseadas no algoritmo adaptive re-weighting homotopy. As novas técnicas são aplicadas para arrays em que o número de fontes é menor do que o número de sensores, tal que a matriz de auto correlação se torna mal-condicionada. O algoritmo DCD é usado para obter uma redução adicional do custo computacional. / In this text, low-cost adaptive filtering techniques are proposed for widely-linear processing and beamforming applications. New reduced-complexity versions of widely-linear adaptive filters are proposed for complex and quaternion processing. The low-cost techniques avoid redundant secondorder statistics in the autocorrelation matrix, which is obtained replacing the original widely-linear data vector by a real vector with the same information. Using this approach, many complex-complex (or quaternion-quaternion) operations are substituted by less costly real-complex (or real-quaternion) computations in the algorithms. An analysis in the mean and in the variance is performed for quaternion-based techniques, suitable for any quaternion least-mean squares (LMS) algorithm. The fastest-converging widely-linear quaternion LMS algorithm with real-valued input is obtained. For complex-valued processing, a low-cost and stable version of the widely-linear recursive least-squares (RLS) algorithm is also developed. The widely-linear RLS technique is modified to apply the dichotomous coordinate descent (DCD) method, which leads to an algorithm with computational complexity linear on the data vector length N (in opposition to the original WL technique, for which the complexity is quadratic in N). New complex-valued techniques based on the adaptive re-weighting homotopy algorithm are developed for beamforming. The algorithms are applied to sensor arrays in which the number of interferer sources is less than the number of sensors, so that the autocorrelation matrix is ill-conditioned. DCD iterations are applied to further reduce the computational complexity.

Locating a radiating source based on range or range measurements obtained from a network of passive sensors has been a subject of research over the past two decades due to the problem’s importance in applications in wireless communications, surveillance, navigation, geosciences, and several other fields. In this thesis, we develop new solution methods for the problem of localizing a single radiating source based on range and range-difference measurements. Iterative re-weighting algorithms are developed for both range-based and range-difference-based least squares localization. Then we propose a penalty convex-concave procedure for finding an approximate solution to nonlinear least squares problems that are related to the range measurements. Finally, the sequential convex relaxation procedures are proposed to obtain the nonlinear least squares estimate of source coordinates. Localization in wireless sensor network, where the RF signals are used to derive the ranging measurements, is the primary application area of this work. However, the solution methods proposed are general and could be applied to range and range-difference measurements derived from other types of signals. / Graduate / 0544 / ismailds@uvic.ca

No description available.

在本論文中我們提出了一種個人化情緒／情境音樂檢索方法。主要的概念為根據使用者的feedback來找出符合該使用者情緒／情境的音樂在features上所具備的特性，藉此達到個人化的效果。為了更明確表示出音樂的特性，我們利用統計features分布情況的方式來做為音樂的表示法。同時，定義了兩層features自動weighting的方法來決定每個feature在不同情緒／情境下的鑑別度。最後，我們將探討音樂特性與音色對不同的情緒／情境會造成什麼樣的影響，並試著分析音樂與情緒／情境間的關係。 / In this paper, an approach for personalized music retrieval based on emotions / situations is proposed. The main concept is to find out the properties of music that caused the user have emotions / situations responses via the user feedback. And using the user feedback will help us to establish a personalized music retrieval system based on emotions / situations. To represent the music properties clearly, we proposed a new method of music representation based on statistics. And we defined a two-phase features re-weighting method to find out the importance of features in different emotions / situations. At last, we will discuss the influence of music properties and timbre on different emotions / situations, and try to analyze the relationship between the emotions / situations.

<p>Minimum cycle mean (MCM) is an important concept in directed graphs. From clock period optimization, timing analysis to layout optimization, minimum cycle mean algorithms have found widespread use in VLSI system design optimization. With transistor size scaling to 10nm and below, complexities and size of the systems have grown rapidly over the last decade. Scalability of the algorithms both in terms of their runtime and memory usage is therefore important. </p> <p><br></p> <p>Among the few classical MCM algorithms, the algorithm by Young, Tarjan, and Orlin (YTO), has been particularly popular. When implemented with a binary heap, the YTO algorithm has the best runtime performance although it has higher asymptotic time complexity than Karp's algorithm. However, as an efficient implementation of YTO relies on data redundancy, its memory usage is higher and could be a prohibitive factor in large size problems. On the other hand, a typical implementation of Karp's algorithm can also be memory hungry. An early termination technique from Hartmann and Orlin (HO) can be directly applied to Karp's algorithm to improve its runtime performance and memory usage. Although not as efficient as YTO in runtime, HO algorithm has much less memory usage than YTO. We propose several improvements to HO algorithm. The proposed algorithm has comparable runtime performance to YTO for circuit graphs and dense random graphs while being better than HO algorithm in memory usage. </p> <p><br></p> <p>Minimum balancing of a directed graph is an application of the minimum cycle mean algorithm. Minimum balance algorithms have been used to optimally distribute slack for mitigating process variation induced timing violation issues in clock network. In a conventional minimum balance algorithm, the principal subroutine is that of finding MCM in a graph. In particular, the minimum balance algorithm iteratively finds the minimum cycle mean and the corresponding minimum-mean cycle, and uses the mean and cycle to update the graph by changing edge weights and reducing the graph size. The iterations terminate when the updated graph is a single node. Studies have shown that the bottleneck of the iterative process is the graph update operation as previous approaches involved updating the entire graph. We propose an improvement to the minimum balance algorithm by performing fewer changes to the edge weights in each iteration, resulting in better efficiency.</p> <p><br></p> <p>We also apply the minimum cycle mean algorithm in latency insensitive system design. Timing violations can occur in high performance communication links in system-on-chips (SoCs) in the late stages of the physical design process. To address the issues, latency insensitive systems (LISs) employ pipelining in the communication channels through insertion of the relay stations. Although the functionality of a LIS is robust with respect to the communication latencies, such insertion can degrade system throughput performance. Earlier studies have shown that the proper sizing of buffer queues after relay station insertion could eliminate such performance loss. However, solving the problem of maximum performance buffer queue sizing requires use of mixed integer linear programming (MILP) of which runtime is not scalable. We formulate the problem as a parameterized graph optimization problem where for every communication channel there is a parameterized edge with buffer counts as the edge weight. We then use minimum cycle mean algorithm to determine from which edges buffers can be removed safely without creating negative cycles. This is done iteratively in the similar style as the minimum balance algorithm. Experimental results suggest that the proposed approach is scalable. Moreover, quality of the solution is observed to be as good as that of the MILP based approach.</p><p><br></p>