An Approach To Rectangle Detection Based On Spectral Clustering And Genetic Algorithm

In the image recognition system, in order to extract higher level of information for further analysis and detection, it's necessary to find a specific object or interesting region from the image. Rectangle as one of the most common man-made shapes, detection of it has a wide application. It may be used in computer vision applications such as recognizing license plates of cars, and military applications such as extracting buildings from satellite remote sensing images. It can also be applied in the automatic detection of particles with rectangular shapes by cryo-electron microscopy. Rectangles arise in scenarios where there are doors, windows or even posters and traffic signs, which can be used as localization landmarks. Detecting and recognizing them will enable the robot to lower the uncertainty bounds in its self-estimated position.An approach based on the use of spectral clustering and genetic algorithm to detect rectangles in images is presented in this paper(SCGA). The proposed approach tries to find the best sets of vertices of rectangles in the image. The method firstly applies edge detection on the input image and obtains the edge map; secondly, it performs line detection to the edge map and obtains all straight line segments; thirdly, the method uses corner detection to get the vertices of potential rectangles in the input image. Individuals in the proposed algorithm consist of four genes and each gene represents a vertex of the rectangle. Fitness scores are estimated according to the evidence of four edges presence and the extent of four angles near to 90°. Individuals with higher fitness scores are more likely to be selected and produce new generation by crossover and mutation operation. The approach obtains the optimal solution by several selection, crossover and mutation operations. In order to detect multiple rectangles, I use spectral clustering to calculate the number of rectangles in image and produce initial populations for each rectangle. Although the proposed approach performs a preprocessing step at first, the use of more elaborated edge, line and corner detector is not critical for it, the contribution of them is merely to reduce the search space and accelerate the convergence speed of the genetic algorithm. The proposed method can work fine without line or corner detection, only edge detection is necessary for it.For the test, I firstly design an efficiency and stability test on a synthetic image with a single rectangular. Secondly, in order to show the proposed approach does not over-rely on the preprocessing step and is insensitive to the parameters, I design three experiments. Thirdly, we perform a qualitative test to prove the multiple rectangles detection ability of our method. At last, we carry out an anti-interference test both on our method and a contour-detection-based one. Experimental results show that our method is efficient, stable, insensitive to the preprocess operations and has a strong anti-interference.