PatchCity: Procedural City Generation using Texture Synthesis

PatchCity is a new approach to the procedural generation of city models. The algorithm uses texture synthesis to create a city layout in the visual style of one or more input examples. Data is provided in vector graphic form from either real or synthetic city definitions. The paper describes the PatchCity algorithm, illustrates its use, and identifies its strengths and limitations. The technique provides a greater range of features and styles of city layout than existing generative methods, thereby achieving results that are more realistic. An open source implementation of the algorithm is available.

Graph matching with subdivision surfaces for texture synthesis on surfaces

Existing texture synthesis-from-example strategies for polygon meshes typically make use of three components: a multi-resolution mesh hierarchy that allows the overall nature of the pattern to be reproduced before filling in detail; a matching strategy that extends the synthesized texture using the best fit from a texture sample; and a transfer mechanism that copies the selected portion of the texture sample to the target surface. We introduce novel alternatives for each of these components. Use of p2-subdivision surfaces provides the mesh hierarchy and allows fine control over the surface complexity. Adaptive subdivision is used to create an even vertex distribution over the surface. Use of the graph defined by a surface region for matching, rather than a regular texture neighbourhood, provides for flexible control over the scale of the texture and allows simultaneous matching against multiple levels of an image pyramid created from the texture sample. We use graph cuts for texture transfer, adapting this scheme to the context of surface synthesis. The resulting surface textures are realistic, tolerant of local mesh detail and are comparable to results produced by texture neighbourhood sampling approaches.

Combining anisotropic diffusion, transport equation and texture synthesis for inpainting textured images

In this work we propose a new image inpainting technique that combines texture synthesis, anisotropic diffusion, transport equation and a new sampling mechanism designed to alleviate the computational burden of the inpainting process. Given an image to be inpainted, anisotropic diffusion is initially applied to generate a cartoon image. A block-based inpainting approach is then applied so that to combine the cartoon image and a measure based on transport equation that dictates the priority on which pixels are filled. A sampling region is then defined dynamically so as to hold the propagation of the edges towards image structures while avoiding unnecessary searches during the completion process. Finally, a cartoon-based metric is computed to measure likeness between target and candidate blocks. Experimental results and comparisons against existing techniques attest the good performance and flexibility of our technique when dealing with real and synthetic images. © 2013 Elsevier B.V. All rights reserved.

Texture descriptor based on partially self-avoiding deterministic walker on networks

Texture image analysis is an important field of investigation that has attracted the attention from computer vision community in the last decades. In this paper, a novel approach for texture image analysis is proposed by using a combination of graph theory and partially self-avoiding deterministic walks. From the image, we build a regular graph where each vertex represents a pixel and it is connected to neighboring pixels (pixels whose spatial distance is less than a given radius). Transformations on the regular graph are applied to emphasize different image features. To characterize the transformed graphs, partially self-avoiding deterministic walks are performed to compose the feature vector. Experimental results on three databases indicate that the proposed method significantly improves correct classification rate compared to the state-of-the-art, e.g. from 89.37% (original tourist walk) to 94.32% on the Brodatz database, from 84.86% (Gabor filter) to 85.07% on the Vistex database and from 92.60% (original tourist walk) to 98.00% on the plant leaves database. In view of these results, it is expected that this method could provide good results in other applications such as texture synthesis and texture segmentation. (C) 2012 Elsevier Ltd. All rights reserved.

Synthesis of Nature Sounds for Speech Masking

