Recursion - Image Scrambler

One commonly used programming technique is recursion. With this technique, problems are solved by solving similar problems, but for smaller cases. We can build sets of objects or tasks using recursive rules and initial values. Recursive functions are functions that are self-invoking, using smaller sets or elements each time, until reaching a point where the initial value is used instead of self-invoking. In this laboratory experience, you will practice the definition and implementation of recursive functions to scramble an image and make it incomprehensible.

Objectives:

Define and implement recursive functions.
Practice image processing.
Practice the use of decision and repetition structures.

Pre-Lab:

Before arriving at the laboratory you should have:

Reviewed the concepts related to recursive functions.
Studied the concepts and instructions for the laboratory session.
Taken the Pre-Lab quiz, available in Moodle.

Scrambling Images Digitally

When scrambling images digitally, we reorder the pixels of the image to break the relation between adjacent pixels, making the original image incomprehensible. This technique is frequently used to cypher images and hide data. [1]

Figure 1. The image to the left was cyphered using the image scrambling technique to obtain the image on the right. Taken from [2].

There are many methods that have been proposed to scramble images. In this laboratory experience, you will use a simple method that has a natural implementation with recursive functions.

Scramble It!

The method you will use to scramble the image works by exchanging rectangles of an image a certain number of times, which is established by the level. Figure 2 illustrates a level 1 scramble: the diagonal quadrants are exchanged. Observe Figure 6 as well.

Figure 2. Level 1 scramble: (a) is the original image divided in quadrants, (b) is the image after scrambling it with the first level by exchanging diagonal quadrants.

The next level scramble, level 2, first exchanges the left and right halves of the image. Afterwards, the level 1 scramble is applied to each quadrant. Observe that the level 1 scramble is applied to each of the four quadrants of the original image.

Figure 3. Level 2 scramble: (a) is the original image, (b) is the image after exchanging the left and right halves, (c) is the image after applying a level 1 scramble to each quadrant.

Question: Which of the following figures (a), (b), (c), (d) (in Figure 5) represents the result of applying a level 2 scramble to the drawing of a penguin in Figure 4?

Figure 4.

Figure 5.

If we follow the pattern, a level 3 scramble starts by exchanging the diagonal quadrants. Afterward, a level 2 scramble is applied to each quadrant: exchange the left and right halves and apply a level 1 scramble to each new quadrant. Figure 8 shows the process of applying a level 3 scramble.

To scramble an image repeat this process for a certain level N. What is the pattern? How would a level 4 scramble start? In how many quadrants will we have divided the original image after completing the scramble?

The algorithm to scramble that was just described, is its own inverse. That is, if you apply the same algorithm to the scrambled image, you should obtain the original image.

The following figures illustrate the exchanges that are done by level 1, 2 and 3 scrambles.

Figure 6. Level 1 scramble: the diagonal quadrants are exchanged.

Figure 7. Level 2 scramble: (a) the left and right halves are exchanged, (b) a level 1 scramble is applied to each quadrant.

Figure 8. Level 3 scramble: (a) the diagonal quadrants are exchanged to then apply a level 2 scramble to each quadrant, (b) the left and right halves are exchanged in each quadrant, (c) a level 1 scramble is applied in each new quadrant.

Which of the following would be the result of a level 2 "scramble" on the penguin picture?

A level 1 "scramble" is a diagonal swap of the image quadrants. Level 2 is a swap of the two image halves and then apply level 1 "scramble". If we swap the penguin halves, its left side will be on the right side, and the right side will be on the left, like you can see on the second choice. Now if we move the quadrants diagonally, then at the end the correct answer is the first choice.

What would be the output of the following program?

"01234567" ”45670123” ”67452301” ”76543210” Each time that the recursive function revoltillo is called, it swaps the first and the second halves of the string that is passed by reference. The figure bellow is the recursion tree for revoltillo(“01234567”,2). As the various invocations return, they form the result: ”67452301”

Additional Functions Provided in the Project

The project which you will be working on today contains the cropSwap function that implements the functionality of exchanging the pixels contained in two congruent rectangles within an image. Its prototype is:

void ImageScrambler::cropSwap(QImage &img, int x0, int y0, int x1, int y1, int width, int height );

Its parameters are:

img: reference to the image that we wish to modify (an object of the QImage class)
x0, y0,x1, y1: coordinates of the upper left corners of the rectangles.
width, height: width and height (in pixels) of the rectangles.

For example, if we wish to exchange the pixels of the upper and lower halves of an image P with width 100 and height 150, we invoke the function:

cropSwap(P, 0, 0, 0, 75, 100, 75 );

Laboratory Session:

The project ImageScrambler contains the skeleton of an application to scramble and unscramble images. In today’s laboratory experience you will work in the Filter.cpp file to complete the application.

Exercise 1 - Pseudocode for the Scrambling Function

Write the pseudocode to express the scrambling algorithm described above as a recursive function.

Exercise 2 - Recursive Function to Scramble an Image

Instructions

Load the project ImageScrambler into QtCreator. There are two ways to do this:
- Using the virtual machine: Double click the file ImageScrambler.pro that can be found in the folder /home/eip/labs/recursion-imagescrambler of your virtual machine.
- Downloading the project’s folder from Bitbucket: Use a terminal and write the command git clone http:/bitbucket.org/eip-uprrp/recursion-imagescrambler to download the folder recursion-imagescrambler from Bitbucket. Double click the file ImageScrambler.pro located in the folder that you downloaded to your computer.
The code that we provide creates the interface in Figure 9.
Figure 9. Interface for the Image Scrambler project.
The button that says Scramble Image is programmed so it invokes a function called ScrambleFilter.
Complete the function ScrambleFilter contained in the Filter.cpp file so it implements the recursive algorithm to scramble images. The function has the following format:
QImage ImageScrambler::ScrambleFilter(QImage image, int N, int sx, int sy, int width, int height);
Download this image so you can validate the function you implemented.

Deliverables

Use “Deliverable 1” in Moodle to upload the file with the pseudocode for the recursive function.
Use "Deliverable 2" in Moodle to upload the Filter.cpp file that contains the functions you implemented in this laboratory experience. Remember to use good programming techniques, include the names of the programmers involved, and document your program.

References

[1] F. Maleki et al., ‘‘An Image Encryption System by Cellular Automata with Memory,’’ Proc. 3rd Int’l Conf. Availability, Reliability, and Security, IEEE CS Press, 2008, pp. 12661271.

[2] Dalhoum, Abdel Latif Abu, et al. "Digital Image Scrambling Using 2 D Cellular Automata." IEEE MultiMedia 19.4 (2012): 28-36.

[3] http://www.instructables.com/id/Python-Programming-recursion/

recursion-imagescrambler