In this assignment, well solve several 2D optimization problems with linear programming and use RGB and HSV histograms to index and retrieve images.

Problem 1

Lets implement a few tools to minimize/maximize linear 2D functions subject to several linear constraints. To begin with, we need to represent linear equations. Well do it with a class that splits a linear equation into two function expressions: one on the left side of the equation (left-hand side or lhs) and one on the right side of the equation (right-hand side or rhs). This class is implemented in line_eq.py.

class line_eq(object):

def __init__(self, lhs=None, rhs=None):

self.__lhs__ = lhs self.__rhs__ = rhs

def get_lhs(self): return self.__lhs__

def get_rhs(self): return self.__rhs__

def __str__(self):

return str(self.__lhs__) + = + str(self.__rhs__)

To save ourselves some typing, lets define a maker function and save it in maker.py.

def make_line_eq(lhs, rhs):

return line_eq(lhs=lhs, rhs=rhs)

Implement the function line_intersection(fexpr1, fexpr2) that takes two function expressions of line equations (i.e., line_eq objects) and returns a 2D point object (see point2d.py) representing the intersection point of 2 lines or None if the lines do not intersect. Save your implementation in linprog.py. Lets do a few tests.

Test 01

Lets intersect y = 1 and x = 1.

>>> ln1 = make_line_eq(make_var(y), make_const(1.0))

>>> ln2 = make_line_eq(make_var(x), make_const(1.0))

>>> p = line_intersection(ln1, ln2)

>>> print(p.get_x())

1.0

>>> print(p.get_y())

1.0

>>> print(p)

(1.0, 1.0)

Test 02

Lets intersect y = 2 and y = x 6.

>>> ln1 = make_line_eq(make_var(y), make_const(2.0))

>>> ln2 = make_line_eq(make_var(y), make_plus(make_pwr(x, 1.0), make_const(-6.0)))

>>> print(line_intersection(ln1, ln2))

(8.0, 2.0)

>>> print(line_intersection(ln2, ln1))

(8.0, 2.0)

Test 03

Lets intersect y = 2 and y = x + 10.

>>> ln1 = make_line_eq(make_var(y), make_const(-2.0))

>>> ln2 = make_line_eq(make_var(y), make_plus(make_pwr(x, 1.0),

make_const(10.0)))

>>> print(line_intersection(ln1, ln2))

(-12.0, -2.0)

>>> print(line_intersection(ln2, ln1))

(-12.0, -2.0)

Test 04

Lets intersect y = x and y = x + 6.

>>> ln1 = make_line_eq(make_var(y), make_pwr(x, 1.0))

>>> print(ln1) y = (x^1.0)

>>> ln2 = make_line_eq(make_var(y), make_plus(make_prod(make_const(-1.0), make_pwr(x, 1.0)), make_const(6.0)))

>>> print(ln2) y = ((-1.0*(x^1.0))+6.0)

>>> print(line_intersection(ln1, ln2))

(3.0, 3.0)

>>> print(line_intersection(ln2, ln1))

(3.0, 3.0)

Test 05

Lets intersect between y = 0.2x + 10 and y = 0.2x + 5.

>>> ln1 = make_line_eq(make_var(y), make_plus(make_prod(make_const(-1.0/5.0),

make_pwr(x, 1.0)), make_const(10.0)))

>>> ln2 = make_line_eq(make_var(y), make_plus(make_prod(make_const(1.0/5.0), make_pwr(x, 1.0)), make_const(5.0)))

>>> print(ln1) y = ((-0.2*(x^1.0))+10.0) >>> print(ln2) y = ((0.2*(x^1.0))+5.0)

>>> print(line_intersection(ln1, ln2))

(12.5, 7.5)

>>> print(line_intersection(ln2, ln1))

(12.5, 7.5)

>>> ln1f = tof(ln1.get_rhs())

>>> p = line_intersection(ln1, ln2)

>>> ln1f(p.get_x().get_val())

7.5

>>> ln2f = tof(ln2.get_rhs()) >>> ln2f(p.get_x().get_val())

7.5

>>> ln2f(p.get_x().get_val()) == p.get_y().get_val()

True

>>> ln1f(p.get_x().get_val()) == p.get_y().get_val() True

Test 06

Lets intersect x = 1 and y = 0.5x.

>>> ln1 = make_line_eq(make_var(x), make_const(1.0))

>>> ln2 = make_line_eq(make_var(y), make_prod(make_const(0.5), make_pwr(x, 1.0)))

>>> print(line_intersection(ln1, ln2))

(1.0, 0.5)

Implement the functions maximize_obj_fun(f, corner_points) and minimize_obj_fun(f, corner_points) that take a Python function f and an array of corner points, each corner point being a poind2d object, and a corner point from corner_points (i.e., a point2d object) where f achieves its maximum/minimum value and a const object representing that value. Save your implementations in linprog.py. Lets do a couple of quick tests.

>>> f1 = lambda x, y: 2*x + y

>>> corner_points = [make_point2d(1, 1), make_point2d(1, 5), make_point2d(5, 1)]

>>> p, maxv = maximize_obj_fun(f1, corner_points)

>>> isinstance(p, point2d)

True

>>> isinstance(maxv, const)

True

>>> print(p)

(5, 1)

>>> print(maxv)

11

>>> f2 = lambda x, y: x 2*y

>>> p, minv = minimize_obj_fun(f2, corner_points)

>>> print(p)

