估算打印处理所需的时间的图像处理装置及图像处理方法

摘要

本发明提供一种估算打印处理所需的时间的图像处理装置及图像处理方法。当估算打印处理所需的时间时，以这样的方式进行考虑到对象之间的交叠的估算，即，所述对象被视为具有预定的简单形状的对象。

说明书

技术领域

本发明涉及一种估算针对打印数据的打印处理所需的时间的技术。

背景技术

针对以页面描述语言(PDL)描述的打印数据的打印处理，包括由打印数据生成中间数据并基于中间数据生成位图图像。能够利用包括日本特开2011-31580号公报中讨论的已知技术，来估算打印处理所需的时间(被称为打印处理时间)。在日本特开2011-31580号公报中，基于打印数据中的对象(诸如图形、文字和图像)的类型和渲染(rendering)面积，来估算打印处理时间。

然而，对于打印处理时间的常规估算并未考虑对象是否实际上彼此交叠，这会在很大程度上影响打印处理时间。

发明内容

鉴于上述情况，本发明的目的在于一种考虑到对象是否彼此交叠来估算打印处理时间的方法。

根据本发明的一方面，一种图像处理装置，其用于获得要用于估算页的渲染时间的信息，所述图像处理装置包括存储程序的存储器，以及执行所述程序的一个或更多个处理器，所述一个或更多个处理器控制所述图像处理装置用作：生成单元，其被构造为针对所述页中的多个对象中的至少一个对象，基于关于所述页中的对象的形状的信息，生成通过简化所述对象的形状而获得的预定形状的对象，确定单元，其被构造为确定由所述生成单元生成的所述预定形状的至少两个对象之间的交叠，以及获得单元，其被构造为基于所确定的交叠，获得要用于估算所述渲染时间的信息。

通过以下参照附图对示例性实施例的描述，本发明的进一步特征将变得清楚。

附图说明

图1是例示根据第一示例性实施例的装置的硬件构造的示例的图。

图2是例示根据第一示例性实施例的装置的软件模块构造的示例的图。

图3是例示根据第一示例性实施例的对象的示例的图。

图4是例示根据第一示例性实施例的计算交叠参数的处理的示例的流程图。

图5是例示根据第一示例性实施例的群集(cluster)生成处理的流程图。

图6是例示包括对象的页的示例的图。

图7是例示群集列表的构造的示例的图。

图8是例示矩形分割(segment)的图。

图9是例示表示图6中所示的页的群集的图。

图10是例示根据第二示例性实施例的群集生成处理的流程图。

图11A至图11D是各自例示根据第二示例性实施例的群集合并的概念的图。

图12是例示根据第三示例性实施例的群集生成处理的流程图。

图13A至图13C是例示跨度(span)的图。

具体实施方式

将描述对象之间的交叠如何影响打印处理时间。

打印数据包括各种对象。打印处理时间可能依据对象是否彼此交叠而变化。打印处理方法的一个示例包括：当两个对象彼此交叠时，基于对象如何彼此交叠来确定用于交叠部分的最终渲染颜色，并且利用该渲染颜色渲染交叠部分。当采用这样的打印处理方法时，彼此不交叠的两个对象的打印处理时间与彼此交叠的两个相同对象的打印处理时间不同。

估算打印处理时间的可能的方法包括如下的方法，即，基于对象的形状确定对象是否彼此交叠，基于确定结果获得考虑到对象之间的交叠的估算参数，并且使用该估算参数来估算打印处理时间。

这个概念开创了基于各个对象的详细形状来精确地确定对象是否彼此交叠的一个示例性实施例。然而，确定对象是否彼此交叠的这种处理需要获得各个对象的详细形状的处理，因而需要花费时间。

鉴于上述情况，在本示例性实施例中，下面将描述用于确定对象是否彼此交叠而无需获得各个对象的详细形状的处理的快速且有效的方法。

下面参照附图描述根据本示例性实施例的图像处理装置。

图1是例示根据本示例性实施例的、用作图像处理装置的多功能外围设备(MFP)100的硬件构造的示例的框图。

MFP 100包括用作控制整个MFP 100的处理器的中央处理单元(CPU)101、随机存取存储器(RAM)102、只读存储器(ROM)103、网络接口(IF)104、光栅图像处理器(RIP)105、显示器IF 106、显示器107、打印机IF 108以及打印机109。ROM 103中存储由CPU 101利用RAM102执行的、图2中所示的软件200。因此，CPU 101用作执行根据本示例性实施例的对应的处理(例如，由打印数据生成中间数据的处理)的、图2中的各个模块(下面描述)。网络IF 104是通过网络与外部装置(例如，个人计算机(PC)和其他MFP)进行通信的接口，并且主要负责接收打印数据。RIP 105是由如下所述的中间数据生成输出到打印机引擎的位图图像数据的专用集成电路(ASIC)。

显示器IF 106是将表示信息的图像数据发送到诸如液晶显示器(LCD)等的显示器107使得信息被显示的显示控制单元。例如，该信息包括根据本示例性实施例的、表示估算的打印处理所需的时间的估算值。显示器107基于由此接收到的图像数据，在屏幕上显示该信息。

