Google+ Seguidores

miércoles, 15 de agosto de 2018

Ordenamiento por Mezcla ("Merge Sort") - Algoritmos de Ordenamiento

Introducción:

Hola amigos de Internet, bienvenidos a Mi Diario Python, el mejor blog para Aprender Python.

En este árticulo, nos dedicaremos a conocer el algoritmo de ordenamiento "Ordenamiento por Mezcla", más conocido como Merge Sort.

Veremos sus características, su pseudocódigo y al final realizaremos una implementación en el lenguaje de programación Python.

¿Que te parece? Comencemos.

Ordenamiento por Mezcla

El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás.

La idea de los algoritmos de ordenación por mezcla es dividir la matriz por la mitad una y otra vez hasta que cada pieza tenga solo un elemento de longitud. Luego esos elementos se vuelven a juntar (mezclados) en orden de clasificación.

A continuación les mostrare una representación del algoritmo en acción:


Comenzamos dividiendo la matriz:

[31,4,88,2,4,2,42]
[31,4,88,1][4,2,42] Dividimos en 2 partes

[31,4][88,1][4,2][42] Dividimos en 4 partes

[31][4][88][1][4][2][42] Piezas individuales

Ahora tenemos que unirlos de nuevo en orden de mezcla:

Primero fusianamos elementos individuales en pares. Cada par se fusiona en orden de mezcla.

[4,31][1,88][2,4][42]

Luego fusionamos los pares en orden de mezcla:

[1,4,31,88][2,4,42]

Y luego fusionamos los dos últimos grupos.

[1,2,4,4,31,42,88]

Y listo, nuestra lista esta ordenada.

Sí, lo se, al principio puede ser que nos confundamos un poco.

Pseudocódigo del algoritmo:


El pseudocódigo del algoritmo es este (Gracias a nuestros infiltrados en Wikipedia):

function mergesort(m)
  var list left, right, result
  if length(m) ≤ 1
      return m
  else
      var middle = length(m) / 2
      for each x in m up to middle - 1
          add x to left
      for each x in m at and after middle
          add x to right
      left = mergesort(left)
      right = mergesort(right)
      if last(left) ≤ first(right) 
         append right to left
         return left
      result = merge(left, right)
      return result

function merge(left, right)
  var list result
  while length(left) > 0 and length(right) > 0
      if first(left) ≤ first(right)
          append first(left) to result
          left = rest(left)
      else
          append first(right) to result
          right = rest(right)
  if length(left) > 0 
      append rest(left) to result
  if length(right) > 0 
      append rest(right) to result
  return result

Como pueden observar, son dos funciones. La primera, merge_sort, ordena la lista, mientras que la segunda, merge, se encarga de intercalar los elementos de las listas left y right que merge recibe como parámetros.

Implementación del algoritmo:

No hay nada como un ejemplo para entender mejor como funciona algo. 

Realizaremos un implemntación del algoritmo y sus dos funciones, basándonos en el pseudocódigo mostrado anteriormente.

Puedes ver y dercargar todo el código ingresando al siguiente enlace: https://gist.github.com/LuisAlejandroSalcedo/1275c76efa33d6bbead0c8c5ae1f8f1e.

# Función merge_sort
def merge_sort(lista):
 
   """
   Lo primero que se ve en el psudocódigo es un if que
   comprueba la longitud de la lista. Si es menor que 2, 1 o 0, se devuelve la lista.
   ¿Por que? Ya esta ordenada. 
   """
   if len(lista) < 2:
      return lista
    
    # De lo contrario, se divide en 2
   else:
        middle = len(lista) // 2
        right = merge_sort(lista[:middle])
        left = merge_sort(lista[middle:])
        return merge(right, left)
    
