Defect image segmentation using multilevel thresholding based on firefly algorithm with opposition-learning

Chen Kai Dai Min Zhang Zhisheng Chen Ping Shi Jinfei

(1Mechanical Engineering School, Southeast University, Nanjing 211189, China)(2Huaihai Institute of Technology, Lianyungang 222005, China)

?

Defect image segmentation using multilevel thresholding based on firefly algorithm with opposition-learning

Chen Kai1Dai Min1Zhang Zhisheng1Chen Ping1Shi Jinfei2

(1Mechanical Engineering School, Southeast University, Nanjing 211189, China)(2Huaihai Institute of Technology, Lianyungang 222005, China)

To segment defects from the quad flat non-lead (QFN) package surface, a multilevel Otsu thresholding method based on the firefly algorithm with opposition-learning is proposed. First, the Otsu thresholding algorithm is expanded to a multilevel Otsu thresholding algorithm. Secondly, a firefly algorithm with opposition-learning(OFA) is proposed. In the OFA, opposite fireflies are generated to increase the diversity of the fireflies and improve the global search ability. Thirdly, the OFA is applied to searching multilevel thresholds for image segmentation. Finally, the proposed method is implemented to segment the QFN images with defects and the results are compared with three methods, i.e., the exhaustive search method, the multilevel Otsu thresholding method based on particle swarm optimization and the multilevel Otsu thresholding method based on the firefly algorithm. Experimental results show that the proposed method can segment QFN surface defects images more efficiently and at a greater speed than that of the other three methods.

quad flat non-lead (QFN) surface defects; opposition-learning; firefly algorithm; multilevel Otsu thresholding algorithm

The quad flat non-lead (QFN) package is a type of flat no-lead package that has been widely used. However, on the surface of the QFN package, there are different types of defects which are harmful to the quality of the QFN package. The defects are relatively small, so it is difficult to segment the defects from the surface image with a single threshold. Therefore, multilevel image segmentation is applied to segmenting QFN surface defects from the QFN board.

The Otsu thresholding segmentation algorithm[1]is a classical and efficient image segmentation algorithm. In the case of segmenting several objects from the background, Otsu thresholding needs to be extended to multilevel Otsu thresholding segmentation. However, multilevel Otsu thresholding segmentation is time-consuming and involves large computation. Thus, several meta-heuristics optimal algorithms have been introduced to solve the problems. Yin[2]presented an optimal thresholding using genetic algorithms. Ghamisi et al.[3]developed a fractional-order Darwinian particle swarm optimization and the Darwinian particle swarm optimization for determining thresholds. Gao et al.[4]designed an ant colony optimization segmentation algorithm for solving multilevel Otsu problems. Sathya and Kayalvizhi[5]introduced a bacterial foraging algorithm into finding thresholds.

Recently, Yang[6]presented a new meta-heuristic algorithm, called the firefly algorithm. Due to the good performance on global search, the firefly algorithm has been widely used for solving optimization problems. Horng et al.[7]proposed a multilevel minimum cross entropy threshold selection based on the firefly algorithm, and demonstrated that the firefly algorithm outperformed the particle swarm optimization (PSO) and the quantum particle swarm optimization. Hassanzadeh et al.[8]applied the firefly algorithm to Otsu’s method. Nevertheless, in some cases, the firefly algorithm may easily fall into a local optimum which will lead to inappropriate results and slow convergence.

Hence, a novel firefly algorithm with opposition-learning is proposed to help fireflies escape from the local optimum and a multilevel Otsu thresholding based on the firefly algorithm with opposition-learning is applied to segmenting QFN surface defects.

1 Multilevel Otsu Thresholding Algorithm

σ2=ω1(μ1-μT)2+ω2(μ2-μT)2

(1)

In the situation of complex or multi-target image segmentation, an image needs to be classified intojclassesC1,C2,…,Cjwith the set of thresholdst1,t2,…,tj-1. Otsu thresholding should be expanded to multilevel Otsu thresholding. The between-class variance in multilevel Otsu thresholding can be defined by

(2)

where

(3)

(4)

Clearly, the multilevel Otsu thresholding algorithm is time-consuming and involves a large computation. Hence, the firefly algorithm with opposition-learning is proposed to solve the multilevel Otsu thresholding problem in the next section.

