116 results for Report, 2007

  • 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
  • Performance Evaluation of Stereo and Motion Analysis on Rectified Image Sequences

    Liu, Zhifeng (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). This paper introduces into seven real-world road driving stereo sequences (provided by Daimler AG, Germany; now freely available for academic research); it also informs about their use for performance evaluation in some experiments using common stereo and motion analysis algorithms. Often, such algorithms are tested on a few frames only, or on synthetic sequences, but not on long real-world sequences. The provided sequences have 250 to 300 stereo pairs each; they have been used at Daimler AG for testing 6D vision, which fuses disparity and motion data (by using a Kalman filter). In this paper we introduce into those seven sequences (and inform about the download web site); we discuss a few approaches how to use those sequences for testing either stereo or motion algorithms, or both combined together. Certainly, those sequences do have many more potentials for future performance evaluations for stereo and motion analysis algorithms.

    View record details
  • Belief-Propagation on Edge Images for Stereo Analysis of Image Sequences

    Guan, Shushi; 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 history of stereo analysis of images dates back more than one hundred years, but stereo analysis of image sequences is a fairly recent subject. Sequences allow time-propagation of results, but also come with particular characteristics such as being of lower resolution, or with less contrast. This article discusses the application of belief propagation (BP), which is widely used for solving various low-level vision problems, for the stereo analysis of night-vision stereo sequences. For this application it appears that BP often fails on the original frames for objects with blurry borders (trees, clouds, . . . ). In this paper, we show that BP leads to more accurate stereo correspondence results if it is applied on edge images, where we have decided for the Sobel edge operator, due to its time efficiency. We present the applied algorithm and illustrate results (without, or with prior edge processing) on seven, geometrically rectified night-vision stereo sequences (provided by Daimler AG, Germany).

    View record details
  • A novel method for analyzing the global stability of inviscid columnar swirling flow in a finite pipe

    Wang, Shixiao (2007-07)

    Report
    The University of Auckland Library

    We developed a general strategy to study the stability problem of the inviscid columnar swirling flow in a finite pipe based on the perturbation method of linear operators. By virtue of the columnar base state we were able to derive all the necessary formulas used in perturbation method in a manner of separation of variables. We then conduct a necessary benchmark case study based on the solid body rotation flow. We then applied the general method to the Lamb-Oseen vortex and the q-vortex, and found their approximated growth rate functions. The perturbation method proved effective and robust in application to these vortex flows. We also extended the method, by using the analytic continuation, to find the unstable modes with complex growth rates. This analytic continuation method reflects the global nature of the perturbation method. This study fills a major gap in the study of the global stability for swirling flows, and will have a positive impact on the study of the vortex breakdown phenomenon.

    View record details
  • Asymptotics of Diagonal Coefficients of Multivariate Generating Functions

    Raichev, A; Wilson, Mark (2007-05)

    Report
    The University of Auckland Library

    This article presents some recent progress in the asymptotics of diagonal coefficients of multivariate generating functions and can be seen as an extension of [RW].

    View record details
  • Asymptotics of the Minimum Manipulating Coalition Size for Positional Voting Rules under IC Behaviour

    Pritchard, G; Wilson, Mark (2007-02)

    Report
    The University of Auckland Library

    In 1973–75 Gibbard and Satterthwaite published a fundamental impossibility theorem which states that every non-dictatorial social choice function, whose range contains at least three alternatives, at certain profiles can be manipulated by a single individual voter [6, 15]. After that, the natural question arose: if there are no perfect rules, which ones are the best, i.e. least manipulable? To this question there can be no absolute answer – it depends both on the behaviour of the voters, and on the measure used to quantify the term “manipulability”. Among models of voter behaviour, the following two have gained the most attention ([3,14]). The Impartial Culture (IC) model assumes that voters are independent, and that each voter is equally likely to vote for any candidate. The Impartial Anonymous Culture (IAC) model assumes some degree of dependency. This paper concerns itself with the IC model.

    View record details
  • On Universal Computably Enumerable Prefix Codes

    Calude, C.S; Staiger, L (2007-10)

    Report
    The University of Auckland Library

    We study computably enumerable (c.e.) prefix codes which are capable of coding all positive integers in an optimal way up to a fixed constant: these codes will be called universal. We prove various characterisations of these codes including the following one: a c.e. prefix code is universal iff it contains the domain of a universal self-delimiting Turing machine. Finally, we study various properties of these codes from the points of view of computability, maximality, and density.

    View record details
  • Prefix-free Lukasiewicz Languages

    Staiger, L (2007-01)

    Report
    The University of Auckland Library

    Generalised Łukasiewicz languages are simply described languages having good information-theoretic properties. An especially desirable property is the one of being a prefix code. This paper addresses the question under which conditions a generalised Łukasiewicz language is a prefix code. Moreover, an upper bound on the delay of decipherability of a generalised Łukasiewicz language is derived.

    View record details
  • Describing Groups

    Nies, A (2007-03)

    Report
    The University of Auckland Library

    Two ways of describing a group are considered. 1. A group is finite-automaton presentable if its elements can be represented by strings over a finite alphabet, in such a way that the set of representing strings and the group operation can be recognized by finite automata. 2. An infinite f.g. group is quasi-finitely axiomatizable if there is a description consisting of a single first-order sentence, together with the information that the group is finitely generated. In the first part of the paper we survey examples of FA-presentable groups, but also discuss theorems restricting this class. In the second part, we give examples of quasi-finitely axiomatizable groups, consider the algebraic content of the notion, and compare it to the notion of a group which is a prime model. We also show that if a structure is bi-interpretable in parameters with the ring of integers, then it is prime and quasi-finitely axiomatizable.

    View record details
  • An Algebraic Characterization of the Halting Probability

    Chaitin, G.J (2007-04)

    Report
    The University of Auckland Library

    Using 1947 work of Post showing that the word problem for semigroups is unsolvable, we explicitly exhibit an algebraic characterization of the bits of the halting probability Ω. Our proof closely follows a 1978 formulation of Post’s work by M. Davis. The proof is selfcontained and not very complicated.

    View record details
  • Two Sources Are Better than One for Increasing the Kolmogorov Complexity of Infinite Sequences

    Zimand, M (2007-05)

    Report
    The University of Auckland Library

    The randomness rate of an infinite binary sequence is characterized by the sequence of ratios between the Kolmogorov complexity and the length of the initial segments of the sequence. It is known that there is no uniform effective procedure that transforms one input sequence into another sequence with higher randomness rate. By contrast, we display such a uniform effective procedure having as input two independent sequences with positive but arbitrarily small constant randomness rate. Moreover the transformation is a truth-table reduction and the output has randomness rate arbitrarily close to 1.

    View record details