The introduction of open-plan offices in the 1960s with the intent of making the workplace more flexible, efficient, and team-oriented resulted in a higher noise floor level, which not only made concentrated work more difficult, but also caused physiological problems, such as increased stress, in addition to a loss of speech privacy. Irrelevant background human speech, in particular, has proven to be a major factor in disrupting concentration and lowering performance. Therefore, reducing the intelligibility of speech and has been a goal of increasing importance in recent years. One method employed to do so is the use of masking noises, which consists in emitting a continuous noise signal over a loudspeaker system that conceals the perturbing speech. Studies have shown that while effective, the maskers employed to date – normally filtered pink noise – are generally poorly accepted by users. The collaborative "Private Workspace" project, within the scope of which this thesis was carried out, attempts to develop a coupled, adaptive noise masking system along with a physical structure to be used for open-plan offices so as to combat these issues. There is evidence to suggest that nature sounds might be more accepted as masker, in part because they can have a visual object that acts as the source for the sound. Direct audio recordings are not recommended for various reasons, and thus the nature sounds must be synthesized. This work done consists of the synthesis of a sound texture to be used as a masker as well as its evaluation. The sound texture is composed of two parts: a wind-like noise synthesized with subtractive synthesis, and a leaf-like noise synthesized through granular synthesis. Different combinations of these two noises produced five variations of the masker, which were evaluated at different levels along with white noise and pink noise using a modified version of an Oldenburger Satztest to test for an affect on speech intelligibility and a questionnaire to asses its subjective acceptance. The goal was to find which of the synthesized noises works best as a speech masker. This thesis first uses a theoretical introduction to establish the basics of sound perception, psychoacoustic masking, and sound texture synthesis. The design of each of the noises, as well as their respective implementations in MATLAB, is explained, followed by the procedures used to evaluate the maskers. The results obtained in the evaluation are analyzed. Lastly, conclusions are drawn and future work is and modifications to the masker are proposed. RESUMEN. La introducción de las oficinas abiertas en los años 60 tenía como objeto flexibilizar el ambiente laboral, hacerlo más eficiente y que estuviera más orientado al trabajo en equipo. Como consecuencia, subió el nivel de ruido de fondo, que no sólo dificulta la concentración, sino que causa problemas fisiológicos, como el aumento del estrés, además de reducir la privacidad. Hay estudios que prueban que las conversaciones de fondo en particular tienen un efecto negativo en el nivel de concentración y disminuyen el rendimiento de los trabajadores. Por lo tanto, reducir la inteligibilidad del habla es uno de los principales objetivos en la actualidad. Un método empleado para hacerlo ha sido el uso de ruido enmascarante, que consiste en reproducir señales continuas de ruido a través de un sistema de altavoces que enmascare el habla. Aunque diversos estudios demuestran que es un método eficaz, los ruidos utilizados hasta la fecha (normalmente ruido rosa filtrado), no son muy bien aceptados por los usuarios. El proyecto colaborativo "Private Workspace", dentro del cual se engloba el trabajo realizado en este Proyecto Fin de Grado, tiene por objeto desarrollar un sistema de ruido enmascarador acoplado y adaptativo, además de una estructura física, para su uso en oficinas abiertas con el fin de combatir los problemas descritos anteriormente. Existen indicios de que los sonidos naturales son mejor aceptados, en parte porque pueden tener una estructura física que simule ser la fuente de los mismos. La utilización de grabaciones directas de estos sonidos no está recomendada por varios motivos, y por lo tanto los sonidos naturales deben ser sintetizados. El presente trabajo consiste en la síntesis de una textura de sonido (en inglés sound texture) para ser usada como ruido enmascarador, además de su evaluación. La textura está compuesta de dos partes: un sonido de viento sintetizado mediante síntesis sustractiva y un sonido de hojas sintetizado mediante síntesis granular. Diferentes combinaciones de estos dos sonidos producen cinco variaciones de ruido enmascarador. Estos cinco ruidos han sido evaluados a diferentes niveles, junto con ruido blanco y ruido rosa, mediante una versión modificada de un Oldenburger Satztest para comprobar cómo afectan a la inteligibilidad del habla, y mediante un cuestionario para una evaluación subjetiva de su aceptación. El objetivo era encontrar qué ruido de los que se han sintetizado funciona mejor como enmascarador del habla. El proyecto consiste en una introducción teórica que establece las bases de la percepción del sonido, el enmascaramiento psicoacústico, y la síntesis de texturas de sonido. Se explica a continuación el diseño de cada uno de los ruidos, así como su implementación en MATLAB. Posteriormente se detallan los procedimientos empleados para evaluarlos. Los resultados obtenidos se analizan y se extraen conclusiones. Por último, se propone un posible trabajo futuro y mejoras al ruido sintetizado.

基于Gabor小波的着色及纹理合成算法

