li-zhaoxi / aamed

Arc Adjacency Matrix based Fast Ellipse Detection

Arc Adjacency Matrix based Fast Ellipse Detection

We proposed a fast ellipse detection method based on arc adjacency matrix. We have successfully used this method in some applications, such as satellite tracking, UGV guidance and pose estimation.

😊The binaries for Matlab and Python can be downloaded from the latest release.

1 Compile our Codes

We have successfully applied AAMED to various platforms (Windows, Ubuntu, ARM). The codes used for different platforms may require some minor changes.

1.1 Windows

• OpenCV > 3.1.0
• VS 2015

You can add all .h and .cpp files into your project. Don't forget to config your project about OpenCV :).

main.cpp has given an example to detect ellipses from an image.

AAMED aamed(drows, dcols). drows (dcols) must be larger than the rows (cols) of all used images. Then, we can use aamed.run_FLED(imgG); to detect ellipses from multiple images.

Very important: Please check rows and cols of your input images are smaller than drows and dcols separately, otherwise, there will be some errors at class NODE_FC

1.2 Ubuntu

We use CMake to generate Makefile, then use make to compile our method. This way is only used for Ubuntu, not suitable for Windows.

cd AAMED/cmake-build
cmake ..
make 
./AAMED

1.3 Python

For Python, the OpenCV and NumPy packages are required.

Building

With the Anaconda distribution of Python (Windows and Linux) and the standard Python in Linux, building the library can be done in the following way:

cd python
python setup.py build_ext --inplace

Once built, the created library (Windows: .pyd, Linux: .so) can be placed anywhere.

If you are building on Windows without Anaconda, you must install OpenCV manually alongside the OpenCV Python package. (Make sure the versions are the same!) Then, in the setup.py file, the opencv_root variable should be set to the specified OpenCV installation location. Once this is done, you can continue to use the same commands above to build.

Note: for Windows without Anaconda, the opencv_world DLL should be together with the .pyd as well. Alternatively, if you do not want to copy the opencv_world DLL around, you can add the OpenCV bin location as a DLL directory at the beginning of your script. For example:

import os
os.add_dll_directory("D:/opencv/build/x64/vc14/bin")

Testing

To quickly test, test_aamed.py is provided.

python test_aamed.py

1.4 MATLAB

We have packaged AAMED, it can be used in MATLAB. AAMED needs OpenCV support. Note that if mexdestoryaamed(obj) is not called, the memory used in AAMED will remain in MATLAB all the time. Only restart matlab can clear the memory.

Install

You need to config OpenCV include path and library path in setup.m firstly. Then, you can run setup.m to compile mexAAMED, mexdestoryAAMED, mexdetectImagebyAAMED, mexSetAAMEDParameters.

Test

test_aamed.m provides an example to detect ellipses from an image.

obj = mexAAMED(540, 960); % AAMED only needs to be defined once
mexSetAAMEDParameters(obj, pi/3, 3.4, 0.77); % Set the parameters.

% This function can be used multiple times to detect ellipses from images
detElps = mexdetectImagebyAAMED(obj, img); 

mexdestoryAAMED(obj); %Free memory (very important).

2 Label Tool

we provide a tool to label ellipses (circles) from an image. This tool is based on MATLAB R2016. First, you need to run setup.m to compile mexElliFit. Then, you can run main.m to use this label tool.

3 AAMED Viewer

we proivide a tool to show critical data (edge contours, DP contours, arc contours, AAM and detected ellipses) in MATLAB. We use this tool to find bugs of AAMED and test functions.

You need to run setup.m to compile mexcvtBasicData, mexcvtRRect, mexcvtVVP, mexcvtAAM. Then you can use main.m to read DetailAAMED.aamed.

4 Nine Datasets

We have uploaded 9 datasets used in our paper to Baidu Cloud (Code: 7br2) and Google Drive.

5 Measure Tool