2 Multilevel Otsu Thresholding based on Firefly Algorithm with Opposition-Learning

2.1 Opposition-learning algorithm

(5)

(6)

2.2 Firefly algorithm with opposition-learning

The firefly algorithm[6]is a new meta-heuristic algorithm for optimization. In the firefly algorithm, there are three idealized rules: 1) All the fireflies are unisex so that one firefly is attracted to other fireflies regardless of their sex; 2) Attractiveness is proportional to their brightness; thus for any two flashing fireflies, the less brighter one moves towards the brighter one. If there is no brighter one than a particular firefly, it will move randomly; 3) The brightness of a firefly is affected or determined by the landscape of the objective function to be optimized. The movement of fireflyiattracted to another more attractive fireflyjis determined by

(7)

The firefly algorithm has shown good performance in solving optimization problems. However, in some cases, the firefly algorithm may fall into local optima. In order to improve its performance, a new firefly algorithm with opposition-learning (simplified OFA) is proposed. The aim of OFA is to combine the firefly algorithm and the opposition-learning algorithm. The main steps of OFA are as follows:

1) Initialize the parameters of OFA, including the number of fireflyn, the light absorption coefficientγ, the initial attractionβ0, the maximum iteration number iter, and a decision valuep0.

2) If rand(0,1)

3) Calculate the number of opposite fireflies according to Eq.(6), and calculate the fitness value of the fireflies and opposite fireflies.

4) Rank the fitness values of the fireflies and opposite fireflies, and select the bestnfireflies as the new fireflies.

5) If the iteration number reaches the maximum iteration number iter, go to 8); otherwise, go to 2).

6) Calculate the fitness values of the fireflies, and rank the fitness values.

7) If the iteration number reaches the maximum iteration number iter, go to 8); otherwise, update fireflies according to Eq.(7), and go to 2).

8) Output the maximum fitness value and the corresponding firefly.

In the OFA, the role of the opposition-learning algorithm is different from the random disturbance term in the firefly algorithm. With the advantage of the opposition-learning algorithm, fireflies can easily escape from local optima and the diversity of fireflies can be increased. As a result, the global optima can be quickly found by the OFA.

2.3 Multilevel Otsu thresholding method based on OFA

In order to solve the optimization problem of the multilevel Otsu thresholding method, an OFA-based multilevel Otsu thresholding method is proposed.

Fig.1 Flowchart of the OFA-based multilevel Otsu thresholding method

3 Experiment

In order to verify the efficiency of the proposed method, three QFN defect images (QFN images with scratch defect, scrape defect and void defect) acquired from the test handler for QFN were tested in this paper and three other methods were programmed for comparison. All the experiments were implemented in a Matlab on a computer with Intel Core 2.26 GHz and 2 GB memory.

The parameters of the OFA-based method are set in Tab.1. The images of segmentation results with two and three thresholds are shown in Fig.2. In Fig.2, the first column is the tested images (QFN image with scratch defect, scrape defect and void defect from up to down); the second column and the third column are the corresponding images of the segmentation results with two thresholds and three thresholds.

Tab.1 Parameters of OFA-based method

Three benchmark methods (i.e., the exhaustive search, PSO-based multilevel Otsu thresholding and FA-based multilevel Otsu thresholding) were implemented for comparison. The parameters of the PSO-based multilevel Otsu thresholding are shown in Tab.2 and the parameters of the FA-based method are set the same as the proposed method. Tab.3 gives the thresholds and the corresponding fitness values of the four methods. It can be found that: 1) The results of the OFA-based method and the FA-based method are equal to that of the exhaustive method; 2) The PSO-based method cannot find the global best results.

Fig.2 Images of segmentation results

Tab.2 Parameters of PSO-based method

In order to further verify the superiority of the proposed method, the computation time and PSNR (peak signal-to-noise ratio) evaluation criteria are used to analyze the performance. The formula of PSNR is

(8)

Taking all into account, the OFA-based method can segment QFN surface defects images more efficiently and with greater speed than that of the other three methods.

Tab.3 Thresholds and the corresponding fitness values obtained by the four methods

Tab.4 Computation time and PSNR value of the four methods

4 Conclusion