# Función merge
def merge(lista1, lista2):
    """
    merge se encargara de intercalar los elementos de las dos
    divisiones.
    """
    i, j = 0, 0 # Variables de incremento
    result = [] # Lista de resultado
 
   # Intercalar ordenadamente
    while(i < len(lista1) and j < len(lista2)):
        if (lista1[i] < lista2[j]):
            result.append(lista1[i])
            i += 1
        else:
            result.append(lista2[j])
            j += 1
 
   # Agregamos los resultados a la lista
    result += lista1[i:]
    result += lista2[j:]
 
    # Retornamos el resultados
    return result

# Prueba del algoritmo

lista = [31,3,88,1,4,2,42]

merge_sort_result = merge_sort(lista)  
print(merge_sort_result)

[1, 2, 3, 4, 31, 42, 88]

Como pueden apreciar, el resultado es satisfactorio.

He utilizado la misma lista que use en el ejemplo del principio.

¿Que te parecio? ¿Alguna duda? No dudes en dejar tu comentario.

Mi nombre es Luis, y fue un placer compartir mis conocimientos con todos ustedes :D.
Seguir Leyendo

martes, 14 de agosto de 2018

Implementación de un Árbol AVL - Estructuras de Datos con Python

Introducción:

Hola amigos de Internet, les doy la bienvenida a Mi Diario Python, el mejor blog para Aprender Python.

En este articulo, nos enfocaremos en conocer los principios básicos de los árboles AVL, un tipo especial de árbol binario. Al final, realizaremos una implementación utilizando el lenguaje de programación Python.

¿Que es un árbol AVL?

Los árboles AVL son un tipo especial de árbol binario. Inventado por los matemáticos rusos Adelson-Velskii y Landis, de allí el nombre AVL. 

El árbol AVL tiene la peculiaridad de ser el primer árbol binario auto-balanceable. 

Los árboles AVL están siempre equilibrados de tal modo que para todos los nodos la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa.

La siguiente imagen es una representación de su equilibrio:

Imagen relacionada

Para conseguir esta propiedad de equilibrio, la inserción y borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado de rompe la condición de equilibrio, hay que realizar una serie de rotaciones de nodos.

Representación de una construcción de un árbol AVL y sus rotaciones


Operaciones:

Otro punto a tener en cuenta son las operaciones que se pueden realizar en un árbol AVL. Esto nos servira para saber que métodos agregar al momento de la implementación.

Rotaciones:

El reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. Pueden darse dos casos: rotación simple o rotación doble; a su vez ambos casos pueden ser hacia la derecha o hacia la izquierda.

Podemos realizar 4 tipos de rotaciones:

Rotación simple a la derecha:

De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i’) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (r), el hijo derecho de i (d’) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d).

rotación simple a la derecha inicio


Rotación simple a la izquierda:

De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), consiste en formar un nuevo árbol cuya raíz sea la raíz del hijo derecho, como hijo derecho colocamos el hijo derecho de d (nuestro d’) y como hijo izquierdo construimos un nuevo árbol que tendrá como raíz la raíz del árbol (r), el hijo izquierdo de d será el hijo derecho (i’) de r y el hijo izquierdo será el hijo izquierdo del árbol (i).


Precondición : Tiene que tener hijo derecho no vacío.

Rotación doble a la derecha:


La Rotación doble a la Derecha son dos rotaciones simples, primero rotación simple izquierda y luego rotación simple derecha.

rotación a la izquierda inicio
rotación a la izquierda final


Rotación doble a la izquierda

La Rotación doble a la Izquierda son dos rotaciones simples, primero rotación simple derecha y luego rotación simple izquierda.

rotación a la izquierda iniciorotación a la izquierda final


Inserción:

La inserción en un árbol de AVL puede ser realizada insertando el valor dado en el árbol como si fuera un árbol de búsqueda binario desequilibrado y después retrocediendo hacia la raíz, rotando sobre cualquier nodo que pueda haberse desequilibrado durante la inserción.

