利用重心原理的图像目标最小外接矩形快速算法

New algorithm for minimum enclosing rectangle of the object in the image region based on center-of-gravity principle

提出了一种基于重心原理的求取目标最小外接矩形的快速算法——寻找主轴法。利用重心原理确定水平主轴与垂直主轴的初始位置和旋转中心,根据水平主轴确定目标的初始外接矩形,在水平主轴和垂直主轴构成的锐角区域内,旋转外接矩形,找到面积最小的外接矩形,作为寻优目标。该算法利用重心原理确定的主轴初始位置非常有效,缩小了搜索区间,减少了整个寻优过程中的旋转次数,并且仅旋转用直线方程表示的主轴,大大减少了运算量,有效提高了运算速度,可以快速找到目标的最小外接矩形。

A new algorithm of minimum enclosing rectangle based on the center-of-gravity principle, searching main axis method, was proposed. Using the center-of-gravity principle the initial positions and the rotating center of the horizontal axis and the vertical axis were obtained. The initial enclosing rectangle was determined by means of the horizontal axis. In the acute angle region between the horizontal axis and the vertical axis the enclosing rectangle was rotated until the enclosing rectangle of minimum area was found. This enclosing rectangle was just the optimization goals. The initial position of the main axis determined with the center-of-gravity principle was so efficient that region of search was shrunk and rotation count was reduced in the whole optimizing procedure. And since only the main axis which could be expressed by linear equation was rotated, calculating complexity was decreased remarkably and computation speed was increased effectively. Minimum enclosing rectangle of the object can be quickly found.