Incremental Linear Discriminant Analysis Using Sufficient Spanning Sets and Its Applications

This paper presents an incremental learning solution for Linear Discriminant Analysis (LDA) and its applications to object recognition problems. We apply the sufficient spanning set approximation in three steps i.e. update for the total scatter matrix, between-class scatter matrix and the projected data matrix, which leads an online solution which closely agrees with the batch solution in accuracy while significantly reducing the computational complexity. The algorithm yields an efficient solution to incremental LDA even when the number of classes as well as the set size is large. The incremental LDA method has been also shown useful for semi-supervised online learning. Label propagation is done by integrating the incremental LDA into an EM framework. The method has been demonstrated in the task of merging large datasets which were collected during MPEG standardization for face image retrieval, face authentication using the BANCA dataset, and object categorisation using the Caltech101 dataset. © 2010 Springer Science+Business Media, LLC.

Management and Analysis of Unstructured Construction Data Types

Compared with structured data sources that are usually stored and analyzed in spreadsheets, relational databases, and single data tables, unstructured construction data sources such as text documents, site images, web pages, and project schedules have been less intensively studied due to additional challenges in data preparation, representation, and analysis. In this paper, our vision for data management and mining addressing such challenges are presented, together with related research results from previous work, as well as our recent developments of data mining on text-based, web-based, image-based, and network-based construction databases.

Data Analysis on Complicated Construction Data Sources: Vision, Research, and Recent Developments

Compared with construction data sources that are usually stored and analyzed in spreadsheets and single data tables, data sources with more complicated structures, such as text documents, site images, web pages, and project schedules have been less intensively studied due to additional challenges in data preparation, representation, and analysis. In this paper, our definition and vision for advanced data analysis addressing such challenges are presented, together with related research results from previous work, as well as our recent developments of data analysis on text-based, image-based, web-based, and network-based construction sources. It is shown in this paper that particular data preparation, representation, and analysis operations should be identified, and integrated with careful problem investigations and scientific validation measures in order to provide general frameworks in support of information search and knowledge discovery from such information-abundant data sources.

Distributed flow algorithms for scalable similarity visualization

We describe simple yet scalable and distributed algorithms for solving the maximum flow problem and its minimum cost flow variant, motivated by problems of interest in objects similarity visualization. We formulate the fundamental problem as a convex-concave saddle point problem. We then show that this problem can be efficiently solved by a first order method or by exploiting faster quasi-Newton steps. Our proposed approach costs at most O(|ε|) per iteration for a graph with |ε| edges. Further, the number of required iterations can be shown to be independent of number of edges for the first order approximation method. We present experimental results in two applications: mosaic generation and color similarity based image layouting. © 2010 IEEE.

Response of growth and fatty acid compositions of Nannochloropsis sp to environmental factors under elevated CO2 concentration

Nannochloropsis sp. was grown with different levels of nitrate, phosphate, salinity and temperature with CO2 at 2,800 mu l l(-1). Increased levels of NaNO3 and KH2PO4 raised protein and polyunsaturated fatty acids (PUFAs) contents but decreased carbohydrate, total lipid and total fatty acids (TFA) contents. Nannochloropsis sp. grew well at salinities from 22 to 49 g l(-1), and lowering salinity enhanced TFA and PUFAs contents. TFA contents increased with the increasing temperature but PUFAs contents decreased. The highest eicosapentaenoic acid (EPA, 20:5 omega 3) content based on the dry mass was above 3% under low N (150 mu M NaNO3) or high N (3000 mu M NaNO3) condition. Excessive nitrate, low salinity and temperature are thus favorable factors for improving EPA yields in Nannochloropsis sp.

结构化P2P网络上可靠的基于内容路由协议

