Estou resolvendo um problema de "mesclar" conjuntos de imagens sobrepostas. Esses conjuntos podem ser representados por gráfico ponderado não direcionado, como este:
Cada nó representa uma imagem. Imagens sobrepostas são conectadas por uma borda. O peso da borda representa o tamanho da área de sobreposição ( misturar uma sobreposição maior mais cedo leva a uma melhor qualidade geral ).
O algoritmo geralmente remove bordas. Pode fazê-lo sequencialmente ou em paralelo. No entanto, quando ocorre a mesclagem, os nós são mesclados e a estrutura do gráfico é alterada. Portanto, a paralelização é possível apenas em componentes conectados que não são sobrepostos!
Esses componentes não sobrepostos são DB e FEG. Podemos executar o algoritmo de mesclagem nesses componentes com segurança em paralelo. O resultado é o seguinte gráfico (os nós mesclados são exibidos em verde):
Agora não há mais paralelismo possível, porque dois componentes conectados estão sobrepostos (eles têm uma borda diretamente entre eles).
A versão paralela do algoritmo ficaria assim:
1. Find connected components (no two are connected directly) and create task for each.
2. Run the tasks in parallel.
3. Update graph.
4. Until single node remains, continue with 1.
A parte complicada é o primeiro passo: como encontrar o melhor conjunto de componentes conectados?
Uma maneira seria um algoritmo ganancioso que simplesmente encontra o maior número de componentes em uma determinada iteração. O algoritmo ganancioso maximizará a paralelização no início, mas ao custo de muitas iterações posteriormente.
A solução ideal pode estar trazendo uma boa quantidade de componentes conectados em cada iteração para maximizar a paralelização e minimizar o número de iterações ao mesmo tempo (portanto, existem duas variáveis na otimização).
Não consigo pensar em nenhum algoritmo de otimização que não seja o retrocesso, ou seja, pesquise o espaço de todas as evoluções possíveis e escolha aquele com paralelização máxima.
Os pesos das arestas podem ser ignorados, mas a versão aprimorada do algoritmo pode levar em consideração, pois as áreas maiores levam mais tempo para se misturar (por exemplo, a área do tamanho 200 leva aproximadamente duas vezes o tempo para se misturar do que duas áreas do tamanho 100). A consideração dos pesos pode levar a uma melhor estratégia na seleção de componentes (tempo de execução geral mais rápido do algoritmo).
Você tem alguma pista para esse algoritmo de otimização, que encontra a melhor estratégia de selecionar partes do gráfico para que haja paralelização máxima e número mínimo de iterações?
Respostas:
Isso é muito semelhante às sobreposições da sequência de genes na montagem do genoma. Capítulo 4 da tese de Ananth .
Em paralelo, você procura pares promissores e mantém uma estrutura de dados de localização de união distribuída. Consulte Tarjan e Vishkin para obter o algoritmo de gancho e atalho para recolher os componentes conectados.
Além disso, você pode tentar métodos gráficos recentes do DeBrujin em pedaços de linha de pixels de 64 bits. Eu acho que isso lhe dará os melhores resultados. Para ajudar com problemas de quantização, primeiro reduzi a dimensão dos pixels para 16 ou 8 bits em preto / branco. Em seguida, você aplica uma classificação paralela aos pedaços de 64 bits e os utiliza para inferir bordas entre as imagens.
fonte