Hello,
I am working on a Python script to do some image processing and Optical Character Recognition of shipping containers. I'm trying to get a 4-sided shape (rectangle or nearly-rectangular trapezoid, depending on perspective) that represents the back of the container. I've written a color-filter/mask routine that is pretty good at isolating the container but it doesn't always yield that nice 4-sided shape I'm after. More often, it yields a bunch of these little (light blue) boxes:

(ignore green, black, and dark blue lines)




if I could stitch together:

• the top left corner of the top-most/left-most box
• the top right corner of the top-most/right-most box
• the bottom right corner of the bottom-most/right-most box
• the bottom left corner of the bottom-most/left-most box

... then I would have the shape I need. The problem is, I can't figure out how to decide whether any given shape is top-most/left-most, bottom-most/right-most box, or anything in between.

You can see my best result above, the yellow box. It is generated by taking the left-most, top-most, right-most, and bottom-most coordinates of all the little blue boxes, but it makes a perfect square, which is not what I need. I need that trapezoid so that I can turn it into a square (de-skew/anti-keystone) and remove the perspective error from the image.

When I try to make the code look at top-most/left-most, top-most/right-most, bottom-most/right-most, bottom-most/left-most coordinates instead of just left-most, top-most, right-most, and bottom-most, I get this (see the yellow "box," fallen so far from near-glory; if you can't see it, it's a long, skinny yellow triangle along the bottom of the container):




I spent a lot of time going over my code but ultimately decided it was all correct, but the principle behind it is flawed.
Below is the code which generated that messed up triangle if you're interested, but I don't think you need to understand Python or sift through my bad programming to give feedback here.
I'm looking for help on the mathematical aspect of the problem and the code is something I can figure out once I understand the math part. But, if it's easier to illustrate the answer with counter-code, I'll take whatever help I can get.

# Coordinates are pixels [x,y], as measured left to right and top to bottom.
# [0,0] = top left, [3024,4032] = bottom right of image
# Rectangles are specified starting at top-left, to top-right, to bottom-right, to bottom left
# Top left point starts out at bottom right
bigBox_x1 = image.shape[1] # (width of image (3024))
bigBox_y1 = image.shape[0] # (height of image (4032))
# Top right point starts out at bottom left
bigBox_x2 = 0
bigBox_y2 = image.shape[0] # (height of image (4032))
# bottom right point starts out at top left
bigBox_x3 = 0
bigBox_y3 = 0
# bottom left point starts out at top right
bigBox_x4 = image.shape[1] # (width of image (3024))
bigBox_y4 = 0
bigBox = np.int0([[bigBox_x1,bigBox_y1],[bigBox_x2,bigBox_y2],[bigBox_x3,bigBox_y3],[bigBox_x4,bigBox_y4]])

