 Patent Application Title |
Patent App Num. |
Date |
 Seam-based reduction and expansion of images using partial solution matrix dependent on dynamic programming access pattern | 20130120407 | 20130516 |
 Systems, methods, and computer-readable storage media for resizing images using seam carving techniques may include generation of a partial solution matrix by at least partially isolating dependencies between sub-problems of a dynamic programming problem corresponding to its solution within different regions of an input image. The number and/or shape of the isolated (or partially isolated) sub-problems may be dependent on the access pattern used by a dynamic programming operation to identify seams in the input image. Multiple sub-problems may be processed independently and in parallel on respective processor core(s) or threads thereof to generate the partial solution matrix. The partial solution matrix may then be processed to identify one or more low-cost seams of the input image. The methods may be implemented as stand-alone applications or... |
| Methods for clustering collections of geo-tagged photographs | 20130022282 | 20130124 |
 Systems and methods for clustering photos that include both time stamps and location coordinates. A two step method that first detects boundaries using time and location information independently to form a set of candidate boundaries is implemented. Such boundaries partition the set of time-ordered photos into clusters. A subset of the candidate boundaries is selected by an efficient dynamic programming procedure to optimize a cost function. Several cost functions are used to design clusterings that are coherent in space, time, or both. One set of cost functions minimizes inter-photo distances directly. A second set maximizes an information measure to select clusterings for consistency in both time and space.
... |
| Population of dynamic objects representing static namespace hierarchies | 20130007699 | 20130103 |
 A namespace-based static metadata model is projected into a dynamic programming environment. A dynamic object is created for each static namespace. The host environment populates the dynamic object with a top-level namespace of the static namespace. The dynamic objects are defined such that a request for a member a member of the namespace lazily populates the static metadata into a projected sub-namespace object or a projected type object.
... |
| Static metadata in dynamic programs | 20130007702 | 20130103 |
 A dynamic programming environment includes a dynamic runtime infrastructure configured to receive static metadata as source text in a source code written in a dynamic programming language. The dynamic runtime infrastructure determines an object representation based on the static metadata from the source text in the source code.
... |
| Method for scheduling power generators based on optimal configurations and approximate dynamic programming | 20120310608 | 20121206 |
 A unit commitment problem is solved for a set of generators with a set of configurations having a set of 2N.T schedules, wherein N is a number of generators i and T is a number of decision time steps. A reduced set of configurations is determined, and then a functional metric to measure a similarity of all possible pairs of the configurations is defined. Dynamic programming is applied to the reduced set of configurations using the similarity metric to determine an optimal configuration.
