Algorithms, Computer Engineering

Assignment Help:
Design an algorithm (using pseudocode) that takes in as an input, two 2-D int arrays that are assumed to be 2 black-and-white images: initialImage x, whose dimensions are IxJ, and finalImage y, whose dimensions are IxK. The algorithm will compare x to the y, row-by-row, as defined below. Your algorithm will employ a dynamic programming scheme to compare X to Y identifying the minimal difference between each row.

Because you are working with black-and-white images only, you should assume that each image is a 2-D int array consisting of 2 possible values: 0 or 1, where 0 represents black and 1 represents white. Thus, this 2-D grid of 0 and 1 values comprise a 2-D black-and-white image. Each row of this image is then simply a 1-D int array filled with either 0s or 1s. Therefore, you must define how you will measure the difference between the strings of 0s and 1s in each row.

Remember that you will do the comparison one row in the images at a time.

First, compare X1,* to Y1,*. (Here X1,* is the first row in image X and Y1,* is the first row in image Y ). Next, compare X2 to Y2... Each one of these comparisons will require the construction of a D (distance) matrix.

In the following example, the first row of X is X1,*, and the first row of Y is Y1,* = 00110.



Use the following recurrence relation to develop your pseudocode:



After the D matrix is completed, the minimum number in the bottom row is the minimal mismatch for this row. You will assign this value to the variable minVali. This number tells how different row X1,* is from row Y1,* . You will then repeat this comparison for all rows i and aggregate the difference when complete into variable totalDifference = Si minVali.

As a result, the algorithm will compare the total difference to a threshold value called thresh. If total value is above the threshold, the images are declared different, otherwise they are declared to be similar images. You can assume that the thresh variable is supplied as an input to your algorithm.

Part 1

Create a portfolio that includes all previous IPs.

Part 2a:

Design pseudocode for the image comparison algorithm discussed above, given input Images X, Y, and thresh. The output is a declaration: The images are similar, or the images are different.

Part 2b:

Discuss the optimality of the dynamic programming solution. Discuss the time complexity of this algorithm in terms of the size of the inputs X and Y.

Related Discussions:- Algorithms

What are the input devices, What are the Input devices Various devices ...

What are the Input devices Various devices are available for data input on graphics workstations. Most systems have a keyboard and one or more additional devices specially desi

Create perl scripts, Create Perl scripts as required below: a) Create a ...

Create Perl scripts as required below: a) Create a script named select_by_attribute.pl that accepts the name of a LibML documentand the name of a particular attribute from the c

Mac and llc, how can we improve the way LLC and MAC are used for LAN operat...

how can we improve the way LLC and MAC are used for LAN operation.?

Show the ranges of port numbers, Q. Show the ranges of Port numbers? P...

Q. Show the ranges of Port numbers? Port numbers are divided into three ranges: Well-known ports are those from 0 through 1,023. Registered ports are those from

Sigmoid units, Sigmoid units: Always remember that the function inside...

Sigmoid units: Always remember that the function inside units take as input the weighted sum, S and of the values coming from the units connected to it. However the function i

Discuss the advantages of electronics data exchange, Discuss the advantages...

Discuss the advantages of Electronics Data Exchange (EDI). Advantages of EDI: Electronics Data Exchange's saves needless re-capture of data. It leads to faster transfer of d

Build and explain a prototype model-uml, International Coal Coal-fire...

International Coal Coal-fired Power Generation Compared with other fossil fuels, burning coal produces relatively large amounts of atmospheric pollutants: carbon dioxide

Multi-threaded concurrency programming with threads, Your task is to implem...

Your task is to implement a memory manager that manages page reads and writes from multiple client threads. In the first programming task the memory manager keeps all the pages in

What is machine.config, What is Machine.config?  Machine configuration ...

What is Machine.config?  Machine configuration file: The machine. config file contains settings that apply to the whole computer.  The machine.config, which can be found in the

Loosely coupled systems, Loosely Coupled Systems These systems do not d...

Loosely Coupled Systems These systems do not distribute the global memory because shared memory concept gives rise to the difficulty  of memory conflicts, which in turn slows d

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd