## Dec 5, 2013

### HowTo: Finding the Corners of a Rectangle using Image Magick and Perl

Problem:
I need to find the x and y coordinates of the corner of a rectangle in an image. The rectangle in the image is may either be rotated or not. The background of the rectangle in the image should be transparent if it is angled.
Solution:
(I dont know if such algorithm like this exists, but if there is non, lets just call it Foobaring Rectangle Corner Detector Algorithm, hehehe)

1. determine the width and height of the image
2. inspect each pixel from upper left to lower right.
3. check each pixel who has and opacity of < 1, get the coordinates with the biggest x, and get the coordinates of the pixel with the smallest y
4. inspect each pixel again, but this time, you start from lower right going to upper left.
5. check each pixel who has and opacity of < 1, get the coordinates with the smallest x, and get the coordinates of the pixel with the biggest y
6. there you have it, you now have the coordinates of each of the corners of the rectangle

Sample Code:
(written in perl, incomplete code, just showing you the idea, I used Image::Magick to access the pixels of the image)

my \$Ax = 0;
my \$Ay = 0;
my \$Bx = \$width;
my \$By = \$height;
my \$Cx = 0;
my \$Cy = \$height;
my \$Dx = 0;
my \$Dy = 0;
for(my \$x = 0;\$x<=\$width;\$x++){
for(my \$y = 0;\$y<=\$height;\$y++){
my \$pixel = \$im->GetPixel('x'=>\$x,'y'=>\$y,'channel'=>'opacity');
if(\$pixel < 1){
# big-x big-y
if(\$Ax <= \$x){
\$Ax = \$x;
\$Ay = \$y;
}
if(\$Cy >= \$y){
\$Cy = \$y;
\$Cx = \$x;
}
}
}
}
for(my \$x = \$width;\$x>=0;\$x--){
for(my \$y = \$height;\$y>=0;\$y--){
my \$pixel = \$im->GetPixel('x'=>\$x,'y'=>\$y,'channel'=>'opacity');
if(\$pixel < 1){
# small-x small-y
if(\$Bx >= \$x){
\$Bx = \$x;
\$By = \$y;
}
if(\$Dy <= \$y){
\$Dy = \$y;
\$Dx = \$x;
}
}
}
}
print "---- COORDINATES ----\n";
print "(\$Ax,\$Ay)\n";
print "(\$Bx,\$By)\n";
print "(\$Cx,\$Cy)\n";
print "(\$Dx,\$Dy)\n";

Notes:
1. The coordinates generated by this is code will not exactly give you a perfect rectangle, this is probably because of the anti-aliasing of the image. I think this will produce a perfect rectangle if used on an image without anti-alias and if the pixel count of the rectangle is a whole number. This is just a hunch, not proven yet.
2. This code is a bit slow because I iterated through all the pixels of the image 2 times. If you can recommend a better way of doing this, feel free to comment.
3. If you found circumstances where this is not applicable, please comment, thanks.