Towards a real-time 3D object recognition pipeline on mobile GPGPU computing platforms using low-cost RGB-D sensors

In this project, we propose the implementation of a 3D object recognition system which will be optimized to operate under demanding time constraints. The system must be robust so that objects can be recognized properly in poor light conditions and cluttered scenes with significant levels of occlusion. An important requirement must be met: the system must exhibit a reasonable performance running on a low power consumption mobile GPU computing platform (NVIDIA Jetson TK1) so that it can be integrated in mobile robotics systems, ambient intelligence or ambient assisted living applications. The acquisition system is based on the use of color and depth (RGB-D) data streams provided by low-cost 3D sensors like Microsoft Kinect or PrimeSense Carmine. The range of algorithms and applications to be implemented and integrated will be quite broad, ranging from the acquisition, outlier removal or filtering of the input data and the segmentation or characterization of regions of interest in the scene to the very object recognition and pose estimation. Furthermore, in order to validate the proposed system, we will create a 3D object dataset. It will be composed by a set of 3D models, reconstructed from common household objects, as well as a handful of test scenes in which those objects appear. The scenes will be characterized by different levels of occlusion, diverse distances from the elements to the sensor and variations on the pose of the target objects. The creation of this dataset implies the additional development of 3D data acquisition and 3D object reconstruction applications. The resulting system has many possible applications, ranging from mobile robot navigation and semantic scene labeling to human-computer interaction (HCI) systems based on visual information.

Rare enlargement of the genial tubercles Enlargement of genial tubercles

Genial tubercles usually are small bony protuberances on the lingual aspect of the mandible symphysis. Conversely, this case shows 3D tomographic reconstruction images of genial tubercles as an oversized projection causing pain and discomfort to the patient.

Estudio sobre la extracción de puntos característicos en imágenes y sus aplicaciones

En aquest treball realitzem un estudi sobre la detecció y la descripció de punts característics, una tecnologia que permet extreure informació continguda en les imatges. Primerament presentem l'estat de l'art juntament amb una avaluació dels mètodes més rellevants. A continuació proposem els nous mètodes que hem creat de detecció i descripció, juntament amb l'algorisme òptim anomenat DART, el qual supera l'estat de l'art. Finalment mostrem algunes aplicacions on s'utilitzen els punts DART. Basant-se en l'aproximació de l'espai d'escales Gaussià, el detector proposat pot extreure punts de distint tamany invariants davant canvis en el punt de vista, la rotació i la iluminació. La reutilització de l'espai d'escales durant el procés de descripció, així com l'ús d'estructures simplificades i optimitzades, permeten realitzar tot el procediment en un temps computacional menor a l'obtingut fins al moment. Així s'aconsegueixen punts invariants i distingibles de forma ràpida, el qual permet la seva utilització en aplicacions com el seguiment d'objectes, la reconstrucció d'escenaris 3D i en motors de cerca visual.

Pericardial fat volume correlates with coronary vasomotion

Purpose: Recent studies showed that pericardial fat was independently correlated with the development of coronary artery disease (CAD). The mechanism remains unclear. We aimed at assessing a possible relationship between pericardial fat volume and endothelium-dependent coronary vasomotion, a surrogate of future cardiovascular events.Methods: Fifty healthy volunteers without known CAD or cardiovascular risk factors (CRF) were enrolled. They all underwent a dynamic Rb- 82 cardiac PET/CT to quantify myocardial blood flow (MBF) at rest, during MBF response to cold pressure test (CPT-MBF) and adenosine stress. Pericardial fat volume (PFV) was measured using a 3D volumetric CT method and common biological CRF (glucose and insulin levels, HOMA-IR, cholesterol, triglyceride, hs-CRP). Relationships between MBF response to CPT, PFV and other CRF were assessed using non-parametric Spearman correlation and multivariate regression analysis of variables with significant correlation on univariate analysis (Stata 11.0).Results: All of the 50 participants had normal MBF response to adenosine (2.7±0.6 mL/min/g; 95%CI: 2.6−2.9) and myocardial flow reserve (2.8±0.8; 95%CI: 2.6−3.0) excluding underlying CAD. Simple regression analysis revealed a significant correlation between absolute CPTMBF and triglyceride level (rho = −0.32, p = 0.024) fasting blood insulin (rho = −0.43, p = 0.0024), HOMA-IR (rho = −0.39, p = 0.007) and PFV (rho = −0.52, p = 0.0001). MBF response to adenosine was only correlated with PFV (rho = −0.32, p = 0.026). On multivariate regression analysis PFV emerged as the only significant predictor of MBF response to CPT (p = 0.002).Conclusion: PFV is significantly correlated with endothelium-dependent coronary vasomotion. High PF burden might negatively influence MBF response to CPT, as well as to adenosine stress, even in persons with normal hyperemic myocardial perfusion imaging, suggesting a link between PF and future cardiovascular events. While outside-to-inside adipokines secretion through the arterial wall has been described, our results might suggest an effect upon NO-dependent and -independent vasodilatation. Further studies are needed to elucidate this mechanism.

Organ volume measurements: comparison between MRI and autopsy findings in infants following sudden unexpected death.

