Shape recognition using fractal geometry

Within this paper fractal transformations are presented as a powerful new shape recognition technique. The motivation behind using fractal transformations is to develop a high speed shape recognition technique which will be scale invariant. A review is given of the most popular existing shape recognition techniques. There then follows a full mathematical analysis of the new technique together with a proof of the authors Fractal Invariance Theorem, the new theorem at the centre of the recognition technique. Through the mathematical analysis it becomes apparent that the fractal recognition technique possesses the remarkable property that it is able to distinguish between similar objects. Details are then given of the practical implementation of the technique together with an algorithm for making the technique rotationally invariant. The technique is then applied to a selection of real world objects and a comparison made with the popular moment invariants technique. This shows that the fractal technique is faster than the technique of moment invariants, and also requires less initial information to be effective. Finally conclusions are drawn and further work detailed.     

Authenticating Pollock paintings using fractal geometry

Jackson Pollock’s paintings are currently valued up to US$75 M, triggering discussions that attributation procedures featuring subjective visual assessments should be complimented by quantitative scientific procedures. We present a fractal analysis of Pollock’s patterns and discuss its potential for authenticity research.     

Texture description and segmentation through fractal geometry

Fractal geometry is receiving increased attention as a model for natural phenomena. In this paper we first present a new method for estimating the fractal dimension from image surfaces and show that it performs better at describing and segmenting generated fractal sets. Since the fractal dimension alone is not sufficient to characterize natural textures, we define a new class of texture measures based on the concept of lacunarity and use them, together with the fractal dimension, to describe and segment natural texture images.     

Computational geometry in a curved world

We extend the results of straight-edged computational geometry into the curved world by defining a pair of new geometric objects, thesplinegon and thesplinehedron, as curved generalizations of the polygon and polyhedron. We identify three distinct techniques for extending polygon algorithms to splinegons: the carrier polygon approach, the bounding polygon approach, and the direct approach. By these methods, large groups of algorithms for polygons can be extended as a class to encompass these new objects. In general, if the original polygon algorithm has time complexityO(f(n)), the comparable splinegon algorithm has time complexity at worstO(Kf(n)) whereK represents a constant number of calls to members of a set of primitive procedures on individual curved edges. These techniques also apply to splinehedra. In addition to presenting the general methods, we state and prove a series of specific theorems. Problem areas include convex hull computation, diameter computation, intersection detection and computation, kernel computation, monotonicity testing, and monotone decomposition, among others.     

Computational algebraic geometry of projective configurations

This article deals with algorithmic and structural aspects related to the computer-aided study of incidence configurations in plane projective geometry. We describe invariant-theoretic algorithms and complexity results for computing the realization space and deciding the coordinatizability of configurations. A practical procedure for automated theorem proving in projective geometry is obtained as a special case. We use the final polynomial technique of Bokowski and Whiteley for encoding the resulting proofs, and we apply Buch-berger's Gröbner basis method for computing minimum degree final polynomials and final syzygies, thus attaining the bounds in the recent effective versions of Hubert's Nullstellen-satz.     

Computational geometry in a curved world

We extend the results of straight-edged computational geometry into the curved world by defining a pair of new geometric objects, thesplinegon and thesplinehedron, as curved generalizations of the polygon and polyhedron. We identify three distinct techniques for extending polygon algorithms to splinegons: the carrier polygon approach, the bounding polygon approach, and the direct approach. By these methods, large groups of algorithms for polygons can be extended as a class to encompass these new objects. In general, if the original polygon algorithm has time complexityO(f(n)), the comparable splinegon algorithm has time complexity at worstO(Kf(n)) whereK represents a constant number of calls to members of a set of primitive procedures on individual curved edges. These techniques also apply to splinehedra. In addition to presenting the general methods, we state and prove a series of specific theorems. Problem areas include convex hull computation, diameter computation, intersection detection and computation, kernel computation, monotonicity testing, and monotone decomposition, among others.This research was partially supported by National Science Foundation Grants MCS 83-03926, DCR85-05517, and CCR87-00917.This author's research was also partially supported by an Exxon Foundation Fellowship, by a Henry Rutgers Research Fellowship, and by National Science Foundation Grant CCR88-03549.     

Computational cancer cells identification by fractal dimension analysis

In the present work a software to identify cell anomaly through their fractal dimension calculation is introduced. The cell electronic microscopic image is imported to the software in gray scale and transformed to a black and white pattern in order to eliminate possible noise due to organic material close to the cell during the acquisition of the image. The number of pixels on the image contour is determined and the box-counting method is used to obtain the fractal dimension of the cell. Results for the fractal dimension have shown in very good agreement with other calculations with the advantage that the software is user-friendly, avoiding human analysis mistakes.     

