Problem 42616. Detect circles in images

Created by Matthew Eicholtz

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given an image and a target radius range, specified as [rmin rmax], find circles in the image. Your function should output an m-by-2 array of circle centers (x,y positions in the image) and an m-by-1 vector of radii corresponding to m circles.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Your detector will be judged on its</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Precision_and_recall\"><w:r><w:t>precision and recall</w:t></w:r></w:hyperlink><w:r><w:t>. The recall must be 0.75 or higher and the precision must be 0.5 or higher to pass.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For example, if an image has 4 true circles, you can miss at most 1 of the circles and have at most 4 false detections.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Additional notes:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Circles can be brighter or darker than the background.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>A detection is considered a match if its position and radius is within 5 pixels of a true circle.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>To make things easier, the target number of circles (N) is provided as an input. Pat yourself on the back if you do not need it.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

93 Solutions
11 Solvers

Last Solution submitted on Jun 10, 2020

Last 200 Solutions

Problem Comments

3 Comments

3 Comments

LY Cao on 18 Sep 2015

PDIST2 is not available here, please fix it

Matthew Eicholtz on 18 Sep 2015

Thanks for bringing this to my attention LY Cao. The test suite has been fixed.

Rafael S.T. Vieira on 10 Jun 2020

Fair warning to the challenger, we need to do some preprocessing for each image. There are black and white, grayscale, and color images within the test case set. I learned a lot from this problem, however...I found it very unsettling that I could not use functions from the image processing toolbox (I had to implement the Circle Hough transform myself).
Imho, the required precision should have been smaller: 5-pixel distance is absurd when one has rubber bands in an image that are not perfect circles. Or, at least, the test cases should allow that we return any number of circles and radii (it is easy to test if the desired circles are within the returned results).

Solution Comments

Solution 773489

2 Comments

2 Comments

Alfonso Nieto-Castanon on 8 Nov 2015

100% precision/recall, but using N so no pat in the back for me

Rafael S.T. Vieira on 10 Jun 2020

I've got precision 100% for most of the test cases. Colored images were the hardest.

Solution 772610

1 Comment

1 Comment

Jan Orwat on 6 Nov 2015

Combination of LY Cao's and mine code. 98.5% precision and recall in total (one circle in test 4 didn't fit in tolerance), without using N. That was fun :)

Problem Recent Solvers11

Problem Tags

circle detection hough transform image processing

Problem 42616. Detect circles in images

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers11

Suggested Problems

More from this Author44

Problem Tags

Problem 42616. Detect circles in images

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers11

Suggested Problems

More from this Author44

Problem Tags

Players