Some Studies On Image Retargeting, Nearest Polynomial And Curve Intersection

In this dissertation, we study the problems of image retargeting, nearest polynomial and curve intersection. With the increase in the diversity of display devices, such as computer, high definition television, cell-phone and personal digital assistant, changing images in size and aspect ratio to fit different screens is a hot issue in recent years; Since the polynomial with perturbed coefficients may lose some original properties, finding the nearest polynomial to the perturbed one for recovering these lost properties is a significant work; Intersection problem is a basic problem in computational geometry, computer aided geometric design, geometric modeling and numerical control machining, and the intersecting results affect the stability and practicality of the systems directly, so designing an accurate, efficient and robust intersection algorithm is an important research topic.This dissertation has six chapters altogether, and the main work can be summarized as follows:In Chapter1, we introduce the research background and the existing problems of image retargeting, nearest polynomial and curve intersection in turn, and then state my research motivation. At last, we give an outline of this dissertation.In Chapter2, we first classify approaches to automatically detect visual importance into two categories:bottom-up methods and top-down methods, and approaches to re-target an image into three categories:discrete methods, continuous methods and hybrid methods, and then make a brief review on each of them. An introduction to the nearest polynomial is also given.In Chapter3, we present an adaptive scaling control method for image retargeting. Considering that different regions from the important objects should be given the same visual importance, we first obtain an importance map having consistent structure with the original image by using the guided filter under the guidance of gradient map. Then a shape parameter is introduced to preserve the aspect ratios and spatial distribution of all important objects, and the Laplacian coordinates of the underlying mesh are smoothed to preserve the image geometric structure as well. Finally the retargeting problem can be formulated as a quadratic programming with linear constraint conditions. Experimental results show that our method succeeds in preserving the important contents and the geometric structure, and can generate the desired results.In Chapter4, we propose a method for computing the nearest complex polynomial. Given a univariate complex polynomial f(z) and a closed complex domain D, we study the computation of a univariate complex polynomial f(z) such that f(z) has a zero in D and the distance||f-f||=min, where f(z) does not have a zero in D and the boundary of D is a curve parameterized by a piecewise rational function. We first prove the existence of the nearest complex polynomial, and also show an important property that a nonzero nearest complex polynomial must have a zero on the boundary of D. Three different kinds of norms, i.e.,||·||p,||·||p,w and||·||mix, are then used to define the distance||·||between two polynomials. Furthermore, we construct the explicit formulas of the nearest complex polynomial f(z) and the minimal distance||f-f||for the case of D consisting of one point, while for the case of D being a general closed complex domain, we take||·||=||·||∞for example and give a specific idea to compute the nearest complex polynomial, where two numerical approaches are also proposed to implement that idea, the first one based on numerical comparison and the second one based on symbolic comparison. Finally, two numerical examples are presented to show the effectiveness and feasibility of our method.In Chapter5, we extend the computational processing in Chapter4. Based on the analysis of the three norms used in Chapter4, two more general kinds of norms, namely||·|p,P and||·||p,p1,p2are firstly defmed, and their dual norms are proved to be||·||q,p-1and||·||respectively. According to these two norms, we then give the explicit formulas of both the nearest complex polynomial and the minimal distance for the case of D consisting of one point.In Chapter6, we introduce homotopy methods to compute the intersections of two plane rational parametric curves. First of all, we transform the intersection problem into finding the solutions of a polynomial system, and then apply two kinds of homotopy methods, i.e., polyhedral homotopy (PH) and linear homotopy (LH), and Ehrlich-Aberth method (EA) to solve this system. By making use of a great deal of numerical examples, we reveal that homotopy methods would have good accuracy, efficiency and robustness in the problem of curve intersection for the first time. At la,st, some other applications of homotopy methods, such as surface intersection, are also presented.