打印机IF 108将由RIP 105生成的位图图像数据转换成以打印机109可接收的格式的数据，并将所得的数据发送到打印机109。打印机109基于由此接收到的数据，在片材上打印图像。

在下文中，打印数据被描述为页面描述语言(PDL)数据。在MFP 100外部的主机PC(未示出)中生成PDL数据。主机PC经由局域网(LAN)将PDL数据发送到MFP 100。根据本示例性实施例，MFP 100执行对打印从主机PC接收到的PDL数据所需的时间进行估算的处理。作为估算的主体的PDL数据不必一定从外部设备接收，并且可以被存储在MFP100的RAM 102中。

图2是例示软件200的构造的示例的图。软件200包括各自在CPU101上进行操作的4个软件模块。

PDL解释器单元201将通过网络IF 104接收到的PDL数据存储在RAM 102中。然后，PDL解释器单元201读出并解释RAM 102中存储的PDL数据中的对象的渲染命令。基于渲染命令确定作为渲染目标的对象的形状和渲染位置(在下文中，被简称为位置)。因此，生成表示对象的形状和位置的中间数据。对象的中间数据包括三种类型的数据，这些数据是表示对象的轮廓的多个矢量数据(边缘)、基于Z顺序(Z-order)确定的对象的层级(level)、以及表示对象的颜色的填充。例如，由PDL解释器单元201针对图13A中所示的对象(是具有顶点A、B和C的三角形)而生成的中间数据，表示从顶点A经由顶点B延伸至顶点C的代表左侧轮廓的矢量(边缘131)以及从顶点C延伸至顶点A的代表右侧轮廓的矢量(边缘132)。RIP 105根据由此生成的中间数据，以如下方式生成位图图像数据。

RIP 105识别用于生成图像数据的扫描线。根据本示例性实施例的RIP 105中预先存储用于生成表示单个页的位图图像数据的帧缓冲器。RIP 105将具有所确定的渲染颜色的像素写入到帧缓冲器，从而生成单个页的位图图像数据。在图13B所示的示例中，对扫描线上的三角形对象进行渲染。RIP 105确定扫描线上的、由三角形对象的中间数据所表示的边缘131和边缘132所定义的跨度。在图13B所示的示例中，三角形对象是与针对该跨度的渲染相关的唯一对象。因此，跨度的渲染颜色被确定为是三角形对象的颜色。因此，具有由此确定的渲染颜色的像素被写入到帧缓冲器中的与跨度相对应的位置中。

在图13C中所示的示例中，三角形对象和矩形对象在扫描线上，并且彼此交叠。在此，RIP 105通过以下处理来渲染扫描线上的对象。更具体地，RIP 105确定扫描线上的三个跨度。由三角形对象的边缘131和矩形对象的边缘133来定义扫描线上的第一跨度(跨度1)。由矩形对象的边缘133和矩形对象的边缘134来定义扫描线上的第二跨度(跨度2)。由矩形对象的边缘134和三角形对象的边缘132来定义扫描线上的第三跨度(跨度3)。如上所述，在图13C所示的示例中，两个对象彼此交叠，并且根据对象的轮廓来确定多个跨度。由于确定跨度的上述处理需要考虑对象之间的形状和交叠，所以需要大量的计算处理。

如同在图13B的情况下，仅单个对象对跨度1和跨度3中的各个做出贡献，RIP 105将跨度1和跨度3中的各个的渲染颜色确定为是做出贡献的对象的颜色。同时，RIP 105基于两个对象中的各个的层级(通过Z顺序确定的对象的交叠方式)，确定两个对象彼此交叠的跨度2的渲染颜色。例如，当交叠在三角形对象上的矩形对象为半透明时，RIP 105通过参照两个对象(或它们的颜色信息)，确定跨度2的渲染颜色。然后，RIP105识别矩形对象和三角形对象的交叠方式(哪一个在另一个上面)。RIP105将作为矩形对象的颜色与三角形对象的颜色之间的组合的颜色，确定为是跨度2的渲染颜色。当交叠在三角形对象上的矩形对象为不透明时，RIP 105以相同的方式，将位于更高层级的矩形对象的颜色确定为是跨度2的渲染颜色。RIP 105将具有由此最终确定的渲染颜色的像素写入到帧缓冲器中的与跨度相对应的位置。

如上所述，由RIP 105根据由PDL解释器单元201生成的中间数据，来生成图像数据的处理(渲染处理)。

由于用于确定渲染处理中的各个跨度的渲染颜色的上述处理需要考虑对象之间的交叠，因而需要大量的计算。更具体地，针对单个跨度的渲染颜色的确定需要以下类型的时间。需要第一类型的时间，用于识别在跨度的渲染中涉及的一个或更多个对象(或它的颜色信息)(被称为跨度处理时间)。需要第二类型的时间，用于对由此基于其Z顺序而识别的一个或多个对象进行排序(sort)(被称为层级排序时间)。根据本示例性实施例，基于跨度处理时间和层级排序时间来估算打印处理时间。

进一步描述了图2中所示的软件200的模块。

