代做 program、代写 Python 程序设计
Large-Scale Linear Optimization Project Fall 2023
Due: Thursday, December 6
You are a recent hire of Abode Inc., a company that specializes in image processing software development. You are tasked to develop a ‘smart’ image cropping and resizing tool that is able to remove parts of the input image inconspicuously. Consider the following image that is to be resized using your tool.
Figure 1. Original image.
To shorten the image width, one could naively remove the irrelevant middle section of the image, which
yields the following cropped image.
Figure 2. Left: Region inside the red rectangle is to be cut off. Right: Cropped image.
It is noticeable that the image has been cropped as the transition from the left portion to the right portion of the image is not smooth. To address this issue, you should remove only points or pixels1 along the seams of the image. A seam is a path from the top to the bottom of the image with minimal cost, where the cost is defined as the sum of absolute intensity differences along the path. Examples of seams are given by the
1https://en.wikipedia.org/wiki/Pixel
1
red paths on the left images of Figure 3. Observe that the path traversed by a seam tries to avoid white clouds which may cause dramatic changes in the pixel intensities. To generate seams for an input image of size m × n, one should proceed as follows.
1. Create a graph with nodes (i,j) ∈ I × J, where I = {1,...,m} and J = {1,...,n}. The nodes would correspond to the pixels in the input image. Node (k, l) ∈ I × J can be traversed from node (i,j)∈I×J if
(a) k=i+1,and
(b) liseitherj−1,j,orj+1.
The graph also has a dummy terminal node t that can be traversed from any nodes (m, j), j = 1, . . . , n.
2. Let y ∈ Rm×n be the intensities of the image pixels. Then, the cost of traversing from node (i,j) to
node (k, l) is given by |y(i, j) − y(k, l)|.
3. For each j ∈ J , formulate a linear program the computes the shortest path from the source node (1, j)
to the terminal node t. The optimal path of the linear program would correspond to a seam.
In this assignment, the input image is given by tower.png and the source node is fixed to (1, 50). Perform
the following tasks:
(a) By utilizing the above procedure, formulate and write down a linear program that computes the shortest path from the source node (1,50) to the terminal node t. Solve the linear program using Python or MATLAB and report the optimal objective value. Remove all pixels along the optimal path and generate the new cropped image. Repeat this procedure 25 times, and plot the final cropped image.
(b) Formulate and write down the dual linear program and solve the problem in Python or MATLAB. Verify that the complementary slackness conditions hold for the primal and dual solutions. Report the optimal objective value.
Upload your code to Canvas. Please also submit a short report in PDF format containing a high-level description of your implementation and answers to the above questions.
Students registered for 3 credit hours: You are allowed to work in groups of 2-3 students. Students registered for 4 credit hours: You must work individually.
Remark: I will run your code on my PC and check its correctness and speed. If you use Python, you will receive a prize if your implementation is the fastest.
2
Figure 3. Left: Pixels along the path are to be removed. Right: Cropped image.
3