OBJECTIVE: To assess the accuracy of a semiautomated 3D volume reconstruction method for organ volume measurement by postmortem MRI. METHODS: This prospective study was approved by the institutional review board and the infants' parents gave their consent. Postmortem MRI was performed in 16 infants (1 month to 1 year of age) at 1.5 T within 48 h of their sudden death. Virtual organ volumes were estimated using the Myrian software. Real volumes were recorded at autopsy by water displacement. The agreement between virtual and real volumes was quantified following the Bland and Altman's method. RESULTS: There was a good agreement between virtual and real volumes for brain (mean difference: -0.03% (-13.6 to +7.1)), liver (+8.3% (-9.6 to +26.2)) and lungs (+5.5% (-26.6 to +37.6)). For kidneys, spleen and thymus, the MRI/autopsy volume ratio was close to 1 (kidney: 0.87±0.1; spleen: 0.99±0.17; thymus: 0.94±0.25), but with a less good agreement. For heart, the MRI/real volume ratio was 1.29±0.76, possibly due to the presence of residual blood within the heart. The virtual volumes of adrenal glands were significantly underestimated (p=0.04), possibly due to their very small size during the first year of life. The percentage of interobserver and intraobserver variation was lower or equal to 10%, but for thymus (15.9% and 12.6%, respectively) and adrenal glands (69% and 25.9%). CONCLUSIONS: Virtual volumetry may provide significant information concerning the macroscopic features of the main organs and help pathologists in sampling organs that are more likely to yield histological findings.

Rigid body dynamics and Kalman filtering

X-ray computed log tomography has always been applied for qualitative reconstructions. In most cases, a series of consecutive slices of the timber are scanned to estimate the 3D image reconstruction of the entire log. However, the unexpected movement of the timber under study influences the quality of image reconstruction since the position and orientation of some scanned slices can be incorrectly estimated. In addition, the reconstruction time remains a significant challenge for practical applications. The present study investigates the possibility to employ modern physics engines for the problem of estimating the position of a moving rigid body and its scanned slices which are subject to X-ray computed tomography. The current work includes implementations of the extended Kalman filter and an algebraic reconstruction method for fan-bean computer tomography. In addition, modern techniques such as NVidia PhysX and CUDA are used in current study. As the result, it is numerically shown that it is possible to apply the extended Kalman filter together with a real-time physics engine, known as PhysX, in order to determine the position of a moving object. It is shown that the position of the rigid body can be determined based only on reconstructions of its slices. However, the simulation of the body movement sometimes is subject to an error during Kalman filter employment as PhysX is not always able to continue simulating the movement properly because of incorrect state estimation.

Une nouvelle méthode pour estimer la torsion géométrique en scoliose idiopathique de l’adolescent

La scoliose idiopathique de l’adolescent (SIA) est une déformation tridimensionnelle (3D) de la colonne vertébrale. Pour la plupart des patients atteints de SIA, aucun traitement chirurgical n’est nécessaire. Lorsque la déformation devient sévère, un traitement chirurgical visant à réduire la déformation est recommandé. Pour déterminer la sévérité de la SIA, l’imagerie la plus utilisée est une radiographie postéroantérieure (PA) ou antéro-postérieure (AP) du rachis. Plusieurs indices sont disponibles à partir de cette modalité d’imagerie afin de quantifier la déformation de la SIA, dont l’angle de Cobb. La conduite thérapeutique est généralement basée sur cet indice. Cependant, les indices disponibles à cette modalité d’imagerie sont de nature bidimensionnelle (2D). Celles-ci ne décrivent donc pas entièrement la déformation dans la SIA dû à sa nature tridimensionnelle (3D). Conséquemment, les classifications basées sur les indices 2D souffrent des mêmes limitations. Dans le but décrire la SIA en 3D, la torsion géométrique a été étudiée et proposée par Poncet et al. Celle-ci mesure la tendance d’une courbe tridimensionnelle à changer de direction. Cependant, la méthode proposée est susceptible aux erreurs de reconstructions 3D et elle est calculée localement au niveau vertébral. L’objectif de cette étude est d’évaluer une nouvelle méthode d’estimation de la torsion géométrique par l’approximation de longueurs d’arcs locaux et par paramétrisation de courbes dans la SIA. Une première étude visera à étudier la sensibilité de la nouvelle méthode présentée face aux erreurs de reconstructions 3D du rachis. Par la suite, deux études cliniques vont présenter la iv torsion géométrique comme indice global et viseront à démontrer l’existence de sous-groupes non-identifiés dans les classifications actuelles et que ceux-ci ont une pertinence clinique. La première étude a évalué la robustesse de la nouvelle méthode d’estimation de la torsion géométrique chez un groupe de patient atteint de la SIA. Elle a démontré que la nouvelle technique est robuste face aux erreurs de reconstructions 3D du rachis. La deuxième étude a évalué la torsion géométrique utilisant cette nouvelle méthode dans une cohorte de patient avec des déformations de type Lenke 1. Elle a démontré qu’il existe deux sous-groupes, une avec des valeurs de torsion élevées et l’autre avec des valeurs basses. Ces deux sous-groupes possèdent des différences statistiquement significatives, notamment au niveau du rachis lombaire avec le groupe de torsion élevée ayant des valeurs d’orientation des plans de déformation maximales (PMC) en thoraco-lombaire (TLL) plus élevées. La dernière étude a évalué les résultats chirurgicaux de patients ayant une déformation Lenke 1 sous-classifiées selon les valeurs de torsion préalablement. Cette étude a pu démontrer des différences au niveau du PMC au niveau thoraco-lombaire avec des valeurs plus élevées en postopératoire chez les patients ayant une haute torsion. Ces études présentent une nouvelle méthode d’estimation de la torsion géométrique et présentent cet indice quantitativement. Elles ont démontré l’existence de sous-groupes 3D basés sur cet indice ayant une pertinence clinique dans la SIA, qui n’étaient pas identifiés auparavant. Ce projet contribue dans la tendance actuelle vers le développement d’indices 3D et de classifications 3D pour la scoliose idiopathique de l’adolescent.

