Interpretación inaceptable Lectura Transparente .png Pixel by Pixel

Estoy creando una herramienta que detecta sprites en una hoja de sprites y convierte cada sprite encontrado en una nueva image Buffenetworking. Este process funciona, pero es prohibitivamente lento con ciertos formattings de image, principalmente imágenes transparentes, como esta:

Kenney's Game Assets - Animal Pack - Round

( Activos del juego de Kenney – Paquete de animales )

He creado un perfil de mi código y he determinado que la gran mayoría, en más del 99% del time de mi aplicación, se gasta solo en este método debido a las muchas llamadas a getRGB() .

 private fun findContiguousSprite(image: BuffenetworkingImage, startingPoint: Point, backgroundColor: Color): List<Point> { val unvisited = LinkedList<Point>() val visited = arrayListOf(startingPoint) unvisited.addAll(neighbors(startingPoint, image).filter { Color(image.getRGB(it.x, it.y)) != backgroundColor }) while (unvisited.isNotEmpty()) { val currentPoint = unvisited.pop() val currentColor = Color(image.getRGB(currentPoint.x, currentPoint.y)) if (currentColor != backgroundColor) { unvisited.addAll(neighbors(currentPoint, image).filter { !visited.contains(it) && !unvisited.contains(it) && (Color(image.getRGB(it.x, it.y)) != backgroundColor) }) visited.add(currentPoint) } } return visited.distinct() } 

He intentado optimizar el process de extracción de colors rgb como se ve en la pregunta Java: get matriz de píxeles de la image accediendo al búfer de datos ráster de la image, pero esto falla en las versiones más nuevas de Java con java.lang.ClassCastException: java.awt.image.DataBufferInt cannot be cast to java.awt.image.DataBufferByte .

Otros obstáculos incluyen el boxeo innecesariamente innecesario de colors, como en la línea Color(image.getRGB(it.x, it.y)) != backgroundColor . Sin embargo, mientras que image.getRGB() regresa por defecto en el espacio de color RGBA, background.rgb solo devuelve el espacio de color sRGB.

Pregunta: ¿Cómo puedo mejorar el performance de la lectura de una BuffenetworkingImage especialmente en el caso de imágenes transparentes? ¿Por qué es tan rápido con casi cualquier otra image .png que arrojo, excepto por estos?

Nota: Si bien el código está en Kotlin, acepto Java o cualquier otro lenguaje JVM como respuesta.