群集管理单元202使用由PDL解释器单元201生成的对象的中间数据，来生成作为对象的轮廓的简化版本的、预定形状的对象。更具体地，群集管理单元202基于对象的位置和形状，将对象的中间数据转换成具有预定形状的另一对象的数据。例如，对于如上所述的三角形对象，群集管理单元202将包含三角形的各个顶点的坐标的边界矩形，设置为作为三角形形状的简化版本的预定形状。因此，群集管理单元202生成预定形状的对象。预定形状的对象(在下文中，被称为群集)包括参照图3描述的三种类型的信息，作为关于对象的信息。

图3例示了具有不同形状的5个对象的中间数据。对象301是具有水平的上底和下底的正方形对象。对象302是正圆形对象。对象303是具有水平的底的等边三角形对象。对象304是各顶点位于正方形形状的右上顶点、左边的中点以及底的中点的等腰三角形对象。对象305是如同配设有凹部的正方形形状的矩形U形对象，该凹部从将正方形形状的上底三等分的两点凹陷至正方形的边长的一半。由边缘来表示对象的轮廓。

5个对象在图3中的两个扫描线a和b上各自具有以下数量的跨度。在图3中，虚线箭头表示扫描线a和b，粗实线表示跨度。对象301、302、303和304中的各个在扫描线a上具有单个跨度并且在扫描线b上具有单个跨度。对象305在扫描线a上具有两个跨度并且在扫描线b上具有单个跨度。因此，对象的跨度的数量在各形状之间不同。

群集具有以下三种类型的信息。下面描述如何使用各种类型的信息。1.边界框

第一类型的信息是关于包含对象的轮廓的矩形(边界框)的信息。根据本示例性实施例，边界框的左上点和右下点的坐标位置被用作表示群集的位置和范围的信息。基于原始对象的位置(渲染位置)和形状(渲染范围)来确定坐标位置。由于以下原因(1)至(3)而使用矩形。对于原因(1)，矩形是能够由左上点和右下点来表示的简单的形状，因而对于确定对象是否交叠而言，是与获得对象的详细形状相比能够快得多地获得的对象形状。对于原因(2)，与识别对象的详细形状之间的交叠区域相比，能够快得多地识别具有简单的矩形形状的对象之间的交叠区域。例如，如下确定矩形1和矩形2是否彼此交叠。更具体地，获得矩形2的各个顶点的坐标，并且确定矩形1的区域是否包括矩形2的顶点中的任一个。当该区域包括至少一个顶点时，矩形1和矩形2被确定为彼此交叠。对于原因(3)，能够利用矩形形状容易地进行对后述的群集进行分割的操作。例如，当两个矩形如图8中所示彼此交叠时，能够基于分割前的两个矩形中的各个的左上点和右下点的坐标，容易地获得表示5个矩形分割中的各个的左上点和右下点的坐标，而不是获得分割前的两个矩形的轮廓。

包含对象的轮廓的矩形是预定形状的示例。预定形状不限于矩形，并且可以是能够用来容易地获得用于后述的打印处理时间的估算参数的任何形状。

2.每像素浓度

第二类型的信息是表示目标边界框中的对象的数量的信息(在下文中被称为每像素浓度)。每像素浓度是表示对象的边界框中的每像素的对象的平均数量的信息(指标)。基于对象的形状来确定每像素浓度，并且利用下面的公式来计算每像素浓度，

每像素浓度＝(对象的面积)/(边界框的面积)。

由于由虚线表示的边界框中的矩形对象具有与边界框相同的面积，所以图3中所示的示例中的对象301的群集的每像素浓度为“1”。对象302的每像素浓度为“0.785”＝正圆形的面积/边界框的面积。对象303、304、305分别具有以上述的方式计算出的“0.5”、“0.475”和“0.833”的每像素浓度。

3.跨度的平均数量

第三信息是跨度的平均数量(在下文中被称为每线跨度(SPL))。SPL是表示对象的边界框中的单个扫描线中的对象的跨度的平均数量的信息(指标)。基于对象的形状来确定SPL，并且通过下面的公式来计算SPL，SPL＝(对象的轮廓的y位移的绝对值的总和)/2/(边界框的高度)。

利用图3中的对象301、304和305作为示例来描述对象的轮廓的y位移。能够由作为表示对象的轮廓的矢量数据的、对象的中间数据中的多个边缘中的各个，获得对象的轮廓在y方向(图中的竖直方向)上的位移。例如，对于对象301，各个边缘(边缘1和边缘2)在y方向上的位移的绝对值等于边界框的高度。对象的轮廓的y位移的绝对值的总和是边缘在y方向上的位移的绝对值的总和。因此，SPL被计算为1.0，同时对象的轮廓的y位移的绝对值的总和是边界框的高度的两倍大。类似地，对象304的边缘(边缘1和边缘2)中的各个在y方向上的位移的绝对值与边界框的高度相同。因此，针对对象304计算出的SPL为1.0。对象301和对象304在形状上彼此不同，但是具有相同的SPL。因此，在对象301和对象304的边界框之间，各个扫描线中的跨度的数量(单个跨度)是相同的。

对于对象305，以不同的方式计算SPL。对象305的中间数据包括4个边缘。边缘1和边缘2中的各个在y方向上的位移的绝对值与边界框的高度相同。另一方面，边缘3和边缘4中的各个在y方向上的位移的绝对值是边界框的高度的一半。因此，对于对象305，SPL被计算为1.5。因此，具有矩形U形形状的对象305的边界框中的每扫描线的跨度的平均数量为1.5。