在结构化P2P网络上构建基于内容的发布/订阅系统,可以很好地支持大规模、高度动态的分布式应用.然而,现有的基于内容的路由协议在P2P网络上只能提供弱的可靠性保证.根据结构化P2P网络的路由协议的特点,设计了一种新型的基于内容的路由协议——基于编码区间的路由(identifierrangebasedrouting,简称IRBR)协议.IRBR协议具有良好的容错性,只要事件的发布者与订阅者之间在P2P网络中是可达的,则订阅者一定能够收到它所订阅的事件,且只收到一次.同时,该协议也比现有的协议具有更高的事件路由效率.在Pastry上开发了一个原型系统,模拟实验表明了该协议的效率和容错性.

一种基于速率的发布/订阅系统的准入控制机制

提出了基于内容发布／订阅系统的一种准入控制机制RacsCBPS来保障客户端的服务质量．首先分析了基于内容发布／订阅系统中实现准入控制机制的难点，给出了RacsCBPS的基本模型，在此基础上，提出了基于覆盖关系的资源需求计算方法和以订阅分发路径为基础的准入控制算法．RacsCBPS在不影响发布／订阅系统松散耦合性的情况下，能够有效地解决因系统资源不足而导致的事件过载问题，同时为系统提供了不同的准入准则，以便在系统资源利用率和服务质量保证程度之间作出不同的权衡．最后通过实验验证了准入控制机制的有效性和相应的系统资源利用率．

不同抗旱性青稞LEA2/LEA3蛋白基因的克隆与表达

