# Merge two images

• @agave Any other example you don't understand? Software part of the problem I mean Probably @seulunga will provide another example

• @elmirap I was not talking about the problem. Just wondering about where you're from. Forget it.

• Ok, I will be at your disposal in case you want to discuss your solution. Other statements or questions are irrelevant (out of scope) I think.

• Thanks guys, hopefully this example clears a bit.

``````+---+---+
|   |   |
| w | b |
|   |   |
+-------+
|   |   |
| w + w +
|   |   |
+-------+

+

+---+---+
|       |
|   W   |
|       |
+   _   +
|       |
|   B   |
|       |
+-------+

=

+---+---+
|       |
|       |
|       |
|   w   |
|       |
|       |
+-------+
``````
``````+---+---+
|   |   |
| w | b |
|   |   |
+-------+
|   |   |
| w + w +
|   |   |
+-------+

+

+---+---+
|       |
|   B   |
|       |
+   _   +
|       |
|   B   |
|       |
+-------+

=

+---+---+
|   |   |
| w | b |
|   |   |
+-------+
|   |   |
| w + w +
|   |   |
+-------+
``````

PS. You just merge back when its a square, not a rectangle.

• @seulunga said in Merge two images:
Thank you very much @seulunga

``````> +---+---+
> |   |   |
> | w | w |
> |   |   |
> +-------+
> |   |   |
> | w + w +
> |   |   |
> +-------+
``````

Can we put together all ""w" quadrants like these above in one ? Please ref to the second rule :"When you merge, if all quadrant colors are white, you should create an image with a single white quadrant"

• correct. once you have 4 quadrants of same in the same color, you should merge them back into a single quadrant.

• @seulunga thanks , just I want to clarify. Do you mean that this rule also considers quadrants with black color?Can I ask you to edit your problem statement, at least the rules? Thank you.

• yes. conceptually you want to keep the data structure sparse instead of dense.

• @seulunga How is the second image (below) a quadrant?

``````+-------+
|       |
|   B   |
|       |
+-------+
|       |
|   B   |
|       |
+-------+
``````

I would think this one is an invalid input. At any instant, the image should have 2^x pixels. 4 adjoining pixels can coalesce together to become a bigger pixel.

I don't like this concept:

``````+-------+-------+
|       |       |
|   W   |   W   |
|       |       |
+-------+-------+
|       |       |
|   W   |   B   |
|       |       |
+-------+-------+
|       |       |
|   B   |   B   |
|       |       |
+-------+-------+
``````

can become

``````+-------+-------+
|               |
|               |
|               |
|       W       |
|               |
|               |
|               |
+-------+-------+
|       |       |
|   B   |   B   |
|       |       |
+-------+-------+
``````

or

``````+-------+-------+
|       |       |
|   W   |   W   |
|       |       |
+-------+-------+
|               |
|               |
|               |
|       W       |
|               |
|               |
|               |
+-------+-------+
``````

Or am I missing something?

• You are right the image should have sizr 2 to the power of n.But we don't have to merge any two adjacent blocks.We can merge only any four subblocks of given block only if all four subblocks have the same color.For example
-w-w
-w-w
merge to one w block
But -w-b
-w-b
can't merge anymore because there different colours

• This is my solution. What do you guys think?

``````import java.awt.*;

