半哑铃状图象识别——要求高精度优化算法【诚邀各位斑竹各位豪杰共同探讨研究】

Question

希望高手不吝赐教！！
情况是这样的：
有若干幅连续的图象——一个半哑铃形的存在渐变色的运动（平动加转动）物体各个时刻的照片，背景颜色复杂且不同时刻不同，我希望准确识别出这个半哑铃形物体的球部分的中心。我已经实现了该图象背景的严格的过滤函数，调用该函数即可严格区分背景和该物体边缘。该图象大约800*600象素。
简化后的问题：
1、800*600象素的纯黑色背景图片上，某位置有一个半哑铃形（0==0的一半0=）物体，该物体在图片上是完整的，但有恰好在边缘的情况。
2、该物体球部分实际为正圆，但在图片上与背景存在过度象素。
3、该物体柄部分为圆柱体，图象上呈现为矩形，但这个矩形的两边并不一定平行于计算机屏幕的X、Y轴。
4、该物体圆部分及柄与圆结合部分为白色，柄另一端为棕色，中间为过度色（实际图上柄小而球大，柄大约3象素宽，球半径15）：
  白白  白色与棕色过度    棕
   0=====================
要求：
给出识别该物体圆球部分的中心即图片上的圆的圆心算法；算法误差小于0.05象素，耗时小于50毫秒。

Answer 1

恩实际上我写了一段区分背景色的函数，利用这个函数结合基于快速行进法的种子填充算法，耗时100毫秒就可以把任意位置哑铃填充起来，，，这个填充算法里有一个布尔类型的双值表table(800,600)，如果继续用这个表就可以节省不少时间，这个表是程序启动时初始化的：）
实际上时间接近100毫秒也可以，再想办法优化呗，再说运行的机器要比我台机快，比本本慢。稍微多点时间应该是可以允许的

Answer 2

郁闷中啊Hough算法和RHT的计算量都很令人担心啊。有没有其他的好办法呢。。

Answer 3

搞软件工程的啊？。。迷糊
初步识别用的是网格，因为球直径为15，所以取Setp值稍小于其内接正四边形边长为网格大小：15/sqr(2)，进行网格搜索效率和精度都不错 。
for x as integer = 0 to w step 9
for y as integer = 0 to h step 9
'判定代码
next
next
效率还可以。。
问题在于。计算机上显示的球体，本身就不是数学意义上的圆，并且图像还存在边缘与底色的过渡，虽然视觉上看更接近一个圆，但实际上给识别带来很大麻烦啊不好办。
到底有没有成熟的方法或者高手临时脑袋一哆嗦指导一下？？？？？？对了，上面那代码是.NET的，写顺手了。。意思就是那么个意思了

Answer 4

四分法比 for x as inte =0 to w step 10要快吗。。还是顺序执行。
楼上思路还是找种子，然后一直爬出来4个点，，，，，，，取距离相等的3个点，，而后解方程(x-a)^2+(y-b)^2=r^2
这个算法误差和我用的取种子，取横弦，得中点，从终点做纵弦纵弦中点即圆心（初步判断），若此圆心与四个交点距离不等则
取相等的三个点，求圆。。
的思路效率差不多，精确度还是没有变化。

Answer 5