We have provided a tool that can be used to measure our method. Firstly, you need to run setup.m in measuretool/MeasureTools to build the mex files. Then, MeasureAllDatasets.m needs to be configured as described below. Finally, you can run MeasureAllDatasets.m to measure the used method.

• data_root_path: The root path of all datasets.
• dataset_name: The file names of used datasets. dataset_name is an array of cell, each element in it is a string that represents the dataset file name.
• gt_label contains the labels of corresponding datasets. Read_Ellipse_GT.m uses these labels to load ground-truth.
• methods_name is the file name that stores the results of used method.
• method_label is the label of corresponding method. Read_Ellipse_Results.m uses this label to load detection results.

The sample output of MeasureAllDatasets.m is as following.

Evaluating dataset: Satellite Images - Dataset Meng #2
Precision: 80.9524%,  Recall: 85%,  F-measure: 82.9268%. 
Average detected time: 2.6065 ms.

6 How to Make your Datasets

The format of ellipse dataset is as follows.

If you want to make a new dataset, you can put the collected images into the file images. Then, the ground-truth files that are generated by labeltool can be put into the file gt. Finally, you need to create the file imagenames.txt that contains all image names.

If you have any questions, please contact me ([email protected]) or create an issue.

aamed's Issues

Faster initialize Node_FC

code：
//nodeMat[0] = pow(double(x), 4) / pow(scale, 4); // x^4
//nodeMat[1] = 2 * pow(double(x), 3)y / pow(scale, 4); // 2 * x^3 * y = 2xy * x^2 = [5][8]
//nodeMat[2] = double(x)xyy / pow(scale, 4); // x^2 * y^2 = [5] * [11]
//nodeMat[3] = 2 * pow(double(x), 3) / pow(scale, 3); // 2 * x^3 = [12][5]
//nodeMat[4] = 2 * double(x)xy / pow(scale, 3); // 2 * x^2 * y = [13][5]
//nodeMat[5] = double(x)x / (scalescale); // x^2
//nodeMat[6] = 2 * double(x)yyy / pow(scale, 4); // 2 * x * y^3 = [10]x
//nodeMat[7] = 4 * double(x)yy / pow(scale, 3); // 4 * x * y^2 = 2 * x * y * 2 * y = [13][8]
//nodeMat[8] = 2 * double(x)y / (scalescale); // 2 * x * y = [13]x
//nodeMat[9] = pow(double(y), 4) / pow(scale, 4); // y^4 = [11][11]
//nodeMat[10] = 2 * pow(double(y), 3) / pow(scale, 3); // 2 * y^3 = [13]*[11]
//nodeMat[11] = double(y)y / (scalescale); // y^2
//nodeMat[12] = 2 * double(x) / scale; // 2x
//nodeMat[13] = 2 * double(y) / scale; // 2y
//nodeMat[14] = 1;

	double xs = double(x) / scale;
	double ys = double(y) / scale;
	nodeMat[14] = 1;
	nodeMat[13] = 2 * ys;
	nodeMat[12] = 2 * xs;
	nodeMat[11] = ys * ys;
	nodeMat[10] = nodeMat[13] * nodeMat[11];
	nodeMat[9] = nodeMat[11] * nodeMat[11];
	nodeMat[8] = nodeMat[13] * xs;
	nodeMat[7] = nodeMat[13] * nodeMat[8];
	nodeMat[6] = nodeMat[10] * xs;
	nodeMat[5] = xs * xs;
	nodeMat[4] = nodeMat[5] * nodeMat[13];
	nodeMat[3] = nodeMat[5] * nodeMat[12];
	nodeMat[2] = nodeMat[5] * nodeMat[11];
	nodeMat[1] = nodeMat[5] * nodeMat[8];
	nodeMat[0] = nodeMat[5] * nodeMat[5];

About 4 times faster.

matlab comlipe error

hi, when i use Opencv3.1.0.

