3D block-based medial axis transform and chessboard distance transform based on dominance

Traditionally, the block-based medial axis transform (BB-MAT) and the chessboard distance transform (CDT) were usually viewed as two completely different image computation problems, especially for three dimensional (3D) space. In fact, there exist some equivalent properties between them. The relationship between both of them is first derived and proved in this paper. One of the significant properties is that CDT for 3D binary image V is equal to BB-MAT for image V' where it denotes the inverse image of V. In a parallel algorithm, a cost is defined as the product of the time complexity and the number of processors used. The main contribution of this work is to reduce the costs of 3D BB-MAT and 3D CDT problems proposed by Wang [65]. Based on the reverse-dominance technique which is redefined from dominance concept, we achieve the computation of the 3D CDT problem by implementing the 3D BB-MAT algorithm first. For a 3D binary image of size N³, our parallel algorithm can be run in O(logN) time using N³ processors on the concurrent read exclusive write (CREW) parallel random access machine (PRAM) model to solve both 3D BB-MAT and 3D CDT problems, respectively. The presented results for the cost are reduced in comparison with those of Wang's. To the best of our knowledge, this work is the lowest costs for the 3D BB-MAT and 3D CDT algorithms known. In parallel algorithms, the running time can be divided into computation time and communication time. The experimental results of the running, communication and computation times for the different problem sizes are implemented in an HP Superdome with SMP/CC-NUMA (symmetric multiprocessor/cache coherent non-uniform memory access) architecture. We conclude that the parallel computer (i.e., SMP/CC-NUMA architecture or cluster system) is more suitable for solving problems with a large amount of input size.     

Expert system for problem solving in distance university education: The successful case of the subject “operations management”

Acquiring the skills needed to solve certain types of problems is one of the main challenges of distance university education, demanding extra motivation from students to tackle it. New technology should be one of our great allies in addressing these problems. This article proposes an expert system with a web‐based problem‐solving simulator for a multidevice environment in order to allow students to access an unlimited number of problems with their corresponding solutions, immediately, anytime and anywhere. The types of problems that can be used are those based on quantitative methods with a fixed methodology to be followed. A successful case study was carried out for the subject Operations Management at the Distance University of Madrid (UDIMA), with three different problem simulators having been developed. The results were very satisfactory compared with previous academic years in terms of motivation. A decrease in students that did not sit the final examination was observed, as was an increase in the number of visits to the Moodle classroom. Students also responded positively in their assessments of the initiative.     

基于欧氏距离变换的肺部粘连肿瘤分割算法

以肺部CT图像为研究对象,针对肺部粘连肿瘤图片本身的特点,提出了一种基于边缘跟踪的二维欧氏距离变换算法.从目标区域的最外层边界开始,自外向内对目标区域进行边缘跟踪、腐蚀,直到肿瘤区粘连部分与肺部边界分离.算法能够计算精确的欧氏距离.通过实验分割出的肿瘤和放射科医生手工勾画的肿瘤轮廓对比,5幅病例图像重叠率达到了75%左右,实验结果表明该方法对于中晚期肺部粘连肿瘤的分割有一定的效果.     

Anti-aliased Euclidean distance transform

We present a modified distance measure for use with distance transforms of anti-aliased, area sampled grayscale images of arbitrary binary contours. The modified measure can be used in any vector-propagation Euclidean distance transform. Our test implementation in the traditional SSED8 algorithm shows a considerable improvement in accuracy and homogeneity of the distance field compared to a traditional binary image transform. At the expense of a 10× slowdown for a particular image resolution, we achieve an accuracy comparable to a binary transform on a supersampled image with 16 × 16 higher resolution, which would require 256 times more computations and memory.     

A double layer method for constructing signed distance fields from triangle meshes

A new algorithm is proposed for constructing signed distance fields (SDF) from triangle meshes. In our approach, both the internal and external distance fields for the triangle mesh are computed first. Then the desired SDF is computed directly from these two distance fields. As only points are used to generate the distance fields, some complicated operations, such as the computation of the distance from a point to a triangle, are avoided. Our algorithm is in a very simple form and is straightforward to parallelize. Actually, we have implemented it by use of the OpenCL API and a CPU-to-GPU speedup ratio of 10–40 is obtained. Further, this method is validated by our numerical results.     