着色和纹理合成是图形图像中的两类基本研究课题。前者需根据用户定义的彩色笔触信息，自动对黑白照片、电影或者漫画染上颜色；后者则需根据用户输入的样本纹理，经计算得出与样本纹理视觉上近似的结果纹理。这两类课题都有广泛的应用背景。如着色常常用于给经典的黑白电影或者照片自动上色，解决现在的染色工序中存在的需要大量人工交互的难题；而纹理合成常用于电影和电子游戏的地形地貌、织物、头发等等纹理的自动生成。 这两大类问题都需要分析纹理特征，并且依赖于分析结果的准确性。Gabor小波滤波器与人眼的视觉感受野相当吻合，用它来分析纹理得到的结果比较精确。鉴于此，本文把Gabor小波应用到了着色问题和纹理合成中。对于着色问题，本文用基于Gabor小波的特征向量重新定义邻居关系，然后用最优化方法迭代地对照片和卡通染色。相比以往的算法，本算法具有用户交互少、效果好、算法简单稳健的优点，并且算法允许用户逐步地添加色彩细节。对于纹理合成，本文用基于Gabor小波的特征向量来预计算K-Coherence候选集，提高了K-Coherence算法的准确性，从而改进了纹理合成的最终效果。 本文提出的算法是天然并行的，因而可利用GPU加速，做到实时计算。

卡通化图像和视频的毛发纹理生成与替换

低成本卡通制作中的图像和视频通常缺乏对动物角色毛发效果的表现,为了能对已有图像及视频中的动物角色进行处理,为其增添具备真实感的毛发效果,提出一种毛发风格化算法——卡通化毛发纹理算法.针对卡通中的动物角色合成毛发纹理并进行替换,分为图像应用及视频应用2个部分.在图像替换时,对要进行风格化处理的目标区域进行图像结构分析,以获取覆盖目标区域的三角网格,再生成毛发纹元并映射于网格之上,通过绘制纹元来生成具备真实感的毛发效果;在进行视频替换时,提取视频关键帧并基于图像应用算法生成相应的卡通化毛发纹理进行图像替换,之后根据关键帧的替换结果指导整个视频的替换.为了获取随时间变化的图像关键帧目标区域,采用SIFT算法计算特征点在时间轴上的匹配;为了快速合成卡通化毛发纹理,采用基于GPU的光线行进算法加速毛发纹元的体绘制过程.实验结果表明,文中算法可成功地对已有图像及视频的动物角色添加具备真实感的毛发效果.

Génération et édition de textures géométriques représentées par des ensembles de points

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Minimum spanning trees for valley and ridge characterization in digital elevation maps

Texture synthesis employs neighbourhood matching to generate appropriate new content. Terrain synthesis has the added constraint that new content must be geographically plausible. The profile recognition and polygon breaking algorithm (PPA) [Chang et al. 1998] provides a robust mechanism for characterizing terrain as systems of valley and ridge lines in digital elevation maps. We exploit this to create a terrain characterization metric that is robust, efficient to compute and is sensitive to terrain properties.

Terrain regions are characterized as a minimum spanning tree derived from a graph created from the sample points of the elevation map which are encoded as weights in the edges of the graph. This formulation allows us to provide a single consistent feature definition that is sensitive to the pattern of ridges and valleys in the terrain Alternative formulations of these weights provide richer characteristicmeasures and we provide examples of alternate definitions based on curvature and contour measures.

We show that the measure is robust, with a significant portion derived directly from information local to the terrain sample. Global terrain characteristics introduce the issue of over- and underconnected valley/ridge lines when working with sub-regions. This is addressed by providing two graph construction strategies, which respectively provide an upper bound on connectivity as a single spanning tree, and a lower bound as a forest of trees.

Efficient minimum spanning tree algorithms are adapted to the context of terrain data and are shown to provide substantially better performance than previous PPA implementations. In particular, these are able to characterize valley and ridge behaviour at every point even in large elevation maps, providing a measure sensitive to terrain features at all scales.

The resulting graph based formulation provides an efficient and elegant algorithm for characterizing terrain features. The measure can be calculated efficiently, is robust under changes of neighbourhood position, size and resolution and the hybrid measure is sensitive to terrain features both locally and globally.

Restauração de imagens digitais com texturas utilizando técnicas de decomposição e equações diferenciais parciais

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Uma abordagem híbrida e semiautomática para estimativa de regiões cobertas por nuvens e sombras em imagens de satélite: análise e avaliação

