• 大小: 14.41MB
    文件类型: .zip
    金币: 1
    下载: 0 次
    发布日期: 2023-06-16
  • 语言: Python
  • 标签: python  

资源简介

shape context 形状上下文 验证码识别 PYTHON代码 网上此资源较少 以测试可用 自己修改参考可以用在自己的项目上

资源截图

代码片段和文件信息

#!/usr/bin/env python
# -*- coding: iso-8859-1 -*-

# Documentation is intended to be processed by Epydoc.

“““
Introduction
============

The Munkres module provides an implementation of the Munkres algorithm
(also called the Hungarian algorithm or the Kuhn-Munkres algorithm)
useful for solving the Assignment Problem.

Assignment Problem
==================

Let *C* be an *n*\ x\ *n* matrix representing the costs of each of *n* workers
to perform any of *n* jobs. The assignment problem is to assign jobs to
workers in a way that minimizes the total cost. Since each worker can perform
only one job and each job can be assigned to only one worker the assignments
represent an independent set of the matrix *C*.

One way to generate the optimal set is to create all permutations of
the indexes necessary to traverse the matrix so that no row and column
are used more than once. For instance given this matrix (expressed in
Python)::

    matrix = [[5 9 1]
              [10 3 2]
              [8 7 4]]

You could use this code to generate the traversal indexes::

    def permute(a results):
        if len(a) == 1:
            results.insert(len(results) a)

        else:
            for i in xrange(0 len(a)):
                element = a[i]
                a_copy = [a[j] for j in xrange(0 len(a)) if j != i]
                subresults = []
                permute(a_copy subresults)
                for subresult in subresults:
                    result = [element] + subresult
                    results.insert(len(results) result)

    results = []
    permute(range(len(matrix)) results) # [0 1 2] for a 3x3 matrix

After the call to permute() the results matrix would look like this::

    [[0 1 2]
     [0 2 1]
     [1 0 2]
     [1 2 0]
     [2 0 1]
     [2 1 0]]

You could then use that index matrix to loop over the original cost matrix
and calculate the smallest cost of the combinations::

    n = len(matrix)
    minval = sys.maxint
    for row in xrange(n):
        cost = 0
        for col in xrange(n):
            cost += matrix[row][col]
        minval = min(cost minval)

    print minval

While this approach works fine for small matrices it does not scale. It
executes in O(*n*!) time: Calculating the permutations for an *n*\ x\ *n*
matrix requires *n*! operations. For a 12x12 matrix that‘s 479001600
traversals. Even if you could manage to perform each traversal in just one
millisecond it would still take more than 133 hours to perform the entire
traversal. A 20x20 matrix would take 2432902008176640000 operations. At
an optimistic millisecond per operation that‘s more than 77 million years.

The Munkres algorithm runs in O(*n*\ ^3) time rather than O(*n*!). This
package provides an implementation of that algorithm.

This version is based on
http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html.

This version was written for Python by Brian Clapper from the (Ada) algorithm
at the above web site. (The 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2011-05-28 08:27  Python-Shape-Context-master\
     文件       13295  2011-05-28 08:27  Python-Shape-Context-master\9.png
     文件        1433  2011-05-28 08:27  Python-Shape-Context-master\9M.png
     文件         564  2011-05-28 08:27  Python-Shape-Context-master\9M2.png
     文件        9437  2011-05-28 08:27  Python-Shape-Context-master\A.png
     文件       10433  2011-05-28 08:27  Python-Shape-Context-master\A2.png
     文件       14930  2011-05-28 08:27  Python-Shape-Context-master\AM.png
     文件        5634  2011-05-28 08:27  Python-Shape-Context-master\AM2.png
     文件       14996  2011-05-28 08:27  Python-Shape-Context-master\AM3.png
     文件       14784  2011-05-28 08:27  Python-Shape-Context-master\B.png
     文件       19847  2011-05-28 08:27  Python-Shape-Context-master\BM.png
     文件       19439  2011-05-28 08:27  Python-Shape-Context-master\BM2.png
     文件        9142  2011-05-28 08:27  Python-Shape-Context-master\D.png
     目录           0  2011-05-28 08:27  Python-Shape-Context-master\LAPJV\
     文件         515  2011-05-28 08:27  Python-Shape-Context-master\LAPJV\GNRL.H
     文件       10509  2011-05-28 08:27  Python-Shape-Context-master\LAPJV\LAP.CPP
     文件         746  2011-05-28 08:27  Python-Shape-Context-master\LAPJV\LAP.H
     文件        4236  2011-05-28 08:27  Python-Shape-Context-master\LAPJV\LAPJV.p
     文件        2023  2011-05-28 08:27  Python-Shape-Context-master\LAPJV\LAPMAIN.CPP
     文件         516  2011-05-28 08:27  Python-Shape-Context-master\LAPJV\SYSTEM.CPP
     文件         351  2011-05-28 08:27  Python-Shape-Context-master\LAPJV\SYSTEM.H
     文件          83  2011-05-28 08:27  Python-Shape-Context-master\README
     文件        6732  2011-05-28 08:27  Python-Shape-Context-master\SC.py
     文件        8067  2011-05-28 08:27  Python-Shape-Context-master\SC.pyc
     文件        7454  2011-05-28 08:27  Python-Shape-Context-master\SC2.py
     目录           0  2011-05-28 08:27  Python-Shape-Context-master\info\
     文件      890980  2011-05-28 08:27  Python-Shape-Context-master\info\10.1.1.112.2716.pdf
     文件      965316  2011-05-28 08:27  Python-Shape-Context-master\info\10.1.1.18.8852.pdf
     文件      606363  2011-05-28 08:27  Python-Shape-Context-master\info\13_diplaros.pdf
     文件     1956862  2011-05-28 08:27  Python-Shape-Context-master\info\2009_ijra_bk.pdf
     文件      991291  2011-05-28 08:27  Python-Shape-Context-master\info\54.pdf
............此处省略21个文件信息

评论

共有 条评论