Liste des blocs à une matrice entière - java

Question

J'ai donc le problème suivant: J'ai une méthode qui casse une grande matrice en blocs plus petits de la même taille. Après avoir fait quelques opérations sur les blocs, je veux reconstruire la grande matrice dans le bon ordre, mais je me trompe d'une manière ou d'une autre.

Le code suivant reconstruit correctement une matrice 4x4 qui se divise en 2x2, mais pour toutes les autres dimensions, cela ne fonctionne pas correctement.

public long[][] blocksToMatrix(List<long[][]> blocks, int blockDimension, int width, int height){ 
     long[][] yuvMatrix = new long[height][width]; 
     int heightPos = 0; 
     int widthPos = 0; 
     for (int i = 0; i < blocks.size(); i++) { 
     long[][] yuvBlock = blocks.get(i); 
     int heightPosTemp = heightPos; 
     for (int j = 0; j < blockDimension * blockDimension; j++) { 
      yuvMatrix[heightPos][widthPos] = yuvBlock[j/blockDimension][j % blockDimension]; 
      widthPos++; 
      if (widthPos >= width){ 
       widthPos = (i * blockDimension) % width; 
       heightPos++; 
      } 
      if (widthPos == ((i + 1) * blockDimension) % width){ 
       widthPos = (i * blockDimension) % width; 
       heightPos++; 
      } 
     } 
     if (heightPos == height){ 
      heightPos = heightPosTemp; 
     } 
     else { 
      heightPos = (i * blockDimension) % height; 
     } 
     widthPos = ((i + 1) * blockDimension) % width; 
     } 
     return yuvMatrix; 
    } 

La méthode que je cassais la matrice:

public List<long[][]> matrixToBlocks(long[][] yuvMatrix, int blockDimension, int width, int height){ 
     int blocksSize = width/blockDimension * (height/blockDimension); 
     List<long[][]> blocks = new ArrayList<long[][]>(); 
     for (int i = 0; i < blocksSize; i++) { 
     long[][] subBlock = new long[blockDimension][blockDimension]; 
     int heightPos = (blockDimension * (i/blockDimension)) % height; 
     int widthPos = (blockDimension * i) % width; 
     if (widthPos + blockDimension > width) { 
      widthPos = 0; 
     } 
     for (int row = 0; row < blockDimension; row++) { 
      for (int col = 0; col < blockDimension; col++) { 
       subBlock[row][col] = yuvMatrix[heightPos + row][col + widthPos]; 
      } 
     } 
     blocks.add(subBlock); 
     } 
     return blocks; 
    } 

La façon dont je l'ai testé:

public static void testareMatBlo(int height, int width, int blockdim){ 
     long[][] test = new long[height][width]; 
     int val = 1; 
     for (int i = 0; i < height; i++){ 
     for (int j = 0; j < width; j++){ 
      test[i][j] = val; 
      val++; 
     } 
     } 
     List<long[][]> blocks = matrixToBlocks(test, blockdim, width, height); 
     long[][] matrix = blocksToMatrix(blocks, blockdim, width, height); 
     if (Arrays.deepEquals(test, matrix)){ 
     System.out.println("YES"); 
     } 
     else { 
     System.out.println("NO"); 
     } 
    } 

Cela fonctionne:

testareMatBlo(4, 4, 2); 

Mais quoi que ce soit d'autre doesn 't. Quelqu'un peut-il expliquer ce que j'ai fait de mal?

Answer 1

Je ne l'ai pas lu à fond votre code pour matrixToBlocks(...) mais tous ces calculs comme int blocksSize = width/blockDimension * (height/blockDimension); sont très susceptibles d'introduire difficile de repérer les erreurs - et vous ne fait pas besoin d'eux:

public static List<long[][]> matrixToBlocks(long[][] yuvMatrix, int blockDimension){  
    //Check matrix and block dimension match 
    if(yuvMatrix.length == 0 || yuvMatrix.length % blockDimension != 0 
    || yuvMatrix[0].length == 0 || yuvMatrix[0].length % blockDimension != 0) { 
    throw new IllegalArgumentException("whatever message you like"); 
    } 

    List<long[][]> blocks = new ArrayList<long[][]>(); 

    //Iterate over the blocks in row-major order (down first, then right) 
    for(int c = 0; c < yuvMatrix.length; c += blockDimension) { 
    for(int r = 0; r < yuvMatrix[c].length; r += blockDimension) { 
     long[][] subBlock = new long[blockDimension][blockDimension]; 

     //Iterate over the block in row-major order 
     for(int bc = 0; bc < blockDimension; bc++) { 
     for(int br = 0; br < blockDimension; br++) { 
      subBlock[bc][br]=yuvMatrix[c+bc][r+br]; 
     } 
     }  

     blocks.add(subBlock); 
    } 
    } 

    return blocks; 
} 

Cette méthode n » t paraître plus court mais c'est: en omettant le contrôle préliminaire, il n'y a que 8 lignes de code réelles par rapport à 13 dans votre code. Ce n'est pas le point cependant. Ce qui est plus important est que la logique est plus facile car il y a seulement quelques calculs impliqués (comme c+bc). Vous pourriez penser que c'est inefficace mais ce n'est pas le cas: vous n'accédez à chaque élément qu'une seule fois et donc même s'il y a 4 boucles imbriquées, la complexité globale est toujours O (n) avec n étant la taille de la matrice .

La reconstruction de la matrice est également facile. La principale chose à prendre en compte est l'ordre des blocs: si vous les créez dans l'ordre des rangées (les blocs les uns en dessous des autres sont dans la liste), vous devez recréer la matrice de la même manière:

public static long[][] blocksToMatrix(List<long[][]> blocks, int width, int height) { 
    long[][] yuvMatrix = new long[width][height]; 
    int c = 0; 
    int r = 0; 

    for(long[][] block : blocks) { 
    int blockWidth = block.length; 
    int blockHeight = block[0].length; 

    for(int bc = 0; bc < block.length; bc++) { 
     for(int br = 0; br < block[bc].length; br++) { 
     yuvMatrix[c + bc][r + br] = block[bc][br]; 
     } 
    } 

    //calculate the next offset into the matrix 
    //The blocks where created in row-major order so we need to advance the offset in the same way 
    r += blockHeight; 
    if(r >= height) { 
     r = 0; 
     c += blockWidth; 
    } 
    } 

    return yuvMatrix; 
}