作物的抗旱性是一个多基因控制的、极为复杂的数量性状，植物对干旱在分子水平上的差异反应通过植物组织生理和细胞生物学水平，最终表现为植物抗旱性的不同。在我国，旱地农业超过耕地面积的50%，但水资源短缺，因此培育和选育抗旱高产作物是发展节水型农业最有效的途径。 青藏高原气候恶劣、年均降雨量少，也是世界大麦初生起源中心，因而蕴藏了十分丰富的与抗逆相关的种质资源材料，从这些特殊的资源材料克隆抗旱基因，不仅对培育抗旱、优质、高产大麦新品种具有重要理论意义和经济价值，而且对整个作物抗旱基础和育种应用研究都具重大促进作用。 为了筛选青稞（裸大麦，Hordeum vulgare ssp. vulgare）抗旱性材料，本研究选用来自青藏高原不同地区的84份青稞为材料，在叶片失水率(water loss rate, WLR)检测分析的基础上，选择失水率值差异显著的12个品种，通过相对含水量（relative water content, RWC）和反复干旱法评价其抗旱性，并通过植株对干旱胁迫下的丙二醛（MDA）含量和游离脯氨酸（free-proline）含量变化，了解不同抗旱性材料的生理反应特性。选择抗旱性强弱不同的品种各两份进行LEA2蛋白基因(Dhn6基因)、LEA3蛋白基因(HVA1基因)的克隆，比较LEA蛋白结构差异与作物抗旱性之间的关系。同时，对抗旱性不同的青稞品种受到干旱时间不同的失水变化率（dynamics water loss rate, DWLR）进行了检测；对抗旱性不同的青稞对照材料进行2 h、4 h、8 h和12 h的快速干旱处理，通过SYBR Green实时荧光定量RT-PCR技术对Dhn6基因、Dhn11基因、Dhn13基因和HVA1基因在不同抗旱性材料受到不同干旱时间处理后的相对表达水平进行了检测。本研究对LEA蛋白基因在抗旱性不同的青稞材料中的干旱胁迫分子水平上的差异反应进行了研究，也对植物的抗旱机理进行了初步探讨。主要研究结果如下： 1. 青稞苗期进行离体叶片失水率测定结果表明，来自青藏高原的84份青稞材料的WLR在0.086~0.205gh-1g-1DW之间。选择WLR低于0.1gh-1g-1DW和WLR高于0.18gh-1g-1DW的品种各6份，并对苗期分别进行未干旱及干旱12小时的处理。相对含水量检测结果表明，低失水率青稞材料干旱后的具有更高的相对含水量，盆栽缺水试验也显示叶片失水率低的材料耐旱能力强于失水率高的材料。通过水合茚三酮法测定离体叶片游离脯氨酸的含量，结果表明，所有品种未干旱处理时，游离脯氨酸含量差异不大（17.10~25.74 µgg-1FW）；干旱12小时后，低失水率的品种游离脯氨酸含量明显增高（32.99~53.45µgg-1FW），高失水率品种的游离脯氨酸含量与干旱前变化不明显(P<0.05)。硫代巴比妥酸法测定离体叶片丙二醛(MDA)含量，结果显示，12份所选对照品种中，丙二醛的含量在0.97~2.74nmolg-1FW，干旱12小时后丙二醛的含量显著上升（1.46~4.74nmolg-1FW），高失水率的6个品种的丙二醛含量在未干旱和干旱处理时都明显高于低WLR品种。本研究结果表明青稞的低失水率、低丙二醛含量、高相对含水量和高脯氨酸含量具相关性（P<0.05）。综上研究，我们认为作物失水率的测定可以作为快速检测作物抗旱性的指标之一，因此，强抗旱品种喜玛拉10号(TR1)、品比14号(TR2)和弱抗旱品种冬青8号(TS1)、QB24 (TS2)被选作抗旱基因克隆和表达分析的研究材料。 2. 高等植物胚胎发育晚期丰富蛋白(late embryogenesis abundant proteins, LEA proteins)与植物耐脱水性密切相关，为了探讨青稞LEA蛋白结构差异性与植物抗旱性的关系，本研究以强抗旱品种（喜玛拉10号、品比14号）和弱抗旱品种（冬青8号、QB24）为材料，利用同源克隆法，通过RT-PCR，分别克隆了与抗旱性密切相关的Dhn6基因和HVA1基因。Dhn6基因序列分析结果表明，强抗旱品种品比14号和弱抗旱品种冬青8号Dhn6基因所克隆到的序列为1026bp，它们之间只有5个碱基的差异；喜玛拉10号和QB24克隆到的序列长963bp。在强弱不同的抗旱品种中有22个核苷酸易突变位点，相应的脱水素氨基酸序列推导结果表明，22个核苷酸突变位点中，仅有8个位点导致相应的氨基酸残基的改变，其余的位点系同义突变，另外，21个富含甘氨酸序列的缺失并没有联系作物抗旱性特征。推测这些同义突变位点的氨基酸残基对维持青稞DHN6蛋白的正常结构和功能起着非常重要的作用，也可能DHN6蛋白对青稞长期适应逆境胁迫和遗传进化的结果。对HVA1基因的序列分析结果表明，冬青8号、QB24、品比14号和喜玛拉10号的目的基因核苷酸序列全长分别为661bp、697bp、694bp和691bp，它们都包含1个完整的开放阅读框。相应的LEA3蛋白氨基酸序列结果表明，11个高度保守的氨基酸残基组成基元重复序列的拷贝数与青稞抗旱性之间没有必然关系，在强抗旱品种（喜玛拉10号、品比14号）中三个共同的氨基酸突变位点Gln32、Arg33和Ala195可能对抗旱蛋白的结构和功能有影响；另外，强抗旱青稞品种LEA3蛋白质中11-氨基酸保守基元序列拷贝数和极性氨基酸占蛋白的比例更高，推测LEA3蛋白中基元序列拷贝数和极性氨基酸占蛋白的比例对该蛋白的结构和功能影响更大。 3. LEA蛋白基因的表达水平的上调与植物的耐脱水性密切相关，我们对强抗旱性材料（喜玛拉10号、品比14号）和弱抗旱材料（冬青8号、QB24）进行干旱处理2 h、4 h、6 h、8 h和10 h的失水变化率进行测定，结果表明弱抗旱品种在2~4小时之间失水率变化最明显，而四个对照品种的失水率在8小时后和24小时的失水率值变化不大。进一步提取青稞苗期进行2 h、4 h、8 h和12 h的干旱处理后的总RNA，通过SYBR Green实时荧光定量RT-PCR技术对青稞脱水素基因(Dhn6、Dhn11和Dhn13)和LEA3蛋白基因(HVA1)的相对表达水平受干旱时间和作物抗旱性的影响进行了检测。研究发现，抗旱性不同的青稞品种随干旱处理的时间延长，Dhn6、Dhn11、Dhn13和HVA1基因的相对表达水平不同。 Dhn6基因的相对表达水平在强抗旱青稞品种干旱8小时后快速上升，但在弱抗旱青稞品种干旱处理12小时后检测到更高表达量；Dhn11基因在对照青稞抗旱品种的表达累积水平随干旱时间的延长持续下降；整个干旱过程中，Dhn13基因的相对表达水平在弱抗旱品种持续上升，在强抗旱品种中干旱处理8小时快速上升并达到最高，干旱12小时后降低。与脱水素基因相比较，强抗旱青稞品种在干旱2小时后HVA1基因的相对表达水平显著升高，相对表达量随干旱处理的时间持续上升，在干旱12小时后达到最高；与之相比较，在整个干旱过程中，弱抗旱品种的相对表达水平显著低于强抗旱品种，在干旱8小时之前弱抗旱品种的相对表达水平变化不明显；在干旱8~12小时后却显著上升。上述结果表明，不同的LEA蛋白在植物耐脱水过程中的干旱表达累积水平不同；干旱不是诱导高等植物Dhn11基因表达的主要因素；植物的抗旱性不同，不同LEA蛋白基因对干旱的反应有差异。推测某些LEA蛋白基因的干旱胁迫早期表达累积程度与植物的抗旱性直接相关；其中，Dhn11基因和Dhn12基因不同的表达模式可能与干旱调控表达顺式作用成分(dehydration responsive element, DRE)的有无或结构上的差异有关。 本研究结果认为，(1)失水率和相对含水量可作为植物抗旱性检测的指标之一；(2) DHN6同义突变位点的氨基酸残基对维持该蛋白的正常结构和功能起着重要作用；(3) 11-氨基酸保守基元序列拷贝数和极性氨基酸的比例对LEA3蛋白结构和功能有重要影响；(4)LEA蛋白表达随着干旱胁迫程度而增加，但Dhn11基因并不受干旱诱导表达；(5)作物的抗旱性不同，LEA蛋白对干旱的累积反应并不相同，干旱早期LEA蛋白的累积程度可能会影响植物的抗旱性。 Drought resistance was a complex trait which involved multiple physiological and biochemical mechanisms and regulation of numerous genes. Because its complex traits, it is difficult to understand the mechanisms of drought resistance in plants. Plants respond to water stress through multiple physiological mechanisms at the cellular, tissue, and whole-plant levels. Tibetan hulless barley, a pure line, is a selfing annual plant that has predominantly penetrated into the Qinghai-Tibetan Plateau and remains stable populations there. The wide ecological range of Tibetan hulless barley differs in water availability, temperature, soil type and vegetation, which makes it possess a high potential of adaptive diversity to abiotic stresses. This adaptive genetic diversity indicates that the potential of Tibetan hulless barley serves as a good source for drought resistance alleles for breeding purposes. 12 contrasting drought-tolerant genotypes were selected to measure relative water content (RWC), maldondialdehyde (MDA) and proline content, based on values of water loss rate (WLR) and repeated drought methods from Tibetan populations of cultivated hulless barley. As a result of the screening, sensitive and tolerant genotypes were identified to clarify relationships between characteristics of LEA2/LEA3 genes sequences and expression and drought-tolerant genotypes, associated with resistance to water deficit. In addition, dynamics water loss rate (DWLR) was measured to observe the changes on diffrential drought-tolerant genotypes. Real-time quantitative RT-PCR was applied to detect relative expression levels of Dhn6, Dhn11, Dhn13 and HVA1 genes in sensitive and tolerant genotypes with 2 h, 4 h, 8h and 12 h of dehydration. In the present study, differential sequences and expression of LEA2/LEA3 genes were explored in Tibetan hulless barley, associated with phenotypically diverse drought-tolerant genotypes. 1. The assessments of WLR and RWC were considered as an alternative measure of plant water statues reflecting the metabolic activity in plants, and the parameters of MDA and proline contents were usually consistent with the resistance to water stress. The values of detached leaf WLR of the tested genotypes were highly variable among 84 genotypes, ranging from 0.086 to 0.205 g/h.g DW. The 12 most contrasting genotypes (6 genotypes with the lowest values of WLR and 6 genotypes with the highest values of WLR) were further validated by measuring RWC, MDA and free-proline contents, which were well watered and dehydrated for 12 h. Results of RWC indicated that the values of 12 contrasting genotypes RWC ranged from 89.94% to 93.38% under condition of well water, without significant differences, but 6 genotypes with lower WLR had higher RWC suffered from 12 h dehydration. The results indicated that lower MDA contents, lower scores of WLR and higher proline contents were associated with drought-tolerant genotypes in hulless barley. Remarkably, proline amounts were increased more notable in 6 tolerant genotypes than 6 sensitive genotypes after excised leaves were dehydrated for 12 h, with control to slight changes under condition of well water. Results of MDA contents showed that six 6 tolerant genotypes had lower MDA contents than the 6 sensitive genotypes under both stressed and non-stressed conditions. As a result of that screening, drought- resistant genotypes (Ximala 10 and Pinbi 14) and drought-sensitive genotypes (Dongqing 8 and QB 24) were chosen for comparing the differential characteristics of LEA2/LEA3 genes and their expression analysis. It was conclusion that measurements of WLR could be considered an alternative index as screening of drought-tolerant genotypes in crops. 2. Late embryogenesis abundant (LEA) proteins were thought to protect against water stress in plants. To explore the relationships between configuration of LEA proteins and phenotypically diverse drought-tolerant genotypes, sequences of LEA genes and their deduced proteins were compared in Tibetan hulless barley. Results of comparing Dhn6 gene in Ximala 10 and QB24 indicated that absence of 63bp was found, except that only 5 mutant nucleotides were found. While 22 mutant sites were taken place in Dhn6 gene between sensitive and tolerant lines, 14 synonymous mutation sites appeared in the contrasting genotypes. The additional/absent polypeptide of 21 polar amino acid residues was not consistent with phenotypically drought-tolerant genotypes in hulless barley. It was deduced that synonymous mutation sites would play important roles in holding out right configurations and functions on DHN6 protein. The sequencing analysis results indicated that each cloned HVA1 gene from four selected genotypes contained an entire open reading frame. The whole sequence of HVA1 gene from Dongqing 8, QB24, Pinbi 14 and Ximala 10 was respectively 661bp, 697bp, 694bp and 691bp. Results of DNA sequence analyses showed that the differences in nucleotides of HVA1 gene in sensitive genotypes were not consistent with that of tolerant genotypes, except for absence of 33 nucleotides from +154 to +186 (numbering from ATG) in QB24. Database searches using deduced amino acid sequences showed a high homology in LEA3 proteins in the selected genotypes. Multiple sequence alignments revealed that LEA3 protein from Dongqing 8 was composed of 8 repeats of an 11 amino acid motif, less the fourth motif than Pinbi 14, Ximala 10 and QB24. Consistent mutant amino acid residues appeared in contrasting genotypes by aligning and comparing the coding sequence region, including Gln32, Arg33 and Ala195 in tolerant genotypes as compared to Asp32, Glu33 and Thr195 (Thr184 in Dongqing 8) in sensitive lines. It was concluded that consistent appearance of Gln32, Arg33 and Ala195 would contributed to functions of LEA3 protein in crops, as well as higher proportion of 11-amino-repeating motifs and polar amino acid residues. 3. Most of the LEA genes are up-regulated by dehydration, salinity, or low temperature, are also induced by application of exogenous ABA, which increases in concentration in plants under various stress conditions and acts as a mobile stress signal. Higher levels of proteins of LEA group 3 accumulated was correlated well with high level of desiccation tolerance in severely dehydrated plant seedlings. Dehydrins (DHNs), members of LEA2 protein, are an immunologically distinct protein family, and Dhn genes expression is associated with plant response to dehydration. Dynamic water loss rate was measured between sensitive genotypes and tolerant genotypes after they were dehydrated for 2 h, 4 h, 6h and 8 h. Detailed measurements of WLR at the early stage of dehydration (2, 4, 6, and 8 h) showed that WLR was stabilizing after 8 h, and there were no significant changes between these values and WLR after 24 h. Drought stress was applied to 10-day-old seedlings by draining the solution from the container for defined dehydration periods. Leaf tissues of the selected genotypes were harvested from control plants (time 0); and after 2, 4, 8, and 12 h of dehydration. Differential expression trends of Dhn6, Dhn11, Dhn13 and HVA1 genes were detected in phenotypically diverse drought-tolerant hulless barleys, related to different time of dehydration. Results of quantitative real-time PCR indicated that relative level of HVA1 expression was always higher in tolerant genotypes, rapidly increasing at the earlier stages (after 2-4 h of dehydration). However, HVA1 expressions of sensitive genotypes had a fast increase from 8 h to 12 h of stress. Significant differences in expression trends of dehydrin genes between tolerant genotypes and sensitive lines were detected, mainly in Dhn6 and Dhn13 gene, depending on the duration of the dehydration stress. The relative expression levels of Dhn6 gene were significantly higher in tolerant genotypes after 8 h dehydration, by control with notable higher expression levels after 12 h water stress in sensitive ones. The relative expression levels of Dhn13 gene tended to ascend during exposure to dehydration in drought-sensitive genotypes. However, fluctuate trends of Dhn13 expression level were detected in drought-resistant lines, including in lower expression levels of 12 h dehydration as compared to 8 h water stress. It was conclusion that (1) diverse LEA proteins would play variable roles in resisting water stress in plants; (2) expression of Dhn11 gene was not induced by dehydrated signals because of the trends of expression descended in contrasting genotypes suffered from water deficit and (3) variable accumulations on LEA proteins would be appear in diverse drought-tolerant genotypes during dehydrations. It is deduced that higher accumulations of Dhn6 and Dhn13 expression in 8 h dehydration are related to diverse drought-tolerant lines in crops. The present results indicated that different dehydrin genes would play variable functional roles in resisting water stress when plants were suffered from water deficit. The authors suggest physiologically different reactions between resistant and sensitive genotypes may be the results of differential expression of drought-resistant genes and related signal genes in plants. In addition, contrarily induced expression of Dhn11 and Dhn12 was related to dehydration responsive element (DRE) in barleys. The present study indicated that (1) measurements of WLR and RWC could be considered as one index of drought-tolerant screenings; (2) synonymous mutation sites would play important roles in holding out right configurations and functions on DHN6 protein, (3) higher proportion of 11-amino-repeating motifs and polar amino acid residues would contribute to functions on LEA3 protein, (4) the longer drought, the more accumulation on LEA proteins, except for Dhn11 gene in crops and (5) differential responses on expression of LEA protein genes would result in physiological traits of drought tolerance in plants.

