An uniform grid, where each pixel/voxel got is own value. I want to create a new grid where each pixel/voxel got an equal value even tho the grid becomes non-uniform.

Hello everyone,

I am not the professinal with Matlab and I have a problem to solve.

This problem is really a density problem where I know the densities of each voxel and then I have to create a new grid where each pixel should contain a specific weight, we will skip that part over and only use weight to make it more simple! :)

I have to divide a "special stone" to small pieces of 300 gram. The Stone got a total weight of 3800 gram, but as you can see it got different weights(densities) randomly distributed next to each other. I need to create a new grid where either way the pixels should have the same size (more error) and each pixel got a different weight or a grid with different size of pixels, where the weight is precise 300 gram. Remember the neighbour pixel are different all the time! In my case we are talking about a 3D-problem but I will illustrate it in 2D so people get the idea.

Each number contain a specific known weight(density) as I said (1-9) randomly placed, both the position and the resolution for each pixel/voxel is known and it is a uniform grid here.

I have made a small code for the problem too:

A =[1 4 5 2 3 5;
    2 2 4 6 9 8;
    3 1 5 2 5 9;
    5 2 4 3 1 6;
    2 3 6 9 8 7;
    1 2 6 7 9 2];
% weight of each number for the stone part
B =[103.9;106.0;104.3;104.3;110;104;100.7;101.3;110.0]; 
% B(1) is the value of 1 ect. 
for i =1:max(max(A));
A(A==i)=B(i);
end
Weight = sum(sum(A)) % in this case we got a weight of 3800 gram in total.

I really don't know how to execute this well but, I am not sure if it is possible to create a uniform grid of 12 pixels where the weight is the between 320-300 gram since 3800/12 = 316.9750 gram or something?

I made a post earlier and some said maybe it could be a Knapsack problem, but I don't think it is that, because each pixel is just as important as the other pixel.

But I have no clue how to begin I hope you people can help me out! :)

So shortly again: okay, well the point is that I have to devide the stone into sub areas where it only contain a specific weight and it should be around 300 gram in this case it could be with many different weights. I just don't know what kind of techniques can help me to solve my problem.

So short: I got a stone with different densities randomly distributed (I have converted it to kg) and then I have to split the stone in different sub areas with an equal or almost weight.

Thank you very much for your time.

[Walter Roberson]

Duplicates http://www.mathworks.com/matlabcentral/answers/282996-an-uniform-grid-where-each-pixel-voxel-got-is-own-value-i-want-to-create-a-new-grid-where-each-pix and should be merged into it

Answer 1

[Image Analyst]

If you're not going to use knapsack, then the only other thing I can think of is quadtree decomposition, done by qtdecomp() in the Image Processing Toolbox. But it won't work right out of the box. You have to work with it but it's a lead at least.

[Nick Yin Larsen]

IT's just when I have been looking at knapsack problem, then I don't see how I can implement it? For the knapsack problem we got the total weight right, which I also know, but you never divide the knapsack to have subknapsack of 100gram in this case? And when you look at the value of each weight in the knapsack problem, then you don't look at the neightbour value but just the general value as I understand it... :/

[Walter Roberson]

You apply knapsack over the weights to get groups of 100. Somehow, in some way that is so far undefined in your question, each of those will have a different shape -- we know that from the illustration, but your illustration gives no hint as to whether the larger numbers correspond to larger sizes or what. Your illustration does not even say anything about how the numbers 1 to 9 correspond to "weight".

But somehow you know how big each grouping of 100 is. And then you do Bin Packing to fit all of those into something the size of your original image. We guess. Since you were not clear as to what the output size is, other than your diagrams have the same scale which might indicate that they are to be the same size.

I have no clue what you are really trying to do. Maybe you are trying to do something equivalent to Gerrymandering, cut the space up into adjacent volumes each with the given weight.

[Nick Yin Larsen]

OKay, I didn't write it down in a good way then :)

I just made an example which doesn't corespond to the grafic values but:

A =[1 4 5 2 3 5;
    2 2 4 6 9 8;
    3 1 5 2 5 9;
    5 2 4 3 1 6;
    2 3 6 9 8 7;
    1 2 6 7 9 2];

% weight of each number for the stone part
B =[103.9;106.0;104.3;104.3;110;104;100.7;101.3;110.0]; 

for i =1:max(max(A));
A(A==i)=B(i);
end

Weight = sum(sum(A)) % in this case we got a weight of 3800 gram in total.

So in this example I want to create a new grid, where each pixels got a weight of around 300 gram. So we will say 3800g/300 gram = 12.67 pixels. So I need to create a new grid with 12 pixels (need to be even I guess), so they will have a weight between 320-300 gram or something since 3800/12 = 316.9750 gram. I hope it is more clear? - but I don't know how to generate the new grid :)

Thank you once again!

[Image Analyst]

I still think qtdecomp() is worth looking into. For example you can keep splitting blocks in the image as long as the standard deviation is more than some number. I think you could do the same for the sum instead of the standard deviation. The image will have to be a size that is a multiple of 4 in each direction. Sorry, I just don't have that much experience with the function and it's tricky to use.

[Nick Yin Larsen]

Okay, great I will look more deep in the function then.

Thank you for your help! :)