116 results for Report, 2007

  • Shortest Path Algorithms for Sequences of Polygons

    Li, Fajie; Klette, Reinhard (2007)

    Report
    The University of Auckland Library

    You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original MI_tech website http://www.mi.auckland.ac.nz/index.php?option=com_content&view=article&id=91&Itemid=76 . All other rights are reserved by the author(s). In both English and Chinese Given a sequence k simple polygons in a plane, and a start point p, a target point q. We approximately compute a shortest path that starts at p, then visits each of the polygons in the specified order, and finally ends at q. So far no solution was known if the polygons are disjoint and non-convex. By applying a rubberband algorithm, we give an approximative algorithm with time complexity in κ(ε) · σ(n),where n is the total number of vertices of the given polygons, and function κ(ε) is as κ(ε)=(Lo-L)=/ε where Lo is the length of the initial path, and L is the true (i.e., optimum) path length. The given rubberband algorithm can also be applied to solve approximately three NP-complete or NP-hard 3D Euclidean shortest path (ESP) problems in time κ(ε)·σ(k), where k is the number of layers in a stack which contains the defined obstacles.

    View record details
  • An Approximate Algorithm for Solving the Watchman Route Problem

    Li, Fajie; Klette, Reinhard (2007)

    Report
    The University of Auckland Library

    You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original MI_tech website http://www.mi.auckland.ac.nz/index.php?option=com_content&view=article&id=91&Itemid=76 . All other rights are reserved by the author(s). The watchman route problem (WRP) was first introduced in 1988 and is defined as follows: How to calculate a shortest route completely contained inside a simple polygon such that any point inside this polygon is visible from at least one point on the route? So far the best known result for the WRP is an σ(n3logn) runtime algorithm (with inherent numerical problems of its implementation). This paper gives an κ(ε)·σ(kn) approximate algorithm for WRP by using a rubberband algorithm, where n is the number of vertices of the simple polygon, k a number of essential cuts and ε the chosen accuracy constant.

    View record details
  • Border and Surface Tracing - Theoretical Foundations

    Brimkov, Valentin; Klette, Reinhard (2007)

    Report
    The University of Auckland Library

    You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). In this paper we define and study digital manifolds of arbitrary dimension, and provide (in particular) a general theoretical basis for curve or surface tracing in picture analysis. The studies involve properties such as one-dimensionality of digital curves and (n-1)-dimensionality of digital hypersurfaces that makes them discrete analogs of corresponding notions in continuous topology. The presented approach is fully based on the concept of adjacency relation and complements the concept of dimension as common in combinatorial topology. This work appears to be the first one on digital manifolds based on a graph theoretical definition of dimension. In particular, in the n-dimensional digital space, a digital curve is a one-dimensional object and a digital hypersurface is an (n-1)-dimensional object, as it is in the case of curves and hypersurfaces in the Euclidean space. Relying on the obtained properties of digital hypersurfaces, we propose a uniform approach for studying good pairs defined by separations and obtain a classification of good pairs in arbitrary dimension. We also discuss possible applications of the presented definitions and results.

    View record details
  • Understanding Human Motion: A Historic Review

    Klette, Reinhard; Tee, Garry (2007)

    Report
    The University of Auckland Library

    You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). Understanding human motion is based on analyzing global motion patterns, rather than on studying local patterns such as hand gestures or facial expressions. This report reviews briefly (by selection, not by attempting to cover developments, and with a focus on Western History) people and contributions in science, art, and technology which contributed to the field of human motion understanding. This review basically stops at the time when advanced computing technology became available for performing motion studies based on recorded image data or extensive (model--based) calculations or simulations.

    View record details
  • Surface Area and Surface Integrals on Ellipsoid Segments. (2007)

    Tee, Garry (2007)

    Report
    The University of Auckland Library

    You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). The surface area and general surface integrals over a general segment of a 3-dimensional ellipsoid are computed.

    View record details
  • Permutable Polynomials and Rational Functions

    Tee, Garry (2007)

    Report
    The University of Auckland Library

    You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). Many infinite sequences of permutable rational functions and a few infinite sequences of permutable polynomials are constructed, on the basis of elliptic functions and trigonometric functions.

    View record details
  • Segmentation of Scanned Insect Footprints Using ART2 for Threshold Selection

    Shin, Bok-Suk; Cha, Eui-Young; Klette, Reinhard (2007)

    Report
    The University of Auckland Library

    You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). In a process of insect footprint recognition, footprint segments need to be extracted from scanned insect footprints in order to find out appropriate features for classification. In this paper, we use a clustering method in a preprocessing stage for extraction of insect footprint segments. In general, sizes and strides of footprints may be different according to type and size of an insect for recognition. Therefore we propose a method for insect footprint segment extraction using an improved ART2 algorithm regardless of size and stride of footprint pattern. In the improved ART2 algorithm, an initial threshold value for clustering is determined automatically using the contour shape of the graph created by accumulating distances between all the spots within a binarized footprint pattern image. In the experimental results, applying the proposed method to two kinds of insect footprint patterns, we illustrate that clustering is accomplished correctly.

    View record details
  • Approximate ESPs on Surfaces of Polytopes Using a Rubberband Algorithm

    Li, Fajie; Klette, Reinhard (2007)

    Report
    The University of Auckland Library

    You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). Let p and q be two points on the surface of a polytope P . This report provides a rubberband algorithm for computing a Euclidean shortest path between p and q (surface ESP) that is contained on the surface of P . The algorithm has k1(e) · k2(e) · O(n^2) time complexity, where n is the number of vertices of P , ki(e) = (L0i - Li )/e, for the true length Li of some shortest path with initial (polygonal path) length L0i (used when approximating this shortest path), for i = 1, 2. Rubberband algorithms follow a straightforward design strategy, and the proposed algorithm is easy to implement and thus of importance for applications, e.g. when analyzing 3D ob jects in 3D image analysis (such as in biomedical or industrial image analysis, using 3D image scanners).

    View record details
  • On Depth Recovery from Gradient Vector Fields

    Wei, Tiangong; Klette, Reinhard (2007)

    Report
    The University of Auckland Library

    You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). Depth recovery from gradient vector fields is required when reconstructing a surface (in three-dimensional space) from its gradients. Such a reconstruction task results, for example, for techniques in computer vision aiming at calculating surface normals (such as shape from shading, photometric stereo, shape from texture, shape from contours and so on). Surprisingly, discrete integration has not been studied very intensively so far. This chapter presents three classes of methods for solving problems of depth recovery from gradient vector fields: a two-scan method, a Fourier-transform based method, and a wavelet-transform based method. These methods extend previously known techniques, and related proofs are given in a short but concise form. The two-scan method consists of two different scans through a given gradient vector field. The final surface height values can be determined by averaging these two scans. Fourier-transform based methods are noniterative so that boundary conditions are not needed, and their robustness to noisy gradient estimates can be improved by choosing associated weighting parameters. The wavelet-transform based method overcomes the disadvantage of the Fourier-transform based method, which implicitly require that a surface height function is periodic. Experimental results using synthetic and real images are also presented.

    View record details
  • Euclidean Shortest Paths in Simple Polygons

    Li, Fajie; Klette, Reinhard (2007)

    Report
    The University of Auckland Library

    You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). Let p and q be two points in a simple polygon P. This chapter provides two rubberband algorithms for computing a shortest path between p and q that is contained in P. The two algorithms are based on previously known results on triangular or trapezoidal decompositions of simple polygons, and have either kappa(epsilon) times O(n) or kappa(epsilon) times O(n log n) time complexity, where kappa(epsilon) = (L0 - L)/epsilon, for the true length L of the shortest path and length L0 of a used initial polygonal path. Rubberband algorithms follow a straightforward design strategy, and the proposed algorithms ar easy to implement (after having the decompositions at hand).

    View record details
  • Touring Polygons, Parts Cutting, and q-Rectangles

    Li, Fajie; Klette, Reinhard (2007)

    Report
    The University of Auckland Library

    You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). Given a sequence of k simple polygons in a plane, a start point p, and a target point q. We approximately compute a shortest path that starts at p, then visits each of the polygons in the specified order, and finally ends at q. So far no solution was known if the polygons are pairwise disjoint and non-convex. By applying a rubberband algorithm, we give an approximative algorithm with time complexity in kappa(epsilon) times O(n), where n is the total number of vertices of the given polygons, and function kappa(epsilon) is as follows: kappa(epsilon) = (L_0 - L)/epsilon, where L_0 is the length of the initial path, and L is the true (i.e., optimum) path length. The given rubberband algorithm can also be applied to solve approximately three NP-complete or NP-hard 3D Euclidean shortest path (ESP) problems in time kappa(epsilon) times O(k), where k is the number of layers in a stack which contains the defined obstacles.

    View record details
  • Decomposing a Simple Polygon into Trapezoids

    Li, Fajie; Klette, Reinhard (2007)

    Report
    The University of Auckland Library

    You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). Chazelle's triangulation \cite{BC1991} forms today the common basis for linear-time Euclidean shortest path (ESP) calculations (where start and end point are given within a simple polygon). This paper provides an alternative method for subdividing a simple polygon into ``basic shapes'', using trapezoids instead of triangles. The authors consider the presented method as being substantially simpler than the linear-time triangulation method. However, it requires a sorting step (of a subset of vertices of the given simple polygon); all the other subprocesses are linear time.

    View record details
  • Euclidean Shortest Paths in Simple Cube Curves at a Glance

    Li, Fajie; Klette, Reinhard (2007)

    Report
    The University of Auckland Library

    You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). This paper reports about the development of two provably correct approximate algorithms which calculate the Euclidean shortest path (ESP) within a given cube-curve with arbitrary accuracy, defined by epsilon >0, and in time complexity kappa(epsilon) O(n), where kappa(epsilon) is the length difference between the path used for initialization and the minimum-length path, divided by epsilon. A run-time diagram also illustrates this linear-time behavior of the implemented ESP algorithm.

    View record details
  • Zooming Optical Flow Computation

    Ohnishi, Naoya; Imiya, Atsushi; Klette, Reinhard (2007)

    Report
    The University of Auckland Library

    You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). This paper introduces a new algorithm for computing multi-resolution optical flow, and compares this new hierarchical method with the traditional combination of the Lucas-Kanade method with a pyramid transform. The paper shows that the new method promises convergent optical flow computation. Aiming at accurate and stable computation of optical flow, the new method propagates results of computations from low resolution images to those of higher resolution. The resolution of images increases this way for the sequence of images used in those calculations. The given input sequence of images defines the maximum of possible resolution.

    View record details
  • The Dunedin Arabic Manuscript of Euclid's Elements

    Tee, Garry; Amleh, Amal (2007)

    Report
    The University of Auckland Library

    You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). The central library at the University of Otago has a finely-written Arabic manuscript: Dunedin De Beer Collection MS 98. That contains chapters 1 to 3 of 13 chapters of Euclid's Elements, in the Ishaq-Thabit translation. A few annotations (in Arabic, Persian, and English) are written in the margins, including on the last page the Arabic date 873 A.H. (1468 A.D.) Alos on that last page there is a Persian note dated 924 A.H. (1518 A.D.), telling that Sultan Mahmud Shah gifted this manuscript to a scholar named Hussein.

    View record details
  • Tight frames generated by finite nonabelian groups

    Vale, Richard; Waldron, Shayne (2007-07)

    Report
    The University of Auckland Library

    Let $cH$ be a Hilbert space of finite dimension $d$, such as the finite signals $Cd$ or a space of multivariate orthogonal polynomials, and $nge d$. There is a finite number of tight frames of $n$ vectors for $cH$ which can be obtained as the orbit of a single vector under the unitary action of an abelian group $G$ (of symmetries of the frame). Each of these so called {it harmonic frames} or {it geometrically uniform frames} can be obtained from the character table of $G$ in a simple way. These frames are used in signal processing and information theory. For a nonabelian group $G$ there are in general uncountably many inequivalent tight frames of $n$ vectors for $cH$ which can be obtained as such a $G$--orbit. However, by adding an additional natural symmetry condition (which automatically holds if $G$ is abelian), we obtain a finite class of such frames which can be constructed from the character table of $G$ in a similar fashion to the harmonic frames. This is done by identifying each $G$--orbit with an element of the group algebra $CC G$ (via its Gramian), imposing the condition in the group algebra, and then describing the corresponding class of tight frames.

    View record details
  • On the stability of swirling flows in a finite pipe

    Wang, Shixiao (2007-07)

    Report
    The University of Auckland Library

    We study the stability mechanism of the swirling flow in a finite pipe. We first revisited the Rayleigh's linear stability theory, and build up the nonlinear theory in the framework of Hamiltonian system. We then consider the Lamb-Oseen vortex in a finite pipe with fixed flowrate condition at the boundaries. By using recently developed perturbation method of the linear operators, we analyzed the global stability equation and found the disturbance flow fields. We then conducted a study of the kinetic energy transfer mechanism between the disturbance and the base flow by using the Reynolds-Orr equation. We found that the energy transfer takes place actively at the boundaries as well as inside the flow. This is contrast to the solid body rotation flow. We further investigated Lamb-Oseen vortex in a slightly divergent pipe and showed that the internal flow has a leading role in the energy transfer mechanism. This study clarifies the relation of the Rayleigh stability and the global stability found by Wang and Rusak, and provide a basic understanding of the stability mechanism of swirling flows in a finite pipe

    View record details
  • Separable subspaces of affine function spaces on convex compact sets

    Moors, Warren B.; Reznichenko, E. (2007-02)

    Report
    The University of Auckland Library

    Let $K$ be a compact convex subset of a separated locally convex space (over $mathbb{R}$) and let $A_p(K)$ denote the space of all continuous real-valued affine mappings defined on $K$, endowed with the topology of pointwise convergence on the extreme points of $K$. In this paper we shall examine some topological properties of $A_p(K)$. For example, we shall consider when $A_p(K)$ is monolithic and when separable compact subsets of $A_p(K)$ are metrizable.

    View record details
  • Four dimensional conformal C-spaces

    Gover , A. Rod; Nagy, Paul-Andi (2007-01)

    Report
    The University of Auckland Library

    We investigate the structure of conformal C-spaces, a class of Riemannian manifolds which naturally arises as a conformal generalisation of the Einstein condition. A basic question is when such a structure is closed, or equivalently locally conformally Cotton. In dimension 4 we obtain a full answer to this question and also investigate the incidence of the Bach condition on this class of metrics. This is related to earlier results obtained in the Einstein-Weyl context.

    View record details
  • Integrating Disparity Images by Incorporating Disparity Rate

    Vaudrey, Tobi; Bandino, Hernan; Gehrig, Stefan (2007)

    Report
    The University of Auckland Library

    You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original MI_tech website http://www.mi.auckland.ac.nz/index.php?option=com_content&view=article&id=91&Itemid=76 . All other rights are reserved by the author(s). Intelligent vehicle systems need to distinguish which objects are moving and which are static. A static concrete wall lying in the path of a vehicle should be treated differently than a truck moving in front of the vehicle. This paper proposes a new algorithm that addresses this problem, by providing dense dynamic depth information, while coping with real-time constraints. The algorithm models disparity and disparity rate pixel-wise for an entire image. This model is integrated over time and tracked by means of many pixel-wise Kalman filters. This provides better depth estimation results over time, and also provides speed information at each pixel without using optical flow. This simple approach leads to good experimental results for real stereo sequences, by showing an improvement over previous methods.

    View record details