Os principais objetivos deste trabalho são propor um algoritmo eficiente e o mais automático possível para estimar o que está coberto por regiões de nuvens e sombras em imagens de satélite; e um índice de confiabilidade, que seja aplicado previamente à imagem, visando medir a viabilidade da estimação das regiões cobertas pelos componentes atmosféricos usando tal algoritmo. A motivação vem dos problemas causados por esses elementos, entre eles: dificultam a identificação de objetos de imagem, prejudicam o monitoramento urbano e ambiental, e desfavorecem etapas cruciais do processamento digital de imagens para extrair informações ao usuário, como segmentação e classificação. Através de uma abordagem híbrida, é proposto um método para decompor regiões usando um filtro passa-baixas não-linear de mediana, a fim de mapear as regiões de estrutura (homogêneas), como vegetação, e de textura (heterogêneas), como áreas urbanas, na imagem. Nessas áreas, foram aplicados os métodos de restauração Inpainting por suavização baseado em Transformada Cosseno Discreta (DCT), e Síntese de Textura baseada em modelos, respectivamente. É importante salientar que as técnicas foram modificadas para serem capazes de trabalhar com imagens de características peculiares que são obtidas por meio de sensores de satélite, como por exemplo, as grandes dimensões e a alta variação espectral. Já o índice de confiabilidade, tem como objetivo analisar a imagem que contém as interferências atmosféricas e daí estimar o quão confiável será a redefinição com base no percentual de cobertura de nuvens sobre as regiões de textura e estrutura. Tal índice é composto pela combinação do resultado de algoritmos supervisionados e não-supervisionados envolvendo 3 métricas: Exatidão Global Média (EGM), Medida De Similaridade Estrutural (SSIM) e Confiança Média Dos Pixels (CM). Finalmente, verificou-se a eficácia destas metodologias através de uma avaliação quantitativa (proporcionada pelo índice) e qualitativa (pelas imagens resultantes do processamento), mostrando ser possível a aplicação das técnicas para solucionar os problemas que motivaram a realização deste trabalho.

Advanced Techniques for Image Quality Assessment of Modern X-ray Computed Tomography Systems

X-ray computed tomography (CT) imaging constitutes one of the most widely used diagnostic tools in radiology today with nearly 85 million CT examinations performed in the U.S in 2011. CT imparts a relatively high amount of radiation dose to the patient compared to other x-ray imaging modalities and as a result of this fact, coupled with its popularity, CT is currently the single largest source of medical radiation exposure to the U.S. population. For this reason, there is a critical need to optimize CT examinations such that the dose is minimized while the quality of the CT images is not degraded. This optimization can be difficult to achieve due to the relationship between dose and image quality. All things being held equal, reducing the dose degrades image quality and can impact the diagnostic value of the CT examination.

A recent push from the medical and scientific community towards using lower doses has spawned new dose reduction technologies such as automatic exposure control (i.e., tube current modulation) and iterative reconstruction algorithms. In theory, these technologies could allow for scanning at reduced doses while maintaining the image quality of the exam at an acceptable level. Therefore, there is a scientific need to establish the dose reduction potential of these new technologies in an objective and rigorous manner. Establishing these dose reduction potentials requires precise and clinically relevant metrics of CT image quality, as well as practical and efficient methodologies to measure such metrics on real CT systems. The currently established methodologies for assessing CT image quality are not appropriate to assess modern CT scanners that have implemented those aforementioned dose reduction technologies.

Thus the purpose of this doctoral project was to develop, assess, and implement new phantoms, image quality metrics, analysis techniques, and modeling tools that are appropriate for image quality assessment of modern clinical CT systems. The project developed image quality assessment methods in the context of three distinct paradigms, (a) uniform phantoms, (b) textured phantoms, and (c) clinical images.

The work in this dissertation used the “task-based” definition of image quality. That is, image quality was broadly defined as the effectiveness by which an image can be used for its intended task. Under this definition, any assessment of image quality requires three components: (1) A well defined imaging task (e.g., detection of subtle lesions), (2) an “observer” to perform the task (e.g., a radiologists or a detection algorithm), and (3) a way to measure the observer’s performance in completing the task at hand (e.g., detection sensitivity/specificity).