Computational geometry algorithms for the systolic screen

Adigitized plane of sizeM is a rectangular M × M array of integer lattice points called pixels. A M × M mesh-of-processors in which each processorP _ij represents pixel (i,j) is a natural architecture to store and manipulate images in ; such a parallel architecture is called asystolic screen. In this paper we consider a variety of computational-geometry problems on images in a digitized plane, and present optimal algorithms for solving these problems on a systolic screen. In particular, we presentO(M)-time algorithms for determining all contours of an image; constructing all rectilinear convex hulls of an image (peeling); solving the parallel and perspective visibility problem forn disjoint digitized images; and constructing the Voronoi diagram ofn planar objects represented by disjoint images, for a large class of object types (e.g., points, line segments, circles, ellipses, and polygons of constant size) and distance functions (e.g., allL _p metrics). These algorithms implyO(M)-time solutions to a number of other geometric problems: e.g., rectangular visibility, separability, detection of pseudo-star-shapedness, and optical clustering. One of the proposed techniques also leads to a new parallel algorithm for determining all longest common subsequences of two words.Research supported by the Naural Sciences and Engineering Research Council of Canada. With the Editor-in-Chief's permission, this paper was sent to the referees in a form which kept them unaware of the fact that the Guest Editor is one of the co-authors.     

Computational geometry algorithms for the systolic screen

Adigitized plane Π of sizeM is a rectangular √M × √M array of integer lattice points called pixels. A √M × √M mesh-of-processors in which each processorP _ij represents pixel (i,j) is a natural architecture to store and manipulate images in Π; such a parallel architecture is called asystolic screen. In this paper we consider a variety of computational-geometry problems on images in a digitized plane, and present optimal algorithms for solving these problems on a systolic screen. In particular, we presentO(√M)-time algorithms for determining all contours of an image; constructing all rectilinear convex hulls of an image (peeling); solving the parallel and perspective visibility problem forn disjoint digitized images; and constructing the Voronoi diagram ofn planar objects represented by disjoint images, for a large class of object types (e.g., points, line segments, circles, ellipses, and polygons of constant size) and distance functions (e.g., allL _p metrics). These algorithms implyO(√M)-time solutions to a number of other geometric problems: e.g., rectangular visibility, separability, detection of pseudo-star-shapedness, and optical clustering. One of the proposed techniques also leads to a new parallel algorithm for determining all longest common subsequences of two words.     

Analysis and modeling of biological systems using fractal geometry

Fractal objects which, by definition, are objects that have scale-invariant shapes and fractional scaling dimensions (fractal dimension) with magnitudes related to the complexity of the objects, are ubiquitous in nature. In particular, many biological structures and systems have fractal properties and therefore may be well studied and modelled using fractal geometry. In the box counting algorithm, one of several different approaches to calculate the fractal dimension, one determines, for several values of, the number of boxesN() with side length needed to completely cover the studied object. IfN() andr are found to be related by the power law relationshipN(r) r ^–D, whereD is the scaling dimension, and ifD is a non-integer, then the object is fractal andD is the fractal dimension.In certain circumstances in which one may need to calculate the fractal dimension of a three-dimensional fractal from a two-dimensional projection (e.g. an X-ray), a new mathematical relationship may be utilized to obtain the actual dimensionD; it readsD=–log[1–(1–R ^2– D _p) ^R ]/logR + 3, whereD _p is the fractal dimension of the two-dimensional planar projection of the object andR is the box size used in calculating the box-counting dimension.Fractal dimension calculations have been found to be particularly useful as quantitative indices of the degree of coronary vascularity and the degree of heart interbeat interval variability. Fractal growth models such as diffusion limited aggregation (DLA) can be used to model artery growth.To sum up, fractal geometry is very useful in studying and modeling certain scale-invariant biological structures or systems which may not be easily described with Euclidean shapes.     

Visual analysis of quality-related manufacturing data using fractal geometry