An approach to coded structured light to obtain three dimensional information

The human visual ability to perceive depth looks like a puzzle. We perceive three-dimensional spatial information quickly and efficiently by using the binocular stereopsis of our eyes and, what is mote important the learning of the most common objects which we achieved through living. Nowadays, modelling the behaviour of our brain is a fiction, that is why the huge problem of 3D perception and further, interpretation is split into a sequence of easier problems. A lot of research is involved in robot vision in order to obtain 3D information of the surrounded scene. Most of this research is based on modelling the stereopsis of humans by using two cameras as if they were two eyes. This method is known as stereo vision and has been widely studied in the past and is being studied at present, and a lot of work will be surely done in the future. This fact allows us to affirm that this topic is one of the most interesting ones in computer vision. The stereo vision principle is based on obtaining the three dimensional position of an object point from the position of its projective points in both camera image planes. However, before inferring 3D information, the mathematical models of both cameras have to be known. This step is known as camera calibration and is broadly describes in the thesis. Perhaps the most important problem in stereo vision is the determination of the pair of homologue points in the two images, known as the correspondence problem, and it is also one of the most difficult problems to be solved which is currently investigated by a lot of researchers. The epipolar geometry allows us to reduce the correspondence problem. An approach to the epipolar geometry is describes in the thesis. Nevertheless, it does not solve it at all as a lot of considerations have to be taken into account. As an example we have to consider points without correspondence due to a surface occlusion or simply due to a projection out of the camera scope. The interest of the thesis is focused on structured light which has been considered as one of the most frequently used techniques in order to reduce the problems related lo stereo vision. Structured light is based on the relationship between a projected light pattern its projection and an image sensor. The deformations between the pattern projected into the scene and the one captured by the camera, permits to obtain three dimensional information of the illuminated scene. This technique has been widely used in such applications as: 3D object reconstruction, robot navigation, quality control, and so on. Although the projection of regular patterns solve the problem of points without match, it does not solve the problem of multiple matching, which leads us to use hard computing algorithms in order to search the correct matches. In recent years, another structured light technique has increased in importance. This technique is based on the codification of the light projected on the scene in order to be used as a tool to obtain an unique match. Each token of light is imaged by the camera, we have to read the label (decode the pattern) in order to solve the correspondence problem. The advantages and disadvantages of stereo vision against structured light and a survey on coded structured light are related and discussed. The work carried out in the frame of this thesis has permitted to present a new coded structured light pattern which solves the correspondence problem uniquely and robust. Unique, as each token of light is coded by a different word which removes the problem of multiple matching. Robust, since the pattern has been coded using the position of each token of light with respect to both co-ordinate axis. Algorithms and experimental results are included in the thesis. The reader can see examples 3D measurement of static objects, and the more complicated measurement of moving objects. The technique can be used in both cases as the pattern is coded by a single projection shot. Then it can be used in several applications of robot vision. Our interest is focused on the mathematical study of the camera and pattern projector models. We are also interested in how these models can be obtained by calibration, and how they can be used to obtained three dimensional information from two correspondence points. Furthermore, we have studied structured light and coded structured light, and we have presented a new coded structured light pattern. However, in this thesis we started from the assumption that the correspondence points could be well-segmented from the captured image. Computer vision constitutes a huge problem and a lot of work is being done at all levels of human vision modelling, starting from a)image acquisition; b) further image enhancement, filtering and processing, c) image segmentation which involves thresholding, thinning, contour detection, texture and colour analysis, and so on. The interest of this thesis starts in the next step, usually known as depth perception or 3D measurement.

Aortic arch morphometry in living humans

Anatomical features of the aortic arch such as its steepness, the take-off angles and the distances between its supra-aortic branches can influence the feasibility and difficulty of interventional and/or surgical maneuvers. These anatomical characteristics were assessed by means of 3D multiplanar reconstruction of thoracic angio-computed tomography scans of 92 living patients (79 males, 13 females, mean age 69.4 ± 9.9 years) carried out for various indications (gross pathology of the thoracic aorta excluded). There was a significant variation of all measured parameters between the subjects - a standard aortic arch (i.e. with all measured parameters within 2 SD) does not seem to exist. There were no significant differences between genders but some of the parameters correlated significantly to age.

HIV-1 Nef interferes with T-lymphocyte circulation through confined environments in vivo

