Obter o indice dos 10 valores mais altos de uma matriz

MaxUpGenGros · May 9, 2013 at 11:19 PM

Boa noite.

Estou com um problema num trabalho.

Tenho que percorrer uma matriz de valores e devolver a posiçao dos 10 valores mais altos da mesma.

Não estou a conseguir encontrar um algoritmo que me ajude nisto.

Alguém me podia dar uma ajuda?

Cumprimentos.

ruirodrigues1971 · May 9, 2013 at 11:21 PM

Experimenta pensar desta forma ... simula que tu és o computador e só podes ver um elemento do vector de cada vez ... o que farias para no fim ter o valor maior? 😉

MaxUpGenGros · May 9, 2013 at 11:32 PM

Sim..o Problema é que na matriz vou ter varias linhas e colunas, e os 10 valores maiores tanto podem estar todos na mesma linha, como na mesma coluna..

Não estou a pensar da maneira correcta se calhar..

MaxUpGenGros · May 9, 2013 at 11:57 PM

Respondendo á pergunta, colocaria o primeiro valor do vector numa variavel auxiliar, e comparava todos os elementos com esse valor, e caso encontrasse algum maior colocava-o na variavel..

ruirodrigues1971 · May 10, 2013 at 12:15 AM

Respondendo á pergunta, colocaria o primeiro valor do vector numa variavel auxiliar, e comparava todos os elementos com esse valor, e caso encontrasse algum maior colocava-o na variavel..

é isso mesmo ... logo tens duas fases

1 - Fazer um algoritmo que percorra todos os elementos da matriz

2 - Em cada elemento analisar com o maior até ao momento ... se esse novo elemento for maior ... temos um novo maior 😛

no fim nessa variável maior irá estar o resultado 😉

Edited May 10, 2013 at 12:17 AM by ruirodrigues1971

HappyHippyHippo · May 10, 2013 at 03:15 AM

eu tenho um solução mais simples, isto porque se trata de um problema de descobrir os N maiores.

- crias um array auxiliar de tamanho N*M (N linhas e M colunas da matriz)

- copias todos os elementos da matriz para o array

- ordenas o array (isto é feito através de uma única instrução)

- tens a tua solução nos 10 últimos elementos do array

MaxUpGenGros · May 10, 2013 at 01:02 PM

Ok..vou tentar implementar a ajuda do HappyHippo..

Já agora..como é que eu faço para copiar todos os elementos da matriz para um unico array?

ciclos for para as linhas e colunas da matriz?

Tenho que fazer uma função que devolva um array, e que tenha como parametros de entrada a matriz certo?

MaxUpGenGros · May 10, 2013 at 01:17 PM

Fiz esta função..

Gostava que me dissessem se é a maneira mais correcta de se fazer..Colocar todos os valores da matriz num array.

public static int [] convert2array(BufferedImage image)
{
 int n=320*240;
 int array[]=new int[n];
 WritableRaster a = image.getRaster();
 DataBuffer b = a.getDataBuffer();

 for(int i=0;i<n;i++)
 {
	 array[i]=b.getElem(i);
 }
 return array;

}

Edited May 10, 2013 at 01:17 PM by MaxUpGenGros

HappyHippyHippo · May 10, 2013 at 01:32 PM

hum ... tem mais aspecto de :

public static int [] convert2array(BufferedImage image)
{
 DataBuffer b = image.getRaster().getDataBuffer();

 int n = b.getSize();
 int array[] = new int[n];

 for(int i = 0; i < n; i++)
 {
   array[i] = b.getElem(i);
 }

 return array;
}

ou ainda mais difícil :

public static int [] convert2array(BufferedImage image)
{
 return image.getData().getPixels(0, 0, image.getWidth(), image.getHeight, null);
}

Edited May 10, 2013 at 01:35 PM by HappyHippyHippo

MaxUpGenGros · May 10, 2013 at 01:38 PM

Aquelas linhas todas podem ser reduzidas a apenas essa?

HappyHippyHippo · May 10, 2013 at 01:41 PM

se for o que parece ... sim ... ou achas que ias inventar a roda ?

MaxUpGenGros · May 10, 2013 at 01:42 PM

Para fazer o sort usei o Arrays.sort(array);