Improving manufacturing quality is an important challenge in various industrial settings. Data mining methods mostly approach this challenge by examining the effect of operation settings on product quality. We analyze the impact of operational sequences on product quality. For this purpose, we propose a novel method for visual analysis and classification of operational sequences. The suggested framework is based on an Iterated Function System (IFS), for producing a fractal representation of manufacturing processes. We demonstrate our method with a software application for visual analysis of quality-related data. The proposed method offers production engineers an effective tool for visual detection of operational sequence patterns influencing product quality, and requires no understanding of mathematical or statistical algorithms. Moreover, it enables to detect faulty operational sequence patterns of any length, without predefining the sequence pattern length. It also enables to visually distinguish between different faulty operational sequence patterns in cases of recurring operations within a production route. Our proposed method provides another significant added value by enabling the visual detection of rare and missing operational sequences per product quality measure. We demonstrate cases in which previous methods fail to provide these capabilities.     

Optimization of multi-scale segmentation of satellite imagery using fractal geometry

ABSTRACT

After decades of research, optimal scale selection for image segmentation remains a key scienti?c problem in image analysis. In order to contribute to a solution, a new method was developed in this research, based on the use of fractal dimension as an indicator of optimality. First, the image is partitioned according to the rank-size rule (stemming from the Zipf’s law), to detect a set of scales corresponding to constant fractal dimension over image rescaling; these scales are defined as ‘optimal’. Then, the detected scales are transferred to the segmentation process through the projection of every partition head group to the entire image; this can be seen as a topological transformation. The Fractal Net Evolution Assessment (FNEA) is applied as a segmentation algorithm. The new method was structured as a mathematical proposition, then proved and finally was experimented with three types of satellite imagery (namely, Sentinel-2, RapidEye, and WorldView2) in four study areas with diverse land uses. In all cases, the method achieved to indicate those scales at which fractal dimension remains constant, therefore, the optimal scales. The results were verified visually and showed to be successful. Also, they were compared to pre-existing classification data, revealing high correlation between fractal dimension and classification accuracy. The new method is considered to be a generic, fully quantitative, straightforward, objective, rapid, robust, and easy to apply image segmentation tool.     

Discriminating between photorealistic computer graphics and natural images using fractal geometry

Rendering technology in computer graphics (CG) is now capable of producing highly photorealistic images,giving rise to the problem of how to identify CG images from natural images. Some methods were proposed to solve this problem. In this paper,we give a novel method from a new point of view of image perception. Although the photorealistic CG images are very similar to natural images,they are surrealistic and smoother than natural images,thus leading to the difference in perception. A part of features are derived from fractal dimension to capture the difference in color perception between CG images and natural images,and several generalized dimensions are used as the rest features to capture difference in coarseness. The effect of these features is verified by experiments. The average accuracy is over 91.2%.     

Visual simulation for granular rocks crush in virtual environment based on fractal geometry

In this paper, a new method is proposed for the simulation of rock crushing in virtual environment. The method can be described as a combination of a physical behavioral model with a phenomenological rock generator. The main modules of the solution consist of a Virtual Reality system, fractal geometric modeling, and physical control models. Virtual Reality and geometric modeling compose the phenomenological rock generator, which simulates the process; while the physical behavioral model controls or affects the results of the simulation, We present the key algorithms of the visual simulation solution, such as the rapid modeling algorithm for rock with complex topology, distributed parallel rendering for large scale and complex rock objects. To evaluate the system, a virtual simulation for rocks crushed in cone crusher is introduced.     

Parametric study of novel types of dielectric resonator antennas based on fractal geometry

Dielectric resonator antennas with fractal cross sectional areas have been investigated. Two main configurations of these novel types of dielectric resonator antennas have been examined. Analyses of these proposed dielectric resonator antennas are performed numerically using the finite element method and verified by the finite integration technique. Agreement between the methods is excellent. The effects of antenna parameters, such as fractal iteration level and tapering rate of dielectric resonator, are investigated. © 2007 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2007.     

基于泊松分布和分形几何的甲骨拓片字形复原方法

文中提出了一种基于泊松分布和分形几何的甲骨拓片字形复原方法.分析了甲骨拓片上字形图像和噪声区域的分布特征,通过计算每一个连通区域与拓片上所有连通区域数学期望的差值来识别拓片上的噪声区域.小于数学期望的连通区域被识别为噪声区域并被填充,从而保留了字形笔划区域.分析了甲骨拓片上字形图像边缘的分形几何特征,计算甲骨拓片字形边缘的分形维数等参数,通过计算拓片字形的轮廓线上当前点与左右相邻点形成的向量夹角的余弦值提取特征点,并对甲骨拓片字形边缘进行加权坐标的压缩变换,从而使甲骨拓片字形边缘得到平滑.实验结果显示,该方法可以有效地去除甲骨拓片上的噪声区域,保留字形笔划区域,并使甲骨拓片上字形边缘得到平滑.