说个不成熟的想法：既然，这个问题简化成了一幅二值静止图象，可不可以这样，
分别从四个方向扫描
1.从左至右逐列，从前至后逐行，和相反的两个方向
2.当在任何方向遇到第一个非黑的象素点时就保存坐标。
3.通过比较这四个点的坐标，（假设是正圆），
必定有两个点(扫描线与圆的切点）坐标符合下面两个表达式
x1-x2+(y1-y2)=0 或 x1-x2+(y2-y1)=0其中之一，所以圆心的坐标就是 x1>x2,?x1,x2;y1>y2,?y2,y1
我自己感觉太理想化了

Answer 6

我最开始想的是扫描线的方法，先用固定步长，从上到下扫，800*600的需要扫描60条线，每线至少80个点，以确定半球的最大位置，由于vb的point实在太慢，直接搜索内存又不在行，所以一直没进一步研究。后来看了看边沿检索，又不知道检索出的边沿到底存到了什么地方。按俺的想法，
1）用扫描的方法来决定大概的位置，由于找到半球的大概位置之后，后面的数据就不用再扫描，两次扫描可以以上次的为基准，所以速度也可能不慢。
    此步结果，假如球在100, 100，半径为15的话，可能得到的位置为(90, 90), ( 110, 90),(90, 110), (110,90)4个点异色。由此得到球心在此4点组成的矩形中。
2）用二分法分别在前面选中的矩形中扫描，找到每行、列，异色点最多的。

Answer 7

实际上我的程序是VB 2005写的，.NET区里面人气太NB了，没敢去.NET下获取颜色速度还可以。找到每行、列，异色点最多的............我没理解上去。。
异色是什么意思。。

Answer 8

一个窗体
一个pictutrbox  打开autosize 和autoredraw
手动载入pictutrbox 的图像 这里以上面贴出来的图为例子 并且只处理黑白两种颜色 需要把图片弄干净点,把杂色去掉Private Declare Function GetPixel _
                Lib "gdi32" (ByVal hdc As Long, _
                             ByVal X As Long, _
                             ByVal Y As Long) As LongPrivate Declare Function SetPixel _
                Lib "gdi32" (ByVal hdc As Long, _
                             ByVal X As Long, _
                             ByVal Y As Long, _
                             ByVal crColor As Long) As LongConst pi = 3.141592654Const D  As Long = 86 '圆直径单位,像素Const P  As Long = 28 '圆直径的三分之一,单位,像素Const L  As Long = 130 '圆中心到柄末大概的距离,单位,像素Dim i    As Long, j As Long '循环用临时变量Dim H    As Long, W As Long '存放图片的宽高,  读取变量比读取控件属性快很多.....Dim pHdc As Long '存放图片的场景,  读取变量比读取控件属性快很多.....
    
Dim r    As Long '存放返回的颜色Dim p1x  As Long, p1y As Long '粗略算出的第一点Dim bx   As Long, by As Long '粗略算出的柄的端的点Dim ex   As Long, Ey As Long '最后得到的精确中心点Private Sub cmdCommand1_Click()    H = Picture1.Height / 15
    W = Picture1.Width / 15    pHdc = Picture1.hdc
    
    For i = 0 To H Step P
        For j = 0 To W Step P
            r = GetPixel(pHdc, j, i)            If r <> 0 Then
                If GetPixel(pHdc, j + P, i) <> 0 And GetPixel(pHdc, j, i + P) <> 0 And GetPixel(pHdc, j, i - P) <> 0 And GetPixel(pHdc, j - P, i) <> 0 Then
                    p1x = j: p1y = i '粗略的算出了大概的位置,误差在三分之一的直径以内
                    
                    GoTo b:
                End If
            End If        Next
    Nextb:    For i = 1 To 359 Step 6                                '找出相对于大概的圆心,柄端的位置
        bx = p1x + L * Sin(i * pi / 180)
        by = p1y + L * Cos(i * pi / 180)
        
        If GetPixel(pHdc, bx, by) <> 0 Then
            Call SetPixel(pHdc, bx, by, &HFF&)            Exit For        End If    Next    If bx > p1x Then
        If by > p1y Then '柄端在右下方时            For i = p1x To 0 Step -1                If GetPixel(pHdc, i, p1y) = 0 Then
                    ex = ((D / 2) - (p1x - i)) + p1x                    Exit For                End If            Next            For i = p1y To 0 Step -1                If GetPixel(pHdc, p1x, i) = 0 Then
                    Ey = ((D / 2) - (p1y - i)) + p1y                    Exit For                End If            Next
            
        Else            '柄端在右上方时 '懒得写了
        End If    Else        If by > p1y Then
            '在左下方        Else            '在左上方        End If
    End If    Call SetPixel(pHdc, ex, Ey, &HFF&)
    Picture1.RefreshEnd Sub

Answer 9

LZ你好，今天我是第一次听说了 种子填充算法， 大略的在CNKI上搜罗了一些论文看了，但是看的不是很明白，特别是快速行进法。大概的实现原理可否告知，在此谢过了，.cn。本人愚钝，有一点疑问，还麻烦LZ告知一二：我看了一些基本的种子填充算法，需要判断种子周边连通像素是否在区域内，对此判断是否会有信息丢失？造成图像成像变形，特别在RGB变化的情况下。LZ想精确到0.05个像素，在这种情况下，这个指标我觉得很恐怖。
原因有一下几点：
1.图像采集设备自身的噪声影响，会导致物体图像形状有变化（LZ应该是将图像二值化了吧）。我曾用过灰度矩检测物体边缘，而后最小二乘法拟合直线交点（距物体边缘约500个像素），在此情况下拟合误差都在2个像素以内。
2.光学系统的畸变。这个畸变会导致在不同位置的物体形状不一样。不知道LZ使用摄像机标定到了几阶，常用校正只校正了1阶，并且还是径向校正。同时光学系统的设计时所谓的校正，并不是全场校正，只是在部分位置校正了的。LZ说边缘存在渐变，这是很正常的。艾利斑的大小可能影响了周边像素，即光学系统的分辨率可能低于你的采集设备分辨率。同时光学系统的7种像差也会导致边缘模糊。CCD或者CMOS自身的噪声也会造成，所以边缘模糊是正常的。本人孤陋寡闻，在此还要向各位前辈学习。

Answer 10

就到这里吧。。讨论结束朋友给了一个核心DLL，问题很圆满的解决了。虽然是DLL……
楼上所说我实在没有办法帮助你，因为这方面我也是初学。0.05个像素是能达到的，甚至有的要求精度更高，我用的是彩色的图片，我涉及的方法都是没有经过二值化的，而且都没有读整个图片的全部像素，省去了这个过程，因为我感觉很耗时，采用的方法是比较像素的差异，不过是一个突发奇想得到的比较方式而已，实际上效率比网上常见的比较方式速度要低一些，但是适应性非常好关于你说的变形，正是造成误差的一个主要原因，我的解决思路是利用对称性，无论变形成什么样，只要变形是对称的就可以确定中心。晚上回家结贴，在办公室不好长时间上

Answer 11

首先扫描出一个外接矩形，那么矩形与物体的接触部分有以下几种情况
·3个点，1条线段
·4个点
·5个点
·根据哑铃柄的长短变化可能有6个点
总之将线段抛弃，只留下接触点，那么球体与外接矩形至少有两个接触点。以最典型的4个点（下图）为例：
分别做经过接触点A、B、C、D并且与矩形边垂直的执行，这些直线在矩形内相交与点O1、O2、O3、O4，那么球心必定是这些交点之一。
用排除法直到只剩下一个点：
·球心必定在物体内（白色）——排除O2、O4
·球心到接触点距离相同（AO1=BO1，CO3=DO3）——不一定排除O3
·接触点与球心的对称点（如A'、B'）必定为边界点——这个判断比较麻烦，而且不做也可以
·如果剩下多个点（只有哑铃柄的倾斜度±40°时发生），那么取到接触点（也就是外接矩形）距离大的点。