Visualizing “typical” and “exotic” Internet traffic data

The threat of cyber attacks motivates the need to monitor Internet traffic data for potentially abnormal behavior. Due to the enormous volumes of such data, statistical process monitoring tools, such as those traditionally used on data in the product manufacturing arena, are inadequate. “Exotic” data may indicate a potential attack; detecting such data requires a characterization of “typical” data. We devise some new graphical displays, including a “skyline plot,” that permit ready visual identification of unusual Internet traffic patterns in “streaming” data, and use appropriate statistical measures to help identify potential cyberattacks. These methods are illustrated on a moderate-sized data set (135,605 records) collected at George Mason University.     

The depth of monotone Boolean functions with multi input “AND” and “OR” gates

The problem of maximum depth of monotone Boolean functions is investigated when k-input AND and OR gates are used for realisation.     

Food safety inspection using “from presence to classification” object-detection model

With multiresolution decomposition and forest representation of wavelet transforms, we implemented a “from presence to classification” object-detection model. Three aspects of this model are studied. First, the presence of an object is quickly detected with fewer data manipulations at the coarsest resolution; secondly, object classification with high accuracy is fulfilled at the full resolution; and thirdly, the propagation in the coarse-to-fine process is studied in terms of coefficient propagation within a coefficient tree. We applied this model to internal deboned poultry inspection. As soon as the presence of a hazardous object was detected at a coarse resolution, a signal was actuated to reject the chicken fillet containing foreign inclusions before packing. Only with small foreign inclusions did we need to resort to finer resolution analysis.     

Weighted distance transforms generalized to modules and their computation on point lattices

This paper presents the generalization of weighted distances to modules and their computation through the chamfer algorithm on general point lattices. The first part is dedicated to formalization of definitions and properties (distance, metric, norm) of weighted distances on modules. It resumes tools found in literature to express the weighted distance of any point of a module and to compute optimal weights in the general case to get rotation invariant distances. The second part of this paper proves that, for any point lattice, the sequential two-scan chamfer algorithm produces correct distance maps. Finally, the definitions and computation of weighted distances are applied to the face-centered cubic (FCC) and body-centered cubic (BCC) grids.     

“Paraprogramming” manufacturing information systems

Computer integrated manufacturing (CIM) is creating unexpected problems for a growing number of manufacturing companies. Manufacturers are finding it especially difficult to attract programmers who are both willing and able to develop the highly complex software that integrates existing accounting, sales, production, engineering, and quality control information subsystems. Consequently, many companies abdicate their responsibility for manufacturing information systems and seek third party support ranging from consulting assistance to a total takeover of the company's information resources and operations. Companies that “give away” their internal information system capabilities to third parties will ultimately lose control of their enterprise information, a danger to be avoided. Off-the-shelf software for desktop computers has become sufficiently powerful to help solve a major portion of this serious problem. We hypothesize that manufacturing engineers (and others) can be trained to use packaged software to leverage their company's systems programming capabilities. In effect they would become “paraprogrammers” who would help design, develop, and maintain manufacturing information systems. This new type of professional would not require a computer science or similar educational background, but could be trained to satisfy many specialized programming needs in a manner similar to how paramedics and paralegals are trained and used in the medical and legal professions, respectively. This paper reports on the early stages of research to determine whether or not product design engineers can use a desktop relational database management system and its various command languages to develop a master bill of material information system (BOMIS). The purpose of the research is to evaluate the amount of programming complexity reduction and increased operational effectiveness that can be achieved through paraprogramming by manufacturing engineers.     

The “burning ship” and its quasi-Julia sets

By manipulating the imaginary part of the complex-analytic quadratic equation, we obtain, by iteration, a set that we call the “burning ship” because of its appearance. It is an analogue to the Mandelbrot set (M-set). Its nonanalytic “quasi”-Julia sets yield surprizing graphical shapes.     

基于GPU的3D距离变换*

距离变换在图像处理中有着非常广泛的应用。由于3D图像数据的复杂性,传统基于CPU的3D距离变换效率较低。为此,研究了将3D图像数据有效地组织到纹理中存储的方法,设计并实现了基于GPU的3D距离变换并行算法。实验结果表明,相对基于CPU的算法,该方法具有非常高的加速比。