曲线演化图像分割和森林烟火预警系统

随着计算机技术，图像采集技术和数据存储技术等的进步，图像处理的应用领域越来越广泛。很多的应用系统是综合利用了电子，通讯和图像处理等技术而开发出来的，图像处理往往是系统的核心部分。图像分割是图像处理的核心技术，也是图像处理技术中的难点。所以研究图像分割技术具有非常重要的意义。 传统的图像分割方法有：使用模板对图像进行边缘检测等；利用滤波处理，频谱分析等数字信号处理处理技术进行分割。80年代末以来，偏微分方程方法越来越多地应用到图像分割领域中，已成为图像分割的有力工具。本文对基于偏微分方程的图像分割方法进行研究，介绍单开曲线演化分割算法，并基于Mumford-Shah模型提出一种带状目标分割方法。这种方法能将图像中的带状区域从图像中分割出来－这里假定带状区域的边界可用单值函数表示。与其它方法，如边缘检测分割，C-V模型分割和单开曲线分割相比，本文提出的方法得到的分割结果有与目标的边界吻合的更好，抗噪能力强等优点。 本文介绍了通过对可见光摄像机所拍摄图像进行分析来检测火的森林烟火预警系统。该系统是通过检测烟的存在来判断是否有火情。图像处理软件是森林烟火预警系统的核心组成部分。评价火灾预警系统性能有两个标准。一个是一旦发生火灾，预警系统能否快速地发出火警信号；另一个是在没有火情时，预警系统是否不报警，即误警率是否低。图像分割在设计图像处理算法时，主要在两个地方得到应用。在图像预处理阶段，利用单开曲线演化分割算法或带状区域的分割算法将森林区域分割出来。这样是为了在对图像进行处理时消除非森林区域中的目标对识别结果的影响，降低误警率。在图像处理阶段，利用图像分割算法将烟从图像中分割出来，准确及时报警。