HIV-1 negative factor (Nef) elevates virus replication and contributes to immune evasion in vivo. As one of its established in vitro activities, Nef interferes with T-lymphocyte chemotaxis by reducing host cell actin dynamics. To explore Nef's influence on in vivo recirculation of T lymphocytes, we assessed lymph-node homing of Nef-expressing primary murine lymphocytes and found a drastic impairment in homing to peripheral lymph nodes. Intravital imaging and 3D immunofluorescence reconstruction of lymph nodes revealed that Nef potently impaired T-lymphocyte extravasation through high endothelial venules and reduced subsequent parenchymal motility. Ex vivo analyses of transendothelial migration revealed that Nef disrupted T-lymphocyte polarization and interfered with diapedesis and migration in the narrow subendothelial space. Consistently, Nef specifically affected T-lymphocyte motility modes used in dense environments that pose high physical barriers to migration. Mechanistically, inhibition of lymph node homing, subendothelial migration and cell polarization, but not diapedesis, depended on Nef's ability to inhibit host cell actin remodeling. Nef-mediated interference with in vivo recirculation of T lymphocytes may compromise T-cell help and thus represents an important mechanism for its function as a HIV pathogenicity factor.

Evaluation of magnetic resonance colonography at 3.0 Tesla regarding diagnostic accuracy and image quality

OBJECTIVES: To assess magnetic resonance (MR)-colonography (MRC) for detection of colorectal lesions using two different T1w three-dimensional (3D)-gradient-recalled echo (GRE)-sequences and integrated parallel data acquisition (iPAT) at a 3.0 Tesla MR-unit. MATERIALS AND METHODS: In this prospective study, 34 symptomatic patients underwent dark lumen MRC at a 3.0 Tesla unit before conventional colonoscopy (CC). After colon distension with tap water, 2 high-resolution T1w 3D-GRE [3-dimensional fast low angle shot (3D-FLASH), iPAT factor 2 and 3D-volumetric interpolated breathhold examination (VIBE), iPAT 3] sequences were acquired without and after bolus injection of gadolinium. Prospective evaluation of MRC was performed. Image quality of the different sequences was assessed qualitatively and quantitatively. The findings of the same day CC served as standard of reference. RESULTS: MRC identified all polyps >5 mm (16 of 16) in size and all carcinomas (4 of 4) correctly. Fifty percent of the small polyps 3D-FLASH and in 92% (376 of 408) for the VIBE. The 3D-FLASH sequence showed a 3-fold increase in signal-to-noise ratio (8 +/- 3.3 standard deviation (SD) in lesions without contrast enhancement (CE); 24.3 +/- 7.8 SD after CE). For the 3D-VIBE sequence, signal-to-noise ratio doubled in the detected lesions (147 +/- 54 SD without and 292 +/- 168 SD after CE). Although image quality was ranked lower in the VIBE, the image quality score of both sequences showed no statistical significant difference (chi > 0.6). CONCLUSIONS: MRC using 3D-GRE-sequences and iPAT is feasible at 3.0 T-systems. The high-resolution 3D-FLASH was slightly preferred over the 3D-VIBE because of better image quality, although both used sequences showed no statistical significant difference.

Laparoscopic computer-navigated ablation of liver metastases

Objective In order to benefit from the obvious advantages of minimally invasive liver surgery there is a need to develop high precision tools for intraoperative anatomical orientation, navigation and safety control. In a pilot study we adapted a newly developed system for computer-assisted liver surgery (CALS) in terms of accuracy and technical feasibility to the specific requirements of laparoscopy. Here, we present practical aspects related to laparoscopic computer assisted liver surgery (LCALS). Methods Our video relates to a patient presenting with 3 colorectal liver metastases in Seg. II, III and IVa who was selected in an appropriate oncological setting for LCALS using the CAScination system combined with 3D MEVIS reconstruction. After minimal laparoscopic mobilization of the liver, a 4- landmark registration method was applied to enable navigation. Placement of microwave needles was performed using the targeting module of the navigation system and correct needle positioning was confirmed by intraoperative sonography. Ablation of each lesion was carried out by application of microwave energy at 100 Watts for 1 minute. Results To acquire an accurate (less 0.5 cm) registration, 4 registration cycles were necessary. In total, seven minutes were required to accomplish precise registration. Successful ablation with complete response in all treated areas was assessed by intraoperative sonography and confirmed by postoperative CT scan. Conclusions This teaching video demonstrates the theoretical and practical key points of LCALS with a special emphasis on preoperative planning, intraoperative registration and accuracy testing by laparoscopic methodology. In contrast to mere ultrasound-guided ablation of liver lesions, LCALS offers a more dimensional targeting and higher safety control. This is currently also in routine use to treat vanishing lesions and other difficult to target focal lesions within the liver.

Evaluación del potencial fotovoltaico del Campus Sur de la Universidad Politécnica de Madrid