No entanto, eu quero saber quais as posições dos 10 valores mais altos antes de ter feito a ordenação..

Será que depois de ordenar as posições não se vão alterar?

se for o que parece ... sim ... ou achas que ias inventar a roda ?

Tens toda a razão.

A minha desculpa para isso é que é a primeira vez que estou a trabalhar com java a fundo, e com processamento de imagem também. 😛

Mas obrigado pela dica.

HappyHippyHippo · May 10, 2013 at 01:55 PM

No entanto, eu quero saber quais as posições dos 10 valores mais altos antes de ter feito a ordenação..

Será que depois de ordenar as posições não se vão alterar?

claro que sim ... o que disse serve só para saber quais são os mais altos. seria para ter um threshold dos pontos a serem considerados.

no entanto se é realmente uma imagem eu pergunto: "o que leva a um pixel ter um valor mais alto que outro ?"

isto implica muitos problemas :

um pixel pode ter imensas codificações da cor

vou supor que seja RGBA !

um pixel {R=1, G=0, B=0, A=0} praticamente preto é maior que {R=0, G=255, B=255, A=255} amarelo acho, com intensidade a 100% ?

e se for outra codificação de cor ?

MaxUpGenGros · May 10, 2013 at 02:01 PM

eu faço a conversão da imagem para Gray..E é nessa imagem que vou procurar os 10 pontos mais claros.

Trabalhar com rgb era mais dificil.

HappyHippyHippo · May 10, 2013 at 02:49 PM

ok então ...

agora que tens o teu threshold (o valor do ponto de indíce N - 10 - 1), podes percorrer a matrix e todos que sejam desse valor ou superior serão supostamente pertencentes aos 10 pixeis de maior valor.

podes é ter somente um problema (com esta solução ou outra) :

- imagina que tens 20 pontos de puro branco > quais são os 10 maiores ?

MaxUpGenGros · May 10, 2013 at 03:16 PM

ok então ...

agora que tens o teu threshold (o valor do ponto de indíce N - 10 - 1), podes percorrer a matrix e todos que sejam desse valor ou superior serão supostamente pertencentes aos 10 pixeis de maior valor.

podes é ter somente um problema (com esta solução ou outra) :

- imagina que tens 20 pontos de puro branco > quais são os 10 maiores ?

Pois..È uma boa questão..

Eu aqui disse 10 pontos, mas, esses 10 pontos eram apenas para exemplo.que são poucos num total de 76400..

Eu irei colocar mais ou menos 500 pontos, Para ter uma área mais abrangente.

Portanto esse "problema" acho que não irá ser problema. pois após encontrar os 500 pontos mais elevados(com mais claridade), já passo para outra fase.

Vou tentar implementar essa solução agora a ver se consigo.😉

Portanto..

Tenho o array com os 10 pontos mais elevados nas ultimas 10 posições..

tenho que fazer um ciclo for a percorrer todas as linhas e todas as colunas, procurar nas mesmas quais os indices que contêm esse valor, e posso colocar esses indices em outro array?

MaxUpGenGros · May 10, 2013 at 03:29 PM

Será qualquer coisa a partir daqui certo?

public static int [] findIndex(BufferedImage image,int arr[])
   {
	   DataBuffer b = image.getRaster().getDataBuffer();
	   int h=image.getHeight();
	   int w=image.getWidth();		  

	   for(int i=0;i<h;i++)
	   {
		   for (int j=0;j<w;j++)
		   {

		   }
	   }
   }

HappyHippyHippo · May 10, 2013 at 03:35 PM

Pois..È uma boa questão..

Eu aqui disse 10 pontos, mas, esses 10 pontos eram apenas para exemplo.que são poucos num total de 76400..

Eu irei colocar mais ou menos 500 pontos, Para ter uma área mais abrangente.

Portanto esse "problema" acho que não irá ser problema. pois após encontrar os 500 pontos mais elevados(com mais claridade), já passo para outra fase.

o exemplo que dei era um exemplo.

eu dou outro para perceberes melhor o problema :

queres os N maiores, mas N, N-1 e N+1 são iguais.

isto quer dizer que existem vários pontos no limiar do limite de pontos que ficam abrangidos pelo threshold.