当边界框的高度被定义为1时，群集管理单元202计算1.0作为对象301的SPL，同时轮廓的y位移的绝对值的总和为2。类似地，群集管理单元202分别计算1.0、1.0和1.0作为对象302至对象304的SPL。

群集管理单元202能够执行如下所述的、用于减少群集的数量的合并群集的处理。

矩形生成单元203确定由群集管理单元202生成的群集之间的交叠，并且基于确定的结果对群集进行划分(分割)以生成分割的群集(矩形分割)。根据本示例性实施例，边界框(矩形)表示群集的形状，使得与通过由边缘计算各个对象的轮廓来确定对象之间的交叠的情况相比，能够快得多地确定群集之间的交叠。此外，能够快速地进行用于获得矩形分割的划分。

矩形生成单元203以下述的方式，针对通过划分而获得的矩形分割中的各个，再次计算每像素浓度和SPL。

估算单元204通过获得估算打印处理时间所需的多种类型的估算参数，并且通过将各个估算参数乘以预先针对相应的估算参数确定的系数，来估算打印处理时间。打印处理时间由下面的公式(1)来估算，

其中，M表示要获取的估算参数的总数，i表示估算参数的类型，p(i)表示与指标i相对应的估算参数，x(i)表示与指标i相对应的系数，并且C表示常数。基于RIP 105和打印机109的性能来确定系数x(i)和常数C。表示由此估算的打印处理时间的信息(估算值)被显示在显示器107上。

由估算单元204获得的估算参数包括表示例如如下获得的边缘的数量的估算参数。估算单元204对由PDL解释器单元201生成的中间数据的单个页进行解释，并且从0起对边缘的数量进行计数。在图3中所示的示例中，边缘的数量针对对象301和304中的各个被计数至2，并且针对对象305被计数至4。由于在打印处理中用于生成(形成)跨度的处理所需的时间随着单个页中的边缘的总数(计数结果)增加，所以边缘的数量可以是估算参数。

估算参数还包括与对象之间的交叠相关的参数(交叠参数)。估算单元204基于与由矩形生成单元203生成的矩形分割相关的各个信息(边界框、每像素浓度和SPL)，来估算跨度的实际数量和交叠对象的数量。然后，估算单元204以下述的方式，基于由此估算的跨度的数量和交叠对象的数量，来计算交叠参数。

<交叠参数的计算>

接下来，将参照图4中的流程图描述计算交叠参数的方法。图4是例示由软件200执行的处理的示例的流程图。通过CPU 101执行在ROM103中存储的程序来实现下述的流程图中的处理。为了描述起见，该流程图对应于针对单个页的处理，并且当PDL数据被网络IF104接收并存储在RAM 102中时开始。

在步骤S401中，PDL解释器单元201开始包括步骤S402至步骤S404中的处理的循环处理，反复进行，直到读取在RAM 102中存储的PDL数据中的单个页的所有渲染命令为止。

在步骤S402中，PDL解释器单元201读出并解释在存储的PDL数据中的单个对象的渲染命令，以生成对象的中间数据。

在步骤S403中，PDL解释器单元201由在步骤S402中生成的中间数据获取对象信息。对象信息是指定到对象的信息，并且包括对对象进行定义的边缘的位置/类型、组合运算符(α混合和渲染输出管线(Rendering Output Pipeline，ROP))等。

在步骤S404中，群集管理单元202基于在步骤S403中获取的对象信息生成群集。

参照图5中的流程图来详细描述步骤S404中的群集生成处理。

在步骤S501中，群集管理单元202生成包括上述的三种类型的信息的群集。

参照图6中所示的示例描述由此生成的群集。图6中的页600包括各自具有正圆形形状而彼此不交叠的多个对象601。页620包括与对象601相同并且彼此交叠的对象621。对象621的数量与页600中的对象601的数量相同。用于页620的打印处理涉及跨度处理和层级排序，因此，比用于页600的处理需要更长的时间。本示例性实施例采用下述的群集和矩形分割的概念，以获得估算参数，利用该估算参数，能够考虑到对象是否彼此交叠而精确地估算打印处理时间。

群集管理单元202由关于单个对象601的中间数据，生成包括以下信息的群集，

·边界框＝{(300,400),(800,900)}，

·每像素浓度＝(250×250×π)/(500×500)＝0.785，以及

·SPL＝(500+500)/2/(500)＝1.0。

在作为边界框＝{(300,400),(800,900)}的矩形中，关于对象601的信息被转换成在所生成的群集中、表示各个像素中的对象的平均数量为0.785并且表示各个扫描线上的跨度的平均数量为1.0的信息。当单个群集对应于单个对象时，依据具有复杂形状的对象之间的交叠，生成群集以将关于具有复杂形状的对象的信息转换成具有等量信息的简单的预定形状的对象。