El presente proyecto engloba el estudio del potencial fotovoltaico del Campus Sur de la Universidad Politécnica de Madrid. Este estudio se divide en tres partes. En primer lugar, se calcula la productividad del campus. En segundo lugar, se diseña la disposición de los generadores fotovoltaicos en los terrenos disponibles. Como paso final, se realiza un estudio económico de distintos supuestos. Para realizar los cálculos de productividad, se utiliza IESPRO, un programa desarrollado en Matlab©, junto con una aplicación complementaria desarrollada en el mismo lenguaje. Gracias a estos dos software es posible obtener una estimación muy realista de la energía anual generada. El aprovechamiento del terreno se estudia con la ayuda del software libre Sketchup©. Gracias a esta aplicación, es posible la reconstrucción del Campus Sur en 3D. Dicha reconstrucción incluye edificaciones y vegetación, facilitando la distribución de los generadores fotovoltaicos en todas las zonas, pudiendo evitar zonas con sombreado o no aptas para la instalación, y maximizando la utilización del terreno. El conjunto de los análisis anteriores permiten determinar el rendimiento energético del Campus Sur en sus distintas configuraciones, es decir, únicamente instalando generadores fotovoltaicos en las azoteas de los edificios, o la instalación en todo el terreno disponible, el cual incluye las azoteas y los descampados. Este rendimiento energético, comparado con el consumo anual de todo el campus, permite estimar el coste financiero de llevar a cabo la instalación y su rentabilidad, todo ello detallado en el estudio económico. El estudio económico se basa en dos supuestos, el primero de ellos, únicamente tiene en cuenta la instalación en las azoteas de los edificios. El segundo estudio, incluye los descampados y las azoteas. Con estos dos estudios se puede verificar la viabilidad del proyecto, facilitando datos concretos sobre las ventajas de cada uno de ellos. ABSTRACT. The aim of this work is to study the photovoltaic potential in the South Campus of the Polytechnic University of Madrid. The work has been divided into three parts. The first one is focused on the calculus of the solar harvesting productivity of the South Campus. The second part is centered in the development of the complete photovoltaic system layout design, taking into account the available placement. In the third part, an economic study considering several different scenarios is carried out. In order to calculate the solar productivity, the MATLAB based software tool IESPRO together with a complementary application developed in MATLAB as well, have been used. These programs allow to obtain an accurate estimation of the generated annual energy. The land use is studied with the help of free software SketchUp. With this application, it is possible to rebuild the South Campus in 3D. This reconstruction includes: buildings and vegetation, facilitating the distribution of photovoltaic generators in all areas, to avoid shaded or unsuitable areas for the installation, and maximizing land use. All the above analysis allow determining the energy efficiency of the South Campus for two different configurations, i.e., installing solar photovoltaic arrays only on the roofs of the buildings, or installing solar photovoltaic arrays throughout the land available, including vacant lots and rooftops. The facilities final cost and the cost effectiveness are estimated by comparing the energy efficiency with the South Campus total consumption. This study is based on two different scenarios: the first one considers the solar arrays installation in the buildings roofs, and the second one includes in the layout the vacant lots and rooftops. These studies allow verifying the feasibility of the project, and provide specific information related to the advantages and drawbacks of each scenario.

Radio propagation modeling and measurements for ZigBee based indoor wireless sensor networks

The deployment of nodes in Wireless Sensor Networks (WSNs) arises as one of the biggest challenges of this field, which involves in distributing a large number of embedded systems to fulfill a specific application. The connectivity of WSNs is difficult to estimate due to the irregularity of the physical environment and affects the WSN designers? decision on deploying sensor nodes. Therefore, in this paper, a new method is proposed to enhance the efficiency and accuracy on ZigBee propagation simulation in indoor environments. The method consists of two steps: automatic 3D indoor reconstruction and 3D ray-tracing based radio simulation. The automatic 3D indoor reconstruction employs unattended image classification algorithm and image vectorization algorithm to build the environment database accurately, which also significantly reduces time and efforts spent on non-radio propagation issue. The 3D ray tracing is developed by using kd-tree space division algorithm and a modified polar sweep algorithm, which accelerates the searching of rays over the entire space. Signal propagation model is proposed for the ray tracing engine by considering both the materials of obstacles and the impact of positions along the ray path of radio. Three different WSN deployments are realized in the indoor environment of an office and the results are verified to be accurate. Experimental results also indicate that the proposed method is efficient in pre-simulation strategy and 3D ray searching scheme and is suitable for different indoor environments.

A novel methodology for planning reliable wireless sensor networks

