Future value based single assignment program representations and optimizations

An optimizing compiler internal representation fundamentally affects the clarity, efficiency and feasibility of optimization algorithms employed by the compiler. Static Single Assignment (SSA) as a state-of-the-art program representation has great advantages though still can be improved. This dissertation explores the domain of single assignment beyond SSA, and presents two novel program representations: Future Gated Single Assignment (FGSA) and Recursive Future Predicated Form (RFPF). Both FGSA and RFPF embed control flow and data flow information, enabling efficient traversal program information and thus leading to better and simpler optimizations. We introduce future value concept, the designing base of both FGSA and RFPF, which permits a consumer instruction to be encountered before the producer of its source operand(s) in a control flow setting. We show that FGSA is efficiently computable by using a series T1/T2/TR transformation, yielding an expected linear time algorithm for combining together the construction of the pruned single assignment form and live analysis for both reducible and irreducible graphs. As a result, the approach results in an average reduction of 7.7%, with a maximum of 67% in the number of gating functions compared to the pruned SSA form on the SPEC2000 benchmark suite. We present a solid and near optimal framework to perform inverse transformation from single assignment programs. We demonstrate the importance of unrestricted code motion and present RFPF. We develop algorithms which enable instruction movement in acyclic, as well as cyclic regions, and show the ease to perform optimizations such as Partial Redundancy Elimination on RFPF.

Semi-automatic segmentation of fetal cardiac cavities: progress towards an automated fetal echocardiogram

OBJECTIVE: To develop a novel application of a tool for semi-automatic volume segmentation and adapt it for analysis of fetal cardiac cavities and vessels from heart volume datasets. METHODS: We studied retrospectively virtual cardiac volume cycles obtained with spatiotemporal image correlation (STIC) from six fetuses with postnatally confirmed diagnoses: four with normal hearts between 19 and 29 completed gestational weeks, one with d-transposition of the great arteries and one with hypoplastic left heart syndrome. The volumes were analyzed offline using a commercially available segmentation algorithm designed for ovarian folliculometry. Using this software, individual 'cavities' in a static volume are selected and assigned individual colors in cross-sections and in 3D-rendered views, and their dimensions (diameters and volumes) can be calculated. RESULTS: Individual segments of fetal cardiac cavities could be separated, adjacent segments merged and the resulting electronic casts studied in their spatial context. Volume measurements could also be performed. Exemplary images and interactive videoclips showing the segmented digital casts were generated. CONCLUSION: The approach presented here is an important step towards an automated fetal volume echocardiogram. It has the potential both to help in obtaining a correct structural diagnosis, and to generate exemplary visual displays of cardiac anatomy in normal and structurally abnormal cases for consultation and teaching.

Interrelation of peri-operative morbidity and ASA class assignment in patients undergoing gynaecological surgery

OBJECTIVE: The aim of this study was to estimate intra- and post-operative risk using the American Society of Anaesthesiologists (ASA) classification which is an important predictor of an intervention and of the entire operating programme. STUDY DESIGN: In this retrospective study, 4435 consecutive patients undergoing elective and emergency surgery at the Gynaecological Clinic of the University Hospital of Zurich were included. The ASA classification for pre-operative risk assessment was determined by an anaesthesiologist after a thorough physical examination. We observed several pre-, intra- and post-operative parameters, such as age, body-mass-index, duration of anaesthesia, duration of surgery, blood loss, duration of post-operative stay, complicated post-operative course, morbidity and mortality. The investigation of different risk factors was achieved by a multiple linear regression model for log-transformed duration of hospitalisation. RESULTS: Age and obesity were responsible for a higher ASA classification. ASA grade correlates with the duration of anaesthesia and the duration of the surgery itself. There was a significant difference in blood loss between ASA grades I (113+/-195 ml) and III (222+/-470 ml) and between classes II (176+/-432 ml) and III. The duration of post-operative hospitalisation could also be correlated with ASA class. ASA class I=1.7+/-3.0 days, ASA class II=3.6+/-4.3 days, ASA class III=6.8+/-8.2 days, and ASA class IV=6.2+/-3.9 days. The mean post-operative in-hospital stay was 2.5+/-4.0 days without complications, and 8.7+/-6.7 days with post-operative complications. Multiple linear regression model showed that not only the ASA classification contained an important information for the duration of hospitalisation. Parameters such as age, class of diagnosis, post-operative complications, etc. also have an influence on the duration of hospitalisation. CONCLUSION: This study shows that the ASA classification can be used as a good and early available predictor for the planning of an intervention in gynaecological surgery. The ASA classification helps the surgeon to assess the peri-operative risk profile of which important information can be derived for the planning of the operation programme.

Automatic Food Intake Assessment Using Camera Phones

Obesity is becoming an epidemic phenomenon in most developed countries. The fundamental cause of obesity and overweight is an energy imbalance between calories consumed and calories expended. It is essential to monitor everyday food intake for obesity prevention and management. Existing dietary assessment methods usually require manually recording and recall of food types and portions. Accuracy of the results largely relies on many uncertain factors such as user's memory, food knowledge, and portion estimations. As a result, the accuracy is often compromised. Accurate and convenient dietary assessment methods are still blank and needed in both population and research societies. In this thesis, an automatic food intake assessment method using cameras, inertial measurement units (IMUs) on smart phones was developed to help people foster a healthy life style. With this method, users use their smart phones before and after a meal to capture images or videos around the meal. The smart phone will recognize food items and calculate the volume of the food consumed and provide the results to users. The technical objective is to explore the feasibility of image based food recognition and image based volume estimation. This thesis comprises five publications that address four specific goals of this work: (1) to develop a prototype system with existing methods to review the literature methods, find their drawbacks and explore the feasibility to develop novel methods; (2) based on the prototype system, to investigate new food classification methods to improve the recognition accuracy to a field application level; (3) to design indexing methods for large-scale image database to facilitate the development of new food image recognition and retrieval algorithms; (4) to develop novel convenient and accurate food volume estimation methods using only smart phones with cameras and IMUs. A prototype system was implemented to review existing methods. Image feature detector and descriptor were developed and a nearest neighbor classifier were implemented to classify food items. A reedit card marker method was introduced for metric scale 3D reconstruction and volume calculation. To increase recognition accuracy, novel multi-view food recognition algorithms were developed to recognize regular shape food items. To further increase the accuracy and make the algorithm applicable to arbitrary food items, new food features, new classifiers were designed. The efficiency of the algorithm was increased by means of developing novel image indexing method in large-scale image database. Finally, the volume calculation was enhanced through reducing the marker and introducing IMUs. Sensor fusion technique to combine measurements from cameras and IMUs were explored to infer the metric scale of the 3D model as well as reduce noises from these sensors.