在步骤S502中，群集管理单元202将在步骤S501中生成的对应于单个对象的群集添加到群集列表。群集列表被存储在RAM 102中，并且被以图7中所示的非分支列表结构来管理。因此，新添加的群集连接到列表的端部的群集。因此，当针对页600生成群集时，所生成的群集列表具有彼此连接的12个群集。

通过上述的从步骤S401至步骤S404的处理，页中的所有对象被转换成群集，并且被以群集列表的形式来管理。

进一步描述图4中的流程图。

下面描述在步骤S405至步骤S407中执行的处理。基于各个群集的边界框信息，确定在步骤S404中生成的群集(具有预定形状的对象)之间的交叠，并且生成考虑到群集之间的交叠的多个矩形分割。针对各个矩形分割计算用于获得考虑到对象之间的交叠的交叠参数的信息，并且根据由此计算出的信息，来计算交叠参数。

在步骤S405中，矩形生成单元203基于群集的边界框信息，确定群集列表中的各个群集是否与另一群集交叠。不与任何其他群集交叠的群集的边界框被直接用作矩形分割。另一方面，与另一群集交叠的群集的边界框基于交叠的群集的边界框信息，被划分成多个矩形分割。如同在群集的情况下，由此获得的矩形分割中的各个具有表示自身位置的边界框信息。

利用群集列表仅包括群集801和群集802的图8作为示例描述该处理。关于图8中所示的群集801的信息包括边界框＝{(0,0),(5,5)}，每像素浓度＝1.0，以及SPL＝1.0。关于群集802的信息包括边界框＝{(2,2),(8,8)}，每像素浓度＝0.5，以及SPL＝1.0。矩形分割组810表示将群集801和群集802的边界框划分成多个矩形分割(矩形分割1至矩形分割5)的结果。

矩形生成单元203参照群集列表中的群集801和群集802的边界框信息，来确定边界框是否彼此交叠。在该示例中，矩形生成单元203确定群集801和群集802的边界框彼此交叠。与通过由原始对象的边缘获得对象的轮廓来进行交叠确定相比，通过参照边界框信息(即，左上点和右下点)来进行的该交叠确定能够被更快地进行。接下来，矩形生成单元203识别矩形分割作为交叠部分，在图8中所示的示例中是矩形分割3。矩形分割3具有边界框信息＝{(2,2),(5,5)}。矩形生成单元203将非交叠部分划分成多个矩形分割，从而在图8中的示例中获得矩形分割1、2、4和5。矩形分割1具有边界框信息＝{(0,0),(5,2)}，矩形分割2具有边界框信息＝{(0,2),(2,5)}，矩形分割4具有边界框信息＝{(5,2),(8,5)}，并且矩形分割5具有边界框信息＝{(2,5),(8,8)}。

这种划分边界框的方式仅仅是示例，并且可以以任何其他方式来划分群集的边界框，只要能够以与根据中间数据生成群集的方式相同的方式来获得预定形状的对象即可。

在步骤S406中，矩形生成单元203基于检测到的交叠(交叠部分的位置和范围)，针对通过划分而获得的多个矩形分割中的各个，计算每像素浓度和SPL。针对与用于获得群集的每像素浓度和SPL的计算的对象相同的对象，来进行该计算。更具体地，进行计算以在矩形分割中粗略地识别对象如何交叠。矩形分割的每像素浓度表示矩形分割中的各个像素中的对象的平均数量。矩形分割的SPL表示矩形分割中的各个扫描线上的跨度的平均数量。

因此，获得矩形分割的每像素浓度，作为包括矩形分割的群集的每像素浓度的总和。矩形分割的SPL被确定为是各自通过将各个群集的SPL、乘以矩形分割的边界框的宽度(矩形分割宽度)与群集的边界框的宽度(群集宽度)的比而获得的值的总和。

在存在没有被划分的群集的情况下，可以无改变地使用每像素浓度和SPL。

在图8中所示的示例中，矩形分割1具有

·每像素浓度＝(群集801的每像素浓度)＝1.0，并且

·SPL＝(群集801的SPL)×{(矩形分割1的宽度)/(群集801的宽度)}＝1.0×{5/5}＝1.0。

因此，矩形分割1可以被视为如下的部分，在该部分中，每像素的对象的数量为1，并且各个扫描线上的跨度的数量为1.0。

矩形分割2具有

·每像素浓度＝(群集801的每像素浓度)＝1.0，并且

·SPL＝(群集801的SPL)×{(矩形分割2的宽度)/(群集801的宽度)}＝1.0×{2/5}＝0.2。因此，矩形分割2可以被视为如下的部分，在该部分中，每像素的对象的数量为1，并且各个扫描线上的跨度的数量为0.2。

矩形分割3具有

·每像素浓度＝(群集801的每像素浓度)+(群集802的每像素浓度)＝1.0+0.5＝1.5，并且

·SPL＝(群集801的SPL)×{(矩形分割3的宽度)/(群集801的宽度)}+(群集802的SPL)×{(矩形分割3的宽度)/(群集802的宽度)}＝1.0×{3/5}+1.0×{3/6}＝1.1。因此，矩形分割3可以被视为如下的部分，在该部分中，每像素的对象的数量为1.5，并且各个扫描线上的跨度的数量为1.1。

