CODEWITHSUNDEEP
algorithmimage-manipulation
Pablo Fernandez
Pablo Fernandez

Reputation: 287870

How to calculate the "distance" between two rectangles?

Given one rectangle and a bunch of images (also rectangles), I need to find the best image to place in it. That would be the one that requires less stretching or shrinking and that covers the area the best. I want to find the one with the least distance (as in, least transformation) to the target rectangle. The images are screenshots of websites, so, they contain a mix of text and images. The screenshots suffer whether they are stretched (pixelation) or shrunk (text becomes unreadable).

But it also feels like one of these problems that someone might have looked into already and there might be an algorithm to properly solve it.

The data is stored in a SQL database so I would need the analysis to be doable in SQL. The data might look like this:

---------------------------------------------------------
| Id                                   | Width | Height |  
---------------------------------------------------------
| 00b701c6-1c31-4323-a292-700b4dff2e45 |   784 |   1310 |
| 0a46a0f6-a3b2-4a5d-a8be-55bad84ba37d |  1414 |    957 |
| 0b79fbe8-6b9e-48d1-89da-8981570e23d7 |   784 |    561 |
| 0e9f5935-0e58-42d2-bba2-3e89db55260f |   400 |    400 |
| 0ebf14fb-094b-47f5-9e25-b4f54bc2eab9 |  2260 |    957 |
| 17131cd6-f5b2-4e4d-a63b-b909e04e2d89 |  1414 |    957 |
| 2298fc73-0bcb-49c8-b54e-3184cf4153d4 |   784 |   1310 |
| 28ffee4a-2d08-4862-aeb0-6546cda4e225 |  2560 |   1387 |
| 29cf92ad-b6fd-43c6-abb1-7c5a7e4af92d |  2260 |    957 |
| 307b2b6e-1f66-4784-bd7d-b6bfc4768fbd |  2560 |   1387 |
| 3edc916b-4b3d-4fd8-a1f9-6418a4d8d27a |  2333 |    435 |
| 3ef1132a-d059-487a-9cad-dbb3895ad25a |  1414 |    957 |
| 43e044e5-5f82-4b86-95ba-a9e76f5d2519 |   657 |    435 |
| 464be0ec-5cb7-4f3f-856d-6beb5fbc2f5e |   657 |    435 |
| 510d0236-e61a-4f1c-bb0b-754c4c1f80f7 |  2260 |    957 |
| 52f217d5-038c-475d-af96-89d1930e8c2f |   657 |    435 |
| 532cadf5-c20b-4b1c-84d4-78e1b501495f |  2333 |    435 |
| 5f3e55aa-12a4-4502-a159-fdc128b53e11 |  2260 |    957 |
| 626c33a9-aaa0-47b6-a6f3-bd5235f1655b |   784 |    561 |
| 6711a717-e1ee-4930-9f21-5e225a99a769 |   657 |    435 |
| 7125c301-c311-4339-b36c-519dc3714c68 |   784 |    561 |
| 8f5d8e3b-8213-4cd6-8ea0-311297f4cfc3 |  2333 |    435 |
| c3d7661f-12e6-4297-8830-15e82850bc32 |   784 |   1310 |
| cd32106e-2f3e-4614-ac40-19e3f5d7fa1f |   784 |    561 |
| d7191194-1f8a-4230-8ee0-8a8b427b86e7 |   784 |   1310 |
| d737de66-849d-4ec3-bf3b-cc48bfa1f3a6 |  2560 |   1387 |
| d935e10b-88f3-4aba-a2b4-a1a9cfd8acb4 |  2560 |   1387 |
| dcc8e9e6-4ee3-4737-a530-d2fcffd35a86 |  2333 |    435 |
| ec3187be-5a81-4ecb-a908-ddedaa5930ec |  1414 |    957 |
---------------------------------------------------------

Upvotes: 0

Views: 713

Answers (2)

javidcf
javidcf

Reputation: 59731

You can compute the Jaccard index as follows:

function jaccard(rect : Rectangle, img : Rectangle) : float
  rectArea := rect.width * rect.height
  imgArea := img.width * img.height
  interArea := min(rect.width, img.width) * min(rect.height, img.height)
  return interArea / (rectArea + imgArea - interArea)
end

Then choose the highest scoring image (values go from zero to one).

Upvotes: 2

Johan
Johan

Reputation: 1515

I don't have a complete algorithm but my approach would be to score each image based on how good it matches the rectangle. The interesting parameter would the ratio (width/height), so calculate the ratio for each image and compare it to the ratio of the rectangle. The nearest ratio wins.

As for the second problem I'd probably set a threshold, if the ratio of the best fit is really close to the rectangle (below the threshold) you can get away with stretching (looks better than two very thin borders), if it's above the threshold add black borders since distorted text is hideous.

Upvotes: 0

Related Questions