第38卷第1期2019年1月
大连工业大学学报
劳动法辞职J o u r n a l o fD a l i a nP o l y t e c h n i cU n i v e r s i t y
V o l.38N o.1
其实很简单J a n.2019
收稿日期:2018-03-16.
作者简介：黄超(1994-)，男，硕士研究生.D O I:10.19670/j.c n k i.d l g y d x x b.2019.0114
菌落挑取机器人视觉定位与路径优化
餐厅背景墙效果图黄超1，李体仁1，何凯2
(1.陕西科技大学机电工程学院，陕西西安710021;
2.中国科学院深圳先进技术研究院，广东深圳518055)
摘要：针对菌落挑取机器人挑取目标菌落的工艺流程和特点，结合视觉定位的基本原理，建立了菌落
挑取机器人的菌落二维视觉定位相机模型，提出了菌落二维视觉定位方法与流程，实现了目标菌落在世
界坐标系下的定位㊂针对菌落挑取实验待挑取菌落数量多㊁挑取路径不能进行合理规划而导致挑取效
率低等问题，分别运用基本蚁群算法和改进蚁群算法对菌落挑取路径进行优化，并给出了菌落挑取路径
优化图㊂模拟实验表明，菌落定位准确，菌落挑取效率得到显著提高㊂
关键词：菌落挑取机器人；二维视觉定位；路径优化
中图分类号:T H79;T P242文献标志码:A文章编号:1674-1404(2019)01-0059-05
P a t ho p t i m i z a t i o na n d v i s u a l p o s i t i o n i n g o f c o l o n yp i c k i n g r o b o t
H U A N G C h a o1,L I T i r e n1,H E K a i2
(1.C o l l e g eo fM e c h a n i c a l a n dE l e c t r i c a l E n g i n e e r i n g,S h a n x i U n i v e r s i t y
o f S c i e n c ea n dT e c h n o l o g y,X i a n710021,C h i n a;
2.S h e n z h e n I n s t i t u t e s o f A d v a n c e dT e c h n o l o g y,C h i n e s eA c a d e m y o f S c i e n c e s,S h e n z h e n518055,C h i n a)
A b s t r a c t:A c c o r d i n g t o t h e t e c h n o l o g i c a l p r o c e s s a n dc h a r a c t e r i s t i c so f c o l o n yp i c k i n g r o b o t s e l e c t i n g t a r g e t c o l o n y a sw e l l a s t h eb a s i c p r i n c i p l eo f v i s u a l p o s i t i o n i n g,t h em o d e l o f c o l o n yp i c k i n g r o b o t s t w o-d i m e n s i o n a l v i s u a l p o s i t i o n i n g c a m e r a w a s t a b l i s h e d,t h e nt h e m e t h o da n d p r o c e s so fc o l o n y t w o-d i m e n s i o n a l v i s u a l p o s i t i o n i n g w e r e p u t f o r w a r d,a n d t h e p o s i t i o n i n g o f t a r g e t c o l o n y i n t h ew o r l d c o o r d i n a t e s y s t e m w a s r e a l i z e d.I n t e r m so f t h e p r o b l e m s s u c ha s t h e l a r g en u m b e ro f c o l o n i e s t ob e s e l e c t e d i n t h ec o l o n yp i c k i n g e x p e r i m e n t a n dt h e l o w p i c k i n g e f f i c i e n c y c a u s e db y t h eu n r e a s o n a b l e p l a n n i n g o f t h e p i c k i n gp a t h,t h eb a s i c a n d i m p r o v e da n t c o l o n y a l g o r i t h m sw e r e r e s p e c t i v e l y u s e d t o o p t i m i z e t h e p i c k i n g p a t h o f t h e c o l o n y,a n d t h e o p t i m i z a t i o n d i a g r a mo f t h e p i c k i n g p a t h o f t h e c o l o n y w a s g i v e n.T h e s i m u l a t i o n e x p e r i m e n t s h o w s t h a t t h e c o l o n yp o s i t i o n i n g i s a c c u r a t e a n d t h e e f f i c i e n c y o f c o l o n yp i c k i n g i s i m p
r o v e d s i g n i f i c a n t l y.
K e y w o r d s:c o l o n yp i c k i n g r o b o t;t w od i m e n s i o n a l v i s u a l p o s i t i o n i n g;p a t ho p t i m i z a t i o n
0引言
克隆菌落挑取机器人(俗称挑克隆仪)是集光学成像㊁图像处理㊁自动控制于一体，广泛应用于生物工程领域的一种实验仪器㊂在20世纪90年代初期，美国㊁英国等发达国家相继开发出克隆菌落挑取机器人[1-2]，目前我国正处于初始研发阶段㊂其原理是运用机器视觉技术快速识别㊁定位目标菌落，然后机器根据目标菌落的位置控制挑针挑取菌落㊂传统菌落挑取方式采用手动挑取,
由于挑取效率低，且基于主观判断选择克隆菌落，容易遗漏目标菌落，挑取精度低，已渐渐不能满足一些大规模基因改造项目的实际要求㊂克隆菌落挑取机器人不仅提高了挑取效率，而且提高了挑取精度，极大降低了实验人员的工作强度，加快了实验项目的进度㊂
本研究根据克隆菌落挑取机器人工艺流程的特点和要求，并结合视觉定位基本原理，提出了克隆菌落挑取机器人菌落二维视觉定位方法，并运用改进蚁群算法对菌落挑取路径进行优化㊂
1 克隆菌落挑取机器人工艺流程
克隆菌落挑取机器人的作用是自动挑取克隆菌落，接种到96孔深孔板中㊂其工作流程为：采集培养皿中菌落的分布图像，并快速通过数字处理㊁识别和定位，得到目标菌落的位置坐标；控制系统根据菌落的坐标控制挑针进行挑取；将挑取的菌落接种到96孔深孔板中；如此循环，挑针继续挑取培养皿中的菌落，直到所有的目标菌落挑取完毕㊂在挑针每次挑取菌落之前，要对其进行清洗消毒，防止交叉污染㊂图1为待挑取的培养皿和96孔深孔板
㊂
(a
)培养皿
(b )96孔深孔板
图1 待挑取的培养皿和96微孔板
F i g .1 P e t r i d i s h e s a n d96-d e e p w e l l p
l a t e 2 菌落二维视觉定位原理
在克隆菌落挑取实验中，菌落随机分布在培养皿固体培养基的上表面，其中固体培养基的高度是固定的，所以克隆菌落在机器世界坐标系中
Z 方向的位置是确定的㊂故克隆菌落挑取机器人
只需对菌落进行二维平面的视觉定位㊂
2.1 二维平面视觉定位相机模型
菌落二维视觉定位就是建立图像坐标与世界坐标之间的对应关系，将以像素为单位的图像坐标转换为以毫米为单位的世界坐标㊂这种对应关系是由二维平面视觉定位相机模型决定的㊂二维平面视觉定位相机模型是光学成像的几何模型,
是以机器视觉中的针孔模型[3-4
]为基础建立的，如
图2所示㊂O 为相机光轴中心点,β为菌落所在平面,α为C C D 成像平面㊂O u v U V 坐标系称为图像坐标系，原点建在C C D 成像平面左上角点，图像中行方向与列方向分别对应图像坐标系的U ,
V 轴，单位为p i x e l ，如图3所示;O 1,O 2分别表示光轴中心点O 在α㊁β面的垂直投影点,O 1在图像坐标系O u v U V 下的坐标为(u 0,v 0);O w X w Y w 称为机器人的世界坐标系，单位m m
㊂图2 图像坐标系下的菌落图像
F i g .2 T h e c o l o n y i m a g e i n t h e i m a g e c o o r d i n a t e s y
s t e
m 图3 图像坐标系与世界坐标系
F i g .3 T h e i m a g e c o o r d i n a t e s y
s t e ma n d t h ew o r l d c o o r d i n a t e s y
s t e m 设菌落P 点在世界坐标系O w X w Y w 下的坐
标为P (X ,Y ),P 点在坐标系O 2X Y 下的坐标为
P (x ,y )
，其对应在图像坐标系下坐标为P (u ,v )㊂P 点在O 1U V 坐标系下坐标为P (a ,b )㊂根据针孔模型中透视投影关系[4]
，其比例关系见公式
(1),k 表示比例系数㊂
x a =y b
=k (1
)根据图3中位置关系，坐标系O 1U V 与坐标
系O u v
U V 之间的转换关系为a =u -u 0
b =v 0-
v {
(2
)0
6大 连 工 业 大 学 学 报
第38卷
由式(1)㊁式(2)可以表示图像坐标系O u v U V 与坐标系O 2X Y 之间的转换关系:
x y 1éëêêêùûúúú=k 0-k u 00-k k v 0001éëêêêùûúúúu v 1éëêêêùûú
úú
(3)坐标系O 2X Y 与世界坐标系O w X w Y w 之间
转换关系，可以用旋转矩阵R 和平移向量t 表示，如公式(4
)所示㊂X Y éëêê
ùûúú=R t []x y 1éëêêêùû
úúú(4
)令旋转矩阵R =c
o s θ-s i n θs i n θc o s θéëêêùûúú
，平移向量t =e f []T ，则由式(3)㊁式(4
)可得X Y éëêêùûúú=R t []k 0-k u 00-k k v 0001éëêêêùûúúúu v 1éëêêêùû
úúú=M u v 1éëêêêùûúúú(5
)
对于一个已建立好的视觉系统，其中k ,u 0,
v 0,e ,f ,θ都是确定量，故M 是视觉定位系统的参数矩阵，设M =g h m h -g n éëêê
ùû
úú，则X Y éëêêùûúú=g h m h -g n éëêêùûúúu v 1éëêêêùûúúú=M u v 1éëêêê
ùû
úúú(6
)2.2 二维视觉定位系统标定
M 是由视觉定位系统决定的,
求解M 也就是视觉定位系统的标定㊂一旦视觉定位系统发生改变或与机器位置发生变化,M 就发生改变，视觉定位系统就需要重新标定㊂
视觉定位系统标定采用通用精确定位点阵的平面模板
[5
]，如图4所示㊂通过获得标定板上特
征点的图像坐标与其对应的世界坐标，运用最小二乘法解出M ㊂M 中有4个待求参数，故至少需要2组标定板上的对应点，才能求解出M
㊂
图4 平面棋盘格标定模板
F i g .4 P l a n e c h e c k e r b o a r d c a l i b r a t i o n t e m p
l a t e 2.3 菌落二维目标定位
视觉定位系统识别定位目标菌落，得到其图
像坐标(u ,v )，将其带入公式(6)中，可以求出目标菌落在世界坐标系下的位置坐标，进而为下步挑取做好准备，其流程如图5所示
㊂
图5 菌落二维目标定位流程
F i g .5 T h e t w o -d i m e n s i o n a l t a r g
e t l o c a l i z a t i o n p r o c e s s o
f t h e c o l o n y
3 菌落挑取路径优化
在克隆菌落挑取实验中，培养皿中要挑取的目标菌落数量有100多个，为了提高机器人的挑取效率，就要对菌落挑取路径进行分析优化㊂菌落挑取路径优化问题可以转化为组合优化中典型的T S P 问题，但和T S P 问题有一处不同，即菌落挑取路径中最优路径不是一个闭合回路，求解这种问题可以参考一些求解T S P 问题的方法㊂蚁群算法作为一种刚兴起的启发式算法，在求解T S P 问题中与传统优化算法相比,
不易陷入局部最小值，同时具有自我学习㊁不断优化的优点[6
]
㊂文献[7]运用基本蚁群算法优化菌落挑取路径，提高挑取效率，但这种算法只适用于菌落数量少的情况，对于数量较多的挑取，基本蚁群算法优化效果并不是很好，同样存在求解速度慢㊁易陷入局部
最优的缺陷[
8-9]
㊂为了改进算法的优化效果，很多学者提出了
一些改进算法㊂S t u t z l e 等[10]
提出MMA S (m a x -m i na n t s y s t e m )蚁群系统，其对路径上的信息素进行上下界的限制以克服解的停滞问题㊂G a m -
b a r d e l l a 等[11]
提出A C S (a n t c o l o n y s y
s t e m )蚁群系统，其对信息素进行局部和全局两次更新以提
高全局收敛能力㊂本研究提出一种改进的蚁群算法求解菌落挑取路径优化问题，对搜索机制进行调整，
避免陷入局部最优，同时改进局部信息素更新原则，提高算法的全局搜索能力㊂实验模拟结
1
6第1期
黄超等：菌落挑取机器人视觉定位与路径优化
果表明，改进的蚁群算法优化结果比基本蚁群算法优化结果有了一定改进，更接近理想解㊂
3.1蚁群算法的改进可爱英文怎么说
3.1.1加入扰动的改进
针对蚁群算法容易陷入局部最优解，加入扰动参数q，每隔一定时间，蚂蚁在选择下一个城市时，只根据能见度选择，这样可以排除因为蚁群算法正反馈导致的较大误差解，扩大了解的搜索范围，有效避免了蚁群算法过早陷入局部最优解㊂这里引入常数q0，蚂蚁从城市i选择下一个城市j 时，首先产生一个[0,1]均匀分布的随机数q，当q 小于常数q0时，蚂蚁根据先验知识即能见度选择下一个城市㊂转移概率公式改进为
p k i j(t)=
ταi j(t)ηβi j(t)
ðsɪa l l o w e dταi s(t)ηβi s(t)jɪa l l o w e d,q>q0
ηi j(t)
ðsɪa l l o w e dηi s(t)jɪa l l o w e d,qɤq0 0其他
ì
î
í
ï
假唐僧
ï
ï
ï
ï
ï
ï
ï
(7)
式中:p k i j(t)表示t时刻蚂蚁k的转移概率,ηi j表示边(i,j)上的能见度,τi j表示边(i,j)上的信息素轨迹强度,α表示信息素重要程度参数,β表示启发式因子重要程度参数,a l l o w e d为禁忌表，表示蚂蚁k下一步允许选择的城市㊂
3.1.2局部信息素更新原则的改进
基本蚁群算法在信息素更新原则中，利用了蚂蚁周游最短路径的信息，虽然能避免陷入局部最优解，但整个求解过程耗费时间过长㊂为了在加快求解速度时，避免结果早熟，每只蚂蚁在周游过程中局部信息素更新，不仅要考虑最短路径信息，同时还要考虑城市i到城市j之间的信息，这样既可以快速求解全局最优解，同时也能够避免陷入局部最优解㊂改进的信息素更新原则为
Δτi j
b e s t(t,t+1)=
d i j Q
l b e s t l e n i
,jɪl b e s t t r a v e l
0其他{(8)
式中:l b e s t l e n表示最好路径l b e s t t r a v e l的长度,d i j表示城市i到城市j之间的距离,Q为信息量增加系数㊂3.2菌落挑取路径优化模拟
在克隆菌落挑取实验中，培养皿中待挑取的目标菌落数量有100多个㊂为了提高挑取效率，现随机生成100个菌落位置，分别使用基本蚁群算法和改进蚁群算法对挑取路径进行优化，模拟结果如图6㊁图7所示㊂其中菌落个数n=100，蚂蚁个数m=100，迭代次数N C=400，信息素重要程度参数α=1，启发式因子重要程度参数β=4，信息素挥发系数ρ=0.1，信息素总量Q=104；改进蚁群算法中q0=0.01㊂
如图6所示，使用基本蚁群算法对菌落挑取路径进行优化，其最短距离为853m m，但路径图明显有交叉，优化结果及早地陷入局部最优解㊂而采用改进蚁群算法优化结果如图7所示，得到路径最优解为792.6m m，路径优化图基本没有交叉
㊂
(a)
路径优化结果
(b)平均距离与最短距离
图6基本蚁群算法路径优化结果
F i g.6 P a t ho p t i m i z a t i o no f b a s i c a n t c o l o n y a l g o r i t h m
使用改进蚁群算法得到的优化结果比基本蚁群算法的结果更优，改进蚁群算法优化路径基本没有交叉地方，其最短距离也缩短了60.4m m，更接近理想最优解㊂同时改进蚁群算法使结果过早陷入局部最优解的趋势得到改善㊂所以采用改进蚁群算法优化克隆菌落挑取路径更接近最优解，这个优化路径对于实际应用有很大的指导意义㊂4结论
建立了菌落二维视觉定位相机模型，提出了
26大连工业大学学报第38卷
(a
)
路径优化结果 (b
)平均距离与最短距离图7 改进蚁群算法路径优化结果
F i g .7 P a t ho p t i m i z a t i o no f a n t c o l o n y a l g
o r i t h m 克隆菌落挑取机器人的菌落视觉定位方法，确定了目标菌落在世界坐标系中的位置㊂采用改进蚁群算法优化菌落挑取路径，结果表明，改进后的蚁群算法优化结果比基本蚁群算法优化结果有一定的改进，更接近理想最优解㊂经过改进，蚁群算法优化后的菌落挑取路径更接近理想状态，菌落挑取效率更高，从而提高克隆菌落挑取机器人的筛选通量㊂
入党校申请书
参考文献:
橘子老虎[1]J O N E SP ,WA T S O N A ,D A V I E SM ,e t a l .I n t e g
r a -t i o no f i m a g ea n a l y s i sa n dr o b o t i c s i n t oa f u l l y a u t o -m a t e dc o l o n yp i c k i n g a n d p l a t eh a n d l i n g s y
s t e m [J ].N u c l e i cA c i d sR e s e a r c h ,1992,20(17):4599-4606.[2]U B E RD C ,J A K L E V I CJ M ,T H E I L E H ,e ta l .
A p p l i c a t i o no f r o b o t i c s a n d i m a g e p r o c e s s i n g t oa u t o -m a t e d c o l o n y p i c k i n g a n d a r r a y i n g [J ].
B i o t e c h n i q
u e s ,1991,11(5):642-647.
[3
]徐鹏.基于机器视觉的机械零件二维尺寸检测系统研究[D ].广州：华南理工大学,2015.
[4
]代娜.基于机器视觉的小型规则零件二维尺寸测量研究[D ].武汉：湖北工业大学,2008.[5
]谈高超.基于机器视觉的批量零件自动检测系统的研制与工程应用[D ].上海：东华大学,2014.[6]胡银厚.求解T S P 算法的研究与改进[D ].郑州：郑州大学,2012.
[7
]邱实，程金光，张荣福.基于蚁群算法的单克隆菌落挑选仪路径规划[J ].光学仪器,2015,37(3):264-267.
[8]陈灵佳.蚁群算法在解决T S P 问题中的应用[J ].
电子技术与软件工程,2017(10):145.[9]段海滨.蚁群算法原理及其应用[M ].北京：科学出版社,2005.[10]S T U T Z L E T ,H O O S H.MA X -M I N a n ts y
s t e m a n d l o c a l s e a r c hf o r t h et r a v e l i n g s a l e s m a n p r o b l e m [C ]//P r o c e e d i n g
so f1997I E E EI n t e r n a t i o n a lC o n -f e r e n c eo nE v o l u t i o n a r y C o m p u t a t i o n .I n d i a n a p o l i s :I E E E ,1997:309-314.
[11]G AM B A R D E L L AL M ,D O R I G O M.S o l v i n g s y
m -m e t r i c a n da s y m m e t r i cT S P sb y a n tc o l o n i e s [C ]//P r o c e e d i n g
s o f 1996I E E EC o n f e r e n c eo nE v o l u t i o n -a r y C o m p u t a t i o n .N a g o y
a :I E E E ,1996:622-627.(责任编辑：刘发盛)
棒棒糖蛋糕3
6第1期
黄超等：菌落挑取机器人视觉定位与路径优化