以与用于矩形分割1和矩形分割2中的对应一者的方式相同的方式，获得矩形分割4和矩形分割5中的各个的每像素浓度和SPL。

在步骤S406中，如同在上面参照图8描述的示例中，矩形生成单元203获得各个矩形分割的每像素浓度和SPL。

图9例示了表示对页600和页620执行步骤S405和步骤S406中的处理的结果的页900和页920。页900和页920中的各个矩形表示单个矩形分割。为了描述起见，矩形各自以其中的用于识别各个矩形分割的数字来表示。更具体地，由页600生成12个矩形分割，由页620生成25个矩形分割。针对这些矩形分割中的各个获得每像素浓度和SPL。

接下来，在步骤S407中，估算单元204基于在步骤S405中生成的矩形分割中的各个的边界框信息、每像素浓度以及SPL，来计算交叠参数。该交叠参数用作在用于估算上述的打印处理时间的公式中的估算参数中的一者。

估算单元204获得将SPL乘以对应矩形分割的高度的结果，作为矩形分割中的跨度的数量的估算值。每像素浓度能够被视为每像素的交叠的对象的数量。因此，每像素浓度乘以估算的跨度的数量的结果，用作识别对矩形分割的区域中的各个跨度做出贡献的一个或更多个对象(或它们的颜色信息)所需的时间的总和的指标。针对所有矩形分割的跨度处理时间的指标由下面的公式来计算，

其中，N表示矩形分割的总数，每像素浓度(i)表示第i个矩形分割的每像素浓度，并且跨度(i)表示第i个矩形分割中的跨度的数量。

基于一个或更多个对象的Z顺序，来对为单个跨度做出贡献的一个或更多个对象(或它们的颜色信息)进行排序，以确定针对跨度的渲染颜色。排序(层级排序)所需的时间大致与交叠的对象的数量的平方成比例。估算单元204进行针对所有矩形分割的层级排序所需的时间的指标由下面的公式来计算。

利用该公式，例如，如下面的表1中所示，针对图9中所示的页900，获得跨度处理时间指标＝4716，层级排序时间指标＝3696。如下面的表2中所示，针对页920，获得跨度处理时间指标＝12325，层级排序时间指标＝30745。数值越大表示处理时间越长。因此，根据本示例性实施例，能够获得考虑到各个跨度上的对象之间的交叠的精确估算参数，用于估算图6中的页600和页620的打印处理时间。

表1

在上述的估算公式中使用在步骤S407中由此计算出的交叠参数(跨度处理时间指标和层级排序时间指标)，使得能够估算考虑到对象之间的交叠的打印处理时间。对于图6和图9中所示的示例，在估算公式中使用估算参数，从而能够利用根据交叠的方式而在具有相同数量的相同形状的对象的页之间改变的指标，来估算接近实际打印时间的精确打印时间。

表2

在第一示例性实施例中，针对各个对象生成一个群集，并且在群集列表中进行管理。在第二示例性实施例中，当在步骤S404中生成对象的群集时，从已经生成并且在群集列表中管理的群集中选择与所生成的群集高度相关的群集，并且将该群集与所生成的群集合并。因此，限制了在群集列表中管理的群集的数量，从而能够节省用于存储群集列表的RAM102的存储器资源，并且能够限制在步骤S405中生成矩形分割所需的时间。

根据本示例性实施例的硬件构造和软件构造与图1和图2中所示的第一示例性实施例中的相同，因此将不进行描述。

本示例性实施例的特征在于图4中所示的流程图中的步骤S404中的处理。更具体地，根据本示例性实施例，执行图10中所示的流程图中的处理，代替第一示例性实施例中的步骤S404中的处理(图5)。除步骤S404中的处理以外的处理与第一示例性实施例中的相同，因此将不进行描述。

描述图10中的流程图。

在步骤S501中，群集管理单元202以与第一示例性实施例中的方式相同的方式，生成对象的群集。

接下来，在步骤S1001中，群集管理单元202确定已在群集列表中管理的群集中的任何一个是否与所生成的群集的信息高度相关。当群集管理单元202确定群集列表包括与所生成的群集高度相关的群集时(在步骤S1001中为是)，则处理前进到步骤S1002。当群集管理单元202确定群集列表不包括与所生成的群集高度相关的群集时(在步骤S1001中为否)，则处理进入与第一示例性实施例中相同的步骤S502。

基于当群集被合并时群集的信息的精确性将会劣化多少(劣化等级)，来确定群集之间的相关性。实现低于阈值的劣化等级的群集被确定为是高度相关的群集。群集管理单元202在确定作为以下两种情况之一的群集之间的关系之后，计算劣化等级。

在第一种情况下，所生成的群集的边界框未被包括在群集列表中的群集中。在这种情况下，在群集被合并之前和之后的每像素浓度的改变量可以被用作劣化等级。群集管理单元202在改变量等于阈值或更大时不进行合并，而在改变量小于阈值时进行合并。合并后的每像素浓度由下面的公式来计算，

其中，N表示要合并的群集的数量(在该示例中为2)，i表示作为合并目标的各个群集的指标，每像素浓度(i)表示群集(i)的每像素浓度，并且面积比(i)表示群集(i)的边界框的面积、与完全包括作为合并目标的两个群集的边界框的边界矩形(通过合并而获得的群集)的面积的比。