Proceso de inserción:

  1. Buscar hasta encontrar la posición de inserción o modificación (proceso idéntico a inserción en árbol binario de búsqueda).
  2. Insertar el nuevo nodo con factor de equilibrio “equilibrado”.
  3. Desandar el camino de búsqueda, verificando el equilibrio de los nodos, y re-equilibrando si es necesario.
Insercion1.jpg Insercion2.jpg Insercion3-1.jpg Insercion3-2.jpg Insercion4-1.jpg Insercion4-2.jpg

Referencias: 


Implementación:

Ahora sí es el momento de escribir código. 

"""
Árbol AVL - Implementación en Python
"""

from __future__ import print_function

"""
Declaramos la clase "Node", con cada una de sus propiedades.
"""
class Node:
    def __init__(self, label):
        self.label = label
        self._parent = None
        self._left = None
        self._right = None
        self.height = 0

    @property
    def right(self):
        return self._right

    @right.setter
    def right(self, node):
        if node is not None:
            node._parent = self
            self._right = node

    @property
    def left(self):
        return self._left

    @left.setter
    def left(self, node):
        if node is not None:
            node._parent = self
            self._left = node

    @property
    def parent(self):
        return self._parent

    @parent.setter
    def parent(self, node):
        if node is not None:
            self._parent = node
            self.height = self.parent.height + 1
        else:
            self.height = 0

# Declaramos la clase AVL
class AVL:

    def __init__(self):
        self.root = None
        self.size = 0

        """
        Operación de inserción para agregar nuevos nodos
        al árbol.
        """
    def insert(self, value):
        node = Node(value)

        if self.root is None:
            self.root = node
            self.root.height = 0
            self.size = 1
        else:
            dad_node = None
            curr_node = self.root

            while True:
                if curr_node is not None:

                    dad_node = curr_node

                    if node.label < curr_node.label:
                        curr_node = curr_node.left
                    else:
                        curr_node = curr_node.right
                else:
                    node.height = dad_node.height
                    dad_node.height += 1
                    if node.label < dad_node.label:
                        dad_node.left = node
                    else:
                        dad_node.right = node
                    self.rebalance(node)
                    self.size += 1
                    break

        # Operación de rotación
    def rebalance(self, node):
        n = node

        while n is not None:
            height_right = n.height
            height_left = n.height

            if n.right is not None:
                height_right = n.right.height

            if n.left is not None:
                height_left = n.left.height

            if abs(height_left - height_right) > 1:
                if height_left > height_right:
                    left_child = n.left
                    if left_child is not None:
                        h_right = (left_child.right.height
                                    if (left_child.right is not None) else 0)
                        h_left = (left_child.left.height
                                    if (left_child.left is not None) else 0)
                    if (h_left > h_right):
                        self.rotate_left(n)
                        break
                    else:
                        self.double_rotate_right(n)
                        break
                else:
                    right_child = n.right
                    if right_child is not None:
                        h_right = (right_child.right.height
                            if (right_child.right is not None) else 0)
                        h_left = (right_child.left.height
                            if (right_child.left is not None) else 0)
                    if (h_left > h_right):
                        self.double_rotate_left(n)
                        break
                    else:
                        self.rotate_right(n)
                        break
            n = n.parent

    def rotate_left(self, node):
        aux = node.parent.label
        node.parent.label = node.label
        node.parent.right = Node(aux)
        node.parent.right.height = node.parent.height + 1
        node.parent.left = node.right


    def rotate_right(self, node):
        aux = node.parent.label
        node.parent.label = node.label
        node.parent.left = Node(aux)
        node.parent.left.height = node.parent.height + 1
        node.parent.right = node.right

    def double_rotate_left(self, node):
        self.rotate_right(node.getRight().getRight())
        self.rotate_left(node)

    def double_rotate_right(self, node):
        self.rotate_left(node.getLeft().getLeft())
        self.rotate_right(node)

    def empty(self):
        if self.root is None:
            return True
        return False

    def preShow(self, curr_node):
        if curr_node is not None:
            self.preShow(curr_node.left)
            print(curr_node.label, end=" ")
            self.preShow(curr_node.right)

    def preorder(self, curr_node):
        if curr_node is not None:
            self.preShow(curr_node.left)
            self.preShow(curr_node.right)
            print(curr_node.label, end=" ")

    def getRoot(self):
        return self.root