for smallBox in boxList:
    print(smallBox)
    # big box is stretching up and to the left
    # evaluate upper left corner of small box.
    # is it Left-er than than current top-left?
    # Is it higher than current top-left?
    if smallBox[0][0] < bigBox[0][0]: # bigBox_x1 starts at image width (3024) and gets incrementally decreased
        # Ok, it's left-er than current top left. But is it higher than current top left?
        if smallBox[0][1] < bigBox[0][1]:# bigBox_y1 starts at image height (4032) and gets incrementally decreased
            # if so, set its top-left as our new top-left:
            bigBox[0][0] = smallBox[0][0]
            bigBox[0][1] = smallBox[0][1]
            print("new top left:",[bigBox[0][0],bigBox[0][1]])
    # big box is stretching down and to the left.
    # evaluate lower left corner of small box.
    # is it Left-er than than current bottom-left?
    # Is it lower than current bottom-left?
    if smallBox[3][0] < bigBox[3][0]:# bigBox_x4 starts at image width (3024) and gets incrementally decreased
        # Ok, it's left-er than current bottom left. But is it lower than current bottom left?
        if smallBox[3][1] > bigBox[3][1]:# bigBox_y4 starts at 0 and gets incrementally increased
            # if so, set its bottom-left as our new bottom-left:
            bigBox[3][1] = smallBox[3][1]
            bigBox[3][0] = smallBox[3][0]
            print("new bottom left:",[bigBox[3][0],bigBox[3][1]])
    # big box is stretching up and to the right.
    # evaluate upper right corner of small box.
    # is it right-er than than current top-right?
    # Is it higher than current top-right?
    if smallBox[1][0] > bigBox[1][0]:# bigBox_x2 starts at 0 and gets incrementally increased
        # Ok, it's right-er than current top right. But is it higher than current top right?
        if smallBox[1][1] < bigBox[1][1]:# bigBox_y2 starts at image height (4032) and gets incrementally decreased
            # if so, set its top-right as our new top-right:
            bigBox[1][1] = smallBox[1][1]
            bigBox[1][0] = smallBox[1][0]
            print("new top right:",[bigBox[1][0],bigBox[1][1]])
    # big box is stretching down and to the right.
    # evaluate lower right corner of small box.
    # is it right-er than than current bottom-right?
    # Is it lower than current bottom-right?
    if smallBox[2][0] > bigBox[2][0] :# bigBox_x3 starts at 0 and gets incrementally increased
        # Ok, it's right-er than current bottom right. But is it lower than current bottom right?
        # if so, set its bottom-right as our new bottom-right:
        if smallBox[2][1] > bigBox[2][1]:# bigBox_y3 starts at 0 and gets incrementally increased
            bigBox[2][1] = smallBox[2][1]
            bigBox[2][0] = smallBox[2][0]
            print("new bottom right:",[bigBox[2][0],bigBox[2][1]])
    print("\n")

Thanks!

 

I think your problem comes down to what, exactly, is the "top-most/left-most" box? That is very ambiguous? How can a box be top-most/left-most if there is another box that is further to the left? Or another box that is higher?

Consider the following:


Which box do you want to be identified as the "top-most/left-most" box?

Probably B, right?

Yet B is neither the top-most nor the left-most box, so whatever algorithm you use to identify it has to allow for that possibility.

I can think of a few ways to try to approach finding a bounding (or roughly bounding) trapezoid. One would be start with the large bounding rectangle you identified initially and then define a smaller rectangle in each corner of some appropriate size -- maybe just dividing big rectangle in four is enough, or perhaps you use strips that are some fraction of the dimension. The you identify the (top,left) corner in the top-left region and so on to get your four corners.

Using your first picture above, the red boxes are (very roughly) the corners after dividing the yellow box into four rows and four columns. Within each red box, the extreme coordinates are used to identify the corner for the trapezoid, which is the blue shape.


I don't know how fragile this approach is, but it might be worth a shot.

 

Another idea - start with your yellow rectangle. Each of the four yellow sides touches a blue box somewhere. For each side, keep this point fixed and rotate the line toward the opposite line until it hits another blue point. As the original line is parallel to your axes, calculating the angle to rotate the line to hit any other point is straightforward, simply choose the one that needs the smallest rotation. Finished.

 

Hola Stantor
Your containers are all in good shape? IOW, within ISO standards?

Those damaged (like when passing under bridges with not enough clearance) could get the rear header / corner casings / corner posts (even heavily) distorted. Door panels as well.

 

I think your problem comes down to what, exactly, is the "top-most/left-most" box? That is very ambiguous? How can a box be top-most/left-most if there is another box that is further to the left? Or another box that is higher?

Consider the following:

View attachment 276647
Which box do you want to be identified as the "top-most/left-most" box?

Probably B, right?

Yet B is neither the top-most nor the left-most box, so whatever algorithm you use to identify it has to allow for that possibility.

Yes! You understand the problem perfectly, and managed to describe it better than I did, in a more concise manner. Thank you.