(1, 5)

>>> print(minv)

-9

Use line_intersection(), maximize_obj_fun(), and minimize_obj_fun() to solve the following optimization problems. Save your solutions in the functions opt_prob_1a(), opt_prob_1b(), and opt_prob_1c() in linprog.py. In the body of each of these functions, you should write code to identify the corner points and then return the values from maximize_obj_fun() or minimize_obj_fun(). In a comment before each function, write your answer to each problem in the format x,y,minv/maxv.

• Problem 1a: Maximize 2x + y that satisfies x 1, y 1, x 5, y 5, and x + y 6.
• Problem 1b: Minimize x/2 + y that satisfies y 2, x 0, x y, x + y 6.
• Problem 1c: Maximize 3x 2y that satisfies x + y 0, x y 0, 2x + 4y 5.

Problem 2

I posted the following zip archives under Canvas announcements for Assignment 12. The archives are:

• zip;
• zip;
• zip;
• zip;
• zip;
• zip;
• zip;
• zip;

After you download them, place them into the folder images on your computer. There should 318 images of various streets in Logan as well as some lunch tray images from a Logan school. I received the latter from Dr. Heidi Wengreen, a USU nutrition professor, with whom I collaborated on a food texture recognition project a couple of years ago. Well use the images in the directory images for persistent indexing (aka pickling). The hist_test.zip contains two image directories: car_test and food_test. Well use these for image retrieval. It is possible to compute RGB, HSV, and grayscale histograms. We wont use grayscale histograms in this assignment.

Indexing Images

Implement the function hist_index_img. This function takes an image path imgp, a string specification of the color space (this can be either rgb or hsv), and the bin size, i.e., the number of bins in each color channel in the histogram (well use 8 and 16 in this assignment).

The function hist_index_img places the key-value pair (imgp, norm_hist) in the dictionary HIST_INDEX. Depending on the value of color_space, the norm_hist is either the normalized and flattened RGB histogram of the image in imgp or the normalized and flattened HSV histogram of the same image. Well discuss how to flatten histograms in lecture 25. Save your implementation in hist_image_index.py. Lets do a test.

def test_01(): HIST_INDEX = {} hist_index_img_dir(IMGDIR, rgb, 8, rgb_hist8.pck)

>>> test_01() ../images/ indexing ../images/16_07_02_14_23_48_orig.png ../images/16_07_02_14_23_48_orig.png indexed indexing ../images/16_07_02_15_18_56_orig.png

indexing ../images/16_07_02_14_50_47_orig.png ../images/16_07_02_14_50_47_orig.png indexed indexing finished

Calling test_01() creates a pickle file rgb_hist8.pck in your current working directory, which is the persisted version of the dictionary HIST_INDEX. There are three other tests in hist_image_index.py to create rgb_hist16.pck, hsv_hist8.pck, and hsv_hist16.pck in a similar fashion.

Retrieving Images

Once you have persisted the dictionary, you can load it into Python as follows:

def load_hist_index(pick_path):

with open(pick_path, rb) as histfile: return pickle.load(histfile)

>>> hist_index = load_hist_index(rgb_hist8.pck)

>>> len(hist_index)

>>> 318

Implement the function find_sim_rgb_images(imgpath, bin_size, hist_index, hist_sim) that finds and displays the top 3 images most similar to the image in imgpath by computing the similarity scores between this image and all images in a given histogram dictionary hist_index. The parameter bin_size should be 8 or 16. Use the following strings as values of hist_sim (i.e., the histogram similarity metric): correl for correlation, chisqr for chi square, inter for intersection, and bhatta for bhattacharrya. Lots more on these metrics in the upcoming lecture 25. The top three images and the input image are displayed in four separate matplotlib figures along with their similarity scores. The similarity scores are also printed in the Python shell. This function computes a list of 2-tuples of the form (path, sim_score), where sim_score is the similarity score computed with hist_sim between the image in imgpath and the image in path. This list of 2-tuples (i.e., the match list) is then sorted from lowest to highest or from highest to lowest similarity score, depending on the value of hist_sim, because for some similarity metrics the higher the better, for others vice versa. The list of the top 3 matches is returned.

Lets do a test where we use the 8-bin rgb index to find the top 3 similar images by using the histogram intersection similarity function (i.e., cv2.HISTCMP_INTERSECT).

def test_01():

hist_index = load_hist_index(PICDIR + rgb_hist8.pck) assert len(hist_index) == 318 imgpath = IMGDIR + food_test/img01.JPG inimg = cv2.imread(imgpath) top_matches = find_sim_rgb_images(imgpath,

8, hist_index, inter)

for imagepath, sim in top_matches:

print(imagepath + > + str(sim))

show_images(inimg, top_matches) del hist_index

Here is the output in the Py shell.

images/123461762.JPG > 2.69072864504 images/123465049.JPG > 2.63319342056 images/123472255.JPG > 2.43531483644

The figures of the input and top 3 matches are in Figures ?? and ??. To show these figures, you should implement the function show_images(imgpath, match_list) that takes the path to the image youre matching and the match list returned by find_sim_rgb_images() or find_sim_hsv_images() (see below).

Figure 1: Input image (Figure 1) and first match image (Figure 2)

Implement the function find_sim_hsv_images(imgpath, bin_size, hist_index, hist_sim) that behaves in the same way as find_sim_rgb_images(), except hist_index is an HSV dictionary. More tests are in hist_index_retrieval.py