In this paper,we consider approximation algorithms for optimizing a generic multivariate polynomial function in discrete(typically binary)variables.Such models have natural applications in graph theory,neural networks...In this paper,we consider approximation algorithms for optimizing a generic multivariate polynomial function in discrete(typically binary)variables.Such models have natural applications in graph theory,neural networks,error-correcting codes,among many others.In particular,we focus on three types of optimization models:(1)maximizing a homogeneous polynomial function in binary variables;(2)maximizing a homogeneous polynomial function in binary variables,mixed with variables under spherical constraints;(3)maximizing an inhomogeneous polynomial function in binary variables.We propose polynomial-time randomized approximation algorithms for such polynomial optimizationmodels,and establish the approximation ratios(or relative approximation ratios whenever appropriate)for the proposed algorithms.Some examples of applications for these models and algorithms are discussed as well.展开更多
In this paper, we introduce a novel class of coplanar conics, the pencil of which can doubly contact to calibrate camera and estimate pose. We first analyze the properties of con-axes and con-eccentricity ellipses, wh...In this paper, we introduce a novel class of coplanar conics, the pencil of which can doubly contact to calibrate camera and estimate pose. We first analyze the properties of con-axes and con-eccentricity ellipses, which consist of a naturM extending pattern of concentric circles. Then the general case that two ellipses have two repeated complex intersection points is presented. This degenerate configuration results in a one-parameter family of homographies which map the planar pattern to its image. Although it is unable to compute the complete homography, an indirect 3-degree polynomial or 5-degree polynomial constraint on intrinsic parameters from one image can also be used for camera calibration and pose estimation under the minimal conditions. Furthermore, this nonlinear problem can be treated as a polynomial optimization problem （POP） and the global optimization solution can be also obtained by using SparsePOP （a sparse semidefinite programming relaxation of POPs）, Finally, the experiments with simulated data and real images are shown to verify the correctness and robustness of the proposed technique.展开更多
基金supported in part by Hong Kong General Research Fund(No.CityU143711)Zhening Li was supported in part by Natural Science Foundation of Shanghai(No.12ZR1410100)+1 种基金Ph.D.Programs Foundation of Chinese Ministry of Education(No.20123108120002)Shuzhong Zhang was supported in part by U.S.National Science Foundation(No.CMMI-1161242).
文摘In this paper,we consider approximation algorithms for optimizing a generic multivariate polynomial function in discrete(typically binary)variables.Such models have natural applications in graph theory,neural networks,error-correcting codes,among many others.In particular,we focus on three types of optimization models:(1)maximizing a homogeneous polynomial function in binary variables;(2)maximizing a homogeneous polynomial function in binary variables,mixed with variables under spherical constraints;(3)maximizing an inhomogeneous polynomial function in binary variables.We propose polynomial-time randomized approximation algorithms for such polynomial optimizationmodels,and establish the approximation ratios(or relative approximation ratios whenever appropriate)for the proposed algorithms.Some examples of applications for these models and algorithms are discussed as well.
基金the National Basic Research Program (973) of China(No.2011CB302203)the National Natural Science Foundation of China(No.60833009)
文摘In this paper, we introduce a novel class of coplanar conics, the pencil of which can doubly contact to calibrate camera and estimate pose. We first analyze the properties of con-axes and con-eccentricity ellipses, which consist of a naturM extending pattern of concentric circles. Then the general case that two ellipses have two repeated complex intersection points is presented. This degenerate configuration results in a one-parameter family of homographies which map the planar pattern to its image. Although it is unable to compute the complete homography, an indirect 3-degree polynomial or 5-degree polynomial constraint on intrinsic parameters from one image can also be used for camera calibration and pose estimation under the minimal conditions. Furthermore, this nonlinear problem can be treated as a polynomial optimization problem （POP） and the global optimization solution can be also obtained by using SparsePOP （a sparse semidefinite programming relaxation of POPs）, Finally, the experiments with simulated data and real images are shown to verify the correctness and robustness of the proposed technique.
