# Path: kraken/lib/morph.py
# def label(image: np.ndarray, **kw) -> np.ndarray:
# def find_objects(image: np.ndarray, **kw) -> np.ndarray:
# def r_dilation(image, size, origin=0):
# def r_erosion(image, size, origin=0):
# def rb_dilation(image, size, origin=0):
# def rb_erosion(image, size, origin=0):
# def rb_opening(image, size, origin=0):
# def spread_labels(labels, maxdist=9999999):
# def correspondences(labels1, labels2):
# def propagate_labels(image, labels, conflict=0):
# def select_regions(binary, f, min=0, nbest=100000):
# 
# Path: kraken/lib/sl.py
# def dim0(s):
# def dim1(s):
# def area(a):
# def width(s):
# def height(s):
# def aspect(a):
# def xcenter(s):
# def ycenter(s):
# def center(s):
# 
# Path: kraken/lib/util.py
# def pil2array(im: Image.Image, alpha: int = 0) -> np.ndarray:
#     if im.mode == '1':
#         return np.array(im.convert('L'))
#     return np.array(im)
# 
# def is_bitonal(im: Union[Image.Image, torch.Tensor]) -> bool:
#     """
#     Tests a PIL image or torch tensor for bitonality.
# 
#     Args:
#         im: Image to test
# 
#     Returns:
#         True if the image contains only two different color values. False
#         otherwise.
#     """
#     if isinstance(im, Image.Image):
#         return im.getcolors(2) is not None and len(im.getcolors(2)) == 2
#     elif isinstance(im, torch.Tensor):
#         return len(im.int().unique()) == 2
# 
# def get_im_str(im: Image.Image) -> str:
#     return im.filename if hasattr(im, 'filename') else str(im)
# 
# Path: kraken/lib/exceptions.py
# class KrakenInputException(Exception):
# 
#     def __init__(self, message=None):
#         Exception.__init__(self, message)
# 
# Path: kraken/lib/segmentation.py
# def reading_order(lines: Sequence[Tuple[slice, slice]], text_direction: str = 'lr') -> np.ndarray:
#     """Given the list of lines (a list of 2D slices), computes
#     the partial reading order.  The output is a binary 2D array
#     such that order[i,j] is true if line i comes before line j
#     in reading order."""
# 
#     logger.info('Compute reading order on {} lines in {} direction'.format(len(lines), text_direction))
# 
#     order = np.zeros((len(lines), len(lines)), 'B')
# 
#     def _x_overlaps(u, v):
#         return u[1].start < v[1].stop and u[1].stop > v[1].start
# 
#     def _above(u, v):
#         return u[0].start < v[0].start
# 
#     def _left_of(u, v):
#         return u[1].stop < v[1].start
# 
#     def _separates(w, u, v):
#         if w == u or w == v:
#             return 0
#         if w[0].stop < min(u[0].start, v[0].start):
#             return 0
#         if w[0].start > max(u[0].stop, v[0].stop):
#             return 0
#         if w[1].start < u[1].stop and w[1].stop > v[1].start:
#             return 1
#         return 0
# 
#     if text_direction == 'rl':
#         def horizontal_order(u, v):
#             return not _left_of(u, v)
#     else:
#         horizontal_order = _left_of
# 
#     for i, u in enumerate(lines):
#         for j, v in enumerate(lines):
#             if _x_overlaps(u, v):
#                 if _above(u, v):
#                     order[i, j] = 1
#             else:
#                 if [w for w in lines if _separates(w, u, v)] == []:
#                     if horizontal_order(u, v):
#                         order[i, j] = 1
#     return order
# 
# def topsort(order: np.ndarray) -> List[int]:
#     """Given a binary array defining a partial order (o[i,j]==True means i<j),
#     compute a topological sort.  This is a quick and dirty implementation
#     that works for up to a few thousand elements."""
#     logger.info('Perform topological sort on partially ordered lines')
#     n = len(order)
#     visited = np.zeros(n)
#     L = []
# 
#     def _visit(k):
#         if visited[k]:
#             return
#         visited[k] = 1
#         a, = np.nonzero(np.ravel(order[:, k]))
#         for line in a:
#             _visit(line)
#         L.append(k)
# 
#     for k in range(n):
#         _visit(k)
#     return L


import logging
import numpy as np
from typing import Tuple, List, Callable, Optional, Dict, Any, Union
from scipy.ndimage.filters import (gaussian_filter, uniform_filter,
                                   maximum_filter)
from kraken.lib import morph, sl
from kraken.lib.util import pil2array, is_bitonal, get_im_str
from kraken.lib.exceptions import KrakenInputException
from kraken.lib.segmentation import reading_order, topsort
    elif text_direction == 'vertical-rl':
        angle = 90
        offset = (im.size[0], 0)
    else:
        logger.error(f'Invalid text direction \'{text_direction}\'')
        raise KrakenInputException(f'Invalid text direction {text_direction}')

    logger.debug(f'Rotating input image by {angle} degrees')
    im = im.rotate(angle, expand=True)

    a = pil2array(im)
    binary = np.array(a > 0.5*(np.amin(a) + np.amax(a)), 'i')
    binary = 1 - binary

    _, ccs = morph.label(1 - binary)
    if ccs > np.dot(*im.size)/(30*30):
        logger.warning(f'Too many connected components for a page image: {ccs}')
        return {'text_direction': text_direction, 'boxes':  []}

    if not scale:
        scale = estimate_scale(binary)

    if no_hlines:
        binary = remove_hlines(binary, scale)
    # emptyish images will cause exceptions here.

    try:
        if mask:
            if mask.mode != '1' and not is_bitonal(mask):
                logger.error('Mask is not bitonal')