CCD-微型计算机图象数据处理系统

本文主要介绍用于图象数据处理的 CCD-微机系统。该系统使用电荷耦合器件(CCD)作为传感器,并与微型计算机连接,进行图象数据的采集和处理。系统还包括有光学系统、CCD 驱动控制线路、计算机 I/O 接口和应用软件。数据采集程序用汇编语言编写,数据处理和打印程序用 BASIC 语言编写,整个软件用BASIC 语言编写的程序管理。应用该系统曾对静止和运动物体尺寸进行过非接触测量,重复性很好。

Fast Contour Matching Using Approximate Earth Mover's Distance

Weighted graph matching is a good way to align a pair of shapes represented by a set of descriptive local features; the set of correspondences produced by the minimum cost of matching features from one shape to the features of the other often reveals how similar the two shapes are. However, due to the complexity of computing the exact minimum cost matching, previous algorithms could only run efficiently when using a limited number of features per shape, and could not scale to perform retrievals from large databases. We present a contour matching algorithm that quickly computes the minimum weight matching between sets of descriptive local features using a recently introduced low-distortion embedding of the Earth Mover's Distance (EMD) into a normed space. Given a novel embedded contour, the nearest neighbors in a database of embedded contours are retrieved in sublinear time via approximate nearest neighbors search. We demonstrate our shape matching method on databases of 10,000 images of human figures and 60,000 images of handwritten digits.

