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

Copy machine problem, We are trying to figure out how many copy machines we...

We are trying to figure out how many copy machines we should install in the basement of Stranahan Hall.  Copy machines should be available 24/7.  Students may walk up at any time o

Write an awk program - unix , Write an AWK program which takes the followin...

Write an AWK program which takes the following input file and processes it. $cat data.txt John Do 111-1111 English 90 Maths 80 Alice Do 222-2222 English 90 Maths 90 Chemistry 93

C++, At a shop of marbles, packs of marbles are prepared. Packets are named...

At a shop of marbles, packs of marbles are prepared. Packets are named A, B, C, D, E …….. All packets are kept in a VERTICAL SHELF in random order. Any numbers of packets with thes

What is over-clocking, Overclocking is the process of making a computer or ...

Overclocking is the process of making a computer or component operate faster than the clock frequency particular by the manufacturer by modifying system parameters. One of the most

Vector processing, Vector Processing  A vector is an ordered set of the...

Vector Processing  A vector is an ordered set of the similar type of scalar data items. The scalar item can be a floating point number, a logical value or an integer. Vector pr

How do you track down a transition by name, Question 1: a) How do you ...

Question 1: a) How do you track down a transition by name? b) Why Premiere Pro is considered a non-linear editor? c) Explain clearly the main problem that may arise wh

Search-based tools, The search-based tools initially identify the problem a...

The search-based tools initially identify the problem and after that appropriately give advice on how to correct it. AT Expert from Cray Research is one of the tools being used

Artificial intelligence agents, Artificial Intelligence Agents: We int...

Artificial Intelligence Agents: We introduced what we'll be conversation about in Artificial Intelligence and why those things are necessary. This discussion is of course abou

What is process, In Windows, Thread is a unit of implementation. Process is...

In Windows, Thread is a unit of implementation. Process is the environment in which thread implements. Scheduler, schedules the Threads not the process. In Unix variants, Thread is

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