Automatic Cropping with Hill Climbing Algorithm
Overview
SmartCrop is an automatic cropping tool that optimizes product images. It automatically crops product images to different sizes, given a specified aspect ratio. In this project, images have been cropped using specifications for the different types of Instagram posts. The idea is to use a single product image as different posts across instagram, without affecting the product in the image.
The program:
- Detects the product in the image and gets it location data
- Locates points within the image which form a box that satisfies specified aspect ratio requirements, while containing (most to all of) the product in the picture
- Crops the image using the location of the box in step 2.
The Algorithm
Hill Climbing Algorithm is a local search algorithm for mathematical optimization problems. The algorithm starts at an initial state and finds the neighbouring states. It then compares the value assigned to each state; the Objective Function if the goal is to get the maximum value or the cost function if the goal is to get the minimum value. The state with the highest objective function or lowest cost function becomes the optimal state. In this project, I defined a cost function as my goal was to find the box with the minimum distance to the image edges (closest box to the edges) in order to capture as much of the product and background as possible.
Two variations of the hill-climbing algorithm were used; Random-restart hill climbing and steepest-ascent hill climbing.
The program starts at a random initial state i.e. a random box with dimensions that satisfy the specified aspect ratio.
The steepest-ascent hill climbing algorithm gets all the neighbours. I have defined neighbours as all possible boxes with the same dimension. For example, given a 1:1 aspect ratio, the program starts with a random box of say 270 x 270. The neighbours are all 270 x 270 boxes located at any point within the image.
Using the steepest-ascent hill climbing algorithm may give the best 270 x 270 box(local minimum), but not necessarily the best square cropper for the image(global minimum). Enter random-restart.
Random restart repeats the process multiple times (10 times in the case of this project) and has a different initial state each time. This means we get to compare 1:1 boxes of different sizes, giving us a better shot at getting the global minimum.
Pseudocode
Note
- A state is a box with points a,b,c,d, a point has coordinates(x,y)
- Neigbours represent different states.
- The set of neighbours have been limited to a size of 30 out of potential hundreds of thousands to millions of possible neighbours.
- Each neighbour has a cost function which is a value assigned to each state depending on their distance to the image edges.
- The cost function also considers the center of the box. A box also carries some value depending on how close its center is to the center of the image
Link to GitHub Repository Here
Execution
Original Image
Vertical Posts
Landscape Post
IG Stories
IGTV Cover
Libraries and resources used
- cvlib Object Detection to get detect object and get bounding box
- OpenCV to read the image into the program
- Python Pillow for cropping and saving
- Other dependencies in requirements.txt file
Conclusion
I very much liked the result of combining these two variations hill climbing algorithm. The algorithm has a tendency to do better with a larger set of neighbours, more random restarts and, of course, defining a good cost function.