cmd_str = [cmd_str, '-I''D:\opencv3.1\opencv\build\include'' -L''D:\opencv3.1\opencv\build\x64\vc14\lib'' -lopencv_world310']

however, the errors:
(1) undefined reference to cv::Mat::t() const (2) undefined reference to cv::fastFree(void*)
(3) undefined reference to `cv::Mat::deallocate()

Why the code get different results for the same image?

I run your program using Python as follow:

from pyAAMED import pyAAMED
import cv2

imgC = cv2.imread('002_0038.jpg')
imgG = cv2.cvtColor(imgC, cv2.COLOR_BGR2GRAY)

aamed = pyAAMED(1000, 1000)
aamed.setParameters(3.1415926/3, 3.4,0.77)

res = aamed.run_AAMED(imgG)
print(res)
res = aamed.run_AAMED(imgG)
print(res)
res = aamed.run_AAMED(imgG)
print(res)

The output is:

[[119.57775   118.13536   188.85326   187.00667   -25.195826    0.9755703]]
[[119.57469  118.17392  188.82712  187.16432  -24.618874   0.98002 ]]
[[119.561386   118.19473    188.83266    187.21588    -24.959404   0.98063296]]

Why the three results are not the same?

The program may even give different numbers of ellipses for the same image. I wonder why.

We face the following errors while executing the setup.m program using MATLAB R2019b. Kindly suggest how to solve these issues

Building with 'MinGW64 Compiler (C++)'.
Error using mex
Cannot export mexFunction: symbol not defined
C:\Users\NITR\AppData\Local\Temp\mex_154556940944356_3936\mexElliFit.obj:mexElliFit.cpp:(.text+0x998):
undefined reference to cv::Mat::t() const' C:\Users\NITR\AppData\Local\Temp\mex_154556940944356_3936\mexElliFit.obj:mexElliFit.cpp:(.text+0x9ad): undefined reference to cv::Mat::inv(int) const'

Provide OPENCV version and Visual Studio version info in README.MD

I'm unable to compile the program in Codeblocks. I think the problem is regarding OCV version i'm using in CODEblocks

Ellipse size variable?

Hi, thank you for making this code available. i have it running very well on my images, however i notice that smaller ellipses are not found. Is there a variable set somewhere that filters ellipses by size?

Thanks

python comlipe error

Cannot open source file: '..\src\AAMBasedCombinations.cpp': No such file or directory

when i look into the file and find no AAMBasedCombinations.cpp indeed,is there something missing?

About Null Exception

the function "getlinkArcs‘’ in FLED.cpp causes exception all the time , why this happend?

Node_FC 写入权限冲突

您好，在Node_FC.h中28行，出现next_dot 异常，写入权限错误。

Segmentation Fault on some images

Some images seem to cause a seg fault. About half the jpegs I tested cause this.

It looks like it seg faults here. It looks like (data + idxdMove)->Location or (data + idxdFind)->Location is some erroneous values but not sure why this happens.

As an example, this image causes a seg fault

proper documentation

Can you please elaborate on how to fine tune the algorithm, there are no comments and the variable names aren't really that descriptive..
even after reading the IEEE paper you and 3 others have composed I can still barely understand the parameters for the AAMED function

please elaborate

Group.app的PosteriorArcsSearch2中，索引号是不是用错了

如下代码：

	// 验证是否满足第二个约束式
	idx_use = find_arc_idx*arcs_num;
	isValid = true;
	for (int i = 0; i < group_num; i++)
	{
		int tmpData_i = temp[i];

--------------->// check_val= Matrix[find_arc_idx, tmpData_i]
check_val = link_data[idx_use + tmpData_i];
if (check_val == 0) // L{i,k} ==0 ,there needs to use CASE_1 to varify whether L_{i,k} = -1.
{
-------------------->// 计算的是[point_idx, tmpData_i]
temp_val = CASE_1(_asrs_data + point_idx, _asrs_data + tmpData_i);
if (temp_val == -1)
{
-------------------------->// 赋值给了[find_arc_idx, tmpData_i]和[tmpData_i, point_idx]
_link_data[idx_use + tmpData_i] = _link_data[tmpData_i * arcs_num + point_idx] = -1;
isValid = false;
break;
}
}
else if (check_val == -1)
{
isValid = false;
break;
}
}

是不是搞错了，应该全部是find_arc_idx?

Sir, kindly suggest "how to solve the following issues"

We have successfully created mexElliFit.mexw64 from mexElliFit.cpp file. The mexElliFit.mexw64 is placed in the same location, where text_ellifit.m is stored. However, while executing text_ellifit.m program, the following error occurs.

Invalid MEX-file 'F:\LAPTOP\AAMED-master\labeltool\mexElliFit.mexw64': The specified module could not be found.

Error in test_ellifit (line 9)
res = mexElliFit([x(:),y(:)]);

Error with python building on Ubuntu

Hi. I am trying to build the python package but facing the following error, could you please help to avoid it? I use cython 3.0.10 and python 3.10.13.

AAMED-master/python$ python setup.py build_ext --inplace
running build_ext
Compiling pyAAMED.pyx because it changed.
[1/1] Cythonizing pyAAMED.pyx
/home/ubunter/miniconda3/envs/playground310/lib/python3.10/site-packages/Cython/Compiler/Main.py:381: FutureWarning: Cython directive 'language_level' not set, using '3str' for now (Py3). This has changed from earlier releases! File: /home/ubunter/Downloads/AAMED-master/python/pyAAMED.pyx
  tree = Parsing.p_module(s, pxd, full_module_name)

Error compiling Cython file:
------------------------------------------------------------
...
cdef class pyAAMED:
    cdef FLED* _fled;
    cdef int drows;
    cdef int dcols;
    def __cinit__(self, int drows, int dcols):
        self._fled = new FLED(drows, dcols)
                     ^
------------------------------------------------------------

pyAAMED.pyx:20:21: Operation only allowed in c++

Error compiling Cython file:
------------------------------------------------------------
...



    def release(self):
        #self._fled.release()
        del self._fled
        ^
------------------------------------------------------------

pyAAMED.pyx:42:8: Operation only allowed in c++
Traceback (most recent call last):
  File "/home/ubunter/Downloads/AAMED-master/python/setup.py", line 127, in <module>
    setup(
  File "/home/ubunter/miniconda3/envs/playground310/lib/python3.10/site-packages/setuptools/__init__.py", line 107, in setup
    return distutils.core.setup(**attrs)
  File "/home/ubunter/miniconda3/envs/playground310/lib/python3.10/site-packages/setuptools/_distutils/core.py", line 185, in setup
    return run_commands(dist)
  File "/home/ubunter/miniconda3/envs/playground310/lib/python3.10/site-packages/setuptools/_distutils/core.py", line 201, in run_commands
    dist.run_commands()
  File "/home/ubunter/miniconda3/envs/playground310/lib/python3.10/site-packages/setuptools/_distutils/dist.py", line 969, in run_commands
    self.run_command(cmd)
  File "/home/ubunter/miniconda3/envs/playground310/lib/python3.10/site-packages/setuptools/dist.py", line 1234, in run_command
    super().run_command(command)
  File "/home/ubunter/miniconda3/envs/playground310/lib/python3.10/site-packages/setuptools/_distutils/dist.py", line 988, in run_command
    cmd_obj.run()
  File "/home/ubunter/miniconda3/envs/playground310/lib/python3.10/site-packages/setuptools/_distutils/command/build_ext.py", line 345, in run
    self.build_extensions()
  File "/home/ubunter/Downloads/AAMED-master/python/setup.py", line 124, in build_extensions
    build_ext.build_extensions(self)
  File "/home/ubunter/miniconda3/envs/playground310/lib/python3.10/site-packages/setuptools/_distutils/command/build_ext.py", line 467, in build_extensions
    self._build_extensions_serial()
  File "/home/ubunter/miniconda3/envs/playground310/lib/python3.10/site-packages/setuptools/_distutils/command/build_ext.py", line 493, in _build_extensions_serial
    self.build_extension(ext)
  File "/home/ubunter/miniconda3/envs/playground310/lib/python3.10/site-packages/Cython/Distutils/build_ext.py", line 130, in build_extension
    new_ext = cythonize(
  File "/home/ubunter/miniconda3/envs/playground310/lib/python3.10/site-packages/Cython/Build/Dependencies.py", line 1154, in cythonize
    cythonize_one(*args)
  File "/home/ubunter/miniconda3/envs/playground310/lib/python3.10/site-packages/Cython/Build/Dependencies.py", line 1321, in cythonize_one
    raise CompileError(None, pyx_file)
Cython.Compiler.Errors.CompileError: pyAAMED.pyx

possible bug of Get_del_phi_max???

Hi, Thanks a lot for open sourcing your great work.
I am here to report a possible bug of Get_del_phi_max function.
I have read the paper "A Parameter Independent Line Fitting Method".
In your code of this function: Get_del_phi_max

return max_del_phi / s_pow_2;

Should this be return max_del_phi / s_pow_3;?
It is also ok to use return max_del_phi / s_pow_2;, but when you do the condition test if (dMax > dTol*s && pMax != 0), there is no need to multiply s.

This is my understanding of the paper "A Parameter Independent Line Fitting Method" and your implementation.

Looking forward to hear from you.

Ubuntu: ./AAMED OpenCV 3.1 "Assertion failed", core dumped

Hi. Thanks for sharing your software and writing instructions. I was wondering if you could advise me of an error that occurs when I try to execute AAMED.

On my Ubuntu system, I installed and built OpenCV 3.1.0 in ~/opencv-3.1.0/, which built to 100%.
Then I set my environment variable OpenCV_DIR to point to the build/ directory for OpenCV.
Then downloaded & built AAMED. But when I try to run it I get a failed assertion. Log follows:

$ git clone https://github.com/Li-Zhaoxi/AAMED.git
Cloning into 'AAMED'...
remote: Enumerating objects: 240, done.
remote: Counting objects: 100% (240/240), done.
remote: Compressing objects: 100% (177/177), done.
remote: Total 240 (delta 86), reused 209 (delta 59), pack-reused 0
Receiving objects: 100% (240/240), 1.04 MiB | 4.58 MiB/s, done.
Resolving deltas: 100% (86/86), done.

$ cd AAMED/cmake-build

$ cmake ..
-- The C compiler identification is GNU 10.2.0
-- The CXX compiler identification is GNU 10.2.0
-- Check for working C compiler: /usr/bin/cc
-- Check for working C compiler: /usr/bin/cc -- works
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Detecting C compile features
-- Detecting C compile features - done
-- Check for working CXX compiler: /usr/bin/c++
-- Check for working CXX compiler: /usr/bin/c++ -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Configuring done
-- Generating done
-- Build files have been written to: /home/shawley/Downloads/AAMED/cmake-build

$ make 
make[1]: Entering directory '/home/shawley/Downloads/AAMED/cmake-build'
make[2]: Entering directory '/home/shawley/Downloads/AAMED/cmake-build'
Scanning dependencies of target AAMED
make[2]: Leaving directory '/home/shawley/Downloads/AAMED/cmake-build'
make[2]: Entering directory '/home/shawley/Downloads/AAMED/cmake-build'
[  6%] Building CXX object CMakeFiles/AAMED.dir/src/main.cpp.o
[ 13%] Building CXX object CMakeFiles/AAMED.dir/src/adaptApproximateContours.cpp.o
[ 20%] Building CXX object CMakeFiles/AAMED.dir/src/adaptApproxPolyDP.cpp.o
[ 26%] Building CXX object CMakeFiles/AAMED.dir/src/Contours.cpp.o
[ 33%] Building CXX object CMakeFiles/AAMED.dir/src/EllipseNonMaximumSuppression.cpp.o
[ 40%] Building CXX object CMakeFiles/AAMED.dir/src/FLED.cpp.o
[ 46%] Building CXX object CMakeFiles/AAMED.dir/src/FLED_drawAndWriteFunctions.cpp.o
/home/shawley/Downloads/AAMED/src/FLED_drawAndWriteFunctions.cpp: In member function ‘void FLED::drawFSA_ArcContours()’:
/home/shawley/Downloads/AAMED/src/FLED_drawAndWriteFunctions.cpp:153:22: warning: ‘__builtin___sprintf_chk’ may write a terminating nul past the end of the destination [-Wformat-overflow=]
  153 |   sprintf(arcnum, "%d", i);
      |                      ^
In file included from /usr/include/stdio.h:866,
                 from /usr/include/c++/10/cstdio:42,
                 from /usr/include/c++/10/ext/string_conversions.h:43,
                 from /usr/include/c++/10/bits/basic_string.h:6535,
                 from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from /home/shawley/Downloads/AAMED/src/FLED.h:3,
                 from /home/shawley/Downloads/AAMED/src/FLED_drawAndWriteFunctions.cpp:1:
/usr/include/x86_64-linux-gnu/bits/stdio2.h:38:34: note: ‘__builtin___sprintf_chk’ output between 2 and 11 bytes into a destination of size 10
   38 |   return __builtin___sprintf_chk (__s, __USE_FORTIFY_LEVEL - 1,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   39 |       __bos (__s), __fmt, __va_arg_pack ());
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[ 53%] Building CXX object CMakeFiles/AAMED.dir/src/FLED_PrivateFunctions.cpp.o
[ 60%] Building CXX object CMakeFiles/AAMED.dir/src/Group.cpp.o
[ 66%] Building CXX object CMakeFiles/AAMED.dir/src/LinkMatrix.cpp.o
[ 73%] Building CXX object CMakeFiles/AAMED.dir/src/Node_FC.cpp.o
[ 80%] Building CXX object CMakeFiles/AAMED.dir/src/Segmentation.cpp.o
[ 86%] Building CXX object CMakeFiles/AAMED.dir/src/Validation.cpp.o
[ 93%] Building CXX object CMakeFiles/AAMED.dir/src/FLED_Initialization.cpp.o
[100%] Linking CXX executable AAMED
make[2]: Leaving directory '/home/shawley/Downloads/AAMED/cmake-build'
[100%] Built target AAMED
make[1]: Leaving directory '/home/shawley/Downloads/AAMED/cmake-build'

$ ./AAMED 
OpenCV Error: Assertion failed (scn == 3 || scn == 4) in ipp_cvtColor, file /home/shawley/opencv-3.1.0/modules/imgproc/src/color.cpp, line 7456
terminate called after throwing an instance of 'cv::Exception'
  what():  /home/shawley/opencv-3.1.0/modules/imgproc/src/color.cpp:7456: error: (-215) scn == 3 || scn == 4 in function ipp_cvtColor

Aborted (core dumped)

Any suggestions on how to recover from this? Thanks.

(P.S.- The only binaries for opencv-dev for my Ubuntu 20.10 system is OpenCV 4. So to get version 3.1 instead, I had to build it from source.)

Bug of ground truth?

Sorry for disturb.

Several issues:

1. Read_Ellipse_GT contains some bugs. In the dataset, you name text files in the gt folder with a prefix like 'gt_', so the code should be like fid_gt = fopen([gt_path,'gt_',imgname{i},'.txt'],'r');.

2. About the ground truth itself, for the dataset 'Prasad Images - Dataset Prasad', if I plot gt ellipses out, I got the following figure
   

It seems not correct.

Any comments will be appreciated.