This paper presents a novel multilevel Otsu thresholding based on the firefly algorithm with opposition-learning for segmenting QFN surface defect image. The main contributions are: 1) The firefly algorithm with opposition-learning (OFA) is proposed; 2) The OFA is applied when searching multilevel thresholds for image segmentation. Experimental results show that the proposed method can efficiently deal with QFN surface defects segmentation and its speed is faster than that of the other three methods. In the future, the adaptive selection of threshold number and defect feature extraction for QFN surface defects images are the next problems to be solved.

[1]Otsu N. Threshold selection method from gray-level histograms[J].IEEETransactionsonSystems,Man,andCybernetics, 1979, 9(1):62-66.

[2]Yin P Y. A fast scheme for optimal thresholding using genetic algorithms [J].SignalProcessing, 1999, 72(2): 85-95.

[3]Ghamisi P, Couceiro M S, Benediktsson J A, et al. An efficient method for segmentation of images based on fractional calculus and natural selection [J].ExpertsSystemswithApplications, 2012, 39(16): 12407-12417.

[4]Gao K L, Dong M, Zhu L Q, et al. Image segmentation method based upon Otsu ACO Algorithm [C]//InformationandAutomation:CommunicationsinComputerandInformationScience. Springer, 2011, 86: 574-580.

[5]Sathya P D, Kayalvizhi R. Optimal multilevel thresholding using bacterial foraging algorithm [J].ExpertSystemswithApplications, 2011, 38(12): 15549-15564.

[6]Yang X S. Firefly algorithms for multimodal optimization [C]//StochasticAlgorithms:FoundationsandApplications. Springer, 2009: 169-178.

[7]Horng M H, Liou R J. Multilevel minimum cross entropy threshold selection based on the firefly algorithm [J].ExpertSystemswithApplications, 2011, 38(12): 14805-14811.

[8]Hassanzadeh T, Vojodi H, Eftekhari A M. An image segmentation approach based on maximum variance intra-cluster method and firefly algorithm [C]//2011SeventhInternationalConferenceonNaturalComputation. Shanghai, China, 2011: 1817-1821.

[9]Tizhoosh H R. Opposition-based learning: a new scheme for machine intelligence [C]//InternationalConferenceonIntelligentAgents,WebTechnologiesandInternetCommerce. Canberra, Australia, 2005, 1: 695-701.

基于反向螢火蟲算法的多閾值缺陷圖像分割

陳 愷1戴 敏1張志勝1陳 平1史金飛2

(1東南大學(xué)機(jī)械工程學(xué)院,南京211189)(2淮海工學(xué)院,連云港222005)

為了分割QFN表面的缺陷,提出一種基于反向螢火蟲算法的大津多閾值分割法．首先,將大津閾值分割擴(kuò)展為大津多閾值分割．其次,提出了一種基于反向?qū)W習(xí)的螢火蟲算法．在該算法中,生成的反向螢火蟲用于增加螢火蟲的多樣性和全局搜索能力．然后,將基于反向?qū)W習(xí)的螢火蟲算法應(yīng)用于多閾值分割．最后,使用所提出的方法對QFN缺陷圖像進(jìn)行閾值分割實(shí)驗(yàn),并將結(jié)果與窮舉法、基于粒子群算法的大津多閾值分割法、基于螢火蟲算法的大津多閾值分割法進(jìn)行比較．實(shí)驗(yàn)結(jié)果表明,所提方法能更有效地分割QFN表面缺陷,且分割速度快．

QFN表面缺陷;反向?qū)W習(xí);螢火蟲算法;大津多閾值算法

TP391.41

Received 2014-03-10．

Biographies：Chen Kai (1986—), female, graduate; Zhang Zhisheng(corresponding author), male, doctor, professor, oldbc@seu.edu.cn.

s：The National Natural Science Foundation of China (No.50805023), the Science and Technology Support Program of Jiangsu Province (No.BE2008081), the Transformation Program of Science and Technology Achievements of Jiangsu Province (No.BA2010093), the Program for Special Talent in Six Fields of Jiangsu Province (No.2008144).

：Chen Kai, Dai Min, Zhang Zhisheng, et al. Defect image segmentation using multilevel thresholding based on firefly algorithm with opposition-learning．[J]．Journal of Southeast University (English Edition),2014,30(4):434-438．

10.3969/j.issn.1003-7985.2014.04.006

10.3969/j.issn.1003-7985.2014.04.006