Placing a shape inside another shape using opencv

Question

I have two images and I need to place the second image inside the first image. The second image can be resized, rotated or skewed such that it covers a larger area of the other images as possible. As an example, in the figure shown below, the green circle need to be placed inside the blue shape:

Here the green circle is transformed such that it covers a larger area. Another example is shown below:

Note that there may be some multiple results. However, any similar result is acceptable as shown in the above example.

How do I solve this problem? Thanks in advance!

Answer 1

I tested the idea I mentioned earlier in the comments and the output is almost good. It may be better but it takes time. The final code was too much and it depends on one of my old personal projects, so I will not share. But I will explain step by step how I wrote such an algorithm. Note that I have tested the algorithm many times. Not yet 100% accurate.

---

for N times do this:
    1. Copy from shape
    2. Transform it randomly
    3. Put the shape on the background
    4-1. It is not acceptable if the shape exceeds the background. Go to 
         the first step.
    4.2. Otherwise we will continue to step 5.
    5. We calculate the length, width and number of shape pixels.
    6. We keep a list of the best candidates and compare these three 
       parameters (W, H, Pixels) with the members of the list. If we 
       find a better item, we will save it.

• I set the value of N to 5,000. The larger the number, the slower the algorithm runs, but the better the result.

• You can use anything for Transform. Mirror, Rotate, Shear, Scale, Resize, etc. But I used warpPerspective for this one.

im1 = cv2.imread(sys.path[0]+'/Back.png')
im2 = cv2.imread(sys.path[0]+'/Shape.png')
bH, bW = im1.shape[:2]
sH, sW = im2.shape[:2]


# TopLeft, TopRight, BottomRight, BottomLeft of the shape
_inp = np.float32([[0, 0], [sW, 0], [sW, sH], [0, sH]])
cx = random.randint(5, sW-5)
ch = random.randint(5, sH-5)
o = 0
# Random transformed output
_out = np.float32([
            [random.randint(-o, cx-1), random.randint(1-o, ch-1)],
            [random.randint(cx+1, sW+o), random.randint(1-o, ch-1)],
            [random.randint(cx+1, sW+o), random.randint(ch+1, sH+o)],
            [random.randint(-o, cx-1), random.randint(ch+1, sH+o)]
])

# Transformed output
M = cv2.getPerspectiveTransform(_inp, _out)
t = cv2.warpPerspective(shape, M, (bH, bW))

• You can use countNonZero to find the number of pixels and findContours and boundingRect to find the shape size.

def getSize(msk):
    cnts, _ = cv2.findContours(msk, cv2.RETR_TREE, cv2.CHAIN_APPROX_NONE)
    cnts.sort(key=lambda p: max(cv2.boundingRect(p)[2],cv2.boundingRect(p)[3]), reverse=True)
    w,h=0,0
    if(len(cnts)>0):
        _, _, w, h = cv2.boundingRect(cnts[0])
    pix = cv2.countNonZero(msk)
    return pix, w, h

• To find overlaping of back and shape you can do something like this: make a mask from back and shape and use bitwise methods; Change this section according to the software you wrote. This is just an example :)

mskMix = cv2.bitwise_and(mskBack, mskShape)
mskMix = cv2.bitwise_xor(mskMix, mskShape)
isCandidate = not np.any(mskMix == 255)

For example this is not a candidate answer; This is because if you look closely at the image on the right, you will notice that the shape has exceeded the background.

---

I just tested the circle with 4 different backgrounds; And the results:
After 4879 Iterations:

After 1587 Iterations:

After 4621 Iterations:

After 4574 Iterations:

---

• A few additional points. If you use a method like medianBlur to cover the noise in the Background mask and Shape mask, you may find a better solution.

• I suggest you read about Evolutionary Computation, Metaheuristic and Soft Computing algorithms for better understanding of this algorithm :)