Wireless sensor networks (WSNs) have shown their potentials in various applications, which bring a lot of benefits to users from both research and industrial areas. For many setups, it is envisioned thatWSNs will consist of tens to hundreds of nodes that operate on small batteries. However due to the diversity of the deployed environments and resource constraints on radio communication, sensing ability and energy supply, it is a very challenging issue to plan optimized WSN topology and predict its performance before real deployment. During the network planning phase, the connectivity, coverage, cost, network longevity and service quality should all be considered. Therefore it requires designers coping with comprehensive and interdisciplinary knowledge, including networking, radio engineering, embedded system and so on, in order to efficiently construct a reliable WSN for any specific types of environment. Nowadays there is still a lack of the analysis and experiences to guide WSN designers to efficiently construct WSN topology successfully without many trials. Therefore, simulation is a feasible approach to the quantitative analysis of the performance of wireless sensor networks. However the existing planning algorithms and tools, to some extent, have serious limitations to practically design reliable WSN topology: Only a few of them tackle the 3D deployment issue, and an overwhelming number of works are proposed to place devices in 2D scheme. Without considering the full dimension, the impacts of environment to the performance of WSN are not completely studied, thus the values of evaluated metrics such as connectivity and sensing coverage are not sufficiently accurate to make proper decision. Even fewer planning methods model the sensing coverage and radio propagation by considering the realistic scenario where obstacles exist. Radio signals propagate with multi-path phenomenon in the real world, in which direct paths, reflected paths and diffracted paths contribute to the received signal strength. Besides, obstacles between the path of sensor and objects might block the sensing signals, thus create coverage hole in the application. None of the existing planning algorithms model the network longevity and packet delivery capability properly and practically. They often employ unilateral and unrealistic formulations. The optimization targets are often one-sided in the current works. Without comprehensive evaluation on the important metrics, the performance of planned WSNs can not be reliable and entirely optimized. Modeling of environment is usually time consuming and the cost is very high, while none of the current works figure out any method to model the 3D deployment environment efficiently and accurately. Therefore many researchers are trapped by this issue, and their algorithms can only be evaluated in the same scenario, without the possibility to test the robustness and feasibility for implementations in different environments. In this thesis, we propose a novel planning methodology and an intelligent WSN planning tool to assist WSN designers efficiently planning reliable WSNs. First of all, a new method is proposed to efficiently and automatically model the 3D indoor and outdoor environments. To the best of our knowledge, this is the first time that the advantages of image understanding algorithm are applied to automatically reconstruct 3D outdoor and indoor scenarios for signal propagation and network planning purpose. The experimental results indicate that the proposed methodology is able to accurately recognize different objects from the satellite images of the outdoor target regions and from the scanned floor plan of indoor area. Its mechanism offers users a flexibility to reconstruct different types of environment without any human interaction. Thereby it significantly reduces human efforts, cost and time spent on reconstructing a 3D geographic database and allows WSN designers concentrating on the planning issues. Secondly, an efficient ray-tracing engine is developed to accurately and practically model the radio propagation and sensing signal on the constructed 3D map. The engine contributes on efficiency and accuracy to the estimated results. By using image processing concepts, including the kd-tree space division algorithm and modified polar sweep algorithm, the rays are traced efficiently without detecting all the primitives in the scene. The radio propagation model iv is proposed, which emphasizes not only the materials of obstacles but also their locations along the signal path. The sensing signal of sensor nodes, which is sensitive to the obstacles, is benefit from the ray-tracing algorithm via obstacle detection. The performance of this modelling method is robust and accurate compared with conventional methods, and experimental results imply that this methodology is suitable for both outdoor urban scenes and indoor environments. Moreover, it can be applied to either GSM communication or ZigBee protocol by varying frequency parameter of the radio propagation model. Thirdly, WSN planning method is proposed to tackle the above mentioned challenges and efficiently deploy reliable WSNs. More metrics (connectivity, coverage, cost, lifetime, packet latency and packet drop rate) are modeled more practically compared with other works. Especially 3D ray tracing method is used to model the radio link and sensing signal which are sensitive to the obstruction of obstacles; network routing is constructed by using AODV protocol; the network longevity, packet delay and packet drop rate are obtained via simulating practical events in WSNet simulator, which to the best of our knowledge, is the first time that network simulator is involved in a planning algorithm. Moreover, a multi-objective optimization algorithm is developed to cater for the characteristics of WSNs. The capability of providing multiple optimized solutions simultaneously allows users making their own decisions accordingly, and the results are more comprehensively optimized compared with other state-of-the-art algorithms. iMOST is developed by integrating the introduced algorithms, to assist WSN designers efficiently planning reliable WSNs for different configurations. The abbreviated name iMOST stands for an Intelligent Multi-objective Optimization Sensor network planning Tool. iMOST contributes on: (1) Convenient operation with a user-friendly vision system; (2) Efficient and automatic 3D database reconstruction and fast 3D objects design for both indoor and outdoor environments; (3) It provides multiple multi-objective optimized 3D deployment solutions and allows users to configure the network properties, hence it can adapt to various WSN applications; (4) Deployment solutions in the 3D space and the corresponding evaluated performance are visually presented to users; and (5) The Node Placement Module of iMOST is available online as well as the source code of the other two rebuilt heuristics. Therefore WSN designers will be benefit from v this tool on efficiently constructing environment database, practically and efficiently planning reliable WSNs for both outdoor and indoor applications. With the open source codes, they are also able to compare their developed algorithms with ours to contribute to this academic field. Finally, solid real results are obtained for both indoor and outdoor WSN planning. Deployments have been realized for both indoor and outdoor environments based on the provided planning solutions. The measured results coincide well with the estimated results. The proposed planning algorithm is adaptable according to the WSN designer’s desirability and configuration, and it offers flexibility to plan small and large scale, indoor and outdoor 3D deployments. The thesis is organized in 7 chapters. In Chapter 1, WSN applications and motivations of this work are introduced, the state-of-the-art planning algorithms and tools are reviewed, challenges are stated out and the proposed methodology is briefly introduced. In Chapter 2, the proposed 3D environment reconstruction methodology is introduced and its performance is evaluated for both outdoor and indoor environment. The developed ray-tracing engine and proposed radio propagation modelling method are described in details in Chapter 3, their performances are evaluated in terms of computation efficiency and accuracy. Chapter 4 presents the modelling of important metrics of WSNs and the proposed multi-objective optimization planning algorithm, the performance is compared with the other state-of-the-art planning algorithms. The intelligent WSN planning tool iMOST is described in Chapter 5. RealWSN deployments are prosecuted based on the planned solutions for both indoor and outdoor scenarios, important data are measured and results are analysed in Chapter 6. Chapter 7 concludes the thesis and discusses about future works. vi Resumen en Castellano Las redes de sensores inalámbricas (en inglés Wireless Sensor Networks, WSNs) han demostrado su potencial en diversas aplicaciones que aportan una gran cantidad de beneficios para el campo de la investigación y de la industria. Para muchas configuraciones se prevé que las WSNs consistirán en decenas o cientos de nodos que funcionarán con baterías pequeñas. Sin embargo, debido a la diversidad de los ambientes para desplegar las redes y a las limitaciones de recursos en materia de comunicación de radio, capacidad de detección y suministro de energía, la planificación de la topología de la red y la predicción de su rendimiento es un tema muy difícil de tratar antes de la implementación real. Durante la fase de planificación del despliegue de la red se deben considerar aspectos como la conectividad, la cobertura, el coste, la longevidad de la red y la calidad del servicio. Por lo tanto, requiere de diseñadores con un amplio e interdisciplinario nivel de conocimiento que incluye la creación de redes, la ingeniería de radio y los sistemas embebidos entre otros, con el fin de construir de manera eficiente una WSN confiable para cualquier tipo de entorno. Hoy en día todavía hay una falta de análisis y experiencias que orienten a los diseñadores de WSN para construir las topologías WSN de manera eficiente sin realizar muchas pruebas. Por lo tanto, la simulación es un enfoque viable para el análisis cuantitativo del rendimiento de las redes de sensores inalámbricos. Sin embargo, los algoritmos y herramientas de planificación existentes tienen, en cierta medida, serias limitaciones para diseñar en la práctica una topología fiable de WSN: Sólo unos pocos abordan la cuestión del despliegue 3D mientras que existe una gran cantidad de trabajos que colocan los dispositivos en 2D. Si no se analiza la dimensión completa (3D), los efectos del entorno en el desempeño de WSN no se estudian por completo, por lo que los valores de los parámetros evaluados, como la conectividad y la cobertura de detección, no son lo suficientemente precisos para tomar la decisión correcta. Aún en menor medida los métodos de planificación modelan la cobertura de los sensores y la propagación de la señal de radio teniendo en cuenta un escenario realista donde existan obstáculos. Las señales de radio en el mundo real siguen una propagación multicamino, en la que los caminos directos, los caminos reflejados y los caminos difractados contribuyen a la intensidad de la señal recibida. Además, los obstáculos entre el recorrido del sensor y los objetos pueden bloquear las señales de detección y por lo tanto crear áreas sin cobertura en la aplicación. Ninguno de los algoritmos de planificación existentes modelan el tiempo de vida de la red y la capacidad de entrega de paquetes correctamente y prácticamente. A menudo se emplean formulaciones unilaterales y poco realistas. Los objetivos de optimización son a menudo tratados unilateralmente en los trabajos actuales. Sin una evaluación exhaustiva de los parámetros importantes, el rendimiento previsto de las redes inalámbricas de sensores no puede ser fiable y totalmente optimizado. Por lo general, el modelado del entorno conlleva mucho tiempo y tiene un coste muy alto, pero ninguno de los trabajos actuales propone algún método para modelar el entorno de despliegue 3D con eficiencia y precisión. Por lo tanto, muchos investigadores están limitados por este problema y sus algoritmos sólo se pueden evaluar en el mismo escenario, sin la posibilidad de probar la solidez y viabilidad para las implementaciones en diferentes entornos. En esta tesis, se propone una nueva metodología de planificación así como una herramienta inteligente de planificación de redes de sensores inalámbricas para ayudar a los diseñadores a planificar WSNs fiables de una manera eficiente. En primer lugar, se propone un nuevo método para modelar demanera eficiente y automática los ambientes interiores y exteriores en 3D. Según nuestros conocimientos hasta la fecha, esta es la primera vez que las ventajas del algoritmo de _image understanding_se aplican para reconstruir automáticamente los escenarios exteriores e interiores en 3D para analizar la propagación de la señal y viii la planificación de la red. Los resultados experimentales indican que la metodología propuesta es capaz de reconocer con precisión los diferentes objetos presentes en las imágenes satelitales de las regiones objetivo en el exterior y de la planta escaneada en el interior. Su mecanismo ofrece a los usuarios la flexibilidad para reconstruir los diferentes tipos de entornos sin ninguna interacción humana. De este modo se reduce considerablemente el esfuerzo humano, el coste y el tiempo invertido en la reconstrucción de una base de datos geográfica con información 3D, permitiendo así que los diseñadores se concentren en los temas de planificación. En segundo lugar, se ha desarrollado un motor de trazado de rayos (en inglés ray tracing) eficiente para modelar con precisión la propagación de la señal de radio y la señal de los sensores en el mapa 3D construido. El motor contribuye a la eficiencia y la precisión de los resultados estimados. Mediante el uso de los conceptos de procesamiento de imágenes, incluyendo el algoritmo del árbol kd para la división del espacio y el algoritmo _polar sweep_modificado, los rayos se trazan de manera eficiente sin la detección de todas las primitivas en la escena. El modelo de propagación de radio que se propone no sólo considera los materiales de los obstáculos, sino también su ubicación a lo largo de la ruta de señal. La señal de los sensores de los nodos, que es sensible a los obstáculos, se ve beneficiada por la detección de objetos llevada a cabo por el algoritmo de trazado de rayos. El rendimiento de este método de modelado es robusto y preciso en comparación con los métodos convencionales, y los resultados experimentales indican que esta metodología es adecuada tanto para escenas urbanas al aire libre como para ambientes interiores. Por otra parte, se puede aplicar a cualquier comunicación GSM o protocolo ZigBee mediante la variación de la frecuencia del modelo de propagación de radio. En tercer lugar, se propone un método de planificación de WSNs para hacer frente a los desafíos mencionados anteriormente y desplegar redes de sensores fiables de manera eficiente. Se modelan más parámetros (conectividad, cobertura, coste, tiempo de vida, la latencia de paquetes y tasa de caída de paquetes) en comparación con otros trabajos. Especialmente el método de trazado de rayos 3D se utiliza para modelar el enlace de radio y señal de los sensores que son sensibles a la obstrucción de obstáculos; el enrutamiento de la red se construye utilizando el protocolo AODV; la longevidad de la red, retardo de paquetes ix y tasa de abandono de paquetes se obtienen a través de la simulación de eventos prácticos en el simulador WSNet, y según nuestros conocimientos hasta la fecha, es la primera vez que simulador de red está implicado en un algoritmo de planificación. Por otra parte, se ha desarrollado un algoritmo de optimización multi-objetivo para satisfacer las características de las redes inalámbricas de sensores. La capacidad de proporcionar múltiples soluciones optimizadas de forma simultánea permite a los usuarios tomar sus propias decisiones en consecuencia, obteniendo mejores resultados en comparación con otros algoritmos del estado del arte. iMOST se desarrolla mediante la integración de los algoritmos presentados, para ayudar de forma eficiente a los diseñadores en la planificación de WSNs fiables para diferentes configuraciones. El nombre abreviado iMOST (Intelligent Multi-objective Optimization Sensor network planning Tool) representa una herramienta inteligente de planificación de redes de sensores con optimización multi-objetivo. iMOST contribuye en: (1) Operación conveniente con una interfaz de fácil uso, (2) Reconstrucción eficiente y automática de una base de datos con información 3D y diseño rápido de objetos 3D para ambientes interiores y exteriores, (3) Proporciona varias soluciones de despliegue optimizadas para los multi-objetivo en 3D y permite a los usuarios configurar las propiedades de red, por lo que puede adaptarse a diversas aplicaciones de WSN, (4) las soluciones de implementación en el espacio 3D y el correspondiente rendimiento evaluado se presentan visualmente a los usuarios, y (5) El _Node Placement Module_de iMOST está disponible en línea, así como el código fuente de las otras dos heurísticas de planificación. Por lo tanto los diseñadores WSN se beneficiarán de esta herramienta para la construcción eficiente de la base de datos con información del entorno, la planificación práctica y eficiente de WSNs fiables tanto para aplicaciones interiores y exteriores. Con los códigos fuente abiertos, son capaces de comparar sus algoritmos desarrollados con los nuestros para contribuir a este campo académico. Por último, se obtienen resultados reales sólidos tanto para la planificación de WSN en interiores y exteriores. Los despliegues se han realizado tanto para ambientes de interior y como para ambientes de exterior utilizando las soluciones de planificación propuestas. Los resultados medidos coinciden en gran medida con los resultados estimados. El algoritmo de planificación x propuesto se adapta convenientemente al deiseño de redes de sensores inalámbricas, y ofrece flexibilidad para planificar los despliegues 3D a pequeña y gran escala tanto en interiores como en exteriores. La tesis se estructura en 7 capítulos. En el Capítulo 1, se presentan las aplicaciones de WSN y motivaciones de este trabajo, se revisan los algoritmos y herramientas de planificación del estado del arte, se presentan los retos y se describe brevemente la metodología propuesta. En el Capítulo 2, se presenta la metodología de reconstrucción de entornos 3D propuesta y su rendimiento es evaluado tanto para espacios exteriores como para espacios interiores. El motor de trazado de rayos desarrollado y el método de modelado de propagación de radio propuesto se describen en detalle en el Capítulo 3, evaluándose en términos de eficiencia computacional y precisión. En el Capítulo 4 se presenta el modelado de los parámetros importantes de las WSNs y el algoritmo de planificación de optimización multi-objetivo propuesto, el rendimiento se compara con los otros algoritmos de planificación descritos en el estado del arte. La herramienta inteligente de planificación de redes de sensores inalámbricas, iMOST, se describe en el Capítulo 5. En el Capítulo 6 se llevan a cabo despliegues reales de acuerdo a las soluciones previstas para los escenarios interiores y exteriores, se miden los datos importantes y se analizan los resultados. En el Capítulo 7 se concluye la tesis y se discute acerca de los trabajos futuros.