I can think of a few ways to try to approach finding a bounding (or roughly bounding) trapezoid. One would be start with the large bounding rectangle you identified initially and then define a smaller rectangle in each corner of some appropriate size -- maybe just dividing big rectangle in four is enough, or perhaps you use strips that are some fraction of the dimension. The you identify the (top,left) corner in the top-left region and so on to get your four corners.

Using your first picture above, the red boxes are (very roughly) the corners after dividing the yellow box into four rows and four columns. Within each red box, the extreme coordinates are used to identify the corner for the trapezoid, which is the blue shape.

View attachment 276648
I don't know how fragile this approach is, but it might be worth a shot.

I need to ruminate on this a bit. I feel like there's something to it that I'm missing. Per my current level of comprehension, it seems like I would be taking the larger problem and splitting it into 4 smaller versions of that same problem.

 

Another idea - start with your yellow rectangle. Each of the four yellow sides touches a blue box somewhere. For each side, keep this point fixed and rotate the line toward the opposite line until it hits another blue point. As the original line is parallel to your axes, calculating the angle to rotate the line to hit any other point is straightforward, simply choose the one that needs the smallest rotation. Finished.

This is easy as pie if you're doing it on paper, but I can't think of an efficient way to do it programmatically. And it isn't guaranteed that it will find the the other corner. Consider this, (using @WBahn's image):

 

Hola Stantor
Your containers are all in good shape? IOW, within ISO standards?

Those damaged (like when passing under bridges with not enough clearance) could get the rear header / corner casings / corner posts (even heavily) distorted. Door panels as well.

Yes sir, all good containers, the best quality. These are having liners installed and being filled with blown-in pellet product. They must be absolutely watertight to prevent contamination of the product.

 

Unless someone comes along with a better idea in the next few hours, I think this is how I'm going to attack it: feed all the x-values and y-values into a histogram function, classifying them into 10-or-so "bins." For the x-values, the points at either end of the histogram should be representative of the left and right sides. For the y-values, the points at either end of the histogram should be representative of the top and bottom sides. Now cross-reference bin0 of the x-values to bin0 of the y-values, and if there is a single coordinate set common to both groups, that is the top-most/left-most corner. Then do the same for x-bin9 and y-bin0, x-bin9 and y-bin9, x-bin0 and y-bin9. If there is only one common coordinate set in each of these coordinate bins, then it should work fine. If there are more than one matches, we'll then it will take more work. Maybe re-run the algorithm with finer resolution of bins?

 

In my mind, I would treat the rectangular shapes at first as if they were points defined by the geometric center of each rectangle. Then I would sort said points along the X axis from the bottom up, and then along the Y axis from left to right. That way a list of points could be formed that would sequentially define a perimetric polygon. After that, the points that define the extreme vertices of said polygon could be found by calculating and finding the sharpest angles between sets of 3 points when analyzed sequentially either clockwise or counterclockwise.
Once the four pertinent points are found, the last step would be finding the corners of each rectangle to which they belong to that best fit the largest polygon you're trying to form.

 

In my mind, I would treat the rectangular shapes at first as if they were points defined by the geometric center of each rectangle. Then I would sort said points along the X axis from the bottom up, and then along the Y axis from left to right. That way a list of points could be formed that would sequentially define a perimetric polygon. After that, the points that define the extreme vertices of said polygon could be found by calculating and finding the sharpest angles between sets of 3 points when analyzed sequentially either clockwise or counterclockwise.
Once the four pertinent points are found, the last step would be finding the corners of each rectangle to which they belong to that best fit the largest polygon you're trying to form.

That's along the lines of what I proposed but simpler. The simpler the better, but since rectangles are sometimes nested it might fall victim to this:

Center-B is indeed Left-er and higher than center-D, but...

 

That's along the lines of what I proposed but simpler. The simpler the better, but since rectangles are sometimes nested it might fall victim to this:
View attachment 276693
Center-B is indeed Left-er and higher than center-D, but...

In that case, you'll need to add another analysis and discard the smaller rectangles within the larger ones. A good thing that I've observed is that the rectangles never seem to intersect.

 

