基于优化K-D树的大面积高密度PCB快速AOI

Fast AOI for large area and high-density PCB based on optimized K-D tree

传统的AO I孔搜索算法是基于顺序的查询方法,其局限在于,随着孔数N的增加,其查询时间以O(N2)急剧恶化,严重影响了大面积高密度PCB的检测效率。提出一种基于优化K-D树的AO I系统查询算法,该方法在建立树和进行完整查询时的效率均为O(NlogN)。实验表明,这种方法查询效率明显高于顺序查询法,对含有大量孔的PCB仍然有较短的查询时间,因而可以较大幅度地提高AO I的检测效率,在需要点位置查询的仪器领域也有广泛的应用前景。

Traditional algorithm for searching the holes on PCB is based on sequential query method.But as the number of holes（N） increases,a sharp deterioration of query time,which is proportional to O（N2） appears.The detection efficiency for large area,high-density PCB is seriously affected.A search algorithm of AOI system based on optimized K-D tree is proposed.The required time for the method to build up the tree and perform the whole search is proportional to O（Nlog N） on contrast.Experimental results show that this method still consumes a short query time when the PCB contains a great number of holes.The search efficiency of the method based on optimized K-D tree is significantly higher than that of sequential query method.Therefore,this method can greatly improve AOI detection efficiency and has great application future in the instrumental fields that have to query the positions of points.