First, this task-based image quality paradigm was implemented using a novel multi-sized phantom platform (with uniform background) developed specifically to assess modern CT systems (Mercury Phantom, v3.0, Duke University). A comprehensive evaluation was performed on a state-of-the-art CT system (SOMATOM Definition Force, Siemens Healthcare) in terms of noise, resolution, and detectability as a function of patient size, dose, tube energy (i.e., kVp), automatic exposure control, and reconstruction algorithm (i.e., Filtered Back-Projection– FPB vs Advanced Modeled Iterative Reconstruction– ADMIRE). A mathematical observer model (i.e., computer detection algorithm) was implemented and used as the basis of image quality comparisons. It was found that image quality increased with increasing dose and decreasing phantom size. The CT system exhibited nonlinear noise and resolution properties, especially at very low-doses, large phantom sizes, and for low-contrast objects. Objective image quality metrics generally increased with increasing dose and ADMIRE strength, and with decreasing phantom size. The ADMIRE algorithm could offer comparable image quality at reduced doses or improved image quality at the same dose (increase in detectability index by up to 163% depending on iterative strength). The use of automatic exposure control resulted in more consistent image quality with changing phantom size.

Based on those results, the dose reduction potential of ADMIRE was further assessed specifically for the task of detecting small (<=6 mm) low-contrast (<=20 HU) lesions. A new low-contrast detectability phantom (with uniform background) was designed and fabricated using a multi-material 3D printer. The phantom was imaged at multiple dose levels and images were reconstructed with FBP and ADMIRE. Human perception experiments were performed to measure the detection accuracy from FBP and ADMIRE images. It was found that ADMIRE had equivalent performance to FBP at 56% less dose.

Using the same image data as the previous study, a number of different mathematical observer models were implemented to assess which models would result in image quality metrics that best correlated with human detection performance. The models included naïve simple metrics of image quality such as contrast-to-noise ratio (CNR) and more sophisticated observer models such as the non-prewhitening matched filter observer model family and the channelized Hotelling observer model family. It was found that non-prewhitening matched filter observers and the channelized Hotelling observers both correlated strongly with human performance. Conversely, CNR was found to not correlate strongly with human performance, especially when comparing different reconstruction algorithms.

The uniform background phantoms used in the previous studies provided a good first-order approximation of image quality. However, due to their simplicity and due to the complexity of iterative reconstruction algorithms, it is possible that such phantoms are not fully adequate to assess the clinical impact of iterative algorithms because patient images obviously do not have smooth uniform backgrounds. To test this hypothesis, two textured phantoms (classified as gross texture and fine texture) and a uniform phantom of similar size were built and imaged on a SOMATOM Flash scanner (Siemens Healthcare). Images were reconstructed using FBP and a Sinogram Affirmed Iterative Reconstruction (SAFIRE). Using an image subtraction technique, quantum noise was measured in all images of each phantom. It was found that in FBP, the noise was independent of the background (textured vs uniform). However, for SAFIRE, noise increased by up to 44% in the textured phantoms compared to the uniform phantom. As a result, the noise reduction from SAFIRE was found to be up to 66% in the uniform phantom but as low as 29% in the textured phantoms. Based on this result, it clear that further investigation was needed into to understand the impact that background texture has on image quality when iterative reconstruction algorithms are used.

To further investigate this phenomenon with more realistic textures, two anthropomorphic textured phantoms were designed to mimic lung vasculature and fatty soft tissue texture. The phantoms (along with a corresponding uniform phantom) were fabricated with a multi-material 3D printer and imaged on the SOMATOM Flash scanner. Scans were repeated a total of 50 times in order to get ensemble statistics of the noise. A novel method of estimating the noise power spectrum (NPS) from irregularly shaped ROIs was developed. It was found that SAFIRE images had highly locally non-stationary noise patterns with pixels near edges having higher noise than pixels in more uniform regions. Compared to FBP, SAFIRE images had 60% less noise on average in uniform regions for edge pixels, noise was between 20% higher and 40% lower. The noise texture (i.e., NPS) was also highly dependent on the background texture for SAFIRE. Therefore, it was concluded that quantum noise properties in the uniform phantoms are not representative of those in patients for iterative reconstruction algorithms and texture should be considered when assessing image quality of iterative algorithms.