# Path: kraken/lib/morph.py
# def label(image: np.ndarray, **kw) -> np.ndarray:
# def find_objects(image: np.ndarray, **kw) -> np.ndarray:
# def r_dilation(image, size, origin=0):
# def r_erosion(image, size, origin=0):
# def rb_dilation(image, size, origin=0):
# def rb_erosion(image, size, origin=0):
# def rb_opening(image, size, origin=0):
# def spread_labels(labels, maxdist=9999999):
# def correspondences(labels1, labels2):
# def propagate_labels(image, labels, conflict=0):
# def select_regions(binary, f, min=0, nbest=100000):
# 
# Path: kraken/lib/sl.py
# def dim0(s):
# def dim1(s):
# def area(a):
# def width(s):
# def height(s):
# def aspect(a):
# def xcenter(s):
# def ycenter(s):
# def center(s):
# 
# Path: kraken/lib/util.py
# def pil2array(im: Image.Image, alpha: int = 0) -> np.ndarray:
#     if im.mode == '1':
#         return np.array(im.convert('L'))
#     return np.array(im)
# 
# def is_bitonal(im: Union[Image.Image, torch.Tensor]) -> bool:
#     """
#     Tests a PIL image or torch tensor for bitonality.
# 
#     Args:
#         im: Image to test
# 
#     Returns:
#         True if the image contains only two different color values. False
#         otherwise.
#     """
#     if isinstance(im, Image.Image):
#         return im.getcolors(2) is not None and len(im.getcolors(2)) == 2
#     elif isinstance(im, torch.Tensor):
#         return len(im.int().unique()) == 2
# 
# def get_im_str(im: Image.Image) -> str:
#     return im.filename if hasattr(im, 'filename') else str(im)
# 
# Path: kraken/lib/exceptions.py
# class KrakenInputException(Exception):
# 
#     def __init__(self, message=None):
#         Exception.__init__(self, message)
# 
# Path: kraken/lib/segmentation.py
# def reading_order(lines: Sequence[Tuple[slice, slice]], text_direction: str = 'lr') -> np.ndarray:
#     """Given the list of lines (a list of 2D slices), computes
#     the partial reading order.  The output is a binary 2D array
#     such that order[i,j] is true if line i comes before line j
#     in reading order."""
# 
#     logger.info('Compute reading order on {} lines in {} direction'.format(len(lines), text_direction))
# 
#     order = np.zeros((len(lines), len(lines)), 'B')
# 
#     def _x_overlaps(u, v):
#         return u[1].start < v[1].stop and u[1].stop > v[1].start
# 
#     def _above(u, v):
#         return u[0].start < v[0].start
# 
#     def _left_of(u, v):
#         return u[1].stop < v[1].start
# 
#     def _separates(w, u, v):
#         if w == u or w == v:
#             return 0
#         if w[0].stop < min(u[0].start, v[0].start):
#             return 0
#         if w[0].start > max(u[0].stop, v[0].stop):
#             return 0
#         if w[1].start < u[1].stop and w[1].stop > v[1].start:
#             return 1
#         return 0
# 
#     if text_direction == 'rl':
#         def horizontal_order(u, v):
#             return not _left_of(u, v)
#     else:
#         horizontal_order = _left_of
# 
#     for i, u in enumerate(lines):
#         for j, v in enumerate(lines):
#             if _x_overlaps(u, v):
#                 if _above(u, v):
#                     order[i, j] = 1
#             else:
#                 if [w for w in lines if _separates(w, u, v)] == []:
#                     if horizontal_order(u, v):
#                         order[i, j] = 1
#     return order
# 
# def topsort(order: np.ndarray) -> List[int]:
#     """Given a binary array defining a partial order (o[i,j]==True means i<j),
#     compute a topological sort.  This is a quick and dirty implementation
#     that works for up to a few thousand elements."""
#     logger.info('Perform topological sort on partially ordered lines')
#     n = len(order)
#     visited = np.zeros(n)
#     L = []
# 
#     def _visit(k):
#         if visited[k]:
#             return
#         visited[k] = 1
#         a, = np.nonzero(np.ravel(order[:, k]))
#         for line in a:
#             _visit(line)
#         L.append(k)
# 
#     for k in range(n):
#         _visit(k)
#     return L


# Path: kraken/pageseg.py
import logging
import numpy as np
from typing import Tuple, List, Callable, Optional, Dict, Any, Union
from scipy.ndimage.filters import (gaussian_filter, uniform_filter,
                                   maximum_filter)
from kraken.lib import morph, sl
from kraken.lib.util import pil2array, is_bitonal, get_im_str
from kraken.lib.exceptions import KrakenInputException
from kraken.lib.segmentation import reading_order, topsort

    elif text_direction == 'vertical-rl':
        angle = 90
        offset = (im.size[0], 0)
    else:
        logger.error(f'Invalid text direction \'{text_direction}\'')
        raise KrakenInputException(f'Invalid text direction {text_direction}')

    logger.debug(f'Rotating input image by {angle} degrees')
    im = im.rotate(angle, expand=True)

    a = pil2array(im)
    binary = np.array(a > 0.5*(np.amin(a) + np.amax(a)), 'i')
    binary = 1 - binary

    _, ccs = morph.label(1 - binary)
    if ccs > np.dot(*im.size)/(30*30):
        logger.warning(f'Too many connected components for a page image: {ccs}')
        return {'text_direction': text_direction, 'boxes':  []}

    if not scale:
        scale = estimate_scale(binary)

    if no_hlines:
        binary = remove_hlines(binary, scale)
    # emptyish images will cause exceptions here.

    try:
        if mask:
            if mask.mode != '1' and not is_bitonal(mask):
                logger.error('Mask is not bitonal')

                raise KrakenInputException('Mask is not bitonal')