if __name__ == '__main__':
    t = AVL()
    t.insert(5)
    t.insert(9)
    t.insert(13)
    t.insert(10)
    t.insert(17)
    t.preShow(t.root)

5 9 10 13 17 

El método preShow nos mostrara nos nodos del árbol. Todo de manera equilibrada.

¿Alguna duda? No dudes en dejar tu comentario.

Mi nombre es Luis, y fue un placer compartir mis conocimientos con todos ustedes :D.
Seguir Leyendo

domingo, 12 de agosto de 2018

Procesamiento de Imágenes con Python y Scikit-Image

Introducción:

Hola amigos de Internet, les doy la bienvenida a Mi Diario Python, el mejor blog para Aprender Python. 

En este articulo nos dedicaremos a conocer algunos algoritmos utilizados en el procesamiento de imágenes y los aplicaremos utilizando la librería Scikit-Image.

Procesamiento de Imagenes:

Antes de poder ir a la practica debemos conocer algunos conceptos básicos.

Una imagen es una función bidimensional f(x,y) que representa la intensidad de la luz, donde x e y son coordenadas espaciales y el valor de f es proporcional al brillo de la imagen en un punto cualquiera.

Sabes esto es muy importante ya que nos da la base para poder saber como obtener valores de pixeles. 

En las imágenes, estas pueden ser representadas como una matriz cuyos índices de fila y columna identifican un punto de la imagen el cual es un indicador del nivel de brillo. Estos puntos de la matriz son a los que llamamos pixeles.

 Otro punto a tener en cuenta son las imágenes en escala de grises.

Cuando hablamos de imágenes en escala de grises, nos referimos a una imagen de 8 bits donde cada pixel de la imagen tiene asignada una intensidad con un rango de 0 a 255. 

Para obtener información relevante de una imagen se utiliza el procesamiento digital de señales mediante el cual se busca transformar una imagen en otra mediante procesos algorítmicos con el objetivo de resaltar cierta información de interés o atenuar información irrelevante.

Pre-procesado:

Dentro de la etapa de pre-procesado se tienen diferentes técnicas, las cuales sin aplicadas dependiendo de problema que presenta la imagen.

A continuación realizaremos algunos ejercicios comunes en esta área.

Detección de bordes:

Esto es algo muy común. Cuando hablamos de "detección de bordes", nos referimos a detectar discontinuidades en el nivel de intensidad de la imagen. 

Para realizar este tipo de detección, existen diferentes tipos de filtros, a continuación implementaremos algunos de estos filtros utilizando scikit-imagee y matplotlib:

# Librerias necesarias
from skimage import io
from skimage import filters
from skimage.color import rgb2gray
import matplotlib.pyplot as plt

# Abrimos la imagen
imagen = io.imread("imagen.jpg")
imagen_g = rgb2gray(imagen)

# Filtros: sobel, roberts, prewitt
filtros = [filters.sobel, filters.roberts, filters.prewitt]

for filtro in filtros:
    # Aplicamos cada uno de los filtros
    img_fil = filtro(imagen_g)
    
    # Mostramos los resultados 
    plt.imshow(img_fil)
    plt.show()

png
png
png

Mejoramiento del contraste:

En algunas ocasiones se necesita aumentar el contraste de las imágenes. Al aumentar el contraste incrementa el cambio en la intensidad de la luz entre las zonas más oscuras o más claras.

Scikit-Image nos proporciona diversas funciones para el mejoramiento de contraste:

from skimage import exposure
from skimage import io
import numpy as np
import matplotlib.pyplot as plt

