Ir para o conteúdo
MaxUpGenGros

Obter o indice dos 10 valores mais altos de uma matriz

Mensagens Recomendadas

MaxUpGenGros    0
MaxUpGenGros

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.


FCoelho

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
MaxUpGenGros    0
MaxUpGenGros

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..


FCoelho

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
MaxUpGenGros    0
MaxUpGenGros

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..


FCoelho

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
ruirodrigues1971    2
ruirodrigues1971

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 :P

no fim nessa variável maior irá estar o resultado ;)

Editado por ruirodrigues1971

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
HappyHippyHippo    1140
HappyHippyHippo

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


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
MaxUpGenGros    0
MaxUpGenGros

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?


FCoelho

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
MaxUpGenGros    0
MaxUpGenGros

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;

}

Editado por MaxUpGenGros

FCoelho

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
HappyHippyHippo    1140
HappyHippyHippo

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);
}

Editado por HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
MaxUpGenGros    0
MaxUpGenGros

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. :P

Mas obrigado pela dica.


FCoelho

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
HappyHippyHippo    1140
HappyHippyHippo

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 ?


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
MaxUpGenGros    0
MaxUpGenGros

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.


FCoelho

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
HappyHippyHippo    1140
HappyHippyHippo

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 ?


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
MaxUpGenGros    0
MaxUpGenGros

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?


FCoelho

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
MaxUpGenGros    0
MaxUpGenGros

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++)
		   {

		   }
	   }
   }


FCoelho

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
HappyHippyHippo    1140
HappyHippyHippo

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


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
ruirodrigues1971    2
ruirodrigues1971

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

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

Editado por ruirodrigues1971

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
HappyHippyHippo    1140
HappyHippyHippo

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

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


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
ruirodrigues1971    2
ruirodrigues1971

Não acompanhei todo o tópico, estava só a responder à pergunta inicial de forma genérica e também com um algoritmo simples.

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

claro que se fosse eu a fazer e tivesse numa de ser o mais rápido e o que ocupasse menos memória ... aí iria para outro tipo de soluções ;)

No caso especifico em que só se quer os 10 maiores, não é preciso ordenar o vector e com isso se poupa bastante tempo ao algoritmo global... por isso é que propus o selection sort, pois é simples e pode ser interrompido após a 10ª iteração do algoritmo de ordenação ;) ... claro que dependendo da dimensão do problema temos diferentes soluções.

Se o objectivo é ele implementar um algoritmo de inicio até ao fim, penso que este algoritmo é simples e é competitivo com o sort da Arrays que usa o mergeSort http://www.javamex.com/tutorials/collections/sorting_java_algorithm_performance.shtml ... só que aqui ele não está a implementar o algoritmo de raiz, está basicamente a usar um algoritmo feito por outros.

Solução1 usando o sort já feito

Custo para criar Estrutura paralela = K

Custo para ordenar usando o sort do Array NxLg N

Solução2 usando a variante do Selection Sort

Custo para criar Estrutura paralela = K

Custo para encontrar os 10 melhores usando o sort do Array 10 xN

com N = 76400 e 10 melhores

Solução 1 = 1239306

Solução 2 = 764000

A solução 1 é 62% mais lenta ;) ... mas história não acaba aqui a solução1 é a melhor logo nos 17 melhores ... ou seja se a ideia é ter mais de 16 melhores, então é de usar o mergeSort ... e usando então o sort dado pelo Java :P

Claro que se o objectivo é implementar um algoritmo simples e rápido, continuaria com a solução2, mas se o objectivo é ser o mais rápido e mais de 16 melhores iria para a solução1 (usando o sort dado ou implementar o merge sort que é algo complexo para os iniciados). Depende sempre do objectivo do exercício(implementar um algoritmo de ordenação, apenas resolver o problema, etc.) e do tempo disponível que nos é dado para resolver o problema. Eu pensava que o objectivo dele fosse o de implementar uma algoritmo de ordenação ... e não usar um já feito ;)

Desculpa este testamento ... como adoro algoritmia

Um abraço,

Editado por ruirodrigues1971

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
MaxUpGenGros    0
MaxUpGenGros

Este trabalho está a ser feito com sockets, e tenho que analisar as imagens que chegam quase em tempo real..

Por isso interessa-me a solução mais rápida..


FCoelho

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
HappyHippyHippo    1140
HappyHippyHippo

Este trabalho está a ser feito com sockets, e tenho que analisar as imagens que chegam quase em tempo real..

Por isso interessa-me a solução mais rápida..

não achas que já devias ter dito isso ???


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
pedrosorio    4
pedrosorio

Já que estamos a debater várias hipóteses, dou também a minha sugestão:

Como os teus valores de intensidade estão num range pequeno e bem definido (provavelmente [0,255]) para encontrar os maiores K elementos, aconselho-te a usar http://en.wikipedia.org/wiki/Counting_sort.

Basicamente, calculas o histograma da intensidade da imagem (uma passagem pelos W*H pixels em que vais actualizando um contador com 256 elementos):

Array hist (256 elementos = 0)
for x = 1 to W
 for y = 1 to H
   hist[intensidade(x,y)] = hist[intensidade(x,y)] + 1

Depois percorres o histograma contando o número de pixels com intensidade maior ou igual a in começando em 255 (já que queres os maiores K), e diminuis a intensidade enquanto o total de pixels contados N < K:

N = 0
in = 256
Do
 in = in - 1
 N = N + hist[in]
While N < K

O índice in, em que parares dá-te a menor intensidade que vais querer considerar (existem N pixels com intensidade >= in)

Depois disto só precisas de percorrer novamente os W*H pixels e acrescentar a uma lista as coordenadas dos pixels que tiverem intensidade >= in. Isto dá-te uma lista que provavelmente tem mais de K pixels. Se quiseres ter apenas K, manténs um contador do número de pixels com intensidade in que ainda podes adicionar (basicamente se contaste N pixels e queres K, não podes colocar na lista todos os pixels de intensidade in mas apenas hist[in] - N + K):

countin = hist[in] - N + K
lista = []
for x = 1 to W
 for y = 1 to H
   if intensidade(x,y) >= in
     if intensidade(x,y) == in
       if countin > 0
         lista.add([x,y])
         countin = countin - 1
     else
       lista.add([x,y])

No fim tens a lista com K coordenadas de pixels. Na prática, como sabes que queres K pixels podes começar logo com um array de K coordenadas e limitar-te a preenchê-lo.

Com esta abordagem não usas réplicas da imagem (memória extra O(K)), e o número de operações é 2*W*H + 255 (i.e. independente de K, e linear no número de pixels da imagem). Em suma, menos memória extra (na prática apenas a lista com o número de pixels que queres extrair + 256 inteiros =P) e tempo de execução imbatível quando comparado com qualquer abordagem que use sorts com compares (que é sempre na melhor das hipóteses O(W*H*log(W*H))).

Editado por pedrosorio

Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
MaxUpGenGros    0
MaxUpGenGros

não achas que já devias ter dito isso ???

Porquê que dizes isso?

Vai afectar muito a maneira como tenho que abordar o problema?


FCoelho

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.