These are having liners installed and being filled with blown-in pellet product. They must be absolutely watertight to prevent contamination of the product.

Why containers? Unless they are going on cargo ships. When working their pellets came to the plant in tank trailers and then the pellets were unloaded to silos. This was delivered a few times a week to keep up with production. This is a link to the trailers I'm talking about - https://www.mactrailer.com/pneumatic-tank-trailers.html

 

Why containers? Unless they are going on cargo ships. When working their pellets came to the plant in tank trailers and then the pellets were unloaded to silos. This was delivered a few times a week to keep up with production. This is a link to the trailers I'm talking about - https://www.mactrailer.com/pneumatic-tank-trailers.html

Yes, my employer has those trucks too (Bulk Trucks) for delivering large amounts domestically. But for overseas shipping, bulk orders go into lined containers. Smaller overseas orders go into bags on pallets, supersacks, or Gaylord boxes, and then into containers. Smaller domestic orders go into the same bags/sacks/boxes but are loaded onto a truck rather than into a container.

 

Heard of bulk carriers?

A common terminal could be shooting into holds more than 900 tns/hour per pipe.

Discharging with vacuvators could be done in 36 hrs for a bulk carrier with 31.000 tons.

It all depends what trade you serve.

 

Use the OpenCV Python library - actually CV2 is current and best incarnation of the library. The presenter uses CV2.
Here is an excellent how-to video to pre-processing images before OCR.
The feature he is looking for is called de-skewing.
The video is long but the presenter is right - you'll eventually need all of the pre-processing features he presents and knowing how/when to use each type of pre-processing is key to getting text from nearly any image.

 

Yes, de-skewing, using CV2. I have the de-skweing part down already. If I manually specify the corners of the container I can get a usable image, even from something badly skewed.






I can't manually specify the corners though; I have to detect the container, isolate it, and find its corners programatically in order to have the data needed to de-skew it. That's what I'm working on right now. Using a color filter I can get the rough shape, but getting from rough shape to usable coordinates is the hardest part of this so far.


Sooner or later I'll need to get away from color filtering and into pattern/feature recognition, as the above wouldn't work for many containers of the same color.

 

Heard of bulk carriers?

A common terminal could be shooting into holds more than 900 tns/hour per pipe.

Discharging with vacuvators could be done in 36 hrs for a bulk carrier with 31.000 tons.

It all depends what trade you serve.

I know of the existence of what you describe, but options like that, and decisions to pursue them, are way above my pay grade. The situation is decided for me; I must perform OCR on shipping containers.

 

It might be easier to automate the picture taking methods - a drone with a programmed fight an photo pattern - adding QR Code tags to each container as they enter the lot, QR tags for each aisle of the lot. Many different things can be done (have been done).

 

Heard of bulk carriers?

A common terminal could be shooting into holds more than 900 tns/hour per pipe.

Discharging with vacuvators could be done in 36 hrs for a bulk carrier with 31.000 tons.

It all depends what trade you serve.

The manufacturers of the plastic pellets use the bulk containers (occasionally). This site is apparently a distributor that may compound in various colir packages or just break bulk shipments into smaller loads/packages as a value-added service. Usually they have some partnership agreement with the various manufacturers they study represent. It would be rare that a distributor could make a margin on a bulk shipment like that with two material movements - when the manufacturers could do it with one movement (especially on such a big volume).

 

It might be easier to automate the picture taking methods - a drone with a programmed fight an photo pattern - adding QR Code tags to each container as they enter the lot, QR tags for each aisle of the lot. Many different things can be done (have been done).

I am developing this for two applications. The immediate need is for a fixed camera to give the container ID of a container parked in a fixed position (on a scale). The future application is a drone-mounted camera to perform continuous audit of container yards. The de-skewing of the current application should be easier than I'm making it; the container will always be in the same spot (+/- 1ft) so I could forego detecting corners and just apply a static deskew factor. But I am trying to develop around the more demanding application from the start to minimize rework.