Qualidade nos serviços públicos

Dissertação de Mestrado apresentada à Universidade Fernando Pessoa como parte dos requisitos para obtenção do grau de Mestre em Ciências da Comunicação, especialização em Relações Públicas.

Search by Shape Examples: Modeling Nonrigid Deformation

We describe our work on shape-based image database search using the technique of modal matching. Modal matching employs a deformable shape decomposition that allows users to select example objects and have the computer efficiently sort the set of objects based on the similarity of their shape. Shapes are compared in terms of the types of nonrigid deformations (differences) that relate them. The modal decomposition provides deformation "control knobs" for flexible matching and thus allows for selecting weighted subsets of shape parameters that are deemed significant for a particular category or context. We demonstrate the utility of this approach for shape comparison in 2-D image databases; however, the general formulation is applicable to signals of any dimensionality.

Seed Scheduling for Peer-to-Peer Networks

The initial phase in a content distribution (file sharing) scenario is a delicate phase due to the lack of global knowledge and the dynamics of the overlay. An unwise distribution of the pieces in this phase can cause delays in reaching steady state, thus increasing file download times. We devise a scheduling algorithm at the seed (source peer with full content), based on a proportional fair approach, and we implement it on a real file sharing client [1]. In dynamic overlays, our solution improves up to 25% the average downloading time of a standard protocol ala BitTorrent.

Region Segmentation via Deformable Model-Guided Split and Merge

An improved method for deformable shape-based image segmentation is described. Image regions are merged together and/or split apart, based on their agreement with an a priori distribution on the global deformation parameters for a shape template. The quality of a candidate region merging is evaluated by a cost measure that includes: homogeneity of image properties within the combined region, degree of overlap with a deformed shape model, and a deformation likelihood term. Perceptually-motivated criteria are used to determine where/how to split regions, based on the local shape properties of the region group's bounding contour. A globally consistent interpretation is determined in part by the minimum description length principle. Experiments show that the model-based splitting strategy yields a significant improvement in segmention over a method that uses merging alone.