Volcado de código: en caso de que quiera la sección completa del código:

 private fun findSpriteDimensions(image: BuffenetworkingImage, backgroundColor: Color): List<Rectangle> { val workingImage = image.copy() val spriteDimensions = ArrayList<Rectangle>() for (pixel in workingImage) { val (point, color) = pixel if (color != backgroundColor) { logger.debug("Found a sprite starting at (${point.x}, ${point.y})") val spritePlot = findContiguousSprite(workingImage, point, backgroundColor) val spriteRectangle = spanRectangleFrom(spritePlot) logger.debug("The identified sprite has an area of ${spriteRectangle.width}x${spriteRectangle.height}") spriteDimensions.add(spriteRectangle) workingImage.erasePoints(spritePlot, backgroundColor) } } return spriteDimensions } private fun findContiguousSprite(image: BuffenetworkingImage, startingPoint: Point, backgroundColor: Color): List<Point> { val unvisited = LinkedList<Point>() val visited = arrayListOf(startingPoint) unvisited.addAll(neighbors(startingPoint, image).filter { Color(image.getRGB(it.x, it.y)) != backgroundColor }) while (unvisited.isNotEmpty()) { val currentPoint = unvisited.pop() val currentColor = Color(image.getRGB(currentPoint.x, currentPoint.y)) if (currentColor != backgroundColor) { unvisited.addAll(neighbors(currentPoint, image).filter { !visited.contains(it) && !unvisited.contains(it) && (Color(image.getRGB(it.x, it.y)) != backgroundColor) }) visited.add(currentPoint) } } return visited.distinct() } private fun neighbors(point: Point, image: Image): List<Point> { val points = ArrayList<Point>() val imageWidth = image.getWidth(null) - 1 val imageHeight = image.getHeight(null) - 1 // Left neighbor if (point.x > 0) points.add(Point(point.x - 1, point.y)) // Right neighbor if (point.x < imageWidth) points.add(Point(point.x + 1, point.y)) // Top neighbor if (point.y > 0) points.add(Point(point.x, point.y - 1)) // Bottom neighbor if (point.y < imageHeight) points.add(Point(point.x, point.y + 1)) // Top-left neighbor if (point.x > 0 && point.y > 0) points.add(Point(point.x - 1, point.y - 1)) // Top-right neighbor if (point.x < imageWidth && point.y > 0) points.add(Point(point.x + 1, point.y - 1)) // Bottom-left neighbor if (point.x > 0 && point.y < imageHeight - 1) points.add(Point(point.x - 1, point.y + 1)) // Bottom-right neighbor if (point.x < imageWidth && point.y < imageHeight) points.add(Point(point.x + 1, point.y + 1)) return points } 

Primera optimization

Impulsado por el comentario de @Durandal, decidí cambiar mi ArrayList a HashSet. También encontré una forma de preservar los valores alfa usando un constructor alternativo para Color, Color(rgb, preserveAlpha) . Ahora ya no necesito boxear getRGB() antes de comparar los dos valores.

 private fun findContiguousSprite(image: BuffenetworkingImage, point: Point, backgroundColor: Color): List<Point> { val unvisited = LinkedList<Point>() val visited = hashSetOf(point) unvisited.addAll(neighbors(point, image).filter { image.getRGB(it.x, it.y) != backgroundColor.rgb }) while (unvisited.isNotEmpty()) { val currentPoint = unvisited.pop() val currentColor = image.getRGB(currentPoint.x, currentPoint.y) if (currentColor != backgroundColor.rgb) { unvisited.addAll(neighbors(currentPoint, image).filter { !visited.contains(it) && !unvisited.contains(it) && image.getRGB(it.x, it.y) != backgroundColor.rgb }) visited.add(currentPoint) } } return visited.toList() } 

Esto procesó la image de arriba en 319ms . ¡Increíble!

Usar contains en una ArrayList o LinkedList tiene complejidad O (n). Esto puede convertirse rápidamente en una gran sobrecarga, considerando que está haciendo muchas llamadas a contains () en su filter. La complejidad de la búsqueda visitada.contiene () crece con el tamaño de la image procesada (más píxeles para visitar y más píxeles visitados, convirtiendo la complejidad en O (n ^ 2)).

La forma más sencilla de networkingucir este costo es usar un tipo de colección que contenga un resumen rápido; como O (1) en el caso de HashSet. La semántica Set también se ajusta a sus requisitos un poco mejor que las lists, ya que entiendo que las collections visitadas / no visitadas no deben permitir duplicates. Como Sets no permite duplicates por contrato, algunos de los controles de contenido explícito pueden eliminarse; en los lugares que desee responder al evento del punto que se agrega primero, también puede hacer uso del resultado boolean que el método add () da (verdadero cuando el elemento no estaba presente y se agregó).

Si bien el boxeo / unboxing cuesta algo de time, es un costo lineal. La networkingucción de la sobrecarga del boxeo requerirá bastantes cambios en el código y "solo" obtendrá una aceleración de factor constante. Las collections estándar no funcionan con primitivas (sin el autoboxing que desea evitar en primer lugar). Si bien hay collections de terceros de propósito especial (se me ocurre Trove) que manejan primitivas sin boxeo. Solo iría de esta manera si fuera absolutamente necesario, cambiar a types primitivos donde sea posible haría que tu código sea más largo y algo más ofuscado.

  • ¿Cómo establecer el margen inferior a FAB en el layout Anko DSL?
  • Android Despliegue las fonts de kotlin a un repository de maven
  • La demostración IOU de Corda V1.0 no funciona en Windows
  • ¿Cómo puedo inicializar la variable antes de cada testing usando el marco kotlin-test
  • ¿Cómo inyectar reemploops de testing en el gráfico de dependencia pnetworkingeterminado?
  • ¿Puede elegir la versión de Android Studio kotlin?
  • Las declaraciones destructivas de KOTLIN REPL no funcionan con Pair
  • Crear classs de Kotlin en Android Studio usando acciones de intención
  • Kotlin, problema de condición de carrera
  • ¿Por qué Kotlin comstack más rápido que Scala?
  • Es posible get nombres de variables locales programáticamente en Java o Kotlin?