imagen = io.imread("imagen.jpg")

# Estiramiento de contraste
p2, p98 = np.percentile(imagen, (2,98))
img_rescale = exposure.rescale_intensity(imagen, in_range=(p2,p98))

# Ecualización
img_eq = exposure.equalize_hist(imagen)

# Ecualización adaptiva
img_adapteq = exposure.equalize_adapthist(imagen, clip_limit=0.03)

for eq in (img_eq, img_adapteq):
    plt.imshow(eq)
    plt.show()
C:\Users\PILAR\AppData\Local\Programs\Python\Python36-32\lib\site-packages\skimage\exposure\exposure.py:63: UserWarning: This might be a color image. The histogram will be computed on the flattened image. You can instead apply this function to each color channel.
  warn("This might be a color image. The histogram will be "
C:\Users\PILAR\AppData\Local\Programs\Python\Python36-32\lib\site-packages\skimage\util\dtype.py:130: UserWarning: Possible precision loss when converting from float64 to uint16
  .format(dtypeobj_in, dtypeobj_out))
png
png

Eliminación de ruido:

Existen diferentes tipos de ruidos que pueden reducir la calidad de la imagen. Uno de los más comunes es el ruido conocido como sal y pimienta, el cual es producido por perturbaciones agudas y repentinas en la imagen causadas por el mismo equipo de medición o el ambiente.

Para minimizar el ruido, podemos utilizar el filtro de medianas:

from skimage import io
from skimage.filters.rank import median
from skimage.morphology import disk
from skimage.color import rgb2gray
import matplotlib.pyplot as plt

imagen = io.imread("charlie.jpg")
img_gray = rgb2gray(imagen)

med = median(img_gray)

plt.imshow(med)
plt.show()
C:\Users\PILAR\AppData\Local\Programs\Python\Python36-32\lib\site-packages\skimage\util\dtype.py:130: UserWarning: Possible precision loss when converting from float64 to uint8
  .format(dtypeobj_in, dtypeobj_out))
png

Restauración:

Al restaurar una imagen se busca normalmente eliminar el ruido, mejorar el brillo, el color y los detalles de la misma, recuperando de esta forma aquellas partes que han sido deterioradas

Para la restauración, utilizaremos el filtro Wiener:

from skimage import restoration
from scipy.signal import convolve2d
from skimage import io
from skimage.color import rgb2gray
import numpy as np
import matplotlib.pyplot as plt

imagen = io.imread("imagen_ruido.jpg")

img = rgb2gray(imagen)

psf = np.ones((5,5)) / 25

img = convolve2d(img, psf, 'same')
img += 0.1 * img.std() * np.random.standard_normal((img.shape))
deconvolved_img = restoration.wiener(img, psf, 100)

plt.imshow(deconvolved_img)
plt.show()
png

Suavizar y resaltar contornos:

En algunos casos no basta con detectar los bordes en la imagen, sino que se necesita detectarlos y suavizarlos. Para esto se utiliza el filtro Canny, el cual se compone de tres etapas: la primera dirigida a la reducción del ruido, obteniendo una imagen suavizada y la segunda donde se encuentra los gradientes en la intensidad de los píxeles.

from skimage import io
from skimage import feature
from skimage.color import rgb2gray
import matplotlib.pyplot as plt

imagen = io.imread("mario.jpg")
img = rgb2gray(imagen)
edge = feature.canny(img)
plt.imshow(edge)
plt.show()
png


Estos algunos ejemplos básicos que nos servirán mucho.

Puedes ver y descargar todos los ejemplo en formato ipynb: https://github.com/LuisAlejandroSalcedo/Procesamiento-de-Imagenes-con-Python-y-Scikit-Image.

¿Alguna duda ? No dudes en dejar tu comentario.

Mi nombre es Luis y fue un placer compartir mis conocimientos con todos ustedes :D. 

Seguir Leyendo
Powered by Blogger .