在第二种情况下，所生成的群集的边界框被包括在群集列表中的群集中。在这种情况下，关于所生成的群集的边界框的面积，在合并之前和之后的面积比的改变量可以被用作劣化等级。群集管理单元202在面积比等于阈值或更大时不进行合并，而在面积比不大于阈值时进行合并。

参照图11描述确定相关性是否为高的方法的具体示例。

在图11A中，群集1101具有边界框＝{(0,0),(100,100)}并且每像素浓度＝1.0，群集1102具有边界框＝{(105,100),(205,100)}并且每像素浓度＝1.0。因此，群集1101和群集1102彼此分开5个像素的距离。在该示例中，每像素浓度的改变量的阈值为0.1。

当两个群集1101和群集1102被合并时，所得的群集1103是包括两个群集1101和群集1102的大群集。关于大群集1103的信息包括边界框＝{(0,0),(205,100)}并且每像素浓度＝1.0×(100/205)+1.0×10000/20500＝0.98。作为合并的结果的每像素浓度的改变量是来自群集1101和群集1102的改变量的总和。更具体地，改变量为(1.0-0.98)+(1.0-0.98)＝0.04。因此，作为合并的结果的每像素浓度的改变量(劣化等级)小于阈值。因此，两个群集1101和群集1102被确定为是彼此高度相关，因而在步骤S1002中被合并。

在图11B中，群集1111具有边界框＝{(0,0),(100,100)}并且每像素浓度＝1.0，群集1112具有边界框＝{(100,100),(200,200)}并且每像素浓度＝1.0。当两个群集1111和群集1112被合并时，所得的群集1113具有0.5的每像素浓度和1.0的每像素浓度的改变量。因此，作为群集1111和群集1112合并的结果的每像素浓度的改变量(劣化等级)大于阈值，因而群集1111和群集1112被确定为彼此不是高度相关。

当如图11C中所示，所生成的群集的边界框被包括在另一群集的边界框中时，基于群集之间的面积比来确定相关性是否为高。例如，面积比的阈值被设置为150％。当群集1121的面积为3600像素，并且群集1122的面积为2500像素时，面积比为3600/2500＝1.4，即，140％。因此，群集1121和群集1122之间的面积比(劣化等级)小于阈值150％，并且结果，群集1121和群集1122被确定为是彼此高度相关。换言之，作为合并群集1121和群集1122的结果的信息的劣化是小的。

如图11D中所示，当群集1131的面积为3600像素，并且群集1132的面积为400像素时，群集1131和群集1132之间的面积比为3600/400＝9.0，即，900％。因此，群集1131和群集1132之间的面积比大于阈值，并且结果，群集1131和群集1132被确定为彼此不是高度相关。换言之，作为合并群集1131和群集1132的结果的信息的劣化是大的。

在步骤S1002中，群集管理单元202执行将在步骤S501中生成的群集与群集列表中的群集中的最相关的群集进行合并的处理。如下获得合并后的边界框、每像素浓度和SPL，

·边界框＝{(合并后的群集的最小边界框x,y),(合并后的群集的最大边界框x,y)}

·每像素浓度＝上述的(作为合并的结果的每像素浓度)，以及

·SPL＝{合并后的群集的(SPL×边界框的高度)值的总和)}/合并后的边界框的高度。

因此，群集管理单元202具有在步骤S1002中作为合并PDL数据中的多个对象的结果来生成单个群集的功能。

如上所述，当生成群集时，将群集与同所生成的群集高度相关的群集合并，从而以关于群集的信息的最小可能劣化的方式，来限制在群集列表的最终版本中管理的群集的数量。

在第二示例性实施例中，通过合并彼此高度相关的群集，来限制在群集列表中管理的群集的数量。根据第三示例性实施例，为在群集列表中管理的群集的数量设置阈值。这是因为，对于包括从中生成彼此不是高度相关的群集的许多对象的PDL数据而言，无法有效减少在群集列表中管理的群集的数量。因此，在本示例性实施例中，当所生成的群集被添加到群集列表时，群集管理单元202确定在群集列表中管理的群集的总数是否超过阈值。当群集的总数超过阈值时，从群集列表中选择能够与所生成的群集以最小劣化等级合并的群集。因此，将所选择的群集和所生成的群集合并。

根据本示例性实施例的硬件构造和软件构造与图1和图2中所示的第一示例性实施例中的硬件构造和软件构造相同，因此将不进行描述。

在本示例性实施例中，群集管理单元202在图4中所示的流程图中的步骤S404中，执行在图12中所示的流程图中的处理。除步骤S404中的处理以外的处理与第一示例性实施例中的相同，因此将不进行描述。

图12中的步骤S501、S502、S1001和S1002与第二示例性实施例中的相同，因此将不进行描述。在下面的描述中，群集列表中的各个群集包括关于已被合并在群集中的对象(群集)的数量的信息(在下文中，被称为群集中的对象的数量)，以及边界框、每像素浓度和SPL。通过进一步参照该信息，来确定群集列表中的各个群集的合并是否导致大的信息劣化。