The move beyond just assessing noise properties in textured phantoms towards assessing detectability, a series of new phantoms were designed specifically to measure low-contrast detectability in the presence of background texture. The textures used were optimized to match the texture in the liver regions actual patient CT images using a genetic algorithm. The so called “Clustured Lumpy Background” texture synthesis framework was used to generate the modeled texture. Three textured phantoms and a corresponding uniform phantom were fabricated with a multi-material 3D printer and imaged on the SOMATOM Flash scanner. Images were reconstructed with FBP and SAFIRE and analyzed using a multi-slice channelized Hotelling observer to measure detectability and the dose reduction potential of SAFIRE based on the uniform and textured phantoms. It was found that at the same dose, the improvement in detectability from SAFIRE (compared to FBP) was higher when measured in a uniform phantom compared to textured phantoms.

The final trajectory of this project aimed at developing methods to mathematically model lesions, as a means to help assess image quality directly from patient images. The mathematical modeling framework is first presented. The models describe a lesion’s morphology in terms of size, shape, contrast, and edge profile as an analytical equation. The models can be voxelized and inserted into patient images to create so-called “hybrid” images. These hybrid images can then be used to assess detectability or estimability with the advantage that the ground truth of the lesion morphology and location is known exactly. Based on this framework, a series of liver lesions, lung nodules, and kidney stones were modeled based on images of real lesions. The lesion models were virtually inserted into patient images to create a database of hybrid images to go along with the original database of real lesion images. ROI images from each database were assessed by radiologists in a blinded fashion to determine the realism of the hybrid images. It was found that the radiologists could not readily distinguish between real and virtual lesion images (area under the ROC curve was 0.55). This study provided evidence that the proposed mathematical lesion modeling framework could produce reasonably realistic lesion images.

Based on that result, two studies were conducted which demonstrated the utility of the lesion models. The first study used the modeling framework as a measurement tool to determine how dose and reconstruction algorithm affected the quantitative analysis of liver lesions, lung nodules, and renal stones in terms of their size, shape, attenuation, edge profile, and texture features. The same database of real lesion images used in the previous study was used for this study. That database contained images of the same patient at 2 dose levels (50% and 100%) along with 3 reconstruction algorithms from a GE 750HD CT system (GE Healthcare). The algorithms in question were FBP, Adaptive Statistical Iterative Reconstruction (ASiR), and Model-Based Iterative Reconstruction (MBIR). A total of 23 quantitative features were extracted from the lesions under each condition. It was found that both dose and reconstruction algorithm had a statistically significant effect on the feature measurements. In particular, radiation dose affected five, three, and four of the 23 features (related to lesion size, conspicuity, and pixel-value distribution) for liver lesions, lung nodules, and renal stones, respectively. MBIR significantly affected 9, 11, and 15 of the 23 features (including size, attenuation, and texture features) for liver lesions, lung nodules, and renal stones, respectively. Lesion texture was not significantly affected by radiation dose.

The second study demonstrating the utility of the lesion modeling framework focused on assessing detectability of very low-contrast liver lesions in abdominal imaging. Specifically, detectability was assessed as a function of dose and reconstruction algorithm. As part of a parallel clinical trial, images from 21 patients were collected at 6 dose levels per patient on a SOMATOM Flash scanner. Subtle liver lesion models (contrast = -15 HU) were inserted into the raw projection data from the patient scans. The projections were then reconstructed with FBP and SAFIRE (strength 5). Also, lesion-less images were reconstructed. Noise, contrast, CNR, and detectability index of an observer model (non-prewhitening matched filter) were assessed. It was found that SAFIRE reduced noise by 52%, reduced contrast by 12%, increased CNR by 87%. and increased detectability index by 65% compared to FBP. Further, a 2AFC human perception experiment was performed to assess the dose reduction potential of SAFIRE, which was found to be 22% compared to the standard of care dose.

In conclusion, this dissertation provides to the scientific community a series of new methodologies, phantoms, analysis techniques, and modeling tools that can be used to rigorously assess image quality from modern CT systems. Specifically, methods to properly evaluate iterative reconstruction have been developed and are expected to aid in the safe clinical implementation of dose reduction technologies.