Merge two images


  • -1
    S

    Imagine an image would be just represented by black or white.

    A fully white image:

    +---+
    |   |
    | w |
    |   |
    +---+
    

    A fully black image:

    +---+
    |   |
    | b |
    |   |
    +---+
    

    An image with 3 quadrants with colors and the last quadrant on the right its 4 sub images.

    +---+---+
    |   |   |
    | w | b |
    |   |   |
    +-------+
    |   |w|w|
    | w +---+
    |   |b|b|
    +-------+
    
    Imagine that you can actually have many sub images inside a single quadrant.
    
    
    • Define a data structure for this image.
    • Implement a merge colors operation between two images. Rule is as follows:
      -- If one of the images is white, the result is white, otherwise the result is black.
      -- When you merge, if all quadrant colors are white, you should create an image with a single white quadrant

  • 0

    @seulunga Very interesting question. I have to warm up Quadtrees , I believe that they want Quadtrees


  • 0
    S

    You don't need to review anything fancy like quad trees. Can you think in a simple data structure that would represent the above image?

    Hint: Think about 2 types of objects: One leaf and one intermediate object.


  • 0

    I would do something like:

    {(0, 0): "W", (0, 1): "B", (1,0): "W", (1,1): {(0,0): "W", (0,1): "B", ...}}
    

    and so on till the end of time...


  • 0
    S

    @agave yep exactly. how would the code for merging the images work?


  • 0

    @seulunga what happens when all quadrant colors are black? Shall we create one single black quadrant as the case with white


  • 0

    @seulunga I don't get the merging rule, too vague. Give an example of the application of the two rules.


  • 0

    I am don't get if I merge quadrant with black and white with quadrant with black what will be the result? Black or? I start from the assumption that we merge both pictures quadrantt by quadrant. Am I wrong?


  • 0
    S

    So you can only merge when the images have the same sizes:
    W + W = W
    W + B = W
    B + B = B
    B + W = W

    In short, if either operand is white, the result is white.

    If you compare this to boolean algebra:

    • Black = false
    • White = true
    • Combination operation = OR

    Hopefully is clear now.


  • 0

    @seulunga what about if the images have different # of quadrants?


  • 0
    S

    @agave What do you think should be the proper behavior? Try thinking how would you do for a simple case like:

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

    And extending for when you have many quadrants.


  • 0

    @seulunga It should be the same

    ------------
    |w  | b |
    ----------
    | w | w |
    -----------
    But in case we merge 
    
    ---------------
    |w|b|
    ------
    |w+w|
    -------
    
    with 
    *-------*
    |        |
    | w      |
    |        |
    *------*
    
    we will have only one quadrant W
    ---------*
    |       *|
    |  w     |
    |        |
    |____ _  |

  • 0

    @seulunga I don't know, YOU have to tell me the proper behavior. There is no guessing.


  • 0

    @agave I belive that @seulunga told us more than necessarily ( my personal opinion only) for which I want to thank @seulunga .
    Actually till now I coudn't find the smpler solution because I concetrated on Q-trees, but I am on the way to solve it with Q-trees (not so sofisitcated, just hierarchical structure to represent the quadrants)


  • 0

    @seulunga what about the following case?

    +---+---+
    |   |   |
    | w | b |
    |   |   |
    +-------+
    |   |   |
    | w + w +
    |   |   |
    +-------+
    
    +---+---+
    |       |
    |   W   |
    |       |
    +   _   +
    |       |
    |   B   |
    |       |
    +-------+
    

    And extending for when you have many quadrants.


  • 0

    @agave, first I must to appologize that the question was not pointed to me, but I think that the answer is
    | W |
    | w + w |
    But we will check this when @seulunga answers

    | W |
    | w + w |

    makes one W quadrant |W|


  • 0

    @elmirap See? It's not that crystal-clear after all. :grinning:


  • 0

    @elmirap where are you from? You use weird grammar.


  • 0

    @agave what is not clear ? I don't see really.


  • 0

    @elmirap said in Merge two images:

    @agave, first I must to appologize that the question is not pointed to me,

    I understand but it's like very weird use of English


Log in to reply
 

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