在步骤S1201中，对于群集列表中的各个群集，群集管理单元202对群集中的对象的数量进行更新。例如，图11A中所示的群集1101和群集1102分别用作所生成的群集和群集列表中的群集，并且群集1102中的对象的数量为1。当在步骤S1002中合并群集1101和群集1102时，利用关于通过合并而获得的群集1103的信息，对群集列表中的群集1102进行更新。因此，群集1103中的对象的数量为2。

在步骤S1202中，作为在步骤S502中添加所生成的群集的结果，群集管理单元202确定群集列表中的群集的总数是否已超过阈值。当总数超过阈值时(在步骤S1202中为是)，则处理前进到步骤S1203。另一方面，当总数不超过阈值时(在步骤S1202中为否)，终止本示例性实施例中的群集生成处理。

在步骤S1203中，群集管理单元202对从群集列表中的所有群集中选择的、能够以最低信息劣化等级合并的两个群集执行合并处理，使得群集列表中的群集的数量被限制。基于针对群集列表中的两个群集之间的各个组合而计算出的信息劣化等级，来选择两个群集。由三种类型的信息获得劣化等级，该信息包括每像素浓度的改变量(与第二示例性实施例中的相同，因此将不进行描述)，以及边界框之间的面积比和如下获得的对象的数量比，

·边界框之间的面积比＝两个群集的边界框面积的最大值/两个群集的边界框面积的最小值，并且

·对象的数量比＝两个群集中的对象的数量的最大值/两个群集中的对象的数量的最小值。

通过参照各个劣化等级，在下列条件下选择要合并的两个群集，

(1)选择实现最小面积比的两个群集组(一对群集)，

(2)当存在多个实现最小面积比的两个群集组(多对群集)时，从多对群集中选择实现最小的对象的数量比的两个群集组，

(3)当存在实现相同的面积比和相同的对象的数量比的多对群集时，选择实现最小的每像素浓度的改变量的一对群集，并且

(4)当存在实现相同的面积比、相同的对象的数量比和相同的每像素浓度的改变量的多对群集时，从这些多对群集中选择任何一对。

使用这些条件用于选择一对群集的原因如下。

一般地，作为合并群集的结果，关系“边界框面积的改变>群集中的对象的数量的改变>群集的每像素浓度的改变”适用于对原始群集的信息的精度的劣化等级的顺序。

如上所述，当群集列表中的群集的数量超过阈值时，合并群集列表中的群集，使得群集的数量减少。

表示PDL数据中的各个对象的群集的预定形状，不限于如上述的示例性实施例中的矩形，并且可以是根据对象的形状的任何其他的简单的形状。例如，对于圆形对象可以采用八角形群集。

表示对象的矩形群集的数量不限于如上述的示例性实施例中的一个，并且依据对象的形状可以多于一个。这意味着，当由单个对象生成群集时可以生成多个矩形分割。例如，对于十字形对象，可以生成作为与在左和在右的两个水平条以及在中央的一个竖直条相对应的矩形分割的群集。由此，甚至能够获得更精确的估算参数。

作为表示对象的单个群集的形状的矩形，不限于包含该对象的边界矩形，并且可以是具有接近对象形状的形状的任何其他矩形。更具体地，当对象具有凸透镜形状时，可以采用与对象的凸面具有交点的矩形。

上述示例性实施例中的重要特征是，当获得考虑到对象之间的交叠的估算参数时，使用有效限制计算量并且同时在很大程度上不使关于对象的信息劣化的预定形状的群集。

其他实施例

还可以通过读出并执行记录在存储介质(也可更完整地称为“非暂时性计算机可读存储介质”)上的计算机可执行指令(例如，一个或更多个程序)以执行上述实施例中的一个或更多个的功能、并且/或者包括用于执行上述实施例中的一个或更多个的功能的一个或更多个电路(例如，专用集成电路(ASIC))的系统或装置的计算机，来实现本发明的实施例，并且，可以利用通过由系统或装置的计算机例如读出并执行来自存储介质的计算机可执行指令以执行上述实施例中的一个或更多个的功能、并且/或者控制一个或更多个电路以执行上述实施例中的一个或更多个的功能的方法，来实现本发明的实施例。计算机可以包括一个或更多个处理器(例如，中央处理单元(CPU)，微处理单元(MPU))，并且可以包括分开的计算机或分开的处理器的网络，以读出并执行计算机可执行指令。计算机可执行指令可以例如从网络或存储介质被提供给计算机。存储介质可以包括例如硬盘、随机存取存储器(RAM)、只读存储器(ROM)、分布式计算系统的存储器、光盘(诸如压缩光盘(CD)、数字通用光盘(DVD)或蓝光光盘(BD)^TM)、闪存装置以及存储卡等中的一者或更多。

本发明的实施例还可以通过如下的方法来实现，即，通过网络或者各种存储介质将执行上述实施例的功能的软件(程序)提供给系统或装置，该系统或装置的计算机或是中央处理单元(CPU)、微处理单元(MPU)读出并执行程序的方法。

虽然参照示例性实施例对本发明进行了描述，但是应当理解，本发明不限于所公开的示例性实施例。应当对所附权利要求的范围给予最宽的解释，以使其涵盖所有这些变型例以及等同的结构和功能。