... |
| |
| Dynamic management of groups for entitlement and provisioning of computer resources | 20120278903 | 20121101 |
| Methods, systems, and techniques for managing groups of entities, such as individuals, employees, or systems, and providing entitlement and access to computer resources based on group membership are provided. Example embodiments provide a Group Management System having a Group Management Engine “GME,” an Entitlement Engine, and a Provisioning Engine, which work together to allow simplified grouping of entities and providing entitlement and access to the entities based upon the group membership. In one embodiment, the GME leverages dynamic programming techniques to enable accurate, scalable systems that can manage near real time updates and changes to the group's status or to the entities' status. These components cooperate to enable provisioning of applications based upon current entitlement.
... |
| Managing fresh-product inventory | 20120271740 | 20121025 |
| Freshness inventory control problem may be formulated as a stochastic dynamic program. In one aspect, a stochastic dynamic programming formulation takes as input inventory status, stochastic demand forecast and cost information associated with on-hand inventory. The stochastic dynamic programming formulation is maximized to determine order quantity and depletion quantity of the product per period.
... |
| Apparatus for calculating scores for chains of sequence alignments | 20120245852 | 20120927 |
| Each of a plurality of substantially co-linear alignments has a score. Each alignment may comprise a starting alignment that has been diagonally extended to meet a length requirement. Dynamic programming is performed in interalignment regions between the extended alignments to generate a corresponding set of interalignment scores. Alignment scores and interalignment scores are summed to generate a score for the entire chain of alignments. This process is repeated for multiple chains. Chains of alignments are ranked by chain score and are displayed to a user. In one embodiment, additional dynamic programming is performed at the head and tail of each chain to increase the chain score when possible. An integrated circuit that performs the method at high speed in hardware is disclosed. Techniques are disclosed that... |
| Stereo matching system using dynamic programming and method thereof | 20120163703 | 20120628 |
| Disclosed is a stereo matching system and method using a dynamic programming scheme. The stereo matching system and method using a dynamic programming scheme according to the present invention may perform viterbi type stereo matching using at least two different penalty of disparity discontinuity (PD) values and synthesize the performed stereo matching results, thereby outputting a disparity map.
... |
| Apparatus and method for stereo matching | 20120163704 | 20120628 |
| An image matching apparatus includes a bilateral filter that filters a left image and a right image to output a second left image and a second right image; a census cost calculation unit performing census transform on a window based on a first pixel of the second left image and a window based on a second pixel of the second right image to calculate a census cost corresponding to a pair of pixels of the first and second pixels; a support weight calculation unit obtaining support weights of the left and right images or the second left and second right images; a cost aggregation unit obtaining energy values of nodes corresponding to the pair of pixels of the first and second pixels using the census cost... |
| Method and system for processing ultrasound data | 20120128223 | 20120524 |
| A method of processing ultrasound data includes receiving ultrasound data for a first ultrasound image, the first ultrasound image being represented as a first set of discrete pixels corresponding to positions of a region of interest; receiving ultrasound data for a second ultrasound image, the second ultrasound image being represented as a second set of discrete pixels corresponding to positions of the region of interest; generating a displacement map by minimizing a cost function using a dynamic programming procedure that identifies each of the first set of discrete pixels with a corresponding one of the second set of discrete pixels; refining the displacement map to obtain intermediate displacement values corresponding to positions between the discrete pixels based on minimizing a local approximation to the cost function;... |
| Duty cycle independent real time dynamic programming implementation for hybrid systems controls optimization | 20120130695 | 20120524 |
| For the current time step, for starting environment conditions substantially similar to the current environment conditions, the combination of control parameters that results in the system response designated as the optimal response is determined from the expected system responses and is applied to the system.
... |
| Pricing mechanisms for perishable time-varying resources | 20120095940 | 20120419 |
| A price determination module (PDM) is described herein which defines price information for perishable resource items subject to variable supply and demand. The price information specifies pricing options for consideration by consumers. In one approach, the PDM provides a plurality of per-instant pricing options, where each pricing option defines a price for a resource item in a particular time instance. In another approach, the PDM provides a plurality of per-contract pricing options, where each pricing option defines a price for a resource item in a particular time segment. The PDM can determine the pricing options by formulating and solving an optimization problem, e.g., using a dynamic programming technique. The optimization problem can be constrained by either hard or soft capacity constraints.
... |
| |
| Method for efficiently managing property types and constraints in a prototype based dynamic programming language | 20120084750 | 20120405 |
| Methods and systems for managing property types, constraints, and other property validations in prototype-based dynamic programming languages, such as the JavaScript® programming language, are presented. A property definition is created for a target class by a programmer, and a properties class is automatically generated for the target class along with get and set methods to access and validate properties in the properties class. A properties class of a parent class can be automatically determined to exist and added such that the target class properties class inherits from the parent class properties class.
... |
| Model, service and implementation separation | 20120084795 | 20120405 |
| Embodiments are directed to combining service operations with various managed system objects to form a new dynamic programming interface combination and determining valid dynamic programming interface combinations. A computer system determines which service operations are offered by a selected managed system. The selected managed system is configured to provide various services comprising multiple different service operations. The computer system determines that managed system objects of the managed system are to be combined with at least one of the service operations. The computer system also combines the service operation with the managed system object, so that a new dynamic programming interface combination is created. The new dynamic programming interface combination is configured for use by the services offered by the managed system.
... |
| Character string generation method, article of manufacture and system | 20120036149 | 20120209 |
| A method, article of manufacture, and system for enabling context surrounding a search result to be displayed succinctly. The method includes searching a document set configured as a frequency ordered suffix tree to obtain a frequency ordered context tree. Applying dynamic programming to the frequency ordered context tree to retrieve a set (C) of context strings (c) having n1 elements of context strings (c). Defining an area covered by a character string (s) in the entire set of context strings C {c1, . . . , cn1} as the product of (1) the number (n2) of context strings (c) having s as a prefix and (2) the length of character string (s). Obtaining a set of character strings (S) that maximizes the sum of areas. In... |
| Semantic parsing of objects in video | 20120027304 | 20120202 |
| The invention provides an improved method to detect semantic attributes of human body in computer vision. In detecting semantic attributes of human body in computer vision, the invention maintains a list of semantic attributes, each of which corresponds to a human body part. A computer module then analyzes segments of a frame of a digital video to detect each semantic attribute by finding a most likely attribute for each segment. A threshold is applied to select candidate segments of the frame for further analysis. The candidate segments of the frame then go through geometric and resolution context analysis by applying the physical structure principles of a human body and by analyzing increasingly higher resolution versions of the image to verify the existence and accuracy of parts... |
| Searching in audio speech | 20100324900 | 20101223 |
| A computerized method of detecting a target word in a speech signal. A speech recognition engine and a previously constructed phoneme model is provided. The speech signal is input into the speech recognition engine. Based on the phoneme model, the input speech signal is indexed. A time-ordered list is stored representing n-best phoneme candidates of the input speech signal and phonemes of the input speech signal in multiple phoneme frames. The target word is transcribed into a transcription of target phonemes. The time-ordered list of n-best phoneme candidates is searched for a locus of said target phonemes. While searching, scoring is based on the ranking of the phoneme candidates among the n-best phoneme candidates and based on the number of the target phonemes found. A composite... |
| Compile-time context for dynamically bound operations | 20100299658 | 20101125 |
| Compile-time context information is captured and provided to a runtime binder for dynamic features in programming languages. For example, a C# run-time binder uses the information to perform a run-time bind with semantics matching the compiler's binding behavior. Dynamic programming language features supported relate to compound operations, events, delegates, member accessibility, dynamic-typed objects, structs passed by ref, arguments passed by name rather than position, extension methods, conditionally compiled methods, literal arguments, overflow checking, dynamic indexed properties, dynamic method groups, and static method groups.
... |
| Systems and methods for markdown optimization when inventory pooling level is above pricing level | 20100250329 | 20100930 |
| Computer-implemented systems and methods generate a near-optimum product markdown plan for a plurality of uniform pricing levels having a required inventory sell-through target over all of the plurality of uniform pricing levels. A plurality of feasible markdown schedules are generated for the uniform pricing level, where each of the plurality of feasible markdown schedules meets all individual constraints for the uniform pricing level. All dominated feasible markdown schedules are removed for the uniform pricing level to generate one or more candidate markdown schedules for the uniform pricing level. A near-optimum product markdown plan is generated, where generating the near-optimum product markdown plans includes executing a limited exact algorithm solver for a plurality of iterations, and executing a dynamic programming solver if no product markdown plan generated... |
| Mass segmentation using mirror image of region of interest | 20100226551 | 20100909 |
| A method and an apparatus for automatic segmentation of an image representing a mass of a tissue region based on dynamic programming that guarantees an accurate and closed contour of the mass is disclosed. The method according to one embodiment accesses digital image data representing an image including the mass of the tissue region, creates a mirror image of the digital image data, extracts a Region of Interest (ROI) which includes a portion of the mirror image containing the mass, transforms the ROI to polar space for obtaining a polar image of the ROI, assigns local cost to sub portions of the polar image, and finds a contour of the mass based on the assigned local cost.
... |
| System and method for stereo matching of images | 20100220932 | 20100902 |
| A system and method for stereo matching of at least two images, e.g., a stereoscopic image pair, employing a global optimization function, e.g., a belief propagation function, that utilizes dynamic programming as a preprocessing step are provided. The system and method of the present disclosure provide for acquiring a first image and a second image from a scene, estimating the disparity of at least one point in the first image with at least one corresponding point in the second image, and minimizing the estimated disparity using a belief propagation function, e.g., a global optimization function, wherein the belief propagation function is initialized with a result of a deterministic matching function, e.g., dynamic programming, applied to the first and second image to speed up the belief propagation... |
| Stereo image segmentation | 20100220921 | 20100902 |
| Real-time segmentation of foreground from background layers in binocular video sequences may be provided by a segmentation process which may be based on one or more factors including likelihoods for stereo-matching, color, and optionally contrast, which may be fused to infer foreground and/or background layers accurately and efficiently. In one example, the stereo image may be segmented into foreground, background, and/or occluded regions using stereo disparities. The stereo-match likelihood may be fused with a contrast sensitive color model that is initialized or learned from training data. Segmentation may then be solved by an optimization algorithm such as dynamic programming or graph cut. In a second example, the stereo-match likelihood may be marginalized over foreground and background hypotheses, and fused with a contrast-sensitive color model that is... |
| Automating dynamic programs | 20100205590 | 20100812 |
| Solving combinatorial optimisation problems using dynamic programming involves automating the integration of bounds propagation into compilation of a dynamic program. This is done by extracting bounds from partial results obtained during dynamic programming, and tightening the bounds throughout execution of the dynamic program. This dramatically reduces the number of “good” solutions that need to be constructed at each stage, improving speed and scalability of algorithms using such dynamic programming.
... |
| Method for composing confocal microscopy image with higher resolution | 20100150472 | 20100617 |
| A method for composing a confocal microscopy image with a higher resolution comprising the steps of: (1) start; (2) to decide whether the number of images to be stitched are more than two, if no, going to step (3), otherwise, going to step (7); (3) proceeding pyramidal correlations; (4) gaining compensation for the overlapped region of the two images; (5) proceeding an intensity adjustment beyond the overlapped regions; (6) proceeding a dynamic programming, then going to step (15); (7) to decide whether the pyramidal correlation is a must, if yes, going step (8), otherwise, going to step (12); (8) proceeding the pyramidal correlations; (9) proceeding an adjacency adjustment; (10) to decide whether a linear adjustment by a distance map is a must, if yes, going to... |
| Method and apparatus for improving performance of approximate string queries using variable length high-quality grams | 20100125594 | 20100520 |
| A computer process, called VGRAM, improves the performance of these string search algorithms in computers by using a carefully chosen dictionary of variable-length grams based on their frequencies in the string collection. A dynamic programming algorithm for computing a tight lower bound on the number of common grams shared by two similar strings in order to improve query performance is disclosed. A method for automatically computing a dictionary of high-quality grams for a workload of queries. Improvement on query performance is achieved by these techniques by a cost-based quantitative approach to deciding good grams for approximate string queries. An approach for answering approximate queries efficiently based on discarding gram lists, and another is based on combining correlated lists. An indexing structure is reduced to a given... |
| Method and system for scheduling image acquisition events based on dynamic programming | 20100115519 | 20100506 |
| A method and system for scheduling events into a set of opportunities is presented. The method includes 1) dividing a path of an image acquisition device so that there is at least a first portion and a second portion at any given moment, wherein each of the first portion and the second portion includes at least one state and the first portion includes a null state in which no image is taken; 2) combining each state in the first portion with at least one state in the second portion one by one to generate a series of updated sequences; and 3) selecting at least one of the updated sequences based on a merit value associated with each of the updated sequences. The invention uses only two... |
| Ticker uploader for ebay® | 20100100534 | 20100422 |
| A method for automatically uploading information to an eBay® server includes the steps of: (a) receiving in a parsing server a formatted electronic file containing information about at least one of product information including event ticket information and other product information, and service information; (b) translating the formatted electronic file within the parsing server into a format that is compatible with eBay® API to provide a compatible parsed data file using a dynamic programming language; and (c) automatically uploading the compatible parsed data file to an eBay® server. The method also updates any existing event tickets or products or services that have been uploaded to eBay® previously using this method.
... |
| Ribcage segmentation | 20100098313 | 20100422 |
| A technique for segmenting a ribcage, e.g., in a chest radiograph, may involve determining whether or not the top of the image cuts through the lungs. The process may then proceed to segment the top and the sides of the ribcage. A dynamic programming technique may be used to perform the segmentation.
... |
| Automated information technology management | 20100094590 | 20100415 |
| Systems, articles of manufacture, and associated computer-executed methods determine an optimum temporal segmentation for automated information technology (IT) management. A computer-executed method detects changes in a performance metric in an automated information technology (IT) management system comprising defining a plurality of temporal segments as sets of contiguous time samples wherein time samples within a segment are mutually more similar in terms of performance metric behavior than time samples in previous and subsequent segments, and discovering the segments using an information-theoretical approach. Detecting changes in the performance metric can further comprise associating cost with the segments that is lesser for homogeneous metric behavior and greater for heterogeneous metric behavior within a segment, and finding segmentation that minimizes the cost using dynamic programming. The segments can be discovered... |
| Method and system for automatic coronary artery detection | 20100067760 | 20100318 |
| A method and system for coronary artery detection in 3D cardiac volumes is disclosed. The heart chambers are segmented in the cardiac volume, and an initial estimation of a coronary artery is generated based on the segmented heart chambers. The initial estimation of the coronary artery is then refined based on local information in the cardiac volume in order to detect the coronary artery in the cardiac volume. The detected coronary artery can be extended using 3D dynamic programming.
... |
| Detouring in scripting systems | 20100058293 | 20100304 |
| A system described herein includes a receiver component that receives third party code for execution in a host environment, wherein the third party code corresponds to a dynamic programming language, and wherein the third party code has at least one object reference to a first object that is used by the third party code. A detouring component automatically replaces the first object referenced by the third party code with a proxy object such that the third party code at runtime calls the proxy object instead of the first object.
... |
| System and method for loading records into a partitioned database table | 20100030793 | 20100204 |
| An improved system and method for loading records into a partitioned database table is provided. A translation of records may be generated from a set of source partitions to a set of target partitions by generating a bipartite graph, determining a maximal matching using dynamic programming for a chain of nodes remaining in the bipartite graph after removing singleton edges, and generating a maximal matching after adding back the singleton edges for translation of records from the set of source partitions to the set of target partitions. The partition translation may be executed by traversing from top to bottom the set of source partitions and the set of target partitions in record key order to generate an optimal sequence of operations to transfer the records from... |
| Method and apparatus for improving security in an application level virtual machine environment | 20100005449 | 20100107 |
| In one embodiment the present invention includes a security manager for managing security in a dynamic programming environment. The security manager interfaces between the dynamic programming environment and a non-dynamic programming environment. In this manner, the dynamic programming environment is unable to compromise the non-dynamic programming environment, yet still provide features desirable in a dynamic programming environment. An example using Ruby in a robust business programming environment is detailed.
... |
| Systems and methods for tokenizing and interpreting uniform resource locators | 20090327304 | 20091231 |
| Aspects include methods, computer readable storing instructions for such methods, and systems for processing text strings such as URLs that comprise patterns of parameters and values for such parameters, delimited in a site-specific manner. Such aspects provide for accepting a number of text strings that are expected to have a common delimiting strategy, then deeply tokenizing those text strings to arrive at a set of tokens from which are selected anchor tokens used to form patterns having the anchor tokens separated by wildcard portions for recursive processing. The patterns formed can be mapped to a tree of nodes. Information concerning relationships between nodes and between tokens within a given node, as well as other heuristics concerning which tokens are parameters and which are values can be... |
| Nucleotide and amino acid sequence compression | 20090292699 | 20091126 |
| A biomolecular sequence database is encoded using a set of byte-aligned block codes. Some of the block codes encode a portion of a current sequence by pointing to an identical portion of another sequence. Others of the block codes are run length codes. Multiple different ways of encoding a current sequence using different ones of the block codes are determined. Dynamic programming is used to determine which one of these ways most efficiently encodes the current sequence into the shortest string of block codes. Each sequence in the database is encoded as such a string of block codes.
... |
| Method and apparatus for reading and programming a non-volatile memory cell in a virtual ground array | 20090290430 | 20091126 |
| A method and apparatus for dynamic programming and dynamic reading of a select non-volatile memory cell in a virtual grounds array is disclosed. The array of non-volatile memory cells are arranged in a plurality of rows and columns, wherein each cell in the same column share a first local bit line to one side and share a second local bit line to another side. Alternating local bit lines are connected to a first global bit line and other alternating local bit lines are connected to a second global bit line with the global bit lines connected to a sense amplifier. In the dynamic read operation the global bit lines and the associated local bit lines are connected to a precharged voltage. One of the first or... |
| Sequence similarity measuring apparatus and control method thereof | 20090287755 | 20091119 |
| Disclosed is a sequence similarity measuring apparatus and a method of controlling the same. The sequence similarity measuring apparatus using dynamic programming includes: a matrix generating unit for generating a matrix based on the dynamic programming by using two sequences; a normalization unit for calculating a similarity reference value by inputting an element value of a last row/column of the matrix generated by the matrix generating unit into a normalization formula for a given sequence length; and a similarity measuring unit for measuring predefined sequence similarity between the two sequences, based on the similarity reference value calculated by the normalization unit. This makes it possible to easily and correctly achieve similarity comparison between multiple sequences, and thus this technology is expected to be widely utilized in... |
| Power management of a hybrid vehicle | 20090259355 | 20091015 |
| A system and method of determining and applying power split ratios to power sources within hybrid vehicles. The power split ratio is determined using a two-scale dynamic programming technique to achieve optimal state of charge depletion over the course of a trip. On the macro-scale level, a global state of charge profile is created for the entire trip. On the micro-scale level, the state of charge profile and accompanying power split ratio is recalculated at the end of each segment as the vehicle proceeds along the trip. Various trip modeling techniques are used to provide constraints for the dynamic programming.
... |
| Power management systems and methods in a hybrid vehicle | 20090259363 | 20091015 |
| A system and method of determining and applying power split ratios to power sources within hybrid vehicles. The power split ratio is determined using a two-scale dynamic programming technique to achieve optimal state of charge depletion over the course of a trip. On the macro-scale level, a global state of charge profile is created for the entire trip. On the micro-scale level, the state of charge profile and accompanying power split ratio is recalculated at the end of each segment as the vehicle proceeds along the trip. Various trip modeling techniques are used to provide constraints for the dynamic programming.
... |
| System and method for optimizing online keyword auctions subject to budget and estimated query volume constraints | 20090254397 | 20091008 |
| An improved system and method for optimizing online keyword auctions subject to budget and estimated query volume constraints is provided. A linear programming model of slates of advertisements may be created using estimates of the query volume for multiple time periods for use in generating a slate of advertisements that may represent a candidate set of advertisements in order of optimal revenue to an auctioneer. Upon receiving a query request, the slate generated by the linear program or a slate generated by dynamic programming may be chosen based on whether the weighted sum of prices for the slate of advertisements computed by dynamic programming may be within a factor of the weighted sum of the prices for the slate of advertisements computed by the linear program.... |
| System and method for optimizing online keyword auctions subject to budget and estimated query volume constraints | 20090254397 | 20091008 |
| An improved system and method for optimizing online keyword auctions subject to budget and estimated query volume constraints is provided. A linear programming model of slates of advertisements may be created using estimates of the query volume for multiple time periods for use in generating a slate of advertisements that may represent a candidate set of advertisements in order of optimal revenue to an auctioneer. Upon receiving a query request, the slate generated by the linear program or a slate generated by dynamic programming may be chosen based on whether the weighted sum of prices for the slate of advertisements computed by dynamic programming may be within a factor of the weighted sum of the prices for the slate of advertisements computed by the linear program.... |
| Online handwriting expression recognition | 20090245646 | 20091001 |
| One way of recognizing online handwritten mathematical expressions is to use a one-pass dynamic programming based symbol decoding generation algorithm. This method embeds segmentation into symbol identification to form a unified framework for symbol recognition. Along with decoding, a symbol graph is produced. Besides accurately recognizing handwritten mathematical expressions, this method can produce high quality symbol graphs. This method uses six knowledge source models to help search for possible symbol hypotheses during the decoding process. Here, knowledge source exponential weights and a symbol insertion penalty are used to weigh the various knowledge source model probabilities to increase accuracy.
... |
| Multi-user mimo systems with imperfect csit and arq | 20090213741 | 20090827 |
| A robust closed-loop cross-layer design provides for the downlink multi-user multi-antenna systems with imperfect Channel State Information at the transmitter (CSIT) for slow fading channels. Using ACK/NAK feedbacks from mobiles, a closed-loop cross-layer scheduler does not require any knowledge of the CSIT error statistics. To take into account of the potential packet outage (due to imperfect CSIT), we define system goodput, which measures the average bits per second per Hertz (b/s/Hz) successfully delivered to the mobiles, as the optimization objectives. We formulate the cross-layer design as a mixed combinatorial search and Markov decision problem. Based on dynamic programming approach, the optimal power and rate allocation is determined using backward recursion and forward recursion algorithms. Simulations illustrate that the proposed closed-loop cross-layer scheduler has very robust goodput... |
| Multi-user mimo systems with imperfect csit and arq | 20090213741 | 20090827 |
| A robust closed-loop cross-layer design provides for the downlink multi-user multi-antenna systems with imperfect Channel State Information at the transmitter (CSIT) for slow fading channels. Using ACK/NAK feedbacks from mobiles, a closed-loop cross-layer scheduler does not require any knowledge of the CSIT error statistics. To take into account of the potential packet outage (due to imperfect CSIT), we define system goodput, which measures the average bits per second per Hertz (b/s/Hz) successfully delivered to the mobiles, as the optimization objectives. We formulate the cross-layer design as a mixed combinatorial search and Markov decision problem. Based on dynamic programming approach, the optimal power and rate allocation is determined using backward recursion and forward recursion algorithms. Simulations illustrate that the proposed closed-loop cross-layer scheduler has very robust goodput... |
| Multi-user mimo systems with imperfect csit and arq | 20090213741 | 20090827 |
| A robust closed-loop cross-layer design provides for the downlink multi-user multi-antenna systems with imperfect Channel State Information at the transmitter (CSIT) for slow fading channels. Using ACK/NAK feedbacks from mobiles, a closed-loop cross-layer scheduler does not require any knowledge of the CSIT error statistics. To take into account of the potential packet outage (due to imperfect CSIT), we define system goodput, which measures the average bits per second per Hertz (b/s/Hz) successfully delivered to the mobiles, as the optimization objectives. We formulate the cross-layer design as a mixed combinatorial search and Markov decision problem. Based on dynamic programming approach, the optimal power and rate allocation is determined using backward recursion and forward recursion algorithms. Simulations illustrate that the proposed closed-loop cross-layer scheduler has very robust goodput... |
| Multi-user mimo systems with imperfect csit and arq | 20090213741 | 20090827 |
| A robust closed-loop cross-layer design provides for the downlink multi-user multi-antenna systems with imperfect Channel State Information at the transmitter (CSIT) for slow fading channels. Using ACK/NAK feedbacks from mobiles, a closed-loop cross-layer scheduler does not require any knowledge of the CSIT error statistics. To take into account of the potential packet outage (due to imperfect CSIT), we define system goodput, which measures the average bits per second per Hertz (b/s/Hz) successfully delivered to the mobiles, as the optimization objectives. We formulate the cross-layer design as a mixed combinatorial search and Markov decision problem. Based on dynamic programming approach, the optimal power and rate allocation is determined using backward recursion and forward recursion algorithms. Simulations illustrate that the proposed closed-loop cross-layer scheduler has very robust goodput... |
| Multi-user mimo systems with imperfect csit and arq | 20090213741 | 20090827 |
| A robust closed-loop cross-layer design provides for the downlink multi-user multi-antenna systems with imperfect Channel State Information at the transmitter (CSIT) for slow fading channels. Using ACK/NAK feedbacks from mobiles, a closed-loop cross-layer scheduler does not require any knowledge of the CSIT error statistics. To take into account of the potential packet outage (due to imperfect CSIT), we define system goodput, which measures the average bits per second per Hertz (b/s/Hz) successfully delivered to the mobiles, as the optimization objectives. We formulate the cross-layer design as a mixed combinatorial search and Markov decision problem. Based on dynamic programming approach, the optimal power and rate allocation is determined using backward recursion and forward recursion algorithms. Simulations illustrate that the proposed closed-loop cross-layer scheduler has very robust goodput... |
| Method and apparatus for providing a dynamic programming guide containing future times when on-demand broadcasting requests can be satisfied | 20090172732 | 20090702 |
| An audio-visual content service provider (400) processor (401) receives (101) at least one on-demand broadcasting request for particular audio-visual content from an end user (405). The processor then determines (102) at least one future time at which the on-demand broadcasting request can likely be satisfied and provides (103) a corresponding dynamic programming guide to the end user that comprises, at least in part, this at least one future time.
... |
| System and method of executing a dynamic program in a structured environment | 20090119642 | 20090507 |
| In one embodiment the present invention includes a first virtual machine that executes a non-dynamic program, that implements a second virtual machine that executes a dynamic program. The dynamic program operates in the structured environment of the non-dynamic programming language via various allowed interaction pathways. In this manner, dynamic programs may be executed in a robust business applications environment.
... |
| Method and system for vessel segmentation in fluoroscopic images | 20090080728 | 20090326 |
| A method and system for vessel segmentation in fluoroscopic images is disclosed. Hierarchical learning-based detection is used to perform the vessel segmentation. A boundary classifier is trained and used to detect boundary pixels of a vessel in a fluoroscopic image. A cross-segment classifier is trained and used to detect cross-segments connecting the boundary pixels. A quadrilateral classifier is trained and used to detect quadrilaterals connecting the cross segments. Dynamic programming is then used to combine the quadrilaterals to generate a tubular structure representing the vessel.
... |
| Object segmentation using dynamic programming | 20090060332 | 20090305 |
| An object in an image may be segmented by determining local pixel costs based on the image and using the local costs to determined cumulative pixel costs. A contour may then be determined based on the cumulative pixel costs.
... |
| Runtime code modification | 20090024986 | 20090122 |
| Source languages are translated to target dynamic programming languages. Runtime functionality including reflection and/or dynamic code modification exposed by a source language is mapped to a dynamic language implementation such as that of a script language. Target language dynamism is leveraged to efficiently support runtime functionality in a source language that is more static, for example.
... |
| System and method for smoothing hierarchical data using isotonic regression | 20080275890 | 20081106 |
| An improved system and method is provided for detecting a web page template. A web page template detector may be provided for performing page-level template detection on a web page. In general, the web page template classifier may be trained using automatically generated training data, and then the web page template classifier may be applied to web pages to identify web page templates. A web page template may be detected by classifying segments of a web page as template structures, by assigning classification scores to the segments of the web page classified as template structures, and then by smoothing the classification scores assigned to the segments of the web page. Generalized isotonic regression may be applied for smoothing scores associated with the nodes of a hierarchy... |
| System and method for detecting a web page | 20080275901 | 20081106 |
| An improved system and method is provided for detecting a web page template. A web page template detector may be provided for performing page-level template detection on a web page. In general, the web page template classifier may be trained using automatically generated training data, and then the web page template classifier may be applied to web pages to identify web page templates. A web page template may be detected by classifying segments of a web page as template structures, by assigning classification scores to the segments of the web page classified as template structures, and then by smoothing the classification scores assigned to the segments of the web page. Generalized isotonic regression may be applied for smoothing scores associated with the nodes of a hierarchy... |
| Methods and systems for powertrain optimization and improved fuel economy | 20080262712 | 20081023 |
| The technology described herein provides methods and systems for powertrain optimization and improved fuel economy including multiple displacement engine modeling and control optimization, automotive powertrain matching for fuel economy, cycle-based automotive shift and lock-up scheduling for fuel economy, and engine performance requirements based on vehicle attributes and drive cycle characteristics. Also provided is a reverse tractive road load demand simulation algorithm used to propagate a reverse tractive road load demand and a corresponding component torque and speed, derived from a vehicle speed trace, in a reverse direction through a powertrain system. Also provided is a dynamic optimization algorithm. The dynamic programming algorithm is applied to a matrix of fuel flow rates to find the optimal control path that maximizes the powertrain efficiency over a cycle.
... |
| Scheduling packet transmission | 20080253372 | 20081016 |
| Scheduling packet transmission. A plurality of data packets is received, wherein at least a portion of the plurality of data packets is associated with one media unit and comprises different quality information. Profit-to-size ratios or distortion-to-size ratios for the data packets are determined. A plurality of schedules of the data packets are determined utilizing dynamic programming for a plurality of data rates based at least in part on the profit-to-size ratios or distortion-to-size ratios.
... |
| Learning a* priority function from unlabeled data | 20080256007 | 20081016 |
| A technique for increasing efficiency of inference of structure variables (e.g., an inference problem) using a priority-driven algorithm rather than conventional dynamic programming. The technique employs a probable approximate underestimate which can be used to compute a probable approximate solution to the inference problem when used as a priority function (“a probable approximate underestimate function”) for a more computationally complex classification function. The probable approximate underestimate function can have a functional form of a simpler, easier to decode model. The model can be learned from unlabeled data by solving a linear/quadratic optimization problem. The priority function can be computed quickly, and can result in solutions that are substantially optimal. Using the priority function, computation efficiency of a classification function (e.g., discriminative classifier) can be increased using... |
| Optimized smith-waterman search | 20080250016 | 20081009 |
| An optimized database searching for a query sequence having a plurality of vectors arranged in a linear fashion, wherein the vectors are parallel to a query sequence, and a plurality of elements of the query sequence are reordered in a striped pattern, and wherein a set of dynamic programming scoring results are reported for further processing.
... |
| Detailed placer for optimizing high density cell placement in a linear runtime | 20080250375 | 20081009 |
| A detailed placement process which optimizes cell placement with up to one hundred percent densities in a linear run time. The output from a conjugate-gradient coarse placement process is input to the detailed placement process. A dynamic programming technique is used to optimize cell placement by swapping cells between two or more rows. The search space is pruned beforehand. A greedy cleanup phase using an incremental row placer is used. Thereby, the detailed placement process handles congestion driven placements characterized by non-uniform densities expeditiously and efficiently.
... |
| Optimally selecting tv programs for recording and viewing | 20080235734 | 20080925 |
| A system (400), apparatus (300), and method (200) are provided to simultaneously select TV programs for recording and watching during a certain time period [b, e] having a beginning time b and an ending time e. For each TV program a value is provided for receiving and recording and an additional value for watching. The values represent the preferences of a viewer. A dynamic programming approach is provided that solves the selection and viewing problem to optimality (guaranteed). The key idea behind the DP approach is the definition of the states, which represent all relevant information of previous steps needed to be able to judge a following step. A state definition includes time points at which the tuners are available after having received a program, and... |
| Multiple criteria decision making (mcdm) method for maintaining complex technology | 20080168015 | 20080710 |
| The invention relates to a method of multiple criteria decision making. In particular, a method of maintaining a complex article is described that includes the steps of; (a) taking a set of options for replacing each of a plurality of components of the complex article, (b) identifying an optimum solution set from the set of possible replacement options of step (a) that best satisfies a plurality of criteria and (c) implementing an optimum solution of the optimum solution set. The step of identifying an optimum solution set comprises the step of evaluating a plurality of potential solutions from the set of possible options defined in step (a) against the plurality of criteria. The criteria values for potential solutions comprise probability functions and the step of evaluating... |
| Mass segmentation using mirror image of region of interest | 20080152220 | 20080626 |
| A method and an apparatus for automatic segmentation of an image representing a mass of a tissue region based on dynamic programming that guarantees an accurate and closed contour of the mass is disclosed. The method according to one embodiment accesses digital image data representing an image including the mass of the tissue region, creates a mirror image of the digital image data, extracts a Region of Interest (ROI) which includes a portion of the mirror image containing the mass, transforms the ROI to polar space for obtaining a polar image of the ROI, assigns local cost to sub portions of the polar image, and finds a contour of the mass based on the assigned local cost.
... |
| System and method for generating a maximum utility slate of advertisements for online advertisement auctions | 20080154662 | 20080626 |
| An improved system and method for generating a maximum utility slate of advertisements for online advertisement auctions is provided. Various utility factors for each advertisement that may be a candidate in a slate of advertisements may be applied within a framework in order to generate a maximum utility slate of advertisements. Either backward or forward dynamic programming may be applied to recursively evaluate the utility of subslates of advertisements in order to generate a maximum utility slate of advertisements. In an embodiment, a network with directed edges and associated costs may be defined, and the longest path may be found in the directed network for constructing a maximum utility slate of advertisements. Various utility factors may be applied for different objectives of an auctioneer and the... |
| Dynamic economic load dispatch | 20080154810 | 20080626 |
| In an embodiment, a system and method provide a constraint on a genetic algorithm, and further provide dynamic programming capability to the genetic algorithm. The system and method then allocate load demand over a finite number of time intervals among a number of power generating units as a function of the constraint on the genetic algorithm and the dynamic programming capability of the genetic algorithm.
... |
| Memory-efficient method for high-quality codebook based voice conversion | 20080147385 | 20080619 |
| An improved system method for enabling and implementing codebook-based voice conversion that both significantly reduces the memory footprint and improves the continuity of the output. In various embodiments, the paired source-target codebook is implemented as a multi-stage vector quantizer. During the conversion, N best candidates in a tree search are taken as the output from the quantizer. The N candidates for each vector to be converted are used in a dynamic programming-based approach that finds a smooth but accurate output sequence.
... |
| Ruled-line-projection extracting apparatus, ruled-line projection extracting method, and computer product | 20080112619 | 20080515 |
| A set of straight lines that associate a top parallel geodesic projection positioned at an upper end with a bottom parallel geodesic projection positioned at a lower end, among sets of parallel geodesic projections, is extracted as a set of ruled-line candidate projections as a search target of a set of ruled line projections. A deviation of neighborhood, which is a distance between a cross ratio vector of the ruled-line candidate projection and a cross ratio vector of a neighboring line obtained by shifting the ruled-line candidate projection by a predetermined interval, is calculated for each ruled-line candidate projection. A set of straight lines having the smallest sum total of deviations of neighborhood, in the set of straight lines, which do not intersect with each other,... |
| Methods for gray-level ridge feature extraction and associated print matching | 20080101663 | 20080501 |
| A method for level three feature extraction from a print image extracts features associated with a selected ridge segment using a gray-level image under the guidance of at least one binary image. The level three features are a sequence of vectors each corresponding to a different level three characteristic and each representing a sequence of values at selected points on a print image. The level three features are stored and used for level three matching of two prints. During the matching stage, ridge segments are correlated against each other by shifting or a dynamic programming method to determine a measure of similarity between the print images.
... |
| Optimal content distribution in video-on-demand tree networks | 20080071894 | 20080320 |
| A method provides for the optimal location of servers and the optimal assignment of programs to the servers in a video-on-demand (VOD) network with a tree topology. Each node may have demands for multiple VOD programs. The central server at the root of the network stores all programs, and each of the other servers may store some of these programs. The cost considered include cost of servers, cost of assigning programs to servers, and cost of link bandwidths used for broadcasting programs from servers to demands at various nodes. The demand for a specific program is served by the closest server that has this program along the path that connects the requesting node to the root of the tree network. The invention consists of a dynamic... |
| Calculating cost measures between hmm acoustic models | 20080059184 | 20080306 |
| Measurement of Kullback-Leibler Divergence (KLD) between hidden Markov models (HMM) of acoustic units utilizes an unscented transform to approximate KLD between Gaussian mixtures. Dynamic programming equalizes the number of states between HMMs having a different number of states, while the total KLD of the HMMs is obtained by summing individual KLDs calculated by state pair by state pair comparisons.
... |
| System and method for hierarchical segmentation of websites by topic | 20080046429 | 20080221 |
| An improved system and method is provided for hierarchical segmentation of websites by topic. To do so, an organization of topics may be determined within directories of a website, the hierarchical arrangement of the web pages in the website may be segmented by topic, and the segments representing regions of coherent topics in the website directory may be output. In an embodiment, a website directory may be converted into a binary tree and dynamic programming may be applied to iteratively determine whether to add a node of the tree to a segment representing a topic. A node selection cost may be evaluated to determine whether to add a node of the tree as a segment representing a topic. And a cohesiveness cost may be evaluated to... |
| Dynamic asset allocation using stochastic dynamic programming | 20080010181 | 20080110 |
| A system and method are disclosed for capturing the full dynamic and multi-dimensional nature of the asset allocation problem through applications of stochastic dynamic programming and stochastic programming techniques. The system and method provide a novel approach to asset allocation and based on stochastic dynamic programming and Monte Carlo sampling that permit one to consider many rebalancing periods, many asset classes, dynamic cash flows, and a general representation of investor risk preference. The system and method further provide a novel approach of representing utility by directly modeling risk aversion as a function of wealth, and thus provide a general framework for representing investor preference. The system and method demonstrate how the optimal asset allocation depends on the investment horizon, wealth, and the investors risk preference and... |
| Recursive and trellis-based feedback reduction for mimo-ofdm with rate-limited feedback | 20070297529 | 20071227 |
| Techniques are provided for reducing feedback while maintaining performance in a MIMO-OFDM system. The disclosed techniques employ finite-rate feedback methods that uses vector quantization compression. The disclosed methods/techniques generally involve: receiving a plurality of symbols from a plurality of sub-carriers at a receiver; selecting a plurality of indices of codewords corresponding to a codebook of pre-coding weighting matrices for the sub-carriers based on vector quantization compression of the codewords; and transmitting the selected indices over a wireless channel to a transmitter. Finite state vector quantization feedback makes use of a finite state vector quantizer (FSVQ), which is a recursive vector quantizer (VQ) with a finite number of states. In finite state vector quantization feedback, optimal precoding matrices (beamforming vectors) are selected sequentially across subcarriers. In a... |
| System and method for fuel procurement planning | 20070214031 | 20070913 |
| A system creating a purchasing and delivery plan for a commodity is provided. This system sets the number of delivery means that deliver the commodity according to each delivery schedule and the amount of the commodity purchases from each supplier as variables, and for a mixed integer programming problem that minimizes the value of a first objective function that computes the expected value for the delivery and purchase costs, computes a dual solution for a qualification problem for a linear relaxation problem for this. Furthermore, a delivery schedule exhibiting a constraint that violates the dual solution of the qualification problem is searched for by solving a dynamic programming problem having a recursive equation that expresses the changes in the value of a second objective function based... |
| Method and system for generating threads of documents | 20070203924 | 20070830 |
| A method and system for generating threads of documents from a collection C of documents containing terms. Each document of C has a timestamp and an associated timestamp index. The timestamp indexes are ordered in accordance with an ordering of the associated timestamps. A relevance graph G generated from C is an acyclic directed graph. Each node of G denotes a document of C. Each edge of G connects a pair of directed nodes pointing from a node having an earlier timestamp to a node having a later timestamp. At least one thread of G is determined by executing a matching-based algorithm or a dynamic programming algorithm. Each thread is a path through G originating at a first node and terminating at a second node and... |
| System, method and software for static and dynamic programming and configuration of an adaptive computing architecture | 20070157166 | 20070705 |
| The present invention provides a system, method and software for programming and configuring an adaptive computing architecture or device. The invention utilizes program constructs which correspond to and map directly to the adaptive hardware having a plurality of reconfigurable nodes coupled through a reconfigurable matrix interconnection network. A first program construct corresponds to a selected node. A second program construct corresponds to an executable task of the selected node and includes one or more firing conditions capable of determining the commencement of the executable task of the selected node. A third program construct corresponds to at least one input port coupling the selected node to the matrix interconnect network for input data to be consumed by the executable task. A fourth program construct corresponds to at... |
| Pattern matching method and apparatus | 20070150275 | 20070628 |
| A system is provided for matching two or more sequences of phonemes both or all of which may be generated from text or speech. A dynamic programming matching technique is preferably used having constraints which depend upon whether or not the two sequences are generated from text or speech and in which the scoring of the dynamic programming paths is weighted by phoneme confusion scores, phoneme insertion scores and phoneme deletion scores where appropriate.
... |
| Optimization of cascaded classifiers | 20070112701 | 20070517 |
| An optimization system comprises a reception component that receives a cascade of classifiers. The system further includes an optimization component communicatively coupled to the reception component, the optimization component receives input relating to one of speed and accuracy of the cascade of classifiers and optimizes the cascade of classifiers based at least in part upon the received input and confidence scores associated with each classifier within the cascade of classifiers. The optimization component can utilize at least one of a steepest descent algorithm, a dynamic programming algorithm, a simulated annealing algorithm, and a branch and bound variant of a depth first search algorithm in connection with optimizing the cascade of classifiers.
... |
| Systems and methods for employing tagged types in a dynamic runtime environment | 20070067372 | 20070322 |
| The present invention relates to systems and methods that facilitate dynamic programming language execution in a managed code environment. A class component is provided that declares an inheritance hierarchy for one or more tagged values associated with a dynamic programming language. During execution of the tagged values, a rules component mitigates user-defined types from inheriting or deriving properties from the tagged values in order to support a type safe runtime environment. A bifurcated class tree is provided that defines non-tagged type elements on one side of the tree and tagged type element values on an alternate branch of the tree. The rules component analyzes runtime extensions that help to prevent data from one component of the tree deriving or inheriting properties from another component of the... |
| Probabilistic wavelet synopses for multiple measures | 20070058871 | 20070315 |
| A technique for building probabilistic wavelet synopses for multi-measure data sets is provided. In the presence of multiple measures, it is demonstrated that the problem of exact probabilistic coefficient thresholding becomes significantly more complex. An algorithmic formulation for probabilistic multi-measure wavelet thresholding based on the idea of partial-order dynamic programming (PODP) is provided. A fast, greedy approximation algorithm for probabilistic multi-measure thresholding based on the idea of marginal error gains is provided. An empirical study with both synthetic and real-life data sets validated the approach, demonstrating that the algorithms outperform naive approaches based on optimizing individual measures independently and the greedy thresholding scheme provides near-optimal and, at the same time, fast and scalable solutions to the probabilistic wavelet synopsis construction problem.
... |
| Dynamic configuration of unified messaging state changes | 20070055751 | 20070308 |
| The subject invention relates to systems and methods that enable dynamic programming and execution of an electronic communications dialog. In one aspect, a configurable messaging system is provided. The system includes a configuration file to describe interface options of a computerized dialog session, wherein the configuration file specifies interface activities and state transitions between the interface options within the configuration file. A state controller executes the interface options during communications activities with the dialog session. The configuration file can also describe prompt elements to solicit information from users or applications.
... |
| Stereo image segmentation | 20070031037 | 20070208 |
| Real-time segmentation of foreground from background layers in binocular video sequences may be provided by a segmentation process which may be based on one or more factors including likelihoods for stereo-matching, color, and optionally contrast, which may be fused to infer foreground and/or background layers accurately and efficiently. In one example, the stereo image may be segmented into foreground, background, and/or occluded regions using stereo disparities. The stereo-match likelihood may be fused with a contrast sensitive color model that is initialized or learned from training data. Segmentation may then be solved by an optimization algorithm such as dynamic programming or graph cut. In a second example, the stereo-match likelihood may be marginalized over foreground and background hypotheses, and fused with a contrast-sensitive color model that is... |
| Technique for processing a computer program | 20070022424 | 20070125 |
| The present invention is directed to a method for processing, in a computer system, a computer program having a plurality of operations. The method features calling a dynamic programming routine to generate a schedule for executing a subgroup of the plurality of operations by modeling operations of a computational processor associated with the computer system to minimize a computational cost of placing the computer system in a final machine state (finMS).
... |
| Decoding procedure for statistical machine translation | 20070010989 | 20070111 |
| A source sentence is decoded in an iterative manner. At each step a set of partially constructed target sentences are collated, each of which has a score or an associated probability, computed from a language model score and a translation model score. At each iteration, a family of exponentially many alignments is constructed and the optimal translation for this family is found out. To construct the alignment family, a set of transformation operators is employed. The described decoding algorithm is based on the Alternating Optimization framework and employs dynamic programming. Pruning and caching techniques may be used to speed up the decoding.
... |
| Speech recognition device | 20060235686 | 20061019 |
| Disclosed is a speech recognition device using a hidden Markov model and a two-level dynamic programming scheme. The speech recognition device includes an analog to digital converter for sampling and quantizing speech signals into digital speech signals; a noise eliminator for reducing noise from the digital speech signals; a feature vector generator for generating a feature vector from the noise-eliminated speech signals, and converting the feature vector into a test pattern; and a processor including a plurality of processing elements arranged in parallel, each processing element calculating a matching cost of a test pattern and a reference pattern, selecting the minimum value from among the calculated matching costs, and outputting the minimum value as the minimum matching cost of an input test pattern.
... |
| Methods and apparatus relating to searching of spoken audio data | 20060206324 | 20060914 |
| Methods for processing audio data containing speech to produce a searchable index file and for subsequently searching such an index file are provided. The processing method uses a phonetic approach and models each frame of the audio data with a set of reference phones. A score for each of the reference phones, representing the difference of the audio from the phone model, is stored in the searchable data file for each of the phones in the reference set. A consequence of storing information regarding each of the reference phones is that the accuracy of searches carried out on the index file is not compromised by the rejection of information about particular phones. A subsequent search method is also provided which uses a simple and efficient dynamic... |
| Enterprise portfolio analysis using finite state markov decision process | 20060195373 | 20060831 |
| This invention introduces a method, system and computer readable media that enables a computer system or computer networked system to perform enterprise portfolio transition optimization. The invention considers several key factors that are traditionally treated informally. The invention provides a sequential decision model for enterprise portfolio transition management of computer and software resources. Using a finite state Markov Decision process, a mathematical formulation is developed to ensure an optimal enterprise portfolio transition plan, with the objective of balancing expected value and risk, that is solved numerically via an approximate dynamic programming algorithm. The output of the model is a set of recommendations in the form of a transition plan for each of the computer and software resources selected within the enterprise portfolio during each phase of... |
| Efficient methods for temporal event clustering of digital photographs | 20060173746 | 20060803 |
| Techniques for reducing the computational complexity of conventional similarity-based approaches for temporal event clustering of digital photograph collections include one or more approaches to select boundaries based on dynamic programming and the Bayes information criterion. Each method performs competitively with conventional approaches and offer significant computational savings.
... |
| Efficiently calculating scores for chains of sequence alignments | 20060155479 | 20060713 |
| Each of a plurality of substantially co-linear alignments has a score. Each alignment may comprise a starting alignment that has been diagonally extended to meet a length requirement. Dynamic programming is performed in interalignment regions between the extended alignments to generate a corresponding set of interalignment scores. Alignment scores and interalignment scores are summed to generate a score for the entire chain of alignments. This process is repeated for multiple chains. Chains of alignments are ranked by chain score and are displayed to a user. In one embodiment, additional dynamic programming is performed at the head and tail of each chain to increase the chain score when possible. An integrated circuit that performs the method at high speed in hardware is disclosed. Techniques are disclosed that... |
| Apparatus and method for determining stereo disparity based on two-path dynamic programming and ggcp | 20060120594 | 20060608 |
| Provided is an apparatus and method for determining stereo disparity based on two-path dynamic programming and GGCP. The apparatus includes a pre-processing unit for analyzing texture distribution of an input image by using a Laplacian of Gaussian (LOG) filter and dividing the input image into a homogeneous region and a non-homogeneous region; a local matching unit for determining candidate disparities to be included in an each pixel of all pixels; a local post-processing unit for removing candidate disparities in a pixel of low reliability by performing a visibility test betweens candidate disparities in each pixel to improve the reliability of the candidate disparity; and a global optimizing unit for determining a final disparity for candidate disparities in an each pixel by performing a dynamic programming.
... |
| Video-based encroachment detection | 20060093187 | 20060504 |
| A method and system for video-based encroachment detection are provided, the method including receiving first and second images, modeling a background from the first image, subtracting the background from the second image to provide a detection map, calibrating the size of an object from the pixel level, integrating a projection of the object with the detection map using dynamic programming, and detecting the object in a region if the projection matches that region of the detection map; and the system including a processor, a background modeling unit coupled with the processor for modeling a background from the first image and subtracting the background from the second image to provide a detection map, and a dynamic programming unit coupled with the processor for calibrating the size of... |
| Unit selection module and method for chinese text-to-speech synthesis | 20060095264 | 20060504 |
| This invention relates to a unit selection module for Chinese Text-to-Speech (TTS) synthesis, mainly comprising a probabilistic context free grammar (PCFG) parser, a latent semantic indexing (LSI) module, and a modified variable-length unit selection scheme; any Chinese sentence is firstly input and then parsed into a context-free grammar (CFG) by the PCFG parser; wherein there are several possible CFGs for every Chinese sentence, and the CFG (or the syntactic structure) with the highest probability is then taken as the best CFG (or the syntactic structure) of the Chinese sentence; the LSI module is then used to calculate the structural distance between all the candidate synthesis units and the target unit in a corpus; through the modified variable-length unit selection scheme, tagged with the dynamic programming algorithm,... |
| Detailed placer for optimizing high density cell placement in a linear runtime | 20060090151 | 20060427 |
| A detailed placement process which optimizes cell placement with up to one hundred percent densities in a linear run time. The output from a conjugate-gradient coarse placement process is input to the detailed placement process. A dynamic programming technique is used to optimize cell placement by swapping cells between two or more rows. The search space is pruned beforehand. A greedy cleanup phase using an incremental row placer is used. Thereby, the detailed placement process handles congestion driven placements characterized by non-uniform densities expeditiously and efficiently.
... |
| Method for segmenting audio signals | 20060085188 | 20060420 |
| An input signal is converted to a feature-space representation. The feature-space representation is projected onto a discriminant subspace using a linear discriminant analysis transform to enhance the separation of feature clusters. Dynamic programming is used to find global changes to derive optimal cluster boundaries. The cluster boundaries are used to identify the segments of the audio signal.
... |
| Method and apparatus for estimating pitch of signal | 20060080088 | 20060413 |
| A pitch estimating method and apparatus in which mixture Gaussian distributions based on candidate pitches having high period estimating values are generated, a mixture Gaussian distribution having a high likelihood is selected and dynamic programming is executed so that the pitch of the speech signal can be accurately estimated. The pitch estimating method comprises computing a normalized autocorrelation function of a windowed signal obtained by multiplying a frame of a speech signal by a window signal and determining candidate pitches from a peak value of the normalized autocorrelation function of the windowed signal, interpolating a period of the determined candidate pitches and a period estimating value representing a length of the period, generating Gaussian distributions for the candidate pitches for each frame for which the interpolated... |
