16acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/*M/////////////////////////////////////////////////////////////////////////////////////// 26acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 36acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 46acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 56acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// By downloading, copying, installing or using the software you agree to this license. 66acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// If you do not agree to this license, do not download, install, 76acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// copy or use the software. 86acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 96acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Intel License Agreement 116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// For Open Source Computer Vision Library 126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Copyright (C) 2000, Intel Corporation, all rights reserved. 146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Third party copyrights are property of their respective owners. 156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Redistribution and use in source and binary forms, with or without modification, 176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// are permitted provided that the following conditions are met: 186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// * Redistribution's of source code must retain the above copyright notice, 206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// this list of conditions and the following disclaimer. 216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// * Redistribution's in binary form must reproduce the above copyright notice, 236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// this list of conditions and the following disclaimer in the documentation 246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// and/or other materials provided with the distribution. 256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// * The name of Intel Corporation may not be used to endorse or promote products 276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// derived from this software without specific prior written permission. 286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// This software is provided by the copyright holders and contributors "as is" and 306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// any express or implied warranties, including, but not limited to, the implied 316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// warranties of merchantability and fitness for a particular purpose are disclaimed. 326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// In no event shall the Intel Corporation or contributors be liable for any direct, 336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// indirect, incidental, special, exemplary, or consequential damages 346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// (including, but not limited to, procurement of substitute goods or services; 356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// loss of use, data, or profits; or business interruption) however caused 366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// and on any theory of liability, whether in contract, strict liability, 376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// or tort (including negligence or otherwise) arising in any way out of 386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// the use of this software, even if advised of the possibility of such damage. 396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//M*/ 416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#include "_cv.h" 436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#include "_cvlist.h" 446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define halfPi ((float)(CV_PI*0.5)) 466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define Pi ((float)CV_PI) 476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define a0 0 /*-4.172325e-7f*/ /*(-(float)0x7)/((float)0x1000000); */ 486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define a1 1.000025f /*((float)0x1922253)/((float)0x1000000)*2/Pi; */ 496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define a2 -2.652905e-4f /*(-(float)0x2ae6)/((float)0x1000000)*4/(Pi*Pi); */ 506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define a3 -0.165624f /*(-(float)0xa45511)/((float)0x1000000)*8/(Pi*Pi*Pi); */ 516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define a4 -1.964532e-3f /*(-(float)0x30fd3)/((float)0x1000000)*16/(Pi*Pi*Pi*Pi); */ 526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define a5 1.02575e-2f /*((float)0x191cac)/((float)0x1000000)*32/(Pi*Pi*Pi*Pi*Pi); */ 536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define a6 -9.580378e-4f /*(-(float)0x3af27)/((float)0x1000000)*64/(Pi*Pi*Pi*Pi*Pi*Pi); */ 546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define _sin(x) ((((((a6*(x) + a5)*(x) + a4)*(x) + a3)*(x) + a2)*(x) + a1)*(x) + a0) 566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define _cos(x) _sin(halfPi - (x)) 576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/****************************************************************************************\ 596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn* Classical Hough Transform * 606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\****************************************************************************************/ 616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renntypedef struct CvLinePolar 636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float rho; 656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float angle; 666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCvLinePolar; 686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/*=====================================================================================*/ 706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define hough_cmp_gt(l1,l2) (aux[l1] > aux[l2]) 726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic CV_IMPLEMENT_QSORT_EX( icvHoughSortDescent32s, int, hough_cmp_gt, const int* ) 746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* 766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennHere image is an input raster; 776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstep is it's step; size characterizes it's ROI; 786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennrho and theta are discretization steps (in pixels and radians correspondingly). 796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennthreshold is the minimum number of pixels in the feature for it 806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennto be a candidate for line. lines is the output 816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennarray of (rho, theta) pairs. linesMax is the buffer size (number of pairs). 826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennFunctions return the actual number of found lines. 836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn*/ 846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void 856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvHoughLinesStandard( const CvMat* img, float rho, float theta, 866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int threshold, CvSeq *lines, int linesMax ) 876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int *accum = 0; 896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int *sort_buf=0; 906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float *tabSin = 0; 916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float *tabCos = 0; 926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "icvHoughLinesStandard" ); 946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const uchar* image; 986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int step, width, height; 996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int numangle, numrho; 1006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int total = 0; 1016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float ang; 1026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int r, n; 1036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, j; 1046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float irho = 1 / rho; 1056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double scale; 1066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ASSERT( CV_IS_MAT(img) && CV_MAT_TYPE(img->type) == CV_8UC1 ); 1086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn image = img->data.ptr; 1106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn step = img->step; 1116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn width = img->cols; 1126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn height = img->rows; 1136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn numangle = cvRound(CV_PI / theta); 1156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn numrho = cvRound(((width + height) * 2 + 1) / rho); 1166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( accum = (int*)cvAlloc( sizeof(accum[0]) * (numangle+2) * (numrho+2) )); 1186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( sort_buf = (int*)cvAlloc( sizeof(accum[0]) * numangle * numrho )); 1196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( tabSin = (float*)cvAlloc( sizeof(tabSin[0]) * numangle )); 1206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( tabCos = (float*)cvAlloc( sizeof(tabCos[0]) * numangle )); 1216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( accum, 0, sizeof(accum[0]) * (numangle+2) * (numrho+2) ); 1226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( ang = 0, n = 0; n < numangle; ang += theta, n++ ) 1246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tabSin[n] = (float)(sin(ang) * irho); 1266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tabCos[n] = (float)(cos(ang) * irho); 1276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // stage 1. fill accumulator 1306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < height; i++ ) 1316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < width; j++ ) 1326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( image[i * step + j] != 0 ) 1346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( n = 0; n < numangle; n++ ) 1356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn r = cvRound( j * tabCos[n] + i * tabSin[n] ); 1376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn r += (numrho - 1) / 2; 1386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn accum[(n+1) * (numrho+2) + r+1]++; 1396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // stage 2. find local maximums 1436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( r = 0; r < numrho; r++ ) 1446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( n = 0; n < numangle; n++ ) 1456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int base = (n+1) * (numrho+2) + r+1; 1476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( accum[base] > threshold && 1486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn accum[base] > accum[base - 1] && accum[base] >= accum[base + 1] && 1496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn accum[base] > accum[base - numrho - 2] && accum[base] >= accum[base + numrho + 2] ) 1506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sort_buf[total++] = base; 1516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // stage 3. sort the detected lines by accumulator value 1546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvHoughSortDescent32s( sort_buf, total, accum ); 1556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // stage 4. store the first min(total,linesMax) lines to the output buffer 1576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn linesMax = MIN(linesMax, total); 1586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn scale = 1./(numrho+2); 1596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < linesMax; i++ ) 1606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvLinePolar line; 1626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int idx = sort_buf[i]; 1636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int n = cvFloor(idx*scale) - 1; 1646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int r = idx - (n+1)*(numrho+2) - 1; 1656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn line.rho = (r - (numrho - 1)*0.5f) * rho; 1666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn line.angle = n * theta; 1676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( lines, &line ); 1686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 1716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &sort_buf ); 1736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &tabSin ); 1746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &tabCos ); 1756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &accum ); 1766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 1776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/****************************************************************************************\ 1806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn* Multi-Scale variant of Classical Hough Transform * 1816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\****************************************************************************************/ 1826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#if defined _MSC_VER && _MSC_VER >= 1200 1846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#pragma warning( disable: 4714 ) 1856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#endif 1866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//DECLARE_AND_IMPLEMENT_LIST( _index, h_ ); 1886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennIMPLEMENT_LIST( _index, h_ ) 1896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void 1916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvHoughLinesSDiv( const CvMat* img, 1926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float rho, float theta, int threshold, 1936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int srn, int stn, 1946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq* lines, int linesMax ) 1956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 1966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn uchar *caccum = 0; 1976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn uchar *buffer = 0; 1986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float *sinTable = 0; 1996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int *x = 0; 2006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int *y = 0; 2016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn _CVLIST *list = 0; 2026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "icvHoughLinesSDiv" ); 2046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 2066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define _POINT(row, column)\ 2086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (image_src[(row)*step+(column)]) 2096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn uchar *mcaccum = 0; 2116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int rn, tn; /* number of rho and theta discrete values */ 2126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int index, i; 2136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int ri, ti, ti1, ti0; 2146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int row, col; 2156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float r, t; /* Current rho and theta */ 2166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float rv; /* Some temporary rho value */ 2176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float irho; 2186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float itheta; 2196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float srho, stheta; 2206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float isrho, istheta; 2216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const uchar* image_src; 2236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int w, h, step; 2246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int fn = 0; 2256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float xc, yc; 2266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const float d2r = (float)(Pi / 180); 2286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int sfn = srn * stn; 2296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int fi; 2306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int count; 2316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int cmax = 0; 2326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CVPOS pos; 2346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn _index *pindex; 2356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn _index vi; 2366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ASSERT( CV_IS_MAT(img) && CV_MAT_TYPE(img->type) == CV_8UC1 ); 2386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ASSERT( linesMax > 0 && rho > 0 && theta > 0 ); 2396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn threshold = MIN( threshold, 255 ); 2416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn image_src = img->data.ptr; 2436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn step = img->step; 2446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn w = img->cols; 2456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn h = img->rows; 2466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn irho = 1 / rho; 2486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn itheta = 1 / theta; 2496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn srho = rho / srn; 2506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn stheta = theta / stn; 2516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn isrho = 1 / srho; 2526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn istheta = 1 / stheta; 2536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn rn = cvFloor( sqrt( (double)w * w + (double)h * h ) * irho ); 2556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tn = cvFloor( 2 * Pi * itheta ); 2566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn list = h_create_list__index( linesMax < 1000 ? linesMax : 1000 ); 2586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn vi.value = threshold; 2596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn vi.rho = -1; 2606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn h_add_head__index( list, &vi ); 2616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* Precalculating sin */ 2636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( sinTable = (float*)cvAlloc( 5 * tn * stn * sizeof( float ))); 2646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( index = 0; index < 5 * tn * stn; index++ ) 2666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sinTable[index] = (float)cos( stheta * index * 0.2f ); 2686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( caccum = (uchar*)cvAlloc( rn * tn * sizeof( caccum[0] ))); 2716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( caccum, 0, rn * tn * sizeof( caccum[0] )); 2726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* Counting all feature pixels */ 2746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( row = 0; row < h; row++ ) 2756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( col = 0; col < w; col++ ) 2766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn fn += _POINT( row, col ) != 0; 2776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( x = (int*)cvAlloc( fn * sizeof(x[0]))); 2796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( y = (int*)cvAlloc( fn * sizeof(y[0]))); 2806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* Full Hough Transform (it's accumulator update part) */ 2826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn fi = 0; 2836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( row = 0; row < h; row++ ) 2846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( col = 0; col < w; col++ ) 2866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( _POINT( row, col )) 2886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int halftn; 2906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float r0; 2916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float scale_factor; 2926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int iprev = -1; 2936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float phi, phi1; 2946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float theta_it; /* Value of theta for iterating */ 2956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* Remember the feature point */ 2976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn x[fi] = col; 2986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn y[fi] = row; 2996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn fi++; 3006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn yc = (float) row + 0.5f; 3026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn xc = (float) col + 0.5f; 3036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* Update the accumulator */ 3056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn t = (float) fabs( cvFastArctan( yc, xc ) * d2r ); 3066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn r = (float) sqrt( (double)xc * xc + (double)yc * yc ); 3076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn r0 = r * irho; 3086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ti0 = cvFloor( (t + Pi / 2) * itheta ); 3096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn caccum[ti0]++; 3116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn theta_it = rho / r; 3136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn theta_it = theta_it < theta ? theta_it : theta; 3146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn scale_factor = theta_it * itheta; 3156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn halftn = cvFloor( Pi / theta_it ); 3166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( ti1 = 1, phi = theta_it - halfPi, phi1 = (theta_it + t) * itheta; 3176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ti1 < halftn; ti1++, phi += theta_it, phi1 += scale_factor ) 3186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn rv = r0 * _cos( phi ); 3206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = cvFloor( rv ) * tn; 3216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i += cvFloor( phi1 ); 3226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( i >= 0 ); 3236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( i < rn * tn ); 3246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn caccum[i] = (uchar) (caccum[i] + ((i ^ iprev) != 0)); 3256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn iprev = i; 3266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( cmax < caccum[i] ) 3276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cmax = caccum[i]; 3286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* Starting additional analysis */ 3346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn count = 0; 3356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( ri = 0; ri < rn; ri++ ) 3366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( ti = 0; ti < tn; ti++ ) 3386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( caccum[ri * tn + ti > threshold] ) 3406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn count++; 3426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( count * 100 > rn * tn ) 3476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvHoughLinesStandard( img, rho, theta, threshold, lines, linesMax ); 3496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 3506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( buffer = (uchar *) cvAlloc(srn * stn + 2)); 3536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn mcaccum = buffer + 1; 3546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn count = 0; 3566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( ri = 0; ri < rn; ri++ ) 3576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( ti = 0; ti < tn; ti++ ) 3596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( caccum[ri * tn + ti] > threshold ) 3616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn count++; 3636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( mcaccum, 0, sfn * sizeof( uchar )); 3646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( index = 0; index < fn; index++ ) 3666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int ti2; 3686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float r0; 3696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn yc = (float) y[index] + 0.5f; 3716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn xc = (float) x[index] + 0.5f; 3726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* Update the accumulator */ 3746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn t = (float) fabs( cvFastArctan( yc, xc ) * d2r ); 3756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn r = (float) sqrt( (double)xc * xc + (double)yc * yc ) * isrho; 3766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ti0 = cvFloor( (t + Pi * 0.5f) * istheta ); 3776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ti2 = (ti * stn - ti0) * 5; 3786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn r0 = (float) ri *srn; 3796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( ti1 = 0 /*, phi = ti*theta - Pi/2 - t */ ; ti1 < stn; ti1++, ti2 += 5 3816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /*phi += stheta */ ) 3826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /*rv = r*_cos(phi) - r0; */ 3846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn rv = r * sinTable[(int) (abs( ti2 ))] - r0; 3856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = cvFloor( rv ) * stn + ti1; 3866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = CV_IMAX( i, -1 ); 3886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = CV_IMIN( i, sfn ); 3896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn mcaccum[i]++; 3906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( i >= -1 ); 3916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( i <= sfn ); 3926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* Find peaks in maccum... */ 3966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( index = 0; index < sfn; index++ ) 3976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = 0; 3996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pos = h_get_tail_pos__index( list ); 4006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( h_get_prev__index( &pos )->value < mcaccum[index] ) 4016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn vi.value = mcaccum[index]; 4036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn vi.rho = index / stn * srho + ri * rho; 4046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn vi.theta = index % stn * stheta + ti * theta - halfPi; 4056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( h_is_pos__index( pos )) 4066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( h_get__index( pos )->value > mcaccum[index] ) 4086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn h_insert_after__index( list, pos, &vi ); 4106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( h_get_count__index( list ) > linesMax ) 4116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn h_remove_tail__index( list ); 4136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 4156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn h_get_prev__index( &pos ); 4176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !h_is_pos__index( pos )) 4196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn h_add_head__index( list, &vi ); 4216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( h_get_count__index( list ) > linesMax ) 4226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn h_remove_tail__index( list ); 4246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pos = h_get_head_pos__index( list ); 4336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( h_get_count__index( list ) == 1 ) 4346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( h_get__index( pos )->rho < 0 ) 4366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn h_clear_list__index( list ); 4386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 4416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( h_is_pos__index( pos )) 4436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvLinePolar line; 4456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pindex = h_get__index( pos ); 4466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( pindex->rho < 0 ) 4476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* This should be the last element... */ 4496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn h_get_next__index( &pos ); 4506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( !h_is_pos__index( pos )); 4516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 4526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn line.rho = pindex->rho; 4546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn line.angle = pindex->theta; 4556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( lines, &line ); 4566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( lines->total >= linesMax ) 4586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 4596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn h_get_next__index( &pos ); 4606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 4646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn h_destroy_list__index( list ); 4666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &sinTable ); 4676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &x ); 4686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &y ); 4696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &caccum ); 4706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &buffer ); 4716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 4726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/****************************************************************************************\ 4756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn* Probabilistic Hough Transform * 4766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\****************************************************************************************/ 4776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#if defined WIN64 && defined EM64T && _MSC_VER == 1400 && !defined CV_ICC 4796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#pragma optimize("",off) 4806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#endif 4816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void 4836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvHoughLinesProbabalistic( CvMat* image, 4846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float rho, float theta, int threshold, 4856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int lineLength, int lineGap, 4866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq *lines, int linesMax ) 4876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 4886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat* accum = 0; 4896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat* mask = 0; 4906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat* trigtab = 0; 4916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage* storage = 0; 4926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "icvHoughLinesProbalistic" ); 4946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 4966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq* seq; 4986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeqWriter writer; 4996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int width, height; 5006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int numangle, numrho; 5016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float ang; 5026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int r, n, count; 5036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint pt; 5046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float irho = 1 / rho; 5056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvRNG rng = cvRNG(-1); 5066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const float* ttab; 5076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn uchar* mdata0; 5086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ASSERT( CV_IS_MAT(image) && CV_MAT_TYPE(image->type) == CV_8UC1 ); 5106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn width = image->cols; 5126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn height = image->rows; 5136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn numangle = cvRound(CV_PI / theta); 5156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn numrho = cvRound(((width + height) * 2 + 1) / rho); 5166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( accum = cvCreateMat( numangle, numrho, CV_32SC1 )); 5186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( mask = cvCreateMat( height, width, CV_8UC1 )); 5196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( trigtab = cvCreateMat( 1, numangle, CV_32FC2 )); 5206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvZero( accum ); 5216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( storage = cvCreateMemStorage(0) ); 5236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( ang = 0, n = 0; n < numangle; ang += theta, n++ ) 5256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn trigtab->data.fl[n*2] = (float)(cos(ang) * irho); 5276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn trigtab->data.fl[n*2+1] = (float)(sin(ang) * irho); 5286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ttab = trigtab->data.fl; 5306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn mdata0 = mask->data.ptr; 5316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( cvStartWriteSeq( CV_32SC2, sizeof(CvSeq), sizeof(CvPoint), storage, &writer )); 5336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // stage 1. collect non-zero image points 5356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( pt.y = 0, count = 0; pt.y < height; pt.y++ ) 5366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const uchar* data = image->data.ptr + pt.y*image->step; 5386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn uchar* mdata = mdata0 + pt.y*width; 5396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( pt.x = 0; pt.x < width; pt.x++ ) 5406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( data[pt.x] ) 5426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn mdata[pt.x] = (uchar)1; 5446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( pt, writer ); 5456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 5476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn mdata[pt.x] = 0; 5486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn seq = cvEndWriteSeq( &writer ); 5526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn count = seq->total; 5536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // stage 2. process all the points in random order 5556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( ; count > 0; count-- ) 5566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // choose random point out of the remaining ones 5586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int idx = cvRandInt(&rng) % count; 5596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int max_val = threshold-1, max_n = 0; 5606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint* pt = (CvPoint*)cvGetSeqElem( seq, idx ); 5616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint line_end[2] = {{0,0}, {0,0}}; 5626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float a, b; 5636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int* adata = accum->data.i; 5646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, j, k, x0, y0, dx0, dy0, xflag; 5656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int good_line; 5666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const int shift = 16; 5676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = pt->y; 5696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn j = pt->x; 5706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // "remove" it by overriding it with the last element 5726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *pt = *(CvPoint*)cvGetSeqElem( seq, count-1 ); 5736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // check if it has been excluded already (i.e. belongs to some other line) 5756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !mdata0[i*width + j] ) 5766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 5776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // update accumulator, find the most probable line 5796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( n = 0; n < numangle; n++, adata += numrho ) 5806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn r = cvRound( j * ttab[n*2] + i * ttab[n*2+1] ); 5826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn r += (numrho - 1) / 2; 5836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int val = ++adata[r]; 5846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( max_val < val ) 5856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn max_val = val; 5876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn max_n = n; 5886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // if it is too "weak" candidate, continue with another point 5926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( max_val < threshold ) 5936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 5946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // from the current point walk in each direction 5966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // along the found line and extract the line segment 5976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn a = -ttab[max_n*2+1]; 5986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn b = ttab[max_n*2]; 5996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn x0 = j; 6006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn y0 = i; 6016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( fabs(a) > fabs(b) ) 6026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn xflag = 1; 6046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx0 = a > 0 ? 1 : -1; 6056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy0 = cvRound( b*(1 << shift)/fabs(a) ); 6066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn y0 = (y0 << shift) + (1 << (shift-1)); 6076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 6096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn xflag = 0; 6116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy0 = b > 0 ? 1 : -1; 6126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx0 = cvRound( a*(1 << shift)/fabs(b) ); 6136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn x0 = (x0 << shift) + (1 << (shift-1)); 6146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( k = 0; k < 2; k++ ) 6176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int gap = 0, x = x0, y = y0, dx = dx0, dy = dy0; 6196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( k > 0 ) 6216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = -dx, dy = -dy; 6226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // walk along the line using fixed-point arithmetics, 6246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // stop at the image border or in case of too big gap 6256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( ;; x += dx, y += dy ) 6266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn uchar* mdata; 6286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i1, j1; 6296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( xflag ) 6316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn j1 = x; 6336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i1 = y >> shift; 6346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 6366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn j1 = x >> shift; 6386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i1 = y; 6396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( j1 < 0 || j1 >= width || i1 < 0 || i1 >= height ) 6426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 6436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn mdata = mdata0 + i1*width + j1; 6456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // for each non-zero point: 6476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // update line end, 6486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // clear the mask element 6496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // reset the gap 6506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( *mdata ) 6516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn gap = 0; 6536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn line_end[k].y = i1; 6546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn line_end[k].x = j1; 6556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( ++gap > lineGap ) 6576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 6586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn good_line = abs(line_end[1].x - line_end[0].x) >= lineLength || 6626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn abs(line_end[1].y - line_end[0].y) >= lineLength; 6636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( k = 0; k < 2; k++ ) 6656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int x = x0, y = y0, dx = dx0, dy = dy0; 6676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( k > 0 ) 6696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = -dx, dy = -dy; 6706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // walk along the line using fixed-point arithmetics, 6726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // stop at the image border or in case of too big gap 6736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( ;; x += dx, y += dy ) 6746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn uchar* mdata; 6766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i1, j1; 6776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( xflag ) 6796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn j1 = x; 6816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i1 = y >> shift; 6826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 6846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn j1 = x >> shift; 6866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i1 = y; 6876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn mdata = mdata0 + i1*width + j1; 6906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // for each non-zero point: 6926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // update line end, 6936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // clear the mask element 6946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // reset the gap 6956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( *mdata ) 6966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( good_line ) 6986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn adata = accum->data.i; 7006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( n = 0; n < numangle; n++, adata += numrho ) 7016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn r = cvRound( j1 * ttab[n*2] + i1 * ttab[n*2+1] ); 7036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn r += (numrho - 1) / 2; 7046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn adata[r]--; 7056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *mdata = 0; 7086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( i1 == line_end[k].y && j1 == line_end[k].x ) 7116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 7126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( good_line ) 7166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvRect lr = { line_end[0].x, line_end[0].y, line_end[1].x, line_end[1].y }; 7186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( lines, &lr ); 7196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( lines->total >= linesMax ) 7206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 7216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 7256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMat( &accum ); 7276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMat( &mask ); 7286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMat( &trigtab ); 7296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMemStorage( &storage ); 7306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 7316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#if defined WIN64 && defined EM64T && _MSC_VER == 1400 && !defined CV_ICC 7346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#pragma optimize("",on) 7356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#endif 7366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* Wrapper function for standard hough transform */ 7396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_IMPL CvSeq* 7406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvHoughLines2( CvArr* src_image, void* lineStorage, int method, 7416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double rho, double theta, int threshold, 7426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double param1, double param2 ) 7436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 7446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq* result = 0; 7456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvHoughLines" ); 7476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 7496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat stub, *img = (CvMat*)src_image; 7516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat* mat = 0; 7526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq* lines = 0; 7536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq lines_header; 7546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeqBlock lines_block; 7556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int lineType, elemSize; 7566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int linesMax = INT_MAX; 7576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int iparam1, iparam2; 7586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( img = cvGetMat( img, &stub )); 7606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !CV_IS_MASK_ARR(img)) 7626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadArg, "The source image must be 8-bit, single-channel" ); 7636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !lineStorage ) 7656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "NULL destination" ); 7666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( rho <= 0 || theta <= 0 || threshold <= 0 ) 7686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsOutOfRange, "rho, theta and threshold must be positive" ); 7696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( method != CV_HOUGH_PROBABILISTIC ) 7716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn lineType = CV_32FC2; 7736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn elemSize = sizeof(float)*2; 7746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 7766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn lineType = CV_32SC4; 7786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn elemSize = sizeof(int)*4; 7796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( CV_IS_STORAGE( lineStorage )) 7826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( lines = cvCreateSeq( lineType, sizeof(CvSeq), elemSize, (CvMemStorage*)lineStorage )); 7846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( CV_IS_MAT( lineStorage )) 7866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn mat = (CvMat*)lineStorage; 7886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !CV_IS_MAT_CONT( mat->type ) || (mat->rows != 1 && mat->cols != 1) ) 7906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadArg, 7916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn "The destination matrix should be continuous and have a single row or a single column" ); 7926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( CV_MAT_TYPE( mat->type ) != lineType ) 7946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadArg, 7956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn "The destination matrix data type is inappropriate, see the manual" ); 7966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( lines = cvMakeSeqHeaderForArray( lineType, sizeof(CvSeq), elemSize, mat->data.ptr, 7986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn mat->rows + mat->cols - 1, &lines_header, &lines_block )); 7996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn linesMax = lines->total; 8006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( cvClearSeq( lines )); 8016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 8036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadArg, "Destination is not CvMemStorage* nor CvMat*" ); 8056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn iparam1 = cvRound(param1); 8086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn iparam2 = cvRound(param2); 8096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn switch( method ) 8116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_HOUGH_STANDARD: 8136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( icvHoughLinesStandard( img, (float)rho, 8146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (float)theta, threshold, lines, linesMax )); 8156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 8166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_HOUGH_MULTI_SCALE: 8176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( icvHoughLinesSDiv( img, (float)rho, (float)theta, 8186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn threshold, iparam1, iparam2, lines, linesMax )); 8196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 8206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_HOUGH_PROBABILISTIC: 8216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( icvHoughLinesProbabalistic( img, (float)rho, (float)theta, 8226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn threshold, iparam1, iparam2, lines, linesMax )); 8236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 8246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn default: 8256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadArg, "Unrecognized method id" ); 8266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( mat ) 8296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( mat->cols > mat->rows ) 8316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn mat->cols = lines->total; 8326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 8336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn mat->rows = lines->total; 8346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 8366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn result = lines; 8386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 8416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return result; 8436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 8446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/****************************************************************************************\ 8476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn* Circle Detection * 8486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\****************************************************************************************/ 8496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void 8516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvHoughCirclesGradient( CvMat* img, float dp, float min_dist, 8526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int min_radius, int max_radius, 8536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int canny_threshold, int acc_threshold, 8546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq* circles, int circles_max ) 8556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 8566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const int SHIFT = 10, ONE = 1 << SHIFT, R_THRESH = 30; 8576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat *dx = 0, *dy = 0; 8586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat *edges = 0; 8596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat *accum = 0; 8606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int* sort_buf = 0; 8616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat* dist_buf = 0; 8626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage* storage = 0; 8636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "icvHoughCirclesGradient" ); 8656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 8676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int x, y, i, j, center_count, nz_count; 8696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int rows, cols, arows, acols; 8706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int astep, *adata; 8716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float* ddata; 8726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq *nz, *centers; 8736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float idp, dr; 8746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeqReader reader; 8756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( edges = cvCreateMat( img->rows, img->cols, CV_8UC1 )); 8776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( cvCanny( img, edges, MAX(canny_threshold/2,1), canny_threshold, 3 )); 8786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( dx = cvCreateMat( img->rows, img->cols, CV_16SC1 )); 8806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( dy = cvCreateMat( img->rows, img->cols, CV_16SC1 )); 8816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( cvSobel( img, dx, 1, 0, 3 )); 8826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( cvSobel( img, dy, 0, 1, 3 )); 8836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dp < 1.f ) 8856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dp = 1.f; 8866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn idp = 1.f/dp; 8876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( accum = cvCreateMat( cvCeil(img->rows*idp)+2, cvCeil(img->cols*idp)+2, CV_32SC1 )); 8886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( cvZero(accum)); 8896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( storage = cvCreateMemStorage() ); 8916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( nz = cvCreateSeq( CV_32SC2, sizeof(CvSeq), sizeof(CvPoint), storage )); 8926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( centers = cvCreateSeq( CV_32SC1, sizeof(CvSeq), sizeof(int), storage )); 8936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn rows = img->rows; 8956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cols = img->cols; 8966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn arows = accum->rows - 2; 8976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn acols = accum->cols - 2; 8986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn adata = accum->data.i; 8996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn astep = accum->step/sizeof(adata[0]); 9006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( y = 0; y < rows; y++ ) 9026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const uchar* edges_row = edges->data.ptr + y*edges->step; 9046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const short* dx_row = (const short*)(dx->data.ptr + y*dx->step); 9056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const short* dy_row = (const short*)(dy->data.ptr + y*dy->step); 9066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( x = 0; x < cols; x++ ) 9086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float vx, vy; 9106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int sx, sy, x0, y0, x1, y1, r, k; 9116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint pt; 9126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn vx = dx_row[x]; 9146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn vy = dy_row[x]; 9156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !edges_row[x] || (vx == 0 && vy == 0) ) 9176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 9186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( fabs(vx) < fabs(vy) ) 9206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sx = cvRound(vx*ONE/fabs(vy)); 9226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sy = vy < 0 ? -ONE : ONE; 9236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 9256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( vx != 0 ); 9276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sy = cvRound(vy*ONE/fabs(vx)); 9286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sx = vx < 0 ? -ONE : ONE; 9296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn x0 = cvRound((x*idp)*ONE) + ONE + (ONE/2); 9326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn y0 = cvRound((y*idp)*ONE) + ONE + (ONE/2); 9336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( k = 0; k < 2; k++ ) 9356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn x0 += min_radius * sx; 9376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn y0 += min_radius * sy; 9386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( x1 = x0, y1 = y0, r = min_radius; r <= max_radius; x1 += sx, y1 += sy, r++ ) 9406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int x2 = x1 >> SHIFT, y2 = y1 >> SHIFT; 9426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( (unsigned)x2 >= (unsigned)acols || 9436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (unsigned)y2 >= (unsigned)arows ) 9446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 9456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn adata[y2*astep + x2]++; 9466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn x0 -= min_radius * sx; 9496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn y0 -= min_radius * sy; 9506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sx = -sx; sy = -sy; 9516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt.x = x; pt.y = y; 9546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( nz, &pt ); 9556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nz_count = nz->total; 9596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !nz_count ) 9606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 9616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( y = 1; y < arows - 1; y++ ) 9636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( x = 1; x < acols - 1; x++ ) 9656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int base = y*(acols+2) + x; 9676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( adata[base] > acc_threshold && 9686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn adata[base] > adata[base-1] && adata[base] > adata[base+1] && 9696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn adata[base] > adata[base-acols-2] && adata[base] > adata[base+acols+2] ) 9706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush(centers, &base); 9716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn center_count = centers->total; 9756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !center_count ) 9766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 9776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( sort_buf = (int*)cvAlloc( MAX(center_count,nz_count)*sizeof(sort_buf[0]) )); 9796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvCvtSeqToArray( centers, sort_buf ); 9806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvHoughSortDescent32s( sort_buf, center_count, adata ); 9826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvClearSeq( centers ); 9836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPushMulti( centers, sort_buf, center_count ); 9846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( dist_buf = cvCreateMat( 1, nz_count, CV_32FC1 )); 9866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ddata = dist_buf->data.fl; 9876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dr = dp; 9896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_dist = MAX( min_dist, dp ); 9906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_dist *= min_dist; 9916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < centers->total; i++ ) 9936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int ofs = *(int*)cvGetSeqElem( centers, i ); 9956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn y = ofs/(acols+2) - 1; 9966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn x = ofs - (y+1)*(acols+2) - 1; 9976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float cx = (float)(x*dp), cy = (float)(y*dp); 9986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int start_idx = nz_count - 1; 9996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float start_dist, dist_sum; 10006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float r_best = 0, c[3]; 10016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int max_count = R_THRESH; 10026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < circles->total; j++ ) 10046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float* c = (float*)cvGetSeqElem( circles, j ); 10066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( (c[0] - cx)*(c[0] - cx) + (c[1] - cy)*(c[1] - cy) < min_dist ) 10076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 10086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( j < circles->total ) 10116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 10126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvStartReadSeq( nz, &reader ); 10146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < nz_count; j++ ) 10156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint pt; 10176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float _dx, _dy; 10186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( pt, reader ); 10196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn _dx = cx - pt.x; _dy = cy - pt.y; 10206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ddata[j] = _dx*_dx + _dy*_dy; 10216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sort_buf[j] = j; 10226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvPow( dist_buf, dist_buf, 0.5 ); 10256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvHoughSortDescent32s( sort_buf, nz_count, (int*)ddata ); 10266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dist_sum = start_dist = ddata[sort_buf[nz_count-1]]; 10286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = nz_count - 2; j >= 0; j-- ) 10296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float d = ddata[sort_buf[j]]; 10316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( d > max_radius ) 10336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 10346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( d - start_dist > dr ) 10366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float r_cur = ddata[sort_buf[(j + start_idx)/2]]; 10386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( (start_idx - j)*r_best >= max_count*r_cur || 10396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (r_best < FLT_EPSILON && start_idx - j >= max_count) ) 10406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn r_best = r_cur; 10426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn max_count = start_idx - j; 10436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn start_dist = d; 10456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn start_idx = j; 10466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dist_sum = 0; 10476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dist_sum += d; 10496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( max_count > R_THRESH ) 10526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn c[0] = cx; 10546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn c[1] = cy; 10556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn c[2] = (float)r_best; 10566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( circles, c ); 10576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( circles->total > circles_max ) 10586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 10596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 10636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMat( &dist_buf ); 10656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &sort_buf ); 10666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMemStorage( &storage ); 10676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMat( &edges ); 10686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMat( &dx ); 10696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMat( &dy ); 10706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMat( &accum ); 10716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 10726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_IMPL CvSeq* 10746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvHoughCircles( CvArr* src_image, void* circle_storage, 10756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int method, double dp, double min_dist, 10766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double param1, double param2, 10776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int min_radius, int max_radius ) 10786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 10796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq* result = 0; 10806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvHoughCircles" ); 10826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 10846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat stub, *img = (CvMat*)src_image; 10866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat* mat = 0; 10876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq* circles = 0; 10886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq circles_header; 10896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeqBlock circles_block; 10906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int circles_max = INT_MAX; 10916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int canny_threshold = cvRound(param1); 10926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int acc_threshold = cvRound(param2); 10936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( img = cvGetMat( img, &stub )); 10956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !CV_IS_MASK_ARR(img)) 10976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadArg, "The source image must be 8-bit, single-channel" ); 10986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !circle_storage ) 11006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "NULL destination" ); 11016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dp <= 0 || min_dist <= 0 || canny_threshold <= 0 || acc_threshold <= 0 ) 11036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsOutOfRange, "dp, min_dist, canny_threshold and acc_threshold must be all positive numbers" ); 11046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_radius = MAX( min_radius, 0 ); 11066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( max_radius <= 0 ) 11076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn max_radius = MAX( img->rows, img->cols ); 11086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( max_radius <= min_radius ) 11096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn max_radius = min_radius + 2; 11106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( CV_IS_STORAGE( circle_storage )) 11126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( circles = cvCreateSeq( CV_32FC3, sizeof(CvSeq), 11146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sizeof(float)*3, (CvMemStorage*)circle_storage )); 11156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( CV_IS_MAT( circle_storage )) 11176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn mat = (CvMat*)circle_storage; 11196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !CV_IS_MAT_CONT( mat->type ) || (mat->rows != 1 && mat->cols != 1) || 11216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MAT_TYPE(mat->type) != CV_32FC3 ) 11226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadArg, 11236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn "The destination matrix should be continuous and have a single row or a single column" ); 11246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( circles = cvMakeSeqHeaderForArray( CV_32FC3, sizeof(CvSeq), sizeof(float)*3, 11266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn mat->data.ptr, mat->rows + mat->cols - 1, &circles_header, &circles_block )); 11276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn circles_max = circles->total; 11286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( cvClearSeq( circles )); 11296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 11316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadArg, "Destination is not CvMemStorage* nor CvMat*" ); 11336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn switch( method ) 11366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_HOUGH_GRADIENT: 11386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( icvHoughCirclesGradient( img, (float)dp, (float)min_dist, 11396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_radius, max_radius, canny_threshold, 11406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn acc_threshold, circles, circles_max )); 11416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 11426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn default: 11436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadArg, "Unrecognized method id" ); 11446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( mat ) 11476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( mat->cols > mat->rows ) 11496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn mat->cols = circles->total; 11506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 11516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn mat->rows = circles->total; 11526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 11546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn result = circles; 11556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 11576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return result; 11596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 11606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* End of file. */ 1162