isto quer dizer que deverias escolher entre os pontos no limiar que fazem parte dos N e deixar de fora alguns que na realidade possuem o mesmo valor que o ponto N mas não podem fazer parte do grupo.

percebeste agora ?

procurar nas mesmas quais os indices que contêm esse valor

não, tens de procurar aqueles que tem um valor igual ou superior ! é um threshold, um limite é o teu limite inferior dos pontos pertencentes ao grupo dos pontos com valor mais alto

ruirodrigues1971 · May 10, 2013 at 11:52 PM

Peço desculpa não tinha percebido a pergunta.

Vamos usar esta estrutura

struct ElementosComCoordenada

{

double elemento;

string coordenada; //[1,1] --> "1,1"

};

Crias esta estruturas

Matriz de elementos ----> Array de ElementosComCoordenada

De seguida usar um algoritmo de ordenação ... com aqui só estás interessado em saber apenas os 10 melhores ... penso que o mais rápido (e que vai parar logo que descubras os 10 melhores) é o https://en.wikipedia.org/wiki/Sorting_algorithm#Selection_sort

basicamente o algoritmo procura o ElementoComCoordenada em toda Array coloca o maior no ínicio do array ...

o próximo ciclo já começa no segundo elemento ... quando tiveres os 10 maiores podes parar ...

as coordenadas estão nos elementos ElementosComCoordenada 😉

Espero que tenha feito sentido o que disse

https://www.youtube.com/embed/Yfj8Gp5gkPg?feature=oembed

https://www.youtube.com/embed/BSXIolKg5F8?feature=oembed

neste vídeo ele coloca no fim os maiores ... eu colocaria no início do teu exemplo, só para ser mais intuitivo.

Edited May 10, 2013 at 11:55 PM by ruirodrigues1971

HappyHippyHippo · May 11, 2013 at 12:14 AM

Peço desculpa não tinha percebido a pergunta.

Vamos usar esta estrutura

struct ElementosComCoordenada

{

double elemento;

string coordenada; //[1,1] --> "1,1"

};

Crias esta estruturas

Matriz de elementos ----> Array de ElementosComCoordenada

De seguida usar um algoritmo de ordenação ... com aqui só estás interessado em saber apenas os 10 melhores ... penso que o mais rápido (e que vai parar logo que descubras os 10 melhores) é o https://en.wikipedia.org/wiki/Sorting_algorithm#Selection_sort

basicamente o algoritmo procura o ElementoComCoordenada em toda Array coloca o maior no ínicio do array ...

o próximo ciclo já começa no segundo elemento ... quando tiveres os 10 maiores podes parar ...

as coordenadas estão nos elementos ElementosComCoordenada 😉

Espero que tenha feito sentido o que disse

https://www.youtube.com/embed/Yfj8Gp5gkPg?feature=oembed

https://www.youtube.com/embed/BSXIolKg5F8?feature=oembed

neste vídeo ele coloca no fim os maiores ... eu colocaria no início do teu exemplo, só para ser mais intuitivo.

estás a recomendar :

- criar uma estrutura

- alocar uma array de estruturas

- percorrer a imagem populando a lista estrutura

- obrigar a criar uma instãncia da classe Comparable a ser fornecia à função de ordenação

- ver os últimos elementos

...

em que ponto esse algoritmo é mais simples que ao que foi apresentado anteriormente ?

- criar uma cópia dos valores dos pixeis da imagem (1 linha)

- ordenar o array

- criar uma imagem com o mesmo tamanho da original

- percorrer a original e se o valor for igual ou maior que o threshold determinado, copiar o valor do pixel

Sign In

Obter o indice dos 10 valores mais altos de uma matriz

Recommended Posts

MaxUpGenGros

Top Posters In This Topic

Top Posters In This Topic

ruirodrigues1971

MaxUpGenGros

MaxUpGenGros

ruirodrigues1971

HappyHippyHippo

MaxUpGenGros

MaxUpGenGros

HappyHippyHippo

MaxUpGenGros

HappyHippyHippo

MaxUpGenGros

HappyHippyHippo

MaxUpGenGros

HappyHippyHippo

MaxUpGenGros

MaxUpGenGros

HappyHippyHippo

ruirodrigues1971

HappyHippyHippo

Create an account or sign in to comment

Create an account

Sign in

Home

Activity

Revista PROGRAMAR

Important Information