public class Image {
private Image quadrant1 = null;
private Image quadrant2 = null;
private Image quadrant3 = null;
private Image quadrant4 = null;
private ImageColor color = ImageColor.MIXED;

public enum ImageColor {BLACK, WHITE, MIXED}

public Image(Image quadrant1, Image quadrant2, Image quadrant3, Image quadrant4) {
if(quadrant1.isSolidColor() &&
quadrant1.getColor() == quadrant2.getColor() &&
quadrant1.getColor() == quadrant3.getColor() &&
quadrant1.getColor() == quadrant4.getColor()) {
color = quadrant1.getColor();
} else {
this.quadrant1 = quadrant1;
this.quadrant2 = quadrant2;
this.quadrant3 = quadrant3;
this.quadrant4 = quadrant4;
}
}

public Image(ImageColor color) {
assert color != ImageColor.MIXED;
this.color = color;
}

public boolean isSolidColor() {
return color != ImageColor.MIXED;
}

public Image getQuadrant1() {
return isSolidColor() ? this : quadrant1;
}

public Image getQuadrant2() {
return isSolidColor() ? this : quadrant2;
}

public Image getQuadrant3() {
return isSolidColor() ? this : quadrant3;
}

public Image getQuadrant4() {
return isSolidColor() ? this : quadrant4;
}

public ImageColor getColor() {
return color;
}

public Image merge(Image image) {
return Image.merge(this, image);
}

public static Image merge(Image image1, Image image2) {
if (image1.getColor() == ImageColor.WHITE || image2.getColor() == ImageColor.WHITE) return new Image(ImageColor.WHITE);
if (image1.getColor() == ImageColor.BLACK && image2.getColor() == ImageColor.BLACK) return new Image(ImageColor.BLACK);
return new Image(
merge(image1.getQuadrant1(), image2.getQuadrant1()),
merge(image2.getQuadrant2(), image2.getQuadrant2()),
merge(image2.getQuadrant3(), image2.getQuadrant3()),
merge(image2.getQuadrant4(), image2.getQuadrant4()));
}
}

``````

• I got this question like this, we have two black and white images of the size of (2^n)*(2^n), then each of them is represented as a quad tree, in which if the colors of one section are all the same, they are compressed to one node, the goal is compute a tree which is the intersection of two given the rule that intersection of white and black is black, as a sample, see the example below, you need to do a recursion on both trees at the same time, you should note that this special case that if one section is complement of the other one, then it needs to be represented as a compressed node, so if one is BBWB and the other one WWBW this is B.
[0_1482869385540_aks 27-Dec-2016 21-08-13 Page 1.pdf]df)>! ~~

• Spoiler~~~~>! strikethrough text~~strikethrough text

• My python solution, merges 4 equal quadrants into one when needed:

``````class Node:
def __init__(self, children):
self.children = children

def __eq__(self, other):
if not isinstance(other, Node):
return False
return all((self.children[i] == c for i, c in enumerate(other.children)))

class LeafNode:
def __init__(self, color):
self.color = color

def __eq__(self, other):
if not isinstance(other, LeafNode):
return False
return self.color == other.color

def merge_nodes(node_a, node_b):
if isinstance(node_a, LeafNode) and isinstance(node_b, LeafNode):
return LeafNode(node_a.color or node_b.color)

if isinstance(node_a, LeafNode):
temp = node_a
node_a = node_b
node_b = temp

children = None
if isinstance(node_b, LeafNode):
children = [merge_nodes(c, node_b) for c in node_a.children]
else:
children = [merge_nodes(node_a.children[i], node_b.children[i]) for i in range(4)]

if all((isinstance(c, LeafNode) for c in children)):
color = children[0].color
for i in range(1, 4):
if color != children[i].color:
return Node(children)
return LeafNode(color)

return Node(children)
``````

With some test cases:

``````b = LeafNode(False)
w = LeafNode(True)

assert merge_nodes(b, w) == w
assert merge_nodes(w, w) == w
assert merge_nodes(b, b) == b

bbbw = Node([b, b, b, w])
bwbb = Node([b, w, b, b])
bbww = Node([b, b, w, w])
wbbw = Node([w, b, b, w])
wwbw = Node([w, w, b, w])
bwbw = Node([b, w, b, w])

assert merge_nodes(bbbw, w) == w
assert merge_nodes(bbww, w) == w
assert merge_nodes(wbbw, w) == w
assert merge_nodes(wwbw, w) == w

assert merge_nodes(bbbw, b) == bbbw
assert merge_nodes(bwbb, b) == bwbb
assert merge_nodes(wbbw, b) == wbbw
assert merge_nodes(wwbw, b) == wwbw

assert merge_nodes(bbbw, bwbb) == bwbw
assert merge_nodes(bbww, wwbw) == w

b___bwbbw___wwbw = Node([b, bwbb, w, wwbw])
wbbww___bbbwb___ = Node([wbbw, w, bbbw, b])
wbbww___w___wwbw = Node([wbbw, w, w, wwbw])

assert merge_nodes(b___bwbbw___wwbw, wbbww___bbbwb___) == wbbww___w___wwbw
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.